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
3 * expected output automatically extracted from slash-slash comments below.
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. */
8 #include "BigIntegerLibrary.hh"
14 // Evaluate expr and print the result or "error" as appropriate.
15 #define TEST(expr) do {\
16 cout << "Line " << __LINE__ << ": ";\
19 } catch (const char *err) {\
25 const BigUnsigned &check(const BigUnsigned &x) {
26 unsigned int l = x.getLength();
27 if (l != 0 && x.getBlock(l-1) == 0)
28 cout << "check: Unzapped number!" << endl;
29 if (l > x.getCapacity())
30 cout << "check: Capacity inconsistent with length!" << endl;
34 const BigInteger &check(const BigInteger &x) {
35 if (x.getSign() == 0 && !x.getMagnitude().isZero())
36 cout << "check: Sign should not be zero!" << endl;
37 if (x.getSign() != 0 && x.getMagnitude().isZero())
38 cout << "check: Sign should be zero!" << endl;
39 check(x.getMagnitude());
43 short pathologicalShort = ~((unsigned short)(~0) >> 1);
44 int pathologicalInt = ~((unsigned int)(~0) >> 1);
45 long pathologicalLong = ~((unsigned long)(~0) >> 1);
51 BigUnsigned z(0), one(1), ten(10);
56 // TODO: Comprehensively test the general and special cases of each function.
58 // === Default constructors ===
60 TEST(check(BigUnsigned())); //0
61 TEST(check(BigInteger())); //0
63 // === BigUnsigned conversion limits ===
65 TEST(BigUnsigned(0).toUnsignedLong()); //0
66 TEST(BigUnsigned(4294967295U).toUnsignedLong()); //4294967295
67 TEST(stringToBigUnsigned("4294967296").toUnsignedLong()); //error
69 TEST(BigUnsigned(0).toLong()); //0
70 TEST(BigUnsigned(2147483647).toLong()); //2147483647
71 TEST(BigUnsigned(2147483648U).toLong()); //error
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
78 TEST(BigUnsigned(0).toInt()); //0
79 TEST(BigUnsigned(2147483647).toInt()); //2147483647
80 TEST(BigUnsigned(2147483648U).toInt()); //error
82 TEST(BigUnsigned(0).toUnsignedShort()); //0
83 TEST(BigUnsigned(65535).toUnsignedShort()); //65535
84 TEST(BigUnsigned(65536).toUnsignedShort()); //error
86 TEST(BigUnsigned(0).toShort()); //0
87 TEST(BigUnsigned(32767).toShort()); //32767
88 TEST(BigUnsigned(32768).toShort()); //error
90 // === BigInteger conversion limits ===
92 TEST(BigInteger(-1).toUnsignedLong()); //error
93 TEST(BigInteger(0).toUnsignedLong()); //0
94 TEST(BigInteger(4294967295U).toUnsignedLong()); //4294967295
95 TEST(stringToBigInteger("4294967296").toUnsignedLong()); //error
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
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
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
117 TEST(BigInteger(-1).toUnsignedShort()); //error
118 TEST(BigInteger(0).toUnsignedShort()); //0
119 TEST(BigInteger(65535).toUnsignedShort()); //65535
120 TEST(BigInteger(65536).toUnsignedShort()); //error
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
129 // === Negative BigUnsigneds ===
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
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
146 // === BigUnsigned addition ===
148 TEST(check(BigUnsigned(0) + 0)); //0
149 TEST(check(BigUnsigned(0) + 1)); //1
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
156 // === BigUnsigned subtraction ===
158 TEST(check(BigUnsigned(1) - 0)); //1
159 TEST(check(BigUnsigned(1) - 1)); //0
160 TEST(check(BigUnsigned(2) - 1)); //1
162 TEST(check(stringToBigUnsigned("12884901889")
163 - stringToBigUnsigned("4294967298"))); //8589934591
164 // Borrow that removes a block
165 TEST(check(stringToBigUnsigned("4294967296") - 1)); //4294967295
167 // === BigUnsigned multiplication and division ===
169 BigUnsigned a = check(BigUnsigned(314159265) * 358979323);
170 TEST(a); //112776680263877595
171 TEST(a / 123); //916883579381118
174 TEST(BigUnsigned(5) / 0); //error
176 // === Block accessors ===
180 TEST(b.getBlock(0)); //0
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?
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.
199 TEST(bb.getBlock(0)); //3
200 TEST(bb.getBlock(1)); //0
201 TEST(bb.getBlock(2)); //0
202 TEST(bb.getBlock(314159)); //0
204 // === Bit accessors ===
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
213 // 25 is binary 11001.
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
228 // === Combining BigUnsigned, BigInteger, and primitive integers ===
230 BigUnsigned p1 = BigUnsigned(3) * 5;
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;
242 // === Test some previous bugs ===
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);
251 num.divideWithRemainder(denom, quotient);
256 /* Test that BigInteger subtraction sets the sign properly.
257 * Bug reported by Samuel Larkin. */
258 BigInteger zero(0), three(3), ans;
260 TEST(check(ans).getSign()); //-1
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;
273 /* Test that bitwise XOR allocates the larger length.
274 * Bug reported by Sriram Sankararaman. */
275 BigUnsigned a(0), b(3), ans;
281 /* Test that an aliased multiplication works.
282 * Bug reported by Boris Dessy. */
285 TEST(check(num)); //25
288 } catch (const char *err) {
289 cout << "UNCAUGHT ERROR: " << err << endl;