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 0 && __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   int count = 0;
  51   if (x & 0xffff0000U)
  52     x >>= 16;
  53   else
  54     count += 16;
  55   if (x & 0xff00)
  56     x >>= 8;
  57   else
  58     count += 8;
  59   if (x & 0xf0)
  60     x >>= 4;
  61   else
  62     count += 4;
  63   if (x & 0xc)
  64     x >>= 2;
  65   else
  66     count += 2;
  67   if (x & 2)
  68     x >>= 1;
  69   else
  70     count++;
  71   if (!(x & 1))
  72     count++;
  73   return count;
  74 }
  75 #endif
  76
  77 /* Compute and return the number of leading zeros in X. */
  78 static inline int
  79 count_leading_zeros (unsigned int x)
  80 {
  81   COUNT_LEADING_ZEROS (__builtin_clz, unsigned int);
  82 }
  83
  84 /* Compute and return the number of leading zeros in X. */
  85 static inline int
  86 count_leading_zeros_l (unsigned long int x)
  87 {
  88   COUNT_LEADING_ZEROS (__builtin_clzl, unsigned long int);
  89 }
  90
  91 #if HAVE_UNSIGNED_LONG_LONG_INT
  92 /* Compute and return the number of leading zeros in X. */
  93 static inline int
  94 count_leading_zeros_ll (unsigned long long int x)
  95 {
  96   COUNT_LEADING_ZEROS (__builtin_clzll, unsigned long long int);
  97 }
  98 #endif
  99
 100 #endif /* COUNT_LEADING_ZEROS_H */