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
21 use crate::{c, error, polyfill::ArrayFlatMap};
22
23 #[cfg(any(test, feature = "alloc"))]
24 use crate::bits;
25
26 #[cfg(feature = "alloc")]
27 use core::num::Wrapping;
28
29 // XXX: Not correct for x32 ABIs.
30 #[cfg(target_pointer_width = "64")]
31 pub type Limb = u64;
32 #[cfg(target_pointer_width = "32")]
33 pub type Limb = u32;
34 #[cfg(target_pointer_width = "64")]
35 pub const LIMB_BITS: usize = 64;
36 #[cfg(target_pointer_width = "32")]
37 pub const LIMB_BITS: usize = 32;
38
39 #[cfg(target_pointer_width = "64")]
40 #[derive(Debug, PartialEq)]
41 #[repr(u64)]
42 pub enum LimbMask {
43 True = 0xffff_ffff_ffff_ffff,
44 False = 0,
45 }
46
47 #[cfg(target_pointer_width = "32")]
48 #[derive(Debug, PartialEq)]
49 #[repr(u32)]
50 pub enum LimbMask {
51 True = 0xffff_ffff,
52 False = 0,
53 }
54
55 pub const LIMB_BYTES: usize = (LIMB_BITS + 7) / 8;
56
57 #[inline]
limbs_equal_limbs_consttime(a: &[Limb], b: &[Limb]) -> LimbMask58 pub fn limbs_equal_limbs_consttime(a: &[Limb], b: &[Limb]) -> LimbMask {
59 prefixed_extern! {
60 fn LIMBS_equal(a: *const Limb, b: *const Limb, num_limbs: c::size_t) -> LimbMask;
61 }
62
63 assert_eq!(a.len(), b.len());
64 unsafe { LIMBS_equal(a.as_ptr(), b.as_ptr(), a.len()) }
65 }
66
67 #[inline]
limbs_less_than_limbs_consttime(a: &[Limb], b: &[Limb]) -> LimbMask68 pub fn limbs_less_than_limbs_consttime(a: &[Limb], b: &[Limb]) -> LimbMask {
69 assert_eq!(a.len(), b.len());
70 unsafe { LIMBS_less_than(a.as_ptr(), b.as_ptr(), b.len()) }
71 }
72
73 #[inline]
limbs_less_than_limbs_vartime(a: &[Limb], b: &[Limb]) -> bool74 pub fn limbs_less_than_limbs_vartime(a: &[Limb], b: &[Limb]) -> bool {
75 limbs_less_than_limbs_consttime(a, b) == LimbMask::True
76 }
77
78 #[inline]
79 #[cfg(feature = "alloc")]
limbs_less_than_limb_constant_time(a: &[Limb], b: Limb) -> LimbMask80 pub fn limbs_less_than_limb_constant_time(a: &[Limb], b: Limb) -> LimbMask {
81 unsafe { LIMBS_less_than_limb(a.as_ptr(), b, a.len()) }
82 }
83
84 #[inline]
limbs_are_zero_constant_time(limbs: &[Limb]) -> LimbMask85 pub fn limbs_are_zero_constant_time(limbs: &[Limb]) -> LimbMask {
86 unsafe { LIMBS_are_zero(limbs.as_ptr(), limbs.len()) }
87 }
88
89 #[cfg(any(test, feature = "alloc"))]
90 #[inline]
limbs_are_even_constant_time(limbs: &[Limb]) -> LimbMask91 pub fn limbs_are_even_constant_time(limbs: &[Limb]) -> LimbMask {
92 unsafe { LIMBS_are_even(limbs.as_ptr(), limbs.len()) }
93 }
94
95 #[cfg(any(test, feature = "alloc"))]
96 #[inline]
limbs_equal_limb_constant_time(a: &[Limb], b: Limb) -> LimbMask97 pub fn limbs_equal_limb_constant_time(a: &[Limb], b: Limb) -> LimbMask {
98 unsafe { LIMBS_equal_limb(a.as_ptr(), b, a.len()) }
99 }
100
101 /// Returns the number of bits in `a`.
102 //
103 // This strives to be constant-time with respect to the values of all bits
104 // except the most significant bit. This does not attempt to be constant-time
105 // with respect to `a.len()` or the value of the result or the value of the
106 // most significant bit (It's 1, unless the input is zero, in which case it's
107 // zero.)
108 #[cfg(any(test, feature = "alloc"))]
limbs_minimal_bits(a: &[Limb]) -> bits::BitLength109 pub fn limbs_minimal_bits(a: &[Limb]) -> bits::BitLength {
110 for num_limbs in (1..=a.len()).rev() {
111 let high_limb = a[num_limbs - 1];
112
113 // Find the number of set bits in |high_limb| by a linear scan from the
114 // most significant bit to the least significant bit. This works great
115 // for the most common inputs because usually the most significant bit
116 // it set.
117 for high_limb_num_bits in (1..=LIMB_BITS).rev() {
118 let shifted = unsafe { LIMB_shr(high_limb, high_limb_num_bits - 1) };
119 if shifted != 0 {
120 return bits::BitLength::from_usize_bits(
121 ((num_limbs - 1) * LIMB_BITS) + high_limb_num_bits,
122 );
123 }
124 }
125 }
126
127 // No bits were set.
128 bits::BitLength::from_usize_bits(0)
129 }
130
131 /// Equivalent to `if (r >= m) { r -= m; }`
132 #[inline]
limbs_reduce_once_constant_time(r: &mut [Limb], m: &[Limb])133 pub fn limbs_reduce_once_constant_time(r: &mut [Limb], m: &[Limb]) {
134 assert_eq!(r.len(), m.len());
135 unsafe { LIMBS_reduce_once(r.as_mut_ptr(), m.as_ptr(), m.len()) };
136 }
137
138 #[derive(Clone, Copy, PartialEq)]
139 pub enum AllowZero {
140 No,
141 Yes,
142 }
143
144 /// Parses `input` into `result`, reducing it via conditional subtraction
145 /// (mod `m`). Assuming 2**((self.num_limbs * LIMB_BITS) - 1) < m and
146 /// m < 2**(self.num_limbs * LIMB_BITS), the value will be reduced mod `m` in
147 /// constant time so that the result is in the range [0, m) if `allow_zero` is
148 /// `AllowZero::Yes`, or [1, m) if `allow_zero` is `AllowZero::No`. `result` is
149 /// padded with zeros to its length.
parse_big_endian_in_range_partially_reduced_and_pad_consttime( input: untrusted::Input, allow_zero: AllowZero, m: &[Limb], result: &mut [Limb], ) -> Result<(), error::Unspecified>150 pub fn parse_big_endian_in_range_partially_reduced_and_pad_consttime(
151 input: untrusted::Input,
152 allow_zero: AllowZero,
153 m: &[Limb],
154 result: &mut [Limb],
155 ) -> Result<(), error::Unspecified> {
156 parse_big_endian_and_pad_consttime(input, result)?;
157 limbs_reduce_once_constant_time(result, m);
158 if allow_zero != AllowZero::Yes {
159 if limbs_are_zero_constant_time(result) != LimbMask::False {
160 return Err(error::Unspecified);
161 }
162 }
163 Ok(())
164 }
165
166 /// Parses `input` into `result`, verifies that the value is less than
167 /// `max_exclusive`, and pads `result` with zeros to its length. If `allow_zero`
168 /// is not `AllowZero::Yes`, zero values are rejected.
169 ///
170 /// This attempts to be constant-time with respect to the actual value *only if*
171 /// the value is actually in range. In other words, this won't leak anything
172 /// about a valid value, but it might leak small amounts of information about an
173 /// invalid value (which constraint it failed).
parse_big_endian_in_range_and_pad_consttime( input: untrusted::Input, allow_zero: AllowZero, max_exclusive: &[Limb], result: &mut [Limb], ) -> Result<(), error::Unspecified>174 pub fn parse_big_endian_in_range_and_pad_consttime(
175 input: untrusted::Input,
176 allow_zero: AllowZero,
177 max_exclusive: &[Limb],
178 result: &mut [Limb],
179 ) -> Result<(), error::Unspecified> {
180 parse_big_endian_and_pad_consttime(input, result)?;
181 if limbs_less_than_limbs_consttime(result, max_exclusive) != LimbMask::True {
182 return Err(error::Unspecified);
183 }
184 if allow_zero != AllowZero::Yes {
185 if limbs_are_zero_constant_time(result) != LimbMask::False {
186 return Err(error::Unspecified);
187 }
188 }
189 Ok(())
190 }
191
192 /// Parses `input` into `result`, padding `result` with zeros to its length.
193 /// This attempts to be constant-time with respect to the value but not with
194 /// respect to the length; it is assumed that the length is public knowledge.
parse_big_endian_and_pad_consttime( input: untrusted::Input, result: &mut [Limb], ) -> Result<(), error::Unspecified>195 pub fn parse_big_endian_and_pad_consttime(
196 input: untrusted::Input,
197 result: &mut [Limb],
198 ) -> Result<(), error::Unspecified> {
199 if input.is_empty() {
200 return Err(error::Unspecified);
201 }
202
203 // `bytes_in_current_limb` is the number of bytes in the current limb.
204 // It will be `LIMB_BYTES` for all limbs except maybe the highest-order
205 // limb.
206 let mut bytes_in_current_limb = input.len() % LIMB_BYTES;
207 if bytes_in_current_limb == 0 {
208 bytes_in_current_limb = LIMB_BYTES;
209 }
210
211 let num_encoded_limbs = (input.len() / LIMB_BYTES)
212 + (if bytes_in_current_limb == LIMB_BYTES {
213 0
214 } else {
215 1
216 });
217 if num_encoded_limbs > result.len() {
218 return Err(error::Unspecified);
219 }
220
221 result.fill(0);
222
223 // XXX: Questionable as far as constant-timedness is concerned.
224 // TODO: Improve this.
225 input.read_all(error::Unspecified, |input| {
226 for i in 0..num_encoded_limbs {
227 let mut limb: Limb = 0;
228 for _ in 0..bytes_in_current_limb {
229 let b: Limb = input.read_byte()?.into();
230 limb = (limb << 8) | b;
231 }
232 result[num_encoded_limbs - i - 1] = limb;
233 bytes_in_current_limb = LIMB_BYTES;
234 }
235 Ok(())
236 })
237 }
238
big_endian_from_limbs(limbs: &[Limb], out: &mut [u8])239 pub fn big_endian_from_limbs(limbs: &[Limb], out: &mut [u8]) {
240 let be_bytes = unstripped_be_bytes(limbs);
241 assert_eq!(out.len(), be_bytes.len());
242 out.iter_mut().zip(be_bytes).for_each(|(o, i)| {
243 *o = i;
244 });
245 }
246
247 /// Returns an iterator of the big-endian encoding of `limbs`.
248 ///
249 /// The number of bytes returned will be a multiple of `LIMB_BYTES`
250 /// and thus may be padded with leading zeros.
unstripped_be_bytes(limbs: &[Limb]) -> impl ExactSizeIterator<Item = u8> + Clone + '_251 pub fn unstripped_be_bytes(limbs: &[Limb]) -> impl ExactSizeIterator<Item = u8> + Clone + '_ {
252 // The unwrap is safe because a slice can never be larger than `usize` bytes.
253 ArrayFlatMap::new(limbs.iter().rev().copied(), Limb::to_be_bytes).unwrap()
254 }
255
256 #[cfg(feature = "alloc")]
257 pub type Window = Limb;
258
259 /// Processes `limbs` as a sequence of 5-bit windows, folding the windows from
260 /// most significant to least significant and returning the accumulated result.
261 /// The first window will be mapped by `init` to produce the initial value for
262 /// the accumulator. Then `f` will be called to fold the accumulator and the
263 /// next window until all windows are processed. When the input's bit length
264 /// isn't divisible by 5, the window passed to `init` will be partial; all
265 /// windows passed to `fold` will be full.
266 ///
267 /// This is designed to avoid leaking the contents of `limbs` through side
268 /// channels as long as `init` and `fold` are side-channel free.
269 ///
270 /// Panics if `limbs` is empty.
271 #[cfg(feature = "alloc")]
fold_5_bit_windows<R, I: FnOnce(Window) -> R, F: Fn(R, Window) -> R>( limbs: &[Limb], init: I, fold: F, ) -> R272 pub fn fold_5_bit_windows<R, I: FnOnce(Window) -> R, F: Fn(R, Window) -> R>(
273 limbs: &[Limb],
274 init: I,
275 fold: F,
276 ) -> R {
277 #[derive(Clone, Copy)]
278 #[repr(transparent)]
279 struct BitIndex(Wrapping<c::size_t>);
280
281 const WINDOW_BITS: Wrapping<c::size_t> = Wrapping(5);
282
283 prefixed_extern! {
284 fn LIMBS_window5_split_window(
285 lower_limb: Limb,
286 higher_limb: Limb,
287 index_within_word: BitIndex,
288 ) -> Window;
289 fn LIMBS_window5_unsplit_window(limb: Limb, index_within_word: BitIndex) -> Window;
290 }
291
292 let num_limbs = limbs.len();
293 let mut window_low_bit = {
294 let num_whole_windows = (num_limbs * LIMB_BITS) / 5;
295 let mut leading_bits = (num_limbs * LIMB_BITS) - (num_whole_windows * 5);
296 if leading_bits == 0 {
297 leading_bits = WINDOW_BITS.0;
298 }
299 BitIndex(Wrapping(LIMB_BITS - leading_bits))
300 };
301
302 let initial_value = {
303 let leading_partial_window =
304 unsafe { LIMBS_window5_split_window(*limbs.last().unwrap(), 0, window_low_bit) };
305 window_low_bit.0 -= WINDOW_BITS;
306 init(leading_partial_window)
307 };
308
309 let mut low_limb = 0;
310 limbs
311 .iter()
312 .rev()
313 .fold(initial_value, |mut acc, current_limb| {
314 let higher_limb = low_limb;
315 low_limb = *current_limb;
316
317 if window_low_bit.0 > Wrapping(LIMB_BITS) - WINDOW_BITS {
318 let window =
319 unsafe { LIMBS_window5_split_window(low_limb, higher_limb, window_low_bit) };
320 window_low_bit.0 -= WINDOW_BITS;
321 acc = fold(acc, window);
322 };
323 while window_low_bit.0 < Wrapping(LIMB_BITS) {
324 let window = unsafe { LIMBS_window5_unsplit_window(low_limb, window_low_bit) };
325 // The loop exits when this subtraction underflows, causing `window_low_bit` to
326 // wrap around to a very large value.
327 window_low_bit.0 -= WINDOW_BITS;
328 acc = fold(acc, window);
329 }
330 window_low_bit.0 += Wrapping(LIMB_BITS); // "Fix" the underflow.
331
332 acc
333 })
334 }
335
336 #[inline]
limbs_add_assign_mod(a: &mut [Limb], b: &[Limb], m: &[Limb])337 pub(crate) fn limbs_add_assign_mod(a: &mut [Limb], b: &[Limb], m: &[Limb]) {
338 debug_assert_eq!(a.len(), m.len());
339 debug_assert_eq!(b.len(), m.len());
340 prefixed_extern! {
341 // `r` and `a` may alias.
342 fn LIMBS_add_mod(
343 r: *mut Limb,
344 a: *const Limb,
345 b: *const Limb,
346 m: *const Limb,
347 num_limbs: c::size_t,
348 );
349 }
350 unsafe { LIMBS_add_mod(a.as_mut_ptr(), a.as_ptr(), b.as_ptr(), m.as_ptr(), m.len()) }
351 }
352
353 prefixed_extern! {
354 fn LIMBS_are_zero(a: *const Limb, num_limbs: c::size_t) -> LimbMask;
355 fn LIMBS_less_than(a: *const Limb, b: *const Limb, num_limbs: c::size_t) -> LimbMask;
356 fn LIMBS_reduce_once(r: *mut Limb, m: *const Limb, num_limbs: c::size_t);
357 }
358
359 #[cfg(any(test, feature = "alloc"))]
360 prefixed_extern! {
361 fn LIMB_shr(a: Limb, shift: c::size_t) -> Limb;
362 fn LIMBS_are_even(a: *const Limb, num_limbs: c::size_t) -> LimbMask;
363 fn LIMBS_equal_limb(a: *const Limb, b: Limb, num_limbs: c::size_t) -> LimbMask;
364 }
365
366 #[cfg(feature = "alloc")]
367 prefixed_extern! {
368 fn LIMBS_less_than_limb(a: *const Limb, b: Limb, num_limbs: c::size_t) -> LimbMask;
369 }
370
371 #[cfg(test)]
372 mod tests {
373 use super::*;
374
375 const MAX: Limb = LimbMask::True as Limb;
376
377 #[test]
test_limbs_are_even()378 fn test_limbs_are_even() {
379 static EVENS: &[&[Limb]] = &[
380 &[],
381 &[0],
382 &[2],
383 &[0, 0],
384 &[2, 0],
385 &[0, 1],
386 &[0, 2],
387 &[0, 3],
388 &[0, 0, 0, 0, MAX],
389 ];
390 for even in EVENS {
391 assert_eq!(limbs_are_even_constant_time(even), LimbMask::True);
392 }
393 static ODDS: &[&[Limb]] = &[
394 &[1],
395 &[3],
396 &[1, 0],
397 &[3, 0],
398 &[1, 1],
399 &[1, 2],
400 &[1, 3],
401 &[1, 0, 0, 0, MAX],
402 ];
403 for odd in ODDS {
404 assert_eq!(limbs_are_even_constant_time(odd), LimbMask::False);
405 }
406 }
407
408 static ZEROES: &[&[Limb]] = &[
409 &[],
410 &[0],
411 &[0, 0],
412 &[0, 0, 0],
413 &[0, 0, 0, 0],
414 &[0, 0, 0, 0, 0],
415 &[0, 0, 0, 0, 0, 0, 0],
416 &[0, 0, 0, 0, 0, 0, 0, 0],
417 &[0, 0, 0, 0, 0, 0, 0, 0, 0],
418 ];
419
420 static NONZEROES: &[&[Limb]] = &[
421 &[1],
422 &[0, 1],
423 &[1, 1],
424 &[1, 0, 0, 0],
425 &[0, 1, 0, 0],
426 &[0, 0, 1, 0],
427 &[0, 0, 0, 1],
428 ];
429
430 #[test]
test_limbs_are_zero()431 fn test_limbs_are_zero() {
432 for zero in ZEROES {
433 assert_eq!(limbs_are_zero_constant_time(zero), LimbMask::True);
434 }
435 for nonzero in NONZEROES {
436 assert_eq!(limbs_are_zero_constant_time(nonzero), LimbMask::False);
437 }
438 }
439
440 #[test]
test_limbs_equal_limb()441 fn test_limbs_equal_limb() {
442 for zero in ZEROES {
443 assert_eq!(limbs_equal_limb_constant_time(zero, 0), LimbMask::True);
444 }
445 for nonzero in NONZEROES {
446 assert_eq!(limbs_equal_limb_constant_time(nonzero, 0), LimbMask::False);
447 }
448 static EQUAL: &[(&[Limb], Limb)] = &[
449 (&[1], 1),
450 (&[MAX], MAX),
451 (&[1, 0], 1),
452 (&[MAX, 0, 0], MAX),
453 (&[0b100], 0b100),
454 (&[0b100, 0], 0b100),
455 ];
456 for &(a, b) in EQUAL {
457 assert_eq!(limbs_equal_limb_constant_time(a, b), LimbMask::True);
458 }
459 static UNEQUAL: &[(&[Limb], Limb)] = &[
460 (&[0], 1),
461 (&[2], 1),
462 (&[3], 1),
463 (&[1, 1], 1),
464 (&[0b100, 0b100], 0b100),
465 (&[1, 0, 0b100, 0, 0, 0, 0, 0], 1),
466 (&[1, 0, 0, 0, 0, 0, 0, 0b100], 1),
467 (&[MAX, MAX], MAX),
468 (&[MAX, 1], MAX),
469 ];
470 for &(a, b) in UNEQUAL {
471 assert_eq!(limbs_equal_limb_constant_time(a, b), LimbMask::False);
472 }
473 }
474
475 #[test]
476 #[cfg(feature = "alloc")]
test_limbs_less_than_limb_constant_time()477 fn test_limbs_less_than_limb_constant_time() {
478 static LESSER: &[(&[Limb], Limb)] = &[
479 (&[0], 1),
480 (&[0, 0], 1),
481 (&[1, 0], 2),
482 (&[2, 0], 3),
483 (&[2, 0], 3),
484 (&[MAX - 1], MAX),
485 (&[MAX - 1, 0], MAX),
486 ];
487 for &(a, b) in LESSER {
488 assert_eq!(limbs_less_than_limb_constant_time(a, b), LimbMask::True);
489 }
490 static EQUAL: &[(&[Limb], Limb)] = &[
491 (&[0], 0),
492 (&[0, 0, 0, 0], 0),
493 (&[1], 1),
494 (&[1, 0, 0, 0, 0, 0, 0], 1),
495 (&[MAX], MAX),
496 ];
497 static GREATER: &[(&[Limb], Limb)] = &[
498 (&[1], 0),
499 (&[2, 0], 1),
500 (&[3, 0, 0, 0], 1),
501 (&[0, 1, 0, 0], 1),
502 (&[0, 0, 1, 0], 1),
503 (&[0, 0, 1, 1], 1),
504 (&[MAX], MAX - 1),
505 ];
506 for &(a, b) in EQUAL.iter().chain(GREATER.iter()) {
507 assert_eq!(limbs_less_than_limb_constant_time(a, b), LimbMask::False);
508 }
509 }
510
511 #[test]
test_parse_big_endian_and_pad_consttime()512 fn test_parse_big_endian_and_pad_consttime() {
513 const LIMBS: usize = 4;
514
515 {
516 // Empty input.
517 let inp = untrusted::Input::from(&[]);
518 let mut result = [0; LIMBS];
519 assert!(parse_big_endian_and_pad_consttime(inp, &mut result).is_err());
520 }
521
522 // The input is longer than will fit in the given number of limbs.
523 {
524 let inp = [1, 2, 3, 4, 5, 6, 7, 8, 9];
525 let inp = untrusted::Input::from(&inp);
526 let mut result = [0; 8 / LIMB_BYTES];
527 assert!(parse_big_endian_and_pad_consttime(inp, &mut result[..]).is_err());
528 }
529
530 // Less than a full limb.
531 {
532 let inp = [0xfe];
533 let inp = untrusted::Input::from(&inp);
534 let mut result = [0; LIMBS];
535 assert_eq!(
536 Ok(()),
537 parse_big_endian_and_pad_consttime(inp, &mut result[..])
538 );
539 assert_eq!(&[0xfe, 0, 0, 0], &result);
540 }
541
542 // A whole limb for 32-bit, half a limb for 64-bit.
543 {
544 let inp = [0xbe, 0xef, 0xf0, 0x0d];
545 let inp = untrusted::Input::from(&inp);
546 let mut result = [0; LIMBS];
547 assert_eq!(Ok(()), parse_big_endian_and_pad_consttime(inp, &mut result));
548 assert_eq!(&[0xbeeff00d, 0, 0, 0], &result);
549 }
550
551 // XXX: This is a weak set of tests. TODO: expand it.
552 }
553
554 #[test]
test_big_endian_from_limbs_same_length()555 fn test_big_endian_from_limbs_same_length() {
556 #[cfg(target_pointer_width = "32")]
557 let limbs = [
558 0xbccddeef, 0x89900aab, 0x45566778, 0x01122334, 0xddeeff00, 0x99aabbcc, 0x55667788,
559 0x11223344,
560 ];
561
562 #[cfg(target_pointer_width = "64")]
563 let limbs = [
564 0x8990_0aab_bccd_deef,
565 0x0112_2334_4556_6778,
566 0x99aa_bbcc_ddee_ff00,
567 0x1122_3344_5566_7788,
568 ];
569
570 let expected = [
571 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee,
572 0xff, 0x00, 0x01, 0x12, 0x23, 0x34, 0x45, 0x56, 0x67, 0x78, 0x89, 0x90, 0x0a, 0xab,
573 0xbc, 0xcd, 0xde, 0xef,
574 ];
575
576 let mut out = [0xabu8; 32];
577 big_endian_from_limbs(&limbs[..], &mut out);
578 assert_eq!(&out[..], &expected[..]);
579 }
580
581 #[should_panic]
582 #[test]
test_big_endian_from_limbs_fewer_limbs()583 fn test_big_endian_from_limbs_fewer_limbs() {
584 #[cfg(target_pointer_width = "32")]
585 // Two fewer limbs.
586 let limbs = [
587 0xbccddeef, 0x89900aab, 0x45566778, 0x01122334, 0xddeeff00, 0x99aabbcc,
588 ];
589
590 // One fewer limb.
591 #[cfg(target_pointer_width = "64")]
592 let limbs = [
593 0x8990_0aab_bccd_deef,
594 0x0112_2334_4556_6778,
595 0x99aa_bbcc_ddee_ff00,
596 ];
597
598 let mut out = [0xabu8; 32];
599
600 big_endian_from_limbs(&limbs[..], &mut out);
601 }
602
603 #[test]
test_limbs_minimal_bits()604 fn test_limbs_minimal_bits() {
605 const ALL_ONES: Limb = LimbMask::True as Limb;
606 static CASES: &[(&[Limb], usize)] = &[
607 (&[], 0),
608 (&[0], 0),
609 (&[ALL_ONES], LIMB_BITS),
610 (&[ALL_ONES, 0], LIMB_BITS),
611 (&[ALL_ONES, 1], LIMB_BITS + 1),
612 (&[0, 0], 0),
613 (&[1, 0], 1),
614 (&[0, 1], LIMB_BITS + 1),
615 (&[0, ALL_ONES], 2 * LIMB_BITS),
616 (&[ALL_ONES, ALL_ONES], 2 * LIMB_BITS),
617 (&[ALL_ONES, ALL_ONES >> 1], 2 * LIMB_BITS - 1),
618 (&[ALL_ONES, 0b100_0000], LIMB_BITS + 7),
619 (&[ALL_ONES, 0b101_0000], LIMB_BITS + 7),
620 (&[ALL_ONES, ALL_ONES >> 1], LIMB_BITS + (LIMB_BITS) - 1),
621 ];
622 for (limbs, bits) in CASES {
623 assert_eq!(limbs_minimal_bits(limbs).as_usize_bits(), *bits);
624 }
625 }
626 }
627