nx_vp8.nx source
↩ module page · 218 lines · 7084 B
1// nx_vp8.nx -- VP8 lossy: the boolean entropy decoder and keyframe header.
2//
3// The last missing piece of WebP. VP8's entropy coder is a BINARY arithmetic
4// coder -- one bit per call against an 8-bit probability -- which is a
5// different animal from VP8L's canonical Huffman and from AV1's multi-symbol
6// CDF coder. All three now exist in this tree and none substitutes for
7// another.
8//
9// PROBABILITY 128 IS A RAW BIT. With prob 128 the split lands exactly at the
10// midpoint, so the coder degenerates to reading the bitstream MSB-first. That
11// is not a curiosity -- it is the property that makes the renormalisation
12// loop testable without an encoder: decode a run of prob-128 literals and
13// they must reproduce the raw bits exactly. Any error in the shift, the carry
14// or the byte refill breaks it immediately.
15//
16// THE RANGE INVARIANT. After every decode the range must satisfy
17// 128 <= range <= 255. A renormalisation loop that under- or over-shifts
18// still returns plausible bits for a while and then diverges; asserting the
19// invariant after every call catches it at the first bit rather than the
20// thousandth.
21//
22// THE START CODE IS NOT OPTIONAL. A keyframe carries 9d 01 2a after the
23// 3-byte tag. Skipping the check means a corrupt or non-VP8 payload is
24// decoded as if it were a frame, with dimensions read out of arbitrary bytes.
25//
26// genealogy_id: vp8_rfc6386
27// lineage_id: nx_vp8_v1
28// license_tier: ORIGINAL
29
30import "nx_syscalls.nx"
31const NX_MAGIC_16383: i64 = 16383
32
33const NX_VP8_BD_BYTES: i64 = 48
34
35const NX_VP8_FLD_KEYFRAME: i64 = 0
36const NX_VP8_FLD_VERSION: i64 = 1
37const NX_VP8_FLD_SHOW: i64 = 2
38const NX_VP8_FLD_PART1LEN: i64 = 3
39const NX_VP8_FLD_WIDTH: i64 = 4
40const NX_VP8_FLD_HEIGHT: i64 = 5
41const NX_VP8_FLD_HSCALE: i64 = 6
42const NX_VP8_FLD_VSCALE: i64 = 7
43const NX_VP8_FLD_HDRLEN: i64 = 8
44
45struct NxVp8Bool {
46 data: i64,
47 size: i64,
48 pos: i64,
49 value: i64,
50 range: i64,
51 bit_count: i64,
52 overflow: i64,
53}
54
55func nx_vp8_at(d: *u8, i: i64) -> i64 { return (d[i] as i64) & 255 }
56
57// ===== boolean decoder ============================================
58
59func nx_vp8_bool_init(d: *u8, n: i64, off: i64) -> *NxVp8Bool {
60 if off + 2 > n { return 0 as *NxVp8Bool }
61 let b: *NxVp8Bool = sys_mmap(NX_VP8_BD_BYTES) as *NxVp8Bool
62 b.data = d as i64
63 b.size = n
64 b.pos = off + 2
65 b.value = (nx_vp8_at(d, off) << 8) | nx_vp8_at(d, off + 1)
66 b.range = 255
67 b.bit_count = 0
68 b.overflow = 0
69 return b
70}
71
72func nx_vp8_bool_get(b: *NxVp8Bool, prob: i64) -> i64 {
73 if b == (0 as *NxVp8Bool) { return 0 }
74 if prob < 0 { return 0 }
75 if prob > 255 { return 0 }
76 let d: *u8 = b.data as *u8
77
78 let split: i64 = 1 + (((b.range - 1) * prob) >> 8)
79 let bigsplit: i64 = split << 8
80 var bit: i64 = 0
81 if b.value >= bigsplit {
82 bit = 1
83 b.range = b.range - split
84 b.value = b.value - bigsplit
85 } else {
86 b.range = split
87 }
88
89 // renormalise: keep the range in [128, 255], refilling a byte every 8 shifts
90 var go: i64 = 1
91 while go == 1 {
92 if b.range >= 128 { go = 0 } else {
93 b.value = (b.value << 1) & 0xffff
94 b.range = b.range << 1
95 b.bit_count = b.bit_count + 1
96 if b.bit_count == 8 {
97 b.bit_count = 0
98 if b.pos < b.size {
99 b.value = b.value | nx_vp8_at(d, b.pos)
100 b.pos = b.pos + 1
101 } else {
102 b.overflow = 1
103 }
104 }
105 }
106 }
107 return bit
108}
109
110// an unbiased bit -- and, at prob 128, exactly the next raw stream bit
111func nx_vp8_bool_bit(b: *NxVp8Bool) -> i64 {
112 return nx_vp8_bool_get(b, 128)
113}
114
115// n unbiased bits, most significant first
116func nx_vp8_bool_literal(b: *NxVp8Bool, n: i64) -> i64 {
117 if n <= 0 { return 0 }
118 if n > 32 { return 0 }
119 var v: i64 = 0
120 var i: i64 = 0
121 while i < n {
122 v = (v << 1) | nx_vp8_bool_bit(b)
123 i = i + 1
124 }
125 return v
126}
127
128// a magnitude then a sign bit, as VP8 codes its deltas
129func nx_vp8_bool_signed(b: *NxVp8Bool, n: i64) -> i64 {
130 let v: i64 = nx_vp8_bool_literal(b, n)
131 if nx_vp8_bool_bit(b) == 1 { return 0 - v }
132 return v
133}
134
135// an optional signed value, gated by a flag
136func nx_vp8_bool_maybe_signed(b: *NxVp8Bool, n: i64) -> i64 {
137 if nx_vp8_bool_bit(b) == 0 { return 0 }
138 return nx_vp8_bool_signed(b, n)
139}
140
141// ===== the uncompressed frame header ==============================
142//
143// Three tag bytes, then for a keyframe a 3-byte start code and two 2-byte
144// dimension codes, each carrying a 14-bit size and a 2-bit scale.
145
146func nx_vp8_frame_parse(d: *u8, n: i64, fld: *i64) -> i64 {
147 if n < 3 { return 0 }
148 let tag: i64 = nx_vp8_at(d, 0) | (nx_vp8_at(d, 1) << 8) | (nx_vp8_at(d, 2) << 16)
149 let keyframe: i64 = 1 - (tag & 1)
150 let version: i64 = (tag >> 1) & 7
151 let show: i64 = (tag >> 4) & 1
152 let part1: i64 = (tag >> 5) & 0x7ffff
153
154 fld[NX_VP8_FLD_KEYFRAME] = keyframe
155 fld[NX_VP8_FLD_VERSION] = version
156 fld[NX_VP8_FLD_SHOW] = show
157 fld[NX_VP8_FLD_PART1LEN] = part1
158
159 if keyframe == 0 {
160 fld[NX_VP8_FLD_WIDTH] = 0
161 fld[NX_VP8_FLD_HEIGHT] = 0
162 fld[NX_VP8_FLD_HSCALE] = 0
163 fld[NX_VP8_FLD_VSCALE] = 0
164 fld[NX_VP8_FLD_HDRLEN] = 3
165 return 1
166 }
167
168 if n < 10 { return 0 }
169 // the start code is mandatory: without it, dimensions come from junk
170 if nx_vp8_at(d, 3) != 0x9d { return 0 }
171 if nx_vp8_at(d, 4) != 0x01 { return 0 }
172 if nx_vp8_at(d, 5) != 0x2a { return 0 }
173
174 let hcode: i64 = nx_vp8_at(d, 6) | (nx_vp8_at(d, 7) << 8)
175 let vcode: i64 = nx_vp8_at(d, 8) | (nx_vp8_at(d, 9) << 8)
176 let w: i64 = hcode & 0x3fff
177 let h: i64 = vcode & 0x3fff
178 if w == 0 { return 0 }
179 if h == 0 { return 0 }
180
181 fld[NX_VP8_FLD_WIDTH] = w
182 fld[NX_VP8_FLD_HEIGHT] = h
183 fld[NX_VP8_FLD_HSCALE] = (hcode >> 14) & 3
184 fld[NX_VP8_FLD_VSCALE] = (vcode >> 14) & 3
185 fld[NX_VP8_FLD_HDRLEN] = 10
186 return 1
187}
188
189func nx_vp8_frame_write(o: *u8, cap: i64, width: i64, height: i64,
190 hscale: i64, vscale: i64, part1: i64) -> i64 {
191 if cap < 10 { return 0 }
192 if width <= 0 { return 0 }
193 if height <= 0 { return 0 }
194 if width > NX_MAGIC_16383 { return 0 }
195 if height > NX_MAGIC_16383 { return 0 }
196 if hscale < 0 { return 0 }
197 if hscale > 3 { return 0 }
198 if vscale < 0 { return 0 }
199 if vscale > 3 { return 0 }
200 if part1 < 0 { return 0 }
201 if part1 > 0x7ffff { return 0 }
202
203 // keyframe (bit 0 clear), version 0, show_frame set
204 let tag: i64 = (1 << 4) | (part1 << 5)
205 o[0] = (tag & 255) as u8
206 o[1] = ((tag >> 8) & 255) as u8
207 o[2] = ((tag >> 16) & 255) as u8
208 o[3] = 0x9d as u8
209 o[4] = 0x01 as u8
210 o[5] = 0x2a as u8
211 let hcode: i64 = width | (hscale << 14)
212 let vcode: i64 = height | (vscale << 14)
213 o[6] = (hcode & 255) as u8
214 o[7] = ((hcode >> 8) & 255) as u8
215 o[8] = (vcode & 255) as u8
216 o[9] = ((vcode >> 8) & 255) as u8
217 return 10
218}