Debian Codegraph @

src/Common/BitArray.php

raw
1 <?php
2 declare(strict_types = 1);
3
4 namespace BaconQrCode\Common;
5
6 use BaconQrCode\Exception\InvalidArgumentException;
7 use SplFixedArray;
8
9 /**
10 * A simple, fast array of bits.
11 */
12 final class BitArray
13 {
14 /**
15 * Bits represented as an array of integers.
16 *
17 * @var SplFixedArray<int>
18 */
19 private SplFixedArray $bits;
20
21 /**
22 * Creates a new bit array with a given size.
23 */
24 public function __construct(private int $size = 0)
25 {
26 $this->bits = SplFixedArray::fromArray(array_fill(0, ($this->size + 31) >> 3, 0));
27 }
28
29 /**
30 * Gets the size in bits.
31 */
32 public function getSize() : int
33 {
34 return $this->size;
35 }
36
37 /**
38 * Gets the size in bytes.
39 */
40 public function getSizeInBytes() : int
41 {
42 return ($this->size + 7) >> 3;
43 }
44
45 /**
46 * Ensures that the array has a minimum capacity.
47 */
48 public function ensureCapacity(int $size) : void
49 {
50 if ($size > count($this->bits) << 5) {
51 $this->bits->setSize(($size + 31) >> 5);
52 }
53 }
54
55 /**
56 * Gets a specific bit.
57 */
58 public function get(int $i) : bool
59 {
60 return 0 !== ($this->bits[$i >> 5] & (1 << ($i & 0x1f)));
61 }
62
63 /**
64 * Sets a specific bit.
65 */
66 public function set(int $i) : void
67 {
68 $this->bits[$i >> 5] = $this->bits[$i >> 5] | 1 << ($i & 0x1f);
69 }
70
71 /**
72 * Flips a specific bit.
73 */
74 public function flip(int $i) : void
75 {
76 $this->bits[$i >> 5] ^= 1 << ($i & 0x1f);
77 }
78
79 /**
80 * Gets the next set bit position from a given position.
81 */
82 public function getNextSet(int $from) : int
83 {
84 if ($from >= $this->size) {
85 return $this->size;
86 }
87
88 $bitsOffset = $from >> 5;
89 $currentBits = $this->bits[$bitsOffset];
90 $bitsLength = count($this->bits);
91 $currentBits &= ~((1 << ($from & 0x1f)) - 1);
92
93 while (0 === $currentBits) {
94 if (++$bitsOffset === $bitsLength) {
95 return $this->size;
96 }
97
98 $currentBits = $this->bits[$bitsOffset];
99 }
100
101 $result = ($bitsOffset << 5) + BitUtils::numberOfTrailingZeros($currentBits);
102 return min($result, $this->size);
103 }
104
105 /**
106 * Gets the next unset bit position from a given position.
107 */
108 public function getNextUnset(int $from) : int
109 {
110 if ($from >= $this->size) {
111 return $this->size;
112 }
113
114 $bitsOffset = $from >> 5;
115 $currentBits = ~$this->bits[$bitsOffset];
116 $bitsLength = count($this->bits);
117 $currentBits &= ~((1 << ($from & 0x1f)) - 1);
118
119 while (0 === $currentBits) {
120 if (++$bitsOffset === $bitsLength) {
121 return $this->size;
122 }
123
124 $currentBits = ~$this->bits[$bitsOffset];
125 }
126
127 $result = ($bitsOffset << 5) + BitUtils::numberOfTrailingZeros($currentBits);
128 return min($result, $this->size);
129 }
130
131 /**
132 * Sets a bulk of bits.
133 */
134 public function setBulk(int $i, int $newBits) : void
135 {
136 $this->bits[$i >> 5] = $newBits;
137 }
138
139 /**
140 * Sets a range of bits.
141 *
142 * @throws InvalidArgumentException if end is smaller than start
143 */
144 public function setRange(int $start, int $end) : void
145 {
146 if ($end < $start) {
147 throw new InvalidArgumentException('End must be greater or equal to start');
148 }
149
150 if ($end === $start) {
151 return;
152 }
153
154 --$end;
155
156 $firstInt = $start >> 5;
157 $lastInt = $end >> 5;
158
159 for ($i = $firstInt; $i <= $lastInt; ++$i) {
160 $firstBit = $i > $firstInt ? 0 : $start & 0x1f;
161 $lastBit = $i < $lastInt ? 31 : $end & 0x1f;
162
163 if (0 === $firstBit && 31 === $lastBit) {
164 $mask = 0x7fffffff;
165 } else {
166 $mask = 0;
167
168 for ($j = $firstBit; $j < $lastBit; ++$j) {
169 $mask |= 1 << $j;
170 }
171 }
172
173 $this->bits[$i] = $this->bits[$i] | $mask;
174 }
175 }
176
177 /**
178 * Clears the bit array, unsetting every bit.
179 */
180 public function clear() : void
181 {
182 $bitsLength = count($this->bits);
183
184 for ($i = 0; $i < $bitsLength; ++$i) {
185 $this->bits[$i] = 0;
186 }
187 }
188
189 /**
190 * Checks if a range of bits is set or not set.
191
192 * @throws InvalidArgumentException if end is smaller than start
193 */
194 public function isRange(int $start, int $end, bool $value) : bool
195 {
196 if ($end < $start) {
197 throw new InvalidArgumentException('End must be greater or equal to start');
198 }
199
200 if ($end === $start) {
201 return true;
202 }
203
204 --$end;
205
206 $firstInt = $start >> 5;
207 $lastInt = $end >> 5;
208
209 for ($i = $firstInt; $i <= $lastInt; ++$i) {
210 $firstBit = $i > $firstInt ? 0 : $start & 0x1f;
211 $lastBit = $i < $lastInt ? 31 : $end & 0x1f;
212
213 if (0 === $firstBit && 31 === $lastBit) {
214 $mask = 0x7fffffff;
215 } else {
216 $mask = 0;
217
218 for ($j = $firstBit; $j <= $lastBit; ++$j) {
219 $mask |= 1 << $j;
220 }
221 }
222
223 if (($this->bits[$i] & $mask) !== ($value ? $mask : 0)) {
224 return false;
225 }
226 }
227
228 return true;
229 }
230
231 /**
232 * Appends a bit to the array.
233 */
234 public function appendBit(bool $bit) : void
235 {
236 $this->ensureCapacity($this->size + 1);
237
238 if ($bit) {
239 $this->bits[$this->size >> 5] = $this->bits[$this->size >> 5] | (1 << ($this->size & 0x1f));
240 }
241
242 ++$this->size;
243 }
244
245 /**
246 * Appends a number of bits (up to 32) to the array.
247
248 * @throws InvalidArgumentException if num bits is not between 0 and 32
249 */
250 public function appendBits(int $value, int $numBits) : void
251 {
252 if ($numBits < 0 || $numBits > 32) {
253 throw new InvalidArgumentException('Num bits must be between 0 and 32');
254 }
255
256 $this->ensureCapacity($this->size + $numBits);
257
258 for ($numBitsLeft = $numBits; $numBitsLeft > 0; $numBitsLeft--) {
259 $this->appendBit((($value >> ($numBitsLeft - 1)) & 0x01) === 1);
260 }
261 }
262
263 /**
264 * Appends another bit array to this array.
265 */
266 public function appendBitArray(self $other) : void
267 {
268 $otherSize = $other->getSize();
269 $this->ensureCapacity($this->size + $other->getSize());
270
271 for ($i = 0; $i < $otherSize; ++$i) {
272 $this->appendBit($other->get($i));
273 }
274 }
275
276 /**
277 * Makes an exclusive-or comparision on the current bit array.
278 *
279 * @throws InvalidArgumentException if sizes don't match
280 */
281 public function xorBits(self $other) : void
282 {
283 $bitsLength = count($this->bits);
284 $otherBits = $other->getBitArray();
285
286 if ($bitsLength !== count($otherBits)) {
287 throw new InvalidArgumentException('Sizes don\'t match');
288 }
289
290 for ($i = 0; $i < $bitsLength; ++$i) {
291 $this->bits[$i] = $this->bits[$i] ^ $otherBits[$i];
292 }
293 }
294
295 /**
296 * Converts the bit array to a byte array.
297 *
298 * @return SplFixedArray<int>
299 */
300 public function toBytes(int $bitOffset, int $numBytes) : SplFixedArray
301 {
302 $bytes = new SplFixedArray($numBytes);
303
304 for ($i = 0; $i < $numBytes; ++$i) {
305 $byte = 0;
306
307 for ($j = 0; $j < 8; ++$j) {
308 if ($this->get($bitOffset)) {
309 $byte |= 1 << (7 - $j);
310 }
311
312 ++$bitOffset;
313 }
314
315 $bytes[$i] = $byte;
316 }
317
318 return $bytes;
319 }
320
321 /**
322 * Gets the internal bit array.
323 *
324 * @return SplFixedArray<int>
325 */
326 public function getBitArray() : SplFixedArray
327 {
328 return $this->bits;
329 }
330
331 /**
332 * Reverses the array.
333 */
334 public function reverse() : void
335 {
336 $newBits = new SplFixedArray(count($this->bits));
337
338 for ($i = 0; $i < $this->size; ++$i) {
339 if ($this->get($this->size - $i - 1)) {
340 $newBits[$i >> 5] = $newBits[$i >> 5] | (1 << ($i & 0x1f));
341 }
342 }
343
344 $this->bits = $newBits;
345 }
346
347 /**
348 * Returns a string representation of the bit array.
349 */
350 public function __toString() : string
351 {
352 $result = '';
353
354 for ($i = 0; $i < $this->size; ++$i) {
355 if (0 === ($i & 0x07)) {
356 $result .= ' ';
357 }
358
359 $result .= $this->get($i) ? 'X' : '.';
360 }
361
362 return $result;
363 }
364 }