bits.rs
1 // Copyright (c) 2025 ADnet Contributors 2 // This file is part of the AlphaVM library. 3 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at: 7 8 // http://www.apache.org/licenses/LICENSE-2.0 9 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 16 use anyhow::{Result, ensure}; 17 18 /// Takes as input a sequence of objects, and converts them to a series of little-endian bits. 19 /// All traits that implement `ToBits` can be automatically converted to bits in this manner. 20 #[macro_export] 21 macro_rules! to_bits_le { 22 ($($x:expr),*) => ({ 23 let mut buffer = vec![]; 24 $($x.write_bits_le(&mut buffer);)* 25 buffer 26 }); 27 ($($x:expr),*; $size:expr) => ({ 28 let mut buffer = Vec::with_capacity($size); 29 $($x.write_bits_le(&mut buffer);)* 30 buffer 31 }); 32 } 33 34 /// Takes as input a sequence of objects, and converts them to a series of little-endian bits. 35 /// All traits that implement `ToBitsRaw` can be automatically converted to bits in this manner. 36 #[macro_export] 37 macro_rules! to_bits_raw_le { 38 ($($x:expr),*) => ({ 39 let mut buffer = vec![]; 40 $($x.write_bits_raw_le(&mut buffer);)* 41 buffer 42 }); 43 ($($x:expr),*; $size:expr) => ({ 44 let mut buffer = Vec::with_capacity($size); 45 $($x.write_bits_raw_le(&mut buffer);)* 46 buffer 47 }); 48 } 49 50 pub trait ToBits: Sized { 51 /// Writes `self` into the given vector as a boolean array in little-endian order. 52 fn write_bits_le(&self, vec: &mut Vec<bool>); 53 54 /// Writes `self` into the given vector as a boolean array in big-endian order. 55 fn write_bits_be(&self, vec: &mut Vec<bool>); 56 57 /// Returns `self` as a boolean array in little-endian order. 58 fn to_bits_le(&self) -> Vec<bool> { 59 let mut bits = Vec::new(); 60 self.write_bits_le(&mut bits); 61 bits 62 } 63 64 /// Returns `self` as a boolean array in big-endian order. 65 fn to_bits_be(&self) -> Vec<bool> { 66 let mut bits = Vec::new(); 67 self.write_bits_be(&mut bits); 68 bits 69 } 70 71 /// An optional indication of how many bits an object can be represented with. 72 fn num_bits() -> Option<usize> { 73 None 74 } 75 } 76 77 pub trait ToBitsRaw: ToBits + Sized { 78 /// Writes `self` into the given vector as a raw boolean array in little-endian order. 79 fn write_bits_raw_le(&self, vec: &mut Vec<bool>); 80 81 /// Writes `self` into the given vector as a boolean array in big-endian order. 82 fn write_bits_raw_be(&self, vec: &mut Vec<bool>); 83 84 /// Returns `self` as a boolean array in little-endian order. 85 fn to_bits_raw_le(&self) -> Vec<bool> { 86 let mut bits = Vec::new(); 87 self.write_bits_raw_le(&mut bits); 88 bits 89 } 90 91 /// Returns `self` as a boolean array in big-endian order. 92 fn to_bits_raw_be(&self) -> Vec<bool> { 93 let mut bits = Vec::new(); 94 self.write_bits_raw_be(&mut bits); 95 bits 96 } 97 } 98 99 pub trait FromBits: Sized { 100 /// Reads `Self` from a boolean array in little-endian order. 101 fn from_bits_le(bits: &[bool]) -> Result<Self>; 102 103 /// Reads `Self` from a boolean array in big-endian order. 104 fn from_bits_be(bits: &[bool]) -> Result<Self>; 105 } 106 107 /********************/ 108 /****** Tuples ******/ 109 /********************/ 110 111 /// A helper macro to implement `ToBits` for a tuple of `ToBits` circuits. 112 macro_rules! to_bits_tuple { 113 (($t0:ident, $i0:tt), $(($ty:ident, $idx:tt)),+) => { 114 impl<$t0: ToBits, $($ty: ToBits),+> ToBits for ($t0, $($ty),+) { 115 /// A helper method to return a concatenated list of little-endian bits from the circuits. 116 #[inline] 117 fn write_bits_le(&self, vec: &mut Vec<bool>) { 118 // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out. 119 (&self).write_bits_le(vec); 120 } 121 122 /// A helper method to return a concatenated list of big-endian bits from the circuits. 123 #[inline] 124 fn write_bits_be(&self, vec: &mut Vec<bool>) { 125 // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out. 126 (&self).write_bits_be(vec); 127 } 128 } 129 130 impl<'a, $t0: ToBits, $($ty: ToBits),+> ToBits for &'a ($t0, $($ty),+) { 131 /// A helper method to return a concatenated list of little-endian bits from the circuits. 132 #[inline] 133 fn write_bits_le(&self, vec: &mut Vec<bool>) { 134 // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out. 135 self.$i0.write_bits_le(vec); 136 $(self.$idx.write_bits_le(vec);)+ 137 } 138 139 /// A helper method to return a concatenated list of big-endian bits from the circuits. 140 #[inline] 141 fn write_bits_be(&self, vec: &mut Vec<bool>) { 142 // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out. 143 self.$i0.write_bits_be(vec); 144 $(self.$idx.write_bits_be(vec);)+ 145 } 146 } 147 148 impl<$t0: ToBitsRaw, $($ty: ToBitsRaw),+> ToBitsRaw for ($t0, $($ty),+) { 149 /// A helper method to return a concatenated list of little-endian bits without variant or identifier bits from the circuits. 150 #[inline] 151 fn write_bits_raw_le(&self, vec: &mut Vec<bool>) { 152 // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out. 153 (&self).write_bits_raw_le(vec); 154 } 155 156 /// A helper method to return a concatenated list of bits-endian bits without variant or identifier bits from the circuits. 157 #[inline] 158 fn write_bits_raw_be(&self, vec: &mut Vec<bool>) { 159 // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out. 160 (&self).write_bits_raw_be(vec); 161 } 162 } 163 164 impl<'a, $t0: ToBitsRaw, $($ty: ToBitsRaw),+> ToBitsRaw for &'a ($t0, $($ty),+) { 165 /// A helper method to return a concatenated list of little-endian bits without variant or identifier bits from the circuits. 166 #[inline] 167 fn write_bits_raw_le(&self, vec: &mut Vec<bool>) { 168 // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out. 169 self.$i0.write_bits_raw_le(vec); 170 $(self.$idx.write_bits_raw_le(vec);)+ 171 } 172 173 /// A helper method to return a concatenated list of bits-endian bits without variant or identifier bits from the circuits. 174 #[inline] 175 fn write_bits_raw_be(&self, vec: &mut Vec<bool>) { 176 // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out. 177 self.$i0.write_bits_raw_be(vec); 178 $(self.$idx.write_bits_raw_be(vec);)+ 179 } 180 } 181 } 182 } 183 184 to_bits_tuple!((C0, 0), (C1, 1)); 185 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2)); 186 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3)); 187 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4)); 188 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5)); 189 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6)); 190 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6), (C7, 7)); 191 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6), (C7, 7), (C8, 8)); 192 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6), (C7, 7), (C8, 8), (C9, 9)); 193 to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6), (C7, 7), (C8, 8), (C9, 9), (C10, 10)); 194 195 /********************/ 196 /****** Boolean *****/ 197 /********************/ 198 199 impl ToBits for bool { 200 /// A helper method to return a concatenated list of little-endian bits. 201 #[inline] 202 fn write_bits_le(&self, vec: &mut Vec<bool>) { 203 vec.push(*self); 204 } 205 206 /// A helper method to return a concatenated list of big-endian bits. 207 #[inline] 208 fn write_bits_be(&self, vec: &mut Vec<bool>) { 209 vec.push(*self); 210 } 211 } 212 213 /********************/ 214 /***** Integers *****/ 215 /********************/ 216 217 macro_rules! impl_bits_for_integer { 218 ($int:ty) => { 219 impl ToBits for $int { 220 /// Returns `self` as a boolean array in little-endian order. 221 #[inline] 222 fn write_bits_le(&self, vec: &mut Vec<bool>) { 223 let mut value = *self; 224 for _ in 0..<$int>::BITS { 225 vec.push(value & 1 == 1); 226 value = value.wrapping_shr(1u32); 227 } 228 } 229 230 /// Returns `self` as a boolean array in big-endian order. 231 #[inline] 232 fn write_bits_be(&self, vec: &mut Vec<bool>) { 233 let reversed = self.reverse_bits(); 234 reversed.write_bits_le(vec); 235 } 236 237 fn num_bits() -> Option<usize> { 238 Some(<$int>::BITS as usize) 239 } 240 } 241 242 impl FromBits for $int { 243 /// Reads `Self` from a boolean array in little-endian order. 244 #[inline] 245 fn from_bits_le(bits: &[bool]) -> Result<Self> { 246 // If the number of bits exceeds the size of the integer, ensure that the upper bits are all zero. 247 // Note that because the input bits are little-endian, these are the bits at the end of slice. 248 for bit in bits.iter().skip(<$int>::BITS as usize) { 249 ensure!(!bit, "upper bits are not zero"); 250 } 251 // Construct the integer from the bits. 252 Ok(bits.iter().take(<$int>::BITS as usize).rev().fold(0, |value, bit| match bit { 253 true => (value.wrapping_shl(1)) ^ 1, 254 false => (value.wrapping_shl(1)) ^ 0, 255 })) 256 } 257 258 /// Reads `Self` from a boolean array in big-endian order. 259 #[inline] 260 fn from_bits_be(bits: &[bool]) -> Result<Self> { 261 // If the number of bits exceeds the size of the integer, ensure that the upper bits are all zero. 262 // Note that because the input bits are big-endian, these are the bits at the beginning of slice. 263 for bit in bits.iter().take(bits.len().saturating_sub(<$int>::BITS as usize)) { 264 ensure!(!bit, "upper bits are not zero"); 265 } 266 // Construct the integer from the bits. 267 Ok(bits.iter().skip(bits.len().saturating_sub(<$int>::BITS as usize)).fold(0, |value, bit| match bit { 268 true => (value.wrapping_shl(1)) ^ 1, 269 false => (value.wrapping_shl(1)) ^ 0, 270 })) 271 } 272 } 273 }; 274 } 275 276 impl_bits_for_integer!(u8); 277 impl_bits_for_integer!(u16); 278 impl_bits_for_integer!(u32); 279 impl_bits_for_integer!(u64); 280 impl_bits_for_integer!(u128); 281 282 impl_bits_for_integer!(i8); 283 impl_bits_for_integer!(i16); 284 impl_bits_for_integer!(i32); 285 impl_bits_for_integer!(i64); 286 impl_bits_for_integer!(i128); 287 288 /********************/ 289 /****** String ******/ 290 /********************/ 291 292 impl ToBits for String { 293 /// A helper method to return a concatenated list of little-endian bits. 294 #[inline] 295 fn write_bits_le(&self, vec: &mut Vec<bool>) { 296 // The vector is order-preserving, meaning the first byte in is the first byte bits out. 297 self.as_bytes().write_bits_le(vec); 298 } 299 300 /// A helper method to return a concatenated list of big-endian bits. 301 #[inline] 302 fn write_bits_be(&self, vec: &mut Vec<bool>) { 303 // The vector is order-preserving, meaning the first byte in is the first byte bits out. 304 self.as_bytes().write_bits_be(vec); 305 } 306 } 307 308 /********************/ 309 /****** Arrays ******/ 310 /********************/ 311 312 impl<C: ToBits> ToBits for Vec<C> { 313 /// A helper method to return a concatenated list of little-endian bits. 314 #[inline] 315 fn write_bits_le(&self, vec: &mut Vec<bool>) { 316 // The vector is order-preserving, meaning the first variable in is the first variable bits out. 317 self.as_slice().write_bits_le(vec); 318 } 319 320 /// A helper method to return a concatenated list of big-endian bits. 321 #[inline] 322 fn write_bits_be(&self, vec: &mut Vec<bool>) { 323 // The vector is order-preserving, meaning the first variable in is the first variable bits out. 324 self.as_slice().write_bits_be(vec); 325 } 326 } 327 328 impl<C: ToBits, const N: usize> ToBits for [C; N] { 329 /// A helper method to return a concatenated list of little-endian bits. 330 #[inline] 331 fn write_bits_le(&self, vec: &mut Vec<bool>) { 332 // The slice is order-preserving, meaning the first variable in is the first variable bits out. 333 self.as_slice().write_bits_le(vec) 334 } 335 336 /// A helper method to return a concatenated list of big-endian bits. 337 #[inline] 338 fn write_bits_be(&self, vec: &mut Vec<bool>) { 339 // The slice is order-preserving, meaning the first variable in is the first variable bits out. 340 self.as_slice().write_bits_be(vec) 341 } 342 } 343 344 impl<C: ToBits> ToBits for &[C] { 345 /// A helper method to return a concatenated list of little-endian bits. 346 #[inline] 347 fn write_bits_le(&self, vec: &mut Vec<bool>) { 348 if let Some(num_bits) = C::num_bits() { 349 vec.reserve(num_bits * self.len()); 350 } 351 352 for elem in self.iter() { 353 elem.write_bits_le(vec); 354 } 355 } 356 357 /// A helper method to return a concatenated list of big-endian bits. 358 #[inline] 359 fn write_bits_be(&self, vec: &mut Vec<bool>) { 360 if let Some(num_bits) = C::num_bits() { 361 vec.reserve(num_bits * self.len()); 362 } 363 364 for elem in self.iter() { 365 elem.write_bits_be(vec); 366 } 367 } 368 } 369 370 impl<C: ToBitsRaw> ToBitsRaw for Vec<C> { 371 /// A helper method to return a concatenated list of little-endian bits. 372 #[inline] 373 fn write_bits_raw_le(&self, vec: &mut Vec<bool>) { 374 // The vector is order-preserving, meaning the first variable in is the first variable bits out. 375 self.as_slice().write_bits_raw_le(vec); 376 } 377 378 /// A helper method to return a concatenated list of big-endian bits. 379 #[inline] 380 fn write_bits_raw_be(&self, vec: &mut Vec<bool>) { 381 // The vector is order-preserving, meaning the first variable in is the first variable bits out. 382 self.as_slice().write_bits_raw_be(vec); 383 } 384 } 385 386 impl<C: ToBitsRaw, const N: usize> ToBitsRaw for [C; N] { 387 /// A helper method to return a concatenated list of little-endian bits. 388 #[inline] 389 fn write_bits_raw_le(&self, vec: &mut Vec<bool>) { 390 // The slice is order-preserving, meaning the first variable in is the first variable bits out. 391 self.as_slice().write_bits_raw_le(vec) 392 } 393 394 /// A helper method to return a concatenated list of big-endian bits. 395 #[inline] 396 fn write_bits_raw_be(&self, vec: &mut Vec<bool>) { 397 // The slice is order-preserving, meaning the first variable in is the first variable bits out. 398 self.as_slice().write_bits_raw_be(vec) 399 } 400 } 401 402 impl<C: ToBitsRaw> ToBitsRaw for &[C] { 403 /// A helper method to return a concatenated list of little-endian bits. 404 #[inline] 405 fn write_bits_raw_le(&self, vec: &mut Vec<bool>) { 406 if let Some(num_bits) = C::num_bits() { 407 vec.reserve(num_bits * self.len()); 408 } 409 410 for elem in self.iter() { 411 elem.write_bits_raw_le(vec); 412 } 413 } 414 415 /// A helper method to return a concatenated list of big-endian bits. 416 #[inline] 417 fn write_bits_raw_be(&self, vec: &mut Vec<bool>) { 418 if let Some(num_bits) = C::num_bits() { 419 vec.reserve(num_bits * self.len()); 420 } 421 422 for elem in self.iter() { 423 elem.write_bits_raw_be(vec); 424 } 425 } 426 } 427 428 impl FromBits for Vec<u8> { 429 /// A helper method to return `Self` from a concatenated list of little-endian bits. 430 #[inline] 431 fn from_bits_le(bits: &[bool]) -> Result<Self> { 432 // The vector is order-preserving, meaning the first variable in is the first variable bits out. 433 bits.chunks(8).map(u8::from_bits_le).collect::<Result<Vec<_>>>() 434 } 435 436 /// A helper method to return `Self` from a concatenated list of big-endian bits. 437 #[inline] 438 fn from_bits_be(bits: &[bool]) -> Result<Self> { 439 // The vector is order-preserving, meaning the first variable in is the first variable bits out. 440 bits.chunks(8).map(u8::from_bits_be).collect::<Result<Vec<_>>>() 441 } 442 } 443 444 #[cfg(test)] 445 mod tests { 446 use super::*; 447 use crate::{TestRng, Uniform}; 448 449 use anyhow::Result; 450 use rand::{Rng, distributions::Alphanumeric}; 451 452 const ITERATIONS: u64 = 10000; 453 454 fn random_string(len: u16, rng: &mut TestRng) -> String { 455 rng.sample_iter(&Alphanumeric).take(len as usize).map(char::from).collect() 456 } 457 458 #[test] 459 fn test_to_bits_le_macro() { 460 let rng = &mut TestRng::default(); 461 462 // The checker. 463 macro_rules! check { 464 ($given:expr) => {{ 465 let given = $given; 466 467 let mut expected = Vec::new(); 468 given.iter().for_each(|elem| elem.write_bits_le(&mut expected)); 469 470 let candidate = to_bits_le!(given); 471 assert_eq!(candidate, expected); 472 }}; 473 } 474 475 // U8 476 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u8>>()); 477 // U16 478 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u16>>()); 479 // U32 480 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u32>>()); 481 // U64 482 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u64>>()); 483 // U128 484 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u128>>()); 485 // I8 486 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i8>>()); 487 // I16 488 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i16>>()); 489 // I32 490 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i32>>()); 491 // I64 492 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i64>>()); 493 // I128 494 check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i128>>()); 495 // String 496 check!((0..100).map(|_| random_string(rng.r#gen(), rng)).collect::<Vec<String>>()); 497 // Vec<Vec<u8>> 498 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u8>>()).collect::<Vec<_>>()); 499 // Vec<Vec<u16>> 500 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u16>>()).collect::<Vec<_>>()); 501 // Vec<Vec<u32>> 502 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u32>>()).collect::<Vec<_>>()); 503 // Vec<Vec<u64>> 504 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u64>>()).collect::<Vec<_>>()); 505 // Vec<Vec<u128>> 506 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u128>>()).collect::<Vec<_>>()); 507 // Vec<Vec<i8>> 508 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i8>>()).collect::<Vec<_>>()); 509 // Vec<Vec<i16>> 510 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i16>>()).collect::<Vec<_>>()); 511 // Vec<Vec<i32>> 512 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i32>>()).collect::<Vec<_>>()); 513 // Vec<Vec<i64>> 514 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i64>>()).collect::<Vec<_>>()); 515 // Vec<Vec<i128>> 516 check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i128>>()).collect::<Vec<_>>()); 517 // Vec<Vec<String>> 518 check!( 519 (0..100) 520 .map(|_| (0..128).map(|_| random_string(rng.r#gen(), rng)).collect::<Vec<String>>()) 521 .collect::<Vec<_>>() 522 ); 523 } 524 525 #[test] 526 fn test_to_bits_le_macro_with_capacity() { 527 let mut expected = Vec::new(); 528 1u8.write_bits_le(&mut expected); 529 2u16.write_bits_le(&mut expected); 530 3u32.write_bits_le(&mut expected); 531 4u64.write_bits_le(&mut expected); 532 5u128.write_bits_le(&mut expected); 533 6i8.write_bits_le(&mut expected); 534 7i16.write_bits_le(&mut expected); 535 8i32.write_bits_le(&mut expected); 536 9i64.write_bits_le(&mut expected); 537 10i128.write_bits_le(&mut expected); 538 539 let capacity = expected.len(); 540 541 let candidate = to_bits_le![1u8, 2u16, 3u32, 4u64, 5u128, 6i8, 7i16, 8i32, 9i64, 10i128; capacity]; 542 assert_eq!(candidate, expected); 543 } 544 545 #[test] 546 fn test_integers() -> Result<()> { 547 macro_rules! check_integer { 548 ($integer:tt, $rng:expr) => {{ 549 for _ in 0..ITERATIONS { 550 let expected: $integer = Uniform::rand($rng); 551 552 let bits_le = expected.to_bits_le(); 553 assert_eq!(expected, $integer::from_bits_le(&bits_le)?); 554 555 let bits_be = expected.to_bits_be(); 556 assert_eq!(expected, $integer::from_bits_be(&bits_be)?); 557 } 558 }}; 559 } 560 561 let mut rng = TestRng::default(); 562 563 check_integer!(u8, &mut rng); 564 check_integer!(u16, &mut rng); 565 check_integer!(u32, &mut rng); 566 check_integer!(u64, &mut rng); 567 check_integer!(u128, &mut rng); 568 569 check_integer!(i8, &mut rng); 570 check_integer!(i16, &mut rng); 571 check_integer!(i32, &mut rng); 572 check_integer!(i64, &mut rng); 573 check_integer!(i128, &mut rng); 574 575 Ok(()) 576 } 577 }