<?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;

/**
 * GIF（87a・89a）
 *
 * 読み込み：LZW（12ビット、クリア、遅延クリア）、インターレース、全体・ローカルのパレット、透明色、
 * アニメーション（グラフィック制御拡張の遅延・廃棄方法、NETSCAPE2.0の繰り返し回数）。
 * 書き出し：256色以下はそのまま、それ以上はメディアンカットで減色（任意で誤差拡散）。framesがあればアニメーション。
 */
class Gif implements ImageInterface {
  public function parse(string $file): \stdClass {
    $d = (string)file_get_contents($file);
    $s = $this->scan($d, false);
    $first = $s['images'][0] ?? null;
    return (object)[
      'version' => substr($d, 3, 3),
      'width' => $s['width'],
      'height' => $s['height'],
      'bitDepth' => $s['depth'],
      'numColors' => 1 << $s['depth'],
      'globalColors' => strlen($s['gct']) / 3,
      'bgColor' => $s['bg'],
      'frames' => count($s['images']),
      'loops' => $s['loops'],
      'delayTime' => $first ? $first['delay'] / 100.0 : 0,
      'hasAlpha' => $first !== null && $first['transparent'] !== null,
      'interlace' => $first !== null && $first['interlace'],
      'compression' => 'LZW',
    ];
  }

  /**
   * ブロックを読む
   *
   * @param bool $decode  画像のLZWを展開するか（falseなら大きさ等だけ）
   */
  private function scan(string $d, bool $decode): array {
    $v = substr($d, 0, 6);
    if ($v !== 'GIF87a' && $v !== 'GIF89a') throw new \RuntimeException('GIFではありません。');
    if (strlen($d) < 13) throw new \RuntimeException('GIFのヘッダーが途中で切れています。');
    $h = unpack('vw/vh/Cflags/Cbg/Caspect', substr($d, 6, 7));
    Bitmap::check($h['w'], $h['h']);
    $pos = 13;
    $gct = '';
    if ($h['flags'] & 0x80) {
      $gct = substr($d, $pos, 3 << (($h['flags'] & 7) + 1));
      $pos += strlen($gct);
    }
    $len = strlen($d);
    $images = [];
    $gce = null;
    $loops = 1; // NETSCAPE2.0が無ければ1回
    while ($pos < $len) {
      $b = ord($d[$pos++]);
      if ($b === 0x3b) break;
      if ($b === 0x21) {
        $label = ord($d[$pos++] ?? "\0");
        [$data, $pos] = $this->subBlocks($d, $pos);
        if ($label === 0xf9 && strlen($data) >= 4) {
          $g = unpack('Cflags/vdelay/Ctrans', $data);
          $gce = ['dispose' => ($g['flags'] >> 2) & 7, 'delay' => $g['delay'], 'transparent' => $g['flags'] & 1 ? $g['trans'] : null];
        } else if ($label === 0xff && (str_starts_with($data, 'NETSCAPE2.0') || str_starts_with($data, 'ANIMEXTS1.0')) && strlen($data) >= 14 && ord($data[11]) === 1) {
          // 繰り返し回数（0 = 無限）。ブラウザと同じく、最初の再生に加えてn回
          $n = unpack('v', substr($data, 12, 2))[1];
          $loops = $n === 0 ? 0 : $n + 1;
        }
        continue;
      }
      if ($b !== 0x2c) {
        // 不明なブロック：ブラウザと同じく、そこで終わりにする
        break;
      }
      if ($pos + 9 > $len) throw new \RuntimeException('GIFの画像記述子が途中で切れています。');
      $im = unpack('vx/vy/vw/vh/Cflags', substr($d, $pos, 9));
      $pos += 9;
      $lct = '';
      if ($im['flags'] & 0x80) {
        $lct = substr($d, $pos, 3 << (($im['flags'] & 7) + 1));
        $pos += strlen($lct);
      }
      $min = ord($d[$pos++] ?? "\0");
      [$data, $pos] = $this->subBlocks($d, $pos);
      $images[] = [
        'x' => $im['x'], 'y' => $im['y'], 'w' => $im['w'], 'h' => $im['h'],
        'interlace' => ($im['flags'] & 0x40) !== 0,
        'palette' => $lct !== '' ? $lct : $gct,
        'indices' => $decode ? $this->unlzw($data, $min, $im['w'] * $im['h']) : '',
        'dispose' => $gce['dispose'] ?? 0,
        'delay' => $gce['delay'] ?? 0,
        'transparent' => $gce['transparent'] ?? null,
      ];
      $gce = null;
    }
    if (!$images) throw new \RuntimeException('GIFに画像がありません。');
    return ['width' => $h['w'], 'height' => $h['h'], 'gct' => $gct, 'bg' => $h['bg'], 'depth' => (($h['flags'] >> 4) & 7) + 1, 'images' => $images, 'loops' => $loops];
  }

  /** データのサブブロック（長さ＋データ、長さ0で終わり）を繋げる */
  private function subBlocks(string $d, int $pos): array {
    $out = '';
    $len = strlen($d);
    while ($pos < $len) {
      $n = ord($d[$pos++]);
      if ($n === 0) break;
      $out .= substr($d, $pos, $n);
      $pos += $n;
    }
    return [$out, $pos];
  }

  /**
   * LZWを展開する
   *
   * @return string  パレットの指標（1画素1バイト）
   */
  private function unlzw(string $data, int $min, int $count): string {
    if ($min < 2 || $min > 8) throw new \RuntimeException('GIFのLZWの最小符号長が不正です。');
    $clear = 1 << $min;
    $eoi = $clear + 1;
    $base = [];
    for ($i = 0; $i < $clear; $i++) $base[] = chr($i);
    $base[] = '';
    $base[] = '';
    $dict = $base;
    $size = $min + 1;
    $mask = (1 << $size) - 1;
    $out = '';
    $outLen = 0;
    $prev = null;
    $buf = $bits = $pos = 0;
    $len = strlen($data);
    while ($outLen < $count) {
      while ($bits < $size) {
        if ($pos >= $len) break 2;
        $buf |= ord($data[$pos++]) << $bits;
        $bits += 8;
      }
      $code = $buf & $mask;
      $buf >>= $size;
      $bits -= $size;

      if ($code === $clear) {
        $dict = $base;
        $size = $min + 1;
        $mask = (1 << $size) - 1;
        $prev = null;
        continue;
      }
      if ($code === $eoi) break;
      $n = count($dict);
      if ($code < $n && $code !== $clear && $code !== $eoi) {
        $entry = $dict[$code];
      } else if ($code === $n && $prev !== null) {
        $entry = $prev.$prev[0];
      } else {
        // 壊れたデータ：ブラウザと同じく、そこまでを表示する
        break;
      }
      $out .= $entry;
      $outLen += strlen($entry);
      if ($prev !== null && $n < 4096) {
        $dict[] = $prev.$entry[0];
        if ($n + 1 >= (1 << $size) && $size < 12) {
          $size++;
          $mask = (1 << $size) - 1;
        }
      }
      $prev = $entry;
    }
    return $outLen >= $count ? substr($out, 0, $count) : $out;
  }

  public function decode(string $data): Bitmap {
    $s = $this->scan($data, true);
    $w = $s['width'];
    $h = $s['height'];
    $canvas = new Bitmap($w, $h);
    $img = null;
    foreach ($s['images'] as $f) {
      $frame = $this->frame($f);
      $prevCanvas = $f['dispose'] === 3 ? $canvas->copy() : null;
      $canvas->draw($frame, $f['x'], $f['y'], true);
      if ($img === null) $img = $canvas->copy();
      $img->frames[] = ['bitmap' => $canvas->copy(), 'delay' => $f['delay'] * 10];
      // 廃棄方法：2 = 背景に戻す（ブラウザと同じく透明）、3 = 前に戻す
      if ($f['dispose'] === 2) $canvas->clear($f['x'], $f['y'], $f['w'], $f['h']);
      else if ($f['dispose'] === 3) $canvas = $prevCanvas;
    }
    if (count($img->frames) < 2) {
      $img->frames = [];
    } else {
      $img->loops = $s['loops'];
    }
    return $img;
  }

  /**
   * 1枚の画像をRGBAにする（透明色は透明、足りない画素も透明）
   */
  private function frame(array $f): Bitmap {
    $lut = [];
    $pal = $f['palette'];
    $n = intdiv(strlen($pal), 3);
    for ($i = 0; $i < 256; $i++) {
      $lut[chr($i)] = $i === $f['transparent'] ? "\0\0\0\0" : ($i < $n ? substr($pal, $i * 3, 3)."\xff" : "\0\0\0\xff");
    }
    $count = $f['w'] * $f['h'];
    $px = strtr($f['indices'], $lut);
    if (strlen($px) < $count * 4) $px .= str_repeat("\0\0\0\0", $count - intdiv(strlen($px), 4));
    $rows = str_split($px, $f['w'] * 4);
    if ($f['interlace']) {
      // 行の順：8行毎（0から）、8行毎（4から）、4行毎（2から）、2行毎（1から）
      $order = [];
      foreach ([[0, 8], [4, 8], [2, 4], [1, 2]] as [$start, $step]) for ($y = $start; $y < $f['h']; $y += $step) $order[] = $y;
      $sorted = array_fill(0, $f['h'], '');
      foreach ($order as $i => $y) $sorted[$y] = $rows[$i];
      $rows = $sorted;
    }
    return new Bitmap($f['w'], $f['h'], implode('', $rows));
  }

  /**
   * 画素をGIFにする
   *
   * 透明（アルファ128未満）は1つの透明色にする。framesがあればアニメーション（全体のパレットを共有）。
   *
   * @param array $opt  dither：256色を超える場合に誤差拡散を使う（既定false）
   */
  public function encode(Bitmap $img, array $opt = []): string {
    $images = $img->frames ? array_column($img->frames, 'bitmap') : [$img];
    $w = $img->width;
    $h = $img->height;

    // 色を数える（透明は1色）
    $colors = [];
    $hasAlpha = false;
    foreach ($images as $f) {
      if ($f->width !== $w || $f->height !== $h) throw new \InvalidArgumentException('フレームの大きさが画像と違います。');
      for ($i = 0, $n = strlen($f->data); $i < $n && count($colors) <= 256; $i += 4) {
        if (ord($f->data[$i + 3]) < 128) {
          $hasAlpha = true;
        } else {
          $colors[substr($f->data, $i, 3)] = true;
        }
      }
    }
    $max = $hasAlpha ? 255 : 256;
    $exact = count($colors) <= $max;
    $palette = $exact ? array_keys($colors) : $this->medianCut($images, $max);
    if (!$palette) $palette = ["\0\0\0"];
    $trans = $hasAlpha ? count($palette) : null;
    if ($hasAlpha) $palette[] = "\0\0\0";

    $bits = 1;
    while ((1 << $bits) < count($palette)) $bits++;
    $gct = str_pad(implode('', $palette), 3 << $bits, "\0");
    $min = max(2, $bits);

    $out = 'GIF89a'.pack('vvCCC', $w, $h, 0x80 | 0x70 | ($bits - 1), 0, 0).$gct;
    if ($img->frames && $img->loops !== 1) {
      $out .= "\x21\xff\x0bNETSCAPE2.0\x03\x01".pack('v', $img->loops === 0 ? 0 : min(65535, $img->loops - 1))."\0";
    }
    $index = $exact ? array_flip($palette) : null;
    foreach ($images as $i => $f) {
      $idx = $exact ? $this->mapExact($f, $index, $trans) : $this->mapNearest($f, $palette, $trans, (bool)($opt['dither'] ?? false));
      $delay = $img->frames ? (int)round($img->frames[$i]['delay'] / 10) : 0;
      // 透明があるフレームは、次のフレームの前に消す（前のフレームが透けない様に）
      $dispose = $img->frames ? ($hasAlpha ? 2 : 1) : 0;
      if ($img->frames || $hasAlpha) {
        $out .= "\x21\xf9\x04".chr(($dispose << 2) | ($hasAlpha ? 1 : 0)).pack('v', min(65535, $delay)).chr($trans ?? 0)."\0";
      }
      $out .= "\x2c".pack('vvvvC', 0, 0, $w, $h, 0).chr($min);
      foreach (str_split($this->lzw($idx, $min), 255) as $block) $out .= chr(strlen($block)).$block;
      $out .= "\0";
    }
    return $out."\x3b";
  }

  private function mapExact(Bitmap $f, array $index, ?int $trans): string {
    $out = '';
    for ($i = 0, $n = strlen($f->data); $i < $n; $i += 4) {
      $out .= ord($f->data[$i + 3]) < 128 ? chr($trans) : chr($index[substr($f->data, $i, 3)]);
    }
    return $out;
  }

  /**
   * 一番近い色にする（5ビット毎にまとめた色で探した結果を覚えておく）
   */
  private function mapNearest(Bitmap $f, array $palette, ?int $trans, bool $dither): string {
    $pal = array_map(fn($c) => [ord($c[0]), ord($c[1]), ord($c[2])], $palette);
    if ($trans !== null) array_pop($pal);
    $cache = [];
    $nearest = function(int $r, int $g, int $b) use ($pal, &$cache): int {
      $key = (($r >> 3) << 10) | (($g >> 3) << 5) | ($b >> 3);
      if (isset($cache[$key])) return $cache[$key];
      $best = 0;
      $bd = PHP_INT_MAX;
      foreach ($pal as $i => [$pr, $pg, $pb]) {
        $dr = $pr - $r;
        $dg = $pg - $g;
        $db = $pb - $b;
        $d = 2 * $dr * $dr + 4 * $dg * $dg + 3 * $db * $db;
        if ($d < $bd) {
          $bd = $d;
          $best = $i;
        }
      }
      return $cache[$key] = $best;
    };
    $w = $f->width;
    $out = '';
    $err = $dither ? [array_fill(0, $w * 3 + 6, 0), array_fill(0, $w * 3 + 6, 0)] : null;
    for ($y = 0; $y < $f->height; $y++) {
      $row = $f->row($y);
      if ($dither) {
        $cur = $err[0];
        $next = array_fill(0, $w * 3 + 6, 0);
      }
      for ($x = 0; $x < $w; $x++) {
        $o = $x * 4;
        if (ord($row[$o + 3]) < 128) {
          $out .= chr($trans);
          continue;
        }
        $c = [ord($row[$o]), ord($row[$o + 1]), ord($row[$o + 2])];
        if ($dither) for ($k = 0; $k < 3; $k++) $c[$k] = max(0, min(255, $c[$k] + intdiv($cur[3 + $x * 3 + $k], 16)));
        $i = $nearest($c[0], $c[1], $c[2]);
        $out .= chr($i);
        if ($dither) {
          // Floyd–Steinberg：右7、左下3、下5、右下1
          for ($k = 0; $k < 3; $k++) {
            $e = $c[$k] - $pal[$i][$k];
            $cur[3 + ($x + 1) * 3 + $k] += $e * 7;
            $next[3 + ($x - 1) * 3 + $k] += $e * 3;
            $next[3 + $x * 3 + $k] += $e * 5;
            $next[3 + ($x + 1) * 3 + $k] += $e;
          }
        }
      }
      if ($dither) $err[0] = $next;
    }
    return $out;
  }

  /**
   * メディアンカットで減色する
   *
   * @return array  色（3バイトの文字列）
   */
  private function medianCut(array $images, int $max): array {
    // 多過ぎる場合は間引く
    $total = 0;
    foreach ($images as $f) $total += $f->width * $f->height;
    $step = max(1, intdiv($total, 200000));
    $px = [];
    $k = 0;
    foreach ($images as $f) {
      for ($i = 0, $n = strlen($f->data); $i < $n; $i += 4) {
        if ($k++ % $step || ord($f->data[$i + 3]) < 128) continue;
        $px[] = (ord($f->data[$i]) << 16) | (ord($f->data[$i + 1]) << 8) | ord($f->data[$i + 2]);
      }
    }
    if (!$px) return [];
    // 箱：[色, 一番広い色の軸, 分ける優先度]（範囲は箱を作る時に1回だけ計算する）
    $measure = function(array $box): array {
      $best = -1;
      $ch = 0;
      foreach ([16, 8, 0] as $sh) {
        $lo = 255;
        $hi = 0;
        foreach ($box as $c) {
          $v = ($c >> $sh) & 255;
          if ($v < $lo) $lo = $v;
          if ($v > $hi) $hi = $v;
        }
        if ($hi - $lo > $best) {
          $best = $hi - $lo;
          $ch = $sh;
        }
      }
      return [$box, $ch, count($box) > 1 ? $best * count($box) : 0];
    };
    $boxes = [$measure($px)];
    while (count($boxes) < $max) {
      $bi = -1;
      $top = 0;
      foreach ($boxes as $i => [, , $score]) {
        if ($score > $top) {
          $top = $score;
          $bi = $i;
        }
      }
      if ($bi < 0) break;
      [$box, $ch] = $boxes[$bi];
      // 1つの軸（8ビット）で並べる：数え上げソート
      $buckets = array_fill(0, 256, []);
      foreach ($box as $c) $buckets[($c >> $ch) & 255][] = $c;
      $box = array_merge(...$buckets);
      $mid = intdiv(count($box), 2);
      array_splice($boxes, $bi, 1, [$measure(array_slice($box, 0, $mid)), $measure(array_slice($box, $mid))]);
    }
    $boxes = array_column($boxes, 0);
    return array_map(function($box) {
      $r = $g = $b = 0;
      foreach ($box as $c) {
        $r += ($c >> 16) & 255;
        $g += ($c >> 8) & 255;
        $b += $c & 255;
      }
      $n = count($box);
      return chr(intdiv($r + ($n >> 1), $n)).chr(intdiv($g + ($n >> 1), $n)).chr(intdiv($b + ($n >> 1), $n));
    }, $boxes);
  }

  /**
   * LZWで圧縮する
   */
  private function lzw(string $idx, int $min): string {
    $clear = 1 << $min;
    $eoi = $clear + 1;
    $size = $min + 1;
    $next = $clear + 2;
    $dict = [];
    $out = '';
    $buf = $bits = 0;
    $emit = function(int $code) use (&$buf, &$bits, &$out, &$size): void {
      $buf |= $code << $bits;
      $bits += $size;
      while ($bits >= 8) {
        $out .= chr($buf & 255);
        $buf >>= 8;
        $bits -= 8;
      }
    };
    $emit($clear);
    $n = strlen($idx);
    if ($n === 0) {
      $emit($eoi);
      return $out.($bits > 0 ? chr($buf & 255) : '');
    }
    $w = $idx[0];
    for ($i = 1; $i < $n; $i++) {
      $c = $idx[$i];
      $wc = $w.$c;
      if (isset($dict[$wc])) {
        $w = $wc;
        continue;
      }
      $emit(strlen($w) === 1 ? ord($w) : $dict[$w]);
      if ($next < 4096) {
        $dict[$wc] = $next++;
        if ($next > (1 << $size) && $size < 12) $size++;
      } else {
        // 辞書が一杯：クリアして最初から
        $emit($clear);
        $dict = [];
        $size = $min + 1;
        $next = $clear + 2;
      }
      $w = $c;
    }
    $emit(strlen($w) === 1 ? ord($w) : $dict[$w]);
    $emit($eoi);
    return $out.($bits > 0 ? chr($buf & 255) : '');
  }
}