<?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;
}
/**
* 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";
}
}
}
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>';
}
/**
* 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;
}
}
(c) 2026 Seekquarry - Open Source Search Engine Software