diff options
Diffstat (limited to 'vendor/chillerlan/php-qrcode/src/Decoder')
6 files changed, 1396 insertions, 0 deletions
diff --git a/vendor/chillerlan/php-qrcode/src/Decoder/Binarizer.php b/vendor/chillerlan/php-qrcode/src/Decoder/Binarizer.php new file mode 100644 index 000000000..7b7b49f65 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Decoder/Binarizer.php @@ -0,0 +1,361 @@ +<?php +/** + * Class Binarizer + * + * @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\LuminanceSourceInterface; +use chillerlan\QRCode\Data\QRMatrix; +use function array_fill, count, intdiv, max; + +/** + * This class implements a local thresholding algorithm, which while slower than the + * GlobalHistogramBinarizer, is fairly efficient for what it does. It is designed for + * high frequency images of barcodes with black data on white backgrounds. For this application, + * it does a much better job than a global blackpoint with severe shadows and gradients. + * However, it tends to produce artifacts on lower frequency images and is therefore not + * a good general purpose binarizer for uses outside ZXing. + * + * This class extends GlobalHistogramBinarizer, using the older histogram approach for 1D readers, + * and the newer local approach for 2D readers. 1D decoding using a per-row histogram is already + * inherently local, and only fails for horizontal gradients. We can revisit that problem later, + * but for now it was not a win to use local blocks for 1D. + * + * This Binarizer is the default for the unit tests and the recommended class for library users. + * + * @author dswitkin@google.com (Daniel Switkin) + */ +final class Binarizer{ + + // This class uses 5x5 blocks to compute local luminance, where each block is 8x8 pixels. + // So this is the smallest dimension in each axis we can accept. + private const BLOCK_SIZE_POWER = 3; + private const BLOCK_SIZE = 8; // ...0100...00 + private const BLOCK_SIZE_MASK = 7; // ...0011...11 + private const MINIMUM_DIMENSION = 40; + private const MIN_DYNAMIC_RANGE = 24; + +# private const LUMINANCE_BITS = 5; + private const LUMINANCE_SHIFT = 3; + private const LUMINANCE_BUCKETS = 32; + + private LuminanceSourceInterface $source; + private array $luminances; + + /** + * + */ + public function __construct(LuminanceSourceInterface $source){ + $this->source = $source; + $this->luminances = $this->source->getLuminances(); + } + + /** + * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException + */ + private function estimateBlackPoint(array $buckets):int{ + // Find the tallest peak in the histogram. + $numBuckets = count($buckets); + $maxBucketCount = 0; + $firstPeak = 0; + $firstPeakSize = 0; + + for($x = 0; $x < $numBuckets; $x++){ + + if($buckets[$x] > $firstPeakSize){ + $firstPeak = $x; + $firstPeakSize = $buckets[$x]; + } + + if($buckets[$x] > $maxBucketCount){ + $maxBucketCount = $buckets[$x]; + } + } + + // Find the second-tallest peak which is somewhat far from the tallest peak. + $secondPeak = 0; + $secondPeakScore = 0; + + for($x = 0; $x < $numBuckets; $x++){ + $distanceToBiggest = ($x - $firstPeak); + // Encourage more distant second peaks by multiplying by square of distance. + $score = ($buckets[$x] * $distanceToBiggest * $distanceToBiggest); + + if($score > $secondPeakScore){ + $secondPeak = $x; + $secondPeakScore = $score; + } + } + + // Make sure firstPeak corresponds to the black peak. + if($firstPeak > $secondPeak){ + $temp = $firstPeak; + $firstPeak = $secondPeak; + $secondPeak = $temp; + } + + // If there is too little contrast in the image to pick a meaningful black point, throw rather + // than waste time trying to decode the image, and risk false positives. + if(($secondPeak - $firstPeak) <= ($numBuckets / 16)){ + throw new QRCodeDecoderException('no meaningful dark point found'); // @codeCoverageIgnore + } + + // Find a valley between them that is low and closer to the white peak. + $bestValley = ($secondPeak - 1); + $bestValleyScore = -1; + + for($x = ($secondPeak - 1); $x > $firstPeak; $x--){ + $fromFirst = ($x - $firstPeak); + $score = ($fromFirst * $fromFirst * ($secondPeak - $x) * ($maxBucketCount - $buckets[$x])); + + if($score > $bestValleyScore){ + $bestValley = $x; + $bestValleyScore = $score; + } + } + + return ($bestValley << self::LUMINANCE_SHIFT); + } + + /** + * Calculates the final BitMatrix once for all requests. This could be called once from the + * constructor instead, but there are some advantages to doing it lazily, such as making + * profiling easier, and not doing heavy lifting when callers don't expect it. + * + * Converts a 2D array of luminance data to 1 bit data. As above, assume this method is expensive + * and do not call it repeatedly. This method is intended for decoding 2D barcodes and may or + * may not apply sharpening. Therefore, a row from this matrix may not be identical to one + * fetched using getBlackRow(), so don't mix and match between them. + * + * @return \chillerlan\QRCode\Decoder\BitMatrix The 2D array of bits for the image (true means black). + */ + public function getBlackMatrix():BitMatrix{ + $width = $this->source->getWidth(); + $height = $this->source->getHeight(); + + if($width >= self::MINIMUM_DIMENSION && $height >= self::MINIMUM_DIMENSION){ + $subWidth = ($width >> self::BLOCK_SIZE_POWER); + + if(($width & self::BLOCK_SIZE_MASK) !== 0){ + $subWidth++; + } + + $subHeight = ($height >> self::BLOCK_SIZE_POWER); + + if(($height & self::BLOCK_SIZE_MASK) !== 0){ + $subHeight++; + } + + return $this->calculateThresholdForBlock($subWidth, $subHeight, $width, $height); + } + + // If the image is too small, fall back to the global histogram approach. + return $this->getHistogramBlackMatrix($width, $height); + } + + /** + * + */ + private function getHistogramBlackMatrix(int $width, int $height):BitMatrix{ + + // Quickly calculates the histogram by sampling four rows from the image. This proved to be + // more robust on the blackbox tests than sampling a diagonal as we used to do. + $buckets = array_fill(0, self::LUMINANCE_BUCKETS, 0); + $right = intdiv(($width * 4), 5); + $x = intdiv($width, 5); + + for($y = 1; $y < 5; $y++){ + $row = intdiv(($height * $y), 5); + $localLuminances = $this->source->getRow($row); + + for(; $x < $right; $x++){ + $pixel = ($localLuminances[$x] & 0xff); + $buckets[($pixel >> self::LUMINANCE_SHIFT)]++; + } + } + + $blackPoint = $this->estimateBlackPoint($buckets); + + // We delay reading the entire image luminance until the black point estimation succeeds. + // Although we end up reading four rows twice, it is consistent with our motto of + // "fail quickly" which is necessary for continuous scanning. + $matrix = new BitMatrix(max($width, $height)); + + for($y = 0; $y < $height; $y++){ + $offset = ($y * $width); + + for($x = 0; $x < $width; $x++){ + $matrix->set($x, $y, (($this->luminances[($offset + $x)] & 0xff) < $blackPoint), QRMatrix::M_DATA); + } + } + + return $matrix; + } + + /** + * Calculates a single black point for each block of pixels and saves it away. + * See the following thread for a discussion of this algorithm: + * + * @see http://groups.google.com/group/zxing/browse_thread/thread/d06efa2c35a7ddc0 + */ + private function calculateBlackPoints(int $subWidth, int $subHeight, int $width, int $height):array{ + $blackPoints = array_fill(0, $subHeight, array_fill(0, $subWidth, 0)); + + for($y = 0; $y < $subHeight; $y++){ + $yoffset = ($y << self::BLOCK_SIZE_POWER); + $maxYOffset = ($height - self::BLOCK_SIZE); + + if($yoffset > $maxYOffset){ + $yoffset = $maxYOffset; + } + + for($x = 0; $x < $subWidth; $x++){ + $xoffset = ($x << self::BLOCK_SIZE_POWER); + $maxXOffset = ($width - self::BLOCK_SIZE); + + if($xoffset > $maxXOffset){ + $xoffset = $maxXOffset; + } + + $sum = 0; + $min = 255; + $max = 0; + + for($yy = 0, $offset = ($yoffset * $width + $xoffset); $yy < self::BLOCK_SIZE; $yy++, $offset += $width){ + + for($xx = 0; $xx < self::BLOCK_SIZE; $xx++){ + $pixel = ((int)($this->luminances[(int)($offset + $xx)]) & 0xff); + $sum += $pixel; + // still looking for good contrast + if($pixel < $min){ + $min = $pixel; + } + + if($pixel > $max){ + $max = $pixel; + } + } + + // short-circuit min/max tests once dynamic range is met + if(($max - $min) > self::MIN_DYNAMIC_RANGE){ + // finish the rest of the rows quickly + for($yy++, $offset += $width; $yy < self::BLOCK_SIZE; $yy++, $offset += $width){ + for($xx = 0; $xx < self::BLOCK_SIZE; $xx++){ + $sum += ((int)($this->luminances[(int)($offset + $xx)]) & 0xff); + } + } + } + } + + // The default estimate is the average of the values in the block. + $average = ($sum >> (self::BLOCK_SIZE_POWER * 2)); + + if(($max - $min) <= self::MIN_DYNAMIC_RANGE){ + // If variation within the block is low, assume this is a block with only light or only + // dark pixels. In that case we do not want to use the average, as it would divide this + // low contrast area into black and white pixels, essentially creating data out of noise. + // + // The default assumption is that the block is light/background. Since no estimate for + // the level of dark pixels exists locally, use half the min for the block. + $average = ($min / 2); + + if($y > 0 && $x > 0){ + // Correct the "white background" assumption for blocks that have neighbors by comparing + // the pixels in this block to the previously calculated black points. This is based on + // the fact that dark barcode symbology is always surrounded by some amount of light + // background for which reasonable black point estimates were made. The bp estimated at + // the boundaries is used for the interior. + + // The (min < bp) is arbitrary but works better than other heuristics that were tried. + $averageNeighborBlackPoint = ( + ($blackPoints[($y - 1)][$x] + (2 * $blackPoints[$y][($x - 1)]) + $blackPoints[($y - 1)][($x - 1)]) / 4 + ); + + if($min < $averageNeighborBlackPoint){ + $average = $averageNeighborBlackPoint; + } + } + } + + $blackPoints[$y][$x] = $average; + } + } + + return $blackPoints; + } + + /** + * For each block in the image, calculate the average black point using a 5x5 grid + * of the surrounding blocks. Also handles the corner cases (fractional blocks are computed based + * on the last pixels in the row/column which are also used in the previous block). + */ + private function calculateThresholdForBlock(int $subWidth, int $subHeight, int $width, int $height):BitMatrix{ + $matrix = new BitMatrix(max($width, $height)); + $blackPoints = $this->calculateBlackPoints($subWidth, $subHeight, $width, $height); + + for($y = 0; $y < $subHeight; $y++){ + $yoffset = ($y << self::BLOCK_SIZE_POWER); + $maxYOffset = ($height - self::BLOCK_SIZE); + + if($yoffset > $maxYOffset){ + $yoffset = $maxYOffset; + } + + for($x = 0; $x < $subWidth; $x++){ + $xoffset = ($x << self::BLOCK_SIZE_POWER); + $maxXOffset = ($width - self::BLOCK_SIZE); + + if($xoffset > $maxXOffset){ + $xoffset = $maxXOffset; + } + + $left = $this->cap($x, 2, ($subWidth - 3)); + $top = $this->cap($y, 2, ($subHeight - 3)); + $sum = 0; + + for($z = -2; $z <= 2; $z++){ + $br = $blackPoints[($top + $z)]; + $sum += ($br[($left - 2)] + $br[($left - 1)] + $br[$left] + $br[($left + 1)] + $br[($left + 2)]); + } + + $average = (int)($sum / 25); + + // Applies a single threshold to a block of pixels. + for($j = 0, $o = ($yoffset * $width + $xoffset); $j < self::BLOCK_SIZE; $j++, $o += $width){ + for($i = 0; $i < self::BLOCK_SIZE; $i++){ + // Comparison needs to be <= so that black == 0 pixels are black even if the threshold is 0. + $v = (((int)($this->luminances[($o + $i)]) & 0xff) <= $average); + + $matrix->set(($xoffset + $i), ($yoffset + $j), $v, QRMatrix::M_DATA); + } + } + } + } + + return $matrix; + } + + /** + * @noinspection PhpSameParameterValueInspection + */ + private function cap(int $value, int $min, int $max):int{ + + if($value < $min){ + return $min; + } + + if($value > $max){ + return $max; + } + + return $value; + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Decoder/BitMatrix.php b/vendor/chillerlan/php-qrcode/src/Decoder/BitMatrix.php new file mode 100644 index 000000000..21f504e72 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Decoder/BitMatrix.php @@ -0,0 +1,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'); + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Decoder/Decoder.php b/vendor/chillerlan/php-qrcode/src/Decoder/Decoder.php new file mode 100644 index 000000000..6f369a6df --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Decoder/Decoder.php @@ -0,0 +1,173 @@ +<?php +/** + * Class Decoder + * + * @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\{BitBuffer, EccLevel, LuminanceSourceInterface, MaskPattern, Mode, Version}; +use chillerlan\QRCode\Data\{AlphaNum, Byte, ECI, Hanzi, Kanji, Number}; +use chillerlan\QRCode\Detector\Detector; +use Throwable; +use function chr, str_replace; + +/** + * The main class which implements QR Code decoding -- as opposed to locating and extracting + * the QR Code from an image. + * + * @author Sean Owen + */ +final class Decoder{ + + private ?Version $version = null; + private ?EccLevel $eccLevel = null; + private ?MaskPattern $maskPattern = null; + private BitBuffer $bitBuffer; + + /** + * Decodes a QR Code represented as a BitMatrix. + * A 1 or "true" is taken to mean a black module. + * + * @throws \Throwable|\chillerlan\QRCode\Decoder\QRCodeDecoderException + */ + public function decode(LuminanceSourceInterface $source):DecoderResult{ + $matrix = (new Detector($source))->detect(); + + try{ + // clone the BitMatrix to avoid errors in case we run into mirroring + return $this->decodeMatrix(clone $matrix); + } + catch(Throwable $e){ + + try{ + /* + * Prepare for a mirrored reading. + * + * Since we're here, this means we have successfully detected some kind + * of version and format information when mirrored. This is a good sign, + * that the QR code may be mirrored, and we should try once more with a + * mirrored content. + */ + return $this->decodeMatrix($matrix->resetVersionInfo()->mirrorDiagonal()); + } + catch(Throwable $f){ + // Throw the exception from the original reading + throw $e; + } + + } + + } + + /** + * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException + */ + private function decodeMatrix(BitMatrix $matrix):DecoderResult{ + // Read raw codewords + $rawCodewords = $matrix->readCodewords(); + $this->version = $matrix->getVersion(); + $this->eccLevel = $matrix->getEccLevel(); + $this->maskPattern = $matrix->getMaskPattern(); + + if($this->version === null || $this->eccLevel === null || $this->maskPattern === null){ + throw new QRCodeDecoderException('unable to read version or format info'); // @codeCoverageIgnore + } + + $resultBytes = (new ReedSolomonDecoder($this->version, $this->eccLevel))->decode($rawCodewords); + + return $this->decodeBitStream($resultBytes); + } + + /** + * Decode the contents of that stream of bytes + * + * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException + */ + private function decodeBitStream(BitBuffer $bitBuffer):DecoderResult{ + $this->bitBuffer = $bitBuffer; + $versionNumber = $this->version->getVersionNumber(); + $symbolSequence = -1; + $parityData = -1; + $fc1InEffect = false; + $result = ''; + + // While still another segment to read... + while($this->bitBuffer->available() >= 4){ + $datamode = $this->bitBuffer->read(4); // mode is encoded by 4 bits + + // OK, assume we're done + if($datamode === Mode::TERMINATOR){ + break; + } + elseif($datamode === Mode::NUMBER){ + $result .= Number::decodeSegment($this->bitBuffer, $versionNumber); + } + elseif($datamode === Mode::ALPHANUM){ + $result .= $this->decodeAlphanumSegment($versionNumber, $fc1InEffect); + } + elseif($datamode === Mode::BYTE){ + $result .= Byte::decodeSegment($this->bitBuffer, $versionNumber); + } + elseif($datamode === Mode::KANJI){ + $result .= Kanji::decodeSegment($this->bitBuffer, $versionNumber); + } + elseif($datamode === Mode::STRCTURED_APPEND){ + + if($this->bitBuffer->available() < 16){ + throw new QRCodeDecoderException('structured append: not enough bits left'); + } + // sequence number and parity is added later to the result metadata + // Read next 8 bits (symbol sequence #) and 8 bits (parity data), then continue + $symbolSequence = $this->bitBuffer->read(8); + $parityData = $this->bitBuffer->read(8); + } + elseif($datamode === Mode::FNC1_FIRST || $datamode === Mode::FNC1_SECOND){ + // We do little with FNC1 except alter the parsed result a bit according to the spec + $fc1InEffect = true; + } + elseif($datamode === Mode::ECI){ + $result .= ECI::decodeSegment($this->bitBuffer, $versionNumber); + } + elseif($datamode === Mode::HANZI){ + $result .= Hanzi::decodeSegment($this->bitBuffer, $versionNumber); + } + else{ + throw new QRCodeDecoderException('invalid data mode'); + } + + } + + return new DecoderResult([ + 'rawBytes' => $this->bitBuffer, + 'data' => $result, + 'version' => $this->version, + 'eccLevel' => $this->eccLevel, + 'maskPattern' => $this->maskPattern, + 'structuredAppendParity' => $parityData, + 'structuredAppendSequence' => $symbolSequence, + ]); + } + + /** + * + */ + private function decodeAlphanumSegment(int $versionNumber, bool $fc1InEffect):string{ + $str = AlphaNum::decodeSegment($this->bitBuffer, $versionNumber); + + // See section 6.4.8.1, 6.4.8.2 + if($fc1InEffect){ // ??? + // We need to massage the result a bit if in an FNC1 mode: + $str = str_replace(chr(0x1d), '%', $str); + $str = str_replace('%%', '%', $str); + } + + return $str; + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Decoder/DecoderResult.php b/vendor/chillerlan/php-qrcode/src/Decoder/DecoderResult.php new file mode 100644 index 000000000..13fd24ba8 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Decoder/DecoderResult.php @@ -0,0 +1,99 @@ +<?php +/** + * Class DecoderResult + * + * @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\{BitBuffer, EccLevel, MaskPattern, Version}; +use chillerlan\QRCode\Data\QRMatrix; +use function property_exists; + +/** + * Encapsulates the result of decoding a matrix of bits. This typically + * applies to 2D barcode formats. For now, it contains the raw bytes obtained + * as well as a String interpretation of those bytes, if applicable. + * + * @property \chillerlan\QRCode\Common\BitBuffer $rawBytes + * @property string $data + * @property \chillerlan\QRCode\Common\Version $version + * @property \chillerlan\QRCode\Common\EccLevel $eccLevel + * @property \chillerlan\QRCode\Common\MaskPattern $maskPattern + * @property int $structuredAppendParity + * @property int $structuredAppendSequence + */ +final class DecoderResult{ + + private BitBuffer $rawBytes; + private Version $version; + private EccLevel $eccLevel; + private MaskPattern $maskPattern; + private string $data = ''; + private int $structuredAppendParity = -1; + private int $structuredAppendSequence = -1; + + /** + * DecoderResult constructor. + */ + public function __construct(?iterable $properties = null){ + + if(!empty($properties)){ + + foreach($properties as $property => $value){ + + if(!property_exists($this, $property)){ + continue; + } + + $this->{$property} = $value; + } + + } + + } + + /** + * @return mixed|null + */ + public function __get(string $property){ + + if(property_exists($this, $property)){ + return $this->{$property}; + } + + return null; + } + + /** + * + */ + public function __toString():string{ + return $this->data; + } + + /** + * + */ + public function hasStructuredAppend():bool{ + return $this->structuredAppendParity >= 0 && $this->structuredAppendSequence >= 0; + } + + /** + * Returns a QRMatrix instance with the settings and data of the reader result + */ + public function getQRMatrix():QRMatrix{ + return (new QRMatrix($this->version, $this->eccLevel)) + ->initFunctionalPatterns() + ->writeCodewords($this->rawBytes) + ->setFormatInfo($this->maskPattern) + ->mask($this->maskPattern) + ; + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Decoder/QRCodeDecoderException.php b/vendor/chillerlan/php-qrcode/src/Decoder/QRCodeDecoderException.php new file mode 100644 index 000000000..11157afc1 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Decoder/QRCodeDecoderException.php @@ -0,0 +1,20 @@ +<?php +/** + * Class QRCodeDecoderException + * + * @created 01.12.2021 + * @author smiley <smiley@chillerlan.net> + * @copyright 2021 smiley + * @license MIT + */ + +namespace chillerlan\QRCode\Decoder; + +use chillerlan\QRCode\QRCodeException; + +/** + * An exception container + */ +final class QRCodeDecoderException extends QRCodeException{ + +} diff --git a/vendor/chillerlan/php-qrcode/src/Decoder/ReedSolomonDecoder.php b/vendor/chillerlan/php-qrcode/src/Decoder/ReedSolomonDecoder.php new file mode 100644 index 000000000..5f104a1c8 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Decoder/ReedSolomonDecoder.php @@ -0,0 +1,313 @@ +<?php +/** + * Class ReedSolomonDecoder + * + * @created 24.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\{BitBuffer, EccLevel, GenericGFPoly, GF256, Version}; +use function array_fill, array_reverse, count; + +/** + * Implements Reed-Solomon decoding + * + * The algorithm will not be explained here, but the following references were helpful + * in creating this implementation: + * + * - Bruce Maggs "Decoding Reed-Solomon Codes" (see discussion of Forney's Formula) + * http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps + * - J.I. Hall. "Chapter 5. Generalized Reed-Solomon Codes" (see discussion of Euclidean algorithm) + * https://users.math.msu.edu/users/halljo/classes/codenotes/GRS.pdf + * + * Much credit is due to William Rucklidge since portions of this code are an indirect + * port of his C++ Reed-Solomon implementation. + * + * @author Sean Owen + * @author William Rucklidge + * @author sanfordsquires + */ +final class ReedSolomonDecoder{ + + private Version $version; + private EccLevel $eccLevel; + + /** + * ReedSolomonDecoder constructor + */ + public function __construct(Version $version, EccLevel $eccLevel){ + $this->version = $version; + $this->eccLevel = $eccLevel; + } + + /** + * Error-correct and copy data blocks together into a stream of bytes + */ + public function decode(array $rawCodewords):BitBuffer{ + $dataBlocks = $this->deinterleaveRawBytes($rawCodewords); + $dataBytes = []; + + foreach($dataBlocks as [$numDataCodewords, $codewordBytes]){ + $corrected = $this->correctErrors($codewordBytes, $numDataCodewords); + + for($i = 0; $i < $numDataCodewords; $i++){ + $dataBytes[] = $corrected[$i]; + } + } + + return new BitBuffer($dataBytes); + } + + /** + * When QR Codes use multiple data blocks, they are actually interleaved. + * That is, the first byte of data block 1 to n is written, then the second bytes, and so on. This + * method will separate the data into original blocks. + * + * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException + */ + private function deinterleaveRawBytes(array $rawCodewords):array{ + // Figure out the number and size of data blocks used by this version and + // error correction level + [$numEccCodewords, $eccBlocks] = $this->version->getRSBlocks($this->eccLevel); + + // Now establish DataBlocks of the appropriate size and number of data codewords + $result = [];//new DataBlock[$totalBlocks]; + $numResultBlocks = 0; + + foreach($eccBlocks as [$numEccBlocks, $eccPerBlock]){ + for($i = 0; $i < $numEccBlocks; $i++, $numResultBlocks++){ + $result[$numResultBlocks] = [$eccPerBlock, array_fill(0, ($numEccCodewords + $eccPerBlock), 0)]; + } + } + + // All blocks have the same amount of data, except that the last n + // (where n may be 0) have 1 more byte. Figure out where these start. + /** @phan-suppress-next-line PhanTypePossiblyInvalidDimOffset */ + $shorterBlocksTotalCodewords = count($result[0][1]); + $longerBlocksStartAt = (count($result) - 1); + + while($longerBlocksStartAt >= 0){ + $numCodewords = count($result[$longerBlocksStartAt][1]); + + if($numCodewords === $shorterBlocksTotalCodewords){ + break; + } + + $longerBlocksStartAt--; + } + + $longerBlocksStartAt++; + + $shorterBlocksNumDataCodewords = ($shorterBlocksTotalCodewords - $numEccCodewords); + // The last elements of result may be 1 element longer; + // first fill out as many elements as all of them have + $rawCodewordsOffset = 0; + + for($i = 0; $i < $shorterBlocksNumDataCodewords; $i++){ + for($j = 0; $j < $numResultBlocks; $j++){ + $result[$j][1][$i] = $rawCodewords[$rawCodewordsOffset++]; + } + } + + // Fill out the last data block in the longer ones + for($j = $longerBlocksStartAt; $j < $numResultBlocks; $j++){ + $result[$j][1][$shorterBlocksNumDataCodewords] = $rawCodewords[$rawCodewordsOffset++]; + } + + // Now add in error correction blocks + /** @phan-suppress-next-line PhanTypePossiblyInvalidDimOffset */ + $max = count($result[0][1]); + + for($i = $shorterBlocksNumDataCodewords; $i < $max; $i++){ + for($j = 0; $j < $numResultBlocks; $j++){ + $iOffset = ($j < $longerBlocksStartAt) ? $i : ($i + 1); + $result[$j][1][$iOffset] = $rawCodewords[$rawCodewordsOffset++]; + } + } + + // DataBlocks containing original bytes, "de-interleaved" from representation in the QR Code + return $result; + } + + /** + * Given data and error-correction codewords received, possibly corrupted by errors, attempts to + * correct the errors in-place using Reed-Solomon error correction. + */ + private function correctErrors(array $codewordBytes, int $numDataCodewords):array{ + // First read into an array of ints + $codewordsInts = []; + + foreach($codewordBytes as $codewordByte){ + $codewordsInts[] = ($codewordByte & 0xFF); + } + + $decoded = $this->decodeWords($codewordsInts, (count($codewordBytes) - $numDataCodewords)); + + // Copy back into array of bytes -- only need to worry about the bytes that were data + // We don't care about errors in the error-correction codewords + for($i = 0; $i < $numDataCodewords; $i++){ + $codewordBytes[$i] = $decoded[$i]; + } + + return $codewordBytes; + } + + /** + * Decodes given set of received codewords, which include both data and error-correction + * codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place, + * in the input. + * + * @param array $received data and error-correction codewords + * @param int $numEccCodewords number of error-correction codewords available + * + * @return int[] + * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException if decoding fails for any reason + */ + private function decodeWords(array $received, int $numEccCodewords):array{ + $poly = new GenericGFPoly($received); + $syndromeCoefficients = []; + $error = false; + + for($i = 0; $i < $numEccCodewords; $i++){ + $syndromeCoefficients[$i] = $poly->evaluateAt(GF256::exp($i)); + + if($syndromeCoefficients[$i] !== 0){ + $error = true; + } + } + + if(!$error){ + return $received; + } + + [$sigma, $omega] = $this->runEuclideanAlgorithm( + GF256::buildMonomial($numEccCodewords, 1), + new GenericGFPoly(array_reverse($syndromeCoefficients)), + $numEccCodewords + ); + + $errorLocations = $this->findErrorLocations($sigma); + $errorMagnitudes = $this->findErrorMagnitudes($omega, $errorLocations); + $errorLocationsCount = count($errorLocations); + $receivedCount = count($received); + + for($i = 0; $i < $errorLocationsCount; $i++){ + $position = ($receivedCount - 1 - GF256::log($errorLocations[$i])); + + if($position < 0){ + throw new QRCodeDecoderException('Bad error location'); + } + + $received[$position] ^= $errorMagnitudes[$i]; + } + + return $received; + } + + /** + * @return \chillerlan\QRCode\Common\GenericGFPoly[] [sigma, omega] + * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException + */ + private function runEuclideanAlgorithm(GenericGFPoly $a, GenericGFPoly $b, int $z):array{ + // Assume a's degree is >= b's + if($a->getDegree() < $b->getDegree()){ + $temp = $a; + $a = $b; + $b = $temp; + } + + $rLast = $a; + $r = $b; + $tLast = new GenericGFPoly([0]); + $t = new GenericGFPoly([1]); + + // Run Euclidean algorithm until r's degree is less than z/2 + while((2 * $r->getDegree()) >= $z){ + $rLastLast = $rLast; + $tLastLast = $tLast; + $rLast = $r; + $tLast = $t; + + // Divide rLastLast by rLast, with quotient in q and remainder in r + [$q, $r] = $rLastLast->divide($rLast); + + $t = $q->multiply($tLast)->addOrSubtract($tLastLast); + + if($r->getDegree() >= $rLast->getDegree()){ + throw new QRCodeDecoderException('Division algorithm failed to reduce polynomial?'); + } + } + + $sigmaTildeAtZero = $t->getCoefficient(0); + + if($sigmaTildeAtZero === 0){ + throw new QRCodeDecoderException('sigmaTilde(0) was zero'); + } + + $inverse = GF256::inverse($sigmaTildeAtZero); + + return [$t->multiplyInt($inverse), $r->multiplyInt($inverse)]; + } + + /** + * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException + */ + private function findErrorLocations(GenericGFPoly $errorLocator):array{ + // This is a direct application of Chien's search + $numErrors = $errorLocator->getDegree(); + + if($numErrors === 1){ // shortcut + return [$errorLocator->getCoefficient(1)]; + } + + $result = array_fill(0, $numErrors, 0); + $e = 0; + + for($i = 1; $i < 256 && $e < $numErrors; $i++){ + if($errorLocator->evaluateAt($i) === 0){ + $result[$e] = GF256::inverse($i); + $e++; + } + } + + if($e !== $numErrors){ + throw new QRCodeDecoderException('Error locator degree does not match number of roots'); + } + + return $result; + } + + /** + * + */ + private function findErrorMagnitudes(GenericGFPoly $errorEvaluator, array $errorLocations):array{ + // This is directly applying Forney's Formula + $s = count($errorLocations); + $result = []; + + for($i = 0; $i < $s; $i++){ + $xiInverse = GF256::inverse($errorLocations[$i]); + $denominator = 1; + + for($j = 0; $j < $s; $j++){ + if($i !== $j){ +# $denominator = GF256::multiply($denominator, GF256::addOrSubtract(1, GF256::multiply($errorLocations[$j], $xiInverse))); + // Above should work but fails on some Apple and Linux JDKs due to a Hotspot bug. + // Below is a funny-looking workaround from Steven Parkes + $term = GF256::multiply($errorLocations[$j], $xiInverse); + $denominator = GF256::multiply($denominator, ((($term & 0x1) === 0) ? ($term | 1) : ($term & ~1))); + } + } + + $result[$i] = GF256::multiply($errorEvaluator->evaluateAt($xiInverse), GF256::inverse($denominator)); + } + + return $result; + } + +} |