rustfs_erasure_codec/core/leopard_gf8/
mod.rs

1extern crate alloc;
2
3use alloc::boxed::Box;
4use alloc::vec::Vec;
5use spin::Once;
6
7use crate::errors::Error;
8#[cfg(feature = "std")]
9use std::sync::atomic::AtomicUsize;
10#[cfg(feature = "std")]
11use std::sync::atomic::Ordering;
12
13pub(crate) mod decode;
14mod driver;
15mod encode;
16mod ops;
17mod tables;
18#[cfg(test)]
19mod tests;
20mod work;
21
22const BITWIDTH8: usize = 8;
23const ORDER8: usize = 1 << BITWIDTH8;
24const MODULUS8: usize = ORDER8 - 1;
25const POLYNOMIAL8: usize = 0x11D;
26pub(crate) const WORK_SIZE8: usize = 32 << 10;
27const WORK_SIZE8_HIGH_FANOUT: usize = 128 << 10;
28
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub(crate) struct Mul8Lut {
31    pub(super) value: [u8; 256],
32    /// Pre-split low nibble table: `low[i] = value[i]` for i in 0..16.
33    /// Used by SIMD nibble-lookup to avoid per-call table construction.
34    pub(super) low: [u8; 16],
35    /// Pre-split high nibble table: `high[i] = value[i * 16]` for i in 0..16.
36    /// Used by SIMD nibble-lookup to avoid per-call table construction.
37    pub(super) high: [u8; 16],
38}
39
40#[derive(Debug)]
41pub(crate) struct LeopardGf8Tables {
42    pub(crate) fft_skew: Box<[u8; MODULUS8]>,
43    pub(crate) log_walsh: Box<[u8; ORDER8]>,
44    pub(crate) log_lut: Box<[u8; ORDER8]>,
45    pub(crate) exp_lut: Box<[u8; ORDER8]>,
46    pub(crate) mul_luts: Box<[Mul8Lut; ORDER8]>,
47}
48
49#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub(crate) struct LeopardGf8EncodeDriver {
51    pub(crate) shard_size: usize,
52    pub(crate) m: usize,
53    pub(crate) mtrunc: usize,
54    pub(crate) last_count: usize,
55    pub(crate) chunk_size: usize,
56    pub(crate) work_slices: usize,
57    pub(crate) skew_offset: usize,
58}
59
60#[derive(Debug, Clone, Copy)]
61struct Stage4Block {
62    r: usize,
63    dist: usize,
64    log_m01: u8,
65    log_m23: u8,
66    log_m02: u8,
67}
68
69#[derive(Debug, Clone, Copy)]
70struct Stage2Block {
71    r: usize,
72    dist: usize,
73    log_m: u8,
74}
75
76#[derive(Debug, Clone)]
77struct FftDit8Plan {
78    mtrunc: usize,
79    stage4_blocks: Vec<Stage4Block>,
80    final_stage: Vec<Stage2Block>,
81}
82
83#[derive(Debug, Clone)]
84struct IfftDit8Plan {
85    mtrunc: usize,
86    m: usize,
87    initial_blocks: Vec<Stage4Block>,
88    later_blocks: Vec<Stage4Block>,
89    clear_start: usize,
90    final_stage: Option<Stage2Block>,
91}
92
93#[derive(Debug, Clone, Copy, PartialEq, Eq)]
94#[allow(clippy::enum_variant_names)]
95enum IfftProfilePhase {
96    FirstGroup,
97    LaterGroup,
98    RemainderGroup,
99}
100
101#[cfg(feature = "std")]
102#[derive(Debug, Default)]
103pub(crate) struct LeopardGf8ProfileMetrics {
104    encode_calls: AtomicUsize,
105    encode_chunks: AtomicUsize,
106    encode_full_groups: AtomicUsize,
107    encode_remainder_groups: AtomicUsize,
108    encode_later_group_calls: AtomicUsize,
109    fft_stage_calls: AtomicUsize,
110    ifft_stage_calls: AtomicUsize,
111    first_group_ifft_calls: AtomicUsize,
112    later_group_ifft_calls: AtomicUsize,
113    remainder_group_ifft_calls: AtomicUsize,
114    first_group_input_copy_bytes: AtomicUsize,
115    later_group_input_copy_bytes: AtomicUsize,
116    remainder_group_input_copy_bytes: AtomicUsize,
117    first_group_zero_fill_bytes: AtomicUsize,
118    later_group_zero_fill_bytes: AtomicUsize,
119    remainder_group_zero_fill_bytes: AtomicUsize,
120    later_group_xor_bytes: AtomicUsize,
121    remainder_group_xor_bytes: AtomicUsize,
122    output_writeback_calls: AtomicUsize,
123    input_copy_bytes: AtomicUsize,
124    zero_fill_bytes: AtomicUsize,
125    xor_bytes: AtomicUsize,
126    output_writeback_bytes: AtomicUsize,
127}
128
129#[cfg(feature = "std")]
130impl LeopardGf8ProfileMetrics {
131    fn add_ifft_calls(&self, phase: IfftProfilePhase) {
132        self.ifft_stage_calls.fetch_add(1, Ordering::Relaxed);
133        match phase {
134            IfftProfilePhase::FirstGroup => &self.first_group_ifft_calls,
135            IfftProfilePhase::LaterGroup => &self.later_group_ifft_calls,
136            IfftProfilePhase::RemainderGroup => &self.remainder_group_ifft_calls,
137        }
138        .fetch_add(1, Ordering::Relaxed);
139    }
140
141    fn add_input_copy_bytes(&self, phase: IfftProfilePhase, bytes: usize) {
142        self.input_copy_bytes.fetch_add(bytes, Ordering::Relaxed);
143        match phase {
144            IfftProfilePhase::FirstGroup => &self.first_group_input_copy_bytes,
145            IfftProfilePhase::LaterGroup => &self.later_group_input_copy_bytes,
146            IfftProfilePhase::RemainderGroup => &self.remainder_group_input_copy_bytes,
147        }
148        .fetch_add(bytes, Ordering::Relaxed);
149    }
150
151    fn add_zero_fill_bytes(&self, phase: IfftProfilePhase, bytes: usize) {
152        self.zero_fill_bytes.fetch_add(bytes, Ordering::Relaxed);
153        match phase {
154            IfftProfilePhase::FirstGroup => &self.first_group_zero_fill_bytes,
155            IfftProfilePhase::LaterGroup => &self.later_group_zero_fill_bytes,
156            IfftProfilePhase::RemainderGroup => &self.remainder_group_zero_fill_bytes,
157        }
158        .fetch_add(bytes, Ordering::Relaxed);
159    }
160
161    fn add_xor_bytes(&self, phase: IfftProfilePhase, bytes: usize) {
162        self.xor_bytes.fetch_add(bytes, Ordering::Relaxed);
163        match phase {
164            IfftProfilePhase::LaterGroup => &self.later_group_xor_bytes,
165            IfftProfilePhase::RemainderGroup => &self.remainder_group_xor_bytes,
166            IfftProfilePhase::FirstGroup => return,
167        }
168        .fetch_add(bytes, Ordering::Relaxed);
169    }
170
171    fn add_output_writeback(&self, bytes: usize) {
172        self.output_writeback_calls.fetch_add(1, Ordering::Relaxed);
173        self.output_writeback_bytes
174            .fetch_add(bytes, Ordering::Relaxed);
175    }
176}
177
178#[cfg(feature = "std")]
179#[derive(Debug, Clone, Copy, PartialEq, Eq)]
180pub struct LeopardGf8ProfileStats {
181    pub encode_calls: usize,
182    pub encode_chunks: usize,
183    pub encode_full_groups: usize,
184    pub encode_remainder_groups: usize,
185    pub encode_later_group_calls: usize,
186    pub fft_stage_calls: usize,
187    pub ifft_stage_calls: usize,
188    pub first_group_ifft_calls: usize,
189    pub later_group_ifft_calls: usize,
190    pub remainder_group_ifft_calls: usize,
191    pub first_group_input_copy_bytes: usize,
192    pub later_group_input_copy_bytes: usize,
193    pub remainder_group_input_copy_bytes: usize,
194    pub first_group_zero_fill_bytes: usize,
195    pub later_group_zero_fill_bytes: usize,
196    pub remainder_group_zero_fill_bytes: usize,
197    pub later_group_xor_bytes: usize,
198    pub remainder_group_xor_bytes: usize,
199    pub output_writeback_calls: usize,
200    pub input_copy_bytes: usize,
201    pub zero_fill_bytes: usize,
202    pub xor_bytes: usize,
203    pub output_writeback_bytes: usize,
204}
205
206static TABLES8: Once<LeopardGf8Tables> = Once::new();
207
208#[cfg(feature = "std")]
209static PROFILE8: LeopardGf8ProfileMetrics = LeopardGf8ProfileMetrics {
210    encode_calls: AtomicUsize::new(0),
211    encode_chunks: AtomicUsize::new(0),
212    encode_full_groups: AtomicUsize::new(0),
213    encode_remainder_groups: AtomicUsize::new(0),
214    encode_later_group_calls: AtomicUsize::new(0),
215    fft_stage_calls: AtomicUsize::new(0),
216    ifft_stage_calls: AtomicUsize::new(0),
217    first_group_ifft_calls: AtomicUsize::new(0),
218    later_group_ifft_calls: AtomicUsize::new(0),
219    remainder_group_ifft_calls: AtomicUsize::new(0),
220    first_group_input_copy_bytes: AtomicUsize::new(0),
221    later_group_input_copy_bytes: AtomicUsize::new(0),
222    remainder_group_input_copy_bytes: AtomicUsize::new(0),
223    first_group_zero_fill_bytes: AtomicUsize::new(0),
224    later_group_zero_fill_bytes: AtomicUsize::new(0),
225    remainder_group_zero_fill_bytes: AtomicUsize::new(0),
226    later_group_xor_bytes: AtomicUsize::new(0),
227    remainder_group_xor_bytes: AtomicUsize::new(0),
228    output_writeback_calls: AtomicUsize::new(0),
229    input_copy_bytes: AtomicUsize::new(0),
230    zero_fill_bytes: AtomicUsize::new(0),
231    xor_bytes: AtomicUsize::new(0),
232    output_writeback_bytes: AtomicUsize::new(0),
233};
234
235pub(crate) fn init_leopard_gf8_tables() -> &'static LeopardGf8Tables {
236    TABLES8.call_once(tables::build_tables8)
237}
238
239#[cfg(feature = "std")]
240pub(crate) fn leopard_gf8_profile_stats() -> LeopardGf8ProfileStats {
241    LeopardGf8ProfileStats {
242        encode_calls: PROFILE8.encode_calls.load(Ordering::Relaxed),
243        encode_chunks: PROFILE8.encode_chunks.load(Ordering::Relaxed),
244        encode_full_groups: PROFILE8.encode_full_groups.load(Ordering::Relaxed),
245        encode_remainder_groups: PROFILE8.encode_remainder_groups.load(Ordering::Relaxed),
246        encode_later_group_calls: PROFILE8.encode_later_group_calls.load(Ordering::Relaxed),
247        fft_stage_calls: PROFILE8.fft_stage_calls.load(Ordering::Relaxed),
248        ifft_stage_calls: PROFILE8.ifft_stage_calls.load(Ordering::Relaxed),
249        first_group_ifft_calls: PROFILE8.first_group_ifft_calls.load(Ordering::Relaxed),
250        later_group_ifft_calls: PROFILE8.later_group_ifft_calls.load(Ordering::Relaxed),
251        remainder_group_ifft_calls: PROFILE8.remainder_group_ifft_calls.load(Ordering::Relaxed),
252        first_group_input_copy_bytes: PROFILE8
253            .first_group_input_copy_bytes
254            .load(Ordering::Relaxed),
255        later_group_input_copy_bytes: PROFILE8
256            .later_group_input_copy_bytes
257            .load(Ordering::Relaxed),
258        remainder_group_input_copy_bytes: PROFILE8
259            .remainder_group_input_copy_bytes
260            .load(Ordering::Relaxed),
261        first_group_zero_fill_bytes: PROFILE8.first_group_zero_fill_bytes.load(Ordering::Relaxed),
262        later_group_zero_fill_bytes: PROFILE8.later_group_zero_fill_bytes.load(Ordering::Relaxed),
263        remainder_group_zero_fill_bytes: PROFILE8
264            .remainder_group_zero_fill_bytes
265            .load(Ordering::Relaxed),
266        later_group_xor_bytes: PROFILE8.later_group_xor_bytes.load(Ordering::Relaxed),
267        remainder_group_xor_bytes: PROFILE8.remainder_group_xor_bytes.load(Ordering::Relaxed),
268        output_writeback_calls: PROFILE8.output_writeback_calls.load(Ordering::Relaxed),
269        input_copy_bytes: PROFILE8.input_copy_bytes.load(Ordering::Relaxed),
270        zero_fill_bytes: PROFILE8.zero_fill_bytes.load(Ordering::Relaxed),
271        xor_bytes: PROFILE8.xor_bytes.load(Ordering::Relaxed),
272        output_writeback_bytes: PROFILE8.output_writeback_bytes.load(Ordering::Relaxed),
273    }
274}
275
276#[cfg(feature = "std")]
277pub(crate) fn reset_leopard_gf8_profile_stats() {
278    PROFILE8.encode_calls.store(0, Ordering::Relaxed);
279    PROFILE8.encode_chunks.store(0, Ordering::Relaxed);
280    PROFILE8.encode_full_groups.store(0, Ordering::Relaxed);
281    PROFILE8.encode_remainder_groups.store(0, Ordering::Relaxed);
282    PROFILE8
283        .encode_later_group_calls
284        .store(0, Ordering::Relaxed);
285    PROFILE8.fft_stage_calls.store(0, Ordering::Relaxed);
286    PROFILE8.ifft_stage_calls.store(0, Ordering::Relaxed);
287    PROFILE8.first_group_ifft_calls.store(0, Ordering::Relaxed);
288    PROFILE8.later_group_ifft_calls.store(0, Ordering::Relaxed);
289    PROFILE8
290        .remainder_group_ifft_calls
291        .store(0, Ordering::Relaxed);
292    PROFILE8
293        .first_group_input_copy_bytes
294        .store(0, Ordering::Relaxed);
295    PROFILE8
296        .later_group_input_copy_bytes
297        .store(0, Ordering::Relaxed);
298    PROFILE8
299        .remainder_group_input_copy_bytes
300        .store(0, Ordering::Relaxed);
301    PROFILE8
302        .first_group_zero_fill_bytes
303        .store(0, Ordering::Relaxed);
304    PROFILE8
305        .later_group_zero_fill_bytes
306        .store(0, Ordering::Relaxed);
307    PROFILE8
308        .remainder_group_zero_fill_bytes
309        .store(0, Ordering::Relaxed);
310    PROFILE8.later_group_xor_bytes.store(0, Ordering::Relaxed);
311    PROFILE8
312        .remainder_group_xor_bytes
313        .store(0, Ordering::Relaxed);
314    PROFILE8.output_writeback_calls.store(0, Ordering::Relaxed);
315    PROFILE8.input_copy_bytes.store(0, Ordering::Relaxed);
316    PROFILE8.zero_fill_bytes.store(0, Ordering::Relaxed);
317    PROFILE8.xor_bytes.store(0, Ordering::Relaxed);
318    PROFILE8.output_writeback_bytes.store(0, Ordering::Relaxed);
319}
320
321pub(crate) fn build_leopard_gf8_encode_driver(
322    data_shards: usize,
323    parity_shards: usize,
324    shard_size: usize,
325) -> Result<LeopardGf8EncodeDriver, Error> {
326    driver::build_leopard_gf8_encode_driver(data_shards, parity_shards, shard_size)
327}
328
329fn build_fft_dit8_plan(mtrunc: usize, m: usize, skew_lut: &[u8; MODULUS8]) -> FftDit8Plan {
330    let mut stage4_blocks = Vec::new();
331    let mut dist4 = m;
332    let mut dist = m >> 2;
333    while dist != 0 {
334        let mut r = 0usize;
335        while r < mtrunc {
336            let i_end = r + dist;
337            stage4_blocks.push(Stage4Block {
338                r,
339                dist,
340                log_m01: skew_lut[i_end - 1],
341                log_m02: skew_lut[i_end + dist - 1],
342                log_m23: skew_lut[i_end + dist * 2 - 1],
343            });
344            r += dist4;
345        }
346        dist4 = dist;
347        dist >>= 2;
348    }
349
350    let final_stage = if dist4 == 2 {
351        let mut blocks = Vec::new();
352        let mut r = 0usize;
353        while r < mtrunc {
354            blocks.push(Stage2Block {
355                r,
356                dist: 1,
357                log_m: skew_lut[r],
358            });
359            r += 2;
360        }
361        blocks
362    } else {
363        Vec::new()
364    };
365
366    FftDit8Plan {
367        mtrunc,
368        stage4_blocks,
369        final_stage,
370    }
371}
372
373fn build_ifft_dit8_plan(mtrunc: usize, m: usize, skew_lut: &[u8]) -> IfftDit8Plan {
374    let mut initial_blocks = Vec::new();
375    let mut later_blocks = Vec::new();
376    let mut dist = 1usize;
377    let mut dist4 = 4usize;
378
379    if dist4 <= m {
380        let full_groups = mtrunc & !3usize;
381        let mut r = 0usize;
382        while r < full_groups {
383            let i_end = r + dist;
384            initial_blocks.push(Stage4Block {
385                r,
386                dist,
387                log_m01: skew_lut[i_end],
388                log_m02: skew_lut[i_end + dist],
389                log_m23: skew_lut[i_end + dist * 2],
390            });
391            r += dist4;
392        }
393
394        if full_groups < mtrunc {
395            let r = full_groups;
396            let i_end = r + dist;
397            initial_blocks.push(Stage4Block {
398                r,
399                dist,
400                log_m01: skew_lut[i_end],
401                log_m02: skew_lut[i_end + dist],
402                log_m23: skew_lut[i_end + dist * 2],
403            });
404        }
405
406        dist = dist4;
407        dist4 <<= 2;
408        while dist4 <= m {
409            let mut r = 0usize;
410            while r < mtrunc {
411                let i_end = r + dist;
412                later_blocks.push(Stage4Block {
413                    r,
414                    dist,
415                    log_m01: skew_lut[i_end],
416                    log_m02: skew_lut[i_end + dist],
417                    log_m23: skew_lut[i_end + dist * 2],
418                });
419                r += dist4;
420            }
421            dist = dist4;
422            dist4 <<= 2;
423        }
424    }
425
426    let final_stage = if dist < m {
427        Some(Stage2Block {
428            r: 0,
429            dist,
430            log_m: skew_lut[dist],
431        })
432    } else {
433        None
434    };
435
436    IfftDit8Plan {
437        mtrunc,
438        m,
439        initial_blocks,
440        later_blocks,
441        clear_start: (mtrunc + 3) & !3usize,
442        final_stage,
443    }
444}
445
446/// IFFT plan builder for the decode path.
447///
448/// The decode path passes the full `fft_skew` array (no offset), so skew
449/// indices use `i_end - 1` style indexing (matching the FFT plan builder).
450/// The encoder uses `build_ifft_dit8_plan` with `fft_skew[m-1..]`, which
451/// effectively achieves the same result with `i_end` indexing.
452fn build_ifft_decode_dit8_plan(mtrunc: usize, m: usize, skew_lut: &[u8; MODULUS8]) -> IfftDit8Plan {
453    let mut initial_blocks = Vec::new();
454    let mut later_blocks = Vec::new();
455    let mut dist = 1usize;
456    let mut dist4 = 4usize;
457
458    if dist4 <= m {
459        let full_groups = mtrunc & !3usize;
460        let mut r = 0usize;
461        while r < full_groups {
462            let i_end = r + dist;
463            initial_blocks.push(Stage4Block {
464                r,
465                dist,
466                log_m01: skew_lut[i_end - 1],
467                log_m02: skew_lut[i_end + dist - 1],
468                log_m23: skew_lut[i_end + dist * 2 - 1],
469            });
470            r += dist4;
471        }
472
473        if full_groups < mtrunc {
474            let r = full_groups;
475            let i_end = r + dist;
476            initial_blocks.push(Stage4Block {
477                r,
478                dist,
479                log_m01: skew_lut[i_end - 1],
480                log_m02: skew_lut[i_end + dist - 1],
481                log_m23: skew_lut[i_end + dist * 2 - 1],
482            });
483        }
484
485        dist = dist4;
486        dist4 <<= 2;
487        while dist4 <= m {
488            let mut r = 0usize;
489            while r < mtrunc {
490                let i_end = r + dist;
491                later_blocks.push(Stage4Block {
492                    r,
493                    dist,
494                    log_m01: skew_lut[i_end - 1],
495                    log_m02: skew_lut[i_end + dist - 1],
496                    log_m23: skew_lut[i_end + dist * 2 - 1],
497                });
498                r += dist4;
499            }
500            dist = dist4;
501            dist4 <<= 2;
502        }
503    }
504
505    let final_stage = if dist < m {
506        Some(Stage2Block {
507            r: 0,
508            dist,
509            log_m: skew_lut[dist - 1],
510        })
511    } else {
512        None
513    };
514
515    IfftDit8Plan {
516        mtrunc,
517        m,
518        initial_blocks,
519        later_blocks,
520        clear_start: (mtrunc + 3) & !3usize,
521        final_stage,
522    }
523}
524
525pub(crate) fn encode_skeleton<T: AsRef<[u8]>, U: AsRef<[u8]> + AsMut<[u8]>>(
526    data_shards: usize,
527    parity_shards: usize,
528    data: &[T],
529    parity: &mut [U],
530) -> Result<LeopardGf8EncodeDriver, Error> {
531    encode::encode_skeleton(data_shards, parity_shards, data, parity)
532}
533
534pub(crate) fn encode_with_tables<T: AsRef<[u8]>, U: AsRef<[u8]> + AsMut<[u8]>>(
535    data_shards: usize,
536    parity_shards: usize,
537    data: &[T],
538    parity: &mut [U],
539) -> Result<LeopardGf8EncodeDriver, Error> {
540    encode::encode_with_tables(data_shards, parity_shards, data, parity)
541}
542
543pub(crate) fn reconstruct_with_tables(
544    present: &[bool],
545    outputs: &mut [&mut [u8]],
546    input_data: &[Option<&[u8]>],
547    data_shards: usize,
548    parity_shards: usize,
549) -> Result<(), Error> {
550    let tables = init_leopard_gf8_tables();
551    decode::reconstruct_with_tables(
552        present,
553        outputs,
554        input_data,
555        data_shards,
556        parity_shards,
557        tables,
558    )
559}
560
561fn ceil_pow2(n: usize) -> usize {
562    n.next_power_of_two()
563}
rustfs_erasure_codec/core/leopard_gf8/mod.rs

rustfs_erasure_codec/core/leopard_gf8/
mod.rs
