1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

#[cfg(test)]
mod fixed_big_int_test;

use std::fmt;

// FixedBigInt is the fix-sized multi-word integer.
pub(crate) struct FixedBigInt {
    bits: Vec<u64>,
    n: usize,
    msb_mask: u64,
}

impl fmt::Display for FixedBigInt {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut out = String::new();
        for i in (0..self.bits.len()).rev() {
            out += format!("{:016X}", self.bits[i]).as_str();
        }

        write!(f, "{}", out)
    }
}

impl FixedBigInt {
    pub(crate) fn new(n: usize) -> Self {
        let mut chunk_size = (n + 63) / 64;
        if chunk_size == 0 {
            chunk_size = 1;
        }

        FixedBigInt {
            bits: vec![0; chunk_size],
            n,
            msb_mask: if n % 64 == 0 {
                u64::MAX
            } else {
                (1 << (64 - n % 64)) - 1
            },
        }
    }

    // lsh is the left shift operation.
    pub(crate) fn lsh(&mut self, n: usize) {
        if n == 0 {
            return;
        }
        let n_chunk = (n / 64) as isize;
        let n_n = n % 64;

        for i in (0..self.bits.len() as isize).rev() {
            let mut carry: u64 = 0;
            if i - n_chunk >= 0 {
                carry = if n_n >= 64 {
                    0
                } else {
                    self.bits[(i - n_chunk) as usize] << n_n
                };
                if i - n_chunk > 0 {
                    carry |= if n_n == 0 {
                        0
                    } else {
                        self.bits[(i - n_chunk - 1) as usize] >> (64 - n_n)
                    };
                }
            }
            self.bits[i as usize] = if n >= 64 {
                carry
            } else {
                (self.bits[i as usize] << n) | carry
            };
        }

        let last = self.bits.len() - 1;
        self.bits[last] &= self.msb_mask;
    }

    // bit returns i-th bit of the fixedBigInt.
    pub(crate) fn bit(&self, i: usize) -> usize {
        if i >= self.n {
            return 0;
        }
        let chunk = i / 64;
        let pos = i % 64;
        if self.bits[chunk] & (1 << pos) != 0 {
            1
        } else {
            0
        }
    }

    // set_bit sets i-th bit to 1.
    pub(crate) fn set_bit(&mut self, i: usize) {
        if i >= self.n {
            return;
        }
        let chunk = i / 64;
        let pos = i % 64;
        self.bits[chunk] |= 1 << pos;
    }
}