Skip to main content

openreadout_codecs/
blosc.rs

1//! Blosc 1 chunk decoding and LZ4 block decoding (pure Rust).
2//!
3//! Blosc chunk layout from the public c-blosc documentation (`README_CHUNK_FORMAT.rst`) and the
4//! BSD-3-licensed c-blosc sources (`blosc.c` block splitting rules, `blosclz.c` decoder,
5//! `shuffle.c` bit-unshuffle rules); the bit transpose from the MIT-licensed bitshuffle
6//! library's description; Snappy from its public format description; LZ4 blocks through the
7//! MIT-licensed `lz4_flex` crate. Provenance: `docs/provenance/ome-zarr.md`.
8//!
9//! Every length in the input is checked before use; malformed input is an error, never a panic.
10
11use crate::{CodecError, Result};
12
13/// Byte-shuffle filter applied (flags bit 0).
14const FLAG_SHUFFLE: u8 = 0x01;
15/// The payload is stored uncompressed after the header (flags bit 1).
16const FLAG_MEMCPYED: u8 = 0x02;
17/// Bit-shuffle filter applied (flags bit 2).
18const FLAG_BITSHUFFLE: u8 = 0x04;
19/// Blocks are not split into one stream per byte of the type (flags bit 4).
20const FLAG_DONT_SPLIT: u8 = 0x10;
21const HEADER: usize = 16;
22const MAX_SPLITS: usize = 16;
23const MIN_BUFFERSIZE: usize = 128;
24/// Largest decoded chunk accepted (a guard against absurd headers).
25const MAX_DECODED: usize = 1 << 31;
26
27fn err(detail: impl Into<String>) -> CodecError {
28    CodecError::Decode {
29        codec: "blosc",
30        detail: detail.into(),
31    }
32}
33
34fn le32(b: &[u8], at: usize) -> Option<usize> {
35    let s = b.get(at..at.checked_add(4)?)?;
36    Some(u32::from_le_bytes([s[0], s[1], s[2], s[3]]) as usize)
37}
38
39/// The compressor recorded in a Blosc header (flags bits 5–7).
40#[derive(Debug, Clone, Copy, PartialEq, Eq)]
41#[non_exhaustive]
42pub enum BloscCompressor {
43    /// Blosc's own LZ77 variant.
44    BloscLz,
45    /// LZ4 block format.
46    Lz4,
47    /// Snappy.
48    Snappy,
49    /// zlib (deflate with a zlib header).
50    Zlib,
51    /// Zstandard.
52    Zstd,
53    /// A compressor code this decoder does not know.
54    Unknown(u8),
55}
56
57impl BloscCompressor {
58    fn from_flags(flags: u8) -> Self {
59        match flags >> 5 {
60            0 => Self::BloscLz,
61            1 => Self::Lz4,
62            2 => Self::Snappy,
63            3 => Self::Zlib,
64            4 => Self::Zstd,
65            n => Self::Unknown(n),
66        }
67    }
68    /// Name as numcodecs spells it (`cname`).
69    pub fn name(self) -> &'static str {
70        match self {
71            Self::BloscLz => "blosclz",
72            Self::Lz4 => "lz4",
73            Self::Snappy => "snappy",
74            Self::Zlib => "zlib",
75            Self::Zstd => "zstd",
76            Self::Unknown(_) => "unknown",
77        }
78    }
79}
80
81/// Header fields of a Blosc 1 chunk.
82#[derive(Debug, Clone, Copy, PartialEq, Eq)]
83pub struct BloscHeader {
84    /// Format version of the Blosc header.
85    pub version: u8,
86    /// Flag bits: shuffle mode (bits 0 and 2), memcpy'd (bit 1), compressor (bits 5 to 7).
87    pub flags: u8,
88    /// Size of one element in bytes, used by the shuffle filters.
89    pub typesize: usize,
90    /// Decoded size in bytes.
91    pub nbytes: usize,
92    /// Uncompressed size of one block in bytes.
93    pub blocksize: usize,
94    /// Compressed size including the header.
95    pub cbytes: usize,
96    /// The compressor that produced the blocks.
97    pub compressor: BloscCompressor,
98}
99
100/// Parse the 16-byte Blosc header.
101pub fn blosc_header(data: &[u8]) -> Result<BloscHeader> {
102    if data.len() < HEADER {
103        return Err(err(format!(
104            "{} bytes is shorter than the 16-byte header",
105            data.len()
106        )));
107    }
108    let flags = data[2];
109    Ok(BloscHeader {
110        version: data[0],
111        flags,
112        typesize: data[3] as usize,
113        nbytes: le32(data, 4).unwrap_or(0),
114        blocksize: le32(data, 8).unwrap_or(0),
115        cbytes: le32(data, 12).unwrap_or(0),
116        compressor: BloscCompressor::from_flags(flags),
117    })
118}
119
120/// Decode one Blosc 1 chunk (as written by c-blosc 1.x / numcodecs `Blosc`).
121pub fn blosc_decode(data: &[u8]) -> Result<Vec<u8>> {
122    let h = blosc_header(data)?;
123    if h.nbytes > MAX_DECODED {
124        return Err(err(format!("header declares {} decoded bytes", h.nbytes)));
125    }
126    if h.cbytes > data.len() {
127        return Err(err(format!(
128            "header declares {} compressed bytes, {} present (truncated)",
129            h.cbytes,
130            data.len()
131        )));
132    }
133    let data = &data[..h.cbytes];
134    if h.nbytes == 0 {
135        return Ok(Vec::new());
136    }
137    if h.flags & FLAG_MEMCPYED != 0 {
138        let body = data
139            .get(HEADER..HEADER + h.nbytes)
140            .ok_or_else(|| err("stored (memcpyed) payload is truncated"))?;
141        return Ok(body.to_vec());
142    }
143    if h.blocksize == 0 || h.typesize == 0 {
144        return Err(err("block size or type size is 0"));
145    }
146    if h.blocksize > MAX_DECODED {
147        return Err(err(format!("header declares a {}-byte block", h.blocksize)));
148    }
149    let nblocks = h.nbytes.div_ceil(h.blocksize);
150    let leftover = h.nbytes % h.blocksize;
151    let mut out = vec![0u8; h.nbytes];
152    let mut tmp = vec![0u8; h.blocksize.min(h.nbytes)];
153    let shuffle = h.flags & FLAG_SHUFFLE != 0 && h.typesize > 1;
154    let bitshuffle = h.flags & FLAG_BITSHUFFLE != 0 && h.blocksize >= h.typesize;
155    for b in 0..nblocks {
156        let start = le32(data, HEADER + 4 * b).ok_or_else(|| err("block offsets truncated"))?;
157        let is_leftover = leftover != 0 && b == nblocks - 1;
158        let bsize = if is_leftover { leftover } else { h.blocksize };
159        let nsplits = if h.flags & FLAG_DONT_SPLIT == 0
160            && h.typesize <= MAX_SPLITS
161            && h.blocksize / h.typesize >= MIN_BUFFERSIZE
162            && !is_leftover
163        {
164            h.typesize
165        } else {
166            1
167        };
168        let neblock = bsize / nsplits;
169        let mut src = start;
170        let mut filled = 0usize;
171        for _ in 0..nsplits {
172            let cbytes = le32(data, src).ok_or_else(|| err("split size truncated"))?;
173            src += 4;
174            let end = src
175                .checked_add(cbytes)
176                .ok_or_else(|| err("split size overflows"))?;
177            let stream = data
178                .get(src..end)
179                .ok_or_else(|| err(format!("block {b}: split runs past the chunk")))?;
180            let dst = tmp
181                .get_mut(filled..filled + neblock)
182                .ok_or_else(|| err("block larger than declared"))?;
183            if cbytes == neblock {
184                dst.copy_from_slice(stream);
185            } else {
186                let dec = decompress_stream(h.compressor, stream, neblock)?;
187                if dec.len() != neblock {
188                    return Err(err(format!(
189                        "block {b}: split decoded to {} bytes, expected {neblock}",
190                        dec.len()
191                    )));
192                }
193                dst.copy_from_slice(&dec);
194            }
195            src = end;
196            filled += neblock;
197        }
198        let dest = out
199            .get_mut(b * h.blocksize..b * h.blocksize + bsize)
200            .ok_or_else(|| err("block outside the decoded chunk"))?;
201        if shuffle {
202            unshuffle(h.typesize, &tmp[..bsize], dest);
203        } else if bitshuffle {
204            bitunshuffle(h.typesize, &tmp[..bsize], dest);
205        } else {
206            dest.copy_from_slice(&tmp[..bsize]);
207        }
208    }
209    Ok(out)
210}
211
212/// Undo the Blosc byte shuffle: byte `j` of element `i` was stored at `j * n + i`; trailing
213/// bytes that do not fill a whole element are stored as they are.
214fn unshuffle(typesize: usize, src: &[u8], dest: &mut [u8]) {
215    let n = src.len() / typesize;
216    for i in 0..n {
217        for j in 0..typesize {
218            dest[i * typesize + j] = src[j * n + i];
219        }
220    }
221    let done = n * typesize;
222    dest[done..].copy_from_slice(&src[done..]);
223}
224
225/// Undo the bit shuffle of one block (c-blosc `bitunshuffle`): when the block holds a multiple
226/// of 8 whole elements, bit `k` of byte `j` of element `i` was stored at bit `i % 8` of byte
227/// `(j * 8 + k) * n / 8 + i / 8` (`n` elements; one row of `n` bits per bit of each byte);
228/// bytes after the whole elements are stored as they are. Other blocks are stored unshuffled.
229fn bitunshuffle(typesize: usize, src: &[u8], dest: &mut [u8]) {
230    let n = src.len() / typesize;
231    if !n.is_multiple_of(8) {
232        dest.copy_from_slice(src);
233        return;
234    }
235    let row = n / 8;
236    let done = n * typesize;
237    dest[..done].fill(0);
238    for j in 0..typesize {
239        for k in 0..8 {
240            let bits = &src[(j * 8 + k) * row..(j * 8 + k + 1) * row];
241            for i in 0..n {
242                let bit = (bits[i / 8] >> (i % 8)) & 1;
243                dest[i * typesize + j] |= bit << k;
244            }
245        }
246    }
247    dest[done..].copy_from_slice(&src[done..]);
248}
249
250/// A Snappy raw block (public format description, `format_description.txt`): a varint decoded
251/// length, then literals and back references (1, 2 or 4-byte offsets). Must decode to exactly
252/// `expected` bytes.
253pub fn snappy_decode(src: &[u8], expected: usize) -> Result<Vec<u8>> {
254    let bad = |d: &str| CodecError::Decode {
255        codec: "snappy",
256        detail: d.into(),
257    };
258    let mut ip = 0usize;
259    let mut len = 0usize;
260    let mut shift = 0u32;
261    loop {
262        let b = *src.get(ip).ok_or_else(|| bad("length truncated"))?;
263        ip += 1;
264        len |= usize::from(b & 0x7f)
265            .checked_shl(shift)
266            .ok_or_else(|| bad("length overflows"))?;
267        if b & 0x80 == 0 {
268            break;
269        }
270        shift += 7;
271        if shift > 28 {
272            return Err(bad("length overflows"));
273        }
274    }
275    if len != expected || len > MAX_DECODED {
276        return Err(bad(&format!("declares {len} bytes, expected {expected}")));
277    }
278    let mut out: Vec<u8> = Vec::with_capacity(len);
279    let le = |at: usize, n: usize| -> Option<usize> {
280        let s = src.get(at..at.checked_add(n)?)?;
281        Some(s.iter().rev().fold(0usize, |a, &b| a << 8 | usize::from(b)))
282    };
283    while ip < src.len() {
284        let tag = src[ip];
285        ip += 1;
286        let (n, offset) = match tag & 3 {
287            0 => {
288                let mut n = usize::from(tag >> 2);
289                if n >= 60 {
290                    let extra = n - 59;
291                    n = le(ip, extra).ok_or_else(|| bad("literal length truncated"))?;
292                    ip += extra;
293                }
294                n += 1;
295                let lit = src
296                    .get(ip..ip.checked_add(n).ok_or_else(|| bad("literal overflows"))?)
297                    .ok_or_else(|| bad("literal runs past the input"))?;
298                if out.len() + n > len {
299                    return Err(bad("literal runs past the declared length"));
300                }
301                out.extend_from_slice(lit);
302                ip += n;
303                continue;
304            }
305            1 => {
306                let o = *src.get(ip).ok_or_else(|| bad("copy truncated"))?;
307                ip += 1;
308                (
309                    4 + usize::from((tag >> 2) & 7),
310                    usize::from(tag >> 5) << 8 | usize::from(o),
311                )
312            }
313            2 => {
314                let o = le(ip, 2).ok_or_else(|| bad("copy truncated"))?;
315                ip += 2;
316                (1 + usize::from(tag >> 2), o)
317            }
318            _ => {
319                let o = le(ip, 4).ok_or_else(|| bad("copy truncated"))?;
320                ip += 4;
321                (1 + usize::from(tag >> 2), o)
322            }
323        };
324        if offset == 0 || offset > out.len() || out.len() + n > len {
325            return Err(bad("back reference outside the output"));
326        }
327        let from = out.len() - offset;
328        for k in 0..n {
329            let v = out[from + k];
330            out.push(v);
331        }
332    }
333    if out.len() != len {
334        return Err(bad(&format!("decoded {} of {len} bytes", out.len())));
335    }
336    Ok(out)
337}
338
339fn decompress_stream(c: BloscCompressor, src: &[u8], expected: usize) -> Result<Vec<u8>> {
340    match c {
341        BloscCompressor::BloscLz => blosclz_decode(src, expected),
342        BloscCompressor::Lz4 => lz4_block_decode(src, expected),
343        BloscCompressor::Snappy => snappy_decode(src, expected),
344        BloscCompressor::Zlib => crate::zlib_decode(src, expected),
345        BloscCompressor::Zstd => crate::zstd_decode(src, expected),
346        BloscCompressor::Unknown(_) => Err(err(format!(
347            "the {} compressor inside Blosc is not decoded",
348            c.name()
349        ))),
350    }
351}
352
353/// BloscLZ (the default Blosc compressor), following `blosclz_decompress` in c-blosc (BSD-3).
354pub fn blosclz_decode(src: &[u8], maxout: usize) -> Result<Vec<u8>> {
355    const MAX_DISTANCE: usize = 8191;
356    let bad = || err("malformed BloscLZ stream");
357    let mut out: Vec<u8> = Vec::with_capacity(maxout);
358    if src.is_empty() {
359        return Ok(out);
360    }
361    let mut ip = 0usize;
362    let mut ctrl = usize::from(src[ip] & 31);
363    ip += 1;
364    loop {
365        if ctrl >= 32 {
366            let mut len = (ctrl >> 5) - 1;
367            let ofs = (ctrl & 31) << 8;
368            if len == 6 {
369                loop {
370                    if ip + 1 >= src.len() {
371                        return Err(bad());
372                    }
373                    let code = src[ip];
374                    ip += 1;
375                    len += usize::from(code);
376                    if code != 255 {
377                        break;
378                    }
379                }
380            } else if ip + 1 >= src.len() {
381                return Err(bad());
382            }
383            let code = usize::from(src[ip]);
384            ip += 1;
385            len += 3;
386            // distance back from the output position, minus one (see `ref--` in C)
387            let mut back = ofs + code;
388            if code == 255 && ofs == (31 << 8) {
389                if ip + 1 >= src.len() {
390                    return Err(bad());
391                }
392                let far = (usize::from(src[ip]) << 8) + usize::from(src[ip + 1]);
393                ip += 2;
394                back = far + MAX_DISTANCE;
395            }
396            back += 1;
397            if out.len() + len > maxout || back > out.len() {
398                return Err(bad());
399            }
400            let from = out.len() - back;
401            for k in 0..len {
402                let v = out[from + k];
403                out.push(v);
404            }
405            if ip >= src.len() {
406                break;
407            }
408            ctrl = usize::from(src[ip]);
409            ip += 1;
410        } else {
411            let n = ctrl + 1;
412            if out.len() + n > maxout || ip + n > src.len() {
413                return Err(bad());
414            }
415            out.extend_from_slice(&src[ip..ip + n]);
416            ip += n;
417            if ip >= src.len() {
418                break;
419            }
420            ctrl = usize::from(src[ip]);
421            ip += 1;
422        }
423    }
424    Ok(out)
425}
426
427/// One raw LZ4 block (no frame, no size prefix) that decodes to exactly `expected` bytes.
428pub fn lz4_block_decode(src: &[u8], expected: usize) -> Result<Vec<u8>> {
429    #[cfg(feature = "lz4")]
430    {
431        lz4_flex::block::decompress(src, expected).map_err(|e| CodecError::Decode {
432            codec: "lz4",
433            detail: e.to_string(),
434        })
435    }
436    #[cfg(not(feature = "lz4"))]
437    {
438        let _ = (src, expected);
439        Err(CodecError::NotCompiled {
440            codec: "lz4",
441            feature: "lz4",
442        })
443    }
444}
445
446/// numcodecs `LZ4`: a little-endian u32 decoded size, then one LZ4 block.
447pub fn lz4_sized_decode(src: &[u8]) -> Result<Vec<u8>> {
448    let n = le32(src, 0).ok_or_else(|| CodecError::Decode {
449        codec: "lz4",
450        detail: "missing 4-byte size prefix".into(),
451    })?;
452    if n > MAX_DECODED {
453        return Err(CodecError::Decode {
454            codec: "lz4",
455            detail: format!("size prefix declares {n} bytes"),
456        });
457    }
458    lz4_block_decode(&src[4..], n)
459}
460
461/// The HDF5 LZ4 filter (registered filter id 32004): a big-endian u64 decoded size and a
462/// big-endian u32 block size, then per block a big-endian u32 compressed size and the LZ4
463/// block (stored as is when the compressed size equals the block's decoded size).
464pub fn hdf5_lz4_decode(src: &[u8]) -> Result<Vec<u8>> {
465    let e = |d: &str| CodecError::Decode {
466        codec: "hdf5-lz4",
467        detail: d.into(),
468    };
469    let be = |at: usize, n: usize| -> Option<u64> {
470        let s = src.get(at..at.checked_add(n)?)?;
471        Some(s.iter().fold(0u64, |a, &b| a << 8 | u64::from(b)))
472    };
473    let total = usize::try_from(be(0, 8).ok_or_else(|| e("header truncated"))?)
474        .map_err(|_| e("declared size too large"))?;
475    let block = be(8, 4).ok_or_else(|| e("header truncated"))? as usize;
476    if total > MAX_DECODED {
477        return Err(e("declared size too large"));
478    }
479    if block == 0 && total > 0 {
480        return Err(e("block size 0"));
481    }
482    let mut out = Vec::with_capacity(total);
483    let mut at = 12usize;
484    while out.len() < total {
485        let want = block.min(total - out.len());
486        let c = be(at, 4).ok_or_else(|| e("block header truncated"))? as usize;
487        at += 4;
488        let end = at.checked_add(c).ok_or_else(|| e("block size overflows"))?;
489        let s = src
490            .get(at..end)
491            .ok_or_else(|| e("block runs past the chunk"))?;
492        if c == want {
493            out.extend_from_slice(s);
494        } else {
495            out.extend_from_slice(&lz4_block_decode(s, want)?);
496        }
497        at = end;
498    }
499    Ok(out)
500}
501
502#[cfg(test)]
503mod tests {
504    use super::*;
505
506    #[test]
507    fn memcpyed_and_shuffled_stored_blocks() {
508        // stored payload
509        let mut c = vec![
510            2u8,
511            1,
512            FLAG_MEMCPYED,
513            2,
514            4,
515            0,
516            0,
517            0,
518            4,
519            0,
520            0,
521            0,
522            20,
523            0,
524            0,
525            0,
526        ];
527        c.extend_from_slice(&[1, 2, 3, 4]);
528        assert_eq!(blosc_decode(&c).unwrap(), vec![1, 2, 3, 4]);
529        // one block of 4 u16 values, shuffled, split size == neblock (stored raw)
530        let mut c = vec![
531            2u8,
532            1,
533            FLAG_SHUFFLE | FLAG_DONT_SPLIT,
534            2,
535            8,
536            0,
537            0,
538            0,
539            8,
540            0,
541            0,
542            0,
543        ];
544        let body_start = 16 + 4;
545        c.extend_from_slice(&((body_start + 4 + 8) as u32).to_le_bytes());
546        c.extend_from_slice(&(body_start as u32).to_le_bytes());
547        c.extend_from_slice(&8u32.to_le_bytes());
548        // values 0x0201, 0x0403, 0x0605, 0x0807 shuffled: low bytes then high bytes
549        c.extend_from_slice(&[1, 3, 5, 7, 2, 4, 6, 8]);
550        assert_eq!(blosc_decode(&c).unwrap(), vec![1, 2, 3, 4, 5, 6, 7, 8]);
551        // truncated
552        assert!(blosc_decode(&c[..c.len() - 3]).is_err());
553        assert!(blosc_decode(&c[..10]).is_err());
554    }
555
556    #[test]
557    fn bitunshuffle_transposes_bits() {
558        // 8 u16 elements 0x0001, 0x0002, ..., 0x0008: bit rows of 8 bits (1 byte) each
559        let vals: Vec<u16> = (1..=8).collect();
560        let mut shuffled = vec![0u8; 16];
561        for (i, v) in vals.iter().enumerate() {
562            for j in 0..2 {
563                let byte = v.to_le_bytes()[j];
564                for k in 0..8 {
565                    if byte >> k & 1 == 1 {
566                        shuffled[j * 8 + k] |= 1 << i;
567                    }
568                }
569            }
570        }
571        let mut out = vec![0u8; 16];
572        bitunshuffle(2, &shuffled, &mut out);
573        let back: Vec<u16> = out
574            .chunks(2)
575            .map(|c| u16::from_le_bytes([c[0], c[1]]))
576            .collect();
577        assert_eq!(back, vals);
578        // not a multiple of 8 elements: stored as it is
579        let mut out = vec![0u8; 6];
580        bitunshuffle(2, &[1, 2, 3, 4, 5, 6], &mut out);
581        assert_eq!(out, [1, 2, 3, 4, 5, 6]);
582    }
583
584    #[test]
585    fn snappy_literals_and_copies() {
586        // "abcabcabcd": literal "abc", copy len 6 offset 3 (1-byte offset form), literal "d"
587        let src = [10u8, 0x08, b'a', b'b', b'c', 0x09, 3, 0x00, b'd'];
588        assert_eq!(snappy_decode(&src, 10).unwrap(), b"abcabcabcd");
589        assert!(snappy_decode(&src, 9).is_err());
590        assert!(snappy_decode(&src[..6], 10).is_err());
591        assert!(snappy_decode(&[4, 0x05, 9, 0], 4).is_err());
592    }
593
594    #[test]
595    fn blosclz_literal_and_match() {
596        // literal run of 3 ("abc"), a match of length 3 at distance 3, a literal "d"
597        let src = [2u8, b'a', b'b', b'c', 0x20, 2, 0, b'd'];
598        assert_eq!(blosclz_decode(&src, 7).unwrap(), b"abcabcd");
599        assert!(blosclz_decode(&[0, b'x', 0x20, 5, 0, b'y'], 8).is_err());
600    }
601
602    #[test]
603    fn hdf5_lz4_stored_block() {
604        let mut s = Vec::new();
605        s.extend_from_slice(&4u64.to_be_bytes());
606        s.extend_from_slice(&4u32.to_be_bytes());
607        s.extend_from_slice(&4u32.to_be_bytes());
608        s.extend_from_slice(&[9, 8, 7, 6]);
609        assert_eq!(hdf5_lz4_decode(&s).unwrap(), vec![9, 8, 7, 6]);
610        assert!(hdf5_lz4_decode(&s[..14]).is_err());
611    }
612}