]>
Commit | Line | Data |
---|---|---|
dfeab068 RE |
1 | #include <stdio.h> |
2 | #include "cryptlib.h" | |
3 | #include "bn_lcl.h" | |
4 | ||
5 | #undef BN_MUL_HIGH_DEBUG | |
6 | ||
7 | #ifdef BN_MUL_HIGH_DEBUG | |
8 | #define debug_BN_print(a,b,c) BN_print_fp(a,b); printf(c); | |
9 | #else | |
10 | #define debug_BN_print(a,b,c) | |
11 | #endif | |
12 | ||
13 | int BN_mul_high(BIGNUM *r,BIGNUM *a,BIGNUM *b,BIGNUM *low, int words); | |
14 | ||
15 | #undef t1 | |
16 | #undef t2 | |
17 | ||
6b691a5c | 18 | int BN_mul_high(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *low, int words) |
dfeab068 RE |
19 | { |
20 | int w2,borrow=0,full=0; | |
21 | BIGNUM t1,t2,t3,h,ah,al,bh,bl,m,s0,s1; | |
22 | BN_ULONG ul1,ul2; | |
23 | ||
24 | BN_mul(r,a,b); | |
25 | BN_rshift(r,r,words*BN_BITS2); | |
26 | return(1); | |
27 | ||
28 | w2=(words+1)/2; | |
29 | ||
30 | #ifdef BN_MUL_HIGH_DEBUG | |
31 | fprintf(stdout,"words=%d w2=%d\n",words,w2); | |
32 | #endif | |
33 | debug_BN_print(stdout,a," a\n"); | |
34 | debug_BN_print(stdout,b," b\n"); | |
35 | debug_BN_print(stdout,low," low\n"); | |
36 | BN_init(&al); BN_init(&ah); | |
37 | BN_init(&bl); BN_init(&bh); | |
38 | BN_init(&t1); BN_init(&t2); BN_init(&t3); | |
39 | BN_init(&s0); BN_init(&s1); | |
40 | BN_init(&h); BN_init(&m); | |
41 | ||
42 | bn_set_low (&al,a,w2); | |
43 | bn_set_high(&ah,a,w2); | |
44 | bn_set_low (&bl,b,w2); | |
45 | bn_set_high(&bh,b,w2); | |
46 | ||
47 | bn_set_low(&s0,low,w2); | |
48 | bn_set_high(&s1,low,w2); | |
49 | ||
50 | debug_BN_print(stdout,&al," al\n"); | |
51 | debug_BN_print(stdout,&ah," ah\n"); | |
52 | debug_BN_print(stdout,&bl," bl\n"); | |
53 | debug_BN_print(stdout,&bh," bh\n"); | |
54 | debug_BN_print(stdout,&s0," s0\n"); | |
55 | debug_BN_print(stdout,&s1," s1\n"); | |
56 | ||
57 | /* Calculate (al-ah)*(bh-bl) */ | |
58 | BN_sub(&t1,&al,&ah); | |
59 | BN_sub(&t2,&bh,&bl); | |
60 | BN_mul(&m,&t1,&t2); | |
61 | ||
62 | /* Calculate ah*bh */ | |
63 | BN_mul(&h,&ah,&bh); | |
64 | ||
65 | /* s0 == low(al*bl) | |
66 | * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) | |
67 | * We know s0 and s1 so the only unknown is high(al*bl) | |
68 | * high(al*bl) == s1 - low(ah*bh+(al-ah)*(bh-bl)+s0) | |
69 | */ | |
70 | BN_add(&m,&m,&h); | |
71 | BN_add(&t2,&m,&s0); | |
72 | ||
73 | debug_BN_print(stdout,&t2," middle value\n"); | |
74 | ||
75 | /* Quick and dirty mask off of high words */ | |
76 | if (w2 < t2.top) t2.top=w2; | |
77 | #if 0 | |
78 | bn_set_low(&t3,&t2,w2); | |
79 | #endif | |
80 | ||
81 | debug_BN_print(stdout,&t2," low middle value\n"); | |
82 | BN_sub(&t1,&s1,&t2); | |
83 | ||
84 | if (t1.neg) | |
85 | { | |
86 | debug_BN_print(stdout,&t1," before\n"); | |
87 | BN_zero(&t2); | |
88 | BN_set_bit(&t2,w2*BN_BITS2); | |
89 | BN_add(&t1,&t2,&t1); | |
90 | /* BN_mask_bits(&t1,w2*BN_BITS2); */ | |
91 | /* if (words < t1.top) t1.top=words; */ | |
92 | debug_BN_print(stdout,&t1," after\n"); | |
93 | borrow=1; | |
94 | } | |
95 | ||
96 | /* XXXXX SPEED THIS UP */ | |
97 | /* al*bl == high(al*bl)<<words+s0 */ | |
98 | BN_lshift(&t1,&t1,w2*BN_BITS2); | |
99 | BN_add(&t1,&t1,&s0); | |
100 | if (w2*2 < t1.top) t1.top=w2*2; /* This should not happen? */ | |
101 | ||
102 | /* We now have | |
103 | * al*bl - t1 | |
104 | * (al-ah)*(bh-bl)+ah*bh - m | |
105 | * ah*bh - h | |
106 | */ | |
107 | #if 0 | |
108 | BN_add(&m,&m,&t1); | |
109 | debug_BN_print(stdout,&t1," s10\n"); | |
110 | debug_BN_print(stdout,&m," s21\n"); | |
111 | debug_BN_print(stdout,&h," s32\n"); | |
112 | BN_lshift(&m,&m,w2*BN_BITS2); | |
113 | BN_lshift(&h,&h,w2*2*BN_BITS2); | |
114 | BN_add(r,&m,&t1); | |
115 | BN_add(r,r,&h); | |
116 | BN_rshift(r,r,w2*2*BN_BITS2); | |
117 | #else | |
118 | BN_add(&m,&m,&t1); /* Do a cmp then +1 if needed? */ | |
119 | bn_set_high(&t3,&t1,w2); | |
120 | BN_add(&m,&m,&t3); | |
121 | bn_set_high(&t3,&m,w2); | |
122 | BN_add(r,&h,&t3); | |
123 | #endif | |
124 | ||
125 | #ifdef BN_MUL_HIGH_DEBUG | |
126 | printf("carry=%d\n",borrow); | |
127 | #endif | |
128 | debug_BN_print(stdout,r," ret\n"); | |
129 | BN_free(&t1); BN_free(&t2); | |
130 | BN_free(&m); BN_free(&h); | |
131 | return(1); | |
132 | } | |
133 | ||
134 | ||
135 |