jf_vid/advz/
bytes_to_field.rs

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

jf_vid/advz/
bytes_to_field.rs
