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