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