| 1 | <?php |
| 2 | /************************************************************* |
| 3 | # 076 License |
| 4 | |
| 5 | Copyright (c) テクニカル諏訪子 |
| 6 | |
| 7 | Permission is hereby granted to any person obtaining a copy of the software |
| 8 | Little Beast (the "Software") to use, modify, merge, copy, publish, distribute, |
| 9 | sublicense, and/or sell copies of the Software, subject to the following conditions: |
| 10 | |
| 11 | 1. **Origin Attribution**: |
| 12 | - You must not misrepresent the origin of the Software; you must not claim |
| 13 | you created the original Software. |
| 14 | - If the Software is used in a product, you must either: |
| 15 | a. Provide clear attribution in the product's documentation, user interface, |
| 16 | or other visible areas, **OR** |
| 17 | b. Pay the original developers a fee they specify in writing. |
| 18 | 2. **Usage Restriction**: |
| 19 | - The Software, or any derivative works, dependencies, or libraries |
| 20 | incorporating it, must not be used for censorship or to suppress freedom of |
| 21 | speech, expression, or creativity. Prohibited uses include, but are not |
| 22 | limited to: |
| 23 | - Censorship of so-called "hate speech", visuals, non-mainstream opinions, |
| 24 | ideas, or objective reality. |
| 25 | - Tools or systems designed to restrict access to information or |
| 26 | artistic works. |
| 27 | 3. **Notice Preservation**: |
| 28 | - This license and the above copyright notice must remain intact in all copies |
| 29 | of the source code. |
| 30 | |
| 31 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, |
| 32 | INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A |
| 33 | PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
| 34 | HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF |
| 35 | CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE |
| 36 | OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| 37 | */ |
| 38 | namespace Std\Lib\Image; |
| 39 | |
| 40 | /** |
| 41 | * WebPの可逆圧縮（VP8L） |
| 42 | * |
| 43 | * 読み込み：全ての変換（予測、色、緑を引く、パレット）、カラーキャッシュ、メタプレフィックス符号、後方参照。 |
| 44 | * 書き出し：256色以下はパレット（少なければ画素を詰める）、それ以外は緑を引く＋予測、LZ77とカラーキャッシュ、ハフマン符号。 |
| 45 | * 画素は内部ではARGBの整数（又はその4バイトの列、ビッグエンディアン）。 |
| 46 | */ |
| 47 | final class Vp8l { |
| 48 | private const ORDER = [17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]; |
| 49 | /** 距離の符号1～120の(x, y)のずれ */ |
| 50 | private const PLANE = [ |
| 51 | [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], |
| 52 | [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], |
| 53 | [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], |
| 54 | [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], |
| 55 | [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], |
| 56 | [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], |
| 57 | [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], |
| 58 | [-6, 7], [7, 6], [-7, 6], [8, 5], [7, 7], [-7, 7], [8, 6], [8, 7], |
| 59 | ]; |
| 60 | private const HASH = 0x1e35a7bd; |
| 61 | private const MAX_LENGTH = 4096; |
| 62 | private const MAX_DISTANCE = 1048576; |
| 63 | |
| 64 | private string $d = ''; |
| 65 | private int $p = 0; |
| 66 | private int $buf = 0; |
| 67 | private int $bits = 0; |
| 68 | |
| 69 | private string $out = ''; |
| 70 | private int $acc = 0; |
| 71 | private int $nb = 0; |
| 72 | |
| 73 | //////// 読み込み |
| 74 | |
| 75 | /** |
| 76 | * VP8Lチャンクの中身を読む |
| 77 | * |
| 78 | * @return array [幅, 丈, ARGBの列] |
| 79 | */ |
| 80 | public function decode(string $data): array { |
| 81 | if (strlen($data) < 5 || $data[0] !== "\x2f") throw new \RuntimeException('VP8Lの印がありません。'); |
| 82 | $this->start($data, 1); |
| 83 | $w = $this->read(14) + 1; |
| 84 | $h = $this->read(14) + 1; |
| 85 | $this->read(1); // アルファを使うか（参考だけ） |
| 86 | if ($this->read(3) !== 0) throw new \RuntimeException('未対応のVP8Lの版です。'); |
| 87 | Bitmap::check($w, $h); |
| 88 | return [$w, $h, $this->imageStream($w, $h)]; |
| 89 | } |
| 90 | |
| 91 | /** |
| 92 | * ヘッダーの無い画像（ALPHチャンクの中身）を読む |
| 93 | */ |
| 94 | public function decodeImage(string $data, int $w, int $h): string { |
| 95 | $this->start($data, 0); |
| 96 | return $this->imageStream($w, $h); |
| 97 | } |
| 98 | |
| 99 | private function start(string $data, int $pos): void { |
| 100 | $this->d = $data; |
| 101 | $this->p = $pos; |
| 102 | $this->buf = $this->bits = 0; |
| 103 | } |
| 104 | |
| 105 | private function read(int $n): int { |
| 106 | while ($this->bits < $n) { |
| 107 | $this->buf |= ord($this->d[$this->p++] ?? "\0") << $this->bits; |
| 108 | $this->bits += 8; |
| 109 | } |
| 110 | $v = $this->buf & ((1 << $n) - 1); |
| 111 | $this->buf >>= $n; |
| 112 | $this->bits -= $n; |
| 113 | return $v; |
| 114 | } |
| 115 | |
| 116 | private function imageStream(int $w, int $h): string { |
| 117 | $transforms = []; |
| 118 | $xsize = $w; |
| 119 | while ($this->read(1)) { |
| 120 | $type = $this->read(2); |
| 121 | if (isset($transforms[$type])) throw new \RuntimeException('VP8Lの変換が重複しています。'); |
| 122 | $t = ['type' => $type, 'w' => $xsize]; |
| 123 | if ($type === 0 || $type === 1) { |
| 124 | $t['bits'] = $this->read(3) + 2; |
| 125 | $t['bw'] = self::subSize($xsize, $t['bits']); |
| 126 | $t['data'] = $this->subImage($t['bw'], self::subSize($h, $t['bits'])); |
| 127 | } else if ($type === 3) { |
| 128 | $n = $this->read(8) + 1; |
| 129 | $pal = $this->subImage($n, 1); |
| 130 | for ($i = 1; $i < $n; $i++) $pal[$i] = self::add($pal[$i], $pal[$i - 1]); |
| 131 | // 範囲外の番号は透明な黒 |
| 132 | $t['palette'] = array_pad(array_map(fn($c) => pack('N', $c), $pal), 256, "\0\0\0\0"); |
| 133 | $t['bits'] = $n <= 2 ? 3 : ($n <= 4 ? 2 : ($n <= 16 ? 1 : 0)); |
| 134 | $xsize = self::subSize($xsize, $t['bits']); |
| 135 | } |
| 136 | $transforms[$type] = $t; |
| 137 | } |
| 138 | $px = $this->entropyImage($xsize, $h, true); |
| 139 | foreach (array_reverse($transforms, true) as $type => $t) { |
| 140 | $px = match ($type) { |
| 141 | 0 => self::inversePredictor($px, $t, $h), |
| 142 | 1 => self::inverseColor($px, $t, $h), |
| 143 | 2 => self::addGreen($px, $t['w'], $h), |
| 144 | 3 => self::inversePalette($px, $t, $h, $xsize), |
| 145 | }; |
| 146 | if ($type === 3) $xsize = $t['w']; |
| 147 | } |
| 148 | return $px; |
| 149 | } |
| 150 | |
| 151 | private static function subSize(int $size, int $bits): int { |
| 152 | return ($size + (1 << $bits) - 1) >> $bits; |
| 153 | } |
| 154 | |
| 155 | /** 変換用の小さい画像（ARGBの整数の配列） */ |
| 156 | private function subImage(int $w, int $h): array { |
| 157 | return array_values(unpack('N*', $this->entropyImage($w, $h, false))); |
| 158 | } |
| 159 | |
| 160 | /** |
| 161 | * エントロピー符号化した画像 |
| 162 | * |
| 163 | * @param bool $main 主画像（メタプレフィックス符号を使える） |
| 164 | */ |
| 165 | private function entropyImage(int $w, int $h, bool $main): string { |
| 166 | $cacheBits = 0; |
| 167 | if ($this->read(1)) { |
| 168 | $cacheBits = $this->read(4); |
| 169 | if ($cacheBits < 1 || $cacheBits > 11) throw new \RuntimeException('VP8Lのカラーキャッシュが不正です。'); |
| 170 | } |
| 171 | $meta = null; |
| 172 | $metaBits = 0; |
| 173 | $metaW = 0; |
| 174 | $groups = 1; |
| 175 | if ($main && $this->read(1)) { |
| 176 | $metaBits = $this->read(3) + 2; |
| 177 | $metaW = self::subSize($w, $metaBits); |
| 178 | $meta = $this->subImage($metaW, self::subSize($h, $metaBits)); |
| 179 | foreach ($meta as $i => $v) $meta[$i] = ($v >> 8) & 0xffff; |
| 180 | $groups = max($meta) + 1; |
| 181 | } |
| 182 | $cacheSize = $cacheBits ? 1 << $cacheBits : 0; |
| 183 | $codes = []; |
| 184 | for ($g = 0; $g < $groups; $g++) { |
| 185 | $codes[] = [$this->readCode(280 + $cacheSize), $this->readCode(256), $this->readCode(256), $this->readCode(256), $this->readCode(40)]; |
| 186 | } |
| 187 | |
| 188 | $total = $w * $h; |
| 189 | $px = ''; |
| 190 | $cache = $cacheSize ? array_fill(0, $cacheSize, 0) : null; |
| 191 | $shift = 32 - $cacheBits; |
| 192 | $pos = $x = $y = 0; |
| 193 | $mask = (1 << $metaBits) - 1; |
| 194 | [$G, $R, $B, $A, $D] = $codes[0]; |
| 195 | while ($pos < $total) { |
| 196 | if ($meta !== null && ($x & $mask) === 0) [$G, $R, $B, $A, $D] = $codes[$meta[($y >> $metaBits) * $metaW + ($x >> $metaBits)]]; |
| 197 | $s = $this->sym($G); |
| 198 | if ($s < 256) { |
| 199 | $r = $this->sym($R); |
| 200 | $b = $this->sym($B); |
| 201 | $v = ($this->sym($A) << 24) | ($r << 16) | ($s << 8) | $b; |
| 202 | $px .= pack('N', $v); |
| 203 | if ($cache !== null) $cache[(($v * self::HASH) & 0xffffffff) >> $shift] = $v; |
| 204 | $pos++; |
| 205 | if (++$x === $w) { |
| 206 | $x = 0; |
| 207 | $y++; |
| 208 | // 壊れた（短い）ファイルで長く掛からない様に |
| 209 | if ($this->p > strlen($this->d) + 8) throw new \RuntimeException('VP8Lのデータが途中で切れています。'); |
| 210 | } |
| 211 | continue; |
| 212 | } |
| 213 | if ($s < 280) { |
| 214 | $len = $this->prefixValue($s - 256); |
| 215 | $dcode = $this->prefixValue($this->sym($D)); |
| 216 | if ($dcode > 120) { |
| 217 | $dist = $dcode - 120; |
| 218 | } else { |
| 219 | [$xi, $yi] = self::PLANE[$dcode - 1]; |
| 220 | $dist = max(1, $xi + $yi * $w); |
| 221 | } |
| 222 | if ($dist > $pos || $pos + $len > $total) throw new \RuntimeException('VP8Lの後方参照が不正です。'); |
| 223 | $chunk = substr($px, ($pos - $dist) * 4, min($dist, $len) * 4); |
| 224 | if ($dist < $len) $chunk = substr(str_repeat($chunk, intdiv($len, $dist) + 1), 0, $len * 4); |
| 225 | $px .= $chunk; |
| 226 | if ($cache !== null) foreach (unpack('N*', $chunk) as $v) $cache[(($v * self::HASH) & 0xffffffff) >> $shift] = $v; |
| 227 | $pos += $len; |
| 228 | $x += $len; |
| 229 | if ($x >= $w) { |
| 230 | $y += intdiv($x, $w); |
| 231 | $x %= $w; |
| 232 | if ($this->p > strlen($this->d) + 8) throw new \RuntimeException('VP8Lのデータが途中で切れています。'); |
| 233 | } |
| 234 | if ($meta !== null && $pos < $total) [$G, $R, $B, $A, $D] = $codes[$meta[($y >> $metaBits) * $metaW + ($x >> $metaBits)]]; |
| 235 | continue; |
| 236 | } |
| 237 | if ($cache === null) throw new \RuntimeException('VP8Lのカラーキャッシュがありません。'); |
| 238 | $v = $cache[$s - 280]; |
| 239 | $px .= pack('N', $v); |
| 240 | $cache[(($v * self::HASH) & 0xffffffff) >> $shift] = $v; |
| 241 | $pos++; |
| 242 | if (++$x === $w) { |
| 243 | $x = 0; |
| 244 | $y++; |
| 245 | } |
| 246 | } |
| 247 | if ($this->p - ($this->bits >> 3) > strlen($this->d)) throw new \RuntimeException('VP8Lのデータが途中で切れています。'); |
| 248 | return $px; |
| 249 | } |
| 250 | |
| 251 | private function prefixValue(int $prefix): int { |
| 252 | if ($prefix < 4) return $prefix + 1; |
| 253 | $extra = ($prefix - 2) >> 1; |
| 254 | return ((2 + ($prefix & 1)) << $extra) + $this->read($extra) + 1; |
| 255 | } |
| 256 | |
| 257 | /** プレフィックス符号（ハフマン符号）を読む */ |
| 258 | private function readCode(int $alphabet): array { |
| 259 | $lengths = array_fill(0, $alphabet, 0); |
| 260 | if ($this->read(1)) { |
| 261 | // 簡単な符号：1か2個の記号 |
| 262 | $two = $this->read(1); |
| 263 | $s = $this->read($this->read(1) ? 8 : 1); |
| 264 | if ($s >= $alphabet) throw new \RuntimeException('VP8Lの符号が不正です。'); |
| 265 | $lengths[$s] = 1; |
| 266 | if ($two) { |
| 267 | $s = $this->read(8); |
| 268 | if ($s >= $alphabet) throw new \RuntimeException('VP8Lの符号が不正です。'); |
| 269 | $lengths[$s] = 1; |
| 270 | } |
| 271 | return self::buildCode($lengths); |
| 272 | } |
| 273 | $clen = array_fill(0, 19, 0); |
| 274 | $n = 4 + $this->read(4); |
| 275 | for ($i = 0; $i < $n; $i++) $clen[self::ORDER[$i]] = $this->read(3); |
| 276 | $cl = self::buildCode($clen); |
| 277 | $max = $alphabet; |
| 278 | if ($this->read(1)) { |
| 279 | $max = 2 + $this->read(2 + 2 * $this->read(3)); |
| 280 | if ($max > $alphabet) throw new \RuntimeException('VP8Lの符号長が多過ぎます。'); |
| 281 | } |
| 282 | $prev = 8; |
| 283 | $sym = 0; |
| 284 | while ($sym < $alphabet && $max-- > 0) { |
| 285 | $c = $this->sym($cl); |
| 286 | if ($c < 16) { |
| 287 | $lengths[$sym++] = $c; |
| 288 | if ($c !== 0) $prev = $c; |
| 289 | continue; |
| 290 | } |
| 291 | [$rep, $val] = match ($c) {16 => [3 + $this->read(2), $prev], 17 => [3 + $this->read(3), 0], default => [11 + $this->read(7), 0]}; |
| 292 | if ($sym + $rep > $alphabet) throw new \RuntimeException('VP8Lの符号長が不正です。'); |
| 293 | for ($i = 0; $i < $rep; $i++) $lengths[$sym++] = $val; |
| 294 | } |
| 295 | return self::buildCode($lengths); |
| 296 | } |
| 297 | |
| 298 | /** |
| 299 | * 符号長から読む為の表を作る（下位ビットから読むので、符号を反転して引く） |
| 300 | * |
| 301 | * @return array ['single' => 記号]（0ビット）、又は[根の表, 長い符号の表] |
| 302 | */ |
| 303 | private static function buildCode(array $lengths): array { |
| 304 | $count = array_fill(0, 16, 0); |
| 305 | $one = 0; |
| 306 | $used = 0; |
| 307 | foreach ($lengths as $s => $l) { |
| 308 | if ($l === 0) continue; |
| 309 | $count[$l]++; |
| 310 | $one = $s; |
| 311 | $used++; |
| 312 | } |
| 313 | if ($used <= 1) return ['single' => $one]; |
| 314 | $kraft = 0; |
| 315 | for ($l = 1; $l < 16; $l++) $kraft += $count[$l] << (15 - $l); |
| 316 | if ($kraft !== 1 << 15) throw new \RuntimeException('VP8Lのハフマン符号が不完全です。'); |
| 317 | $next = []; |
| 318 | $code = 0; |
| 319 | for ($l = 1; $l < 16; $l++) { |
| 320 | $code = ($code + $count[$l - 1]) << 1; |
| 321 | $next[$l] = $code; |
| 322 | } |
| 323 | $prim = 8; |
| 324 | $root = array_fill(0, 1 << $prim, 0); |
| 325 | $codes = []; |
| 326 | $subBits = []; |
| 327 | foreach ($lengths as $s => $l) { |
| 328 | if ($l === 0) continue; |
| 329 | $c = $next[$l]++; |
| 330 | $r = 0; |
| 331 | for ($i = 0; $i < $l; $i++) $r |= (($c >> $i) & 1) << ($l - 1 - $i); |
| 332 | $codes[] = [$s, $l, $r]; |
| 333 | if ($l > $prim) { |
| 334 | $k = $r & 0xff; |
| 335 | $subBits[$k] = max($subBits[$k] ?? 0, $l - $prim); |
| 336 | } |
| 337 | } |
| 338 | $long = []; |
| 339 | foreach ($subBits as $k => $sb) { |
| 340 | $long[$k] = [$sb, array_fill(0, 1 << $sb, 0)]; |
| 341 | $root[$k] = -1; |
| 342 | } |
| 343 | foreach ($codes as [$s, $l, $r]) { |
| 344 | if ($l <= $prim) { |
| 345 | for ($j = $r; $j < 256; $j += 1 << $l) $root[$j] = ($l << 16) | $s; |
| 346 | } else { |
| 347 | $k = $r & 0xff; |
| 348 | $sb = $long[$k][0]; |
| 349 | for ($j = $r >> $prim; $j < (1 << $sb); $j += 1 << ($l - $prim)) $long[$k][1][$j] = ($l << 16) | $s; |
| 350 | } |
| 351 | } |
| 352 | return [$root, $long]; |
| 353 | } |
| 354 | |
| 355 | private function sym(array $c): int { |
| 356 | if (isset($c['single'])) return $c['single']; |
| 357 | if ($this->bits < 15) { |
| 358 | do { |
| 359 | $this->buf |= ord($this->d[$this->p++] ?? "\0") << $this->bits; |
| 360 | $this->bits += 8; |
| 361 | } while ($this->bits <= 48); |
| 362 | } |
| 363 | $e = $c[0][$this->buf & 0xff]; |
| 364 | if ($e < 0) { |
| 365 | [$sb, $sub] = $c[1][$this->buf & 0xff]; |
| 366 | $e = $sub[($this->buf >> 8) & ((1 << $sb) - 1)]; |
| 367 | } |
| 368 | $l = $e >> 16; |
| 369 | $this->buf >>= $l; |
| 370 | $this->bits -= $l; |
| 371 | return $e & 0xffff; |
| 372 | } |
| 373 | |
| 374 | //////// 逆変換 |
| 375 | |
| 376 | /** 各成分を256で割った余りで足す */ |
| 377 | private static function add(int $a, int $b): int { |
| 378 | return ((($a & 0xff00ff00) + ($b & 0xff00ff00)) & 0xff00ff00) | ((($a & 0x00ff00ff) + ($b & 0x00ff00ff)) & 0x00ff00ff); |
| 379 | } |
| 380 | |
| 381 | private static function sub(int $a, int $b): int { |
| 382 | return ((($a | 0x00ff00ff) - ($b & 0xff00ff00)) & 0xff00ff00) | ((($a | 0xff00ff00) - ($b & 0x00ff00ff)) & 0x00ff00ff); |
| 383 | } |
| 384 | |
| 385 | private static function avg(int $a, int $b): int { |
| 386 | return ((($a ^ $b) & 0xfefefefe) >> 1) + ($a & $b); |
| 387 | } |
| 388 | |
| 389 | /** |
| 390 | * 予測値（モード0～13） |
| 391 | */ |
| 392 | private static function predict(int $mode, int $L, int $T, int $TR, int $TL): int { |
| 393 | return match ($mode) { |
| 394 | 1 => $L, |
| 395 | 2 => $T, |
| 396 | 3 => $TR, |
| 397 | 4 => $TL, |
| 398 | 5 => self::avg(self::avg($L, $TR), $T), |
| 399 | 6 => self::avg($L, $TL), |
| 400 | 7 => self::avg($L, $T), |
| 401 | 8 => self::avg($TL, $T), |
| 402 | 9 => self::avg($T, $TR), |
| 403 | 10 => self::avg(self::avg($L, $TL), self::avg($T, $TR)), |
| 404 | 11 => self::select($L, $T, $TL), |
| 405 | 12 => self::clampAdd($L, $T, $TL), |
| 406 | 13 => self::clampHalf(self::avg($L, $T), $TL), |
| 407 | default => 0xff000000, |
| 408 | }; |
| 409 | } |
| 410 | |
| 411 | private static function select(int $L, int $T, int $TL): int { |
| 412 | // 左なら|T - TL|、上なら|L - TL|が予測との距離 |
| 413 | $pl = $pt = 0; |
| 414 | for ($s = 0; $s < 32; $s += 8) { |
| 415 | $tl = ($TL >> $s) & 255; |
| 416 | $pl += abs((($T >> $s) & 255) - $tl); |
| 417 | $pt += abs((($L >> $s) & 255) - $tl); |
| 418 | } |
| 419 | return $pl < $pt ? $L : $T; |
| 420 | } |
| 421 | |
| 422 | private static function clampAdd(int $a, int $b, int $c): int { |
| 423 | $out = 0; |
| 424 | for ($s = 0; $s < 32; $s += 8) { |
| 425 | $v = (($a >> $s) & 255) + (($b >> $s) & 255) - (($c >> $s) & 255); |
| 426 | $out |= ($v < 0 ? 0 : ($v > 255 ? 255 : $v)) << $s; |
| 427 | } |
| 428 | return $out; |
| 429 | } |
| 430 | |
| 431 | private static function clampHalf(int $a, int $b): int { |
| 432 | $out = 0; |
| 433 | for ($s = 0; $s < 32; $s += 8) { |
| 434 | $av = ($a >> $s) & 255; |
| 435 | $v = $av + intdiv($av - (($b >> $s) & 255), 2); |
| 436 | $out |= ($v < 0 ? 0 : ($v > 255 ? 255 : $v)) << $s; |
| 437 | } |
| 438 | return $out; |
| 439 | } |
| 440 | |
| 441 | private static function inversePredictor(string $px, array $t, int $h): string { |
| 442 | $w = $t['w']; |
| 443 | $bits = $t['bits']; |
| 444 | $bw = $t['bw']; |
| 445 | $modes = $t['data']; |
| 446 | $out = ''; |
| 447 | $prev = []; |
| 448 | for ($y = 0; $y < $h; $y++) { |
| 449 | $res = unpack('N*', substr($px, $y * $w * 4, $w * 4)); |
| 450 | // 左上は黒、1行目は左、左の列は上 |
| 451 | $cur = [self::add($res[1], $y === 0 ? 0xff000000 : $prev[0])]; |
| 452 | if ($y === 0) { |
| 453 | for ($x = 1; $x < $w; $x++) $cur[$x] = self::add($res[$x + 1], $cur[$x - 1]); |
| 454 | } else { |
| 455 | $mrow = ($y >> $bits) * $bw; |
| 456 | for ($x = 1; $x < $w; $x++) { |
| 457 | // 右端の右上は、この行の左端 |
| 458 | $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]); |
| 459 | $cur[$x] = self::add($res[$x + 1], $pred); |
| 460 | } |
| 461 | } |
| 462 | $out .= pack('N*', ...$cur); |
| 463 | $prev = $cur; |
| 464 | } |
| 465 | return $out; |
| 466 | } |
| 467 | |
| 468 | private static function inverseColor(string $px, array $t, int $h): string { |
| 469 | $w = $t['w']; |
| 470 | $bits = $t['bits']; |
| 471 | $bw = $t['bw']; |
| 472 | $out = ''; |
| 473 | $s8 = fn(int $v): int => $v >= 128 ? $v - 256 : $v; |
| 474 | for ($y = 0; $y < $h; $y++) { |
| 475 | $row = unpack('N*', substr($px, $y * $w * 4, $w * 4)); |
| 476 | $mrow = ($y >> $bits) * $bw; |
| 477 | for ($x = 0; $x < $w; $x++) { |
| 478 | $e = $t['data'][$mrow + ($x >> $bits)]; |
| 479 | $p = $row[$x + 1]; |
| 480 | $g = $s8(($p >> 8) & 255); |
| 481 | $r = ((($p >> 16) & 255) + (($s8($e & 255) * $g) >> 5)) & 255; |
| 482 | $b = (($p & 255) + (($s8(($e >> 8) & 255) * $g) >> 5) + (($s8(($e >> 16) & 255) * $s8($r)) >> 5)) & 255; |
| 483 | $row[$x + 1] = ($p & 0xff00ff00) | ($r << 16) | $b; |
| 484 | } |
| 485 | $out .= pack('N*', ...$row); |
| 486 | } |
| 487 | return $out; |
| 488 | } |
| 489 | |
| 490 | private static function addGreen(string $px, int $w, int $h): string { |
| 491 | $out = ''; |
| 492 | for ($y = 0; $y < $h; $y++) { |
| 493 | $row = unpack('N*', substr($px, $y * $w * 4, $w * 4)); |
| 494 | foreach ($row as $i => $p) { |
| 495 | $g = ($p >> 8) & 255; |
| 496 | $row[$i] = ($p & 0xff00ff00) | (((($p >> 16) + $g) & 255) << 16) | ((($p & 255) + $g) & 255); |
| 497 | } |
| 498 | $out .= pack('N*', ...$row); |
| 499 | } |
| 500 | return $out; |
| 501 | } |
| 502 | |
| 503 | private static function inversePalette(string $px, array $t, int $h, int $pw): string { |
| 504 | $pal = $t['palette']; |
| 505 | $bits = $t['bits']; |
| 506 | $w = $t['w']; |
| 507 | $out = ''; |
| 508 | if ($bits === 0) { |
| 509 | for ($i = 2, $n = strlen($px); $i < $n; $i += 4) $out .= $pal[ord($px[$i])]; |
| 510 | return $out; |
| 511 | } |
| 512 | $ib = 8 >> $bits; |
| 513 | $mask = (1 << $ib) - 1; |
| 514 | $per = (1 << $bits) - 1; |
| 515 | for ($y = 0; $y < $h; $y++) { |
| 516 | $o = $y * $pw * 4 + 2; |
| 517 | $g = 0; |
| 518 | for ($x = 0; $x < $w; $x++) { |
| 519 | if (($x & $per) === 0) $g = ord($px[$o + ($x >> $bits) * 4]); |
| 520 | $out .= $pal[$g & $mask]; |
| 521 | $g >>= $ib; |
| 522 | } |
| 523 | } |
| 524 | return $out; |
| 525 | } |
| 526 | |
| 527 | //////// 書き出し |
| 528 | |
| 529 | /** |
| 530 | * VP8Lチャンクの中身を作る |
| 531 | * |
| 532 | * @param array $px ARGBの整数の配列（左上から行の順） |
| 533 | */ |
| 534 | public function encode(array $px, int $w, int $h, bool $alpha): string { |
| 535 | $this->out = ''; |
| 536 | $this->acc = $this->nb = 0; |
| 537 | $this->put(0x2f, 8); |
| 538 | $this->put($w - 1, 14); |
| 539 | $this->put($h - 1, 14); |
| 540 | $this->put($alpha ? 1 : 0, 1); |
| 541 | $this->put(0, 3); |
| 542 | $this->stream($px, $w, $h); |
| 543 | return $this->flush(); |
| 544 | } |
| 545 | |
| 546 | /** |
| 547 | * ヘッダーの無い画像（ALPHチャンク用） |
| 548 | */ |
| 549 | public function encodeImage(array $px, int $w, int $h): string { |
| 550 | $this->out = ''; |
| 551 | $this->acc = $this->nb = 0; |
| 552 | $this->stream($px, $w, $h); |
| 553 | return $this->flush(); |
| 554 | } |
| 555 | |
| 556 | private function put(int $v, int $n): void { |
| 557 | $this->acc |= $v << $this->nb; |
| 558 | $this->nb += $n; |
| 559 | while ($this->nb >= 8) { |
| 560 | $this->out .= chr($this->acc & 255); |
| 561 | $this->acc >>= 8; |
| 562 | $this->nb -= 8; |
| 563 | } |
| 564 | } |
| 565 | |
| 566 | private function flush(): string { |
| 567 | if ($this->nb > 0) $this->out .= chr($this->acc & 255); |
| 568 | $this->acc = $this->nb = 0; |
| 569 | return $this->out; |
| 570 | } |
| 571 | |
| 572 | private function stream(array $px, int $w, int $h): void { |
| 573 | $colors = []; |
| 574 | foreach ($px as $c) { |
| 575 | $colors[$c] = true; |
| 576 | if (count($colors) > 256) break; |
| 577 | } |
| 578 | if (count($colors) <= 256) { |
| 579 | // パレット（色の番号を緑に入れ、少なければ1バイトに詰める） |
| 580 | $pal = array_keys($colors); |
| 581 | sort($pal); |
| 582 | $n = count($pal); |
| 583 | $index = array_flip($pal); |
| 584 | $bits = $n <= 2 ? 3 : ($n <= 4 ? 2 : ($n <= 16 ? 1 : 0)); |
| 585 | $this->put(1, 1); |
| 586 | $this->put(3, 2); |
| 587 | $this->put($n - 1, 8); |
| 588 | $delta = [$pal[0]]; |
| 589 | for ($i = 1; $i < $n; $i++) $delta[] = self::sub($pal[$i], $pal[$i - 1]); |
| 590 | $this->entropy($delta, $n, 1, false); |
| 591 | $pw = self::subSize($w, $bits); |
| 592 | $per = 1 << $bits; |
| 593 | $ib = 8 >> $bits; |
| 594 | $packed = []; |
| 595 | for ($y = 0; $y < $h; $y++) { |
| 596 | $row = $y * $w; |
| 597 | for ($xb = 0; $xb < $pw; $xb++) { |
| 598 | $g = 0; |
| 599 | for ($k = 0, $x = $xb * $per; $k < $per && $x < $w; $k++, $x++) $g |= $index[$px[$row + $x]] << ($k * $ib); |
| 600 | $packed[] = $g << 8; |
| 601 | } |
| 602 | } |
| 603 | $px = $packed; |
| 604 | $w = $pw; |
| 605 | } else { |
| 606 | // 緑を引いてから予測 |
| 607 | $this->put(1, 1); |
| 608 | $this->put(2, 2); |
| 609 | foreach ($px as $i => $c) { |
| 610 | $g = ($c >> 8) & 255; |
| 611 | $px[$i] = ($c & 0xff00ff00) | (((($c >> 16) - $g) & 255) << 16) | ((($c & 255) - $g) & 255); |
| 612 | } |
| 613 | $bits = $w * $h > 65536 ? 5 : 4; |
| 614 | [$modes, $px] = self::predictor($px, $w, $h, $bits); |
| 615 | $this->put(1, 1); |
| 616 | $this->put(0, 2); |
| 617 | $this->put($bits - 2, 3); |
| 618 | $this->entropy($modes, self::subSize($w, $bits), self::subSize($h, $bits), false); |
| 619 | } |
| 620 | $this->put(0, 1); |
| 621 | $this->entropy($px, $w, $h, true); |
| 622 | } |
| 623 | |
| 624 | /** |
| 625 | * 予測の変換（ブロック毎に残差の小さいモードを選ぶ） |
| 626 | * |
| 627 | * @return array [モードの画像, 残差] |
| 628 | */ |
| 629 | private static function predictor(array $px, int $w, int $h, int $bits): array { |
| 630 | $bw = self::subSize($w, $bits); |
| 631 | $bh = self::subSize($h, $bits); |
| 632 | $size = 1 << $bits; |
| 633 | $modes = []; |
| 634 | $res = $px; |
| 635 | $cost = static function(int $d): int { |
| 636 | $c = 0; |
| 637 | for ($s = 0; $s < 32; $s += 8) { |
| 638 | $v = ($d >> $s) & 255; |
| 639 | $c += $v < 128 ? $v : 256 - $v; |
| 640 | } |
| 641 | return $c; |
| 642 | }; |
| 643 | for ($by = 0; $by < $bh; $by++) { |
| 644 | for ($bx = 0; $bx < $bw; $bx++) { |
| 645 | $x0 = $bx * $size; |
| 646 | $y0 = $by * $size; |
| 647 | $x1 = min($w, $x0 + $size); |
| 648 | $y1 = min($h, $y0 + $size); |
| 649 | $best = 1; |
| 650 | $bestCost = PHP_INT_MAX; |
| 651 | foreach ([1, 2, 11, 12, 7, 13, 3, 4] as $m) { |
| 652 | $c = 0; |
| 653 | for ($y = max(1, $y0); $y < $y1 && $c < $bestCost; $y++) { |
| 654 | $row = $y * $w; |
| 655 | for ($x = max(1, $x0); $x < $x1; $x++) { |
| 656 | $i = $row + $x; |
| 657 | $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]))); |
| 658 | } |
| 659 | } |
| 660 | if ($c < $bestCost) { |
| 661 | $bestCost = $c; |
| 662 | $best = $m; |
| 663 | } |
| 664 | } |
| 665 | $modes[$by * $bw + $bx] = 0xff000000 | ($best << 8); |
| 666 | } |
| 667 | } |
| 668 | $res[0] = self::sub($px[0], 0xff000000); |
| 669 | for ($x = 1; $x < $w; $x++) $res[$x] = self::sub($px[$x], $px[$x - 1]); |
| 670 | for ($y = 1; $y < $h; $y++) { |
| 671 | $row = $y * $w; |
| 672 | $res[$row] = self::sub($px[$row], $px[$row - $w]); |
| 673 | $mrow = ($y >> $bits) * $bw; |
| 674 | for ($x = 1; $x < $w; $x++) { |
| 675 | $i = $row + $x; |
| 676 | $m = ($modes[$mrow + ($x >> $bits)] >> 8) & 15; |
| 677 | $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])); |
| 678 | } |
| 679 | } |
| 680 | return [$modes, $res]; |
| 681 | } |
| 682 | |
| 683 | /** |
| 684 | * エントロピー符号化した画像を書く |
| 685 | */ |
| 686 | private function entropy(array $px, int $w, int $h, bool $main): void { |
| 687 | $tokens = self::lz77($px, $w); |
| 688 | // カラーキャッシュの大きさは、見積もった大きさで選ぶ |
| 689 | $best = null; |
| 690 | foreach ($main ? [0, 6, 10] : [0] as $cacheBits) { |
| 691 | $hist = self::histogram($px, $tokens, $w, $cacheBits); |
| 692 | $size = 0; |
| 693 | foreach ($hist as $hh) $size += self::entropyBits($hh); |
| 694 | if ($best === null || $size < $best[0]) $best = [$size, $cacheBits, $hist]; |
| 695 | } |
| 696 | [, $cacheBits, $hist] = $best; |
| 697 | if ($cacheBits) { |
| 698 | $this->put(1, 1); |
| 699 | $this->put($cacheBits, 4); |
| 700 | } else { |
| 701 | $this->put(0, 1); |
| 702 | } |
| 703 | if ($main) $this->put(0, 1); // メタプレフィックス符号は使わない |
| 704 | $codes = []; |
| 705 | foreach ($hist as $hh) $codes[] = $this->writeCode($hh); |
| 706 | [[$gc, $gl], [$rc, $rl], [$bc, $bl], [$ac, $al], [$dc, $dl]] = $codes; |
| 707 | |
| 708 | $cache = $cacheBits ? array_fill(0, 1 << $cacheBits, -1) : null; |
| 709 | $shift = 32 - $cacheBits; |
| 710 | $pos = 0; |
| 711 | foreach ($tokens as $t) { |
| 712 | if ($t >= 0) { |
| 713 | if ($cache !== null) { |
| 714 | $k = (($t * self::HASH) & 0xffffffff) >> $shift; |
| 715 | if ($cache[$k] === $t) { |
| 716 | $this->put($gc[280 + $k], $gl[280 + $k]); |
| 717 | $pos++; |
| 718 | continue; |
| 719 | } |
| 720 | $cache[$k] = $t; |
| 721 | } |
| 722 | $g = ($t >> 8) & 255; |
| 723 | $r = ($t >> 16) & 255; |
| 724 | $b = $t & 255; |
| 725 | $a = ($t >> 24) & 255; |
| 726 | $this->put($gc[$g], $gl[$g]); |
| 727 | $this->put($rc[$r], $rl[$r]); |
| 728 | $this->put($bc[$b], $bl[$b]); |
| 729 | $this->put($ac[$a], $al[$a]); |
| 730 | $pos++; |
| 731 | continue; |
| 732 | } |
| 733 | $len = (-$t) >> 21; |
| 734 | $dcode = (-$t) & 0x1fffff; |
| 735 | [$p, $eb, $ev] = self::prefix($len); |
| 736 | $this->put($gc[256 + $p], $gl[256 + $p]); |
| 737 | if ($eb) $this->put($ev, $eb); |
| 738 | [$p, $eb, $ev] = self::prefix($dcode); |
| 739 | $this->put($dc[$p], $dl[$p]); |
| 740 | if ($eb) $this->put($ev, $eb); |
| 741 | if ($cache !== null) { |
| 742 | for ($i = $pos; $i < $pos + $len; $i++) $cache[(($px[$i] * self::HASH) & 0xffffffff) >> $shift] = $px[$i]; |
| 743 | } |
| 744 | $pos += $len; |
| 745 | } |
| 746 | } |
| 747 | |
| 748 | /** |
| 749 | * 値をプレフィックス符号と追加ビットにする |
| 750 | * |
| 751 | * @return array [符号, 追加ビット数, 追加ビット] |
| 752 | */ |
| 753 | private static function prefix(int $v): array { |
| 754 | $d = $v - 1; |
| 755 | if ($d < 4) return [$d, 0, 0]; |
| 756 | $hb = strlen(decbin($d)) - 1; |
| 757 | $s = ($d >> ($hb - 1)) & 1; |
| 758 | return [2 * $hb + $s, $hb - 1, $d & ((1 << ($hb - 1)) - 1)]; |
| 759 | } |
| 760 | |
| 761 | /** |
| 762 | * LZ77（同じ画素列の繰り返しを後方参照にする） |
| 763 | * |
| 764 | * @return array 画素（0以上）、又は-(長さ << 21 | 距離の符号) |
| 765 | */ |
| 766 | private static function lz77(array $px, int $w): array { |
| 767 | $n = count($px); |
| 768 | $head = []; |
| 769 | $chain = []; |
| 770 | $tokens = []; |
| 771 | $plane = []; |
| 772 | foreach (self::PLANE as $i => [$xi, $yi]) $plane[$yi * 16 + 8 - $xi] = $i + 1; |
| 773 | $insert = function(int $i) use (&$head, &$chain, $px, $n): void { |
| 774 | if ($i + 1 >= $n) return; |
| 775 | $k = ($px[$i] << 32) ^ $px[$i + 1]; |
| 776 | if (isset($head[$k])) $chain[$i] = $head[$k]; |
| 777 | $head[$k] = $i; |
| 778 | }; |
| 779 | $i = 0; |
| 780 | while ($i < $n) { |
| 781 | $max = min(self::MAX_LENGTH, $n - $i); |
| 782 | $best = 0; |
| 783 | $bestDist = 0; |
| 784 | if ($max >= 3) { |
| 785 | // すぐ左とすぐ上を先に試す |
| 786 | foreach ([1, $w] as $dist) { |
| 787 | if ($dist > $i || $px[$i] !== $px[$i - $dist]) continue; |
| 788 | $l = 1; |
| 789 | while ($l < $max && $px[$i + $l] === $px[$i - $dist + $l]) $l++; |
| 790 | if ($l > $best) { |
| 791 | $best = $l; |
| 792 | $bestDist = $dist; |
| 793 | } |
| 794 | } |
| 795 | $k = ($px[$i] << 32) ^ $px[$i + 1]; |
| 796 | $c = $head[$k] ?? -1; |
| 797 | for ($tries = 0; $c >= 0 && $tries < 16 && $best < $max && $i - $c <= self::MAX_DISTANCE; $tries++) { |
| 798 | $l = 0; |
| 799 | while ($l < $max && $px[$c + $l] === $px[$i + $l]) $l++; |
| 800 | if ($l > $best) { |
| 801 | $best = $l; |
| 802 | $bestDist = $i - $c; |
| 803 | } |
| 804 | $c = $chain[$c] ?? -1; |
| 805 | } |
| 806 | } |
| 807 | if ($best >= 3) { |
| 808 | $yi = intdiv($bestDist, $w); |
| 809 | $xi = $bestDist - $yi * $w; |
| 810 | $code = $bestDist + 120; |
| 811 | if ($xi <= 8 && $yi < 8 && isset($plane[$yi * 16 + 8 - $xi])) { |
| 812 | $code = $plane[$yi * 16 + 8 - $xi]; |
| 813 | } else if ($w - $xi <= 7 && $yi + 1 < 8 && isset($plane[($yi + 1) * 16 + 8 + $w - $xi])) { |
| 814 | $code = $plane[($yi + 1) * 16 + 8 + $w - $xi]; |
| 815 | } |
| 816 | $tokens[] = -(($best << 21) | $code); |
| 817 | for ($j = $i; $j < $i + $best; $j++) $insert($j); |
| 818 | $i += $best; |
| 819 | } else { |
| 820 | $tokens[] = $px[$i]; |
| 821 | $insert($i); |
| 822 | $i++; |
| 823 | } |
| 824 | } |
| 825 | return $tokens; |
| 826 | } |
| 827 | |
| 828 | /** |
| 829 | * 5つの符号の記号の数（カラーキャッシュの当たりも数える） |
| 830 | */ |
| 831 | private static function histogram(array $px, array $tokens, int $w, int $cacheBits): array { |
| 832 | $g = array_fill(0, 280 + ($cacheBits ? 1 << $cacheBits : 0), 0); |
| 833 | $r = $b = $a = array_fill(0, 256, 0); |
| 834 | $d = array_fill(0, 40, 0); |
| 835 | $cache = $cacheBits ? array_fill(0, 1 << $cacheBits, -1) : null; |
| 836 | $shift = 32 - $cacheBits; |
| 837 | $pos = 0; |
| 838 | foreach ($tokens as $t) { |
| 839 | if ($t >= 0) { |
| 840 | if ($cache !== null) { |
| 841 | $k = (($t * self::HASH) & 0xffffffff) >> $shift; |
| 842 | if ($cache[$k] === $t) { |
| 843 | $g[280 + $k]++; |
| 844 | $pos++; |
| 845 | continue; |
| 846 | } |
| 847 | $cache[$k] = $t; |
| 848 | } |
| 849 | $g[($t >> 8) & 255]++; |
| 850 | $r[($t >> 16) & 255]++; |
| 851 | $b[$t & 255]++; |
| 852 | $a[($t >> 24) & 255]++; |
| 853 | $pos++; |
| 854 | continue; |
| 855 | } |
| 856 | $len = (-$t) >> 21; |
| 857 | $g[256 + self::prefix($len)[0]]++; |
| 858 | $d[self::prefix((-$t) & 0x1fffff)[0]]++; |
| 859 | if ($cache !== null) { |
| 860 | for ($i = $pos; $i < $pos + $len; $i++) $cache[(($px[$i] * self::HASH) & 0xffffffff) >> $shift] = $px[$i]; |
| 861 | } |
| 862 | $pos += $len; |
| 863 | } |
| 864 | return [$g, $r, $b, $a, $d]; |
| 865 | } |
| 866 | |
| 867 | /** 記号の数から見積もった符号の大きさ（ビット） */ |
| 868 | private static function entropyBits(array $hist): float { |
| 869 | $total = array_sum($hist); |
| 870 | if ($total === 0) return 0.0; |
| 871 | $bits = 0.0; |
| 872 | $used = 0; |
| 873 | foreach ($hist as $c) { |
| 874 | if ($c === 0) continue; |
| 875 | $bits -= $c * log($c / $total, 2); |
| 876 | $used++; |
| 877 | } |
| 878 | // 符号長の分も大体足す |
| 879 | return $bits + $used * 4; |
| 880 | } |
| 881 | |
| 882 | /** |
| 883 | * プレフィックス符号を書く |
| 884 | * |
| 885 | * @return array [記号 => 反転した符号, 記号 => 長さ] |
| 886 | */ |
| 887 | private function writeCode(array $hist): array { |
| 888 | $used = []; |
| 889 | foreach ($hist as $s => $c) if ($c > 0) $used[] = $s; |
| 890 | $len = array_fill(0, count($hist), 0); |
| 891 | if (count($used) <= 2 && ($used[1] ?? $used[0] ?? 0) < 256) { |
| 892 | // 簡単な符号 |
| 893 | $syms = $used ?: [0]; |
| 894 | $this->put(1, 1); |
| 895 | $this->put(count($syms) - 1, 1); |
| 896 | if ($syms[0] < 2) { |
| 897 | $this->put(0, 1); |
| 898 | $this->put($syms[0], 1); |
| 899 | } else { |
| 900 | $this->put(1, 1); |
| 901 | $this->put($syms[0], 8); |
| 902 | } |
| 903 | if (count($syms) === 2) { |
| 904 | $this->put($syms[1], 8); |
| 905 | $len[$syms[0]] = $len[$syms[1]] = 1; |
| 906 | } |
| 907 | return self::canonical($len); |
| 908 | } |
| 909 | $this->put(0, 1); |
| 910 | if (count($used) === 1) { |
| 911 | // 1つだけの記号は0ビット |
| 912 | $len[$used[0]] = 1; |
| 913 | $this->writeLengths($len); |
| 914 | $len[$used[0]] = 0; |
| 915 | return self::canonical($len); |
| 916 | } |
| 917 | $len = self::lengths($hist, 15); |
| 918 | $this->writeLengths($len); |
| 919 | return self::canonical($len); |
| 920 | } |
| 921 | |
| 922 | private function writeLengths(array $len): void { |
| 923 | // 連長圧縮（16：前の長さを3～6回、17：0を3～10回、18：0を11～138回） |
| 924 | $tokens = []; |
| 925 | $n = count($len); |
| 926 | $prev = 8; |
| 927 | for ($i = 0; $i < $n;) { |
| 928 | $v = $len[$i]; |
| 929 | $run = 1; |
| 930 | while ($i + $run < $n && $len[$i + $run] === $v) $run++; |
| 931 | $i += $run; |
| 932 | if ($v === 0) { |
| 933 | while ($run >= 11) { |
| 934 | $r = min($run, 138); |
| 935 | $tokens[] = [18, 7, $r - 11]; |
| 936 | $run -= $r; |
| 937 | } |
| 938 | if ($run >= 3) { |
| 939 | $tokens[] = [17, 3, $run - 3]; |
| 940 | $run = 0; |
| 941 | } |
| 942 | for (; $run > 0; $run--) $tokens[] = [0, 0, 0]; |
| 943 | continue; |
| 944 | } |
| 945 | if ($v !== $prev) { |
| 946 | $tokens[] = [$v, 0, 0]; |
| 947 | $prev = $v; |
| 948 | $run--; |
| 949 | } |
| 950 | while ($run >= 3) { |
| 951 | $r = min($run, 6); |
| 952 | $tokens[] = [16, 2, $r - 3]; |
| 953 | $run -= $r; |
| 954 | } |
| 955 | for (; $run > 0; $run--) $tokens[] = [$v, 0, 0]; |
| 956 | } |
| 957 | $hist = array_fill(0, 19, 0); |
| 958 | foreach ($tokens as [$s]) $hist[$s]++; |
| 959 | $used = array_keys(array_filter($hist)); |
| 960 | if (count($used) === 1) { |
| 961 | $cl = array_fill(0, 19, 0); |
| 962 | $cl[$used[0]] = 1; |
| 963 | } else { |
| 964 | $cl = self::lengths($hist, 7); |
| 965 | } |
| 966 | $num = 19; |
| 967 | while ($num > 4 && $cl[self::ORDER[$num - 1]] === 0) $num--; |
| 968 | $this->put($num - 4, 4); |
| 969 | for ($i = 0; $i < $num; $i++) $this->put($cl[self::ORDER[$i]], 3); |
| 970 | $this->put(0, 1); // 全ての記号の長さを書く |
| 971 | if (count($used) === 1) $cl[$used[0]] = 0; |
| 972 | [$codes, $cl] = self::canonical($cl); |
| 973 | foreach ($tokens as [$s, $eb, $ev]) { |
| 974 | $this->put($codes[$s], $cl[$s]); |
| 975 | if ($eb) $this->put($ev, $eb); |
| 976 | } |
| 977 | } |
| 978 | |
| 979 | /** |
| 980 | * 長さの制限付きのハフマン符号長（制限を超えたら、少ない記号の数を底上げしてやり直す） |
| 981 | */ |
| 982 | private static function lengths(array $hist, int $limit): array { |
| 983 | $len = array_fill(0, count($hist), 0); |
| 984 | for ($min = 1; ; $min *= 2) { |
| 985 | $leaves = []; |
| 986 | foreach ($hist as $s => $c) if ($c > 0) $leaves[] = [max($c, $min), $s]; |
| 987 | usort($leaves, fn($a, $b) => $a[0] <=> $b[0] ?: $a[1] <=> $b[1]); |
| 988 | $m = count($leaves); |
| 989 | $freq = array_column($leaves, 0); |
| 990 | $parent = []; |
| 991 | $li = 0; |
| 992 | $ni = $m; |
| 993 | for ($next = $m; $next < 2 * $m - 1; $next++) { |
| 994 | $pick = []; |
| 995 | for ($k = 0; $k < 2; $k++) { |
| 996 | if ($li < $m && ($ni >= $next || $freq[$li] <= $freq[$ni])) $pick[] = $li++; |
| 997 | else $pick[] = $ni++; |
| 998 | } |
| 999 | $freq[$next] = $freq[$pick[0]] + $freq[$pick[1]]; |
| 1000 | $parent[$pick[0]] = $parent[$pick[1]] = $next; |
| 1001 | } |
| 1002 | $depth = [2 * $m - 2 => 0]; |
| 1003 | for ($i = 2 * $m - 3; $i >= 0; $i--) $depth[$i] = $depth[$parent[$i]] + 1; |
| 1004 | $max = 0; |
| 1005 | for ($i = 0; $i < $m; $i++) $max = max($max, $depth[$i]); |
| 1006 | if ($max <= $limit) { |
| 1007 | for ($i = 0; $i < $m; $i++) $len[$leaves[$i][1]] = $depth[$i]; |
| 1008 | return $len; |
| 1009 | } |
| 1010 | } |
| 1011 | } |
| 1012 | |
| 1013 | /** |
| 1014 | * 符号長から符号を作る（書く時は下位ビットからなので反転する） |
| 1015 | */ |
| 1016 | private static function canonical(array $len): array { |
| 1017 | $count = array_fill(0, 16, 0); |
| 1018 | foreach ($len as $l) if ($l) $count[$l]++; |
| 1019 | $next = []; |
| 1020 | $code = 0; |
| 1021 | for ($l = 1; $l < 16; $l++) { |
| 1022 | $code = ($code + $count[$l - 1]) << 1; |
| 1023 | $next[$l] = $code; |
| 1024 | } |
| 1025 | $codes = array_fill(0, count($len), 0); |
| 1026 | foreach ($len as $s => $l) { |
| 1027 | if (!$l) continue; |
| 1028 | $c = $next[$l]++; |
| 1029 | $r = 0; |
| 1030 | for ($i = 0; $i < $l; $i++) $r |= (($c >> $i) & 1) << ($l - 1 - $i); |
| 1031 | $codes[$s] = $r; |
| 1032 | } |
| 1033 | return [$codes, $len]; |
| 1034 | } |
| 1035 | } |