f67d38b35cc5
ljpeg.rs
//! The lossless JPEG decoder of PR #1068, kept unchanged as the reference (tests and benchmarks
//! only).
use crate::{Error, Result};
/// A decoded lossless JPEG image.
#[derive(Debug)]
pub struct Decoded {
pub width: usize,
pub height: usize,
pub components: usize,
pub precision: u8,
pub predictor: u8,
/// Samples, interleaved by component, line after line, shifted back up by the point transform.
pub samples: Vec<u16>,
}
const LOOKUP_BITS: u32 = 9;
/// A Huffman table for decoding (T.81 Annex C and F.2.2.3).
#[derive(Clone)]
struct Huffman {
/// For codes of up to LOOKUP_BITS bits: (length, value) indexed by the next LOOKUP_BITS bits;
/// length 0 means "longer code".
fast: Vec<(u8, u8)>,
maxcode: [i32; 17],
valptr: [i32; 17],
mincode: [i32; 17],
values: Vec<u8>,
}
impl Huffman {
fn new(bits: &[u8; 16], values: Vec<u8>) -> Result<Huffman> {
// C.2: code sizes and codes
let mut sizes = Vec::new();
for (l, &n) in bits.iter().enumerate() {
for _ in 0..n {
sizes.push(l as u8 + 1);
}
}
if sizes.len() != values.len() || sizes.is_empty() {
return Err(Error::Malformed("lossless JPEG: Huffman table counts"));
}
let mut codes = Vec::with_capacity(sizes.len());
let mut code: u32 = 0;
let mut si = sizes[0];
let mut k = 0;
while k < sizes.len() {
while k < sizes.len() && sizes[k] == si {
codes.push(code);
code += 1;
k += 1;
}
// the codes of one length must fit in that length
if code > (1u32 << si) {
return Err(Error::Malformed("lossless JPEG: Huffman table over-subscribed"));
}
code <<= 1;
si += 1;
}
// F.2.2.3 decoder tables
let mut maxcode = [-1i32; 17];
let mut valptr = [0i32; 17];
let mut mincode = [0i32; 17];
let mut j = 0usize;
for l in 1..=16usize {
let n = usize::from(bits[l - 1]);
if n == 0 {
maxcode[l] = -1;
} else {
valptr[l] = j as i32;
mincode[l] = codes[j] as i32;
j += n;
maxcode[l] = codes[j - 1] as i32;
}
}
let mut fast = vec![(0u8, 0u8); 1 << LOOKUP_BITS];
for (i, (&c, &s)) in codes.iter().zip(&sizes).enumerate() {
let s = u32::from(s);
if s <= LOOKUP_BITS {
let shift = LOOKUP_BITS - s;
let base = (c << shift) as usize;
for f in fast.iter_mut().skip(base).take(1 << shift) {
*f = (s as u8, values[i]);
}
}
}
Ok(Huffman { fast, maxcode, valptr, mincode, values })
}
}
/// Entropy-coded data reader: removes stuffed zero bytes and stops at markers (feeding zeros).
struct Bits<'a> {
data: &'a [u8],
pos: usize,
acc: u64,
n: u32,
/// The marker that ended the data (after 0xFF), if one was met.
marker: Option<u8>,
}
impl<'a> Bits<'a> {
fn new(data: &'a [u8], pos: usize) -> Self {
Bits { data, pos, acc: 0, n: 0, marker: None }
}
fn fill(&mut self) {
while self.n <= 56 {
let mut byte = 0u8;
if self.marker.is_none() {
match self.data.get(self.pos) {
Some(&0xFF) => match self.data.get(self.pos + 1) {
Some(&0x00) => {
byte = 0xFF;
self.pos += 2;
}
Some(&m) => self.marker = Some(m),
None => self.marker = Some(0xD9),
},
Some(&b) => {
byte = b;
self.pos += 1;
}
None => self.marker = Some(0xD9),
}
}
self.acc |= u64::from(byte) << (56 - self.n);
self.n += 8;
}
}
fn peek(&mut self, k: u32) -> u32 {
if self.n < k {
self.fill();
}
(self.acc >> (64 - k)) as u32
}
fn skip(&mut self, k: u32) {
self.acc <<= k;
self.n -= k;
}
fn bits(&mut self, k: u32) -> u32 {
if k == 0 {
return 0;
}
let v = self.peek(k);
self.skip(k);
v
}
/// Decode one Huffman symbol (F.2.2.3).
fn decode(&mut self, h: &Huffman) -> Result<u8> {
let p = self.peek(LOOKUP_BITS) as usize;
if let Some(&(len, v)) = h.fast.get(p)
&& len > 0
{
self.skip(u32::from(len));
return Ok(v);
}
let mut code = self.bits(1) as i32;
for l in 1..=16usize {
if code <= h.maxcode[l] {
let i = h.valptr[l] + code - h.mincode[l];
return h.values.get(i as usize).copied().ok_or(Error::Malformed("lossless JPEG: bad Huffman code"));
}
code = (code << 1) | self.bits(1) as i32;
}
Err(Error::Malformed("lossless JPEG: bad Huffman code"))
}
/// Skip to the byte after the next RSTn marker, starting a new bit stream there.
fn restart(&mut self) -> Result<()> {
// the decoder may have looked ahead into fill bits; find the marker in the bytes
let mut p = self.pos;
loop {
match (self.data.get(p), self.data.get(p + 1)) {
(Some(0xFF), Some(&m)) if (0xD0..=0xD7).contains(&m) => {
*self = Bits::new(self.data, p + 2);
return Ok(());
}
(Some(_), Some(_)) => p += 1,
_ => return Err(Error::Malformed("lossless JPEG: missing restart marker")),
}
}
}
}
struct Component {
id: u8,
table: usize,
}
/// Decode a lossless JPEG stream. `max_samples` caps the picture (width × height × components).
pub fn decode(data: &[u8], max_samples: usize) -> Result<Decoded> {
if data.get(0..2) != Some(&[0xFF, 0xD8]) {
return Err(Error::Malformed("lossless JPEG: no SOI marker"));
}
let mut pos = 2usize;
let mut tables: [Option<Huffman>; 4] = [None, None, None, None];
let mut frame: Option<(u8, usize, usize, Vec<Component>)> = None;
let mut restart_interval = 0usize;
loop {
// markers may be preceded by fill bytes 0xFF
while data.get(pos) == Some(&0xFF) && data.get(pos + 1) == Some(&0xFF) {
pos += 1;
}
let (Some(&0xFF), Some(&m)) = (data.get(pos), data.get(pos + 1)) else {
return Err(Error::Malformed("lossless JPEG: expected a marker"));
};
pos += 2;
if m == 0xD9 {
return Err(Error::Malformed("lossless JPEG: no scan"));
}
if (0xD0..=0xD8).contains(&m) || m == 0x01 {
continue; // markers without a segment
}
let len_b = data.get(pos..pos + 2).ok_or(Error::Truncated)?;
let len = usize::from(u16::from_be_bytes([len_b[0], len_b[1]]));
if len < 2 {
return Err(Error::Malformed("lossless JPEG: segment length"));
}
let seg = data.get(pos + 2..pos + len).ok_or(Error::Truncated)?;
match m {
0xC3 => {
let [p, y0, y1, x0, x1, nf, rest @ ..] = seg else {
return Err(Error::Malformed("lossless JPEG: short frame header"));
};
let (precision, nf) = (*p, usize::from(*nf));
let height = usize::from(u16::from_be_bytes([*y0, *y1]));
let width = usize::from(u16::from_be_bytes([*x0, *x1]));
if !(2..=16).contains(&precision) {
return Err(Error::Unsupported(format!("lossless JPEG precision {precision}")));
}
if height == 0 {
return Err(Error::Unsupported("lossless JPEG with the height in a DNL marker".into()));
}
if width == 0 || !(1..=4).contains(&nf) || rest.len() < nf * 3 {
return Err(Error::Malformed("lossless JPEG: frame header"));
}
let mut comps = Vec::with_capacity(nf);
for c in rest.as_chunks::<3>().0.iter().take(nf) {
if c[1] != 0x11 {
return Err(Error::Unsupported("subsampled lossless JPEG components".into()));
}
comps.push(Component { id: c[0], table: 0 });
}
frame = Some((precision, width, height, comps));
}
0xC4 => {
let mut s = seg;
while !s.is_empty() {
let [tcth, counts @ ..] = s else { break };
let bits: [u8; 16] = counts.get(..16).and_then(|b| b.try_into().ok()).ok_or(Error::Truncated)?;
let n: usize = bits.iter().map(|&b| usize::from(b)).sum();
let values = counts.get(16..16 + n).ok_or(Error::Truncated)?.to_vec();
let th = usize::from(tcth & 0x0F);
if tcth >> 4 != 0 || th > 3 {
return Err(Error::Malformed("lossless JPEG: Huffman table class or id"));
}
if values.iter().any(|&v| v > 16) {
return Err(Error::Malformed("lossless JPEG: difference category above 16"));
}
tables[th] = Some(Huffman::new(&bits, values)?);
s = counts.get(16 + n..).unwrap_or(&[]);
}
}
0xDD => {
let r = seg.get(0..2).ok_or(Error::Truncated)?;
restart_interval = usize::from(u16::from_be_bytes([r[0], r[1]]));
}
0xDA => {
let Some((precision, width, height, mut comps)) = frame.take() else {
return Err(Error::Malformed("lossless JPEG: scan before the frame header"));
};
let ns = usize::from(*seg.first().ok_or(Error::Truncated)?);
if ns != comps.len() {
return Err(Error::Unsupported("lossless JPEG with more than one scan".into()));
}
for k in 0..ns {
let c = seg.get(1 + 2 * k..3 + 2 * k).ok_or(Error::Truncated)?;
let comp = comps.iter_mut().find(|x| x.id == c[0]).ok_or(Error::Malformed("lossless JPEG: unknown scan component"))?;
comp.table = usize::from(c[1] >> 4);
if comp.table > 3 {
return Err(Error::Malformed("lossless JPEG: Huffman table id"));
}
}
let tail = seg.get(1 + 2 * ns..4 + 2 * ns).ok_or(Error::Truncated)?;
let (predictor, pt) = (tail[0], tail[2] & 0x0F);
if !(1..=7).contains(&predictor) {
return Err(Error::Unsupported(format!("lossless JPEG predictor {predictor}")));
}
if pt >= precision {
return Err(Error::Malformed("lossless JPEG: point transform"));
}
let n = width.checked_mul(height).and_then(|v| v.checked_mul(comps.len())).ok_or(Error::TooLarge)?;
if n > max_samples {
return Err(Error::TooLarge);
}
let mut hufs = Vec::with_capacity(comps.len());
for c in &comps {
hufs.push(tables.get(c.table).and_then(|t| t.as_ref()).ok_or(Error::Malformed("lossless JPEG: missing Huffman table"))?);
}
let samples = scan(data, pos + len, &hufs, width, height, precision, predictor, pt, restart_interval)?;
return Ok(Decoded { width, height, components: comps.len(), precision, predictor, samples });
}
0xC0..=0xC2 | 0xC5..=0xC7 | 0xC9..=0xCB | 0xCD..=0xCF => {
return Err(Error::Unsupported("lossy (DCT) JPEG in a DNG".into()));
}
_ => {} // APPn, COM, DQT … are skipped
}
pos += len;
}
}
/// Decode the entropy-coded data of one scan (H.1.2).
fn scan(data: &[u8], start: usize, hufs: &[&Huffman], width: usize, height: usize, precision: u8, predictor: u8, pt: u8, restart: usize) -> Result<Vec<u16>> {
let nc = hufs.len();
let row_len = width * nc;
if restart != 0 && !restart.is_multiple_of(width) {
return Err(Error::Unsupported("lossless JPEG restart interval that splits a line".into()));
}
let lines_per_interval = if restart == 0 { usize::MAX } else { restart / width };
let mut out = vec![0u16; row_len * height];
let mut bits = Bits::new(data, start);
let initial = 1i32 << (precision - pt - 1);
let mut line_in_interval = 0usize;
for y in 0..height {
if line_in_interval == lines_per_interval {
bits.restart()?;
line_in_interval = 0;
}
let first_line = line_in_interval == 0;
let (above, cur) = if y == 0 {
(None, &mut out[..row_len])
} else {
let (a, c) = out.split_at_mut(y * row_len);
(Some(&a[(y - 1) * row_len..]), &mut c[..row_len])
};
for x in 0..width {
for (c, h) in hufs.iter().enumerate() {
let i = x * nc + c;
let ssss = u32::from(bits.decode(h)?);
let diff = match ssss {
0 => 0,
16 => 32768,
s => {
let v = bits.bits(s) as i32;
if v < (1 << (s - 1)) { v - (1 << s) + 1 } else { v }
}
};
let px = match above {
_ if first_line && x == 0 => initial,
_ if first_line => i32::from(cur[i - nc]),
Some(a) if x == 0 => i32::from(a[i]),
Some(a) => predict(predictor, i32::from(cur[i - nc]), i32::from(a[i]), i32::from(a[i - nc])),
None => initial,
};
cur[i] = ((px + diff) & 0xFFFF) as u16;
}
}
line_in_interval += 1;
}
if pt > 0 {
for s in &mut out {
*s <<= pt;
}
}
Ok(out)
}
/// Table H.1 predictors (`ra` left, `rb` above, `rc` above left).
pub fn predict(p: u8, ra: i32, rb: i32, rc: i32) -> i32 {
match p {
1 => ra,
2 => rb,
3 => rc,
4 => ra + rb - rc,
5 => ra + ((rb - rc) >> 1),
6 => rb + ((ra - rc) >> 1),
_ => (ra + rb) >> 1,
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.