]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/old/bn_high.c
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(r
,a
,b
,low
,words
)
22 int w2
,borrow
=0,full
=0;
23 BIGNUM t1
,t2
,t3
,h
,ah
,al
,bh
,bl
,m
,s0
,s1
;
27 BN_rshift(r
,r
,words
*BN_BITS2
);
32 #ifdef BN_MUL_HIGH_DEBUG
33 fprintf(stdout
,"words=%d w2=%d\n",words
,w2
);
35 debug_BN_print(stdout
,a
," a\n");
36 debug_BN_print(stdout
,b
," b\n");
37 debug_BN_print(stdout
,low
," low\n");
38 BN_init(&al
); BN_init(&ah
);
39 BN_init(&bl
); BN_init(&bh
);
40 BN_init(&t1
); BN_init(&t2
); BN_init(&t3
);
41 BN_init(&s0
); BN_init(&s1
);
42 BN_init(&h
); BN_init(&m
);
44 bn_set_low (&al
,a
,w2
);
45 bn_set_high(&ah
,a
,w2
);
46 bn_set_low (&bl
,b
,w2
);
47 bn_set_high(&bh
,b
,w2
);
49 bn_set_low(&s0
,low
,w2
);
50 bn_set_high(&s1
,low
,w2
);
52 debug_BN_print(stdout
,&al
," al\n");
53 debug_BN_print(stdout
,&ah
," ah\n");
54 debug_BN_print(stdout
,&bl
," bl\n");
55 debug_BN_print(stdout
,&bh
," bh\n");
56 debug_BN_print(stdout
,&s0
," s0\n");
57 debug_BN_print(stdout
,&s1
," s1\n");
59 /* Calculate (al-ah)*(bh-bl) */
68 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
69 * We know s0 and s1 so the only unknown is high(al*bl)
70 * high(al*bl) == s1 - low(ah*bh+(al-ah)*(bh-bl)+s0)
75 debug_BN_print(stdout
,&t2
," middle value\n");
77 /* Quick and dirty mask off of high words */
78 if (w2
< t2
.top
) t2
.top
=w2
;
80 bn_set_low(&t3
,&t2
,w2
);
83 debug_BN_print(stdout
,&t2
," low middle value\n");
88 debug_BN_print(stdout
,&t1
," before\n");
90 BN_set_bit(&t2
,w2
*BN_BITS2
);
92 /* BN_mask_bits(&t1,w2*BN_BITS2); */
93 /* if (words < t1.top) t1.top=words; */
94 debug_BN_print(stdout
,&t1
," after\n");
98 /* XXXXX SPEED THIS UP */
99 /* al*bl == high(al*bl)<<words+s0 */
100 BN_lshift(&t1
,&t1
,w2
*BN_BITS2
);
102 if (w2
*2 < t1
.top
) t1
.top
=w2
*2; /* This should not happen? */
106 * (al-ah)*(bh-bl)+ah*bh - m
111 debug_BN_print(stdout
,&t1
," s10\n");
112 debug_BN_print(stdout
,&m
," s21\n");
113 debug_BN_print(stdout
,&h
," s32\n");
114 BN_lshift(&m
,&m
,w2
*BN_BITS2
);
115 BN_lshift(&h
,&h
,w2
*2*BN_BITS2
);
118 BN_rshift(r
,r
,w2
*2*BN_BITS2
);
120 BN_add(&m
,&m
,&t1
); /* Do a cmp then +1 if needed? */
121 bn_set_high(&t3
,&t1
,w2
);
123 bn_set_high(&t3
,&m
,w2
);
127 #ifdef BN_MUL_HIGH_DEBUG
128 printf("carry=%d\n",borrow
);
130 debug_BN_print(stdout
,r
," ret\n");
131 BN_free(&t1
); BN_free(&t2
);
132 BN_free(&m
); BN_free(&h
);