lib/count-leading-zeros.h

   1 /* count-leading-zeros.h -- counts the number of leading 0 bits in a word.
   2    Copyright (C) 2012-2013 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 #ifndef _GL_INLINE_HEADER_BEGIN
  27  #error "Please include config.h first."
  28 #endif
  29 _GL_INLINE_HEADER_BEGIN
  30 #ifndef COUNT_LEADING_ZEROS_INLINE
  31 # define COUNT_LEADING_ZEROS_INLINE _GL_INLINE
  32 #endif
  33
  34 /* Expand the code which computes the number of leading zeros of the local
  35    variable 'x' of type TYPE (an unsigned integer type) and returns it
  36    from the current function.  */
  37 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  38 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE)     \
  39   return x ? BUILTIN (x) : CHAR_BIT * sizeof x;
  40 #else
  41 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE)                             \
  42   /* This condition is written so as to avoid shifting by more than     \
  43      31 bits at once, and also avoids a random HP-UX cc bug.  */        \
  44   verify (((TYPE) -1 >> 31 >> 31 >> 2) == 0); /* TYPE has at most 64 bits */ \
  45   int count = 0;                                                        \
  46   if (1 < (TYPE) -1 >> 31) { /* TYPE has more than 32 bits? */          \
  47     count = count_leading_zeros_32 (x >> 31 >> 1);                      \
  48     if (count < 32)                                                     \
  49       return count;                                                     \
  50   }                                                                     \
  51   return count + count_leading_zeros_32 (x);
  52
  53 /* Compute and return the number of leading zeros in the least
  54    significant 32 bits of X. */
  55 COUNT_LEADING_ZEROS_INLINE int
  56 count_leading_zeros_32 (unsigned int x)
  57 {
  58   /* http://graphics.stanford.edu/~seander/bithacks.html */
  59   static const char deBruijnLookup[32] = {
  60     0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  61     8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
  62   };
  63
  64   x &= 0xffffffffU;
  65   if (!x)
  66     return 32;
  67   x |= x >> 1;
  68   x |= x >> 2;
  69   x |= x >> 4;
  70   x |= x >> 8;
  71   x |= x >> 16;
  72   return 31 - deBruijnLookup[(x * 0x07c4acddU) >> 27];
  73 }
  74 #endif
  75
  76 /* Compute and return the number of leading zeros in X. */
  77 COUNT_LEADING_ZEROS_INLINE int
  78 count_leading_zeros (unsigned int x)
  79 {
  80   COUNT_LEADING_ZEROS (__builtin_clz, unsigned int);
  81 }
  82
  83 /* Compute and return the number of leading zeros in X. */
  84 COUNT_LEADING_ZEROS_INLINE int
  85 count_leading_zeros_l (unsigned long int x)
  86 {
  87   COUNT_LEADING_ZEROS (__builtin_clzl, unsigned long int);
  88 }
  89
  90 #if HAVE_UNSIGNED_LONG_LONG_INT
  91 /* Compute and return the number of leading zeros in X. */
  92 COUNT_LEADING_ZEROS_INLINE int
  93 count_leading_zeros_ll (unsigned long long int x)
  94 {
  95   COUNT_LEADING_ZEROS (__builtin_clzll, unsigned long long int);
  96 }
  97 #endif
  98
  99 _GL_INLINE_HEADER_END
 100
 101 #endif /* COUNT_LEADING_ZEROS_H */