diff options
Diffstat (limited to 'vendor/chillerlan/php-qrcode/src/Detector')
9 files changed, 1989 insertions, 0 deletions
diff --git a/vendor/chillerlan/php-qrcode/src/Detector/AlignmentPattern.php b/vendor/chillerlan/php-qrcode/src/Detector/AlignmentPattern.php new file mode 100644 index 000000000..72feafdfa --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/AlignmentPattern.php @@ -0,0 +1,34 @@ +<?php +/** + * Class AlignmentPattern + * + * @created 17.01.2021 + * @author ZXing Authors + * @author Smiley <smiley@chillerlan.net> + * @copyright 2021 Smiley + * @license Apache-2.0 + */ + +namespace chillerlan\QRCode\Detector; + +/** + * Encapsulates an alignment pattern, which are the smaller square patterns found in + * all but the simplest QR Codes. + * + * @author Sean Owen + */ +final class AlignmentPattern extends ResultPoint{ + + /** + * Combines this object's current estimate of a finder pattern position and module size + * with a new estimate. It returns a new FinderPattern containing an average of the two. + */ + public function combineEstimate(float $i, float $j, float $newModuleSize):self{ + return new self( + (($this->x + $j) / 2.0), + (($this->y + $i) / 2.0), + (($this->estimatedModuleSize + $newModuleSize) / 2.0) + ); + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Detector/AlignmentPatternFinder.php b/vendor/chillerlan/php-qrcode/src/Detector/AlignmentPatternFinder.php new file mode 100644 index 000000000..d9edc50bb --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/AlignmentPatternFinder.php @@ -0,0 +1,284 @@ +<?php +/** + * Class AlignmentPatternFinder + * + * @created 17.01.2021 + * @author ZXing Authors + * @author Smiley <smiley@chillerlan.net> + * @copyright 2021 Smiley + * @license Apache-2.0 + */ + +namespace chillerlan\QRCode\Detector; + +use chillerlan\QRCode\Decoder\BitMatrix; +use function abs, count; + +/** + * This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder + * patterns but are smaller and appear at regular intervals throughout the image. + * + * At the moment this only looks for the bottom-right alignment pattern. + * + * This is mostly a simplified copy of FinderPatternFinder. It is copied, + * pasted and stripped down here for maximum performance but does unfortunately duplicate + * some code. + * + * This class is thread-safe but not reentrant. Each thread must allocate its own object. + * + * @author Sean Owen + */ +final class AlignmentPatternFinder{ + + private BitMatrix $matrix; + private float $moduleSize; + /** @var \chillerlan\QRCode\Detector\AlignmentPattern[] */ + private array $possibleCenters; + + /** + * Creates a finder that will look in a portion of the whole image. + * + * @param \chillerlan\QRCode\Decoder\BitMatrix $matrix image to search + * @param float $moduleSize estimated module size so far + */ + public function __construct(BitMatrix $matrix, float $moduleSize){ + $this->matrix = $matrix; + $this->moduleSize = $moduleSize; + $this->possibleCenters = []; + } + + /** + * This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since + * it's pretty performance-critical and so is written to be fast foremost. + * + * @param int $startX left column from which to start searching + * @param int $startY top row from which to start searching + * @param int $width width of region to search + * @param int $height height of region to search + * + * @return \chillerlan\QRCode\Detector\AlignmentPattern|null + */ + public function find(int $startX, int $startY, int $width, int $height):?AlignmentPattern{ + $maxJ = ($startX + $width); + $middleI = ($startY + ($height / 2)); + $stateCount = []; + + // We are looking for black/white/black modules in 1:1:1 ratio; + // this tracks the number of black/white/black modules seen so far + for($iGen = 0; $iGen < $height; $iGen++){ + // Search from middle outwards + $i = (int)($middleI + ((($iGen & 0x01) === 0) ? ($iGen + 1) / 2 : -(($iGen + 1) / 2))); + $stateCount[0] = 0; + $stateCount[1] = 0; + $stateCount[2] = 0; + $j = $startX; + // Burn off leading white pixels before anything else; if we start in the middle of + // a white run, it doesn't make sense to count its length, since we don't know if the + // white run continued to the left of the start point + while($j < $maxJ && !$this->matrix->check($j, $i)){ + $j++; + } + + $currentState = 0; + + while($j < $maxJ){ + + if($this->matrix->check($j, $i)){ + // Black pixel + if($currentState === 1){ // Counting black pixels + $stateCount[$currentState]++; + } + // Counting white pixels + else{ + // A winner? + if($currentState === 2){ + // Yes + if($this->foundPatternCross($stateCount)){ + $confirmed = $this->handlePossibleCenter($stateCount, $i, $j); + + if($confirmed !== null){ + return $confirmed; + } + } + + $stateCount[0] = $stateCount[2]; + $stateCount[1] = 1; + $stateCount[2] = 0; + $currentState = 1; + } + else{ + $stateCount[++$currentState]++; + } + } + } + // White pixel + else{ + // Counting black pixels + if($currentState === 1){ + $currentState++; + } + + $stateCount[$currentState]++; + } + + $j++; + } + + if($this->foundPatternCross($stateCount)){ + $confirmed = $this->handlePossibleCenter($stateCount, $i, $maxJ); + + if($confirmed !== null){ + return $confirmed; + } + } + + } + + // Hmm, nothing we saw was observed and confirmed twice. If we had + // any guess at all, return it. + if(count($this->possibleCenters)){ + return $this->possibleCenters[0]; + } + + return null; + } + + /** + * @param int[] $stateCount count of black/white/black pixels just read + * + * @return bool true if the proportions of the counts is close enough to the 1/1/1 ratios + * used by alignment patterns to be considered a match + */ + private function foundPatternCross(array $stateCount):bool{ + $maxVariance = ($this->moduleSize / 2.0); + + for($i = 0; $i < 3; $i++){ + if(abs($this->moduleSize - $stateCount[$i]) >= $maxVariance){ + return false; + } + } + + return true; + } + + /** + * This is called when a horizontal scan finds a possible alignment pattern. It will + * cross-check with a vertical scan, and if successful, will see if this pattern had been + * found on a previous horizontal scan. If so, we consider it confirmed and conclude we have + * found the alignment pattern. + * + * @param int[] $stateCount reading state module counts from horizontal scan + * @param int $i row where alignment pattern may be found + * @param int $j end of possible alignment pattern in row + * + * @return \chillerlan\QRCode\Detector\AlignmentPattern|null if we have found the same pattern twice, or null if not + */ + private function handlePossibleCenter(array $stateCount, int $i, int $j):?AlignmentPattern{ + $stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2]); + $centerJ = $this->centerFromEnd($stateCount, $j); + $centerI = $this->crossCheckVertical($i, (int)$centerJ, (2 * $stateCount[1]), $stateCountTotal); + + if($centerI !== null){ + $estimatedModuleSize = (($stateCount[0] + $stateCount[1] + $stateCount[2]) / 3.0); + + foreach($this->possibleCenters as $center){ + // Look for about the same center and module size: + if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){ + return $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize); + } + } + + // Hadn't found this before; save it + $point = new AlignmentPattern($centerJ, $centerI, $estimatedModuleSize); + $this->possibleCenters[] = $point; + } + + return null; + } + + /** + * Given a count of black/white/black pixels just seen and an end position, + * figures the location of the center of this black/white/black run. + * + * @param int[] $stateCount + * @param int $end + * + * @return float + */ + private function centerFromEnd(array $stateCount, int $end):float{ + return (float)(($end - $stateCount[2]) - $stateCount[1] / 2); + } + + /** + * After a horizontal scan finds a potential alignment pattern, this method + * "cross-checks" by scanning down vertically through the center of the possible + * alignment pattern to see if the same proportion is detected. + * + * @param int $startI row where an alignment pattern was detected + * @param int $centerJ center of the section that appears to cross an alignment pattern + * @param int $maxCount maximum reasonable number of modules that should be + * observed in any reading state, based on the results of the horizontal scan + * @param int $originalStateCountTotal + * + * @return float|null vertical center of alignment pattern, or null if not found + */ + private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):?float{ + $maxI = $this->matrix->getSize(); + $stateCount = []; + $stateCount[0] = 0; + $stateCount[1] = 0; + $stateCount[2] = 0; + + // Start counting up from center + $i = $startI; + while($i >= 0 && $this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){ + $stateCount[1]++; + $i--; + } + // If already too many modules in this state or ran off the edge: + if($i < 0 || $stateCount[1] > $maxCount){ + return null; + } + + while($i >= 0 && !$this->matrix->check($centerJ, $i) && $stateCount[0] <= $maxCount){ + $stateCount[0]++; + $i--; + } + + if($stateCount[0] > $maxCount){ + return null; + } + + // Now also count down from center + $i = ($startI + 1); + while($i < $maxI && $this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){ + $stateCount[1]++; + $i++; + } + + if($i === $maxI || $stateCount[1] > $maxCount){ + return null; + } + + while($i < $maxI && !$this->matrix->check($centerJ, $i) && $stateCount[2] <= $maxCount){ + $stateCount[2]++; + $i++; + } + + if($stateCount[2] > $maxCount){ + return null; + } + + // phpcs:ignore + if((5 * abs(($stateCount[0] + $stateCount[1] + $stateCount[2]) - $originalStateCountTotal)) >= (2 * $originalStateCountTotal)){ + return null; + } + + if(!$this->foundPatternCross($stateCount)){ + return null; + } + + return $this->centerFromEnd($stateCount, $i); + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Detector/Detector.php b/vendor/chillerlan/php-qrcode/src/Detector/Detector.php new file mode 100644 index 000000000..123b685c6 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/Detector.php @@ -0,0 +1,350 @@ +<?php +/** + * Class Detector + * + * @created 17.01.2021 + * @author ZXing Authors + * @author Smiley <smiley@chillerlan.net> + * @copyright 2021 Smiley + * @license Apache-2.0 + */ + +namespace chillerlan\QRCode\Detector; + +use chillerlan\QRCode\Common\{LuminanceSourceInterface, Version}; +use chillerlan\QRCode\Decoder\{Binarizer, BitMatrix}; +use function abs, intdiv, is_nan, max, min, round; +use const NAN; + +/** + * Encapsulates logic that can detect a QR Code in an image, even if the QR Code + * is rotated or skewed, or partially obscured. + * + * @author Sean Owen + */ +final class Detector{ + + private BitMatrix $matrix; + + /** + * Detector constructor. + */ + public function __construct(LuminanceSourceInterface $source){ + $this->matrix = (new Binarizer($source))->getBlackMatrix(); + } + + /** + * Detects a QR Code in an image. + */ + public function detect():BitMatrix{ + [$bottomLeft, $topLeft, $topRight] = (new FinderPatternFinder($this->matrix))->find(); + + $moduleSize = $this->calculateModuleSize($topLeft, $topRight, $bottomLeft); + $dimension = $this->computeDimension($topLeft, $topRight, $bottomLeft, $moduleSize); + $provisionalVersion = new Version(intdiv(($dimension - 17), 4)); + $alignmentPattern = null; + + // Anything above version 1 has an alignment pattern + if(!empty($provisionalVersion->getAlignmentPattern())){ + // Guess where a "bottom right" finder pattern would have been + $bottomRightX = ($topRight->getX() - $topLeft->getX() + $bottomLeft->getX()); + $bottomRightY = ($topRight->getY() - $topLeft->getY() + $bottomLeft->getY()); + + // Estimate that alignment pattern is closer by 3 modules + // from "bottom right" to known top left location + $correctionToTopLeft = (1.0 - 3.0 / (float)($provisionalVersion->getDimension() - 7)); + $estAlignmentX = (int)($topLeft->getX() + $correctionToTopLeft * ($bottomRightX - $topLeft->getX())); + $estAlignmentY = (int)($topLeft->getY() + $correctionToTopLeft * ($bottomRightY - $topLeft->getY())); + + // Kind of arbitrary -- expand search radius before giving up + for($i = 4; $i <= 16; $i <<= 1){//?????????? + $alignmentPattern = $this->findAlignmentInRegion($moduleSize, $estAlignmentX, $estAlignmentY, (float)$i); + + if($alignmentPattern !== null){ + break; + } + } + // If we didn't find alignment pattern... well try anyway without it + } + + $transform = $this->createTransform($topLeft, $topRight, $bottomLeft, $dimension, $alignmentPattern); + + return (new GridSampler)->sampleGrid($this->matrix, $dimension, $transform); + } + + /** + * Computes an average estimated module size based on estimated derived from the positions + * of the three finder patterns. + * + * @throws \chillerlan\QRCode\Detector\QRCodeDetectorException + */ + private function calculateModuleSize(FinderPattern $topLeft, FinderPattern $topRight, FinderPattern $bottomLeft):float{ + // Take the average + $moduleSize = (( + $this->calculateModuleSizeOneWay($topLeft, $topRight) + + $this->calculateModuleSizeOneWay($topLeft, $bottomLeft) + ) / 2.0); + + if($moduleSize < 1.0){ + throw new QRCodeDetectorException('module size < 1.0'); + } + + return $moduleSize; + } + + /** + * Estimates module size based on two finder patterns -- it uses + * #sizeOfBlackWhiteBlackRunBothWays(int, int, int, int) to figure the + * width of each, measuring along the axis between their centers. + */ + private function calculateModuleSizeOneWay(FinderPattern $a, FinderPattern $b):float{ + + $moduleSizeEst1 = $this->sizeOfBlackWhiteBlackRunBothWays($a->getX(), $a->getY(), $b->getX(), $b->getY()); + $moduleSizeEst2 = $this->sizeOfBlackWhiteBlackRunBothWays($b->getX(), $b->getY(), $a->getX(), $a->getY()); + + if(is_nan($moduleSizeEst1)){ + return ($moduleSizeEst2 / 7.0); + } + + if(is_nan($moduleSizeEst2)){ + return ($moduleSizeEst1 / 7.0); + } + // Average them, and divide by 7 since we've counted the width of 3 black modules, + // and 1 white and 1 black module on either side. Ergo, divide sum by 14. + return (($moduleSizeEst1 + $moduleSizeEst2) / 14.0); + } + + /** + * See #sizeOfBlackWhiteBlackRun(int, int, int, int); computes the total width of + * a finder pattern by looking for a black-white-black run from the center in the direction + * of another po$(another finder pattern center), and in the opposite direction too. + * + * @noinspection DuplicatedCode + */ + private function sizeOfBlackWhiteBlackRunBothWays(float $fromX, float $fromY, float $toX, float $toY):float{ + $result = $this->sizeOfBlackWhiteBlackRun((int)$fromX, (int)$fromY, (int)$toX, (int)$toY); + $dimension = $this->matrix->getSize(); + // Now count other way -- don't run off image though of course + $scale = 1.0; + $otherToX = ($fromX - ($toX - $fromX)); + + if($otherToX < 0){ + $scale = ($fromX / ($fromX - $otherToX)); + $otherToX = 0; + } + elseif($otherToX >= $dimension){ + $scale = (($dimension - 1 - $fromX) / ($otherToX - $fromX)); + $otherToX = ($dimension - 1); + } + + $otherToY = (int)($fromY - ($toY - $fromY) * $scale); + $scale = 1.0; + + if($otherToY < 0){ + $scale = ($fromY / ($fromY - $otherToY)); + $otherToY = 0; + } + elseif($otherToY >= $dimension){ + $scale = (($dimension - 1 - $fromY) / ($otherToY - $fromY)); + $otherToY = ($dimension - 1); + } + + $otherToX = (int)($fromX + ($otherToX - $fromX) * $scale); + $result += $this->sizeOfBlackWhiteBlackRun((int)$fromX, (int)$fromY, $otherToX, $otherToY); + + // Middle pixel is double-counted this way; subtract 1 + return ($result - 1.0); + } + + /** + * This method traces a line from a po$in the image, in the direction towards another point. + * It begins in a black region, and keeps going until it finds white, then black, then white again. + * It reports the distance from the start to this point. + * + * This is used when figuring out how wide a finder pattern is, when the finder pattern + * may be skewed or rotated. + */ + private function sizeOfBlackWhiteBlackRun(int $fromX, int $fromY, int $toX, int $toY):float{ + // Mild variant of Bresenham's algorithm; + // @see https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm + $steep = abs($toY - $fromY) > abs($toX - $fromX); + + if($steep){ + $temp = $fromX; + $fromX = $fromY; + $fromY = $temp; + $temp = $toX; + $toX = $toY; + $toY = $temp; + } + + $dx = abs($toX - $fromX); + $dy = abs($toY - $fromY); + $error = (-$dx / 2); + $xstep = (($fromX < $toX) ? 1 : -1); + $ystep = (($fromY < $toY) ? 1 : -1); + + // In black pixels, looking for white, first or second time. + $state = 0; + // Loop up until x == toX, but not beyond + $xLimit = ($toX + $xstep); + + for($x = $fromX, $y = $fromY; $x !== $xLimit; $x += $xstep){ + $realX = ($steep) ? $y : $x; + $realY = ($steep) ? $x : $y; + + // Does current pixel mean we have moved white to black or vice versa? + // Scanning black in state 0,2 and white in state 1, so if we find the wrong + // color, advance to next state or end if we are in state 2 already + if(($state === 1) === $this->matrix->check($realX, $realY)){ + + if($state === 2){ + return FinderPattern::distance($x, $y, $fromX, $fromY); + } + + $state++; + } + + $error += $dy; + + if($error > 0){ + + if($y === $toY){ + break; + } + + $y += $ystep; + $error -= $dx; + } + } + + // Found black-white-black; give the benefit of the doubt that the next pixel outside the image + // is "white" so this last po$at (toX+xStep,toY) is the right ending. This is really a + // small approximation; (toX+xStep,toY+yStep) might be really correct. Ignore this. + if($state === 2){ + return FinderPattern::distance(($toX + $xstep), $toY, $fromX, $fromY); + } + + // else we didn't find even black-white-black; no estimate is really possible + return NAN; + } + + /** + * Computes the dimension (number of modules on a size) of the QR Code based on the position + * of the finder patterns and estimated module size. + * + * @throws \chillerlan\QRCode\Detector\QRCodeDetectorException + */ + private function computeDimension(FinderPattern $nw, FinderPattern $ne, FinderPattern $sw, float $size):int{ + $tltrCentersDimension = (int)round($nw->getDistance($ne) / $size); + $tlblCentersDimension = (int)round($nw->getDistance($sw) / $size); + $dimension = (int)((($tltrCentersDimension + $tlblCentersDimension) / 2) + 7); + + switch($dimension % 4){ + case 0: + $dimension++; + break; + // 1? do nothing + case 2: + $dimension--; + break; + case 3: + throw new QRCodeDetectorException('estimated dimension: '.$dimension); + } + + if(($dimension % 4) !== 1){ + throw new QRCodeDetectorException('dimension mod 4 is not 1'); + } + + return $dimension; + } + + /** + * Attempts to locate an alignment pattern in a limited region of the image, which is + * guessed to contain it. + * + * @param float $overallEstModuleSize estimated module size so far + * @param int $estAlignmentX x coordinate of center of area probably containing alignment pattern + * @param int $estAlignmentY y coordinate of above + * @param float $allowanceFactor number of pixels in all directions to search from the center + * + * @return \chillerlan\QRCode\Detector\AlignmentPattern|null if found, or null otherwise + */ + private function findAlignmentInRegion( + float $overallEstModuleSize, + int $estAlignmentX, + int $estAlignmentY, + float $allowanceFactor + ):?AlignmentPattern{ + // Look for an alignment pattern (3 modules in size) around where it should be + $dimension = $this->matrix->getSize(); + $allowance = (int)($allowanceFactor * $overallEstModuleSize); + $alignmentAreaLeftX = max(0, ($estAlignmentX - $allowance)); + $alignmentAreaRightX = min(($dimension - 1), ($estAlignmentX + $allowance)); + + if(($alignmentAreaRightX - $alignmentAreaLeftX) < ($overallEstModuleSize * 3)){ + return null; + } + + $alignmentAreaTopY = max(0, ($estAlignmentY - $allowance)); + $alignmentAreaBottomY = min(($dimension - 1), ($estAlignmentY + $allowance)); + + if(($alignmentAreaBottomY - $alignmentAreaTopY) < ($overallEstModuleSize * 3)){ + return null; + } + + return (new AlignmentPatternFinder($this->matrix, $overallEstModuleSize))->find( + $alignmentAreaLeftX, + $alignmentAreaTopY, + ($alignmentAreaRightX - $alignmentAreaLeftX), + ($alignmentAreaBottomY - $alignmentAreaTopY), + ); + } + + /** + * + */ + private function createTransform( + FinderPattern $nw, + FinderPattern $ne, + FinderPattern $sw, + int $size, + ?AlignmentPattern $ap = null + ):PerspectiveTransform{ + $dimMinusThree = ($size - 3.5); + + if($ap instanceof AlignmentPattern){ + $bottomRightX = $ap->getX(); + $bottomRightY = $ap->getY(); + $sourceBottomRightX = ($dimMinusThree - 3.0); + $sourceBottomRightY = $sourceBottomRightX; + } + else{ + // Don't have an alignment pattern, just make up the bottom-right point + $bottomRightX = ($ne->getX() - $nw->getX() + $sw->getX()); + $bottomRightY = ($ne->getY() - $nw->getY() + $sw->getY()); + $sourceBottomRightX = $dimMinusThree; + $sourceBottomRightY = $dimMinusThree; + } + + return (new PerspectiveTransform)->quadrilateralToQuadrilateral( + 3.5, + 3.5, + $dimMinusThree, + 3.5, + $sourceBottomRightX, + $sourceBottomRightY, + 3.5, + $dimMinusThree, + $nw->getX(), + $nw->getY(), + $ne->getX(), + $ne->getY(), + $bottomRightX, + $bottomRightY, + $sw->getX(), + $sw->getY() + ); + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Detector/FinderPattern.php b/vendor/chillerlan/php-qrcode/src/Detector/FinderPattern.php new file mode 100644 index 000000000..3ae4650ad --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/FinderPattern.php @@ -0,0 +1,92 @@ +<?php +/** + * Class FinderPattern + * + * @created 17.01.2021 + * @author ZXing Authors + * @author Smiley <smiley@chillerlan.net> + * @copyright 2021 Smiley + * @license Apache-2.0 + */ + +namespace chillerlan\QRCode\Detector; + +use function sqrt; + +/** + * Encapsulates a finder pattern, which are the three square patterns found in + * the corners of QR Codes. It also encapsulates a count of similar finder patterns, + * as a convenience to the finder's bookkeeping. + * + * @author Sean Owen + */ +final class FinderPattern extends ResultPoint{ + + private int $count; + + /** + * + */ + public function __construct(float $posX, float $posY, float $estimatedModuleSize, ?int $count = null){ + parent::__construct($posX, $posY, $estimatedModuleSize); + + $this->count = ($count ?? 1); + } + + /** + * + */ + public function getCount():int{ + return $this->count; + } + + /** + * @param \chillerlan\QRCode\Detector\FinderPattern $b second pattern + * + * @return float distance between two points + */ + public function getDistance(FinderPattern $b):float{ + return self::distance($this->x, $this->y, $b->x, $b->y); + } + + /** + * Get square of distance between a and b. + */ + public function getSquaredDistance(FinderPattern $b):float{ + return self::squaredDistance($this->x, $this->y, $b->x, $b->y); + } + + /** + * Combines this object's current estimate of a finder pattern position and module size + * with a new estimate. It returns a new FinderPattern containing a weighted average + * based on count. + */ + public function combineEstimate(float $i, float $j, float $newModuleSize):self{ + $combinedCount = ($this->count + 1); + + return new self( + ($this->count * $this->x + $j) / $combinedCount, + ($this->count * $this->y + $i) / $combinedCount, + ($this->count * $this->estimatedModuleSize + $newModuleSize) / $combinedCount, + $combinedCount + ); + } + + /** + * + */ + private static function squaredDistance(float $aX, float $aY, float $bX, float $bY):float{ + $xDiff = ($aX - $bX); + $yDiff = ($aY - $bY); + + return ($xDiff * $xDiff + $yDiff * $yDiff); + } + + /** + * + */ + public static function distance(float $aX, float $aY, float $bX, float $bY):float{ + return sqrt(self::squaredDistance($aX, $aY, $bX, $bY)); + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Detector/FinderPatternFinder.php b/vendor/chillerlan/php-qrcode/src/Detector/FinderPatternFinder.php new file mode 100644 index 000000000..61628d063 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/FinderPatternFinder.php @@ -0,0 +1,773 @@ +<?php +/** + * Class FinderPatternFinder + * + * @created 17.01.2021 + * @author ZXing Authors + * @author Smiley <smiley@chillerlan.net> + * @copyright 2021 Smiley + * @license Apache-2.0 + * + * @phan-file-suppress PhanTypePossiblyInvalidDimOffset + */ + +namespace chillerlan\QRCode\Detector; + +use chillerlan\QRCode\Decoder\BitMatrix; +use function abs, count, intdiv, usort; +use const PHP_FLOAT_MAX; + +/** + * This class attempts to find finder patterns in a QR Code. Finder patterns are the square + * markers at three corners of a QR Code. + * + * This class is thread-safe but not reentrant. Each thread must allocate its own object. + * + * @author Sean Owen + */ +final class FinderPatternFinder{ + + private const MIN_SKIP = 2; + private const MAX_MODULES = 177; // 1 pixel/module times 3 modules/center + private const CENTER_QUORUM = 2; // support up to version 10 for mobile clients + private BitMatrix $matrix; + /** @var \chillerlan\QRCode\Detector\FinderPattern[] */ + private array $possibleCenters; + private bool $hasSkipped = false; + + /** + * Creates a finder that will search the image for three finder patterns. + * + * @param BitMatrix $matrix image to search + */ + public function __construct(BitMatrix $matrix){ + $this->matrix = $matrix; + $this->possibleCenters = []; + } + + /** + * @return \chillerlan\QRCode\Detector\FinderPattern[] + */ + public function find():array{ + $dimension = $this->matrix->getSize(); + + // We are looking for black/white/black/white/black modules in + // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far + // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the + // image, and then account for the center being 3 modules in size. This gives the smallest + // number of pixels the center could be, so skip this often. + $iSkip = intdiv((3 * $dimension), (4 * self::MAX_MODULES)); + + if($iSkip < self::MIN_SKIP){ + $iSkip = self::MIN_SKIP; + } + + $done = false; + + for($i = ($iSkip - 1); ($i < $dimension) && !$done; $i += $iSkip){ + // Get a row of black/white values + $stateCount = $this->getCrossCheckStateCount(); + $currentState = 0; + + for($j = 0; $j < $dimension; $j++){ + + // Black pixel + if($this->matrix->check($j, $i)){ + // Counting white pixels + if(($currentState & 1) === 1){ + $currentState++; + } + + $stateCount[$currentState]++; + } + // White pixel + else{ + // Counting black pixels + if(($currentState & 1) === 0){ + // A winner? + if($currentState === 4){ + // Yes + if($this->foundPatternCross($stateCount)){ + $confirmed = $this->handlePossibleCenter($stateCount, $i, $j); + + if($confirmed){ + // Start examining every other line. Checking each line turned out to be too + // expensive and didn't improve performance. + $iSkip = 3; + + if($this->hasSkipped){ + $done = $this->haveMultiplyConfirmedCenters(); + } + else{ + $rowSkip = $this->findRowSkip(); + + if($rowSkip > $stateCount[2]){ + // Skip rows between row of lower confirmed center + // and top of presumed third confirmed center + // but back up a bit to get a full chance of detecting + // it, entire width of center of finder pattern + + // Skip by rowSkip, but back off by $stateCount[2] (size of last center + // of pattern we saw) to be conservative, and also back off by iSkip which + // is about to be re-added + $i += ($rowSkip - $stateCount[2] - $iSkip); + $j = ($dimension - 1); + } + } + } + else{ + $stateCount = $this->doShiftCounts2($stateCount); + $currentState = 3; + + continue; + } + // Clear state to start looking again + $currentState = 0; + $stateCount = $this->getCrossCheckStateCount(); + } + // No, shift counts back by two + else{ + $stateCount = $this->doShiftCounts2($stateCount); + $currentState = 3; + } + } + else{ + $stateCount[++$currentState]++; + } + } + // Counting white pixels + else{ + $stateCount[$currentState]++; + } + } + } + + if($this->foundPatternCross($stateCount)){ + $confirmed = $this->handlePossibleCenter($stateCount, $i, $dimension); + + if($confirmed){ + $iSkip = $stateCount[0]; + + if($this->hasSkipped){ + // Found a third one + $done = $this->haveMultiplyConfirmedCenters(); + } + } + } + } + + return $this->orderBestPatterns($this->selectBestPatterns()); + } + + /** + * @return int[] + */ + private function getCrossCheckStateCount():array{ + return [0, 0, 0, 0, 0]; + } + + /** + * @param int[] $stateCount + * + * @return int[] + */ + private function doShiftCounts2(array $stateCount):array{ + $stateCount[0] = $stateCount[2]; + $stateCount[1] = $stateCount[3]; + $stateCount[2] = $stateCount[4]; + $stateCount[3] = 1; + $stateCount[4] = 0; + + return $stateCount; + } + + /** + * Given a count of black/white/black/white/black pixels just seen and an end position, + * figures the location of the center of this run. + * + * @param int[] $stateCount + */ + private function centerFromEnd(array $stateCount, int $end):float{ + return (float)(($end - $stateCount[4] - $stateCount[3]) - $stateCount[2] / 2); + } + + /** + * @param int[] $stateCount + */ + private function foundPatternCross(array $stateCount):bool{ + // Allow less than 50% variance from 1-1-3-1-1 proportions + return $this->foundPatternVariance($stateCount, 2.0); + } + + /** + * @param int[] $stateCount + */ + private function foundPatternDiagonal(array $stateCount):bool{ + // Allow less than 75% variance from 1-1-3-1-1 proportions + return $this->foundPatternVariance($stateCount, 1.333); + } + + /** + * @param int[] $stateCount count of black/white/black/white/black pixels just read + * + * @return bool true if the proportions of the counts is close enough to the 1/1/3/1/1 ratios + * used by finder patterns to be considered a match + */ + private function foundPatternVariance(array $stateCount, float $variance):bool{ + $totalModuleSize = 0; + + for($i = 0; $i < 5; $i++){ + $count = $stateCount[$i]; + + if($count === 0){ + return false; + } + + $totalModuleSize += $count; + } + + if($totalModuleSize < 7){ + return false; + } + + $moduleSize = ($totalModuleSize / 7.0); + $maxVariance = ($moduleSize / $variance); + + return + abs($moduleSize - $stateCount[0]) < $maxVariance + && abs($moduleSize - $stateCount[1]) < $maxVariance + && abs(3.0 * $moduleSize - $stateCount[2]) < (3 * $maxVariance) + && abs($moduleSize - $stateCount[3]) < $maxVariance + && abs($moduleSize - $stateCount[4]) < $maxVariance; + } + + /** + * After a vertical and horizontal scan finds a potential finder pattern, this method + * "cross-cross-cross-checks" by scanning down diagonally through the center of the possible + * finder pattern to see if the same proportion is detected. + * + * @param int $centerI row where a finder pattern was detected + * @param int $centerJ center of the section that appears to cross a finder pattern + * + * @return bool true if proportions are withing expected limits + */ + private function crossCheckDiagonal(int $centerI, int $centerJ):bool{ + $stateCount = $this->getCrossCheckStateCount(); + + // Start counting up, left from center finding black center mass + $i = 0; + + while($centerI >= $i && $centerJ >= $i && $this->matrix->check(($centerJ - $i), ($centerI - $i))){ + $stateCount[2]++; + $i++; + } + + if($stateCount[2] === 0){ + return false; + } + + // Continue up, left finding white space + while($centerI >= $i && $centerJ >= $i && !$this->matrix->check(($centerJ - $i), ($centerI - $i))){ + $stateCount[1]++; + $i++; + } + + if($stateCount[1] === 0){ + return false; + } + + // Continue up, left finding black border + while($centerI >= $i && $centerJ >= $i && $this->matrix->check(($centerJ - $i), ($centerI - $i))){ + $stateCount[0]++; + $i++; + } + + if($stateCount[0] === 0){ + return false; + } + + $dimension = $this->matrix->getSize(); + + // Now also count down, right from center + $i = 1; + // phpcs:ignore + while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && $this->matrix->check(($centerJ + $i), ($centerI + $i))){ + $stateCount[2]++; + $i++; + } + + // phpcs:ignore + while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && !$this->matrix->check(($centerJ + $i), ($centerI + $i))){ + $stateCount[3]++; + $i++; + } + + if($stateCount[3] === 0){ + return false; + } + + // phpcs:ignore + while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && $this->matrix->check(($centerJ + $i), ($centerI + $i))){ + $stateCount[4]++; + $i++; + } + + if($stateCount[4] === 0){ + return false; + } + + return $this->foundPatternDiagonal($stateCount); + } + + /** + * After a horizontal scan finds a potential finder pattern, this method + * "cross-checks" by scanning down vertically through the center of the possible + * finder pattern to see if the same proportion is detected. + * + * @param int $startI row where a finder pattern was detected + * @param int $centerJ center of the section that appears to cross a finder pattern + * @param int $maxCount maximum reasonable number of modules that should be + * observed in any reading state, based on the results of the horizontal scan + * @param int $originalStateCountTotal + * + * @return float|null vertical center of finder pattern, or null if not found + * @noinspection DuplicatedCode + */ + private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):?float{ + $maxI = $this->matrix->getSize(); + $stateCount = $this->getCrossCheckStateCount(); + + // Start counting up from center + $i = $startI; + while($i >= 0 && $this->matrix->check($centerJ, $i)){ + $stateCount[2]++; + $i--; + } + + if($i < 0){ + return null; + } + + while($i >= 0 && !$this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){ + $stateCount[1]++; + $i--; + } + + // If already too many modules in this state or ran off the edge: + if($i < 0 || $stateCount[1] > $maxCount){ + return null; + } + + while($i >= 0 && $this->matrix->check($centerJ, $i) && $stateCount[0] <= $maxCount){ + $stateCount[0]++; + $i--; + } + + if($stateCount[0] > $maxCount){ + return null; + } + + // Now also count down from center + $i = ($startI + 1); + while($i < $maxI && $this->matrix->check($centerJ, $i)){ + $stateCount[2]++; + $i++; + } + + if($i === $maxI){ + return null; + } + + while($i < $maxI && !$this->matrix->check($centerJ, $i) && $stateCount[3] < $maxCount){ + $stateCount[3]++; + $i++; + } + + if($i === $maxI || $stateCount[3] >= $maxCount){ + return null; + } + + while($i < $maxI && $this->matrix->check($centerJ, $i) && $stateCount[4] < $maxCount){ + $stateCount[4]++; + $i++; + } + + if($stateCount[4] >= $maxCount){ + return null; + } + + // If we found a finder-pattern-like section, but its size is more than 40% different from + // the original, assume it's a false positive + $stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]); + + if((5 * abs($stateCountTotal - $originalStateCountTotal)) >= (2 * $originalStateCountTotal)){ + return null; + } + + if(!$this->foundPatternCross($stateCount)){ + return null; + } + + return $this->centerFromEnd($stateCount, $i); + } + + /** + * Like #crossCheckVertical(int, int, int, int), and in fact is basically identical, + * except it reads horizontally instead of vertically. This is used to cross-cross + * check a vertical cross-check and locate the real center of the alignment pattern. + * @noinspection DuplicatedCode + */ + private function crossCheckHorizontal(int $startJ, int $centerI, int $maxCount, int $originalStateCountTotal):?float{ + $maxJ = $this->matrix->getSize(); + $stateCount = $this->getCrossCheckStateCount(); + + $j = $startJ; + while($j >= 0 && $this->matrix->check($j, $centerI)){ + $stateCount[2]++; + $j--; + } + + if($j < 0){ + return null; + } + + while($j >= 0 && !$this->matrix->check($j, $centerI) && $stateCount[1] <= $maxCount){ + $stateCount[1]++; + $j--; + } + + if($j < 0 || $stateCount[1] > $maxCount){ + return null; + } + + while($j >= 0 && $this->matrix->check($j, $centerI) && $stateCount[0] <= $maxCount){ + $stateCount[0]++; + $j--; + } + + if($stateCount[0] > $maxCount){ + return null; + } + + $j = ($startJ + 1); + while($j < $maxJ && $this->matrix->check($j, $centerI)){ + $stateCount[2]++; + $j++; + } + + if($j === $maxJ){ + return null; + } + + while($j < $maxJ && !$this->matrix->check($j, $centerI) && $stateCount[3] < $maxCount){ + $stateCount[3]++; + $j++; + } + + if($j === $maxJ || $stateCount[3] >= $maxCount){ + return null; + } + + while($j < $maxJ && $this->matrix->check($j, $centerI) && $stateCount[4] < $maxCount){ + $stateCount[4]++; + $j++; + } + + if($stateCount[4] >= $maxCount){ + return null; + } + + // If we found a finder-pattern-like section, but its size is significantly different from + // the original, assume it's a false positive + $stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]); + + if((5 * abs($stateCountTotal - $originalStateCountTotal)) >= $originalStateCountTotal){ + return null; + } + + if(!$this->foundPatternCross($stateCount)){ + return null; + } + + return $this->centerFromEnd($stateCount, $j); + } + + /** + * This is called when a horizontal scan finds a possible alignment pattern. It will + * cross-check with a vertical scan, and if successful, will, ah, cross-cross-check + * with another horizontal scan. This is needed primarily to locate the real horizontal + * center of the pattern in cases of extreme skew. + * And then we cross-cross-cross check with another diagonal scan. + * + * If that succeeds the finder pattern location is added to a list that tracks + * the number of times each location has been nearly-matched as a finder pattern. + * Each additional find is more evidence that the location is in fact a finder + * pattern center + * + * @param int[] $stateCount reading state module counts from horizontal scan + * @param int $i row where finder pattern may be found + * @param int $j end of possible finder pattern in row + * + * @return bool if a finder pattern candidate was found this time + */ + private function handlePossibleCenter(array $stateCount, int $i, int $j):bool{ + $stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]); + $centerJ = $this->centerFromEnd($stateCount, $j); + $centerI = $this->crossCheckVertical($i, (int)$centerJ, $stateCount[2], $stateCountTotal); + + if($centerI !== null){ + // Re-cross check + $centerJ = $this->crossCheckHorizontal((int)$centerJ, (int)$centerI, $stateCount[2], $stateCountTotal); + if($centerJ !== null && ($this->crossCheckDiagonal((int)$centerI, (int)$centerJ))){ + $estimatedModuleSize = ($stateCountTotal / 7.0); + $found = false; + + // cautious (was in for fool in which $this->possibleCenters is updated) + $count = count($this->possibleCenters); + + for($index = 0; $index < $count; $index++){ + $center = $this->possibleCenters[$index]; + // Look for about the same center and module size: + if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){ + $this->possibleCenters[$index] = $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize); + $found = true; + break; + } + } + + if(!$found){ + $point = new FinderPattern($centerJ, $centerI, $estimatedModuleSize); + $this->possibleCenters[] = $point; + } + + return true; + } + } + + return false; + } + + /** + * @return int number of rows we could safely skip during scanning, based on the first + * two finder patterns that have been located. In some cases their position will + * allow us to infer that the third pattern must lie below a certain point farther + * down in the image. + */ + private function findRowSkip():int{ + $max = count($this->possibleCenters); + + if($max <= 1){ + return 0; + } + + $firstConfirmedCenter = null; + + foreach($this->possibleCenters as $center){ + + if($center->getCount() >= self::CENTER_QUORUM){ + + if($firstConfirmedCenter === null){ + $firstConfirmedCenter = $center; + } + else{ + // We have two confirmed centers + // How far down can we skip before resuming looking for the next + // pattern? In the worst case, only the difference between the + // difference in the x / y coordinates of the two centers. + // This is the case where you find top left last. + $this->hasSkipped = true; + + return (int)((abs($firstConfirmedCenter->getX() - $center->getX()) - + abs($firstConfirmedCenter->getY() - $center->getY())) / 2); + } + } + } + + return 0; + } + + /** + * @return bool true if we have found at least 3 finder patterns that have been detected + * at least #CENTER_QUORUM times each, and, the estimated module size of the + * candidates is "pretty similar" + */ + private function haveMultiplyConfirmedCenters():bool{ + $confirmedCount = 0; + $totalModuleSize = 0.0; + $max = count($this->possibleCenters); + + foreach($this->possibleCenters as $pattern){ + if($pattern->getCount() >= self::CENTER_QUORUM){ + $confirmedCount++; + $totalModuleSize += $pattern->getEstimatedModuleSize(); + } + } + + if($confirmedCount < 3){ + return false; + } + // OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive" + // and that we need to keep looking. We detect this by asking if the estimated module sizes + // vary too much. We arbitrarily say that when the total deviation from average exceeds + // 5% of the total module size estimates, it's too much. + $average = ($totalModuleSize / (float)$max); + $totalDeviation = 0.0; + + foreach($this->possibleCenters as $pattern){ + $totalDeviation += abs($pattern->getEstimatedModuleSize() - $average); + } + + return $totalDeviation <= (0.05 * $totalModuleSize); + } + + /** + * @return \chillerlan\QRCode\Detector\FinderPattern[] the 3 best FinderPatterns from our list of candidates. The "best" are + * those that have been detected at least #CENTER_QUORUM times, and whose module + * size differs from the average among those patterns the least + * @throws \chillerlan\QRCode\Detector\QRCodeDetectorException if 3 such finder patterns do not exist + */ + private function selectBestPatterns():array{ + $startSize = count($this->possibleCenters); + + if($startSize < 3){ + throw new QRCodeDetectorException('could not find enough finder patterns'); + } + + usort( + $this->possibleCenters, + fn(FinderPattern $a, FinderPattern $b) => ($a->getEstimatedModuleSize() <=> $b->getEstimatedModuleSize()) + ); + + $distortion = PHP_FLOAT_MAX; + $bestPatterns = []; + + for($i = 0; $i < ($startSize - 2); $i++){ + $fpi = $this->possibleCenters[$i]; + $minModuleSize = $fpi->getEstimatedModuleSize(); + + for($j = ($i + 1); $j < ($startSize - 1); $j++){ + $fpj = $this->possibleCenters[$j]; + $squares0 = $fpi->getSquaredDistance($fpj); + + for($k = ($j + 1); $k < $startSize; $k++){ + $fpk = $this->possibleCenters[$k]; + $maxModuleSize = $fpk->getEstimatedModuleSize(); + + // module size is not similar + if($maxModuleSize > ($minModuleSize * 1.4)){ + continue; + } + + $a = $squares0; + $b = $fpj->getSquaredDistance($fpk); + $c = $fpi->getSquaredDistance($fpk); + + // sorts ascending - inlined + if($a < $b){ + if($b > $c){ + if($a < $c){ + $temp = $b; + $b = $c; + $c = $temp; + } + else{ + $temp = $a; + $a = $c; + $c = $b; + $b = $temp; + } + } + } + else{ + if($b < $c){ + if($a < $c){ + $temp = $a; + $a = $b; + $b = $temp; + } + else{ + $temp = $a; + $a = $b; + $b = $c; + $c = $temp; + } + } + else{ + $temp = $a; + $a = $c; + $c = $temp; + } + } + + // a^2 + b^2 = c^2 (Pythagorean theorem), and a = b (isosceles triangle). + // Since any right triangle satisfies the formula c^2 - b^2 - a^2 = 0, + // we need to check both two equal sides separately. + // The value of |c^2 - 2 * b^2| + |c^2 - 2 * a^2| increases as dissimilarity + // from isosceles right triangle. + $d = (abs($c - 2 * $b) + abs($c - 2 * $a)); + + if($d < $distortion){ + $distortion = $d; + $bestPatterns = [$fpi, $fpj, $fpk]; + } + } + } + } + + if($distortion === PHP_FLOAT_MAX){ + throw new QRCodeDetectorException('finder patterns may be too distorted'); + } + + return $bestPatterns; + } + + /** + * Orders an array of three ResultPoints in an order [A,B,C] such that AB is less than AC + * and BC is less than AC, and the angle between BC and BA is less than 180 degrees. + * + * @param \chillerlan\QRCode\Detector\FinderPattern[] $patterns array of three FinderPattern to order + * + * @return \chillerlan\QRCode\Detector\FinderPattern[] + */ + private function orderBestPatterns(array $patterns):array{ + + // Find distances between pattern centers + $zeroOneDistance = $patterns[0]->getDistance($patterns[1]); + $oneTwoDistance = $patterns[1]->getDistance($patterns[2]); + $zeroTwoDistance = $patterns[0]->getDistance($patterns[2]); + + // Assume one closest to other two is B; A and C will just be guesses at first + if($oneTwoDistance >= $zeroOneDistance && $oneTwoDistance >= $zeroTwoDistance){ + [$pointB, $pointA, $pointC] = $patterns; + } + elseif($zeroTwoDistance >= $oneTwoDistance && $zeroTwoDistance >= $zeroOneDistance){ + [$pointA, $pointB, $pointC] = $patterns; + } + else{ + [$pointA, $pointC, $pointB] = $patterns; + } + + // Use cross product to figure out whether A and C are correct or flipped. + // This asks whether BC x BA has a positive z component, which is the arrangement + // we want for A, B, C. If it's negative, then we've got it flipped around and + // should swap A and C. + if($this->crossProductZ($pointA, $pointB, $pointC) < 0.0){ + $temp = $pointA; + $pointA = $pointC; + $pointC = $temp; + } + + return [$pointA, $pointB, $pointC]; + } + + /** + * Returns the z component of the cross product between vectors BC and BA. + */ + private function crossProductZ(FinderPattern $pointA, FinderPattern $pointB, FinderPattern $pointC):float{ + $bX = $pointB->getX(); + $bY = $pointB->getY(); + + return ((($pointC->getX() - $bX) * ($pointA->getY() - $bY)) - (($pointC->getY() - $bY) * ($pointA->getX() - $bX))); + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Detector/GridSampler.php b/vendor/chillerlan/php-qrcode/src/Detector/GridSampler.php new file mode 100644 index 000000000..f70bb0eca --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/GridSampler.php @@ -0,0 +1,181 @@ +<?php +/** + * Class GridSampler + * + * @created 17.01.2021 + * @author ZXing Authors + * @author Smiley <smiley@chillerlan.net> + * @copyright 2021 Smiley + * @license Apache-2.0 + */ + +namespace chillerlan\QRCode\Detector; + +use chillerlan\QRCode\Data\QRMatrix; +use chillerlan\QRCode\Decoder\BitMatrix; +use function array_fill, count, intdiv, sprintf; + +/** + * Implementations of this class can, given locations of finder patterns for a QR code in an + * image, sample the right points in the image to reconstruct the QR code, accounting for + * perspective distortion. It is abstracted since it is relatively expensive and should be allowed + * to take advantage of platform-specific optimized implementations, like Sun's Java Advanced + * Imaging library, but which may not be available in other environments such as J2ME, and vice + * versa. + * + * The implementation used can be controlled by calling #setGridSampler(GridSampler) + * with an instance of a class which implements this interface. + * + * @author Sean Owen + */ +final class GridSampler{ + + private array $points; + + /** + * Checks a set of points that have been transformed to sample points on an image against + * the image's dimensions to see if the point are even within the image. + * + * This method will actually "nudge" the endpoints back onto the image if they are found to be + * barely (less than 1 pixel) off the image. This accounts for imperfect detection of finder + * patterns in an image where the QR Code runs all the way to the image border. + * + * For efficiency, the method will check points from either end of the line until one is found + * to be within the image. Because the set of points are assumed to be linear, this is valid. + * + * @param int $dimension matrix width/height + * + * @throws \chillerlan\QRCode\Detector\QRCodeDetectorException if an endpoint is lies outside the image boundaries + */ + private function checkAndNudgePoints(int $dimension):void{ + $nudged = true; + $max = count($this->points); + + // Check and nudge points from start until we see some that are OK: + for($offset = 0; $offset < $max && $nudged; $offset += 2){ + $x = (int)$this->points[$offset]; + $y = (int)$this->points[($offset + 1)]; + + if($x < -1 || $x > $dimension || $y < -1 || $y > $dimension){ + throw new QRCodeDetectorException(sprintf('checkAndNudgePoints 1, x: %s, y: %s, d: %s', $x, $y, $dimension)); + } + + $nudged = false; + + if($x === -1){ + $this->points[$offset] = 0.0; + $nudged = true; + } + elseif($x === $dimension){ + $this->points[$offset] = ($dimension - 1); + $nudged = true; + } + + if($y === -1){ + $this->points[($offset + 1)] = 0.0; + $nudged = true; + } + elseif($y === $dimension){ + $this->points[($offset + 1)] = ($dimension - 1); + $nudged = true; + } + + } + + // Check and nudge points from end: + $nudged = true; + + for($offset = ($max - 2); $offset >= 0 && $nudged; $offset -= 2){ + $x = (int)$this->points[$offset]; + $y = (int)$this->points[($offset + 1)]; + + if($x < -1 || $x > $dimension || $y < -1 || $y > $dimension){ + throw new QRCodeDetectorException(sprintf('checkAndNudgePoints 2, x: %s, y: %s, d: %s', $x, $y, $dimension)); + } + + $nudged = false; + + if($x === -1){ + $this->points[$offset] = 0.0; + $nudged = true; + } + elseif($x === $dimension){ + $this->points[$offset] = ($dimension - 1); + $nudged = true; + } + + if($y === -1){ + $this->points[($offset + 1)] = 0.0; + $nudged = true; + } + elseif($y === $dimension){ + $this->points[($offset + 1)] = ($dimension - 1); + $nudged = true; + } + + } + + } + + /** + * Samples an image for a rectangular matrix of bits of the given dimension. The sampling + * transformation is determined by the coordinates of 4 points, in the original and transformed + * image space. + * + * @return \chillerlan\QRCode\Decoder\BitMatrix representing a grid of points sampled from the image within a region + * defined by the "from" parameters + * @throws \chillerlan\QRCode\Detector\QRCodeDetectorException if image can't be sampled, for example, if the transformation defined + * by the given points is invalid or results in sampling outside the image boundaries + */ + public function sampleGrid(BitMatrix $matrix, int $dimension, PerspectiveTransform $transform):BitMatrix{ + + if($dimension <= 0){ + throw new QRCodeDetectorException('invalid matrix size'); + } + + $bits = new BitMatrix($dimension); + $this->points = array_fill(0, (2 * $dimension), 0.0); + + for($y = 0; $y < $dimension; $y++){ + $max = count($this->points); + $iValue = ($y + 0.5); + + for($x = 0; $x < $max; $x += 2){ + $this->points[$x] = (($x / 2) + 0.5); + $this->points[($x + 1)] = $iValue; + } + // phpcs:ignore + [$this->points, ] = $transform->transformPoints($this->points); + // Quick check to see if points transformed to something inside the image; + // sufficient to check the endpoints + $this->checkAndNudgePoints($matrix->getSize()); + + // no need to try/catch as QRMatrix::set() will silently discard out of bounds values +# try{ + for($x = 0; $x < $max; $x += 2){ + // Black(-ish) pixel + $bits->set( + intdiv($x, 2), + $y, + $matrix->check((int)$this->points[$x], (int)$this->points[($x + 1)]), + QRMatrix::M_DATA + ); + } +# } +# catch(\Throwable $aioobe){//ArrayIndexOutOfBoundsException + // This feels wrong, but, sometimes if the finder patterns are misidentified, the resulting + // transform gets "twisted" such that it maps a straight line of points to a set of points + // whose endpoints are in bounds, but others are not. There is probably some mathematical + // way to detect this about the transformation that I don't know yet. + // This results in an ugly runtime exception despite our clever checks above -- can't have + // that. We could check each point's coordinates but that feels duplicative. We settle for + // catching and wrapping ArrayIndexOutOfBoundsException. +# throw new QRCodeDetectorException('ArrayIndexOutOfBoundsException'); +# } + + } + + return $bits; + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Detector/PerspectiveTransform.php b/vendor/chillerlan/php-qrcode/src/Detector/PerspectiveTransform.php new file mode 100644 index 000000000..7964092e3 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/PerspectiveTransform.php @@ -0,0 +1,182 @@ +<?php +/** + * Class PerspectiveTransform + * + * @created 17.01.2021 + * @author ZXing Authors + * @author Smiley <smiley@chillerlan.net> + * @copyright 2021 Smiley + * @license Apache-2.0 + */ + +namespace chillerlan\QRCode\Detector; + +use function count; + +/** + * This class implements a perspective transform in two dimensions. Given four source and four + * destination points, it will compute the transformation implied between them. The code is based + * directly upon section 3.4.2 of George Wolberg's "Digital Image Warping"; see pages 54-56. + * + * @author Sean Owen + */ +final class PerspectiveTransform{ + + private float $a11; + private float $a12; + private float $a13; + private float $a21; + private float $a22; + private float $a23; + private float $a31; + private float $a32; + private float $a33; + + /** + * + */ + private function set( + float $a11, float $a21, float $a31, + float $a12, float $a22, float $a32, + float $a13, float $a23, float $a33 + ):self{ + $this->a11 = $a11; + $this->a12 = $a12; + $this->a13 = $a13; + $this->a21 = $a21; + $this->a22 = $a22; + $this->a23 = $a23; + $this->a31 = $a31; + $this->a32 = $a32; + $this->a33 = $a33; + + return $this; + } + + /** + * @SuppressWarnings(PHPMD.ExcessiveParameterList) + */ + public function quadrilateralToQuadrilateral( + float $x0, float $y0, float $x1, float $y1, float $x2, float $y2, float $x3, float $y3, + float $x0p, float $y0p, float $x1p, float $y1p, float $x2p, float $y2p, float $x3p, float $y3p + ):self{ + return (new self) + ->squareToQuadrilateral($x0p, $y0p, $x1p, $y1p, $x2p, $y2p, $x3p, $y3p) + ->times($this->quadrilateralToSquare($x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3)); + } + + /** + * + */ + private function quadrilateralToSquare( + float $x0, float $y0, float $x1, float $y1, + float $x2, float $y2, float $x3, float $y3 + ):self{ + // Here, the adjoint serves as the inverse: + return $this + ->squareToQuadrilateral($x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3) + ->buildAdjoint(); + } + + /** + * + */ + private function buildAdjoint():self{ + // Adjoint is the transpose of the cofactor matrix: + return $this->set( + ($this->a22 * $this->a33 - $this->a23 * $this->a32), + ($this->a23 * $this->a31 - $this->a21 * $this->a33), + ($this->a21 * $this->a32 - $this->a22 * $this->a31), + ($this->a13 * $this->a32 - $this->a12 * $this->a33), + ($this->a11 * $this->a33 - $this->a13 * $this->a31), + ($this->a12 * $this->a31 - $this->a11 * $this->a32), + ($this->a12 * $this->a23 - $this->a13 * $this->a22), + ($this->a13 * $this->a21 - $this->a11 * $this->a23), + ($this->a11 * $this->a22 - $this->a12 * $this->a21) + ); + } + + /** + * + */ + private function squareToQuadrilateral( + float $x0, float $y0, float $x1, float $y1, + float $x2, float $y2, float $x3, float $y3 + ):self{ + $dx3 = ($x0 - $x1 + $x2 - $x3); + $dy3 = ($y0 - $y1 + $y2 - $y3); + + if($dx3 === 0.0 && $dy3 === 0.0){ + // Affine + return $this->set(($x1 - $x0), ($x2 - $x1), $x0, ($y1 - $y0), ($y2 - $y1), $y0, 0.0, 0.0, 1.0); + } + + $dx1 = ($x1 - $x2); + $dx2 = ($x3 - $x2); + $dy1 = ($y1 - $y2); + $dy2 = ($y3 - $y2); + $denominator = ($dx1 * $dy2 - $dx2 * $dy1); + $a13 = (($dx3 * $dy2 - $dx2 * $dy3) / $denominator); + $a23 = (($dx1 * $dy3 - $dx3 * $dy1) / $denominator); + + return $this->set( + ($x1 - $x0 + $a13 * $x1), + ($x3 - $x0 + $a23 * $x3), + $x0, + ($y1 - $y0 + $a13 * $y1), + ($y3 - $y0 + $a23 * $y3), + $y0, + $a13, + $a23, + 1.0 + ); + } + + /** + * + */ + private function times(PerspectiveTransform $other):self{ + return $this->set( + ($this->a11 * $other->a11 + $this->a21 * $other->a12 + $this->a31 * $other->a13), + ($this->a11 * $other->a21 + $this->a21 * $other->a22 + $this->a31 * $other->a23), + ($this->a11 * $other->a31 + $this->a21 * $other->a32 + $this->a31 * $other->a33), + ($this->a12 * $other->a11 + $this->a22 * $other->a12 + $this->a32 * $other->a13), + ($this->a12 * $other->a21 + $this->a22 * $other->a22 + $this->a32 * $other->a23), + ($this->a12 * $other->a31 + $this->a22 * $other->a32 + $this->a32 * $other->a33), + ($this->a13 * $other->a11 + $this->a23 * $other->a12 + $this->a33 * $other->a13), + ($this->a13 * $other->a21 + $this->a23 * $other->a22 + $this->a33 * $other->a23), + ($this->a13 * $other->a31 + $this->a23 * $other->a32 + $this->a33 * $other->a33) + ); + } + + /** + * @return array[] [$xValues, $yValues] + */ + public function transformPoints(array $xValues, ?array $yValues = null):array{ + $max = count($xValues); + + if($yValues !== null){ // unused + + for($i = 0; $i < $max; $i++){ + $x = $xValues[$i]; + $y = $yValues[$i]; + $denominator = ($this->a13 * $x + $this->a23 * $y + $this->a33); + $xValues[$i] = (($this->a11 * $x + $this->a21 * $y + $this->a31) / $denominator); + $yValues[$i] = (($this->a12 * $x + $this->a22 * $y + $this->a32) / $denominator); + } + + return [$xValues, $yValues]; + } + + for($i = 0; $i < $max; $i += 2){ + $x = $xValues[$i]; + $y = $xValues[($i + 1)]; + $denominator = ($this->a13 * $x + $this->a23 * $y + $this->a33); + $xValues[$i] = (($this->a11 * $x + $this->a21 * $y + $this->a31) / $denominator); + $xValues[($i + 1)] = (($this->a12 * $x + $this->a22 * $y + $this->a32) / $denominator); + } + + return [$xValues, []]; + } + +} diff --git a/vendor/chillerlan/php-qrcode/src/Detector/QRCodeDetectorException.php b/vendor/chillerlan/php-qrcode/src/Detector/QRCodeDetectorException.php new file mode 100644 index 000000000..2444e193c --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/QRCodeDetectorException.php @@ -0,0 +1,20 @@ +<?php +/** + * Class QRCodeDetectorException + * + * @created 01.12.2021 + * @author smiley <smiley@chillerlan.net> + * @copyright 2021 smiley + * @license MIT + */ + +namespace chillerlan\QRCode\Detector; + +use chillerlan\QRCode\QRCodeException; + +/** + * An exception container + */ +final class QRCodeDetectorException extends QRCodeException{ + +} diff --git a/vendor/chillerlan/php-qrcode/src/Detector/ResultPoint.php b/vendor/chillerlan/php-qrcode/src/Detector/ResultPoint.php new file mode 100644 index 000000000..92997a746 --- /dev/null +++ b/vendor/chillerlan/php-qrcode/src/Detector/ResultPoint.php @@ -0,0 +1,73 @@ +<?php +/** + * Class ResultPoint + * + * @created 17.01.2021 + * @author ZXing Authors + * @author Smiley <smiley@chillerlan.net> + * @copyright 2021 Smiley + * @license Apache-2.0 + */ + +namespace chillerlan\QRCode\Detector; + +use function abs; + +/** + * Encapsulates a point of interest in an image containing a barcode. Typically, this + * would be the location of a finder pattern or the corner of the barcode, for example. + * + * @author Sean Owen + */ +abstract class ResultPoint{ + + protected float $x; + protected float $y; + protected float $estimatedModuleSize; + + /** + * + */ + public function __construct(float $x, float $y, float $estimatedModuleSize){ + $this->x = $x; + $this->y = $y; + $this->estimatedModuleSize = $estimatedModuleSize; + } + + /** + * + */ + public function getX():float{ + return $this->x; + } + + /** + * + */ + public function getY():float{ + return $this->y; + } + + /** + * + */ + public function getEstimatedModuleSize():float{ + return $this->estimatedModuleSize; + } + + /** + * Determines if this finder pattern "about equals" a finder pattern at the stated + * position and size -- meaning, it is at nearly the same center with nearly the same size. + */ + public function aboutEquals(float $moduleSize, float $i, float $j):bool{ + + if(abs($i - $this->y) <= $moduleSize && abs($j - $this->x) <= $moduleSize){ + $moduleSizeDiff = abs($moduleSize - $this->estimatedModuleSize); + + return $moduleSizeDiff <= 1.0 || $moduleSizeDiff <= $this->estimatedModuleSize; + } + + return false; + } + +} |