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 | ||
82cba2ff MM |
58 | // === Default constructors === |
59 | ||
e6866cd0 MM |
60 | TEST(check(BigUnsigned())); //0 |
61 | TEST(check(BigInteger())); //0 | |
62 | ||
cb2f0c28 MM |
63 | // === Block-array constructors === |
64 | ||
65 | BigUnsigned::Blk myBlocks[3]; | |
66 | myBlocks[0] = 3; | |
67 | myBlocks[1] = 4; | |
68 | myBlocks[2] = 0; | |
69 | BigUnsigned bu(myBlocks, 3); | |
70 | TEST(check(bu)); //17179869187 | |
71 | TEST(check(BigInteger(myBlocks, 3))); //17179869187 | |
72 | TEST(check(BigInteger(bu ))); //17179869187 | |
73 | ||
74 | // For nonzero magnitude, reject zero and invalid signs. | |
75 | TEST(check(BigInteger(myBlocks, 3, BigInteger::positive))); //17179869187 | |
76 | TEST(check(BigInteger(myBlocks, 3, BigInteger::negative))); //-17179869187 | |
77 | TEST(check(BigInteger(myBlocks, 3, BigInteger::zero ))); //error | |
78 | TEST(check(BigInteger(bu, BigInteger::positive))); //17179869187 | |
79 | TEST(check(BigInteger(bu, BigInteger::negative))); //-17179869187 | |
80 | TEST(check(BigInteger(bu, BigInteger::zero ))); //error | |
81 | ||
82 | // For zero magnitude, force the sign to zero without error. | |
83 | BigUnsigned::Blk myZeroBlocks[1]; | |
84 | myZeroBlocks[0] = 0; | |
85 | TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::positive))); //0 | |
86 | TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::negative))); //0 | |
87 | TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::zero ))); //0 | |
88 | ||
82cba2ff MM |
89 | // === BigUnsigned conversion limits === |
90 | ||
e6866cd0 MM |
91 | TEST(BigUnsigned(0).toUnsignedLong()); //0 |
92 | TEST(BigUnsigned(4294967295U).toUnsignedLong()); //4294967295 | |
93 | TEST(stringToBigUnsigned("4294967296").toUnsignedLong()); //error | |
94 | ||
95 | TEST(BigUnsigned(0).toLong()); //0 | |
96 | TEST(BigUnsigned(2147483647).toLong()); //2147483647 | |
97 | TEST(BigUnsigned(2147483648U).toLong()); //error | |
98 | ||
99 | // int is the same as long on a 32-bit system | |
100 | TEST(BigUnsigned(0).toUnsignedInt()); //0 | |
101 | TEST(BigUnsigned(4294967295U).toUnsignedInt()); //4294967295 | |
102 | TEST(stringToBigUnsigned("4294967296").toUnsignedInt()); //error | |
103 | ||
104 | TEST(BigUnsigned(0).toInt()); //0 | |
105 | TEST(BigUnsigned(2147483647).toInt()); //2147483647 | |
106 | TEST(BigUnsigned(2147483648U).toInt()); //error | |
107 | ||
108 | TEST(BigUnsigned(0).toUnsignedShort()); //0 | |
109 | TEST(BigUnsigned(65535).toUnsignedShort()); //65535 | |
110 | TEST(BigUnsigned(65536).toUnsignedShort()); //error | |
111 | ||
112 | TEST(BigUnsigned(0).toShort()); //0 | |
113 | TEST(BigUnsigned(32767).toShort()); //32767 | |
114 | TEST(BigUnsigned(32768).toShort()); //error | |
115 | ||
82cba2ff MM |
116 | // === BigInteger conversion limits === |
117 | ||
e6866cd0 MM |
118 | TEST(BigInteger(-1).toUnsignedLong()); //error |
119 | TEST(BigInteger(0).toUnsignedLong()); //0 | |
120 | TEST(BigInteger(4294967295U).toUnsignedLong()); //4294967295 | |
121 | TEST(stringToBigInteger("4294967296").toUnsignedLong()); //error | |
122 | ||
123 | TEST(stringToBigInteger("-2147483649").toLong()); //error | |
124 | TEST(stringToBigInteger("-2147483648").toLong()); //-2147483648 | |
125 | TEST(BigInteger(-2147483647).toLong()); //-2147483647 | |
126 | TEST(BigInteger(0).toLong()); //0 | |
127 | TEST(BigInteger(2147483647).toLong()); //2147483647 | |
128 | TEST(BigInteger(2147483648U).toLong()); //error | |
129 | ||
130 | // int is the same as long on a 32-bit system | |
131 | TEST(BigInteger(-1).toUnsignedInt()); //error | |
132 | TEST(BigInteger(0).toUnsignedInt()); //0 | |
133 | TEST(BigInteger(4294967295U).toUnsignedInt()); //4294967295 | |
134 | TEST(stringToBigInteger("4294967296").toUnsignedInt()); //error | |
135 | ||
136 | TEST(stringToBigInteger("-2147483649").toInt()); //error | |
137 | TEST(stringToBigInteger("-2147483648").toInt()); //-2147483648 | |
138 | TEST(BigInteger(-2147483647).toInt()); //-2147483647 | |
139 | TEST(BigInteger(0).toInt()); //0 | |
140 | TEST(BigInteger(2147483647).toInt()); //2147483647 | |
141 | TEST(BigInteger(2147483648U).toInt()); //error | |
142 | ||
143 | TEST(BigInteger(-1).toUnsignedShort()); //error | |
144 | TEST(BigInteger(0).toUnsignedShort()); //0 | |
145 | TEST(BigInteger(65535).toUnsignedShort()); //65535 | |
146 | TEST(BigInteger(65536).toUnsignedShort()); //error | |
147 | ||
148 | TEST(BigInteger(-32769).toShort()); //error | |
149 | TEST(BigInteger(-32768).toShort()); //-32768 | |
150 | TEST(BigInteger(-32767).toShort()); //-32767 | |
151 | TEST(BigInteger(0).toShort()); //0 | |
152 | TEST(BigInteger(32767).toShort()); //32767 | |
153 | TEST(BigInteger(32768).toShort()); //error | |
706f6a7e | 154 | |
82cba2ff MM |
155 | // === Negative BigUnsigneds === |
156 | ||
e6866cd0 MM |
157 | // ...during construction |
158 | TEST(BigUnsigned(short(-1))); //error | |
159 | TEST(BigUnsigned(pathologicalShort)); //error | |
160 | TEST(BigUnsigned(-1)); //error | |
161 | TEST(BigUnsigned(pathologicalInt)); //error | |
162 | TEST(BigUnsigned(long(-1))); //error | |
163 | TEST(BigUnsigned(pathologicalLong)); //error | |
82cba2ff | 164 | |
e6866cd0 MM |
165 | // ...during subtraction |
166 | TEST(BigUnsigned(5) - BigUnsigned(6)); //error | |
167 | TEST(stringToBigUnsigned("314159265358979323") - stringToBigUnsigned("314159265358979324")); //error | |
168 | TEST(check(BigUnsigned(5) - BigUnsigned(5))); //0 | |
169 | TEST(check(stringToBigUnsigned("314159265358979323") - stringToBigUnsigned("314159265358979323"))); //0 | |
170 | TEST(check(stringToBigUnsigned("4294967296") - BigUnsigned(1))); //4294967295 | |
171 | ||
82cba2ff MM |
172 | // === BigUnsigned addition === |
173 | ||
e6866cd0 MM |
174 | TEST(check(BigUnsigned(0) + 0)); //0 |
175 | TEST(check(BigUnsigned(0) + 1)); //1 | |
176 | // Ordinary carry | |
177 | TEST(check(stringToBigUnsigned("8589934591" /* 2^33 - 1*/) | |
178 | + stringToBigUnsigned("4294967298" /* 2^32 + 2 */))); //12884901889 | |
179 | // Creation of a new block | |
180 | TEST(check(BigUnsigned(0xFFFFFFFFU) + 1)); //4294967296 | |
181 | ||
82cba2ff MM |
182 | // === BigUnsigned subtraction === |
183 | ||
e6866cd0 MM |
184 | TEST(check(BigUnsigned(1) - 0)); //1 |
185 | TEST(check(BigUnsigned(1) - 1)); //0 | |
186 | TEST(check(BigUnsigned(2) - 1)); //1 | |
187 | // Ordinary borrow | |
188 | TEST(check(stringToBigUnsigned("12884901889") | |
189 | - stringToBigUnsigned("4294967298"))); //8589934591 | |
190 | // Borrow that removes a block | |
191 | TEST(check(stringToBigUnsigned("4294967296") - 1)); //4294967295 | |
706f6a7e | 192 | |
82cba2ff MM |
193 | // === BigUnsigned multiplication and division === |
194 | ||
706f6a7e | 195 | BigUnsigned a = check(BigUnsigned(314159265) * 358979323); |
e6866cd0 MM |
196 | TEST(a); //112776680263877595 |
197 | TEST(a / 123); //916883579381118 | |
198 | TEST(a % 123); //81 | |
199 | ||
200 | TEST(BigUnsigned(5) / 0); //error | |
201 | ||
82cba2ff MM |
202 | // === Block accessors === |
203 | ||
88dbe518 MM |
204 | BigUnsigned b; |
205 | TEST(b); //0 | |
206 | TEST(b.getBlock(0)); //0 | |
207 | b.setBlock(1, 314); | |
208 | // Did b grow properly? And did we zero intermediate blocks? | |
209 | TEST(check(b)); //1348619730944 | |
210 | TEST(b.getLength()); //2 | |
211 | TEST(b.getBlock(0)); //0 | |
212 | TEST(b.getBlock(1)); //314 | |
213 | // Did b shrink properly? | |
214 | b.setBlock(1, 0); | |
215 | TEST(check(b)); //0 | |
216 | ||
217 | BigUnsigned bb(314); | |
218 | bb.setBlock(1, 159); | |
219 | // Make sure we used allocateAndCopy, not allocate | |
220 | TEST(bb.getBlock(0)); //314 | |
221 | TEST(bb.getBlock(1)); //159 | |
222 | // Blocks beyond the number should be zero regardless of whether they are | |
223 | // within the capacity. | |
224 | bb.add(1, 2); | |
225 | TEST(bb.getBlock(0)); //3 | |
226 | TEST(bb.getBlock(1)); //0 | |
227 | TEST(bb.getBlock(2)); //0 | |
228 | TEST(bb.getBlock(314159)); //0 | |
229 | ||
82cba2ff MM |
230 | // === Bit accessors === |
231 | ||
88dbe518 MM |
232 | TEST(BigUnsigned(0).bitLength()); //0 |
233 | TEST(BigUnsigned(1).bitLength()); //1 | |
234 | TEST(BigUnsigned(4095).bitLength()); //12 | |
235 | TEST(BigUnsigned(4096).bitLength()); //13 | |
236 | // 5 billion is between 2^32 (about 4 billion) and 2^33 (about 8 billion). | |
237 | TEST(stringToBigUnsigned("5000000000").bitLength()); //33 | |
238 | ||
239 | // 25 is binary 11001. | |
240 | BigUnsigned bbb(25); | |
241 | TEST(bbb.getBit(4)); //1 | |
242 | TEST(bbb.getBit(3)); //1 | |
243 | TEST(bbb.getBit(2)); //0 | |
244 | TEST(bbb.getBit(1)); //0 | |
245 | TEST(bbb.getBit(0)); //1 | |
246 | TEST(bbb.bitLength()); //5 | |
247 | // Effectively add 2^32. | |
248 | bbb.setBit(32, true); | |
249 | TEST(bbb); //4294967321 | |
250 | bbb.setBit(31, true); | |
251 | bbb.setBit(32, false); | |
252 | TEST(check(bbb)); //2147483673 | |
253 | ||
82cba2ff MM |
254 | // === Combining BigUnsigned, BigInteger, and primitive integers === |
255 | ||
e6866cd0 MM |
256 | BigUnsigned p1 = BigUnsigned(3) * 5; |
257 | TEST(p1); //15 | |
258 | /* In this case, we would like g++ to implicitly promote the BigUnsigned to a | |
259 | * BigInteger, but it seems to prefer converting the -5 to a BigUnsigned, which | |
260 | * causes an error. If I take out constructors for BigUnsigned from signed | |
261 | * primitive integers, the BigUnsigned(3) becomes ambiguous, and if I take out | |
262 | * all the constructors but BigUnsigned(unsigned long), g++ uses that | |
263 | * constructor and gets a wrong (positive) answer. Thus, I think we'll just | |
264 | * have to live with this cast. */ | |
265 | BigInteger p2 = BigInteger(BigUnsigned(3)) * -5; | |
266 | TEST(p2); //-15 | |
706f6a7e | 267 | |
82cba2ff MM |
268 | // === Test some previous bugs === |
269 | ||
706f6a7e MM |
270 | { |
271 | /* Test that BigInteger division sets the sign to zero. | |
272 | * Bug reported by David Allen. */ | |
273 | BigInteger num(3), denom(5), quotient; | |
274 | num.divideWithRemainder(denom, quotient); | |
275 | check(quotient); | |
276 | num = 5; | |
277 | num.divideWithRemainder(denom, quotient); | |
278 | check(num); | |
279 | } | |
280 | ||
281 | { | |
282 | /* Test that BigInteger subtraction sets the sign properly. | |
283 | * Bug reported by Samuel Larkin. */ | |
284 | BigInteger zero(0), three(3), ans; | |
285 | ans = zero - three; | |
e6866cd0 | 286 | TEST(check(ans).getSign()); //-1 |
706f6a7e MM |
287 | } |
288 | ||
289 | { | |
290 | /* Test that BigInteger multiplication shifts bits properly on systems | |
291 | * where long is bigger than int. (Obviously, this would only catch the | |
292 | * bug when run on such a system.) | |
293 | * Bug reported by Mohand Mezmaz. */ | |
294 | BigInteger f=4; f*=3; | |
e6866cd0 | 295 | TEST(check(f)); //12 |
706f6a7e MM |
296 | } |
297 | ||
298 | { | |
299 | /* Test that bitwise XOR allocates the larger length. | |
300 | * Bug reported by Sriram Sankararaman. */ | |
301 | BigUnsigned a(0), b(3), ans; | |
302 | ans = a ^ b; | |
e6866cd0 | 303 | TEST(ans); //3 |
706f6a7e MM |
304 | } |
305 | ||
306 | { | |
307 | /* Test that an aliased multiplication works. | |
308 | * Bug reported by Boris Dessy. */ | |
309 | BigInteger num(5); | |
310 | num *= num; | |
e6866cd0 | 311 | TEST(check(num)); //25 |
706f6a7e MM |
312 | } |
313 | ||
79881c05 MM |
314 | { |
315 | /* Test that BigUnsignedInABase(std::string) constructor rejects digits | |
316 | * too big for the specified base. | |
317 | * Bug reported by Niakam Kazemi. */ | |
318 | TEST(BigUnsignedInABase("f", 10)); //error | |
319 | } | |
320 | ||
706f6a7e | 321 | } catch (const char *err) { |
e6866cd0 | 322 | cout << "UNCAUGHT ERROR: " << err << endl; |
706f6a7e MM |
323 | } |
324 | ||
0afe80d5 MM |
325 | return 0; |
326 | } |