util/rsaref/digit.c

   1 /* DIGIT.C - digit arithmetic routines
   2  */
   3
   4 /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
   5       Inc., created 1991. 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 = (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);
  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 = (NN_HALF_DIGIT)HIGH_HALF (c);
  55   cLow = (NN_HALF_DIGIT)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 = (NN_HALF_DIGIT)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 = (NN_HALF_DIGIT)LOW_HALF (t[1]);
  87   else
  88     aLow =
  89       (NN_HALF_DIGIT)((TO_HIGH_HALF (t[1]) + HIGH_HALF (t[0])) / (cHigh + 1));
  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 }