util/host-utils.c

   1 /*
   2  * Utility compute operations used by translated code.
   3  *
   4  * Copyright (c) 2003 Fabrice Bellard
   5  * Copyright (c) 2007 Aurelien Jarno
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  20  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  */
  25
  26 #include <stdlib.h>
  27 #include <stdint.h>
  28 #include "qemu/host-utils.h"
  29
  30 /* Long integer helpers */
  31 #ifndef CONFIG_INT128
  32 static inline void mul64(uint64_t *plow, uint64_t *phigh,
  33                          uint64_t a, uint64_t b)
  34 {
  35     typedef union {
  36         uint64_t ll;
  37         struct {
  38 #ifdef HOST_WORDS_BIGENDIAN
  39             uint32_t high, low;
  40 #else
  41             uint32_t low, high;
  42 #endif
  43         } l;
  44     } LL;
  45     LL rl, rm, rn, rh, a0, b0;
  46     uint64_t c;
  47
  48     a0.ll = a;
  49     b0.ll = b;
  50
  51     rl.ll = (uint64_t)a0.l.low * b0.l.low;
  52     rm.ll = (uint64_t)a0.l.low * b0.l.high;
  53     rn.ll = (uint64_t)a0.l.high * b0.l.low;
  54     rh.ll = (uint64_t)a0.l.high * b0.l.high;
  55
  56     c = (uint64_t)rl.l.high + rm.l.low + rn.l.low;
  57     rl.l.high = c;
  58     c >>= 32;
  59     c = c + rm.l.high + rn.l.high + rh.l.low;
  60     rh.l.low = c;
  61     rh.l.high += (uint32_t)(c >> 32);
  62
  63     *plow = rl.ll;
  64     *phigh = rh.ll;
  65 }
  66
  67 /* Unsigned 64x64 -> 128 multiplication */
  68 void mulu64 (uint64_t *plow, uint64_t *phigh, uint64_t a, uint64_t b)
  69 {
  70     mul64(plow, phigh, a, b);
  71 }
  72
  73 /* Signed 64x64 -> 128 multiplication */
  74 void muls64 (uint64_t *plow, uint64_t *phigh, int64_t a, int64_t b)
  75 {
  76     uint64_t rh;
  77
  78     mul64(plow, &rh, a, b);
  79
  80     /* Adjust for signs.  */
  81     if (b < 0) {
  82         rh -= a;
  83     }
  84     if (a < 0) {
  85         rh -= b;
  86     }
  87     *phigh = rh;
  88 }
  89
  90 /* Unsigned 128x64 division.  Returns 1 if overflow (divide by zero or */
  91 /* quotient exceeds 64 bits).  Otherwise returns quotient via plow and */
  92 /* remainder via phigh. */
  93 int divu128(uint64_t *plow, uint64_t *phigh, uint64_t divisor)
  94 {
  95     uint64_t dhi = *phigh;
  96     uint64_t dlo = *plow;
  97     unsigned i;
  98     uint64_t carry = 0;
  99
 100     if (divisor == 0) {
 101         return 1;
 102     } else if (dhi == 0) {
 103         *plow  = dlo / divisor;
 104         *phigh = dlo % divisor;
 105         return 0;
 106     } else if (dhi > divisor) {
 107         return 1;
 108     } else {
 109
 110         for (i = 0; i < 64; i++) {
 111             carry = dhi >> 63;
 112             dhi = (dhi << 1) | (dlo >> 63);
 113             if (carry || (dhi >= divisor)) {
 114                 dhi -= divisor;
 115                 carry = 1;
 116             } else {
 117                 carry = 0;
 118             }
 119             dlo = (dlo << 1) | carry;
 120         }
 121
 122         *plow = dlo;
 123         *phigh = dhi;
 124         return 0;
 125     }
 126 }
 127
 128 int divs128(int64_t *plow, int64_t *phigh, int64_t divisor)
 129 {
 130     int sgn_dvdnd = *phigh < 0;
 131     int sgn_divsr = divisor < 0;
 132     int overflow = 0;
 133
 134     if (sgn_dvdnd) {
 135         *plow = ~(*plow);
 136         *phigh = ~(*phigh);
 137         if (*plow == (int64_t)-1) {
 138             *plow = 0;
 139             (*phigh)++;
 140          } else {
 141             (*plow)++;
 142          }
 143     }
 144
 145     if (sgn_divsr) {
 146         divisor = 0 - divisor;
 147     }
 148
 149     overflow = divu128((uint64_t *)plow, (uint64_t *)phigh, (uint64_t)divisor);
 150
 151     if (sgn_dvdnd  ^ sgn_divsr) {
 152         *plow = 0 - *plow;
 153     }
 154
 155     if (!overflow) {
 156         if ((*plow < 0) ^ (sgn_dvdnd ^ sgn_divsr)) {
 157             overflow = 1;
 158         }
 159     }
 160
 161     return overflow;
 162 }
 163
 164 #endif /* !CONFIG_INT128 */