boolean.rs

1/// Returns the Walsh spectrum of an n-input boolean function packed as a truth-table code.2pub fn walsh_spectrum(code: u128, n: usize) -> Vec<i64> {3    let size = 1usize << n;4    let mut t: Vec<i64> = (0..size)5        .map(|x| if (code >> x) & 1 == 1 { -1 } else { 1 })6        .collect();7    let mut len = 1;8    while len < size {9        let mut i = 0;10        while i < size {11            for j in i..i + len {12                let a = t[j];13                let b = t[j + len];14                t[j] = a + b;15                t[j + len] = a - b;16            }17            i += len << 1;18        }19        len <<= 1;20    }21    t22}2324/// Returns how far the packed function sits from every affine function, zero when it is one.25///26/// ```27/// assert_eq!(mrlynum::boolean::nonlinearity(0b0110, 2), 0);28/// assert_eq!(mrlynum::boolean::nonlinearity(0b1000, 2), 1);29/// ```30pub fn nonlinearity(code: u128, n: usize) -> i64 {31    if n == 0 {32        return 0;33    }34    let max_w = walsh_spectrum(code, n)35        .into_iter()36        .map(|w| w.abs())37        .max()38        .unwrap_or(0);39    (1i64 << (n - 1)) - max_w / 240}4142/// Reports whether the packed function outputs one on exactly half of its inputs.43pub fn is_balanced(code: u128, n: usize) -> bool {44    let size = 1u32 << n;45    (code & ((1u128 << size) - 1)).count_ones() == size / 246}4748/// Returns the mean chance that flipping one input bit flips the output, 0.5 at full avalanche.49pub fn sac(code: u128, n: usize) -> f64 {50    if n == 0 {51        return 0.0;52    }53    let size = 1usize << n;54    let mut total = 0.0;55    for bit in 0..n {56        let mut flips = 0usize;57        for x in 0..size {58            let f = (code >> x) & 1;59            let g = (code >> (x ^ (1 << bit))) & 1;60            if f != g {61                flips += 1;62            }63        }64        total += flips as f64 / size as f64;65    }66    total / n as f6467}6869#[cfg(test)]70mod tests {71    use super::*;72    #[test]73    fn linear_function_has_zero_nonlinearity() {74        let n = 3;75        let size = 1usize << n;76        let mut code: u128 = 0;77        for x in 0..size {78            if x & 1 == 1 {79                code |= 1 << x;80            }81        }82        assert_eq!(nonlinearity(code, n), 0);83    }84    #[test]85    fn n3_max_nonlinearity_is_two() {86        let n = 3;87        let max = (0..(1u128 << (1 << n)))88            .map(|c| nonlinearity(c, n))89            .max()90            .unwrap();91        assert_eq!(max, 2);92    }93    #[test]94    fn n4_reaches_bent_level_six() {95        let n = 4;96        let max = (0..(1u128 << (1 << n)))97            .map(|c| nonlinearity(c, n))98            .max()99            .unwrap();100        assert_eq!(max, 6);101    }102    #[test]103    fn balance_detects_half_ones() {104        assert!(is_balanced(0b0011, 2));105        assert!(!is_balanced(0b0111, 2));106    }107    #[test]108    fn carpet_corners_expand_on_four_walsh_characters() {109        let code = 7;110        for x in 0..2u32 {111            for y in 0..2u32 {112                let (sx, sy) = (1 - 2 * (x as i64), 1 - 2 * (y as i64));113                assert_eq!(114                    ((code >> (2 * x + y)) & 1) as i64,115                    (3 + sx + sy - sx * sy) / 4116                );117            }118        }119        let spectrum = walsh_spectrum(code, 2);120        assert_eq!(spectrum, vec![-2, -2, -2, 2]);121        let quarters: Vec<i64> = spectrum122            .iter()123            .enumerate()124            .map(|(s, &w)| ((if s == 0 { 4 } else { 0 }) - w) / 2)125            .collect();126        assert_eq!(quarters, vec![3, 1, 1, -1]);127    }128    #[test]129    fn sac_of_constant_is_zero() {130        assert_eq!(sac(0, 3), 0.0);131        let n = 3;132        let size = 1usize << n;133        let mut code: u128 = 0;134        for x in 0..size {135            if x & 1 == 1 {136                code |= 1 << x;137            }138        }139        assert!((sac(code, n) - 1.0 / 3.0).abs() < 1e-12);140    }141}