From e8d08eba98dea0504426cf9d37e3fcb26babb18b Mon Sep 17 00:00:00 2001 From: jsing Date: Fri, 20 Jan 2023 10:00:51 +0000 Subject: [PATCH] Reorder functions. No functional change. --- lib/libcrypto/bn/bn_mul.c | 692 +++++++++++++++++++------------------- 1 file changed, 346 insertions(+), 346 deletions(-) diff --git a/lib/libcrypto/bn/bn_mul.c b/lib/libcrypto/bn/bn_mul.c index f6e6e9bf654..5437e7e883d 100644 --- a/lib/libcrypto/bn/bn_mul.c +++ b/lib/libcrypto/bn/bn_mul.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_mul.c,v 1.25 2023/01/16 16:53:19 jsing Exp $ */ +/* $OpenBSD: bn_mul.c,v 1.26 2023/01/20 10:00:51 jsing Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -64,7 +64,6 @@ #include "bn_local.h" -#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) /* Here follows specialised variants of bn_add_words() and bn_sub_words(). They have the property performing operations on arrays of different sizes. The sizes of those arrays is expressed through @@ -76,13 +75,13 @@ assembler counterparts for the systems that use assembler files. */ BN_ULONG -bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, +bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) { - BN_ULONG c, t; + BN_ULONG c, l, t; assert(cl >= 0); - c = bn_sub_words(r, a, b, cl); + c = bn_add_words(r, a, b, cl); if (dl == 0) return c; @@ -92,66 +91,99 @@ bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, b += cl; if (dl < 0) { - for (;;) { - t = b[0]; - r[0] = (0 - t - c) & BN_MASK2; - if (t != 0) - c = 1; + int save_dl = dl; + while (c) { + l = (c + b[0]) & BN_MASK2; + c = (l < c); + r[0] = l; if (++dl >= 0) break; - t = b[1]; - r[1] = (0 - t - c) & BN_MASK2; - if (t != 0) - c = 1; + l = (c + b[1]) & BN_MASK2; + c = (l < c); + r[1] = l; if (++dl >= 0) break; - t = b[2]; - r[2] = (0 - t - c) & BN_MASK2; - if (t != 0) - c = 1; + l = (c + b[2]) & BN_MASK2; + c = (l < c); + r[2] = l; if (++dl >= 0) break; - t = b[3]; - r[3] = (0 - t - c) & BN_MASK2; - if (t != 0) - c = 1; + l = (c + b[3]) & BN_MASK2; + c = (l < c); + r[3] = l; if (++dl >= 0) break; + save_dl = dl; b += 4; r += 4; } + if (dl < 0) { + if (save_dl < dl) { + switch (dl - save_dl) { + case 1: + r[1] = b[1]; + if (++dl >= 0) + break; + case 2: + r[2] = b[2]; + if (++dl >= 0) + break; + case 3: + r[3] = b[3]; + if (++dl >= 0) + break; + } + b += 4; + r += 4; + } + } + if (dl < 0) { + for (;;) { + r[0] = b[0]; + if (++dl >= 0) + break; + r[1] = b[1]; + if (++dl >= 0) + break; + r[2] = b[2]; + if (++dl >= 0) + break; + r[3] = b[3]; + if (++dl >= 0) + break; + + b += 4; + r += 4; + } + } } else { int save_dl = dl; while (c) { - t = a[0]; - r[0] = (t - c) & BN_MASK2; - if (t != 0) - c = 0; + t = (a[0] + c) & BN_MASK2; + c = (t < c); + r[0] = t; if (--dl <= 0) break; - t = a[1]; - r[1] = (t - c) & BN_MASK2; - if (t != 0) - c = 0; + t = (a[1] + c) & BN_MASK2; + c = (t < c); + r[1] = t; if (--dl <= 0) break; - t = a[2]; - r[2] = (t - c) & BN_MASK2; - if (t != 0) - c = 0; + t = (a[2] + c) & BN_MASK2; + c = (t < c); + r[2] = t; if (--dl <= 0) break; - t = a[3]; - r[3] = (t - c) & BN_MASK2; - if (t != 0) - c = 0; + t = (a[3] + c) & BN_MASK2; + c = (t < c); + r[3] = t; if (--dl <= 0) break; @@ -201,16 +233,16 @@ bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, } return c; } -#endif +#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) BN_ULONG -bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, +bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) { - BN_ULONG c, l, t; + BN_ULONG c, t; assert(cl >= 0); - c = bn_add_words(r, a, b, cl); + c = bn_sub_words(r, a, b, cl); if (dl == 0) return c; @@ -220,99 +252,66 @@ bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, b += cl; if (dl < 0) { - int save_dl = dl; - while (c) { - l = (c + b[0]) & BN_MASK2; - c = (l < c); - r[0] = l; + for (;;) { + t = b[0]; + r[0] = (0 - t - c) & BN_MASK2; + if (t != 0) + c = 1; if (++dl >= 0) break; - l = (c + b[1]) & BN_MASK2; - c = (l < c); - r[1] = l; + t = b[1]; + r[1] = (0 - t - c) & BN_MASK2; + if (t != 0) + c = 1; if (++dl >= 0) break; - l = (c + b[2]) & BN_MASK2; - c = (l < c); - r[2] = l; + t = b[2]; + r[2] = (0 - t - c) & BN_MASK2; + if (t != 0) + c = 1; if (++dl >= 0) break; - l = (c + b[3]) & BN_MASK2; - c = (l < c); - r[3] = l; + t = b[3]; + r[3] = (0 - t - c) & BN_MASK2; + if (t != 0) + c = 1; if (++dl >= 0) break; - save_dl = dl; b += 4; r += 4; } - if (dl < 0) { - if (save_dl < dl) { - switch (dl - save_dl) { - case 1: - r[1] = b[1]; - if (++dl >= 0) - break; - case 2: - r[2] = b[2]; - if (++dl >= 0) - break; - case 3: - r[3] = b[3]; - if (++dl >= 0) - break; - } - b += 4; - r += 4; - } - } - if (dl < 0) { - for (;;) { - r[0] = b[0]; - if (++dl >= 0) - break; - r[1] = b[1]; - if (++dl >= 0) - break; - r[2] = b[2]; - if (++dl >= 0) - break; - r[3] = b[3]; - if (++dl >= 0) - break; - - b += 4; - r += 4; - } - } } else { int save_dl = dl; while (c) { - t = (a[0] + c) & BN_MASK2; - c = (t < c); - r[0] = t; + t = a[0]; + r[0] = (t - c) & BN_MASK2; + if (t != 0) + c = 0; if (--dl <= 0) break; - t = (a[1] + c) & BN_MASK2; - c = (t < c); - r[1] = t; + t = a[1]; + r[1] = (t - c) & BN_MASK2; + if (t != 0) + c = 0; if (--dl <= 0) break; - t = (a[2] + c) & BN_MASK2; - c = (t < c); - r[2] = t; + t = a[2]; + r[2] = (t - c) & BN_MASK2; + if (t != 0) + c = 0; if (--dl <= 0) break; - t = (a[3] + c) & BN_MASK2; - c = (t < c); - r[3] = t; + t = a[3]; + r[3] = (t - c) & BN_MASK2; + if (t != 0) + c = 0; if (--dl <= 0) break; @@ -360,10 +359,247 @@ bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, } } } - return c; + return c; +} +#endif + +void +bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) +{ + BN_ULONG *rr; + + + if (na < nb) { + int itmp; + BN_ULONG *ltmp; + + itmp = na; + na = nb; + nb = itmp; + ltmp = a; + a = b; + b = ltmp; + + } + rr = &(r[na]); + if (nb <= 0) { + (void)bn_mul_words(r, a, na, 0); + return; + } else + rr[0] = bn_mul_words(r, a, na, b[0]); + + for (;;) { + if (--nb <= 0) + return; + rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); + if (--nb <= 0) + return; + rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); + if (--nb <= 0) + return; + rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); + if (--nb <= 0) + return; + rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); + rr += 4; + r += 4; + b += 4; + } +} + +void +bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) +{ + bn_mul_words(r, a, n, b[0]); + + for (;;) { + if (--n <= 0) + return; + bn_mul_add_words(&(r[1]), a, n, b[1]); + if (--n <= 0) + return; + bn_mul_add_words(&(r[2]), a, n, b[2]); + if (--n <= 0) + return; + bn_mul_add_words(&(r[3]), a, n, b[3]); + if (--n <= 0) + return; + bn_mul_add_words(&(r[4]), a, n, b[4]); + r += 4; + b += 4; + } +} + +#ifdef BN_RECURSION +/* a and b must be the same size, which is n2. + * r needs to be n2 words and t needs to be n2*2 + * l is the low words of the output. + * t needs to be n2*3 + */ +void +bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, + BN_ULONG *t) +{ + int i, n; + int c1, c2; + int neg, oneg, zero; + BN_ULONG ll, lc, *lp, *mp; + + n = n2 / 2; + + /* Calculate (al-ah)*(bh-bl) */ + neg = zero = 0; + c1 = bn_cmp_words(&(a[0]), &(a[n]), n); + c2 = bn_cmp_words(&(b[n]), &(b[0]), n); + switch (c1 * 3 + c2) { + case -4: + bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); + bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); + break; + case -3: + zero = 1; + break; + case -2: + bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); + bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); + neg = 1; + break; + case -1: + case 0: + case 1: + zero = 1; + break; + case 2: + bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); + bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); + neg = 1; + break; + case 3: + zero = 1; + break; + case 4: + bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); + bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); + break; + } + + oneg = neg; + /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ + /* r[10] = (a[1]*b[1]) */ +# ifdef BN_MUL_COMBA + if (n == 8) { + bn_mul_comba8(&(t[0]), &(r[0]), &(r[n])); + bn_mul_comba8(r, &(a[n]), &(b[n])); + } else +# endif + { + bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2])); + bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2])); + } + + /* s0 == low(al*bl) + * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) + * We know s0 and s1 so the only unknown is high(al*bl) + * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) + * high(al*bl) == s1 - (r[0]+l[0]+t[0]) + */ + if (l != NULL) { + lp = &(t[n2 + n]); + c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n)); + } else { + c1 = 0; + lp = &(r[0]); + } + + if (neg) + neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n)); + else { + bn_add_words(&(t[n2]), lp, &(t[0]), n); + neg = 0; + } + + if (l != NULL) { + bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n); + } else { + lp = &(t[n2 + n]); + mp = &(t[n2]); + for (i = 0; i < n; i++) + lp[i] = ((~mp[i]) + 1) & BN_MASK2; + } + + /* s[0] = low(al*bl) + * t[3] = high(al*bl) + * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign + * r[10] = (a[1]*b[1]) + */ + /* R[10] = al*bl + * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) + * R[32] = ah*bh + */ + /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) + * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) + * R[3]=r[1]+(carry/borrow) + */ + if (l != NULL) { + lp = &(t[n2]); + c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n)); + } else { + lp = &(t[n2 + n]); + c1 = 0; + } + c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n)); + if (oneg) + c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n)); + else + c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n)); + + c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n)); + c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n)); + if (oneg) + c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n)); + else + c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n)); + + if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */ + { + i = 0; + if (c1 > 0) { + lc = c1; + do { + ll = (r[i] + lc) & BN_MASK2; + r[i++] = ll; + lc = (lc > ll); + } while (lc); + } else { + lc = -c1; + do { + ll = r[i]; + r[i++] = (ll - lc) & BN_MASK2; + lc = (lc > ll); + } while (lc); + } + } + if (c2 != 0) /* Add starting at r[1] */ + { + i = n; + if (c2 > 0) { + lc = c2; + do { + ll = (r[i] + lc) & BN_MASK2; + r[i++] = ll; + lc = (lc > ll); + } while (lc); + } else { + lc = -c2; + do { + ll = r[i]; + r[i++] = (ll - lc) & BN_MASK2; + lc = (lc > ll); + } while (lc); + } + } } -#ifdef BN_RECURSION /* Karatsuba recursive multiplication algorithm * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ @@ -699,175 +935,6 @@ bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *t) bn_add_words(&(r[n]), &(r[n]), &(t[n]), n); } } - -/* a and b must be the same size, which is n2. - * r needs to be n2 words and t needs to be n2*2 - * l is the low words of the output. - * t needs to be n2*3 - */ -void -bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, - BN_ULONG *t) -{ - int i, n; - int c1, c2; - int neg, oneg, zero; - BN_ULONG ll, lc, *lp, *mp; - - n = n2 / 2; - - /* Calculate (al-ah)*(bh-bl) */ - neg = zero = 0; - c1 = bn_cmp_words(&(a[0]), &(a[n]), n); - c2 = bn_cmp_words(&(b[n]), &(b[0]), n); - switch (c1 * 3 + c2) { - case -4: - bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); - bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); - break; - case -3: - zero = 1; - break; - case -2: - bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n); - bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); - neg = 1; - break; - case -1: - case 0: - case 1: - zero = 1; - break; - case 2: - bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); - bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n); - neg = 1; - break; - case 3: - zero = 1; - break; - case 4: - bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n); - bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n); - break; - } - - oneg = neg; - /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ - /* r[10] = (a[1]*b[1]) */ -# ifdef BN_MUL_COMBA - if (n == 8) { - bn_mul_comba8(&(t[0]), &(r[0]), &(r[n])); - bn_mul_comba8(r, &(a[n]), &(b[n])); - } else -# endif - { - bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, 0, 0, &(t[n2])); - bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2])); - } - - /* s0 == low(al*bl) - * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) - * We know s0 and s1 so the only unknown is high(al*bl) - * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) - * high(al*bl) == s1 - (r[0]+l[0]+t[0]) - */ - if (l != NULL) { - lp = &(t[n2 + n]); - c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n)); - } else { - c1 = 0; - lp = &(r[0]); - } - - if (neg) - neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n)); - else { - bn_add_words(&(t[n2]), lp, &(t[0]), n); - neg = 0; - } - - if (l != NULL) { - bn_sub_words(&(t[n2 + n]), &(l[n]), &(t[n2]), n); - } else { - lp = &(t[n2 + n]); - mp = &(t[n2]); - for (i = 0; i < n; i++) - lp[i] = ((~mp[i]) + 1) & BN_MASK2; - } - - /* s[0] = low(al*bl) - * t[3] = high(al*bl) - * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign - * r[10] = (a[1]*b[1]) - */ - /* R[10] = al*bl - * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) - * R[32] = ah*bh - */ - /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) - * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) - * R[3]=r[1]+(carry/borrow) - */ - if (l != NULL) { - lp = &(t[n2]); - c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n)); - } else { - lp = &(t[n2 + n]); - c1 = 0; - } - c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n)); - if (oneg) - c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n)); - else - c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n)); - - c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2 + n]), n)); - c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n)); - if (oneg) - c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n)); - else - c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n)); - - if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */ - { - i = 0; - if (c1 > 0) { - lc = c1; - do { - ll = (r[i] + lc) & BN_MASK2; - r[i++] = ll; - lc = (lc > ll); - } while (lc); - } else { - lc = -c1; - do { - ll = r[i]; - r[i++] = (ll - lc) & BN_MASK2; - lc = (lc > ll); - } while (lc); - } - } - if (c2 != 0) /* Add starting at r[1] */ - { - i = n; - if (c2 > 0) { - lc = c2; - do { - ll = (r[i] + lc) & BN_MASK2; - r[i++] = ll; - lc = (lc > ll); - } while (lc); - } else { - lc = -c2; - do { - ll = r[i]; - r[i++] = (ll - lc) & BN_MASK2; - lc = (lc > ll); - } while (lc); - } - } -} #endif /* BN_RECURSION */ int @@ -1023,70 +1090,3 @@ err: BN_CTX_end(ctx); return (ret); } - -void -bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) -{ - BN_ULONG *rr; - - - if (na < nb) { - int itmp; - BN_ULONG *ltmp; - - itmp = na; - na = nb; - nb = itmp; - ltmp = a; - a = b; - b = ltmp; - - } - rr = &(r[na]); - if (nb <= 0) { - (void)bn_mul_words(r, a, na, 0); - return; - } else - rr[0] = bn_mul_words(r, a, na, b[0]); - - for (;;) { - if (--nb <= 0) - return; - rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); - if (--nb <= 0) - return; - rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); - if (--nb <= 0) - return; - rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); - if (--nb <= 0) - return; - rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); - rr += 4; - r += 4; - b += 4; - } -} - -void -bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) -{ - bn_mul_words(r, a, n, b[0]); - - for (;;) { - if (--n <= 0) - return; - bn_mul_add_words(&(r[1]), a, n, b[1]); - if (--n <= 0) - return; - bn_mul_add_words(&(r[2]), a, n, b[2]); - if (--n <= 0) - return; - bn_mul_add_words(&(r[3]), a, n, b[3]); - if (--n <= 0) - return; - bn_mul_add_words(&(r[4]), a, n, b[4]); - r += 4; - b += 4; - } -} -- 2.20.1