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