<?php
/*************************************************************
# 076 License

Copyright (c) テクニカル諏訪子

Permission is hereby granted to any person obtaining a copy of the software
Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
sublicense, and/or sell copies of the Software, subject to the following conditions:

    1. **Origin Attribution**:
       - You must not misrepresent the origin of the Software; you must not claim
         you created the original Software.
       - If the Software is used in a product, you must either:
         a. Provide clear attribution in the product's documentation, user interface,
            or other visible areas, **OR**
         b. Pay the original developers a fee they specify in writing.
    2. **Usage Restriction**:
       - The Software, or any derivative works, dependencies, or libraries
         incorporating it, must not be used for censorship or to suppress freedom of
         speech, expression, or creativity. Prohibited uses include, but are not
         limited to:
         - Censorship of so-called "hate speech", visuals, non-mainstream opinions,
           ideas, or objective reality.
         - Tools or systems designed to restrict access to information or
           artistic works.
    3. **Notice Preservation**:
       - This license and the above copyright notice must remain intact in all copies
         of the source code.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
namespace Std\Lib;

use Std\Lib\Image\Bitmap;

/**
 * QRコード（ISO/IEC 18004）
 *
 * 型番1～40、誤り訂正L・M・Q・H、数字・英数字・バイト（UTF-8）のモード、8つのマスクから減点の一番少ない物。
 * 画像にはbitmap()（PNG等はImage::encodeで）。
 */
final class Qr {
  /** 誤り訂正のレベル => [形式情報のビット, 1ブロックの誤り訂正の数（型番1～40）, ブロックの数] */
  private const EC = [
    'L' => [1, [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],
      [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' => [0, [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],
      [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' => [3, [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],
      [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' => [2, [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],
      [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]],
  ];
  private const ALNUM = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:';

  public int $version;
  public int $size;
  public int $mask;
  public string $level;
  /** 行毎のモジュール（trueが黒） */
  public array $modules = [];
  /** 機能パターン（データを置かない所） */
  private array $function = [];

  /**
   * @param string $text  中身（数字だけ、英大文字等だけなら小さいモードを使う）
   * @param string $level  誤り訂正（L：7%、M：15%、Q：25%、H：30%）
   * @param int $minVersion  最小の型番
   * @throws \InvalidArgumentException  入り切らない場合
   */
  public function __construct(string $text, string $level = 'M', int $minVersion = 1) {
    if (!isset(self::EC[$level])) throw new \InvalidArgumentException('誤り訂正のレベルはL・M・Q・Hです。');
    $this->level = $level;
    [$mode, $count] = match (true) {
      preg_match('/^\d*$/', $text) === 1 => [1, strlen($text)],
      strspn($text, self::ALNUM) === strlen($text) => [2, strlen($text)],
      default => [4, strlen($text)],
    };
    for ($v = max(1, $minVersion); $v <= 40; $v++) {
      $bits = self::segment($text, $mode, $count, $v);
      if ($bits !== null && strlen($bits) <= self::dataCodewords($v, $level) * 8) break;
    }
    if ($v > 40) throw new \InvalidArgumentException('QRコードに入り切りません。');
    $this->version = $v;
    $this->size = $v * 4 + 17;

    // 終端（4ビットまで）、8ビットに揃え、残りは0xEC・0x11の繰り返し
    $cap = self::dataCodewords($v, $level) * 8;
    $bits .= str_repeat('0', min(4, $cap - strlen($bits)));
    $bits .= str_repeat('0', (8 - strlen($bits) % 8) % 8);
    for ($pad = 0xec; strlen($bits) < $cap; $pad ^= 0xec ^ 0x11) $bits .= sprintf('%08b', $pad);
    $data = array_map('bindec', str_split($bits, 8));

    $this->modules = array_fill(0, $this->size, array_fill(0, $this->size, false));
    $this->function = $this->modules;
    $this->drawFunctions();
    $this->drawCodewords(self::interleave($data, $v, $level));

    // 減点の一番少ないマスク
    $best = null;
    for ($m = 0; $m < 8; $m++) {
      $this->applyMask($m);
      $this->drawFormat($m);
      $p = $this->penalty();
      if ($best === null || $p < $best[0]) $best = [$p, $m];
      $this->applyMask($m);
    }
    $this->mask = $best[1];
    $this->applyMask($this->mask);
    $this->drawFormat($this->mask);
    unset($this->function);
  }

  /**
   * 画像にする
   *
   * @param int $scale  1モジュールの画素数
   * @param int $margin  周りの白（モジュール、規格では4以上）
   */
  public function bitmap(int $scale = 4, int $margin = 4): Bitmap {
    $w = ($this->size + 2 * $margin) * $scale;
    $white = str_repeat("\xff\xff\xff\xff", $w);
    $data = str_repeat($white, $margin * $scale);
    foreach ($this->modules as $row) {
      $line = str_repeat("\xff\xff\xff\xff", $margin * $scale);
      foreach ($row as $dark) $line .= str_repeat($dark ? "\0\0\0\xff" : "\xff\xff\xff\xff", $scale);
      $line .= str_repeat("\xff\xff\xff\xff", $margin * $scale);
      $data .= str_repeat($line, $scale);
    }
    $data .= str_repeat($white, $margin * $scale);
    return new Bitmap($w, $w, $data);
  }

  /**
   * モード、文字数、データのビット列（文字数が型番の欄に入らなければnull）
   */
  private static function segment(string $text, int $mode, int $count, int $v): ?string {
    $cbits = match ($mode) {
      1 => $v < 10 ? 10 : ($v < 27 ? 12 : 14),
      2 => $v < 10 ? 9 : ($v < 27 ? 11 : 13),
      default => $v < 10 ? 8 : 16,
    };
    if ($count >= 1 << $cbits) return null;
    $bits = sprintf('%04b', $mode).str_pad(decbin($count), $cbits, '0', STR_PAD_LEFT);
    if ($mode === 1) {
      foreach (str_split($text, 3) as $g) if ($g !== '') $bits .= str_pad(decbin((int)$g), [1 => 4, 2 => 7, 3 => 10][strlen($g)], '0', STR_PAD_LEFT);
    } else if ($mode === 2) {
      foreach (str_split($text, 2) as $g) {
        if ($g === '') continue;
        $bits .= strlen($g) === 2
          ? str_pad(decbin(strpos(self::ALNUM, $g[0]) * 45 + strpos(self::ALNUM, $g[1])), 11, '0', STR_PAD_LEFT)
          : str_pad(decbin(strpos(self::ALNUM, $g)), 6, '0', STR_PAD_LEFT);
      }
    } else {
      for ($i = 0; $i < $count; $i++) $bits .= sprintf('%08b', ord($text[$i]));
    }
    return $bits;
  }

  /** データを置けるモジュールの数（機能パターンと形式・型番情報を除く） */
  private static function rawModules(int $v): int {
    $n = (16 * $v + 128) * $v + 64;
    if ($v >= 2) {
      $align = intdiv($v, 7) + 2;
      $n -= (25 * $align - 10) * $align - 55;
      if ($v >= 7) $n -= 36;
    }
    return $n;
  }

  private static function dataCodewords(int $v, string $level): int {
    [, $ecc, $blocks] = self::EC[$level];
    return intdiv(self::rawModules($v), 8) - $ecc[$v - 1] * $blocks[$v - 1];
  }

  /**
   * ブロックに分けて誤り訂正を付け、交互に並べる
   */
  private static function interleave(array $data, int $v, string $level): array {
    [, $eccs, $nblocks] = self::EC[$level];
    $ecc = $eccs[$v - 1];
    $n = $nblocks[$v - 1];
    $total = intdiv(self::rawModules($v), 8);
    $short = $n - $total % $n;
    $shortLen = intdiv($total, $n);
    $gen = self::generator($ecc);
    $blocks = [];
    $pos = 0;
    for ($i = 0; $i < $n; $i++) {
      $len = $shortLen - $ecc + ($i < $short ? 0 : 1);
      $d = array_slice($data, $pos, $len);
      $pos += $len;
      $blocks[] = [$d, self::remainder($d, $gen)];
    }
    $out = [];
    for ($i = 0; $i <= $shortLen - $ecc; $i++) {
      foreach ($blocks as [$d]) if (isset($d[$i])) $out[] = $d[$i];
    }
    for ($i = 0; $i < $ecc; $i++) {
      foreach ($blocks as [, $e]) $out[] = $e[$i];
    }
    return $out;
  }

  /** GF(2^8)（x^8 + x^4 + x^3 + x^2 + 1）の掛け算 */
  private static function mul(int $x, int $y): int {
    $z = 0;
    for ($i = 7; $i >= 0; $i--) {
      $z = ($z << 1) ^ (($z >> 7) * 0x11d);
      $z ^= (($y >> $i) & 1) * $x;
    }
    return $z;
  }

  /** リード・ソロモンの生成多項式（最高次の係数は省く） */
  private static function generator(int $degree): array {
    $g = array_fill(0, $degree, 0);
    $g[$degree - 1] = 1;
    $root = 1;
    for ($i = 0; $i < $degree; $i++) {
      for ($j = 0; $j < $degree; $j++) {
        $g[$j] = self::mul($g[$j], $root);
        if ($j + 1 < $degree) $g[$j] ^= $g[$j + 1];
      }
      $root = self::mul($root, 0x02);
    }
    return $g;
  }

  private static function remainder(array $data, array $gen): array {
    $r = array_fill(0, count($gen), 0);
    foreach ($data as $b) {
      $f = $b ^ array_shift($r);
      $r[] = 0;
      foreach ($gen as $i => $c) $r[$i] ^= self::mul($c, $f);
    }
    return $r;
  }

  private function set(int $x, int $y, bool $dark): void {
    $this->modules[$y][$x] = $dark;
    $this->function[$y][$x] = true;
  }

  /** 位置検出、タイミング、位置合わせのパターン、型番情報（形式情報の場所は先に取っておく） */
  private function drawFunctions(): void {
    $s = $this->size;
    for ($i = 0; $i < $s; $i++) {
      $this->set(6, $i, $i % 2 === 0);
      $this->set($i, 6, $i % 2 === 0);
    }
    foreach ([[3, 3], [$s - 4, 3], [3, $s - 4]] as [$cx, $cy]) {
      for ($dy = -4; $dy <= 4; $dy++) {
        for ($dx = -4; $dx <= 4; $dx++) {
          $x = $cx + $dx;
          $y = $cy + $dy;
          if ($x < 0 || $y < 0 || $x >= $s || $y >= $s) continue;
          $d = max(abs($dx), abs($dy));
          $this->set($x, $y, $d !== 2 && $d !== 4);
        }
      }
    }
    // 位置合わせ（位置検出と重なる3つの角以外）
    if ($this->version > 1) {
      $n = intdiv($this->version, 7) + 2;
      $step = intdiv($this->version * 8 + $n * 3 + 5, $n * 4 - 4) * 2;
      $pos = [6];
      for ($i = $n - 1; $i >= 1; $i--) $pos[$i] = $s - 7 - ($n - 1 - $i) * $step;
      ksort($pos);
      foreach ($pos as $i => $x) {
        foreach ($pos as $j => $y) {
          if (($i === 0 && $j === 0) || ($i === 0 && $j === $n - 1) || ($i === $n - 1 && $j === 0)) continue;
          for ($dy = -2; $dy <= 2; $dy++) for ($dx = -2; $dx <= 2; $dx++) $this->set($x + $dx, $y + $dy, max(abs($dx), abs($dy)) !== 1);
        }
      }
    }
    $this->drawFormat(0);
    if ($this->version >= 7) {
      $rem = $this->version;
      for ($i = 0; $i < 12; $i++) $rem = ($rem << 1) ^ (($rem >> 11) * 0x1f25);
      $bits = ($this->version << 12) | $rem;
      for ($i = 0; $i < 18; $i++) {
        $dark = (($bits >> $i) & 1) === 1;
        $a = $s - 11 + $i % 3;
        $b = intdiv($i, 3);
        $this->set($a, $b, $dark);
        $this->set($b, $a, $dark);
      }
    }
  }

  /** 形式情報（誤り訂正のレベルとマスク）の2つの写し */
  private function drawFormat(int $mask): void {
    $data = (self::EC[$this->level][0] << 3) | $mask;
    $rem = $data;
    for ($i = 0; $i < 10; $i++) $rem = ($rem << 1) ^ (($rem >> 9) * 0x537);
    $bits = (($data << 10) | $rem) ^ 0x5412;
    $bit = fn(int $i): bool => (($bits >> $i) & 1) === 1;
    $s = $this->size;
    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($s - 1 - $i, 8, $bit($i));
    for ($i = 8; $i < 15; $i++) $this->set(8, $s - 15 + $i, $bit($i));
    $this->set(8, $s - 8, true);
  }

  /** 右下から2列ずつ、上下にジグザグに置く */
  private function drawCodewords(array $data): void {
    $s = $this->size;
    $total = count($data) * 8;
    $i = 0;
    for ($right = $s - 1; $right >= 1; $right -= 2) {
      if ($right === 6) $right = 5;
      $up = (($right + 1) & 2) === 0;
      for ($vert = 0; $vert < $s; $vert++) {
        $y = $up ? $s - 1 - $vert : $vert;
        for ($j = 0; $j < 2; $j++) {
          $x = $right - $j;
          if ($this->function[$y][$x]) continue;
          // 残りのモジュールは0（白）
          if ($i < $total) $this->modules[$y][$x] = (($data[$i >> 3] >> (7 - ($i & 7))) & 1) === 1;
          $i++;
        }
      }
    }
  }

  /** マスク（2回掛けると元に戻る） */
  private function applyMask(int $m): void {
    for ($y = 0; $y < $this->size; $y++) {
      for ($x = 0; $x < $this->size; $x++) {
        if ($this->function[$y][$x]) continue;
        $flip = match ($m) {
          0 => ($x + $y) % 2 === 0,
          1 => $y % 2 === 0,
          2 => $x % 3 === 0,
          3 => ($x + $y) % 3 === 0,
          4 => (intdiv($x, 3) + intdiv($y, 2)) % 2 === 0,
          5 => $x * $y % 2 + $x * $y % 3 === 0,
          6 => ($x * $y % 2 + $x * $y % 3) % 2 === 0,
          default => (($x + $y) % 2 + $x * $y % 3) % 2 === 0,
        };
        if ($flip) $this->modules[$y][$x] = !$this->modules[$y][$x];
      }
    }
  }

  /**
   * 減点（同じ色の5つ以上の並び、2x2の塊、位置検出に似た模様、黒の割合）
   */
  private function penalty(): int {
    $s = $this->size;
    $p = 0;
    $lines = [];
    for ($y = 0; $y < $s; $y++) {
      $lines[] = implode('', array_map(fn($d) => $d ? '1' : '0', $this->modules[$y]));
    }
    $cols = [];
    for ($x = 0; $x < $s; $x++) {
      $c = '';
      for ($y = 0; $y < $s; $y++) $c .= $lines[$y][$x];
      $cols[] = $c;
    }
    $dark = 0;
    foreach ([...$lines, ...$cols] as $k => $line) {
      if ($k < $s) $dark += substr_count($line, '1');
      if (preg_match_all('/0{5,}|1{5,}/', $line, $m)) foreach ($m[0] as $run) $p += strlen($run) - 2;
      // 1:1:3:1:1の両側に4つの白（外側は白とみなす）
      $padded = '0000'.$line.'0000';
      $p += 40 * (preg_match_all('/(?=00001011101)/', $padded) + preg_match_all('/(?=10111010000)/', $padded));
    }
    for ($y = 0; $y < $s - 1; $y++) {
      for ($x = 0; $x < $s - 1; $x++) {
        $c = $lines[$y][$x];
        if ($c === $lines[$y][$x + 1] && $c === $lines[$y + 1][$x] && $c === $lines[$y + 1][$x + 1]) $p += 3;
      }
    }
    $total = $s * $s;
    $p += 10 * max(0, intdiv(abs($dark * 20 - $total * 10) + $total - 1, $total) - 1);
    return $p;
  }
}