woocommerce-pos / vendor_prefixed / chillerlan / php-qrcode / src / Decoder / BitMatrix.php

BitMatrix.php in WCPOS – Point of Sale (POS) plugin for WooCommerce 1.10.19, at vendor_prefixed/chillerlan/php-qrcode/src/Decoder/BitMatrix.php

395 lines 14.2 KB

Raw Download Zip

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