#
source:
trunk/third/moira/util/rsaref/digit.c
@
23095

Revision 23095, 2.5 KB checked in by ghudson, 16 years ago (diff) |
---|

Line | |
---|---|

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

**Note:**See TracBrowser for help on using the repository browser.