qrcode_rust_shared/
qr_polynomial.rs

1//! QR Code Polynomial - Galois Field polynomial operations
2
3use crate::qr_math::QRMath;
4
5/// Polynomial with coefficients in GF(256)
6/// Coefficients are stored in **descending order** (num[0] = highest degree)
7pub struct Polynomial {
8    pub num: Vec<i32>,
9}
10
11impl Polynomial {
12    /// Create a polynomial from coefficients
13    pub fn new(num: Vec<i32>, _shift: i32) -> Self {
14        // Remove leading zeros
15        let mut start = 0;
16        let len = num.len();
17        while start < len - 1 && num[start] == 0 {
18            start += 1;
19        }
20
21        let num = if start > 0 {
22            num[start..].to_vec()
23        } else {
24            num
25        };
26
27        Polynomial { num }
28    }
29
30    pub fn get(&self, index: usize) -> i32 {
31        self.num.get(index).copied().unwrap_or(0)
32    }
33
34    pub fn len(&self) -> usize {
35        self.num.len()
36    }
37
38    pub fn is_empty(&self) -> bool {
39        self.num.is_empty()
40    }
41
42    /// Multiply two polynomials in GF(256)
43    pub fn multiply(&self, e: &Polynomial) -> Polynomial {
44        let mut num = vec![0; self.len() + e.len() - 1];
45
46        for i in 0..self.len() {
47            for j in 0..e.len() {
48                // In GF(256), addition is XOR
49                num[i + j] ^= QRMath::gexp(QRMath::glog(self.get(i)) + QRMath::glog(e.get(j)));
50            }
51        }
52
53        Polynomial::new(num, 0)
54    }
55
56    /// Generate Reed-Solomon error correction polynomial
57    /// g(x) = (x + α^0)(x + α^1)...(x + α^(ec_count-1))
58    pub fn generate_rs_poly(ec_count: i32) -> Polynomial {
59        let mut result = Polynomial::new(vec![1], 0);
60
61        for i in 0..ec_count {
62            let factor = Polynomial::new(vec![1, QRMath::gexp(i)], 0);
63            result = result.multiply(&factor);
64        }
65
66        result
67    }
68
69    /// Polynomial modulo operation (descending order)
70    pub fn r#mod(&self, e: &Polynomial) -> Polynomial {
71        if (self.len() as i32 - e.len() as i32) < 0 {
72            return Polynomial::new(self.num.clone(), 0);
73        }
74
75        let ratio = QRMath::glog(self.get(0)) - QRMath::glog(e.get(0));
76
77        let mut num = self.num.clone();
78        for (i, item) in num.iter_mut().enumerate().take(e.len()) {
79            *item ^= QRMath::gexp(QRMath::glog(e.get(i)) + ratio);
80        }
81
82        Polynomial::new(num, 0).r#mod(e)
83    }
84
85    /// Modulo with shift (for RS error correction calculation)
86    pub fn r#mod_with_shift(&self, e: &Polynomial, shift: i32) -> Polynomial {
87        let mut extended = self.num.clone();
88        extended.extend(std::iter::repeat_n(0, shift as usize));
89
90        let shifted_poly = Polynomial::new(extended, 0);
91        shifted_poly.r#mod(e)
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn test_polynomial_new() {
101        let p = Polynomial::new(vec![1, 2, 3], 0);
102        assert_eq!(p.len(), 3);
103        assert_eq!(p.get(0), 1);
104        assert_eq!(p.get(1), 2);
105        assert_eq!(p.get(2), 3);
106    }
107
108    #[test]
109    fn test_polynomial_new_removes_leading_zeros() {
110        let p = Polynomial::new(vec![0, 0, 1, 2], 0);
111        assert_eq!(p.len(), 2);
112        assert_eq!(p.get(0), 1);
113        assert_eq!(p.get(1), 2);
114    }
115
116    #[test]
117    fn test_multiply_simple() {
118        let p1 = Polynomial::new(vec![1, 2], 0);
119        let p2 = Polynomial::new(vec![1, 3], 0);
120        let result = p1.multiply(&p2);
121
122        assert_eq!(result.get(0), 1);
123        assert_eq!(result.get(1), 1); // 3 ^ 2 = 1
124        assert_eq!(result.get(2), 6);
125    }
126
127    #[test]
128    fn test_generate_rs_poly() {
129        let poly = Polynomial::generate_rs_poly(2);
130        assert_eq!(poly.len(), 3);
131        assert_eq!(poly.get(0), 1);
132    }
133
134    #[test]
135    fn test_mod_result_degree() {
136        let divisor = Polynomial::generate_rs_poly(4);
137
138        for test_data in [
139            vec![1, 2, 3, 4, 5, 6, 7, 8],
140            vec![1, 0, 0, 0, 0, 0, 0, 0],
141            vec![255, 254, 253, 252],
142        ] {
143            let dividend = Polynomial::new(test_data, 0);
144            let remainder = dividend.r#mod(&divisor);
145            assert!(remainder.len() <= 4);
146        }
147    }
148
149    #[test]
150    fn test_mod_with_shift() {
151        let p = Polynomial::new(vec![1, 2, 3], 0);
152        let divisor = Polynomial::generate_rs_poly(4);
153        let result = p.r#mod_with_shift(&divisor, 4);
154        assert!(result.len() <= 4);
155    }
156}
qrcode_rust_shared/qr_polynomial.rs

qrcode_rust_shared/
qr_polynomial.rs
