xref: /webrtc/util/src/fixed_big_int/mod.rs (revision 5d8fe953) 
1 #[cfg(test)]
2 mod fixed_big_int_test;
3 
4 use std::fmt;
5 
6 // FixedBigInt is the fix-sized multi-word integer.
7 pub(crate) struct FixedBigInt {
8     bits: Vec<u64>,
9     n: usize,
10     msb_mask: u64,
11 }
12 
13 impl fmt::Display for FixedBigInt {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result14     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
15         let mut out = String::new();
16         for i in (0..self.bits.len()).rev() {
17             out += format!("{:016X}", self.bits[i]).as_str();
18         }
19 
20         write!(f, "{out}")
21     }
22 }
23 
24 impl FixedBigInt {
new(n: usize) -> Self25     pub(crate) fn new(n: usize) -> Self {
26         let mut chunk_size = (n + 63) / 64;
27         if chunk_size == 0 {
28             chunk_size = 1;
29         }
30 
31         FixedBigInt {
32             bits: vec![0; chunk_size],
33             n,
34             msb_mask: if n % 64 == 0 {
35                 u64::MAX
36             } else {
37                 (1 << (64 - n % 64)) - 1
38             },
39         }
40     }
41 
42     // lsh is the left shift operation.
lsh(&mut self, n: usize)43     pub(crate) fn lsh(&mut self, n: usize) {
44         if n == 0 {
45             return;
46         }
47         let n_chunk = (n / 64) as isize;
48         let n_n = n % 64;
49 
50         for i in (0..self.bits.len() as isize).rev() {
51             let mut carry: u64 = 0;
52             if i - n_chunk >= 0 {
53                 carry = if n_n >= 64 {
54                     0
55                 } else {
56                     self.bits[(i - n_chunk) as usize] << n_n
57                 };
58                 if i - n_chunk > 0 {
59                     carry |= if n_n == 0 {
60                         0
61                     } else {
62                         self.bits[(i - n_chunk - 1) as usize] >> (64 - n_n)
63                     };
64                 }
65             }
66             self.bits[i as usize] = if n >= 64 {
67                 carry
68             } else {
69                 (self.bits[i as usize] << n) | carry
70             };
71         }
72 
73         let last = self.bits.len() - 1;
74         self.bits[last] &= self.msb_mask;
75     }
76 
77     // bit returns i-th bit of the fixedBigInt.
bit(&self, i: usize) -> usize78     pub(crate) fn bit(&self, i: usize) -> usize {
79         if i >= self.n {
80             return 0;
81         }
82         let chunk = i / 64;
83         let pos = i % 64;
84         usize::from(self.bits[chunk] & (1 << pos) != 0)
85     }
86 
87     // set_bit sets i-th bit to 1.
set_bit(&mut self, i: usize)88     pub(crate) fn set_bit(&mut self, i: usize) {
89         if i >= self.n {
90             return;
91         }
92         let chunk = i / 64;
93         let pos = i % 64;
94         self.bits[chunk] |= 1 << pos;
95     }
96 }
97