lib/integer_length_l.c

   1 /* integer_length_l - find most significant bit in an 'unsigned long'.
   2    Copyright (C) 2011-2014 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 Bruno Haible <bruno@clisp.org>, 2011.  */
  18
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include "integer_length.h"
  23
  24 #include <limits.h>
  25 #include <stddef.h>
  26
  27 #undef MIN
  28 #define MIN(a,b) ((a) < (b) ? (a) : (b))
  29
  30 #ifdef USE_LONG_LONG
  31 # define FUNC integer_length_ll
  32 # define TYPE unsigned long long
  33 # define GCC_BUILTIN __builtin_clzll
  34 #else
  35 # define FUNC integer_length_l
  36 # define TYPE unsigned long
  37 # define GCC_BUILTIN __builtin_clzl
  38 #endif
  39
  40 #define NBITS (sizeof (TYPE) * CHAR_BIT)
  41
  42 /* Modify shift count to be in bounds, even in dead code, otherwise GCC
  43    emits warnings "right shift count >= width of type".  */
  44 #define MSC(i) MIN (i, NBITS - 1)
  45
  46 int
  47 FUNC (TYPE x)
  48 {
  49 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  50   if (x == 0)
  51     return 0;
  52   else
  53     return NBITS - GCC_BUILTIN (x);
  54 #else
  55   /* Split x into chunks, and look at one chunk after the other.  */
  56   if (sizeof (TYPE) > 2 * sizeof (unsigned int))
  57     {
  58       /* Generic loop.  */
  59       size_t i;
  60
  61       for (i = (sizeof (TYPE) - 1) / sizeof (unsigned int); i >= 2; i--)
  62         {
  63           unsigned int y = x >> (i * sizeof (unsigned int) * CHAR_BIT);
  64           if (y != 0)
  65             return i * sizeof (unsigned int) * CHAR_BIT + integer_length (y);
  66         }
  67     }
  68
  69   /* Unrolled the last 2 loop rounds.  */
  70   /* i = 1 */
  71   if (sizeof (TYPE) > 1 * sizeof (unsigned int))
  72     {
  73       unsigned int y = x >> MSC (1 * sizeof (unsigned int) * CHAR_BIT);
  74       if (y != 0)
  75         return 1 * sizeof (unsigned int) * CHAR_BIT + integer_length (y);
  76     }
  77
  78   /* i = 0 */
  79   return integer_length ((unsigned int) x);
  80 #endif
  81 }