rle_decode_fast/
lib.rs

1//! # rle-decode-helper
2//!
3//! **THE** fastest way to implement any kind of decoding for **R**un **L**ength **E**ncoded data in Rust.
4//!
5//! Writing a fast decoder that is also safe can be quite challenging, so this crate is here to save you the
6//! hassle of maintaining and testing your own implementation.
7//!
8//! # Usage
9//!
10//! ```rust
11//! let mut decode_buffer = vec![0, 0, 1, 1, 0, 2, 3];
12//! let lookbehind_length = 4;
13//! let output_length = 10;
14//! rle_decode_fast::rle_decode(&mut decode_buffer, lookbehind_length, output_length);
15//! assert_eq!(decode_buffer, [0, 0, 1, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0]);
16//! ```
17
18#![no_std]
19
20use core::ptr;
21use core::ops;
22extern crate alloc;
23use alloc::vec::Vec;
24
25/// Fast decoding of run length encoded data
26///
27/// Takes the last `lookbehind_length` items of the buffer and repeatedly appends them until
28/// `fill_length` items have been copied.
29///
30/// # Panics
31/// * `lookbehind_length` is 0
32/// * `lookbehind_length` >= `buffer.len()`
33/// * `fill_length + buffer.len()` would overflow
34#[inline(always)]
35pub fn rle_decode<T>(
36    buffer: &mut Vec<T>,
37    mut lookbehind_length: usize,
38    mut fill_length: usize,
39) where T: Copy {
40    if lookbehind_length == 0 {
41        lookbehind_length_fail();
42    }
43
44    let copy_fragment_start = buffer.len()
45        .checked_sub(lookbehind_length)
46        .expect("attempt to repeat fragment larger than buffer size");
47
48    // Reserve space for *all* copies
49    buffer.reserve(fill_length);
50
51    while fill_length >= lookbehind_length {{}
52        append_from_within(
53            buffer,
54            copy_fragment_start..(copy_fragment_start + lookbehind_length),
55        );
56        fill_length -= lookbehind_length;
57        lookbehind_length *= 2;
58    }
59
60    // Copy the last remaining bytes
61    append_from_within(
62        buffer,
63        copy_fragment_start..(copy_fragment_start + fill_length),
64    );
65}
66
67
68/// Copy of `vec::append_from_within()` proposed for inclusion in stdlib,
69/// see https://github.com/rust-lang/rfcs/pull/2714
70/// Heavily based on the implementation of `slice::copy_within()`,
71/// so we're pretty sure the implementation is sound
72///
73/// Note that the generic bounds were replaced by an explicit a..b range.
74/// This is so that we can compile this on older toolchains (< 1.28).
75#[inline(always)]
76fn append_from_within<T>(seif: &mut Vec<T>, src: ops::Range<usize>) where T: Copy, {
77    assert!(src.start <= src.end, "src end is before src start");
78    assert!(src.end <= seif.len(), "src is out of bounds");
79    let count = src.end - src.start;
80    seif.reserve(count);
81    let vec_len = seif.len();
82    unsafe {
83        // This is safe because reserve() above succeeded,
84        // so `seif.len() + count` did not overflow usize
85        // Derive both `src_ptr` and `dest_ptr` from the same loan
86        let ptr = seif.as_mut_ptr();
87        let src_ptr = ptr.add(src.start);
88        let dest_ptr = ptr.add(vec_len);
89        ptr::copy_nonoverlapping(src_ptr, dest_ptr, count);
90        seif.set_len(vec_len + count);
91    }
92}
93
94#[inline(never)]
95#[cold]
96fn lookbehind_length_fail() -> ! {
97    panic!("attempt to repeat fragment of size 0");
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103    use alloc::vec;
104
105    #[test]
106    fn test_basic() {
107        let mut buf = vec![1, 2, 3, 4, 5];
108        rle_decode(&mut buf, 3, 10);
109        assert_eq!(buf, &[1, 2, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3, 4, 5, 3]);
110    }
111
112    #[test]
113    fn test_zero_repeat() {
114        let mut buf = vec![1, 2, 3, 4, 5];
115        rle_decode(&mut buf, 3, 0);
116        assert_eq!(buf, &[1, 2, 3, 4, 5]);
117    }
118
119    #[test]
120    #[should_panic]
121    fn test_zero_fragment() {
122        let mut buf = vec![1, 2, 3, 4, 5];
123        rle_decode(&mut buf, 0, 10);
124    }
125
126    #[test]
127    #[should_panic]
128    fn test_zero_fragment_and_repeat() {
129        let mut buf = vec![1, 2, 3, 4, 5];
130        rle_decode(&mut buf, 0, 0);
131    }
132
133    #[test]
134    #[should_panic]
135    fn test_overflow_fragment() {
136        let mut buf = vec![1, 2, 3, 4, 5];
137        rle_decode(&mut buf, 10, 10);
138    }
139
140    #[test]
141    #[should_panic]
142    fn test_overflow_buf_size() {
143        let mut buf = vec![1, 2, 3, 4, 5];
144        rle_decode(&mut buf, 4, usize::max_value());
145    }
146}
rle_decode_fast/lib.rs

rle_decode_fast/
lib.rs
