Commit | Line | Data |
---|---|---|
0afe80d5 MM |
1 | /* Test suite for the library. First, it ``tests'' that all the constructs it |
2 | * uses compile successfully. Then, its output to stdout is compared to the | |
e6866cd0 MM |
3 | * expected output automatically extracted from slash-slash comments below. |
4 | * | |
5 | * NOTE: For now, the test suite expects a 32-bit system. On others, some tests | |
6 | * may fail, and it may be ineffective at catching bugs. TODO: Remedy this. */ | |
0afe80d5 MM |
7 | |
8 | #include "BigIntegerLibrary.hh" | |
9 | ||
10 | #include <string> | |
11 | #include <iostream> | |
12 | using namespace std; | |
13 | ||
e6866cd0 MM |
14 | // Evaluate expr and print the result or "error" as appropriate. |
15 | #define TEST(expr) do {\ | |
16 | cout << "Line " << __LINE__ << ": ";\ | |
17 | try {\ | |
18 | cout << (expr);\ | |
19 | } catch (const char *err) {\ | |
20 | cout << "error";\ | |
21 | }\ | |
22 | cout << endl;\ | |
23 | } while (0) | |
24 | ||
706f6a7e MM |
25 | const BigUnsigned &check(const BigUnsigned &x) { |
26 | unsigned int l = x.getLength(); | |
27 | if (l != 0 && x.getBlock(l-1) == 0) | |
e6866cd0 | 28 | cout << "check: Unzapped number!" << endl; |
706f6a7e | 29 | if (l > x.getCapacity()) |
e6866cd0 | 30 | cout << "check: Capacity inconsistent with length!" << endl; |
706f6a7e MM |
31 | return x; |
32 | } | |
33 | ||
34 | const BigInteger &check(const BigInteger &x) { | |
35 | if (x.getSign() == 0 && !x.getMagnitude().isZero()) | |
e6866cd0 | 36 | cout << "check: Sign should not be zero!" << endl; |
706f6a7e | 37 | if (x.getSign() != 0 && x.getMagnitude().isZero()) |
e6866cd0 | 38 | cout << "check: Sign should be zero!" << endl; |
706f6a7e MM |
39 | check(x.getMagnitude()); |
40 | return x; | |
41 | } | |
42 | ||
e6866cd0 MM |
43 | short pathologicalShort = ~((unsigned short)(~0) >> 1); |
44 | int pathologicalInt = ~((unsigned int)(~0) >> 1); | |
45 | long pathologicalLong = ~((unsigned long)(~0) >> 1); | |
706f6a7e | 46 | |
0afe80d5 | 47 | int main() { |
706f6a7e MM |
48 | |
49 | try { | |
50 | ||
0afe80d5 | 51 | BigUnsigned z(0), one(1), ten(10); |
e6866cd0 MM |
52 | TEST(z); //0 |
53 | TEST(1); //1 | |
54 | TEST(10); //10 | |
0afe80d5 | 55 | |
706f6a7e MM |
56 | // TODO: Comprehensively test the general and special cases of each function. |
57 | ||
e6866cd0 MM |
58 | // Default constructors |
59 | TEST(check(BigUnsigned())); //0 | |
60 | TEST(check(BigInteger())); //0 | |
61 | ||
62 | // BigUnsigned conversion limits | |
63 | TEST(BigUnsigned(0).toUnsignedLong()); //0 | |
64 | TEST(BigUnsigned(4294967295U).toUnsignedLong()); //4294967295 | |
65 | TEST(stringToBigUnsigned("4294967296").toUnsignedLong()); //error | |
66 | ||
67 | TEST(BigUnsigned(0).toLong()); //0 | |
68 | TEST(BigUnsigned(2147483647).toLong()); //2147483647 | |
69 | TEST(BigUnsigned(2147483648U).toLong()); //error | |
70 | ||
71 | // int is the same as long on a 32-bit system | |
72 | TEST(BigUnsigned(0).toUnsignedInt()); //0 | |
73 | TEST(BigUnsigned(4294967295U).toUnsignedInt()); //4294967295 | |
74 | TEST(stringToBigUnsigned("4294967296").toUnsignedInt()); //error | |
75 | ||
76 | TEST(BigUnsigned(0).toInt()); //0 | |
77 | TEST(BigUnsigned(2147483647).toInt()); //2147483647 | |
78 | TEST(BigUnsigned(2147483648U).toInt()); //error | |
79 | ||
80 | TEST(BigUnsigned(0).toUnsignedShort()); //0 | |
81 | TEST(BigUnsigned(65535).toUnsignedShort()); //65535 | |
82 | TEST(BigUnsigned(65536).toUnsignedShort()); //error | |
83 | ||
84 | TEST(BigUnsigned(0).toShort()); //0 | |
85 | TEST(BigUnsigned(32767).toShort()); //32767 | |
86 | TEST(BigUnsigned(32768).toShort()); //error | |
87 | ||
88 | // BigInteger conversion limits | |
89 | TEST(BigInteger(-1).toUnsignedLong()); //error | |
90 | TEST(BigInteger(0).toUnsignedLong()); //0 | |
91 | TEST(BigInteger(4294967295U).toUnsignedLong()); //4294967295 | |
92 | TEST(stringToBigInteger("4294967296").toUnsignedLong()); //error | |
93 | ||
94 | TEST(stringToBigInteger("-2147483649").toLong()); //error | |
95 | TEST(stringToBigInteger("-2147483648").toLong()); //-2147483648 | |
96 | TEST(BigInteger(-2147483647).toLong()); //-2147483647 | |
97 | TEST(BigInteger(0).toLong()); //0 | |
98 | TEST(BigInteger(2147483647).toLong()); //2147483647 | |
99 | TEST(BigInteger(2147483648U).toLong()); //error | |
100 | ||
101 | // int is the same as long on a 32-bit system | |
102 | TEST(BigInteger(-1).toUnsignedInt()); //error | |
103 | TEST(BigInteger(0).toUnsignedInt()); //0 | |
104 | TEST(BigInteger(4294967295U).toUnsignedInt()); //4294967295 | |
105 | TEST(stringToBigInteger("4294967296").toUnsignedInt()); //error | |
106 | ||
107 | TEST(stringToBigInteger("-2147483649").toInt()); //error | |
108 | TEST(stringToBigInteger("-2147483648").toInt()); //-2147483648 | |
109 | TEST(BigInteger(-2147483647).toInt()); //-2147483647 | |
110 | TEST(BigInteger(0).toInt()); //0 | |
111 | TEST(BigInteger(2147483647).toInt()); //2147483647 | |
112 | TEST(BigInteger(2147483648U).toInt()); //error | |
113 | ||
114 | TEST(BigInteger(-1).toUnsignedShort()); //error | |
115 | TEST(BigInteger(0).toUnsignedShort()); //0 | |
116 | TEST(BigInteger(65535).toUnsignedShort()); //65535 | |
117 | TEST(BigInteger(65536).toUnsignedShort()); //error | |
118 | ||
119 | TEST(BigInteger(-32769).toShort()); //error | |
120 | TEST(BigInteger(-32768).toShort()); //-32768 | |
121 | TEST(BigInteger(-32767).toShort()); //-32767 | |
122 | TEST(BigInteger(0).toShort()); //0 | |
123 | TEST(BigInteger(32767).toShort()); //32767 | |
124 | TEST(BigInteger(32768).toShort()); //error | |
706f6a7e MM |
125 | |
126 | // Negative BigUnsigneds | |
e6866cd0 MM |
127 | // ...during construction |
128 | TEST(BigUnsigned(short(-1))); //error | |
129 | TEST(BigUnsigned(pathologicalShort)); //error | |
130 | TEST(BigUnsigned(-1)); //error | |
131 | TEST(BigUnsigned(pathologicalInt)); //error | |
132 | TEST(BigUnsigned(long(-1))); //error | |
133 | TEST(BigUnsigned(pathologicalLong)); //error | |
134 | // ...during subtraction | |
135 | TEST(BigUnsigned(5) - BigUnsigned(6)); //error | |
136 | TEST(stringToBigUnsigned("314159265358979323") - stringToBigUnsigned("314159265358979324")); //error | |
137 | TEST(check(BigUnsigned(5) - BigUnsigned(5))); //0 | |
138 | TEST(check(stringToBigUnsigned("314159265358979323") - stringToBigUnsigned("314159265358979323"))); //0 | |
139 | TEST(check(stringToBigUnsigned("4294967296") - BigUnsigned(1))); //4294967295 | |
140 | ||
141 | // Addition | |
142 | TEST(check(BigUnsigned(0) + 0)); //0 | |
143 | TEST(check(BigUnsigned(0) + 1)); //1 | |
144 | // Ordinary carry | |
145 | TEST(check(stringToBigUnsigned("8589934591" /* 2^33 - 1*/) | |
146 | + stringToBigUnsigned("4294967298" /* 2^32 + 2 */))); //12884901889 | |
147 | // Creation of a new block | |
148 | TEST(check(BigUnsigned(0xFFFFFFFFU) + 1)); //4294967296 | |
149 | ||
150 | // Subtraction | |
151 | TEST(check(BigUnsigned(1) - 0)); //1 | |
152 | TEST(check(BigUnsigned(1) - 1)); //0 | |
153 | TEST(check(BigUnsigned(2) - 1)); //1 | |
154 | // Ordinary borrow | |
155 | TEST(check(stringToBigUnsigned("12884901889") | |
156 | - stringToBigUnsigned("4294967298"))); //8589934591 | |
157 | // Borrow that removes a block | |
158 | TEST(check(stringToBigUnsigned("4294967296") - 1)); //4294967295 | |
706f6a7e MM |
159 | |
160 | // Multiplication and division | |
161 | BigUnsigned a = check(BigUnsigned(314159265) * 358979323); | |
e6866cd0 MM |
162 | TEST(a); //112776680263877595 |
163 | TEST(a / 123); //916883579381118 | |
164 | TEST(a % 123); //81 | |
165 | ||
166 | TEST(BigUnsigned(5) / 0); //error | |
167 | ||
168 | BigUnsigned p1 = BigUnsigned(3) * 5; | |
169 | TEST(p1); //15 | |
170 | /* In this case, we would like g++ to implicitly promote the BigUnsigned to a | |
171 | * BigInteger, but it seems to prefer converting the -5 to a BigUnsigned, which | |
172 | * causes an error. If I take out constructors for BigUnsigned from signed | |
173 | * primitive integers, the BigUnsigned(3) becomes ambiguous, and if I take out | |
174 | * all the constructors but BigUnsigned(unsigned long), g++ uses that | |
175 | * constructor and gets a wrong (positive) answer. Thus, I think we'll just | |
176 | * have to live with this cast. */ | |
177 | BigInteger p2 = BigInteger(BigUnsigned(3)) * -5; | |
178 | TEST(p2); //-15 | |
706f6a7e MM |
179 | |
180 | { | |
181 | /* Test that BigInteger division sets the sign to zero. | |
182 | * Bug reported by David Allen. */ | |
183 | BigInteger num(3), denom(5), quotient; | |
184 | num.divideWithRemainder(denom, quotient); | |
185 | check(quotient); | |
186 | num = 5; | |
187 | num.divideWithRemainder(denom, quotient); | |
188 | check(num); | |
189 | } | |
190 | ||
191 | { | |
192 | /* Test that BigInteger subtraction sets the sign properly. | |
193 | * Bug reported by Samuel Larkin. */ | |
194 | BigInteger zero(0), three(3), ans; | |
195 | ans = zero - three; | |
e6866cd0 | 196 | TEST(check(ans).getSign()); //-1 |
706f6a7e MM |
197 | } |
198 | ||
199 | { | |
200 | /* Test that BigInteger multiplication shifts bits properly on systems | |
201 | * where long is bigger than int. (Obviously, this would only catch the | |
202 | * bug when run on such a system.) | |
203 | * Bug reported by Mohand Mezmaz. */ | |
204 | BigInteger f=4; f*=3; | |
e6866cd0 | 205 | TEST(check(f)); //12 |
706f6a7e MM |
206 | } |
207 | ||
208 | { | |
209 | /* Test that bitwise XOR allocates the larger length. | |
210 | * Bug reported by Sriram Sankararaman. */ | |
211 | BigUnsigned a(0), b(3), ans; | |
212 | ans = a ^ b; | |
e6866cd0 | 213 | TEST(ans); //3 |
706f6a7e MM |
214 | } |
215 | ||
216 | { | |
217 | /* Test that an aliased multiplication works. | |
218 | * Bug reported by Boris Dessy. */ | |
219 | BigInteger num(5); | |
220 | num *= num; | |
e6866cd0 | 221 | TEST(check(num)); //25 |
706f6a7e MM |
222 | } |
223 | ||
224 | } catch (const char *err) { | |
e6866cd0 | 225 | cout << "UNCAUGHT ERROR: " << err << endl; |
706f6a7e MM |
226 | } |
227 | ||
0afe80d5 MM |
228 | return 0; |
229 | } |