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
59 TEST(check(BigUnsigned())); //0
60 TEST(check(BigInteger())); //0
62 // BigUnsigned conversion limits
63 TEST(BigUnsigned(0).toUnsignedLong()); //0
64 TEST(BigUnsigned(4294967295U).toUnsignedLong()); //4294967295
65 TEST(stringToBigUnsigned("4294967296").toUnsignedLong()); //error
67 TEST(BigUnsigned(0).toLong()); //0
68 TEST(BigUnsigned(2147483647).toLong()); //2147483647
69 TEST(BigUnsigned(2147483648U).toLong()); //error
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
76 TEST(BigUnsigned(0).toInt()); //0
77 TEST(BigUnsigned(2147483647).toInt()); //2147483647
78 TEST(BigUnsigned(2147483648U).toInt()); //error
80 TEST(BigUnsigned(0).toUnsignedShort()); //0
81 TEST(BigUnsigned(65535).toUnsignedShort()); //65535
82 TEST(BigUnsigned(65536).toUnsignedShort()); //error
84 TEST(BigUnsigned(0).toShort()); //0
85 TEST(BigUnsigned(32767).toShort()); //32767
86 TEST(BigUnsigned(32768).toShort()); //error
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
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
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
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
114 TEST(BigInteger(-1).toUnsignedShort()); //error
115 TEST(BigInteger(0).toUnsignedShort()); //0
116 TEST(BigInteger(65535).toUnsignedShort()); //65535
117 TEST(BigInteger(65536).toUnsignedShort()); //error
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
126 // Negative BigUnsigneds
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
142 TEST(check(BigUnsigned(0) + 0)); //0
143 TEST(check(BigUnsigned(0) + 1)); //1
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
151 TEST(check(BigUnsigned(1) - 0)); //1
152 TEST(check(BigUnsigned(1) - 1)); //0
153 TEST(check(BigUnsigned(2) - 1)); //1
155 TEST(check(stringToBigUnsigned("12884901889")
156 - stringToBigUnsigned("4294967298"))); //8589934591
157 // Borrow that removes a block
158 TEST(check(stringToBigUnsigned("4294967296") - 1)); //4294967295
160 // Multiplication and division
161 BigUnsigned a = check(BigUnsigned(314159265) * 358979323);
162 TEST(a); //112776680263877595
163 TEST(a / 123); //916883579381118
166 TEST(BigUnsigned(5) / 0); //error
171 TEST(b.getBlock(0)); //0
173 // Did b grow properly? And did we zero intermediate blocks?
174 TEST(check(b)); //1348619730944
175 TEST(b.getLength()); //2
176 TEST(b.getBlock(0)); //0
177 TEST(b.getBlock(1)); //314
178 // Did b shrink properly?
184 // Make sure we used allocateAndCopy, not allocate
185 TEST(bb.getBlock(0)); //314
186 TEST(bb.getBlock(1)); //159
187 // Blocks beyond the number should be zero regardless of whether they are
188 // within the capacity.
190 TEST(bb.getBlock(0)); //3
191 TEST(bb.getBlock(1)); //0
192 TEST(bb.getBlock(2)); //0
193 TEST(bb.getBlock(314159)); //0
196 TEST(BigUnsigned(0).bitLength()); //0
197 TEST(BigUnsigned(1).bitLength()); //1
198 TEST(BigUnsigned(4095).bitLength()); //12
199 TEST(BigUnsigned(4096).bitLength()); //13
200 // 5 billion is between 2^32 (about 4 billion) and 2^33 (about 8 billion).
201 TEST(stringToBigUnsigned("5000000000").bitLength()); //33
203 // 25 is binary 11001.
205 TEST(bbb.getBit(4)); //1
206 TEST(bbb.getBit(3)); //1
207 TEST(bbb.getBit(2)); //0
208 TEST(bbb.getBit(1)); //0
209 TEST(bbb.getBit(0)); //1
210 TEST(bbb.bitLength()); //5
211 // Effectively add 2^32.
212 bbb.setBit(32, true);
213 TEST(bbb); //4294967321
214 bbb.setBit(31, true);
215 bbb.setBit(32, false);
216 TEST(check(bbb)); //2147483673
218 BigUnsigned p1 = BigUnsigned(3) * 5;
220 /* In this case, we would like g++ to implicitly promote the BigUnsigned to a
221 * BigInteger, but it seems to prefer converting the -5 to a BigUnsigned, which
222 * causes an error. If I take out constructors for BigUnsigned from signed
223 * primitive integers, the BigUnsigned(3) becomes ambiguous, and if I take out
224 * all the constructors but BigUnsigned(unsigned long), g++ uses that
225 * constructor and gets a wrong (positive) answer. Thus, I think we'll just
226 * have to live with this cast. */
227 BigInteger p2 = BigInteger(BigUnsigned(3)) * -5;
231 /* Test that BigInteger division sets the sign to zero.
232 * Bug reported by David Allen. */
233 BigInteger num(3), denom(5), quotient;
234 num.divideWithRemainder(denom, quotient);
237 num.divideWithRemainder(denom, quotient);
242 /* Test that BigInteger subtraction sets the sign properly.
243 * Bug reported by Samuel Larkin. */
244 BigInteger zero(0), three(3), ans;
246 TEST(check(ans).getSign()); //-1
250 /* Test that BigInteger multiplication shifts bits properly on systems
251 * where long is bigger than int. (Obviously, this would only catch the
252 * bug when run on such a system.)
253 * Bug reported by Mohand Mezmaz. */
254 BigInteger f=4; f*=3;
259 /* Test that bitwise XOR allocates the larger length.
260 * Bug reported by Sriram Sankararaman. */
261 BigUnsigned a(0), b(3), ans;
267 /* Test that an aliased multiplication works.
268 * Bug reported by Boris Dessy. */
271 TEST(check(num)); //25
274 } catch (const char *err) {
275 cout << "UNCAUGHT ERROR: " << err << endl;