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