2 * Copyright (c) Meta Platforms, Inc. and affiliates.
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.
16 MEM_STATIC unsigned ZSTD_countTrailingZeros32_fallback(U32 val)
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];
28 MEM_STATIC unsigned ZSTD_countTrailingZeros32(U32 val)
31 # if defined(_MSC_VER)
33 return (unsigned)_tzcnt_u32(val);
37 _BitScanForward(&r, val);
40 /* Should not reach this code path */
44 # elif defined(__GNUC__) && (__GNUC__ >= 4)
45 return (unsigned)__builtin_ctz(val);
47 return ZSTD_countTrailingZeros32_fallback(val);
51 MEM_STATIC unsigned ZSTD_countLeadingZeros32_fallback(U32 val) {
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};
63 return 31 - DeBruijnClz[(val * 0x07C4ACDDU) >> 27];
67 MEM_STATIC unsigned ZSTD_countLeadingZeros32(U32 val)
70 # if defined(_MSC_VER)
72 return (unsigned)_lzcnt_u32(val);
76 _BitScanReverse(&r, val);
77 return (unsigned)(31 - r);
79 /* Should not reach this code path */
83 # elif defined(__GNUC__) && (__GNUC__ >= 4)
84 return (unsigned)__builtin_clz(val);
86 return ZSTD_countLeadingZeros32_fallback(val);
90 MEM_STATIC unsigned ZSTD_countTrailingZeros64(U64 val)
93 # if defined(_MSC_VER) && defined(_WIN64)
95 return (unsigned)_tzcnt_u64(val);
99 _BitScanForward64(&r, val);
102 /* Should not reach this code path */
106 # elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(__LP64__)
107 return (unsigned)__builtin_ctzll(val);
110 U32 mostSignificantWord = (U32)(val >> 32);
111 U32 leastSignificantWord = (U32)val;
112 if (leastSignificantWord == 0) {
113 return 32 + ZSTD_countTrailingZeros32(mostSignificantWord);
115 return ZSTD_countTrailingZeros32(leastSignificantWord);
121 MEM_STATIC unsigned ZSTD_countLeadingZeros64(U64 val)
124 # if defined(_MSC_VER) && defined(_WIN64)
125 # if STATIC_BMI2 == 1
126 return (unsigned)_lzcnt_u64(val);
130 _BitScanReverse64(&r, val);
131 return (unsigned)(63 - r);
133 /* Should not reach this code path */
137 # elif defined(__GNUC__) && (__GNUC__ >= 4)
138 return (unsigned)(__builtin_clzll(val));
141 U32 mostSignificantWord = (U32)(val >> 32);
142 U32 leastSignificantWord = (U32)val;
143 if (mostSignificantWord == 0) {
144 return 32 + ZSTD_countLeadingZeros32(leastSignificantWord);
146 return ZSTD_countLeadingZeros32(mostSignificantWord);
152 MEM_STATIC unsigned ZSTD_NbCommonBytes(size_t val)
154 if (MEM_isLittleEndian()) {
156 return ZSTD_countTrailingZeros64((U64)val) >> 3;
158 return ZSTD_countTrailingZeros32((U32)val) >> 3;
160 } else { /* Big Endian CPU */
162 return ZSTD_countLeadingZeros64((U64)val) >> 3;
164 return ZSTD_countLeadingZeros32((U32)val) >> 3;
169 MEM_STATIC unsigned ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */
172 return 31 - ZSTD_countLeadingZeros32(val);
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
180 U64 ZSTD_rotateRight_U64(U64 const value, U32 count) {
182 count &= 0x3F; /* for fickle pattern recognition */
183 return (value >> count) | (U64)(value << ((0U - count) & 0x3F));
187 U32 ZSTD_rotateRight_U32(U32 const value, U32 count) {
189 count &= 0x1F; /* for fickle pattern recognition */
190 return (value >> count) | (U32)(value << ((0U - count) & 0x1F));
194 U16 ZSTD_rotateRight_U16(U16 const value, U32 count) {
196 count &= 0x0F; /* for fickle pattern recognition */
197 return (value >> count) | (U16)(value << ((0U - count) & 0x0F));
200 #endif /* ZSTD_BITS_H */