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