diff options
Diffstat (limited to 'src/crypto/fipsmodule/bn/mul.c')
-rw-r--r-- | src/crypto/fipsmodule/bn/mul.c | 212 |
1 files changed, 104 insertions, 108 deletions
diff --git a/src/crypto/fipsmodule/bn/mul.c b/src/crypto/fipsmodule/bn/mul.c index 36a40601..7cc0e3cd 100644 --- a/src/crypto/fipsmodule/bn/mul.c +++ b/src/crypto/fipsmodule/bn/mul.c @@ -113,15 +113,15 @@ static void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, } #if !defined(OPENSSL_X86) || defined(OPENSSL_NO_ASM) -/* 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 cl, which is the common length ( - * basicall, min(len(a),len(b)) ), and dl, which is the delta between the two - * lengths, calculated as len(a)-len(b). All lengths are the number of - * BN_ULONGs... For the operations that require a result array as parameter, - * it must have the length cl+abs(dl). These functions should probably end up - * in bn_asm.c as soon as there are assembler counterparts for the systems that - * use assembler files. */ +// 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 cl, which is the common length ( +// basicall, min(len(a),len(b)) ), and dl, which is the delta between the two +// lengths, calculated as len(a)-len(b). All lengths are the number of +// BN_ULONGs... For the operations that require a result array as parameter, +// it must have the length cl+abs(dl). These functions should probably end up +// in bn_asm.c as soon as there are assembler counterparts for the systems that +// use assembler files. static BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) { @@ -274,25 +274,24 @@ static BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, return c; } #else -/* On other platforms the function is defined in asm. */ +// On other platforms the function is defined in asm. BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int cl, int dl); #endif -/* Karatsuba recursive multiplication algorithm - * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ - -/* r is 2*n2 words in size, - * a and b are both n2 words in size. - * n2 must be a power of 2. - * We multiply and return the result. - * t must be 2*n2 words in size - * We calculate - * a[0]*b[0] - * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) - * a[1]*b[1] - */ -/* dnX may not be positive, but n2/2+dnX has to be */ +// Karatsuba recursive multiplication algorithm +// (cf. Knuth, The Art of Computer Programming, Vol. 2) + +// r is 2*n2 words in size, +// a and b are both n2 words in size. +// n2 must be a power of 2. +// We multiply and return the result. +// t must be 2*n2 words in size +// We calculate +// a[0]*b[0] +// a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) +// a[1]*b[1] +// dnX may not be positive, but n2/2+dnX has to be static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int dna, int dnb, BN_ULONG *t) { int n = n2 / 2, c1, c2; @@ -300,15 +299,14 @@ static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, unsigned int neg, zero; BN_ULONG ln, lo, *p; - /* Only call bn_mul_comba 8 if n2 == 8 and the - * two arrays are complete [steve] - */ + // Only call bn_mul_comba 8 if n2 == 8 and the + // two arrays are complete [steve] if (n2 == 8 && dna == 0 && dnb == 0) { bn_mul_comba8(r, a, b); return; } - /* Else do normal multiply */ + // Else do normal multiply if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { bn_mul_normal(r, a, n2 + dna, b, n2 + dnb); if ((dna + dnb) < 0) { @@ -318,21 +316,21 @@ static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, return; } - /* r=(a[0]-a[1])*(b[1]-b[0]) */ + // r=(a[0]-a[1])*(b[1]-b[0]) c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); zero = neg = 0; switch (c1 * 3 + c2) { case -4: - bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ - bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ + bn_sub_part_words(t, &(a[n]), a, tna, tna - n); // - + bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); // - break; case -3: zero = 1; break; case -2: - bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ - bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ + bn_sub_part_words(t, &(a[n]), a, tna, tna - n); // - + bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); // + neg = 1; break; case -1: @@ -341,8 +339,8 @@ static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, zero = 1; break; case 2: - bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ - bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ + bn_sub_part_words(t, a, &(a[n]), tna, n - tna); // + + bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); // - neg = 1; break; case 3: @@ -355,7 +353,7 @@ static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, } if (n == 4 && dna == 0 && dnb == 0) { - /* XXX: bn_mul_comba4 could take extra args to do this well */ + // XXX: bn_mul_comba4 could take extra args to do this well if (!zero) { bn_mul_comba4(&(t[n2]), t, &(t[n])); } else { @@ -365,7 +363,7 @@ static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, bn_mul_comba4(r, a, b); bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n])); } else if (n == 8 && dna == 0 && dnb == 0) { - /* XXX: bn_mul_comba8 could take extra args to do this well */ + // XXX: bn_mul_comba8 could take extra args to do this well if (!zero) { bn_mul_comba8(&(t[n2]), t, &(t[n])); } else { @@ -385,24 +383,24 @@ static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p); } - /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) */ + // t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign + // r[10] holds (a[0]*b[0]) + // r[32] holds (b[1]*b[1]) c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); if (neg) { - /* if t[32] is negative */ + // if t[32] is negative c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); } else { - /* Might have a carry */ + // Might have a carry c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); } - /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - * c1 holds the carry bits */ + // t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) + // r[10] holds (a[0]*b[0]) + // r[32] holds (b[1]*b[1]) + // c1 holds the carry bits c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); if (c1) { p = &(r[n + n2]); @@ -410,8 +408,8 @@ static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, ln = (lo + c1) & BN_MASK2; *p = ln; - /* The overflow will stop before we over write - * words we should not overwrite */ + // The overflow will stop before we over write + // words we should not overwrite if (ln < (BN_ULONG)c1) { do { p++; @@ -423,9 +421,9 @@ static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, } } -/* n+tn is the word length - * t needs to be n*4 is size, as does r */ -/* tnX may not be negative but less than n */ +// n+tn is the word length +// t needs to be n*4 is size, as does r +// tnX may not be negative but less than n static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, int tna, int tnb, BN_ULONG *t) { int i, j, n2 = n * 2; @@ -437,33 +435,33 @@ static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, return; } - /* r=(a[0]-a[1])*(b[1]-b[0]) */ + // r=(a[0]-a[1])*(b[1]-b[0]) c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); neg = 0; switch (c1 * 3 + c2) { case -4: - bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ - bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ + bn_sub_part_words(t, &(a[n]), a, tna, tna - n); // - + bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); // - break; case -3: - /* break; */ + // break; case -2: - bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ - bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ + bn_sub_part_words(t, &(a[n]), a, tna, tna - n); // - + bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); // + neg = 1; break; case -1: case 0: case 1: - /* break; */ + // break; case 2: - bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ - bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ + bn_sub_part_words(t, a, &(a[n]), tna, n - tna); // + + bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); // - neg = 1; break; case 3: - /* break; */ + // break; case 4: bn_sub_part_words(t, a, &(a[n]), tna, n - tna); bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); @@ -480,8 +478,8 @@ static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); bn_mul_recursive(r, a, b, n, 0, 0, p); i = n / 2; - /* If there is only a bottom half to the number, - * just do it */ + // If there is only a bottom half to the number, + // just do it if (tna > tnb) { j = tna - i; } else { @@ -492,12 +490,12 @@ static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i, p); OPENSSL_memset(&(r[n2 + i * 2]), 0, sizeof(BN_ULONG) * (n2 - i * 2)); } else if (j > 0) { - /* eg, n == 16, i == 8 and tn == 11 */ + // eg, n == 16, i == 8 and tn == 11 bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i, p); OPENSSL_memset(&(r[n2 + tna + tnb]), 0, sizeof(BN_ULONG) * (n2 - tna - tnb)); } else { - /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ + // (j < 0) eg, n == 16, i == 8 and tn == 5 OPENSSL_memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2); if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { @@ -505,9 +503,9 @@ static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, } else { for (;;) { i /= 2; - /* these simplified conditions work - * exclusively because difference - * between tna and tnb is 1 or 0 */ + // these simplified conditions work + // exclusively because difference + // between tna and tnb is 1 or 0 if (i < tna || i < tnb) { bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i, p); @@ -522,25 +520,24 @@ static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, } } - /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - */ + // t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign + // r[10] holds (a[0]*b[0]) + // r[32] holds (b[1]*b[1]) c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); if (neg) { - /* if t[32] is negative */ + // if t[32] is negative c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); } else { - /* Might have a carry */ + // Might have a carry c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); } - /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - * c1 holds the carry bits */ + // t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) + // r[10] holds (a[0]*b[0]) + // r[32] holds (b[1]*b[1]) + // c1 holds the carry bits c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); if (c1) { p = &(r[n + n2]); @@ -548,8 +545,8 @@ static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, ln = (lo + c1) & BN_MASK2; *p = ln; - /* The overflow will stop before we over write - * words we should not overwrite */ + // The overflow will stop before we over write + // words we should not overwrite if (ln < (BN_ULONG)c1) { do { p++; @@ -627,7 +624,7 @@ int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { } bn_mul_part_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d); } else { - /* al <= j || bl <= j */ + // al <= j || bl <= j if (!bn_wexpand(t, k * 2)) { goto err; } @@ -659,7 +656,7 @@ err: return ret; } -/* tmp must have 2*n words */ +// tmp must have 2*n words static void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp) { int i, j, max; const BN_ULONG *ap; @@ -687,23 +684,22 @@ static void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp) bn_add_words(r, r, r, max); - /* There will not be a carry */ + // There will not be a carry bn_sqr_words(tmp, a, n); bn_add_words(r, r, tmp, max); } -/* r is 2*n words in size, - * a and b are both n words in size. (There's not actually a 'b' here ...) - * n must be a power of 2. - * We multiply and return the result. - * t must be 2*n words in size - * We calculate - * a[0]*b[0] - * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) - * a[1]*b[1] - */ +// r is 2*n words in size, +// a and b are both n words in size. (There's not actually a 'b' here ...) +// n must be a power of 2. +// We multiply and return the result. +// t must be 2*n words in size +// We calculate +// a[0]*b[0] +// a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) +// a[1]*b[1] static void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t) { int n = n2 / 2; int zero, c1; @@ -720,7 +716,7 @@ static void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t bn_sqr_normal(r, a, n2, t); return; } - /* r=(a[0]-a[1])*(a[1]-a[0]) */ + // r=(a[0]-a[1])*(a[1]-a[0]) c1 = bn_cmp_words(a, &(a[n]), n); zero = 0; if (c1 > 0) { @@ -731,7 +727,7 @@ static void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t zero = 1; } - /* The result will always be negative unless it is zero */ + // The result will always be negative unless it is zero p = &(t[n2 * 2]); if (!zero) { @@ -742,19 +738,19 @@ static void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t bn_sqr_recursive(r, a, n, p); bn_sqr_recursive(&(r[n2]), &(a[n]), n, p); - /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) */ + // t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero + // r[10] holds (a[0]*b[0]) + // r[32] holds (b[1]*b[1]) c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); - /* t[32] is negative */ + // t[32] is negative c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); - /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1]) - * r[10] holds (a[0]*a[0]) - * r[32] holds (a[1]*a[1]) - * c1 holds the carry bits */ + // t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1]) + // r[10] holds (a[0]*a[0]) + // r[32] holds (a[1]*a[1]) + // c1 holds the carry bits c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); if (c1) { p = &(r[n + n2]); @@ -762,8 +758,8 @@ static void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t ln = (lo + c1) & BN_MASK2; *p = ln; - /* The overflow will stop before we over write - * words we should not overwrite */ + // The overflow will stop before we over write + // words we should not overwrite if (ln < (BN_ULONG)c1) { do { p++; @@ -818,7 +814,7 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) { goto err; } - max = 2 * al; /* Non-zero (from above) */ + max = 2 * al; // Non-zero (from above) if (!bn_wexpand(rr, max)) { goto err; } @@ -852,8 +848,8 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) { } rr->neg = 0; - /* If the most-significant half of the top word of 'a' is zero, then - * the square of 'a' will max-1 words. */ + // If the most-significant half of the top word of 'a' is zero, then + // the square of 'a' will max-1 words. if (a->d[al - 1] == (a->d[al - 1] & BN_MASK2l)) { rr->top = max - 1; } else { |