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