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