/*
 * 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
 */
/*
 * Draws the square black-and-white symbol a phone camera reads, from a
 * piece of text, in the browser. This says the same thing as QrCode.php
 * says on the server, so a page being written shows the same symbol it
 * will show once it is saved; a test holds the two to that.
 *
 * The text is carried in the eight-bit mode at the middle of the four
 * levels of damage the symbol can survive. Sizes one through nine are
 * made, holding up to 182 bytes.
 */
/*
 * The polynomial the arithmetic of this symbol is done over.
 */
var QR_FIELD_POLYNOMIAL = 0x11D;
/*
 * How many bytes of the message each size holds, from size one.
 */
var QR_MESSAGE_BYTES = [16, 28, 44, 64, 86, 108, 124, 154, 182];
/*
 * How many bytes of correction each block of each size carries.
 */
var QR_CORRECTION_BYTES = [10, 16, 26, 18, 24, 16, 18, 22, 22];
/*
 * How many blocks the message of each size is split into.
 */
var QR_BLOCK_COUNTS = [1, 1, 1, 2, 2, 4, 4, 4, 5];
/*
 * Where the small square guides sit, by size. Size one has none.
 */
var QR_GUIDE_CENTERS = [[], [6, 18], [6, 22], [6, 26], [6, 30], [6, 34],
    [6, 22, 38], [6, 24, 42], [6, 26, 46]];
/*
 * What each power of the generator comes to, worked out once.
 */
var qr_powers = null;
/*
 * Which power of the generator each value is, worked out once.
 */
var qr_logs = null;
/*
 * 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.
 */
function qrBuildTables()
{
    if (qr_powers !== null) {
        return;
    }
    qr_powers = [];
    qr_logs = [];
    let value = 1;
    for (let power = 0; power < 255; power++) {
        qr_powers[power] = value;
        qr_logs[value] = power;
        value <<= 1;
        if (value > 255) {
            value ^= QR_FIELD_POLYNOMIAL;
        }
    }
}
/*
 * The value a power of the generator comes to.
 *
 * @param int power which power
 * @return int the value
 */
function qrExponentOf(power)
{
    qrBuildTables();
    return qr_powers[power % 255];
}
/*
 * Which power of the generator a value is.
 *
 * @param int value the value to look up
 * @return int the power
 */
function qrLogOf(value)
{
    qrBuildTables();
    return (qr_logs[value] === undefined) ? 0 : qr_logs[value];
}
/*
 * 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
 */
function qrSizeFor(text)
{
    for (let index = 0; index < QR_MESSAGE_BYTES.length; index++) {
        if (text.length + 2 <= QR_MESSAGE_BYTES[index]) {
            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
 */
function qrMessageBytes(text, size)
{
    let bits = "0100" + text.length.toString(2).padStart(8, "0");
    for (let index = 0; index < text.length; index++) {
        bits += text.charCodeAt(index).toString(2).padStart(8, "0");
    }
    let wanted = QR_MESSAGE_BYTES[size - 1] * 8;
    bits += "0".repeat(Math.min(4, wanted - bits.length));
    if (bits.length % 8 != 0) {
        bits += "0".repeat(8 - bits.length % 8);
    }
    let bytes = [];
    for (let index = 0; index < bits.length; index += 8) {
        bytes.push(parseInt(bits.substr(index, 8), 2));
    }
    let fillers = [0xEC, 0x11];
    let which = 0;
    while (bytes.length < QR_MESSAGE_BYTES[size - 1]) {
        bytes.push(fillers[which % 2]);
        which++;
    }
    return bytes;
}
/*
 * The polynomial used to make a given number of correction bytes, with
 * each term given as a power, largest first.
 *
 * @param int wanted how many correction bytes it is for
 * @return Array the polynomial's terms as powers
 */
function qrCorrectionPolynomial(wanted)
{
    let terms = [0];
    for (let step = 0; step < wanted; step++) {
        let next = [];
        for (let index = 0; index <= terms.length; index++) {
            next[index] = 0;
        }
        for (let index = 0; index < terms.length; index++) {
            next[index] ^= qrExponentOf((terms[index] + step) % 255);
            next[index + 1] ^= qrExponentOf(terms[index]);
        }
        terms = [];
        for (let index = 0; index < next.length; index++) {
            terms.push(qrLogOf(next[index]));
        }
    }
    return terms.reverse();
}
/*
 * 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
 */
function qrCorrectionFor(block, wanted)
{
    let divisor = qrCorrectionPolynomial(wanted);
    let working = block.slice();
    for (let index = 0; index < wanted; index++) {
        working.push(0);
    }
    for (let index = 0; index < block.length; index++) {
        let leading = working[index];
        if (leading == 0) {
            continue;
        }
        let scale = qrLogOf(leading);
        for (let step = 0; step <= wanted; step++) {
            working[index + step] ^= qrExponentOf(
                (divisor[step] + scale) % 255);
        }
    }
    return working.slice(block.length, block.length + wanted);
}
/*
 * Splits the message into its blocks, works out the correction bytes for
 * each, and puts them back together in the order the symbol wants, 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
 */
function qrWithCorrection(message, size)
{
    let blocks = QR_BLOCK_COUNTS[size - 1];
    let per_block = Math.floor(message.length / blocks);
    let longer = message.length % blocks;
    let pieces = [];
    let corrections = [];
    let at = 0;
    for (let which = 0; which < blocks; which++) {
        let take = per_block + ((which >= blocks - longer) ? 1 : 0);
        let piece = message.slice(at, at + take);
        at += take;
        pieces.push(piece);
        corrections.push(qrCorrectionFor(piece,
            QR_CORRECTION_BYTES[size - 1]));
    }
    let whole = [];
    let longest = 0;
    for (let index = 0; index < pieces.length; index++) {
        longest = Math.max(longest, pieces[index].length);
    }
    for (let index = 0; index < longest; index++) {
        for (let which = 0; which < pieces.length; which++) {
            if (pieces[which][index] !== undefined) {
                whole.push(pieces[which][index]);
            }
        }
    }
    for (let index = 0; index < QR_CORRECTION_BYTES[size - 1]; index++) {
        for (let which = 0; which < corrections.length; which++) {
            whole.push(corrections[which][index]);
        }
    }
    return whole;
}
/*
 * 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
 */
function qrPlacePatterns(grid, fixed, size, width)
{
    let corners = [[0, 0], [0, width - 7], [width - 7, 0]];
    for (let which = 0; which < corners.length; which++) {
        for (let row = -1; row < 8; row++) {
            for (let column = -1; column < 8; column++) {
                let at_row = corners[which][0] + row;
                let at_column = corners[which][1] + column;
                if (at_row < 0 || at_row >= width || at_column < 0 ||
                    at_column >= width) {
                    continue;
                }
                let edge = Math.max(Math.abs(row - 3), Math.abs(column - 3));
                grid[at_row][at_column] = (row >= 0 && row < 7 &&
                    column >= 0 && column < 7 && (edge == 3 || edge <= 1));
                fixed[at_row][at_column] = true;
            }
        }
    }
    let centers = QR_GUIDE_CENTERS[size - 1];
    for (let down_at = 0; down_at < centers.length; down_at++) {
        for (let across_at = 0; across_at < centers.length; across_at++) {
            let down = centers[down_at];
            let across = centers[across_at];
            if ((down < 8 && across < 8) ||
                (down < 8 && across > width - 9) ||
                (down > width - 9 && across < 8)) {
                continue;
            }
            for (let row = -2; row <= 2; row++) {
                for (let column = -2; column <= 2; column++) {
                    let edge = Math.max(Math.abs(row), Math.abs(column));
                    grid[down + row][across + column] = (edge != 1);
                    fixed[down + row][across + column] = true;
                }
            }
        }
    }
    for (let 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 (let along = 0; along < 9; along++) {
        fixed[8][along] = true;
        fixed[along][8] = true;
    }
    for (let 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
 */
function qrPlaceMessage(grid, fixed, whole, width)
{
    let bits = "";
    for (let index = 0; index < whole.length; index++) {
        bits += whole[index].toString(2).padStart(8, "0");
    }
    let at = 0;
    let upward = true;
    for (let right = width - 1; right > 0; right -= 2) {
        if (right == 6) {
            right--;
        }
        for (let step = 0; step < width; step++) {
            let row = upward ? width - 1 - step : step;
            for (let side = 0; side < 2; side++) {
                let column = right - side;
                if (fixed[row][column]) {
                    continue;
                }
                grid[row][column] = (at < bits.length) ?
                    (bits.charAt(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
 */
function qrMaskAt(pattern, row, column)
{
    if (pattern == 0) {
        return (row + column) % 2 == 0;
    }
    if (pattern == 1) {
        return row % 2 == 0;
    }
    if (pattern == 2) {
        return column % 3 == 0;
    }
    if (pattern == 3) {
        return (row + column) % 3 == 0;
    }
    if (pattern == 4) {
        return (Math.floor(row / 2) + Math.floor(column / 3)) % 2 == 0;
    }
    if (pattern == 5) {
        return (row * column) % 2 + (row * column) % 3 == 0;
    }
    if (pattern == 6) {
        return ((row * column) % 2 + (row * column) % 3) % 2 == 0;
    }
    return ((row + column) % 2 + (row * column) % 3) % 2 == 0;
}
/*
 * Turns the squares over according to one of the eight patterns, leaving
 * alone the squares that were put in beforehand.
 *
 * @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
 */
function qrApplyMask(grid, fixed, pattern, width)
{
    for (let row = 0; row < width; row++) {
        for (let column = 0; column < width; column++) {
            if (fixed[row][column]) {
                continue;
            }
            if (qrMaskAt(pattern, row, column)) {
                grid[row][column] = !grid[row][column];
            }
        }
    }
}
/*
 * 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
 */
function qrPenalty(grid, width)
{
    let score = 0;
    let ways = [[0, 1], [1, 0]];
    for (let row = 0; row < width; row++) {
        for (let column = 0; column < width; column++) {
            for (let which = 0; which < ways.length; which++) {
                let way = ways[which];
                let run = 1;
                while (true) {
                    let next_row = row + way[0] * run;
                    let next_column = column + way[1] * run;
                    if (next_row >= width || next_column >= width ||
                        grid[next_row][next_column] != grid[row][column]) {
                        break;
                    }
                    run++;
                }
                let before_row = row - way[0];
                let before_column = column - way[1];
                let 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;
            }
        }
    }
    let dark = 0;
    for (let row = 0; row < width; row++) {
        for (let column = 0; column < width; column++) {
            if (grid[row][column]) {
                dark++;
            }
        }
    }
    let portion = Math.floor(Math.abs(dark * 100 - width * width * 50) /
        (width * width));
    score += Math.floor(portion / 5) * 10;
    return score;
}
/*
 * Tries each of the eight patterns and keeps the one that leaves the
 * symbol easiest to read.
 *
 * @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
 */
function qrBestMask(grid, fixed, width)
{
    let best = 0;
    let best_score = -1;
    for (let pattern = 0; pattern < 8; pattern++) {
        let trial = [];
        for (let row = 0; row < width; row++) {
            trial[row] = grid[row].slice();
        }
        qrApplyMask(trial, fixed, pattern, width);
        let score = qrPenalty(trial, width);
        if (best_score < 0 || score < best_score) {
            best_score = score;
            best = pattern;
        }
    }
    return best;
}
/*
 * 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
 */
function qrPlaceFormat(grid, mask, width)
{
    let said = mask;
    let working = said << 10;
    for (let step = 4; step >= 0; step--) {
        if (working & (1 << (step + 10))) {
            working ^= 0x537 << step;
        }
    }
    let format = ((said << 10) | working) ^ 0x5412;
    for (let step = 0; step < 15; step++) {
        let 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;
}
/*
 * 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
 */
function qrGrid(text)
{
    let size = qrSizeFor(text);
    if (size < 1) {
        return false;
    }
    let message = qrMessageBytes(text, size);
    let whole = qrWithCorrection(message, size);
    let width = 17 + 4 * size;
    let grid = [];
    let fixed = [];
    for (let row = 0; row < width; row++) {
        grid[row] = [];
        fixed[row] = [];
        for (let column = 0; column < width; column++) {
            grid[row][column] = false;
            fixed[row][column] = false;
        }
    }
    qrPlacePatterns(grid, fixed, size, width);
    qrPlaceMessage(grid, fixed, whole, width);
    let mask = qrBestMask(grid, fixed, width);
    qrApplyMask(grid, fixed, mask, width);
    qrPlaceFormat(grid, mask, width);
    return grid;
}
/*
 * How wide and tall a symbol is drawn where a page says nothing about
 * its size, matching what the server draws. The unit is the size a
 * browser draws a picture at.
 */
var QR_SYMBOL_SIDE = 192;
/*
 * Draws the symbol as a picture made of squares, which 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
 */
function qrSvg(text, quiet)
{
    let clear = (quiet === undefined) ? 4 : quiet;
    let grid = qrGrid(text);
    if (grid === false) {
        return false;
    }
    let width = grid.length;
    let whole = width + 2 * clear;
    let dark = "";
    for (let row = 0; row < width; row++) {
        for (let column = 0; column < width; column++) {
            if (grid[row][column]) {
                dark += "M" + (column + clear) + "," + (row + clear) +
                    "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 page meant a symbol
       filling the column. The size here matches the one the server
       draws, so a page and its preview show the same thing. */
    return '<svg xmlns="http://www.w3.org/2000/svg" width="' +
        QR_SYMBOL_SIDE + '" height="' + QR_SYMBOL_SIDE +
        '" viewBox="0 0 ' + whole + ' ' + whole +
        '" shape-rendering="crispEdges">' +
        '<rect width="' + whole + '" height="' + whole +
        '" fill="#fff"/><path d="' + dark + '" fill="#000"/></svg>';
}
