oxedyne/fe2o3 — fe2o3_graphics/src/jpeg.rs

oxedyne/fe2o3/fe2o3_graphics/src/jpeg.rs

98.0 KiB, 252 runs

created by r1870400018:17591, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1	//! A JPEG codec.
2	//!
3	//! JPEG is a stream of marker segments -- tables, a frame header, then one or more scans of
4	//! entropy-coded data. Nothing in it is a general-purpose compressor that could sensibly be
5	//! borrowed, so the whole of it is owned here: the Huffman decoder, the inverse DCT, the chroma
6	//! upsampler and the colour transform alike.
7	//!
8	//! Owning the decoder is also a security position, for the reasons `crate::png` gives. This one
9	//! runs in a crate that forbids `unsafe`, bounds-checks every table index it is handed, and refuses
10	//! a frame header whose dimensions exceed [`MAX_PIXELS`] before it allocates anything.
11	//!
12	//! # What is supported
13	//!
14	//! Decoding: baseline sequential (SOF0), extended sequential with Huffman coding (SOF1), and
15	//! progressive (SOF2), at eight bits a sample. Greyscale, YCbCr and RGB three-component images, and
16	//! four-component CMYK and YCCK. Any sampling factors, with 4:4:4, 4:2:2 and 4:2:0 taking the same
17	//! triangle-filter upsampling libjpeg uses by default. Restart intervals, and scans that are
18	//! interleaved or not.
19	//!
20	//! Encoding: baseline sequential, at a quality that maps onto the Annex K quantisation tables the
21	//! same way libjpeg's does, with 4:4:4, 4:2:2 or 4:2:0 chroma and a greyscale mode.
22	//!
23	//! Arithmetic coding, lossless and hierarchical modes, and twelve-bit samples are refused by name
24	//! rather than misread.
25	//!
26	//! A progressive file whose later scans never arrived takes the Annex K.8 block smoothing libjpeg
27	//! applies by default, which estimates the lowest few AC coefficients of each block from the mean of
28	//! its neighbours rather than showing the flat squares of a half-loaded photograph.
29	//!
30	//! # Damaged files
31	//!
32	//! A photograph library holds files that were truncated by a failed copy or a full disk, and a
33	//! decoder that refuses them shows nothing where it could have shown most of the picture. Where the
34	//! entropy-coded data runs out, the rest of the image is left flat mid-grey and what did arrive is
35	//! returned. A malformed header is still an error, because there is then no picture to show.
36	//!
37	//! # Agreement with other decoders
38	//!
39	//! The inverse DCT is the integer one from the specification's informative annex, in the arrangement
40	//! libjpeg calls `islow`, at the same fixed-point precision and with the same rounding. The colour
41	//! transform and the chroma upsampler are likewise the fixed-point forms libjpeg uses. Two decoders
42	//! of the same file are not obliged to agree to the last bit, but these choices mean this one does.
43	//!
44	//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
45	//! Anthropic Claude
46
47	use crate::pixmap::{
48	Pixmap,
49	MAX_PIXELS,
50	};
51
52	use oxedyne_fe2o3_core::prelude::*;
53
54	use std::num::Wrapping;
55
56	// ┌───────────────────────────────────────────────────────────────────────────┐
57	// │ MARKERS │
58	// └───────────────────────────────────────────────────────────────────────────┘
59
60	const SOI: u8 = 0xD8; // start of image
61	const EOI: u8 = 0xD9; // end of image
62	const SOS: u8 = 0xDA; // start of scan
63	const DQT: u8 = 0xDB; // define quantisation tables
64	const DNL: u8 = 0xDC; // define number of lines
65	const DRI: u8 = 0xDD; // define restart interval
66	const DHT: u8 = 0xC4; // define Huffman tables
67	const DAC: u8 = 0xCC; // define arithmetic coding conditioning
68	const RST0: u8 = 0xD0; // the first restart marker; there are eight, consecutive
69	const RST7: u8 = 0xD7; // the last
70	const APP0: u8 = 0xE0; // the first application segment; there are sixteen
71	const APP15: u8 = 0xEF; // the last
72	const ICC_APP2: u8 = 0xE2; // where an ICC colour profile travels
73	const ADOBE_APP14: u8 = 0xEE; // where Adobe declares a colour transform
74	const COM: u8 = 0xFE; // a comment
75	const TEM: u8 = 0x01; // arithmetic coding only, and carries no length
76
77	const DCTSIZE: usize = 8; // the side of a DCT block, in samples
78	const DCTSIZE2: usize = 64; // and its coefficient count
79
80	// The natural (row-major) position each zigzag position maps to.
81	const NATURAL: [usize; DCTSIZE2] = [
82	0, 1, 8, 16, 9, 2, 3, 10,
83	17, 24, 32, 25, 18, 11, 4, 5,
84	12, 19, 26, 33, 40, 48, 41, 34,
85	27, 20, 13, 6, 7, 14, 21, 28,
86	35, 42, 49, 56, 57, 50, 43, 36,
87	29, 22, 15, 23, 30, 37, 44, 51,
88	58, 59, 52, 45, 38, 31, 39, 46,
89	53, 60, 61, 54, 47, 55, 62, 63,
90	];
91
92	const LOOKAHEAD: usize = 8; // bits of a Huffman code the lookahead table resolves in one step
93
94	// ┌───────────────────────────────────────────────────────────────────────────┐
95	// │ HUFFMAN TABLES │
96	// └───────────────────────────────────────────────────────────────────────────┘
97
98	/// A Huffman table, derived from the counts and values a DHT segment carries.
99	#[derive(Clone, Debug)]
100	struct Huff {
101	maxcode: [i32; 18], // largest code of each length, -1 where there are none
102	mincode: [i32; 17], // and the smallest
103	valptr: [usize; 17], // where each length's values begin in vals
104	vals: Vec<u8>, // the symbols, in canonical code order
105	look: Vec<(u8, u8)>, // by the next LOOKAHEAD bits: code length and symbol, 0 if none
106	}
107
108	impl Huff {
109
110	/// Derives a table from a count of codes at each length 1 to 16, and the symbols they name.
111	fn new(counts: &[u8; 17], vals: Vec<u8>) -> Outcome<Self> {
112	// The code length of each symbol, in order.
113	let mut sizes: Vec<u8> = Vec::with_capacity(vals.len());
114	for l in 1..=16usize {
115	for _ in 0..counts[l] {
116	sizes.push(l as u8);
117	}
118	}
119	if sizes.len() != vals.len() {
120	return Err(err!(
121	"A Huffman table declares {} codes across its sixteen lengths but carries {} \
122	symbols.", sizes.len(), vals.len();
123	Invalid, Input, Decode, Mismatch));
124	}
125	if sizes.is_empty() {
126	return Err(err!("A Huffman table carries no codes."; Invalid, Input, Decode, Missing));
127	}
128
129	// The canonical codes.
130	let mut codes: Vec<u32> = vec![0; sizes.len()];
131	let mut code = 0u32;
132	let mut si = sizes[0];
133	let mut k = 0usize;
134	while k < sizes.len() {
135	while k < sizes.len() && sizes[k] == si {
136	codes[k] = code;
137	code = code.wrapping_add(1);
138	k += 1;
139	}
140	// A binary tree of depth `si` holds two to the `si` leaves, and a table that names more
141	// than that has assigned a code that is the prefix of another.
142	if code > (1u32 << si) {
143	return Err(err!(
144	"A Huffman table declares more codes of length {} than that length holds, so it \
145	is not a prefix code.", si;
146	Invalid, Input, Decode));
147	}
148	code <<= 1;
149	si += 1;
150	if si > 16 {
151	break;
152	}
153	}
154
155	let mut maxcode = [-1i32; 18];
156	let mut mincode = [0i32; 17];
157	let mut valptr = [0usize; 17];
158	let mut p = 0usize;
159	for l in 1..=16usize {
160	if counts[l] > 0 {
161	valptr[l] = p;
162	mincode[l] = codes[p] as i32;
163	p += counts[l] as usize;
164	maxcode[l] = codes[p - 1] as i32;
165	} else {
166	maxcode[l] = -1;
167	}
168	}
169	maxcode[17] = 0x000F_FFFF; // A sentinel, so the slow path always terminates.
170
171	// The lookahead, filled for every code no longer than LOOKAHEAD bits.
172	let mut look = vec![(0u8, 0u8); 1 << LOOKAHEAD];
173	for (i, sz) in sizes.iter().enumerate() {
174	let l = *sz as usize;
175	if l > LOOKAHEAD {
176	break;
177	}
178	let lo = (codes[i] as usize) << (LOOKAHEAD - l);
179	let hi = lo + (1usize << (LOOKAHEAD - l));
180	for e in look.iter_mut().take(hi.min(1 << LOOKAHEAD)).skip(lo) {
181	*e = (l as u8, vals[i]);
182	}
183	}
184
185	Ok(Self { maxcode, mincode, valptr, vals, look })
186	}
187	}
188
189	// ┌───────────────────────────────────────────────────────────────────────────┐
190	// │ THE ENTROPY-CODED BIT STREAM │
191	// └───────────────────────────────────────────────────────────────────────────┘
192
193	/// A reader of the bits in an entropy-coded segment.
194	///
195	/// A 0xFF byte inside entropy-coded data is written as 0xFF 0x00, so the reader unstuffs as it goes.
196	/// A 0xFF followed by anything else is a marker, which ends the segment: the reader then pads with
197	/// zero bits rather than reading past it, which is what a decoder must do with a truncated file if
198	/// it is to show the part that did arrive.
199	struct Bits<'a> {
200	buf: &'a [u8], // the whole file
201	pos: usize, // the next byte to read
202	acc: u32, // the bit buffer; its lowest cnt bits are unconsumed
203	cnt: u32, // how many bits of acc are valid
204	hit: bool, // a marker or the end was met, so the reader now pads
205	pad: u32, // how many of the cnt bits are padding rather than data
206	}
207
208	impl<'a> Bits<'a> {
209
210	fn new(buf: &'a [u8], pos: usize) -> Self {
211	Self { buf, pos, acc: 0, cnt: 0, hit: false, pad: 0 }
212	}
213
214	/// The next byte of entropy-coded data, unstuffed, or `None` once a marker has been met.
215	fn byte(&mut self) -> Option<u8> {
216	if self.hit {
217	return None;
218	}
219	if self.pos >= self.buf.len() {
220	self.hit = true;
221	return None;
222	}
223	let b = self.buf[self.pos];
224	if b != 0xFF {
225	self.pos += 1;
226	return Some(b);
227	}
228	// A 0xFF is a stuffed literal, padding before a marker, or the marker itself.
229	let mut k = self.pos + 1;
230	while k < self.buf.len() && self.buf[k] == 0xFF {
231	k += 1;
232	}
233	if k < self.buf.len() && self.buf[k] == 0x00 {
234	self.pos = k + 1;
235	return Some(0xFF);
236	}
237	self.hit = true;
238	None
239	}
240
241	/// Tops the bit buffer up to at least 25 bits, padding with zeros past the end of the data.
242	fn fill(&mut self) {
243	while self.cnt <= 24 {
244	match self.byte() {
245	Some(b) => self.acc = (self.acc << 8) \| (b as u32),
246	None => {
247	self.acc <<= 8;
248	self.pad += 8;
249	},
250	}
251	self.cnt += 8;
252	}
253	}
254
255	/// Whether every bit left is padding, so the entropy-coded data has genuinely run out.
256	///
257	/// This is not the same as having met the marker that ends the segment: the buffer reads ahead,
258	/// so the marker is normally in hand while several real bits are still to be spent.
259	fn starved(&mut self) -> bool {
260	self.fill();
261	self.hit && self.pad >= self.cnt
262	}
263
264	fn bit(&mut self) -> u32 {
265	if self.cnt == 0 {
266	self.fill();
267	}
268	self.cnt -= 1;
269	self.pad = self.pad.min(self.cnt);
270	(self.acc >> self.cnt) & 1
271	}
272
273	/// The next `n` bits, as an unsigned integer, where `n` is at most 16.
274	fn receive(&mut self, n: u32) -> u32 {
275	if n == 0 {
276	return 0;
277	}
278	if self.cnt < n {
279	self.fill();
280	}
281	self.cnt -= n;
282	self.pad = self.pad.min(self.cnt);
283	(self.acc >> self.cnt) & ((1u32 << n) - 1)
284	}
285
286	fn huff(&mut self, t: &Huff) -> Outcome<u8> {
287	self.fill();
288	if self.cnt >= LOOKAHEAD as u32 {
289	let peek = ((self.acc >> (self.cnt - LOOKAHEAD as u32)) & 0xFF) as usize;
290	let (l, v) = t.look[peek];
291	if l != 0 {
292	self.cnt -= l as u32;
293	self.pad = self.pad.min(self.cnt);
294	return Ok(v);
295	}
296	}
297	let mut code = 0i32;
298	for l in 1..=16usize {
299	code = (code << 1) \| (self.bit() as i32);
300	if code <= t.maxcode[l] {
301	let idx = t.valptr[l] + ((code - t.mincode[l]) as usize);
302	match t.vals.get(idx) {
303	Some(v) => return Ok(*v),
304	None => break,
305	}
306	}
307	}
308	if self.hit {
309	// The data ran out; libjpeg's answer here is a zero, and so is ours, so that a truncated
310	// file still shows the part of the image that arrived.
311	return Ok(0);
312	}
313	Err(err!(
314	"No Huffman code of any length from 1 to 16 matches the bits at offset {} of the \
315	entropy-coded data.", self.pos;
316	Invalid, Input, Decode))
317	}
318
319	/// Steps over the restart marker that ends a restart interval.
320	///
321	/// Whatever bits are left in the interval are discarded, and any padding an encoder left before
322	/// the marker is walked over rather than read as data.
323	fn restart(&mut self) {
324	self.acc = 0;
325	self.cnt = 0;
326	self.pad = 0;
327	let n = self.buf.len();
328	let mut k = self.pos;
329	while k + 1 < n {
330	if self.buf[k] == 0xFF && self.buf[k + 1] != 0x00 && self.buf[k + 1] != 0xFF {
331	break;
332	}
333	k += 1;
334	}
335	if k + 1 < n {
336	let m = self.buf[k + 1];
337	if (RST0..=RST7).contains(&m) {
338	self.pos = k + 2;
339	self.hit = false;
340	return;
341	}
342	}
343	// Whatever is there is not a restart marker, so the scan's data ends at it.
344	self.pos = k.min(n);
345	self.hit = true;
346	}
347	}
348
349	/// Sign-extends a value of `n` bits read out of the stream, as the specification's EXTEND does.
350	fn extend(v: u32, n: u32) -> i32 {
351	if n == 0 {
352	return 0;
353	}
354	let v = v as i32;
355	if v < (1 << (n - 1)) {
356	v - (1 << n) + 1
357	} else {
358	v
359	}
360	}
361
362	// ┌───────────────────────────────────────────────────────────────────────────┐
363	// │ THE INVERSE DCT │
364	// └───────────────────────────────────────────────────────────────────────────┘
365	//
366	// The integer inverse DCT of the specification's informative annex, in the arrangement libjpeg calls
367	// `islow`: a row-column decomposition of the AAN even-odd factorisation, at thirteen fractional
368	// bits, carrying two extra bits between the passes. The arithmetic wraps rather than panicking,
369	// because a file whose coefficients are large enough to overflow is a file to be read the way every
370	// other decoder reads it, not one to abort on.
371
372	/// An integer that wraps rather than trapping, so a hostile coefficient cannot panic the decoder.
373	type W = Wrapping<i32>;
374
375	const fn w(v: i32) -> W {
376	Wrapping(v)
377	}
378
379	const CONST_BITS: usize = 13; // fractional bits the constants below carry
380	const PASS1_BITS: usize = 2; // extra fractional bits carried between the two passes
381
382	//// The rotation constants of the even and odd parts, named for the value each stands for and
383	//// held at CONST_BITS fractional bits. The first three belong to the even part.
384	const FIX_0_541196100: W = w(4433);
385	const FIX_0_765366865: W = w(6270);
386	const FIX_1_847759065: W = w(15137);
387	const FIX_0_298631336: W = w(2446);
388	const FIX_2_053119869: W = w(16819);
389	const FIX_3_072711026: W = w(25172);
390	const FIX_1_501321110: W = w(12299);
391	const FIX_0_899976223: W = w(7373);
392	const FIX_2_562915447: W = w(20995);
393	const FIX_1_961570560: W = w(16069);
394	const FIX_0_390180644: W = w(3196);
395	const FIX_1_175875602: W = w(9633);
396
397	/// Rounds a fixed-point value down by `n` bits, to nearest.
398	fn descale(x: W, n: usize) -> W {
399	(x + w(1 << (n - 1))) >> n
400	}
401
402	fn clamp8(v: i32) -> u8 {
403	if v < 0 {
404	0
405	} else if v > 255 {
406	255
407	} else {
408	v as u8
409	}
410	}
411
412	/// The odd part of one pass, shared by both: four coefficients in, four butterfly terms out.
413	fn odd_part(t0: W, t1: W, t2: W, t3: W) -> (W, W, W, W) {
414	let z1 = t0 + t3;
415	let z2 = t1 + t2;
416	let z3 = t0 + t2;
417	let z4 = t1 + t3;
418	let z5 = (z3 + z4) * FIX_1_175875602;
419
420	let t0 = t0 * FIX_0_298631336;
421	let t1 = t1 * FIX_2_053119869;
422	let t2 = t2 * FIX_3_072711026;
423	let t3 = t3 * FIX_1_501321110;
424	let z1 = z1 * -FIX_0_899976223;
425	let z2 = z2 * -FIX_2_562915447;
426	let z3 = z3 * -FIX_1_961570560 + z5;
427	let z4 = z4 * -FIX_0_390180644 + z5;
428
429	(t0 + z1 + z3, t1 + z2 + z4, t2 + z2 + z3, t3 + z1 + z4)
430	}
431
432	/// The even part of one pass: four coefficients in, four butterfly terms out.
433	fn even_part(c0: W, c2: W, c4: W, c6: W) -> (W, W, W, W) {
434	let z1 = (c2 + c6) * FIX_0_541196100;
435	let t2 = z1 + c6 * -FIX_1_847759065;
436	let t3 = z1 + c2 * FIX_0_765366865;
437	let t0 = (c0 + c4) << CONST_BITS;
438	let t1 = (c0 - c4) << CONST_BITS;
439	(t0 + t3, t1 + t2, t1 - t2, t0 - t3)
440	}
441
442	/// Inverts the DCT of one block, dequantising on the way in, and writes eight rows of eight samples.
443	///
444	/// The coefficients are in natural order, as is the quantisation table, and the samples land at
445	/// `out[at + y * stride + x]`.
446	fn idct(coef: &[i16], q: &[u16; DCTSIZE2], out: &mut [u8], at: usize, stride: usize) {
447	let mut ws = [w(0); DCTSIZE2];
448
449	// Pass one, over the columns.
450	for c in 0..DCTSIZE {
451	let ac_zero = (1..DCTSIZE).all(\|r\| coef[r * DCTSIZE + c] == 0);
452	if ac_zero {
453	let dc = w((coef[c] as i32) * (q[c] as i32)) << PASS1_BITS;
454	for r in 0..DCTSIZE {
455	ws[r * DCTSIZE + c] = dc;
456	}
457	continue;
458	}
459	let d = \|r: usize\| w((coef[r * DCTSIZE + c] as i32) * (q[r * DCTSIZE + c] as i32));
460	let (t10, t11, t12, t13) = even_part(d(0), d(2), d(4), d(6));
461	let (o0, o1, o2, o3) = odd_part(d(7), d(5), d(3), d(1));
462	let s = CONST_BITS - PASS1_BITS;
463	ws[c] = descale(t10 + o3, s);
464	ws[7 * DCTSIZE + c] = descale(t10 - o3, s);
465	ws[DCTSIZE + c] = descale(t11 + o2, s);
466	ws[6 * DCTSIZE + c] = descale(t11 - o2, s);
467	ws[2 * DCTSIZE + c] = descale(t12 + o1, s);
468	ws[5 * DCTSIZE + c] = descale(t12 - o1, s);
469	ws[3 * DCTSIZE + c] = descale(t13 + o0, s);
470	ws[4 * DCTSIZE + c] = descale(t13 - o0, s);
471	}
472
473	// Pass two, over the rows, with the level shift folded into the clamp.
474	let s = CONST_BITS + PASS1_BITS + 3;
475	for r in 0..DCTSIZE {
476	let v = &ws[r * DCTSIZE..r * DCTSIZE + DCTSIZE];
477	let (t10, t11, t12, t13) = even_part(v[0], v[2], v[4], v[6]);
478	let (o0, o1, o2, o3) = odd_part(v[7], v[5], v[3], v[1]);
479	let row = at + r * stride;
480	let put = \|out: &mut [u8], i: usize, x: W\| {
481	out[row + i] = clamp8(descale(x, s).0 + 128);
482	};
483	put(out, 0, t10 + o3);
484	put(out, 7, t10 - o3);
485	put(out, 1, t11 + o2);
486	put(out, 6, t11 - o2);
487	put(out, 2, t12 + o1);
488	put(out, 5, t12 - o1);
489	put(out, 3, t13 + o0);
490	put(out, 4, t13 - o0);
491	}
492	}
493
494	/// The one sample a block reduces to when only its DC coefficient is read.
495	fn idct_dc(coef: &[i16], q: &[u16; DCTSIZE2]) -> u8 {
496	let dc = w((coef[0] as i32) * (q[0] as i32));
497	clamp8(descale(dc, 3).0 + 128)
498	}
499
500	// ┌───────────────────────────────────────────────────────────────────────────┐
501	// │ COLOUR │
502	// └───────────────────────────────────────────────────────────────────────────┘
503
504	/// The fixed-point tables the YCbCr to RGB transform uses, at sixteen fractional bits.
505	struct YccTab {
506	cr_r: [i32; 256], // the red contribution of Cr, already descaled
507	cb_b: [i32; 256], // the blue contribution of Cb, already descaled
508	cr_g: [i32; 256], // the green contribution of Cr, still scaled
509	cb_g: [i32; 256], // the same for Cb, carrying the rounding term
510	}
511
512	impl YccTab {
513
514	fn new() -> Self {
515	let half = 1i32 << 15;
516	let mut t = Self {
517	cr_r: [0; 256],
518	cb_b: [0; 256],
519	cr_g: [0; 256],
520	cb_g: [0; 256],
521	};
522	for i in 0..256 {
523	let x = (i as i32) - 128;
524	t.cr_r[i] = (91881 * x + half) >> 16; // 1.40200
525	t.cb_b[i] = (116130 * x + half) >> 16; // 1.77200
526	t.cr_g[i] = -46802 * x; // -0.71414
527	t.cb_g[i] = -22554 * x + half; // -0.34414
528	}
529	t
530	}
531
532	/// One pixel, from luminance and the two chrominances.
533	fn rgb(&self, y: u8, cb: u8, cr: u8) -> (u8, u8, u8) {
534	let (y, cb, cr) = (y as i32, cb as usize, cr as usize);
535	(
536	clamp8(y + self.cr_r[cr]),
537	clamp8(y + ((self.cb_g[cb] + self.cr_g[cr]) >> 16)),
538	clamp8(y + self.cb_b[cb]),
539	)
540	}
541	}
542
543	// ┌───────────────────────────────────────────────────────────────────────────┐
544	// │ THE FRAME │
545	// └───────────────────────────────────────────────────────────────────────────┘
546
547	/// How the samples of a frame's components are to be read as colour.
548	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
549	enum Space {
550	Grey, // one component: luminance
551	Ycc, // three: luminance and two chrominances
552	Rgb, // three, already red, green and blue
553	Cmyk, // four: cyan, magenta, yellow, black, inverted where Adobe says
554	Ycck, // four: a YCbCr encoding of inverted CMY, then black
555	}
556
557	/// One component of a frame.
558	#[derive(Clone, Debug)]
559	struct Comp {
560	id: u8, // the identifier a scan header names it by
561	h: usize, // horizontal sampling factor
562	v: usize, // vertical sampling factor
563	tq: usize, // which of the four quantisation table slots it uses
564	dw: usize, // width in samples, before upsampling
565	dh: usize, // and height
566	bw: usize, // width in blocks, of the samples that carry image
567	bh: usize, // and height
568	bwp: usize, // width in blocks of the allocation, which the MCU grid rounds up
569	bhp: usize, // and height
570	coef: Vec<i16>, // natural order within a block, row-major across blocks
571	}
572
573	impl Comp {
574
575	/// Where a block's coefficients begin.
576	fn at(&self, bx: usize, by: usize) -> usize {
577	(by * self.bwp + bx) * DCTSIZE2
578	}
579	}
580
581	/// A frame, and everything the scans within it have filled in.
582	struct Frame {
583	prog: bool, // do the coefficients arrive over several scans, each refining?
584	w: usize, // width in pixels
585	h: usize, // height in pixels
586	hmax: usize, // the largest horizontal sampling factor across the components
587	vmax: usize, // and vertical
588	mcux: usize, // MCUs across
589	mcuy: usize, // and down
590	comps: Vec<Comp>, // in the order the frame header gives them
591	// Per component, the successive-approximation bit at which each coefficient was last
592	// received, or -1 for a coefficient no scan ever carried.
593	seen: Vec<[i8; DCTSIZE2]>,
594	}
595
596	fn ceil_div(a: usize, b: usize) -> usize {
597	if b == 0 {
598	0
599	} else {
600	a.div_ceil(b)
601	}
602	}
603
604	// ┌───────────────────────────────────────────────────────────────────────────┐
605	// │ PARSING │
606	// └───────────────────────────────────────────────────────────────────────────┘
607
608	/// The tables and frame a file has declared so far.
609	struct Reader {
610	quant: [Option<[u16; DCTSIZE2]>; 4], // the four slots, in natural order
611	dc: [Option<Huff>; 4], // the four DC Huffman table slots
612	ac: [Option<Huff>; 4], // and the four AC ones
613	ri: usize, // the restart interval in MCUs, or zero for none
614	jfif: bool, // a JFIF APP0 alone makes a three-component frame YCbCr
615	adobe: Option<u8>, // the colour transform an Adobe APP14 declared
616	frame: Option<Frame>, // the frame, once its header has been read
617	}
618
619	/// Removes the metadata a JPEG carries, without touching the image itself.
620	///
621	/// A photograph off a phone arrives with an Exif block naming the camera, the moment and, very
622	/// often, the coordinates of whoever pressed the shutter. Publishing the file publishes all of it.
623	/// This walks the marker segments and drops the ones that describe the picture rather than encode
624	/// it, leaving the entropy-coded scan untouched: the result decodes to exactly the same pixels, so
625	/// nothing is re-compressed and no quality is lost.
626	///
627	/// Removed: every application segment except those below, and every comment segment. That takes
628	/// Exif and XMP (APP1), Photoshop and IPTC (APP13), maker notes, and any JUMBF or C2PA assertion
629	/// (APP11) with them -- so a caller relying on embedded provenance must read it before calling.
630	///
631	/// Kept, because dropping them changes how the file decodes or renders: JFIF (APP0), an ICC colour
632	/// profile (APP2), and the Adobe colour transform (APP14).
633	pub fn strip_metadata(buf: &[u8]) -> Outcome<Vec<u8>> {
634	if buf.len() < 2 \|\| buf[0] != 0xFF \|\| buf[1] != SOI {
635	return Err(err!("The data does not begin with a JPEG start-of-image marker.";
636	Invalid, Input, Decode));
637	}
638	let mut out = Vec::with_capacity(buf.len());
639	out.extend_from_slice(&buf[..2]);
640
641	let mut pos = 2;
642	loop {
643	let (marker, after) = res!(next_marker(buf, pos));
644	// The scan and everything after it is image data; copy the remainder untouched.
645	if marker == SOS {
646	out.extend_from_slice(&buf[pos..]);
647	return Ok(out);
648	}
649	// Markers that stand alone carry no length.
650	if marker == EOI \|\| marker == TEM \|\| (RST0..=RST7).contains(&marker) {
651	out.extend_from_slice(&buf[pos..after]);
652	if marker == EOI {
653	return Ok(out);
654	}
655	pos = after;
656	continue;
657	}
658	let (_start, end) = res!(segment(buf, after, marker));
659	let drop = match marker {
660	APP0 \| ADOBE_APP14 => false, // JFIF and the Adobe colour transform.
661	ICC_APP2 => false, // A colour profile is how the pixels are read.
662	COM => true,
663	m if (APP0..=APP15).contains(&m) => true,
664	_ => false,
665	};
666	if !drop {
667	out.extend_from_slice(&buf[pos..end]);
668	}
669	pos = end;
670	}
671	}
672
673	/// The two-byte length a marker segment begins with, and the bounds of its payload.
674	fn segment(buf: &[u8], pos: usize, marker: u8) -> Outcome<(usize, usize)> {
675	if pos + 2 > buf.len() {
676	return Err(err!(
677	"The marker {:#04X} at offset {} has no length, only {} bytes remain.",
678	marker, pos, buf.len() - pos;
679	Invalid, Input, Decode));
680	}
681	let len = ((buf[pos] as usize) << 8) \| (buf[pos + 1] as usize);
682	if len < 2 {
683	return Err(err!(
684	"The marker {:#04X} at offset {} declares a segment length of {}, and a length counts \
685	its own two bytes.", marker, pos, len;
686	Invalid, Input, Decode));
687	}
688	let end = pos + len;
689	if end > buf.len() {
690	return Err(err!(
691	"The marker {:#04X} at offset {} declares {} bytes, but only {} remain.",
692	marker, pos, len, buf.len() - pos;
693	Invalid, Input, Decode));
694	}
695	Ok((pos + 2, end))
696	}
697
698	/// Finds the next marker at or after an offset, stepping over any padding.
699	fn next_marker(buf: &[u8], pos: usize) -> Outcome<(u8, usize)> {
700	let mut k = pos;
701	while k < buf.len() && buf[k] != 0xFF {
702	k += 1;
703	}
704	while k < buf.len() && buf[k] == 0xFF {
705	k += 1;
706	}
707	if k >= buf.len() {
708	return Err(err!(
709	"The file ends at offset {} without a further marker.", buf.len();
710	Invalid, Input, Decode, Missing));
711	}
712	Ok((buf[k], k + 1))
713	}
714
715	/// Reads a frame header, and refuses what this codec does not implement, by name.
716	///
717	/// The coefficient buffers are allocated only when `alloc` is set, so that a caller after the size
718	/// alone pays for nothing else.
719	fn read_frame(data: &[u8], marker: u8, at: usize, alloc: bool) -> Outcome<Frame> {
720	let kind = match marker {
721	0xC0 => "baseline sequential",
722	0xC1 => "extended sequential",
723	0xC2 => "progressive",
724	0xC3 => return Err(err!(
725	"The frame at offset {} is lossless (SOF3). This codec implements the DCT modes.", at;
726	Invalid, Input, Decode, NoImpl)),
727	0xC5..=0xC7 => return Err(err!(
728	"The frame at offset {} is differential (SOF{}), part of a hierarchical image. This \
729	codec implements the non-hierarchical modes.", at, marker - 0xC0;
730	Invalid, Input, Decode, NoImpl)),
731	0xC9..=0xCB => return Err(err!(
732	"The frame at offset {} is arithmetic coded (SOF{}). This codec implements Huffman \
733	coding.", at, marker - 0xC0;
734	Invalid, Input, Decode, NoImpl)),
735	0xCD..=0xCF => return Err(err!(
736	"The frame at offset {} is differential and arithmetic coded (SOF{}). This codec \
737	implements neither.", at, marker - 0xC0;
738	Invalid, Input, Decode, NoImpl)),
739	_ => return Err(err!(
740	"The marker {:#04X} at offset {} is not a frame header this codec knows.", marker, at;
741	Invalid, Input, Decode, NoImpl)),
742	};
743	if data.len() < 6 {
744	return Err(err!(
745	"A {} frame header at offset {} is at least 6 bytes, but this one is {}.",
746	kind, at, data.len();
747	Invalid, Input, Decode));
748	}
749	let prec = data[0];
750	if prec != 8 {
751	return Err(err!(
752	"The frame at offset {} declares {} bits a sample. This codec implements 8.", at, prec;
753	Invalid, Input, Decode, NoImpl));
754	}
755	let h = ((data[1] as usize) << 8) \| (data[2] as usize);
756	let w = ((data[3] as usize) << 8) \| (data[4] as usize);
757	if h == 0 {
758	return Err(err!(
759	"The frame at offset {} declares no height, so its number of lines arrives in a DNL \
760	segment. This codec implements the height a frame header carries.", at;
761	Invalid, Input, Decode, NoImpl));
762	}
763	if w == 0 {
764	return Err(err!(
765	"The frame at offset {} declares a width of zero.", at; Invalid, Input, Decode));
766	}
767	let n = match w.checked_mul(h) {
768	Some(n) => n,
769	None => return Err(err!(
770	"The frame at offset {} declares {} by {} pixels, which overflows.", at, w, h;
771	Invalid, Input, Decode, Overflow)),
772	};
773	if n > MAX_PIXELS {
774	return Err(err!(
775	"The frame at offset {} declares {} by {} pixels, over the ceiling of {}.",
776	at, w, h, MAX_PIXELS;
777	Invalid, Input, Decode, Excessive));
778	}
779
780	let nc = data[5] as usize;
781	if nc == 0 \|\| nc > 4 {
782	return Err(err!(
783	"The frame at offset {} declares {} components. This codec implements 1 to 4.", at, nc;
784	Invalid, Input, Decode, NoImpl));
785	}
786	if data.len() < 6 + nc * 3 {
787	return Err(err!(
788	"The frame at offset {} declares {} components, needing {} bytes, but its header is {}.",
789	at, nc, 6 + nc * 3, data.len();
790	Invalid, Input, Decode));
791	}
792
793	let mut comps = Vec::with_capacity(nc);
794	let (mut hmax, mut vmax) = (1usize, 1usize);
795	for i in 0..nc {
796	let b = 6 + i * 3;
797	let id = data[b];
798	let h_i = (data[b + 1] >> 4) as usize;
799	let v_i = (data[b + 1] & 15) as usize;
800	let tq = data[b + 2] as usize;
801	if h_i == 0 \|\| h_i > 4 \|\| v_i == 0 \|\| v_i > 4 {
802	return Err(err!(
803	"Component {} of the frame at offset {} declares sampling factors {} by {}, and the \
804	specification allows 1 to 4.", id, at, h_i, v_i;
805	Invalid, Input, Decode, Range));
806	}
807	if tq > 3 {
808	return Err(err!(
809	"Component {} of the frame at offset {} names quantisation table {}, and there are \
810	four slots, 0 to 3.", id, at, tq;
811	Invalid, Input, Decode, Range));
812	}
813	hmax = hmax.max(h_i);
814	vmax = vmax.max(v_i);
815	comps.push(Comp {
816	id,
817	h: h_i,
818	v: v_i,
819	tq,
820	dw: 0,
821	dh: 0,
822	bw: 0,
823	bh: 0,
824	bwp: 0,
825	bhp: 0,
826	coef: Vec::new(),
827	});
828	}
829
830	let mcux = ceil_div(w, DCTSIZE * hmax);
831	let mcuy = ceil_div(h, DCTSIZE * vmax);
832	for c in comps.iter_mut() {
833	c.dw = ceil_div(w * c.h, hmax);
834	c.dh = ceil_div(h * c.v, vmax);
835	c.bw = ceil_div(c.dw, DCTSIZE);
836	c.bh = ceil_div(c.dh, DCTSIZE);
837	c.bwp = mcux * c.h;
838	c.bhp = mcuy * c.v;
839	let cells = match c.bwp.checked_mul(c.bhp).and_then(\|n\| n.checked_mul(DCTSIZE2)) {
840	Some(n) => n,
841	None => return Err(err!(
842	"Component {} of the frame at offset {} needs a coefficient buffer that overflows.",
843	c.id, at;
844	Invalid, Input, Decode, Overflow)),
845	};
846	if cells > MAX_PIXELS * 2 {
847	return Err(err!(
848	"Component {} of the frame at offset {} needs {} coefficients, which is beyond what \
849	this codec will allocate.", c.id, at, cells;
850	Invalid, Input, Decode, Excessive));
851	}
852	if alloc {
853	c.coef = vec![0i16; cells];
854	}
855	}
856
857	Ok(Frame {
858	seen: vec![[-1i8; DCTSIZE2]; comps.len()],
859	prog: marker == 0xC2,
860	w,
861	h,
862	hmax,
863	vmax,
864	mcux,
865	mcuy,
866	comps,
867	})
868	}
869
870	/// Reads one or more quantisation tables out of a DQT segment.
871	fn read_quant(data: &[u8], slots: &mut [Option<[u16; DCTSIZE2]>; 4], at: usize) -> Outcome<()> {
872	let mut p = 0usize;
873	while p < data.len() {
874	let pq = (data[p] >> 4) as usize;
875	let tq = (data[p] & 15) as usize;
876	p += 1;
877	if tq > 3 {
878	return Err(err!(
879	"A DQT segment at offset {} names table slot {}, and there are four, 0 to 3.", at, tq;
880	Invalid, Input, Decode, Range));
881	}
882	if pq > 1 {
883	return Err(err!(
884	"A DQT segment at offset {} declares precision {} for table {}, and the \
885	specification allows 0 for eight bits and 1 for sixteen.", at, pq, tq;
886	Invalid, Input, Decode, Range));
887	}
888	let need = if pq == 0 { DCTSIZE2 } else { DCTSIZE2 * 2 };
889	if p + need > data.len() {
890	return Err(err!(
891	"A DQT segment at offset {} declares table {} but carries only {} of the {} bytes it \
892	needs.", at, tq, data.len() - p, need;
893	Invalid, Input, Decode));
894	}
895	let mut t = [0u16; DCTSIZE2];
896	for k in 0..DCTSIZE2 {
897	let v = if pq == 0 {
898	data[p + k] as u16
899	} else {
900	((data[p + k * 2] as u16) << 8) \| (data[p + k * 2 + 1] as u16)
901	};
902	if v == 0 {
903	return Err(err!(
904	"A DQT segment at offset {} gives table {} a zero divisor at zigzag position {}.",
905	at, tq, k;
906	Invalid, Input, Decode, ZeroDenominator));
907	}
908	t[NATURAL[k]] = v;
909	}
910	p += need;
911	slots[tq] = Some(t);
912	}
913	Ok(())
914	}
915
916	/// Reads one or more Huffman tables out of a DHT segment.
917	fn read_huff(
918	data: &[u8],
919	dc: &mut [Option<Huff>; 4],
920	ac: &mut [Option<Huff>; 4],
921	at: usize,
922	)
923	-> Outcome<()>
924	{
925	let mut p = 0usize;
926	while p < data.len() {
927	let tc = (data[p] >> 4) as usize;
928	let th = (data[p] & 15) as usize;
929	p += 1;
930	if tc > 1 {
931	return Err(err!(
932	"A DHT segment at offset {} declares table class {}, and there are two: 0 for DC and \
933	1 for AC.", at, tc;
934	Invalid, Input, Decode, Range));
935	}
936	if th > 3 {
937	return Err(err!(
938	"A DHT segment at offset {} names table slot {}, and there are four, 0 to 3.", at, th;
939	Invalid, Input, Decode, Range));
940	}
941	if p + 16 > data.len() {
942	return Err(err!(
943	"A DHT segment at offset {} ends before the sixteen code counts of table {}.", at, th;
944	Invalid, Input, Decode));
945	}
946	let mut counts = [0u8; 17];
947	let mut total = 0usize;
948	for l in 1..=16usize {
949	counts[l] = data[p + l - 1];
950	total += counts[l] as usize;
951	}
952	p += 16;
953	if total > 256 {
954	return Err(err!(
955	"A DHT segment at offset {} gives table {} {} symbols, and a byte names at most 256.",
956	at, th, total;
957	Invalid, Input, Decode, Excessive));
958	}
959	if p + total > data.len() {
960	return Err(err!(
961	"A DHT segment at offset {} declares {} symbols for table {} but carries only {}.",
962	at, total, th, data.len() - p;
963	Invalid, Input, Decode));
964	}
965	let vals = data[p..p + total].to_vec();
966	p += total;
967	let t = res!(Huff::new(&counts, vals));
968	if tc == 0 {
969	dc[th] = Some(t);
970	} else {
971	ac[th] = Some(t);
972	}
973	}
974	Ok(())
975	}
976
977	// ┌───────────────────────────────────────────────────────────────────────────┐
978	// │ SCANS │
979	// └───────────────────────────────────────────────────────────────────────────┘
980
981	/// One component of a scan: which component of the frame, and which two table slots it reads with.
982	#[derive(Clone, Copy, Debug)]
983	struct ScanComp {
984	ci: usize, // the index of the component within the frame
985	td: usize, // the DC table slot
986	ta: usize, // and the AC one
987	}
988
989	#[derive(Clone, Debug)]
990	struct Scan {
991	comps: Vec<ScanComp>, // in the order the scan gives them
992	ss: usize, // first coefficient of the spectral band, zigzag order
993	se: usize, // and the last
994	ah: u32, // bit position the previous scan of this band reached
995	al: u32, // and the one this scan reaches
996	}
997
998	fn read_scan(data: &[u8], frame: &Frame, at: usize) -> Outcome<Scan> {
999	if data.is_empty() {
1000	return Err(err!("The scan header at offset {} is empty.", at; Invalid, Input, Decode));
1001	}
1002	let ns = data[0] as usize;
1003	if ns == 0 \|\| ns > 4 {
1004	return Err(err!(
1005	"The scan at offset {} declares {} components, and the specification allows 1 to 4.",
1006	at, ns;
1007	Invalid, Input, Decode, Range));
1008	}
1009	if data.len() < 1 + ns * 2 + 3 {
1010	return Err(err!(
1011	"The scan header at offset {} declares {} components, needing {} bytes, but it is {}.",
1012	at, ns, 1 + ns * 2 + 3, data.len();
1013	Invalid, Input, Decode));
1014	}
1015	let mut comps = Vec::with_capacity(ns);
1016	for i in 0..ns {
1017	let b = 1 + i * 2;
1018	let id = data[b];
1019	let ci = match frame.comps.iter().position(\|c\| c.id == id) {
1020	Some(ci) => ci,
1021	None => return Err(err!(
1022	"The scan at offset {} names component {}, which its frame does not declare.", at, id;
1023	Invalid, Input, Decode, NotFound)),
1024	};
1025	comps.push(ScanComp {
1026	ci,
1027	td: (data[b + 1] >> 4) as usize,
1028	ta: (data[b + 1] & 15) as usize,
1029	});
1030	}
1031	let b = 1 + ns * 2;
1032	let ss = data[b] as usize;
1033	let se = data[b + 1] as usize;
1034	let ah = (data[b + 2] >> 4) as u32;
1035	let al = (data[b + 2] & 15) as u32;
1036
1037	if frame.prog {
1038	if ss > 63 \|\| se > 63 \|\| ss > se {
1039	return Err(err!(
1040	"The progressive scan at offset {} declares the spectral band {} to {}, which is not \
1041	a band within 0 to 63.", at, ss, se;
1042	Invalid, Input, Decode, Range));
1043	}
1044	if ss == 0 && se != 0 {
1045	return Err(err!(
1046	"The progressive scan at offset {} mixes the DC coefficient with AC coefficients, \
1047	running from 0 to {}. A DC scan carries coefficient 0 alone.", at, se;
1048	Invalid, Input, Decode));
1049	}
1050	if ss != 0 && ns != 1 {
1051	return Err(err!(
1052	"The progressive scan at offset {} carries {} components over the AC band {} to {}, \
1053	and an AC scan carries one component.", at, ns, ss, se;
1054	Invalid, Input, Decode));
1055	}
1056	if al > 13 \|\| ah > 13 {
1057	return Err(err!(
1058	"The progressive scan at offset {} declares successive approximation {} to {}, and \
1059	the specification allows 0 to 13.", at, ah, al;
1060	Invalid, Input, Decode, Range));
1061	}
1062	if ah != 0 && ah != al + 1 {
1063	return Err(err!(
1064	"The progressive scan at offset {} refines from bit {} to bit {}, and a refinement \
1065	moves one bit at a time.", at, ah, al;
1066	Invalid, Input, Decode));
1067	}
1068	}
1069	Ok(Scan { comps, ss, se, ah, al })
1070	}
1071
1072	/// A borrowed pair of Huffman tables, one for each class.
1073	struct Tables<'a> {
1074	dc: Option<&'a Huff>, // absent for a scan that reads no DC coefficients
1075	ac: Option<&'a Huff>, // absent for a scan that reads no AC coefficients
1076	}
1077
1078	/// The state a scan carries from one block to the next.
1079	struct ScanState {
1080	pred: Vec<i32>, // the DC predictor of each scan component
1081	eobrun: u32, // how many end-of-band runs remain
1082	}
1083
1084	/// Decodes the entropy-coded data of one scan; the offset it ended at comes back.
1085	fn decode_scan(
1086	buf: &[u8],
1087	start: usize,
1088	frame: &mut Frame,
1089	scan: &Scan,
1090	tabs: &[Tables],
1091	ri: usize,
1092	)
1093	-> Outcome<usize>
1094	{
1095	let mut bits = Bits::new(buf, start);
1096	let mut st = ScanState {
1097	pred: vec![0i32; scan.comps.len()],
1098	eobrun: 0,
1099	};
1100
1101	// A scan of one component walks that component's own block grid; a scan of several walks the
1102	// MCU grid, taking each component's sampling factors' worth of blocks in turn.
1103	let single = scan.comps.len() == 1;
1104	let (nx, ny) = if single {
1105	let c = &frame.comps[scan.comps[0].ci];
1106	(c.bw, c.bh)
1107	} else {
1108	(frame.mcux, frame.mcuy)
1109	};
1110	let total = nx * ny;
1111	let mut todo = ri;
1112
1113	for i in 0..total {
1114	if ri > 0 && todo == 0 {
1115	bits.restart();
1116	for p in st.pred.iter_mut() {
1117	*p = 0;
1118	}
1119	st.eobrun = 0;
1120	todo = ri;
1121	}
1122	if bits.starved() {
1123	// The entropy-coded data has run out before the scan did. The coefficients left behind
1124	// are zero, which the inverse DCT turns into a flat mid-grey, and that is what every
1125	// other decoder shows for the tail of a truncated file. Carrying on with whatever the
1126	// padding decodes to would fill it with noise instead.
1127	if ri == 0 {
1128	break;
1129	}
1130	todo -= 1;
1131	continue;
1132	}
1133	let (ux, uy) = (i % nx, i / nx);
1134	if single {
1135	let sc = scan.comps[0];
1136	res!(decode_block(&mut bits, frame, scan, &tabs[0], &mut st, 0, sc.ci, ux, uy));
1137	} else {
1138	for (k, sc) in scan.comps.iter().enumerate() {
1139	let (ch, cv) = {
1140	let c = &frame.comps[sc.ci];
1141	(c.h, c.v)
1142	};
1143	for by in 0..cv {
1144	for bx in 0..ch {
1145	res!(decode_block(
1146	&mut bits,
1147	frame,
1148	scan,
1149	&tabs[k],
1150	&mut st,
1151	k,
1152	sc.ci,
1153	ux * ch + bx,
1154	uy * cv + by,
1155	));
1156	}
1157	}
1158	}
1159	}
1160	if ri > 0 {
1161	todo -= 1;
1162	}
1163	}
1164	Ok(bits.pos)
1165	}
1166
1167	/// Decodes one block, by whichever of the five block codings the scan calls for.
1168	fn decode_block(
1169	bits: &mut Bits,
1170	frame: &mut Frame,
1171	scan: &Scan,
1172	tabs: &Tables,
1173	st: &mut ScanState,
1174	k: usize,
1175	ci: usize,
1176	bx: usize,
1177	by: usize,
1178	)
1179	-> Outcome<()>
1180	{
1181	let c = &mut frame.comps[ci];
1182	if bx >= c.bwp \|\| by >= c.bhp {
1183	return Ok(()); // Padding beyond the allocation, which no image sample depends on.
1184	}
1185	let at = c.at(bx, by);
1186	let blk = &mut c.coef[at..at + DCTSIZE2];
1187	if !frame.prog {
1188	return block_sequential(bits, tabs, &mut st.pred[k], blk);
1189	}
1190	match (scan.ss, scan.ah) {
1191	(0, 0) => block_dc_first(bits, tabs, &mut st.pred[k], blk, scan.al),
1192	(0, _) => {
1193	if bits.bit() != 0 {
1194	blk[0] \|= (1i32 << scan.al) as i16;
1195	}
1196	Ok(())
1197	},
1198	(_, 0) => block_ac_first(bits, tabs, st, blk, scan),
1199	(_, _) => block_ac_refine(bits, tabs, st, blk, scan),
1200	}
1201	}
1202
1203	/// The AC table a scan needs, or an error naming the slot that was never declared.
1204	fn need_ac<'a>(tabs: &'a Tables) -> Outcome<&'a Huff> {
1205	match tabs.ac {
1206	Some(t) => Ok(t),
1207	None => Err(err!(
1208	"A scan reads AC coefficients with a Huffman table its file never declared.";
1209	Invalid, Input, Decode, Missing)),
1210	}
1211	}
1212
1213	fn need_dc<'a>(tabs: &'a Tables) -> Outcome<&'a Huff> {
1214	match tabs.dc {
1215	Some(t) => Ok(t),
1216	None => Err(err!(
1217	"A scan reads DC coefficients with a Huffman table its file never declared.";
1218	Invalid, Input, Decode, Missing)),
1219	}
1220	}
1221
1222	/// Decodes a whole block, DC and AC together, as a sequential scan carries it.
1223	fn block_sequential(bits: &mut Bits, tabs: &Tables, pred: &mut i32, blk: &mut [i16]) -> Outcome<()> {
1224	let dct = res!(need_dc(tabs));
1225	let act = res!(need_ac(tabs));
1226	let t = res!(bits.huff(dct)) as u32;
1227	if t > 15 {
1228	return Err(err!(
1229	"A DC coefficient declares magnitude category {}, and the categories run to 15.", t;
1230	Invalid, Input, Decode, Range));
1231	}
1232	let diff = extend(bits.receive(t), t);
1233	*pred = pred.wrapping_add(diff);
1234	blk[0] = *pred as i16;
1235
1236	let mut k = 1usize;
1237	while k < DCTSIZE2 {
1238	let rs = res!(bits.huff(act));
1239	let s = (rs & 15) as u32;
1240	let r = (rs >> 4) as usize;
1241	if s == 0 {
1242	if r != 15 {
1243	break; // End of block.
1244	}
1245	k += 16; // A run of sixteen zeros.
1246	} else {
1247	k += r;
1248	if k >= DCTSIZE2 {
1249	return Err(err!(
1250	"An AC run of {} carries coefficient {} past the 63rd of its block.", r, k;
1251	Invalid, Input, Decode, Range));
1252	}
1253	blk[NATURAL[k]] = extend(bits.receive(s), s) as i16;
1254	k += 1;
1255	}
1256	}
1257	Ok(())
1258	}
1259
1260	/// Decodes the DC coefficient of a block in a progressive scan's first pass over it.
1261	fn block_dc_first(
1262	bits: &mut Bits,
1263	tabs: &Tables,
1264	pred: &mut i32,
1265	blk: &mut [i16],
1266	al: u32,
1267	)
1268	-> Outcome<()>
1269	{
1270	let dct = res!(need_dc(tabs));
1271	let t = res!(bits.huff(dct)) as u32;
1272	if t > 15 {
1273	return Err(err!(
1274	"A DC coefficient declares magnitude category {}, and the categories run to 15.", t;
1275	Invalid, Input, Decode, Range));
1276	}
1277	let diff = extend(bits.receive(t), t);
1278	*pred = pred.wrapping_add(diff);
1279	blk[0] = pred.wrapping_shl(al) as i16;
1280	Ok(())
1281	}
1282
1283	/// Decodes a band of AC coefficients in a progressive scan's first pass over them.
1284	fn block_ac_first(
1285	bits: &mut Bits,
1286	tabs: &Tables,
1287	st: &mut ScanState,
1288	blk: &mut [i16],
1289	scan: &Scan,
1290	)
1291	-> Outcome<()>
1292	{
1293	if st.eobrun > 0 {
1294	st.eobrun -= 1;
1295	return Ok(());
1296	}
1297	let act = res!(need_ac(tabs));
1298	let mut k = scan.ss;
1299	while k <= scan.se {
1300	let rs = res!(bits.huff(act));
1301	let s = (rs & 15) as u32;
1302	let r = (rs >> 4) as u32;
1303	if s == 0 {
1304	if r != 15 {
1305	st.eobrun = (1u32 << r) - 1;
1306	if r > 0 {
1307	st.eobrun += bits.receive(r);
1308	}
1309	break;
1310	}
1311	k += 15;
1312	} else {
1313	k += r as usize;
1314	if k > scan.se {
1315	return Err(err!(
1316	"An AC run of {} carries coefficient {} past the {}th, where the scan's band \
1317	ends.", r, k, scan.se;
1318	Invalid, Input, Decode, Range));
1319	}
1320	blk[NATURAL[k]] = (extend(bits.receive(s), s) << scan.al) as i16;
1321	}
1322	k += 1;
1323	}
1324	Ok(())
1325	}
1326
1327	/// Appends a bit to a band of AC coefficients a previous scan already placed.
1328	///
1329	/// This is the one block coding with no simple shape: a symbol names a run of coefficients that were
1330	/// zero before this scan, and the bits of the coefficients that were not zero are interleaved
1331	/// between them, one correction bit each, in the order they occur.
1332	fn block_ac_refine(
1333	bits: &mut Bits,
1334	tabs: &Tables,
1335	st: &mut ScanState,
1336	blk: &mut [i16],
1337	scan: &Scan,
1338	)
1339	-> Outcome<()>
1340	{
1341	let act = res!(need_ac(tabs));
1342	let p1 = 1i16 << scan.al; // The bit a newly nonzero positive coefficient takes.
1343	let m1 = (-1i16) << scan.al; // The same, negative.
1344	let mut k = scan.ss;
1345
1346	if st.eobrun == 0 {
1347	while k <= scan.se {
1348	let rs = res!(bits.huff(act));
1349	let s = rs & 15;
1350	let mut r = (rs >> 4) as i32;
1351	let mut place = 0i16;
1352	if s != 0 {
1353	if s != 1 {
1354	return Err(err!(
1355	"A refining AC scan declares a new coefficient of magnitude category {}, and \
1356	a refinement can only make a coefficient newly nonzero, category 1.", s;
1357	Invalid, Input, Decode));
1358	}
1359	place = if bits.bit() != 0 { p1 } else { m1 };
1360	} else if r != 15 {
1361	st.eobrun = 1u32 << r;
1362	if r > 0 {
1363	st.eobrun += bits.receive(r as u32);
1364	}
1365	break;
1366	}
1367	// Walk over the coefficients already nonzero, correcting each, and over `r` of those
1368	// still zero, to reach the one the symbol names.
1369	loop {
1370	if k > scan.se {
1371	break;
1372	}
1373	let pos = NATURAL[k];
1374	if blk[pos] != 0 {
1375	if bits.bit() != 0 && (blk[pos] & p1) == 0 {
1376	blk[pos] = if blk[pos] >= 0 {
1377	blk[pos].wrapping_add(p1)
1378	} else {
1379	blk[pos].wrapping_add(m1)
1380	};
1381	}
1382	} else {
1383	r -= 1;
1384	if r < 0 {
1385	break;
1386	}
1387	}
1388	k += 1;
1389	}
1390	if place != 0 && k <= scan.se {
1391	blk[NATURAL[k]] = place;
1392	}
1393	k += 1;
1394	}
1395	}
1396
1397	if st.eobrun > 0 {
1398	// The rest of the band lies inside an end-of-band run, so it carries correction bits for
1399	// the coefficients already nonzero and nothing else.
1400	while k <= scan.se {
1401	let pos = NATURAL[k];
1402	if blk[pos] != 0 && bits.bit() != 0 && (blk[pos] & p1) == 0 {
1403	blk[pos] = if blk[pos] >= 0 {
1404	blk[pos].wrapping_add(p1)
1405	} else {
1406	blk[pos].wrapping_add(m1)
1407	};
1408	}
1409	k += 1;
1410	}
1411	st.eobrun -= 1;
1412	}
1413	Ok(())
1414	}
1415
1416	// ┌───────────────────────────────────────────────────────────────────────────┐
1417	// │ UPSAMPLING AND OUTPUT │
1418	// └───────────────────────────────────────────────────────────────────────────┘
1419
1420	/// One component's samples, after the inverse DCT and before upsampling.
1421	struct Plane {
1422	data: Vec<u8>, // the samples, row-major
1423	stride: usize, // row distance, which the MCU grid may round up beyond dw
1424	dw: usize, // the width that carries image; the rest of a row is padding
1425	dh: usize, // and the height
1426	}
1427
1428	impl Plane {
1429
1430	/// A sample, with the coordinates clamped into the part that carries image.
1431	fn at(&self, x: usize, y: usize) -> i32 {
1432	let x = x.min(self.dw - 1);
1433	let y = y.min(self.dh - 1);
1434	self.data[y * self.stride + x] as i32
1435	}
1436	}
1437
1438	/// Expands a plane to the full image size.
1439	///
1440	/// Doubling in either direction takes the triangle filter libjpeg applies by default, which weights
1441	/// the nearer source sample three to one against its neighbour; every other ratio replicates. The
1442	/// filter matters: against a sharp chroma edge, replication and the triangle filter disagree by far
1443	/// more than the rounding of an inverse DCT does.
1444	fn upsample(p: &Plane, xf: usize, yf: usize, ow: usize, oh: usize) -> Vec<u8> {
1445	let mut out = vec![0u8; ow * oh];
1446	if xf == 1 && yf == 1 {
1447	for y in 0..oh {
1448	for x in 0..ow {
1449	out[y * ow + x] = p.at(x, y) as u8;
1450	}
1451	}
1452	return out;
1453	}
1454	if xf == 1 && yf == 2 {
1455	// Subsampled down the vertical only: the filter runs in that direction alone.
1456	for oy in 0..oh {
1457	let iy = oy / 2;
1458	let far = if oy % 2 == 0 {
1459	iy.saturating_sub(1)
1460	} else {
1461	(iy + 1).min(p.dh - 1)
1462	};
1463	// The two output rows take different rounding terms, as the horizontal filter's do.
1464	let r = if oy % 2 == 0 { 1 } else { 2 };
1465	for ox in 0..ow {
1466	out[oy * ow + ox] = clamp8((3 * p.at(ox, iy) + p.at(ox, far) + r) >> 2);
1467	}
1468	}
1469	return out;
1470	}
1471	// A plane only two samples wide has no interior for the filter to work over, and libjpeg drops
1472	// to replication there rather than filtering across the whole width.
1473	if xf == 2 && (yf == 1 \|\| yf == 2) && p.dw > 2 {
1474	for oy in 0..oh {
1475	let (near, far) = if yf == 1 {
1476	(oy, oy)
1477	} else {
1478	let iy = oy / 2;
1479	let far = if oy % 2 == 0 {
1480	iy.saturating_sub(1)
1481	} else {
1482	(iy + 1).min(p.dh - 1)
1483	};
1484	(iy, far)
1485	};
1486	// The column sums the filter runs along, weighted three to one vertically.
1487	let col = \|ix: usize\| -> i32 {
1488	if yf == 1 {
1489	p.at(ix, near)
1490	} else {
1491	3 * p.at(ix, near) + p.at(ix, far)
1492	}
1493	};
1494	// The rounding differs between the two, and between the two outputs of each: these are
1495	// the terms libjpeg's `h2v1_fancy_upsample` and `h2v2_fancy_upsample` add.
1496	let (shift, r_even, r_odd) = if yf == 1 {
1497	(2, 1, 2)
1498	} else {
1499	(4, 8, 7)
1500	};
1501	for ox in 0..ow {
1502	let ix = ox / 2;
1503	let this = col(ix);
1504	let v = if ox % 2 == 0 {
1505	if ix == 0 {
1506	(this * 4 + r_even) >> shift
1507	} else {
1508	(this * 3 + col(ix - 1) + r_even) >> shift
1509	}
1510	} else if ix + 1 >= p.dw {
1511	(this * 4 + r_odd) >> shift
1512	} else {
1513	(this * 3 + col(ix + 1) + r_odd) >> shift
1514	};
1515	out[oy * ow + ox] = clamp8(v);
1516	}
1517	}
1518	return out;
1519	}
1520	// Any other ratio: replicate.
1521	for oy in 0..oh {
1522	let sy = oy / yf;
1523	for ox in 0..ow {
1524	out[oy * ow + ox] = p.at(ox / xf, sy) as u8;
1525	}
1526	}
1527	out
1528	}
1529
1530	/// Scales a plane to an arbitrary size by nearest neighbour, for the reduced-scale decode.
1531	fn rescale(p: &Plane, ow: usize, oh: usize) -> Vec<u8> {
1532	let mut out = vec![0u8; ow * oh];
1533	for oy in 0..oh {
1534	let sy = (oy * p.dh) / oh;
1535	for ox in 0..ow {
1536	out[oy * ow + ox] = p.at((ox * p.dw) / ow, sy) as u8;
1537	}
1538	}
1539	out
1540	}
1541
1542	/// Which colour the components of a frame carry, given their count and what the file's application
1543	/// segments said.
1544	///
1545	/// The order of the tests is libjpeg's, and it matters: a JFIF segment settles the question by
1546	/// itself, because JFIF is defined as YCbCr. Files exist that carry a JFIF segment and an Adobe one
1547	/// declaring no transform, and reading the Adobe segment first turns them into false colour.
1548	fn space_of(comps: &[Comp], jfif: bool, adobe: Option<u8>) -> Outcome<Space> {
1549	match comps.len() {
1550	1 => Ok(Space::Grey),
1551	3 => {
1552	if jfif {
1553	return Ok(Space::Ycc);
1554	}
1555	if let Some(t) = adobe {
1556	return Ok(if t == 0 { Space::Rgb } else { Space::Ycc });
1557	}
1558	// With neither segment, component identifiers spelling RGB are the only sign that a
1559	// three-component frame is not YCbCr.
1560	if comps[0].id == b'R' && comps[1].id == b'G' && comps[2].id == b'B' {
1561	Ok(Space::Rgb)
1562	} else {
1563	Ok(Space::Ycc)
1564	}
1565	},
1566	4 => Ok(match adobe {
1567	Some(2) => Space::Ycck,
1568	_ => Space::Cmyk,
1569	}),
1570	n => Err(err!(
1571	"A frame of {} components has no colour interpretation this codec knows.", n;
1572	Invalid, Input, Decode, NoImpl)),
1573	}
1574	}
1575
1576	/// Turns the upsampled component channels into a pixmap.
1577	///
1578	/// The four-component spaces are Adobe's, where the stored samples are the complement of the ink,
1579	/// so a channel of 255 is no ink at all. Where a file carries no Adobe segment its four components
1580	/// are taken as ink directly.
1581	fn colourise(
1582	ch: &[Vec<u8>],
1583	w: usize,
1584	h: usize,
1585	space: Space,
1586	inverted: bool,
1587	)
1588	-> Outcome<Pixmap>
1589	{
1590	let mut pm = res!(Pixmap::new(w, h));
1591	let tab = YccTab::new();
1592	let out = pm.data_mut();
1593	for i in 0..(w * h) {
1594	let (r, g, b) = match space {
1595	Space::Grey => {
1596	let y = ch[0][i];
1597	(y, y, y)
1598	},
1599	Space::Rgb => (ch[0][i], ch[1][i], ch[2][i]),
1600	Space::Ycc => tab.rgb(ch[0][i], ch[1][i], ch[2][i]),
1601	Space::Cmyk \| Space::Ycck => {
1602	let (c, m, y) = if space == Space::Ycck {
1603	let (r, g, b) = tab.rgb(ch[0][i], ch[1][i], ch[2][i]);
1604	(255 - r, 255 - g, 255 - b)
1605	} else {
1606	(ch[0][i], ch[1][i], ch[2][i])
1607	};
1608	let k = ch[3][i];
1609	let (c, m, y, k) = if inverted {
1610	(c as u32, m as u32, y as u32, k as u32)
1611	} else {
1612	// No Adobe segment: the samples are ink, so complement them into the same form.
1613	(255 - c as u32, 255 - m as u32, 255 - y as u32, 255 - k as u32)
1614	};
1615	(
1616	((c * k + 127) / 255) as u8,
1617	((m * k + 127) / 255) as u8,
1618	((y * k + 127) / 255) as u8,
1619	)
1620	},
1621	};
1622	let at = i * 4;
1623	out[at] = r;
1624	out[at + 1] = g;
1625	out[at + 2] = b;
1626	out[at + 3] = 255;
1627	}
1628	Ok(pm)
1629	}
1630
1631	// ┌───────────────────────────────────────────────────────────────────────────┐
1632	// │ BLOCK SMOOTHING │
1633	// └───────────────────────────────────────────────────────────────────────────┘
1634	//
1635	// A progressive file whose later scans never arrived, or whose encoder stopped short of the last
1636	// approximation bit, holds blocks whose low-frequency detail is missing. Rendered as they stand
1637	// they show the flat squares of a half-loaded photograph. The specification's Annex K.8 estimates
1638	// the five lowest AC coefficients from the DC values of the eight neighbouring blocks, which is a
1639	// smooth surface fitted through the block means, and libjpeg applies it by default. A file whose
1640	// scans all completed is untouched, because there is then nothing to estimate.
1641
1642	// The five coefficients an estimate may fill in: their zigzag position, their natural position,
1643	// and the multiplier and neighbour combination Annex K.8 gives each.
1644	const SMOOTH: [(usize, usize, i64); 5] = [
1645	(1, 1, 36), // One cycle across.
1646	(2, 8, 36), // One cycle down.
1647	(3, 16, 9), // Two cycles down.
1648	(4, 9, 5), // One cycle each way.
1649	(5, 2, 9), // Two cycles across.
1650	];
1651
1652	/// Is this a frame block smoothing has anything to say about?
1653	///
1654	/// Every component's DC must have arrived, since the estimates are built from it, and at least one
1655	/// of the five estimated coefficients must be inexact somewhere.
1656	fn smoothing_helps(frame: &Frame) -> bool {
1657	if !frame.prog {
1658	return false;
1659	}
1660	let mut useful = false;
1661	for seen in &frame.seen {
1662	if seen[0] < 0 {
1663	return false;
1664	}
1665	for (zz, _, _) in SMOOTH {
1666	if seen[zz] != 0 {
1667	useful = true;
1668	}
1669	}
1670	}
1671	useful
1672	}
1673
1674	/// Fills in the five lowest AC coefficients of one block from its neighbours' DC values.
1675	///
1676	/// A coefficient is estimated only where it is still zero and no scan has pinned it down exactly.
1677	fn smooth(
1678	ws: &mut [i16; DCTSIZE2],
1679	coef: &[i16],
1680	c: &Comp,
1681	bx: usize,
1682	by: usize,
1683	q: &[u16; DCTSIZE2],
1684	seen: &[i8; DCTSIZE2],
1685	) {
1686	// The DC values of the three by three neighbourhood, with the edges replicating.
1687	let dc = \|dx: i32, dy: i32\| -> i64 {
1688	let x = (bx as i32 + dx).clamp(0, c.bw as i32 - 1) as usize;
1689	let y = (by as i32 + dy).clamp(0, c.bh as i32 - 1) as usize;
1690	coef[(y * c.bwp + x) * DCTSIZE2] as i64
1691	};
1692	let (d1, d2, d3) = (dc(-1, -1), dc(0, -1), dc(1, -1));
1693	let (d4, d5, d6) = (dc(-1, 0), dc(0, 0), dc(1, 0));
1694	let (d7, d8, d9) = (dc(-1, 1), dc(0, 1), dc(1, 1));
1695	let q00 = q[0] as i64;
1696
1697	for (zz, nat, mul) in SMOOTH {
1698	let al = seen[zz];
1699	if al == 0 \|\| ws[nat] != 0 {
1700	continue;
1701	}
1702	let comb = match zz {
1703	1 => d4 - d6,
1704	2 => d2 - d8,
1705	3 => d2 + d8 - 2 * d5,
1706	4 => d1 - d3 - d7 + d9,
1707	_ => d4 + d6 - 2 * d5,
1708	};
1709	let num = mul * q00 * comb;
1710	let qn = q[nat] as i64;
1711	let mut pred = ((qn << 7) + num.abs()) / (qn << 8);
1712	// An estimate may not claim more precision than the scans that did arrive left room for.
1713	if al > 0 && pred >= (1i64 << al) {
1714	pred = (1i64 << al) - 1;
1715	}
1716	if num < 0 {
1717	pred = -pred;
1718	}
1719	ws[nat] = pred as i16;
1720	}
1721	}
1722
1723	// ┌───────────────────────────────────────────────────────────────────────────┐
1724	// │ THE DECODER │
1725	// └───────────────────────────────────────────────────────────────────────────┘
1726
1727	/// Walks the marker segments of a file, decoding every scan it finds.
1728	fn parse(buf: &[u8]) -> Outcome<Reader> {
1729	if buf.len() < 2 \|\| buf[0] != 0xFF \|\| buf[1] != SOI {
1730	return Err(err!(
1731	"The bytes do not begin with a JPEG start-of-image marker."; Invalid, Input, Decode));
1732	}
1733	let mut r = Reader {
1734	quant: [None, None, None, None],
1735	dc: [None, None, None, None],
1736	ac: [None, None, None, None],
1737	ri: 0,
1738	jfif: false,
1739	adobe: None,
1740	frame: None,
1741	};
1742	let mut pos = 2usize;
1743	let mut scans = 0usize;
1744
1745	loop {
1746	let (marker, next) = match next_marker(buf, pos) {
1747	Ok(m) => m,
1748	Err(_) => break, // A file that stops after its last scan is one we have already read.
1749	};
1750	pos = next;
1751	match marker {
1752	SOI => (),
1753	EOI => break,
1754	TEM => (),
1755	RST0..=RST7 => (),
1756	0xFF => (),
1757	DQT => {
1758	let (a, b) = res!(segment(buf, pos, marker));
1759	res!(read_quant(&buf[a..b], &mut r.quant, pos));
1760	pos = b;
1761	},
1762	DHT => {
1763	let (a, b) = res!(segment(buf, pos, marker));
1764	res!(read_huff(&buf[a..b], &mut r.dc, &mut r.ac, pos));
1765	pos = b;
1766	},
1767	DRI => {
1768	let (a, b) = res!(segment(buf, pos, marker));
1769	if b - a < 2 {
1770	return Err(err!(
1771	"A DRI segment at offset {} carries {} bytes, and a restart interval is two.",
1772	pos, b - a;
1773	Invalid, Input, Decode));
1774	}
1775	r.ri = ((buf[a] as usize) << 8) \| (buf[a + 1] as usize);
1776	pos = b;
1777	},
1778	DAC => return Err(err!(
1779	"The file carries an arithmetic coding conditioning segment at offset {}. This codec \
1780	implements Huffman coding.", pos;
1781	Invalid, Input, Decode, NoImpl)),
1782	APP0..=APP15 => {
1783	let (a, b) = res!(segment(buf, pos, marker));
1784	if marker == APP0 && b - a >= 5 && &buf[a..a + 5] == b"JFIF\0" {
1785	r.jfif = true;
1786	}
1787	if marker == 0xEE && b - a >= 12 && &buf[a..a + 5] == b"Adobe" {
1788	r.adobe = Some(buf[b - 1]);
1789	}
1790	pos = b;
1791	},
1792	COM \| DNL => {
1793	let (_, b) = res!(segment(buf, pos, marker));
1794	pos = b;
1795	},
1796	SOS => {
1797	let (a, b) = res!(segment(buf, pos, marker));
1798	let frame = match r.frame.as_mut() {
1799	Some(f) => f,
1800	None => return Err(err!(
1801	"The scan at offset {} arrives before any frame header.", pos;
1802	Invalid, Input, Decode, Order)),
1803	};
1804	let scan = res!(read_scan(&buf[a..b], frame, pos));
1805	// Borrow the tables the scan names, refusing a slot the file never filled.
1806	let mut tabs = Vec::with_capacity(scan.comps.len());
1807	for sc in &scan.comps {
1808	let want_dc = !frame.prog \|\| (scan.ss == 0);
1809	let want_ac = !frame.prog \|\| (scan.ss != 0);
1810	if sc.td > 3 \|\| sc.ta > 3 {
1811	return Err(err!(
1812	"The scan at offset {} names Huffman slots {} and {}, and there are four \
1813	of each, 0 to 3.", pos, sc.td, sc.ta;
1814	Invalid, Input, Decode, Range));
1815	}
1816	if want_dc && r.dc[sc.td].is_none() && scan.ah == 0 {
1817	return Err(err!(
1818	"The scan at offset {} reads component {} with DC Huffman table {}, which \
1819	the file has not declared.", pos, frame.comps[sc.ci].id, sc.td;
1820	Invalid, Input, Decode, Missing));
1821	}
1822	if want_ac && r.ac[sc.ta].is_none() {
1823	return Err(err!(
1824	"The scan at offset {} reads component {} with AC Huffman table {}, which \
1825	the file has not declared.", pos, frame.comps[sc.ci].id, sc.ta;
1826	Invalid, Input, Decode, Missing));
1827	}
1828	tabs.push(Tables {
1829	dc: r.dc[sc.td].as_ref(),
1830	ac: r.ac[sc.ta].as_ref(),
1831	});
1832	}
1833	for sc in &scan.comps {
1834	for k in scan.ss..=scan.se.min(DCTSIZE2 - 1) {
1835	frame.seen[sc.ci][k] = scan.al as i8;
1836	}
1837	}
1838	pos = res!(decode_scan(buf, b, frame, &scan, &tabs, r.ri));
1839	scans += 1;
1840	},
1841	0xC0..=0xCF => {
1842	let (a, b) = res!(segment(buf, pos, marker));
1843	if r.frame.is_some() {
1844	return Err(err!(
1845	"The file carries a second frame header at offset {}. This codec implements \
1846	the single-frame modes.", pos;
1847	Invalid, Input, Decode, NoImpl));
1848	}
1849	r.frame = Some(res!(read_frame(&buf[a..b], marker, pos, true)));
1850	pos = b;
1851	},
1852	_ => {
1853	let (_, b) = res!(segment(buf, pos, marker));
1854	pos = b;
1855	},
1856	}
1857	}
1858
1859	if r.frame.is_none() {
1860	return Err(err!("The file carries no frame header."; Invalid, Input, Decode, Missing));
1861	}
1862	if scans == 0 {
1863	return Err(err!("The file carries no scan."; Invalid, Input, Decode, Missing));
1864	}
1865	Ok(r)
1866	}
1867
1868	/// The quantisation table a component names, or an error naming the slot the file left empty.
1869	fn quant_of(r: &Reader, c: &Comp) -> Outcome<[u16; DCTSIZE2]> {
1870	match r.quant[c.tq] {
1871	Some(t) => Ok(t),
1872	None => Err(err!(
1873	"Component {} reads quantisation table {}, which the file has not declared.", c.id, c.tq;
1874	Invalid, Input, Decode, Missing)),
1875	}
1876	}
1877
1878	/// The pixels come out opaque: JPEG carries no alpha channel.
1879	pub fn decode(buf: &[u8]) -> Outcome<Pixmap> {
1880	let mut r = res!(parse(buf));
1881	let mut frame = match r.frame.take() {
1882	Some(f) => f,
1883	None => return Err(err!("The file carries no frame header."; Invalid, Input, Decode, Missing)),
1884	};
1885	let space = res!(space_of(&frame.comps, r.jfif, r.adobe));
1886	let (w, h) = (frame.w, frame.h);
1887	let (hmax, vmax) = (frame.hmax, frame.vmax);
1888	let smoothing = smoothing_helps(&frame);
1889	let seen = frame.seen.clone();
1890
1891	let mut chans: Vec<Vec<u8>> = Vec::with_capacity(frame.comps.len());
1892	for (ci, c) in frame.comps.iter_mut().enumerate() {
1893	let q = res!(quant_of(&r, c));
1894	let stride = c.bwp * DCTSIZE;
1895	let mut plane = Plane {
1896	data: vec![0u8; stride * c.bhp * DCTSIZE],
1897	stride,
1898	dw: c.dw,
1899	dh: c.dh,
1900	};
1901	let coef = std::mem::take(&mut c.coef);
1902	// Only the blocks that carry image are transformed: the upsampler reads no further, and the
1903	// MCU grid's padding blocks would only be cropped away.
1904	let mut ws = [0i16; DCTSIZE2];
1905	for by in 0..c.bh {
1906	for bx in 0..c.bw {
1907	let at = (by * c.bwp + bx) * DCTSIZE2;
1908	let src = if smoothing {
1909	ws.copy_from_slice(&coef[at..at + DCTSIZE2]);
1910	smooth(&mut ws, &coef, c, bx, by, &q, &seen[ci]);
1911	&ws[..]
1912	} else {
1913	&coef[at..at + DCTSIZE2]
1914	};
1915	idct(
1916	src,
1917	&q,
1918	&mut plane.data,
1919	by * DCTSIZE * stride + bx * DCTSIZE,
1920	stride,
1921	);
1922	}
1923	}
1924	drop(coef);
1925	let xf = hmax / c.h;
1926	let yf = vmax / c.v;
1927	let exact = hmax % c.h == 0 && vmax % c.v == 0;
1928	chans.push(if exact {
1929	upsample(&plane, xf, yf, w, h)
1930	} else {
1931	rescale(&plane, w, h)
1932	});
1933	}
1934	colourise(&chans, w, h, space, r.adobe.is_some())
1935	}
1936
1937	/// Decodes a JPEG at an eighth of its size, from the DC coefficient of each block alone.
1938	///
1939	/// One coefficient a block is the block's mean, so this costs the entropy decoding and nothing else:
1940	/// no inverse DCT runs, and the image never exists at full size. It is what a thumbnail wants.
1941	pub fn decode_eighth(buf: &[u8]) -> Outcome<Pixmap> {
1942	let mut r = res!(parse(buf));
1943	let mut frame = match r.frame.take() {
1944	Some(f) => f,
1945	None => return Err(err!("The file carries no frame header."; Invalid, Input, Decode, Missing)),
1946	};
1947	let space = res!(space_of(&frame.comps, r.jfif, r.adobe));
1948	let w = ceil_div(frame.w, DCTSIZE);
1949	let h = ceil_div(frame.h, DCTSIZE);
1950
1951	let mut chans: Vec<Vec<u8>> = Vec::with_capacity(frame.comps.len());
1952	for c in frame.comps.iter_mut() {
1953	let q = res!(quant_of(&r, c));
1954	let coef = std::mem::take(&mut c.coef);
1955	let mut plane = Plane {
1956	data: vec![0u8; c.bwp * c.bhp],
1957	stride: c.bwp,
1958	dw: c.bw,
1959	dh: c.bh,
1960	};
1961	for by in 0..c.bhp {
1962	for bx in 0..c.bwp {
1963	let at = (by * c.bwp + bx) * DCTSIZE2;
1964	plane.data[by * c.bwp + bx] = idct_dc(&coef[at..at + DCTSIZE2], &q);
1965	}
1966	}
1967	drop(coef);
1968	chans.push(rescale(&plane, w, h));
1969	}
1970	colourise(&chans, w, h, space, r.adobe.is_some())
1971	}
1972
1973	/// Reads a JPEG's size without decoding a single block.
1974	///
1975	/// Only the marker segments up to the frame header are walked, so this costs a few hundred bytes of
1976	/// reading whatever the size of the file.
1977	pub fn dimensions(buf: &[u8]) -> Outcome<(usize, usize)> {
1978	if buf.len() < 2 \|\| buf[0] != 0xFF \|\| buf[1] != SOI {
1979	return Err(err!(
1980	"The bytes do not begin with a JPEG start-of-image marker."; Invalid, Input, Decode));
1981	}
1982	let mut pos = 2usize;
1983	loop {
1984	let (marker, next) = res!(next_marker(buf, pos));
1985	pos = next;
1986	match marker {
1987	SOI \| TEM \| RST0..=RST7 \| 0xFF => (),
1988	EOI \| SOS => return Err(err!(
1989	"The file reaches its {} at offset {} without a frame header.",
1990	if marker == EOI { "end" } else { "first scan" }, pos;
1991	Invalid, Input, Decode, Missing)),
1992	0xC0..=0xCF if marker != DHT && marker != DAC && marker != 0xC8 => {
1993	let (a, b) = res!(segment(buf, pos, marker));
1994	let f = res!(read_frame(&buf[a..b], marker, pos, false));
1995	return Ok((f.w, f.h));
1996	},
1997	_ => {
1998	let (_, b) = res!(segment(buf, pos, marker));
1999	pos = b;
2000	},
2001	}
2002	}
2003	}
2004
2005	// ┌───────────────────────────────────────────────────────────────────────────┐
2006	// │ THE ENCODER │
2007	// └───────────────────────────────────────────────────────────────────────────┘
2008
2009	/// How much the two chrominance channels are reduced against the luminance.
2010	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
2011	pub enum Chroma {
2012	Full, // 4:4:4 -- a chrominance sample for every pixel
2013	Half, // 4:2:2 -- one for every two pixels across
2014	Quarter, // 4:2:0 -- one for every two across and two down
2015	}
2016
2017	impl Chroma {
2018
2019	/// The horizontal and vertical sampling factors the luminance takes against it.
2020	fn factors(&self) -> (usize, usize) {
2021	match self {
2022	Self::Full => (1, 1),
2023	Self::Half => (2, 1),
2024	Self::Quarter => (2, 2),
2025	}
2026	}
2027	}
2028
2029	/// What an encoder is asked for.
2030	#[derive(Clone, Copy, Debug)]
2031	pub struct Options {
2032	pub quality: u8, // 1 to 100, scaling the tables the way libjpeg's does
2033	pub chroma: Chroma, // ignored for a greyscale image
2034	pub grey: bool, // write one luminance component rather than three
2035	}
2036
2037	impl Default for Options {
2038
2039	/// Quality 85 with 4:2:0 chroma, which is what a photograph is usually wanted at.
2040	fn default() -> Self {
2041	Self {
2042	quality: 85,
2043	chroma: Chroma::Quarter,
2044	grey: false,
2045	}
2046	}
2047	}
2048
2049	// The luminance quantisation table of the specification's Annex K, in natural order.
2050	const QUANT_LUMA: [u16; DCTSIZE2] = [
2051	16, 11, 10, 16, 24, 40, 51, 61,
2052	12, 12, 14, 19, 26, 58, 60, 55,
2053	14, 13, 16, 24, 40, 57, 69, 56,
2054	14, 17, 22, 29, 51, 87, 80, 62,
2055	18, 22, 37, 56, 68, 109, 103, 77,
2056	24, 35, 55, 64, 81, 104, 113, 92,
2057	49, 64, 78, 87, 103, 121, 120, 101,
2058	72, 92, 95, 98, 112, 100, 103, 99,
2059	];
2060
2061	// The chrominance quantisation table of the specification's Annex K, in natural order.
2062	const QUANT_CHROMA: [u16; DCTSIZE2] = [
2063	17, 18, 24, 47, 99, 99, 99, 99,
2064	18, 21, 26, 66, 99, 99, 99, 99,
2065	24, 26, 56, 99, 99, 99, 99, 99,
2066	47, 66, 99, 99, 99, 99, 99, 99,
2067	99, 99, 99, 99, 99, 99, 99, 99,
2068	99, 99, 99, 99, 99, 99, 99, 99,
2069	99, 99, 99, 99, 99, 99, 99, 99,
2070	99, 99, 99, 99, 99, 99, 99, 99,
2071	];
2072
2073	//// The Annex K Huffman tables. A BITS array is the count of codes at each length, indexed by that
2074	//// length; a VALS array is the symbols those codes name, in canonical code order.
2075	const DC_LUMA_BITS: [u8; 17] = [0, 0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0];
2076	const DC_CHROMA_BITS: [u8; 17] = [0, 0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0];
2077	const DC_VALS: [u8; 12] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]; // the magnitude categories
2078
2079	const AC_LUMA_BITS: [u8; 17] = [0, 0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 0x7D];
2080
2081	const AC_LUMA_VALS: [u8; 162] = [
2082	0x01, 0x02, 0x03, 0x00, 0x04, 0x11, 0x05, 0x12,
2083	0x21, 0x31, 0x41, 0x06, 0x13, 0x51, 0x61, 0x07,
2084	0x22, 0x71, 0x14, 0x32, 0x81, 0x91, 0xA1, 0x08,
2085	0x23, 0x42, 0xB1, 0xC1, 0x15, 0x52, 0xD1, 0xF0,
2086	0x24, 0x33, 0x62, 0x72, 0x82, 0x09, 0x0A, 0x16,
2087	0x17, 0x18, 0x19, 0x1A, 0x25, 0x26, 0x27, 0x28,
2088	0x29, 0x2A, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39,
2089	0x3A, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49,
2090	0x4A, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59,
2091	0x5A, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69,
2092	0x6A, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79,
2093	0x7A, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89,
2094	0x8A, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98,
2095	0x99, 0x9A, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7,
2096	0xA8, 0xA9, 0xAA, 0xB2, 0xB3, 0xB4, 0xB5, 0xB6,
2097	0xB7, 0xB8, 0xB9, 0xBA, 0xC2, 0xC3, 0xC4, 0xC5,
2098	0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xD2, 0xD3, 0xD4,
2099	0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xE1, 0xE2,
2100	0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA,
2101	0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8,
2102	0xF9, 0xFA,
2103	];
2104
2105	const AC_CHROMA_BITS: [u8; 17] = [0, 0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 0x77];
2106
2107	const AC_CHROMA_VALS: [u8; 162] = [
2108	0x00, 0x01, 0x02, 0x03, 0x11, 0x04, 0x05, 0x21,
2109	0x31, 0x06, 0x12, 0x41, 0x51, 0x07, 0x61, 0x71,
2110	0x13, 0x22, 0x32, 0x81, 0x08, 0x14, 0x42, 0x91,
2111	0xA1, 0xB1, 0xC1, 0x09, 0x23, 0x33, 0x52, 0xF0,
2112	0x15, 0x62, 0x72, 0xD1, 0x0A, 0x16, 0x24, 0x34,
2113	0xE1, 0x25, 0xF1, 0x17, 0x18, 0x19, 0x1A, 0x26,
2114	0x27, 0x28, 0x29, 0x2A, 0x35, 0x36, 0x37, 0x38,
2115	0x39, 0x3A, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48,
2116	0x49, 0x4A, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58,
2117	0x59, 0x5A, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68,
2118	0x69, 0x6A, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
2119	0x79, 0x7A, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
2120	0x88, 0x89, 0x8A, 0x92, 0x93, 0x94, 0x95, 0x96,
2121	0x97, 0x98, 0x99, 0x9A, 0xA2, 0xA3, 0xA4, 0xA5,
2122	0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xB2, 0xB3, 0xB4,
2123	0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xC2, 0xC3,
2124	0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xD2,
2125	0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA,
2126	0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9,
2127	0xEA, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8,
2128	0xF9, 0xFA,
2129	];
2130
2131	/// A Huffman table in the form an encoder wants: a code and a length for each symbol.
2132	struct Codes {
2133	code: [u16; 256], // the code of each symbol, zero where the table has none
2134	len: [u8; 256], // and its length
2135	}
2136
2137	impl Codes {
2138
2139	/// Derives the codes from a count of codes at each length and the symbols they name.
2140	fn new(counts: &[u8; 17], vals: &[u8]) -> Outcome<Self> {
2141	let mut t = Self { code: [0; 256], len: [0; 256] };
2142	let mut code = 0u32;
2143	let mut k = 0usize;
2144	for l in 1..=16usize {
2145	for _ in 0..counts[l] {
2146	let s = match vals.get(k) {
2147	Some(s) => *s as usize,
2148	None => return Err(err!(
2149	"A Huffman table declares more codes than it carries symbols.";
2150	Bug, Invalid, Input)),
2151	};
2152	t.code[s] = code as u16;
2153	t.len[s] = l as u8;
2154	code += 1;
2155	k += 1;
2156	}
2157	code <<= 1;
2158	}
2159	Ok(t)
2160	}
2161	}
2162
2163	/// A writer of the bits of an entropy-coded segment, stuffing a zero after every 0xFF it emits.
2164	struct BitWriter {
2165	out: Vec<u8>, // the bytes written so far
2166	acc: u32, // the bits not yet whole, in the low cnt positions
2167	cnt: u32, // how many bits of acc are pending
2168	}
2169
2170	impl BitWriter {
2171
2172	fn new() -> Self {
2173	Self { out: Vec::new(), acc: 0, cnt: 0 }
2174	}
2175
2176	/// Appends the low `len` bits of a code, `len` being at most 16.
2177	fn put(&mut self, code: u32, len: u32) {
2178	if len == 0 {
2179	return;
2180	}
2181	self.acc = (self.acc << len) \| (code & ((1u32 << len) - 1));
2182	self.cnt += len;
2183	while self.cnt >= 8 {
2184	self.cnt -= 8;
2185	let b = ((self.acc >> self.cnt) & 0xFF) as u8;
2186	self.out.push(b);
2187	if b == 0xFF {
2188	self.out.push(0x00);
2189	}
2190	}
2191	}
2192
2193	/// Appends a symbol's Huffman code, refusing a symbol the table never gave one.
2194	fn sym(&mut self, t: &Codes, s: u8) -> Outcome<()> {
2195	let i = s as usize;
2196	if t.len[i] == 0 {
2197	return Err(err!(
2198	"The encoder's Huffman table has no code for the symbol {:#04X}.", s;
2199	Bug, Invalid, Encode));
2200	}
2201	self.put(t.code[i] as u32, t.len[i] as u32);
2202	Ok(())
2203	}
2204
2205	/// Pads the last byte with one bits, as the specification requires, and yields the bytes.
2206	fn finish(mut self) -> Vec<u8> {
2207	if self.cnt > 0 {
2208	let pad = 8 - self.cnt;
2209	self.put((1u32 << pad) - 1, pad);
2210	}
2211	self.out
2212	}
2213	}
2214
2215	/// The magnitude category of a coefficient difference, and the bits that follow it.
2216	fn category(v: i32) -> (u8, u32) {
2217	let mag = v.unsigned_abs();
2218	let mut s = 0u8;
2219	let mut t = mag;
2220	while t > 0 {
2221	s += 1;
2222	t >>= 1;
2223	}
2224	let bits = if v < 0 {
2225	(v + (1i32 << s) - 1) as u32
2226	} else {
2227	v as u32
2228	};
2229	(s, bits & ((1u32 << s.max(1)) - 1))
2230	}
2231
2232	/// The cosines the forward DCT needs, indexed by sample then frequency.
2233	fn cos_table() -> [[f32; DCTSIZE]; DCTSIZE] {
2234	let mut t = [[0.0f32; DCTSIZE]; DCTSIZE];
2235	for (x, row) in t.iter_mut().enumerate() {
2236	for (u, c) in row.iter_mut().enumerate() {
2237	let s = if u == 0 {
2238	(0.5f32).sqrt()
2239	} else {
2240	1.0
2241	};
2242	c = s (((2 * x + 1) as f32) * (u as f32) * std::f32::consts::PI / 16.0).cos();
2243	}
2244	}
2245	t
2246	}
2247
2248	/// Takes the forward DCT of one block of samples and quantises it, in natural order.
2249	fn fdct(samples: &[u8], at: usize, stride: usize, q: &[u16; DCTSIZE2], cos: &[[f32; DCTSIZE]; DCTSIZE])
2250	-> [i32; DCTSIZE2]
2251	{
2252	// The rows first, then the columns: the two-dimensional transform is separable.
2253	let mut rows = [0.0f32; DCTSIZE2];
2254	for y in 0..DCTSIZE {
2255	for u in 0..DCTSIZE {
2256	let mut s = 0.0f32;
2257	for x in 0..DCTSIZE {
2258	s += ((samples[at + y * stride + x] as f32) - 128.0) * cos[x][u];
2259	}
2260	rows[y * DCTSIZE + u] = s;
2261	}
2262	}
2263	let mut out = [0i32; DCTSIZE2];
2264	for u in 0..DCTSIZE {
2265	for v in 0..DCTSIZE {
2266	let mut s = 0.0f32;
2267	for y in 0..DCTSIZE {
2268	s += rows[y * DCTSIZE + u] * cos[y][v];
2269	}
2270	let c = s / 4.0;
2271	let d = q[v * DCTSIZE + u] as f32;
2272	out[v * DCTSIZE + u] = (c / d).round() as i32;
2273	}
2274	}
2275	out
2276	}
2277
2278	/// Scales an Annex K quantisation table for a quality, the way libjpeg's `jpeg_set_quality` does.
2279	fn scale_quant(base: &[u16; DCTSIZE2], quality: u8) -> [u16; DCTSIZE2] {
2280	let q = quality.clamp(1, 100) as i32;
2281	let scale = if q < 50 {
2282	5000 / q
2283	} else {
2284	200 - q * 2
2285	};
2286	let mut t = [0u16; DCTSIZE2];
2287	for (i, v) in base.iter().enumerate() {
2288	let s = ((v as i32) scale + 50) / 100;
2289	t[i] = s.clamp(1, 255) as u16;
2290	}
2291	t
2292	}
2293
2294	/// Appends a marker segment: its marker, its length, and its payload.
2295	fn seg(out: &mut Vec<u8>, marker: u8, body: &[u8]) {
2296	out.push(0xFF);
2297	out.push(marker);
2298	let len = body.len() + 2;
2299	out.push((len >> 8) as u8);
2300	out.push((len & 0xFF) as u8);
2301	out.extend_from_slice(body);
2302	}
2303
2304	/// One component being encoded: its samples, padded out to whole MCUs.
2305	struct EncComp {
2306	id: u8, // 1 for luminance, 2 and 3 for the chrominances
2307	h: usize, // horizontal sampling factor
2308	v: usize, // vertical sampling factor
2309	tbl: usize, // table pair: 0 for luminance, 1 for chrominance
2310	data: Vec<u8>, // the samples, bw * 8 to a row
2311	stride: usize, // the distance between rows
2312	}
2313
2314	/// Encodes a pixmap as a baseline JPEG at the default quality.
2315	///
2316	/// JPEG carries no alpha channel, so a pixel that is not opaque is composited over white first.
2317	pub fn encode(pm: &Pixmap) -> Outcome<Vec<u8>> {
2318	encode_with(pm, &Options::default())
2319	}
2320
2321	/// Encodes a pixmap as a baseline JPEG.
2322	///
2323	/// JPEG carries no alpha channel, so a pixel that is not opaque is composited over white first.
2324	pub fn encode_with(pm: &Pixmap, opts: &Options) -> Outcome<Vec<u8>> {
2325	if opts.quality < 1 \|\| opts.quality > 100 {
2326	return Err(err!(
2327	"A JPEG quality runs from 1 to 100, and {} was asked for.", opts.quality;
2328	Invalid, Input, Range));
2329	}
2330	let (w, h) = (pm.width(), pm.height());
2331	let (hf, vf) = if opts.grey {
2332	(1, 1)
2333	} else {
2334	opts.chroma.factors()
2335	};
2336	let mcux = ceil_div(w, DCTSIZE * hf);
2337	let mcuy = ceil_div(h, DCTSIZE * vf);
2338
2339	// The colour planes, at full size, over white.
2340	let src = pm.data();
2341	let n = w * h;
2342	let mut y = vec![0u8; n];
2343	let mut cb = vec![0u8; n];
2344	let mut cr = vec![0u8; n];
2345	for i in 0..n {
2346	let a = src[i * 4 + 3] as u32;
2347	let over = \|c: u8\| -> i32 {
2348	if a == 255 {
2349	c as i32
2350	} else {
2351	(((c as u32) * a + 255 * (255 - a) + 127) / 255) as i32
2352	}
2353	};
2354	let (r, g, b) = (over(src[i * 4]), over(src[i * 4 + 1]), over(src[i * 4 + 2]));
2355	// The forward colour transform, at sixteen fractional bits, as libjpeg's is.
2356	y[i] = clamp8((19595 * r + 38470 * g + 7471 * b + 32768) >> 16);
2357	cb[i] = clamp8(((-11056 * r - 21712 * g + 32768 * b + (128 << 16) + 32768) >> 16).clamp(0, 255));
2358	cr[i] = clamp8(((32768 * r - 27440 * g - 5328 * b + (128 << 16) + 32768) >> 16).clamp(0, 255));
2359	}
2360
2361	let mut comps: Vec<EncComp> = Vec::new();
2362	comps.push(EncComp {
2363	id: 1,
2364	h: hf,
2365	v: vf,
2366	tbl: 0,
2367	data: pad_plane(&y, w, h, mcux * hf * DCTSIZE, mcuy * vf * DCTSIZE),
2368	stride: mcux * hf * DCTSIZE,
2369	});
2370	if !opts.grey {
2371	let cw = ceil_div(w, hf);
2372	let chh = ceil_div(h, vf);
2373	let (dcb, dcr) = (box_down(&cb, w, h, hf, vf), box_down(&cr, w, h, hf, vf));
2374	for (id, plane) in [(2u8, dcb), (3u8, dcr)] {
2375	comps.push(EncComp {
2376	id,
2377	h: 1,
2378	v: 1,
2379	tbl: 1,
2380	data: pad_plane(&plane, cw, chh, mcux * DCTSIZE, mcuy * DCTSIZE),
2381	stride: mcux * DCTSIZE,
2382	});
2383	}
2384	}
2385
2386	let ql = scale_quant(&QUANT_LUMA, opts.quality);
2387	let qc = scale_quant(&QUANT_CHROMA, opts.quality);
2388	let quants = [ql, qc];
2389
2390	let mut out: Vec<u8> = Vec::with_capacity(n / 4 + 1024);
2391	out.push(0xFF);
2392	out.push(SOI);
2393
2394	// A JFIF segment, declaring square pixels of no particular density.
2395	seg(&mut out, APP0, &[
2396	b'J', b'F', b'I', b'F', 0x00,
2397	0x01, 0x01, // Version 1.1.
2398	0x00, // Density in no units.
2399	0x00, 0x01, 0x00, 0x01, // One by one.
2400	0x00, 0x00, // No thumbnail.
2401	]);
2402
2403	// The quantisation tables, in zigzag order, at eight bits.
2404	let ntbl = if opts.grey { 1 } else { 2 };
2405	for (i, q) in quants.iter().enumerate().take(ntbl) {
2406	let mut body = Vec::with_capacity(1 + DCTSIZE2);
2407	body.push(i as u8);
2408	for k in 0..DCTSIZE2 {
2409	body.push(q[NATURAL[k]] as u8);
2410	}
2411	seg(&mut out, DQT, &body);
2412	}
2413
2414	// The frame header.
2415	let mut body = Vec::with_capacity(8 + comps.len() * 3);
2416	body.push(8);
2417	body.push((h >> 8) as u8);
2418	body.push((h & 0xFF) as u8);
2419	body.push((w >> 8) as u8);
2420	body.push((w & 0xFF) as u8);
2421	body.push(comps.len() as u8);
2422	for c in &comps {
2423	body.push(c.id);
2424	body.push(((c.h as u8) << 4) \| (c.v as u8));
2425	body.push(c.tbl as u8);
2426	}
2427	seg(&mut out, 0xC0, &body);
2428
2429	// The Huffman tables.
2430	let dc_codes = [
2431	res!(Codes::new(&DC_LUMA_BITS, &DC_VALS)),
2432	res!(Codes::new(&DC_CHROMA_BITS, &DC_VALS)),
2433	];
2434	let ac_codes = [
2435	res!(Codes::new(&AC_LUMA_BITS, &AC_LUMA_VALS)),
2436	res!(Codes::new(&AC_CHROMA_BITS, &AC_CHROMA_VALS)),
2437	];
2438	let decl: &[(u8, &[u8; 17], &[u8])] = &[
2439	(0x00, &DC_LUMA_BITS, &DC_VALS),
2440	(0x10, &AC_LUMA_BITS, &AC_LUMA_VALS),
2441	(0x01, &DC_CHROMA_BITS, &DC_VALS),
2442	(0x11, &AC_CHROMA_BITS, &AC_CHROMA_VALS),
2443	];
2444	for (tc, bits, vals) in decl.iter().take(if opts.grey { 2 } else { 4 }) {
2445	let mut body = Vec::with_capacity(17 + vals.len());
2446	body.push(*tc);
2447	body.extend_from_slice(&bits[1..17]);
2448	body.extend_from_slice(vals);
2449	seg(&mut out, DHT, &body);
2450	}
2451
2452	// The scan header.
2453	let mut body = Vec::with_capacity(4 + comps.len() * 2);
2454	body.push(comps.len() as u8);
2455	for c in &comps {
2456	body.push(c.id);
2457	body.push(((c.tbl as u8) << 4) \| (c.tbl as u8));
2458	}
2459	body.push(0); // First coefficient of the band.
2460	body.push(63); // Last coefficient.
2461	body.push(0); // No successive approximation.
2462	seg(&mut out, SOS, &body);
2463
2464	// The entropy-coded data, one MCU at a time.
2465	let cos = cos_table();
2466	let mut bw = BitWriter::new();
2467	let mut pred = vec![0i32; comps.len()];
2468	for my in 0..mcuy {
2469	for mx in 0..mcux {
2470	for (ci, c) in comps.iter().enumerate() {
2471	for by in 0..c.v {
2472	for bx in 0..c.h {
2473	let px = (mx * c.h + bx) * DCTSIZE;
2474	let py = (my * c.v + by) * DCTSIZE;
2475	let blk = fdct(
2476	&c.data,
2477	py * c.stride + px,
2478	c.stride,
2479	&quants[c.tbl],
2480	&cos,
2481	);
2482	res!(emit_block(
2483	&mut bw,
2484	&blk,
2485	&dc_codes[c.tbl],
2486	&ac_codes[c.tbl],
2487	&mut pred[ci],
2488	));
2489	}
2490	}
2491	}
2492	}
2493	}
2494	out.extend_from_slice(&bw.finish());
2495	out.push(0xFF);
2496	out.push(EOI);
2497	Ok(out)
2498	}
2499
2500	/// Writes one quantised block: the DC difference, then the AC coefficients in zigzag order.
2501	fn emit_block(
2502	bw: &mut BitWriter,
2503	blk: &[i32; DCTSIZE2],
2504	dc: &Codes,
2505	ac: &Codes,
2506	pred: &mut i32,
2507	)
2508	-> Outcome<()>
2509	{
2510	let diff = blk[0] - *pred;
2511	*pred = blk[0];
2512	let (s, bits) = category(diff);
2513	res!(bw.sym(dc, s));
2514	if s > 0 {
2515	bw.put(bits, s as u32);
2516	}
2517
2518	let mut run = 0u8;
2519	for k in 1..DCTSIZE2 {
2520	let v = blk[NATURAL[k]];
2521	if v == 0 {
2522	run += 1;
2523	continue;
2524	}
2525	while run > 15 {
2526	res!(bw.sym(ac, 0xF0)); // A run of sixteen zeros.
2527	run -= 16;
2528	}
2529	let (s, bits) = category(v);
2530	if s > 10 {
2531	return Err(err!(
2532	"A quantised coefficient of {} needs magnitude category {}, and a baseline AC \
2533	coefficient runs to 10.", v, s;
2534	Bug, Invalid, Encode, Range));
2535	}
2536	res!(bw.sym(ac, (run << 4) \| s));
2537	bw.put(bits, s as u32);
2538	run = 0;
2539	}
2540	if run > 0 {
2541	res!(bw.sym(ac, 0x00)); // End of block.
2542	}
2543	Ok(())
2544	}
2545
2546	/// Copies a plane into a larger one, replicating its last row and column into the padding.
2547	///
2548	/// The padding is what the blocks beyond the image's edge are filled with, and replication is what
2549	/// libjpeg uses: it costs the fewest bits, because it adds no edge for the transform to describe.
2550	fn pad_plane(src: &[u8], w: usize, h: usize, pw: usize, ph: usize) -> Vec<u8> {
2551	let mut out = vec![0u8; pw * ph];
2552	for y in 0..ph {
2553	let sy = y.min(h - 1);
2554	for x in 0..pw {
2555	out[y * pw + x] = src[sy * w + x.min(w - 1)];
2556	}
2557	}
2558	out
2559	}
2560
2561	/// Reduces a plane by averaging each box of `hf` by `vf` samples.
2562	fn box_down(src: &[u8], w: usize, h: usize, hf: usize, vf: usize) -> Vec<u8> {
2563	if hf == 1 && vf == 1 {
2564	return src.to_vec();
2565	}
2566	let (dw, dh) = (ceil_div(w, hf), ceil_div(h, vf));
2567	let mut out = vec![0u8; dw * dh];
2568	let half = ((hf * vf) / 2) as u32;
2569	for y in 0..dh {
2570	for x in 0..dw {
2571	let mut sum = 0u32;
2572	for j in 0..vf {
2573	let sy = (y * vf + j).min(h - 1);
2574	for i in 0..hf {
2575	let sx = (x * hf + i).min(w - 1);
2576	sum += src[sy * w + sx] as u32;
2577	}
2578	}
2579	out[y * dw + x] = ((sum + half) / ((hf * vf) as u32)) as u8;
2580	}
2581	}
2582	out
2583	}
2584
2585	#[cfg(test)]
2586	mod tests {
2587	use super::*;
2588
2589	/// A small pixmap with a hard edge in it, so that the AC coefficients are not all zero.
2590	fn sample(w: usize, h: usize) -> Outcome<Pixmap> {
2591	let mut pm = res!(Pixmap::new(w, h));
2592	let d = pm.data_mut();
2593	for y in 0..h {
2594	for x in 0..w {
2595	let at = (y * w + x) * 4;
2596	let on = (x / 4 + y / 4) % 2 == 0;
2597	d[at] = if on { 220 } else { 30 };
2598	d[at + 1] = ((x * 255) / w.max(1)) as u8;
2599	d[at + 2] = ((y * 255) / h.max(1)) as u8;
2600	d[at + 3] = 255;
2601	}
2602	}
2603	Ok(pm)
2604	}
2605
2606	#[test]
2607	fn test_the_start_of_image_marker_is_checked_00() {
2608	assert!(decode(&[]).is_err());
2609	assert!(decode(&[0xFF]).is_err());
2610	assert!(decode(&[0x00, 0x00, 0x00, 0x00]).is_err());
2611	assert!(decode(b"\x89PNG\r\n\x1a\n").is_err(), "a PNG must not decode as a JPEG");
2612	assert!(dimensions(&[0xFF, 0xD8]).is_err(), "a file with no frame header has no size");
2613	}
2614
2615	#[test]
2616	fn test_a_round_trip_keeps_the_size_and_the_colours_01() -> Outcome<()> {
2617	for (w, h) in [(1usize, 1usize), (8, 8), (17, 13), (33, 9), (64, 48)] {
2618	let pm = res!(sample(w, h));
2619	let opts = Options { quality: 95, chroma: Chroma::Full, grey: false };
2620	let buf = res!(encode_with(&pm, &opts));
2621	let back = res!(decode(&buf));
2622	assert_eq!(back.width(), w, "the width of a {} by {} round trip", w, h);
2623	assert_eq!(back.height(), h, "the height of a {} by {} round trip", w, h);
2624	let (pw, ph) = res!(dimensions(&buf));
2625	assert_eq!((pw, ph), (w, h), "the probe's size for {} by {}", w, h);
2626	}
2627	Ok(())
2628	}
2629
2630	#[test]
2631	fn test_every_chroma_mode_round_trips_02() -> Outcome<()> {
2632	let pm = res!(sample(24, 20));
2633	for chroma in [Chroma::Full, Chroma::Half, Chroma::Quarter] {
2634	for grey in [false, true] {
2635	let opts = Options { quality: 80, chroma, grey };
2636	let buf = res!(encode_with(&pm, &opts));
2637	let back = res!(decode(&buf));
2638	assert_eq!(back.width(), 24, "{:?}, grey {}", chroma, grey);
2639	assert_eq!(back.height(), 20, "{:?}, grey {}", chroma, grey);
2640	}
2641	}
2642	Ok(())
2643	}
2644
2645	#[test]
2646	fn test_a_quality_outside_1_to_100_is_refused_03() -> Outcome<()> {
2647	let pm = res!(sample(8, 8));
2648	let opts = Options { quality: 0, chroma: Chroma::Full, grey: false };
2649	assert!(encode_with(&pm, &opts).is_err(), "quality 0 must be refused");
2650	let opts = Options { quality: 101, chroma: Chroma::Full, grey: false };
2651	assert!(encode_with(&pm, &opts).is_err(), "quality 101 must be refused");
2652	Ok(())
2653	}
2654
2655	#[test]
2656	fn test_the_quality_scale_matches_the_published_tables_04() {
2657	// At quality 50 the tables are the ones of Annex K, unscaled; at 100 every divisor is 1.
2658	let at50 = scale_quant(&QUANT_LUMA, 50);
2659	assert_eq!(at50, QUANT_LUMA, "quality 50 is the table as published");
2660	let at100 = scale_quant(&QUANT_LUMA, 100);
2661	assert!(at100.iter().all(\|v\| *v == 1), "quality 100 divides by one");
2662	// A divisor never reaches zero, whatever the quality, since it is divided by.
2663	for q in 1..=100u8 {
2664	let t = scale_quant(&QUANT_CHROMA, q);
2665	assert!(t.iter().all(\|v\| *v >= 1), "quality {} produced a zero divisor", q);
2666	assert!(t.iter().all(\|v\| *v <= 255), "quality {} overflowed eight bits", q);
2667	}
2668	}
2669
2670	#[test]
2671	fn test_the_magnitude_categories_are_the_specifications_05() {
2672	// The category is the number of bits the magnitude needs, and the bits that follow are the
2673	// value itself for a positive difference and its complement for a negative one.
2674	assert_eq!(category(0).0, 0);
2675	assert_eq!(category(1), (1, 1));
2676	assert_eq!(category(-1), (1, 0));
2677	assert_eq!(category(2), (2, 2));
2678	assert_eq!(category(-2), (2, 1));
2679	assert_eq!(category(-3), (2, 0));
2680	assert_eq!(category(255).0, 8);
2681	assert_eq!(category(-255), (8, 0));
2682	// EXTEND is the inverse.
2683	for v in [-2047i32, -300, -5, -1, 1, 5, 300, 2047] {
2684	let (s, bits) = category(v);
2685	assert_eq!(extend(bits, s as u32), v, "EXTEND must invert the category of {}", v);
2686	}
2687	}
2688
2689	#[test]
2690	fn test_the_standard_huffman_tables_are_prefix_codes_06() -> Outcome<()> {
2691	// Deriving each table both ways checks the counts against the symbols, and would catch a
2692	// mistyped digit in either.
2693	for (bits, vals) in [
2694	(&DC_LUMA_BITS, &DC_VALS[..]),
2695	(&DC_CHROMA_BITS, &DC_VALS[..]),
2696	(&AC_LUMA_BITS, &AC_LUMA_VALS[..]),
2697	(&AC_CHROMA_BITS, &AC_CHROMA_VALS[..]),
2698	] {
2699	let total: usize = bits[1..17].iter().map(\|c\| *c as usize).sum();
2700	assert_eq!(total, vals.len(), "the counts and the symbols must agree");
2701	res!(Huff::new(bits, vals.to_vec()));
2702	res!(Codes::new(bits, vals));
2703	}
2704	Ok(())
2705	}
2706
2707	#[test]
2708	fn test_a_huffman_table_that_is_not_a_prefix_code_is_refused_07() {
2709	// Three codes of length one is one more than a binary tree of that depth holds.
2710	let mut counts = [0u8; 17];
2711	counts[1] = 3;
2712	assert!(Huff::new(&counts, vec![1, 2, 3]).is_err(), "an over-full length must be refused");
2713	// Counts and symbols that disagree.
2714	let mut counts = [0u8; 17];
2715	counts[2] = 2;
2716	assert!(Huff::new(&counts, vec![1]).is_err(), "a short symbol list must be refused");
2717	// No codes at all.
2718	assert!(Huff::new(&[0u8; 17], Vec::new()).is_err(), "an empty table must be refused");
2719	}
2720
2721	#[test]
2722	fn test_a_truncated_file_is_refused_or_read_but_never_panics_08() -> Outcome<()> {
2723	let pm = res!(sample(32, 24));
2724	let buf = res!(encode(&pm));
2725	for cut in [2, 8, 40, 100, buf.len() / 2, buf.len() - 4, buf.len() - 1] {
2726	if cut >= buf.len() {
2727	continue;
2728	}
2729	// Either answer is acceptable; what is not is a panic or an allocation the size of the
2730	// header's arithmetic rather than the file's.
2731	let _ = decode(&buf[..cut]);
2732	let _ = dimensions(&buf[..cut]);
2733	let _ = decode_eighth(&buf[..cut]);
2734	}
2735	Ok(())
2736	}
2737
2738	#[test]
2739	fn test_a_corrupted_file_is_refused_or_read_but_never_panics_09() -> Outcome<()> {
2740	let pm = res!(sample(24, 24));
2741	let buf = res!(encode(&pm));
2742	// Walk a flipped bit through the file. Most land in entropy-coded data, where the result is a
2743	// wrong picture rather than an error, and the point is that it is a picture and not a panic.
2744	for i in (0..buf.len()).step_by(7) {
2745	let mut b = buf.clone();
2746	b[i] ^= 0x5A;
2747	let _ = decode(&b);
2748	}
2749	Ok(())
2750	}
2751
2752	#[test]
2753	fn test_the_modes_this_codec_does_not_implement_are_refused_by_name_10() -> Outcome<()> {
2754	let pm = res!(sample(16, 16));
2755	let buf = res!(encode(&pm));
2756	// The frame header this encoder wrote, found by its marker.
2757	let sof = match buf.windows(2).position(\|w\| w[0] == 0xFF && w[1] == 0xC0) {
2758	Some(i) => i,
2759	None => return Err(err!("The encoder wrote no SOF0 marker."; Test, Missing)),
2760	};
2761
2762	// Arithmetic coding, lossless, and hierarchical modes each name themselves when refused.
2763	for (m, want) in [
2764	(0xC9u8, "arithmetic"),
2765	(0xC3, "lossless"),
2766	(0xC5, "differential"),
2767	] {
2768	let mut b = buf.clone();
2769	b[sof + 1] = m;
2770	match decode(&b) {
2771	Ok(_) => return Err(err!(
2772	"A frame marked {:#04X} decoded, and this codec does not implement it.", m;
2773	Test, Invalid)),
2774	Err(e) => {
2775	let s = fmt!("{}", e);
2776	assert!(
2777	s.contains(want),
2778	"refusing {:#04X} should name it '{}', and it said: {}", m, want, s,
2779	);
2780	},
2781	}
2782	}
2783
2784	// Twelve bits a sample.
2785	let mut b = buf.clone();
2786	b[sof + 4] = 12; // The precision byte, after the marker and the two length bytes.
2787	match decode(&b) {
2788	Ok(_) => return Err(err!("A twelve-bit frame decoded."; Test, Invalid)),
2789	Err(e) => {
2790	let s = fmt!("{}", e);
2791	assert!(s.contains("12 bits"), "refusing 12 bits should say so: {}", s);
2792	},
2793	}
2794	Ok(())
2795	}
2796
2797	#[test]
2798	fn test_the_inverse_dct_of_a_flat_block_is_flat_11() {
2799	// A block whose only coefficient is the DC one is a constant, and the constant is the DC
2800	// coefficient divided by eight, plus the level shift of 128.
2801	let q = [1u16; DCTSIZE2];
2802	for dc in [-1024i16, -8, 0, 8, 800] {
2803	let mut coef = [0i16; DCTSIZE2];
2804	coef[0] = dc;
2805	let mut out = [0u8; DCTSIZE2];
2806	idct(&coef, &q, &mut out, 0, DCTSIZE);
2807	let want = clamp8(((dc as i32) + 4) / 8 + 128);
2808	// The rounding of a division that truncates towards zero differs by one below zero.
2809	let want = if dc < 0 {
2810	clamp8(((dc as i32) + 4).div_euclid(8) + 128)
2811	} else {
2812	want
2813	};
2814	for v in out {
2815	assert_eq!(v, want, "a block with only DC {} must be flat at {}", dc, want);
2816	}
2817	assert_eq!(idct_dc(&coef, &q), want, "the DC-only path must agree with the full one");
2818	}
2819	}
2820
2821	#[test]
2822	fn test_an_absurd_frame_header_is_refused_12() -> Outcome<()> {
2823	let pm = res!(sample(8, 8));
2824	let buf = res!(encode(&pm));
2825	let sof = match buf.windows(2).position(\|w\| w[0] == 0xFF && w[1] == 0xC0) {
2826	Some(i) => i,
2827	None => return Err(err!("The encoder wrote no SOF0 marker."; Test, Missing)),
2828	};
2829	// 65535 by 65535 is 4.29 billion pixels, over the ceiling.
2830	let mut b = buf.clone();
2831	b[sof + 5] = 0xFF;
2832	b[sof + 6] = 0xFF;
2833	b[sof + 7] = 0xFF;
2834	b[sof + 8] = 0xFF;
2835	assert!(decode(&b).is_err(), "a frame over the pixel ceiling must be refused");
2836	assert!(dimensions(&b).is_err(), "the probe must refuse it too, before it allocates");
2837	// A height of zero, which means the line count arrives in a DNL segment.
2838	let mut b = buf.clone();
2839	b[sof + 5] = 0;
2840	b[sof + 6] = 0;
2841	assert!(decode(&b).is_err(), "a frame with no height must be refused");
2842	Ok(())
2843	}
2844
2845	#[test]
2846	fn test_a_zero_quantisation_divisor_is_refused_13() -> Outcome<()> {
2847	let pm = res!(sample(8, 8));
2848	let buf = res!(encode(&pm));
2849	let dqt = match buf.windows(2).position(\|w\| w[0] == 0xFF && w[1] == DQT) {
2850	Some(i) => i,
2851	None => return Err(err!("The encoder wrote no DQT marker."; Test, Missing)),
2852	};
2853	let mut b = buf.clone();
2854	b[dqt + 5] = 0; // The first divisor, after the marker, the length and the slot byte.
2855	assert!(decode(&b).is_err(), "a zero divisor must be refused, not divided by");
2856	Ok(())
2857	}
2858
2859	#[test]
2860	fn test_the_eighth_scale_decode_is_an_eighth_of_the_size_14() -> Outcome<()> {
2861	for (w, h) in [(1usize, 1usize), (8, 8), (9, 9), (17, 13), (64, 48)] {
2862	let pm = res!(sample(w, h));
2863	let buf = res!(encode(&pm));
2864	let small = res!(decode_eighth(&buf));
2865	assert_eq!(small.width(), ceil_div(w, 8), "the eighth-scale width of {} by {}", w, h);
2866	assert_eq!(small.height(), ceil_div(h, 8), "the eighth-scale height of {} by {}", w, h);
2867	}
2868	Ok(())
2869	}
2870
2871	#[test]
2872	fn test_alpha_is_composited_over_white_15() -> Outcome<()> {
2873	// JPEG has no alpha channel, so a transparent pixel has to become something. White is what a
2874	// viewer expects, and a decoder that silently kept the colour under the transparency would
2875	// produce a picture nobody drew.
2876	let mut pm = res!(Pixmap::new(16, 16));
2877	pm.fill(crate::colour::Rgba::new(255, 0, 0, 0)); // Fully transparent red.
2878	let opts = Options { quality: 95, chroma: Chroma::Full, grey: false };
2879	let buf = res!(encode_with(&pm, &opts));
2880	let back = res!(decode(&buf));
2881	let c = match back.pixel(8, 8) {
2882	Some(c) => c,
2883	None => return Err(err!("A 16 by 16 pixmap has a pixel at 8, 8."; Test, Missing)),
2884	};
2885	assert!(
2886	c.r > 250 && c.g > 250 && c.b > 250,
2887	"transparent red should encode as white, and came back as {:?}", c,
2888	);
2889	assert_eq!(c.a, 255, "a decoded JPEG is opaque");
2890	Ok(())
2891	}
2892
2893	#[test]
2894	fn test_a_jfif_segment_outranks_an_adobe_one_16() -> Outcome<()> {
2895	// Files exist carrying both a JFIF segment and an Adobe segment declaring no transform. JFIF
2896	// is defined as YCbCr, so it settles the question and the Adobe segment is not consulted;
2897	// reading the Adobe segment first turns such a file into false colour, red for blue.
2898	let pm = res!(Pixmap::filled(32, 32, crate::colour::Rgba::new(220, 30, 40, 255)));
2899	let opts = Options { quality: 95, chroma: Chroma::Full, grey: false };
2900	let buf = res!(encode_with(&pm, &opts));
2901
2902	// An Adobe APP14 segment declaring transform 0, spliced in after the JFIF segment.
2903	let adobe: [u8; 16] = [
2904	0xFF, 0xEE, 0x00, 0x0E,
2905	b'A', b'd', b'o', b'b', b'e',
2906	0x00, 0x64, // Version.
2907	0x00, 0x00, 0x00, 0x00, // Two flag words.
2908	0x00, // Transform: none.
2909	];
2910	let at = match buf.windows(2).position(\|w\| w[0] == 0xFF && w[1] == DQT) {
2911	Some(i) => i,
2912	None => return Err(err!("The encoder wrote no DQT marker."; Test, Missing)),
2913	};
2914	let mut spliced = Vec::with_capacity(buf.len() + adobe.len());
2915	spliced.extend_from_slice(&buf[..at]);
2916	spliced.extend_from_slice(&adobe);
2917	spliced.extend_from_slice(&buf[at..]);
2918
2919	let back = res!(decode(&spliced));
2920	let c = match back.pixel(16, 16) {
2921	Some(c) => c,
2922	None => return Err(err!("A 32 by 32 pixmap has a pixel at 16, 16."; Test, Missing)),
2923	};
2924	assert!(
2925	(c.r as i32 - 220).abs() < 8 && (c.g as i32 - 30).abs() < 8 && (c.b as i32 - 40).abs() < 8,
2926	"a file with both segments is YCbCr, so it should decode near (220, 30, 40), not {:?}", c,
2927	);
2928	Ok(())
2929	}
2930
2931	#[test]
2932	fn test_a_truncated_scan_leaves_the_rest_mid_grey_17() -> Outcome<()> {
2933	// When the entropy-coded data runs out, the coefficients not yet read stay at zero, which the
2934	// inverse DCT renders as a flat mid-grey. Carrying on with whatever the zero padding decodes
2935	// to would fill the tail of the picture with noise instead, which is what this codec did
2936	// until a truncated photograph was decoded beside another implementation's reading of it.
2937	let pm = res!(sample(64, 64));
2938	let opts = Options { quality: 90, chroma: Chroma::Full, grey: false };
2939	let buf = res!(encode_with(&pm, &opts));
2940	let sos = match buf.windows(2).position(\|w\| w[0] == 0xFF && w[1] == SOS) {
2941	Some(i) => i,
2942	None => return Err(err!("The encoder wrote no SOS marker."; Test, Missing)),
2943	};
2944	// Keep the scan header and a little of its data, and drop the rest along with the EOI.
2945	let cut = (sos + 40).min(buf.len());
2946	let back = res!(decode(&buf[..cut]));
2947	assert_eq!(back.width(), 64);
2948	assert_eq!(back.height(), 64);
2949	for x in 0..64 {
2950	let c = match back.pixel(x, 63) {
2951	Some(c) => c,
2952	None => return Err(err!("No pixel at ({}, 63).", x; Test, Missing)),
2953	};
2954	assert_eq!(
2955	(c.r, c.g, c.b), (128, 128, 128),
2956	"the last row of a truncated file is mid-grey, and pixel {} is {:?}", x, c,
2957	);
2958	}
2959	Ok(())
2960	}
2961
2962	/// A three by three grid of blocks whose DC values ramp from left to right.
2963	fn ramp_blocks() -> Comp {
2964	let mut c = Comp {
2965	id: 1, h: 1, v: 1, tq: 0,
2966	dw: 24, dh: 24, bw: 3, bh: 3, bwp: 3, bhp: 3,
2967	coef: vec![0i16; 9 * DCTSIZE2],
2968	};
2969	for by in 0..3 {
2970	for bx in 0..3 {
2971	c.coef[(by * 3 + bx) * DCTSIZE2] = (100 + 100 * bx) as i16;
2972	}
2973	}
2974	c
2975	}
2976
2977	#[test]
2978	fn test_block_smoothing_estimates_from_the_neighbouring_means_18() {
2979	// The middle block of a left-to-right ramp. Annex K.8 estimates the first horizontal AC
2980	// coefficient as 36 * Q00 * (left - right), scaled by its own quantiser: with Q00 of 16, a
2981	// ramp of 100 to 300 and a quantiser of 11 that is -41 before the approximation clamp.
2982	let c = ramp_blocks();
2983	let mut q = [1u16; DCTSIZE2];
2984	q[0] = 16;
2985	q[1] = 11;
2986	let mut seen = [0i8; DCTSIZE2];
2987
2988	// A coefficient no scan ever carried takes the estimate whole.
2989	seen[1] = -1;
2990	let mut ws = [0i16; DCTSIZE2];
2991	ws.copy_from_slice(&c.coef[DCTSIZE2 * 4..DCTSIZE2 * 5]);
2992	smooth(&mut ws, &c.coef, &c, 1, 1, &q, &seen);
2993	assert_eq!(ws[1], -41, "the estimate follows the ramp, and downwards");
2994
2995	// A coefficient received down to bit 1 is known to within two, so the estimate is clamped.
2996	seen[1] = 1;
2997	let mut ws = [0i16; DCTSIZE2];
2998	smooth(&mut ws, &c.coef, &c, 1, 1, &q, &seen);
2999	assert_eq!(ws[1], -1, "an estimate may not exceed what the scans left undetermined");
3000
3001	// A coefficient a scan pinned down exactly is never estimated.
3002	seen[1] = 0;
3003	let mut ws = [0i16; DCTSIZE2];
3004	smooth(&mut ws, &c.coef, &c, 1, 1, &q, &seen);
3005	assert_eq!(ws[1], 0, "a coefficient known exactly must be left alone");
3006
3007	// Nor is one that already carries a value.
3008	seen[1] = -1;
3009	let mut ws = [0i16; DCTSIZE2];
3010	ws[1] = 7;
3011	smooth(&mut ws, &c.coef, &c, 1, 1, &q, &seen);
3012	assert_eq!(ws[1], 7, "a coefficient already received must be left alone");
3013	}
3014
3015	#[test]
3016	fn test_block_smoothing_applies_only_where_it_can_help_19() -> Outcome<()> {
3017	// A sequential frame is never smoothed, and neither is a progressive one whose scans all
3018	// reached the last approximation bit: there is then nothing left to estimate.
3019	let pm = res!(sample(32, 32));
3020	let buf = res!(encode(&pm));
3021	let r = res!(parse(&buf));
3022	let frame = match r.frame {
3023	Some(f) => f,
3024	None => return Err(err!("The file carries no frame header."; Test, Missing)),
3025	};
3026	assert!(!smoothing_helps(&frame), "a sequential frame is never smoothed");
3027	Ok(())
3028	}
3029	}