\BaconQrCode\EncoderMatrixUtil

<?php
/**
 * BaconQrCode
 *
 * @link      http://github.com/Bacon/BaconQrCode For the canonical source repository
 * @copyright 2013 Ben 'DASPRiD' Scholzen
 * @license   http://opensource.org/licenses/BSD-2-Clause Simplified BSD License
 */

namespace BaconQrCode\Encoder;

use BaconQrCode\Common\BitArray;
use BaconQrCode\Common\ErrorCorrectionLevel;
use BaconQrCode\Common\Version;
use BaconQrCode\Exception;

/**
 * Matrix utility.
 */
class MatrixUtil
{
    /**
     * Position detection pattern.
     *
     * @var array
     */
    protected static $positionDetectionPattern = array(
        array(1, 1, 1, 1, 1, 1, 1),
        array(1, 0, 0, 0, 0, 0, 1),
        array(1, 0, 1, 1, 1, 0, 1),
        array(1, 0, 1, 1, 1, 0, 1),
        array(1, 0, 1, 1, 1, 0, 1),
        array(1, 0, 0, 0, 0, 0, 1),
        array(1, 1, 1, 1, 1, 1, 1),
    );

    /**
     * Position adjustment pattern.
     *
     * @var array
     */
    protected static $positionAdjustmentPattern = array(
        array(1, 1, 1, 1, 1),
        array(1, 0, 0, 0, 1),
        array(1, 0, 1, 0, 1),
        array(1, 0, 0, 0, 1),
        array(1, 1, 1, 1, 1),
    );

    /**
     * Coordinates for position adjustment patterns for each version.
     *
     * @var array
     */
    protected static $positionAdjustmentPatternCoordinateTable = array(
        array(null, null, null, null, null, null, null), // Version 1
        array(   6,   18, null, null, null, null, null), // Version 2
        array(   6,   22, null, null, null, null, null), // Version 3
        array(   6,   26, null, null, null, null, null), // Version 4
        array(   6,   30, null, null, null, null, null), // Version 5
        array(   6,   34, null, null, null, null, null), // Version 6
        array(   6,   22,   38, null, null, null, null), // Version 7
        array(   6,   24,   42, null, null, null, null), // Version 8
        array(   6,   26,   46, null, null, null, null), // Version 9
        array(   6,   28,   50, null, null, null, null), // Version 10
        array(   6,   30,   54, null, null, null, null), // Version 11
        array(   6,   32,   58, null, null, null, null), // Version 12
        array(   6,   34,   62, null, null, null, null), // Version 13
        array(   6,   26,   46,   66, null, null, null), // Version 14
        array(   6,   26,   48,   70, null, null, null), // Version 15
        array(   6,   26,   50,   74, null, null, null), // Version 16
        array(   6,   30,   54,   78, null, null, null), // Version 17
        array(   6,   30,   56,   82, null, null, null), // Version 18
        array(   6,   30,   58,   86, null, null, null), // Version 19
        array(   6,   34,   62,   90, null, null, null), // Version 20
        array(   6,   28,   50,   72,   94, null, null), // Version 21
        array(   6,   26,   50,   74,   98, null, null), // Version 22
        array(   6,   30,   54,   78,  102, null, null), // Version 23
        array(   6,   28,   54,   80,  106, null, null), // Version 24
        array(   6,   32,   58,   84,  110, null, null), // Version 25
        array(   6,   30,   58,   86,  114, null, null), // Version 26
        array(   6,   34,   62,   90,  118, null, null), // Version 27
        array(   6,   26,   50,   74,   98,  122, null), // Version 28
        array(   6,   30,   54,   78,  102,  126, null), // Version 29
        array(   6,   26,   52,   78,  104,  130, null), // Version 30
        array(   6,   30,   56,   82,  108,  134, null), // Version 31
        array(   6,   34,   60,   86,  112,  138, null), // Version 32
        array(   6,   30,   58,   86,  114,  142, null), // Version 33
        array(   6,   34,   62,   90,  118,  146, null), // Version 34
        array(   6,   30,   54,   78,  102,  126,  150), // Version 35
        array(   6,   24,   50,   76,  102,  128,  154), // Version 36
        array(   6,   28,   54,   80,  106,  132,  158), // Version 37
        array(   6,   32,   58,   84,  110,  136,  162), // Version 38
        array(   6,   26,   54,   82,  110,  138,  166), // Version 39
        array(   6,   30,   58,   86,  114,  142,  170), // Version 40
    );

    /**
     * Type information coordinates.
     *
     * @var array
     */
    protected static $typeInfoCoordinates = array(
        array(8, 0),
        array(8, 1),
        array(8, 2),
        array(8, 3),
        array(8, 4),
        array(8, 5),
        array(8, 7),
        array(8, 8),
        array(7, 8),
        array(5, 8),
        array(4, 8),
        array(3, 8),
        array(2, 8),
        array(1, 8),
        array(0, 8),
    );

    /**
     * Version information polynomial.
     *
     * @var integer
     */
    protected static $versionInfoPoly = 0x1f25;

    /**
     * Type information polynomial.
     *
     * @var integer
     */
    protected static $typeInfoPoly = 0x537;

    /**
     * Type information mask pattern.
     *
     * @var integer
     */
    protected static $typeInfoMaskPattern = 0x5412;

    /**
     * Clears a given matrix.
     *
     * @param  ByteMatrix $matrix
     * @return void
     */
    public static function clearMatrix(ByteMatrix $matrix)
    {
        $matrix->clear(-1);
    }

    /**
     * Builds a complete matrix.
     *
     * @param  BitArray             $dataBits
     * @param  ErrorCorrectionLevel $level
     * @param  Version              $version
     * @param  integer              $maskPattern
     * @param  ByteMatrix           $matrix
     * @return void
     */
    public static function buildMatrix(
        BitArray $dataBits,
        ErrorCorrectionLevel $level,
        Version $version,
        $maskPattern,
        ByteMatrix $matrix
    ) {
        self::clearMatrix($matrix);
        self::embedBasicPatterns($version, $matrix);
        self::embedTypeInfo($level, $maskPattern, $matrix);
        self::maybeEmbedVersionInfo($version, $matrix);
        self::embedDataBits($dataBits, $maskPattern, $matrix);
    }

    /**
     * Embeds type information into a matrix.
     *
     * @param  ErrorCorrectionLevel $level
     * @param  integer              $maskPattern
     * @param  ByteMatrix           $matrix
     * @return void
     */
    protected static function embedTypeInfo(ErrorCorrectionLevel $level, $maskPattern, ByteMatrix $matrix)
    {
        $typeInfoBits = new BitArray();
        self::makeTypeInfoBits($level, $maskPattern, $typeInfoBits);

        $typeInfoBitsSize = $typeInfoBits->getSize();

        for ($i = 0; $i < $typeInfoBitsSize; $i++) {
            $bit = $typeInfoBits->get($typeInfoBitsSize - 1 - $i);

            $x1 = self::$typeInfoCoordinates[$i][0];
            $y1 = self::$typeInfoCoordinates[$i][1];

            $matrix->set($x1, $y1, $bit);

            if ($i < 8) {
                $x2 = $matrix->getWidth() - $i - 1;
                $y2 = 8;
            } else {
                $x2 = 8;
                $y2 = $matrix->getHeight() - 7 + ($i - 8);
            }

            $matrix->set($x2, $y2, $bit);
        }
    }

    /**
     * Generates type information bits and appends them to a bit array.
     *
     * @param  ErrorCorrectionLevel $level
     * @param  integer $maskPattern
     * @param  BitArray $bits
     * @return void
     * @throws Exception\RuntimeException
     */
    protected static function makeTypeInfoBits(ErrorCorrectionLevel $level, $maskPattern, BitArray $bits)
    {
        $typeInfo = ($level->get() << 3) | $maskPattern;
        $bits->appendBits($typeInfo, 5);

        $bchCode = self::calculateBchCode($typeInfo, self::$typeInfoPoly);
        $bits->appendBits($bchCode, 10);

        $maskBits = new BitArray();
        $maskBits->appendBits(self::$typeInfoMaskPattern, 15);
        $bits->xorBits($maskBits);

        if ($bits->getSize() !== 15) {
            throw new Exception\RuntimeException('Bit array resulted in invalid size: ' . $bits->getSize());
        }
    }

    /**
     * Embeds version information if required.
     *
     * @param  Version    $version
     * @param  ByteMatrix $matrix
     * @return void
     */
    protected static function maybeEmbedVersionInfo(Version $version, ByteMatrix $matrix)
    {
        if ($version->getVersionNumber() < 7) {
            return;
        }

        $versionInfoBits = new BitArray();
        self::makeVersionInfoBits($version, $versionInfoBits);

        $bitIndex = 6 * 3 - 1;

        for ($i = 0; $i < 6; $i++) {
            for ($j = 0; $j < 3; $j++) {
                $bit = $versionInfoBits->get($bitIndex);
                $bitIndex--;

                $matrix->set($i, $matrix->getHeight() - 11 + $j, $bit);
                $matrix->set($matrix->getHeight() - 11 + $j, $i, $bit);
            }
        }
    }

    /**
     * Generates version information bits and appends them to a bit array.
     *
     * @param  Version  $version
     * @param  BitArray $bits
     * @return void
     * @throws Exception\RuntimeException
     */
    protected static function makeVersionInfoBits(Version $version, BitArray $bits)
    {
        $bits->appendBits($version->getVersionNumber(), 6);

        $bchCode = self::calculateBchCode($version->getVersionNumber(), self::$versionInfoPoly);
        $bits->appendBits($bchCode, 12);

        if ($bits->getSize() !== 18) {
            throw new Exception\RuntimeException('Bit array resulted in invalid size: ' . $bits->getSize());
        }
    }

    /**
     * Calculates the BHC code for a value and a polynomial.
     *
     * @param  integer $value
     * @param  integer $poly
     * @return integer
     */
    protected static function calculateBchCode($value, $poly)
    {
        $msbSetInPoly   = self::findMsbSet($poly);
        $value        <<= $msbSetInPoly - 1;

        while (self::findMsbSet($value) >= $msbSetInPoly) {
            $value ^= $poly << (self::findMsbSet($value) - $msbSetInPoly);
        }

        return $value;
    }

    /**
     * Finds and MSB set.
     *
     * @param  integer $value
     * @return integer
     */
    protected static function findMsbSet($value)
    {
        $numDigits = 0;

        while ($value !== 0) {
            $value >>= 1;
            $numDigits++;
        }

        return $numDigits;
    }

    /**
     * Embeds basic patterns into a matrix.
     *
     * @param  Version    $version
     * @param  ByteMatrix $matrix
     * @return void
     */
    protected static function embedBasicPatterns(Version $version, ByteMatrix $matrix)
    {
        self::embedPositionDetectionPatternsAndSeparators($matrix);
        self::embedDarkDotAtLeftBottomCorner($matrix);
        self::maybeEmbedPositionAdjustmentPatterns($version, $matrix);
        self::embedTimingPatterns($matrix);
    }

    /**
     * Embeds position detection patterns and separators into a byte matrix.
     *
     * @param  ByteMatrix $matrix
     * @return void
     */
    protected static function embedPositionDetectionPatternsAndSeparators(ByteMatrix $matrix)
    {
        $pdpWidth = count(self::$positionDetectionPattern[0]);

        self::embedPositionDetectionPattern(0, 0, $matrix);
        self::embedPositionDetectionPattern($matrix->getWidth() - $pdpWidth, 0, $matrix);
        self::embedPositionDetectionPattern(0, $matrix->getWidth() - $pdpWidth, $matrix);

        $hspWidth = 8;

        self::embedHorizontalSeparationPattern(0, $hspWidth - 1, $matrix);
        self::embedHorizontalSeparationPattern($matrix->getWidth() - $hspWidth, $hspWidth - 1, $matrix);
        self::embedHorizontalSeparationPattern(0, $matrix->getWidth() - $hspWidth, $matrix);

        $vspSize = 7;

        self::embedVerticalSeparationPattern($vspSize, 0, $matrix);
        self::embedVerticalSeparationPattern($matrix->getHeight() - $vspSize - 1, 0, $matrix);
        self::embedVerticalSeparationPattern($vspSize, $matrix->getHeight() - $vspSize, $matrix);
    }

    /**
     * Embeds a single position detection pattern into a byte matrix.
     *
     * @param  integer    $xStart
     * @param  integer    $yStart
     * @param  ByteMatrix $matrix
     * @return void
     */
    protected static function embedPositionDetectionPattern($xStart, $yStart, ByteMatrix $matrix)
    {
        for ($y = 0; $y < 7; $y++) {
            for ($x = 0; $x < 7; $x++) {
                $matrix->set($xStart + $x, $yStart + $y, self::$positionDetectionPattern[$y][$x]);
            }
        }
    }

    /**
     * Embeds a single horizontal separation pattern.
     *
     * @param  integer    $xStart
     * @param  integer    $yStart
     * @param  ByteMatrix $matrix
     * @return void
     * @throws Exception\RuntimeException
     */
    protected static function embedHorizontalSeparationPattern($xStart, $yStart, ByteMatrix $matrix)
    {
        for ($x = 0; $x < 8; $x++) {
            if ($matrix->get($xStart + $x, $yStart) !== -1) {
                throw new Exception\RuntimeException('Byte already set');
            }

            $matrix->set($xStart + $x, $yStart, 0);
        }
    }

    /**
     * Embeds a single vertical separation pattern.
     *
     * @param  integer    $xStart
     * @param  integer    $yStart
     * @param  ByteMatrix $matrix
     * @return void
     * @throws Exception\RuntimeException
     */
    protected static function embedVerticalSeparationPattern($xStart, $yStart, ByteMatrix $matrix)
    {
        for ($y = 0; $y < 7; $y++) {
            if ($matrix->get($xStart, $yStart + $y) !== -1) {
                throw new Exception\RuntimeException('Byte already set');
            }

            $matrix->set($xStart, $yStart + $y, 0);
        }
    }

    /**
     * Embeds a dot at the left bottom corner.
     *
     * @param  ByteMatrix $matrix
     * @return void
     * @throws Exception\RuntimeException
     */
    protected static function embedDarkDotAtLeftBottomCorner(ByteMatrix $matrix)
    {
        if ($matrix->get(8, $matrix->getHeight() - 8) === 0) {
            throw new Exception\RuntimeException('Byte already set to 0');
        }

        $matrix->set(8, $matrix->getHeight() - 8, 1);
    }

    /**
     * Embeds position adjustment patterns if required.
     *
     * @param  Version    $version
     * @param  ByteMatrix $matrix
     * @return void
     */
    protected static function maybeEmbedPositionAdjustmentPatterns(Version $version, ByteMatrix $matrix)
    {
        if ($version->getVersionNumber() < 2) {
            return;
        }

        $index = $version->getVersionNumber() - 1;

        $coordinates    = self::$positionAdjustmentPatternCoordinateTable[$index];
        $numCoordinates = count($coordinates);

        for ($i = 0; $i < $numCoordinates; $i++) {
            for ($j = 0; $j < $numCoordinates; $j++) {
                $y = $coordinates[$i];
                $x = $coordinates[$j];

                if ($x === null || $y === null) {
                    continue;
                }

                if ($matrix->get($x, $y) === -1) {
                    self::embedPositionAdjustmentPattern($x - 2, $y - 2, $matrix);
                }
            }
        }
    }

    /**
     * Embeds a single position adjustment pattern.
     *
     * @param  integer    $xStart
     * @param  intger     $yStart
     * @param  ByteMatrix $matrix
     * @return void
     */
    protected static function embedPositionAdjustmentPattern($xStart, $yStart, ByteMatrix $matrix)
    {
        for ($y = 0; $y < 5; $y++) {
            for ($x = 0; $x < 5; $x++) {
                $matrix->set($xStart + $x, $yStart + $y, self::$positionAdjustmentPattern[$y][$x]);
            }
        }
    }

    /**
     * Embeds timing patterns into a matrix.
     *
     * @param  ByteMatrix $matrix
     * @return void
     */
    protected static function embedTimingPatterns(ByteMatrix $matrix)
    {
        $matrixWidth = $matrix->getWidth();

        for ($i = 8; $i < $matrixWidth - 8; $i++) {
            $bit = ($i + 1) % 2;

            if ($matrix->get($i, 6) === -1) {
                $matrix->set($i, 6, $bit);
            }

            if ($matrix->get(6, $i) === -1) {
                $matrix->set(6, $i, $bit);
            }
        }
    }

    /**
     * Embeds "dataBits" using "getMaskPattern".
     *
     *  For debugging purposes, it skips masking process if "getMaskPattern" is
     * -1. See 8.7 of JISX0510:2004 (p.38) for how to embed data bits.
     *
     * @param  BitArray   $dataBits
     * @param  integer    $maskPattern
     * @param  ByteMatrix $matrix
     * @return void
     * @throws Exception\WriterException
     */
    protected static function embedDataBits(BitArray $dataBits, $maskPattern, ByteMatrix $matrix)
    {
        $bitIndex  = 0;
        $direction = -1;

        // Start from the right bottom cell.
        $x = $matrix->getWidth() - 1;
        $y = $matrix->getHeight() - 1;

        while ($x > 0) {
            // Skip vertical timing pattern.
            if ($x === 6) {
                $x--;
            }

            while ($y >= 0 && $y < $matrix->getHeight()) {
                for ($i = 0; $i < 2; $i++) {
                    $xx = $x - $i;

                    // Skip the cell if it's not empty.
                    if ($matrix->get($xx, $y) !== -1) {
                        continue;
                    }

                    if ($bitIndex < $dataBits->getSize()) {
                        $bit = $dataBits->get($bitIndex);
                        $bitIndex++;
                    } else {
                        // Padding bit. If there is no bit left, we'll fill the
                        // left cells with 0, as described in 8.4.9 of
                        // JISX0510:2004 (p. 24).
                        $bit = false;
                    }

                    // Skip masking if maskPattern is -1.
                    if ($maskPattern !== -1 && MaskUtil::getDataMaskBit($maskPattern, $xx, $y)) {
                        $bit = !$bit;
                    }

                    $matrix->set($xx, $y, $bit);
                }

                $y += $direction;
            }

            $direction  = -$direction;
            $y         += $direction;
            $x         -= 2;
        }

        // All bits should be consumed
        if ($bitIndex !== $dataBits->getSize()) {
            throw new Exception\WriterException('Not all bits consumed (' . $bitIndex . ' out of ' . $dataBits->getSize() .')');
        }
    }
}