diff options
Diffstat (limited to 'crypto/bn/bn_mul.c')
| -rw-r--r-- | crypto/bn/bn_mul.c | 33 |
1 files changed, 22 insertions, 11 deletions
diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c index 12e5be80eb..f53985d750 100644 --- a/crypto/bn/bn_mul.c +++ b/crypto/bn/bn_mul.c @@ -379,7 +379,8 @@ BN_ULONG bn_add_part_words(BN_ULONG *r, /* Karatsuba recursive multiplication algorithm * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ -/* r is 2*n2 words in size, +/*- + * 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. @@ -500,7 +501,8 @@ 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 + /*- + * 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]) */ @@ -517,7 +519,8 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 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]) + /*- + * 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 @@ -676,7 +679,8 @@ 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 + /*- + * 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]) */ @@ -693,7 +697,8 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, 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]) + /*- + * 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 @@ -720,7 +725,8 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, } } -/* a and b must be the same size, which is n2. +/*- + * a and b must be the same size, which is n2. * r needs to be n2 words and t needs to be n2*2 */ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, @@ -749,7 +755,8 @@ void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, } } -/* a and b must be the same size, which is n2. +/*- + * 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 @@ -820,7 +827,8 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2])); } - /* s0 == low(al*bl) + /*- + * 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)) @@ -857,16 +865,19 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, lp[i]=((~mp[i])+1)&BN_MASK2; } - /* s[0] = low(al*bl) + /*- + * 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[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[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) */ |