deps/libchdr/deps/zstd-1.5.5/lib/common/bits.h

   1 /*
   2  * Copyright (c) Meta Platforms, Inc. and affiliates.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under both the BSD-style license (found in the
   6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
   7  * in the COPYING file in the root directory of this source tree).
   8  * You may select, at your option, one of the above-listed licenses.
   9  */
  10
  11 #ifndef ZSTD_BITS_H
  12 #define ZSTD_BITS_H
  13
  14 #include "mem.h"
  15
  16 MEM_STATIC unsigned ZSTD_countTrailingZeros32_fallback(U32 val)
  17 {
  18     assert(val != 0);
  19     {
  20         static const U32 DeBruijnBytePos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
  21                                                 30, 22, 20, 15, 25, 17, 4, 8,
  22                                                 31, 27, 13, 23, 21, 19, 16, 7,
  23                                                 26, 12, 18, 6, 11, 5, 10, 9};
  24         return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >> 27];
  25     }
  26 }
  27
  28 MEM_STATIC unsigned ZSTD_countTrailingZeros32(U32 val)
  29 {
  30     assert(val != 0);
  31 #   if defined(_MSC_VER)
  32 #       if STATIC_BMI2 == 1
  33             return (unsigned)_tzcnt_u32(val);
  34 #       else
  35             if (val != 0) {
  36                 unsigned long r;
  37                 _BitScanForward(&r, val);
  38                 return (unsigned)r;
  39             } else {
  40                 /* Should not reach this code path */
  41                 __assume(0);
  42             }
  43 #       endif
  44 #   elif defined(__GNUC__) && (__GNUC__ >= 4)
  45         return (unsigned)__builtin_ctz(val);
  46 #   else
  47         return ZSTD_countTrailingZeros32_fallback(val);
  48 #   endif
  49 }
  50
  51 MEM_STATIC unsigned ZSTD_countLeadingZeros32_fallback(U32 val) {
  52     assert(val != 0);
  53     {
  54         static const U32 DeBruijnClz[32] = {0, 9, 1, 10, 13, 21, 2, 29,
  55                                             11, 14, 16, 18, 22, 25, 3, 30,
  56                                             8, 12, 20, 28, 15, 17, 24, 7,
  57                                             19, 27, 23, 6, 26, 5, 4, 31};
  58         val |= val >> 1;
  59         val |= val >> 2;
  60         val |= val >> 4;
  61         val |= val >> 8;
  62         val |= val >> 16;
  63         return 31 - DeBruijnClz[(val * 0x07C4ACDDU) >> 27];
  64     }
  65 }
  66
  67 MEM_STATIC unsigned ZSTD_countLeadingZeros32(U32 val)
  68 {
  69     assert(val != 0);
  70 #   if defined(_MSC_VER)
  71 #       if STATIC_BMI2 == 1
  72             return (unsigned)_lzcnt_u32(val);
  73 #       else
  74             if (val != 0) {
  75                 unsigned long r;
  76                 _BitScanReverse(&r, val);
  77                 return (unsigned)(31 - r);
  78             } else {
  79                 /* Should not reach this code path */
  80                 __assume(0);
  81             }
  82 #       endif
  83 #   elif defined(__GNUC__) && (__GNUC__ >= 4)
  84         return (unsigned)__builtin_clz(val);
  85 #   else
  86         return ZSTD_countLeadingZeros32_fallback(val);
  87 #   endif
  88 }
  89
  90 MEM_STATIC unsigned ZSTD_countTrailingZeros64(U64 val)
  91 {
  92     assert(val != 0);
  93 #   if defined(_MSC_VER) && defined(_WIN64)
  94 #       if STATIC_BMI2 == 1
  95             return (unsigned)_tzcnt_u64(val);
  96 #       else
  97             if (val != 0) {
  98                 unsigned long r;
  99                 _BitScanForward64(&r, val);
 100                 return (unsigned)r;
 101             } else {
 102                 /* Should not reach this code path */
 103                 __assume(0);
 104             }
 105 #       endif
 106 #   elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(__LP64__)
 107         return (unsigned)__builtin_ctzll(val);
 108 #   else
 109         {
 110             U32 mostSignificantWord = (U32)(val >> 32);
 111             U32 leastSignificantWord = (U32)val;
 112             if (leastSignificantWord == 0) {
 113                 return 32 + ZSTD_countTrailingZeros32(mostSignificantWord);
 114             } else {
 115                 return ZSTD_countTrailingZeros32(leastSignificantWord);
 116             }
 117         }
 118 #   endif
 119 }
 120
 121 MEM_STATIC unsigned ZSTD_countLeadingZeros64(U64 val)
 122 {
 123     assert(val != 0);
 124 #   if defined(_MSC_VER) && defined(_WIN64)
 125 #       if STATIC_BMI2 == 1
 126             return (unsigned)_lzcnt_u64(val);
 127 #       else
 128             if (val != 0) {
 129                 unsigned long r;
 130                 _BitScanReverse64(&r, val);
 131                 return (unsigned)(63 - r);
 132             } else {
 133                 /* Should not reach this code path */
 134                 __assume(0);
 135             }
 136 #       endif
 137 #   elif defined(__GNUC__) && (__GNUC__ >= 4)
 138         return (unsigned)(__builtin_clzll(val));
 139 #   else
 140         {
 141             U32 mostSignificantWord = (U32)(val >> 32);
 142             U32 leastSignificantWord = (U32)val;
 143             if (mostSignificantWord == 0) {
 144                 return 32 + ZSTD_countLeadingZeros32(leastSignificantWord);
 145             } else {
 146                 return ZSTD_countLeadingZeros32(mostSignificantWord);
 147             }
 148         }
 149 #   endif
 150 }
 151
 152 MEM_STATIC unsigned ZSTD_NbCommonBytes(size_t val)
 153 {
 154     if (MEM_isLittleEndian()) {
 155         if (MEM_64bits()) {
 156             return ZSTD_countTrailingZeros64((U64)val) >> 3;
 157         } else {
 158             return ZSTD_countTrailingZeros32((U32)val) >> 3;
 159         }
 160     } else {  /* Big Endian CPU */
 161         if (MEM_64bits()) {
 162             return ZSTD_countLeadingZeros64((U64)val) >> 3;
 163         } else {
 164             return ZSTD_countLeadingZeros32((U32)val) >> 3;
 165         }
 166     }
 167 }
 168
 169 MEM_STATIC unsigned ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
 170 {
 171     assert(val != 0);
 172     return 31 - ZSTD_countLeadingZeros32(val);
 173 }
 174
 175 /* ZSTD_rotateRight_*():
 176  * Rotates a bitfield to the right by "count" bits.
 177  * https://en.wikipedia.org/w/index.php?title=Circular_shift&oldid=991635599#Implementing_circular_shifts
 178  */
 179 MEM_STATIC
 180 U64 ZSTD_rotateRight_U64(U64 const value, U32 count) {
 181     assert(count < 64);
 182     count &= 0x3F; /* for fickle pattern recognition */
 183     return (value >> count) | (U64)(value << ((0U - count) & 0x3F));
 184 }
 185
 186 MEM_STATIC
 187 U32 ZSTD_rotateRight_U32(U32 const value, U32 count) {
 188     assert(count < 32);
 189     count &= 0x1F; /* for fickle pattern recognition */
 190     return (value >> count) | (U32)(value << ((0U - count) & 0x1F));
 191 }
 192
 193 MEM_STATIC
 194 U16 ZSTD_rotateRight_U16(U16 const value, U32 count) {
 195     assert(count < 16);
 196     count &= 0x0F; /* for fickle pattern recognition */
 197     return (value >> count) | (U16)(value << ((0U - count) & 0x0F));
 198 }
 199
 200 #endif /* ZSTD_BITS_H */