hacspec_lib/
seq.rs

1//!
2//! # Sequences
3//!
4//! This module implements variable-length sequences and utility functions for it.
5//! Seq only supports operations that are safe on secret values.
6//! For use with public values you can use `PublicSeq`.
7//!
8
9use crate::prelude::*;
10
11mod bytes;
12pub use bytes::*;
13
14macro_rules! declare_seq {
15    ($name:ident, $constraint:ident) => {
16        /// Variable length byte arrays.
17        #[derive(Debug, Clone, Default)]
18        pub struct $name<T: Default + $constraint> {
19            pub(crate) b: Vec<T>,
20        }
21        declare_seq_with_contents_constraints_impl!($name, Clone + Default + $constraint);
22    };
23    ($name:ident) => {
24        /// Variable length byte arrays.
25        #[derive(Debug, Clone, Default)]
26        pub struct $name<T: Default> {
27            pub(crate) b: Vec<T>,
28        }
29
30        declare_seq_with_contents_constraints_impl!($name, Clone + Default);
31    };
32}
33
34macro_rules! declare_seq_with_contents_constraints_impl {
35    ($name:ident, $bound:tt $(+ $others:tt )*) => {
36
37        impl<T: $bound $(+ $others)*> $name<T> {
38            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
39            pub fn new(l: usize) -> Self {
40                Self {
41                    b: vec![T::default(); l],
42                }
43            }
44
45            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
46            pub fn with_capacity(l: usize) -> Self {
47                Self {
48                    b: Vec::with_capacity(l),
49                }
50            }
51
52            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
53            #[inline(always)]
54            pub fn reserve(mut self, additional: usize) -> Self {
55                self.b.reserve(additional);
56                self
57            }
58
59            /// Get the size of this sequence.
60            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
61            pub fn len(&self) -> usize {
62                self.b.len()
63            }
64
65            #[cfg_attr(feature="use_attributes", in_hacspec)]
66            pub fn slice(&self, start_out: usize, len: usize) -> Self {
67                Self::from_slice(self, start_out, len)
68            }
69
70            #[cfg_attr(feature="use_attributes", not_hacspec)]
71            pub fn native_slice(&self) -> &[T] {
72                &self.b
73            }
74
75            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
76            pub fn into_slice(mut self, start_out: usize, len: usize) -> Self {
77                self.b = self.b.drain(start_out..start_out+len).collect();
78                self
79            }
80
81            #[cfg_attr(feature="use_attributes", in_hacspec)]
82            pub fn slice_range(&self, r: Range<usize>) -> Self {
83                self.slice(r.start, r.end - r.start)
84            }
85
86            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
87            pub fn into_slice_range(mut self, r: Range<usize>) -> Self {
88                self.b = self.b.drain(r).collect();
89                self
90            }
91
92            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
93            #[inline(always)]
94            pub fn split_off(mut self, at: usize) -> (Self, Self) {
95                let other = Self::from_vec(self.b.split_off(at));
96                (self, other)
97            }
98
99            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
100            #[inline(always)]
101            pub fn pop(mut self) -> (T, Self) {
102                let other = Self::from_vec(self.b.split_off(1));
103                let first = self.b.pop().unwrap();
104                (first, other)
105            }
106
107            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
108            #[inline(always)]
109            pub fn truncate(mut self, len: usize) -> Self  {
110                self.b.truncate(len);
111                self
112            }
113
114            #[cfg_attr(feature="use_attributes", in_hacspec)]
115            pub fn from_slice<A: SeqTrait<T>>(input: &A, start: usize, len: usize) -> Self {
116                let mut a = Self::new(len);
117                a = a.update_slice(0, input, start, len);
118                a
119            }
120
121            #[cfg_attr(feature="use_attributes", in_hacspec)]
122            pub fn concat<A: SeqTrait<T>>(&self, next: &A) -> Self {
123                let mut out = Self::new(self.len() + next.len());
124                out = out.update_start(self);
125                out = out.update_slice(self.len(), next, 0, next.len());
126                out
127            }
128
129            #[cfg_attr(feature="use_attributes", in_hacspec)]
130            #[inline(always)]
131            pub fn concat_owned(mut self, mut next: Self) -> Self {
132                self.b.append(&mut next.b);
133                self
134            }
135
136            #[cfg_attr(feature="use_attributes", in_hacspec)]
137            pub fn push(&self, next: &T) -> Self {
138                let mut out = Self::new(self.len() + 1);
139                out = out.update_start(self);
140                out[self.len()] = next.clone();
141                out
142            }
143
144            #[cfg_attr(feature="use_attributes", in_hacspec)]
145            pub fn push_owned(mut self, next: T) -> Self {
146                self.b.push(next);
147                self
148            }
149
150            #[cfg_attr(feature="use_attributes", in_hacspec)]
151            pub fn from_slice_range<A: SeqTrait<T>>(input: &A, r: Range<usize>) -> Self {
152                Self::from_slice(input, r.start, r.end - r.start)
153            }
154
155            #[cfg_attr(feature="use_attributes", in_hacspec)]
156            pub fn num_chunks(
157                &self,
158                chunk_size: usize
159            ) -> usize {
160                (self.len() + chunk_size - 1) / chunk_size
161            }
162
163            /// Get the number of chunks of `chunk_size` in this array.
164            /// There might be less than `chunk_size` remaining elements in this
165            /// array beyond these.
166            #[cfg_attr(feature = "use_attributes", in_hacspec)]
167            pub fn num_exact_chunks(&self, chunk_size: usize) -> usize {
168                self.len() / chunk_size
169            }
170
171            #[cfg_attr(feature="use_attributes", in_hacspec)]
172            pub fn get_chunk(
173                &self,
174                chunk_size: usize,
175                chunk_number: usize
176            ) -> (usize, Self) {
177                let idx_start = chunk_size * chunk_number;
178                let len = if idx_start + chunk_size > self.len() {
179                    self.len() - idx_start
180                } else {
181                    chunk_size
182                };
183                let out = self.slice(idx_start, len);
184                (len, out)
185            }
186
187            /// Get the `chunk_number` chunk of `chunk_size` from this array
188            /// as `Seq<T>`.
189            /// The resulting sequence is of exactly `chunk_size` length.
190            /// Until #84 is fixed this returns an empty sequence if not enough
191            /// elements are left.
192            #[cfg_attr(feature = "use_attributes", in_hacspec)]
193            pub fn get_exact_chunk(&self, chunk_size: usize, chunk_number: usize) -> Self {
194                let (len, chunk) = self.get_chunk(chunk_size, chunk_number);
195                if len != chunk_size {
196                   Self::new(0)
197                } else {
198                    chunk
199                }
200            }
201
202            /// Get the remaining chunk of this array of length less than
203            /// `chunk_size`.
204            /// If there's no remainder, i.e. if the length of this array can
205            /// be divided by `chunk_size` without a remainder, the function
206            /// returns an empty sequence (until #84 is fixed).
207            #[cfg_attr(feature = "use_attributes", in_hacspec)]
208            pub fn get_remainder_chunk(&self, chunk_size: usize) -> Self {
209                let chunks = self.num_chunks(chunk_size);
210                let last_chunk = if chunks > 0 {
211                    chunks - 1
212                } else {
213                    0
214                };
215                let (len, chunk) = self.get_chunk(chunk_size, last_chunk);
216                if len == chunk_size {
217                    Self::new(0)
218                } else {
219                    chunk
220                }
221            }
222
223            #[cfg_attr(feature="use_attributes", in_hacspec)]
224            pub fn set_chunk<A: SeqTrait<T>>(
225                self,
226                chunk_size: usize,
227                chunk_number: usize,
228                input: &A,
229            ) -> Self {
230                let idx_start = chunk_size * chunk_number;
231                let len = if idx_start + chunk_size > self.len() {
232                    self.len() - idx_start
233                } else {
234                    chunk_size
235                };
236                debug_assert!(input.len() == len, "the chunk length should match the input. got {}, expected {}", input.len(), len);
237                self.update_slice(idx_start, input, 0, len)
238            }
239
240            #[cfg_attr(feature="use_attributes", in_hacspec)]
241            pub fn set_exact_chunk<A: SeqTrait<T>>(
242                self,
243                chunk_size: usize,
244                chunk_number: usize,
245                input: &A,
246            ) -> Self {
247                debug_assert!(input.len() == chunk_size, "the chunk length must match the chunk_size. got {}, expected {}", input.len(), chunk_size);
248                let idx_start = chunk_size * chunk_number;
249                debug_assert!(idx_start + chunk_size <= self.len(), "not enough space for a full chunk. space left: {}, needed {}", input.len(), chunk_size);
250                self.update_slice(idx_start, input, 0, chunk_size)
251            }
252
253            #[cfg_attr(feature = "use_attributes", in_hacspec($name))]
254            pub fn update_owned(
255                mut self,
256                start_out: usize,
257                mut v: Self,
258            ) -> Self {
259                debug_assert!(self.len() >= start_out + v.len(), "{} < {} + {}", self.len(), start_out, v.len());
260                for (o, i) in self.b.iter_mut().skip(start_out).zip(v.b.drain(..)) {
261                    *o = i;
262                }
263                self
264            }
265        }
266
267        impl<T: $bound $(+ $others)*> SeqTrait<T> for $name<T> {
268            /// Get a new sequence of capacity `l`.
269            #[cfg_attr(feature="use_attributes", in_hacspec)]
270            fn create(l: usize) -> Self {
271                Self::new(l)
272            }
273
274            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
275            fn len(&self) -> usize {
276                self.b.len()
277            }
278            #[cfg_attr(feature="use_attributes", not_hacspec)]
279            fn iter(&self) -> core::slice::Iter<T> {
280                self.b.iter()
281            }
282
283            #[cfg_attr(feature = "use_attributes", in_hacspec($name))]
284            fn update_slice<A: SeqTrait<T>>(
285                mut self,
286                start_out: usize,
287                v: &A,
288                start_in: usize,
289                len: usize,
290            ) -> Self {
291                debug_assert!(self.len() >= start_out + len, "{} < {} + {}", self.len(), start_out, len);
292                debug_assert!(v.len() >= start_in + len, "{} < {} + {}", v.len(), start_in, len);
293                for i in 0..len {
294                    self[start_out + i] = v[start_in + i].clone();
295                }
296                self
297            }
298
299            #[cfg_attr(feature = "use_attributes", in_hacspec($name))]
300            fn update<A: SeqTrait<T>>(self, start: usize, v: &A) -> Self {
301                let len = v.len();
302                self.update_slice(start, v, 0, len)
303            }
304
305            #[cfg_attr(feature = "use_attributes", in_hacspec($name))]
306            fn update_start<A: SeqTrait<T>>(self, v: &A) -> Self {
307                let len = v.len();
308                self.update_slice(0, v, 0, len)
309            }
310        }
311
312        impl<T: $bound $(+ $others)*> Index<u8> for $name<T> {
313            type Output = T;
314            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
315            fn index(&self, i: u8) -> &T {
316                &self.b[i as usize]
317            }
318        }
319
320        impl<T: $bound $(+ $others)*> IndexMut<u8> for $name<T> {
321            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
322            fn index_mut(&mut self, i: u8) -> &mut T {
323                &mut self.b[i as usize]
324            }
325        }
326
327        impl<T: $bound $(+ $others)*> Index<u32> for $name<T> {
328            type Output = T;
329            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
330            fn index(&self, i: u32) -> &T {
331                &self.b[i as usize]
332            }
333        }
334
335        impl<T: $bound $(+ $others)*> IndexMut<u32> for $name<T> {
336            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
337            fn index_mut(&mut self, i: u32) -> &mut T {
338                &mut self.b[i as usize]
339            }
340        }
341
342        impl<T: $bound $(+ $others)*> Index<i32> for $name<T> {
343            type Output = T;
344            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
345            fn index(&self, i: i32) -> &T {
346                &self.b[i as usize]
347            }
348        }
349
350        impl<T: $bound $(+ $others)*> IndexMut<i32> for $name<T> {
351            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
352            fn index_mut(&mut self, i: i32) -> &mut T {
353                &mut self.b[i as usize]
354            }
355        }
356
357        impl<T: $bound $(+ $others)*> Index<usize> for $name<T> {
358            type Output = T;
359            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
360            fn index(&self, i: usize) -> &T {
361                &self.b[i]
362            }
363        }
364
365        impl<T: $bound $(+ $others)*> IndexMut<usize> for $name<T> {
366            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
367            fn index_mut(&mut self, i: usize) -> &mut T {
368                &mut self.b[i]
369            }
370        }
371
372        impl<T: $bound $(+ $others)*> Index<Range<usize>> for $name<T> {
373            type Output = [T];
374            #[cfg_attr(feature="use_attributes", unsafe_hacspec)]
375            fn index(&self, r: Range<usize>) -> &[T] {
376                &self.b[r]
377            }
378        }
379
380        impl<T: $bound $(+ $others)*> $name<T> {
381            #[cfg_attr(feature="use_attributes", not_hacspec)]
382            pub fn from_vec(b: Vec<T>) -> $name<T> {
383                Self {
384                    b,
385                }
386            }
387
388            #[cfg_attr(feature="use_attributes", not_hacspec)]
389            pub fn from_native_slice(x: &[T]) -> $name<T> {
390                Self {
391                    b: x.to_vec(),
392                }
393            }
394
395            #[cfg_attr(feature="use_attributes", in_hacspec)]
396            pub fn from_seq<U: SeqTrait<T>>(x: &U) -> $name<T> {
397                let mut tmp = $name::new(x.len());
398                for i in 0..x.len() {
399                    tmp[i] = x[i].clone();
400                }
401                tmp
402            }
403        }
404    };
405}
406
407declare_seq!(SecretSeq, SecretInteger);
408declare_seq!(PublicSeq, PublicInteger);
409declare_seq!(Seq);
410
411pub type ByteSeq = Seq<U8>;
412pub type PublicByteSeq = PublicSeq<u8>;
413
414/// Read hex string to Bytes.
415impl Seq<U8> {
416    #[cfg_attr(feature = "use_attributes", not_hacspec)]
417    pub fn from_hex(s: &str) -> Seq<U8> {
418        Seq::from_vec(
419            hex_string_to_bytes(s)
420                .iter()
421                .map(|x| U8::classify(*x))
422                .collect::<Vec<_>>(),
423        )
424    }
425
426    #[cfg_attr(feature = "use_attributes", not_hacspec)]
427    pub fn from_string(s: String) -> Seq<U8> {
428        Seq::<U8>::from_vec(
429            hex_string_to_bytes(&s)
430                .iter()
431                .map(|x| U8::classify(*x))
432                .collect::<Vec<_>>(),
433        )
434    }
435}
436
437impl<T: Copy + Default + PartialEq + PublicInteger> PartialEq for PublicSeq<T> {
438    #[cfg_attr(feature = "use_attributes", not_hacspec)]
439    fn eq(&self, other: &Self) -> bool {
440        self.b == other.b
441    }
442}
443
444impl<T: Copy + Default + PartialEq + PublicInteger> PartialEq for Seq<T> {
445    #[cfg_attr(feature = "use_attributes", not_hacspec)]
446    fn eq(&self, other: &Self) -> bool {
447        self.b == other.b
448    }
449}
450
451impl<T: Copy + Default + PartialEq + PublicInteger> Eq for PublicSeq<T> {}
452
453impl PartialEq for Seq<U8> {
454    #[cfg_attr(feature = "use_attributes", not_hacspec)]
455    fn eq(&self, other: &Self) -> bool {
456        self.b[..]
457            .iter()
458            .map(|x| <U8>::declassify(*x))
459            .collect::<Vec<_>>()
460            == other.b[..]
461                .iter()
462                .map(|x| <U8>::declassify(*x))
463                .collect::<Vec<_>>()
464    }
465}
466
467#[macro_export]
468macro_rules! assert_secret_seq_eq {
469    ( $a1: expr, $a2: expr, $si: ident) => {
470        assert_eq!(
471            $a1.iter().map(|x| $si::declassify(*x)).collect::<Vec<_>>(),
472            $a2.iter().map(|x| $si::declassify(*x)).collect::<Vec<_>>()
473        );
474    };
475}
476
477impl PublicSeq<u8> {
478    #[cfg_attr(feature = "use_attributes", unsafe_hacspec)]
479    pub fn from_hex(s: &str) -> PublicSeq<u8> {
480        PublicSeq::from_vec(
481            hex_string_to_bytes(s)
482                .iter()
483                .map(|x| *x)
484                .collect::<Vec<_>>(),
485        )
486    }
487
488    #[cfg_attr(feature = "use_attributes", not_hacspec)]
489    pub fn from_string(s: String) -> PublicSeq<u8> {
490        PublicSeq::<u8>::from_vec(
491            hex_string_to_bytes(&s)
492                .iter()
493                .map(|x| *x)
494                .collect::<Vec<_>>(),
495        )
496    }
497}
498
499macro_rules! impl_from_public_slice {
500    ($t:ty,$st:ty) => {
501        impl Seq<$st> {
502            #[cfg_attr(feature = "use_attributes", not_hacspec)]
503            pub fn from_public_slice(v: &[$t]) -> Seq<$st> {
504                Self::from_vec(
505                    v[..]
506                        .iter()
507                        .map(|x| <$st>::classify(*x))
508                        .collect::<Vec<$st>>(),
509                )
510            }
511
512            #[cfg_attr(feature = "use_attributes", in_hacspec)]
513            pub fn from_public_seq<U: SeqTrait<$t>>(x: &U) -> Seq<$st> {
514                let mut tmp = Self::new(x.len());
515                for i in 0..x.len() {
516                    tmp[i] = <$st>::classify(x[i]);
517                }
518                tmp
519            }
520        }
521    };
522}
523
524impl_from_public_slice!(u8, U8);
525impl_from_public_slice!(u16, U16);
526impl_from_public_slice!(u32, U32);
527impl_from_public_slice!(u64, U64);
528impl_from_public_slice!(u128, U128);
529
530macro_rules! impl_declassify {
531    ($t:ty,$st:ty) => {
532        impl Seq<$st> {
533            #[cfg_attr(feature = "use_attributes", in_hacspec)]
534            pub fn declassify(self) -> Seq<$t> {
535                let mut tmp = <Seq<$t>>::new(self.len());
536                for i in 0..self.len() {
537                    tmp[i] = <$st>::declassify(self[i]);
538                }
539                tmp
540            }
541            #[cfg_attr(feature = "use_attributes", not_hacspec)]
542            pub fn into_native(self) -> Vec<$t> {
543                self.b.into_iter().map(|x| x.declassify()).collect()
544            }
545            #[cfg_attr(feature = "use_attributes", not_hacspec)]
546            pub fn to_native(&self) -> Vec<$t> {
547                self.b.iter().map(|&x| <$st>::declassify(x)).collect()
548            }
549        }
550    };
551}
552
553impl_declassify!(u8, U8);
554impl_declassify!(u16, U16);
555impl_declassify!(u32, U32);
556impl_declassify!(u64, U64);
557impl_declassify!(u128, U128);
558
559impl Seq<U8> {
560    #[cfg_attr(feature = "use_attributes", not_hacspec)]
561    pub fn to_hex(&self) -> String {
562        let strs: Vec<String> = self.b.iter().map(|b| format!("{:02x}", b)).collect();
563        strs.join("")
564    }
565}
566
567impl PublicSeq<u8> {
568    #[cfg_attr(feature = "use_attributes", not_hacspec)]
569    pub fn to_hex(&self) -> String {
570        let strs: Vec<String> = self.iter().map(|b| format!("{:02x}", b)).collect();
571        strs.join("")
572    }
573}
574
575#[macro_export]
576macro_rules! public_byte_seq {
577    ($( $b:expr ),+) => {
578        PublicByteSeq::from_vec(
579            vec![
580                $(
581                    $b
582                ),+
583            ]
584        )
585    };
586}
587
588#[macro_export]
589macro_rules! byte_seq {
590    ($( $b:expr ),+) => {
591        ByteSeq::from_vec(
592            vec![
593                $(
594                    U8($b)
595                ),+
596            ]
597        )
598    };
599}
hacspec_lib/seq.rs

hacspec_lib/
seq.rs
