<?php
/**
 * QR code encoder (ISO/IEC 18004), byte mode with UTF-8 text, versions 1 to 40, levels L, M, Q, H.
 *
 * Written for this plugin so the code runs on PHP 7.4 without extensions and nothing is fetched from
 * elsewhere. Checked module by module against an independent library (see the plugin's test suite).
 *
 * @package ThreeCE
 */

if ( ! defined( 'ABSPATH' ) ) {
	exit;
}

/**
 * QR code encoder.
 */
class ThreeCE_QR {

	/**
	 * Error correction codewords per block, by level and version (index 0 is version 1).
	 */
	const ECC_PER_BLOCK = array(
		'L' => array( 7, 10, 15, 20, 26, 18, 20, 24, 30, 18, 20, 24, 26, 30, 22, 24, 28, 30, 28, 28, 28, 28, 30, 30, 26, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30 ),
		'M' => array( 10, 16, 26, 18, 24, 16, 18, 22, 22, 26, 30, 22, 22, 24, 24, 28, 28, 26, 26, 26, 26, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28 ),
		'Q' => array( 13, 22, 18, 26, 18, 24, 18, 22, 20, 24, 28, 26, 24, 20, 30, 24, 28, 28, 26, 30, 28, 30, 30, 30, 30, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30 ),
		'H' => array( 17, 28, 22, 16, 22, 28, 26, 26, 24, 28, 24, 28, 22, 24, 24, 30, 28, 28, 26, 28, 30, 24, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30 ),
	);

	/**
	 * Number of error correction blocks, by level and version (index 0 is version 1).
	 */
	const BLOCKS = array(
		'L' => array( 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 7, 8, 8, 9, 9, 10, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 24, 25 ),
		'M' => array( 1, 1, 1, 2, 2, 4, 4, 4, 5, 5, 5, 8, 9, 9, 10, 10, 11, 13, 14, 16, 17, 17, 18, 20, 21, 23, 25, 26, 28, 29, 31, 33, 35, 37, 38, 40, 43, 45, 47, 49 ),
		'Q' => array( 1, 1, 2, 2, 4, 4, 6, 6, 8, 8, 8, 10, 12, 16, 12, 17, 16, 18, 21, 20, 23, 23, 25, 27, 29, 34, 34, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 62, 65, 68 ),
		'H' => array( 1, 1, 2, 4, 4, 4, 5, 6, 8, 8, 11, 11, 16, 16, 18, 16, 19, 21, 25, 25, 25, 34, 30, 32, 35, 37, 40, 42, 45, 48, 51, 54, 57, 60, 63, 66, 70, 74, 77, 81 ),
	);

	/**
	 * Two format bits per level.
	 */
	const FORMAT_BITS = array(
		'L' => 1,
		'M' => 0,
		'Q' => 3,
		'H' => 2,
	);

	/**
	 * Side length in modules.
	 *
	 * @var int
	 */
	private $size;

	/**
	 * Dark (1) or light (0) per module, by row then column.
	 *
	 * @var array<int, array<int, int>>
	 */
	private $modules = array();

	/**
	 * Modules that belong to a function pattern and never carry data.
	 *
	 * @var array<int, array<int, bool>>
	 */
	private $function = array();

	/**
	 * QR code for a text, or null if it is empty or longer than version 40 holds.
	 *
	 * @param string   $text  Text, encoded as UTF-8 bytes.
	 * @param string   $ecc   Error correction level L, M, Q or H (anything else: M).
	 * @param int|null $mask  Mask 0 to 7, or null to pick the one with the lowest penalty.
	 * @return array{version: int, ecc: string, mask: int, size: int, rows: array<int, string>}|null
	 */
	public static function matrix( $text, $ecc = 'M', $mask = null ) {
		$text = (string) $text;
		$ecc  = strtoupper( (string) $ecc );
		$ecc  = isset( self::BLOCKS[ $ecc ] ) ? $ecc : 'M';
		$mask = is_int( $mask ) && $mask >= 0 && $mask <= 7 ? $mask : null;
		if ( '' === $text ) {
			return null;
		}
		$length  = strlen( $text );
		$version = 0;
		for ( $v = 1; $v <= 40; $v++ ) {
			$needed = 4 + ( $v < 10 ? 8 : 16 ) + 8 * $length;
			if ( $needed <= self::data_codewords( $v, $ecc ) * 8 ) {
				$version = $v;
				break;
			}
		}
		if ( 0 === $version ) {
			return null;
		}
		$qr = new self( $version );
		$qr->draw_function_patterns( $version, $ecc );
		$qr->draw_codewords( self::interleave( self::data_bytes( $text, $version, $ecc ), $version, $ecc ) );
		if ( null === $mask ) {
			$best = PHP_INT_MAX;
			for ( $m = 0; $m < 8; $m++ ) {
				$qr->apply_mask( $m );
				$qr->draw_format_bits( $ecc, $m );
				$penalty = $qr->penalty();
				if ( $penalty < $best ) {
					$best = $penalty;
					$mask = $m;
				}
				$qr->apply_mask( $m ); // XOR again undoes the mask.
			}
		}
		$qr->apply_mask( (int) $mask );
		$qr->draw_format_bits( $ecc, (int) $mask );
		$rows = array();
		foreach ( $qr->modules as $row ) {
			$rows[] = implode( '', $row );
		}
		return array(
			'version' => $version,
			'ecc'     => $ecc,
			'mask'    => (int) $mask,
			'size'    => $qr->size,
			'rows'    => $rows,
		);
	}

	/**
	 * Empty symbol of a version.
	 *
	 * @param int $version Version 1 to 40.
	 */
	private function __construct( $version ) {
		$this->size     = 4 * $version + 17;
		$this->modules  = array_fill( 0, $this->size, array_fill( 0, $this->size, 0 ) );
		$this->function = array_fill( 0, $this->size, array_fill( 0, $this->size, false ) );
	}

	/**
	 * Modules that carry data or error correction, after all function patterns.
	 *
	 * @param int $version Version.
	 */
	private static function raw_data_modules( $version ): int {
		$result = ( 16 * $version + 128 ) * $version + 64;
		if ( $version >= 2 ) {
			$align   = intdiv( $version, 7 ) + 2;
			$result -= ( 25 * $align - 10 ) * $align - 55;
			if ( $version >= 7 ) {
				$result -= 36;
			}
		}
		return $result;
	}

	/**
	 * Data codewords of a version and level.
	 *
	 * @param int    $version Version.
	 * @param string $ecc     Level.
	 */
	private static function data_codewords( $version, $ecc ): int {
		return intdiv( self::raw_data_modules( $version ), 8 ) - self::ECC_PER_BLOCK[ $ecc ][ $version - 1 ] * self::BLOCKS[ $ecc ][ $version - 1 ];
	}

	/**
	 * Mode indicator, length, text bytes, terminator and padding as codewords.
	 *
	 * @param string $text    Text.
	 * @param int    $version Version.
	 * @param string $ecc     Level.
	 * @return array<int, int>
	 */
	private static function data_bytes( $text, $version, $ecc ) {
		$capacity = self::data_codewords( $version, $ecc ) * 8;
		$bits     = '0100' . str_pad( decbin( strlen( $text ) ), $version < 10 ? 8 : 16, '0', STR_PAD_LEFT );
		foreach ( unpack( 'C*', $text ) as $byte ) {
			$bits .= str_pad( decbin( $byte ), 8, '0', STR_PAD_LEFT );
		}
		$bits .= str_repeat( '0', min( 4, $capacity - strlen( $bits ) ) );
		$bits .= str_repeat( '0', ( 8 - strlen( $bits ) % 8 ) % 8 );
		$bytes = array();
		foreach ( str_split( $bits, 8 ) as $chunk ) {
			$bytes[] = bindec( $chunk );
		}
		$needed = intdiv( $capacity, 8 );
		for ( $i = count( $bytes ), $pad = 0xEC; $i < $needed; $i++, $pad ^= 0xEC ^ 0x11 ) {
			$bytes[] = $pad;
		}
		return $bytes;
	}

	/**
	 * Splits the data into blocks, adds Reed-Solomon codewords and interleaves them.
	 *
	 * @param array<int, int> $data    Data codewords.
	 * @param int             $version Version.
	 * @param string          $ecc     Level.
	 * @return array<int, int>
	 */
	private static function interleave( $data, $version, $ecc ) {
		$blocks    = self::BLOCKS[ $ecc ][ $version - 1 ];
		$ecc_len   = self::ECC_PER_BLOCK[ $ecc ][ $version - 1 ];
		$raw       = intdiv( self::raw_data_modules( $version ), 8 );
		$short     = $blocks - $raw % $blocks;
		$short_len = intdiv( $raw, $blocks );
		$divisor   = self::rs_divisor( $ecc_len );
		$parts     = array();
		$offset    = 0;
		for ( $i = 0; $i < $blocks; $i++ ) {
			$len     = $short_len - $ecc_len + ( $i < $short ? 0 : 1 );
			$block   = array_slice( $data, $offset, $len );
			$offset += $len;
			$parts[] = array( $block, self::rs_remainder( $block, $divisor ) );
		}
		$result = array();
		for ( $i = 0; $i <= $short_len - $ecc_len; $i++ ) {
			foreach ( $parts as $part ) {
				if ( isset( $part[0][ $i ] ) ) {
					$result[] = $part[0][ $i ];
				}
			}
		}
		for ( $i = 0; $i < $ecc_len; $i++ ) {
			foreach ( $parts as $part ) {
				$result[] = $part[1][ $i ];
			}
		}
		return $result;
	}

	/**
	 * Generator polynomial of the given degree, highest coefficient first and left out.
	 *
	 * @param int $degree Number of error correction codewords.
	 * @return array<int, int>
	 */
	private static function rs_divisor( $degree ) {
		$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::gf_multiply( $result[ $j ], $root );
				if ( $j + 1 < $degree ) {
					$result[ $j ] ^= $result[ $j + 1 ];
				}
			}
			$root = self::gf_multiply( $root, 0x02 );
		}
		return $result;
	}

	/**
	 * Reed-Solomon remainder of a block.
	 *
	 * @param array<int, int> $data    Block.
	 * @param array<int, int> $divisor Generator polynomial.
	 * @return array<int, int>
	 */
	private static function rs_remainder( $data, $divisor ) {
		$result = array_fill( 0, count( $divisor ), 0 );
		foreach ( $data as $byte ) {
			$factor   = $byte ^ array_shift( $result );
			$result[] = 0;
			foreach ( $divisor as $i => $coefficient ) {
				$result[ $i ] ^= self::gf_multiply( $coefficient, $factor );
			}
		}
		return $result;
	}

	/**
	 * Product in GF(2^8) with the QR polynomial x^8 + x^4 + x^3 + x^2 + 1.
	 *
	 * @param int $x Factor.
	 * @param int $y Factor.
	 */
	private static function gf_multiply( $x, $y ): int {
		$z = 0;
		for ( $i = 7; $i >= 0; $i-- ) {
			$z  = ( $z << 1 ) ^ ( ( $z >> 7 ) * 0x11D );
			$z ^= ( ( $y >> $i ) & 1 ) * $x;
		}
		return $z;
	}

	/**
	 * Sets a function module.
	 *
	 * @param int  $x    Column.
	 * @param int  $y    Row.
	 * @param bool $dark Dark module.
	 */
	private function set( $x, $y, $dark ): void {
		$this->modules[ $y ][ $x ]  = $dark ? 1 : 0;
		$this->function[ $y ][ $x ] = true;
	}

	/**
	 * Finder, timing and alignment patterns, the dark module, reserved format and version areas.
	 *
	 * @param int    $version Version.
	 * @param string $ecc     Level.
	 */
	private function draw_function_patterns( $version, $ecc ): void {
		for ( $i = 0; $i < $this->size; $i++ ) {
			$this->set( 6, $i, 0 === $i % 2 );
			$this->set( $i, 6, 0 === $i % 2 );
		}
		foreach ( array( array( 3, 3 ), array( $this->size - 4, 3 ), array( 3, $this->size - 4 ) ) as $center ) {
			for ( $dy = -4; $dy <= 4; $dy++ ) {
				for ( $dx = -4; $dx <= 4; $dx++ ) {
					$x = $center[0] + $dx;
					$y = $center[1] + $dy;
					if ( $x >= 0 && $x < $this->size && $y >= 0 && $y < $this->size ) {
						$distance = max( abs( $dx ), abs( $dy ) );
						$this->set( $x, $y, 2 !== $distance && 4 !== $distance );
					}
				}
			}
		}
		$positions = self::alignment_positions( $version );
		$count     = count( $positions );
		foreach ( $positions as $i => $cx ) {
			foreach ( $positions as $j => $cy ) {
				if ( ( 0 === $i && 0 === $j ) || ( 0 === $i && $count - 1 === $j ) || ( $count - 1 === $i && 0 === $j ) ) {
					continue;
				}
				for ( $dy = -2; $dy <= 2; $dy++ ) {
					for ( $dx = -2; $dx <= 2; $dx++ ) {
						$ring = max( abs( $dx ), abs( $dy ) );
						$this->set( $cx + $dx, $cy + $dy, 1 !== $ring );
					}
				}
			}
		}
		$this->draw_format_bits( $ecc, 0 );
		if ( $version >= 7 ) {
			$rem = $version;
			for ( $i = 0; $i < 12; $i++ ) {
				$rem = ( $rem << 1 ) ^ ( ( $rem >> 11 ) * 0x1F25 );
			}
			$bits = $version << 12 | $rem;
			for ( $i = 0; $i < 18; $i++ ) {
				$dark = 1 === ( ( $bits >> $i ) & 1 );
				$a    = $this->size - 11 + $i % 3;
				$b    = intdiv( $i, 3 );
				$this->set( $a, $b, $dark );
				$this->set( $b, $a, $dark );
			}
		}
	}

	/**
	 * Centers of the alignment patterns along one axis.
	 *
	 * @param int $version Version.
	 * @return array<int, int>
	 */
	private static function alignment_positions( $version ) {
		if ( 1 === $version ) {
			return array();
		}
		$count = intdiv( $version, 7 ) + 2;
		$step  = 32 === $version ? 26 : intdiv( $version * 4 + $count * 2 + 1, $count * 2 - 2 ) * 2;
		$size  = 4 * $version + 17;
		$list  = array( 6 );
		for ( $pos = $size - 7, $i = 0; $i < $count - 1; $i++, $pos -= $step ) {
			array_splice( $list, 1, 0, array( $pos ) );
		}
		return $list;
	}

	/**
	 * Both copies of the 15 format bits (level and mask with BCH code) plus the dark module.
	 *
	 * @param string $ecc  Level.
	 * @param int    $mask Mask.
	 */
	private function draw_format_bits( $ecc, $mask ): void {
		$data = self::FORMAT_BITS[ $ecc ] << 3 | $mask;
		$rem  = $data;
		for ( $i = 0; $i < 10; $i++ ) {
			$rem = ( $rem << 1 ) ^ ( ( $rem >> 9 ) * 0x537 );
		}
		$bits = ( $data << 10 | $rem ) ^ 0x5412;
		$bit  = function ( $i ) use ( $bits ) {
			return 1 === ( ( $bits >> $i ) & 1 );
		};
		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( $this->size - 1 - $i, 8, $bit( $i ) );
		}
		for ( $i = 8; $i < 15; $i++ ) {
			$this->set( 8, $this->size - 15 + $i, $bit( $i ) );
		}
		$this->set( 8, $this->size - 8, true );
	}

	/**
	 * Places the codewords in the zigzag order, two columns at a time from the right.
	 *
	 * @param array<int, int> $codewords Interleaved codewords.
	 */
	private function draw_codewords( $codewords ): void {
		$total = count( $codewords ) * 8;
		$i     = 0;
		for ( $right = $this->size - 1; $right >= 1; $right -= 2 ) {
			if ( 6 === $right ) {
				$right = 5;
			}
			for ( $vert = 0; $vert < $this->size; $vert++ ) {
				for ( $j = 0; $j < 2; $j++ ) {
					$x      = $right - $j;
					$upward = 0 === ( ( $right + 1 ) & 2 );
					$y      = $upward ? $this->size - 1 - $vert : $vert;
					if ( ! $this->function[ $y ][ $x ] && $i < $total ) {
						$this->modules[ $y ][ $x ] = ( $codewords[ $i >> 3 ] >> ( 7 - ( $i & 7 ) ) ) & 1;
						++$i;
					}
				}
			}
		}
	}

	/**
	 * Flips the data modules where the mask condition holds. Applying it twice undoes it.
	 *
	 * @param int $mask Mask 0 to 7.
	 */
	private function apply_mask( $mask ): void {
		for ( $y = 0; $y < $this->size; $y++ ) {
			for ( $x = 0; $x < $this->size; $x++ ) {
				if ( $this->function[ $y ][ $x ] ) {
					continue;
				}
				switch ( $mask ) {
					case 0:
						$flip = 0 === ( $x + $y ) % 2;
						break;
					case 1:
						$flip = 0 === $y % 2;
						break;
					case 2:
						$flip = 0 === $x % 3;
						break;
					case 3:
						$flip = 0 === ( $x + $y ) % 3;
						break;
					case 4:
						$flip = 0 === ( intdiv( $x, 3 ) + intdiv( $y, 2 ) ) % 2;
						break;
					case 5:
						$flip = 0 === $x * $y % 2 + $x * $y % 3;
						break;
					case 6:
						$flip = 0 === ( $x * $y % 2 + $x * $y % 3 ) % 2;
						break;
					default:
						$flip = 0 === ( ( $x + $y ) % 2 + $x * $y % 3 ) % 2;
				}
				if ( $flip ) {
					$this->modules[ $y ][ $x ] ^= 1;
				}
			}
		}
	}

	/**
	 * Penalty score of the current symbol (rules N1 to N4).
	 */
	private function penalty(): int {
		$result = 0;
		$size   = $this->size;
		$lines  = array();
		for ( $y = 0; $y < $size; $y++ ) {
			$lines[] = $this->modules[ $y ];
		}
		for ( $x = 0; $x < $size; $x++ ) {
			$lines[] = array_column( $this->modules, $x );
		}
		foreach ( $lines as $line ) {
			$color   = 0;
			$run     = 0;
			$history = array_fill( 0, 7, 0 );
			foreach ( $line as $module ) {
				if ( $module === $color ) {
					++$run;
					if ( 5 === $run ) {
						$result += 3;
					} elseif ( $run > 5 ) {
						++$result;
					}
				} else {
					$this->add_history( $run, $history );
					if ( 0 === $color ) {
						$result += $this->count_finder_like( $history ) * 40;
					}
					$color = $module;
					$run   = 1;
				}
			}
			if ( 1 === $color ) {
				$this->add_history( $run, $history );
				$run = 0;
			}
			$this->add_history( $run + $size, $history );
			$result += $this->count_finder_like( $history ) * 40;
		}
		$dark = 0;
		for ( $y = 0; $y < $size; $y++ ) {
			for ( $x = 0; $x < $size; $x++ ) {
				$color = $this->modules[ $y ][ $x ];
				$dark += $color;
				if ( $x < $size - 1 && $y < $size - 1 && $color === $this->modules[ $y ][ $x + 1 ] && $color === $this->modules[ $y + 1 ][ $x ] && $color === $this->modules[ $y + 1 ][ $x + 1 ] ) {
					$result += 3;
				}
			}
		}
		$total   = $size * $size;
		$k       = intdiv( abs( $dark * 20 - $total * 10 ) + $total - 1, $total ) - 1;
		$result += $k * 10;
		return $result;
	}

	/**
	 * Pushes a run length into the history; the first run counts the light quiet zone as well.
	 *
	 * @param int             $run     Run length.
	 * @param array<int, int> $history Last seven runs, newest first.
	 */
	private function add_history( $run, &$history ): void {
		if ( 0 === $history[0] ) {
			$run += $this->size;
		}
		array_pop( $history );
		array_unshift( $history, $run );
	}

	/**
	 * Patterns dark-light-dark-dark-dark-light-dark in 1:1:3:1:1 with four light modules on one side.
	 *
	 * @param array<int, int> $history Last seven runs, newest first.
	 */
	private function count_finder_like( $history ): int {
		$n    = $history[1];
		$core = $n > 0 && $history[2] === $n && $history[3] === $n * 3 && $history[4] === $n && $history[5] === $n;
		return ( $core && $history[0] >= $n * 4 && $history[6] >= $n ? 1 : 0 ) + ( $core && $history[6] >= $n * 4 && $history[0] >= $n ? 1 : 0 );
	}
}