<?php
/**
 * SeekQuarry/Yioop --
 * Open Source Pure PHP Search Engine, Crawler, and Indexer
 *
 * Copyright (C) 2009 - 2026  Chris Pollett chris@pollett.org
 *
 * LICENSE:
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 *
 * END LICENSE
 *
 * @author Chris Pollett chris@pollett.org
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2026
 * @filesource
 */
namespace seekquarry\yioop\library;

/**
 * Draws the square black-and-white symbol a phone camera reads, from a
 * piece of text, without any program outside Yioop.
 *
 * Yioop used to ask the qrencode command to make these, which meant a site
 * that wanted them had to install it and say where it was. Everything the
 * symbol needs is arithmetic, so it is done here instead, and the same
 * arithmetic is written again in scripts/qr.js so a page being written can
 * show its symbol before it is saved.
 *
 * The text is carried in the eight-bit mode, which takes any bytes, at the
 * middle of the four levels of damage the symbol can survive. Sizes one
 * through nine are made, holding up to 182 bytes, which covers an address
 * or a short note; longer text is refused rather than drawn wrongly.
 */
class QrCode
{
    /**
     * The polynomial the arithmetic of this symbol is done over. Every
     * multiplication of two values wraps by this when it overflows a byte.
     */
    const FIELD_POLYNOMIAL = 0x11D;
    /**
     * What each power of the generator comes to.
     * @var array
     */
    public static $powers = null;
    /**
     * Which power of the generator each value is.
     * @var array
     */
    public static $logs = null;
    /**
     * How many bytes of the message each size holds, at the middle level
     * of damage tolerance, from size one.
     * @var array
     */
    public static $message_bytes = [16, 28, 44, 64, 86, 108, 124, 154, 182];
    /**
     * How many bytes of correction each block of each size carries.
     * @var array
     */
    public static $correction_bytes = [10, 16, 26, 18, 24, 16, 18, 22, 22];
    /**
     * How many blocks the message of each size is split into.
     * @var array
     */
    public static $block_counts = [1, 1, 1, 2, 2, 4, 4, 4, 5];
    /**
     * Where the small square guides sit, by size, so a reader can find its
     * bearings across a larger symbol. Size one has none.
     * @var array
     */
    public static $guide_centers = [[], [6, 18], [6, 22], [6, 26], [6, 30],
        [6, 34], [6, 22, 38], [6, 24, 42], [6, 26, 46]];
    /**
     * Makes the symbol for a piece of text as a grid of true and false,
     * true being a dark square.
     *
     * @param string $text what the symbol should say
     * @return array|bool the grid, row by row, or false when the text is
     *      longer than the largest size made here can hold
     */
    public static function grid($text)
    {
        $size = self::sizeFor($text);
        if ($size < 1) {
            return false;
        }
        $message = self::messageBytes($text, $size);
        $whole = self::withCorrection($message, $size);
        $width = 17 + 4 * $size;
        $grid = [];
        $fixed = [];
        for ($row = 0; $row < $width; $row++) {
            $grid[$row] = array_fill(0, $width, false);
            $fixed[$row] = array_fill(0, $width, false);
        }
        self::placePatterns($grid, $fixed, $size, $width);
        self::placeMessage($grid, $fixed, $whole, $width);
        $mask = self::bestMask($grid, $fixed, $width);
        self::applyMask($grid, $fixed, $mask, $width);
        self::placeFormat($grid, $mask, $width);
        return $grid;
    }
    /**
     * How wide and tall a symbol is drawn where a page says nothing
     * about its size. Twelve of the sizes a browser calls a rem, which
     * is what the preview beside the editor already holds one to, so a
     * page and its preview show the same thing. The unit is the size a
     * browser draws a picture at.
     * @var int
     */
    const SYMBOL_SIDE = 192;
    /**
     * Draws the symbol as a picture made of squares, which needs no image
     * library and stays sharp at any size.
     *
     * @param string $text what the symbol should say
     * @param int $quiet how many squares of clear space to leave around it
     * @return string|bool the picture, or false when the text is too long
     */
    public static function svg($text, $quiet = 4)
    {
        $grid = self::grid($text);
        if ($grid === false) {
            return false;
        }
        $width = count($grid);
        $whole = $width + 2 * $quiet;
        $dark = "";
        for ($row = 0; $row < $width; $row++) {
            for ($column = 0; $column < $width; $column++) {
                if ($grid[$row][$column]) {
                    $dark .= "M" . ($column + $quiet) . "," .
                        ($row + $quiet) . "h1v1h-1z";
                }
            }
        }
        /* A picture with only a view box and no size of its own is
           drawn as wide as whatever holds it, which on a wiki page
           meant a symbol filling the column. Giving it a size of its
           own leaves it a symbol somebody can hold a telephone up to,
           while the squares stay sharp if a page asks for it larger. */
        return '<svg xmlns="http://www.w3.org/2000/svg" width="' .
            self::SYMBOL_SIDE . '" height="' . self::SYMBOL_SIDE .
            '" viewBox="0 0 ' . $whole . ' ' . $whole .
            '" shape-rendering="crispEdges">' .
            '<rect width="' . $whole . '" height="' . $whole .
            '" fill="#fff"/><path d="' . $dark . '" fill="#000"/></svg>';
    }
    /**
     * The smallest size that holds a piece of text.
     *
     * @param string $text the text to be carried
     * @return int the size, or zero when none of them holds it
     */
    public static function sizeFor($text)
    {
        $length = strlen($text);
        foreach (self::$message_bytes as $index => $bytes) {
            if ($length + 2 <= $bytes) {
                return $index + 1;
            }
        }
        return 0;
    }
    /**
     * Turns the text into the bytes of the message: a mark saying how it
     * is written, how long it is, the text itself, and padding out to the
     * length this size expects.
     *
     * @param string $text the text to carry
     * @param int $size which size of symbol
     * @return array the message as byte values
     */
    public static function messageBytes($text, $size)
    {
        $bits = "0100" . str_pad(decbin(strlen($text)), 8, "0",
            STR_PAD_LEFT);
        for ($index = 0; $index < strlen($text); $index++) {
            $bits .= str_pad(decbin(ord($text[$index])), 8, "0",
                STR_PAD_LEFT);
        }
        $wanted = self::$message_bytes[$size - 1] * 8;
        $bits .= str_repeat("0", min(4, $wanted - strlen($bits)));
        if (strlen($bits) % 8 != 0) {
            $bits .= str_repeat("0", 8 - strlen($bits) % 8);
        }
        $bytes = [];
        for ($index = 0; $index < strlen($bits); $index += 8) {
            $bytes[] = bindec(substr($bits, $index, 8));
        }
        $fillers = [0xEC, 0x11];
        $which = 0;
        while (count($bytes) < self::$message_bytes[$size - 1]) {
            $bytes[] = $fillers[$which % 2];
            $which++;
        }
        return $bytes;
    }
    /**
     * Splits the message into its blocks, works out the correction bytes
     * for each, and puts them back together in the order the symbol wants:
     * the first byte of every block, then the second of every block, and
     * so on, so damage in one place is spread across all of them.
     *
     * @param array $message the message bytes
     * @param int $size which size of symbol
     * @return array every byte the symbol carries, in order
     */
    public static function withCorrection($message, $size)
    {
        $blocks = self::$block_counts[$size - 1];
        $per_block = intdiv(count($message), $blocks);
        $longer = count($message) % $blocks;
        $pieces = [];
        $corrections = [];
        $at = 0;
        for ($which = 0; $which < $blocks; $which++) {
            $take = $per_block + (($which >= $blocks - $longer) ? 1 : 0);
            $piece = array_slice($message, $at, $take);
            $at += $take;
            $pieces[] = $piece;
            $corrections[] = self::correctionFor($piece,
                self::$correction_bytes[$size - 1]);
        }
        $whole = [];
        $longest = 0;
        foreach ($pieces as $piece) {
            $longest = max($longest, count($piece));
        }
        for ($index = 0; $index < $longest; $index++) {
            foreach ($pieces as $piece) {
                if (isset($piece[$index])) {
                    $whole[] = $piece[$index];
                }
            }
        }
        for ($index = 0; $index < self::$correction_bytes[$size - 1];
            $index++) {
            foreach ($corrections as $correction) {
                $whole[] = $correction[$index];
            }
        }
        return $whole;
    }
    /**
     * Works out the correction bytes for one block, by dividing it by the
     * polynomial that belongs to that many correction bytes and keeping
     * what is left over.
     *
     * @param array $block the block's message bytes
     * @param int $wanted how many correction bytes to make
     * @return array the correction bytes
     */
    public static function correctionFor($block, $wanted)
    {
        $divisor = self::correctionPolynomial($wanted);
        $working = array_merge($block, array_fill(0, $wanted, 0));
        for ($index = 0; $index < count($block); $index++) {
            $leading = $working[$index];
            if ($leading == 0) {
                continue;
            }
            $scale = self::logOf($leading);
            for ($step = 0; $step <= $wanted; $step++) {
                $working[$index + $step] ^= self::exponentOf(
                    ($divisor[$step] + $scale) % 255);
            }
        }
        return array_slice($working, count($block), $wanted);
    }
    /**
     * The polynomial used to make a given number of correction bytes, with
     * each term given as a power rather than a value, which is how the
     * division above wants it.
     *
     * @param int $wanted how many correction bytes it is for
     * @return array the polynomial's terms as powers
     */
    public static function correctionPolynomial($wanted)
    {
        $terms = [0];
        for ($step = 0; $step < $wanted; $step++) {
            $next = array_fill(0, count($terms) + 1, 0);
            foreach ($terms as $index => $term) {
                $next[$index] ^= self::exponentOf(($term + $step) % 255);
                $next[$index + 1] ^= self::exponentOf($term);
            }
            $terms = [];
            foreach ($next as $value) {
                $terms[] = self::logOf($value);
            }
        }
        /* Built from the smallest term upward; the division wants the
           largest first. */
        return array_reverse($terms);
    }
    /**
     * The value a power of the field's generator comes to.
     *
     * @param int $power which power
     * @return int the value
     */
    public static function exponentOf($power)
    {
        self::buildTables();
        return self::$powers[$power % 255];
    }
    /**
     * Which power of the generator a value is.
     *
     * @param int $value the value to look up
     * @return int the power
     */
    public static function logOf($value)
    {
        self::buildTables();
        return self::$logs[$value] ?? 0;
    }
    /**
     * Works out both tables once. Every value in this arithmetic is some
     * power of the same number, so walking the powers once gives both the
     * value of each power and the power of each value; looking either up
     * by searching would be done tens of thousands of times to draw one
     * symbol.
     */
    public static function buildTables()
    {
        if (self::$powers !== null) {
            return;
        }
        self::$powers = [];
        self::$logs = [];
        $value = 1;
        for ($power = 0; $power < 255; $power++) {
            self::$powers[$power] = $value;
            self::$logs[$value] = $power;
            $value <<= 1;
            if ($value > 255) {
                $value ^= self::FIELD_POLYNOMIAL;
            }
        }
    }
    /**
     * Puts in everything that is the same whatever the text says: the
     * three big squares at the corners, the guides, the two dotted lines,
     * the one square that is always dark, and the space kept for the
     * information about how the symbol is written.
     *
     * @param array &$grid the grid being drawn
     * @param array &$fixed which squares may not be changed afterwards
     * @param int $size which size of symbol
     * @param int $width how many squares across it is
     */
    public static function placePatterns(&$grid, &$fixed, $size, $width)
    {
        $corners = [[0, 0], [0, $width - 7], [$width - 7, 0]];
        foreach ($corners as $corner) {
            for ($row = -1; $row < 8; $row++) {
                for ($column = -1; $column < 8; $column++) {
                    $at_row = $corner[0] + $row;
                    $at_column = $corner[1] + $column;
                    if ($at_row < 0 || $at_row >= $width ||
                        $at_column < 0 || $at_column >= $width) {
                        continue;
                    }
                    $edge = max(abs($row - 3), abs($column - 3));
                    /* Dark around the outside and again in the middle,
                       with a clear ring between: the shape a reader looks
                       for to find the symbol's corners. */
                    $grid[$at_row][$at_column] = ($row >= 0 && $row < 7 &&
                        $column >= 0 && $column < 7 &&
                        ($edge == 3 || $edge <= 1));
                    $fixed[$at_row][$at_column] = true;
                }
            }
        }
        foreach (self::$guide_centers[$size - 1] as $down) {
            foreach (self::$guide_centers[$size - 1] as $across) {
                if (($down < 8 && $across < 8) ||
                    ($down < 8 && $across > $width - 9) ||
                    ($down > $width - 9 && $across < 8)) {
                    continue;
                }
                for ($row = -2; $row <= 2; $row++) {
                    for ($column = -2; $column <= 2; $column++) {
                        $edge = max(abs($row), abs($column));
                        $grid[$down + $row][$across + $column] =
                            ($edge != 1);
                        $fixed[$down + $row][$across + $column] = true;
                    }
                }
            }
        }
        for ($along = 8; $along < $width - 8; $along++) {
            $grid[6][$along] = ($along % 2 == 0);
            $fixed[6][$along] = true;
            $grid[$along][6] = ($along % 2 == 0);
            $fixed[$along][6] = true;
        }
        $grid[$width - 8][8] = true;
        $fixed[$width - 8][8] = true;
        for ($along = 0; $along < 9; $along++) {
            if (!$fixed[8][$along]) {
                $fixed[8][$along] = true;
            }
            if (!$fixed[$along][8]) {
                $fixed[$along][8] = true;
            }
        }
        for ($along = $width - 8; $along < $width; $along++) {
            $fixed[8][$along] = true;
            $fixed[$along][8] = true;
        }
    }
    /**
     * Lays the bytes into the grid, two squares wide at a time, going up
     * the right-hand side then down the next pair, skipping everything
     * already spoken for.
     *
     * @param array &$grid the grid being drawn
     * @param array $fixed which squares may not be written into
     * @param array $whole every byte the symbol carries
     * @param int $width how many squares across it is
     */
    public static function placeMessage(&$grid, $fixed, $whole, $width)
    {
        $bits = "";
        foreach ($whole as $byte) {
            $bits .= str_pad(decbin($byte), 8, "0", STR_PAD_LEFT);
        }
        $at = 0;
        $upward = true;
        for ($right = $width - 1; $right > 0; $right -= 2) {
            if ($right == 6) {
                $right--;
            }
            for ($step = 0; $step < $width; $step++) {
                $row = $upward ? $width - 1 - $step : $step;
                for ($side = 0; $side < 2; $side++) {
                    $column = $right - $side;
                    if ($fixed[$row][$column]) {
                        continue;
                    }
                    $grid[$row][$column] = ($at < strlen($bits)) ?
                        ($bits[$at] === "1") : false;
                    $at++;
                }
            }
            $upward = !$upward;
        }
    }
    /**
     * Whether a square is turned over by a given pattern.
     *
     * @param int $pattern which of the eight patterns
     * @param int $row the square's row
     * @param int $column the square's column
     * @return bool whether it is turned over
     */
    public static function maskAt($pattern, $row, $column)
    {
        switch ($pattern) {
            case 0:
                return ($row + $column) % 2 == 0;
            case 1:
                return $row % 2 == 0;
            case 2:
                return $column % 3 == 0;
            case 3:
                return ($row + $column) % 3 == 0;
            case 4:
                return (intdiv($row, 2) + intdiv($column, 3)) % 2 == 0;
            case 5:
                return ($row * $column) % 2 + ($row * $column) % 3 == 0;
            case 6:
                return (($row * $column) % 2 + ($row * $column) % 3) % 2 == 0;
            default:
                return (($row + $column) % 2 + ($row * $column) % 3) % 2 == 0;
        }
    }
    /**
     * Turns the squares over according to one of the eight patterns, so a
     * symbol does not end up with large blank areas a reader would
     * struggle with. The squares that were put in beforehand are left
     * alone.
     *
     * @param array &$grid the grid being drawn
     * @param array $fixed which squares may not be turned over
     * @param int $pattern which of the eight patterns
     * @param int $width how many squares across it is
     */
    public static function applyMask(&$grid, $fixed, $pattern, $width)
    {
        for ($row = 0; $row < $width; $row++) {
            for ($column = 0; $column < $width; $column++) {
                if ($fixed[$row][$column]) {
                    continue;
                }
                if (self::maskAt($pattern, $row, $column)) {
                    $grid[$row][$column] = !$grid[$row][$column];
                }
            }
        }
    }
    /**
     * Tries each of the eight patterns and keeps the one that leaves the
     * symbol easiest to read, judged by the rules the standard gives:
     * long runs of one color, blocks of one color, anything resembling a
     * corner square, and too much or too little dark overall.
     *
     * @param array $grid the grid as laid out, before any turning over
     * @param array $fixed which squares may not be turned over
     * @param int $width how many squares across it is
     * @return int which pattern to use
     */
    public static function bestMask($grid, $fixed, $width)
    {
        $best = 0;
        $best_score = -1;
        for ($pattern = 0; $pattern < 8; $pattern++) {
            $trial = $grid;
            self::applyMask($trial, $fixed, $pattern, $width);
            $score = self::penalty($trial, $width);
            if ($best_score < 0 || $score < $best_score) {
                $best_score = $score;
                $best = $pattern;
            }
        }
        return $best;
    }
    /**
     * How hard a grid would be to read, lower being better.
     *
     * @param array $grid the grid to judge
     * @param int $width how many squares across it is
     * @return int the score
     */
    public static function penalty($grid, $width)
    {
        $score = 0;
        for ($row = 0; $row < $width; $row++) {
            for ($column = 0; $column < $width; $column++) {
                foreach ([[0, 1], [1, 0]] as $way) {
                    $run = 1;
                    while (true) {
                        $next_row = $row + $way[0] * $run;
                        $next_column = $column + $way[1] * $run;
                        if ($next_row >= $width || $next_column >= $width ||
                            $grid[$next_row][$next_column] !=
                            $grid[$row][$column]) {
                            break;
                        }
                        $run++;
                    }
                    $before_row = $row - $way[0];
                    $before_column = $column - $way[1];
                    $starts = ($before_row < 0 || $before_column < 0 ||
                        $grid[$before_row][$before_column] !=
                        $grid[$row][$column]);
                    if ($starts && $run >= 5) {
                        $score += 3 + ($run - 5);
                    }
                }
                if ($row + 1 < $width && $column + 1 < $width &&
                    $grid[$row][$column] == $grid[$row + 1][$column] &&
                    $grid[$row][$column] == $grid[$row][$column + 1] &&
                    $grid[$row][$column] == $grid[$row + 1][$column + 1]) {
                    $score += 3;
                }
            }
        }
        $dark = 0;
        foreach ($grid as $row_values) {
            foreach ($row_values as $value) {
                if ($value) {
                    $dark++;
                }
            }
        }
        $portion = intdiv(abs($dark * 100 - $width * $width * 50),
            $width * $width);
        $score += intdiv($portion, 5) * 10;
        return $score;
    }
    /**
     * Writes in the fifteen squares that say which level of damage
     * tolerance and which pattern were used, twice over so a reader that
     * cannot make out one copy can use the other.
     *
     * @param array &$grid the grid being drawn
     * @param int $mask which pattern was used
     * @param int $width how many squares across it is
     */
    public static function placeFormat(&$grid, $mask, $width)
    {
        $said = (0 << 3) | $mask;
        $working = $said << 10;
        for ($step = 4; $step >= 0; $step--) {
            if ($working & (1 << ($step + 10))) {
                $working ^= 0x537 << $step;
            }
        }
        $format = (($said << 10) | $working) ^ 0x5412;
        for ($step = 0; $step < 15; $step++) {
            $on = (($format >> $step) & 1) == 1;
            if ($step < 6) {
                $grid[8][$step] = $on;
            } else if ($step < 8) {
                $grid[8][$step + 1] = $on;
            } else if ($step == 8) {
                $grid[7][8] = $on;
            } else {
                $grid[14 - $step][8] = $on;
            }
            if ($step < 8) {
                $grid[$width - 1 - $step][8] = $on;
            } else {
                $grid[8][$width - 15 + $step] = $on;
            }
        }
        $grid[$width - 8][8] = true;
    }
}
