5 #undef BN_MUL_HIGH_DEBUG
7 #ifdef BN_MUL_HIGH_DEBUG
8 #define debug_BN_print(a,b,c) BN_print_fp(a,b); printf(c);
10 #define debug_BN_print(a,b,c)
13 int BN_mul_high(BIGNUM *r,BIGNUM *a,BIGNUM *b,BIGNUM *low, int words);
18 int BN_mul_high(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *low, int words)
20 int w2,borrow=0,full=0;
21 BIGNUM t1,t2,t3,h,ah,al,bh,bl,m,s0,s1;
25 BN_rshift(r,r,words*BN_BITS2);
30 #ifdef BN_MUL_HIGH_DEBUG
31 fprintf(stdout,"words=%d w2=%d\n",words,w2);
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);
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);
47 bn_set_low(&s0,low,w2);
48 bn_set_high(&s1,low,w2);
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");
57 /* Calculate (al-ah)*(bh-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)
73 debug_BN_print(stdout,&t2," middle value\n");
75 /* Quick and dirty mask off of high words */
76 if (w2 < t2.top) t2.top=w2;
78 bn_set_low(&t3,&t2,w2);
81 debug_BN_print(stdout,&t2," low middle value\n");
86 debug_BN_print(stdout,&t1," before\n");
88 BN_set_bit(&t2,w2*BN_BITS2);
90 /* BN_mask_bits(&t1,w2*BN_BITS2); */
91 /* if (words < t1.top) t1.top=words; */
92 debug_BN_print(stdout,&t1," after\n");
96 /* XXXXX SPEED THIS UP */
97 /* al*bl == high(al*bl)<<words+s0 */
98 BN_lshift(&t1,&t1,w2*BN_BITS2);
100 if (w2*2 < t1.top) t1.top=w2*2; /* This should not happen? */
104 * (al-ah)*(bh-bl)+ah*bh - m
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);
116 BN_rshift(r,r,w2*2*BN_BITS2);
118 BN_add(&m,&m,&t1); /* Do a cmp then +1 if needed? */
119 bn_set_high(&t3,&t1,w2);
121 bn_set_high(&t3,&m,w2);
125 #ifdef BN_MUL_HIGH_DEBUG
126 printf("carry=%d\n",borrow);
128 debug_BN_print(stdout,r," ret\n");
129 BN_free(&t1); BN_free(&t2);
130 BN_free(&m); BN_free(&h);