1use serde::{Deserialize, Serialize};
31use std::convert::TryFrom;
32use std::convert::TryInto;
33use std::fmt;
34use std::ops::{Add, BitAnd, BitOr, BitXor, Neg, Not, Shl, Shr, Sub};
35use std::u128;
36
37use super::{bzhi_u128, BV};
38use crate::error::ExecError;
39
40#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
41pub struct B129 {
42 tag: bool,
43 bits: u128,
44 len: u32,
45}
46
47impl fmt::LowerHex for B129 {
48 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
49 if self.len <= 128 || !self.tag {
50 write!(f, "{:x}", self.bits)
51 } else {
52 write!(f, "1{:0>32x}", self.bits)
53 }
54 }
55}
56
57impl fmt::UpperHex for B129 {
58 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
59 if self.len <= 128 || !self.tag {
60 write!(f, "{:X}", self.bits)
61 } else {
62 write!(f, "1{:0>32X}", self.bits)
63 }
64 }
65}
66
67impl fmt::Display for B129 {
68 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69 if self.len % 4 == 0 {
70 write!(f, "#x")?
71 } else {
72 write!(f, "#b")?
73 }
74 if self.len == 129 {
75 if self.tag {
76 write!(f, "1")?
77 } else {
78 write!(f, "0")?
79 }
80 write_bits!(f, self.bits, 128)
81 } else {
82 write_bits!(f, self.bits, self.len)
83 }
84 }
85}
86
87impl TryInto<u64> for B129 {
88 type Error = ExecError;
89
90 fn try_into(self) -> Result<u64, ExecError> {
91 if self.len <= 64 {
92 Ok(self.bits as u64)
93 } else {
94 Err(ExecError::Overflow)
95 }
96 }
97}
98
99fn bzhi(bv: B129, len: u32) -> B129 {
100 if len > 128 {
101 bv
102 } else {
103 B129 { len: bv.len, tag: false, bits: bzhi_u128(bv.bits, len) }
104 }
105}
106
107impl Not for B129 {
108 type Output = B129;
109
110 fn not(self) -> Self::Output {
111 bzhi(B129 { len: self.len, tag: !self.tag, bits: !self.bits }, self.len)
112 }
113}
114
115impl BitXor for B129 {
116 type Output = Self;
117
118 fn bitxor(self, rhs: Self) -> Self::Output {
119 B129 { len: self.len, tag: self.tag ^ rhs.tag, bits: self.bits ^ rhs.bits }
120 }
121}
122
123impl BitOr for B129 {
124 type Output = Self;
125
126 fn bitor(self, rhs: Self) -> Self::Output {
127 B129 { len: self.len, tag: self.tag | rhs.tag, bits: self.bits | rhs.bits }
128 }
129}
130
131impl BitAnd for B129 {
132 type Output = Self;
133
134 fn bitand(self, rhs: Self) -> Self::Output {
135 B129 { len: self.len, tag: self.tag & rhs.tag, bits: self.bits & rhs.bits }
136 }
137}
138
139impl Add<B129> for B129 {
140 type Output = Self;
141
142 fn add(self, rhs: Self) -> Self::Output {
143 let (sum, carry) = self.bits.overflowing_add(rhs.bits);
144 bzhi(B129 { len: self.len, tag: self.tag ^ rhs.tag ^ carry, bits: sum }, self.len)
145 }
146}
147
148impl Neg for B129 {
149 type Output = B129;
150
151 fn neg(self) -> Self::Output {
152 !self + B129 { len: self.len, tag: false, bits: 1 }
153 }
154}
155
156impl Sub<B129> for B129 {
157 type Output = Self;
158
159 fn sub(self, rhs: Self) -> Self::Output {
160 self + (-rhs)
161 }
162}
163
164impl Shl<B129> for B129 {
165 type Output = B129;
166
167 fn shl(self, rhs: Self) -> Self::Output {
168 if rhs.bits >= 129 || rhs.tag {
169 B129 { len: self.len, tag: false, bits: 0 }
170 } else if rhs.bits == 128 {
171 bzhi(B129 { len: self.len, tag: self.bits & 0b1 == 0b1, bits: 0 }, self.len)
172 } else if rhs.bits == 0 {
173 self
174 } else {
175 let tag = (self.bits >> (128 - rhs.bits)) & 0b1 == 0b1;
176 bzhi(B129 { len: self.len, tag, bits: self.bits << rhs.bits }, self.len)
177 }
178 }
179}
180
181impl Shr<B129> for B129 {
182 type Output = B129;
183
184 fn shr(self, rhs: Self) -> Self::Output {
185 if rhs.bits >= 129 || rhs.tag {
186 B129 { len: self.len, tag: false, bits: 0 }
187 } else if rhs.bits == 128 {
188 bzhi(B129 { len: self.len, tag: false, bits: if self.tag { 1 } else { 0 } }, self.len)
189 } else if rhs.bits == 0 {
190 self
191 } else {
192 let mask = if self.tag { 0b1 << (128 - rhs.bits) } else { 0 };
193 bzhi(B129 { len: self.len, tag: false, bits: (self.bits >> rhs.bits) | mask }, self.len)
194 }
195 }
196}
197
198fn shift_u32(bits: u32, len: u32) -> B129 {
199 B129 { len, tag: false, bits: bits as u128 }
200}
201
202const ALL_ONES_129: B129 = B129 { tag: true, bits: u128::MAX, len: 129 };
203
204impl BV for B129 {
205 const BIT_ONE: Self = B129 { len: 1, tag: false, bits: 1 };
206 const BIT_ZERO: Self = B129 { len: 1, tag: false, bits: 0 };
207 const MAX_WIDTH: u32 = 129;
208
209 fn new(bits: u64, len: u32) -> Self {
210 assert!(len <= 129);
211 B129 { len, tag: false, bits: bits as u128 }
212 }
213
214 fn len(self) -> u32 {
215 self.len
216 }
217
218 fn lower_u64(self) -> u64 {
219 self.bits as u64
220 }
221
222 fn lower_u8(self) -> u8 {
223 (self.bits & 0xFF) as u8
224 }
225
226 fn is_zero(self) -> bool {
227 !self.tag && self.bits == 0
228 }
229
230 fn zeros(len: u32) -> Self {
231 B129 { len, tag: false, bits: 0 }
232 }
233
234 fn ones(len: u32) -> Self {
235 bzhi(B129 { len, tag: true, bits: u128::MAX }, len)
236 }
237
238 fn leading_zeros(self) -> u32 {
239 if self.tag {
240 0
241 } else {
242 (self.bits.leading_zeros() + 1) - (129 - self.len)
243 }
244 }
245
246 fn from_u8(value: u8) -> Self {
247 B129 { len: 8, tag: false, bits: value as u128 }
248 }
249
250 fn from_u16(value: u16) -> Self {
251 B129 { len: 16, tag: false, bits: value as u128 }
252 }
253
254 fn from_u32(value: u32) -> Self {
255 B129 { len: 32, tag: false, bits: value as u128 }
256 }
257
258 fn from_u64(value: u64) -> Self {
259 B129 { len: 64, tag: false, bits: value as u128 }
260 }
261
262 fn from_bytes(bytes: &[u8]) -> Self {
263 assert!(bytes.len() <= 16);
264 let mut bits: u128 = 0;
265 for byte in bytes {
266 bits = (bits << 8) | (*byte as u128)
267 }
268 B129 { len: bytes.len() as u32 * 8, tag: false, bits }
269 }
270
271 fn to_le_bytes(self) -> Vec<u8> {
272 assert!(self.len % 8 == 0);
273 self.bits.to_le_bytes()[..self.len as usize / 8].to_vec()
274 }
275
276 fn to_be_bytes(self) -> Vec<u8> {
277 assert!(self.len % 8 == 0);
278 self.bits.to_be_bytes()[16 - self.len as usize / 8..].to_vec()
279 }
280
281 fn zero_extend(self, new_len: u32) -> Self {
282 assert!(self.len <= new_len && new_len <= 129);
283 B129 { len: new_len, tag: self.tag, bits: self.bits }
284 }
285
286 fn sign_extend(self, new_len: u32) -> Self {
287 assert!(self.len <= new_len && new_len <= 129);
288 if self.len == 0 {
289 B129 { len: new_len, tag: false, bits: 0 }
290 } else if new_len < 129 {
291 if (self.bits >> (self.len - 1)) & 1 == 1 {
292 let top = bzhi_u128(u128::MAX, new_len) & !bzhi_u128(u128::MAX, self.len);
293 B129 { len: new_len, tag: false, bits: self.bits | top }
294 } else {
295 B129 { len: new_len, tag: false, bits: self.bits }
296 }
297 } else if self.len == 129 {
298 self
299 } else {
300 if (self.bits >> (self.len - 1)) & 0b1 == 0b1 {
302 B129 { len: new_len, tag: true, bits: self.bits | !bzhi_u128(u128::MAX, self.len) }
303 } else {
304 B129 { len: new_len, tag: false, bits: self.bits }
305 }
306 }
307 }
308
309 fn unsigned(self) -> i128 {
310 assert!(!self.tag);
311 i128::try_from(self.bits).unwrap()
312 }
313
314 fn signed(self) -> i128 {
315 if self.len == 129 {
316 if self.tag {
317 assert!(self.bits & 0x8000_0000_0000_0000_0000_0000_0000_0000 != 0);
318 self.bits as i128
319 } else {
320 assert!(self.bits & 0x8000_0000_0000_0000_0000_0000_0000_0000 == 0);
321 self.bits as i128
322 }
323 } else {
324 self.sign_extend(128).bits as i128
325 }
326 }
327
328 fn slice(self, from: u32, len: u32) -> Option<Self> {
329 if from + len <= self.len {
330 Some(bzhi(B129 { len, ..self >> shift_u32(from, self.len) }, len))
331 } else {
332 None
333 }
334 }
335
336 fn from_str(bv: &str) -> Option<Self> {
337 if bv.len() <= 2 || !(bv.starts_with('#') || bv.starts_with('0')) {
338 return None;
339 }
340
341 match bv.chars().nth(1) {
342 Some('x') => {
343 let hex = &bv[2..];
344 let len = hex.len();
345 if len <= 32 {
346 Some(B129 { len: len as u32 * 4, tag: false, bits: u128::from_str_radix(hex, 16).ok()? })
347 } else if len == 33 {
348 let tag_bit = &hex[0..1];
349 if tag_bit != "0" && tag_bit != "1" {
350 return None;
351 }
352 Some(B129 { len: 129, tag: tag_bit == "1", bits: u128::from_str_radix(&hex[1..], 16).ok()? })
353 } else {
354 None
355 }
356 }
357 Some('b') => {
358 let bin = &bv[2..];
359 let len = bin.len();
360 if len <= 128 {
361 Some(B129 { len: len as u32, tag: false, bits: u128::from_str_radix(bin, 2).ok()? })
362 } else if len == 129 {
363 let tag_bit = &bin[0..1];
364 if tag_bit != "0" && tag_bit != "1" {
365 return None;
366 }
367 Some(B129 { len: len as u32, tag: tag_bit == "1", bits: u128::from_str_radix(&bin[1..], 2).ok()? })
368 } else {
369 None
370 }
371 }
372 _ => None,
373 }
374 }
375
376 fn add_i128(self, op: i128) -> Self {
377 if op > 0 {
378 self + bzhi(B129 { len: self.len, tag: false, bits: op as u128 }, self.len)
379 } else {
380 self + bzhi(B129 { len: self.len, tag: true, bits: op as u128 }, self.len)
381 }
382 }
383
384 fn set_slice(self, n: u32, update: Self) -> Self {
385 let mask = (ALL_ONES_129 << shift_u32(n, 129)).slice(0, n + update.len).unwrap().zero_extend(self.len);
386 let update = update.zero_extend(self.len) << shift_u32(n, self.len);
387 (self & !mask) | update
388 }
389
390 fn set_slice_int(int: i128, n: u32, update: Self) -> i128 {
391 assert!(update.len <= 128);
392 let mask = !bzhi_u128(u128::max_value() << n, n as u32 + update.len());
393 let update = (update.bits as u128) << n;
394 ((int as u128 & mask) | update) as i128
395 }
396
397 fn get_slice_int(len: u32, int: i128, n: u32) -> Self {
398 assert!(len <= 128);
399 B129 { len, tag: false, bits: bzhi_u128((int >> n) as u128, len) }
400 }
401}
402
403#[cfg(test)]
404mod tests {
405 use super::*;
406 use std::u128;
407
408 const JUST_TAG: B129 = B129 { tag: true, bits: 0, len: 129 };
409
410 const ONE_129: B129 = B129 { tag: false, bits: 1, len: 129 };
411
412 const TWO_129: B129 = B129 { tag: false, bits: 2, len: 129 };
413
414 const ALL_ONES_129: B129 = B129 { tag: true, bits: u128::MAX, len: 129 };
415
416 const ALL_ZEROS_129: B129 = B129 { tag: false, bits: 0, len: 129 };
417
418 #[test]
419 fn test_lower_hex() {
420 assert_eq!(format!("0x{:x}", ALL_ONES_129), "0x1ffffffffffffffffffffffffffffffff");
421 assert_eq!(
422 format!("0x{:x}", B129 { tag: false, bits: u128::MAX, len: 129 }),
423 "0xffffffffffffffffffffffffffffffff"
424 );
425 assert_eq!(
426 format!("0x{:x}", B129 { tag: false, bits: u128::MAX, len: 128 }),
427 "0xffffffffffffffffffffffffffffffff"
428 );
429 assert_eq!(format!("0x{:x}", B129 { tag: false, bits: 0, len: 129 }), "0x0");
430 assert_eq!(format!("0x{:x}", JUST_TAG), "0x100000000000000000000000000000000")
431 }
432
433 #[test]
434 fn test_upper_hex() {
435 assert_eq!(format!("0x{:X}", ALL_ONES_129), "0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
436 assert_eq!(
437 format!("0x{:X}", B129 { tag: false, bits: u128::MAX, len: 129 }),
438 "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
439 );
440 assert_eq!(
441 format!("0x{:X}", B129 { tag: false, bits: u128::MAX, len: 128 }),
442 "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
443 );
444 assert_eq!(format!("0x{:X}", B129 { tag: false, bits: 0, len: 129 }), "0x0");
445 assert_eq!(format!("0x{:X}", JUST_TAG), "0x100000000000000000000000000000000")
446 }
447
448 #[test]
449 fn test_not() {
450 assert_eq!(!ALL_ONES_129, ALL_ZEROS_129);
451 assert_eq!(!JUST_TAG, B129 { tag: false, bits: u128::MAX, len: 129 });
452 assert_eq!(!B129 { tag: false, bits: 0xFF, len: 8 }, B129 { tag: false, bits: 0, len: 8 });
453 }
454
455 #[test]
456 fn test_bitxor() {
457 assert_eq!(ALL_ONES_129 ^ ALL_ZEROS_129, ALL_ONES_129);
458 assert_eq!(ALL_ONES_129 ^ ALL_ONES_129, ALL_ZEROS_129)
459 }
460
461 #[test]
462 fn test_bitor() {
463 assert_eq!(ALL_ONES_129 | ALL_ZEROS_129, ALL_ONES_129);
464 assert_eq!(ALL_ONES_129 | ALL_ONES_129, ALL_ONES_129)
465 }
466
467 #[test]
468 fn test_bitand() {
469 assert_eq!(ALL_ONES_129 & ALL_ZEROS_129, ALL_ZEROS_129);
470 assert_eq!(ALL_ONES_129 & ALL_ONES_129, ALL_ONES_129)
471 }
472
473 #[test]
474 fn test_add() {
475 assert_eq!(ALL_ONES_129 + ONE_129, ALL_ZEROS_129);
476 assert_eq!(ALL_ONES_129 + TWO_129, ONE_129);
477 assert_eq!(ONE_129 + ONE_129, TWO_129);
478 assert_eq!(B129 { tag: false, ..ALL_ONES_129 } + ONE_129, JUST_TAG);
479 assert_eq!(JUST_TAG + JUST_TAG, ALL_ZEROS_129);
480 }
481
482 #[test]
483 fn test_sub() {
484 assert_eq!(ALL_ONES_129 - JUST_TAG, B129 { tag: false, ..ALL_ONES_129 });
485 assert_eq!(ALL_ONES_129 - ONE_129, ALL_ONES_129 & !ONE_129);
486 assert_eq!(TWO_129 - TWO_129, ALL_ZEROS_129);
487 assert_eq!(TWO_129 - ONE_129, ONE_129)
488 }
489
490 #[test]
491 fn test_leading_zeros() {
492 assert_eq!(ALL_ONES_129.leading_zeros(), 0);
493 assert_eq!(ALL_ZEROS_129.leading_zeros(), 129);
494 assert_eq!(JUST_TAG.leading_zeros(), 0);
495 assert_eq!(ONE_129.leading_zeros(), 128);
496 assert_eq!(B129::new(0b001, 3).leading_zeros(), 2);
497 assert_eq!(B129::new(0b010, 3).leading_zeros(), 1);
498 assert_eq!(B129::new(0b00001, 5).leading_zeros(), 4);
499 assert_eq!(B129::new(0, 32).leading_zeros(), 32);
500 assert_eq!(B129::new(0, 64).leading_zeros(), 64);
501 assert_eq!(B129::new(0xFFFF_FFFF_FFFF_FFFF, 64).leading_zeros(), 0);
502 }
503
504 #[test]
505 fn test_arith_shiftr() {
506 assert_eq!(B129::new(0b100, 3).arith_shiftr(0), B129::new(0b100, 3));
507 assert_eq!(B129::new(0b100, 3).arith_shiftr(1), B129::new(0b110, 3));
508 assert_eq!(B129::new(0b100, 3).arith_shiftr(2), B129::new(0b111, 3));
509 assert_eq!(B129::new(0b100, 3).arith_shiftr(3), B129::new(0b111, 3));
510 assert_eq!(B129::new(0b100, 3).arith_shiftr(4), B129::new(0b111, 3));
511
512 assert_eq!(B129::new(0b0110, 4).arith_shiftr(2), B129::new(0b0001, 4));
513
514 for i in 0..131 {
515 assert_eq!(ALL_ONES_129.arith_shiftr(i as i128), ALL_ONES_129);
516 assert_eq!(ALL_ZEROS_129.arith_shiftr(i as i128), ALL_ZEROS_129);
517 }
518 }
519
520 #[test]
521 fn test_sign_extend() {
522 assert_eq!(B129::new(0b1, 1).sign_extend(129), ALL_ONES_129);
523 assert_eq!(B129::new(0b01, 2).sign_extend(129), ONE_129);
524
525 assert_eq!(B129::new(0b1, 1).sign_extend(5), B129::new(0b11111, 5));
526 assert_eq!(B129::new(0b01, 2).sign_extend(5), B129::new(0b00001, 5));
527 }
528
529 #[test]
530 fn test_to_bytes() {
531 assert_eq!(B129::new(0x123456, 24).to_le_bytes(), [0x56, 0x34, 0x12]);
532 assert_eq!(B129::new(0x123456, 24).to_be_bytes(), [0x12, 0x34, 0x56]);
533 }
534
535 #[test]
536 fn test_signed() {
537 assert_eq!(B129::new(0xff, 8).signed(), -1);
538 assert_eq!((B129::new(0xff, 8) - B129::new(1, 8)).signed(), -2);
539 assert_eq!(B129::ones(128).signed(), -1);
540 assert_eq!((B129::ones(128) - B129::new(1, 128)).signed(), -2);
541 assert_eq!(ALL_ONES_129.signed(), -1);
542 assert_eq!((ALL_ONES_129 - ONE_129).signed(), -2);
543 }
544
545 #[test]
546 fn test_shl() {
547 assert!(B129::new(0b001, 3) << B129::new(2, 3) == B129::new(0b100, 3));
548 assert!(B129::new(0b001, 3) << B129::new(3, 3) == B129::new(0b000, 3));
549 assert!(B129::new(0x0000_0000_0000_0001, 64) << B129::new(64, 64) == B129::new(0, 64));
550 assert!(B129::new(0x0000_0000_0000_0001, 64) << B129::new(65, 64) == B129::new(0, 64));
551 assert!(B129::new(0xFFFF_FFFF_FFFF_FFFF, 64) << B129::new(64, 64) == B129::new(0, 64));
552 assert!(B129::new(0xFFFF_FFFF_FFFF_FFFF, 64) << B129::new(66, 64) == B129::new(0, 64));
553 assert_eq!(
554 B129::new(0xFFFF_FFFF_FFFF_FFFF, 129) << B129::new(64, 129)
555 | B129::new(0xFFFF_FFFF_FFFF_FFFF, 129)
556 | ONE_129 << B129::new(128, 129),
557 ALL_ONES_129
558 );
559 }
560
561 #[test]
562 fn test_shr() {
563 assert!(B129::new(0b100, 3) >> B129::new(2, 3) == B129::new(0b001, 3));
564 assert!(B129::new(0b100, 3) >> B129::new(3, 3) == B129::new(0b000, 3));
565 assert!(B129::new(0xFFFF_FFFF_FFFF_FFFF, 64) >> B129::new(64, 64) == B129::new(0, 64));
566 assert!(B129::new(0xFFFF_FFFF_FFFF_FFFF, 64) >> B129::new(66, 64) == B129::new(0, 64));
567 }
568
569 #[test]
570 fn test_set_slice() {
571 assert!(B129::new(0b000, 3).set_slice(1, B129::new(0b1, 1)) == B129::new(0b010, 3));
572 assert!(B129::new(0b111, 3).set_slice(1, B129::new(0b0, 1)) == B129::new(0b101, 3));
573 assert!(B129::new(0b111, 3).set_slice(1, B129::new(0b1, 1)) == B129::new(0b111, 3));
574 assert!(B129::new(0b000, 3).set_slice(1, B129::new(0b0, 1)) == B129::new(0b000, 3));
575 assert!(B129::new(0xCAFE, 16).set_slice(4, B129::new(0x0, 4)) == B129::new(0xCA0E, 16));
576 assert!(B129::new(0xFFFF, 16).set_slice(12, B129::new(0x0, 4)) == B129::new(0x0FFF, 16));
577 assert!(B129::new(0xFFFF, 16).set_slice(8, B129::new(0x0, 4)) == B129::new(0xF0FF, 16));
578 assert!(B129::new(0xFFFF, 16).set_slice(4, B129::new(0x0, 4)) == B129::new(0xFF0F, 16));
579 assert!(B129::new(0xFFFF, 16).set_slice(0, B129::new(0x0, 4)) == B129::new(0xFFF0, 16));
580 assert_eq!(B129::new(0, 129).set_slice(128, B129::BIT_ONE) >> B129::new(128, 129), ONE_129);
581 }
582}