webrtc_util/fixed_big_int/
mod.rs

1#[cfg(test)]
2mod fixed_big_int_test;
3
4use std::fmt;
5
6// FixedBigInt is the fix-sized multi-word integer.
7pub(crate) struct FixedBigInt {
8    bits: Vec<u64>,
9    n: usize,
10    msb_mask: u64,
11}
12
13impl fmt::Display for FixedBigInt {
14    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
24impl FixedBigInt {
25    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.
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.
78    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.
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}
webrtc_util/fixed_big_int/mod.rs

webrtc_util/fixed_big_int/
mod.rs
