crypto/bn/old/bn_high.c

   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
  18 int BN_mul_high(r,a,b,low,words)
  19 BIGNUM *r,*a,*b,*low;
  20 int words;
  21         {
  22         int w2,borrow=0,full=0;
  23         BIGNUM t1,t2,t3,h,ah,al,bh,bl,m,s0,s1;
  24         BN_ULONG ul1,ul2;
  25
  26         BN_mul(r,a,b);
  27         BN_rshift(r,r,words*BN_BITS2);
  28         return(1);
  29
  30         w2=(words+1)/2;
  31
  32 #ifdef BN_MUL_HIGH_DEBUG
  33 fprintf(stdout,"words=%d w2=%d\n",words,w2);
  34 #endif
  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);
  43
  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);
  48
  49         bn_set_low(&s0,low,w2);
  50         bn_set_high(&s1,low,w2);
  51
  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");
  58
  59         /* Calculate (al-ah)*(bh-bl) */
  60         BN_sub(&t1,&al,&ah);
  61         BN_sub(&t2,&bh,&bl);
  62         BN_mul(&m,&t1,&t2);
  63
  64         /* Calculate ah*bh */
  65         BN_mul(&h,&ah,&bh);
  66
  67         /* s0 == low(al*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)
  71          */
  72         BN_add(&m,&m,&h);
  73         BN_add(&t2,&m,&s0);
  74
  75 debug_BN_print(stdout,&t2," middle value\n");
  76
  77         /* Quick and dirty mask off of high words */
  78         if (w2 < t2.top) t2.top=w2;
  79 #if 0
  80         bn_set_low(&t3,&t2,w2);
  81 #endif
  82
  83 debug_BN_print(stdout,&t2," low middle value\n");
  84         BN_sub(&t1,&s1,&t2);
  85
  86         if (t1.neg)
  87                 {
  88 debug_BN_print(stdout,&t1," before\n");
  89                 BN_zero(&t2);
  90                 BN_set_bit(&t2,w2*BN_BITS2);
  91                 BN_add(&t1,&t2,&t1);
  92                 /* BN_mask_bits(&t1,w2*BN_BITS2); */
  93                 /* if (words < t1.top) t1.top=words; */
  94 debug_BN_print(stdout,&t1," after\n");
  95                 borrow=1;
  96                 }
  97
  98 /* XXXXX SPEED THIS UP */
  99         /* al*bl == high(al*bl)<<words+s0 */
 100         BN_lshift(&t1,&t1,w2*BN_BITS2);
 101         BN_add(&t1,&t1,&s0);
 102         if (w2*2 < t1.top) t1.top=w2*2; /* This should not happen? */
 103
 104         /* We now have
 105          * al*bl                        - t1
 106          * (al-ah)*(bh-bl)+ah*bh        - m
 107          * ah*bh                        - h
 108          */
 109 #if 0
 110         BN_add(&m,&m,&t1);
 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);
 116         BN_add(r,&m,&t1);
 117         BN_add(r,r,&h);
 118         BN_rshift(r,r,w2*2*BN_BITS2);
 119 #else
 120         BN_add(&m,&m,&t1);              /* Do a cmp then +1 if needed? */
 121         bn_set_high(&t3,&t1,w2);
 122         BN_add(&m,&m,&t3);
 123         bn_set_high(&t3,&m,w2);
 124         BN_add(r,&h,&t3);
 125 #endif
 126
 127 #ifdef BN_MUL_HIGH_DEBUG
 128 printf("carry=%d\n",borrow);
 129 #endif
 130 debug_BN_print(stdout,r," ret\n");
 131         BN_free(&t1); BN_free(&t2);
 132         BN_free(&m); BN_free(&h);
 133         return(1);
 134         }
 135
 136
 137