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