Initial check in of big integer library, v2010.04.30
[pdfium.git] / third_party / bigint / testsuite.cc
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.
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. */
7
8 #include "BigIntegerLibrary.hh"
9
10 #include <string>
11 #include <iostream>
12 using namespace std;
13
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
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;
31         return x;
32 }
33
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());
40         return x;
41 }
42
43 short pathologicalShort = ~((unsigned short)(~0) >> 1);
44 int pathologicalInt = ~((unsigned int)(~0) >> 1);
45 long pathologicalLong = ~((unsigned long)(~0) >> 1);
46
47 int main() {
48
49 try {
50
51 BigUnsigned z(0), one(1), ten(10);
52 TEST(z); //0
53 TEST(1); //1
54 TEST(10); //10
55
56 // TODO: Comprehensively test the general and special cases of each function.
57
58 // === Default constructors ===
59
60 TEST(check(BigUnsigned())); //0
61 TEST(check(BigInteger())); //0
62
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
89 // === BigUnsigned conversion limits ===
90
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
116 // === BigInteger conversion limits ===
117
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
154
155 // === Negative BigUnsigneds ===
156
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
164
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
172 // === BigUnsigned addition ===
173
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
182 // === BigUnsigned subtraction ===
183
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
192
193 // === BigUnsigned multiplication and division ===
194
195 BigUnsigned a = check(BigUnsigned(314159265) * 358979323);
196 TEST(a); //112776680263877595
197 TEST(a / 123); //916883579381118
198 TEST(a % 123); //81
199
200 TEST(BigUnsigned(5) / 0); //error
201
202 // === Block accessors ===
203
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
230 // === Bit accessors ===
231
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
254 // === Combining BigUnsigned, BigInteger, and primitive integers ===
255
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
267
268 // === Test some previous bugs ===
269
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;
286         TEST(check(ans).getSign()); //-1
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;
295         TEST(check(f)); //12
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;
303         TEST(ans); //3
304 }
305
306 {
307         /* Test that an aliased multiplication works.
308          * Bug reported by Boris Dessy. */
309         BigInteger num(5);
310         num *= num;
311         TEST(check(num)); //25
312 }
313
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
321 } catch (const char *err) {
322         cout << "UNCAUGHT ERROR: " << err << endl;
323 }
324
325 return 0;
326 }