Return to digit.c CVS log

Up to [rsaref] / rsaref / source

Annotation of rsaref/source/digit.c, revision 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.