chillerlan\QRCode\Decoder\BitMatrix

Complexity

Total Complexity

58

Size/Duplication

Total Lines	412
Duplicated Lines	0 %

Importance

Changes	2
Bugs	0	Features	0

13 Methods

Rating	Name	Duplication	Size	Complexity
B	readFormatInformation()	0	56	9
A	setLogoSpace()	0	2	1
A	decodeVersionInformation()	0	31	5
A	mirror()	0	12	4
A	__construct()	0	3	1
A	copyVersionBit()	0	7	3
A	numBitsDiffering()	0	13	2
B	readCodewords()	0	58	10
B	readVersion()	0	47	11
B	doDecodeFormatInformation()	0	35	8
A	setMirror()	0	7	1
A	setQuietZone()	0	2	1
A	uRShift()	0	7	2

<?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, count;
use const PHP_INT_MAX, PHP_INT_SIZE;

/**
 *
 */
final class BitMatrix extends QRMatrix{

	/**
	 * See ISO 18004:2006, Annex C, Table C.1
	 *
	 * [data bits, sequence after masking]
	 */
	private const DECODE_LOOKUP = [
		0x00 => 0x5412,
		0x01 => 0x5125,
		0x02 => 0x5E7C,
		0x03 => 0x5B4B,
		0x04 => 0x45F9,
		0x05 => 0x40CE,
		0x06 => 0x4F97,
		0x07 => 0x4AA0,
		0x08 => 0x77C4,
		0x09 => 0x72F3,
		0x0A => 0x7DAA,
		0x0B => 0x789D,
		0x0C => 0x662F,
		0x0D => 0x6318,
		0x0E => 0x6C41,
		0x0F => 0x6976,
		0x10 => 0x1689,
		0x11 => 0x13BE,
		0x12 => 0x1CE7,
		0x13 => 0x19D0,
		0x14 => 0x0762,
		0x15 => 0x0255,
		0x16 => 0x0D0C,
		0x17 => 0x083B,
		0x18 => 0x355F,
		0x19 => 0x3068,
		0x1A => 0x3F31,
		0x1B => 0x3A06,
		0x1C => 0x24B4,
		0x1D => 0x2183,
		0x1E => 0x2EDA,
		0x1F => 0x2BED,
	];

	private const FORMAT_INFO_MASK_QR = 0x5412;

	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));
	}

	/**
	 * Prepare the parser for a mirrored operation.
	 * This flag has effect only on the readFormatInformation() and the
	 * readVersion() methods. Before proceeding with readCodewords() the
	 * mirror() method should be called.
	 *
	 * @param bool $mirror Whether to read version and format information mirrored.
	 */
	public function setMirror(bool $mirror):self{
		$this->version     = null;
		$this->eccLevel    = null;
		$this->maskPattern = null;
		$this->mirror      = $mirror;

		return $this;
	}

	/**
	 * Mirror the bit matrix in order to attempt a second reading.
	 */
	public function mirror():self{

		for($x = 0; $x < $this->moduleCount; $x++){
			for($y = $x + 1; $y < $this->moduleCount; $y++){
				if($this->get($x, $y) !== $this->get($y, $x)){
					$this->flip($y, $x);
					$this->flip($x, $y);
				}
			}
		}

		return $this;
	}

	/**
	 * 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.
	 *
	 * @return array bytes encoded within the QR Code
	 * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException if the exact number of bytes expected is not read
	 */
	public function readCodewords():array{

		$this
			->readFormatInformation()
			->readVersion()
			->mask() // reverse the mask pattern
		;

		// invoke a fresh matrix with only the function & format patterns to compare against
		$fp        = (new QRMatrix($this->version, $this->eccLevel, $this->maskPattern))->initFunctionalPatterns();

It seems like $this->eccLevel can also be of type null; however, parameter $eccLevel of chillerlan\QRCode\Data\QRMatrix::__construct() does only seem to accept chillerlan\QRCode\Common\EccLevel, maybe add an additional type check?

It seems like $this->version can also be of type null; however, parameter $version of chillerlan\QRCode\Data\QRMatrix::__construct() does only seem to accept chillerlan\QRCode\Common\Version, maybe add an additional type check?

It seems like $this->maskPattern can also be of type null; however, parameter $maskPattern of chillerlan\QRCode\Data\QRMatrix::__construct() does only seem to accept chillerlan\QRCode\Common\MaskPattern, maybe add an additional type check?

		$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($fp->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

The condition $direction is always true.

		}

		if(count($result) !== $this->version->getTotalCodewords()){

The method getTotalCodewords() does not exist on null.

			throw new QRCodeDecoderException('result count differs from total codewords for version');
		}

		return $result;
	}

	/**
	 * Reads format information from one of its two locations within the QR Code.
	 *
	 * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException if both format information locations cannot be parsed as
	 *                                                           the valid encoding of format information
	 */
	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;
	}

	/**
	 * @param int $maskedFormatInfo1 format info indicator, with mask still applied
	 * @param int $maskedFormatInfo2 second copy of same info; both are checked at the same time
	 *                               to establish best match
	 *
	 * @return int|null information about the format it specifies, or null if doesn't seem to match any known pattern
	 */
	private function doDecodeFormatInformation(int $maskedFormatInfo1, int $maskedFormatInfo2):?int{
		// Find the int in FORMAT_INFO_DECODE_LOOKUP with fewest bits differing
		$bestDifference = PHP_INT_MAX;
		$bestFormatInfo = 0;

		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 \chillerlan\QRCode\Decoder\QRCodeDecoderException if both version information locations cannot be parsed as
	 *                                                           the valid encoding of version information
	 * @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');
	}

	/**
	 *
	 */
	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);

It seems like $targetVersionPattern can also be of type null; however, parameter $b of chillerlan\QRCode\Decoder\BitMatrix::numBitsDiffering() does only seem to accept integer, maybe add an additional type check?

			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 $size = null):self{
		throw new QRCodeDataException('not supported');
	}

	/**
	 * @codeCoverageIgnore
	 * @throws \chillerlan\QRCode\Data\QRCodeDataException
	 */
	public function setLogoSpace(int $width, int $height, int $startX = null, int $startY = null):self{
		throw new QRCodeDataException('not supported');
	}

}