Reduction table

reduction_div.rs

const REDUCTION_TABLE: [[u32; 2]; 255] = [
    [0, 0],
    [0, 1],
    [43691, 1],
    [0, 2],
    [52429, 2],
    [43691, 2],
    [9363, 66],
    [0, 3],
    [58255, 3],
    [52429, 3],
    [47663, 3],
    [43691, 3],
    [40330, 3],
    [9363, 67],
    [34953, 3],
    [0, 4],
    [61681, 4],
    [58255, 4],
    [55189, 4],
    [52429, 4],
    [34329, 68],
    [47663, 4],
    [25645, 68],
    [43691, 4],
    [18351, 68],
    [40330, 4],
    [12137, 68],
    [9363, 68],
    [36158, 4],
    [34953, 4],
    [2115, 68],
    [0, 5],
    [63551, 5],
    [61681, 5],
    [59919, 5],
    [58255, 5],
    [56680, 5],
    [55189, 5],
    [42011, 69],
    [52429, 5],
    [36765, 69],
    [34329, 69],
    [48771, 5],
    [47663, 5],
    [46604, 5],
    [25645, 69],
    [23705, 69],
    [43691, 5],
    [20063, 69],
    [18351, 69],
    [41121, 5],
    [40330, 5],
    [39569, 5],
    [12137, 69],
    [10725, 69],
    [9363, 69],
    [8049, 69],
    [36158, 5],
    [35545, 5],
    [34953, 5],
    [34380, 5],
    [2115, 69],
    [1041, 69],
    [0, 6],
    [64528, 6],
    [63551, 6],
    [62602, 6],
    [61681, 6],
    [56039, 70],
    [59919, 6],
    [59075, 6],
    [58255, 6],
    [57457, 6],
    [56680, 6],
    [46313, 70],
    [55189, 6],
    [54472, 6],
    [42011, 70],
    [53093, 6],
    [52429, 6],
    [51782, 6],
    [36765, 70],
    [50534, 6],
    [34329, 70],
    [49345, 6],
    [48771, 6],
    [48211, 6],
    [47663, 6],
    [28719, 70],
    [46604, 6],
    [26647, 70],
    [25645, 70],
    [24665, 70],
    [23705, 70],
    [44151, 6],
    [43691, 6],
    [20945, 70],
    [20063, 70],
    [42367, 6],
    [18351, 70],
    [41528, 6],
    [41121, 6],
    [40722, 6],
    [40330, 6],
    [39946, 6],
    [39569, 6],
    [12863, 70],
    [12137, 70],
    [38480, 6],
    [10725, 70],
    [37787, 6],
    [9363, 70],
    [37118, 6],
    [8049, 70],
    [7409, 70],
    [36158, 6],
    [35849, 6],
    [35545, 6],
    [4957, 70],
    [34953, 6],
    [34664, 6],
    [34380, 6],
    [2665, 70],
    [2115, 70],
    [1573, 70],
    [1041, 70],
    [517, 70],
    [0, 7],
    [65028, 7],
    [64528, 7],
    [64036, 7],
    [63551, 7],
    [63073, 7],
    [62602, 7],
    [62138, 7],
    [61681, 7],
    [61231, 7],
    [56039, 71],
    [60350, 7],
    [59919, 7],
    [59494, 7],
    [59075, 7],
    [58662, 7],
    [58255, 7],
    [57853, 7],
    [57457, 7],
    [57066, 7],
    [56680, 7],
    [56300, 7],
    [46313, 71],
    [55554, 7],
    [55189, 7],
    [54828, 7],
    [54472, 7],
    [42705, 71],
    [42011, 71],
    [53431, 7],
    [53093, 7],
    [52759, 7],
    [52429, 7],
    [38671, 71],
    [51782, 7],
    [51464, 7],
    [36765, 71],
    [36145, 71],
    [50534, 7],
    [34927, 71],
    [34329, 71],
    [49637, 7],
    [49345, 7],
    [32577, 71],
    [48771, 7],
    [31443, 71],
    [48211, 7],
    [47935, 7],
    [47663, 7],
    [29251, 71],
    [28719, 71],
    [46864, 7],
    [46604, 7],
    [46346, 7],
    [26647, 71],
    [45840, 7],
    [25645, 71],
    [45344, 7],
    [24665, 71],
    [44859, 7],
    [23705, 71],
    [23233, 71],
    [44151, 7],
    [43920, 7],
    [43691, 7],
    [21393, 71],
    [20945, 71],
    [43019, 7],
    [20063, 71],
    [42582, 7],
    [42367, 7],
    [42154, 7],
    [18351, 71],
    [41735, 7],
    [41528, 7],
    [17111, 71],
    [41121, 7],
    [16305, 71],
    [40722, 7],
    [40525, 7],
    [40330, 7],
    [40137, 7],
    [39946, 7],
    [39757, 7],
    [39569, 7],
    [13231, 71],
    [12863, 71],
    [39017, 7],
    [12137, 71],
    [11779, 71],
    [38480, 7],
    [11073, 71],
    [10725, 71],
    [37958, 7],
    [37787, 7],
    [9699, 71],
    [9363, 71],
    [37283, 7],
    [37118, 7],
    [8373, 71],
    [8049, 71],
    [36632, 7],
    [7409, 71],
    [7093, 71],
    [36158, 7],
    [36003, 7],
    [35849, 7],
    [5857, 71],
    [35545, 7],
    [35395, 7],
    [4957, 71],
    [35099, 7],
    [34953, 7],
    [34808, 7],
    [34664, 7],
    [3507, 71],
    [34380, 7],
    [2943, 71],
    [2665, 71],
    [33962, 7],
    [2115, 71],
    [1843, 71],
    [1573, 71],
    [33421, 7],
    [1041, 71],
    [33157, 7],
    [517, 71],
    [32897, 7],
];

fn do_division_u16_by_u8(v: u16, k: u8) -> u16 {
    let pos = k - 1;
    let divisor = REDUCTION_TABLE[pos as usize];
    let magic = divisor[0];
    let more = divisor[1];
    if magic == 0 {
        v >> more
    } else {
        let quotient = (v as u32 * magic) >> 16;
        if more & 0x40 != 0 {
            let t = ((v as u32 - quotient) >> 1) + quotient;
            (t >> (more & 0x1F)) as u16
        } else {
            (quotient >> more) as u16
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    fn div_by_n_reference(v: u16, d: u8) -> u16 {
        (v as f32 / d as f32) as u16
    }

    #[test]
    fn div_optimization() {
        for d in 1..u8::MAX {
            for v in 1..u16::MAX {
                let opt = div_by_n_reference(v, d);
                let slow = do_division_u16_by_u8(v, d);
                assert_eq!(opt, slow, "Division failed on {v}, {d}");
            }
        }
    }
}