lzfse_rust/ring/
object.rs

1use crate::match_kit;
2use crate::types::Idx;
3
4use super::ring_box::RingBox;
5use super::ring_size::RingSize;
6use super::ring_type::RingType;
7use super::ring_view::RingView;
8
9use std::marker::PhantomData;
10use std::mem;
11use std::ops::{Deref, DerefMut};
12use std::ptr;
13use std::slice;
14
15pub const OVERMATCH_LEN: usize = 5 * mem::size_of::<usize>();
16
17pub struct Ring<'a, T>(*mut u8, PhantomData<T>, PhantomData<&'a mut ()>);
18
19// Implementation notes:
20//
21// Hybrid ring buffer.
22//
23// |tttt|HHHH|...............................................|TTTT|hhhh|S|
24// <-------------------------- RING_CAPACITY ---------------------------->
25//      <----------------------- RING_SIZE ----------------------->
26//      ^ PTR *mut u8
27//
28// Tag  | Zone           | Size
29// ----------------------------------
30// HHHH | head           | RING_LIMIT
31// TTTT | tail           | RING_LIMIT
32// hhhh | head shadow    | RING_LIMIT
33// tttt | tail shadow    | RING_LIMIT
34// S    | Slack          | WIDTH
35
36impl<'a, T: RingType> Ring<'a, T> {
37    /// May overmatch `max` by  `LEN + OVERMATCH_LEN` bytes
38    #[inline(always)]
39    pub fn match_inc_coarse<const LEN: usize>(&self, idxs: (Idx, Idx), max: usize) -> usize {
40        assert!(LEN + OVERMATCH_LEN <= T::RING_LIMIT as usize);
41        debug_assert!(self.head_shadowed_len(LEN + OVERMATCH_LEN));
42        let indexes = (
43            (usize::from(idxs.0)) % T::RING_SIZE as usize,
44            (usize::from(idxs.1)) % T::RING_SIZE as usize,
45        );
46        let u_0 = unsafe { self.0.add(indexes.0 + LEN).cast::<usize>().read_unaligned() };
47        let u_1 = unsafe { self.0.add(indexes.1 + LEN).cast::<usize>().read_unaligned() };
48        let x = u_0 ^ u_1;
49        if x != 0 {
50            // Likely
51            LEN + match_kit::nclz_bytes(x) as usize
52        } else {
53            // Unlikely.
54            unsafe { self.match_inc_coarse_cont::<LEN>(indexes, max) }
55        }
56    }
57
58    unsafe fn match_inc_coarse_cont<const LEN: usize>(
59        &self,
60        mut indexes: (usize, usize),
61        max: usize,
62    ) -> usize {
63        let mut len = LEN + mem::size_of::<usize>();
64        loop {
65            for i in 0..4 {
66                let off = LEN + mem::size_of::<usize>() + i * mem::size_of::<usize>();
67                let u_0 = self.0.add(indexes.0 + off).cast::<usize>().read_unaligned();
68                let u_1 = self.0.add(indexes.1 + off).cast::<usize>().read_unaligned();
69                let x = u_0 ^ u_1;
70                if x != 0 {
71                    return len + i * mem::size_of::<usize>() + match_kit::nclz_bytes(x) as usize;
72                }
73            }
74            if len >= max {
75                break;
76            }
77            len += 4 * mem::size_of::<usize>();
78            indexes = (
79                indexes.0.wrapping_add(4 * mem::size_of::<usize>()) % T::RING_SIZE as usize,
80                indexes.1.wrapping_add(4 * mem::size_of::<usize>()) % T::RING_SIZE as usize,
81            );
82        }
83        max
84    }
85
86    /// May overmatch `max` by  `LEN + OVERMATCH_LEN` bytes
87    #[inline(always)]
88    pub fn match_dec_coarse<const LEN: usize>(&self, idxs: (Idx, Idx), max: usize) -> usize {
89        assert!(LEN + OVERMATCH_LEN <= T::RING_LIMIT as usize);
90        debug_assert!(self.head_shadowed_len(LEN + OVERMATCH_LEN));
91        let off = LEN + OVERMATCH_LEN;
92        let indexes = (
93            (usize::from(idxs.0).wrapping_sub(off)) % T::RING_SIZE as usize,
94            (usize::from(idxs.1).wrapping_sub(off)) % T::RING_SIZE as usize,
95        );
96        let off = 4 * mem::size_of::<usize>();
97        let u_0 = unsafe { self.0.add(indexes.0 + off).cast::<usize>().read_unaligned() };
98        let u_1 = unsafe { self.0.add(indexes.1 + off).cast::<usize>().read_unaligned() };
99        let x = u_0 ^ u_1;
100        if x != 0 {
101            // Likely
102            LEN + match_kit::nctz_bytes(x) as usize
103        } else {
104            // Unlikely.
105            unsafe { self.match_dec_cont::<LEN>(indexes, max) }
106        }
107    }
108
109    unsafe fn match_dec_cont<const LEN: usize>(
110        &self,
111        mut indexes: (usize, usize),
112        max: usize,
113    ) -> usize {
114        let mut len = LEN + mem::size_of::<usize>();
115        loop {
116            for i in 0..4 {
117                let off = (3 - i) * mem::size_of::<usize>();
118                let u_0 = self.0.add(indexes.0 + off).cast::<usize>().read_unaligned();
119                let u_1 = self.0.add(indexes.1 + off).cast::<usize>().read_unaligned();
120                let x = u_0 ^ u_1;
121                if x != 0 {
122                    return len + i * mem::size_of::<usize>() + match_kit::nctz_bytes(x) as usize;
123                }
124            }
125            if len >= max {
126                break;
127            }
128            len += 4 * mem::size_of::<usize>();
129            indexes = (
130                indexes.0.wrapping_sub(4 * mem::size_of::<usize>()) % T::RING_SIZE as usize,
131                indexes.1.wrapping_sub(4 * mem::size_of::<usize>()) % T::RING_SIZE as usize,
132            );
133        }
134        max
135    }
136
137    pub fn head_shadowed(&self) -> bool {
138        self.head_shadowed_len(T::RING_LIMIT as usize)
139    }
140
141    #[inline(always)]
142    pub fn head_shadowed_len(&self, len: usize) -> bool {
143        unsafe { zone_eq::<T>(self.0, len) }
144    }
145
146    #[inline(always)]
147    pub fn head_copy_out(&mut self) {
148        self.head_copy_out_len(T::RING_LIMIT as usize);
149    }
150
151    /// Copy head -> head shadow
152    #[inline(always)]
153    pub fn head_copy_out_len(&mut self, len: usize) {
154        unsafe { zone_copy_1::<T>(self.0, len) };
155    }
156
157    #[inline(always)]
158    #[allow(dead_code)]
159    pub fn head_copy_in(&mut self) {
160        self.head_copy_in_len(T::RING_LIMIT as usize);
161    }
162
163    /// Copy head shadow -> head
164    #[inline(always)]
165    pub fn head_copy_in_len(&mut self, len: usize) {
166        unsafe { zone_copy_2::<T>(self.0, len) };
167    }
168
169    #[allow(dead_code)]
170    pub fn tail_shadowed(&self) -> bool {
171        self.tail_shadowed_len(T::RING_LIMIT as usize)
172    }
173
174    #[allow(dead_code)]
175    #[inline(always)]
176    pub fn tail_shadowed_len(&self, len: usize) -> bool {
177        unsafe { zone_eq::<T>(self.0.sub(T::RING_LIMIT as usize), len) }
178    }
179
180    #[inline(always)]
181    pub fn tail_copy_out(&mut self) {
182        self.tail_copy_out_len(T::RING_LIMIT as usize);
183    }
184
185    /// Copy tail -> tail shadow
186    #[inline(always)]
187    pub fn tail_copy_out_len(&mut self, len: usize) {
188        unsafe { zone_copy_2::<T>(self.0.sub(T::RING_LIMIT as usize), len) };
189    }
190
191    #[allow(dead_code)]
192    #[inline(always)]
193    pub fn tail_copy_in(&mut self) {
194        self.tail_copy_in_len(T::RING_LIMIT as usize);
195    }
196
197    /// Copy tail shadow -> tail
198    #[allow(dead_code)]
199    #[inline(always)]
200    pub fn tail_copy_in_len(&mut self, len: usize) {
201        assert!(len <= T::RING_LIMIT as usize);
202        unsafe { zone_copy_1::<T>(self.0.sub(T::RING_LIMIT as usize), len) };
203    }
204
205    #[inline(always)]
206    pub fn view(&self, head: Idx, tail: Idx) -> RingView<T> {
207        RingView::new(self, head, tail)
208    }
209}
210
211impl<'a, T: RingSize> Ring<'a, T> {
212    #[inline(always)]
213    pub fn get_u32(&self, idx: Idx) -> u32 {
214        let index = idx % T::RING_SIZE;
215        unsafe { self.0.add(index as usize).cast::<u32>().read_unaligned() }
216    }
217
218    #[inline(always)]
219    pub unsafe fn set_quad_index(&mut self, index: usize, u: u32) {
220        debug_assert!(index < T::RING_SIZE as usize);
221        self.0.add(index).cast::<u32>().write_unaligned(u);
222    }
223}
224
225impl<'a, T: RingSize> Deref for Ring<'a, T> {
226    type Target = [u8];
227
228    #[inline(always)]
229    fn deref(&self) -> &Self::Target {
230        unsafe { slice::from_raw_parts(self.0, T::RING_SIZE as usize) }
231    }
232}
233
234impl<'a, T: RingSize> DerefMut for Ring<'a, T> {
235    #[inline(always)]
236    fn deref_mut(&mut self) -> &mut Self::Target {
237        unsafe { slice::from_raw_parts_mut(self.0, T::RING_SIZE as usize) }
238    }
239}
240
241impl<'a, T: RingType> From<&'a mut RingBox<T>> for Ring<'a, T> {
242    #[inline(always)]
243    fn from(ring_box: &'a mut RingBox<T>) -> Self {
244        Self(
245            unsafe { ring_box.0.as_mut_ptr().add(T::RING_LIMIT as usize) },
246            PhantomData::default(),
247            PhantomData::default(),
248        )
249    }
250}
251
252#[inline(always)]
253unsafe fn zone_copy_1<T: RingType>(ptr: *mut u8, len: usize) {
254    assert!(len <= T::RING_LIMIT as usize);
255    ptr::copy_nonoverlapping(ptr, ptr.add(T::RING_SIZE as usize), len);
256}
257
258#[inline(always)]
259unsafe fn zone_copy_2<T: RingType>(ptr: *mut u8, len: usize) {
260    ptr::copy_nonoverlapping(ptr.add(T::RING_SIZE as usize), ptr, len);
261}
262
263#[inline(always)]
264unsafe fn zone_eq<T: RingType>(ptr: *mut u8, len: usize) -> bool {
265    assert!(len <= T::RING_LIMIT as usize);
266    let u = slice::from_raw_parts(ptr.add(T::RING_SIZE as usize), len);
267    let v = slice::from_raw_parts(ptr, len);
268    u == v
269}
270
271#[cfg(test)]
272mod tests {
273    use super::*;
274
275    #[derive(Copy, Clone, Debug)]
276    struct T;
277
278    unsafe impl RingSize for T {
279        const RING_SIZE: u32 = 0x0100;
280    }
281
282    unsafe impl RingType for T {
283        const RING_LIMIT: u32 = 0x0040;
284    }
285
286    // Cycling match_index, match_distance and match_len combinations.
287    #[test]
288    fn match_inc_1() {
289        let mut ring_box = RingBox::<T>::default();
290        let mut ring = Ring::from(&mut ring_box);
291        for match_index in 0x0000..0x0100 {
292            for match_distance in 0x0001..0x0100 {
293                ring.fill(0xFF);
294                for n in 0..match_distance {
295                    ring[(match_index + n) % 0x0100] = (n + 1) as u8;
296                }
297                let index = match_index + match_distance;
298                for match_len in 0..0x0100 - match_distance {
299                    ring.head_copy_out();
300                    ring.tail_copy_out();
301                    let n = ring.match_inc_coarse::<0>(
302                        (Idx::new(index as u32), Idx::new(match_index as u32)),
303                        0x100,
304                    );
305                    assert_eq!(n, match_len);
306                    ring[(index + match_len) % 0x0100] = (match_len % match_distance + 1) as u8;
307                }
308            }
309        }
310    }
311
312    // Cycling match_index, match_distance combinations with overmatch limit checking.
313    #[test]
314    fn match_inc_2() {
315        let mut ring_box = RingBox::<T>::default();
316        let mut ring = Ring::from(&mut ring_box);
317        for match_index in 0x0000..0x0100 {
318            for match_distance in 0x0001..0x0100 {
319                ring.fill(0xFF);
320                for n in 0..match_distance {
321                    ring[(match_index + n) % 0x0100] = (n + 1) as u8;
322                }
323                let index = match_index + match_distance;
324                for match_len in 0..0x0100 - match_distance {
325                    ring[(index + match_len) % 0x0100] = (match_len % match_distance + 1) as u8;
326                }
327                ring.head_copy_out();
328                ring.tail_copy_out();
329                let match_len = 0x0100 - match_distance;
330                let n = ring.match_inc_coarse::<0>(
331                    (Idx::new(index as u32), Idx::new(match_index as u32)),
332                    0,
333                );
334                assert!(n <= match_len);
335                assert!(n <= OVERMATCH_LEN);
336                let n = ring.match_inc_coarse::<4>(
337                    (Idx::new(index as u32), Idx::new(match_index as u32)),
338                    0,
339                );
340                assert!(n <= match_len + 4);
341                assert!(n <= 4 + OVERMATCH_LEN);
342            }
343        }
344    }
345
346    // Cycling match_index, match_distance and match_len combinations.
347    #[test]
348    fn match_dec_1() {
349        let mut ring_box = RingBox::<T>::default();
350        let mut ring = Ring::from(&mut ring_box);
351        for match_index in 0x0000..0x0100usize {
352            for match_distance in 0x0001..0x0100 {
353                ring.fill(0xFF);
354                for n in 1..=match_distance {
355                    ring[(match_index.wrapping_sub(n)) % 0x0100] = n as u8;
356                }
357                let index = match_index.wrapping_sub(match_distance);
358                for match_len in 0..0x0100 - match_distance {
359                    ring.head_copy_out();
360                    ring.tail_copy_out();
361                    let n = ring.match_dec_coarse::<0>(
362                        (Idx::new(index as u32), Idx::new(match_index as u32)),
363                        0x100,
364                    );
365                    assert_eq!(n, match_len);
366                    ring[index.wrapping_sub(match_len + 1) % 0x0100] =
367                        (match_len % match_distance + 1) as u8;
368                }
369            }
370        }
371    }
372
373    // Cycling match_index, match_distance combinations with overmatch limit checking.
374    #[test]
375    fn match_dec_2() {
376        let mut ring_box = RingBox::<T>::default();
377        let mut ring = Ring::from(&mut ring_box);
378        for match_index in 0x0000..0x0100usize {
379            for match_distance in 0x0001..0x0100 {
380                ring.fill(0xFF);
381                for n in 1..=match_distance {
382                    ring[(match_index.wrapping_sub(n)) % 0x0100] = n as u8;
383                }
384                let index = match_index.wrapping_sub(match_distance);
385                for match_len in 0..0x0100 - match_distance {
386                    ring[index.wrapping_sub(match_len + 1) % 0x0100] =
387                        (match_len % match_distance + 1) as u8;
388                }
389                ring.head_copy_out();
390                ring.tail_copy_out();
391                let match_len = 0x0100 - match_distance;
392                let n = ring.match_dec_coarse::<0>(
393                    (Idx::new(index as u32), Idx::new(match_index as u32)),
394                    0,
395                );
396                assert!(n <= match_len);
397                assert!(n <= OVERMATCH_LEN);
398                let n = ring.match_dec_coarse::<4>(
399                    (Idx::new(index as u32), Idx::new(match_index as u32)),
400                    0,
401                );
402                assert!(n <= match_len + 4);
403                assert!(n <= 4 + OVERMATCH_LEN);
404            }
405        }
406    }
407}
lzfse_rust/ring/object.rs

lzfse_rust/ring/
object.rs
