1: /*
    2:  * Utility compute operations used by translated code.
    3:  *
    4:  * Copyright (c) 2007 Thiemo Seufer
    5:  * Copyright (c) 2007 Jocelyn Mayer
    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: #if defined(__x86_64__)
   27: #define __HAVE_FAST_MULU64__
   28: static always_inline void mulu64 (uint64_t *plow, uint64_t *phigh,
   29:                                   uint64_t a, uint64_t b)
   30: {
   31:     __asm__ ("mul %0\n\t"
   32:              : "=d" (*phigh), "=a" (*plow)
   33:              : "a" (a), "0" (b));
   34: }
   35: #define __HAVE_FAST_MULS64__
   36: static always_inline void muls64 (uint64_t *plow, uint64_t *phigh,
   37:                                   int64_t a, int64_t b)
   38: {
   39:     __asm__ ("imul %0\n\t"
   40:              : "=d" (*phigh), "=a" (*plow)
   41:              : "a" (a), "0" (b));
   42: }
   43: #else
   44: void muls64(uint64_t *phigh, uint64_t *plow, int64_t a, int64_t b);
   45: void mulu64(uint64_t *phigh, uint64_t *plow, uint64_t a, uint64_t b);
   46: #endif
   47: 
   48: /* Note that some of those functions may end up calling libgcc functions,
   49:    depending on the host machine. It is up to the target emulation to
   50:    cope with that. */
   51: 
   52: /* Binary search for leading zeros.  */
   53: 
   54: static always_inline int clz32(uint32_t val)
   55: {
   56:     int cnt = 0;
   57: 
   58:     if (!(val & 0xFFFF0000U)) {
   59:         cnt += 16;
   60:         val <<= 16;
   61:     }
   62:     if (!(val & 0xFF000000U)) {
   63:         cnt += 8;
   64:         val <<= 8;
   65:     }
   66:     if (!(val & 0xF0000000U)) {
   67:         cnt += 4;
   68:         val <<= 4;
   69:     }
   70:     if (!(val & 0xC0000000U)) {
   71:         cnt += 2;
   72:         val <<= 2;
   73:     }
   74:     if (!(val & 0x80000000U)) {
   75:         cnt++;
   76:         val <<= 1;
   77:     }
   78:     if (!(val & 0x80000000U)) {
   79:         cnt++;
   80:     }
   81:     return cnt;
   82: }
   83: 
   84: static always_inline int clo32(uint32_t val)
   85: {
   86:     return clz32(~val);
   87: }
   88: 
   89: static always_inline int clz64(uint64_t val)
   90: {
   91:     int cnt = 0;
   92: 
   93:     if (!(val >> 32)) {
   94:         cnt += 32;
   95:     } else {
   96:         val >>= 32;
   97:     }
   98: 
   99:     return cnt + clz32(val);
  100: }
  101: 
  102: static always_inline int clo64(uint64_t val)
  103: {
  104:     return clz64(~val);
  105: }
  106: 
  107: static always_inline int ctz32 (uint32_t val)
  108: {
  109:     int cnt;
  110: 
  111:     cnt = 0;
  112:     if (!(val & 0x0000FFFFUL)) {
  113:          cnt += 16;
  114:         val >>= 16;
  115:      }
  116:     if (!(val & 0x000000FFUL)) {
  117:          cnt += 8;
  118:         val >>= 8;
  119:      }
  120:     if (!(val & 0x0000000FUL)) {
  121:          cnt += 4;
  122:         val >>= 4;
  123:      }
  124:     if (!(val & 0x00000003UL)) {
  125:          cnt += 2;
  126:         val >>= 2;
  127:      }
  128:     if (!(val & 0x00000001UL)) {
  129:          cnt++;
  130:         val >>= 1;
  131:      }
  132:     if (!(val & 0x00000001UL)) {
  133:          cnt++;
  134:      }
  135: 
  136:      return cnt;
  137:  }
  138:  
  139: static always_inline int cto32 (uint32_t val)
  140:  {
  141:     return ctz32(~val);
  142: }
  143: 
  144: static always_inline int ctz64 (uint64_t val)
  145: {
  146:     int cnt;
  147: 
  148:     cnt = 0;
  149:     if (!((uint32_t)val)) {
  150:         cnt += 32;
  151:         val >>= 32;
  152:     }
  153: 
  154:     return cnt + ctz32(val);
  155: }
  156: 
  157: static always_inline int cto64 (uint64_t val)
  158: {
  159:     return ctz64(~val);
  160: }
  161: 
  162: static always_inline int ctpop8 (uint8_t val)
  163: {
  164:     val = (val & 0x55) + ((val >> 1) & 0x55);
  165:     val = (val & 0x33) + ((val >> 2) & 0x33);
  166:     val = (val & 0x0f) + ((val >> 4) & 0x0f);
  167: 
  168:     return val;
  169: }
  170: 
  171: static always_inline int ctpop16 (uint16_t val)
  172: {
  173:     val = (val & 0x5555) + ((val >> 1) & 0x5555);
  174:     val = (val & 0x3333) + ((val >> 2) & 0x3333);
  175:     val = (val & 0x0f0f) + ((val >> 4) & 0x0f0f);
  176:     val = (val & 0x00ff) + ((val >> 8) & 0x00ff);
  177: 
  178:     return val;
  179: }
  180: 
  181: static always_inline int ctpop32 (uint32_t val)
  182: {
  183:     val = (val & 0x55555555) + ((val >>  1) & 0x55555555);
  184:     val = (val & 0x33333333) + ((val >>  2) & 0x33333333);
  185:     val = (val & 0x0f0f0f0f) + ((val >>  4) & 0x0f0f0f0f);
  186:     val = (val & 0x00ff00ff) + ((val >>  8) & 0x00ff00ff);
  187:     val = (val & 0x0000ffff) + ((val >> 16) & 0x0000ffff);
  188: 
  189:     return val;
  190: }
  191: 
  192: static always_inline int ctpop64 (uint64_t val)
  193: {
  194:     val = (val & 0x5555555555555555ULL) + ((val >>  1) & 0x5555555555555555ULL);
  195:     val = (val & 0x3333333333333333ULL) + ((val >>  2) & 0x3333333333333333ULL);
  196:     val = (val & 0x0f0f0f0f0f0f0f0fULL) + ((val >>  4) & 0x0f0f0f0f0f0f0f0fULL);
  197:     val = (val & 0x00ff00ff00ff00ffULL) + ((val >>  8) & 0x00ff00ff00ff00ffULL);
  198:     val = (val & 0x0000ffff0000ffffULL) + ((val >> 16) & 0x0000ffff0000ffffULL);
  199:     val = (val & 0x00000000ffffffffULL) + ((val >> 32) & 0x00000000ffffffffULL);
  200: 
  201:     return val;
  202: }