nx_webp_vp8l.nx source
↩ module page · 404 lines · 16319 B
1// nx_webp_vp8l.nx -- sovereign WebP VP8L (lossless) pixel decoder.
2//
3// THE LAST MILE. WebP already reaches four layers deep in this tree: sniffed
4// by nx_media_sniff, sized by nx_img_dims, negotiated by nx_cms_image and
5// transfer-validated by nx_manga_get. Nothing turned the bitstream into
6// pixels. This does.
7//
8// VP8L is, in order: a 5-byte header, an optional stack of up to 4 reversible
9// transforms, an optional colour cache, an optional meta-Huffman image that
10// selects which of N Huffman groups applies to each 2^k block, and then one
11// LZ77 stream over ARGB pixels. Decode runs the stream, then UNDOES the
12// transforms in reverse order.
13//
14// Composes: nx_bitstream (LSB-first, matches VP8L exactly), nx_webp_huff
15// (canonical trees incl. the zero-bit single-symbol case).
16//
17// genealogy_id: webp_lossless_bitstream_spec_2012
18// lineage_id: nx_webp_vp8l_v1
19// license_tier: ORIGINAL
20
21import "nx_syscalls.nx"
22import "nx_bitstream.nx"
23import "nx_huffman.nx"
24import "nx_webp_huff.nx"
25
26// ===== spec constants =============================================
27
28const NX_VP8L_SIG: i64 = 0x2f
29const NX_VP8L_NUM_LIT: i64 = 256
30const NX_VP8L_NUM_LEN: i64 = 24
31const NX_VP8L_NUM_DIST: i64 = 40
32const NX_VP8L_GROUP_SIZE: i64 = 5
33const NX_VP8L_PLANE_CODES: i64 = 120
34const NX_VP8L_BLACK: i64 = 0xff000000
35const NX_VP8L_CACHE_MUL: i64 = 0x1e35a7bd
36const NX_VP8L_U32: i64 = 0xffffffff
37
38const NX_VP8L_XF_PREDICT: i64 = 0
39const NX_VP8L_XF_COLOR: i64 = 1
40const NX_VP8L_XF_SUBGREEN: i64 = 2
41const NX_VP8L_XF_PALETTE: i64 = 3
42const NX_VP8L_XF_COUNT: i64 = 4
43
44// ===== small helpers ==============================================
45
46func vl_min(a: i64, b: i64) -> i64 { if a < b { return a } return b }
47
48func vl_abs(a: i64) -> i64 { if a < 0 { return 0 - a } return a }
49
50func vl_clip255(v: i64) -> i64 {
51 if v < 0 { return 0 }
52 if v > 255 { return 255 }
53 return v
54}
55
56// ceil(a / 2^b) -- the spec block-count rule for sub-images
57func vl_subsample_size(size: i64, bits: i64) -> i64 {
58 return (size + (1 << bits) - 1) >> bits
59}
60
61func vl_chan(argb: i64, shift: i64) -> i64 { return (argb >> shift) & 255 }
62
63func vl_argb(a: i64, r: i64, g: i64, b: i64) -> i64 {
64 return ((a & 255) << 24) | ((r & 255) << 16) | ((g & 255) << 8) | (b & 255)
65}
66
67// per-channel average of two ARGB pixels, no float, no overflow
68func vl_average2(a: i64, b: i64) -> i64 {
69 let x: i64 = a & NX_VP8L_U32
70 let y: i64 = b & NX_VP8L_U32
71 return ((((x ^ y) & 0xfefefefe) >> 1) + (x & y)) & NX_VP8L_U32
72}
73
74// ===== the 14 predictors ==========================================
75//
76// t = top, l = left, tl = top-left, tr = top-right. Modes 11..13 are the
77// non-linear ones (Select and the two clamped add-subtracts) that give VP8L
78// most of its edge over PNG's Paeth.
79
80func vl_sub3(a: i64, b: i64, c: i64) -> i64 {
81 let pbc: i64 = b - c
82 let pca: i64 = a - c
83 return vl_abs(pbc) - vl_abs(pca)
84}
85
86func vl_select(t: i64, l: i64, tl: i64) -> i64 {
87 var d: i64 = vl_sub3(vl_chan(t, 24), vl_chan(l, 24), vl_chan(tl, 24))
88 d = d + vl_sub3(vl_chan(t, 16), vl_chan(l, 16), vl_chan(tl, 16))
89 d = d + vl_sub3(vl_chan(t, 8), vl_chan(l, 8), vl_chan(tl, 8))
90 d = d + vl_sub3(vl_chan(t, 0), vl_chan(l, 0), vl_chan(tl, 0))
91 if d <= 0 { return t }
92 return l
93}
94
95func vl_clamp_add_sub_full(c0: i64, c1: i64, c2: i64) -> i64 {
96 let a: i64 = vl_clip255(vl_chan(c0, 24) + vl_chan(c1, 24) - vl_chan(c2, 24))
97 let r: i64 = vl_clip255(vl_chan(c0, 16) + vl_chan(c1, 16) - vl_chan(c2, 16))
98 let g: i64 = vl_clip255(vl_chan(c0, 8) + vl_chan(c1, 8) - vl_chan(c2, 8))
99 let b: i64 = vl_clip255(vl_chan(c0, 0) + vl_chan(c1, 0) - vl_chan(c2, 0))
100 return vl_argb(a, r, g, b)
101}
102
103func vl_add_sub_half(a: i64, b: i64) -> i64 {
104 return vl_clip255(a + (a - b) / 2)
105}
106
107func vl_clamp_add_sub_half(c0: i64, c1: i64, c2: i64) -> i64 {
108 let ave: i64 = vl_average2(c0, c1)
109 let a: i64 = vl_add_sub_half(vl_chan(ave, 24), vl_chan(c2, 24))
110 let r: i64 = vl_add_sub_half(vl_chan(ave, 16), vl_chan(c2, 16))
111 let g: i64 = vl_add_sub_half(vl_chan(ave, 8), vl_chan(c2, 8))
112 let b: i64 = vl_add_sub_half(vl_chan(ave, 0), vl_chan(c2, 0))
113 return vl_argb(a, r, g, b)
114}
115
116func vl_predict(mode: i64, l: i64, t: i64, tl: i64, tr: i64) -> i64 {
117 if mode == 0 { return NX_VP8L_BLACK }
118 if mode == 1 { return l }
119 if mode == 2 { return t }
120 if mode == 3 { return tr }
121 if mode == 4 { return tl }
122 if mode == 5 { return vl_average2(vl_average2(l, tr), t) }
123 if mode == 6 { return vl_average2(l, tl) }
124 if mode == 7 { return vl_average2(l, t) }
125 if mode == 8 { return vl_average2(tl, t) }
126 if mode == 9 { return vl_average2(t, tr) }
127 if mode == 10 { return vl_average2(vl_average2(l, tl), vl_average2(t, tr)) }
128 if mode == 11 { return vl_select(t, l, tl) }
129 if mode == 12 { return vl_clamp_add_sub_full(l, t, tl) }
130 return vl_clamp_add_sub_half(l, t, tl)
131}
132
133// ===== distance code -> pixel distance ============================
134//
135// The first 120 distance codes address a small 2-D neighbourhood rather than
136// a linear run, which is what lets VP8L reference the pixel directly above
137// cheaply. Codes above that are plain linear distances.
138
139func vl_plane_table(out: *i64) -> i64 {
140 out[0]=0x18; out[1]=0x07; out[2]=0x17; out[3]=0x19; out[4]=0x28
141 out[5]=0x06; out[6]=0x27; out[7]=0x29; out[8]=0x16; out[9]=0x1a
142 out[10]=0x26; out[11]=0x2a; out[12]=0x38; out[13]=0x05; out[14]=0x37
143 out[15]=0x39; out[16]=0x15; out[17]=0x1b; out[18]=0x36; out[19]=0x3a
144 out[20]=0x25; out[21]=0x2b; out[22]=0x48; out[23]=0x04; out[24]=0x47
145 out[25]=0x49; out[26]=0x14; out[27]=0x1c; out[28]=0x35; out[29]=0x3b
146 out[30]=0x46; out[31]=0x4a; out[32]=0x24; out[33]=0x2c; out[34]=0x58
147 out[35]=0x45; out[36]=0x4b; out[37]=0x34; out[38]=0x3c; out[39]=0x03
148 out[40]=0x57; out[41]=0x59; out[42]=0x13; out[43]=0x1d; out[44]=0x56
149 out[45]=0x5a; out[46]=0x23; out[47]=0x2d; out[48]=0x44; out[49]=0x4c
150 out[50]=0x55; out[51]=0x5b; out[52]=0x33; out[53]=0x3d; out[54]=0x68
151 out[55]=0x02; out[56]=0x67; out[57]=0x69; out[58]=0x12; out[59]=0x1e
152 out[60]=0x66; out[61]=0x6a; out[62]=0x22; out[63]=0x2e; out[64]=0x54
153 out[65]=0x5c; out[66]=0x43; out[67]=0x4d; out[68]=0x65; out[69]=0x6b
154 out[70]=0x32; out[71]=0x3e; out[72]=0x78; out[73]=0x01; out[74]=0x77
155 out[75]=0x79; out[76]=0x53; out[77]=0x5d; out[78]=0x11; out[79]=0x1f
156 out[80]=0x64; out[81]=0x6c; out[82]=0x42; out[83]=0x4e; out[84]=0x76
157 out[85]=0x7a; out[86]=0x21; out[87]=0x2f; out[88]=0x75; out[89]=0x7b
158 out[90]=0x31; out[91]=0x3f; out[92]=0x63; out[93]=0x6d; out[94]=0x52
159 out[95]=0x5e; out[96]=0x00; out[97]=0x74; out[98]=0x7c; out[99]=0x41
160 out[100]=0x4f; out[101]=0x10; out[102]=0x20; out[103]=0x62; out[104]=0x6e
161 out[105]=0x30; out[106]=0x73; out[107]=0x7d; out[108]=0x51; out[109]=0x5f
162 out[110]=0x40; out[111]=0x72; out[112]=0x7e; out[113]=0x61; out[114]=0x6f
163 out[115]=0x50; out[116]=0x71; out[117]=0x7f; out[118]=0x60; out[119]=0x70
164 return NX_VP8L_PLANE_CODES
165}
166
167func vl_dist_map(plane: *i64, dist_code: i64, xsize: i64) -> i64 {
168 if dist_code > NX_VP8L_PLANE_CODES { return dist_code - NX_VP8L_PLANE_CODES }
169 let code: i64 = plane[dist_code - 1]
170 let yoffset: i64 = code >> 4
171 let xoffset: i64 = 8 - (code & 0xf)
172 let dist: i64 = yoffset * xsize + xoffset
173 if dist < 1 { return 1 }
174 return dist
175}
176
177// ===== prefix-coded length / distance =============================
178//
179// Codes 0..3 are literal; above that the code splits into an offset and a
180// run of extra bits. Same rule for both length and distance alphabets.
181
182func vl_prefix_value(bs: *NxBitStream, prefix: i64) -> i64 {
183 if prefix < 4 { return prefix + 1 }
184 let extra_bits: i64 = (prefix - 2) >> 1
185 let offset: i64 = (2 + (prefix & 1)) << extra_bits
186 return offset + nx_bitstream_read_lsb(bs, extra_bits) + 1
187}
188
189// ===== colour cache ===============================================
190
191func vl_cache_index(argb: i64, bits: i64) -> i64 {
192 let v: i64 = (NX_VP8L_CACHE_MUL * (argb & NX_VP8L_U32)) & NX_VP8L_U32
193 return v >> (32 - bits)
194}
195
196// ===== the entropy-coded pixel stream =============================
197//
198// One pass over width*height ARGB pixels. Three outcomes per symbol:
199// < 256 a green literal, followed by red, blue, alpha literals
200// 256..279 an LZ77 length, then a distance -> copy a back-reference
201// >= 280 a colour-cache hit
202//
203// `groups` holds n_groups * 5 trees; `meta` (may be 0) selects the group
204// per block of 2^meta_bits pixels.
205
206func vl_decode_pixels(bs: *NxBitStream, out: *i64, width: i64, height: i64,
207 groups: *i64, meta: *i64, meta_bits: i64, meta_w: i64,
208 cache_bits: i64, plane: *i64) -> i64 {
209 let npix: i64 = width * height
210 var cache: *i64 = 0 as *i64
211 var cache_size: i64 = 0
212 if cache_bits > 0 {
213 cache_size = 1 << cache_bits
214 cache = sys_mmap(cache_size * 8 + 64) as *i64
215 var ci: i64 = 0
216 while ci < cache_size { cache[ci] = 0; ci = ci + 1 }
217 }
218
219 var pos: i64 = 0
220 var x: i64 = 0
221 var y: i64 = 0
222 var ok: i64 = 1
223 var go: i64 = 1
224
225 while go == 1 {
226 if pos >= npix { go = 0 } else {
227 // select the Huffman group for this pixel block
228 var g: i64 = 0
229 if meta != (0 as *i64) {
230 let mx: i64 = x >> meta_bits
231 let my: i64 = y >> meta_bits
232 g = meta[my * meta_w + mx]
233 }
234 let base: i64 = g * NX_VP8L_GROUP_SIZE
235 let t_green: *NxWlTree = groups[base] as *NxWlTree
236 let sym: i64 = wl_decode_symbol(t_green, bs)
237
238 if sym < 0 { ok = 0; go = 0 } else {
239 if sym < NX_VP8L_NUM_LIT {
240 // literal ARGB: green came first, then red, blue, alpha
241 let t_red: *NxWlTree = groups[base + 1] as *NxWlTree
242 let t_blue: *NxWlTree = groups[base + 2] as *NxWlTree
243 let t_alpha: *NxWlTree = groups[base + 3] as *NxWlTree
244 let r: i64 = wl_decode_symbol(t_red, bs)
245 let b: i64 = wl_decode_symbol(t_blue, bs)
246 let a: i64 = wl_decode_symbol(t_alpha, bs)
247 if r < 0 { ok = 0; go = 0 } else {
248 if b < 0 { ok = 0; go = 0 } else {
249 if a < 0 { ok = 0; go = 0 } else {
250 let px: i64 = vl_argb(a, r, sym, b)
251 out[pos] = px
252 if cache_bits > 0 { cache[vl_cache_index(px, cache_bits)] = px }
253 pos = pos + 1
254 x = x + 1
255 if x >= width { x = 0; y = y + 1 }
256 } } }
257 } else {
258 if sym < NX_VP8L_NUM_LIT + NX_VP8L_NUM_LEN {
259 // LZ77 back-reference
260 let length: i64 = vl_prefix_value(bs, sym - NX_VP8L_NUM_LIT)
261 let t_dist: *NxWlTree = groups[base + 4] as *NxWlTree
262 let dsym: i64 = wl_decode_symbol(t_dist, bs)
263 if dsym < 0 { ok = 0; go = 0 } else {
264 let dist_code: i64 = vl_prefix_value(bs, dsym)
265 let dist: i64 = vl_dist_map(plane, dist_code, width)
266 if dist > pos { ok = 0; go = 0 } else {
267 if pos + length > npix { ok = 0; go = 0 } else {
268 var k: i64 = 0
269 while k < length {
270 let px: i64 = out[pos - dist]
271 out[pos] = px
272 if cache_bits > 0 { cache[vl_cache_index(px, cache_bits)] = px }
273 pos = pos + 1
274 x = x + 1
275 if x >= width { x = 0; y = y + 1 }
276 k = k + 1
277 }
278 } }
279 }
280 } else {
281 // colour-cache hit
282 if cache_bits <= 0 { ok = 0; go = 0 } else {
283 let idx: i64 = sym - NX_VP8L_NUM_LIT - NX_VP8L_NUM_LEN
284 if idx >= cache_size { ok = 0; go = 0 } else {
285 out[pos] = cache[idx]
286 pos = pos + 1
287 x = x + 1
288 if x >= width { x = 0; y = y + 1 }
289 }
290 }
291 } } }
292 }
293 }
294 if bs.overflow == 1 { return 0 }
295 return ok
296}
297
298// ===== inverse transforms =========================================
299//
300// Applied in REVERSE of the order they were read. Each one is its own
301// function so a future encoder can share them and so a failure is
302// attributable to a single transform rather than to a fused pass.
303
304func vl_inv_subtract_green(argb: *i64, npix: i64) -> i64 {
305 var i: i64 = 0
306 while i < npix {
307 let p: i64 = argb[i]
308 let g: i64 = vl_chan(p, 8)
309 let r: i64 = (vl_chan(p, 16) + g) & 255
310 let b: i64 = (vl_chan(p, 0) + g) & 255
311 argb[i] = vl_argb(vl_chan(p, 24), r, g, b)
312 i = i + 1
313 }
314 return 1
315}
316
317func vl_inv_predict(argb: *i64, w: i64, h: i64, bits: i64, sub: *i64) -> i64 {
318 let tiles_w: i64 = vl_subsample_size(w, bits)
319 // pixel 0 is predicted from opaque black; the rest of row 0 from the left;
320 // column 0 of every other row from the pixel above.
321 argb[0] = (argb[0] + NX_VP8L_BLACK) & NX_VP8L_U32
322 var x: i64 = 1
323 while x < w {
324 argb[x] = (argb[x] + argb[x - 1]) & NX_VP8L_U32
325 x = x + 1
326 }
327 var y: i64 = 1
328 while y < h {
329 let row: i64 = y * w
330 argb[row] = (argb[row] + argb[row - w]) & NX_VP8L_U32
331 x = 1
332 while x < w {
333 let mode: i64 = vl_chan(sub[(y >> bits) * tiles_w + (x >> bits)], 8)
334 let l: i64 = argb[row + x - 1]
335 let t: i64 = argb[row + x - w]
336 let tl: i64 = argb[row + x - w - 1]
337 var tr: i64 = t
338 if x + 1 < w { tr = argb[row + x - w + 1] }
339 let pred: i64 = vl_predict(mode, l, t, tl, tr)
340 let cur: i64 = argb[row + x]
341 let a: i64 = (vl_chan(cur, 24) + vl_chan(pred, 24)) & 255
342 let r: i64 = (vl_chan(cur, 16) + vl_chan(pred, 16)) & 255
343 let g: i64 = (vl_chan(cur, 8) + vl_chan(pred, 8)) & 255
344 let b: i64 = (vl_chan(cur, 0) + vl_chan(pred, 0)) & 255
345 argb[row + x] = vl_argb(a, r, g, b)
346 x = x + 1
347 }
348 y = y + 1
349 }
350 return 1
351}
352
353// signed 8-bit reading of a colour-transform element
354func vl_s8(v: i64) -> i64 {
355 let m: i64 = v & 255
356 if m >= 128 { return m - 256 }
357 return m
358}
359
360func vl_inv_color(argb: *i64, w: i64, h: i64, bits: i64, sub: *i64) -> i64 {
361 let tiles_w: i64 = vl_subsample_size(w, bits)
362 var y: i64 = 0
363 while y < h {
364 var x: i64 = 0
365 while x < w {
366 let t: i64 = sub[(y >> bits) * tiles_w + (x >> bits)]
367 let g2r: i64 = vl_s8(vl_chan(t, 0))
368 let g2b: i64 = vl_s8(vl_chan(t, 8))
369 let r2b: i64 = vl_s8(vl_chan(t, 16))
370 let p: i64 = argb[y * w + x]
371 let g: i64 = vl_chan(p, 8)
372 var r: i64 = vl_chan(p, 16)
373 var b: i64 = vl_chan(p, 0)
374 r = (r + ((g2r * ((g << 24) >> 24)) >> 5)) & 255
375 b = (b + ((g2b * ((g << 24) >> 24)) >> 5)) & 255
376 b = (b + ((r2b * ((r << 24) >> 24)) >> 5)) & 255
377 argb[y * w + x] = vl_argb(vl_chan(p, 24), r, g, b)
378 x = x + 1
379 }
380 y = y + 1
381 }
382 return 1
383}
384
385// ===== header ====================================================
386//
387// Returns 1 and fills wh[0]=width wh[1]=height when the 5-byte VP8L header
388// is well formed. A wrong signature or a non-zero version is REFUSED rather
389// than guessed at -- a wrong answer is worse than an absent one.
390
391func vp8l_read_header(bs: *NxBitStream, wh: *i64) -> i64 {
392 let sig: i64 = nx_bitstream_read_lsb(bs, 8)
393 if sig != NX_VP8L_SIG { return 0 }
394 let w: i64 = nx_bitstream_read_lsb(bs, 14) + 1
395 let h: i64 = nx_bitstream_read_lsb(bs, 14) + 1
396 let alpha: i64 = nx_bitstream_read_lsb(bs, 1)
397 let version: i64 = nx_bitstream_read_lsb(bs, 3)
398 if version != 0 { return 0 }
399 if bs.overflow == 1 { return 0 }
400 wh[0] = w
401 wh[1] = h
402 wh[2] = alpha
403 return 1
404}