vid/utils/
bytes_to_field.rs

1use std::{
2    borrow::Borrow,
3    iter::Take,
4    marker::PhantomData,
5    vec::{IntoIter, Vec},
6};
7
8use ark_ff::{BigInteger, PrimeField};
9
10/// Deterministic, infallible, invertible iterator adaptor to convert from
11/// arbitrary bytes to field elements.
12///
13/// The final field element is padded with zero bytes as needed.
14///
15/// # Example
16///
17/// [doctest ignored because it's a private module.]
18/// ```ignore
19/// # use jf_vid::advz::{bytes_to_field};
20/// # use ark_ed_on_bn254::Fr as Fr254;
21/// let bytes = [1, 2, 3];
22/// let mut elems_iter = bytes_to_field::<_, Fr254>(bytes);
23/// assert_eq!(elems_iter.next(), Some(Fr254::from(197121u64)));
24/// assert_eq!(elems_iter.next(), None);
25/// ```
26///
27/// # Panics
28///
29/// Panics only under conditions that should be checkable at compile time:
30///
31/// - The [`PrimeField`] modulus bit length is too small to hold a `u64`.
32/// - The [`PrimeField`] byte length is too large to fit inside a `usize`.
33///
34/// If any of the above conditions holds then this function *always* panics.
35pub fn bytes_to_field<I, F>(bytes: I) -> impl Iterator<Item = F>
36where
37    F: PrimeField,
38    I: IntoIterator,
39    I::Item: Borrow<u8>,
40{
41    BytesToField::new(bytes.into_iter())
42}
43
44/// Deterministic, infallible inverse of [`bytes_to_field`].
45///
46/// The composition of [`field_to_bytes`] with [`bytes_to_field`] might contain
47/// extra zero bytes.
48///
49/// # Example
50///
51/// [doctest ignored because it's a private module.]
52/// ```ignore
53/// # use jf_vid::advz::{bytes_to_field, field_to_bytes};
54/// # use ark_ed_on_bn254::Fr as Fr254;
55/// let bytes = [1, 2, 3];
56/// let mut bytes_iter = field_to_bytes(bytes_to_field::<_, Fr254>(bytes));
57/// assert_eq!(bytes_iter.next(), Some(1));
58/// assert_eq!(bytes_iter.next(), Some(2));
59/// assert_eq!(bytes_iter.next(), Some(3));
60/// for _ in 0..28 {
61///     assert_eq!(bytes_iter.next(), Some(0));
62/// }
63/// assert_eq!(bytes_iter.next(), None);
64/// ```
65///
66/// ## Panics
67///
68/// Panics under the conditions listed at [`bytes_to_field`].
69pub fn field_to_bytes<I, F>(elems: I) -> impl Iterator<Item = u8>
70where
71    F: PrimeField,
72    I: IntoIterator,
73    I::Item: Borrow<F>,
74{
75    FieldToBytes::new(elems.into_iter())
76}
77
78struct BytesToField<I, F> {
79    bytes_iter: I,
80    elem_byte_capacity: usize,
81    _phantom: PhantomData<F>,
82}
83
84impl<I, F> BytesToField<I, F>
85where
86    F: PrimeField,
87{
88    fn new(bytes_iter: I) -> Self {
89        Self {
90            bytes_iter,
91            elem_byte_capacity: elem_byte_capacity::<F>(),
92            _phantom: PhantomData,
93        }
94    }
95}
96
97impl<I, F> Iterator for BytesToField<I, F>
98where
99    I: Iterator,
100    I::Item: Borrow<u8>,
101    F: PrimeField,
102{
103    type Item = F;
104
105    fn next(&mut self) -> Option<Self::Item> {
106        let mut elem_bytes = Vec::with_capacity(self.elem_byte_capacity);
107        for _ in 0..elem_bytes.capacity() {
108            if let Some(byte) = self.bytes_iter.next() {
109                elem_bytes.push(*byte.borrow());
110            } else {
111                break;
112            }
113        }
114        if elem_bytes.is_empty() {
115            None
116        } else {
117            Some(F::from_le_bytes_mod_order(&elem_bytes))
118        }
119    }
120}
121
122struct FieldToBytes<I, F> {
123    elems_iter: I,
124    bytes_iter: Take<IntoIter<u8>>,
125    elem_byte_capacity: usize,
126    _phantom: PhantomData<F>,
127}
128
129impl<I, F> FieldToBytes<I, F>
130where
131    F: PrimeField,
132{
133    fn new(elems_iter: I) -> Self {
134        Self {
135            elems_iter,
136            bytes_iter: Vec::new().into_iter().take(0),
137            elem_byte_capacity: elem_byte_capacity::<F>(),
138            _phantom: PhantomData,
139        }
140    }
141}
142
143impl<I, F> Iterator for FieldToBytes<I, F>
144where
145    I: Iterator,
146    I::Item: Borrow<F>,
147    F: PrimeField,
148{
149    type Item = u8;
150
151    fn next(&mut self) -> Option<Self::Item> {
152        if let Some(byte) = self.bytes_iter.next() {
153            return Some(byte);
154        }
155        if let Some(elem) = self.elems_iter.next() {
156            self.bytes_iter = elem
157                .borrow()
158                .into_bigint()
159                .to_bytes_le()
160                .into_iter()
161                .take(self.elem_byte_capacity);
162            return self.bytes_iter.next();
163        }
164        None
165    }
166}
167
168/// Return the number of bytes that can be encoded into a generic [`PrimeField`]
169/// parameter.
170///
171/// Returns the byte length of the [`PrimeField`] modulus minus 1.
172///
173/// It should be possible to do all this at compile time but I don't know how.
174/// Want to panic on overflow, so use checked arithmetic and type conversion.
175pub fn elem_byte_capacity<F: PrimeField>() -> usize {
176    usize::try_from((F::MODULUS_BIT_SIZE - 1) / 8)
177        .expect("prime field modulus byte len should fit into usize")
178}
179
180#[cfg(test)]
181mod tests {
182    use ark_bls12_381::Fr as Fr381;
183    use ark_bn254::Fr as Fr254;
184    use rand::RngCore;
185
186    use super::{bytes_to_field, field_to_bytes, PrimeField, Vec};
187
188    fn bytes_to_field_iter<F: PrimeField>() {
189        let byte_lens = [0, 1, 2, 16, 31, 32, 33, 48, 65, 100, 200, 5000];
190
191        let max_len = *byte_lens.iter().max().unwrap();
192        let mut bytes = Vec::with_capacity(max_len);
193        // TODO pre-allocate space for elems, owned, borrowed
194        let mut rng = jf_utils::test_rng();
195
196        for len in byte_lens {
197            // fill bytes with random bytes and trailing zeros
198            bytes.resize(len, 0);
199            rng.fill_bytes(&mut bytes);
200
201            // round trip, owned:
202            // bytes as Iterator<Item = u8>, elems as Iterator<Item = F>
203            let owned: Vec<_> = field_to_bytes(bytes_to_field::<_, F>(bytes.clone()))
204                .take(bytes.len())
205                .collect();
206            assert_eq!(owned, bytes);
207
208            // round trip, borrowed:
209            // bytes as Iterator<Item = &u8>, elems as Iterator<Item = &F>
210            let elems: Vec<_> = bytes_to_field::<_, F>(bytes.iter()).collect();
211            let borrowed: Vec<_> = field_to_bytes::<_, F>(elems.iter())
212                .take(bytes.len())
213                .collect();
214            assert_eq!(borrowed, bytes);
215        }
216
217        // empty input -> empty output
218        let bytes = Vec::new();
219        assert!(bytes.is_empty());
220        let mut elems_iter = bytes_to_field::<_, F>(bytes.iter());
221        assert!(elems_iter.next().is_none());
222
223        // 1-item input -> 1-item output
224        let bytes = [42u8; 1];
225        let mut elems_iter = bytes_to_field::<_, F>(bytes.iter());
226        assert_eq!(elems_iter.next().unwrap(), F::from(42u64));
227        assert!(elems_iter.next().is_none());
228    }
229
230    #[test]
231    fn test_bytes_field_elems_iter() {
232        bytes_to_field_iter::<Fr254>();
233        bytes_to_field_iter::<Fr381>();
234    }
235}
vid/utils/bytes_to_field.rs

vid/utils/
bytes_to_field.rs
