BitArray.php 9.65 KB
Newer Older
1
<?php
2
3
4
5
6
7
8
/**
 * BaconQrCode
 *
 * @link      http://github.com/Bacon/BaconQrCode For the canonical source repository
 * @copyright 2013 Ben 'DASPRiD' Scholzen
 * @license   http://opensource.org/licenses/BSD-2-Clause Simplified BSD License
 */
9
10
11
12
13
14
15
16

namespace BaconQrCode\Common;

use SplFixedArray;

/**
 * A simple, fast array of bits.
 */
17
class BitArray
18
19
20
21
{
    /**
     * Bits represented as an array of integers.
     *
22
     * @var SplFixedArray
23
     */
24
    protected $bits;
25
26
27
28

    /**
     * Size of the bit array in bits.
     *
29
     * @var integer
30
     */
31
    protected $size;
32
33
34

    /**
     * Creates a new bit array with a given size.
35
36
     *
     * @param integer $size
37
     */
38
    public function __construct($size = 0)
39
40
    {
        $this->size = $size;
41
        $this->bits = new SplFixedArray(($this->size + 31) >> 3);
42
43
44
45
    }

    /**
     * Gets the size in bits.
46
47
     *
     * @return integer
48
     */
49
    public function getSize()
50
51
52
53
54
55
    {
        return $this->size;
    }

    /**
     * Gets the size in bytes.
56
57
     *
     * @return integer
58
     */
59
    public function getSizeInBytes()
60
61
62
63
64
65
    {
        return ($this->size + 7) >> 3;
    }

    /**
     * Ensures that the array has a minimum capacity.
66
67
68
     *
     * @param  integer $size
     * @return void
69
     */
70
    public function ensureCapacity($size)
71
72
73
74
75
76
77
78
    {
        if ($size > count($this->bits) << 5) {
            $this->bits->setSize(($size + 31) >> 5);
        }
    }

    /**
     * Gets a specific bit.
79
80
81
     *
     * @param  integer $i
     * @return boolean
82
     */
83
    public function get($i)
84
    {
85
        return ($this->bits[$i >> 5] & (1 << ($i & 0x1f))) !== 0;
86
87
88
89
    }

    /**
     * Sets a specific bit.
90
91
92
     *
     * @param  integer $i
     * @return void
93
     */
94
    public function set($i)
95
96
97
98
99
100
    {
        $this->bits[$i >> 5] = $this->bits[$i >> 5] | 1 << ($i & 0x1f);
    }

    /**
     * Flips a specific bit.
101
102
103
     *
     * @param  integer $i
     * @return void
104
     */
105
    public function flip($i)
106
107
108
109
110
111
    {
        $this->bits[$i >> 5] ^= 1 << ($i & 0x1f);
    }

    /**
     * Gets the next set bit position from a given position.
112
113
114
     *
     * @param  integer $from
     * @return integer
115
     */
116
    public function getNextSet($from)
117
118
119
120
121
    {
        if ($from >= $this->size) {
            return $this->size;
        }

122
        $bitsOffset  = $from >> 5;
123
        $currentBits = $this->bits[$bitsOffset];
124
125
        $bitsLength  = count($this->bits);

126
127
        $currentBits &= ~((1 << ($from & 0x1f)) - 1);

128
        while ($currentBits === 0) {
129
130
131
132
133
134
135
136
            if (++$bitsOffset === $bitsLength) {
                return $this->size;
            }

            $currentBits = $this->bits[$bitsOffset];
        }

        $result = ($bitsOffset << 5) + BitUtils::numberOfTrailingZeros($currentBits);
137

138
139
140
141
142
        return $result > $this->size ? $this->size : $result;
    }

    /**
     * Gets the next unset bit position from a given position.
143
144
145
     *
     * @param  integer $from
     * @return integer
146
     */
147
    public function getNextUnset($from)
148
149
150
151
152
    {
        if ($from >= $this->size) {
            return $this->size;
        }

153
        $bitsOffset  = $from >> 5;
154
        $currentBits = ~$this->bits[$bitsOffset];
155
156
        $bitsLength  = count($this->bits);

157
158
        $currentBits &= ~((1 << ($from & 0x1f)) - 1);

159
        while ($currentBits === 0) {
160
161
162
163
164
165
166
167
            if (++$bitsOffset === $bitsLength) {
                return $this->size;
            }

            $currentBits = ~$this->bits[$bitsOffset];
        }

        $result = ($bitsOffset << 5) + BitUtils::numberOfTrailingZeros($currentBits);
168

169
170
171
172
173
        return $result > $this->size ? $this->size : $result;
    }

    /**
     * Sets a bulk of bits.
174
175
176
177
     *
     * @param  integer $i
     * @param  integer $newBits
     * @return void
178
     */
179
    public function setBulk($i, $newBits)
180
181
182
183
184
185
186
    {
        $this->bits[$i >> 5] = $newBits;
    }

    /**
     * Sets a range of bits.
     *
187
188
189
190
     * @param  integer $start
     * @param  integer $end
     * @return void
     * @throws Exception\InvalidArgumentException
191
     */
192
    public function setRange($start, $end)
193
194
    {
        if ($end < $start) {
195
            throw new Exception\InvalidArgumentException('End must be greater or equal to start');
196
197
198
199
200
201
        }

        if ($end === $start) {
            return;
        }

202
        $end--;
203
204

        $firstInt = $start >> 5;
205
        $lastInt  = $end >> 5;
206

207
208
209
        for ($i = $firstInt; $i <= $lastInt; $i++) {
            $firstBit = $i > $firstInt ?  0 : $start & 0x1f;
            $lastBit  = $i < $lastInt ? 31 : $end & 0x1f;
210

211
            if ($firstBit === 0 && $lastBit === 31) {
212
213
214
215
                $mask = 0x7fffffff;
            } else {
                $mask = 0;

216
                for ($j = $firstBit; $j < $lastBit; $j++) {
217
218
219
220
221
222
223
224
225
226
                    $mask |= 1 << $j;
                }
            }

            $this->bits[$i] = $this->bits[$i] | $mask;
        }
    }

    /**
     * Clears the bit array, unsetting every bit.
227
228
     *
     * @return void
229
     */
230
    public function clear()
231
232
233
    {
        $bitsLength = count($this->bits);

234
        for ($i = 0; $i < $bitsLength; $i++) {
235
236
237
238
239
240
            $this->bits[$i] = 0;
        }
    }

    /**
     * Checks if a range of bits is set or not set.
241
242
243
244
245
246
     *
     * @param  integer $start
     * @param  integer $end
     * @param  integer $value
     * @return boolean
     * @throws Exception\InvalidArgumentException
247
     */
248
    public function isRange($start, $end, $value)
249
250
    {
        if ($end < $start) {
251
            throw new Exception\InvalidArgumentException('End must be greater or equal to start');
252
253
254
        }

        if ($end === $start) {
255
            return;
256
257
        }

258
        $end--;
259
260

        $firstInt = $start >> 5;
261
        $lastInt  = $end >> 5;
262

263
264
265
        for ($i = $firstInt; $i <= $lastInt; $i++) {
            $firstBit = $i > $firstInt ?  0 : $start & 0x1f;
            $lastBit  = $i < $lastInt ? 31 : $end & 0x1f;
266

267
            if ($firstBit === 0 && $lastBit === 31) {
268
269
270
271
                $mask = 0x7fffffff;
            } else {
                $mask = 0;

272
                for ($j = $firstBit; $j <= $lastBit; $j++) {
273
274
275
276
277
278
279
280
281
282
283
284
285
286
                    $mask |= 1 << $j;
                }
            }

            if (($this->bits[$i] & $mask) !== ($value ? $mask : 0)) {
                return false;
            }
        }

        return true;
    }

    /**
     * Appends a bit to the array.
287
288
289
     *
     * @param  boolean $bit
     * @return void
290
     */
291
    public function appendBit($bit)
292
293
294
295
296
297
298
    {
        $this->ensureCapacity($this->size + 1);

        if ($bit) {
            $this->bits[$this->size >> 5] = $this->bits[$this->size >> 5] | (1 << ($this->size & 0x1f));
        }

299
        $this->size++;
300
301
302
303
    }

    /**
     * Appends a number of bits (up to 32) to the array.
304
305
306
307
308
     *
     * @param  integer $value
     * @param  integer $numBits
     * @return void
     * @throws Exception\InvalidArgumentException
309
     */
310
    public function appendBits($value, $numBits)
311
312
    {
        if ($numBits < 0 || $numBits > 32) {
313
            throw new Exception\InvalidArgumentException('Num bits must be between 0 and 32');
314
315
316
317
318
319
320
321
322
323
324
        }

        $this->ensureCapacity($this->size + $numBits);

        for ($numBitsLeft = $numBits; $numBitsLeft > 0; $numBitsLeft--) {
            $this->appendBit((($value >> ($numBitsLeft - 1)) & 0x01) === 1);
        }
    }

    /**
     * Appends another bit array to this array.
325
326
327
     *
     * @param  BitArray $other
     * @return void
328
     */
329
    public function appendBitArray(self $other)
330
331
332
333
    {
        $otherSize = $other->getSize();
        $this->ensureCapacity($this->size + $other->getSize());

334
        for ($i = 0; $i < $otherSize; $i++) {
335
336
337
338
339
340
341
            $this->appendBit($other->get($i));
        }
    }

    /**
     * Makes an exclusive-or comparision on the current bit array.
     *
342
343
344
     * @param  BitArray $other
     * @return void
     * @throws Exception\InvalidArgumentException
345
     */
346
    public function xorBits(self $other)
347
348
349
350
351
    {
        $bitsLength = count($this->bits);
        $otherBits  = $other->getBitArray();

        if ($bitsLength !== count($otherBits)) {
352
            throw new Exception\InvalidArgumentException('Sizes don\'t match');
353
354
        }

355
        for ($i = 0; $i < $bitsLength; $i++) {
356
357
358
359
360
361
362
            $this->bits[$i] = $this->bits[$i] ^ $otherBits[$i];
        }
    }

    /**
     * Converts the bit array to a byte array.
     *
363
364
365
     * @param  integer $bitOffset
     * @param  integer $numBytes
     * @return SplFixedArray
366
     */
367
    public function toBytes($bitOffset, $numBytes)
368
369
370
    {
        $bytes = new SplFixedArray($numBytes);

371
        for ($i = 0; $i < $numBytes; $i++) {
372
373
            $byte = 0;

374
            for ($j = 0; $j < 8; $j++) {
375
376
377
378
                if ($this->get($bitOffset)) {
                    $byte |= 1 << (7 - $j);
                }

379
                $bitOffset++;
380
381
382
383
384
385
386
387
388
389
390
            }

            $bytes[$i] = $byte;
        }

        return $bytes;
    }

    /**
     * Gets the internal bit array.
     *
391
     * @return SplFixedArray
392
     */
393
    public function getBitArray()
394
395
396
397
398
399
    {
        return $this->bits;
    }

    /**
     * Reverses the array.
400
401
     *
     * @return void
402
     */
403
    public function reverse()
404
405
406
    {
        $newBits = new SplFixedArray(count($this->bits));

407
        for ($i = 0; $i < $this->size; $i++) {
408
409
410
411
412
            if ($this->get($this->size - $i - 1)) {
                $newBits[$i >> 5] = $newBits[$i >> 5] | (1 << ($i & 0x1f));
            }
        }

413
        $this->bits = newBits;
414
415
416
417
    }

    /**
     * Returns a string representation of the bit array.
418
419
     *
     * @return string
420
     */
421
    public function __toString()
422
423
424
    {
        $result = '';

425
426
        for ($i = 0; $i < $this->size; $i++) {
            if (($i & 0x07) === 0) {
427
428
429
430
431
432
433
434
435
                $result .= ' ';
            }

            $result .= $this->get($i) ? 'X' : '.';
        }

        return $result;
    }
}