24216429358

Committed 09 Apr 2026 10:28PM UTC coverage: 93.896% (+2.7%) from 91.192%

Build # 24216429358

Build Type

push

github

Committed by

web-flow

Commit Message

fix: header compressed size includes size of header itself (#20)

Coverage Stats

2 of 2 new or added lines in 1 file covered. (100.0%)

3 existing lines in 1 file now uncovered.

1569 of 1671 relevant lines covered (93.9%)

367944.29 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

96.58

/src/data/compression/match_length.rs

////////////////////////////////////////////////////////////////////////////////
// This Source Code Form is subject to the terms of the Mozilla Public         /
// License, v. 2.0. If a copy of the MPL was not distributed with this         /
// file, You can obtain one at https://mozilla.org/MPL/2.0/.                   /
//                                                                             /
////////////////////////////////////////////////////////////////////////////////

use std::cmp::min;

use crate::data::control::LONG_LENGTH_MAX;

const USIZE_BYTES: usize = size_of::<usize>();

#[inline(always)]
fn compare_block(src: [u8; USIZE_BYTES], cmp: [u8; USIZE_BYTES]) -> Option<usize> {
    let src_int = usize::from_ne_bytes(src);
    let cmp_int = usize::from_ne_bytes(cmp);

    let xor = src_int ^ cmp_int;

    if xor == 0 {
        None
    } else {
        Some((xor.to_le().trailing_zeros() / 8) as usize)
    }
}

#[inline(always)]
fn match_length_blocks(src: &[u8], cmp: &[u8]) -> Option<usize> {
    // when using fixed length slices this gets optimized to a (fused) simd load and compare
    if src == cmp {
        return None;
    }

    let src_chunks = src.chunks_exact(USIZE_BYTES);
    let cmp_chunks = cmp.chunks_exact(USIZE_BYTES);

    src_chunks
        .zip(cmp_chunks)
        .enumerate()
        .find_map(|(i, (src, cmp))| {
            compare_block(src.try_into().unwrap(), cmp.try_into().unwrap())
                .map(|found| i * USIZE_BYTES + found)
        })
}

#[inline]
fn match_length_simd(buffer: &[u8], source: usize, matched_pos: usize, max_len: usize) -> usize {
    const LANES: usize = 16;

    if source + USIZE_BYTES < buffer.len() {
        if let Some(found) = compare_block(
            buffer[source..source + USIZE_BYTES].try_into().unwrap(),
            buffer[matched_pos..matched_pos + USIZE_BYTES]
                .try_into()
                .unwrap(),
        ) {
            return min(found, max_len);
        }
        if max_len <= USIZE_BYTES {
            return max_len;
        }

        let source_slice = &buffer[source + USIZE_BYTES..min(source + max_len, buffer.len())];
        let match_slice = &buffer[matched_pos + USIZE_BYTES..];

        let source_chunks = source_slice.chunks_exact(LANES);
        let match_chunks = match_slice.chunks_exact(LANES);
        let source_chunks_remainder = source_chunks.remainder();

        let mut num = USIZE_BYTES;
        for (src, cmp) in source_chunks.zip(match_chunks) {
            if let Some(found) = match_length_blocks(src, cmp) {
                return num + found;
            }
            num += LANES;
        }

        source_chunks_remainder
            .iter()
            .zip(match_slice[num - USIZE_BYTES..].iter())
            .take_while(|(a, b)| a == b)
            .count()
            + num
    } else {
        let source_slice = &buffer[source..min(source + max_len, buffer.len())];
        let match_slice = &buffer[matched_pos..];

        source_slice
            .iter()
            .zip(match_slice.iter())
            .take_while(|(a, b)| a == b)
            .count()
    }
}

/// find the length of common bytes between two positions in a buffer
#[inline]
pub fn match_length(
    buffer: &[u8],
    source: usize,
    matched_pos: usize,
    max_len: usize,
    skip: usize,
) -> usize {
    debug_assert!(matched_pos < source);

    match_length_simd(buffer, source + skip, matched_pos + skip, max_len - skip) + skip
}

/// does the byte at the two positions with the specified offset (`skip`) match?
pub fn byte_offset_matches(buffer: &[u8], source: usize, matched_pos: usize, skip: usize) -> bool {
    debug_assert!(matched_pos < source);

    let source_idx = source + skip;

    if source_idx >= buffer.len() {
        return false;
    }

    let match_idx = matched_pos + skip;

    buffer[source_idx] == buffer[match_idx]
}

/// check for any sequence of bytes that matches exactly `except_match_length` bytes with the source position
///
/// For any position that fulfils this condition the function will return `except_match_length` + 1.
/// Any other position will return the match length of that position up to `except_match_length` bytes.
///
/// `skip` can be used to specify the number of bytes that is already known to be matching
pub fn match_length_except(
    buffer: &[u8],
    source: usize,
    bad_match_pos: usize,
    matched_pos: usize,
    except_match_length: usize,
    skip: usize,
) -> u16 {
    let match_len = match_length(buffer, source, matched_pos, except_match_length + 1, skip);
    (if match_len == except_match_length {
        except_match_length
            + usize::from(!byte_offset_matches(
                buffer,
                bad_match_pos,
                matched_pos,
                except_match_length,
            ))
    } else {
        min(match_len, except_match_length)
    }) as u16
}

/// check for any sequence of bytes that matches with `matched_pos`
/// OR matches `or_match_pos` exactly `or_match_length` bytes
///
/// `skip` can be used to specify the number of bytes that is already known to be matching
pub fn match_length_or(
    buffer: &[u8],
    source: usize,
    matched_pos: usize,
    or_match_pos: usize,
    or_match_length: usize,
    skip: usize,
) -> u16 {
    let match_len = match_length(buffer, source, matched_pos, LONG_LENGTH_MAX as usize, skip);
    (if match_len == or_match_length {
        match_len
            + usize::from(!byte_offset_matches(
                buffer,
                or_match_pos,
                matched_pos,
                match_len,
            ))
    } else {
        match_len
    }) as u16
}

1	////////////////////////////////////////////////////////////////////////////////
2	// This Source Code Form is subject to the terms of the Mozilla Public /
3	// License, v. 2.0. If a copy of the MPL was not distributed with this /
4	// file, You can obtain one at https://mozilla.org/MPL/2.0/. /
5	// /
6	////////////////////////////////////////////////////////////////////////////////
7
8	use std::cmp::min;
9
10	use crate::data::control::LONG_LENGTH_MAX;
11
12	const USIZE_BYTES: usize = size_of::<usize>();
13
14	#[inline(always)]
15	fn compare_block(src: [u8; USIZE_BYTES], cmp: [u8; USIZE_BYTES]) -> Option<usize> {	4,843,647✔
16	let src_int = usize::from_ne_bytes(src);	4,843,647✔
17	let cmp_int = usize::from_ne_bytes(cmp);	4,843,647✔
18
19	let xor = src_int ^ cmp_int;	4,843,647✔
20
21	if xor == 0 {	4,843,647✔
22	None	19,793✔
23	} else {
24	Some((xor.to_le().trailing_zeros() / 8) as usize)	4,823,854✔
25	}
26	}	4,843,647✔
27
28	#[inline(always)]
29	fn match_length_blocks(src: &[u8], cmp: &[u8]) -> Option<usize> {	18,110✔
30	// when using fixed length slices this gets optimized to a (fused) simd load and compare
31	if src == cmp {	18,110✔
UNCOV 32	return None;	×
33	}	18,110✔
34
35	let src_chunks = src.chunks_exact(USIZE_BYTES);	18,110✔
36	let cmp_chunks = cmp.chunks_exact(USIZE_BYTES);	18,110✔
37
38	src_chunks	18,110✔
39	.zip(cmp_chunks)	18,110✔
40	.enumerate()	18,110✔
41	.find_map(\|(i, (src, cmp))\| {	18,178✔
42	compare_block(src.try_into().unwrap(), cmp.try_into().unwrap())	18,178✔
43	.map(\|found\| i * USIZE_BYTES + found)	18,178✔
44	})	18,178✔
45	}	18,110✔
46
47	#[inline]
48	fn match_length_simd(buffer: &[u8], source: usize, matched_pos: usize, max_len: usize) -> usize {	4,952,134✔
49	const LANES: usize = 16;
50
51	if source + USIZE_BYTES < buffer.len() {	4,952,134✔
52	if let Some(found) = compare_block(	4,825,469✔
53	buffer[source..source + USIZE_BYTES].try_into().unwrap(),	4,825,469✔
54	buffer[matched_pos..matched_pos + USIZE_BYTES]	4,825,469✔
55	.try_into()	4,825,469✔
56	.unwrap(),	4,825,469✔
57	) {	4,825,469✔
58	return min(found, max_len);	4,805,744✔
59	}	19,725✔
60	if max_len <= USIZE_BYTES {	19,725✔
61	return max_len;	785✔
62	}	18,940✔
63
64	let source_slice = &buffer[source + USIZE_BYTES..min(source + max_len, buffer.len())];	18,940✔
65	let match_slice = &buffer[matched_pos + USIZE_BYTES..];	18,940✔
66
67	let source_chunks = source_slice.chunks_exact(LANES);	18,940✔
68	let match_chunks = match_slice.chunks_exact(LANES);	18,940✔
69	let source_chunks_remainder = source_chunks.remainder();	18,940✔
70
71	let mut num = USIZE_BYTES;	18,940✔
72	for (src, cmp) in source_chunks.zip(match_chunks) {	18,940✔
73	if let Some(found) = match_length_blocks(src, cmp) {	18,110✔
74	return num + found;	18,110✔
UNCOV 75	}	×
UNCOV 76	num += LANES;	×
77	}
78
79	source_chunks_remainder	830✔
80	.iter()	830✔
81	.zip(match_slice[num - USIZE_BYTES..].iter())	830✔
82	.take_while(\|(a, b)\| a == b)	1,616✔
83	.count()	830✔
84	+ num	830✔
85	} else {
86	let source_slice = &buffer[source..min(source + max_len, buffer.len())];	126,665✔
87	let match_slice = &buffer[matched_pos..];	126,665✔
88
89	source_slice	126,665✔
90	.iter()	126,665✔
91	.zip(match_slice.iter())	126,665✔
92	.take_while(\|(a, b)\| a == b)	201,131✔
93	.count()	126,665✔
94	}
95	}	4,952,134✔
96
97	/// find the length of common bytes between two positions in a buffer
98	#[inline]
99	pub fn match_length(	4,952,134✔
100	buffer: &[u8],	4,952,134✔
101	source: usize,	4,952,134✔
102	matched_pos: usize,	4,952,134✔
103	max_len: usize,	4,952,134✔
104	skip: usize,	4,952,134✔
105	) -> usize {	4,952,134✔
106	debug_assert!(matched_pos < source);	4,952,134✔
107
108	match_length_simd(buffer, source + skip, matched_pos + skip, max_len - skip) + skip	4,952,134✔
109	}	4,952,134✔
110
111	/// does the byte at the two positions with the specified offset (`skip`) match?
112	pub fn byte_offset_matches(buffer: &[u8], source: usize, matched_pos: usize, skip: usize) -> bool {	199,864✔
113	debug_assert!(matched_pos < source);	199,864✔
114
115	let source_idx = source + skip;	199,864✔
116
117	if source_idx >= buffer.len() {	199,864✔
118	return false;	×
119	}	199,864✔
120
121	let match_idx = matched_pos + skip;	199,864✔
122
123	buffer[source_idx] == buffer[match_idx]	199,864✔
124	}	199,864✔
125
126	/// check for any sequence of bytes that matches exactly `except_match_length` bytes with the source position
127	///
128	/// For any position that fulfils this condition the function will return `except_match_length` + 1.
129	/// Any other position will return the match length of that position up to `except_match_length` bytes.
130	///
131	/// `skip` can be used to specify the number of bytes that is already known to be matching
132	pub fn match_length_except(	177,533✔
133	buffer: &[u8],	177,533✔
134	source: usize,	177,533✔
135	bad_match_pos: usize,	177,533✔
136	matched_pos: usize,	177,533✔
137	except_match_length: usize,	177,533✔
138	skip: usize,	177,533✔
139	) -> u16 {	177,533✔
140	let match_len = match_length(buffer, source, matched_pos, except_match_length + 1, skip);	177,533✔
141	(if match_len == except_match_length {	177,533✔
142	except_match_length	86,337✔
143	+ usize::from(!byte_offset_matches(	86,337✔
144	buffer,	86,337✔
145	bad_match_pos,	86,337✔
146	matched_pos,	86,337✔
147	except_match_length,	86,337✔
148	))	86,337✔
149	} else {
150	min(match_len, except_match_length)	91,196✔
151	}) as u16
152	}	177,533✔
153
154	/// check for any sequence of bytes that matches with `matched_pos`
155	/// OR matches `or_match_pos` exactly `or_match_length` bytes
156	///
157	/// `skip` can be used to specify the number of bytes that is already known to be matching
158	pub fn match_length_or(	122,645✔
159	buffer: &[u8],	122,645✔
160	source: usize,	122,645✔
161	matched_pos: usize,	122,645✔
162	or_match_pos: usize,	122,645✔
163	or_match_length: usize,	122,645✔
164	skip: usize,	122,645✔
165	) -> u16 {	122,645✔
166	let match_len = match_length(buffer, source, matched_pos, LONG_LENGTH_MAX as usize, skip);	122,645✔
167	(if match_len == or_match_length {	122,645✔
168	match_len	14,623✔
169	+ usize::from(!byte_offset_matches(	14,623✔
170	buffer,	14,623✔
171	or_match_pos,	14,623✔
172	matched_pos,	14,623✔
173	match_len,	14,623✔
174	))	14,623✔
175	} else {
176	match_len	108,022✔
177	}) as u16
178	}	122,645✔

actioninja / refpack-rs / 24216429358

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous