Debian Codegraph @

src/Encoder/MatrixUtil.php

raw
1 <?php
2 declare(strict_types = 1);
3
4 namespace BaconQrCode\Encoder;
5
6 use BaconQrCode\Common\BitArray;
7 use BaconQrCode\Common\ErrorCorrectionLevel;
8 use BaconQrCode\Common\Version;
9 use BaconQrCode\Exception\RuntimeException;
10 use BaconQrCode\Exception\WriterException;
11
12 /**
13 * Matrix utility.
14 */
15 final class MatrixUtil
16 {
17 /**
18 * Position detection pattern.
19 */
20 private const POSITION_DETECTION_PATTERN = [
21 [1, 1, 1, 1, 1, 1, 1],
22 [1, 0, 0, 0, 0, 0, 1],
23 [1, 0, 1, 1, 1, 0, 1],
24 [1, 0, 1, 1, 1, 0, 1],
25 [1, 0, 1, 1, 1, 0, 1],
26 [1, 0, 0, 0, 0, 0, 1],
27 [1, 1, 1, 1, 1, 1, 1],
28 ];
29
30 /**
31 * Position adjustment pattern.
32 */
33 private const POSITION_ADJUSTMENT_PATTERN = [
34 [1, 1, 1, 1, 1],
35 [1, 0, 0, 0, 1],
36 [1, 0, 1, 0, 1],
37 [1, 0, 0, 0, 1],
38 [1, 1, 1, 1, 1],
39 ];
40
41 /**
42 * Coordinates for position adjustment patterns for each version.
43 */
44 private const POSITION_ADJUSTMENT_PATTERN_COORDINATE_TABLE = [
45 [null, null, null, null, null, null, null], // Version 1
46 [ 6, 18, null, null, null, null, null], // Version 2
47 [ 6, 22, null, null, null, null, null], // Version 3
48 [ 6, 26, null, null, null, null, null], // Version 4
49 [ 6, 30, null, null, null, null, null], // Version 5
50 [ 6, 34, null, null, null, null, null], // Version 6
51 [ 6, 22, 38, null, null, null, null], // Version 7
52 [ 6, 24, 42, null, null, null, null], // Version 8
53 [ 6, 26, 46, null, null, null, null], // Version 9
54 [ 6, 28, 50, null, null, null, null], // Version 10
55 [ 6, 30, 54, null, null, null, null], // Version 11
56 [ 6, 32, 58, null, null, null, null], // Version 12
57 [ 6, 34, 62, null, null, null, null], // Version 13
58 [ 6, 26, 46, 66, null, null, null], // Version 14
59 [ 6, 26, 48, 70, null, null, null], // Version 15
60 [ 6, 26, 50, 74, null, null, null], // Version 16
61 [ 6, 30, 54, 78, null, null, null], // Version 17
62 [ 6, 30, 56, 82, null, null, null], // Version 18
63 [ 6, 30, 58, 86, null, null, null], // Version 19
64 [ 6, 34, 62, 90, null, null, null], // Version 20
65 [ 6, 28, 50, 72, 94, null, null], // Version 21
66 [ 6, 26, 50, 74, 98, null, null], // Version 22
67 [ 6, 30, 54, 78, 102, null, null], // Version 23
68 [ 6, 28, 54, 80, 106, null, null], // Version 24
69 [ 6, 32, 58, 84, 110, null, null], // Version 25
70 [ 6, 30, 58, 86, 114, null, null], // Version 26
71 [ 6, 34, 62, 90, 118, null, null], // Version 27
72 [ 6, 26, 50, 74, 98, 122, null], // Version 28
73 [ 6, 30, 54, 78, 102, 126, null], // Version 29
74 [ 6, 26, 52, 78, 104, 130, null], // Version 30
75 [ 6, 30, 56, 82, 108, 134, null], // Version 31
76 [ 6, 34, 60, 86, 112, 138, null], // Version 32
77 [ 6, 30, 58, 86, 114, 142, null], // Version 33
78 [ 6, 34, 62, 90, 118, 146, null], // Version 34
79 [ 6, 30, 54, 78, 102, 126, 150], // Version 35
80 [ 6, 24, 50, 76, 102, 128, 154], // Version 36
81 [ 6, 28, 54, 80, 106, 132, 158], // Version 37
82 [ 6, 32, 58, 84, 110, 136, 162], // Version 38
83 [ 6, 26, 54, 82, 110, 138, 166], // Version 39
84 [ 6, 30, 58, 86, 114, 142, 170], // Version 40
85 ];
86
87 /**
88 * Type information coordinates.
89 */
90 private const TYPE_INFO_COORDINATES = [
91 [8, 0],
92 [8, 1],
93 [8, 2],
94 [8, 3],
95 [8, 4],
96 [8, 5],
97 [8, 7],
98 [8, 8],
99 [7, 8],
100 [5, 8],
101 [4, 8],
102 [3, 8],
103 [2, 8],
104 [1, 8],
105 [0, 8],
106 ];
107
108 /**
109 * Version information polynomial.
110 */
111 private const VERSION_INFO_POLY = 0x1f25;
112
113 /**
114 * Type information polynomial.
115 */
116 private const TYPE_INFO_POLY = 0x537;
117
118 /**
119 * Type information mask pattern.
120 */
121 private const TYPE_INFO_MASK_PATTERN = 0x5412;
122
123 /**
124 * Clears a given matrix.
125 */
126 public static function clearMatrix(ByteMatrix $matrix) : void
127 {
128 $matrix->clear(-1);
129 }
130
131 /**
132 * Builds a complete matrix.
133 */
134 public static function buildMatrix(
135 BitArray $dataBits,
136 ErrorCorrectionLevel $level,
137 Version $version,
138 int $maskPattern,
139 ByteMatrix $matrix
140 ) : void {
141 self::clearMatrix($matrix);
142 self::embedBasicPatterns($version, $matrix);
143 self::embedTypeInfo($level, $maskPattern, $matrix);
144 self::maybeEmbedVersionInfo($version, $matrix);
145 self::embedDataBits($dataBits, $maskPattern, $matrix);
146 }
147
148 /**
149 * Removes the position detection patterns from a matrix.
150 *
151 * This can be useful if you need to render those patterns separately.
152 */
153 public static function removePositionDetectionPatterns(ByteMatrix $matrix) : void
154 {
155 $pdpWidth = count(self::POSITION_DETECTION_PATTERN[0]);
156
157 self::removePositionDetectionPattern(0, 0, $matrix);
158 self::removePositionDetectionPattern($matrix->getWidth() - $pdpWidth, 0, $matrix);
159 self::removePositionDetectionPattern(0, $matrix->getWidth() - $pdpWidth, $matrix);
160 }
161
162 /**
163 * Embeds type information into a matrix.
164 */
165 private static function embedTypeInfo(ErrorCorrectionLevel $level, int $maskPattern, ByteMatrix $matrix) : void
166 {
167 $typeInfoBits = new BitArray();
168 self::makeTypeInfoBits($level, $maskPattern, $typeInfoBits);
169
170 $typeInfoBitsSize = $typeInfoBits->getSize();
171
172 for ($i = 0; $i < $typeInfoBitsSize; ++$i) {
173 $bit = $typeInfoBits->get($typeInfoBitsSize - 1 - $i);
174
175 $x1 = self::TYPE_INFO_COORDINATES[$i][0];
176 $y1 = self::TYPE_INFO_COORDINATES[$i][1];
177
178 $matrix->set($x1, $y1, (int) $bit);
179
180 if ($i < 8) {
181 $x2 = $matrix->getWidth() - $i - 1;
182 $y2 = 8;
183 } else {
184 $x2 = 8;
185 $y2 = $matrix->getHeight() - 7 + ($i - 8);
186 }
187
188 $matrix->set($x2, $y2, (int) $bit);
189 }
190 }
191
192 /**
193 * Generates type information bits and appends them to a bit array.
194 *
195 * @throws RuntimeException if bit array resulted in invalid size
196 */
197 private static function makeTypeInfoBits(ErrorCorrectionLevel $level, int $maskPattern, BitArray $bits) : void
198 {
199 $typeInfo = ($level->getBits() << 3) | $maskPattern;
200 $bits->appendBits($typeInfo, 5);
201
202 $bchCode = self::calculateBchCode($typeInfo, self::TYPE_INFO_POLY);
203 $bits->appendBits($bchCode, 10);
204
205 $maskBits = new BitArray();
206 $maskBits->appendBits(self::TYPE_INFO_MASK_PATTERN, 15);
207 $bits->xorBits($maskBits);
208
209 if (15 !== $bits->getSize()) {
210 throw new RuntimeException('Bit array resulted in invalid size: ' . $bits->getSize());
211 }
212 }
213
214 /**
215 * Embeds version information if required.
216 */
217 private static function maybeEmbedVersionInfo(Version $version, ByteMatrix $matrix) : void
218 {
219 if ($version->getVersionNumber() < 7) {
220 return;
221 }
222
223 $versionInfoBits = new BitArray();
224 self::makeVersionInfoBits($version, $versionInfoBits);
225
226 $bitIndex = 6 * 3 - 1;
227
228 for ($i = 0; $i < 6; ++$i) {
229 for ($j = 0; $j < 3; ++$j) {
230 $bit = $versionInfoBits->get($bitIndex);
231 --$bitIndex;
232
233 $matrix->set($i, $matrix->getHeight() - 11 + $j, (int) $bit);
234 $matrix->set($matrix->getHeight() - 11 + $j, $i, (int) $bit);
235 }
236 }
237 }
238
239 /**
240 * Generates version information bits and appends them to a bit array.
241 *
242 * @throws RuntimeException if bit array resulted in invalid size
243 */
244 private static function makeVersionInfoBits(Version $version, BitArray $bits) : void
245 {
246 $bits->appendBits($version->getVersionNumber(), 6);
247
248 $bchCode = self::calculateBchCode($version->getVersionNumber(), self::VERSION_INFO_POLY);
249 $bits->appendBits($bchCode, 12);
250
251 if (18 !== $bits->getSize()) {
252 throw new RuntimeException('Bit array resulted in invalid size: ' . $bits->getSize());
253 }
254 }
255
256 /**
257 * Calculates the BCH code for a value and a polynomial.
258 */
259 private static function calculateBchCode(int $value, int $poly) : int
260 {
261 $msbSetInPoly = self::findMsbSet($poly);
262 $value <<= $msbSetInPoly - 1;
263
264 while (self::findMsbSet($value) >= $msbSetInPoly) {
265 $value ^= $poly << (self::findMsbSet($value) - $msbSetInPoly);
266 }
267
268 return $value;
269 }
270
271 /**
272 * Finds and MSB set.
273 */
274 private static function findMsbSet(int $value) : int
275 {
276 $numDigits = 0;
277
278 while (0 !== $value) {
279 $value >>= 1;
280 ++$numDigits;
281 }
282
283 return $numDigits;
284 }
285
286 /**
287 * Embeds basic patterns into a matrix.
288 */
289 private static function embedBasicPatterns(Version $version, ByteMatrix $matrix) : void
290 {
291 self::embedPositionDetectionPatternsAndSeparators($matrix);
292 self::embedDarkDotAtLeftBottomCorner($matrix);
293 self::maybeEmbedPositionAdjustmentPatterns($version, $matrix);
294 self::embedTimingPatterns($matrix);
295 }
296
297 /**
298 * Embeds position detection patterns and separators into a byte matrix.
299 */
300 private static function embedPositionDetectionPatternsAndSeparators(ByteMatrix $matrix) : void
301 {
302 $pdpWidth = count(self::POSITION_DETECTION_PATTERN[0]);
303
304 self::embedPositionDetectionPattern(0, 0, $matrix);
305 self::embedPositionDetectionPattern($matrix->getWidth() - $pdpWidth, 0, $matrix);
306 self::embedPositionDetectionPattern(0, $matrix->getWidth() - $pdpWidth, $matrix);
307
308 $hspWidth = 8;
309
310 self::embedHorizontalSeparationPattern(0, $hspWidth - 1, $matrix);
311 self::embedHorizontalSeparationPattern($matrix->getWidth() - $hspWidth, $hspWidth - 1, $matrix);
312 self::embedHorizontalSeparationPattern(0, $matrix->getWidth() - $hspWidth, $matrix);
313
314 $vspSize = 7;
315
316 self::embedVerticalSeparationPattern($vspSize, 0, $matrix);
317 self::embedVerticalSeparationPattern($matrix->getHeight() - $vspSize - 1, 0, $matrix);
318 self::embedVerticalSeparationPattern($vspSize, $matrix->getHeight() - $vspSize, $matrix);
319 }
320
321 /**
322 * Embeds a single position detection pattern into a byte matrix.
323 */
324 private static function embedPositionDetectionPattern(int $xStart, int $yStart, ByteMatrix $matrix) : void
325 {
326 for ($y = 0; $y < 7; ++$y) {
327 for ($x = 0; $x < 7; ++$x) {
328 $matrix->set($xStart + $x, $yStart + $y, self::POSITION_DETECTION_PATTERN[$y][$x]);
329 }
330 }
331 }
332
333 private static function removePositionDetectionPattern(int $xStart, int $yStart, ByteMatrix $matrix) : void
334 {
335 for ($y = 0; $y < 7; ++$y) {
336 for ($x = 0; $x < 7; ++$x) {
337 $matrix->set($xStart + $x, $yStart + $y, 0);
338 }
339 }
340 }
341
342 /**
343 * Embeds a single horizontal separation pattern.
344 *
345 * @throws RuntimeException if a byte was already set
346 */
347 private static function embedHorizontalSeparationPattern(int $xStart, int $yStart, ByteMatrix $matrix) : void
348 {
349 for ($x = 0; $x < 8; $x++) {
350 if (-1 !== $matrix->get($xStart + $x, $yStart)) {
351 throw new RuntimeException('Byte already set');
352 }
353
354 $matrix->set($xStart + $x, $yStart, 0);
355 }
356 }
357
358 /**
359 * Embeds a single vertical separation pattern.
360 *
361 * @throws RuntimeException if a byte was already set
362 */
363 private static function embedVerticalSeparationPattern(int $xStart, int $yStart, ByteMatrix $matrix) : void
364 {
365 for ($y = 0; $y < 7; $y++) {
366 if (-1 !== $matrix->get($xStart, $yStart + $y)) {
367 throw new RuntimeException('Byte already set');
368 }
369
370 $matrix->set($xStart, $yStart + $y, 0);
371 }
372 }
373
374 /**
375 * Embeds a dot at the left bottom corner.
376 *
377 * @throws RuntimeException if a byte was already set to 0
378 */
379 private static function embedDarkDotAtLeftBottomCorner(ByteMatrix $matrix) : void
380 {
381 if (0 === $matrix->get(8, $matrix->getHeight() - 8)) {
382 throw new RuntimeException('Byte already set to 0');
383 }
384
385 $matrix->set(8, $matrix->getHeight() - 8, 1);
386 }
387
388 /**
389 * Embeds position adjustment patterns if required.
390 */
391 private static function maybeEmbedPositionAdjustmentPatterns(Version $version, ByteMatrix $matrix) : void
392 {
393 if ($version->getVersionNumber() < 2) {
394 return;
395 }
396
397 $index = $version->getVersionNumber() - 1;
398
399 $coordinates = self::POSITION_ADJUSTMENT_PATTERN_COORDINATE_TABLE[$index];
400 $numCoordinates = count($coordinates);
401
402 for ($i = 0; $i < $numCoordinates; ++$i) {
403 for ($j = 0; $j < $numCoordinates; ++$j) {
404 $y = $coordinates[$i];
405 $x = $coordinates[$j];
406
407 if (null === $x || null === $y) {
408 continue;
409 }
410
411 if (-1 === $matrix->get($x, $y)) {
412 self::embedPositionAdjustmentPattern($x - 2, $y - 2, $matrix);
413 }
414 }
415 }
416 }
417
418 /**
419 * Embeds a single position adjustment pattern.
420 */
421 private static function embedPositionAdjustmentPattern(int $xStart, int $yStart, ByteMatrix $matrix) : void
422 {
423 for ($y = 0; $y < 5; $y++) {
424 for ($x = 0; $x < 5; $x++) {
425 $matrix->set($xStart + $x, $yStart + $y, self::POSITION_ADJUSTMENT_PATTERN[$y][$x]);
426 }
427 }
428 }
429
430 /**
431 * Embeds timing patterns into a matrix.
432 */
433 private static function embedTimingPatterns(ByteMatrix $matrix) : void
434 {
435 $matrixWidth = $matrix->getWidth();
436
437 for ($i = 8; $i < $matrixWidth - 8; ++$i) {
438 $bit = ($i + 1) % 2;
439
440 if (-1 === $matrix->get($i, 6)) {
441 $matrix->set($i, 6, $bit);
442 }
443
444 if (-1 === $matrix->get(6, $i)) {
445 $matrix->set(6, $i, $bit);
446 }
447 }
448 }
449
450 /**
451 * Embeds "dataBits" using "getMaskPattern".
452 *
453 * For debugging purposes, it skips masking process if "getMaskPattern" is -1. See 8.7 of JISX0510:2004 (p.38) for
454 * how to embed data bits.
455 *
456 * @throws WriterException if not all bits could be consumed
457 */
458 private static function embedDataBits(BitArray $dataBits, int $maskPattern, ByteMatrix $matrix) : void
459 {
460 $bitIndex = 0;
461 $direction = -1;
462
463 // Start from the right bottom cell.
464 $x = $matrix->getWidth() - 1;
465 $y = $matrix->getHeight() - 1;
466
467 while ($x > 0) {
468 // Skip vertical timing pattern.
469 if (6 === $x) {
470 --$x;
471 }
472
473 while ($y >= 0 && $y < $matrix->getHeight()) {
474 for ($i = 0; $i < 2; $i++) {
475 $xx = $x - $i;
476
477 // Skip the cell if it's not empty.
478 if (-1 !== $matrix->get($xx, $y)) {
479 continue;
480 }
481
482 if ($bitIndex < $dataBits->getSize()) {
483 $bit = $dataBits->get($bitIndex);
484 ++$bitIndex;
485 } else {
486 // Padding bit. If there is no bit left, we'll fill the
487 // left cells with 0, as described in 8.4.9 of
488 // JISX0510:2004 (p. 24).
489 $bit = false;
490 }
491
492 // Skip masking if maskPattern is -1.
493 if (-1 !== $maskPattern && MaskUtil::getDataMaskBit($maskPattern, $xx, $y)) {
494 $bit = ! $bit;
495 }
496
497 $matrix->set($xx, $y, (int) $bit);
498 }
499
500 $y += $direction;
501 }
502
503 $direction = -$direction;
504 $y += $direction;
505 $x -= 2;
506 }
507
508 // All bits should be consumed
509 if ($dataBits->getSize() !== $bitIndex) {
510 throw new WriterException('Not all bits consumed (' . $bitIndex . ' out of ' . $dataBits->getSize() .')');
511 }
512 }
513 }