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
  37 #define ROUND(v, a, w)                      \
  38     do {                                    \
  39         if (v & (((1 << w) - 1) << w)) {    \
  40             a  += w;                        \
  41             v >>= w;                        \
  42         }                                   \
  43     } while (0)
  44
  45
  46 #if defined(__GNUC__) && defined(__x86_64__)
  47
  48 int ilog2_32(uint32_t v)
  49 {
  50     int n;
  51
  52     __asm__("bsrl %1,%0"
  53             : "=r" (n)
  54             : "rm" (v), "0" (0));
  55     return n;
  56 }
  57
  58 #elif defined(__GNUC__) && defined(__i386__)
  59
  60 int ilog2_32(uint32_t v)
  61 {
  62     int n;
  63
  64     __asm__("bsrl %1,%0 ; jnz 1f ; xorl %0,%0\n"
  65             "1:"
  66             : "=&r" (n)
  67             : "rm" (v));
  68     return n;
  69 }
  70
  71 #elif defined(HAVE___BUILTIN_CTZ) && INT_MAX >= 2147483647
  72
  73 int ilog2_32(uint32_t v)
  74 {
  75     if (!v)
  76         return 0;
  77
  78     return __builtin_clz(v) ^ 31;
  79 }
  80
  81 #else
  82
  83 int ilog2_32(uint32_t v)
  84 {
  85     int p = 0;
  86
  87     ROUND(v, p, 16);
  88     ROUND(v, p,  8);
  89     ROUND(v, p,  4);
  90     ROUND(v, p,  2);
  91     ROUND(v, p,  1);
  92
  93     return p;
  94 }
  95
  96 #endif
  97
  98 #if defined(__GNUC__) && defined(__x86_64__)
  99
 100 int ilog2_64(uint64_t v)
 101 {
 102     uint64_t n;
 103
 104     __asm__("bsrq %1,%0"
 105             : "=r" (n)
 106             : "rm" (v), "0" (UINT64_C(0)));
 107     return n;
 108 }
 109
 110 #elif defined(HAVE__BUILTIN_CTZLL) && LLONG_MAX >= 9223372036854775807L
 111
 112 int ilog2_64(uint64_t v)
 113 {
 114     if (!v)
 115         return 0;
 116
 117     return __builtin_clzll(v) ^ 63;
 118 }
 119
 120 #else
 121
 122 int ilog2_64(uint64_t vv)
 123 {
 124     int p = 0;
 125     uint32_t v;
 126
 127     v = vv >> 32;
 128     if (v)
 129         p += 32;
 130     else
 131         v = vv;
 132
 133     ROUND(v, p, 16);
 134     ROUND(v, p,  8);
 135     ROUND(v, p,  4);
 136     ROUND(v, p,  2);
 137     ROUND(v, p,  1);
 138
 139     return p;
 140 }
 141
 142 #endif
 143
 144 /*
 145  * v == 0 ? 0 : is_power2(x) ? ilog2_X(v) : -1
 146  */
 147 int alignlog2_32(uint32_t v)
 148 {
 149     if (unlikely(v & (v-1)))
 150         return -1;              /* invalid alignment */
 151
 152     return ilog2_32(v);
 153 }
 154
 155 int alignlog2_64(uint64_t v)
 156 {
 157     if (unlikely(v & (v-1)))
 158         return -1;              /* invalid alignment */
 159
 160     return ilog2_64(v);
 161 }