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 } catch (const char *err) {
 315         cout << "UNCAUGHT ERROR: " << err << endl;
 316 }
 317
 318 return 0;
 319 }