rapidgzip_core/index/
mod.rs

1//! Random-access indexes for gzip, zlib, and raw-DEFLATE sources.
2//!
3//! This module is independent of the decoder: it defines the index data model,
4//! validates it, and reads and writes the supported on-disk formats. Use an
5//! index for random access with [`crate::IndexedReader`].
6
7mod build;
8mod gzi;
9mod gzidx;
10mod gztool;
11mod native;
12mod window_codec;
13
14pub(crate) use build::IndexCollector;
15pub use gzidx::{decode_bit_offset, encode_bit_offset};
16pub use gztool::WithLines;
17pub(crate) use window_codec::{zlib_compress_window, zlib_decompress_window};
18
19use std::borrow::Cow;
20use std::collections::HashMap;
21use std::error::Error;
22use std::fmt::{self, Display, Formatter};
23use std::io::{self, Read, Write};
24use std::num::NonZeroU64;
25use std::sync::Arc;
26
27/// DEFLATE history size, in bytes, required at a resume point.
28pub const WINDOW_SIZE: usize = 32768;
29
30/// Provenance of the compressed source described by an index.
31#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
32#[non_exhaustive]
33pub enum IndexKind {
34    /// Ordinary gzip, including concatenated gzip members.
35    #[default]
36    Gzip,
37    /// A stream proven to consist entirely of BGZF blocks.
38    Bgzf,
39    /// One RFC 1950 zlib stream.
40    Zlib,
41    /// One unwrapped RFC 1951 DEFLATE stream.
42    RawDeflate,
43}
44
45/// How inflation resumes at a checkpoint.
46#[derive(Clone, Copy, Debug, Eq, PartialEq)]
47#[non_exhaustive]
48pub enum CheckpointKind {
49    /// The offset points at the gzip magic bytes of a complete member.
50    GzipMemberHeader,
51    /// The offset points at raw DEFLATE immediately after a known member
52    /// header. Keeping the header offset permits full verification while
53    /// retaining compatibility with raw-DEFLATE index formats.
54    GzipMemberDeflate {
55        /// Absolute byte offset of the gzip member header.
56        header_offset_in_bytes: u64,
57    },
58    /// The offset points at the two-byte header of the zlib stream.
59    ZlibHeader,
60    /// The offset points at the first bit of an unwrapped DEFLATE stream.
61    RawDeflateStart,
62    /// The offset points at the first bit of a raw DEFLATE block.
63    DeflateBlock,
64}
65
66/// How predecessor windows are retained while an index is built.
67#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
68#[non_exhaustive]
69pub enum WindowStorage {
70    /// Retain each 32 KiB window verbatim.
71    Raw,
72    /// Retain the zlib-compressed form when it is smaller.
73    #[default]
74    Zlib,
75}
76
77/// Options for collecting a random-access index during a decode.
78#[derive(Clone, Copy, Debug, Eq, PartialEq)]
79pub struct IndexOptions {
80    /// Target distance between retained interior checkpoints.
81    pub checkpoint_spacing: NonZeroU64,
82    /// In-memory representation of retained predecessor windows.
83    pub window_storage: WindowStorage,
84}
85
86impl Default for IndexOptions {
87    fn default() -> Self {
88        Self {
89            checkpoint_spacing: NonZeroU64::new(4 * 1024 * 1024).expect("four MiB is non-zero"),
90            window_storage: WindowStorage::Zlib,
91        }
92    }
93}
94
95/// Allocation limits applied while parsing an untrusted index file.
96///
97/// The defaults permit more than four million checkpoints while preventing a
98/// small hostile header from requesting an effectively unbounded allocation.
99/// Applications opening exceptionally large trusted indexes can raise these
100/// limits explicitly with the `read_*_with_options` methods.
101#[derive(Clone, Copy, Debug, Eq, PartialEq)]
102pub struct IndexReadOptions {
103    /// Maximum number of checkpoint records.
104    pub max_checkpoints: usize,
105    /// Maximum sum of stored predecessor-window payload bytes.
106    pub max_window_bytes: u64,
107    /// Maximum bytes in one stored predecessor-window payload.
108    pub max_window_payload_bytes: usize,
109}
110
111impl Default for IndexReadOptions {
112    fn default() -> Self {
113        Self {
114            max_checkpoints: 4 * 1024 * 1024,
115            max_window_bytes: 512 * 1024 * 1024,
116            max_window_payload_bytes: 64 * 1024,
117        }
118    }
119}
120
121/// A random-access point into a DEFLATE-based stream.
122///
123/// The compressed position is a bit offset because a DEFLATE block boundary is
124/// not generally byte aligned. [`CheckpointKind`] says whether the offset is a
125/// gzip member header, a known member's raw payload, a zlib header, a raw
126/// stream start, or an interior DEFLATE block, so a reader never has to infer
127/// framing from compressed bytes.
128#[derive(Clone, Copy, Debug, Eq, PartialEq)]
129pub struct Checkpoint {
130    /// Absolute compressed bit offset from the start of the source.
131    pub compressed_offset_in_bits: u64,
132    /// Absolute decompressed byte offset across all members.
133    pub uncompressed_offset_in_bytes: u64,
134    /// How a decoder resumes at this compressed position.
135    pub kind: CheckpointKind,
136    /// Number of newline bytes preceding this point, when supplied by the index.
137    pub line_offset: Option<u64>,
138}
139
140/// Predecessor history for a checkpoint.
141///
142/// An empty window means no history is required: the start of the source, a
143/// member boundary, or an independent BGZF block. A non-empty window is
144/// exactly [`WINDOW_SIZE`] bytes of decompressed history, held either raw or
145/// zlib-compressed to bound resident memory.
146#[derive(Clone, Debug, Eq, PartialEq)]
147pub struct StoredWindow {
148    payload: Vec<u8>,
149    compressed: bool,
150}
151
152impl StoredWindow {
153    /// Returns a window carrying no history.
154    #[must_use]
155    pub const fn empty() -> Self {
156        Self {
157            payload: Vec::new(),
158            compressed: false,
159        }
160    }
161
162    /// Stores exactly one raw DEFLATE history window.
163    ///
164    /// # Errors
165    ///
166    /// Returns [`IndexError::InvalidWindowSize`] unless `bytes` contains
167    /// exactly [`WINDOW_SIZE`] bytes.
168    pub fn from_raw(bytes: impl Into<Vec<u8>>) -> Result<Self, IndexError> {
169        let payload = bytes.into();
170        validate_expanded_window(&payload)?;
171        Ok(Self {
172            payload,
173            compressed: false,
174        })
175    }
176
177    /// Returns whether this window carries no history.
178    #[must_use]
179    pub const fn is_empty(&self) -> bool {
180        self.payload.is_empty()
181    }
182
183    /// Returns the number of bytes currently held, compressed or not.
184    #[must_use]
185    pub const fn stored_len(&self) -> usize {
186        self.payload.len()
187    }
188
189    /// Returns whether the payload is held zlib-compressed.
190    #[must_use]
191    pub const fn is_compressed(&self) -> bool {
192        self.compressed
193    }
194
195    /// Stores `bytes`, optionally zlib-compressed to reduce resident memory.
196    ///
197    /// History that does not shrink is stored raw. The input must contain
198    /// exactly [`WINDOW_SIZE`] bytes.
199    pub fn from_raw_maybe_compress(
200        bytes: impl Into<Vec<u8>>,
201        compress: bool,
202    ) -> Result<Self, IndexError> {
203        let bytes = bytes.into();
204        validate_expanded_window(&bytes)?;
205        if !compress {
206            return Self::from_raw(bytes);
207        }
208        let payload = zlib_compress_window(&bytes)?;
209        if payload.len() >= bytes.len() {
210            return Self::from_raw(bytes);
211        }
212        // This payload was produced from the exact-size `bytes` validated
213        // above, so re-inflating it here would duplicate codec work at every
214        // collected checkpoint. Imported payloads still go through the strict
215        // `from_compressed` validation path.
216        Ok(Self {
217            payload,
218            compressed: true,
219        })
220    }
221
222    /// Returns the window history, expanding it when it is held compressed.
223    pub fn decompressed(&self) -> Result<Cow<'_, [u8]>, IndexError> {
224        if self.compressed {
225            Ok(Cow::Owned(zlib_decompress_window(&self.payload)?))
226        } else {
227            Ok(Cow::Borrowed(&self.payload))
228        }
229    }
230
231    pub(crate) fn from_compressed(payload: Vec<u8>) -> Result<Self, IndexError> {
232        let expanded = zlib_decompress_window(&payload)?;
233        validate_expanded_window(&expanded)?;
234        Ok(Self {
235            payload,
236            compressed: true,
237        })
238    }
239
240    pub(crate) fn payload(&self) -> &[u8] {
241        &self.payload
242    }
243}
244
245fn validate_expanded_window(bytes: &[u8]) -> Result<(), IndexError> {
246    if bytes.len() != WINDOW_SIZE {
247        return Err(IndexError::InvalidWindowSize(
248            u64::try_from(bytes.len()).unwrap_or(u64::MAX),
249        ));
250    }
251    Ok(())
252}
253
254/// Predecessor windows keyed by compressed bit offset.
255#[derive(Clone, Debug, Default, Eq, PartialEq)]
256pub struct WindowMap {
257    windows: HashMap<u64, StoredWindow>,
258}
259
260impl WindowMap {
261    /// Returns an empty map.
262    #[must_use]
263    pub fn new() -> Self {
264        Self::default()
265    }
266
267    /// Associates `window` with `compressed_offset_in_bits`.
268    pub fn insert(&mut self, compressed_offset_in_bits: u64, window: StoredWindow) {
269        self.windows.insert(compressed_offset_in_bits, window);
270    }
271
272    /// Returns the window stored at `compressed_offset_in_bits`, if any.
273    #[must_use]
274    pub fn get(&self, compressed_offset_in_bits: u64) -> Option<&StoredWindow> {
275        self.windows.get(&compressed_offset_in_bits)
276    }
277
278    /// Returns the number of stored windows.
279    #[must_use]
280    pub fn len(&self) -> usize {
281        self.windows.len()
282    }
283
284    /// Returns whether no windows are stored.
285    #[must_use]
286    pub fn is_empty(&self) -> bool {
287        self.windows.is_empty()
288    }
289}
290
291/// An in-memory random-access index for a DEFLATE-based stream.
292#[derive(Clone, Debug, Default, Eq, PartialEq)]
293pub struct DeflateIndex {
294    pub(crate) checkpoints: Vec<Checkpoint>,
295    pub(crate) windows: WindowMap,
296    pub(crate) kind: IndexKind,
297    pub(crate) compressed_size_in_bytes: Option<u64>,
298    pub(crate) uncompressed_size_in_bytes: Option<u64>,
299    pub(crate) checkpoint_spacing_in_bytes: Option<u64>,
300    pub(crate) total_line_count: Option<u64>,
301}
302
303impl DeflateIndex {
304    /// Returns an empty index.
305    #[must_use]
306    pub fn new() -> Self {
307        Self::default()
308    }
309
310    /// Returns the source/container provenance recorded by this index.
311    #[must_use]
312    pub const fn kind(&self) -> IndexKind {
313        self.kind
314    }
315
316    /// Records source/container provenance.
317    pub const fn set_kind(&mut self, kind: IndexKind) {
318        self.kind = kind;
319    }
320
321    /// Returns the known compressed source size in bytes.
322    #[must_use]
323    pub const fn compressed_size(&self) -> Option<u64> {
324        self.compressed_size_in_bytes
325    }
326
327    /// Records the compressed source size, or clears it when unknown.
328    pub const fn set_compressed_size(&mut self, size: Option<u64>) {
329        self.compressed_size_in_bytes = size;
330    }
331
332    /// Returns the known total decompressed size in bytes.
333    #[must_use]
334    pub const fn uncompressed_size(&self) -> Option<u64> {
335        self.uncompressed_size_in_bytes
336    }
337
338    /// Records the total decompressed size, or clears it when unknown.
339    pub const fn set_uncompressed_size(&mut self, size: Option<u64>) {
340        self.uncompressed_size_in_bytes = size;
341    }
342
343    /// Returns the target decompressed checkpoint spacing, when recorded.
344    #[must_use]
345    pub const fn checkpoint_spacing(&self) -> Option<u64> {
346        self.checkpoint_spacing_in_bytes
347    }
348
349    /// Records the target decompressed checkpoint spacing.
350    pub const fn set_checkpoint_spacing(&mut self, spacing: Option<u64>) {
351        self.checkpoint_spacing_in_bytes = spacing;
352    }
353
354    /// Returns the total line count carried by the source index.
355    #[must_use]
356    pub const fn total_line_count(&self) -> Option<u64> {
357        self.total_line_count
358    }
359
360    /// Records the total line count, or clears it when unknown.
361    pub const fn set_total_line_count(&mut self, count: Option<u64>) {
362        self.total_line_count = count;
363    }
364
365    /// Appends a checkpoint and its predecessor window.
366    ///
367    /// Ordering is not checked here; call [`Self::validate`] once the index is
368    /// complete.
369    pub fn push(&mut self, checkpoint: Checkpoint, window: StoredWindow) -> Result<(), IndexError> {
370        if matches!(
371            checkpoint.kind,
372            CheckpointKind::GzipMemberHeader
373                | CheckpointKind::ZlibHeader
374                | CheckpointKind::RawDeflateStart
375        ) {
376            if !checkpoint.compressed_offset_in_bits.is_multiple_of(8) {
377                return Err(IndexError::InvalidCheckpoint(
378                    "stream-start checkpoint is not byte aligned",
379                ));
380            }
381            if !window.is_empty() {
382                return Err(IndexError::InvalidCheckpoint(
383                    "stream-start checkpoint carries a predecessor window",
384                ));
385            }
386        }
387        if let CheckpointKind::GzipMemberDeflate {
388            header_offset_in_bytes,
389        } = checkpoint.kind
390        {
391            if !checkpoint.compressed_offset_in_bits.is_multiple_of(8)
392                || header_offset_in_bytes.saturating_mul(8) >= checkpoint.compressed_offset_in_bits
393            {
394                return Err(IndexError::InvalidCheckpoint(
395                    "member-DEFLATE checkpoint has inconsistent header and payload offsets",
396                ));
397            }
398            if !window.is_empty() {
399                return Err(IndexError::InvalidCheckpoint(
400                    "member-DEFLATE checkpoint carries a predecessor window",
401                ));
402            }
403        }
404        if !window.is_empty() {
405            validate_expanded_window(&window.decompressed()?)?;
406        }
407        if !window.is_empty() {
408            self.windows
409                .insert(checkpoint.compressed_offset_in_bits, window);
410        }
411        self.checkpoints.push(checkpoint);
412        Ok(())
413    }
414
415    /// Returns the number of checkpoints.
416    #[must_use]
417    pub fn checkpoint_count(&self) -> usize {
418        self.checkpoints.len()
419    }
420
421    /// Returns whether the index holds no checkpoints.
422    #[must_use]
423    pub fn is_empty(&self) -> bool {
424        self.checkpoints.is_empty()
425    }
426
427    /// Returns the checkpoints in order.
428    #[must_use]
429    pub fn checkpoints(&self) -> &[Checkpoint] {
430        &self.checkpoints
431    }
432
433    /// Returns the stored predecessor windows.
434    #[must_use]
435    pub const fn windows(&self) -> &WindowMap {
436        &self.windows
437    }
438
439    /// Returns the last checkpoint at or before `uncompressed_offset`.
440    #[must_use]
441    pub fn checkpoint_at_or_before(&self, uncompressed_offset: u64) -> Option<&Checkpoint> {
442        let position = self
443            .checkpoints
444            .partition_point(|point| point.uncompressed_offset_in_bytes <= uncompressed_offset);
445        position
446            .checked_sub(1)
447            .map(|index| &self.checkpoints[index])
448    }
449
450    /// Returns the latest checkpoint proven not to be after zero-based `line`'s start.
451    ///
452    /// A line offset is the number of newline bytes preceding a checkpoint.
453    /// A checkpoint with the same offset as `line` may already be inside that
454    /// line, so targets after line zero resume from the last checkpoint with a
455    /// strictly smaller line offset. Line zero resumes from a checkpoint at
456    /// decoded offset zero. This returns `None` unless the index has a total
457    /// line count and every checkpoint is annotated, because selecting from
458    /// partially annotated metadata could skip past the requested line.
459    #[must_use]
460    pub fn checkpoint_at_or_before_line(&self, line: u64) -> Option<&Checkpoint> {
461        self.total_line_count?;
462        if self
463            .checkpoints
464            .iter()
465            .any(|checkpoint| checkpoint.line_offset.is_none())
466        {
467            return None;
468        }
469        if line == 0 {
470            return self
471                .checkpoints
472                .iter()
473                .take_while(|checkpoint| checkpoint.uncompressed_offset_in_bytes == 0)
474                .last();
475        }
476        let position = self.checkpoints.partition_point(|checkpoint| {
477            checkpoint.line_offset.expect("completeness checked above") < line
478        });
479        position
480            .checked_sub(1)
481            .map(|index| &self.checkpoints[index])
482    }
483
484    /// Writes this index in the crate's native versioned format.
485    ///
486    /// The native format is the only one that round-trips every field,
487    /// including line offsets and compressed window payloads.
488    pub fn write_native(&self, writer: &mut impl Write) -> Result<(), IndexError> {
489        native::write_native(self, writer)
490    }
491
492    /// Reads an index written by [`Self::write_native`].
493    pub fn read_native(reader: &mut impl Read) -> Result<Self, IndexError> {
494        Self::read_native_with_options(reader, IndexReadOptions::default())
495    }
496
497    /// Reads a native index using explicit untrusted-input limits.
498    pub fn read_native_with_options(
499        reader: &mut impl Read,
500        options: IndexReadOptions,
501    ) -> Result<Self, IndexError> {
502        native::read_native(reader, options)
503    }
504
505    /// Writes this index in indexed_gzip `GZIDX` version 1 format.
506    ///
507    /// Every non-empty window is written as exactly [`WINDOW_SIZE`] bytes.
508    pub fn write_gzidx(&self, writer: &mut impl Write) -> Result<(), IndexError> {
509        gzidx::write_gzidx(self, writer)
510    }
511
512    /// Reads an indexed_gzip `GZIDX` index, accepting versions 0 and 1.
513    ///
514    /// When `archive_size` is `Some`, it must equal the compressed size stored
515    /// in the index header.
516    pub fn read_gzidx(
517        reader: &mut impl Read,
518        archive_size: Option<u64>,
519    ) -> Result<Self, IndexError> {
520        Self::read_gzidx_with_options(reader, archive_size, IndexReadOptions::default())
521    }
522
523    /// Reads a GZIDX index using explicit untrusted-input limits.
524    pub fn read_gzidx_with_options(
525        reader: &mut impl Read,
526        archive_size: Option<u64>,
527        options: IndexReadOptions,
528    ) -> Result<Self, IndexError> {
529        gzidx::read_gzidx(reader, archive_size, options)
530    }
531
532    /// Writes this index in htslib BGZF `.gzi` format.
533    ///
534    /// Only indexes whose checkpoints all sit on independent member or block
535    /// boundaries can be represented; a checkpoint carrying a predecessor
536    /// window or a non-byte-aligned offset is refused, because reimporting it
537    /// would install an empty window and seek to the wrong place.
538    pub fn write_gzi(&self, writer: &mut impl Write) -> Result<(), IndexError> {
539        gzi::write_gzi(self, writer)
540    }
541
542    /// Reads an htslib BGZF `.gzi` index.
543    ///
544    /// The format does not record the uncompressed size, so the result leaves
545    /// it unknown. `archive_size`, when supplied, is recorded as the compressed
546    /// size.
547    pub fn read_gzi(reader: &mut impl Read, archive_size: Option<u64>) -> Result<Self, IndexError> {
548        Self::read_gzi_with_options(reader, archive_size, IndexReadOptions::default())
549    }
550
551    /// Reads a `.gzi` index using explicit untrusted-input limits.
552    pub fn read_gzi_with_options(
553        reader: &mut impl Read,
554        archive_size: Option<u64>,
555        options: IndexReadOptions,
556    ) -> Result<Self, IndexError> {
557        gzi::read_gzi(reader, archive_size, options)
558    }
559
560    /// Writes this index in gztool format.
561    ///
562    /// [`WithLines::Yes`] writes version 1 with per-point line counters;
563    /// [`WithLines::No`] writes version 0 and omits them. Windows are stored
564    /// zlib-compressed, as gztool does.
565    pub fn write_gztool(
566        &self,
567        writer: &mut impl Write,
568        lines: WithLines,
569    ) -> Result<(), IndexError> {
570        gztool::write_gztool(self, writer, lines)
571    }
572
573    /// Reads a complete gztool index of either version.
574    ///
575    /// gztool does not record the compressed archive size, so `archive_size`,
576    /// when supplied, is recorded as the compressed size.
577    pub fn read_gztool(
578        reader: &mut impl Read,
579        archive_size: Option<u64>,
580    ) -> Result<Self, IndexError> {
581        Self::read_gztool_with_options(reader, archive_size, IndexReadOptions::default())
582    }
583
584    /// Reads a gztool index using explicit untrusted-input limits.
585    pub fn read_gztool_with_options(
586        reader: &mut impl Read,
587        archive_size: Option<u64>,
588        options: IndexReadOptions,
589    ) -> Result<Self, IndexError> {
590        gztool::read_gztool(reader, archive_size, options)
591    }
592
593    /// Checks the index invariants.
594    ///
595    /// Compressed offsets must increase strictly and decompressed offsets must
596    /// not decrease. Every non-empty window must
597    /// be exactly [`WINDOW_SIZE`] bytes, and offsets must fall inside the
598    /// recorded sizes when those are known.
599    pub fn validate(&self) -> Result<(), IndexError> {
600        let mut previous: Option<&Checkpoint> = None;
601        let mut previous_line_offset = None;
602        if self.total_line_count.is_some_and(|lines| {
603            self.uncompressed_size_in_bytes
604                .is_some_and(|bytes| lines > bytes)
605        }) {
606            return Err(IndexError::InvalidCheckpoint(
607                "total line count exceeds the uncompressed size",
608            ));
609        }
610        for checkpoint in &self.checkpoints {
611            if !checkpoint_kind_matches_index(self.kind, checkpoint.kind) {
612                return Err(IndexError::InvalidCheckpoint(
613                    "checkpoint framing is incompatible with index provenance",
614                ));
615            }
616            if let Some(previous) = previous {
617                if checkpoint.compressed_offset_in_bits <= previous.compressed_offset_in_bits {
618                    return Err(IndexError::InvalidCheckpoint(
619                        "compressed offsets are not strictly increasing",
620                    ));
621                }
622                if checkpoint.uncompressed_offset_in_bytes < previous.uncompressed_offset_in_bytes {
623                    return Err(IndexError::InvalidCheckpoint(
624                        "uncompressed offsets are decreasing",
625                    ));
626                }
627            }
628
629            if self
630                .compressed_size_in_bytes
631                .is_some_and(|size| checkpoint.compressed_offset_in_bits > size.saturating_mul(8))
632            {
633                return Err(IndexError::InvalidCheckpoint(
634                    "checkpoint compressed offset is after the source end",
635                ));
636            }
637            if self
638                .uncompressed_size_in_bytes
639                .is_some_and(|size| checkpoint.uncompressed_offset_in_bytes > size)
640            {
641                return Err(IndexError::InvalidCheckpoint(
642                    "checkpoint uncompressed offset is after the source end",
643                ));
644            }
645            if checkpoint
646                .line_offset
647                .is_some_and(|lines| lines > checkpoint.uncompressed_offset_in_bytes)
648            {
649                return Err(IndexError::InvalidCheckpoint(
650                    "checkpoint line offset exceeds its uncompressed offset",
651                ));
652            }
653            if let Some(line_offset) = checkpoint.line_offset {
654                if previous_line_offset.is_some_and(|previous| line_offset < previous) {
655                    return Err(IndexError::InvalidCheckpoint(
656                        "checkpoint line offsets are decreasing",
657                    ));
658                }
659                if self
660                    .total_line_count
661                    .is_some_and(|total| line_offset > total)
662                {
663                    return Err(IndexError::InvalidCheckpoint(
664                        "checkpoint line offset exceeds the total line count",
665                    ));
666                }
667                previous_line_offset = Some(line_offset);
668            }
669
670            if let Some(window) = self.windows.get(checkpoint.compressed_offset_in_bits) {
671                validate_expanded_window(&window.decompressed()?)?;
672            }
673            if matches!(
674                checkpoint.kind,
675                CheckpointKind::GzipMemberHeader
676                    | CheckpointKind::ZlibHeader
677                    | CheckpointKind::RawDeflateStart
678            ) {
679                if !checkpoint.compressed_offset_in_bits.is_multiple_of(8) {
680                    return Err(IndexError::InvalidCheckpoint(
681                        "stream-start checkpoint is not byte aligned",
682                    ));
683                }
684                if self
685                    .windows
686                    .get(checkpoint.compressed_offset_in_bits)
687                    .is_some()
688                {
689                    return Err(IndexError::InvalidCheckpoint(
690                        "stream-start checkpoint carries a predecessor window",
691                    ));
692                }
693            }
694            if let CheckpointKind::GzipMemberDeflate {
695                header_offset_in_bytes,
696            } = checkpoint.kind
697            {
698                if !checkpoint.compressed_offset_in_bits.is_multiple_of(8)
699                    || header_offset_in_bytes.saturating_mul(8)
700                        >= checkpoint.compressed_offset_in_bits
701                {
702                    return Err(IndexError::InvalidCheckpoint(
703                        "member-DEFLATE checkpoint has inconsistent header and payload offsets",
704                    ));
705                }
706                if self
707                    .windows
708                    .get(checkpoint.compressed_offset_in_bits)
709                    .is_some()
710                {
711                    return Err(IndexError::InvalidCheckpoint(
712                        "member-DEFLATE checkpoint carries a predecessor window",
713                    ));
714                }
715            }
716            if matches!(
717                checkpoint.kind,
718                CheckpointKind::ZlibHeader | CheckpointKind::RawDeflateStart
719            ) && (checkpoint.compressed_offset_in_bits != 0
720                || checkpoint.uncompressed_offset_in_bytes != 0)
721            {
722                return Err(IndexError::InvalidCheckpoint(
723                    "single-stream start checkpoint is not at the source origin",
724                ));
725            }
726            if matches!(self.kind, IndexKind::Zlib | IndexKind::RawDeflate)
727                && matches!(checkpoint.kind, CheckpointKind::DeflateBlock)
728                && self
729                    .windows
730                    .get(checkpoint.compressed_offset_in_bits)
731                    .is_none()
732            {
733                return Err(IndexError::InvalidCheckpoint(
734                    "single-stream interior checkpoint has no predecessor window",
735                ));
736            }
737
738            previous = Some(checkpoint);
739        }
740        Ok(())
741    }
742}
743
744const fn checkpoint_kind_matches_index(kind: IndexKind, checkpoint: CheckpointKind) -> bool {
745    match kind {
746        IndexKind::Gzip | IndexKind::Bgzf => matches!(
747            checkpoint,
748            CheckpointKind::GzipMemberHeader
749                | CheckpointKind::GzipMemberDeflate { .. }
750                | CheckpointKind::DeflateBlock
751        ),
752        IndexKind::Zlib => matches!(
753            checkpoint,
754            CheckpointKind::ZlibHeader | CheckpointKind::DeflateBlock
755        ),
756        IndexKind::RawDeflate => matches!(
757            checkpoint,
758            CheckpointKind::RawDeflateStart | CheckpointKind::DeflateBlock
759        ),
760    }
761}
762
763/// Errors produced while parsing, validating, or writing an index.
764#[derive(Clone, Debug)]
765#[non_exhaustive]
766pub enum IndexError {
767    /// The file did not begin with the expected magic bytes.
768    BadMagic {
769        /// The bytes actually observed.
770        found: Vec<u8>,
771    },
772    /// The format version is newer than this crate supports.
773    UnsupportedVersion(u64),
774    /// The index declared a window size other than [`WINDOW_SIZE`].
775    InvalidWindowSize(u64),
776    /// A declared count or length exceeded the accepted maximum.
777    ExcessiveLength {
778        /// What the value described.
779        what: &'static str,
780        /// The value read from the file.
781        value: u64,
782    },
783    /// A checkpoint field was denormal or inconsistent.
784    InvalidCheckpoint(&'static str),
785    /// A caller-supplied archive size disagreed with the index.
786    ArchiveSizeMismatch {
787        /// Size recorded in the index.
788        index_size: u64,
789        /// Size supplied by the caller.
790        archive_size: u64,
791    },
792    /// The index ended before a complete value could be read.
793    Truncated,
794    /// A window payload could not be compressed or decompressed.
795    WindowCodec(&'static str),
796    /// The process could not reserve memory within the configured limit.
797    AllocationFailed {
798        /// What allocation was attempted.
799        what: &'static str,
800    },
801    /// A format contained flags this crate does not understand.
802    UnsupportedFlags {
803        /// Flags observed in the input.
804        flags: u64,
805    },
806    /// An operation requires metadata not present in this index.
807    MissingMetadata(&'static str),
808    /// The selected on-disk representation cannot encode this source format.
809    IncompatibleFormat {
810        /// Operation or on-disk representation that was requested.
811        operation: &'static str,
812        /// Provenance recorded by the index.
813        kind: IndexKind,
814    },
815    /// An I/O failure occurred.
816    Io {
817        /// The original error.
818        source: Arc<io::Error>,
819    },
820}
821
822impl IndexError {
823    pub(crate) fn io(error: io::Error) -> Self {
824        if error.kind() == io::ErrorKind::UnexpectedEof {
825            Self::Truncated
826        } else {
827            Self::Io {
828                source: Arc::new(error),
829            }
830        }
831    }
832}
833
834impl Display for IndexError {
835    fn fmt(&self, formatter: &mut Formatter<'_>) -> fmt::Result {
836        match self {
837            Self::BadMagic { found } => write!(formatter, "invalid index magic bytes: {found:?}"),
838            Self::UnsupportedVersion(version) => {
839                write!(formatter, "unsupported index format version {version}")
840            }
841            Self::InvalidWindowSize(size) => write!(
842                formatter,
843                "invalid index window size {size}, expected {WINDOW_SIZE}"
844            ),
845            Self::ExcessiveLength { what, value } => {
846                write!(formatter, "index declares an excessive {what}: {value}")
847            }
848            Self::InvalidCheckpoint(reason) => {
849                write!(formatter, "invalid index checkpoint: {reason}")
850            }
851            Self::ArchiveSizeMismatch {
852                index_size,
853                archive_size,
854            } => write!(
855                formatter,
856                "archive size {archive_size} does not match index size {index_size}"
857            ),
858            Self::Truncated => formatter.write_str("truncated index"),
859            Self::WindowCodec(reason) => write!(formatter, "index window codec failure: {reason}"),
860            Self::AllocationFailed { what } => {
861                write!(formatter, "could not allocate memory for index {what}")
862            }
863            Self::UnsupportedFlags { flags } => {
864                write!(formatter, "unsupported index flags {flags:#x}")
865            }
866            Self::MissingMetadata(what) => write!(formatter, "index is missing {what}"),
867            Self::IncompatibleFormat { operation, kind } => {
868                write!(formatter, "{operation} cannot represent a {kind:?} index")
869            }
870            Self::Io { source } => write!(formatter, "index I/O error: {source}"),
871        }
872    }
873}
874
875impl Error for IndexError {
876    fn source(&self) -> Option<&(dyn Error + 'static)> {
877        match self {
878            Self::Io { source } => Some(source.as_ref()),
879            _ => None,
880        }
881    }
882}
883
884impl PartialEq for IndexError {
885    fn eq(&self, other: &Self) -> bool {
886        match (self, other) {
887            (Self::BadMagic { found: left }, Self::BadMagic { found: right }) => left == right,
888            (Self::UnsupportedVersion(left), Self::UnsupportedVersion(right)) => left == right,
889            (Self::InvalidWindowSize(left), Self::InvalidWindowSize(right)) => left == right,
890            (
891                Self::ExcessiveLength {
892                    what: left_what,
893                    value: left_value,
894                },
895                Self::ExcessiveLength {
896                    what: right_what,
897                    value: right_value,
898                },
899            ) => left_what == right_what && left_value == right_value,
900            (Self::InvalidCheckpoint(left), Self::InvalidCheckpoint(right)) => left == right,
901            (
902                Self::ArchiveSizeMismatch {
903                    index_size: left_index,
904                    archive_size: left_archive,
905                },
906                Self::ArchiveSizeMismatch {
907                    index_size: right_index,
908                    archive_size: right_archive,
909                },
910            ) => left_index == right_index && left_archive == right_archive,
911            (Self::Truncated, Self::Truncated) => true,
912            (Self::WindowCodec(left), Self::WindowCodec(right)) => left == right,
913            (Self::AllocationFailed { what: left }, Self::AllocationFailed { what: right }) => {
914                left == right
915            }
916            (Self::UnsupportedFlags { flags: left }, Self::UnsupportedFlags { flags: right }) => {
917                left == right
918            }
919            (Self::MissingMetadata(left), Self::MissingMetadata(right)) => left == right,
920            (
921                Self::IncompatibleFormat {
922                    operation: left_operation,
923                    kind: left_kind,
924                },
925                Self::IncompatibleFormat {
926                    operation: right_operation,
927                    kind: right_kind,
928                },
929            ) => left_operation == right_operation && left_kind == right_kind,
930            (Self::Io { source: left }, Self::Io { source: right }) => {
931                left.kind() == right.kind() && left.to_string() == right.to_string()
932            }
933            _ => false,
934        }
935    }
936}
937
938impl Eq for IndexError {}
939
940pub(crate) fn read_exact_bytes(
941    reader: &mut impl Read,
942    buffer: &mut [u8],
943) -> Result<(), IndexError> {
944    reader.read_exact(buffer).map_err(IndexError::io)
945}
946
947pub(crate) fn read_u8(reader: &mut impl Read) -> Result<u8, IndexError> {
948    let mut byte = [0u8; 1];
949    read_exact_bytes(reader, &mut byte)?;
950    Ok(byte[0])
951}
952
953macro_rules! integer_io {
954    ($read:ident, $write:ident, $type:ty, $from:ident, $to:ident) => {
955        #[allow(dead_code)]
956        pub(crate) fn $read(reader: &mut impl Read) -> Result<$type, IndexError> {
957            let mut bytes = [0u8; size_of::<$type>()];
958            read_exact_bytes(reader, &mut bytes)?;
959            Ok(<$type>::$from(bytes))
960        }
961
962        #[allow(dead_code)]
963        pub(crate) fn $write(writer: &mut impl Write, value: $type) -> Result<(), IndexError> {
964            writer.write_all(&value.$to()).map_err(IndexError::io)
965        }
966    };
967}
968
969integer_io!(read_u32_le, write_u32_le, u32, from_le_bytes, to_le_bytes);
970integer_io!(read_u64_le, write_u64_le, u64, from_le_bytes, to_le_bytes);
971integer_io!(read_u32_be, write_u32_be, u32, from_be_bytes, to_be_bytes);
972integer_io!(read_u64_be, write_u64_be, u64, from_be_bytes, to_be_bytes);
973
974#[cfg(test)]
975mod tests {
976    use super::*;
977
978    fn checkpoint(compressed_bits: u64, uncompressed: u64) -> Checkpoint {
979        Checkpoint {
980            compressed_offset_in_bits: compressed_bits,
981            uncompressed_offset_in_bytes: uncompressed,
982            kind: CheckpointKind::DeflateBlock,
983            line_offset: None,
984        }
985    }
986
987    #[test]
988    fn validate_accepts_ordered_checkpoints_with_windows() {
989        let mut index = DeflateIndex::new();
990        index.set_compressed_size(Some(4096));
991        index.set_uncompressed_size(Some(1 << 20));
992        index
993            .push(checkpoint(0, 0), StoredWindow::empty())
994            .expect("origin");
995        index
996            .push(
997                checkpoint(8 * 1000, 65536),
998                StoredWindow::from_raw(vec![7u8; WINDOW_SIZE]).expect("window"),
999            )
1000            .expect("checkpoint");
1001        assert_eq!(index.validate(), Ok(()));
1002        assert_eq!(index.checkpoint_count(), 2);
1003        assert_eq!(index.windows().len(), 1);
1004    }
1005
1006    #[test]
1007    fn validate_allows_equal_but_rejects_decreasing_uncompressed_offsets() {
1008        let mut index = DeflateIndex::new();
1009        index.set_compressed_size(Some(4096));
1010        index.set_uncompressed_size(Some(1 << 20));
1011        index
1012            .push(checkpoint(0, 100), StoredWindow::empty())
1013            .expect("first");
1014        index
1015            .push(checkpoint(8, 100), StoredWindow::empty())
1016            .expect("equal");
1017        assert_eq!(index.validate(), Ok(()));
1018        index
1019            .push(
1020                checkpoint(8, 100),
1021                StoredWindow::from_raw(vec![0u8; WINDOW_SIZE]).expect("window"),
1022            )
1023            .expect("duplicate accepted until validate");
1024        assert!(matches!(
1025            index.validate(),
1026            Err(IndexError::InvalidCheckpoint(_))
1027        ));
1028
1029        let mut decreasing = DeflateIndex::new();
1030        decreasing
1031            .push(checkpoint(0, 100), StoredWindow::empty())
1032            .expect("first");
1033        decreasing
1034            .push(checkpoint(8, 99), StoredWindow::empty())
1035            .expect("decreasing accepted until validate");
1036        assert!(matches!(
1037            decreasing.validate(),
1038            Err(IndexError::InvalidCheckpoint(_))
1039        ));
1040    }
1041
1042    #[test]
1043    fn validate_rejects_wrong_window_length() {
1044        assert_eq!(
1045            StoredWindow::from_raw(vec![1u8; 10]),
1046            Err(IndexError::InvalidWindowSize(10))
1047        );
1048    }
1049
1050    #[test]
1051    fn checkpoint_at_or_before_picks_the_last_not_after_target() {
1052        let mut index = DeflateIndex::new();
1053        index.set_compressed_size(Some(4096));
1054        index.set_uncompressed_size(Some(1 << 20));
1055        index
1056            .push(checkpoint(0, 0), StoredWindow::empty())
1057            .expect("origin");
1058        index
1059            .push(
1060                checkpoint(80, 1000),
1061                StoredWindow::from_raw(vec![1u8; WINDOW_SIZE]).expect("window"),
1062            )
1063            .expect("checkpoint");
1064        index
1065            .push(
1066                checkpoint(160, 2000),
1067                StoredWindow::from_raw(vec![2u8; WINDOW_SIZE]).expect("window"),
1068            )
1069            .expect("checkpoint");
1070
1071        assert_eq!(
1072            index
1073                .checkpoint_at_or_before(1500)
1074                .map(|point| point.uncompressed_offset_in_bytes),
1075            Some(1000)
1076        );
1077        assert_eq!(
1078            index
1079                .checkpoint_at_or_before(2000)
1080                .map(|point| point.uncompressed_offset_in_bytes),
1081            Some(2000)
1082        );
1083        assert_eq!(
1084            index
1085                .checkpoint_at_or_before(0)
1086                .map(|point| point.uncompressed_offset_in_bytes),
1087            Some(0)
1088        );
1089    }
1090
1091    #[test]
1092    fn checkpoint_at_or_before_returns_nothing_for_an_empty_index() {
1093        assert!(DeflateIndex::new().checkpoint_at_or_before(0).is_none());
1094    }
1095
1096    #[test]
1097    fn line_checkpoint_never_starts_inside_the_requested_line() {
1098        let mut index = DeflateIndex::new();
1099        index.set_total_line_count(Some(2));
1100        for (compressed_bits, uncompressed, line_offset) in
1101            [(0, 0, 0), (80, 1000, 0), (160, 2000, 1)]
1102        {
1103            let mut point = checkpoint(compressed_bits, uncompressed);
1104            point.line_offset = Some(line_offset);
1105            index
1106                .push(point, StoredWindow::empty())
1107                .expect("line checkpoint");
1108        }
1109
1110        assert_eq!(
1111            index
1112                .checkpoint_at_or_before_line(0)
1113                .map(|point| point.uncompressed_offset_in_bytes),
1114            Some(0),
1115        );
1116        assert_eq!(
1117            index
1118                .checkpoint_at_or_before_line(1)
1119                .map(|point| point.uncompressed_offset_in_bytes),
1120            Some(1000),
1121        );
1122        assert_eq!(
1123            index
1124                .checkpoint_at_or_before_line(2)
1125                .map(|point| point.uncompressed_offset_in_bytes),
1126            Some(2000),
1127        );
1128    }
1129}
rapidgzip_core/index/mod.rs

rapidgzip_core/index/
mod.rs
