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