1use std::collections::HashSet;
15
16use crate::cdcl::Lit;
17use crate::modp::{self, ModpEquation};
18
19#[derive(Clone, PartialEq, Eq, Debug)]
22pub struct AffineP {
23 pub p: u64,
24 pub n: usize,
25 pub matrix: Vec<Vec<u64>>,
26 pub translation: Vec<u64>,
27}
28
29impl AffineP {
30 pub fn identity(n: usize, p: u64) -> Self {
32 let matrix = (0..n)
33 .map(|i| (0..n).map(|j| u64::from(i == j)).collect())
34 .collect();
35 AffineP {
36 p,
37 n,
38 matrix,
39 translation: vec![0; n],
40 }
41 }
42
43 pub fn apply(&self, x: &[u64]) -> Vec<u64> {
45 (0..self.n)
46 .map(|i| {
47 let s = (0..self.n).fold(0u64, |a, j| (a + self.matrix[i][j] * x[j]) % self.p);
48 (s + self.translation[i]) % self.p
49 })
50 .collect()
51 }
52
53 pub fn compose(&self, other: &AffineP) -> AffineP {
55 let (p, n) = (self.p, self.n);
56 let mut matrix = vec![vec![0u64; n]; n];
57 for (i, row) in matrix.iter_mut().enumerate() {
58 for (j, cell) in row.iter_mut().enumerate() {
59 *cell = (0..n).fold(0u64, |a, k| {
60 (a + self.matrix[i][k] * other.matrix[k][j]) % p
61 });
62 }
63 }
64 let translation = (0..n)
65 .map(|i| {
66 let av = (0..n).fold(0u64, |a, k| {
67 (a + self.matrix[i][k] * other.translation[k]) % p
68 });
69 (av + self.translation[i]) % p
70 })
71 .collect();
72 AffineP {
73 p,
74 n,
75 matrix,
76 translation,
77 }
78 }
79
80 pub fn is_bijection(&self) -> bool {
82 modp::is_invertible_modp(self.n, self.p, &self.matrix)
83 }
84
85 pub fn is_monomial(&self) -> bool {
88 let n = self.n;
89 let rows = self
90 .matrix
91 .iter()
92 .all(|r| r.iter().filter(|&&x| x != 0).count() == 1);
93 let cols = (0..n).all(|j| (0..n).filter(|&i| self.matrix[i][j] != 0).count() == 1);
94 rows && cols
95 }
96}
97
98pub fn agl_p_order(n: u32, p: u64) -> u128 {
100 (p as u128).pow(n) * modp::gl_order_p(n, p)
101}
102
103pub fn all_affine_p_bijections(n: usize, p: u64) -> Vec<AffineP> {
106 assert!(
107 (p as u128).pow((n * n) as u32) <= 200_000,
108 "exhaustive AGL(n,p) enumeration is bounded (p^{{n²}} ≤ 200k)"
109 );
110 let decode = |mut code: u64, len: usize| -> Vec<u64> {
111 (0..len)
112 .map(|_| {
113 let d = code % p;
114 code /= p;
115 d
116 })
117 .collect()
118 };
119 let mut out = Vec::new();
120 let matrices = (p).pow((n * n) as u32);
121 let translations = (p).pow(n as u32);
122 for code in 0..matrices {
123 let flat = decode(code, n * n);
124 let matrix: Vec<Vec<u64>> = (0..n).map(|i| flat[i * n..(i + 1) * n].to_vec()).collect();
125 if !modp::is_invertible_modp(n, p, &matrix) {
126 continue;
127 }
128 for tcode in 0..translations {
129 out.push(AffineP {
130 p,
131 n,
132 matrix: matrix.clone(),
133 translation: decode(tcode, n),
134 });
135 }
136 }
137 out
138}
139
140pub fn models_p(n: usize, p: u64, equations: &[ModpEquation]) -> Vec<Vec<u64>> {
143 assert!(
144 (p as u128).pow(n as u32) <= 60_000,
145 "model enumeration is brute force — small n"
146 );
147 let total = p.pow(n as u32);
148 (0..total)
149 .filter_map(|code| {
150 let mut c = code;
151 let x: Vec<u64> = (0..n)
152 .map(|_| {
153 let d = c % p;
154 c /= p;
155 d
156 })
157 .collect();
158 equations
159 .iter()
160 .all(|eq| {
161 eq.coeffs
162 .iter()
163 .fold(0u64, |a, &(v, co)| (a + co * x[v]) % p)
164 % p
165 == eq.rhs % p
166 })
167 .then_some(x)
168 })
169 .collect()
170}
171
172pub fn affine_p_symmetries(n: usize, p: u64, models: &[Vec<u64>]) -> Vec<AffineP> {
176 let set: HashSet<Vec<u64>> = models.iter().cloned().collect();
177 all_affine_p_bijections(n, p)
178 .into_iter()
179 .filter(|phi| set.iter().all(|m| set.contains(&phi.apply(m))))
180 .collect()
181}
182
183pub fn affine_p_refutation_drat(
190 num_bool_vars: usize,
191 clauses: &[Vec<Lit>],
192) -> Option<Vec<Vec<Lit>>> {
193 crate::xor_drat::emit_modp_drat(num_bool_vars, clauses)
194}
195
196pub enum AffinePForced {
198 Refuted(Option<Vec<Vec<Lit>>>),
200 Forced(Vec<Vec<Lit>>),
202 Unchanged,
204}
205
206fn gfp_mul(a: u64, b: u64, p: u64) -> u64 {
208 (a % p) * (b % p) % p
209}
210fn gfp_sub(a: u64, b: u64, p: u64) -> u64 {
211 (a % p + p - b % p) % p
212}
213fn gfp_inv(a: u64, p: u64) -> u64 {
214 let (mut result, mut base, mut exp) = (1u64, a % p, p - 2);
215 while exp > 0 {
216 if exp & 1 == 1 {
217 result = gfp_mul(result, base, p);
218 }
219 base = gfp_mul(base, base, p);
220 exp >>= 1;
221 }
222 result
223}
224
225pub fn affine_p_forced(num_bool_vars: usize, clauses: &[Vec<Lit>]) -> AffinePForced {
240 let Some(rec) = modp::recover_from_cnf(num_bool_vars, clauses) else {
241 return AffinePForced::Unchanged;
242 };
243 if !modp::is_prime(rec.modulus) {
244 return AffinePForced::Unchanged; }
246 let Some(ss) = modp::solve_space(&rec.equations, rec.num_vars, rec.modulus) else {
247 return AffinePForced::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
248 };
249 let p = rec.modulus;
250 let key = |c: &[Lit]| -> Vec<(u32, bool)> {
251 let mut k: Vec<(u32, bool)> = c.iter().map(|l| (l.var(), l.is_positive())).collect();
252 k.sort_unstable();
253 k
254 };
255 let existing: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| key(c)).collect();
256 let mut out: Vec<Vec<Lit>> = Vec::new();
257 let mut push_new = |c: Vec<Lit>| {
258 if !existing.contains(&key(&c)) {
259 out.push(c);
260 }
261 };
262 let col = |g: usize| -> Vec<u64> { ss.kernel_basis.iter().map(|kv| kv[g]).collect() };
264
265 let mut classes: std::collections::HashMap<Vec<u64>, Vec<usize>> =
268 std::collections::HashMap::new();
269 for g in 0..rec.num_vars {
270 let c = col(g);
271 if c.iter().all(|&x| x == 0) {
272 let val = ss.particular[g];
273 for (v, &bvar) in rec.groups[g].iter().enumerate() {
274 push_new(vec![if v as u64 == val {
275 Lit::pos(bvar)
276 } else {
277 Lit::neg(bvar)
278 }]);
279 }
280 } else {
281 let scale = gfp_inv(*c.iter().find(|&&x| x != 0).unwrap(), p); classes
283 .entry(c.iter().map(|&x| gfp_mul(x, scale, p)).collect())
284 .or_default()
285 .push(g);
286 }
287 }
288 let mut class_list: Vec<Vec<usize>> = classes
289 .into_values()
290 .map(|mut v| {
291 v.sort_unstable();
292 v
293 })
294 .collect();
295 class_list.sort_unstable_by_key(|c| c[0]);
296 for members in &class_list {
297 if members.len() < 2 {
298 continue; }
300 let rep = members[0];
301 let s_rep = *col(rep).iter().find(|&&x| x != 0).unwrap();
302 for &g in &members[1..] {
303 let s_g = *col(g).iter().find(|&&x| x != 0).unwrap();
304 let c_g = gfp_mul(s_g, gfp_inv(s_rep, p), p); let d_g = gfp_sub(ss.particular[g], gfp_mul(c_g, ss.particular[rep], p), p);
306 let inv_c = gfp_inv(c_g, p);
307 for v in 0..p {
308 let sv = gfp_mul(gfp_sub(v, d_g, p), inv_c, p); let (bg, br) = (rec.groups[g][v as usize], rec.groups[rep][sv as usize]);
310 push_new(vec![Lit::neg(bg), Lit::pos(br)]);
311 push_new(vec![Lit::pos(bg), Lit::neg(br)]);
312 }
313 }
314 }
315
316 if out.is_empty() {
317 AffinePForced::Unchanged
318 } else {
319 AffinePForced::Forced(out)
320 }
321}
322
323pub fn agl_m_order(n: u32, m: u64) -> Option<u128> {
326 Some(
327 crate::modm::squarefree_primes(m)?
328 .iter()
329 .map(|&p| agl_p_order(n, p))
330 .product(),
331 )
332}
333
334fn crt_combine(residues: &[(u64, u64)]) -> (u64, u64) {
336 let (mut acc_r, mut acc_m): (i128, i128) = (0, 1);
337 for &(r, modu) in residues {
338 let modu = modu as i128;
339 let diff = (r as i128 - acc_r).rem_euclid(modu);
340 let t = (diff * mod_inverse(acc_m.rem_euclid(modu) as u64, modu as u64) as i128)
341 .rem_euclid(modu);
342 acc_r += acc_m * t;
343 acc_m *= modu;
344 acc_r = acc_r.rem_euclid(acc_m);
345 }
346 (acc_r as u64, acc_m as u64)
347}
348
349fn mod_inverse(a: u64, m: u64) -> u64 {
351 let (mut old_r, mut r): (i128, i128) = (a as i128, m as i128);
352 let (mut old_s, mut s): (i128, i128) = (1, 0);
353 while r != 0 {
354 let q = old_r / r;
355 (old_r, r) = (r, old_r - q * r);
356 (old_s, s) = (s, old_s - q * s);
357 }
358 old_s.rem_euclid(m as i128) as u64
359}
360
361pub fn affine_m_forced(num_bool_vars: usize, clauses: &[Vec<Lit>]) -> AffinePForced {
375 let Some(rec) = modp::recover_from_cnf(num_bool_vars, clauses) else {
376 return AffinePForced::Unchanged;
377 };
378 let m = rec.modulus;
379 if modp::is_prime(m) {
380 return AffinePForced::Unchanged; }
382 let Some(primes) = crate::modm::squarefree_primes(m) else {
383 return prime_power_forced(num_bool_vars, &rec, clauses); };
385 let mut spaces: Vec<crate::modp::SolutionSpaceP> = Vec::with_capacity(primes.len());
386 for &p in &primes {
387 let Some(ss) = modp::solve_space(&rec.equations, rec.num_vars, p) else {
388 return AffinePForced::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
389 };
390 spaces.push(ss);
391 }
392
393 let key = |c: &[Lit]| -> Vec<(u32, bool)> {
394 let mut k: Vec<(u32, bool)> = c.iter().map(|l| (l.var(), l.is_positive())).collect();
395 k.sort_unstable();
396 k
397 };
398 let existing: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| key(c)).collect();
399 let mut out: Vec<Vec<Lit>> = Vec::new();
400 let push_new = |c: Vec<Lit>, out: &mut Vec<Vec<Lit>>| {
401 if !existing.contains(&key(&c)) {
402 out.push(c);
403 }
404 };
405 let col = |i: usize, g: usize| -> Vec<u64> {
406 spaces[i].kernel_basis.iter().map(|kk| kk[g]).collect()
407 };
408 let forced_res = |i: usize, g: usize| -> Option<u64> {
409 col(i, g)
410 .iter()
411 .all(|&x| x == 0)
412 .then(|| spaces[i].particular[g])
413 };
414
415 for g in 0..rec.num_vars {
417 let constraints: Vec<(u64, u64)> = primes
418 .iter()
419 .enumerate()
420 .filter_map(|(i, &p)| forced_res(i, g).map(|v| (v, p)))
421 .collect();
422 if constraints.is_empty() {
423 continue;
424 }
425 let (res, q) = crt_combine(&constraints);
426 let fully = constraints.len() == primes.len();
427 for (v, &bvar) in rec.groups[g].iter().enumerate() {
428 if (v as u64) % q != res {
429 push_new(vec![Lit::neg(bvar)], &mut out); } else if fully {
431 push_new(vec![Lit::pos(bvar)], &mut out); }
433 }
434 }
435
436 let mut classes: std::collections::HashMap<Vec<Vec<u64>>, Vec<usize>> =
438 std::collections::HashMap::new();
439 for g in 0..rec.num_vars {
440 if (0..primes.len()).any(|i| forced_res(i, g).is_some()) {
441 continue;
442 }
443 let sig: Vec<Vec<u64>> = (0..primes.len())
444 .map(|i| {
445 let (p, c) = (primes[i], col(i, g));
446 let s = gfp_inv(*c.iter().find(|&&x| x != 0).unwrap(), p);
447 c.iter().map(|&x| gfp_mul(x, s, p)).collect()
448 })
449 .collect();
450 classes.entry(sig).or_default().push(g);
451 }
452 let mut class_list: Vec<Vec<usize>> = classes
453 .into_values()
454 .map(|mut v| {
455 v.sort_unstable();
456 v
457 })
458 .collect();
459 class_list.sort_unstable_by_key(|c| c[0]);
460 for members in &class_list {
461 if members.len() < 2 {
462 continue;
463 }
464 let rep = members[0];
465 for &g in &members[1..] {
466 let (mut cs, mut ds): (Vec<(u64, u64)>, Vec<(u64, u64)>) = (Vec::new(), Vec::new());
467 for (i, &p) in primes.iter().enumerate() {
468 let s_rep = *col(i, rep).iter().find(|&&x| x != 0).unwrap();
469 let s_g = *col(i, g).iter().find(|&&x| x != 0).unwrap();
470 let c_i = gfp_mul(s_g, gfp_inv(s_rep, p), p);
471 let d_i = gfp_sub(
472 spaces[i].particular[g],
473 gfp_mul(c_i, spaces[i].particular[rep], p),
474 p,
475 );
476 cs.push((c_i, p));
477 ds.push((d_i, p));
478 }
479 let (c, _) = crt_combine(&cs);
480 let (d, _) = crt_combine(&ds);
481 let inv_c = mod_inverse(c, m);
482 for v in 0..m {
483 let sv = ((v + m - d) % m) * inv_c % m; let (bg, br) = (rec.groups[g][v as usize], rec.groups[rep][sv as usize]);
485 push_new(vec![Lit::neg(bg), Lit::pos(br)], &mut out);
486 push_new(vec![Lit::pos(bg), Lit::neg(br)], &mut out);
487 }
488 }
489 }
490
491 if out.is_empty() {
492 AffinePForced::Unchanged
493 } else {
494 AffinePForced::Forced(out)
495 }
496}
497
498fn gcd_u64(mut a: u64, mut b: u64) -> u64 {
500 while b != 0 {
501 (a, b) = (b, a % b);
502 }
503 a
504}
505
506fn cg_mul(a: u64, b: u64, q: u64) -> u64 {
508 a % q * (b % q) % q
509}
510
511fn kcol(ss: &crate::modm::SolutionSpaceM, g: usize) -> Vec<u64> {
513 ss.kernel_basis.iter().map(|kk| kk[g]).collect()
514}
515
516struct BreakStructure {
521 residue: Vec<(u64, u64)>,
522 link: Vec<Option<(usize, u64, u64)>>,
523}
524
525enum BreakOutcome {
526 Inconsistent,
527 Structure(BreakStructure),
528}
529
530fn composite_break_structure(
532 eqs: &[ModpEquation],
533 num_vars: usize,
534 m: u64,
535) -> Option<BreakOutcome> {
536 use crate::modm::PrimePowerSpace;
537 let factors = crate::modm::prime_power_factorize(m)?;
538 let mut spaces: Vec<(u64, u64, crate::modm::SolutionSpaceM)> =
539 Vec::with_capacity(factors.len());
540 for (p, k) in factors {
541 match crate::modm::solve_space_prime_power(eqs, num_vars, p, k) {
542 None => return None,
543 Some(PrimePowerSpace::Inconsistent) => return Some(BreakOutcome::Inconsistent),
544 Some(PrimePowerSpace::Space(ss)) => spaces.push((p, p.pow(k), ss)),
545 }
546 }
547
548 let residue: Vec<(u64, u64)> = (0..num_vars)
550 .map(|g| {
551 let pairs: Vec<(u64, u64)> = spaces
552 .iter()
553 .filter_map(|(_, q, ss)| {
554 let d = kcol(ss, g).iter().fold(*q, |acc, &x| gcd_u64(acc, x));
555 (d > 1).then(|| (ss.particular[g] % d, d))
556 })
557 .collect();
558 if pairs.is_empty() {
559 (0, 1)
560 } else {
561 (
562 crt_combine(&pairs).0,
563 pairs.iter().map(|&(_, d)| d).product(),
564 )
565 }
566 })
567 .collect();
568
569 let mut classes: std::collections::HashMap<Vec<Vec<u64>>, Vec<usize>> =
571 std::collections::HashMap::new();
572 'g: for g in 0..num_vars {
573 let mut sig: Vec<Vec<u64>> = Vec::with_capacity(spaces.len());
574 for (p, q, ss) in &spaces {
575 let c = kcol(ss, g);
576 let Some(piv) = c.iter().position(|&x| x % p != 0) else {
577 continue 'g;
578 };
579 let inv = mod_inverse(c[piv], *q);
580 sig.push(c.iter().map(|&x| x * inv % q).collect());
581 }
582 classes.entry(sig).or_default().push(g);
583 }
584 let mut link = vec![None; num_vars];
585 let mut class_list: Vec<Vec<usize>> = classes
586 .into_values()
587 .map(|mut v| {
588 v.sort_unstable();
589 v
590 })
591 .collect();
592 class_list.sort_unstable_by_key(|c| c[0]);
593 for members in &class_list {
594 if members.len() < 2 {
595 continue;
596 }
597 let rep = members[0];
598 for &g in &members[1..] {
599 let (mut cs, mut ds): (Vec<(u64, u64)>, Vec<(u64, u64)>) = (Vec::new(), Vec::new());
600 for (p, q, ss) in &spaces {
601 let (cg, cr) = (kcol(ss, g), kcol(ss, rep));
602 let piv = cr.iter().position(|&x| x % p != 0).unwrap();
603 let c_c = cg[piv] * mod_inverse(cr[piv], *q) % q;
604 let d_c = (ss.particular[g] + q - cg_mul(c_c, ss.particular[rep], *q)) % q;
605 cs.push((c_c, *q));
606 ds.push((d_c, *q));
607 }
608 link[g] = Some((rep, crt_combine(&cs).0, crt_combine(&ds).0));
609 }
610 }
611
612 Some(BreakOutcome::Structure(BreakStructure { residue, link }))
613}
614
615fn prime_power_forced(
620 num_bool_vars: usize,
621 rec: &modp::ModpRecovery,
622 clauses: &[Vec<Lit>],
623) -> AffinePForced {
624 let m = rec.modulus;
625 let st = match composite_break_structure(&rec.equations, rec.num_vars, m) {
626 None => return AffinePForced::Unchanged,
627 Some(BreakOutcome::Inconsistent) => {
628 return AffinePForced::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
629 }
630 Some(BreakOutcome::Structure(s)) => s,
631 };
632 let key = |c: &[Lit]| -> Vec<(u32, bool)> {
633 let mut k: Vec<(u32, bool)> = c.iter().map(|l| (l.var(), l.is_positive())).collect();
634 k.sort_unstable();
635 k
636 };
637 let existing: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| key(c)).collect();
638 let mut out: Vec<Vec<Lit>> = Vec::new();
639 let push_new = |c: Vec<Lit>, out: &mut Vec<Vec<Lit>>| {
640 if !existing.contains(&key(&c)) {
641 out.push(c);
642 }
643 };
644 for (g, &(res, modu)) in st.residue.iter().enumerate() {
645 if modu <= 1 {
646 continue;
647 }
648 for (v, &bvar) in rec.groups[g].iter().enumerate() {
649 if (v as u64) % modu != res {
650 push_new(vec![Lit::neg(bvar)], &mut out);
651 } else if modu == m {
652 push_new(vec![Lit::pos(bvar)], &mut out);
653 }
654 }
655 }
656 for g in 0..rec.num_vars {
657 if let Some((rep, c, d)) = st.link[g] {
658 let inv_c = mod_inverse(c, m);
659 for v in 0..m {
660 let sv = (v + m - d) % m * inv_c % m;
661 let (bg, br) = (rec.groups[g][v as usize], rec.groups[rep][sv as usize]);
662 push_new(vec![Lit::neg(bg), Lit::pos(br)], &mut out);
663 push_new(vec![Lit::pos(bg), Lit::neg(br)], &mut out);
664 }
665 }
666 }
667 if out.is_empty() {
668 AffinePForced::Unchanged
669 } else {
670 AffinePForced::Forced(out)
671 }
672}
673
674#[derive(Clone, Debug)]
676enum BoolSub {
677 Const(bool),
679 Survive(u32),
681 Alias(u32),
684}
685
686#[derive(Clone, Debug)]
688pub struct AffinePCanonical {
689 pub num_vars: usize,
690 pub clauses: Vec<Vec<Lit>>,
691 sub: Vec<BoolSub>,
692}
693
694impl AffinePCanonical {
695 pub fn lift(&self, reduced_model: &[bool]) -> Vec<bool> {
697 self.sub
698 .iter()
699 .map(|s| match *s {
700 BoolSub::Const(c) => c,
701 BoolSub::Survive(ni) | BoolSub::Alias(ni) => reduced_model[ni as usize],
702 })
703 .collect()
704 }
705}
706
707pub enum AffinePCanon {
709 Refuted(Option<Vec<Vec<Lit>>>),
710 Canonical(AffinePCanonical),
711 Unchanged,
712}
713
714pub fn affine_p_canonicalize(num_bool_vars: usize, clauses: &[Vec<Lit>]) -> AffinePCanon {
722 let Some(rec) = modp::recover_from_cnf(num_bool_vars, clauses) else {
723 return AffinePCanon::Unchanged;
724 };
725 let p = rec.modulus;
726 if !modp::is_prime(p) {
727 return AffinePCanon::Unchanged;
728 }
729 let Some(ss) = modp::solve_space(&rec.equations, rec.num_vars, p) else {
730 return AffinePCanon::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
731 };
732
733 enum Role {
735 Forced(u64),
736 Survive,
737 Linked { rep: usize, c: u64, d: u64 },
738 }
739 let col = |g: usize| -> Vec<u64> { ss.kernel_basis.iter().map(|k| k[g]).collect() };
740 let mut role: Vec<Role> = Vec::with_capacity(rec.num_vars);
741 let mut classes: std::collections::HashMap<Vec<u64>, Vec<usize>> =
742 std::collections::HashMap::new();
743 for g in 0..rec.num_vars {
744 let c = col(g);
745 if c.iter().all(|&x| x == 0) {
746 role.push(Role::Forced(ss.particular[g]));
747 } else {
748 let s = gfp_inv(*c.iter().find(|&&x| x != 0).unwrap(), p);
749 classes
750 .entry(c.iter().map(|&x| gfp_mul(x, s, p)).collect())
751 .or_default()
752 .push(g);
753 role.push(Role::Survive); }
755 }
756 for members in classes.values() {
757 let mut ms = members.clone();
758 ms.sort_unstable();
759 let rep = ms[0];
760 let s_rep = *col(rep).iter().find(|&&x| x != 0).unwrap();
761 for &g in &ms[1..] {
762 let s_g = *col(g).iter().find(|&&x| x != 0).unwrap();
763 let c = gfp_mul(s_g, gfp_inv(s_rep, p), p);
764 let d = gfp_sub(ss.particular[g], gfp_mul(c, ss.particular[rep], p), p);
765 role[g] = Role::Linked { rep, c, d };
766 }
767 }
768
769 let mut in_group = vec![false; num_bool_vars];
771 for grp in &rec.groups {
772 for &b in grp {
773 in_group[b as usize] = true;
774 }
775 }
776 let mut new_idx: Vec<Option<u32>> = vec![None; num_bool_vars];
777 let mut next = 0u32;
778 for g in 0..rec.num_vars {
779 if matches!(role[g], Role::Survive) {
780 for &b in &rec.groups[g] {
781 new_idx[b as usize] = Some(next);
782 next += 1;
783 }
784 }
785 }
786 for (b, slot) in new_idx.iter_mut().enumerate() {
787 if !in_group[b] {
788 *slot = Some(next);
789 next += 1;
790 }
791 }
792 let reduced_nv = next as usize;
793
794 let mut sub = vec![BoolSub::Const(false); num_bool_vars];
796 for (b, slot) in new_idx.iter().enumerate() {
797 if let Some(ni) = slot {
798 sub[b] = BoolSub::Survive(*ni); }
800 }
801 for g in 0..rec.num_vars {
802 match role[g] {
803 Role::Forced(val) => {
804 for (v, &b) in rec.groups[g].iter().enumerate() {
805 sub[b as usize] = BoolSub::Const(v as u64 == val);
806 }
807 }
808 Role::Survive => {} Role::Linked { rep, c, d } => {
810 let inv_c = gfp_inv(c, p);
811 for (v, &b) in rec.groups[g].iter().enumerate() {
812 let sv = gfp_mul(gfp_sub(v as u64, d, p), inv_c, p); let rep_b = rec.groups[rep][sv as usize];
814 sub[b as usize] = BoolSub::Alias(new_idx[rep_b as usize].unwrap());
815 }
816 }
817 }
818 }
819 if !sub
820 .iter()
821 .any(|s| matches!(s, BoolSub::Const(_) | BoolSub::Alias(_)))
822 {
823 return AffinePCanon::Unchanged; }
825
826 let mut out: Vec<Vec<Lit>> = Vec::new();
828 'clause: for c in clauses {
829 let mut seen: std::collections::HashMap<u32, bool> = std::collections::HashMap::new();
830 let mut lits: Vec<Lit> = Vec::new();
831 for l in c {
832 let (ni, pol) = match sub[l.var() as usize] {
833 BoolSub::Const(cst) => {
834 if cst == l.is_positive() {
835 continue 'clause; }
837 continue; }
839 BoolSub::Survive(ni) | BoolSub::Alias(ni) => (ni, l.is_positive()),
840 };
841 match seen.get(&ni) {
842 Some(&prev) if prev != pol => continue 'clause, Some(_) => continue, None => {
845 seen.insert(ni, pol);
846 lits.push(Lit::new(ni, pol));
847 }
848 }
849 }
850 out.push(lits);
851 }
852 AffinePCanon::Canonical(AffinePCanonical {
853 num_vars: reduced_nv,
854 clauses: out,
855 sub,
856 })
857}
858
859pub fn affine_m_canonicalize(num_bool_vars: usize, clauses: &[Vec<Lit>]) -> AffinePCanon {
869 let Some(rec) = modp::recover_from_cnf(num_bool_vars, clauses) else {
870 return AffinePCanon::Unchanged;
871 };
872 let m = rec.modulus;
873 if modp::is_prime(m) {
874 return AffinePCanon::Unchanged; }
876 let st = match composite_break_structure(&rec.equations, rec.num_vars, m) {
877 None => return AffinePCanon::Unchanged,
878 Some(BreakOutcome::Inconsistent) => {
879 return AffinePCanon::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
880 }
881 Some(BreakOutcome::Structure(s)) => s,
882 };
883
884 enum Role {
885 Forced(u64),
886 Partial { res: u64, modu: u64 },
887 Survive,
888 Linked { rep: usize, c: u64, d: u64 },
889 }
890 let role: Vec<Role> = (0..rec.num_vars)
891 .map(|g| {
892 let (res, modu) = st.residue[g];
893 if modu == m {
894 Role::Forced(res)
895 } else if modu > 1 {
896 Role::Partial { res, modu }
897 } else if let Some((rep, c, d)) = st.link[g] {
898 Role::Linked { rep, c, d }
899 } else {
900 Role::Survive
901 }
902 })
903 .collect();
904
905 let mut in_group = vec![false; num_bool_vars];
908 for grp in &rec.groups {
909 for &b in grp {
910 in_group[b as usize] = true;
911 }
912 }
913 let mut new_idx: Vec<Option<u32>> = vec![None; num_bool_vars];
914 let mut next = 0u32;
915 for g in 0..rec.num_vars {
916 match role[g] {
917 Role::Survive => {
918 for &b in &rec.groups[g] {
919 new_idx[b as usize] = Some(next);
920 next += 1;
921 }
922 }
923 Role::Partial { res, modu } => {
924 for (v, &b) in rec.groups[g].iter().enumerate() {
925 if (v as u64) % modu == res {
926 new_idx[b as usize] = Some(next);
927 next += 1;
928 }
929 }
930 }
931 _ => {}
932 }
933 }
934 for (b, slot) in new_idx.iter_mut().enumerate() {
935 if !in_group[b] {
936 *slot = Some(next);
937 next += 1;
938 }
939 }
940 let reduced_nv = next as usize;
941
942 let mut sub = vec![BoolSub::Const(false); num_bool_vars];
945 for (b, slot) in new_idx.iter().enumerate() {
946 if let Some(ni) = slot {
947 sub[b] = BoolSub::Survive(*ni);
948 }
949 }
950 for g in 0..rec.num_vars {
951 match role[g] {
952 Role::Forced(val) => {
953 for (v, &b) in rec.groups[g].iter().enumerate() {
954 sub[b as usize] = BoolSub::Const(v as u64 == val);
955 }
956 }
957 Role::Partial { .. } | Role::Survive => {} Role::Linked { rep, c, d } => {
959 let inv_c = mod_inverse(c, m);
960 for (v, &b) in rec.groups[g].iter().enumerate() {
961 let sv = (v as u64 + m - d) % m * inv_c % m; let rep_b = rec.groups[rep][sv as usize];
963 sub[b as usize] = BoolSub::Alias(new_idx[rep_b as usize].unwrap());
964 }
965 }
966 }
967 }
968 if !sub
969 .iter()
970 .any(|s| matches!(s, BoolSub::Const(_) | BoolSub::Alias(_)))
971 {
972 return AffinePCanon::Unchanged; }
974
975 let mut out: Vec<Vec<Lit>> = Vec::new();
977 'clause: for c in clauses {
978 let mut seen: std::collections::HashMap<u32, bool> = std::collections::HashMap::new();
979 let mut lits: Vec<Lit> = Vec::new();
980 for l in c {
981 let (ni, pol) = match sub[l.var() as usize] {
982 BoolSub::Const(cst) => {
983 if cst == l.is_positive() {
984 continue 'clause; }
986 continue; }
988 BoolSub::Survive(ni) | BoolSub::Alias(ni) => (ni, l.is_positive()),
989 };
990 match seen.get(&ni) {
991 Some(&prev) if prev != pol => continue 'clause, Some(_) => continue, None => {
994 seen.insert(ni, pol);
995 lits.push(Lit::new(ni, pol));
996 }
997 }
998 }
999 out.push(lits);
1000 }
1001 AffinePCanon::Canonical(AffinePCanonical {
1002 num_vars: reduced_nv,
1003 clauses: out,
1004 sub,
1005 })
1006}
1007
1008#[cfg(test)]
1009#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/affine_gfp/tests.rs"]
1010mod tests;