<?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\Image;

/**
 * WebPの可逆圧縮（VP8L）
 *
 * 読み込み：全ての変換（予測、色、緑を引く、パレット）、カラーキャッシュ、メタプレフィックス符号、後方参照。
 * 書き出し：256色以下はパレット（少なければ画素を詰める）、それ以外は緑を引く＋予測、LZ77とカラーキャッシュ、ハフマン符号。
 * 画素は内部ではARGBの整数（又はその4バイトの列、ビッグエンディアン）。
 */
final class Vp8l {
  private const ORDER = [17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
  /** 距離の符号1～120の(x, y)のずれ */
  private const PLANE = [
    [0, 1], [1, 0], [1, 1], [-1, 1], [0, 2], [2, 0], [1, 2], [-1, 2], [2, 1], [-2, 1], [2, 2], [-2, 2], [0, 3], [3, 0], [1, 3], [-1, 3],
    [3, 1], [-3, 1], [2, 3], [-2, 3], [3, 2], [-3, 2], [0, 4], [4, 0], [1, 4], [-1, 4], [4, 1], [-4, 1], [3, 3], [-3, 3], [2, 4], [-2, 4],
    [4, 2], [-4, 2], [0, 5], [3, 4], [-3, 4], [4, 3], [-4, 3], [5, 0], [1, 5], [-1, 5], [5, 1], [-5, 1], [2, 5], [-2, 5], [5, 2], [-5, 2],
    [4, 4], [-4, 4], [3, 5], [-3, 5], [5, 3], [-5, 3], [0, 6], [6, 0], [1, 6], [-1, 6], [6, 1], [-6, 1], [2, 6], [-2, 6], [6, 2], [-6, 2],
    [4, 5], [-4, 5], [5, 4], [-5, 4], [3, 6], [-3, 6], [6, 3], [-6, 3], [0, 7], [7, 0], [1, 7], [-1, 7], [5, 5], [-5, 5], [7, 1], [-7, 1],
    [4, 6], [-4, 6], [6, 4], [-6, 4], [2, 7], [-2, 7], [7, 2], [-7, 2], [3, 7], [-3, 7], [7, 3], [-7, 3], [5, 6], [-5, 6], [6, 5], [-6, 5],
    [8, 0], [4, 7], [-4, 7], [7, 4], [-7, 4], [8, 1], [8, 2], [6, 6], [-6, 6], [8, 3], [5, 7], [-5, 7], [7, 5], [-7, 5], [8, 4], [6, 7],
    [-6, 7], [7, 6], [-7, 6], [8, 5], [7, 7], [-7, 7], [8, 6], [8, 7],
  ];
  private const HASH = 0x1e35a7bd;
  private const MAX_LENGTH = 4096;
  private const MAX_DISTANCE = 1048576;

  private string $d = '';
  private int $p = 0;
  private int $buf = 0;
  private int $bits = 0;

  private string $out = '';
  private int $acc = 0;
  private int $nb = 0;

  //////// 読み込み

  /**
   * VP8Lチャンクの中身を読む
   *
   * @return array  [幅, 丈, ARGBの列]
   */
  public function decode(string $data): array {
    if (strlen($data) < 5 || $data[0] !== "\x2f") throw new \RuntimeException('VP8Lの印がありません。');
    $this->start($data, 1);
    $w = $this->read(14) + 1;
    $h = $this->read(14) + 1;
    $this->read(1); // アルファを使うか（参考だけ）
    if ($this->read(3) !== 0) throw new \RuntimeException('未対応のVP8Lの版です。');
    Bitmap::check($w, $h);
    return [$w, $h, $this->imageStream($w, $h)];
  }

  /**
   * ヘッダーの無い画像（ALPHチャンクの中身）を読む
   */
  public function decodeImage(string $data, int $w, int $h): string {
    $this->start($data, 0);
    return $this->imageStream($w, $h);
  }

  private function start(string $data, int $pos): void {
    $this->d = $data;
    $this->p = $pos;
    $this->buf = $this->bits = 0;
  }

  private function read(int $n): int {
    while ($this->bits < $n) {
      $this->buf |= ord($this->d[$this->p++] ?? "\0") << $this->bits;
      $this->bits += 8;
    }
    $v = $this->buf & ((1 << $n) - 1);
    $this->buf >>= $n;
    $this->bits -= $n;
    return $v;
  }

  private function imageStream(int $w, int $h): string {
    $transforms = [];
    $xsize = $w;
    while ($this->read(1)) {
      $type = $this->read(2);
      if (isset($transforms[$type])) throw new \RuntimeException('VP8Lの変換が重複しています。');
      $t = ['type' => $type, 'w' => $xsize];
      if ($type === 0 || $type === 1) {
        $t['bits'] = $this->read(3) + 2;
        $t['bw'] = self::subSize($xsize, $t['bits']);
        $t['data'] = $this->subImage($t['bw'], self::subSize($h, $t['bits']));
      } else if ($type === 3) {
        $n = $this->read(8) + 1;
        $pal = $this->subImage($n, 1);
        for ($i = 1; $i < $n; $i++) $pal[$i] = self::add($pal[$i], $pal[$i - 1]);
        // 範囲外の番号は透明な黒
        $t['palette'] = array_pad(array_map(fn($c) => pack('N', $c), $pal), 256, "\0\0\0\0");
        $t['bits'] = $n <= 2 ? 3 : ($n <= 4 ? 2 : ($n <= 16 ? 1 : 0));
        $xsize = self::subSize($xsize, $t['bits']);
      }
      $transforms[$type] = $t;
    }
    $px = $this->entropyImage($xsize, $h, true);
    foreach (array_reverse($transforms, true) as $type => $t) {
      $px = match ($type) {
        0 => self::inversePredictor($px, $t, $h),
        1 => self::inverseColor($px, $t, $h),
        2 => self::addGreen($px, $t['w'], $h),
        3 => self::inversePalette($px, $t, $h, $xsize),
      };
      if ($type === 3) $xsize = $t['w'];
    }
    return $px;
  }

  private static function subSize(int $size, int $bits): int {
    return ($size + (1 << $bits) - 1) >> $bits;
  }

  /** 変換用の小さい画像（ARGBの整数の配列） */
  private function subImage(int $w, int $h): array {
    return array_values(unpack('N*', $this->entropyImage($w, $h, false)));
  }

  /**
   * エントロピー符号化した画像
   *
   * @param bool $main  主画像（メタプレフィックス符号を使える）
   */
  private function entropyImage(int $w, int $h, bool $main): string {
    $cacheBits = 0;
    if ($this->read(1)) {
      $cacheBits = $this->read(4);
      if ($cacheBits < 1 || $cacheBits > 11) throw new \RuntimeException('VP8Lのカラーキャッシュが不正です。');
    }
    $meta = null;
    $metaBits = 0;
    $metaW = 0;
    $groups = 1;
    if ($main && $this->read(1)) {
      $metaBits = $this->read(3) + 2;
      $metaW = self::subSize($w, $metaBits);
      $meta = $this->subImage($metaW, self::subSize($h, $metaBits));
      foreach ($meta as $i => $v) $meta[$i] = ($v >> 8) & 0xffff;
      $groups = max($meta) + 1;
    }
    $cacheSize = $cacheBits ? 1 << $cacheBits : 0;
    $codes = [];
    for ($g = 0; $g < $groups; $g++) {
      $codes[] = [$this->readCode(280 + $cacheSize), $this->readCode(256), $this->readCode(256), $this->readCode(256), $this->readCode(40)];
    }

    $total = $w * $h;
    $px = '';
    $cache = $cacheSize ? array_fill(0, $cacheSize, 0) : null;
    $shift = 32 - $cacheBits;
    $pos = $x = $y = 0;
    $mask = (1 << $metaBits) - 1;
    [$G, $R, $B, $A, $D] = $codes[0];
    while ($pos < $total) {
      if ($meta !== null && ($x & $mask) === 0) [$G, $R, $B, $A, $D] = $codes[$meta[($y >> $metaBits) * $metaW + ($x >> $metaBits)]];
      $s = $this->sym($G);
      if ($s < 256) {
        $r = $this->sym($R);
        $b = $this->sym($B);
        $v = ($this->sym($A) << 24) | ($r << 16) | ($s << 8) | $b;
        $px .= pack('N', $v);
        if ($cache !== null) $cache[(($v * self::HASH) & 0xffffffff) >> $shift] = $v;
        $pos++;
        if (++$x === $w) {
          $x = 0;
          $y++;
          // 壊れた（短い）ファイルで長く掛からない様に
          if ($this->p > strlen($this->d) + 8) throw new \RuntimeException('VP8Lのデータが途中で切れています。');
        }
        continue;
      }
      if ($s < 280) {
        $len = $this->prefixValue($s - 256);
        $dcode = $this->prefixValue($this->sym($D));
        if ($dcode > 120) {
          $dist = $dcode - 120;
        } else {
          [$xi, $yi] = self::PLANE[$dcode - 1];
          $dist = max(1, $xi + $yi * $w);
        }
        if ($dist > $pos || $pos + $len > $total) throw new \RuntimeException('VP8Lの後方参照が不正です。');
        $chunk = substr($px, ($pos - $dist) * 4, min($dist, $len) * 4);
        if ($dist < $len) $chunk = substr(str_repeat($chunk, intdiv($len, $dist) + 1), 0, $len * 4);
        $px .= $chunk;
        if ($cache !== null) foreach (unpack('N*', $chunk) as $v) $cache[(($v * self::HASH) & 0xffffffff) >> $shift] = $v;
        $pos += $len;
        $x += $len;
        if ($x >= $w) {
          $y += intdiv($x, $w);
          $x %= $w;
          if ($this->p > strlen($this->d) + 8) throw new \RuntimeException('VP8Lのデータが途中で切れています。');
        }
        if ($meta !== null && $pos < $total) [$G, $R, $B, $A, $D] = $codes[$meta[($y >> $metaBits) * $metaW + ($x >> $metaBits)]];
        continue;
      }
      if ($cache === null) throw new \RuntimeException('VP8Lのカラーキャッシュがありません。');
      $v = $cache[$s - 280];
      $px .= pack('N', $v);
      $cache[(($v * self::HASH) & 0xffffffff) >> $shift] = $v;
      $pos++;
      if (++$x === $w) {
        $x = 0;
        $y++;
      }
    }
    if ($this->p - ($this->bits >> 3) > strlen($this->d)) throw new \RuntimeException('VP8Lのデータが途中で切れています。');
    return $px;
  }

  private function prefixValue(int $prefix): int {
    if ($prefix < 4) return $prefix + 1;
    $extra = ($prefix - 2) >> 1;
    return ((2 + ($prefix & 1)) << $extra) + $this->read($extra) + 1;
  }

  /** プレフィックス符号（ハフマン符号）を読む */
  private function readCode(int $alphabet): array {
    $lengths = array_fill(0, $alphabet, 0);
    if ($this->read(1)) {
      // 簡単な符号：1か2個の記号
      $two = $this->read(1);
      $s = $this->read($this->read(1) ? 8 : 1);
      if ($s >= $alphabet) throw new \RuntimeException('VP8Lの符号が不正です。');
      $lengths[$s] = 1;
      if ($two) {
        $s = $this->read(8);
        if ($s >= $alphabet) throw new \RuntimeException('VP8Lの符号が不正です。');
        $lengths[$s] = 1;
      }
      return self::buildCode($lengths);
    }
    $clen = array_fill(0, 19, 0);
    $n = 4 + $this->read(4);
    for ($i = 0; $i < $n; $i++) $clen[self::ORDER[$i]] = $this->read(3);
    $cl = self::buildCode($clen);
    $max = $alphabet;
    if ($this->read(1)) {
      $max = 2 + $this->read(2 + 2 * $this->read(3));
      if ($max > $alphabet) throw new \RuntimeException('VP8Lの符号長が多過ぎます。');
    }
    $prev = 8;
    $sym = 0;
    while ($sym < $alphabet && $max-- > 0) {
      $c = $this->sym($cl);
      if ($c < 16) {
        $lengths[$sym++] = $c;
        if ($c !== 0) $prev = $c;
        continue;
      }
      [$rep, $val] = match ($c) {16 => [3 + $this->read(2), $prev], 17 => [3 + $this->read(3), 0], default => [11 + $this->read(7), 0]};
      if ($sym + $rep > $alphabet) throw new \RuntimeException('VP8Lの符号長が不正です。');
      for ($i = 0; $i < $rep; $i++) $lengths[$sym++] = $val;
    }
    return self::buildCode($lengths);
  }

  /**
   * 符号長から読む為の表を作る（下位ビットから読むので、符号を反転して引く）
   *
   * @return array  ['single' => 記号]（0ビット）、又は[根の表, 長い符号の表]
   */
  private static function buildCode(array $lengths): array {
    $count = array_fill(0, 16, 0);
    $one = 0;
    $used = 0;
    foreach ($lengths as $s => $l) {
      if ($l === 0) continue;
      $count[$l]++;
      $one = $s;
      $used++;
    }
    if ($used <= 1) return ['single' => $one];
    $kraft = 0;
    for ($l = 1; $l < 16; $l++) $kraft += $count[$l] << (15 - $l);
    if ($kraft !== 1 << 15) throw new \RuntimeException('VP8Lのハフマン符号が不完全です。');
    $next = [];
    $code = 0;
    for ($l = 1; $l < 16; $l++) {
      $code = ($code + $count[$l - 1]) << 1;
      $next[$l] = $code;
    }
    $prim = 8;
    $root = array_fill(0, 1 << $prim, 0);
    $codes = [];
    $subBits = [];
    foreach ($lengths as $s => $l) {
      if ($l === 0) continue;
      $c = $next[$l]++;
      $r = 0;
      for ($i = 0; $i < $l; $i++) $r |= (($c >> $i) & 1) << ($l - 1 - $i);
      $codes[] = [$s, $l, $r];
      if ($l > $prim) {
        $k = $r & 0xff;
        $subBits[$k] = max($subBits[$k] ?? 0, $l - $prim);
      }
    }
    $long = [];
    foreach ($subBits as $k => $sb) {
      $long[$k] = [$sb, array_fill(0, 1 << $sb, 0)];
      $root[$k] = -1;
    }
    foreach ($codes as [$s, $l, $r]) {
      if ($l <= $prim) {
        for ($j = $r; $j < 256; $j += 1 << $l) $root[$j] = ($l << 16) | $s;
      } else {
        $k = $r & 0xff;
        $sb = $long[$k][0];
        for ($j = $r >> $prim; $j < (1 << $sb); $j += 1 << ($l - $prim)) $long[$k][1][$j] = ($l << 16) | $s;
      }
    }
    return [$root, $long];
  }

  private function sym(array $c): int {
    if (isset($c['single'])) return $c['single'];
    if ($this->bits < 15) {
      do {
        $this->buf |= ord($this->d[$this->p++] ?? "\0") << $this->bits;
        $this->bits += 8;
      } while ($this->bits <= 48);
    }
    $e = $c[0][$this->buf & 0xff];
    if ($e < 0) {
      [$sb, $sub] = $c[1][$this->buf & 0xff];
      $e = $sub[($this->buf >> 8) & ((1 << $sb) - 1)];
    }
    $l = $e >> 16;
    $this->buf >>= $l;
    $this->bits -= $l;
    return $e & 0xffff;
  }

  //////// 逆変換

  /** 各成分を256で割った余りで足す */
  private static function add(int $a, int $b): int {
    return ((($a & 0xff00ff00) + ($b & 0xff00ff00)) & 0xff00ff00) | ((($a & 0x00ff00ff) + ($b & 0x00ff00ff)) & 0x00ff00ff);
  }

  private static function sub(int $a, int $b): int {
    return ((($a | 0x00ff00ff) - ($b & 0xff00ff00)) & 0xff00ff00) | ((($a | 0xff00ff00) - ($b & 0x00ff00ff)) & 0x00ff00ff);
  }

  private static function avg(int $a, int $b): int {
    return ((($a ^ $b) & 0xfefefefe) >> 1) + ($a & $b);
  }

  /**
   * 予測値（モード0～13）
   */
  private static function predict(int $mode, int $L, int $T, int $TR, int $TL): int {
    return match ($mode) {
      1 => $L,
      2 => $T,
      3 => $TR,
      4 => $TL,
      5 => self::avg(self::avg($L, $TR), $T),
      6 => self::avg($L, $TL),
      7 => self::avg($L, $T),
      8 => self::avg($TL, $T),
      9 => self::avg($T, $TR),
      10 => self::avg(self::avg($L, $TL), self::avg($T, $TR)),
      11 => self::select($L, $T, $TL),
      12 => self::clampAdd($L, $T, $TL),
      13 => self::clampHalf(self::avg($L, $T), $TL),
      default => 0xff000000,
    };
  }

  private static function select(int $L, int $T, int $TL): int {
    // 左なら|T - TL|、上なら|L - TL|が予測との距離
    $pl = $pt = 0;
    for ($s = 0; $s < 32; $s += 8) {
      $tl = ($TL >> $s) & 255;
      $pl += abs((($T >> $s) & 255) - $tl);
      $pt += abs((($L >> $s) & 255) - $tl);
    }
    return $pl < $pt ? $L : $T;
  }

  private static function clampAdd(int $a, int $b, int $c): int {
    $out = 0;
    for ($s = 0; $s < 32; $s += 8) {
      $v = (($a >> $s) & 255) + (($b >> $s) & 255) - (($c >> $s) & 255);
      $out |= ($v < 0 ? 0 : ($v > 255 ? 255 : $v)) << $s;
    }
    return $out;
  }

  private static function clampHalf(int $a, int $b): int {
    $out = 0;
    for ($s = 0; $s < 32; $s += 8) {
      $av = ($a >> $s) & 255;
      $v = $av + intdiv($av - (($b >> $s) & 255), 2);
      $out |= ($v < 0 ? 0 : ($v > 255 ? 255 : $v)) << $s;
    }
    return $out;
  }

  private static function inversePredictor(string $px, array $t, int $h): string {
    $w = $t['w'];
    $bits = $t['bits'];
    $bw = $t['bw'];
    $modes = $t['data'];
    $out = '';
    $prev = [];
    for ($y = 0; $y < $h; $y++) {
      $res = unpack('N*', substr($px, $y * $w * 4, $w * 4));
      // 左上は黒、1行目は左、左の列は上
      $cur = [self::add($res[1], $y === 0 ? 0xff000000 : $prev[0])];
      if ($y === 0) {
        for ($x = 1; $x < $w; $x++) $cur[$x] = self::add($res[$x + 1], $cur[$x - 1]);
      } else {
        $mrow = ($y >> $bits) * $bw;
        for ($x = 1; $x < $w; $x++) {
          // 右端の右上は、この行の左端
          $pred = self::predict(($modes[$mrow + ($x >> $bits)] >> 8) & 15, $cur[$x - 1], $prev[$x], $x + 1 < $w ? $prev[$x + 1] : $cur[0], $prev[$x - 1]);
          $cur[$x] = self::add($res[$x + 1], $pred);
        }
      }
      $out .= pack('N*', ...$cur);
      $prev = $cur;
    }
    return $out;
  }

  private static function inverseColor(string $px, array $t, int $h): string {
    $w = $t['w'];
    $bits = $t['bits'];
    $bw = $t['bw'];
    $out = '';
    $s8 = fn(int $v): int => $v >= 128 ? $v - 256 : $v;
    for ($y = 0; $y < $h; $y++) {
      $row = unpack('N*', substr($px, $y * $w * 4, $w * 4));
      $mrow = ($y >> $bits) * $bw;
      for ($x = 0; $x < $w; $x++) {
        $e = $t['data'][$mrow + ($x >> $bits)];
        $p = $row[$x + 1];
        $g = $s8(($p >> 8) & 255);
        $r = ((($p >> 16) & 255) + (($s8($e & 255) * $g) >> 5)) & 255;
        $b = (($p & 255) + (($s8(($e >> 8) & 255) * $g) >> 5) + (($s8(($e >> 16) & 255) * $s8($r)) >> 5)) & 255;
        $row[$x + 1] = ($p & 0xff00ff00) | ($r << 16) | $b;
      }
      $out .= pack('N*', ...$row);
    }
    return $out;
  }

  private static function addGreen(string $px, int $w, int $h): string {
    $out = '';
    for ($y = 0; $y < $h; $y++) {
      $row = unpack('N*', substr($px, $y * $w * 4, $w * 4));
      foreach ($row as $i => $p) {
        $g = ($p >> 8) & 255;
        $row[$i] = ($p & 0xff00ff00) | (((($p >> 16) + $g) & 255) << 16) | ((($p & 255) + $g) & 255);
      }
      $out .= pack('N*', ...$row);
    }
    return $out;
  }

  private static function inversePalette(string $px, array $t, int $h, int $pw): string {
    $pal = $t['palette'];
    $bits = $t['bits'];
    $w = $t['w'];
    $out = '';
    if ($bits === 0) {
      for ($i = 2, $n = strlen($px); $i < $n; $i += 4) $out .= $pal[ord($px[$i])];
      return $out;
    }
    $ib = 8 >> $bits;
    $mask = (1 << $ib) - 1;
    $per = (1 << $bits) - 1;
    for ($y = 0; $y < $h; $y++) {
      $o = $y * $pw * 4 + 2;
      $g = 0;
      for ($x = 0; $x < $w; $x++) {
        if (($x & $per) === 0) $g = ord($px[$o + ($x >> $bits) * 4]);
        $out .= $pal[$g & $mask];
        $g >>= $ib;
      }
    }
    return $out;
  }

  //////// 書き出し

  /**
   * VP8Lチャンクの中身を作る
   *
   * @param array $px  ARGBの整数の配列（左上から行の順）
   */
  public function encode(array $px, int $w, int $h, bool $alpha): string {
    $this->out = '';
    $this->acc = $this->nb = 0;
    $this->put(0x2f, 8);
    $this->put($w - 1, 14);
    $this->put($h - 1, 14);
    $this->put($alpha ? 1 : 0, 1);
    $this->put(0, 3);
    $this->stream($px, $w, $h);
    return $this->flush();
  }

  /**
   * ヘッダーの無い画像（ALPHチャンク用）
   */
  public function encodeImage(array $px, int $w, int $h): string {
    $this->out = '';
    $this->acc = $this->nb = 0;
    $this->stream($px, $w, $h);
    return $this->flush();
  }

  private function put(int $v, int $n): void {
    $this->acc |= $v << $this->nb;
    $this->nb += $n;
    while ($this->nb >= 8) {
      $this->out .= chr($this->acc & 255);
      $this->acc >>= 8;
      $this->nb -= 8;
    }
  }

  private function flush(): string {
    if ($this->nb > 0) $this->out .= chr($this->acc & 255);
    $this->acc = $this->nb = 0;
    return $this->out;
  }

  private function stream(array $px, int $w, int $h): void {
    $colors = [];
    foreach ($px as $c) {
      $colors[$c] = true;
      if (count($colors) > 256) break;
    }
    if (count($colors) <= 256) {
      // パレット（色の番号を緑に入れ、少なければ1バイトに詰める）
      $pal = array_keys($colors);
      sort($pal);
      $n = count($pal);
      $index = array_flip($pal);
      $bits = $n <= 2 ? 3 : ($n <= 4 ? 2 : ($n <= 16 ? 1 : 0));
      $this->put(1, 1);
      $this->put(3, 2);
      $this->put($n - 1, 8);
      $delta = [$pal[0]];
      for ($i = 1; $i < $n; $i++) $delta[] = self::sub($pal[$i], $pal[$i - 1]);
      $this->entropy($delta, $n, 1, false);
      $pw = self::subSize($w, $bits);
      $per = 1 << $bits;
      $ib = 8 >> $bits;
      $packed = [];
      for ($y = 0; $y < $h; $y++) {
        $row = $y * $w;
        for ($xb = 0; $xb < $pw; $xb++) {
          $g = 0;
          for ($k = 0, $x = $xb * $per; $k < $per && $x < $w; $k++, $x++) $g |= $index[$px[$row + $x]] << ($k * $ib);
          $packed[] = $g << 8;
        }
      }
      $px = $packed;
      $w = $pw;
    } else {
      // 緑を引いてから予測
      $this->put(1, 1);
      $this->put(2, 2);
      foreach ($px as $i => $c) {
        $g = ($c >> 8) & 255;
        $px[$i] = ($c & 0xff00ff00) | (((($c >> 16) - $g) & 255) << 16) | ((($c & 255) - $g) & 255);
      }
      $bits = $w * $h > 65536 ? 5 : 4;
      [$modes, $px] = self::predictor($px, $w, $h, $bits);
      $this->put(1, 1);
      $this->put(0, 2);
      $this->put($bits - 2, 3);
      $this->entropy($modes, self::subSize($w, $bits), self::subSize($h, $bits), false);
    }
    $this->put(0, 1);
    $this->entropy($px, $w, $h, true);
  }

  /**
   * 予測の変換（ブロック毎に残差の小さいモードを選ぶ）
   *
   * @return array  [モードの画像, 残差]
   */
  private static function predictor(array $px, int $w, int $h, int $bits): array {
    $bw = self::subSize($w, $bits);
    $bh = self::subSize($h, $bits);
    $size = 1 << $bits;
    $modes = [];
    $res = $px;
    $cost = static function(int $d): int {
      $c = 0;
      for ($s = 0; $s < 32; $s += 8) {
        $v = ($d >> $s) & 255;
        $c += $v < 128 ? $v : 256 - $v;
      }
      return $c;
    };
    for ($by = 0; $by < $bh; $by++) {
      for ($bx = 0; $bx < $bw; $bx++) {
        $x0 = $bx * $size;
        $y0 = $by * $size;
        $x1 = min($w, $x0 + $size);
        $y1 = min($h, $y0 + $size);
        $best = 1;
        $bestCost = PHP_INT_MAX;
        foreach ([1, 2, 11, 12, 7, 13, 3, 4] as $m) {
          $c = 0;
          for ($y = max(1, $y0); $y < $y1 && $c < $bestCost; $y++) {
            $row = $y * $w;
            for ($x = max(1, $x0); $x < $x1; $x++) {
              $i = $row + $x;
              $c += $cost(self::sub($px[$i], self::predict($m, $px[$i - 1], $px[$i - $w], $x + 1 < $w ? $px[$i - $w + 1] : $px[$row], $px[$i - $w - 1])));
            }
          }
          if ($c < $bestCost) {
            $bestCost = $c;
            $best = $m;
          }
        }
        $modes[$by * $bw + $bx] = 0xff000000 | ($best << 8);
      }
    }
    $res[0] = self::sub($px[0], 0xff000000);
    for ($x = 1; $x < $w; $x++) $res[$x] = self::sub($px[$x], $px[$x - 1]);
    for ($y = 1; $y < $h; $y++) {
      $row = $y * $w;
      $res[$row] = self::sub($px[$row], $px[$row - $w]);
      $mrow = ($y >> $bits) * $bw;
      for ($x = 1; $x < $w; $x++) {
        $i = $row + $x;
        $m = ($modes[$mrow + ($x >> $bits)] >> 8) & 15;
        $res[$i] = self::sub($px[$i], self::predict($m, $px[$i - 1], $px[$i - $w], $x + 1 < $w ? $px[$i - $w + 1] : $px[$row], $px[$i - $w - 1]));
      }
    }
    return [$modes, $res];
  }

  /**
   * エントロピー符号化した画像を書く
   */
  private function entropy(array $px, int $w, int $h, bool $main): void {
    $tokens = self::lz77($px, $w);
    // カラーキャッシュの大きさは、見積もった大きさで選ぶ
    $best = null;
    foreach ($main ? [0, 6, 10] : [0] as $cacheBits) {
      $hist = self::histogram($px, $tokens, $w, $cacheBits);
      $size = 0;
      foreach ($hist as $hh) $size += self::entropyBits($hh);
      if ($best === null || $size < $best[0]) $best = [$size, $cacheBits, $hist];
    }
    [, $cacheBits, $hist] = $best;
    if ($cacheBits) {
      $this->put(1, 1);
      $this->put($cacheBits, 4);
    } else {
      $this->put(0, 1);
    }
    if ($main) $this->put(0, 1); // メタプレフィックス符号は使わない
    $codes = [];
    foreach ($hist as $hh) $codes[] = $this->writeCode($hh);
    [[$gc, $gl], [$rc, $rl], [$bc, $bl], [$ac, $al], [$dc, $dl]] = $codes;

    $cache = $cacheBits ? array_fill(0, 1 << $cacheBits, -1) : null;
    $shift = 32 - $cacheBits;
    $pos = 0;
    foreach ($tokens as $t) {
      if ($t >= 0) {
        if ($cache !== null) {
          $k = (($t * self::HASH) & 0xffffffff) >> $shift;
          if ($cache[$k] === $t) {
            $this->put($gc[280 + $k], $gl[280 + $k]);
            $pos++;
            continue;
          }
          $cache[$k] = $t;
        }
        $g = ($t >> 8) & 255;
        $r = ($t >> 16) & 255;
        $b = $t & 255;
        $a = ($t >> 24) & 255;
        $this->put($gc[$g], $gl[$g]);
        $this->put($rc[$r], $rl[$r]);
        $this->put($bc[$b], $bl[$b]);
        $this->put($ac[$a], $al[$a]);
        $pos++;
        continue;
      }
      $len = (-$t) >> 21;
      $dcode = (-$t) & 0x1fffff;
      [$p, $eb, $ev] = self::prefix($len);
      $this->put($gc[256 + $p], $gl[256 + $p]);
      if ($eb) $this->put($ev, $eb);
      [$p, $eb, $ev] = self::prefix($dcode);
      $this->put($dc[$p], $dl[$p]);
      if ($eb) $this->put($ev, $eb);
      if ($cache !== null) {
        for ($i = $pos; $i < $pos + $len; $i++) $cache[(($px[$i] * self::HASH) & 0xffffffff) >> $shift] = $px[$i];
      }
      $pos += $len;
    }
  }

  /**
   * 値をプレフィックス符号と追加ビットにする
   *
   * @return array  [符号, 追加ビット数, 追加ビット]
   */
  private static function prefix(int $v): array {
    $d = $v - 1;
    if ($d < 4) return [$d, 0, 0];
    $hb = strlen(decbin($d)) - 1;
    $s = ($d >> ($hb - 1)) & 1;
    return [2 * $hb + $s, $hb - 1, $d & ((1 << ($hb - 1)) - 1)];
  }

  /**
   * LZ77（同じ画素列の繰り返しを後方参照にする）
   *
   * @return array  画素（0以上）、又は-(長さ << 21 | 距離の符号)
   */
  private static function lz77(array $px, int $w): array {
    $n = count($px);
    $head = [];
    $chain = [];
    $tokens = [];
    $plane = [];
    foreach (self::PLANE as $i => [$xi, $yi]) $plane[$yi * 16 + 8 - $xi] = $i + 1;
    $insert = function(int $i) use (&$head, &$chain, $px, $n): void {
      if ($i + 1 >= $n) return;
      $k = ($px[$i] << 32) ^ $px[$i + 1];
      if (isset($head[$k])) $chain[$i] = $head[$k];
      $head[$k] = $i;
    };
    $i = 0;
    while ($i < $n) {
      $max = min(self::MAX_LENGTH, $n - $i);
      $best = 0;
      $bestDist = 0;
      if ($max >= 3) {
        // すぐ左とすぐ上を先に試す
        foreach ([1, $w] as $dist) {
          if ($dist > $i || $px[$i] !== $px[$i - $dist]) continue;
          $l = 1;
          while ($l < $max && $px[$i + $l] === $px[$i - $dist + $l]) $l++;
          if ($l > $best) {
            $best = $l;
            $bestDist = $dist;
          }
        }
        $k = ($px[$i] << 32) ^ $px[$i + 1];
        $c = $head[$k] ?? -1;
        for ($tries = 0; $c >= 0 && $tries < 16 && $best < $max && $i - $c <= self::MAX_DISTANCE; $tries++) {
          $l = 0;
          while ($l < $max && $px[$c + $l] === $px[$i + $l]) $l++;
          if ($l > $best) {
            $best = $l;
            $bestDist = $i - $c;
          }
          $c = $chain[$c] ?? -1;
        }
      }
      if ($best >= 3) {
        $yi = intdiv($bestDist, $w);
        $xi = $bestDist - $yi * $w;
        $code = $bestDist + 120;
        if ($xi <= 8 && $yi < 8 && isset($plane[$yi * 16 + 8 - $xi])) {
          $code = $plane[$yi * 16 + 8 - $xi];
        } else if ($w - $xi <= 7 && $yi + 1 < 8 && isset($plane[($yi + 1) * 16 + 8 + $w - $xi])) {
          $code = $plane[($yi + 1) * 16 + 8 + $w - $xi];
        }
        $tokens[] = -(($best << 21) | $code);
        for ($j = $i; $j < $i + $best; $j++) $insert($j);
        $i += $best;
      } else {
        $tokens[] = $px[$i];
        $insert($i);
        $i++;
      }
    }
    return $tokens;
  }

  /**
   * 5つの符号の記号の数（カラーキャッシュの当たりも数える）
   */
  private static function histogram(array $px, array $tokens, int $w, int $cacheBits): array {
    $g = array_fill(0, 280 + ($cacheBits ? 1 << $cacheBits : 0), 0);
    $r = $b = $a = array_fill(0, 256, 0);
    $d = array_fill(0, 40, 0);
    $cache = $cacheBits ? array_fill(0, 1 << $cacheBits, -1) : null;
    $shift = 32 - $cacheBits;
    $pos = 0;
    foreach ($tokens as $t) {
      if ($t >= 0) {
        if ($cache !== null) {
          $k = (($t * self::HASH) & 0xffffffff) >> $shift;
          if ($cache[$k] === $t) {
            $g[280 + $k]++;
            $pos++;
            continue;
          }
          $cache[$k] = $t;
        }
        $g[($t >> 8) & 255]++;
        $r[($t >> 16) & 255]++;
        $b[$t & 255]++;
        $a[($t >> 24) & 255]++;
        $pos++;
        continue;
      }
      $len = (-$t) >> 21;
      $g[256 + self::prefix($len)[0]]++;
      $d[self::prefix((-$t) & 0x1fffff)[0]]++;
      if ($cache !== null) {
        for ($i = $pos; $i < $pos + $len; $i++) $cache[(($px[$i] * self::HASH) & 0xffffffff) >> $shift] = $px[$i];
      }
      $pos += $len;
    }
    return [$g, $r, $b, $a, $d];
  }

  /** 記号の数から見積もった符号の大きさ（ビット） */
  private static function entropyBits(array $hist): float {
    $total = array_sum($hist);
    if ($total === 0) return 0.0;
    $bits = 0.0;
    $used = 0;
    foreach ($hist as $c) {
      if ($c === 0) continue;
      $bits -= $c * log($c / $total, 2);
      $used++;
    }
    // 符号長の分も大体足す
    return $bits + $used * 4;
  }

  /**
   * プレフィックス符号を書く
   *
   * @return array  [記号 => 反転した符号, 記号 => 長さ]
   */
  private function writeCode(array $hist): array {
    $used = [];
    foreach ($hist as $s => $c) if ($c > 0) $used[] = $s;
    $len = array_fill(0, count($hist), 0);
    if (count($used) <= 2 && ($used[1] ?? $used[0] ?? 0) < 256) {
      // 簡単な符号
      $syms = $used ?: [0];
      $this->put(1, 1);
      $this->put(count($syms) - 1, 1);
      if ($syms[0] < 2) {
        $this->put(0, 1);
        $this->put($syms[0], 1);
      } else {
        $this->put(1, 1);
        $this->put($syms[0], 8);
      }
      if (count($syms) === 2) {
        $this->put($syms[1], 8);
        $len[$syms[0]] = $len[$syms[1]] = 1;
      }
      return self::canonical($len);
    }
    $this->put(0, 1);
    if (count($used) === 1) {
      // 1つだけの記号は0ビット
      $len[$used[0]] = 1;
      $this->writeLengths($len);
      $len[$used[0]] = 0;
      return self::canonical($len);
    }
    $len = self::lengths($hist, 15);
    $this->writeLengths($len);
    return self::canonical($len);
  }

  private function writeLengths(array $len): void {
    // 連長圧縮（16：前の長さを3～6回、17：0を3～10回、18：0を11～138回）
    $tokens = [];
    $n = count($len);
    $prev = 8;
    for ($i = 0; $i < $n;) {
      $v = $len[$i];
      $run = 1;
      while ($i + $run < $n && $len[$i + $run] === $v) $run++;
      $i += $run;
      if ($v === 0) {
        while ($run >= 11) {
          $r = min($run, 138);
          $tokens[] = [18, 7, $r - 11];
          $run -= $r;
        }
        if ($run >= 3) {
          $tokens[] = [17, 3, $run - 3];
          $run = 0;
        }
        for (; $run > 0; $run--) $tokens[] = [0, 0, 0];
        continue;
      }
      if ($v !== $prev) {
        $tokens[] = [$v, 0, 0];
        $prev = $v;
        $run--;
      }
      while ($run >= 3) {
        $r = min($run, 6);
        $tokens[] = [16, 2, $r - 3];
        $run -= $r;
      }
      for (; $run > 0; $run--) $tokens[] = [$v, 0, 0];
    }
    $hist = array_fill(0, 19, 0);
    foreach ($tokens as [$s]) $hist[$s]++;
    $used = array_keys(array_filter($hist));
    if (count($used) === 1) {
      $cl = array_fill(0, 19, 0);
      $cl[$used[0]] = 1;
    } else {
      $cl = self::lengths($hist, 7);
    }
    $num = 19;
    while ($num > 4 && $cl[self::ORDER[$num - 1]] === 0) $num--;
    $this->put($num - 4, 4);
    for ($i = 0; $i < $num; $i++) $this->put($cl[self::ORDER[$i]], 3);
    $this->put(0, 1); // 全ての記号の長さを書く
    if (count($used) === 1) $cl[$used[0]] = 0;
    [$codes, $cl] = self::canonical($cl);
    foreach ($tokens as [$s, $eb, $ev]) {
      $this->put($codes[$s], $cl[$s]);
      if ($eb) $this->put($ev, $eb);
    }
  }

  /**
   * 長さの制限付きのハフマン符号長（制限を超えたら、少ない記号の数を底上げしてやり直す）
   */
  private static function lengths(array $hist, int $limit): array {
    $len = array_fill(0, count($hist), 0);
    for ($min = 1; ; $min *= 2) {
      $leaves = [];
      foreach ($hist as $s => $c) if ($c > 0) $leaves[] = [max($c, $min), $s];
      usort($leaves, fn($a, $b) => $a[0] <=> $b[0] ?: $a[1] <=> $b[1]);
      $m = count($leaves);
      $freq = array_column($leaves, 0);
      $parent = [];
      $li = 0;
      $ni = $m;
      for ($next = $m; $next < 2 * $m - 1; $next++) {
        $pick = [];
        for ($k = 0; $k < 2; $k++) {
          if ($li < $m && ($ni >= $next || $freq[$li] <= $freq[$ni])) $pick[] = $li++;
          else $pick[] = $ni++;
        }
        $freq[$next] = $freq[$pick[0]] + $freq[$pick[1]];
        $parent[$pick[0]] = $parent[$pick[1]] = $next;
      }
      $depth = [2 * $m - 2 => 0];
      for ($i = 2 * $m - 3; $i >= 0; $i--) $depth[$i] = $depth[$parent[$i]] + 1;
      $max = 0;
      for ($i = 0; $i < $m; $i++) $max = max($max, $depth[$i]);
      if ($max <= $limit) {
        for ($i = 0; $i < $m; $i++) $len[$leaves[$i][1]] = $depth[$i];
        return $len;
      }
    }
  }

  /**
   * 符号長から符号を作る（書く時は下位ビットからなので反転する）
   */
  private static function canonical(array $len): array {
    $count = array_fill(0, 16, 0);
    foreach ($len as $l) if ($l) $count[$l]++;
    $next = [];
    $code = 0;
    for ($l = 1; $l < 16; $l++) {
      $code = ($code + $count[$l - 1]) << 1;
      $next[$l] = $code;
    }
    $codes = array_fill(0, count($len), 0);
    foreach ($len as $s => $l) {
      if (!$l) continue;
      $c = $next[$l]++;
      $r = 0;
      for ($i = 0; $i < $l; $i++) $r |= (($c >> $i) & 1) << ($l - 1 - $i);
      $codes[$s] = $r;
    }
    return [$codes, $len];
  }
}