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 */ 201