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