Botan 3.14.1
Crypto and TLS for C&
mp_core.h
Go to the documentation of this file.
1/*
2* MPI Algorithms
3* (C) 1999-2010,2018,2024 Jack Lloyd
4* 2006 Luca Piccarreta
5* 2016 Matthias Gierlings
6*
7* Botan is released under the Simplified BSD License (see license.txt)
8*/
9
10#ifndef BOTAN_MP_CORE_OPS_H_
11#define BOTAN_MP_CORE_OPS_H_
12
13#include <botan/assert.h>
14#include <botan/types.h>
15#include <botan/internal/bit_ops.h>
16#include <botan/internal/ct_utils.h>
17#include <botan/internal/loadstor.h>
18#include <botan/internal/mem_utils.h>
19#include <botan/internal/mp_asmi.h>
20#include <array>
21#include <bit>
22#include <span>
23#include <utility>
24
25namespace Botan {
26
27/*
28* If cond == 0, does nothing.
29* If cond > 0, swaps x[0:size] with y[0:size]
30* Runs in constant time
31*/
32template <WordType W>
33inline constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size) {
34 const auto mask = CT::Mask<W>::expand(cnd);
35
36 for(size_t i = 0; i != size; ++i) {
37 const W a = x[i];
38 const W b = y[i];
39 x[i] = mask.select(b, a);
40 y[i] = mask.select(a, b);
41 }
42}
43
44/*
45* If cond > 0 adds x[0:size] and y[0:size] and returns carry
46* Runs in constant time
47*/
48template <WordType W>
49inline constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size) {
50 const auto mask = CT::Mask<W>::expand(cnd).value();
51
52 W carry = 0;
53
54 for(size_t i = 0; i != size; ++i) {
55 x[i] = word_add(x[i], y[i] & mask, &carry);
56 }
57
58 return (mask & carry);
59}
60
61/*
62* If cond > 0 subtracts y[0:size] from x[0:size] and returns borrow
63* Runs in constant time
64*/
65template <WordType W>
66inline constexpr auto bigint_cnd_sub(W cnd, W x[], const W y[], size_t size) -> W {
67 const auto mask = CT::Mask<W>::expand(cnd).value();
68
69 W carry = 0;
70
71 for(size_t i = 0; i != size; ++i) {
72 x[i] = word_sub(x[i], y[i] & mask, &carry);
73 }
74
75 return (mask & carry);
76}
77
78/*
79* 2s complement absolute value
80* If cond > 0 sets x to ~x + 1
81* Runs in constant time
82*/
83template <WordType W>
84inline constexpr void bigint_cnd_abs(W cnd, W x[], size_t size) {
85 const auto mask = CT::Mask<W>::expand(cnd);
86
87 W carry = mask.if_set_return(1);
88 for(size_t i = 0; i != size; ++i) {
89 const W z = word_add(~x[i], static_cast<W>(0), &carry);
90 x[i] = mask.select(z, x[i]);
91 }
92}
93
94/**
95* Two operand addition with carry out
96*/
97template <WordType W>
98inline constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W {
99 W carry = 0;
100
101 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
102
103 const size_t blocks = y_size - (y_size % 8);
104
105 for(size_t i = 0; i != blocks; i += 8) {
106 carry = word8_add2(x + i, y + i, carry);
107 }
108
109 for(size_t i = blocks; i != y_size; ++i) {
110 x[i] = word_add(x[i], y[i], &carry);
111 }
112
113 for(size_t i = y_size; i != x_size; ++i) {
114 x[i] = word_add(x[i], static_cast<W>(0), &carry);
115 }
116
117 return carry;
118}
119
120/**
121* Three operand addition with carry out
122*/
123template <WordType W>
124inline constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W {
125 if(x_size < y_size) {
126 return bigint_add3(z, y, y_size, x, x_size);
127 }
128
129 W carry = 0;
130
131 const size_t blocks = y_size - (y_size % 8);
132
133 for(size_t i = 0; i != blocks; i += 8) {
134 carry = word8_add3(z + i, x + i, y + i, carry);
135 }
136
137 for(size_t i = blocks; i != y_size; ++i) {
138 z[i] = word_add(x[i], y[i], &carry);
139 }
140
141 for(size_t i = y_size; i != x_size; ++i) {
142 z[i] = word_add(x[i], static_cast<W>(0), &carry);
143 }
144
145 return carry;
146}
147
148/**
149* Two operand subtraction
150*/
151template <WordType W>
152inline constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W {
153 W borrow = 0;
154
155 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
156
157 const size_t blocks = y_size - (y_size % 8);
158
159 for(size_t i = 0; i != blocks; i += 8) {
160 borrow = word8_sub2(x + i, y + i, borrow);
161 }
162
163 for(size_t i = blocks; i != y_size; ++i) {
164 x[i] = word_sub(x[i], y[i], &borrow);
165 }
166
167 for(size_t i = y_size; i != x_size; ++i) {
168 x[i] = word_sub(x[i], static_cast<W>(0), &borrow);
169 }
170
171 return borrow;
172}
173
174/**
175* Two operand subtraction, x = y - x; assumes y >= x
176*/
177template <WordType W>
178inline constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size) {
179 W borrow = 0;
180
181 for(size_t i = 0; i != y_size; ++i) {
182 x[i] = word_sub(y[i], x[i], &borrow);
183 }
184
185 BOTAN_ASSERT(borrow == 0, "y must be greater than x");
186}
187
188/**
189* Three operand subtraction
190*
191* Expects that x_size >= y_size
192*
193* Writes to z[0:x_size] and returns borrow
194*/
195template <WordType W>
196inline constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W {
197 W borrow = 0;
198
199 BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
200
201 const size_t blocks = y_size - (y_size % 8);
202
203 for(size_t i = 0; i != blocks; i += 8) {
204 borrow = word8_sub3(z + i, x + i, y + i, borrow);
205 }
206
207 for(size_t i = blocks; i != y_size; ++i) {
208 z[i] = word_sub(x[i], y[i], &borrow);
209 }
210
211 for(size_t i = y_size; i != x_size; ++i) {
212 z[i] = word_sub(x[i], static_cast<W>(0), &borrow);
213 }
214
215 return borrow;
216}
217
218/**
219* Conditional subtraction for Montgomery reduction
220*
221* This function assumes that (x0 || x) is less than 2*p
222*
223* Computes z[0:N] = (x0 || x[0:N]) - p[0:N]
224*
225* If z would be positive, returns z[0:N]
226* Otherwise returns original input x
227*/
228template <WordType W>
229inline constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[]) {
230 W borrow = 0;
231
232 const size_t blocks = N - (N % 8);
233
234 for(size_t i = 0; i != blocks; i += 8) {
235 borrow = word8_sub3(z + i, x + i, p + i, borrow);
236 }
237
238 for(size_t i = blocks; i != N; ++i) {
239 z[i] = word_sub(x[i], p[i], &borrow);
240 }
241
242 borrow = (x0 - borrow) > x0;
243
244 CT::conditional_assign_mem(borrow, z, x, N);
245}
246
247/**
248* Conditional subtraction for Montgomery reduction
249*
250* This function assumes that (x0 || x) is less than 2*p
251*
252* Computes z[0:N] = (x0 || x[0:N]) - p[0:N]
253*
254* If z would be positive, returns z[0:N]
255* Otherwise returns original input x
256*/
257template <size_t N, WordType W>
258inline constexpr void bigint_monty_maybe_sub(W z[N], W x0, const W x[N], const W y[N]) {
259 W borrow = 0;
260
261 for(size_t i = 0; i != N; ++i) {
262 z[i] = word_sub(x[i], y[i], &borrow);
263 }
264
265 borrow = (x0 - borrow) > x0;
266
267 CT::conditional_assign_mem(borrow, z, x, N);
268}
269
270/**
271* Return abs(x-y), ie if x >= y, then compute z = x - y
272* Otherwise compute z = y - x
273* No borrow is possible since the result is always >= 0
274*
275* Returns a Mask: |1| if x < y or |0| if x >= y
276* @param z output array of at least N words
277* @param x input array of N words
278* @param y input array of N words
279* @param N length of x and y
280* @param ws array of at least 2*N words
281*/
282template <WordType W>
283inline constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask<W> {
284 // Subtract in both direction then conditional copy out the result
285
286 W* ws0 = ws;
287 W* ws1 = ws + N;
288
289 W borrow0 = 0;
290 W borrow1 = 0;
291
292 const size_t blocks = N - (N % 8);
293
294 for(size_t i = 0; i != blocks; i += 8) {
295 borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
296 borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
297 }
298
299 for(size_t i = blocks; i != N; ++i) {
300 ws0[i] = word_sub(x[i], y[i], &borrow0);
301 ws1[i] = word_sub(y[i], x[i], &borrow1);
302 }
303
304 return CT::conditional_copy_mem(borrow0, z, ws1, ws0, N);
305}
306
307/*
308* Shift Operations
309*/
310
311// Caller must ensure x[x_words..x_size-1] is zeroed.
312template <WordType W>
313inline constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift) {
314 const size_t word_shift = shift / WordInfo<W>::bits;
315 const size_t bit_shift = shift % WordInfo<W>::bits;
316
317 BOTAN_ASSERT_NOMSG(word_shift <= x_size);
318 BOTAN_ASSERT_NOMSG(x_words <= x_size - word_shift);
319
320 unchecked_copy_memory(x + word_shift, x, x_words);
321 zeroize_buffer(x, word_shift);
322
323 const auto carry_mask = CT::Mask<W>::expand(bit_shift);
324 const W carry_shift = carry_mask.if_set_return(WordInfo<W>::bits - bit_shift);
325
326 W carry = 0;
327 for(size_t i = word_shift; i != x_size; ++i) {
328 const W w = x[i];
329 x[i] = (w << bit_shift) | carry;
330 carry = carry_mask.if_set_return(w >> carry_shift);
331 }
332}
333
334template <WordType W>
335inline constexpr void bigint_shr1(W x[], size_t x_size, size_t shift) {
336 const size_t word_shift = shift / WordInfo<W>::bits;
337 const size_t bit_shift = shift % WordInfo<W>::bits;
338
339 const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
340
341 if(top > 0) {
342 unchecked_copy_memory(x, x + word_shift, top);
343 }
344 zeroize_buffer(x + top, std::min(word_shift, x_size));
345
346 const auto carry_mask = CT::Mask<W>::expand(bit_shift);
347 const W carry_shift = carry_mask.if_set_return(WordInfo<W>::bits - bit_shift);
348
349 W carry = 0;
350
351 for(size_t i = 0; i != top; ++i) {
352 const W w = x[top - i - 1];
353 x[top - i - 1] = (w >> bit_shift) | carry;
354 carry = carry_mask.if_set_return(w << carry_shift);
355 }
356}
357
358template <WordType W>
359inline constexpr void bigint_shl2(W y[], size_t y_size, const W x[], size_t x_size, size_t shift) {
360 const size_t word_shift = shift / WordInfo<W>::bits;
361 const size_t bit_shift = shift % WordInfo<W>::bits;
362
363 BOTAN_ASSERT_NOMSG(word_shift <= y_size);
364 BOTAN_ASSERT_NOMSG(x_size < y_size - word_shift);
365
366 unchecked_copy_memory(y + word_shift, x, x_size);
367 zeroize_buffer(y, word_shift);
368 zeroize_buffer(y + word_shift + x_size, y_size - word_shift - x_size);
369
370 const auto carry_mask = CT::Mask<W>::expand(bit_shift);
371 const W carry_shift = carry_mask.if_set_return(WordInfo<W>::bits - bit_shift);
372
373 W carry = 0;
374 for(size_t i = word_shift; i != x_size + word_shift + 1; ++i) {
375 const W w = y[i];
376 y[i] = (w << bit_shift) | carry;
377 carry = carry_mask.if_set_return(w >> carry_shift);
378 }
379}
380
381template <WordType W>
382inline constexpr void bigint_shr2(W y[], size_t y_size, const W x[], size_t x_size, size_t shift) {
383 const size_t word_shift = shift / WordInfo<W>::bits;
384 const size_t bit_shift = shift % WordInfo<W>::bits;
385 const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
386
387 BOTAN_ASSERT_NOMSG(new_size <= y_size);
388
389 if(new_size > 0) {
390 unchecked_copy_memory(y, x + word_shift, new_size);
391 }
392 zeroize_buffer(y + new_size, y_size - new_size);
393
394 const auto carry_mask = CT::Mask<W>::expand(bit_shift);
395 const W carry_shift = carry_mask.if_set_return(WordInfo<W>::bits - bit_shift);
396
397 W carry = 0;
398 for(size_t i = new_size; i > 0; --i) {
399 W w = y[i - 1];
400 y[i - 1] = (w >> bit_shift) | carry;
401 carry = carry_mask.if_set_return(w << carry_shift);
402 }
403}
404
405/*
406* Linear Multiply - returns the carry
407*/
408template <WordType W>
409[[nodiscard]] inline constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W {
410 W carry = 0;
411
412 for(size_t i = 0; i != x_size; ++i) {
413 x[i] = word_madd2(x[i], y, &carry);
414 }
415
416 return carry;
417}
418
419template <WordType W>
420inline constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y) {
421 const size_t blocks = x_size - (x_size % 8);
422
423 W carry = 0;
424
425 for(size_t i = 0; i != blocks; i += 8) {
426 carry = word8_linmul3(z + i, x + i, y, carry);
427 }
428
429 for(size_t i = blocks; i != x_size; ++i) {
430 z[i] = word_madd2(x[i], y, &carry);
431 }
432
433 z[x_size] = carry;
434}
435
436/**
437* Compute z[0:N] = z[0:N] - q * y[0:N]
438*
439* Returns the borrow out, a full word value which the caller must
440* subtract from z[N]
441*/
442template <WordType W>
443inline constexpr auto bigint_submul(W z[], const W y[], size_t N, W q) -> W {
444 W mul_carry = 0;
445 W borrow = 0;
446
447 for(size_t i = 0; i != N; ++i) {
448 const W t = word_madd2(y[i], q, &mul_carry);
449 z[i] = word_sub(z[i], t, &borrow);
450 }
451
452 // Both mul_carry <= W_max - 1 and borrow <= 1, so this cannot overflow
453 return mul_carry + borrow;
454}
455
456/**
457* Compare x and y
458* Return -1 if x < y
459* Return 0 if x == y
460* Return 1 if x > y
461*/
462template <WordType W>
463inline constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size) {
464 static_assert(sizeof(W) >= sizeof(uint32_t), "Size assumption");
465
466 const W LT = static_cast<W>(-1);
467 const W EQ = 0;
468 const W GT = 1;
469
470 const size_t common_elems = std::min(x_size, y_size);
471
472 W result = EQ; // until found otherwise
473
474 for(size_t i = 0; i != common_elems; i++) {
475 const auto is_eq = CT::Mask<W>::is_equal(x[i], y[i]);
476 const auto is_lt = CT::Mask<W>::is_lt(x[i], y[i]);
477
478 result = is_eq.select(result, is_lt.select(LT, GT));
479 }
480
481 if(x_size < y_size) {
482 W mask = 0;
483 for(size_t i = x_size; i != y_size; i++) {
484 mask |= y[i];
485 }
486
487 // If any bits were set in high part of y, then x < y
488 result = CT::Mask<W>::is_zero(mask).select(result, LT);
489 } else if(y_size < x_size) {
490 W mask = 0;
491 for(size_t i = y_size; i != x_size; i++) {
492 mask |= x[i];
493 }
494
495 // If any bits were set in high part of x, then x > y
496 result = CT::Mask<W>::is_zero(mask).select(result, GT);
497 }
498
499 CT::unpoison(result);
500 BOTAN_DEBUG_ASSERT(result == LT || result == GT || result == EQ);
501 return static_cast<int32_t>(result);
502}
503
504/**
505* Compare x and y
506* Returns a Mask: |1| if x[0:x_size] < y[0:y_size] or |0| otherwise
507* If lt_or_equal is true, returns |1| also for x == y
508*/
509template <WordType W>
510inline constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal = false)
511 -> CT::Mask<W> {
512 const size_t common_elems = std::min(x_size, y_size);
513
514 auto is_lt = CT::Mask<W>::expand(lt_or_equal);
515
516 for(size_t i = 0; i != common_elems; i++) {
517 const auto eq = CT::Mask<W>::is_equal(x[i], y[i]);
518 const auto lt = CT::Mask<W>::is_lt(x[i], y[i]);
519 is_lt = eq.select_mask(is_lt, lt);
520 }
521
522 if(x_size < y_size) {
523 W mask = 0;
524 for(size_t i = x_size; i != y_size; i++) {
525 mask |= y[i];
526 }
527 // If any bits were set in high part of y, then is_lt should be forced true
528 is_lt |= CT::Mask<W>::expand(mask);
529 } else if(y_size < x_size) {
530 W mask = 0;
531 for(size_t i = y_size; i != x_size; i++) {
532 mask |= x[i];
533 }
534
535 // If any bits were set in high part of x, then is_lt should be false
536 is_lt &= CT::Mask<W>::is_zero(mask);
537 }
538
539 return is_lt;
540}
541
542template <WordType W>
543inline constexpr auto bigint_ct_is_eq(const W x[], size_t x_size, const W y[], size_t y_size) -> CT::Mask<W> {
544 const size_t common_elems = std::min(x_size, y_size);
545
546 W diff = 0;
547
548 for(size_t i = 0; i != common_elems; i++) {
549 diff |= (x[i] ^ y[i]);
550 }
551
552 // If any bits were set in high part of x/y, then they are not equal
553 if(x_size < y_size) {
554 for(size_t i = x_size; i != y_size; i++) {
555 diff |= y[i];
556 }
557 } else if(y_size < x_size) {
558 for(size_t i = y_size; i != x_size; i++) {
559 diff |= x[i];
560 }
561 }
562
563 return CT::Mask<W>::is_zero(diff);
564}
565
566/**
567* Compute the reciprocal floor((2^(2b) - 1) / D) - 2^b of a normalized
568* divisor D (ie one with its top bit set)
569*
570* This is the same value as computed by Algorithms 2 and 3 of
571* Möller and Granlund "Improved Division by Invariant Integers".
572* (https://gmplib.org/~tege/division-paper.pdf)
573*
574* Uses compiler provided division instructions where available, and
575* Algorithm 2 as the portable 64-bit fallback.
576*/
577template <WordType W>
578constexpr W reciprocal_word(W D) {
580
581 /*
582 * Subtracting 2^b*D from the numerator gives
583 * v = floor(((~D)*2^b + (2^b - 1)) / D). Since D is normalized, ~D < D
584 * and the quotient fits in a word. See the first part of Section III A
585 * in the paper.
586 */
587 if constexpr(sizeof(W) == 4) {
588 const auto nD = ~D; // Work around spurious MSVC warning
589 const typename WordInfo<W>::dword n =
590 (static_cast<typename WordInfo<W>::dword>(nD) << WordInfo<W>::bits) | WordInfo<W>::max;
591 return static_cast<W>(n / D);
592 } else {
593 if(!std::is_constant_evaluated()) {
594#if defined(BOTAN_MP_USE_X86_64_ASM)
595 W quotient = 0;
596 W remainder = 0;
597 // NOLINTNEXTLINE(*-no-assembler)
598 asm("divq %[d]"
599 : "=a"(quotient), "=d"(remainder)
600 : [d] "r"(D), "a"(WordInfo<W>::max), "d"(static_cast<W>(~D))
601 : "cc");
602 return quotient;
603#elif !defined(BOTAN_BUILD_COMPILER_IS_CLANGCL)
604 /* clang-cl has a bug where on encountering a 128/64 division it emits
605 * a call to __udivti3() but then fails to link the relevant builtin into
606 * the binary, causing a link failure. Work around this by simply omitting
607 * such code for clang-cl
608 *
609 * See https://github.com/llvm/llvm-project/issues/25679
610 */
611 if constexpr(WordInfo<W>::dword_is_native) {
612 typename WordInfo<W>::dword n =
613 (static_cast<typename WordInfo<W>::dword>(~D) << WordInfo<W>::bits) | WordInfo<W>::max;
614 return static_cast<W>(n / D);
615 }
616#endif
617 }
618
619 // Algorithm 2 of Möller and Granlund
620 const W d0 = D & 1;
621 const W d9 = D >> 55;
622 const W d40 = (D >> 24) + 1;
623 const W d63 = (D >> 1) + d0; // ceil(D/2)
624
625 // This division is done with a table lookup in the paper
626 const W v0 = ((W(1) << 19) - (W(3) << 8)) / d9;
627 const W v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
628 const W v2 = (v1 << 13) + ((v1 * ((W(1) << 60) - v1 * d40)) >> 47);
629
630 const W e = W(0) - v2 * d63 + (v2 >> 1) * d0;
631
632 W product_hi = 0;
633 word_madd2(v2, e, &product_hi);
634 const W v3 = (v2 << 31) + (product_hi >> 1);
635
636 // Compute floor((v3 + 2^64 + 1) * D / 2^64) modulo 2^64
637 product_hi = D;
638 word_madd2(v3, D, &product_hi);
639 return v3 - D - product_hi;
640 }
641}
642
643/**
644* Compute the same reciprocal as reciprocal_word, but running
645* in constant time.
646*
647* Requires that D is normalized (ie with its top bit set)
648*/
649template <WordType W>
650constexpr W reciprocal_word_ct(W D) {
652
653 // Bit serial long division of ((~D) || (2^b - 1)) / D, with all of the
654 // conditional logic computed via masks
655 W remainder = static_cast<W>(~D);
656 W quotient = 0;
657
658 for(size_t i = 0; i != WordInfo<W>::bits; ++i) {
659 const auto carry = CT::Mask<W>::expand_top_bit(remainder);
660 remainder = static_cast<W>((remainder << 1) | 1);
661 quotient <<= 1;
662
663 const auto sub = carry | CT::Mask<W>::is_gte(remainder, D);
664 remainder -= sub.if_set_return(D);
665 quotient |= sub.if_set_return(1);
666 }
667
668 return quotient;
669}
670
671/**
672* Setup for word level division/modulo operations
673*
674* The general case uses a reciprocal of the normalized divisor,
675* precomputed at construction time, following Algorithm 4 of Möller and
676* Granlund "Improved Division by Invariant Integers" (IEEE Trans.
677* Computers, 2011).
678*
679* The 2/1 division operations run in constant time with respect to the
680* numerator. The divisor is treated as public; construction and the
681* choice of code path are variable time in it.
682*/
683template <WordType W>
684class divide_precomp final {
685 public:
686 // The caller must guarantee not to use divisor == 0
687 static constexpr divide_precomp setup_vartime(W divisor) {
688 const size_t shift = WordInfo<W>::bits - high_bit(divisor);
689 const W norm_divisor = divisor << shift;
690 const W reciprocal = reciprocal_word(norm_divisor);
691 return divide_precomp(divisor, shift, norm_divisor, reciprocal);
692 }
693
694 // The caller must guarantee not to use divisor == 0
695 static constexpr divide_precomp setup(W divisor) {
696 const size_t shift = WordInfo<W>::bits - high_bit(divisor);
697 const W norm_divisor = divisor << shift;
698 const W reciprocal = reciprocal_word_ct(norm_divisor);
699 return divide_precomp(divisor, shift, norm_divisor, reciprocal);
700 }
701
702 // Setup using the value of reciprocal() from a previous setup with this divisor
703 static constexpr divide_precomp setup_with_reciprocal(W divisor, W reciprocal) {
704 // The divisor is public so a variable time count is fine
705 const size_t shift = std::countl_zero(divisor);
706 return divide_precomp(divisor, shift, divisor << shift, reciprocal);
707 }
708
709 constexpr W reciprocal() const { return m_reciprocal; }
710
711 // Return quotient and remainder of (n1 || n0) divided by d
712 //
713 // This assumes n1 < d so that the quotient fits in a word and
714 // will produce incorrect output if n1 >= d, since in that case
715 // the quotient exceeds the word size.
716 //
717 // This is constant time with respect to n1/n0 but leaks information
718 // about the divisor
719 inline constexpr std::pair<W, W> divmod_2to1_vartime(W n1, W n0) const {
720 if(m_divisor == WordInfo<W>::max) {
721 const W q = div_2to1_max_d(n1, n0);
722 const W r = static_cast<W>(n0 + q);
723 return std::make_pair(q, r);
724 }
725
726 if(m_divisor == WordInfo<W>::top_bit) {
727 // Simply a shift by N-1 bits
728 const W q = (n1 << 1) | (n0 >> (WordInfo<W>::bits - 1));
729 const W r = static_cast<W>(n0 & (WordInfo<W>::top_bit - 1));
730 return std::make_pair(q, r);
731 }
732
733 return divmod_2to1_ct(n1, n0);
734 }
735
736 // Return quotient and remainder of (n1 || n0) divided by d
737 //
738 // This assumes n1 < d so that the quotient fits in a word and
739 // will produce incorrect output if n1 >= d, since in that case
740 // the quotient exceeds the word size.
741 inline constexpr std::pair<W, W> divmod_2to1_ct(W n1, W n0) const {
742 /*
743 * Scale the numerator to match the normalized divisor; the scaling cancels
744 * in the quotient and is removed from the remainder by the final shift.
745 */
746 n1 <<= m_shift;
747 const size_t rshift = WordInfo<W>::bits - m_shift;
748 /*
749 * We can't just `n0 >> rshift` because m_shift may be 0 (high bit divisor)
750 * in which case rshift will be the maximum bit length, and >> by the maximum
751 * bitlength is undefined behavior despite having an entirely obvious meaning.
752 *
753 * However we know m_shift is not equal to the bit length of the word, because
754 * that would imply that the divisor is 0. Thus rshift must be >= 1. So split
755 * the shift into two phases (first rshift-1, then 1)
756 */
757 n1 |= (n0 >> 1) >> (rshift - 1);
758 n0 <<= m_shift;
759
760 const auto [q, scaled_r] = div2by1_preinv(n1, n0, m_norm_divisor, m_reciprocal);
761 const W r = scaled_r >> m_shift;
762 return std::make_pair(q, r);
763 }
764
765 // Return floor((n1 || n0) / d)
766 //
767 // This assumes n1 < d so that the quotient fits in a word
768 //
769 // This is constant time with respect to n1/n0 but leaks information about d
770 inline constexpr W div_2to1(W n1, W n0) const { return this->divmod_2to1_vartime(n1, n0).first; }
771
772 // Return (n1 || n0) % d
773 //
774 // This assumes n1 < d
775 //
776 // This is constant time with respect to n1/n0 but leaks information about d
777 inline constexpr W mod_2to1(W n1, W n0) const { return this->divmod_2to1_vartime(n1, n0).second; }
778
779 private:
780 constexpr divide_precomp(W divisor, size_t shift, W norm_divisor, W reciprocal) :
781 m_divisor(divisor), m_shift(shift), m_norm_divisor(norm_divisor), m_reciprocal(reciprocal) {}
782
783 /*
784 * 2/1 division of (u1 || u0) by the normalized divisor D given its
785 * reciprocal v, returning quotient and remainder. Requires u1 < D.
786 *
787 * Algorithm 4 of Möller and Granlund "Improved Division by Invariant
788 * Integers", with the conditional corrections computed as masked updates.
789 *
790 * Runs in constant time with respect to u1 and u0.
791 */
792 static constexpr std::pair<W, W> div2by1_preinv(W u1, W u0, W D, W v) {
793 // Steps 1-3: <q1,q0> = v*u1; <q1,q0> += <u1,u0>; q1 += 1
794 W q1 = u0;
795 const W q0 = word_madd2(u1, v, &q1); // <q1,q0> = u1*v + u0
796 q1 += u1 + 1;
797
798 // Step 4
799 W r = u0 - q1 * D;
800
801 // Steps 5-7: If r >= q0 { q1 -= 1; r += d; }
802 const auto fix_down = CT::Mask<W>::is_gt(r, q0);
803 q1 -= fix_down.if_set_return(1);
804 r += fix_down.if_set_return(D);
805
806 // Steps 8-10: if r >= D { q1 += 1; r -= D; }
807 const auto fix_up = CT::Mask<W>::is_gte(r, D);
808 q1 += fix_up.if_set_return(1);
809 r -= fix_up.if_set_return(D);
810
811 // Step 11
812 return std::make_pair(q1, r);
813 }
814
815 /*
816 * When the divisor is the maximum integer value, then a two word
817 * division becomes simple.
818 */
819 static inline constexpr W div_2to1_max_d(W n1, W n0) {
820 /*
821 Use k to refer to WordInfo<W>::bits
822
823 We are dividing n = (n1 * 2^k) + n0 by 2^k - 1
824
825 Recall that 2^k = 1 (mod 2^k - 1)
826
827 Rewrite n = n1*2^k + n0 as n1*(2^k - 1) + n1 + n0
828
829 The result of dividing n by (2^k - 1) will be equal to
830 (n1*(2^k-1) + n1 + n0) / (2^k-1) =
831 n1 + ((n1 + n0) / (2^k-1)
832
833 Use c to refer to ((n1 + n0) / (2^k-1))
834
835 If (n1 + n0) < (2^k - 1) then c is 0
836 If (n1 + n0) >= (2^k - 1) then c is 1
837
838 Since n1 < 2^k - 1 [*] and n0 <= 2^k - 1 it is impossible for (n1 + n0) / (2^k -1)
839 to be greater than 1.
840
841 [*] We require n1 be strictly less than the divisor to ensure that the
842 output fits in a single word; this is checked at the start of divmod_2to1.
843
844 And since n1 + 1 <= 2^k - 1, c == 1 exactly when n0 + (n1 + 1) carries out.
845 */
846
847 const W s = n0 + n1 + 1;
848 const W c = CT::Mask<W>::is_lt(s, n0).if_set_return(1);
849 return n1 + c;
850 }
851
852 W m_divisor;
853 size_t m_shift;
854 W m_norm_divisor;
855 W m_reciprocal;
856};
857
858/*
859* Compute an integer x such that (a*x) == -1 (mod 2^n)
860*
861* Throws an exception if input is even, since in that case no inverse
862* exists. If input is odd, then input and 2^n are relatively prime and
863* the inverse exists.
864*/
865template <WordType W>
866inline constexpr auto monty_inverse(W a) -> W {
867 BOTAN_ARG_CHECK(CT::driveby_unpoison(a % 2 == 1), "Cannot compute Montgomery inverse of an even integer");
868
869 // Newton's Method, following https://lemire.me/blog/2017/09/18/computing-the-inverse-of-odd-integers/
870
871 constexpr size_t iter = WordInfo<W>::bits == 64 ? 4 : 3;
872
873 // Initial guess provides 5 bits of accuracy
874 W r = (3 * a) ^ 2;
875
876 // Each iteration doubles the accuracy
877 for(size_t i = 0; i != iter; ++i) {
878 r = r * (2 - r * a);
879 }
880
881 // Now invert in addition space
882 r = (WordInfo<W>::max - r) + 1;
883
884 return r;
885}
886
887template <size_t S, WordType W, size_t N>
888inline constexpr W shift_left(std::array<W, N>& x) {
889 static_assert(N >= 1, "Invalid input size");
890 static_assert(S > 0, "Zero shift not supported");
891 static_assert(S < WordInfo<W>::bits, "Shift too large");
892
893 const W carry = x[N - 1] >> (WordInfo<W>::bits - S);
894
895 for(size_t i = N - 1; i != 0; --i) {
896 x[i] = (x[i] << S) | (x[i - 1] >> (WordInfo<W>::bits - S));
897 }
898 x[0] <<= S;
899
900 return carry;
901}
902
903template <size_t S, WordType W, size_t N>
904inline constexpr W shift_right(std::array<W, N>& x) {
905 static_assert(N >= 1, "Invalid input size");
906 static_assert(S > 0, "Zero shift not supported");
907 static_assert(S < WordInfo<W>::bits, "Shift too large");
908
909 const W carry = x[0] << (WordInfo<W>::bits - S);
910
911 for(size_t i = 0; i != N - 1; ++i) {
912 x[i] = (x[i] >> S) | (x[i + 1] << (WordInfo<W>::bits - S));
913 }
914 x[N - 1] >>= S;
915
916 return carry;
917}
918
919// Should be consteval but this triggers a bug in Clang 14
920template <WordType W, size_t N>
921constexpr auto hex_to_words(const char (&s)[N]) {
922 // Char count includes null terminator which we ignore
923 const constexpr size_t C = N - 1;
924
925 // Number of nibbles that a word can hold
926 const constexpr size_t NPW = (WordInfo<W>::bits / 4);
927
928 // Round up to the next number of words that will fit the input
929 const constexpr size_t S = (C + NPW - 1) / NPW;
930
931 static_assert(S > 0, "Input too small");
932
933 const auto hex2int = [](char c) -> int8_t {
934 if(c >= '0' && c <= '9') {
935 return static_cast<int8_t>(c - '0');
936 } else if(c >= 'a' && c <= 'f') {
937 return static_cast<int8_t>(c - 'a' + 10);
938 } else if(c >= 'A' && c <= 'F') {
939 return static_cast<int8_t>(c - 'A' + 10);
940 } else {
941 return -1;
942 }
943 };
944
945 std::array<W, S> r = {0};
946
947 for(size_t i = 0; i != C; ++i) {
948 const int8_t c = hex2int(s[i]);
949 if(c >= 0) {
950 shift_left<4>(r);
951 r[0] += c;
952 }
953 }
954
955 return r;
956}
957
958/*
959* Comba Multiplication / Squaring
960*/
961BOTAN_FUZZER_API void bigint_comba_mul4(word z[8], const word x[4], const word y[4]);
962BOTAN_FUZZER_API void bigint_comba_mul6(word z[12], const word x[6], const word y[6]);
963BOTAN_FUZZER_API void bigint_comba_mul7(word z[14], const word x[7], const word y[7]);
964BOTAN_FUZZER_API void bigint_comba_mul8(word z[16], const word x[8], const word y[8]);
965BOTAN_FUZZER_API void bigint_comba_mul9(word z[18], const word x[9], const word y[9]);
966BOTAN_FUZZER_API void bigint_comba_mul16(word z[32], const word x[16], const word y[16]);
967BOTAN_FUZZER_API void bigint_comba_mul24(word z[48], const word x[24], const word y[24]);
968
969BOTAN_FUZZER_API void bigint_comba_sqr4(word out[8], const word in[4]);
970BOTAN_FUZZER_API void bigint_comba_sqr6(word out[12], const word in[6]);
971BOTAN_FUZZER_API void bigint_comba_sqr7(word out[14], const word x[7]);
972BOTAN_FUZZER_API void bigint_comba_sqr8(word out[16], const word in[8]);
973BOTAN_FUZZER_API void bigint_comba_sqr9(word out[18], const word in[9]);
974BOTAN_FUZZER_API void bigint_comba_sqr16(word out[32], const word in[16]);
975BOTAN_FUZZER_API void bigint_comba_sqr24(word out[48], const word in[24]);
976
977/*
978* Comba Fixed Length Multiplication
979*/
980template <size_t N, WordType W>
981constexpr inline void comba_mul(W z[2 * N], const W x[N], const W y[N]) {
982 if(!std::is_constant_evaluated()) {
983 if constexpr(std::same_as<W, word> && N == 4) {
984 return bigint_comba_mul4(z, x, y);
985 }
986 if constexpr(std::same_as<W, word> && N == 6) {
987 return bigint_comba_mul6(z, x, y);
988 }
989 if constexpr(std::same_as<W, word> && N == 7) {
990 return bigint_comba_mul7(z, x, y);
991 }
992 if constexpr(std::same_as<W, word> && N == 8) {
993 return bigint_comba_mul8(z, x, y);
994 }
995 if constexpr(std::same_as<W, word> && N == 9) {
996 return bigint_comba_mul9(z, x, y);
997 }
998 if constexpr(std::same_as<W, word> && N == 16) {
999 return bigint_comba_mul16(z, x, y);
1000 }
1001 }
1002
1003 word3<W> accum;
1004
1005 for(size_t i = 0; i != 2 * N; ++i) {
1006 const size_t start = i + 1 < N ? 0 : i + 1 - N;
1007 const size_t end = std::min(N, i + 1);
1008
1009 for(size_t j = start; j != end; ++j) {
1010 accum.mul(x[j], y[i - j]);
1011 }
1012 z[i] = accum.extract();
1013 }
1014}
1015
1016template <size_t N, WordType W>
1017constexpr inline void comba_sqr(W z[2 * N], const W x[N]) {
1018 if(!std::is_constant_evaluated()) {
1019 if constexpr(std::same_as<W, word> && N == 4) {
1020 return bigint_comba_sqr4(z, x);
1021 }
1022 if constexpr(std::same_as<W, word> && N == 6) {
1023 return bigint_comba_sqr6(z, x);
1024 }
1025 if constexpr(std::same_as<W, word> && N == 7) {
1026 return bigint_comba_sqr7(z, x);
1027 }
1028 if constexpr(std::same_as<W, word> && N == 8) {
1029 return bigint_comba_sqr8(z, x);
1030 }
1031 if constexpr(std::same_as<W, word> && N == 9) {
1032 return bigint_comba_sqr9(z, x);
1033 }
1034 if constexpr(std::same_as<W, word> && N == 16) {
1035 return bigint_comba_sqr16(z, x);
1036 }
1037 }
1038
1039 word3<W> accum;
1040
1041 for(size_t i = 0; i != 2 * N; ++i) {
1042 const size_t start = i + 1 < N ? 0 : i + 1 - N;
1043 const size_t end = std::min(N, i + 1);
1044
1045 for(size_t j = start; j != end; ++j) {
1046 accum.mul(x[j], x[i - j]);
1047 }
1048 z[i] = accum.extract();
1049 }
1050}
1051
1052/*
1053* Montgomery reduction
1054*
1055* Sets r to the Montgomery reduction of z using parameters p / p_dash
1056*
1057* The workspace should be of size equal to the prime
1058*/
1059BOTAN_FUZZER_API void bigint_monty_redc_4(word r[4], const word z[8], const word p[4], word p_dash, word ws[4]);
1060BOTAN_FUZZER_API void bigint_monty_redc_6(word r[6], const word z[12], const word p[6], word p_dash, word ws[6]);
1061BOTAN_FUZZER_API void bigint_monty_redc_8(word r[8], const word z[16], const word p[8], word p_dash, word ws[8]);
1062BOTAN_FUZZER_API void bigint_monty_redc_12(word r[12], const word z[24], const word p[12], word p_dash, word ws[12]);
1063BOTAN_FUZZER_API void bigint_monty_redc_16(word r[16], const word z[32], const word p[16], word p_dash, word ws[16]);
1064BOTAN_FUZZER_API void bigint_monty_redc_24(word r[24], const word z[48], const word p[24], word p_dash, word ws[24]);
1065BOTAN_FUZZER_API void bigint_monty_redc_32(word r[32], const word z[64], const word p[32], word p_dash, word ws[32]);
1066
1069 word r[], const word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[]);
1070
1071/**
1072* Montgomery Reduction
1073* @param r result of exactly p_size words
1074* @param z integer to reduce, of size exactly 2*p_size.
1075* @param p modulus
1076* @param p_size size of p
1077* @param p_dash Montgomery value
1078* @param ws array of at least p_size words
1079* @param ws_size size of ws in words
1080*
1081* It is allowed to set &r[0] == &z[0] however in this case note that only the
1082* first p_size words of r will be written to and the high p_size words of r/z
1083* will still hold the original inputs, these must be cleared after use.
1084* See bigint_monty_redc_inplace
1085*/
1087 word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size) {
1088 const size_t z_size = 2 * p_size;
1089
1090 BOTAN_ARG_CHECK(ws_size >= p_size, "Montgomery reduction workspace too small");
1091
1092 if(p_size == 4) {
1093 bigint_monty_redc_4(r, z, p, p_dash, ws);
1094 } else if(p_size == 6) {
1095 bigint_monty_redc_6(r, z, p, p_dash, ws);
1096 } else if(p_size == 8) {
1097 bigint_monty_redc_8(r, z, p, p_dash, ws);
1098 } else if(p_size == 12) {
1099 bigint_monty_redc_12(r, z, p, p_dash, ws);
1100 } else if(p_size == 16) {
1101 bigint_monty_redc_16(r, z, p, p_dash, ws);
1102 } else if(p_size == 24) {
1103 bigint_monty_redc_24(r, z, p, p_dash, ws);
1104 } else if(p_size == 32) {
1105 bigint_monty_redc_32(r, z, p, p_dash, ws);
1106 } else {
1107 bigint_monty_redc_generic(r, z, z_size, p, p_size, p_dash, ws);
1108 }
1109}
1110
1111inline void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size) {
1112 bigint_monty_redc(z, z, p, p_size, p_dash, ws, ws_size);
1113 zeroize_buffer(z + p_size, p_size);
1114}
1115
1116/**
1117* Montgomery multiplication
1118*
1119* Computes z[0..p_size) = x*y/R mod p, where R = 2^(p_size * word bits),
1120* and x and y are each p_size words and less than p. z may alias x or y.
1121*
1122* ws must be at least 4*p_size words
1123*/
1125 word z[], const word x[], const word y[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size);
1126
1127/**
1128* Montgomery squaring
1129*
1130* Computes z[0..p_size) = x*x/R mod p, where R = 2^(p_size * word bits),
1131* and x is p_size words and less than p. z may alias x.
1132*
1133* ws must be at least 4*p_size words
1134*/
1136 word z[], const word x[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size);
1137
1138/**
1139* Basecase O(N^2) multiplication
1140*/
1142void basecase_mul(word z[], size_t z_size, const word x[], size_t x_size, const word y[], size_t y_size);
1143
1144/**
1145* Basecase O(N^2) squaring
1146*/
1148void basecase_sqr(word z[], size_t z_size, const word x[], size_t x_size);
1149
1150/*
1151* High Level Multiplication/Squaring Interfaces
1152*/
1153void bigint_mul(word z[],
1154 size_t z_size,
1155 const word x[],
1156 size_t x_size,
1157 size_t x_sw,
1158 const word y[],
1159 size_t y_size,
1160 size_t y_sw,
1161 word workspace[],
1162 size_t ws_size);
1163
1164void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size);
1165
1166/**
1167* Reduce z modulo p = 2**B - C where C is small
1168*
1169* z is assumed to be at most (p-1)**2
1170*
1171* For details on the algorithm see
1172* - Handbook of Applied Cryptography, Algorithm 14.47
1173* - Guide to Elliptic Curve Cryptography, Algorithm 2.54 and Note 2.55
1174*
1175*/
1176template <WordType W, size_t N, W C>
1177constexpr std::array<W, N> redc_crandall(std::span<const W, 2 * N> z) {
1178 static_assert(N >= 2);
1179
1180 std::array<W, N> hi = {};
1181
1182 // hi = hi * c + lo
1183
1184 W carry = 0;
1185 for(size_t i = 0; i != N; ++i) {
1186 hi[i] = word_madd3(z[i + N], C, z[i], &carry);
1187 }
1188
1189 // hi += carry * C
1190 W carry_c[2] = {0};
1191 carry_c[0] = word_madd2(carry, C, &carry_c[1]);
1192
1193 carry = bigint_add2(hi.data(), N, carry_c, 2);
1194
1195 constexpr W P0 = WordInfo<W>::max - (C - 1);
1196
1197 std::array<W, N> r = {};
1198
1199 W borrow = 0;
1200
1201 /*
1202 * For undetermined reasons, on GCC (only) removing this asm block causes
1203 * massive (up to 20%) performance regressions in secp256k1.
1204 *
1205 * The generated code without the asm seems quite reasonable, and timing
1206 * repeated calls to redc_crandall with the cycle counter show that GCC
1207 * computes it in about the same number of cycles with or without the asm.
1208 *
1209 * So the cause of the regression is unclear. But it is reproducible across
1210 * machines and GCC versions.
1211 */
1212#if defined(BOTAN_MP_USE_X86_64_ASM) && defined(__GNUC__) && !defined(__clang__)
1213 if constexpr(N == 4 && std::same_as<W, uint64_t>) {
1214 if(!std::is_constant_evaluated()) {
1215 asm volatile(R"(
1216 movq 0(%[x]), %[borrow]
1217 subq %[p0], %[borrow]
1218 movq %[borrow], 0(%[r])
1219 movq 8(%[x]), %[borrow]
1220 sbbq $-1, %[borrow]
1221 movq %[borrow], 8(%[r])
1222 movq 16(%[x]), %[borrow]
1223 sbbq $-1, %[borrow]
1224 movq %[borrow], 16(%[r])
1225 movq 24(%[x]), %[borrow]
1226 sbbq $-1, %[borrow]
1227 movq %[borrow], 24(%[r])
1228 sbbq %[borrow],%[borrow]
1229 negq %[borrow]
1230 )"
1231 : [borrow] "=r"(borrow)
1232 : [x] "r"(hi.data()), [p0] "r"(P0), [r] "r"(r.data()), "0"(borrow)
1233 : "cc", "memory");
1234
1235 borrow = (carry - borrow) > carry;
1236 CT::conditional_assign_mem(borrow, r.data(), hi.data(), N);
1237 return r;
1238 }
1239 }
1240#endif
1241
1242 r[0] = word_sub(hi[0], P0, &borrow);
1243 for(size_t i = 1; i != N; ++i) {
1244 r[i] = word_sub(hi[i], WordInfo<W>::max, &borrow);
1245 }
1246
1247 borrow = (carry - borrow) > carry;
1248
1249 CT::conditional_assign_mem(borrow, r.data(), hi.data(), N);
1250
1251 return r;
1252}
1253
1254template <WordType W, size_t N, size_t L>
1255inline constexpr auto bytes_to_words(std::span<const uint8_t, L> bytes) {
1256 static_assert(L <= WordInfo<W>::bytes * N);
1257
1258 std::array<W, N> r = {};
1259
1260 constexpr size_t full_words = L / WordInfo<W>::bytes;
1261 constexpr size_t extra_bytes = L % WordInfo<W>::bytes;
1262
1263 static_assert(full_words + (extra_bytes ? 1 : 0) <= N);
1264
1265 for(size_t i = 0; i != full_words; ++i) {
1266 r[i] = load_be<W>(bytes.data(), full_words - 1 - i);
1267 }
1268
1269 if constexpr(extra_bytes > 0) {
1270 constexpr size_t shift = extra_bytes * 8;
1272
1273 for(size_t i = 0; i != extra_bytes; ++i) {
1274 const W b0 = bytes[WordInfo<W>::bytes * full_words + i];
1275 r[0] |= (b0 << (8 * (extra_bytes - 1 - i)));
1276 }
1277 }
1278
1279 return r;
1280}
1281
1282// Extract a WindowBits sized window out of s, depending on offset.
1283template <size_t WindowBits, typename W, size_t N>
1284constexpr size_t read_window_bits(std::span<const W, N> words, size_t offset) {
1285 static_assert(WindowBits >= 1 && WindowBits <= 7);
1286
1287 constexpr uint8_t WindowMask = static_cast<uint8_t>(1 << WindowBits) - 1;
1288
1289 constexpr size_t W_bits = sizeof(W) * 8;
1290 const auto bit_shift = offset % W_bits;
1291 const auto word_offset = words.size() - 1 - (offset / W_bits);
1292
1293 const bool single_byte_window = bit_shift <= (W_bits - WindowBits) || word_offset == 0;
1294
1295 const auto w0 = words[word_offset];
1296
1297 if(single_byte_window) {
1298 return (w0 >> bit_shift) & WindowMask;
1299 } else {
1300 // Otherwise we must join two words and extract the result
1301 const auto w1 = words[word_offset - 1];
1302 const auto combined = ((w0 >> bit_shift) | (w1 << (W_bits - bit_shift)));
1303 return combined & WindowMask;
1304 }
1305}
1306
1307/**
1308* Booth signed digit recoding of a (window_bits + 1) bit window value,
1309* in constant time. Returns the digit, in [0, 2^(window_bits-1)], and a
1310* Choice which is set if the digit is to be negated.
1311*/
1312inline constexpr std::pair<size_t, CT::Choice> booth_recode(size_t x, size_t window_bits) {
1313 const auto sign = CT::Mask<size_t>::expand(x >> window_bits);
1314 const size_t neg_x = (static_cast<size_t>(1) << (window_bits + 1)) - x - 1;
1315 size_t digit = sign.select(neg_x, x);
1316 digit = (digit >> 1) + (digit & 1);
1317 return {digit, sign.as_choice()};
1318}
1319
1320template <size_t WindowBits, std::unsigned_integral T>
1321constexpr std::pair<size_t, CT::Choice> booth_recode(T x) {
1322 static_assert(WindowBits >= 1 && WindowBits <= 16);
1323 return booth_recode(static_cast<size_t>(x), WindowBits);
1324}
1325
1326} // namespace Botan
1327
1328#endif
#define BOTAN_FUZZER_API
Definition api.h:65
#define BOTAN_TEST_API
Definition api.h:41
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
static constexpr Mask< T > is_gte(T x, T y)
Definition ct_utils.h:473
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
static constexpr Mask< T > expand_top_bit(T v)
Definition ct_utils.h:420
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
static constexpr Mask< T > is_gt(T x, T y)
Definition ct_utils.h:463
static constexpr Mask< T > is_lt(T x, T y)
Definition ct_utils.h:455
static constexpr Mask< T > is_zero(T x)
Definition ct_utils.h:442
constexpr W div_2to1(W n1, W n0) const
Definition mp_core.h:770
constexpr W mod_2to1(W n1, W n0) const
Definition mp_core.h:777
static constexpr divide_precomp setup_vartime(W divisor)
Definition mp_core.h:687
static constexpr divide_precomp setup(W divisor)
Definition mp_core.h:695
static constexpr divide_precomp setup_with_reciprocal(W divisor, W reciprocal)
Definition mp_core.h:703
constexpr std::pair< W, W > divmod_2to1_vartime(W n1, W n0) const
Definition mp_core.h:719
constexpr W reciprocal() const
Definition mp_core.h:709
constexpr std::pair< W, W > divmod_2to1_ct(W n1, W n0) const
Definition mp_core.h:741
constexpr W extract()
Definition mp_asmi.h:665
constexpr void mul(W x, W y)
Definition mp_asmi.h:542
constexpr decltype(auto) driveby_unpoison(T &&v)
Definition ct_utils.h:243
constexpr Mask< T > conditional_copy_mem(Mask< T > mask, T *dest, const T *if_set, const T *if_unset, size_t elems)
Definition ct_utils.h:737
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr Mask< T > conditional_assign_mem(T cnd, T *dest, const T *src, size_t elems)
Definition ct_utils.h:754
constexpr void bigint_cnd_abs(W cnd, W x[], size_t size)
Definition mp_core.h:84
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:98
constexpr void bigint_linmul3(W z[], const W x[], size_t x_size, W y)
Definition mp_core.h:420
constexpr auto bigint_cnd_sub(W cnd, W x[], const W y[], size_t size) -> W
Definition mp_core.h:66
BOTAN_TEST_API void bigint_monty_mul(word z[], const word x[], const word y[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_monty.cpp:143
constexpr W reciprocal_word(W D)
Definition mp_core.h:578
constexpr auto bigint_add3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:124
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
Definition mp_core.h:33
constexpr auto word8_sub3(W z[8], const W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:409
constexpr auto bytes_to_words(std::span< const uint8_t, L > bytes)
Definition mp_core.h:1255
constexpr W shift_left(std::array< W, N > &x)
Definition mp_core.h:888
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:355
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260
constexpr auto bigint_submul(W z[], const W y[], size_t N, W q) -> W
Definition mp_core.h:443
constexpr void comba_sqr(W z[2 *N], const W x[N])
Definition mp_core.h:1017
constexpr uint64_t carry_shift(const donna128 &a, size_t shift)
Definition donna128.h:129
BOTAN_FUZZER_API void basecase_sqr(word z[], size_t z_size, const word x[], size_t x_size)
Definition mp_karat.cpp:46
constexpr size_t read_window_bits(std::span< const W, N > words, size_t offset)
Definition mp_core.h:1284
void bigint_comba_sqr4(word z[8], const word x[4])
Definition mp_comba.cpp:22
void bigint_comba_sqr6(word z[12], const word x[6])
Definition mp_comba.cpp:92
constexpr void bigint_shr1(W x[], size_t x_size, size_t shift)
Definition mp_core.h:335
constexpr auto word8_add3(W z[8], const W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:326
constexpr std::pair< size_t, CT::Choice > booth_recode(size_t x, size_t window_bits)
Definition mp_core.h:1312
BOTAN_FUZZER_API void bigint_monty_redc_6(word r[6], const word z[12], const word p[6], word p_dash, word ws[6])
constexpr void comba_mul(W z[2 *N], const W x[N], const W y[N])
Definition mp_core.h:981
constexpr auto word8_sub2(W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:380
void bigint_comba_sqr7(word z[14], const word x[7])
Definition mp_comba.cpp:201
void bigint_comba_mul4(word z[8], const word x[4], const word y[4])
Definition mp_comba.cpp:54
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:111
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:327
void bigint_comba_mul16(word z[32], const word x[16], const word y[16])
Definition mp_comba.cpp:848
BOTAN_FUZZER_API void bigint_monty_redc_24(word r[24], const word z[48], const word p[24], word p_dash, word ws[24])
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:196
constexpr auto monty_inverse(W a) -> W
Definition mp_core.h:866
BOTAN_FUZZER_API void bigint_monty_redc_generic(word r[], const word z[], size_t z_size, const word p[], size_t p_size, word p_dash, word ws[])
Definition mp_monty.cpp:94
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:283
void zeroize_buffer(T buf[], size_t n)
Definition mem_utils.h:37
void bigint_comba_mul6(word z[12], const word x[6], const word y[6])
Definition mp_comba.cpp:139
constexpr W reciprocal_word_ct(W D)
Definition mp_core.h:650
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
Definition mp_core.h:313
uint32_t P0(uint32_t X)
Definition sm3_fn.h:17
constexpr auto bigint_ct_is_eq(const W x[], size_t x_size, const W y[], size_t y_size) -> CT::Mask< W >
Definition mp_core.h:543
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
Definition mp_core.h:463
BOTAN_FUZZER_API void bigint_monty_redc_4(word r[4], const word z[8], const word p[4], word p_dash, word ws[4])
void bigint_monty_redc_inplace(word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:1111
void bigint_monty_redc(word r[], const word z[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_core.h:1086
void bigint_comba_mul7(word z[14], const word x[7], const word y[7])
Definition mp_comba.cpp:251
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:49
void unchecked_copy_memory(T *out, const T *in, size_t n)
Definition mem_utils.h:44
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229
void bigint_comba_mul9(word z[18], const word x[9], const word y[9])
Definition mp_comba.cpp:559
BOTAN_FUZZER_API void bigint_monty_redc_12(word r[12], const word z[24], const word p[12], word p_dash, word ws[12])
BOTAN_TEST_API void bigint_monty_sqr(word z[], const word x[], const word p[], size_t p_size, word p_dash, word ws[], size_t ws_size)
Definition mp_monty.cpp:159
BOTAN_FUZZER_API void bigint_monty_redc_16(word r[16], const word z[32], const word p[16], word p_dash, word ws[16])
constexpr void bigint_shr2(W y[], size_t y_size, const W x[], size_t x_size, size_t shift)
Definition mp_core.h:382
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Definition bit_ops.h:73
void bigint_comba_mul24(word z[48], const word x[24], const word y[24])
constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask< W >
Definition mp_core.h:283
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
Definition mp_core.h:510
constexpr std::array< W, N > redc_crandall(std::span< const W, 2 *N > z)
Definition mp_core.h:1177
constexpr auto word8_add2(W x[8], const W y[8], W carry) -> W
Definition mp_asmi.h:297
constexpr auto bigint_sub2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:152
void bigint_comba_sqr8(word z[16], const word x[8])
Definition mp_comba.cpp:322
constexpr auto hex_to_words(const char(&s)[N])
Definition mp_core.h:921
void bigint_comba_sqr16(word z[32], const word x[16])
Definition mp_comba.cpp:672
constexpr void bigint_shl2(W y[], size_t y_size, const W x[], size_t x_size, size_t shift)
Definition mp_core.h:359
constexpr void bigint_sub2_rev(W x[], const W y[], size_t y_size)
Definition mp_core.h:178
void bigint_comba_sqr9(word z[18], const word x[9])
Definition mp_comba.cpp:482
constexpr auto word8_linmul3(W z[8], const W x[8], W y, W carry) -> W
Definition mp_asmi.h:438
BOTAN_FUZZER_API void basecase_mul(word z[], size_t z_size, const word x[], size_t x_size, const word y[], size_t y_size)
Definition mp_karat.cpp:20
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131
void bigint_comba_sqr24(word z[48], const word x[24])
void bigint_comba_mul8(word z[16], const word x[8], const word y[8])
Definition mp_comba.cpp:388
BOTAN_FUZZER_API void bigint_monty_redc_8(word r[8], const word z[16], const word p[8], word p_dash, word ws[8])
constexpr auto load_be(ParamTs &&... params)
Definition loadstor.h:504
constexpr W shift_right(std::array< W, N > &x)
Definition mp_core.h:904
BOTAN_FUZZER_API void bigint_monty_redc_32(word r[32], const word z[64], const word p[32], word p_dash, word ws[32])
constexpr auto word_madd3(W a, W b, W c, W *d) -> W
Definition mp_asmi.h:158
constexpr auto bigint_linmul2(W x[], size_t x_size, W y) -> W
Definition mp_core.h:409