1use std::os::unix::thread;
 2
 3use rand::{thread_rng, Rng};
 4
 5fn decomposer(mut value: u64, q: u64, d: usize, logb: u64) -> Vec<u64> {
 6    let b = 1u64 << logb;
 7    let full_mask = b - 1u64;
 8    let bby2 = b >> 1;
 9
10    if value >= (q >> 1) {
11        value = !(q - value) + 1;
12    }
13
14    // let mut carry = 0;
15    // let mut out = Vec::with_capacity(d);
16    // for _ in 0..d {
17    //     let k_i = carry + (value & full_mask);
18    //     value = (value) >> logb;
19    //     if k_i > bby2 {
20    //         // if (k_i == bby2 && ((value & 1) == 1)) {
21    //         //     println!("AA");
22    //         // }
23    //         out.push(q - (b - k_i));
24    //         carry = 1;
25    //     } else {
26    //         // if (k_i == bby2) {
27    //         //     println!("BB");
28    //         // }
29    //         out.push(k_i);
30    //         carry = 0;
31    //     }
32    // }
33    // return out;
34
35    let mut out = Vec::with_capacity(d);
36    for _ in 0..d {
37        let k_i = value & full_mask;
38        value = (value - k_i) >> logb;
39
40        if k_i > bby2 || (k_i == bby2 && ((value & 1) == 1)) {
41            // if (k_i == bby2 && ((value & 1) == 1)) {
42            //     println!("AA");
43            // }
44            out.push(q - (b - k_i));
45            value += 1;
46        } else {
47            // if (k_i == bby2) {
48            //     println!("BB");
49            // }
50            out.push(k_i);
51        }
52    }
53
54    return out;
55}
56
57fn recompose(limbs: &[u64], q: u64, logb: u64) -> u64 {
58    let mut out = 0;
59    limbs.iter().enumerate().for_each(|(i, l)| {
60        let a = 1u128 << (logb * (i as u64));
61        let a = ((a * (*l as u128)) % (q as u128)) as u64;
62        out = (out + a) % q;
63    });
64    out % q
65}
66
67fn main() {
68    // let mut v = Vec::with_capacity(10);
69    // v[0] = 1;
70    // println!("Hello, world!");
71
72    let mut rng = thread_rng();
73
74    let q = 36028797018820609u64;
75    let logb = 11;
76    let d = 5;
77
78    for _ in 0..100000 {
79        let value = rng.gen_range(0..q);
80        let limbs = decomposer(value, q, d, logb);
81        // println!("{:?}", &limbs);
82        let value_back = recompose(&limbs, q, logb);
83        assert_eq!(value, value_back)
84    }
85}