Return to digit.c CVS log

Up to [rsaref] / rsaref / source

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

1.1       root        1: /* DIGIT.C - digit arithmetic routines
                      2:  */
                      3: 
                      4: /* Copyright (C) 1991-2 RSA Laboratories, a division of RSA Data
                      5:    Security, Inc. All rights reserved.
                      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: 
                     23:   bHigh = HIGH_HALF (b);
                     24:   bLow = LOW_HALF (b);
                     25:   cHigh = HIGH_HALF (c);
                     26:   cLow = LOW_HALF (c);
                     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: 
                     54:   cHigh = HIGH_HALF (c);
                     55:   cLow = LOW_HALF (c);
                     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)
                     63:     aHigh = HIGH_HALF (t[1]);
                     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)
                     86:     aLow = LOW_HALF (t[1]);
                     87:   else
                     88:     aLow =
                     89:       (NN_HALF_DIGIT)
                     90:         ((NN_DIGIT)(TO_HIGH_HALF (t[1]) + HIGH_HALF (t[0])) / (cHigh + 1));
                     91:   u = (NN_DIGIT)aLow * (NN_DIGIT)cLow;
                     92:   v = (NN_DIGIT)aLow * (NN_DIGIT)cHigh;
                     93:   if ((t[0] -= u) > (MAX_NN_DIGIT - u))
                     94:     t[1]--;
                     95:   if ((t[0] -= TO_HIGH_HALF (v)) > (MAX_NN_DIGIT - TO_HIGH_HALF (v)))
                     96:     t[1]--;
                     97:   t[1] -= HIGH_HALF (v);
                     98: 
                     99:   /* Correct estimate.
                    100:    */
                    101:   while ((t[1] > 0) || ((t[1] == 0) && t[0] >= c)) {
                    102:     if ((t[0] -= c) > (MAX_NN_DIGIT - c))
                    103:       t[1]--;
                    104:     aLow++;
                    105:   }
                    106:   
                    107:   *a = TO_HIGH_HALF (aHigh) + aLow;
                    108: }

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