nasmlib/ilog2.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2016 The NASM Authors - All Rights Reserved
   4  *   See the file AUTHORS included with the NASM distribution for
   5  *   the specific copyright holders.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following
   9  *   conditions are met:
  10  *
  11  *   * Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  *   * Redistributions in binary form must reproduce the above
  14  *     copyright notice, this list of conditions and the following
  15  *     disclaimer in the documentation and/or other materials provided
  16  *     with the distribution.
  17  *
  18  *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  19  *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21  *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28  *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  29  *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  30  *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  *
  32  * ----------------------------------------------------------------------- */
  33
  34 #include "compiler.h"
  35 #include "nasmlib.h"
  36 #include <limits.h>
  37
  38 #define ROUND(v, a, w)                      \
  39     do {                                    \
  40         if (v & (((1 << w) - 1) << w)) {    \
  41             a  += w;                        \
  42             v >>= w;                        \
  43         }                                   \
  44     } while (0)
  45
  46
  47 #if defined(__GNUC__) && defined(__x86_64__)
  48
  49 int ilog2_32(uint32_t v)
  50 {
  51     int n;
  52
  53     __asm__("bsrl %1,%0"
  54             : "=r" (n)
  55             : "rm" (v), "0" (0));
  56     return n;
  57 }
  58
  59 #elif defined(__GNUC__) && defined(__i386__)
  60
  61 int ilog2_32(uint32_t v)
  62 {
  63     int n;
  64
  65 #ifdef __i686__
  66     __asm__("bsrl %1,%0 ; cmovz %2,%0\n"
  67             : "=&r" (n)
  68             : "rm" (v), "r" (0));
  69 #else
  70     __asm__("bsrl %1,%0 ; jnz 1f ; xorl %0,%0\n"
  71             "1:"
  72             : "=&r" (n)
  73             : "rm" (v));
  74 #endif
  75      return n;
  76 }
  77
  78 #elif defined(HAVE___BUILTIN_CLZ) && INT_MAX == 2147483647
  79
  80 int ilog2_32(uint32_t v)
  81 {
  82     if (!v)
  83         return 0;
  84
  85     return __builtin_clz(v) ^ 31;
  86 }
  87
  88 #else
  89
  90 int ilog2_32(uint32_t v)
  91 {
  92     int p = 0;
  93
  94     ROUND(v, p, 16);
  95     ROUND(v, p,  8);
  96     ROUND(v, p,  4);
  97     ROUND(v, p,  2);
  98     ROUND(v, p,  1);
  99
 100     return p;
 101 }
 102
 103 #endif
 104
 105 #if defined(__GNUC__) && defined(__x86_64__)
 106
 107 int ilog2_64(uint64_t v)
 108 {
 109     uint64_t n;
 110
 111     __asm__("bsrq %1,%0"
 112             : "=r" (n)
 113             : "rm" (v), "0" (UINT64_C(0)));
 114     return n;
 115 }
 116
 117 #elif defined(HAVE__BUILTIN_CLZLL) && LLONG_MAX == 9223372036854775807LL
 118
 119 int ilog2_64(uint64_t v)
 120 {
 121     if (!v)
 122         return 0;
 123
 124     return __builtin_clzll(v) ^ 63;
 125 }
 126
 127 #else
 128
 129 int ilog2_64(uint64_t vv)
 130 {
 131     int p = 0;
 132     uint32_t v;
 133
 134     v = vv >> 32;
 135     if (v)
 136         p += 32;
 137     else
 138         v = vv;
 139
 140     ROUND(v, p, 16);
 141     ROUND(v, p,  8);
 142     ROUND(v, p,  4);
 143     ROUND(v, p,  2);
 144     ROUND(v, p,  1);
 145
 146     return p;
 147 }
 148
 149 #endif
 150
 151 /*
 152  * v == 0 ? 0 : is_power2(x) ? ilog2_X(v) : -1
 153  */
 154 int alignlog2_32(uint32_t v)
 155 {
 156     if (unlikely(v & (v-1)))
 157         return -1;              /* invalid alignment */
 158
 159     return ilog2_32(v);
 160 }
 161
 162 int alignlog2_64(uint64_t v)
 163 {
 164     if (unlikely(v & (v-1)))
 165         return -1;              /* invalid alignment */
 166
 167     return ilog2_64(v);
 168 }