20296468854

Committed 17 Dec 2025 08:28AM UTC coverage: 91.019% (-0.2%) from 91.192%

Build # 20296468854

Build Type

push

github

Committed by

actioninja

Commit Message

fix: Finally fix the stupid broken CI

Run Details

1581 of 1737 relevant lines covered (91.02%)

348583.09 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,746,976✔
16	let src_int = usize::from_ne_bytes(src);	4,746,976✔
17	let cmp_int = usize::from_ne_bytes(cmp);	4,746,976✔
18
19	let xor = src_int ^ cmp_int;	4,746,976✔
20
21	if xor == 0 {	4,746,976✔
22	None	20,098✔
23	} else {
24	Some((xor.to_le().trailing_zeros() / 8) as usize)	4,726,878✔
25	}
26	}	4,746,976✔
27
28	#[inline(always)]
29	fn match_length_blocks(src: &[u8], cmp: &[u8]) -> Option<usize> {	18,351✔
30	// when using fixed length slices this gets optimized to a (fused) simd load and compare
31	if src == cmp {	18,351✔
32	return None;	×
33	}	18,351✔
34
35	let src_chunks = src.chunks_exact(USIZE_BYTES);	18,351✔
36	let cmp_chunks = cmp.chunks_exact(USIZE_BYTES);	18,351✔
37
38	src_chunks	18,351✔
39	.zip(cmp_chunks)	18,351✔
40	.enumerate()	18,351✔
41	.find_map(\|(i, (src, cmp))\| {	18,430✔
42	compare_block(src.try_into().unwrap(), cmp.try_into().unwrap())	18,430✔
43	.map(\|found\| i * USIZE_BYTES + found)	18,430✔
44	})	18,430✔
45	}	18,351✔
46
47	#[inline]
48	fn match_length_simd(buffer: &[u8], source: usize, matched_pos: usize, max_len: usize) -> usize {	4,851,588✔
49	const LANES: usize = 16;
50
51	if source + USIZE_BYTES < buffer.len() {	4,851,588✔
52	if let Some(found) = compare_block(	4,728,546✔
53	buffer[source..source + USIZE_BYTES].try_into().unwrap(),	4,728,546✔
54	buffer[matched_pos..matched_pos + USIZE_BYTES]	4,728,546✔
55	.try_into()	4,728,546✔
56	.unwrap(),	4,728,546✔
57	) {	4,728,546✔
58	return min(found, max_len);	4,708,527✔
59	}	20,019✔
60	if max_len <= USIZE_BYTES {	20,019✔
61	return max_len;	864✔
62	}	19,155✔
63
64	let source_slice = &buffer[source + USIZE_BYTES..min(source + max_len, buffer.len())];	19,155✔
65	let match_slice = &buffer[matched_pos + USIZE_BYTES..];	19,155✔
66
67	let source_chunks = source_slice.chunks_exact(LANES);	19,155✔
68	let match_chunks = match_slice.chunks_exact(LANES);	19,155✔
69	let source_chunks_remainder = source_chunks.remainder();	19,155✔
70
71	let mut num = USIZE_BYTES;	19,155✔
72	for (src, cmp) in source_chunks.zip(match_chunks) {	19,155✔
73	if let Some(found) = match_length_blocks(src, cmp) {	18,351✔
74	return num + found;	18,351✔
75	}	×
76	num += LANES;	×
77	}
78
79	source_chunks_remainder	804✔
80	.iter()	804✔
81	.zip(match_slice[num - USIZE_BYTES..].iter())	804✔
82	.take_while(\|(a, b)\| a == b)	1,464✔
83	.count()	804✔
84	+ num	804✔
85	} else {
86	let source_slice = &buffer[source..min(source + max_len, buffer.len())];	123,042✔
87	let match_slice = &buffer[matched_pos..];	123,042✔
88
89	source_slice	123,042✔
90	.iter()	123,042✔
91	.zip(match_slice.iter())	123,042✔
92	.take_while(\|(a, b)\| a == b)	195,996✔
93	.count()	123,042✔
94	}
95	}	4,851,588✔
96
97	/// find the length of common bytes between two positions in a buffer
98	#[inline]
99	pub fn match_length(	4,851,588✔
100	buffer: &[u8],	4,851,588✔
101	source: usize,	4,851,588✔
102	matched_pos: usize,	4,851,588✔
103	max_len: usize,	4,851,588✔
104	skip: usize,	4,851,588✔
105	) -> usize {	4,851,588✔
106	debug_assert!(matched_pos < source);	4,851,588✔
107
108	match_length_simd(buffer, source + skip, matched_pos + skip, max_len - skip) + skip	4,851,588✔
109	}	4,851,588✔
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 {	198,320✔
113	debug_assert!(matched_pos < source);	198,320✔
114
115	let source_idx = source + skip;	198,320✔
116
117	if source_idx >= buffer.len() {	198,320✔
118	return false;	×
119	}	198,320✔
120
121	let match_idx = matched_pos + skip;	198,320✔
122
123	buffer[source_idx] == buffer[match_idx]	198,320✔
124	}	198,320✔
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(	176,536✔
133	buffer: &[u8],	176,536✔
134	source: usize,	176,536✔
135	bad_match_pos: usize,	176,536✔
136	matched_pos: usize,	176,536✔
137	except_match_length: usize,	176,536✔
138	skip: usize,	176,536✔
139	) -> u16 {	176,536✔
140	let match_len = match_length(buffer, source, matched_pos, except_match_length + 1, skip);	176,536✔
141	(if match_len == except_match_length {	176,536✔
142	except_match_length	85,731✔
143	+ usize::from(!byte_offset_matches(	85,731✔
144	buffer,	85,731✔
145	bad_match_pos,	85,731✔
146	matched_pos,	85,731✔
147	except_match_length,	85,731✔
148	))	85,731✔
149	} else {
150	min(match_len, except_match_length)	90,805✔
151	}) as u16
152	}	176,536✔
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(	121,702✔
159	buffer: &[u8],	121,702✔
160	source: usize,	121,702✔
161	matched_pos: usize,	121,702✔
162	or_match_pos: usize,	121,702✔
163	or_match_length: usize,	121,702✔
164	skip: usize,	121,702✔
165	) -> u16 {	121,702✔
166	let match_len = match_length(buffer, source, matched_pos, LONG_LENGTH_MAX as usize, skip);	121,702✔
167	(if match_len == or_match_length {	121,702✔
168	match_len	14,493✔
169	+ usize::from(!byte_offset_matches(	14,493✔
170	buffer,	14,493✔
171	or_match_pos,	14,493✔
172	matched_pos,	14,493✔
173	match_len,	14,493✔
174	))	14,493✔
175	} else {
176	match_len	107,209✔
177	}) as u16
178	}	121,702✔

actioninja / refpack-rs / 20296468854

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