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 // === Block-array constructors ===
65 BigUnsigned::Blk myBlocks
[3];
69 BigUnsigned
bu(myBlocks
, 3);
70 TEST(check(bu
)); //17179869187
71 TEST(check(BigInteger(myBlocks
, 3))); //17179869187
72 TEST(check(BigInteger(bu
))); //17179869187
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
82 // For zero magnitude, force the sign to zero without error.
83 BigUnsigned::Blk myZeroBlocks
[1];
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
89 // === BigUnsigned conversion limits ===
91 TEST(BigUnsigned(0).toUnsignedLong()); //0
92 TEST(BigUnsigned(4294967295U).toUnsignedLong()); //4294967295
93 TEST(stringToBigUnsigned("4294967296").toUnsignedLong()); //error
95 TEST(BigUnsigned(0).toLong()); //0
96 TEST(BigUnsigned(2147483647).toLong()); //2147483647
97 TEST(BigUnsigned(2147483648U).toLong()); //error
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
104 TEST(BigUnsigned(0).toInt()); //0
105 TEST(BigUnsigned(2147483647).toInt()); //2147483647
106 TEST(BigUnsigned(2147483648U).toInt()); //error
108 TEST(BigUnsigned(0).toUnsignedShort()); //0
109 TEST(BigUnsigned(65535).toUnsignedShort()); //65535
110 TEST(BigUnsigned(65536).toUnsignedShort()); //error
112 TEST(BigUnsigned(0).toShort()); //0
113 TEST(BigUnsigned(32767).toShort()); //32767
114 TEST(BigUnsigned(32768).toShort()); //error
116 // === BigInteger conversion limits ===
118 TEST(BigInteger(-1).toUnsignedLong()); //error
119 TEST(BigInteger(0).toUnsignedLong()); //0
120 TEST(BigInteger(4294967295U).toUnsignedLong()); //4294967295
121 TEST(stringToBigInteger("4294967296").toUnsignedLong()); //error
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
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
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
143 TEST(BigInteger(-1).toUnsignedShort()); //error
144 TEST(BigInteger(0).toUnsignedShort()); //0
145 TEST(BigInteger(65535).toUnsignedShort()); //65535
146 TEST(BigInteger(65536).toUnsignedShort()); //error
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
155 // === Negative BigUnsigneds ===
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
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
172 // === BigUnsigned addition ===
174 TEST(check(BigUnsigned(0) + 0)); //0
175 TEST(check(BigUnsigned(0) + 1)); //1
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
182 // === BigUnsigned subtraction ===
184 TEST(check(BigUnsigned(1) - 0)); //1
185 TEST(check(BigUnsigned(1) - 1)); //0
186 TEST(check(BigUnsigned(2) - 1)); //1
188 TEST(check(stringToBigUnsigned("12884901889")
189 - stringToBigUnsigned("4294967298"))); //8589934591
190 // Borrow that removes a block
191 TEST(check(stringToBigUnsigned("4294967296") - 1)); //4294967295
193 // === BigUnsigned multiplication and division ===
195 BigUnsigned a
= check(BigUnsigned(314159265) * 358979323);
196 TEST(a
); //112776680263877595
197 TEST(a
/ 123); //916883579381118
200 TEST(BigUnsigned(5) / 0); //error
202 // === Block accessors ===
206 TEST(b
.getBlock(0)); //0
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?
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.
225 TEST(bb
.getBlock(0)); //3
226 TEST(bb
.getBlock(1)); //0
227 TEST(bb
.getBlock(2)); //0
228 TEST(bb
.getBlock(314159)); //0
230 // === Bit accessors ===
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
239 // 25 is binary 11001.
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
254 // === Combining BigUnsigned, BigInteger, and primitive integers ===
256 BigUnsigned p1
= BigUnsigned(3) * 5;
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;
268 // === Test some previous bugs ===
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
);
277 num
.divideWithRemainder(denom
, quotient
);
282 /* Test that BigInteger subtraction sets the sign properly.
283 * Bug reported by Samuel Larkin. */
284 BigInteger
zero(0), three(3), ans
;
286 TEST(check(ans
).getSign()); //-1
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;
299 /* Test that bitwise XOR allocates the larger length.
300 * Bug reported by Sriram Sankararaman. */
301 BigUnsigned
a(0), b(3), ans
;
307 /* Test that an aliased multiplication works.
308 * Bug reported by Boris Dessy. */
311 TEST(check(num
)); //25
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
321 } catch (const char *err
) {
322 cout
<< "UNCAUGHT ERROR: " << err
<< endl
;