snarkvm_utilities/
bits.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM 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
16use crate::Vec;
17
18use anyhow::{Result, ensure};
19
20/// Takes as input a sequence of objects, and converts them to a series of little-endian bits.
21/// All traits that implement `ToBits` can be automatically converted to bits in this manner.
22#[macro_export]
23macro_rules! to_bits_le {
24    ($($x:expr),*) => ({
25        let mut buffer = $crate::vec![];
26        $($x.write_bits_le(&mut buffer);)*
27        buffer
28    });
29    ($($x:expr),*; $size:expr) => ({
30        let mut buffer = $crate::Vec::with_capacity($size);
31        $($x.write_bits_le(&mut buffer);)*
32        buffer
33    });
34}
35
36pub trait ToBits: Sized {
37    /// Writes `self` into the given vector as a boolean array in little-endian order.
38    fn write_bits_le(&self, vec: &mut Vec<bool>);
39
40    /// Writes `self` into the given vector as a boolean array in big-endian order.
41    fn write_bits_be(&self, vec: &mut Vec<bool>);
42
43    /// Returns `self` as a boolean array in little-endian order.
44    fn to_bits_le(&self) -> Vec<bool> {
45        let mut bits = Vec::new();
46        self.write_bits_le(&mut bits);
47        bits
48    }
49
50    /// Returns `self` as a boolean array in big-endian order.
51    fn to_bits_be(&self) -> Vec<bool> {
52        let mut bits = Vec::new();
53        self.write_bits_be(&mut bits);
54        bits
55    }
56
57    /// An optional indication of how many bits an object can be represented with.
58    fn num_bits() -> Option<usize> {
59        None
60    }
61}
62
63pub trait FromBits: Sized {
64    /// Reads `Self` from a boolean array in little-endian order.
65    fn from_bits_le(bits: &[bool]) -> Result<Self>;
66
67    /// Reads `Self` from a boolean array in big-endian order.
68    fn from_bits_be(bits: &[bool]) -> Result<Self>;
69}
70
71/********************/
72/****** Tuples ******/
73/********************/
74
75/// A helper macro to implement `ToBits` for a tuple of `ToBits` circuits.
76macro_rules! to_bits_tuple {
77    (($t0:ident, $i0:tt), $(($ty:ident, $idx:tt)),+) => {
78        impl<$t0: ToBits, $($ty: ToBits),+> ToBits for ($t0, $($ty),+) {
79            /// A helper method to return a concatenated list of little-endian bits from the circuits.
80            #[inline]
81            fn write_bits_le(&self, vec: &mut Vec<bool>) {
82                // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out.
83                (&self).write_bits_le(vec);
84            }
85
86            /// A helper method to return a concatenated list of big-endian bits from the circuits.
87            #[inline]
88            fn write_bits_be(&self, vec: &mut Vec<bool>) {
89                // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out.
90                (&self).write_bits_be(vec);
91            }
92        }
93
94        impl<'a, $t0: ToBits, $($ty: ToBits),+> ToBits for &'a ($t0, $($ty),+) {
95            /// A helper method to return a concatenated list of little-endian bits from the circuits.
96            #[inline]
97            fn write_bits_le(&self, vec: &mut Vec<bool>) {
98                // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out.
99                self.$i0.write_bits_le(vec);
100                $(self.$idx.write_bits_le(vec);)+
101            }
102
103            /// A helper method to return a concatenated list of big-endian bits from the circuits.
104            #[inline]
105            fn write_bits_be(&self, vec: &mut Vec<bool>) {
106                // The tuple is order-preserving, meaning the first circuit in is the first circuit bits out.
107                self.$i0.write_bits_be(vec);
108                $(self.$idx.write_bits_be(vec);)+
109            }
110        }
111    }
112}
113
114to_bits_tuple!((C0, 0), (C1, 1));
115to_bits_tuple!((C0, 0), (C1, 1), (C2, 2));
116to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3));
117to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4));
118to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5));
119to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6));
120to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6), (C7, 7));
121to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6), (C7, 7), (C8, 8));
122to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6), (C7, 7), (C8, 8), (C9, 9));
123to_bits_tuple!((C0, 0), (C1, 1), (C2, 2), (C3, 3), (C4, 4), (C5, 5), (C6, 6), (C7, 7), (C8, 8), (C9, 9), (C10, 10));
124
125/********************/
126/****** Boolean *****/
127/********************/
128
129impl ToBits for bool {
130    /// A helper method to return a concatenated list of little-endian bits.
131    #[inline]
132    fn write_bits_le(&self, vec: &mut Vec<bool>) {
133        vec.push(*self);
134    }
135
136    /// A helper method to return a concatenated list of big-endian bits.
137    #[inline]
138    fn write_bits_be(&self, vec: &mut Vec<bool>) {
139        vec.push(*self);
140    }
141}
142
143/********************/
144/***** Integers *****/
145/********************/
146
147macro_rules! impl_bits_for_integer {
148    ($int:ty) => {
149        impl ToBits for $int {
150            /// Returns `self` as a boolean array in little-endian order.
151            #[inline]
152            fn write_bits_le(&self, vec: &mut Vec<bool>) {
153                let mut value = *self;
154                for _ in 0..<$int>::BITS {
155                    vec.push(value & 1 == 1);
156                    value = value.wrapping_shr(1u32);
157                }
158            }
159
160            /// Returns `self` as a boolean array in big-endian order.
161            #[inline]
162            fn write_bits_be(&self, vec: &mut Vec<bool>) {
163                let reversed = self.reverse_bits();
164                reversed.write_bits_le(vec);
165            }
166
167            fn num_bits() -> Option<usize> {
168                Some(<$int>::BITS as usize)
169            }
170        }
171
172        impl FromBits for $int {
173            /// Reads `Self` from a boolean array in little-endian order.
174            #[inline]
175            fn from_bits_le(bits: &[bool]) -> Result<Self> {
176                // If the number of bits exceeds the size of the integer, ensure that the upper bits are all zero.
177                // Note that because the input bits are little-endian, these are the bits at the end of slice.
178                for bit in bits.iter().skip(<$int>::BITS as usize) {
179                    ensure!(!bit, "upper bits are not zero");
180                }
181                // Construct the integer from the bits.
182                Ok(bits.iter().take(<$int>::BITS as usize).rev().fold(0, |value, bit| match bit {
183                    true => (value.wrapping_shl(1)) ^ 1,
184                    false => (value.wrapping_shl(1)) ^ 0,
185                }))
186            }
187
188            /// Reads `Self` from a boolean array in big-endian order.
189            #[inline]
190            fn from_bits_be(bits: &[bool]) -> Result<Self> {
191                // If the number of bits exceeds the size of the integer, ensure that the upper bits are all zero.
192                // Note that because the input bits are big-endian, these are the bits at the beginning of slice.
193                for bit in bits.iter().take(bits.len().saturating_sub(<$int>::BITS as usize)) {
194                    ensure!(!bit, "upper bits are not zero");
195                }
196                // Construct the integer from the bits.
197                Ok(bits.iter().skip(bits.len().saturating_sub(<$int>::BITS as usize)).fold(0, |value, bit| match bit {
198                    true => (value.wrapping_shl(1)) ^ 1,
199                    false => (value.wrapping_shl(1)) ^ 0,
200                }))
201            }
202        }
203    };
204}
205
206impl_bits_for_integer!(u8);
207impl_bits_for_integer!(u16);
208impl_bits_for_integer!(u32);
209impl_bits_for_integer!(u64);
210impl_bits_for_integer!(u128);
211
212impl_bits_for_integer!(i8);
213impl_bits_for_integer!(i16);
214impl_bits_for_integer!(i32);
215impl_bits_for_integer!(i64);
216impl_bits_for_integer!(i128);
217
218/********************/
219/****** String ******/
220/********************/
221
222impl ToBits for String {
223    /// A helper method to return a concatenated list of little-endian bits.
224    #[inline]
225    fn write_bits_le(&self, vec: &mut Vec<bool>) {
226        // The vector is order-preserving, meaning the first byte in is the first byte bits out.
227        self.as_bytes().write_bits_le(vec);
228    }
229
230    /// A helper method to return a concatenated list of big-endian bits.
231    #[inline]
232    fn write_bits_be(&self, vec: &mut Vec<bool>) {
233        // The vector is order-preserving, meaning the first byte in is the first byte bits out.
234        self.as_bytes().write_bits_be(vec);
235    }
236}
237
238/********************/
239/****** Arrays ******/
240/********************/
241
242impl<C: ToBits> ToBits for Vec<C> {
243    /// A helper method to return a concatenated list of little-endian bits.
244    #[inline]
245    fn write_bits_le(&self, vec: &mut Vec<bool>) {
246        // The vector is order-preserving, meaning the first variable in is the first variable bits out.
247        self.as_slice().write_bits_le(vec);
248    }
249
250    /// A helper method to return a concatenated list of big-endian bits.
251    #[inline]
252    fn write_bits_be(&self, vec: &mut Vec<bool>) {
253        // The vector is order-preserving, meaning the first variable in is the first variable bits out.
254        self.as_slice().write_bits_be(vec);
255    }
256}
257
258impl<C: ToBits, const N: usize> ToBits for [C; N] {
259    /// A helper method to return a concatenated list of little-endian bits.
260    #[inline]
261    fn write_bits_le(&self, vec: &mut Vec<bool>) {
262        // The slice is order-preserving, meaning the first variable in is the first variable bits out.
263        self.as_slice().write_bits_le(vec)
264    }
265
266    /// A helper method to return a concatenated list of big-endian bits.
267    #[inline]
268    fn write_bits_be(&self, vec: &mut Vec<bool>) {
269        // The slice is order-preserving, meaning the first variable in is the first variable bits out.
270        self.as_slice().write_bits_be(vec)
271    }
272}
273
274impl<C: ToBits> ToBits for &[C] {
275    /// A helper method to return a concatenated list of little-endian bits.
276    #[inline]
277    fn write_bits_le(&self, vec: &mut Vec<bool>) {
278        if let Some(num_bits) = C::num_bits() {
279            vec.reserve(num_bits * self.len());
280        }
281
282        for elem in self.iter() {
283            elem.write_bits_le(vec);
284        }
285    }
286
287    /// A helper method to return a concatenated list of big-endian bits.
288    #[inline]
289    fn write_bits_be(&self, vec: &mut Vec<bool>) {
290        if let Some(num_bits) = C::num_bits() {
291            vec.reserve(num_bits * self.len());
292        }
293
294        for elem in self.iter() {
295            elem.write_bits_be(vec);
296        }
297    }
298}
299
300impl FromBits for Vec<u8> {
301    /// A helper method to return `Self` from a concatenated list of little-endian bits.
302    #[inline]
303    fn from_bits_le(bits: &[bool]) -> Result<Self> {
304        // The vector is order-preserving, meaning the first variable in is the first variable bits out.
305        bits.chunks(8).map(u8::from_bits_le).collect::<Result<Vec<_>>>()
306    }
307
308    /// A helper method to return `Self` from a concatenated list of big-endian bits.
309    #[inline]
310    fn from_bits_be(bits: &[bool]) -> Result<Self> {
311        // The vector is order-preserving, meaning the first variable in is the first variable bits out.
312        bits.chunks(8).map(u8::from_bits_be).collect::<Result<Vec<_>>>()
313    }
314}
315
316#[cfg(test)]
317mod tests {
318    use super::*;
319    use crate::{TestRng, Uniform};
320
321    use anyhow::Result;
322    use rand::{Rng, distributions::Alphanumeric};
323
324    const ITERATIONS: u64 = 10000;
325
326    fn random_string(len: u16, rng: &mut TestRng) -> String {
327        rng.sample_iter(&Alphanumeric).take(len as usize).map(char::from).collect()
328    }
329
330    #[test]
331    fn test_to_bits_le_macro() {
332        let rng = &mut TestRng::default();
333
334        // The checker.
335        macro_rules! check {
336            ($given:expr) => {{
337                let given = $given;
338
339                let mut expected = Vec::new();
340                given.iter().for_each(|elem| elem.write_bits_le(&mut expected));
341
342                let candidate = to_bits_le!(given);
343                assert_eq!(candidate, expected);
344            }};
345        }
346
347        // U8
348        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u8>>());
349        // U16
350        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u16>>());
351        // U32
352        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u32>>());
353        // U64
354        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u64>>());
355        // U128
356        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<u128>>());
357        // I8
358        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i8>>());
359        // I16
360        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i16>>());
361        // I32
362        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i32>>());
363        // I64
364        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i64>>());
365        // I128
366        check!((0..100).map(|_| Uniform::rand(rng)).collect::<Vec<i128>>());
367        // String
368        check!((0..100).map(|_| random_string(rng.gen(), rng)).collect::<Vec<String>>());
369        // Vec<Vec<u8>>
370        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u8>>()).collect::<Vec<_>>());
371        // Vec<Vec<u16>>
372        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u16>>()).collect::<Vec<_>>());
373        // Vec<Vec<u32>>
374        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u32>>()).collect::<Vec<_>>());
375        // Vec<Vec<u64>>
376        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u64>>()).collect::<Vec<_>>());
377        // Vec<Vec<u128>>
378        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<u128>>()).collect::<Vec<_>>());
379        // Vec<Vec<i8>>
380        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i8>>()).collect::<Vec<_>>());
381        // Vec<Vec<i16>>
382        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i16>>()).collect::<Vec<_>>());
383        // Vec<Vec<i32>>
384        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i32>>()).collect::<Vec<_>>());
385        // Vec<Vec<i64>>
386        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i64>>()).collect::<Vec<_>>());
387        // Vec<Vec<i128>>
388        check!((0..100).map(|_| (0..128).map(|_| Uniform::rand(rng)).collect::<Vec<i128>>()).collect::<Vec<_>>());
389        // Vec<Vec<String>>
390        check!(
391            (0..100)
392                .map(|_| (0..128).map(|_| random_string(rng.gen(), rng)).collect::<Vec<String>>())
393                .collect::<Vec<_>>()
394        );
395    }
396
397    #[test]
398    fn test_to_bits_le_macro_with_capacity() {
399        let mut expected = Vec::new();
400        1u8.write_bits_le(&mut expected);
401        2u16.write_bits_le(&mut expected);
402        3u32.write_bits_le(&mut expected);
403        4u64.write_bits_le(&mut expected);
404        5u128.write_bits_le(&mut expected);
405        6i8.write_bits_le(&mut expected);
406        7i16.write_bits_le(&mut expected);
407        8i32.write_bits_le(&mut expected);
408        9i64.write_bits_le(&mut expected);
409        10i128.write_bits_le(&mut expected);
410
411        let capacity = expected.len();
412
413        let candidate = to_bits_le![1u8, 2u16, 3u32, 4u64, 5u128, 6i8, 7i16, 8i32, 9i64, 10i128; capacity];
414        assert_eq!(candidate, expected);
415    }
416
417    #[test]
418    fn test_integers() -> Result<()> {
419        macro_rules! check_integer {
420            ($integer:tt, $rng:expr) => {{
421                for _ in 0..ITERATIONS {
422                    let expected: $integer = Uniform::rand($rng);
423
424                    let bits_le = expected.to_bits_le();
425                    assert_eq!(expected, $integer::from_bits_le(&bits_le)?);
426
427                    let bits_be = expected.to_bits_be();
428                    assert_eq!(expected, $integer::from_bits_be(&bits_be)?);
429                }
430            }};
431        }
432
433        let mut rng = TestRng::default();
434
435        check_integer!(u8, &mut rng);
436        check_integer!(u16, &mut rng);
437        check_integer!(u32, &mut rng);
438        check_integer!(u64, &mut rng);
439        check_integer!(u128, &mut rng);
440
441        check_integer!(i8, &mut rng);
442        check_integer!(i16, &mut rng);
443        check_integer!(i32, &mut rng);
444        check_integer!(i64, &mut rng);
445        check_integer!(i128, &mut rng);
446
447        Ok(())
448    }
449}
snarkvm_utilities/bits.rs

snarkvm_utilities/
bits.rs
