Skip to main content

clm_rust_core/cpn/
solver.rs

1pub fn math_gcd(mut a: i64, mut b: i64) -> i64 {
2    a = a.abs();
3    b = b.abs();
4    while b > 0 {
5        let t = b;
6        b = a % b;
7        a = t;
8    }
9    a
10}
11
12pub fn math_lcm(a: i64, b: i64) -> i64 {
13    if a == 0 || b == 0 {
14        return 0;
15    }
16    let gcd = math_gcd(a, b);
17    ((a * b) / gcd).abs()
18}
19
20pub fn solve_nullspace(
21    matrix: &[Vec<i64>],
22    rows: usize,
23    cols: usize,
24    transpose: bool,
25) -> Vec<Vec<i64>> {
26    let (work_rows, work_cols) = if transpose {
27        (cols, rows)
28    } else {
29        (rows, cols)
30    };
31
32    // Initialize working matrix A
33    let mut a_mat = vec![vec![0; work_cols]; work_rows];
34    for r in 0..work_rows {
35        for c in 0..work_cols {
36            a_mat[r][c] = if transpose {
37                if c < matrix.len() && r < matrix[c].len() {
38                    matrix[c][r]
39                } else {
40                    0
41                }
42            } else {
43                if r < matrix.len() && c < matrix[r].len() {
44                    matrix[r][c]
45                } else {
46                    0
47                }
48            };
49        }
50    }
51
52    let mut pivot_row = vec![-1; work_cols];
53    let mut is_free = vec![true; work_cols];
54
55    let mut p = 0;
56    let mut c = 0;
57
58    while c < work_cols && p < work_rows {
59        // Find pivot row
60        let mut pr = p;
61        let mut found = false;
62        while pr < work_rows {
63            if a_mat[pr][c] != 0 {
64                found = true;
65                break;
66            }
67            pr += 1;
68        }
69
70        if !found {
71            c += 1;
72            continue;
73        }
74
75        // Swap row pr and p if needed
76        if pr != p {
77            a_mat.swap(p, pr);
78        }
79
80        let pivot = a_mat[p][c];
81        is_free[c] = false;
82        pivot_row[c] = p as i32;
83
84        // Eliminate other rows
85        for i in 0..work_rows {
86            if i != p {
87                let val_i = a_mat[i][c];
88                if val_i != 0 {
89                    let g = math_gcd(pivot, val_i);
90                    let factor_p = val_i / g;
91                    let factor_i = pivot / g;
92
93                    for j in 0..work_cols {
94                        a_mat[i][j] = factor_i * a_mat[i][j] - factor_p * a_mat[p][j];
95                    }
96
97                    // Simplify row i
98                    let mut r_gcd = 0;
99                    for j in 0..work_cols {
100                        r_gcd = math_gcd(r_gcd, a_mat[i][j]);
101                    }
102                    if r_gcd > 1 {
103                        for j in 0..work_cols {
104                            a_mat[i][j] /= r_gcd;
105                        }
106                    }
107                }
108            }
109        }
110
111        // Simplify pivot row
112        let mut p_gcd = 0;
113        for j in 0..work_cols {
114            p_gcd = math_gcd(p_gcd, a_mat[p][j]);
115        }
116        if p_gcd > 1 {
117            for j in 0..work_cols {
118                a_mat[p][j] /= p_gcd;
119            }
120        }
121
122        p += 1;
123        c += 1;
124    }
125
126    // Back-Substitution & Basis Generation
127    let mut basis_vectors = Vec::new();
128
129    for f in 0..work_cols {
130        if is_free[f] {
131            let mut num_vec = vec![0; work_cols];
132            let mut den_vec = vec![1; work_cols];
133
134            for j in 0..work_cols {
135                if is_free[j] {
136                    if j == f {
137                        num_vec[j] = 1;
138                        den_vec[j] = 1;
139                    } else {
140                        num_vec[j] = 0;
141                        den_vec[j] = 1;
142                    }
143                } else {
144                    let pr = pivot_row[j] as usize;
145                    let a_pr_j = a_mat[pr][j];
146                    let a_pr_f = a_mat[pr][f];
147
148                    let mut num = -a_pr_f;
149                    let mut den = a_pr_j;
150                    if den < 0 {
151                        num = -num;
152                        den = -den;
153                    }
154                    let g = math_gcd(num, den);
155                    num_vec[j] = num / g;
156                    den_vec[j] = den / g;
157                }
158            }
159
160            // Find LCM of denominators
161            let mut lcm = 1;
162            for j in 0..work_cols {
163                lcm = math_lcm(lcm, den_vec[j]);
164            }
165
166            // Multiply by LCM to get integer vector
167            let mut int_vec = vec![0; work_cols];
168            for j in 0..work_cols {
169                int_vec[j] = num_vec[j] * (lcm / den_vec[j]);
170            }
171
172            // Simplify vector by dividing by overall GCD
173            let mut vec_gcd = 0;
174            for j in 0..work_cols {
175                vec_gcd = math_gcd(vec_gcd, int_vec[j]);
176            }
177            if vec_gcd > 1 {
178                for j in 0..work_cols {
179                    int_vec[j] /= vec_gcd;
180                }
181            }
182
183            // Normalize direction (ensure non-negativity if all components have same sign)
184            let mut all_non_positive = true;
185            for j in 0..work_cols {
186                if int_vec[j] > 0 {
187                    all_non_positive = false;
188                    break;
189                }
190            }
191            if all_non_positive {
192                for j in 0..work_cols {
193                    int_vec[j] = -int_vec[j];
194                }
195            }
196
197            basis_vectors.push(int_vec);
198        }
199    }
200
201    basis_vectors
202}
203
204pub const MAX_SAFE_INT: i64 = 9_007_199_254_740_991;
205pub const MIN_SAFE_INT: i64 = -9_007_199_254_740_991;
206pub const PINVARIANT_OVERFLOW_CODE: &str = "ERR_PINVARIANT_SAFE_INT_OVERFLOW";
207
208#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
209pub struct PInvariantRangeError {
210    pub code: String,
211    pub step: String,
212    pub message: String,
213}
214
215impl PInvariantRangeError {
216    pub fn new(step: &str, message: impl Into<String>) -> Self {
217        Self {
218            code: PINVARIANT_OVERFLOW_CODE.to_string(),
219            step: step.to_string(),
220            message: message.into(),
221        }
222    }
223}
224
225fn check_safe_i128(val: i128, step: &str) -> Result<i64, PInvariantRangeError> {
226    if val < (MIN_SAFE_INT as i128) || val > (MAX_SAFE_INT as i128) {
227        return Err(PInvariantRangeError::new(
228            step,
229            format!("Value {} exceeds IEEE-754 safe integer bounds", val),
230        ));
231    }
232    Ok(val as i64)
233}
234
235fn math_gcd_i128(mut a: i128, mut b: i128) -> i128 {
236    a = a.abs();
237    b = b.abs();
238    while b > 0 {
239        let t = b;
240        b = a % b;
241        a = t;
242    }
243    a
244}
245
246/// Normalize a basis according to `types/lattice/integer_arithmetic_contract.json`:
247/// 1. Divide each non-zero vector by the GCD of its entries.
248/// 2. Ensure the first non-zero component of each vector is strictly positive.
249/// 3. Sort basis vectors in ascending lexicographical order.
250pub fn normalize_primitive_basis(
251    basis: &[Vec<i64>],
252) -> Result<Vec<Vec<i64>>, PInvariantRangeError> {
253    let mut normalized = Vec::with_capacity(basis.len());
254    for vec in basis {
255        let mut g: i128 = 0;
256        for &v in vec {
257            let _ = check_safe_i128(v as i128, "normalization")?;
258            g = math_gcd_i128(g, v as i128);
259        }
260        let mut out: Vec<i64> = if g > 1 {
261            vec.iter().map(|&v| ((v as i128) / g) as i64).collect()
262        } else {
263            vec.clone()
264        };
265        if let Some(&first_nz) = out.iter().find(|&&x| x != 0) {
266            if first_nz < 0 {
267                for x in &mut out {
268                    *x = check_safe_i128(-(*x as i128), "normalization")?;
269                }
270            }
271        }
272        normalized.push(out);
273    }
274    normalized.sort();
275    Ok(normalized)
276}
277
278/// Checked integer nullspace solver enforcing `types/lattice/integer_arithmetic_contract.json` (`INV-494`).
279pub fn solve_nullspace_checked(
280    matrix: &[Vec<i64>],
281    rows: usize,
282    cols: usize,
283    transpose: bool,
284) -> Result<Vec<Vec<i64>>, PInvariantRangeError> {
285    for row in matrix {
286        for &v in row {
287            check_safe_i128(v as i128, "input_validation")?;
288        }
289    }
290
291    let (work_rows, work_cols) = if transpose {
292        (cols, rows)
293    } else {
294        (rows, cols)
295    };
296    if work_rows == 0 || work_cols == 0 {
297        return Ok(Vec::new());
298    }
299
300    let mut a_mat = vec![vec![0i64; work_cols]; work_rows];
301    for r in 0..work_rows {
302        for c in 0..work_cols {
303            let val = if transpose {
304                if c < matrix.len() && r < matrix[c].len() {
305                    matrix[c][r]
306                } else {
307                    0
308                }
309            } else if r < matrix.len() && c < matrix[r].len() {
310                matrix[r][c]
311            } else {
312                0
313            };
314            a_mat[r][c] = check_safe_i128(val as i128, "input_validation")?;
315        }
316    }
317
318    let mut pivot_row = vec![-1i32; work_cols];
319    let mut is_free = vec![true; work_cols];
320    let mut p = 0usize;
321    let mut c = 0usize;
322
323    while c < work_cols && p < work_rows {
324        let mut pr = p;
325        let mut found = false;
326        while pr < work_rows {
327            if a_mat[pr][c] != 0 {
328                found = true;
329                break;
330            }
331            pr += 1;
332        }
333        if !found {
334            c += 1;
335            continue;
336        }
337        if pr != p {
338            a_mat.swap(p, pr);
339        }
340
341        let pivot = a_mat[p][c] as i128;
342        is_free[c] = false;
343        pivot_row[c] = p as i32;
344
345        for i in 0..work_rows {
346            if i != p {
347                let val_i = a_mat[i][c] as i128;
348                if val_i != 0 {
349                    let g = math_gcd_i128(pivot, val_i);
350                    let factor_p = check_safe_i128(val_i / g, "row_elimination")? as i128;
351                    let factor_i = check_safe_i128(pivot / g, "row_elimination")? as i128;
352
353                    for j in 0..work_cols {
354                        let term1 = check_safe_i128(factor_i * (a_mat[i][j] as i128), "row_elimination")? as i128;
355                        let term2 = check_safe_i128(factor_p * (a_mat[p][j] as i128), "row_elimination")? as i128;
356                        a_mat[i][j] = check_safe_i128(term1 - term2, "row_elimination")?;
357                    }
358
359                    let mut r_gcd: i128 = 0;
360                    for j in 0..work_cols {
361                        r_gcd = math_gcd_i128(r_gcd, a_mat[i][j] as i128);
362                    }
363                    if r_gcd > 1 {
364                        for j in 0..work_cols {
365                            a_mat[i][j] = ((a_mat[i][j] as i128) / r_gcd) as i64;
366                        }
367                    }
368                }
369            }
370        }
371
372        let mut p_gcd: i128 = 0;
373        for j in 0..work_cols {
374            p_gcd = math_gcd_i128(p_gcd, a_mat[p][j] as i128);
375        }
376        if p_gcd > 1 {
377            for j in 0..work_cols {
378                a_mat[p][j] = ((a_mat[p][j] as i128) / p_gcd) as i64;
379            }
380        }
381
382        p += 1;
383        c += 1;
384    }
385
386    let mut basis_vectors = Vec::new();
387    for f in 0..work_cols {
388        if is_free[f] {
389            let mut num_vec = vec![0i64; work_cols];
390            let mut den_vec = vec![1i64; work_cols];
391
392            for j in 0..work_cols {
393                if is_free[j] {
394                    num_vec[j] = if j == f { 1 } else { 0 };
395                    den_vec[j] = 1;
396                } else {
397                    let pr = pivot_row[j] as usize;
398                    let a_pr_j = a_mat[pr][j] as i128;
399                    let a_pr_f = a_mat[pr][f] as i128;
400                    let mut num = -a_pr_f;
401                    let mut den = a_pr_j;
402                    if den < 0 {
403                        num = -num;
404                        den = -den;
405                    }
406                    let g = math_gcd_i128(num, den);
407                    num_vec[j] = check_safe_i128(num / g, "back_substitution")?;
408                    den_vec[j] = check_safe_i128(den / g, "back_substitution")?;
409                }
410            }
411
412            let mut lcm: i128 = 1;
413            for j in 0..work_cols {
414                let d = den_vec[j] as i128;
415                if lcm == 0 || d == 0 {
416                    lcm = 0;
417                } else {
418                    let g = math_gcd_i128(lcm, d);
419                    lcm = check_safe_i128(((lcm / g) * d).abs(), "back_substitution")? as i128;
420                }
421            }
422
423            let mut int_vec = vec![0i64; work_cols];
424            for j in 0..work_cols {
425                let mult = lcm / (den_vec[j] as i128);
426                int_vec[j] = check_safe_i128((num_vec[j] as i128) * mult, "back_substitution")?;
427            }
428            basis_vectors.push(int_vec);
429        }
430    }
431
432    normalize_primitive_basis(&basis_vectors)
433}
434
435
436#[path = "solver_precomputed.rs"]
437mod solver_precomputed;
438#[allow(unused_imports)]
439pub use solver_precomputed::*;
440#[cfg(test)]
441#[path = "solver_tests.rs"]
442mod tests;
443