MatrixUtil.php — WP 2FA – Two-factor authentication for WordPress 4.0.0

wp-2fa / includes / classes / bacon / bacon-qr-code / src / Encoder / MatrixUtil.php

wp-2fa / includes / classes / bacon / bacon-qr-code / src / Encoder Last commit date

BlockPair.php 1 week ago ByteMatrix.php 1 week ago Encoder.php 1 week ago MaskUtil.php 1 week ago MatrixUtil.php 1 week ago QrCode.php 1 week ago index.php 1 week ago

MatrixUtil.php

445 lines

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