o1_utils/
bitwise_operations.rs

1//! This module provides a set of functions to perform bit operations on big integers.
2//! In particular, it gives XOR and NOT for `BigUint`.
3use num_bigint::BigUint;
4use std::cmp::{max, Ordering};
5
6use crate::BigUintHelpers;
7
8/// Bitwise operations
9pub trait BitwiseOps<Rhs = Self> {
10    /// Bitwise XOR of two `BigUint` inputs
11    fn bitwise_xor(input1: &Rhs, input: &Rhs) -> Rhs;
12
13    /// Conjunction of the bits of two `BigUint` inputs for a given number of bytes
14    fn bitwise_and(input1: &Rhs, input: &Rhs, bytes: usize) -> Rhs;
15
16    /// Negate the bits of a Self input
17    /// If it provides a larger desired `bits` than the input length then it takes the padded input of `bits` length.
18    /// Otherwise it only takes the bits of the input.
19    fn bitwise_not(input: &Rhs, bits: Option<usize>) -> Rhs;
20}
21
22impl BitwiseOps for BigUint {
23    fn bitwise_xor(input1: &Self, input2: &Self) -> Self {
24        // Pad to equal size in bytes
25        let bytes1 = input1.to_bytes_le().len();
26        let bytes2 = input2.to_bytes_le().len();
27        let in1 = to_padded_bytes(input1, bytes2);
28        let in2 = to_padded_bytes(input2, bytes1);
29        Self::from_bytes_le(
30            &in1.iter()
31                .zip(in2.iter())
32                .map(|(b1, b2)| b1 ^ b2)
33                .collect::<Vec<u8>>(),
34        )
35    }
36
37    #[allow(clippy::cast_possible_truncation)]
38    fn bitwise_not(input: &Self, bits: Option<usize>) -> Self {
39        // pad if needed / desired
40        // first get the number of bits of the input,
41        // take into account that BigUint::bits() returns 0 if the input is 0
42        let in_bits = input.bitlen();
43        let bits = max(in_bits, bits.unwrap_or(0));
44        // build vector of bits in little endian (least significant bit in position 0)
45        let mut bit_vec = vec![];
46        // negate each of the bits of the input
47        (0..bits).for_each(|i| bit_vec.push(!bit_at(input, i as u32)));
48        ToBigUint::to_biguint(&bit_vec)
49    }
50
51    fn bitwise_and(input1: &Self, input2: &Self, bytes: usize) -> Self {
52        let in1 = to_padded_bytes(input1, bytes);
53        let in2 = to_padded_bytes(input2, bytes);
54        Self::from_bytes_le(
55            &in1.iter()
56                .zip(in2.iter())
57                .map(|(b1, b2)| b1 & b2)
58                .collect::<Vec<u8>>(),
59        )
60    }
61}
62
63// Returns a BigUint as a Vec<u8> padded with zeros to a certain number of bytes
64// Panics if bytes < input.len()
65fn to_padded_bytes(input: &BigUint, bytes: usize) -> Vec<u8> {
66    let bytes_inp = input.to_bytes_le().len();
67    match bytes.cmp(&bytes_inp) {
68        Ordering::Greater => pad(input, bytes - bytes_inp),
69        Ordering::Equal | Ordering::Less => input.to_bytes_le(),
70    }
71}
72
73// Pads an input with a number of bytes
74fn pad(input: &BigUint, bytes: usize) -> Vec<u8> {
75    let mut padded = input.to_bytes_le();
76    padded.resize(bytes + padded.len(), 0u8);
77    padded
78}
79
80// Returns the bit value of a BigUint input at a certain position or zero
81fn bit_at(input: &BigUint, index: u32) -> bool {
82    if input.bit(u64::from(index)) {
83        ((input / BigUint::from(2u8).pow(index)) % BigUint::from(2u32)) == BigUint::from(1u32)
84    } else {
85        false
86    }
87}
88
89/// Converts types to a `BigUint`
90trait ToBigUint {
91    /// Converts a vector of bits in little endian to a `BigUint`
92    fn to_biguint(&self) -> BigUint;
93}
94
95impl ToBigUint for Vec<bool> {
96    fn to_biguint(&self) -> BigUint {
97        let mut bigvalue = BigUint::from(0u8);
98        let mut power = BigUint::from(1u8);
99        for bit in self {
100            bigvalue += power.clone() * BigUint::from(u8::from(*bit));
101            power *= BigUint::from(2u8);
102        }
103        bigvalue
104    }
105}
o1_utils/bitwise_operations.rs

o1_utils/
bitwise_operations.rs
