| 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 | } |
|---|
