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
21namespace BLInternal {
22
23struct BitAssign { template<typename T> static BL_INLINE T op(T a, T b) noexcept { BL_UNUSED(a); return b; } };
24struct BitAssignNot { template<typename T> static BL_INLINE T op(T a, T b) noexcept { BL_UNUSED(a); return ~b; } };
25struct BitAnd { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return a & b; } };
26struct BitAndNot { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return a & ~b; } };
27struct BitNotAnd { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return ~a & b; } };
28struct BitOr { template<typename T> static BL_INLINE T op(T a, T b) noexcept { return a | b; } };
29struct 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
37template<typename T, class BitOp, class FullOp>
38static 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`.
69template<typename T>
70static 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`.
73template<typename T>
74static 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//! ```
93template<typename T>
94class BLBitWordIterator {
95public:
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
116template<typename T>
117class BLBitVectorIterator {
118public:
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
175template<typename T>
176class BLBitVectorFlipIterator {
177public:
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
252template<typename T, size_t N>
253class BLFixedBitArray {
254public:
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