monotone

monotone Mtn Source Tree

Root/botan/mp_core.cpp

1/*************************************************
2* MPI Addition/Subtraction Source File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#include <botan/mp_core.h>
7
8namespace Botan {
9
10/*************************************************
11* Two Operand Addition *
12*************************************************/
13void bigint_add2(word x[], u32bit x_size, const word y[], u32bit y_size)
14 {
15 word carry = 0;
16
17 for(u32bit j = 0; j != y_size; j++)
18 {
19 word z = x[j] + y[j] + carry;
20
21 const u32bit top_x = x[j] >> (MP_WORD_BITS - 1);
22 const u32bit top_y = y[j] >> (MP_WORD_BITS - 1);
23 const u32bit top_z = z >> (MP_WORD_BITS - 1);
24
25 x[j] = z;
26 carry = ((top_x | top_y) & !top_z) | (top_x & top_y);
27 }
28
29 if(!carry) return;
30
31 for(u32bit j = y_size; j != x_size; j++)
32 {
33 x[j]++;
34 if(x[j]) return;
35 }
36 x[x_size]++;
37 }
38
39/*************************************************
40* Three Operand Addition *
41*************************************************/
42void bigint_add3(word z[], const word x[], u32bit x_size,
43 const word y[], u32bit y_size)
44 {
45 if(x_size < y_size)
46 { bigint_add3(z, y, y_size, x, x_size); return; }
47
48 word carry = 0;
49 for(u32bit j = 0; j != y_size; j++)
50 {
51 z[j] = x[j] + y[j] + carry;
52
53 const u32bit top_x = x[j] >> (MP_WORD_BITS - 1);
54 const u32bit top_y = y[j] >> (MP_WORD_BITS - 1);
55 const u32bit top_z = z[j] >> (MP_WORD_BITS - 1);
56
57 carry = ((top_x | top_y) & !top_z) | (top_x & top_y);
58 }
59
60 for(u32bit j = y_size; j != x_size; j++)
61 z[j] = x[j];
62
63 if(!carry) return;
64
65 for(u32bit j = y_size; j != x_size; j++)
66 {
67 z[j]++;
68 if(z[j]) return;
69 }
70 z[x_size]++;
71 }
72
73/*************************************************
74* Two Operand Subtraction *
75*************************************************/
76void bigint_sub2(word x[], u32bit x_size, const word y[], u32bit y_size)
77 {
78 word borrow = 0;
79 for(u32bit j = 0; j != y_size; j++)
80 {
81 word r = x[j] - y[j];
82 word next = ((x[j] < r) ? 1 : 0);
83 r -= borrow;
84 borrow = next | ((r == MP_WORD_MAX) ? borrow : 0);
85 x[j] = r;
86 }
87
88 if(!borrow) return;
89
90 for(u32bit j = y_size; j != x_size; j++)
91 {
92 x[j]--;
93 if(x[j] != MP_WORD_MAX) return;
94 }
95 }
96
97/*************************************************
98* Three Operand Subtraction *
99*************************************************/
100void bigint_sub3(word z[], const word x[], u32bit x_size,
101 const word y[], u32bit y_size)
102 {
103 word borrow = 0;
104 for(u32bit j = 0; j != y_size; j++)
105 {
106 z[j] = x[j] - y[j];
107 word next = ((x[j] < z[j]) ? 1 : 0);
108 z[j] -= borrow;
109 borrow = next | ((z[j] == MP_WORD_MAX) ? borrow : 0);
110 }
111
112 for(u32bit j = y_size; j != x_size; j++)
113 z[j] = x[j];
114
115 if(!borrow) return;
116
117 for(u32bit j = y_size; j != x_size; j++)
118 {
119 z[j]--;
120 if(z[j] != MP_WORD_MAX) return;
121 }
122 }
123
124}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status