1 /* SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause */
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 
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 
29 MEM_STATIC unsigned ZSTD_countTrailingZeros32(U32 val)
30 {
31     assert(val != 0);
32 #if (__GNUC__ >= 4)
33     return (unsigned)__builtin_ctz(val);
34 #else
35     return ZSTD_countTrailingZeros32_fallback(val);
36 #endif
37 }
38 
39 MEM_STATIC unsigned ZSTD_countLeadingZeros32_fallback(U32 val)
40 {
41     assert(val != 0);
42     {
43         static const U32 DeBruijnClz[32] = {0, 9, 1, 10, 13, 21, 2, 29,
44                                             11, 14, 16, 18, 22, 25, 3, 30,
45                                             8, 12, 20, 28, 15, 17, 24, 7,
46                                             19, 27, 23, 6, 26, 5, 4, 31};
47         val |= val >> 1;
48         val |= val >> 2;
49         val |= val >> 4;
50         val |= val >> 8;
51         val |= val >> 16;
52         return 31 - DeBruijnClz[(val * 0x07C4ACDDU) >> 27];
53     }
54 }
55 
56 MEM_STATIC unsigned ZSTD_countLeadingZeros32(U32 val)
57 {
58     assert(val != 0);
59 #if (__GNUC__ >= 4)
60     return (unsigned)__builtin_clz(val);
61 #else
62     return ZSTD_countLeadingZeros32_fallback(val);
63 #endif
64 }
65 
66 MEM_STATIC unsigned ZSTD_countTrailingZeros64(U64 val)
67 {
68     assert(val != 0);
69 #if (__GNUC__ >= 4) && defined(__LP64__)
70     return (unsigned)__builtin_ctzll(val);
71 #else
72     {
73         U32 mostSignificantWord = (U32)(val >> 32);
74         U32 leastSignificantWord = (U32)val;
75         if (leastSignificantWord == 0) {
76             return 32 + ZSTD_countTrailingZeros32(mostSignificantWord);
77         } else {
78             return ZSTD_countTrailingZeros32(leastSignificantWord);
79         }
80     }
81 #endif
82 }
83 
84 MEM_STATIC unsigned ZSTD_countLeadingZeros64(U64 val)
85 {
86     assert(val != 0);
87 #if (__GNUC__ >= 4)
88     return (unsigned)(__builtin_clzll(val));
89 #else
90     {
91         U32 mostSignificantWord = (U32)(val >> 32);
92         U32 leastSignificantWord = (U32)val;
93         if (mostSignificantWord == 0) {
94             return 32 + ZSTD_countLeadingZeros32(leastSignificantWord);
95         } else {
96             return ZSTD_countLeadingZeros32(mostSignificantWord);
97         }
98     }
99 #endif
100 }
101 
102 MEM_STATIC unsigned ZSTD_NbCommonBytes(size_t val)
103 {
104     if (MEM_isLittleEndian()) {
105         if (MEM_64bits()) {
106             return ZSTD_countTrailingZeros64((U64)val) >> 3;
107         } else {
108             return ZSTD_countTrailingZeros32((U32)val) >> 3;
109         }
110     } else {  /* Big Endian CPU */
111         if (MEM_64bits()) {
112             return ZSTD_countLeadingZeros64((U64)val) >> 3;
113         } else {
114             return ZSTD_countLeadingZeros32((U32)val) >> 3;
115         }
116     }
117 }
118 
119 MEM_STATIC unsigned ZSTD_highbit32(U32 val)   /* compress, dictBuilder, decodeCorpus */
120 {
121     assert(val != 0);
122     return 31 - ZSTD_countLeadingZeros32(val);
123 }
124 
125 /* ZSTD_rotateRight_*():
126  * Rotates a bitfield to the right by "count" bits.
127  * https://en.wikipedia.org/w/index.php?title=Circular_shift&oldid=991635599#Implementing_circular_shifts
128  */
129 MEM_STATIC
130 U64 ZSTD_rotateRight_U64(U64 const value, U32 count) {
131     assert(count < 64);
132     count &= 0x3F; /* for fickle pattern recognition */
133     return (value >> count) | (U64)(value << ((0U - count) & 0x3F));
134 }
135 
136 MEM_STATIC
137 U32 ZSTD_rotateRight_U32(U32 const value, U32 count) {
138     assert(count < 32);
139     count &= 0x1F; /* for fickle pattern recognition */
140     return (value >> count) | (U32)(value << ((0U - count) & 0x1F));
141 }
142 
143 MEM_STATIC
144 U16 ZSTD_rotateRight_U16(U16 const value, U32 count) {
145     assert(count < 16);
146     count &= 0x0F; /* for fickle pattern recognition */
147     return (value >> count) | (U16)(value << ((0U - count) & 0x0F));
148 }
149 
150 #endif /* ZSTD_BITS_H */
151