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