1/**
2 * A minimal animated GIF (GIF89a) encoder: one global palette of 256 colors,
3 * frames of palette indices, LZW compression, and an infinite loop.
4 */
6/** Encode frames (width x height palette indices each) with palette (256 x RGB) and a delay per frame in 1/100 s. */
7export function encodeGif(width: number, height: number, palette: Uint8Array, frames: Uint8Array[], delayCs: number): Uint8Array {
8 const out = new ByteWriter();
9 out.str('GIF89a');
10 out.u16(width);
11 out.u16(height);
12 out.byte(0xf7); // global color table, 8 bits per color, 256 entries
13 out.byte(0); // background color index
14 out.byte(0); // pixel aspect ratio
15 for (let i = 0; i < 768; i++) out.byte(palette[i] ?? 0);
16 if (frames.length > 1) {
17 // NETSCAPE2.0 application extension: loop forever
18 out.bytes([0x21, 0xff, 0x0b]);
19 out.str('NETSCAPE2.0');
20 out.bytes([0x03, 0x01, 0x00, 0x00, 0x00]);
21 }
22 for (const f of frames) {
23 out.bytes([0x21, 0xf9, 0x04, 0x00]); // graphic control extension, no transparency
24 out.u16(delayCs);
25 out.bytes([0x00, 0x00]);
26 out.byte(0x2c); // image descriptor
27 out.u16(0);
28 out.u16(0);
29 out.u16(width);
30 out.u16(height);
31 out.byte(0); // no local color table, not interlaced
32 lzw(f, 8, out);
33 }
34 out.byte(0x3b);
35 return out.result();
36}
38class ByteWriter {
39 private buf = new Uint8Array(1 << 16);
40 private n = 0;
42 byte(b: number) {
43 if (this.n === this.buf.length) {
44 const nb = new Uint8Array(2 * this.buf.length);
45 nb.set(this.buf);
46 this.buf = nb;
47 }
48 this.buf[this.n++] = b;
49 }
50 bytes(bs: number[]) {
51 for (const b of bs) this.byte(b);
52 }
53 u16(v: number) {
54 this.byte(v & 0xff);
55 this.byte((v >> 8) & 0xff);
56 }
57 str(s: string) {
58 for (let i = 0; i < s.length; i++) this.byte(s.charCodeAt(i));
59 }
60 result(): Uint8Array {
61 return this.buf.slice(0, this.n);
62 }
63}
65/** LZW-compress indices into GIF image data sub-blocks. */
66function lzw(indices: Uint8Array, minCodeSize: number, out: ByteWriter) {
67 out.byte(minCodeSize);
68 const clear = 1 << minCodeSize;
69 const eoi = clear + 1;
70 let codeSize = minCodeSize + 1;
71 let next = eoi + 1;
72 // dictionary: (prefix code << 8 | byte) -> code
73 const dict = new Map<number, number>();
74 const block: number[] = [];
75 let acc = 0;
76 let nbits = 0;
77 const emit = (code: number) => {
78 acc |= code << nbits;
79 nbits += codeSize;
80 while (nbits >= 8) {
81 block.push(acc & 0xff);
82 acc >>>= 8;
83 nbits -= 8;
84 if (block.length === 255) {
85 out.byte(255);
86 out.bytes(block);
87 block.length = 0;
88 }
89 }
90 };
91 emit(clear);
92 let prefix = indices[0];
93 for (let i = 1; i < indices.length; i++) {
94 const c = indices[i];
95 const key = (prefix << 8) | c;
96 const code = dict.get(key);
97 if (code !== undefined) {
98 prefix = code;
99 continue;
100 }
101 emit(prefix);
102 if (next < 4096) {
103 dict.set(key, next++);
104 // the decoder widens its codes one code later than the encoder adds the entry
105 if (next > 1 << codeSize && codeSize < 12) codeSize++;
106 } else {
107 emit(clear);
108 dict.clear();
109 codeSize = minCodeSize + 1;
110 next = eoi + 1;
111 }
112 prefix = c;
113 }
114 emit(prefix);
115 emit(eoi);
116 if (nbits > 0) block.push(acc & 0xff);
117 if (block.length) {
118 out.byte(block.length);
119 out.bytes(block);
120 }
121 out.byte(0);
122}