1  /* integer_length_l - find most significant bit in an 'unsigned long'.
       2     Copyright (C) 2011-2021 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  }