isla_lib/bitvector/
b64.rs

1// BSD 2-Clause License
2//
3// Copyright (c) 2019, 2020 Alasdair Armstrong
4//
5// All rights reserved.
6//
7// Redistribution and use in source and binary forms, with or without
8// modification, are permitted provided that the following conditions are
9// met:
10//
11// 1. Redistributions of source code must retain the above copyright
12// notice, this list of conditions and the following disclaimer.
13//
14// 2. Redistributions in binary form must reproduce the above copyright
15// notice, this list of conditions and the following disclaimer in the
16// documentation and/or other materials provided with the distribution.
17//
18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22// HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30use serde::{Deserialize, Serialize};
31use std::convert::TryInto;
32use std::fmt;
33use std::ops::{Add, BitAnd, BitOr, BitXor, Neg, Not, Shl, Shr, Sub};
34use std::u128;
35
36use super::{bzhi_u128, bzhi_u64, BV};
37use crate::error::ExecError;
38
39#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
40pub struct B64 {
41    pub len: u32,
42    pub bits: u64,
43}
44
45impl fmt::LowerHex for B64 {
46    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
47        write!(f, "{:x}", self.bits)
48    }
49}
50
51impl fmt::UpperHex for B64 {
52    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53        write!(f, "{:x}", self.bits)
54    }
55}
56
57impl fmt::Display for B64 {
58    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
59        if self.len % 4 == 0 {
60            write!(f, "#x")?
61        } else {
62            write!(f, "#b")?
63        }
64        write_bits!(f, self.bits, self.len)
65    }
66}
67
68impl TryInto<u64> for B64 {
69    type Error = ExecError;
70
71    fn try_into(self) -> Result<u64, ExecError> {
72        Ok(self.bits)
73    }
74}
75
76impl Not for B64 {
77    type Output = B64;
78
79    fn not(self) -> Self::Output {
80        B64 { len: self.len, bits: bzhi_u64(!self.bits, self.len) }
81    }
82}
83
84impl BitXor for B64 {
85    type Output = Self;
86
87    fn bitxor(self, rhs: Self) -> Self::Output {
88        B64 { len: self.len, bits: self.bits ^ rhs.bits }
89    }
90}
91
92impl BitOr for B64 {
93    type Output = Self;
94
95    fn bitor(self, rhs: Self) -> Self::Output {
96        B64 { len: self.len, bits: self.bits | rhs.bits }
97    }
98}
99
100impl BitAnd for B64 {
101    type Output = Self;
102
103    fn bitand(self, rhs: Self) -> Self::Output {
104        B64 { len: self.len, bits: self.bits & rhs.bits }
105    }
106}
107
108impl Neg for B64 {
109    type Output = B64;
110
111    fn neg(self) -> Self::Output {
112        B64 { len: self.len, bits: bzhi_u64((-(self.bits as i64)) as u64, self.len) }
113    }
114}
115
116impl Add<B64> for B64 {
117    type Output = B64;
118
119    fn add(self, rhs: Self) -> Self::Output {
120        B64 { len: self.len, bits: bzhi_u64(self.bits.wrapping_add(rhs.bits), self.len) }
121    }
122}
123
124impl Sub<B64> for B64 {
125    type Output = B64;
126
127    fn sub(self, rhs: Self) -> Self::Output {
128        B64 { len: self.len, bits: bzhi_u64(self.bits.wrapping_sub(rhs.bits), self.len) }
129    }
130}
131
132impl Shl<B64> for B64 {
133    type Output = B64;
134
135    fn shl(self, rhs: Self) -> Self::Output {
136        if rhs.bits >= 64 {
137            B64 { len: self.len, bits: 0 }
138        } else {
139            B64 { len: self.len, bits: bzhi_u64(self.bits << rhs.bits, self.len) }
140        }
141    }
142}
143
144impl Shr<B64> for B64 {
145    type Output = B64;
146
147    fn shr(self, rhs: Self) -> Self::Output {
148        if rhs.bits >= 64 {
149            B64 { len: self.len, bits: 0 }
150        } else {
151            B64 { len: self.len, bits: bzhi_u64(self.bits >> rhs.bits, self.len) }
152        }
153    }
154}
155
156impl BV for B64 {
157    const BIT_ONE: Self = B64 { len: 1, bits: 1 };
158    const BIT_ZERO: Self = B64 { len: 1, bits: 0 };
159    const MAX_WIDTH: u32 = 64;
160
161    fn new(bits: u64, len: u32) -> Self {
162        assert!(len <= 64);
163        B64 { len, bits }
164    }
165
166    fn lower_u64(self) -> u64 {
167        self.bits
168    }
169
170    fn lower_u8(self) -> u8 {
171        (self.bits & 0xFF) as u8
172    }
173
174    fn is_zero(self) -> bool {
175        self.bits == 0
176    }
177
178    fn zeros(len: u32) -> Self {
179        assert!(len <= 64);
180        B64 { len, bits: 0 }
181    }
182
183    fn ones(len: u32) -> Self {
184        assert!(len <= 64);
185        B64 { len, bits: bzhi_u64(0xFFFF_FFFF_FFFF_FFFF, len) }
186    }
187
188    fn leading_zeros(self) -> u32 {
189        self.bits.leading_zeros() - (64 - self.len)
190    }
191
192    fn from_u8(value: u8) -> Self {
193        B64 { len: 8, bits: value as u64 }
194    }
195
196    fn from_u16(value: u16) -> Self {
197        B64 { len: 16, bits: value as u64 }
198    }
199
200    fn from_u32(value: u32) -> Self {
201        B64 { len: 32, bits: value as u64 }
202    }
203
204    fn from_u64(value: u64) -> Self {
205        B64 { len: 64, bits: value }
206    }
207
208    fn from_bytes(bytes: &[u8]) -> Self {
209        assert!(bytes.len() <= 8);
210        let mut bits: u64 = 0;
211        for byte in bytes {
212            bits = (bits << 8) | (*byte as u64)
213        }
214        B64 { len: bytes.len() as u32 * 8, bits }
215    }
216
217    fn to_le_bytes(self) -> Vec<u8> {
218        assert!(self.len % 8 == 0);
219        self.bits.to_le_bytes()[..self.len as usize / 8].to_vec()
220    }
221
222    fn to_be_bytes(self) -> Vec<u8> {
223        assert!(self.len % 8 == 0);
224        self.bits.to_be_bytes()[8 - self.len as usize / 8..].to_vec()
225    }
226
227    fn from_str(bv: &str) -> Option<Self> {
228        if bv.len() <= 2 || !(bv.starts_with('#') || bv.starts_with('0')) {
229            return None;
230        }
231
232        match bv.chars().nth(1) {
233            Some('x') => {
234                let hex = &bv[2..];
235                let len = hex.len();
236                if len <= 16 {
237                    Some(B64 { len: len as u32 * 4, bits: u64::from_str_radix(hex, 16).ok()? })
238                } else {
239                    None
240                }
241            }
242            Some('b') => {
243                let bin = &bv[2..];
244                let len = bin.len();
245                if len <= 64 {
246                    Some(B64 { len: len as u32, bits: u64::from_str_radix(bin, 2).ok()? })
247                } else {
248                    None
249                }
250            }
251            _ => None,
252        }
253    }
254
255    fn len(self) -> u32 {
256        self.len
257    }
258
259    fn add_i128(self, op: i128) -> Self {
260        B64 { len: self.len, bits: bzhi_u64(self.bits.wrapping_add(op as u64), self.len) }
261    }
262
263    fn zero_extend(self, new_len: u32) -> Self {
264        assert!(self.len <= new_len && new_len <= 64);
265        B64 { len: new_len, bits: self.bits }
266    }
267
268    fn sign_extend(self, new_len: u32) -> Self {
269        assert!(self.len <= new_len && new_len <= 64);
270        if self.len > 0 {
271            if (self.bits >> (self.len - 1)) & 0b1 == 0b1 {
272                let top = bzhi_u64(0xFFFF_FFFF_FFFF_FFFF, new_len) & !bzhi_u64(0xFFFF_FFFF_FFFF_FFFF, self.len);
273                B64 { len: new_len, bits: self.bits | top }
274            } else {
275                B64 { len: new_len, bits: self.bits }
276            }
277        } else {
278            B64 { len: new_len, bits: 0 }
279        }
280    }
281
282    fn unsigned(self) -> i128 {
283        i128::from(self.bits)
284    }
285
286    fn signed(self) -> i128 {
287        i128::from(self.sign_extend(64).bits as i64)
288    }
289
290    fn slice(self, from: u32, len: u32) -> Option<Self> {
291        if from + len <= self.len {
292            Some(B64 { len, bits: bzhi_u64(self.bits >> from, len) })
293        } else {
294            None
295        }
296    }
297
298    fn set_slice(self, n: u32, update: Self) -> Self {
299        let mask = !bzhi_u64(0xFFFF_FFFF_FFFF_FFFF << n, n + update.len);
300        let update = update.bits << n;
301        B64 { len: self.len, bits: (self.bits & mask) | update }
302    }
303
304    fn set_slice_int(int: i128, n: u32, update: Self) -> i128 {
305        let mask = !bzhi_u128(u128::max_value() << n, n as u32 + update.len());
306        let update = (update.bits as u128) << n;
307        ((int as u128 & mask) | update) as i128
308    }
309
310    fn get_slice_int(len: u32, int: i128, n: u32) -> Self {
311        let slice = bzhi_u64((int >> n) as u64, len);
312        Self::new(slice, len)
313    }
314}
315
316#[cfg(test)]
317mod tests {
318    use super::*;
319
320    #[test]
321    fn test_write_bits64() {
322        assert_eq!(format!("{}", B64::zeros(4)), "#x0");
323        assert_eq!(format!("{}", B64::zeros(8)), "#x00");
324        assert_eq!(format!("{}", B64::zeros(12)), "#x000");
325        assert_eq!(format!("{}", B64::zeros(16)), "#x0000");
326
327        assert_eq!(format!("{}", B64::ones(4)), "#xf");
328        assert_eq!(format!("{}", B64::ones(8)), "#xff");
329        assert_eq!(format!("{}", B64::ones(12)), "#xfff");
330        assert_eq!(format!("{}", B64::ones(16)), "#xffff");
331
332        assert_eq!(format!("{}", B64::from_u32(0xDEAD_BEEFu32)), "#xdeadbeef");
333
334        assert_eq!(format!("{}", B64::new(0b101, 3)), "#b101");
335        assert_eq!(format!("{}", B64::new(0b100, 3)), "#b100");
336        assert_eq!(format!("{}", B64::new(0b001, 3)), "#b001");
337
338        assert_eq!(format!("{}", B64::new(0x0000_0000_0000_0000, 64)), "#x0000000000000000");
339    }
340
341    #[test]
342    fn test_from_bytes() {
343        assert_eq!(B64::from_bytes(&[0xABu8, 0xCDu8]), B64::from_u16(0xABCDu16));
344        assert_eq!(B64::from_bytes(&[0xABu8, 0xCDu8, 0xEFu8]), B64::new(0xABCDEF, 24));
345    }
346
347    #[test]
348    fn test_add() {
349        assert_eq!(B64::new(0xFFFF_FFFF_FFFF_FFFF, 64) + B64::new(1, 64), B64::new(0, 64));
350        assert_eq!(B64::new(0xFF, 8) + B64::new(2, 8), B64::new(1, 8));
351    }
352
353    #[test]
354    fn test_neg() {
355        assert!(-B64::new(0b000, 3) == B64::new(0b000, 3));
356        assert!(-B64::new(0b001, 3) == B64::new(0b111, 3));
357        assert!(-B64::new(0b010, 3) == B64::new(0b110, 3));
358        assert!(-B64::new(0xFF, 8) == B64::new(0x1, 8));
359        assert!(-B64::new(0xFFFF_FFFF_FFFF_FFFF, 64) == B64::new(0x1, 64));
360    }
361
362    #[test]
363    fn test_shl() {
364        assert!(B64::new(0b001, 3) << B64::new(2, 3) == B64::new(0b100, 3));
365        assert!(B64::new(0b001, 3) << B64::new(3, 3) == B64::new(0b000, 3));
366        assert!(B64::new(0x0000_0000_0000_0001, 64) << B64::new(64, 64) == B64::new(0, 64));
367        assert!(B64::new(0x0000_0000_0000_0001, 64) << B64::new(65, 64) == B64::new(0, 64));
368        assert!(B64::new(0xFFFF_FFFF_FFFF_FFFF, 64) << B64::new(64, 64) == B64::new(0, 64));
369        assert!(B64::new(0xFFFF_FFFF_FFFF_FFFF, 64) << B64::new(66, 64) == B64::new(0, 64));
370    }
371
372    #[test]
373    fn test_shr() {
374        assert!(B64::new(0b100, 3) >> B64::new(2, 3) == B64::new(0b001, 3));
375        assert!(B64::new(0b100, 3) >> B64::new(3, 3) == B64::new(0b000, 3));
376        assert!(B64::new(0xFFFF_FFFF_FFFF_FFFF, 64) >> B64::new(64, 64) == B64::new(0, 64));
377        assert!(B64::new(0xFFFF_FFFF_FFFF_FFFF, 64) >> B64::new(66, 64) == B64::new(0, 64));
378    }
379
380    #[test]
381    fn test_zero_extend() {
382        assert!(B64::new(0b100, 3).zero_extend(3) == B64::new(0b100, 3));
383        assert!(B64::new(0b100, 3).zero_extend(6) == B64::new(0b000100, 6));
384    }
385
386    #[test]
387    fn test_sign_extend() {
388        assert!(B64::new(0b100, 3).sign_extend(6) == B64::new(0b111100, 6));
389        assert!(B64::new(0b010, 3).sign_extend(6) == B64::new(0b000010, 6));
390        assert!(B64::new(0b110, 3).sign_extend(3) == B64::new(0b110, 3));
391        assert!(B64::new(0b010, 3).sign_extend(3) == B64::new(0b010, 3));
392        assert!(B64::new(0xF, 4).sign_extend(8) == B64::new(0xFF, 8));
393    }
394
395    #[test]
396    fn test_append() {
397        let sbits_max = B64::new(0xFFFF_FFFF_FFFF_FFFF, 64);
398        assert!(B64::new(0, 0).append(sbits_max) == Some(sbits_max));
399        assert!(sbits_max.append(B64::new(0, 0)) == Some(sbits_max));
400        assert!(sbits_max.append(sbits_max) == None);
401        assert!(B64::new(0xCAFECAFE, 32).append(B64::new(0x1234ABCD, 32)) == Some(B64::new(0xCAFECAFE1234ABCD, 64)));
402    }
403
404    #[test]
405    fn test_slice() {
406        let sbits = B64::new(0xCAFE_F00D_1234_ABCD, 64);
407        assert!(sbits.slice(0, 32) == Some(B64::new(0x1234_ABCD, 32)));
408        assert!(sbits.slice(32, 32) == Some(B64::new(0xCAFE_F00D, 32)));
409        assert!(sbits.slice(16, 16) == Some(B64::new(0x1234, 16)));
410    }
411
412    #[test]
413    fn test_extract() {
414        let sbits = B64::new(0xCAFE_F00D_1234_ABCD, 64);
415        assert!(sbits.extract(31, 0) == Some(B64::new(0x1234_ABCD, 32)));
416        assert!(sbits.extract(63, 32) == Some(B64::new(0xCAFE_F00D, 32)));
417        assert!(sbits.extract(7, 0) == Some(B64::new(0xCD, 8)));
418    }
419
420    #[test]
421    fn test_truncate_lsb() {
422        let sbits = B64::new(0xCAFE_F00D_1234_ABCD, 64);
423        assert!(sbits.truncate_lsb(16) == Some(B64::new(0xCAFE, 16)));
424        assert!(sbits.truncate_lsb(64) == Some(sbits));
425        assert!(sbits.truncate_lsb(0) == Some(B64::new(0, 0)));
426    }
427
428    #[test]
429    fn test_signed() {
430        assert!(B64::new(0b100, 3).signed() == -4);
431        assert!(B64::new(0b011, 3).signed() == 3);
432        assert!(B64::new(0b111, 3).signed() == -1);
433        assert!(B64::new(0b000, 3).signed() == 0);
434        assert!(B64::new(0b1, 1).signed() == -1);
435    }
436
437    #[test]
438    fn test_unsigned() {
439        assert!(B64::new(0b100, 3).unsigned() == 4);
440        assert!(B64::new(0b011, 3).unsigned() == 3);
441        assert!(B64::new(0b111, 3).unsigned() == 7);
442        assert!(B64::new(0b000, 3).unsigned() == 0);
443        assert!(B64::new(0b1, 1).unsigned() == 1);
444    }
445
446    #[test]
447    fn test_replicate() {
448        assert!(B64::new(0b101, 3).replicate(0) == Some(B64::new(0, 0)));
449        assert!(B64::new(0b10, 2).replicate(3) == Some(B64::new(0b101010, 6)));
450        assert!(B64::new(0xCAFE, 16).replicate(4) == Some(B64::new(0xCAFECAFECAFECAFE, 64)));
451        assert!(B64::new(0b1, 1).replicate(128) == None);
452    }
453
454    #[test]
455    fn test_set_slice() {
456        assert!(B64::new(0b000, 3).set_slice(1, B64::new(0b1, 1)) == B64::new(0b010, 3));
457        assert!(B64::new(0b111, 3).set_slice(1, B64::new(0b0, 1)) == B64::new(0b101, 3));
458        assert!(B64::new(0b111, 3).set_slice(1, B64::new(0b1, 1)) == B64::new(0b111, 3));
459        assert!(B64::new(0b000, 3).set_slice(1, B64::new(0b0, 1)) == B64::new(0b000, 3));
460        assert!(B64::new(0xCAFE, 16).set_slice(4, B64::new(0x0, 4)) == B64::new(0xCA0E, 16));
461        assert!(B64::new(0xFFFF, 16).set_slice(12, B64::new(0x0, 4)) == B64::new(0x0FFF, 16));
462        assert!(B64::new(0xFFFF, 16).set_slice(8, B64::new(0x0, 4)) == B64::new(0xF0FF, 16));
463        assert!(B64::new(0xFFFF, 16).set_slice(4, B64::new(0x0, 4)) == B64::new(0xFF0F, 16));
464        assert!(B64::new(0xFFFF, 16).set_slice(0, B64::new(0x0, 4)) == B64::new(0xFFF0, 16));
465    }
466
467    #[test]
468    fn test_leading_zeros() {
469        assert_eq!(B64::new(0b001, 3).leading_zeros(), 2);
470        assert_eq!(B64::new(0b010, 3).leading_zeros(), 1);
471        assert_eq!(B64::new(0b00001, 5).leading_zeros(), 4);
472        assert_eq!(B64::new(0, 32).leading_zeros(), 32);
473        assert_eq!(B64::new(0, 64).leading_zeros(), 64);
474        assert_eq!(B64::new(0xFFFF_FFFF_FFFF_FFFF, 64).leading_zeros(), 0);
475    }
476
477    #[test]
478    fn test_set_slice_int() {
479        assert!(B64::set_slice_int(15, 1, B64::new(0, 2)) == 9)
480    }
481
482    #[test]
483    fn test_arith_shiftr() {
484        assert_eq!(B64::new(0b100, 3).arith_shiftr(0), B64::new(0b100, 3));
485        assert_eq!(B64::new(0b100, 3).arith_shiftr(1), B64::new(0b110, 3));
486        assert_eq!(B64::new(0b100, 3).arith_shiftr(2), B64::new(0b111, 3));
487        assert_eq!(B64::new(0b100, 3).arith_shiftr(3), B64::new(0b111, 3));
488        assert_eq!(B64::new(0b100, 3).arith_shiftr(4), B64::new(0b111, 3));
489
490        assert_eq!(B64::new(0b0110, 4).arith_shiftr(2), B64::new(0b0001, 4));
491    }
492
493    #[test]
494    fn test_to_bytes() {
495        assert_eq!(B64::new(0x123456, 24).to_le_bytes(), [0x56, 0x34, 0x12]);
496        assert_eq!(B64::new(0x123456, 24).to_be_bytes(), [0x12, 0x34, 0x56]);
497    }
498}
isla_lib/bitvector/b64.rs

isla_lib/bitvector/
b64.rs
