| 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 | // === BigUnsigned conversion limits === |
| 64 | |
| 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 | |
| 90 | // === BigInteger conversion limits === |
| 91 | |
| 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 |
| 128 | |
| 129 | // === Negative BigUnsigneds === |
| 130 | |
| 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 |
| 138 | |
| 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 | |
| 146 | // === BigUnsigned addition === |
| 147 | |
| 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 | |
| 156 | // === BigUnsigned subtraction === |
| 157 | |
| 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 |
| 166 | |
| 167 | // === BigUnsigned multiplication and division === |
| 168 | |
| 169 | BigUnsigned a = check(BigUnsigned(314159265) * 358979323); |
| 170 | TEST(a); //112776680263877595 |
| 171 | TEST(a / 123); //916883579381118 |
| 172 | TEST(a % 123); //81 |
| 173 | |
| 174 | TEST(BigUnsigned(5) / 0); //error |
| 175 | |
| 176 | // === Block accessors === |
| 177 | |
| 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 | |
| 204 | // === Bit accessors === |
| 205 | |
| 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 | |
| 228 | // === Combining BigUnsigned, BigInteger, and primitive integers === |
| 229 | |
| 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 |
| 241 | |
| 242 | // === Test some previous bugs === |
| 243 | |
| 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; |
| 260 | TEST(check(ans).getSign()); //-1 |
| 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; |
| 269 | TEST(check(f)); //12 |
| 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; |
| 277 | TEST(ans); //3 |
| 278 | } |
| 279 | |
| 280 | { |
| 281 | /* Test that an aliased multiplication works. |
| 282 | * Bug reported by Boris Dessy. */ |
| 283 | BigInteger num(5); |
| 284 | num *= num; |
| 285 | TEST(check(num)); //25 |
| 286 | } |
| 287 | |
| 288 | } catch (const char *err) { |
| 289 | cout << "UNCAUGHT ERROR: " << err << endl; |
| 290 | } |
| 291 | |
| 292 | return 0; |
| 293 | } |