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
ZSTD_countTrailingZeros32_fallback(U32 val)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
ZSTD_countTrailingZeros32(U32 val)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
ZSTD_countLeadingZeros32_fallback(U32 val)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
ZSTD_countLeadingZeros32(U32 val)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
ZSTD_countTrailingZeros64(U64 val)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
ZSTD_countLeadingZeros64(U64 val)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
ZSTD_NbCommonBytes(size_t val)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
ZSTD_highbit32(U32 val)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
ZSTD_rotateRight_U64(U64 const value,U32 count)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
ZSTD_rotateRight_U32(U32 const value,U32 count)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
ZSTD_rotateRight_U16(U16 const value,U32 count)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