Debian Codegraph @

vendor/chillerlan/php-qrcode/src/Decoder/BitMatrix.php

raw
1 <?php
2 /**
3 * Class BitMatrix
4 *
5 * @created 17.01.2021
6 * @author ZXing Authors
7 * @author Smiley <[email protected]>
8 * @copyright 2021 Smiley
9 * @license Apache-2.0
10 */
11 declare(strict_types=1);
12
13 namespace chillerlan\QRCode\Decoder;
14
15 use chillerlan\QRCode\Common\{EccLevel, MaskPattern, Version};
16 use chillerlan\QRCode\Data\{QRCodeDataException, QRMatrix};
17 use function array_fill, array_reverse, count;
18 use const PHP_INT_MAX, PHP_INT_SIZE;
19
20 /**
21 * Extended QRMatrix to map read data from the Binarizer
22 */
23 final class BitMatrix extends QRMatrix{
24
25 /**
26 * See ISO 18004:2006, Annex C, Table C.1
27 *
28 * [data bits, sequence after masking]
29 */
30 private const DECODE_LOOKUP = [
31 0x5412, // 0101010000010010
32 0x5125, // 0101000100100101
33 0x5E7C, // 0101111001111100
34 0x5B4B, // 0101101101001011
35 0x45F9, // 0100010111111001
36 0x40CE, // 0100000011001110
37 0x4F97, // 0100111110010111
38 0x4AA0, // 0100101010100000
39 0x77C4, // 0111011111000100
40 0x72F3, // 0111001011110011
41 0x7DAA, // 0111110110101010
42 0x789D, // 0111100010011101
43 0x662F, // 0110011000101111
44 0x6318, // 0110001100011000
45 0x6C41, // 0110110001000001
46 0x6976, // 0110100101110110
47 0x1689, // 0001011010001001
48 0x13BE, // 0001001110111110
49 0x1CE7, // 0001110011100111
50 0x19D0, // 0001100111010000
51 0x0762, // 0000011101100010
52 0x0255, // 0000001001010101
53 0x0D0C, // 0000110100001100
54 0x083B, // 0000100000111011
55 0x355F, // 0011010101011111
56 0x3068, // 0011000001101000
57 0x3F31, // 0011111100110001
58 0x3A06, // 0011101000000110
59 0x24B4, // 0010010010110100
60 0x2183, // 0010000110000011
61 0x2EDA, // 0010111011011010
62 0x2BED, // 0010101111101101
63 ];
64
65 private const FORMAT_INFO_MASK_QR = 0x5412; // 0101010000010010
66
67 /**
68 * This flag has effect only on the copyVersionBit() method.
69 * Before proceeding with readCodewords() the resetInfo() method should be called.
70 */
71 private bool $mirror = false;
72
73 /**
74 * @noinspection PhpMissingParentConstructorInspection
75 */
76 public function __construct(int $dimension){
77 $this->moduleCount = $dimension;
78 $this->matrix = array_fill(0, $this->moduleCount, array_fill(0, $this->moduleCount, $this::M_NULL));
79 }
80
81 /**
82 * Resets the current version info in order to attempt another reading
83 */
84 public function resetVersionInfo():self{
85 $this->version = null;
86 $this->eccLevel = null;
87 $this->maskPattern = null;
88
89 return $this;
90 }
91
92 /**
93 * Mirror the bit matrix diagonally in order to attempt a second reading.
94 */
95 public function mirrorDiagonal():self{
96 $this->mirror = !$this->mirror;
97
98 // mirror vertically
99 $this->matrix = array_reverse($this->matrix);
100 // rotate by 90 degrees clockwise
101 return $this->rotate90();
102 }
103
104 /**
105 * Reads the bits in the BitMatrix representing the finder pattern in the
106 * correct order in order to reconstruct the codewords bytes contained within the
107 * QR Code. Throws if the exact number of bytes expected is not read.
108 *
109 * @return int[]
110 * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException
111 */
112 public function readCodewords():array{
113
114 $this
115 ->readFormatInformation()
116 ->readVersion()
117 ->mask($this->maskPattern) // reverse the mask pattern
118 ;
119
120 // invoke a fresh matrix with only the function & format patterns to compare against
121 $matrix = (new QRMatrix($this->version, $this->eccLevel))
122 ->initFunctionalPatterns()
123 ->setFormatInfo($this->maskPattern)
124 ;
125
126 $result = [];
127 $byte = 0;
128 $bitsRead = 0;
129 $direction = true;
130
131 // Read columns in pairs, from right to left
132 for($i = ($this->moduleCount - 1); $i > 0; $i -= 2){
133
134 // Skip whole column with vertical alignment pattern;
135 // saves time and makes the other code proceed more cleanly
136 if($i === 6){
137 $i--;
138 }
139 // Read alternatingly from bottom to top then top to bottom
140 for($count = 0; $count < $this->moduleCount; $count++){
141 $y = ($direction) ? ($this->moduleCount - 1 - $count) : $count;
142
143 for($col = 0; $col < 2; $col++){
144 $x = ($i - $col);
145
146 // Ignore bits covered by the function pattern
147 if($matrix->get($x, $y) !== $this::M_NULL){
148 continue;
149 }
150
151 $bitsRead++;
152 $byte <<= 1;
153
154 if($this->check($x, $y)){
155 $byte |= 1;
156 }
157 // If we've made a whole byte, save it off
158 if($bitsRead === 8){
159 $result[] = $byte;
160 $bitsRead = 0;
161 $byte = 0;
162 }
163 }
164 }
165
166 $direction = !$direction; // switch directions
167 }
168
169 if(count($result) !== $this->version->getTotalCodewords()){
170 throw new QRCodeDecoderException('result count differs from total codewords for version');
171 }
172
173 // bytes encoded within the QR Code
174 return $result;
175 }
176
177 /**
178 * Reads format information from one of its two locations within the QR Code.
179 * Throws if both format information locations cannot be parsed as the valid encoding of format information.
180 *
181 * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException
182 */
183 private function readFormatInformation():self{
184
185 if($this->eccLevel !== null && $this->maskPattern !== null){
186 return $this;
187 }
188
189 // Read top-left format info bits
190 $formatInfoBits1 = 0;
191
192 for($i = 0; $i < 6; $i++){
193 $formatInfoBits1 = $this->copyVersionBit($i, 8, $formatInfoBits1);
194 }
195
196 // ... and skip a bit in the timing pattern ...
197 $formatInfoBits1 = $this->copyVersionBit(7, 8, $formatInfoBits1);
198 $formatInfoBits1 = $this->copyVersionBit(8, 8, $formatInfoBits1);
199 $formatInfoBits1 = $this->copyVersionBit(8, 7, $formatInfoBits1);
200 // ... and skip a bit in the timing pattern ...
201 for($j = 5; $j >= 0; $j--){
202 $formatInfoBits1 = $this->copyVersionBit(8, $j, $formatInfoBits1);
203 }
204
205 // Read the top-right/bottom-left pattern too
206 $formatInfoBits2 = 0;
207 $jMin = ($this->moduleCount - 7);
208
209 for($j = ($this->moduleCount - 1); $j >= $jMin; $j--){
210 $formatInfoBits2 = $this->copyVersionBit(8, $j, $formatInfoBits2);
211 }
212
213 for($i = ($this->moduleCount - 8); $i < $this->moduleCount; $i++){
214 $formatInfoBits2 = $this->copyVersionBit($i, 8, $formatInfoBits2);
215 }
216
217 $formatInfo = $this->doDecodeFormatInformation($formatInfoBits1, $formatInfoBits2);
218
219 if($formatInfo === null){
220
221 // Should return null, but, some QR codes apparently do not mask this info.
222 // Try again by actually masking the pattern first.
223 $formatInfo = $this->doDecodeFormatInformation(
224 ($formatInfoBits1 ^ $this::FORMAT_INFO_MASK_QR),
225 ($formatInfoBits2 ^ $this::FORMAT_INFO_MASK_QR),
226 );
227
228 // still nothing???
229 if($formatInfo === null){
230 throw new QRCodeDecoderException('failed to read format info'); // @codeCoverageIgnore
231 }
232
233 }
234
235 $this->eccLevel = new EccLevel(($formatInfo >> 3) & 0x03); // Bits 3,4
236 $this->maskPattern = new MaskPattern($formatInfo & 0x07); // Bottom 3 bits
237
238 return $this;
239 }
240
241 private function copyVersionBit(int $i, int $j, int $versionBits):int{
242
243 $bit = $this->mirror
244 ? $this->check($j, $i)
245 : $this->check($i, $j);
246
247 return ($bit) ? (($versionBits << 1) | 0x1) : ($versionBits << 1);
248 }
249
250 /**
251 * Returns information about the format it specifies, or null if it doesn't seem to match any known pattern
252 */
253 private function doDecodeFormatInformation(int $maskedFormatInfo1, int $maskedFormatInfo2):int|null{
254 $bestDifference = PHP_INT_MAX;
255 $bestFormatInfo = 0;
256
257 // Find the int in FORMAT_INFO_DECODE_LOOKUP with the fewest bits differing
258 foreach($this::DECODE_LOOKUP as $maskedBits => $dataBits){
259
260 if($maskedFormatInfo1 === $dataBits || $maskedFormatInfo2 === $dataBits){
261 // Found an exact match
262 return $maskedBits;
263 }
264
265 $bitsDifference = $this->numBitsDiffering($maskedFormatInfo1, $dataBits);
266
267 if($bitsDifference < $bestDifference){
268 $bestFormatInfo = $maskedBits;
269 $bestDifference = $bitsDifference;
270 }
271
272 if($maskedFormatInfo1 !== $maskedFormatInfo2){
273 // also try the other option
274 $bitsDifference = $this->numBitsDiffering($maskedFormatInfo2, $dataBits);
275
276 if($bitsDifference < $bestDifference){
277 $bestFormatInfo = $maskedBits;
278 $bestDifference = $bitsDifference;
279 }
280 }
281 }
282 // Hamming distance of the 32 masked codes is 7, by construction, so <= 3 bits differing means we found a match
283 if($bestDifference <= 3){
284 return $bestFormatInfo;
285 }
286
287 return null;
288 }
289
290 /**
291 * Reads version information from one of its two locations within the QR Code.
292 * Throws if both version information locations cannot be parsed as the valid encoding of version information.
293 *
294 * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException
295 * @noinspection DuplicatedCode
296 */
297 private function readVersion():self{
298
299 if($this->version !== null){
300 return $this;
301 }
302
303 $provisionalVersion = (($this->moduleCount - 17) / 4);
304
305 // no version info if v < 7
306 if($provisionalVersion < 7){
307 $this->version = new Version($provisionalVersion);
308
309 return $this;
310 }
311
312 // Read top-right version info: 3 wide by 6 tall
313 $versionBits = 0;
314 $ijMin = ($this->moduleCount - 11);
315
316 for($y = 5; $y >= 0; $y--){
317 for($x = ($this->moduleCount - 9); $x >= $ijMin; $x--){
318 $versionBits = $this->copyVersionBit($x, $y, $versionBits);
319 }
320 }
321
322 $this->version = $this->decodeVersionInformation($versionBits);
323
324 if($this->version !== null && $this->version->getDimension() === $this->moduleCount){
325 return $this;
326 }
327
328 // Hmm, failed. Try bottom left: 6 wide by 3 tall
329 $versionBits = 0;
330
331 for($x = 5; $x >= 0; $x--){
332 for($y = ($this->moduleCount - 9); $y >= $ijMin; $y--){
333 $versionBits = $this->copyVersionBit($x, $y, $versionBits);
334 }
335 }
336
337 $this->version = $this->decodeVersionInformation($versionBits);
338
339 if($this->version !== null && $this->version->getDimension() === $this->moduleCount){
340 return $this;
341 }
342
343 throw new QRCodeDecoderException('failed to read version');
344 }
345
346 /**
347 * Decodes the version information from the given bit sequence, returns null if no valid match is found.
348 */
349 private function decodeVersionInformation(int $versionBits):Version|null{
350 $bestDifference = PHP_INT_MAX;
351 $bestVersion = 0;
352
353 for($i = 7; $i <= 40; $i++){
354 $targetVersion = new Version($i);
355 $targetVersionPattern = $targetVersion->getVersionPattern();
356
357 // Do the version info bits match exactly? done.
358 if($targetVersionPattern === $versionBits){
359 return $targetVersion;
360 }
361
362 // Otherwise see if this is the closest to a real version info bit string
363 // we have seen so far
364 $bitsDifference = $this->numBitsDiffering($versionBits, $targetVersionPattern);
365
366 if($bitsDifference < $bestDifference){
367 $bestVersion = $i;
368 $bestDifference = $bitsDifference;
369 }
370 }
371 // We can tolerate up to 3 bits of error since no two version info codewords will
372 // differ in less than 8 bits.
373 if($bestDifference <= 3){
374 return new Version($bestVersion);
375 }
376
377 // If we didn't find a close enough match, fail
378 return null;
379 }
380
381 private function uRShift(int $a, int $b):int{
382
383 if($b === 0){
384 return $a;
385 }
386
387 return (($a >> $b) & ~((1 << (8 * PHP_INT_SIZE - 1)) >> ($b - 1)));
388 }
389
390 private function numBitsDiffering(int $a, int $b):int{
391 // a now has a 1 bit exactly where its bit differs with b's
392 $a ^= $b;
393 // Offset $i holds the number of 1-bits in the binary representation of $i
394 $BITS_SET_IN_HALF_BYTE = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];
395 // Count bits set quickly with a series of lookups:
396 $count = 0;
397
398 for($i = 0; $i < 32; $i += 4){
399 $count += $BITS_SET_IN_HALF_BYTE[($this->uRShift($a, $i) & 0x0F)];
400 }
401
402 return $count;
403 }
404
405 /**
406 * @codeCoverageIgnore
407 * @throws \chillerlan\QRCode\Data\QRCodeDataException
408 */
409 public function setQuietZone(int|null $quietZoneSize = null):static{
410 throw new QRCodeDataException('not supported');
411 }
412
413 /**
414 * @codeCoverageIgnore
415 * @throws \chillerlan\QRCode\Data\QRCodeDataException
416 */
417 public function setLogoSpace(int $width, int|null $height = null, int|null $startX = null, int|null $startY = null):static{
418 throw new QRCodeDataException('not supported');
419 }
420
421 }