Advertisement
fivemack

Program with unexpected ub on arm64 Mac

Jan 11th, 2024
1,499
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Rust 4.35 KB | Help | 0 0
  1. ( cargo.toml )
  2. [package]
  3. name = "discrete"
  4. version = "0.1.0"
  5. edition = "2021"
  6.  
  7. # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
  8.  
  9. [dependencies]
  10. bit-set = "0.5.3"
  11. clap = { version = "4.4.14", features = ["derive"] }
  12. clap_derive = { version = "4.0.0-rc.1" }
  13. itertools = "0.12.0"
  14. rayon = "1.8.0"
  15.  
  16. (src/main.rs)
  17. use bit_set::BitSet;
  18. use itertools::Itertools;
  19. use rayon::prelude::*;
  20.  
  21. use core::sync::atomic::*;
  22.  
  23. use clap::Parser;
  24.  
  25. #[derive(Parser, Debug)]
  26. #[command()]
  27. struct Args {
  28.     /// Number of dimensions
  29.     #[arg(short, long, default_value_t = 2)]
  30.     dimensions: usize,
  31.  
  32.     /// Number of points to place
  33.     #[arg(long = "pts", default_value_t = 7)]
  34.     n_pts: usize,
  35.  
  36.     /// Side of hypercube to place points in
  37.     #[arg(long = "side", default_value_t = 7)]
  38.     side: u8,
  39.  
  40.     /// List or count
  41.     #[arg(long = "display", default_value_t = false)]
  42.     display: bool,
  43. }
  44.  
  45. fn dist(u: &[u8], v: &[u8]) -> u16 {
  46.     (u.iter()
  47.         .zip(v.iter())
  48.         .map(|a| ((*a.0 as i16 - *a.1 as i16) * (*a.0 as i16 - *a.1 as i16)))
  49.         .sum::<i16>()) as u16
  50. }
  51.  
  52. fn distances(u: &[Vec<u8>]) -> Vec<u16> {
  53.     u.iter()
  54.         .tuple_combinations::<(_, _)>()
  55.         .map(|a| dist(a.0, a.1))
  56.         .collect()
  57. }
  58.  
  59. fn distance_bitset(u: &[Vec<u8>]) -> BitSet {
  60.     let mut bs = BitSet::new();
  61.     for a in distances(u) {
  62.         bs.insert(a as usize);
  63.     }
  64.     bs
  65. }
  66.  
  67. fn hypercube_points(dim: usize, bound: u8) -> Vec<Vec<u8>> {
  68.     let jj = (1..=dim).map(|_| 0..bound);
  69.     jj.multi_cartesian_product().collect()
  70. }
  71.  
  72. fn extend(v: Vec<Vec<u8>>, target_ln: usize, universe: &[Vec<u8>], actor: &dyn ResultAcceptor) {
  73.     if v.len() == target_ln {
  74.         actor.act(&v);
  75.         return;
  76.     }
  77.     let dd0 = distance_bitset(&v);
  78.     for vx in 0..(*universe).len() {
  79.         let np = &universe[vx];
  80.         let mut nds = dd0.clone();
  81.         let mut ok = true;
  82.         for w in &v {
  83.             let xd = dist(w, np) as usize;
  84.             if nds.contains(xd) {
  85.                 ok = false;
  86.                 break;
  87.             }
  88.             nds.insert(xd);
  89.         }
  90.         if ok {
  91.             let mut nv = v.clone();
  92.             nv.push((*np).clone());
  93.             extend(nv, target_ln, &universe[(1 + vx)..], actor);
  94.         }
  95.     }
  96. }
  97.  
  98. trait ResultAcceptor {
  99.     fn act(&self, v: &[Vec<u8>]);
  100. }
  101.  
  102. struct ResultCounter {
  103.     c: AtomicU64,
  104. }
  105.  
  106. struct ResultPrinter {}
  107.  
  108. impl ResultAcceptor for ResultPrinter {
  109.     fn act(&self, v: &[Vec<u8>]) {
  110.         let mut sds = distances(v);
  111.         sds.sort();
  112.         println!("Found {:?} {:?}", v, sds);
  113.     }
  114. }
  115.  
  116. impl ResultAcceptor for ResultCounter {
  117.     fn act(&self, _v: &[Vec<u8>]) {
  118.         _ = self.c.fetch_add(1, Ordering::SeqCst);
  119.     }
  120. }
  121.  
  122. impl ResultCounter {
  123.     fn new() -> ResultCounter {
  124.         ResultCounter {
  125.             c: AtomicU64::new(0),
  126.         }
  127.     }
  128.     fn get_count(&self) -> u64 {
  129.         self.c.load(Ordering::SeqCst)
  130.     }
  131. }
  132.  
  133. fn main() {
  134.     let args = Args::parse();
  135.  
  136.     let pts = hypercube_points(args.dimensions, args.side);
  137.     let mut tasks = (0..(pts.len() - 1))
  138.         .tuple_combinations::<(_, _)>()
  139.         .collect::<Vec<(usize, usize)>>();
  140.     // par_iter seems to start at the end of the vector
  141.     // and the larger jobs are at the start
  142.     // so to avoid a single-threaded tail this is useful
  143.     tasks.reverse();
  144.  
  145.     let counter = ResultCounter::new();
  146.     let printer = ResultPrinter {};
  147.     if args.display {
  148.         let _ = tasks
  149.             .par_iter()
  150.             .map(|a| {
  151.                 eprint!("  {} {}    \r", a.0, a.1);
  152.                 extend(
  153.                     vec![pts[a.0].clone(), pts[a.1].clone()],
  154.                     args.n_pts,
  155.                     &pts[(1 + a.1)..],
  156.                     &printer,
  157.                 )
  158.             })
  159.             .count();
  160.     } else {
  161.         let _ = tasks
  162.             .par_iter()
  163.             .map(|a| {
  164.                 eprint!("  {} {}    \r", a.0, a.1);
  165.                 extend(
  166.                     vec![pts[a.0].clone(), pts[a.1].clone()],
  167.                     args.n_pts,
  168.                     &pts[(1 + a.1)..],
  169.                     &counter,
  170.                 )
  171.             })
  172.             .count();
  173.     }
  174.     if !args.display {
  175.         println!("\n\n  Found {} answers", counter.get_count());
  176.     }
  177. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement