1// Copyright 2016 David Judd.
2// Copyright 2016 Brian Smith.
3//
4// Permission to use, copy, modify, and/or distribute this software for any
5// purpose with or without fee is hereby granted, provided that the above
6// copyright notice and this permission notice appear in all copies.
7//
8// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
9// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
11// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
13// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
14// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15
16//! Unsigned multi-precision integer arithmetic.
17//!
18//! Limbs ordered least-significant-limb to most-significant-limb. The bits
19//! limbs use the native endianness.
20
21use crate::{
22 arithmetic::inout::{AliasingSlices2, AliasingSlices3},
23 c, constant_time,
24 error::{self, LenMismatchError},
25 polyfill::{sliceutil, usize_from_u32, ArrayFlatMap},
26};
27use core::{iter, num::NonZeroUsize};
28
29#[cfg(any(test, feature = "alloc"))]
30use crate::bits;
31
32#[cfg(feature = "alloc")]
33use core::num::Wrapping;
34
35// XXX: Not correct for x32 ABIs.
36pub type Limb = constant_time::Word;
37pub type LeakyLimb = constant_time::LeakyWord;
38pub const LIMB_BITS: usize = usize_from_u32(Limb::BITS);
39pub const LIMB_BYTES: usize = (LIMB_BITS + 7) / 8;
40
41pub type LimbMask = constant_time::BoolMask;
42
43#[inline]
44pub fn limbs_equal_limbs_consttime(a: &[Limb], b: &[Limb]) -> Result<LimbMask, LenMismatchError> {
45 if a.len() != b.len() {
46 return Err(LenMismatchError::new(a.len()));
47 }
48 let all: u64 = a.iter().zip(b).fold(init:0, |running: u64, (a: &u64, b: &u64)| running | (a ^ b));
49 Ok(limb_is_zero_constant_time(limb:all))
50}
51
52#[inline]
53fn limbs_less_than_limbs_constant_time(
54 a: &[Limb],
55 b: &[Limb],
56) -> Result<LimbMask, LenMismatchError> {
57 prefixed_extern! {
58 fn LIMBS_less_than(a: *const Limb, b: *const Limb, num_limbs: c::NonZero_size_t)
59 -> LimbMask;
60 }
61 // Use `b.len` because usually `b` will be the modulus which is likely to
62 // have had its length checked already so this can be elided by the
63 // optimizer.
64 // XXX: Questionable whether `LenMismatchError` is appropriate.
65 let len: NonZero = NonZeroUsize::new(b.len()).ok_or_else(|| LenMismatchError::new(a.len()))?;
66 if a.len() != len.into() {
67 return Err(LenMismatchError::new(a.len()));
68 }
69 Ok(unsafe { LIMBS_less_than(a.as_ptr(), b.as_ptr(), num_limbs:len) })
70}
71
72#[inline]
73pub(crate) fn verify_limbs_less_than_limbs_leak_bit(
74 a: &[Limb],
75 b: &[Limb],
76) -> Result<(), error::Unspecified> {
77 let r: BoolMask = limbs_less_than_limbs_constant_time(a, b).map_err(op:error::erase::<LenMismatchError>)?;
78 if r.leak() {
79 Ok(())
80 } else {
81 Err(error::Unspecified)
82 }
83}
84
85#[inline]
86pub fn limbs_less_than_limbs_vartime(a: &[Limb], b: &[Limb]) -> Result<bool, LenMismatchError> {
87 let r: BoolMask = limbs_less_than_limbs_constant_time(a, b)?;
88 Ok(r.leak())
89}
90
91#[inline]
92fn limb_is_zero_constant_time(limb: Limb) -> LimbMask {
93 prefixed_extern! {
94 fn LIMB_is_zero(limb: Limb) -> LimbMask;
95 }
96 unsafe { LIMB_is_zero(limb) }
97}
98
99#[inline]
100pub fn limbs_are_zero_constant_time(limbs: &[Limb]) -> LimbMask {
101 limb_is_zero_constant_time(limb:limbs.iter().fold(init:0, |a: u64, b: &u64| a | b))
102}
103
104/// Leaks one bit of information (other than the lengths of the inputs):
105/// Whether the given limbs are even.
106#[cfg(any(test, feature = "alloc"))]
107#[inline]
108pub fn limbs_reject_even_leak_bit(limbs: &[Limb]) -> Result<(), error::Unspecified> {
109 let bottom: u64 = *limbs.first().ok_or(err:error::Unspecified)?;
110 if limb_is_zero_constant_time(limb:bottom & 1).leak() {
111 return Err(error::Unspecified);
112 }
113 Ok(())
114}
115
116#[cfg(any(test, feature = "alloc"))]
117#[inline]
118pub fn verify_limbs_equal_1_leak_bit(a: &[Limb]) -> Result<(), error::Unspecified> {
119 if let [bottom: u64, ref rest: &[u64] @ ..] = *a {
120 let equal: BoolMask = limb_is_zero_constant_time(limb:bottom ^ 1) & limbs_are_zero_constant_time(limbs:rest);
121 if equal.leak() {
122 return Ok(());
123 }
124 }
125 Err(error::Unspecified)
126}
127
128/// Returns the number of bits in `a`.
129//
130// This strives to be constant-time with respect to the values of all bits
131// except the most significant bit. This does not attempt to be constant-time
132// with respect to `a.len()` or the value of the result or the value of the
133// most significant bit (It's 1, unless the input is zero, in which case it's
134// zero.)
135#[cfg(any(test, feature = "alloc"))]
136pub fn limbs_minimal_bits(a: &[Limb]) -> bits::BitLength {
137 for num_limbs: usize in (1..=a.len()).rev() {
138 let high_limb: u64 = a[num_limbs - 1];
139
140 // Find the number of set bits in |high_limb| by a linear scan from the
141 // most significant bit to the least significant bit. This works great
142 // for the most common inputs because usually the most significant bit
143 // it set.
144 for high_limb_num_bits: usize in (1..=LIMB_BITS).rev() {
145 let shifted: u64 = unsafe { LIMB_shr(a:high_limb, shift:high_limb_num_bits - 1) };
146 if shifted != 0 {
147 return bits::BitLength::from_bits(
148 ((num_limbs - 1) * LIMB_BITS) + high_limb_num_bits,
149 );
150 }
151 }
152 }
153
154 // No bits were set.
155 bits::BitLength::from_bits(0)
156}
157
158/// Equivalent to `if (r >= m) { r -= m; }`
159#[inline]
160pub fn limbs_reduce_once_constant_time(r: &mut [Limb], m: &[Limb]) -> Result<(), LenMismatchError> {
161 prefixed_extern! {
162 fn LIMBS_reduce_once(r: *mut Limb, m: *const Limb, num_limbs: c::NonZero_size_t);
163 }
164 let num_limbs: NonZero = NonZeroUsize::new(r.len()).ok_or_else(|| LenMismatchError::new(m.len()))?;
165 let r: *mut u64 = r.as_mut_ptr(); // Non-dangling because num_limbs is non-zero.
166 let m: *const u64 = m.as_ptr(); // Non-dangling because num_limbs is non-zero.
167 unsafe { LIMBS_reduce_once(r, m, num_limbs) };
168 Ok(())
169}
170
171#[derive(Clone, Copy, PartialEq)]
172pub enum AllowZero {
173 No,
174 Yes,
175}
176
177/// Parses `input` into `result`, verifies that the value is less than
178/// `max_exclusive`, and pads `result` with zeros to its length. If `allow_zero`
179/// is not `AllowZero::Yes`, zero values are rejected.
180///
181/// This attempts to be constant-time with respect to the actual value *only if*
182/// the value is actually in range. In other words, this won't leak anything
183/// about a valid value, but it might leak small amounts of information about an
184/// invalid value (which constraint it failed).
185pub fn parse_big_endian_in_range_and_pad_consttime(
186 input: untrusted::Input,
187 allow_zero: AllowZero,
188 max_exclusive: &[Limb],
189 result: &mut [Limb],
190) -> Result<(), error::Unspecified> {
191 parse_big_endian_and_pad_consttime(input, result)?;
192 verify_limbs_less_than_limbs_leak_bit(a:result, b:max_exclusive)?;
193 if allow_zero != AllowZero::Yes {
194 if limbs_are_zero_constant_time(limbs:result).leak() {
195 return Err(error::Unspecified);
196 }
197 }
198 Ok(())
199}
200
201/// Parses `input` into `result`, padding `result` with zeros to its length.
202/// This attempts to be constant-time with respect to the value but not with
203/// respect to the length; it is assumed that the length is public knowledge.
204pub fn parse_big_endian_and_pad_consttime(
205 input: untrusted::Input,
206 result: &mut [Limb],
207) -> Result<(), error::Unspecified> {
208 if input.is_empty() {
209 return Err(error::Unspecified);
210 }
211 let input_limbs: impl Iterator = input.as_slice_less_safe().rchunks(LIMB_BYTES).map(|chunk: &[u8]| {
212 let mut padded: [u8; 8] = [0; LIMB_BYTES];
213 sliceutil::overwrite_at_start(&mut padded[(LIMB_BYTES - chunk.len())..], b:chunk);
214 Limb::from_be_bytes(padded)
215 });
216 if input_limbs.len() > result.len() {
217 return Err(error::Unspecified);
218 }
219
220 resultimpl Iterator
221 .iter_mut()
222 .zip(input_limbs.chain(iter::repeat(elt:0)))
223 .for_each(|(r: &mut u64, i: u64)| *r = i);
224
225 Ok(())
226}
227
228pub fn big_endian_from_limbs(limbs: &[Limb], out: &mut [u8]) {
229 let be_bytes: impl ExactSizeIterator + Clone = unstripped_be_bytes(limbs);
230 assert_eq!(out.len(), be_bytes.len());
231 out.iter_mut().zip(be_bytes).for_each(|(o: &mut u8, i: u8)| {
232 *o = i;
233 });
234}
235
236/// Returns an iterator of the big-endian encoding of `limbs`.
237///
238/// The number of bytes returned will be a multiple of `LIMB_BYTES`
239/// and thus may be padded with leading zeros.
240pub fn unstripped_be_bytes(limbs: &[Limb]) -> impl ExactSizeIterator<Item = u8> + Clone + '_ {
241 // The unwrap is safe because a slice can never be larger than `usize` bytes.
242 ArrayFlatMap::new(inner:limbs.iter().rev().copied(), f:Limb::to_be_bytes).unwrap()
243}
244
245// Used in FFI
246pub type Window = constant_time::Word;
247
248// Used in FFI
249pub type LeakyWindow = constant_time::LeakyWord;
250
251/// Processes `limbs` as a sequence of 5-bit windows, folding the windows from
252/// most significant to least significant and returning the accumulated result.
253/// The first window will be mapped by `init` to produce the initial value for
254/// the accumulator. Then `f` will be called to fold the accumulator and the
255/// next window until all windows are processed. When the input's bit length
256/// isn't divisible by 5, the window passed to `init` will be partial; all
257/// windows passed to `fold` will be full.
258///
259/// This is designed to avoid leaking the contents of `limbs` through side
260/// channels as long as `init` and `fold` are side-channel free.
261///
262/// Panics if `limbs` is empty.
263#[cfg(feature = "alloc")]
264pub fn fold_5_bit_windows<R, I: FnOnce(Window) -> R, F: Fn(R, Window) -> R>(
265 limbs: &[Limb],
266 init: I,
267 fold: F,
268) -> R {
269 #[derive(Clone, Copy)]
270 #[repr(transparent)]
271 struct BitIndex(Wrapping<c::size_t>);
272
273 const WINDOW_BITS: Wrapping<c::size_t> = Wrapping(5);
274
275 prefixed_extern! {
276 fn LIMBS_window5_split_window(
277 lower_limb: Limb,
278 higher_limb: Limb,
279 index_within_word: BitIndex,
280 ) -> Window;
281 fn LIMBS_window5_unsplit_window(limb: Limb, index_within_word: BitIndex) -> Window;
282 }
283
284 let num_limbs = limbs.len();
285 let mut window_low_bit = {
286 let num_whole_windows = (num_limbs * LIMB_BITS) / 5;
287 let mut leading_bits = (num_limbs * LIMB_BITS) - (num_whole_windows * 5);
288 if leading_bits == 0 {
289 leading_bits = WINDOW_BITS.0;
290 }
291 BitIndex(Wrapping(LIMB_BITS - leading_bits))
292 };
293
294 let initial_value = {
295 let leading_partial_window =
296 unsafe { LIMBS_window5_split_window(*limbs.first().unwrap(), 0, window_low_bit) };
297 window_low_bit.0 -= WINDOW_BITS;
298 init(leading_partial_window)
299 };
300
301 let mut low_limb = Limb::from(0 as LeakyWindow);
302 limbs.iter().fold(initial_value, |mut acc, current_limb| {
303 let higher_limb = low_limb;
304 low_limb = *current_limb;
305
306 if window_low_bit.0 > Wrapping(LIMB_BITS) - WINDOW_BITS {
307 let window =
308 unsafe { LIMBS_window5_split_window(low_limb, higher_limb, window_low_bit) };
309 window_low_bit.0 -= WINDOW_BITS;
310 acc = fold(acc, window);
311 };
312 while window_low_bit.0 < Wrapping(LIMB_BITS) {
313 let window = unsafe { LIMBS_window5_unsplit_window(low_limb, window_low_bit) };
314 // The loop exits when this subtraction underflows, causing `window_low_bit` to
315 // wrap around to a very large value.
316 window_low_bit.0 -= WINDOW_BITS;
317 acc = fold(acc, window);
318 }
319 window_low_bit.0 += Wrapping(LIMB_BITS); // "Fix" the underflow.
320
321 acc
322 })
323}
324
325#[inline]
326pub(crate) fn limbs_add_assign_mod(
327 a: &mut [Limb],
328 b: &[Limb],
329 m: &[Limb],
330) -> Result<(), LenMismatchError> {
331 prefixed_extern! {
332 // `r` and `a` may alias.
333 fn LIMBS_add_mod(
334 r: *mut Limb,
335 a: *const Limb,
336 b: *const Limb,
337 m: *const Limb,
338 num_limbs: c::NonZero_size_t,
339 );
340 }
341 let num_limbs: NonZero = NonZeroUsize::new(m.len()).ok_or_else(|| LenMismatchError::new(m.len()))?;
342 (a, b).with_non_dangling_non_null_pointers_rab(expected_len:num_limbs, |r: *mut u64, a: *const u64, b: *const u64| {
343 let m: *const u64 = m.as_ptr(); // Also non-dangling because `num_limbs` is non-zero.
344 unsafe { LIMBS_add_mod(r, a, b, m, num_limbs) }
345 })
346}
347
348// r *= 2 (mod m).
349pub(crate) fn limbs_double_mod(r: &mut [Limb], m: &[Limb]) -> Result<(), LenMismatchError> {
350 prefixed_extern! {
351 // `r` and `a` may alias.
352 fn LIMBS_shl_mod(
353 r: *mut Limb,
354 a: *const Limb,
355 m: *const Limb,
356 num_limbs: c::NonZero_size_t);
357 }
358 let num_limbs: NonZero = NonZeroUsize::new(m.len()).ok_or_else(|| LenMismatchError::new(m.len()))?;
359 r.with_non_dangling_non_null_pointers_ra(expected_len:num_limbs, |r: *mut u64, a: *const u64| {
360 let m: *const u64 = m.as_ptr(); // Also non-dangling because num_limbs > 0.
361 unsafe {
362 LIMBS_shl_mod(r, a, m, num_limbs);
363 }
364 })
365}
366
367// *r = -a, assuming a is odd.
368pub(crate) fn limbs_negative_odd(r: &mut [Limb], a: &[Limb]) {
369 debug_assert_eq!(r.len(), a.len());
370 // Two's complement step 1: flip all the bits.
371 // The compiler should optimize this to vectorized (a ^ !0).
372 r.iter_mut().zip(a.iter()).for_each(|(r: &mut u64, &a: u64)| {
373 *r = !a;
374 });
375 // Two's complement step 2: Add one. Since `a` is odd, `r` is even. Thus we
376 // can use a bitwise or for addition.
377 r[0] |= 1;
378}
379
380#[cfg(any(test, feature = "alloc"))]
381prefixed_extern! {
382 fn LIMB_shr(a: Limb, shift: c::size_t) -> Limb;
383}
384
385#[cfg(test)]
386mod tests {
387 use super::*;
388 use alloc::vec::Vec;
389 use cfg_if::cfg_if;
390
391 const MAX: LeakyLimb = LeakyLimb::MAX;
392
393 fn leak_in_test(a: LimbMask) -> bool {
394 a.leak()
395 }
396
397 #[test]
398 fn test_limbs_are_even() {
399 static EVENS: &[&[LeakyLimb]] = &[
400 &[],
401 &[0],
402 &[2],
403 &[0, 0],
404 &[2, 0],
405 &[0, 1],
406 &[0, 2],
407 &[0, 3],
408 &[0, 0, 0, 0, MAX],
409 ];
410 for even in EVENS {
411 let even = &Vec::from_iter(even.iter().copied().map(Limb::from));
412 assert!(matches!(
413 limbs_reject_even_leak_bit(even),
414 Err(error::Unspecified)
415 ));
416 }
417 static ODDS: &[&[LeakyLimb]] = &[
418 &[1],
419 &[3],
420 &[1, 0],
421 &[3, 0],
422 &[1, 1],
423 &[1, 2],
424 &[1, 3],
425 &[1, 0, 0, 0, MAX],
426 ];
427 for odd in ODDS {
428 let odd = &Vec::from_iter(odd.iter().copied().map(Limb::from));
429 assert!(matches!(limbs_reject_even_leak_bit(odd), Ok(())));
430 }
431 }
432
433 static ZEROES: &[&[LeakyLimb]] = &[
434 &[],
435 &[0],
436 &[0, 0],
437 &[0, 0, 0],
438 &[0, 0, 0, 0],
439 &[0, 0, 0, 0, 0],
440 &[0, 0, 0, 0, 0, 0, 0],
441 &[0, 0, 0, 0, 0, 0, 0, 0],
442 &[0, 0, 0, 0, 0, 0, 0, 0, 0],
443 ];
444
445 static NONZEROES: &[&[LeakyLimb]] = &[
446 &[1],
447 &[0, 1],
448 &[1, 1],
449 &[1, 0, 0, 0],
450 &[0, 1, 0, 0],
451 &[0, 0, 1, 0],
452 &[0, 0, 0, 1],
453 ];
454
455 #[test]
456 fn test_limbs_are_zero() {
457 for zero in ZEROES {
458 let zero = &Vec::from_iter(zero.iter().copied().map(Limb::from));
459 assert!(leak_in_test(limbs_are_zero_constant_time(zero)));
460 }
461 for nonzero in NONZEROES {
462 let nonzero = &Vec::from_iter(nonzero.iter().copied().map(Limb::from));
463 assert!(!leak_in_test(limbs_are_zero_constant_time(nonzero)));
464 }
465 }
466
467 #[test]
468 fn test_limbs_equal_limb() {
469 // Equal
470 static EQUAL: &[&[LeakyLimb]] = &[&[1], &[1, 0], &[1, 0, 0], &[1, 0, 0, 0, 0, 0, 0]];
471 for a in EQUAL {
472 let a = &Vec::from_iter(a.iter().copied().map(Limb::from));
473 assert!(matches!(verify_limbs_equal_1_leak_bit(a), Ok(())));
474 }
475
476 // Unequal
477 static UNEQUAL: &[&[LeakyLimb]] = &[
478 &[0],
479 &[2],
480 &[3],
481 &[MAX],
482 &[0, 1],
483 &[1, 1],
484 &[0, 0, 0, 0, 0, 0, 0, 1],
485 &[0, 0, 0, 0, 1, 0, 0, 0],
486 &[0, 0, 0, 0, 1, 0, 0, 1],
487 &[MAX, 1],
488 ];
489 for a in UNEQUAL {
490 let a = &Vec::from_iter(a.iter().copied().map(Limb::from));
491 assert!(matches!(
492 verify_limbs_equal_1_leak_bit(a),
493 Err(error::Unspecified)
494 ));
495 }
496 }
497
498 #[test]
499 fn test_parse_big_endian_and_pad_consttime() {
500 const LIMBS: usize = 4;
501
502 {
503 // Empty input.
504 let inp = untrusted::Input::from(&[]);
505 let mut result = [0; LIMBS].map(From::<LeakyLimb>::from);
506 assert!(parse_big_endian_and_pad_consttime(inp, &mut result).is_err());
507 }
508
509 // The input is longer than will fit in the given number of limbs.
510 {
511 let inp = [1, 2, 3, 4, 5, 6, 7, 8, 9];
512 let inp = untrusted::Input::from(&inp);
513 let mut result = [0; 8 / LIMB_BYTES].map(From::<LeakyLimb>::from);
514 assert!(parse_big_endian_and_pad_consttime(inp, &mut result[..]).is_err());
515 }
516
517 // Less than a full limb.
518 {
519 let inp = [0xfe];
520 let inp = untrusted::Input::from(&inp);
521 let mut result = [0; LIMBS].map(From::<LeakyLimb>::from);
522 assert_eq!(
523 Ok(()),
524 parse_big_endian_and_pad_consttime(inp, &mut result[..])
525 );
526 assert_eq!(&[0xfe, 0, 0, 0], &result);
527 }
528
529 // A whole limb for 32-bit, half a limb for 64-bit.
530 {
531 let inp = [0xbe, 0xef, 0xf0, 0x0d];
532 let inp = untrusted::Input::from(&inp);
533 let mut result = [0; LIMBS].map(From::<LeakyLimb>::from);
534 assert_eq!(Ok(()), parse_big_endian_and_pad_consttime(inp, &mut result));
535 assert_eq!(&[0xbeeff00d, 0, 0, 0], &result);
536 }
537
538 cfg_if! {
539 if #[cfg(target_pointer_width = "64")] {
540 static TEST_CASES: &[(&[u8], &[Limb])] = &[
541 (&[1], &[1, 0]),
542 (&[1, 2], &[0x102, 0]),
543 (&[1, 2, 3], &[0x10203, 0]),
544 (&[1, 2, 3, 4], &[0x102_0304, 0]),
545 (&[1, 2, 3, 4, 5], &[0x1_0203_0405, 0]),
546 (&[1, 2, 3, 4, 5, 6], &[0x102_0304_0506, 0]),
547 (&[1, 2, 3, 4, 5, 6, 7], &[0x1_0203_0405_0607, 0]),
548 (&[1, 2, 3, 4, 5, 6, 7, 8], &[0x102_0304_0506_0708, 0]),
549 (&[1, 2, 3, 4, 5, 6, 7, 8, 9], &[0x0203_0405_0607_0809, 0x1]),
550 (&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa], &[0x0304_0506_0708_090a, 0x102]),
551 (&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa, 0xb], &[0x0405_0607_0809_0a0b, 0x1_0203]),
552 ];
553 for (be_bytes, limbs) in TEST_CASES {
554 let mut buf = [0; 2];
555 parse_big_endian_and_pad_consttime(untrusted::Input::from(be_bytes), &mut buf)
556 .unwrap();
557 assert_eq!(limbs, &buf, "({be_bytes:x?}, {limbs:x?}");
558 }
559 } else if #[cfg(target_pointer_width = "32")] {
560 static TEST_CASES: &[(&[u8], &[Limb])] = &[
561 (&[1], &[1, 0, 0]),
562 (&[1, 2], &[0x102, 0, 0]),
563 (&[1, 2, 3], &[0x10203, 0, 0]),
564 (&[1, 2, 3, 4], &[0x102_0304, 0, 0]),
565 (&[1, 2, 3, 4, 5], &[0x0203_0405, 0x1, 0]),
566 (&[1, 2, 3, 4, 5, 6], &[0x0304_0506, 0x102, 0]),
567 (&[1, 2, 3, 4, 5, 6, 7], &[0x0405_0607, 0x1_0203, 0]),
568 (&[1, 2, 3, 4, 5, 6, 7, 8], &[0x0506_0708, 0x102_0304, 0]),
569 (&[1, 2, 3, 4, 5, 6, 7, 8, 9], &[0x0607_0809, 0x0203_0405, 0x1]),
570 (&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa], &[0x0708_090a, 0x0304_0506, 0x102]),
571 (&[1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa, 0xb], &[0x0809_0a0b, 0x0405_0607, 0x1_0203]),
572 ];
573 for (be_bytes, limbs) in TEST_CASES {
574 let mut buf = [0; 3];
575 parse_big_endian_and_pad_consttime(untrusted::Input::from(be_bytes), &mut buf)
576 .unwrap();
577 assert_eq!(limbs, &buf, "({be_bytes:x?}, {limbs:x?}");
578 }
579 } else {
580 panic!("Unsupported target_pointer_width");
581 }
582
583 // XXX: This is a weak set of tests. TODO: expand it.
584 }
585 }
586
587 #[test]
588 fn test_big_endian_from_limbs_same_length() {
589 #[cfg(target_pointer_width = "32")]
590 let limbs = [
591 0xbccddeef, 0x89900aab, 0x45566778, 0x01122334, 0xddeeff00, 0x99aabbcc, 0x55667788,
592 0x11223344,
593 ];
594
595 #[cfg(target_pointer_width = "64")]
596 let limbs = [
597 0x8990_0aab_bccd_deef,
598 0x0112_2334_4556_6778,
599 0x99aa_bbcc_ddee_ff00,
600 0x1122_3344_5566_7788,
601 ];
602
603 let limbs = limbs.map(From::<LeakyLimb>::from);
604
605 let expected = [
606 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee,
607 0xff, 0x00, 0x01, 0x12, 0x23, 0x34, 0x45, 0x56, 0x67, 0x78, 0x89, 0x90, 0x0a, 0xab,
608 0xbc, 0xcd, 0xde, 0xef,
609 ];
610
611 let mut out = [0xabu8; 32];
612 big_endian_from_limbs(&limbs[..], &mut out);
613 assert_eq!(&out[..], &expected[..]);
614 }
615
616 #[should_panic]
617 #[test]
618 fn test_big_endian_from_limbs_fewer_limbs() {
619 #[cfg(target_pointer_width = "32")]
620 // Two fewer limbs.
621 let limbs = [
622 0xbccddeef, 0x89900aab, 0x45566778, 0x01122334, 0xddeeff00, 0x99aabbcc,
623 ];
624
625 // One fewer limb.
626 #[cfg(target_pointer_width = "64")]
627 let limbs = [
628 0x8990_0aab_bccd_deef,
629 0x0112_2334_4556_6778,
630 0x99aa_bbcc_ddee_ff00,
631 ];
632
633 let limbs = limbs.map(From::<LeakyLimb>::from);
634
635 let mut out = [0xabu8; 32];
636
637 big_endian_from_limbs(&limbs[..], &mut out);
638 }
639
640 #[test]
641 fn test_limbs_minimal_bits() {
642 const ALL_ONES: LeakyLimb = LeakyLimb::MAX;
643 static CASES: &[(&[LeakyLimb], usize)] = &[
644 (&[], 0),
645 (&[0], 0),
646 (&[ALL_ONES], LIMB_BITS),
647 (&[ALL_ONES, 0], LIMB_BITS),
648 (&[ALL_ONES, 1], LIMB_BITS + 1),
649 (&[0, 0], 0),
650 (&[1, 0], 1),
651 (&[0, 1], LIMB_BITS + 1),
652 (&[0, ALL_ONES], 2 * LIMB_BITS),
653 (&[ALL_ONES, ALL_ONES], 2 * LIMB_BITS),
654 (&[ALL_ONES, ALL_ONES >> 1], 2 * LIMB_BITS - 1),
655 (&[ALL_ONES, 0b100_0000], LIMB_BITS + 7),
656 (&[ALL_ONES, 0b101_0000], LIMB_BITS + 7),
657 (&[ALL_ONES, ALL_ONES >> 1], LIMB_BITS + (LIMB_BITS) - 1),
658 ];
659 for (limbs, bits) in CASES {
660 let limbs = &Vec::from_iter(limbs.iter().copied().map(Limb::from));
661 assert_eq!(limbs_minimal_bits(limbs).as_bits(), *bits);
662 }
663 }
664}
665