lib/integer_length_l.c

   1 /* integer_length_l - find most significant bit in an 'unsigned long'.
   2    Copyright (C) 2011-2024 Free Software Foundation, Inc.
   3
   4    This file is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU Lesser General Public License as
   6    published by the Free Software Foundation; either version 2.1 of the
   7    License, or (at your option) any later version.
   8
   9    This file 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 Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public License
  15    along with this program.  If not, see <https://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 # ifdef _WIN64
  35 #  define MSVC_BUILTIN _BitScanReverse64
  36 # endif
  37 #else
  38 # define FUNC integer_length_l
  39 # define TYPE unsigned long
  40 # define GCC_BUILTIN __builtin_clzl
  41 # define MSVC_BUILTIN _BitScanReverse
  42 #endif
  43
  44 #if defined _MSC_VER && !(__clang_major__ >= 4)
  45 # include <intrin.h>
  46 /* Copied from integer_length.c.  */
  47 static inline int
  48 integer_length (unsigned int x)
  49 {
  50   /* _BitScanReverse
  51      <https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64> */
  52   unsigned long bit;
  53   if (_BitScanReverse (&bit, x))
  54     return bit + 1;
  55   else
  56     return 0;
  57 }
  58 #endif
  59
  60 #define NBITS (sizeof (TYPE) * CHAR_BIT)
  61
  62 /* Modify shift count to be in bounds, even in dead code, otherwise GCC
  63    emits warnings "right shift count >= width of type".  */
  64 #define MSC(i) MIN (i, NBITS - 1)
  65
  66 int
  67 FUNC (TYPE x)
  68 {
  69 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__clang_major__ >= 4)
  70   if (x == 0)
  71     return 0;
  72   else
  73     return NBITS - GCC_BUILTIN (x);
  74 #elif defined _MSC_VER && defined MSVC_BUILTIN
  75   /* _BitScanReverse, _BitScanReverse64
  76      <https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64> */
  77   unsigned long bit;
  78   if (MSVC_BUILTIN (&bit, x))
  79     return bit + 1;
  80   else
  81     return 0;
  82 #else
  83   /* Split x into chunks, and look at one chunk after the other.  */
  84   if (sizeof (TYPE) > 2 * sizeof (unsigned int))
  85     {
  86       /* Generic loop.  */
  87       size_t i;
  88
  89       for (i = (sizeof (TYPE) - 1) / sizeof (unsigned int); i >= 2; i--)
  90         {
  91           unsigned int y = x >> (i * sizeof (unsigned int) * CHAR_BIT);
  92           if (y != 0)
  93             return i * sizeof (unsigned int) * CHAR_BIT + integer_length (y);
  94         }
  95     }
  96
  97   /* Unrolled the last 2 loop rounds.  */
  98   /* i = 1 */
  99   if (sizeof (TYPE) > 1 * sizeof (unsigned int))
 100     {
 101       unsigned int y = x >> MSC (1 * sizeof (unsigned int) * CHAR_BIT);
 102       if (y != 0)
 103         return 1 * sizeof (unsigned int) * CHAR_BIT + integer_length (y);
 104     }
 105
 106   /* i = 0 */
 107   return integer_length ((unsigned int) x);
 108 #endif
 109 }