suwako / LittleBeast

master
ブランチ master
LittleBeast / src / Std / Lib / Image / Gif.php
18.7 KB、504行 生 Blame 履歴
1<?php
2/*************************************************************
3# 076 License
4
5Copyright (c) テクニカル諏訪子
6
7Permission is hereby granted to any person obtaining a copy of the software
8Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
9sublicense, 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
31THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
32INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
33PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
34HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
35CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
36OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 */
38namespace Std\Lib\Image;
39
40/**
41 * GIF（87a・89a）
42 *
43 * 読み込み：LZW（12ビット、クリア、遅延クリア）、インターレース、全体・ローカルのパレット、透明色、
44 * アニメーション（グラフィック制御拡張の遅延・廃棄方法、NETSCAPE2.0の繰り返し回数）。
45 * 書き出し：256色以下はそのまま、それ以上はメディアンカットで減色（任意で誤差拡散）。framesがあればアニメーション。
46 */
47class Gif implements ImageInterface {
48 public function parse(string $file): \stdClass {
49 $d = (string)file_get_contents($file);
50 $s = $this->scan($d, false);
51 $first = $s['images'][0] ?? null;
52 return (object)[
53 'version' => substr($d, 3, 3),
54 'width' => $s['width'],
55 'height' => $s['height'],
56 'bitDepth' => $s['depth'],
57 'numColors' => 1 << $s['depth'],
58 'globalColors' => strlen($s['gct']) / 3,
59 'bgColor' => $s['bg'],
60 'frames' => count($s['images']),
61 'loops' => $s['loops'],
62 'delayTime' => $first ? $first['delay'] / 100.0 : 0,
63 'hasAlpha' => $first !== null && $first['transparent'] !== null,
64 'interlace' => $first !== null && $first['interlace'],
65 'compression' => 'LZW',
66 ];
67 }
68
69 /**
70 * ブロックを読む
71 *
72 * @param bool $decode 画像のLZWを展開するか（falseなら大きさ等だけ）
73 */
74 private function scan(string $d, bool $decode): array {
75 $v = substr($d, 0, 6);
76 if ($v !== 'GIF87a' && $v !== 'GIF89a') throw new \RuntimeException('GIFではありません。');
77 if (strlen($d) < 13) throw new \RuntimeException('GIFのヘッダーが途中で切れています。');
78 $h = unpack('vw/vh/Cflags/Cbg/Caspect', substr($d, 6, 7));
79 Bitmap::check($h['w'], $h['h']);
80 $pos = 13;
81 $gct = '';
82 if ($h['flags'] & 0x80) {
83 $gct = substr($d, $pos, 3 << (($h['flags'] & 7) + 1));
84 $pos += strlen($gct);
85 }
86 $len = strlen($d);
87 $images = [];
88 $gce = null;
89 $loops = 1; // NETSCAPE2.0が無ければ1回
90 while ($pos < $len) {
91 $b = ord($d[$pos++]);
92 if ($b === 0x3b) break;
93 if ($b === 0x21) {
94 $label = ord($d[$pos++] ?? "\0");
95 [$data, $pos] = $this->subBlocks($d, $pos);
96 if ($label === 0xf9 && strlen($data) >= 4) {
97 $g = unpack('Cflags/vdelay/Ctrans', $data);
98 $gce = ['dispose' => ($g['flags'] >> 2) & 7, 'delay' => $g['delay'], 'transparent' => $g['flags'] & 1 ? $g['trans'] : null];
99 } else if ($label === 0xff && (str_starts_with($data, 'NETSCAPE2.0') || str_starts_with($data, 'ANIMEXTS1.0')) && strlen($data) >= 14 && ord($data[11]) === 1) {
100 // 繰り返し回数（0 = 無限）。ブラウザと同じく、最初の再生に加えてn回
101 $n = unpack('v', substr($data, 12, 2))[1];
102 $loops = $n === 0 ? 0 : $n + 1;
103 }
104 continue;
105 }
106 if ($b !== 0x2c) {
107 // 不明なブロック：ブラウザと同じく、そこで終わりにする
108 break;
109 }
110 if ($pos + 9 > $len) throw new \RuntimeException('GIFの画像記述子が途中で切れています。');
111 $im = unpack('vx/vy/vw/vh/Cflags', substr($d, $pos, 9));
112 $pos += 9;
113 $lct = '';
114 if ($im['flags'] & 0x80) {
115 $lct = substr($d, $pos, 3 << (($im['flags'] & 7) + 1));
116 $pos += strlen($lct);
117 }
118 $min = ord($d[$pos++] ?? "\0");
119 [$data, $pos] = $this->subBlocks($d, $pos);
120 $images[] = [
121 'x' => $im['x'], 'y' => $im['y'], 'w' => $im['w'], 'h' => $im['h'],
122 'interlace' => ($im['flags'] & 0x40) !== 0,
123 'palette' => $lct !== '' ? $lct : $gct,
124 'indices' => $decode ? $this->unlzw($data, $min, $im['w'] * $im['h']) : '',
125 'dispose' => $gce['dispose'] ?? 0,
126 'delay' => $gce['delay'] ?? 0,
127 'transparent' => $gce['transparent'] ?? null,
128 ];
129 $gce = null;
130 }
131 if (!$images) throw new \RuntimeException('GIFに画像がありません。');
132 return ['width' => $h['w'], 'height' => $h['h'], 'gct' => $gct, 'bg' => $h['bg'], 'depth' => (($h['flags'] >> 4) & 7) + 1, 'images' => $images, 'loops' => $loops];
133 }
134
135 /** データのサブブロック（長さ＋データ、長さ0で終わり）を繋げる */
136 private function subBlocks(string $d, int $pos): array {
137 $out = '';
138 $len = strlen($d);
139 while ($pos < $len) {
140 $n = ord($d[$pos++]);
141 if ($n === 0) break;
142 $out .= substr($d, $pos, $n);
143 $pos += $n;
144 }
145 return [$out, $pos];
146 }
147
148 /**
149 * LZWを展開する
150 *
151 * @return string パレットの指標（1画素1バイト）
152 */
153 private function unlzw(string $data, int $min, int $count): string {
154 if ($min < 2 || $min > 8) throw new \RuntimeException('GIFのLZWの最小符号長が不正です。');
155 $clear = 1 << $min;
156 $eoi = $clear + 1;
157 $base = [];
158 for ($i = 0; $i < $clear; $i++) $base[] = chr($i);
159 $base[] = '';
160 $base[] = '';
161 $dict = $base;
162 $size = $min + 1;
163 $mask = (1 << $size) - 1;
164 $out = '';
165 $outLen = 0;
166 $prev = null;
167 $buf = $bits = $pos = 0;
168 $len = strlen($data);
169 while ($outLen < $count) {
170 while ($bits < $size) {
171 if ($pos >= $len) break 2;
172 $buf |= ord($data[$pos++]) << $bits;
173 $bits += 8;
174 }
175 $code = $buf & $mask;
176 $buf >>= $size;
177 $bits -= $size;
178
179 if ($code === $clear) {
180 $dict = $base;
181 $size = $min + 1;
182 $mask = (1 << $size) - 1;
183 $prev = null;
184 continue;
185 }
186 if ($code === $eoi) break;
187 $n = count($dict);
188 if ($code < $n && $code !== $clear && $code !== $eoi) {
189 $entry = $dict[$code];
190 } else if ($code === $n && $prev !== null) {
191 $entry = $prev.$prev[0];
192 } else {
193 // 壊れたデータ：ブラウザと同じく、そこまでを表示する
194 break;
195 }
196 $out .= $entry;
197 $outLen += strlen($entry);
198 if ($prev !== null && $n < 4096) {
199 $dict[] = $prev.$entry[0];
200 if ($n + 1 >= (1 << $size) && $size < 12) {
201 $size++;
202 $mask = (1 << $size) - 1;
203 }
204 }
205 $prev = $entry;
206 }
207 return $outLen >= $count ? substr($out, 0, $count) : $out;
208 }
209
210 public function decode(string $data): Bitmap {
211 $s = $this->scan($data, true);
212 $w = $s['width'];
213 $h = $s['height'];
214 $canvas = new Bitmap($w, $h);
215 $img = null;
216 foreach ($s['images'] as $f) {
217 $frame = $this->frame($f);
218 $prevCanvas = $f['dispose'] === 3 ? $canvas->copy() : null;
219 $canvas->draw($frame, $f['x'], $f['y'], true);
220 if ($img === null) $img = $canvas->copy();
221 $img->frames[] = ['bitmap' => $canvas->copy(), 'delay' => $f['delay'] * 10];
222 // 廃棄方法：2 = 背景に戻す（ブラウザと同じく透明）、3 = 前に戻す
223 if ($f['dispose'] === 2) $canvas->clear($f['x'], $f['y'], $f['w'], $f['h']);
224 else if ($f['dispose'] === 3) $canvas = $prevCanvas;
225 }
226 if (count($img->frames) < 2) {
227 $img->frames = [];
228 } else {
229 $img->loops = $s['loops'];
230 }
231 return $img;
232 }
233
234 /**
235 * 1枚の画像をRGBAにする（透明色は透明、足りない画素も透明）
236 */
237 private function frame(array $f): Bitmap {
238 $lut = [];
239 $pal = $f['palette'];
240 $n = intdiv(strlen($pal), 3);
241 for ($i = 0; $i < 256; $i++) {
242 $lut[chr($i)] = $i === $f['transparent'] ? "\0\0\0\0" : ($i < $n ? substr($pal, $i * 3, 3)."\xff" : "\0\0\0\xff");
243 }
244 $count = $f['w'] * $f['h'];
245 $px = strtr($f['indices'], $lut);
246 if (strlen($px) < $count * 4) $px .= str_repeat("\0\0\0\0", $count - intdiv(strlen($px), 4));
247 $rows = str_split($px, $f['w'] * 4);
248 if ($f['interlace']) {
249 // 行の順：8行毎（0から）、8行毎（4から）、4行毎（2から）、2行毎（1から）
250 $order = [];
251 foreach ([[0, 8], [4, 8], [2, 4], [1, 2]] as [$start, $step]) for ($y = $start; $y < $f['h']; $y += $step) $order[] = $y;
252 $sorted = array_fill(0, $f['h'], '');
253 foreach ($order as $i => $y) $sorted[$y] = $rows[$i];
254 $rows = $sorted;
255 }
256 return new Bitmap($f['w'], $f['h'], implode('', $rows));
257 }
258
259 /**
260 * 画素をGIFにする
261 *
262 * 透明（アルファ128未満）は1つの透明色にする。framesがあればアニメーション（全体のパレットを共有）。
263 *
264 * @param array $opt dither：256色を超える場合に誤差拡散を使う（既定false）
265 */
266 public function encode(Bitmap $img, array $opt = []): string {
267 $images = $img->frames ? array_column($img->frames, 'bitmap') : [$img];
268 $w = $img->width;
269 $h = $img->height;
270
271 // 色を数える（透明は1色）
272 $colors = [];
273 $hasAlpha = false;
274 foreach ($images as $f) {
275 if ($f->width !== $w || $f->height !== $h) throw new \InvalidArgumentException('フレームの大きさが画像と違います。');
276 for ($i = 0, $n = strlen($f->data); $i < $n && count($colors) <= 256; $i += 4) {
277 if (ord($f->data[$i + 3]) < 128) {
278 $hasAlpha = true;
279 } else {
280 $colors[substr($f->data, $i, 3)] = true;
281 }
282 }
283 }
284 $max = $hasAlpha ? 255 : 256;
285 $exact = count($colors) <= $max;
286 $palette = $exact ? array_keys($colors) : $this->medianCut($images, $max);
287 if (!$palette) $palette = ["\0\0\0"];
288 $trans = $hasAlpha ? count($palette) : null;
289 if ($hasAlpha) $palette[] = "\0\0\0";
290
291 $bits = 1;
292 while ((1 << $bits) < count($palette)) $bits++;
293 $gct = str_pad(implode('', $palette), 3 << $bits, "\0");
294 $min = max(2, $bits);
295
296 $out = 'GIF89a'.pack('vvCCC', $w, $h, 0x80 | 0x70 | ($bits - 1), 0, 0).$gct;
297 if ($img->frames && $img->loops !== 1) {
298 $out .= "\x21\xff\x0bNETSCAPE2.0\x03\x01".pack('v', $img->loops === 0 ? 0 : min(65535, $img->loops - 1))."\0";
299 }
300 $index = $exact ? array_flip($palette) : null;
301 foreach ($images as $i => $f) {
302 $idx = $exact ? $this->mapExact($f, $index, $trans) : $this->mapNearest($f, $palette, $trans, (bool)($opt['dither'] ?? false));
303 $delay = $img->frames ? (int)round($img->frames[$i]['delay'] / 10) : 0;
304 // 透明があるフレームは、次のフレームの前に消す（前のフレームが透けない様に）
305 $dispose = $img->frames ? ($hasAlpha ? 2 : 1) : 0;
306 if ($img->frames || $hasAlpha) {
307 $out .= "\x21\xf9\x04".chr(($dispose << 2) | ($hasAlpha ? 1 : 0)).pack('v', min(65535, $delay)).chr($trans ?? 0)."\0";
308 }
309 $out .= "\x2c".pack('vvvvC', 0, 0, $w, $h, 0).chr($min);
310 foreach (str_split($this->lzw($idx, $min), 255) as $block) $out .= chr(strlen($block)).$block;
311 $out .= "\0";
312 }
313 return $out."\x3b";
314 }
315
316 private function mapExact(Bitmap $f, array $index, ?int $trans): string {
317 $out = '';
318 for ($i = 0, $n = strlen($f->data); $i < $n; $i += 4) {
319 $out .= ord($f->data[$i + 3]) < 128 ? chr($trans) : chr($index[substr($f->data, $i, 3)]);
320 }
321 return $out;
322 }
323
324 /**
325 * 一番近い色にする（5ビット毎にまとめた色で探した結果を覚えておく）
326 */
327 private function mapNearest(Bitmap $f, array $palette, ?int $trans, bool $dither): string {
328 $pal = array_map(fn($c) => [ord($c[0]), ord($c[1]), ord($c[2])], $palette);
329 if ($trans !== null) array_pop($pal);
330 $cache = [];
331 $nearest = function(int $r, int $g, int $b) use ($pal, &$cache): int {
332 $key = (($r >> 3) << 10) | (($g >> 3) << 5) | ($b >> 3);
333 if (isset($cache[$key])) return $cache[$key];
334 $best = 0;
335 $bd = PHP_INT_MAX;
336 foreach ($pal as $i => [$pr, $pg, $pb]) {
337 $dr = $pr - $r;
338 $dg = $pg - $g;
339 $db = $pb - $b;
340 $d = 2 * $dr * $dr + 4 * $dg * $dg + 3 * $db * $db;
341 if ($d < $bd) {
342 $bd = $d;
343 $best = $i;
344 }
345 }
346 return $cache[$key] = $best;
347 };
348 $w = $f->width;
349 $out = '';
350 $err = $dither ? [array_fill(0, $w * 3 + 6, 0), array_fill(0, $w * 3 + 6, 0)] : null;
351 for ($y = 0; $y < $f->height; $y++) {
352 $row = $f->row($y);
353 if ($dither) {
354 $cur = $err[0];
355 $next = array_fill(0, $w * 3 + 6, 0);
356 }
357 for ($x = 0; $x < $w; $x++) {
358 $o = $x * 4;
359 if (ord($row[$o + 3]) < 128) {
360 $out .= chr($trans);
361 continue;
362 }
363 $c = [ord($row[$o]), ord($row[$o + 1]), ord($row[$o + 2])];
364 if ($dither) for ($k = 0; $k < 3; $k++) $c[$k] = max(0, min(255, $c[$k] + intdiv($cur[3 + $x * 3 + $k], 16)));
365 $i = $nearest($c[0], $c[1], $c[2]);
366 $out .= chr($i);
367 if ($dither) {
368 // Floyd–Steinberg：右7、左下3、下5、右下1
369 for ($k = 0; $k < 3; $k++) {
370 $e = $c[$k] - $pal[$i][$k];
371 $cur[3 + ($x + 1) * 3 + $k] += $e * 7;
372 $next[3 + ($x - 1) * 3 + $k] += $e * 3;
373 $next[3 + $x * 3 + $k] += $e * 5;
374 $next[3 + ($x + 1) * 3 + $k] += $e;
375 }
376 }
377 }
378 if ($dither) $err[0] = $next;
379 }
380 return $out;
381 }
382
383 /**
384 * メディアンカットで減色する
385 *
386 * @return array 色（3バイトの文字列）
387 */
388 private function medianCut(array $images, int $max): array {
389 // 多過ぎる場合は間引く
390 $total = 0;
391 foreach ($images as $f) $total += $f->width * $f->height;
392 $step = max(1, intdiv($total, 200000));
393 $px = [];
394 $k = 0;
395 foreach ($images as $f) {
396 for ($i = 0, $n = strlen($f->data); $i < $n; $i += 4) {
397 if ($k++ % $step || ord($f->data[$i + 3]) < 128) continue;
398 $px[] = (ord($f->data[$i]) << 16) | (ord($f->data[$i + 1]) << 8) | ord($f->data[$i + 2]);
399 }
400 }
401 if (!$px) return [];
402 // 箱：[色, 一番広い色の軸, 分ける優先度]（範囲は箱を作る時に1回だけ計算する）
403 $measure = function(array $box): array {
404 $best = -1;
405 $ch = 0;
406 foreach ([16, 8, 0] as $sh) {
407 $lo = 255;
408 $hi = 0;
409 foreach ($box as $c) {
410 $v = ($c >> $sh) & 255;
411 if ($v < $lo) $lo = $v;
412 if ($v > $hi) $hi = $v;
413 }
414 if ($hi - $lo > $best) {
415 $best = $hi - $lo;
416 $ch = $sh;
417 }
418 }
419 return [$box, $ch, count($box) > 1 ? $best * count($box) : 0];
420 };
421 $boxes = [$measure($px)];
422 while (count($boxes) < $max) {
423 $bi = -1;
424 $top = 0;
425 foreach ($boxes as $i => [, , $score]) {
426 if ($score > $top) {
427 $top = $score;
428 $bi = $i;
429 }
430 }
431 if ($bi < 0) break;
432 [$box, $ch] = $boxes[$bi];
433 // 1つの軸（8ビット）で並べる：数え上げソート
434 $buckets = array_fill(0, 256, []);
435 foreach ($box as $c) $buckets[($c >> $ch) & 255][] = $c;
436 $box = array_merge(...$buckets);
437 $mid = intdiv(count($box), 2);
438 array_splice($boxes, $bi, 1, [$measure(array_slice($box, 0, $mid)), $measure(array_slice($box, $mid))]);
439 }
440 $boxes = array_column($boxes, 0);
441 return array_map(function($box) {
442 $r = $g = $b = 0;
443 foreach ($box as $c) {
444 $r += ($c >> 16) & 255;
445 $g += ($c >> 8) & 255;
446 $b += $c & 255;
447 }
448 $n = count($box);
449 return chr(intdiv($r + ($n >> 1), $n)).chr(intdiv($g + ($n >> 1), $n)).chr(intdiv($b + ($n >> 1), $n));
450 }, $boxes);
451 }
452
453 /**
454 * LZWで圧縮する
455 */
456 private function lzw(string $idx, int $min): string {
457 $clear = 1 << $min;
458 $eoi = $clear + 1;
459 $size = $min + 1;
460 $next = $clear + 2;
461 $dict = [];
462 $out = '';
463 $buf = $bits = 0;
464 $emit = function(int $code) use (&$buf, &$bits, &$out, &$size): void {
465 $buf |= $code << $bits;
466 $bits += $size;
467 while ($bits >= 8) {
468 $out .= chr($buf & 255);
469 $buf >>= 8;
470 $bits -= 8;
471 }
472 };
473 $emit($clear);
474 $n = strlen($idx);
475 if ($n === 0) {
476 $emit($eoi);
477 return $out.($bits > 0 ? chr($buf & 255) : '');
478 }
479 $w = $idx[0];
480 for ($i = 1; $i < $n; $i++) {
481 $c = $idx[$i];
482 $wc = $w.$c;
483 if (isset($dict[$wc])) {
484 $w = $wc;
485 continue;
486 }
487 $emit(strlen($w) === 1 ? ord($w) : $dict[$w]);
488 if ($next < 4096) {
489 $dict[$wc] = $next++;
490 if ($next > (1 << $size) && $size < 12) $size++;
491 } else {
492 // 辞書が一杯：クリアして最初から
493 $emit($clear);
494 $dict = [];
495 $size = $min + 1;
496 $next = $clear + 2;
497 }
498 $w = $c;
499 }
500 $emit(strlen($w) === 1 ? ord($w) : $dict[$w]);
501 $emit($eoi);
502 return $out.($bits > 0 ? chr($buf & 255) : '');
503 }
504}