1 | // [Blend2D] |
2 | // 2D Vector Graphics Powered by a JIT Compiler. |
3 | // |
4 | // [License] |
5 | // Zlib - See LICENSE.md file in the package. |
6 | |
7 | #ifndef BLEND2D_BLBITARRAY_P_H |
8 | #define BLEND2D_BLBITARRAY_P_H |
9 | |
10 | #include "./blbitarray.h" |
11 | #include "./blsupport_p.h" |
12 | |
13 | //! \cond INTERNAL |
14 | //! \addtogroup blend2d_internal |
15 | //! \{ |
16 | |
17 | // ============================================================================ |
18 | // [BLBitArray - Internal] |
19 | // ============================================================================ |
20 | |
21 | namespace BLInternal { |
22 | |
23 | struct BitAssign { template<typename T> static BL_INLINE T op(T a, T b) noexcept { BL_UNUSED(a); return b; } }; |
24 | struct BitAssignNot { template<typename T> static BL_INLINE T op(T a, T b) noexcept { BL_UNUSED(a); return ~b; } }; |
25 | struct BitAnd { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return a & b; } }; |
26 | struct BitAndNot { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return a & ~b; } }; |
27 | struct BitNotAnd { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return ~a & b; } }; |
28 | struct BitOr { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return a | b; } }; |
29 | struct BitXor { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return a ^ b; } }; |
30 | |
31 | } // {BLInternal} |
32 | |
33 | // ============================================================================ |
34 | // [BLBitArray - Utilities] |
35 | // ============================================================================ |
36 | |
37 | template<typename T, class BitOp, class FullOp> |
38 | static BL_INLINE void blBitArrayOpInternal(T* buf, size_t index, size_t count) noexcept { |
39 | if (count == 0) |
40 | return; |
41 | |
42 | constexpr size_t kTSizeInBits = blBitSizeOf<T>(); |
43 | size_t vecIndex = index / kTSizeInBits; // T[] |
44 | size_t bitIndex = index % kTSizeInBits; // T[][] |
45 | |
46 | buf += vecIndex; |
47 | |
48 | // The first BitWord requires special handling to preserve bits outside the fill region. |
49 | constexpr T kFillMask = blBitOnes<T>(); |
50 | size_t firstNBits = blMin<size_t>(kTSizeInBits - bitIndex, count); |
51 | |
52 | buf[0] = BitOp::op(buf[0], (kFillMask >> (kTSizeInBits - firstNBits)) << bitIndex); |
53 | buf++; |
54 | count -= firstNBits; |
55 | |
56 | // All bits between the first and last affected BitWords can be just filled. |
57 | while (count >= kTSizeInBits) { |
58 | buf[0] = FullOp::op(buf[0], kFillMask); |
59 | buf++; |
60 | count -= kTSizeInBits; |
61 | } |
62 | |
63 | // The last BitWord requires special handling as well. |
64 | if (count) |
65 | buf[0] = BitOp::op(buf[0], kFillMask >> (kTSizeInBits - count)); |
66 | } |
67 | |
68 | //! Fill `count` bits in bit-vector `buf` starting at bit-index `index`. |
69 | template<typename T> |
70 | static BL_INLINE void blBitArrayFillInternal(T* buf, size_t index, size_t count) noexcept { blBitArrayOpInternal<T, BLInternal::BitOr, BLInternal::BitAssign>(buf, index, count); } |
71 | |
72 | //! Clear `count` bits in bit-vector `buf` starting at bit-index `index`. |
73 | template<typename T> |
74 | static BL_INLINE void blBitArrayClearInternal(T* buf, size_t index, size_t count) noexcept { blBitArrayOpInternal<T, BLInternal::BitAndNot, BLInternal::BitAssignNot>(buf, index, count); } |
75 | |
76 | // ============================================================================ |
77 | // [BLBitWordIterator] |
78 | // ============================================================================ |
79 | |
80 | //! Iterates over each bit in a number which is set to 1. |
81 | //! |
82 | //! Example of use: |
83 | //! |
84 | //! ``` |
85 | //! uint32_t bitsToIterate = 0x110F; |
86 | //! BLBitWordIterator<uint32_t> it(bitsToIterate); |
87 | //! |
88 | //! while (it.hasNext()) { |
89 | //! uint32_t bitIndex = it.next(); |
90 | //! printf("Bit at %u is set\n", unsigned(bitIndex)); |
91 | //! } |
92 | //! ``` |
93 | template<typename T> |
94 | class BLBitWordIterator { |
95 | public: |
96 | BL_INLINE explicit BLBitWordIterator(T bitWord) noexcept |
97 | : _bitWord(bitWord) {} |
98 | |
99 | BL_INLINE void init(T bitWord) noexcept { _bitWord = bitWord; } |
100 | BL_INLINE bool hasNext() const noexcept { return _bitWord != 0; } |
101 | |
102 | BL_INLINE uint32_t next() noexcept { |
103 | BL_ASSERT(_bitWord != 0); |
104 | uint32_t index = blBitCtz(_bitWord); |
105 | _bitWord ^= T(1u) << index; |
106 | return index; |
107 | } |
108 | |
109 | T _bitWord; |
110 | }; |
111 | |
112 | // ============================================================================ |
113 | // [BLBitVectorIterator] |
114 | // ============================================================================ |
115 | |
116 | template<typename T> |
117 | class BLBitVectorIterator { |
118 | public: |
119 | BL_INLINE BLBitVectorIterator(const T* data, size_t numBitWords, size_t start = 0) noexcept { |
120 | init(data, numBitWords, start); |
121 | } |
122 | |
123 | BL_INLINE void init(const T* data, size_t numBitWords, size_t start = 0) noexcept { |
124 | const T* ptr = data + (start / blBitSizeOf<T>()); |
125 | size_t idx = blAlignDown(start, blBitSizeOf<T>()); |
126 | size_t end = numBitWords * blBitSizeOf<T>(); |
127 | |
128 | T bitWord = T(0); |
129 | if (idx < end) { |
130 | bitWord = *ptr++ & (blBitOnes<T>() << (start % blBitSizeOf<T>())); |
131 | while (!bitWord && (idx += blBitSizeOf<T>()) < end) |
132 | bitWord = *ptr++; |
133 | } |
134 | |
135 | _ptr = ptr; |
136 | _idx = idx; |
137 | _end = end; |
138 | _current = bitWord; |
139 | } |
140 | |
141 | BL_INLINE bool hasNext() const noexcept { |
142 | return _current != T(0); |
143 | } |
144 | |
145 | BL_INLINE size_t next() noexcept { |
146 | T bitWord = _current; |
147 | BL_ASSERT(bitWord != T(0)); |
148 | |
149 | uint32_t bit = blBitCtz(bitWord); |
150 | bitWord ^= T(1u) << bit; |
151 | |
152 | size_t n = _idx + bit; |
153 | while (!bitWord && (_idx += blBitSizeOf<T>()) < _end) |
154 | bitWord = *_ptr++; |
155 | |
156 | _current = bitWord; |
157 | return n; |
158 | } |
159 | |
160 | BL_INLINE size_t peekNext() const noexcept { |
161 | BL_ASSERT(_current != T(0)); |
162 | return _idx + blBitCtz(_current); |
163 | } |
164 | |
165 | const T* _ptr; |
166 | size_t _idx; |
167 | size_t _end; |
168 | T _current; |
169 | }; |
170 | |
171 | // ============================================================================ |
172 | // [BLBitVectorFlipIterator] |
173 | // ============================================================================ |
174 | |
175 | template<typename T> |
176 | class BLBitVectorFlipIterator { |
177 | public: |
178 | BL_INLINE BLBitVectorFlipIterator(const T* data, size_t numBitWords, size_t start = 0, T xorMask = 0) noexcept { |
179 | init(data, numBitWords, start, xorMask); |
180 | } |
181 | |
182 | BL_INLINE void init(const T* data, size_t numBitWords, size_t start = 0, T xorMask = 0) noexcept { |
183 | const T* ptr = data + (start / blBitSizeOf<T>()); |
184 | size_t idx = blAlignDown(start, blBitSizeOf<T>()); |
185 | size_t end = numBitWords * blBitSizeOf<T>(); |
186 | |
187 | T bitWord = T(0); |
188 | if (idx < end) { |
189 | bitWord = (*ptr++ ^ xorMask) & (blBitOnes<T>() << (start % blBitSizeOf<T>())); |
190 | while (!bitWord && (idx += blBitSizeOf<T>()) < end) |
191 | bitWord = *ptr++ ^ xorMask; |
192 | } |
193 | |
194 | _ptr = ptr; |
195 | _idx = idx; |
196 | _end = end; |
197 | _current = bitWord; |
198 | _xorMask = xorMask; |
199 | } |
200 | |
201 | BL_INLINE bool hasNext() const noexcept { |
202 | return _current != T(0); |
203 | } |
204 | |
205 | BL_INLINE size_t next() noexcept { |
206 | T bitWord = _current; |
207 | BL_ASSERT(bitWord != T(0)); |
208 | |
209 | uint32_t bit = blBitCtz(bitWord); |
210 | bitWord ^= T(1u) << bit; |
211 | |
212 | size_t n = _idx + bit; |
213 | while (!bitWord && (_idx += blBitSizeOf<T>()) < _end) |
214 | bitWord = *_ptr++ ^ _xorMask; |
215 | |
216 | _current = bitWord; |
217 | return n; |
218 | } |
219 | |
220 | BL_INLINE size_t nextAndFlip() noexcept { |
221 | T bitWord = _current; |
222 | BL_ASSERT(bitWord != T(0)); |
223 | |
224 | uint32_t bit = blBitCtz(bitWord); |
225 | bitWord ^= blBitOnes<T>() << bit; |
226 | _xorMask ^= blBitOnes<T>(); |
227 | |
228 | size_t n = _idx + bit; |
229 | while (!bitWord && (_idx += blBitSizeOf<T>()) < _end) |
230 | bitWord = *_ptr++ ^ _xorMask; |
231 | |
232 | _current = bitWord; |
233 | return n; |
234 | } |
235 | |
236 | BL_INLINE size_t peekNext() const noexcept { |
237 | BL_ASSERT(_current != T(0)); |
238 | return _idx + blBitCtz(_current); |
239 | } |
240 | |
241 | const T* _ptr; |
242 | size_t _idx; |
243 | size_t _end; |
244 | T _current; |
245 | T _xorMask; |
246 | }; |
247 | |
248 | // ============================================================================ |
249 | // [BLFixedBitArray] |
250 | // ============================================================================ |
251 | |
252 | template<typename T, size_t N> |
253 | class BLFixedBitArray { |
254 | public: |
255 | enum : size_t { |
256 | kSizeOfTInBits = blBitSizeOf<T>(), |
257 | kFixedArraySize = (N + kSizeOfTInBits - 1) / kSizeOfTInBits |
258 | }; |
259 | |
260 | BL_INLINE bool bitAt(size_t index) const noexcept { |
261 | BL_ASSERT(index < N); |
262 | return bool((data[index / kSizeOfTInBits] >> (index % kSizeOfTInBits)) & 0x1); |
263 | } |
264 | |
265 | BL_INLINE void setAt(size_t index) noexcept { |
266 | BL_ASSERT(index < N); |
267 | data[index / kSizeOfTInBits] |= T(1) << (index % kSizeOfTInBits); |
268 | } |
269 | |
270 | BL_INLINE void setAt(size_t index, bool value) noexcept { |
271 | BL_ASSERT(index < N); |
272 | |
273 | T clrMask = T(1 ) << (index % kSizeOfTInBits); |
274 | T setMask = T(value) << (index % kSizeOfTInBits); |
275 | data[index / kSizeOfTInBits] = (data[index / kSizeOfTInBits] & ~clrMask) | setMask; |
276 | } |
277 | |
278 | BL_INLINE void clearAt(size_t index) noexcept { |
279 | BL_ASSERT(index < N); |
280 | data[index / kSizeOfTInBits] &= ~(T(1) << (index % kSizeOfTInBits)); |
281 | } |
282 | |
283 | BL_INLINE void clearAll() noexcept { |
284 | for (size_t i = 0; i < kFixedArraySize; i++) |
285 | data[i] = 0; |
286 | } |
287 | |
288 | BL_INLINE void setAll() noexcept { |
289 | for (size_t i = 0; i < kFixedArraySize; i++) |
290 | data[i] = blBitOnes<T>(); |
291 | } |
292 | |
293 | T data[kFixedArraySize]; |
294 | }; |
295 | |
296 | //! \} |
297 | //! \endcond |
298 | |
299 | #endif // BLEND2D_BLBITARRAY_P_H |
300 | |