ilog2.c

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