snarkvm_utilities/
bits.rs

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