include/ilog2.h

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2017 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 #ifndef ILOG2_H
  35 #define ILOG2_H
  36
  37 #include "compiler.h"
  38 #include <limits.h>
  39
  40 #ifdef ILOG2_C                  /* For generating the out-of-line functions */
  41 # undef extern_inline
  42 # define extern_inline
  43 # define inline_prototypes
  44 #endif
  45
  46 #ifdef inline_prototypes
  47 extern unsigned int const_func ilog2_32(uint32_t v);
  48 extern unsigned int const_func ilog2_64(uint64_t v);
  49 extern unsigned int const_func ilog2_64(uint64_t vv);
  50 extern int const_func alignlog2_32(uint32_t v);
  51 extern int const_func alignlog2_64(uint64_t v);
  52 #endif
  53
  54 #ifdef extern_inline
  55
  56 #define ROUND(v, a, w)                                  \
  57     do {                                                \
  58         if (v & (((UINT32_C(1) << w) - 1) << w)) {      \
  59             a  += w;                                    \
  60             v >>= w;                                    \
  61         }                                               \
  62     } while (0)
  63
  64
  65 #if defined(HAVE___BUILTIN_CLZ) && INT_MAX == 2147483647
  66
  67 extern_inline unsigned int const_func ilog2_32(uint32_t v)
  68 {
  69     if (!v)
  70         return 0;
  71
  72     return __builtin_clz(v) ^ 31;
  73 }
  74
  75 #elif defined(__GNUC__) && defined(__x86_64__)
  76
  77 extern_inline unsigned int const_func ilog2_32(uint32_t v)
  78 {
  79     unsigned int n;
  80
  81     __asm__("bsrl %1,%0"
  82             : "=r" (n)
  83             : "rm" (v), "0" (0));
  84     return n;
  85 }
  86
  87 #elif defined(__GNUC__) && defined(__i386__)
  88
  89 extern_inline unsigned int const_func ilog2_32(uint32_t v)
  90 {
  91     unsigned int n;
  92
  93 #ifdef __i686__
  94     __asm__("bsrl %1,%0 ; cmovz %2,%0\n"
  95             : "=&r" (n)
  96             : "rm" (v), "r" (0));
  97 #else
  98     __asm__("bsrl %1,%0 ; jnz 1f ; xorl %0,%0\n"
  99             "1:"
 100             : "=&r" (n)
 101             : "rm" (v));
 102 #endif
 103      return n;
 104 }
 105
 106 #elif defined(HAVE__BITSCANREVERSE)
 107
 108 extern_inline unsigned int const_func ilog2_32(uint32_t v)
 109 {
 110     unsigned long ix;
 111     return _BitScanReverse(&ix, v) ? v : 0;
 112 }
 113
 114 #else
 115
 116 extern_inline unsigned int const_func ilog2_32(uint32_t v)
 117 {
 118     unsigned int p = 0;
 119
 120     ROUND(v, p, 16);
 121     ROUND(v, p,  8);
 122     ROUND(v, p,  4);
 123     ROUND(v, p,  2);
 124     ROUND(v, p,  1);
 125
 126     return p;
 127 }
 128
 129 #endif
 130
 131 #if defined(HAVE__BUILTIN_CLZLL) && LLONG_MAX == 9223372036854775807LL
 132
 133 extern_inline unsigned int const_func ilog2_64(uint64_t v)
 134 {
 135     if (!v)
 136         return 0;
 137
 138     return __builtin_clzll(v) ^ 63;
 139 }
 140
 141 #elif defined(__GNUC__) && defined(__x86_64__)
 142
 143 extern_inline unsigned int const_func ilog2_64(uint64_t v)
 144 {
 145     uint64_t n;
 146
 147     __asm__("bsrq %1,%0"
 148             : "=r" (n)
 149             : "rm" (v), "0" (UINT64_C(0)));
 150     return n;
 151 }
 152
 153 #elif defined(HAVE__BITSCANREVERSE64)
 154
 155 extern_inline unsigned int const_func ilog2_64(uint64_t v)
 156 {
 157     unsigned long ix;
 158     return _BitScanReverse64(&ix, v) ? ix : 0;
 159 }
 160
 161 #else
 162
 163 extern_inline unsigned int const_func ilog2_64(uint64_t vv)
 164 {
 165     unsigned int p = 0;
 166     uint32_t v;
 167
 168     v = vv >> 32;
 169     if (v)
 170         p += 32;
 171     else
 172         v = vv;
 173
 174     return p + ilog2_32(v);
 175 }
 176
 177 #endif
 178
 179 /*
 180  * v == 0 ? 0 : is_power2(x) ? ilog2_X(v) : -1
 181  */
 182 extern_inline int const_func alignlog2_32(uint32_t v)
 183 {
 184     if (unlikely(v & (v-1)))
 185         return -1;              /* invalid alignment */
 186
 187     return ilog2_32(v);
 188 }
 189
 190 extern_inline int const_func alignlog2_64(uint64_t v)
 191 {
 192     if (unlikely(v & (v-1)))
 193         return -1;              /* invalid alignment */
 194
 195     return ilog2_64(v);
 196 }
 197
 198 #undef ROUND
 199
 200 #endif /* extern_inline */
 201
 202 #endif /* ILOG2_H */