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