FR
apps/winzik / src / Cast / Qr.php · commit 6576d6f
<?phpnamespace App\Cast;/** * A QR code of a short text (the address of the TV page, to open it with a tablet or a phone's camera): byte mode, * error correction level L, versions 1 to 6 (up to 134 bytes), the mask of lowest penalty. The method of ISO 18004 * as written by Project Nayuki's reference encoder (MIT), reduced to what WinZik needs. */final class Qr{    private const ECC_PER_BLOCK = [0, 7, 10, 15, 20, 26, 18];    private const BLOCKS = [0, 1, 1, 1, 1, 1, 2];    private const ALIGN = [0, 0, 18, 22, 26, 30, 34];    private int $size;    /** @var list<list<bool>> */    private array $modules = [];    /** @var list<list<bool>> */    private array $function = [];    /**     * @return list<list<bool>> the modules, row by row (true = dark), without the quiet zone     * @throws \InvalidArgumentException a text too long     */    public static function matrix(string $text): array    {        return (new self())->encode($text);    }    /** A PNG of the code (a white margin of 4 modules around), $scale pixels a module. */    public static function png(string $text, string $file, int $scale = 8): bool    {        if (!function_exists('imagecreatetruecolor')) {            return false;        }        $m = self::matrix($text);        $n = count($m);        $px = ($n + 8) * $scale;        $img = imagecreatetruecolor($px, $px);        if ($img === false) {            return false;        }        $white = (int)imagecolorallocate($img, 255, 255, 255);        $black = (int)imagecolorallocate($img, 0, 0, 0);        imagefilledrectangle($img, 0, 0, $px - 1, $px - 1, $white);        foreach ($m as $y => $row) {            foreach ($row as $x => $dark) {                if ($dark) {                    imagefilledrectangle($img, ($x + 4) * $scale, ($y + 4) * $scale, ($x + 5) * $scale - 1, ($y + 5) * $scale - 1, $black);                }            }        }        @mkdir(dirname($file), 0777, true);        $ok = imagepng($img, $file);        return $ok;    }    /** @return list<list<bool>> */    private function encode(string $text): array    {        $version = 0;        for ($v = 1; $v <= 6; $v++) {            if (strlen($text) * 8 + 12 <= self::dataCodewords($v) * 8) {                $version = $v;                break;            }        }        if ($version === 0) {            throw new \InvalidArgumentException('texte trop long pour le QR code');        }        // the bits: mode byte (0100), the length on 8 bits, the bytes, a terminator, padding        $bits = [];        $push = function (int $value, int $count) use (&$bits): void {            for ($i = $count - 1; $i >= 0; $i--) {                $bits[] = ($value >> $i) & 1;            }        };        $push(4, 4);        $push(strlen($text), 8);        foreach (str_split($text) as $c) {            $push(ord($c), 8);        }        $capacity = self::dataCodewords($version) * 8;        $push(0, min(4, $capacity - count($bits)));        $push(0, (8 - count($bits) % 8) % 8);        for ($pad = 0xEC; count($bits) < $capacity; $pad ^= 0xEC ^ 0x11) {            $push($pad, 8);        }        $data = [];        foreach (array_chunk($bits, 8) as $byte) {            $data[] = (int)bindec(implode('', $byte));        }        $codewords = self::addEcc($data, $version);        $this->size = $version * 4 + 17;        $this->modules = array_fill(0, $this->size, array_fill(0, $this->size, false));        $this->function = $this->modules;        $this->drawFunctions($version);        $this->drawCodewords($codewords);        $best = 0;        $bestPenalty = PHP_INT_MAX;        for ($mask = 0; $mask < 8; $mask++) {            $this->applyMask($mask);            $this->drawFormat($mask);            $penalty = $this->penalty();            if ($penalty < $bestPenalty) {                $best = $mask;                $bestPenalty = $penalty;            }            $this->applyMask($mask);    // undone (XOR)        }        $this->applyMask($best);        $this->drawFormat($best);        return $this->modules;    }    private static function rawModules(int $v): int    {        $result = (16 * $v + 128) * $v + 64;        if ($v >= 2) {            $align = intdiv($v, 7) + 2;            $result -= (25 * $align - 10) * $align - 55;        }        return $result;    }    private static function dataCodewords(int $v): int    {        return intdiv(self::rawModules($v), 8) - self::ECC_PER_BLOCK[$v] * self::BLOCKS[$v];    }    /** @param list<int> $data @return list<int> the data and the error correction, blocks interleaved */    private static function addEcc(array $data, int $v): array    {        $blocks = max(1, self::BLOCKS[$v]);        $ecc = self::ECC_PER_BLOCK[$v];        $raw = intdiv(self::rawModules($v), 8);        $short = $blocks - $raw % $blocks;        $shortLen = intdiv($raw, $blocks);        $divisor = self::divisor($ecc);        $all = [];        $k = 0;        for ($i = 0; $i < $blocks; $i++) {            $len = $shortLen - $ecc + ($i < $short ? 0 : 1);            $dat = array_slice($data, $k, $len);            $k += $len;            $rem = self::remainder($dat, $divisor);            if ($i < $short) {                $dat[] = 0;            }            $all[] = array_merge($dat, $rem);        }        $out = [];        for ($i = 0; $i < count($all[0]); $i++) {            foreach ($all as $j => $block) {                if ($i !== $shortLen - $ecc || $j >= $short) {                    $out[] = $block[$i];                }            }        }        return $out;    }    /** @return list<int> */    private static function divisor(int $degree): array    {        $result = array_fill(0, $degree, 0);        $result[$degree - 1] = 1;        $root = 1;        for ($i = 0; $i < $degree; $i++) {            for ($j = 0; $j < $degree; $j++) {                $result[$j] = self::mul($result[$j], $root);                if ($j + 1 < $degree) {                    $result[$j] ^= $result[$j + 1];                }            }            $root = self::mul($root, 2);        }        return $result;    }    /** @param list<int> $data @param list<int> $divisor @return list<int> */    private static function remainder(array $data, array $divisor): array    {        $result = array_fill(0, count($divisor), 0);        foreach ($data as $b) {            $factor = $b ^ array_shift($result);            $result[] = 0;            foreach ($divisor as $i => $d) {                $result[$i] ^= self::mul($d, $factor);            }        }        return $result;    }    private static function mul(int $x, int $y): int    {        $z = 0;        for ($i = 7; $i >= 0; $i--) {            $z = (($z << 1) ^ (($z >> 7) * 0x11D)) & 0xFF;            $z ^= (($y >> $i) & 1) * $x;        }        return $z;    }    private function set(int $x, int $y, bool $dark): void    {        $this->modules[$y][$x] = $dark;        $this->function[$y][$x] = true;    }    private function drawFunctions(int $v): void    {        $n = $this->size;        for ($i = 0; $i < $n; $i++) {            $this->set(6, $i, $i % 2 === 0);            $this->set($i, 6, $i % 2 === 0);        }        foreach ([[3, 3], [$n - 4, 3], [3, $n - 4]] as [$cx, $cy]) {            for ($dy = -4; $dy <= 4; $dy++) {                for ($dx = -4; $dx <= 4; $dx++) {                    $x = $cx + $dx;                    $y = $cy + $dy;                    if ($x >= 0 && $x < $n && $y >= 0 && $y < $n) {                        $d = max(abs($dx), abs($dy));                        $this->set($x, $y, $d !== 2 && $d !== 4);                    }                }            }        }        if ($v >= 2) {            $a = self::ALIGN[$v];            for ($dy = -2; $dy <= 2; $dy++) {                for ($dx = -2; $dx <= 2; $dx++) {                    $this->set($a + $dx, $a + $dy, max(abs($dx), abs($dy)) !== 1);                }            }        }        $this->drawFormat(0);      // reserved now, written with the mask chosen    }    private function drawFormat(int $mask): void    {        $data = 1 << 3 | $mask;     // level L = 01        $rem = $data;        for ($i = 0; $i < 10; $i++) {            $rem = ($rem << 1) ^ (($rem >> 9) * 0x537);        }        $bits = ($data << 10 | $rem) ^ 0x5412;        $bit = fn (int $i) => (($bits >> $i) & 1) === 1;        $n = $this->size;        for ($i = 0; $i <= 5; $i++) {            $this->set(8, $i, $bit($i));        }        $this->set(8, 7, $bit(6));        $this->set(8, 8, $bit(7));        $this->set(7, 8, $bit(8));        for ($i = 9; $i < 15; $i++) {            $this->set(14 - $i, 8, $bit($i));        }        for ($i = 0; $i < 8; $i++) {            $this->set($n - 1 - $i, 8, $bit($i));        }        for ($i = 8; $i < 15; $i++) {            $this->set(8, $n - 15 + $i, $bit($i));        }        $this->set(8, $n - 8, true);    }    /** @param list<int> $codewords */    private function drawCodewords(array $codewords): void    {        $n = $this->size;        $i = 0;        $total = count($codewords) * 8;        for ($right = $n - 1; $right >= 1; $right -= 2) {            if ($right === 6) {                $right = 5;            }            for ($vert = 0; $vert < $n; $vert++) {                for ($j = 0; $j < 2; $j++) {                    $x = $right - $j;                    $upward = (($right + 1) & 2) === 0;                    $y = $upward ? $n - 1 - $vert : $vert;                    if (!$this->function[$y][$x] && $i < $total) {                        $this->modules[$y][$x] = (($codewords[$i >> 3] >> (7 - ($i & 7))) & 1) === 1;                        $i++;                    }                }            }        }    }    private function applyMask(int $mask): void    {        $n = $this->size;        for ($y = 0; $y < $n; $y++) {            for ($x = 0; $x < $n; $x++) {                $invert = match ($mask) {                    0 => ($x + $y) % 2 === 0,                    1 => $y % 2 === 0,                    2 => $x % 3 === 0,                    3 => ($x + $y) % 3 === 0,                    4 => (intdiv($x, 3) + intdiv($y, 2)) % 2 === 0,                    5 => $x * $y % 2 + $x * $y % 3 === 0,                    6 => ($x * $y % 2 + $x * $y % 3) % 2 === 0,                    default => (($x + $y) % 2 + $x * $y % 3) % 2 === 0,                };                if ($invert && !$this->function[$y][$x]) {                    $this->modules[$y][$x] = !$this->modules[$y][$x];                }            }        }    }    /** Runs of 5+ alike, 2x2 blocks, the balance of dark (the finder-like rule left out: a mask is only chosen better or worse). */    private function penalty(): int    {        $n = $this->size;        $p = 0;        $dark = 0;        for ($a = 0; $a < $n; $a++) {            $runRow = $runCol = 1;            for ($b = 0; $b < $n; $b++) {                $dark += $this->modules[$a][$b] ? 1 : 0;                if ($b > 0) {                    $runRow = $this->modules[$a][$b] === $this->modules[$a][$b - 1] ? $runRow + 1 : 1;                    $runCol = $this->modules[$b][$a] === $this->modules[$b - 1][$a] ? $runCol + 1 : 1;                    $p += ($runRow === 5 ? 3 : ($runRow > 5 ? 1 : 0)) + ($runCol === 5 ? 3 : ($runCol > 5 ? 1 : 0));                }                if ($a > 0 && $b > 0) {                    $c = $this->modules[$a][$b];                    if ($c === $this->modules[$a - 1][$b] && $c === $this->modules[$a][$b - 1] && $c === $this->modules[$a - 1][$b - 1]) {                        $p += 3;                    }                }            }        }        $total = $n * $n;        $k = intdiv(abs($dark * 20 - $total * 10) + $total - 1, $total) - 1;        return $p + max(0, $k) * 10;    }}