1 #pragma once
2 /*
3 * Copyright 2016 Huy Cuong Nguyen
4 * Copyright 2017 Axel Waggershauser
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 #include <cassert>
20 #include <cstdint>
21 #include <vector>
22
23 #if defined(__clang__) || defined(__GNUC__)
24 #define ZX_HAS_GCC_BUILTINS
25 #endif
26
27 namespace ZXing {
28 namespace BitHacks {
29
30 /**
31 * The code below is taken from https://graphics.stanford.edu/~seander/bithacks.html
32 * All credits go to Sean Eron Anderson and other authors mentioned in that page.
33 */
34
35 /// <summary>
36 /// Compute the number of zero bits on the left.
37 /// </summary>
NumberOfLeadingZeros(uint32_t x)38 inline int NumberOfLeadingZeros(uint32_t x)
39 {
40 if (x == 0)
41 return 32;
42 #ifdef ZX_HAS_GCC_BUILTINS
43 return __builtin_clz(x);
44 #else
45 int n = 0;
46 if ((x & 0xFFFF0000) == 0) { n = n + 16; x = x << 16; }
47 if ((x & 0xFF000000) == 0) { n = n + 8; x = x << 8; }
48 if ((x & 0xF0000000) == 0) { n = n + 4; x = x << 4; }
49 if ((x & 0xC0000000) == 0) { n = n + 2; x = x << 2; }
50 if ((x & 0x80000000) == 0) { n = n + 1; }
51 return n;
52 #endif
53 }
54
55 /// <summary>
56 /// Compute the number of zero bits on the right.
57 /// </summary>
NumberOfTrailingZeros(uint32_t v)58 inline int NumberOfTrailingZeros(uint32_t v)
59 {
60 #ifdef ZX_HAS_GCC_BUILTINS
61 assert(v != 0);
62 return __builtin_ctz(v);
63 #else
64 int c = 32;
65 v &= -int32_t(v);
66 if (v) c--;
67 if (v & 0x0000FFFF) c -= 16;
68 if (v & 0x00FF00FF) c -= 8;
69 if (v & 0x0F0F0F0F) c -= 4;
70 if (v & 0x33333333) c -= 2;
71 if (v & 0x55555555) c -= 1;
72 return c;
73 #endif
74 }
75
Reverse(uint32_t v)76 inline uint32_t Reverse(uint32_t v)
77 {
78 #if 0
79 return __builtin_bitreverse32(v);
80 #else
81 v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
82 // swap consecutive pairs
83 v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
84 // swap nibbles ...
85 v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
86 // swap bytes
87 v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
88 // swap 2-byte long pairs
89 v = (v >> 16) | (v << 16);
90 return v;
91 #endif
92 }
93
CountBitsSet(uint32_t v)94 inline int CountBitsSet(uint32_t v)
95 {
96 #ifdef ZX_HAS_GCC_BUILTINS
97 return __builtin_popcount(v);
98 #else
99 v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
100 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
101 return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; // count
102 #endif
103 }
104
105 // this is the same as log base 2 of v
HighestBitSet(uint32_t v)106 inline int HighestBitSet(uint32_t v)
107 {
108 return 31 - NumberOfLeadingZeros(v);
109 }
110
111 // shift a whole array of bits by offset bits to the right (thinking of the array as a contiguous stream of bits
112 // starting with the LSB of the first int and ending with the MSB of the last int, this is actually a left shift)
113 template <typename T>
ShiftRight(std::vector<T> & bits,std::size_t offset)114 void ShiftRight(std::vector<T>& bits, std::size_t offset)
115 {
116 assert(offset < sizeof(T) * 8);
117
118 if (offset == 0 || bits.empty())
119 return;
120
121 std::size_t leftOffset = sizeof(T) * 8 - offset;
122 for (std::size_t i = 0; i < bits.size() - 1; ++i) {
123 bits[i] = (bits[i] >> offset) | (bits[i + 1] << leftOffset);
124 }
125 bits.back() >>= offset;
126 }
127
128 // reverse a whole array of bits. padding is the number of 'dummy' bits at the end of the array
129 template <typename T>
Reverse(std::vector<T> & bits,std::size_t padding)130 void Reverse(std::vector<T>& bits, std::size_t padding)
131 {
132 static_assert(sizeof(T) == sizeof(uint32_t), "Reverse only implemented for 32 bit types");
133
134 // reverse all int's first (reversing the ints in the array and the bits in the ints at the same time)
135 auto first = bits.begin(), last = bits.end();
136 for (; first < --last; ++first) {
137 auto t = *first;
138 *first = BitHacks::Reverse(*last);
139 *last = BitHacks::Reverse(t);
140 }
141 if (first == last)
142 *last = BitHacks::Reverse(*last);
143
144 // now correct the int's if the bit size isn't a multiple of 32
145 ShiftRight(bits, padding);
146 }
147
148 } // BitHacks
149 } // ZXing
150