/*
* 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;
}
/*
* 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";
}
}
}
return '<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 ' + whole +
' ' + whole + '" shape-rendering="crispEdges">' +
'<rect width="' + whole + '" height="' + whole +
'" fill="#fff"/><path d="' + dark + '" fill="#000"/></svg>';
}
(c) 2026 Seekquarry - Open Source Search Engine Software