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
16MEM_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
28MEM_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
51MEM_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
67MEM_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
90MEM_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
121MEM_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
152MEM_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
169MEM_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 */
179MEM_STATIC
180U64 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
186MEM_STATIC
187U32 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
193MEM_STATIC
194U16 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