bitsliced_op/
lib.rs

1use std::{io::Error, io::ErrorKind};
2
3use wide::u64x8;
4
5pub mod benchmark;
6
7pub const ALL_ONES: u64x8 = u64x8::splat(0xFFFFFFFFFFFFFFFF);
8pub const ZERO: u64x8 = u64x8::ZERO;
9
10pub fn splat(n: u64) -> u64x8 {
11    u64x8::splat(n)
12}
13
14//expects the input to be in bitsliced form e.g integers are columns, not rows
15//last row is LSB
16pub fn bitsliced_add(a: &[u64x8; 64], b: &[u64x8; 64]) -> [u64x8; 64] {
17    let mut carry = u64x8::ZERO;
18    let mut sum = [u64x8::ZERO; 64];
19    for i in (0..64).rev() {
20        let res = calc_sum_carry(a[i], b[i], carry);
21        sum[i] = res.0;
22        //only set carry if we haven't reached the end yet, we currently ignore overflows
23        carry = res.1;
24    }
25    sum
26}
27
28pub fn bitsliced_add_single(a: &[u64x8; 64], b: u64) -> [u64x8; 64] {
29    let mut carry = u64x8::ZERO;
30    let mut sum = [u64x8::ZERO; 64];
31    for i in (0..64).rev() {
32        let shift_right = 63 - i;
33        let current_bit = (b >> shift_right) & 1;
34        let b_i = if current_bit == 1 { ALL_ONES } else { ZERO };
35        let res = calc_sum_carry(a[i], b_i, carry);
36        sum[i] = res.0;
37        //only set carry if we haven't reached the end yet, we currently ignore overflows
38        carry = res.1;
39    }
40    sum
41}
42
43pub fn bitsliced_add_inline(a: &mut [u64x8; 64], b: &[u64x8; 64]) {
44    let mut carry = u64x8::ZERO;
45    for i in (0..64).rev() {
46        let res = calc_sum_carry(a[i], b[i], carry);
47        a[i] = res.0;
48        //only set carry if we haven't reached the end yet, we currently ignore overflows
49        carry = res.1;
50    }
51}
52
53pub fn bitsliced_add_single_inline(a: &mut [u64x8; 64], b: u64) {
54    let mut carry = u64x8::ZERO;
55    for i in (0..64).rev() {
56        let shift_right = 63 - i;
57        let current_bit = (b >> shift_right) & 1;
58        let b_i = if current_bit == 1 { ALL_ONES } else { ZERO };
59        let res = calc_sum_carry(a[i], b_i, carry);
60        a[i] = res.0;
61        //only set carry if we haven't reached the end yet, we currently ignore overflows
62        carry = res.1;
63    }
64}
65
66fn calc_sum_carry(a: u64x8, b: u64x8, carry: u64x8) -> (u64x8, u64x8) {
67    let sum = a ^ b ^ carry;
68    let next_carry = (a & b) | (carry & (a ^ b));
69    (sum, next_carry)
70}
71
72//this function only works when calculating the module with a number of the power of two
73//currently only supports a single modulo operation for all integers
74//example: if you want to calculate the modulo with 2^56, pass 56 to k
75pub fn bitsliced_modulo_power_of_two(a: &[u64x8; 64], k: usize) -> Result<[u64x8; 64], Error> {
76    if k > 64 {
77        return Err(Error::new(
78            ErrorKind::InvalidData,
79            "k must be <= 64 for bitsliced modulo",
80        ));
81    }
82    let mut out = [u64x8::splat(0); 64];
83    let start: usize = 64 - k;
84    out[start..].copy_from_slice(&a[start..]);
85
86    Ok(out)
87}
88
89pub fn bitsliced_modulo_power_of_two_inline(a: &mut [u64x8; 64], k: usize) -> Result<(), Error> {
90    if k > 64 {
91        return Err(Error::new(
92            ErrorKind::InvalidData,
93            "k must be <= 64 for bitsliced modulo",
94        ));
95    }
96    let end: usize = 64 - k;
97    for i in 0..end {
98        a[i] = u64x8::splat(0);
99    }
100
101    Ok(())
102}
103
104//reduction function: (H+I)%MAX_SIZE
105//H=Hash,I=Index in chain,MAX_SIZE=Max size of output in power of 2
106pub fn des_reduction(h: &[u64x8; 64], i: u64) -> [u64x8; 64] {
107    let mut sum = bitsliced_add_single(h, i);
108    bitsliced_modulo_power_of_two_inline(&mut sum, 56).unwrap();
109    sum
110}
111
112pub fn des_reduction_inline(h: &mut [u64x8; 64], i: u64) {
113    bitsliced_add_single_inline(h, i);
114    bitsliced_modulo_power_of_two_inline(h, 56).unwrap();
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120
121    #[test]
122    fn test_add_works() {
123        let mut a = [ZERO; 64];
124        a[63] = ALL_ONES;
125        let mut b = [ZERO; 64];
126        b[63] = ALL_ONES;
127        let sum = bitsliced_add(&a, &b);
128        assert_eq!(sum[63], ZERO);
129        assert_eq!(sum[62], ALL_ONES);
130        for i in 0..62 {
131            assert_eq!(sum[i], ZERO);
132        }
133    }
134
135    #[test]
136    fn test_add_single_works() {
137        let mut a = [ZERO; 64];
138        a[63] = ALL_ONES;
139        let sum = bitsliced_add_single(&a, 1);
140        assert_eq!(sum[63], ZERO);
141        assert_eq!(sum[62], ALL_ONES);
142        for i in 0..62 {
143            assert_eq!(sum[i], ZERO);
144        }
145    }
146
147    #[test]
148    fn test_add_inline_works() {
149        let mut a = [ZERO; 64];
150        a[63] = ALL_ONES;
151        let mut b = [ZERO; 64];
152        b[63] = ALL_ONES;
153        bitsliced_add_inline(&mut a, &b);
154        assert_eq!(a[63], ZERO);
155        assert_eq!(a[62], ALL_ONES);
156        for i in 0..62 {
157            assert_eq!(a[i], ZERO);
158        }
159    }
160
161    #[test]
162    fn test_add_single_inline_works() {
163        let mut a = [ZERO; 64];
164        a[63] = ALL_ONES;
165        bitsliced_add_single_inline(&mut a, 1);
166        assert_eq!(a[63], ZERO);
167        assert_eq!(a[62], ALL_ONES);
168        for i in 0..62 {
169            assert_eq!(a[i], ZERO);
170        }
171    }
172
173    #[test]
174    fn test_modulo_works() {
175        let a = [ALL_ONES; 64];
176        let res = bitsliced_modulo_power_of_two(&a, 56).unwrap();
177        for i in 0..8 {
178            assert_eq!(res[i], ZERO);
179        }
180        for i in 8..64 {
181            assert_eq!(res[i], ALL_ONES);
182        }
183    }
184
185    #[test]
186    fn test_modulo_inline_works() {
187        let mut a = [ALL_ONES; 64];
188        let _ = bitsliced_modulo_power_of_two_inline(&mut a, 56).unwrap();
189        for i in 0..8 {
190            assert_eq!(a[i], ZERO);
191        }
192        for i in 8..64 {
193            assert_eq!(a[i], ALL_ONES);
194        }
195    }
196}
bitsliced_op/lib.rs

bitsliced_op/
lib.rs
