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