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