Return to digit.c CVS log

Up to [rsaref] / rsaref / source

Annotation of rsaref/source/digit.c, revision 1.1.1.2

1.1       root        1: /* DIGIT.C - digit arithmetic routines
                      2:  */
                      3: 
1.1.1.2 ! root        4: /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
        !             5:       Inc., created 1991. All rights reserved.
1.1       root        6:  */
                      7: 
                      8: #include "global.h"
                      9: #include "rsaref.h"
                     10: #include "nn.h"
                     11: #include "digit.h"
                     12: 
                     13: /* Computes a = b * c, where b and c are digits.
                     14: 
                     15:    Lengths: a[2].
                     16:  */
                     17: void NN_DigitMult (a, b, c)
                     18: NN_DIGIT a[2], b, c;
                     19: {
                     20:   NN_DIGIT t, u;
                     21:   NN_HALF_DIGIT bHigh, bLow, cHigh, cLow;
                     22: 
1.1.1.2 ! root       23:   bHigh = (NN_HALF_DIGIT)HIGH_HALF (b);
        !            24:   bLow = (NN_HALF_DIGIT)LOW_HALF (b);
        !            25:   cHigh = (NN_HALF_DIGIT)HIGH_HALF (c);
        !            26:   cLow = (NN_HALF_DIGIT)LOW_HALF (c);
1.1       root       27: 
                     28:   a[0] = (NN_DIGIT)bLow * (NN_DIGIT)cLow;
                     29:   t = (NN_DIGIT)bLow * (NN_DIGIT)cHigh;
                     30:   u = (NN_DIGIT)bHigh * (NN_DIGIT)cLow;
                     31:   a[1] = (NN_DIGIT)bHigh * (NN_DIGIT)cHigh;
                     32:   
                     33:   if ((t += u) < u)
                     34:     a[1] += TO_HIGH_HALF (1);
                     35:   u = TO_HIGH_HALF (t);
                     36:   
                     37:   if ((a[0] += u) < u)
                     38:     a[1]++;
                     39:   a[1] += HIGH_HALF (t);
                     40: }
                     41: 
                     42: /* Sets a = b / c, where a and c are digits.
                     43: 
                     44:    Lengths: b[2].
                     45:    Assumes b[1] < c and HIGH_HALF (c) > 0. For efficiency, c should be
                     46:    normalized.
                     47:  */
                     48: void NN_DigitDiv (a, b, c)
                     49: NN_DIGIT *a, b[2], c;
                     50: {
                     51:   NN_DIGIT t[2], u, v;
                     52:   NN_HALF_DIGIT aHigh, aLow, cHigh, cLow;
                     53: 
1.1.1.2 ! root       54:   cHigh = (NN_HALF_DIGIT)HIGH_HALF (c);
        !            55:   cLow = (NN_HALF_DIGIT)LOW_HALF (c);
1.1       root       56: 
                     57:   t[0] = b[0];
                     58:   t[1] = b[1];
                     59: 
                     60:   /* Underestimate high half of quotient and subtract.
                     61:    */
                     62:   if (cHigh == MAX_NN_HALF_DIGIT)
1.1.1.2 ! root       63:     aHigh = (NN_HALF_DIGIT)HIGH_HALF (t[1]);
1.1       root       64:   else
                     65:     aHigh = (NN_HALF_DIGIT)(t[1] / (cHigh + 1));
                     66:   u = (NN_DIGIT)aHigh * (NN_DIGIT)cLow;
                     67:   v = (NN_DIGIT)aHigh * (NN_DIGIT)cHigh;
                     68:   if ((t[0] -= TO_HIGH_HALF (u)) > (MAX_NN_DIGIT - TO_HIGH_HALF (u)))
                     69:     t[1]--;
                     70:   t[1] -= HIGH_HALF (u);
                     71:   t[1] -= v;
                     72: 
                     73:   /* Correct estimate.
                     74:    */
                     75:   while ((t[1] > cHigh) ||
                     76:          ((t[1] == cHigh) && (t[0] >= TO_HIGH_HALF (cLow)))) {
                     77:     if ((t[0] -= TO_HIGH_HALF (cLow)) > MAX_NN_DIGIT - TO_HIGH_HALF (cLow))
                     78:       t[1]--;
                     79:     t[1] -= cHigh;
                     80:     aHigh++;
                     81:   }
                     82: 
                     83:   /* Underestimate low half of quotient and subtract.
                     84:    */
                     85:   if (cHigh == MAX_NN_HALF_DIGIT)
1.1.1.2 ! root       86:     aLow = (NN_HALF_DIGIT)LOW_HALF (t[1]);
1.1       root       87:   else
1.1.1.2 ! root       88:     aLow = 
        !            89:       (NN_HALF_DIGIT)((TO_HIGH_HALF (t[1]) + HIGH_HALF (t[0])) / (cHigh + 1));
1.1       root       90:   u = (NN_DIGIT)aLow * (NN_DIGIT)cLow;
                     91:   v = (NN_DIGIT)aLow * (NN_DIGIT)cHigh;
                     92:   if ((t[0] -= u) > (MAX_NN_DIGIT - u))
                     93:     t[1]--;
                     94:   if ((t[0] -= TO_HIGH_HALF (v)) > (MAX_NN_DIGIT - TO_HIGH_HALF (v)))
                     95:     t[1]--;
                     96:   t[1] -= HIGH_HALF (v);
                     97: 
                     98:   /* Correct estimate.
                     99:    */
                    100:   while ((t[1] > 0) || ((t[1] == 0) && t[0] >= c)) {
                    101:     if ((t[0] -= c) > (MAX_NN_DIGIT - c))
                    102:       t[1]--;
                    103:     aLow++;
                    104:   }
                    105:   
                    106:   *a = TO_HIGH_HALF (aHigh) + aLow;
                    107: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.