Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zxing-cpp/core/src/BitHacks.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*
2 * Copyright 2016 Huy Cuong Nguyen
3 * Copyright 2017 Axel Waggershauser
4 */
5 // SPDX-License-Identifier: Apache-2.0
6
7 #pragma once
8
9 #include <cassert>
10 #include <cstdint>
11 #include <cstring>
12 #include <vector>
13
14 // MSVC has the <bit> header but then warns about including it.
15 // We check for _MSVC_LANG here as well, so client code is depending on /Zc:__cplusplus
16 #if __has_include(<bit>) && (__cplusplus > 201703L || (defined(_MSVC_LANG) && _MSVC_LANG > 201703L))
17 #include <bit>
18 #if __cplusplus > 201703L && defined(__ANDROID__) // NDK 25.1.8937393 has the implementation but fails to advertise it
19 #define __cpp_lib_bitops 201907L
20 #endif
21 #elif defined(_MSC_VER)
22 // accoring to #863 MSVC defines __cpp_lib_bitops even when <bit> it not included and bitops are not available
23 #undef __cpp_lib_bitops
24 #endif
25
26 #if defined(__clang__) || defined(__GNUC__)
27 #define ZX_HAS_GCC_BUILTINS
28 #elif defined(_MSC_VER) && !defined(_M_ARM) && !defined(_M_ARM64)
29 #include <intrin.h>
30 #define ZX_HAS_MSC_BUILTINS
31 #endif
32
33 namespace ZXing::BitHacks {
34
35 /**
36 * The code below is taken from https://graphics.stanford.edu/~seander/bithacks.html
37 * All credits go to Sean Eron Anderson and other authors mentioned in that page.
38 */
39
40 /// <summary>
41 /// Compute the number of zero bits on the left.
42 /// </summary>
43 template<typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
44 inline int NumberOfLeadingZeros(T x)
45 {
46 #ifdef __cpp_lib_bitops
47 return std::countl_zero(static_cast<std::make_unsigned_t<T>>(x));
48 #else
49 if constexpr (sizeof(x) <= 4) {
50 static_assert(sizeof(x) == 4, "NumberOfLeadingZeros not implemented for 8 and 16 bit ints.");
51 if (x == 0)
52 return 32;
53 #ifdef ZX_HAS_GCC_BUILTINS
54 return __builtin_clz(x);
55 #elif defined(ZX_HAS_MSC_BUILTINS)
56 unsigned long where;
57 if (_BitScanReverse(&where, x))
58 return 31 - static_cast<int>(where);
59 return 32;
60 #else
61 int n = 0;
62 if ((x & 0xFFFF0000) == 0) { n = n + 16; x = x << 16; }
63 if ((x & 0xFF000000) == 0) { n = n + 8; x = x << 8; }
64 if ((x & 0xF0000000) == 0) { n = n + 4; x = x << 4; }
65 if ((x & 0xC0000000) == 0) { n = n + 2; x = x << 2; }
66 if ((x & 0x80000000) == 0) { n = n + 1; }
67 return n;
68 #endif
69 } else {
70 if (x == 0)
71 return 64;
72 #ifdef ZX_HAS_GCC_BUILTINS
73 return __builtin_clzll(x);
74 #else // including ZX_HAS_MSC_BUILTINS
75 int n = NumberOfLeadingZeros(static_cast<uint32_t>(x >> 32));
76 if (n == 32)
77 n += NumberOfLeadingZeros(static_cast<uint32_t>(x));
78 return n;
79 #endif
80 }
81 #endif
82 }
83
84 /// <summary>
85 /// Compute the number of zero bits on the right.
86 /// </summary>
87 template<typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
88 inline int NumberOfTrailingZeros(T v)
89 {
90 #ifdef __cpp_lib_bitops
91 return std::countr_zero(static_cast<std::make_unsigned_t<T>>(v));
92 #else
93 if constexpr (sizeof(v) <= 4) {
94 static_assert(sizeof(v) == 4, "NumberOfTrailingZeros not implemented for 8 and 16 bit ints.");
95 #ifdef ZX_HAS_GCC_BUILTINS
96 return v == 0 ? 32 : __builtin_ctz(v);
97 #elif defined(ZX_HAS_MSC_BUILTINS)
98 unsigned long where;
99 if (_BitScanForward(&where, v))
100 return static_cast<int>(where);
101 return 32;
102 #else
103 int c = 32;
104 v &= -int32_t(v);
105 if (v) c--;
106 if (v & 0x0000FFFF) c -= 16;
107 if (v & 0x00FF00FF) c -= 8;
108 if (v & 0x0F0F0F0F) c -= 4;
109 if (v & 0x33333333) c -= 2;
110 if (v & 0x55555555) c -= 1;
111 return c;
112 #endif
113 } else {
114 #ifdef ZX_HAS_GCC_BUILTINS
115 return v == 0 ? 64 : __builtin_ctzll(v);
116 #else // including ZX_HAS_MSC_BUILTINS
117 int n = NumberOfTrailingZeros(static_cast<uint32_t>(v));
118 if (n == 32)
119 n += NumberOfTrailingZeros(static_cast<uint32_t>(v >> 32));
120 return n;
121 #endif
122 }
123 #endif
124 }
125
126 inline uint32_t Reverse(uint32_t v)
127 {
128 #if 0
129 return __builtin_bitreverse32(v);
130 #else
131 v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
132 // swap consecutive pairs
133 v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
134 // swap nibbles ...
135 v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
136 // swap bytes
137 v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
138 // swap 2-byte long pairs
139 v = (v >> 16) | (v << 16);
140 return v;
141 #endif
142 }
143
144 inline int CountBitsSet(uint32_t v)
145 {
146 #ifdef __cpp_lib_bitops
147 return std::popcount(v);
148 #elif defined(ZX_HAS_GCC_BUILTINS)
149 return __builtin_popcount(v);
150 #else
151 v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
152 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
153 return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; // count
154 #endif
155 }
156
157 // this is the same as log base 2 of v
158 inline int HighestBitSet(uint32_t v)
159 {
160 return 31 - NumberOfLeadingZeros(v);
161 }
162
163 // shift a whole array of bits by offset bits to the right (thinking of the array as a contiguous stream of bits
164 // starting with the LSB of the first int and ending with the MSB of the last int, this is actually a left shift)
165 template <typename T>
166 void ShiftRight(std::vector<T>& bits, std::size_t offset)
167 {
168 assert(offset < sizeof(T) * 8);
169
170 if (offset == 0 || bits.empty())
171 return;
172
173 std::size_t leftOffset = sizeof(T) * 8 - offset;
174 for (std::size_t i = 0; i < bits.size() - 1; ++i) {
175 bits[i] = (bits[i] >> offset) | (bits[i + 1] << leftOffset);
176 }
177 bits.back() >>= offset;
178 }
179
180 // reverse a whole array of bits. padding is the number of 'dummy' bits at the end of the array
181 template <typename T>
182 void Reverse(std::vector<T>& bits, std::size_t padding)
183 {
184 static_assert(sizeof(T) == sizeof(uint32_t), "Reverse only implemented for 32 bit types");
185
186 // reverse all int's first (reversing the ints in the array and the bits in the ints at the same time)
187 auto first = bits.begin(), last = bits.end();
188 for (; first < --last; ++first) {
189 auto t = *first;
190 *first = BitHacks::Reverse(*last);
191 *last = BitHacks::Reverse(t);
192 }
193 if (first == last)
194 *last = BitHacks::Reverse(*last);
195
196 // now correct the int's if the bit size isn't a multiple of 32
197 ShiftRight(bits, padding);
198 }
199
200 // use to avoid "load of misaligned address" when using a simple type cast
201 template <typename T>
202 T LoadU(const void* ptr)
203 {
204 static_assert(std::is_integral<T>::value, "T must be an integer");
205 T res;
206 memcpy(&res, ptr, sizeof(T));
207 return res;
208 }
209
210 } // namespace ZXing::BitHacks