const POLYNOMIAL: u32 = 0x1_100B;
pub const ORDER: u32 = 65_535;
pub const MAX_INPUT_BLOCKS: usize = 32_768;
pub const MAX_RECOVERY_BLOCKS: usize = 65_535;
fn gcd(mut a: u32, mut b: u32) -> u32 {
while b != 0 {
let t = b;
b = a % b;
a = t;
}
a
}
pub fn input_logbases(count: usize) -> Vec<u32> {
assert!(
count <= MAX_INPUT_BLOCKS,
"PAR2 supports at most {MAX_INPUT_BLOCKS} input blocks, got {count}"
);
let mut out = Vec::with_capacity(count);
let mut logbase = 0u32;
while out.len() < count {
if gcd(ORDER, logbase) == 1 {
out.push(logbase);
}
logbase += 1;
}
out
}
#[derive(Debug, Clone)]
pub struct Gf16 {
antilog: Vec<u16>,
log: Vec<u16>,
}
impl Gf16 {
pub fn new() -> Self {
let mut antilog = vec![0u16; ORDER as usize];
let mut log = vec![0u16; ORDER as usize + 1];
let mut value: u32 = 1;
for (i, slot) in antilog.iter_mut().enumerate() {
*slot = value as u16;
log[value as usize] = i as u16;
value <<= 1;
if value & 0x1_0000 != 0 {
value ^= POLYNOMIAL;
}
}
Self { antilog, log }
}
pub fn mul(&self, a: u16, b: u16) -> u16 {
if a == 0 || b == 0 {
return 0;
}
let exponent = self.log[a as usize] as u32 + self.log[b as usize] as u32;
self.antilog[(exponent % ORDER) as usize]
}
pub fn pow(&self, base: u16, exponent: u32) -> u16 {
if base == 0 {
return u16::from(exponent == 0);
}
let log = self.log[base as usize] as u64;
self.antilog[((log * exponent as u64) % ORDER as u64) as usize]
}
pub fn exp(&self, exponent: u32) -> u16 {
self.antilog[(exponent % ORDER) as usize]
}
pub fn discrete_log(&self, value: u16) -> u16 {
assert!(value != 0, "zero has no discrete logarithm");
self.log[value as usize]
}
pub fn inverse(&self, value: u16) -> u16 {
let log = self.discrete_log(value) as u32;
self.exp(ORDER - log)
}
pub fn input_bases(&self, count: usize) -> Vec<u16> {
input_logbases(count)
.into_iter()
.map(|logbase| self.antilog[logbase as usize])
.collect()
}
pub fn recovery_coefficient(&self, input_index: usize, exponent: u32) -> u16 {
let logbase = input_logbases(input_index + 1)[input_index] as u64;
self.antilog[((logbase * exponent as u64) % ORDER as u64) as usize]
}
}
pub fn xor_dep_matrix(coeff: u16) -> [u16; 16] {
if coeff == 0 {
return [0u16; 16];
}
let mut deps = [0u16; 16];
for b in (0..16).rev() {
if (coeff >> b) & 1 == 1 {
for (k, d) in deps.iter_mut().enumerate() {
*d ^= 1 << k;
}
}
if b > 0 {
let high = deps[15];
deps.copy_within(0..15, 1);
deps[0] = 0;
for k in [0usize, 1, 3, 12] {
deps[k] ^= high;
}
}
}
deps
}
impl Default for Gf16 {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn table_sizes_and_first_powers_of_two() {
let gf = Gf16::new();
assert_eq!(gf.antilog.len(), 65_535);
assert_eq!(gf.log.len(), 65_536);
assert_eq!(gf.antilog[0], 1);
assert_eq!(gf.antilog[1], 2);
assert_eq!(gf.antilog[2], 4);
assert_eq!(gf.antilog[16], 0x100B);
}
#[test]
fn log_and_antilog_are_inverses() {
let gf = Gf16::new();
for exponent in 0..65_535u32 {
let value = gf.antilog[exponent as usize];
assert_eq!(gf.log[value as usize] as u32, exponent);
}
for value in 1..=65_535u32 {
let exponent = gf.log[value as usize];
assert_eq!(gf.antilog[exponent as usize] as u32, value);
}
}
#[test]
fn multiplication_basics_and_log_homomorphism() {
let gf = Gf16::new();
assert_eq!(gf.mul(0, 1234), 0);
assert_eq!(gf.mul(1, 1234), 1234);
assert_eq!(gf.mul(2, 2), 4);
for &(i, j) in &[(3u32, 5u32), (100, 200), (60_000, 60_000)] {
let product = gf.mul(gf.antilog[i as usize], gf.antilog[j as usize]);
assert_eq!(product, gf.antilog[((i + j) % 65_535) as usize]);
}
}
#[test]
fn pow_matches_repeated_multiplication() {
let gf = Gf16::new();
assert_eq!(gf.pow(7, 0), 1);
assert_eq!(gf.pow(7, 1), 7);
for base in [2u16, 7, 12_345, 60_000] {
let mut acc = 1u16;
for exponent in 0..20u32 {
assert_eq!(gf.pow(base, exponent), acc);
acc = gf.mul(acc, base);
}
}
}
#[test]
fn input_logbases_skip_factors_of_65535() {
let logbases = input_logbases(64);
assert_eq!(&logbases[..4], &[1, 2, 4, 7]);
for &logbase in &logbases {
assert_ne!(logbase % 3, 0);
assert_ne!(logbase % 5, 0);
assert_ne!(logbase % 17, 0);
assert_ne!(logbase % 257, 0);
}
assert!(logbases.windows(2).all(|w| w[0] < w[1]));
}
#[test]
fn input_bases_are_antilogs_of_the_logbases() {
let gf = Gf16::new();
assert_eq!(gf.input_bases(4), vec![2, 4, 16, 128]);
}
#[test]
fn recovery_coefficient_exponent_zero_is_one() {
let gf = Gf16::new();
for input_index in [0usize, 1, 5, 100] {
assert_eq!(gf.recovery_coefficient(input_index, 0), 1);
}
assert_eq!(gf.recovery_coefficient(0, 1), 2);
assert_eq!(gf.recovery_coefficient(1, 1), 4);
assert_eq!(gf.recovery_coefficient(0, 2), 4);
}
#[test]
fn inverse_is_the_multiplicative_inverse() {
let gf = Gf16::new();
assert_eq!(gf.inverse(1), 1);
for value in [2u16, 3, 7, 12_345, 60_000, 65_535] {
let inv = gf.inverse(value);
assert_eq!(gf.mul(value, inv), 1, "value={value:#06x}");
}
}
#[test]
fn inverse_covers_every_nonzero_element() {
let gf = Gf16::new();
for exponent in (0..65_535u32).step_by(997) {
let value = gf.exp(exponent);
assert_eq!(gf.mul(value, gf.inverse(value)), 1);
}
}
#[test]
fn full_multiplicative_group_is_covered() {
let gf = Gf16::new();
let mut seen = vec![false; 65_536];
for &value in &gf.antilog {
assert!(!seen[value as usize], "duplicate value {value}");
assert_ne!(value, 0);
seen[value as usize] = true;
}
}
fn apply_dep_matrix(deps: &[u16; 16], x: u16) -> u16 {
let mut result = 0u16;
for (k, &mask) in deps.iter().enumerate() {
let bits = x & mask;
result |= (bits.count_ones() as u16 & 1) << k;
}
result
}
#[test]
fn xor_dep_matrix_special_cases() {
let deps0 = xor_dep_matrix(0);
assert_eq!(deps0, [0u16; 16]);
for x in [0u16, 1, 0xFF, 0x1234, 0xFFFF] {
assert_eq!(apply_dep_matrix(&deps0, x), 0);
}
let deps1 = xor_dep_matrix(1);
for k in 0..16u16 {
assert_eq!(deps1[k as usize], 1 << k, "identity bit {k}");
}
for x in [0u16, 1, 0xFF, 0x1234, 0xFFFF] {
assert_eq!(apply_dep_matrix(&deps1, x), x);
}
}
#[test]
fn xor_dep_matrix_matches_gf_mul_exhaustive() {
let gf = Gf16::new();
let test_coeffs: &[u16] = &[
2, 3, 4, 7, 16, 128, 256, 1000, 0x1234, 0x8000, 0xABCD, 0xFFFE, 65534,
];
for &coeff in test_coeffs {
let deps = xor_dep_matrix(coeff);
for x in 0u32..=65535 {
let x = x as u16;
let expected = gf.mul(x, coeff);
let got = apply_dep_matrix(&deps, x);
assert_eq!(
got, expected,
"coeff={coeff:#06x} x={x:#06x}: expected {expected:#06x}, got {got:#06x}"
);
}
}
}
#[test]
fn xor_dep_matrix_matches_gf_mul_all_coefficients() {
let gf = Gf16::new();
let x: u16 = 0xA5C3;
for coeff in 1u16..=65535 {
let deps = xor_dep_matrix(coeff);
let expected = gf.mul(x, coeff);
let got = apply_dep_matrix(&deps, x);
assert_eq!(
got, expected,
"coeff={coeff:#06x}: expected {expected:#06x}, got {got:#06x}"
);
}
}
}