lib/count-leading-zeros.h

   1 /* count-leading-zeros.h -- counts the number of leading 0 bits in a word.
   2    Copyright (C) 2012 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Eric Blake.  */
  18
  19 #ifndef COUNT_LEADING_ZEROS_H
  20 # define COUNT_LEADING_ZEROS_H 1
  21
  22 #include <limits.h>
  23 #include <stdlib.h>
  24 #include "verify.h"
  25
  26 _GL_INLINE_HEADER_BEGIN
  27 #ifndef COUNT_LEADING_ZEROS_INLINE
  28 # define COUNT_LEADING_ZEROS_INLINE _GL_INLINE
  29 #endif
  30
  31 /* Expand the code which computes the number of leading zeros of the local
  32    variable 'x' of type TYPE (an unsigned integer type) and returns it
  33    from the current function.  */
  34 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  35 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE)     \
  36   return x ? BUILTIN (x) : CHAR_BIT * sizeof x;
  37 #else
  38 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE)                             \
  39   /* This condition is written so as to avoid shifting by more than     \
  40      31 bits at once, and also avoids a random HP-UX cc bug.  */        \
  41   verify (((TYPE) -1 >> 31 >> 31 >> 2) == 0); /* TYPE has at most 64 bits */ \
  42   int count = 0;                                                        \
  43   if (1 < (TYPE) -1 >> 31) { /* TYPE has more than 32 bits? */          \
  44     count = count_leading_zeros_32 (x >> 31 >> 1);                      \
  45     if (count < 32)                                                     \
  46       return count;                                                     \
  47   }                                                                     \
  48   return count + count_leading_zeros_32 (x);
  49
  50 /* Compute and return the number of leading zeros in the least
  51    significant 32 bits of X. */
  52 COUNT_LEADING_ZEROS_INLINE int
  53 count_leading_zeros_32 (unsigned int x)
  54 {
  55   /* http://graphics.stanford.edu/~seander/bithacks.html */
  56   static const char deBruijnLookup[32] = {
  57     0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  58     8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
  59   };
  60
  61   x &= 0xffffffffU;
  62   if (!x)
  63     return 32;
  64   x |= x >> 1;
  65   x |= x >> 2;
  66   x |= x >> 4;
  67   x |= x >> 8;
  68   x |= x >> 16;
  69   return 31 - deBruijnLookup[(x * 0x07c4acddU) >> 27];
  70 }
  71 #endif
  72
  73 /* Compute and return the number of leading zeros in X. */
  74 COUNT_LEADING_ZEROS_INLINE int
  75 count_leading_zeros (unsigned int x)
  76 {
  77   COUNT_LEADING_ZEROS (__builtin_clz, unsigned int);
  78 }
  79
  80 /* Compute and return the number of leading zeros in X. */
  81 COUNT_LEADING_ZEROS_INLINE int
  82 count_leading_zeros_l (unsigned long int x)
  83 {
  84   COUNT_LEADING_ZEROS (__builtin_clzl, unsigned long int);
  85 }
  86
  87 #if HAVE_UNSIGNED_LONG_LONG_INT
  88 /* Compute and return the number of leading zeros in X. */
  89 COUNT_LEADING_ZEROS_INLINE int
  90 count_leading_zeros_ll (unsigned long long int x)
  91 {
  92   COUNT_LEADING_ZEROS (__builtin_clzll, unsigned long long int);
  93 }
  94 #endif
  95
  96 _GL_INLINE_HEADER_END
  97
  98 #endif /* COUNT_LEADING_ZEROS_H */