Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
tjh.dev
kernel
os
linux
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
17MEM_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
29MEM_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
39MEM_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
56MEM_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
66MEM_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
84MEM_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
102MEM_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
119MEM_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 */
129MEM_STATIC
130U64 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
136MEM_STATIC
137U32 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
143MEM_STATIC
144U16 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 */