test-bignum.cc 54.7 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
// Copyright 2010 the V8 project authors. All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include <stdlib.h>

30
#include "src/init/v8.h"
31

32
#include "src/base/platform/platform.h"
33
#include "src/numbers/bignum.h"
34
#include "test/cctest/cctest.h"
35

36 37
namespace v8 {
namespace internal {
38
namespace test_bignum {
39 40 41 42

static const int kBufferSize = 1024;

static void AssignHexString(Bignum* bignum, const char* str) {
43
  bignum->AssignHexString(CStrVector(str));
44 45 46
}

static void AssignDecimalString(Bignum* bignum, const char* str) {
47
  bignum->AssignDecimalString(CStrVector(str));
48 49 50 51 52 53 54 55
}

TEST(Assign) {
  char buffer[kBufferSize];
  Bignum bignum;
  Bignum bignum2;
  bignum.AssignUInt16(0);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
56
  CHECK_EQ(0, strcmp("0", buffer));
57 58
  bignum.AssignUInt16(0xA);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
59
  CHECK_EQ(0, strcmp("A", buffer));
60 61
  bignum.AssignUInt16(0x20);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
62
  CHECK_EQ(0, strcmp("20", buffer));
63 64 65 66


  bignum.AssignUInt64(0);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
67
  CHECK_EQ(0, strcmp("0", buffer));
68 69
  bignum.AssignUInt64(0xA);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
70
  CHECK_EQ(0, strcmp("A", buffer));
71 72
  bignum.AssignUInt64(0x20);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
73
  CHECK_EQ(0, strcmp("20", buffer));
74 75
  bignum.AssignUInt64(0x100);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
76
  CHECK_EQ(0, strcmp("100", buffer));
77 78 79 80

  // The first real test, since this will not fit into one bigit.
  bignum.AssignUInt64(0x12345678);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
81
  CHECK_EQ(0, strcmp("12345678", buffer));
82

83
  uint64_t big = 0xFFFF'FFFF'FFFF'FFFF;
84 85
  bignum.AssignUInt64(big);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
86
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFFFFF", buffer));
87

88
  big = 0x1234'5678'9ABC'DEF0;
89 90
  bignum.AssignUInt64(big);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
91
  CHECK_EQ(0, strcmp("123456789ABCDEF0", buffer));
92 93 94

  bignum2.AssignBignum(bignum);
  CHECK(bignum2.ToHexString(buffer, kBufferSize));
95
  CHECK_EQ(0, strcmp("123456789ABCDEF0", buffer));
96 97 98

  AssignDecimalString(&bignum, "0");
  CHECK(bignum.ToHexString(buffer, kBufferSize));
99
  CHECK_EQ(0, strcmp("0", buffer));
100 101 102

  AssignDecimalString(&bignum, "1");
  CHECK(bignum.ToHexString(buffer, kBufferSize));
103
  CHECK_EQ(0, strcmp("1", buffer));
104 105 106

  AssignDecimalString(&bignum, "1234567890");
  CHECK(bignum.ToHexString(buffer, kBufferSize));
107
  CHECK_EQ(0, strcmp("499602D2", buffer));
108 109 110

  AssignHexString(&bignum, "0");
  CHECK(bignum.ToHexString(buffer, kBufferSize));
111
  CHECK_EQ(0, strcmp("0", buffer));
112 113 114

  AssignHexString(&bignum, "123456789ABCDEF0");
  CHECK(bignum.ToHexString(buffer, kBufferSize));
115
  CHECK_EQ(0, strcmp("123456789ABCDEF0", buffer));
116 117 118 119 120 121 122 123 124
}


TEST(ShiftLeft) {
  char buffer[kBufferSize];
  Bignum bignum;
  AssignHexString(&bignum, "0");
  bignum.ShiftLeft(100);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
125
  CHECK_EQ(0, strcmp("0", buffer));
126 127 128 129

  AssignHexString(&bignum, "1");
  bignum.ShiftLeft(1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
130
  CHECK_EQ(0, strcmp("2", buffer));
131 132 133 134

  AssignHexString(&bignum, "1");
  bignum.ShiftLeft(4);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
135
  CHECK_EQ(0, strcmp("10", buffer));
136 137 138 139

  AssignHexString(&bignum, "1");
  bignum.ShiftLeft(32);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
140
  CHECK_EQ(0, strcmp("100000000", buffer));
141 142 143 144

  AssignHexString(&bignum, "1");
  bignum.ShiftLeft(64);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
145
  CHECK_EQ(0, strcmp("10000000000000000", buffer));
146 147 148 149

  AssignHexString(&bignum, "123456789ABCDEF");
  bignum.ShiftLeft(64);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
150
  CHECK_EQ(0, strcmp("123456789ABCDEF0000000000000000", buffer));
151 152
  bignum.ShiftLeft(1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
153
  CHECK_EQ(0, strcmp("2468ACF13579BDE0000000000000000", buffer));
154 155 156 157 158 159 160 161 162
}


TEST(AddUInt64) {
  char buffer[kBufferSize];
  Bignum bignum;
  AssignHexString(&bignum, "0");
  bignum.AddUInt64(0xA);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
163
  CHECK_EQ(0, strcmp("A", buffer));
164 165 166 167

  AssignHexString(&bignum, "1");
  bignum.AddUInt64(0xA);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
168
  CHECK_EQ(0, strcmp("B", buffer));
169 170 171 172

  AssignHexString(&bignum, "1");
  bignum.AddUInt64(0x100);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
173
  CHECK_EQ(0, strcmp("101", buffer));
174 175 176 177

  AssignHexString(&bignum, "1");
  bignum.AddUInt64(0xFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
178
  CHECK_EQ(0, strcmp("10000", buffer));
179 180 181 182

  AssignHexString(&bignum, "FFFFFFF");
  bignum.AddUInt64(0x1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
183
  CHECK_EQ(0, strcmp("10000000", buffer));
184 185 186 187

  AssignHexString(&bignum, "10000000000000000000000000000000000000000000");
  bignum.AddUInt64(0xFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
188
  CHECK_EQ(0, strcmp("1000000000000000000000000000000000000000FFFF", buffer));
189 190 191 192

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
  bignum.AddUInt64(0x1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
193
  CHECK_EQ(0, strcmp("100000000000000000000000000000000000000000000", buffer));
194 195 196 197 198

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  bignum.AddUInt64(1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
199
  CHECK_EQ(0, strcmp("10000000000000000000000001", buffer));
200 201 202 203 204

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  bignum.AddUInt64(0xFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
205
  CHECK_EQ(0, strcmp("1000000000000000000000FFFF", buffer));
206 207

  AssignHexString(&bignum, "0");
208
  bignum.AddUInt64(0xA'0000'0000);
209
  CHECK(bignum.ToHexString(buffer, kBufferSize));
210
  CHECK_EQ(0, strcmp("A00000000", buffer));
211 212

  AssignHexString(&bignum, "1");
213
  bignum.AddUInt64(0xA'0000'0000);
214
  CHECK(bignum.ToHexString(buffer, kBufferSize));
215
  CHECK_EQ(0, strcmp("A00000001", buffer));
216 217

  AssignHexString(&bignum, "1");
218
  bignum.AddUInt64(0x100'0000'0000);
219
  CHECK(bignum.ToHexString(buffer, kBufferSize));
220
  CHECK_EQ(0, strcmp("10000000001", buffer));
221 222

  AssignHexString(&bignum, "1");
223
  bignum.AddUInt64(0xFFFF'0000'0000);
224
  CHECK(bignum.ToHexString(buffer, kBufferSize));
225
  CHECK_EQ(0, strcmp("FFFF00000001", buffer));
226 227

  AssignHexString(&bignum, "FFFFFFF");
228
  bignum.AddUInt64(0x1'0000'0000);
229
  CHECK(bignum.ToHexString(buffer, kBufferSize));
230
  CHECK_EQ(0, strcmp("10FFFFFFF", buffer));
231 232

  AssignHexString(&bignum, "10000000000000000000000000000000000000000000");
233
  bignum.AddUInt64(0xFFFF'0000'0000);
234
  CHECK(bignum.ToHexString(buffer, kBufferSize));
235
  CHECK_EQ(0, strcmp("10000000000000000000000000000000FFFF00000000", buffer));
236 237

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
238
  bignum.AddUInt64(0x1'0000'0000);
239
  CHECK(bignum.ToHexString(buffer, kBufferSize));
240
  CHECK_EQ(0, strcmp("1000000000000000000000000000000000000FFFFFFFF", buffer));
241 242 243

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
244
  bignum.AddUInt64(0x1'0000'0000);
245
  CHECK(bignum.ToHexString(buffer, kBufferSize));
246
  CHECK_EQ(0, strcmp("10000000000000000100000000", buffer));
247 248 249

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
250
  bignum.AddUInt64(0xFFFF'0000'0000);
251
  CHECK(bignum.ToHexString(buffer, kBufferSize));
252
  CHECK_EQ(0, strcmp("10000000000000FFFF00000000", buffer));
253 254 255 256 257 258 259 260 261 262 263 264
}


TEST(AddBignum) {
  char buffer[kBufferSize];
  Bignum bignum;
  Bignum other;

  AssignHexString(&other, "1");
  AssignHexString(&bignum, "0");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
265
  CHECK_EQ(0, strcmp("1", buffer));
266 267 268 269

  AssignHexString(&bignum, "1");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
270
  CHECK_EQ(0, strcmp("2", buffer));
271 272 273 274

  AssignHexString(&bignum, "FFFFFFF");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
275
  CHECK_EQ(0, strcmp("10000000", buffer));
276 277 278 279

  AssignHexString(&bignum, "FFFFFFFFFFFFFF");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
280
  CHECK_EQ(0, strcmp("100000000000000", buffer));
281 282 283 284

  AssignHexString(&bignum, "10000000000000000000000000000000000000000000");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
285
  CHECK_EQ(0, strcmp("10000000000000000000000000000000000000000001", buffer));
286 287 288 289 290 291

  AssignHexString(&other, "1000000000000");

  AssignHexString(&bignum, "1");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
292
  CHECK_EQ(0, strcmp("1000000000001", buffer));
293 294 295 296

  AssignHexString(&bignum, "FFFFFFF");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
297
  CHECK_EQ(0, strcmp("100000FFFFFFF", buffer));
298 299 300 301

  AssignHexString(&bignum, "10000000000000000000000000000000000000000000");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
302
  CHECK_EQ(0, strcmp("10000000000000000000000000000001000000000000", buffer));
303 304 305 306

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
307
  CHECK_EQ(0, strcmp("1000000000000000000000000000000FFFFFFFFFFFF", buffer));
308 309 310 311 312

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
313
  CHECK_EQ(0, strcmp("10000000000001000000000000", buffer));
314 315 316 317 318 319 320

  other.ShiftLeft(64);
  // other == "10000000000000000000000000000"

  bignum.AssignUInt16(0x1);
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
321
  CHECK_EQ(0, strcmp("10000000000000000000000000001", buffer));
322 323 324 325

  AssignHexString(&bignum, "FFFFFFF");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
326
  CHECK_EQ(0, strcmp("1000000000000000000000FFFFFFF", buffer));
327 328 329 330

  AssignHexString(&bignum, "10000000000000000000000000000000000000000000");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
331
  CHECK_EQ(0, strcmp("10000000000000010000000000000000000000000000", buffer));
332 333 334 335

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
336
  CHECK_EQ(0, strcmp("100000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFF", buffer));
337 338 339 340 341

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  bignum.AddBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
342
  CHECK_EQ(0, strcmp("10010000000000000000000000000", buffer));
343 344 345 346 347 348 349 350 351 352 353 354
}


TEST(SubtractBignum) {
  char buffer[kBufferSize];
  Bignum bignum;
  Bignum other;

  AssignHexString(&bignum, "1");
  AssignHexString(&other, "0");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
355
  CHECK_EQ(0, strcmp("1", buffer));
356 357 358 359 360

  AssignHexString(&bignum, "2");
  AssignHexString(&other, "0");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
361
  CHECK_EQ(0, strcmp("2", buffer));
362 363 364 365 366

  AssignHexString(&bignum, "10000000");
  AssignHexString(&other, "1");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
367
  CHECK_EQ(0, strcmp("FFFFFFF", buffer));
368 369 370 371 372

  AssignHexString(&bignum, "100000000000000");
  AssignHexString(&other, "1");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
373
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFFF", buffer));
374 375 376 377 378

  AssignHexString(&bignum, "10000000000000000000000000000000000000000001");
  AssignHexString(&other, "1");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
379
  CHECK_EQ(0, strcmp("10000000000000000000000000000000000000000000", buffer));
380 381 382 383 384

  AssignHexString(&bignum, "1000000000001");
  AssignHexString(&other, "1000000000000");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
385
  CHECK_EQ(0, strcmp("1", buffer));
386 387 388 389 390

  AssignHexString(&bignum, "100000FFFFFFF");
  AssignHexString(&other, "1000000000000");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
391
  CHECK_EQ(0, strcmp("FFFFFFF", buffer));
392 393 394 395 396

  AssignHexString(&bignum, "10000000000000000000000000000001000000000000");
  AssignHexString(&other, "1000000000000");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
397
  CHECK_EQ(0, strcmp("10000000000000000000000000000000000000000000", buffer));
398 399 400 401 402

  AssignHexString(&bignum, "1000000000000000000000000000000FFFFFFFFFFFF");
  AssignHexString(&other, "1000000000000");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
403
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", buffer));
404 405 406 407 408 409 410

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  // "10 0000 0000 0000 0000 0000 0000"
  AssignHexString(&other, "1000000000000");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
411
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFF000000000000", buffer));
412 413 414 415 416 417 418 419 420 421

  AssignHexString(&other, "1000000000000");
  other.ShiftLeft(48);
  // other == "1000000000000000000000000"

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  // bignum == "10000000000000000000000000"
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
422
  CHECK_EQ(0, strcmp("F000000000000000000000000", buffer));
423 424 425 426 427 428 429 430 431

  other.AssignUInt16(0x1);
  other.ShiftLeft(35);
  // other == "800000000"
  AssignHexString(&bignum, "FFFFFFF");
  bignum.ShiftLeft(60);
  // bignum = FFFFFFF000000000000000
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
432
  CHECK_EQ(0, strcmp("FFFFFFEFFFFFF800000000", buffer));
433 434 435 436

  AssignHexString(&bignum, "10000000000000000000000000000000000000000000");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
437
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF800000000", buffer));
438 439 440 441

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
  bignum.SubtractBignum(other);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
442
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFF", buffer));
443 444 445 446 447 448 449 450 451 452
}


TEST(MultiplyUInt32) {
  char buffer[kBufferSize];
  Bignum bignum;

  AssignHexString(&bignum, "0");
  bignum.MultiplyByUInt32(0x25);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
453
  CHECK_EQ(0, strcmp("0", buffer));
454 455 456 457

  AssignHexString(&bignum, "2");
  bignum.MultiplyByUInt32(0x5);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
458
  CHECK_EQ(0, strcmp("A", buffer));
459 460 461 462

  AssignHexString(&bignum, "10000000");
  bignum.MultiplyByUInt32(0x9);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
463
  CHECK_EQ(0, strcmp("90000000", buffer));
464 465 466 467

  AssignHexString(&bignum, "100000000000000");
  bignum.MultiplyByUInt32(0xFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
468
  CHECK_EQ(0, strcmp("FFFF00000000000000", buffer));
469 470 471 472

  AssignHexString(&bignum, "100000000000000");
  bignum.MultiplyByUInt32(0xFFFFFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
473
  CHECK_EQ(0, strcmp("FFFFFFFF00000000000000", buffer));
474 475 476 477

  AssignHexString(&bignum, "1234567ABCD");
  bignum.MultiplyByUInt32(0xFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
478
  CHECK_EQ(0, strcmp("12333335552433", buffer));
479 480 481 482

  AssignHexString(&bignum, "1234567ABCD");
  bignum.MultiplyByUInt32(0xFFFFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
483
  CHECK_EQ(0, strcmp("12345679998A985433", buffer));
484 485 486 487

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFF");
  bignum.MultiplyByUInt32(0x2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
488
  CHECK_EQ(0, strcmp("1FFFFFFFFFFFFFFFE", buffer));
489 490 491 492

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFF");
  bignum.MultiplyByUInt32(0x4);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
493
  CHECK_EQ(0, strcmp("3FFFFFFFFFFFFFFFC", buffer));
494 495 496 497

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFF");
  bignum.MultiplyByUInt32(0xF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
498
  CHECK_EQ(0, strcmp("EFFFFFFFFFFFFFFF1", buffer));
499 500 501 502

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFF");
  bignum.MultiplyByUInt32(0xFFFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
503
  CHECK_EQ(0, strcmp("FFFFFEFFFFFFFFFF000001", buffer));
504 505 506 507 508 509

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  // "10 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt32(2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
510
  CHECK_EQ(0, strcmp("20000000000000000000000000", buffer));
511 512 513 514 515 516

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  // "10 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt32(0xF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
517
  CHECK_EQ(0, strcmp("F0000000000000000000000000", buffer));
518 519 520 521 522 523

  bignum.AssignUInt16(0xFFFF);
  bignum.ShiftLeft(100);
  // "FFFF0 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt32(0xFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
524
  CHECK_EQ(0, strcmp("FFFE00010000000000000000000000000", buffer));
525 526 527 528 529 530

  bignum.AssignUInt16(0xFFFF);
  bignum.ShiftLeft(100);
  // "FFFF0 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt32(0xFFFFFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
531
  CHECK_EQ(0, strcmp("FFFEFFFF00010000000000000000000000000", buffer));
532 533 534 535 536 537

  bignum.AssignUInt16(0xFFFF);
  bignum.ShiftLeft(100);
  // "FFFF0 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt32(0xFFFFFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
538
  CHECK_EQ(0, strcmp("FFFEFFFF00010000000000000000000000000", buffer));
539 540 541 542

  AssignDecimalString(&bignum, "15611230384529777");
  bignum.MultiplyByUInt32(10000000);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
543
  CHECK_EQ(0, strcmp("210EDD6D4CDD2580EE80", buffer));
544 545 546 547 548 549 550 551 552 553
}


TEST(MultiplyUInt64) {
  char buffer[kBufferSize];
  Bignum bignum;

  AssignHexString(&bignum, "0");
  bignum.MultiplyByUInt64(0x25);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
554
  CHECK_EQ(0, strcmp("0", buffer));
555 556 557 558

  AssignHexString(&bignum, "2");
  bignum.MultiplyByUInt64(0x5);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
559
  CHECK_EQ(0, strcmp("A", buffer));
560 561 562 563

  AssignHexString(&bignum, "10000000");
  bignum.MultiplyByUInt64(0x9);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
564
  CHECK_EQ(0, strcmp("90000000", buffer));
565 566 567 568

  AssignHexString(&bignum, "100000000000000");
  bignum.MultiplyByUInt64(0xFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
569
  CHECK_EQ(0, strcmp("FFFF00000000000000", buffer));
570 571

  AssignHexString(&bignum, "100000000000000");
572
  bignum.MultiplyByUInt64(0xFFFF'FFFF'FFFF'FFFF);
573
  CHECK(bignum.ToHexString(buffer, kBufferSize));
574
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFFFFF00000000000000", buffer));
575 576 577 578

  AssignHexString(&bignum, "1234567ABCD");
  bignum.MultiplyByUInt64(0xFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
579
  CHECK_EQ(0, strcmp("12333335552433", buffer));
580 581

  AssignHexString(&bignum, "1234567ABCD");
582
  bignum.MultiplyByUInt64(0xFF'FFFF'FFFF);
583
  CHECK(bignum.ToHexString(buffer, kBufferSize));
584
  CHECK_EQ(0, strcmp("1234567ABCBDCBA985433", buffer));
585 586 587 588

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFF");
  bignum.MultiplyByUInt64(0x2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
589
  CHECK_EQ(0, strcmp("1FFFFFFFFFFFFFFFE", buffer));
590 591 592 593

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFF");
  bignum.MultiplyByUInt64(0x4);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
594
  CHECK_EQ(0, strcmp("3FFFFFFFFFFFFFFFC", buffer));
595 596 597 598

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFF");
  bignum.MultiplyByUInt64(0xF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
599
  CHECK_EQ(0, strcmp("EFFFFFFFFFFFFFFF1", buffer));
600 601

  AssignHexString(&bignum, "FFFFFFFFFFFFFFFF");
602
  bignum.MultiplyByUInt64(0xFFFF'FFFF'FFFF'FFFF);
603
  CHECK(bignum.ToHexString(buffer, kBufferSize));
604
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFFFFE0000000000000001", buffer));
605 606 607 608 609 610

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  // "10 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt64(2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
611
  CHECK_EQ(0, strcmp("20000000000000000000000000", buffer));
612 613 614 615 616 617

  bignum.AssignUInt16(0x1);
  bignum.ShiftLeft(100);
  // "10 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt64(0xF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
618
  CHECK_EQ(0, strcmp("F0000000000000000000000000", buffer));
619 620 621 622 623 624

  bignum.AssignUInt16(0xFFFF);
  bignum.ShiftLeft(100);
  // "FFFF0 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt64(0xFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
625
  CHECK_EQ(0, strcmp("FFFE00010000000000000000000000000", buffer));
626 627 628 629 630 631

  bignum.AssignUInt16(0xFFFF);
  bignum.ShiftLeft(100);
  // "FFFF0 0000 0000 0000 0000 0000 0000"
  bignum.MultiplyByUInt64(0xFFFFFFFF);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
632
  CHECK_EQ(0, strcmp("FFFEFFFF00010000000000000000000000000", buffer));
633 634 635 636

  bignum.AssignUInt16(0xFFFF);
  bignum.ShiftLeft(100);
  // "FFFF0 0000 0000 0000 0000 0000 0000"
637
  bignum.MultiplyByUInt64(0xFFFF'FFFF'FFFF'FFFF);
638
  CHECK(bignum.ToHexString(buffer, kBufferSize));
639
  CHECK_EQ(0, strcmp("FFFEFFFFFFFFFFFF00010000000000000000000000000", buffer));
640 641

  AssignDecimalString(&bignum, "15611230384529777");
642
  bignum.MultiplyByUInt64(0x8AC7'2304'89E8'0000);
643
  CHECK(bignum.ToHexString(buffer, kBufferSize));
644
  CHECK_EQ(0, strcmp("1E10EE4B11D15A7F3DE7F3C7680000", buffer));
645 646 647 648 649 650 651 652 653 654
}


TEST(MultiplyPowerOfTen) {
  char buffer[kBufferSize];
  Bignum bignum;

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
655
  CHECK_EQ(0, strcmp("3034", buffer));
656 657 658 659

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
660
  CHECK_EQ(0, strcmp("1E208", buffer));
661 662 663 664

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(3);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
665
  CHECK_EQ(0, strcmp("12D450", buffer));
666 667 668 669

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(4);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
670
  CHECK_EQ(0, strcmp("BC4B20", buffer));
671 672 673 674

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(5);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
675
  CHECK_EQ(0, strcmp("75AEF40", buffer));
676 677 678 679

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(6);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
680
  CHECK_EQ(0, strcmp("498D5880", buffer));
681 682 683 684

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(7);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
685
  CHECK_EQ(0, strcmp("2DF857500", buffer));
686 687 688 689

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(8);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
690
  CHECK_EQ(0, strcmp("1CBB369200", buffer));
691 692 693 694

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(9);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
695
  CHECK_EQ(0, strcmp("11F5021B400", buffer));
696 697 698 699

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(10);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
700
  CHECK_EQ(0, strcmp("B3921510800", buffer));
701 702 703 704

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(11);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
705
  CHECK_EQ(0, strcmp("703B4D2A5000", buffer));
706 707 708 709

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(12);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
710
  CHECK_EQ(0, strcmp("4625103A72000", buffer));
711 712 713 714

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(13);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
715
  CHECK_EQ(0, strcmp("2BD72A24874000", buffer));
716 717 718 719

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(14);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
720
  CHECK_EQ(0, strcmp("1B667A56D488000", buffer));
721 722 723 724

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(15);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
725
  CHECK_EQ(0, strcmp("11200C7644D50000", buffer));
726 727 728 729

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(16);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
730
  CHECK_EQ(0, strcmp("AB407C9EB0520000", buffer));
731 732 733 734

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(17);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
735
  CHECK_EQ(0, strcmp("6B084DE32E3340000", buffer));
736 737 738 739

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(18);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
740
  CHECK_EQ(0, strcmp("42E530ADFCE0080000", buffer));
741 742 743 744

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(19);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
745
  CHECK_EQ(0, strcmp("29CF3E6CBE0C0500000", buffer));
746 747 748 749

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(20);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
750
  CHECK_EQ(0, strcmp("1A218703F6C783200000", buffer));
751 752 753 754

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(21);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
755
  CHECK_EQ(0, strcmp("1054F4627A3CB1F400000", buffer));
756 757 758 759

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(22);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
760
  CHECK_EQ(0, strcmp("A3518BD8C65EF38800000", buffer));
761 762 763 764

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(23);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
765
  CHECK_EQ(0, strcmp("6612F7677BFB5835000000", buffer));
766 767 768 769

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(24);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
770
  CHECK_EQ(0, strcmp("3FCBDAA0AD7D17212000000", buffer));
771 772 773 774

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(25);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
775
  CHECK_EQ(0, strcmp("27DF68A46C6E2E74B4000000", buffer));
776 777 778 779

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(26);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
780
  CHECK_EQ(0, strcmp("18EBA166C3C4DD08F08000000", buffer));
781 782 783 784

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(27);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
785
  CHECK_EQ(0, strcmp("F9344E03A5B0A259650000000", buffer));
786 787 788 789

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(28);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
790
  CHECK_EQ(0, strcmp("9BC0B0C2478E6577DF20000000", buffer));
791 792 793 794

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(29);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
795
  CHECK_EQ(0, strcmp("61586E796CB8FF6AEB740000000", buffer));
796 797 798 799

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(30);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
800
  CHECK_EQ(0, strcmp("3CD7450BE3F39FA2D32880000000", buffer));
801 802 803 804

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(31);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
805
  CHECK_EQ(0, strcmp("26068B276E7843C5C3F9500000000", buffer));
806 807 808 809

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(50);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
810
  CHECK_EQ(0, strcmp("149D1B4CFED03B23AB5F4E1196EF45C08000000000000", buffer));
811 812 813 814

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(100);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
815 816 817 818 819
  CHECK_EQ(0,
           strcmp(
               "5827249F27165024FBC47DFCA9359BF316332D1B91ACEECF471FBAB06D9B2"
               "0000000000000000000000000",
               buffer));
820 821 822 823

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(200);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
824 825 826 827 828 829
  CHECK_EQ(0,
           strcmp(
               "64C1F5C06C3816AFBF8DAFD5A3D756365BB0FD020E6F084E759C1F7C99E4F"
               "55B9ACC667CEC477EB958C2AEEB3C6C19BA35A1AD30B35C51EB72040920000"
               "0000000000000000000000000000000000000000000000",
               buffer));
830 831 832 833

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(500);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
834 835 836 837 838 839 840 841 842 843
  CHECK_EQ(0,
           strcmp(
               "96741A625EB5D7C91039FEB5C5ACD6D9831EDA5B083D800E6019442C8C8223"
               "3EAFB3501FE2058062221E15121334928880827DEE1EC337A8B26489F3A40A"
               "CB440A2423734472D10BFCE886F41B3AF9F9503013D86D088929CA86EEB4D8"
               "B9C831D0BD53327B994A0326227CFD0ECBF2EB48B02387AAE2D4CCCDF1F1A1"
               "B8CC4F1FA2C56AD40D0E4DAA9C28CDBF0A549098EA13200000000000000000"
               "00000000000000000000000000000000000000000000000000000000000000"
               "0000000000000000000000000000000000000000000000",
               buffer));
844 845 846 847

  AssignDecimalString(&bignum, "1234");
  bignum.MultiplyByPowerOfTen(1000);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864
  CHECK_EQ(0,
           strcmp(
               "1258040F99B1CD1CC9819C676D413EA50E4A6A8F114BB0C65418C62D399B81"
               "6361466CA8E095193E1EE97173553597C96673AF67FAFE27A66E7EF2E5EF2E"
               "E3F5F5070CC17FE83BA53D40A66A666A02F9E00B0E11328D2224B8694C7372"
               "F3D536A0AD1985911BD361496F268E8B23112500EAF9B88A9BC67B2AB04D38"
               "7FEFACD00F5AF4F764F9ABC3ABCDE54612DE38CD90CB6647CA389EA0E86B16"
               "BF7A1F34086E05ADBE00BD1673BE00FAC4B34AF1091E8AD50BA675E0381440"
               "EA8E9D93E75D816BAB37C9844B1441C38FC65CF30ABB71B36433AF26DD97BD"
               "ABBA96C03B4919B8F3515B92826B85462833380DC193D79F69D20DD6038C99"
               "6114EF6C446F0BA28CC772ACBA58B81C04F8FFDE7B18C4E5A3ABC51E637FDF"
               "6E37FDFF04C940919390F4FF92000000000000000000000000000000000000"
               "00000000000000000000000000000000000000000000000000000000000000"
               "00000000000000000000000000000000000000000000000000000000000000"
               "00000000000000000000000000000000000000000000000000000000000000"
               "0000000000000000000000000000",
               buffer));
865 866 867 868 869 870 871 872 873 874 875 876

  Bignum bignum2;
  AssignHexString(&bignum2, "3DA774C07FB5DF54284D09C675A492165B830D5DAAEB2A7501"
                            "DA17CF9DFA1CA2282269F92A25A97314296B717E3DCBB9FE17"
                            "41A842FE2913F540F40796F2381155763502C58B15AF7A7F88"
                            "6F744C9164FF409A28F7FA0C41F89ED79C1BE9F322C8578B97"
                            "841F1CBAA17D901BE1230E3C00E1C643AF32638B5674E01FEA"
                            "96FC90864E621B856A9E1CE56E6EB545B9C2F8F0CC10DDA88D"
                            "CC6D282605F8DB67044F2DFD3695E7BA63877AE16701536AE6"
                            "567C794D0BFE338DFBB42D92D4215AF3BB22BF0A8B283FDDC2"
                            "C667A10958EA6D2");
  CHECK(bignum2.ToHexString(buffer, kBufferSize));
877 878 879 880 881 882 883 884 885 886 887
  CHECK_EQ(0, strcmp(
                  "3DA774C07FB5DF54284D09C675A492165B830D5DAAEB2A7501"
                  "DA17CF9DFA1CA2282269F92A25A97314296B717E3DCBB9FE17"
                  "41A842FE2913F540F40796F2381155763502C58B15AF7A7F88"
                  "6F744C9164FF409A28F7FA0C41F89ED79C1BE9F322C8578B97"
                  "841F1CBAA17D901BE1230E3C00E1C643AF32638B5674E01FEA"
                  "96FC90864E621B856A9E1CE56E6EB545B9C2F8F0CC10DDA88D"
                  "CC6D282605F8DB67044F2DFD3695E7BA63877AE16701536AE6"
                  "567C794D0BFE338DFBB42D92D4215AF3BB22BF0A8B283FDDC2"
                  "C667A10958EA6D2",
                  buffer));
888 889 890 891

  bignum.AssignBignum(bignum2);
  bignum.MultiplyByPowerOfTen(1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
892 893 894 895 896 897 898 899 900 901
  CHECK_EQ(0,
           strcmp(
               "2688A8F84FD1AB949930261C0986DB4DF931E85A8AD2FA8921284EE1C2BC51"
               "E55915823BBA5789E7EC99E326EEE69F543ECE890929DED9AC79489884BE57"
               "630AD569E121BB76ED8DAC8FB545A8AFDADF1F8860599AFC47A93B6346C191"
               "7237F5BD36B73EB29371F4A4EE7A116CB5E8E5808D1BEA4D7F7E3716090C13"
               "F29E5DDA53F0FD513362A2D20F6505314B9419DB967F8A8A89589FC43917C3"
               "BB892062B17CBE421DB0D47E34ACCCE060D422CFF60DCBD0277EE038BD509C"
               "7BC494D8D854F5B76696F927EA99BC00C4A5D7928434",
               buffer));
902 903 904 905

  bignum.AssignBignum(bignum2);
  bignum.MultiplyByPowerOfTen(2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
906 907 908 909 910 911 912 913 914 915
  CHECK_EQ(0,
           strcmp(
               "1815699B31E30B3CDFBE17D185F44910BBBF313896C3DC95B4B9314D19B5B32"
               "F57AD71655476B630F3E02DF855502394A74115A5BA2B480BCBCD5F52F6F69D"
               "E6C5622CB5152A54788BD9D14B896DE8CB73B53C3800DDACC9C51E0C38FAE76"
               "2F9964232872F9C2738E7150C4AE3F1B18F70583172706FAEE26DC5A78C77A2"
               "FAA874769E52C01DA5C3499F233ECF3C90293E0FB69695D763DAA3AEDA5535B"
               "43DAEEDF6E9528E84CEE0EC000C3C8495C1F9C89F6218AF4C23765261CD5ADD"
               "0787351992A01E5BB8F2A015807AE7A6BB92A08",
               buffer));
916 917 918 919

  bignum.AssignBignum(bignum2);
  bignum.MultiplyByPowerOfTen(5);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
920 921 922 923 924 925 926 927 928 929
  CHECK_EQ(0,
           strcmp(
               "5E13A4863ADEE3E5C9FE8D0A73423D695D62D8450CED15A8C9F368952C6DC3"
               "F0EE7D82F3D1EFB7AF38A3B3920D410AFCAD563C8F5F39116E141A3C5C14B3"
               "58CD73077EA35AAD59F6E24AD98F10D5555ABBFBF33AC361EAF429FD5FBE94"
               "17DA9EF2F2956011F9F93646AA38048A681D984ED88127073443247CCC167C"
               "B354A32206EF5A733E73CF82D795A1AD598493211A6D613C39515E0E0F6304"
               "DCD9C810F3518C7F6A7CB6C81E99E02FCC65E8FDB7B7AE97306CC16A8631CE"
               "0A2AEF6568276BE4C176964A73C153FDE018E34CB4C2F40",
               buffer));
930 931 932 933

  bignum.AssignBignum(bignum2);
  bignum.MultiplyByPowerOfTen(10);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
934 935 936 937 938 939 940 941 942 943
  CHECK_EQ(0,
           strcmp(
               "8F8CB8EB51945A7E815809F6121EF2F4E61EF3405CD9432CAD2709749EEAFD"
               "1B81E843F14A3667A7BDCCC9E0BB795F63CDFDB62844AC7438976C885A0116"
               "29607DA54F9C023CC366570B7637ED0F855D931752038A614922D0923E382C"
               "B8E5F6C975672DB76E0DE471937BB9EDB11E28874F1C122D5E1EF38CECE9D0"
               "0723056BCBD4F964192B76830634B1D322B7EB0062F3267E84F5C824343A77"
               "4B7DCEE6DD464F01EBDC8C671BB18BB4EF4300A42474A6C77243F2A12B03BF"
               "0443C38A1C0D2701EDB393135AE0DEC94211F9D4EB51F990800",
               buffer));
944 945 946 947

  bignum.AssignBignum(bignum2);
  bignum.MultiplyByPowerOfTen(50);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
948 949 950 951 952 953 954 955 956 957 958
  CHECK_EQ(0,
           strcmp(
               "107A8BE345E24407372FC1DE442CBA696BC23C4FFD5B4BDFD9E5C39559815"
               "86628CF8472D2D589F2FC2BAD6E0816EC72CBF85CCA663D8A1EC6C51076D8"
               "2D247E6C26811B7EC4D4300FB1F91028DCB7B2C4E7A60C151161AA7E65E79"
               "B40917B12B2B5FBE7745984D4E8EFA31F9AE6062427B068B144A9CB155873"
               "E7C0C9F0115E5AC72DC5A73C4796DB970BF9205AB8C77A6996EB1B417F9D1"
               "6232431E6313C392203601B9C22CC10DDA88DCC6D282605F8DB67044F2DFD"
               "3695E7BA63877AE16701536AE6567C794D0BFE338DFBB42D924CF964BD2C0"
               "F586E03A2FCD35A408000000000000",
               buffer));
959 960 961 962

  bignum.AssignBignum(bignum2);
  bignum.MultiplyByPowerOfTen(100);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
963 964 965 966 967 968 969 970 971 972 973 974
  CHECK_EQ(0,
           strcmp(
               "46784A90ACD0ED3E7759CC585FB32D36EB6034A6F78D92604E3BAA5ED3D8B"
               "6E60E854439BE448897FB4B7EA5A3D873AA0FCB3CFFD80D0530880E45F511"
               "722A50CE7E058B5A6F5464DB7500E34984EE3202A9441F44FA1554C0CEA96"
               "B438A36F25E7C9D56D71AE2CD313EC37534DA299AC0854FC48591A7CF3171"
               "31265AA4AE62DE32344CE7BEEEF894AE686A2DAAFE5D6D9A10971FFD9C064"
               "5079B209E1048F58B5192D41D84336AC4C8C489EEF00939CFC9D55C122036"
               "01B9C22CC10DDA88DCC6D282605F8DB67044F2DFD3695E7BA3F67B96D3A32"
               "E11FB5561B68744C4035B0800DC166D49D98E3FD1D5BB2000000000000000"
               "0000000000",
               buffer));
975 976 977 978

  bignum.AssignBignum(bignum2);
  bignum.MultiplyByPowerOfTen(200);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
979 980 981 982 983 984 985 986 987 988 989 990 991
  CHECK_EQ(0,
           strcmp(
               "508BD351221DF139D72D88CDC0416845A53EE2D0E6B98352509A9AC312F8C"
               "6CB1A144889416201E0B6CE66EA3EBE259B5FD79ECFC1FD77963CE516CC7E"
               "2FE73D4B5B710C19F6BCB092C7A2FD76286543B8DBD2C596DFF2C896720BA"
               "DFF7BC9C366ACEA3A880AEC287C5E6207DF2739B5326FC19D773BD830B109"
               "ED36C7086544BF8FDB9D4B73719C2B5BC2F571A5937EC46876CD428281F6B"
               "F287E1E07F25C1B1D46BC37324FF657A8B2E0071DB83B86123CA34004F406"
               "001082D7945E90C6E8C9A9FEC2B44BE0DDA46E9F52B152E4D1336D2FCFBC9"
               "96E30CA0082256737365158FE36482AA7EB9DAF2AB128F10E7551A3CD5BE6"
               "0A922F3A7D5EED38B634A7EC95BCF7021BA6820A292000000000000000000"
               "00000000000000000000000000000000",
               buffer));
992 993 994 995

  bignum.AssignBignum(bignum2);
  bignum.MultiplyByPowerOfTen(500);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012
  CHECK_EQ(0,
           strcmp(
               "7845F900E475B5086885BAAAE67C8E85185ACFE4633727F82A4B06B5582AC"
               "BE933C53357DA0C98C20C5AC900C4D76A97247DF52B79F48F9E35840FB715"
               "D392CE303E22622B0CF82D9471B398457DD3196F639CEE8BBD2C146873841"
               "F0699E6C41F04FC7A54B48CEB995BEB6F50FE81DE9D87A8D7F849CC523553"
               "7B7BBBC1C7CAAFF6E9650BE03B308C6D31012AEF9580F70D3EE2083ADE126"
               "8940FA7D6308E239775DFD2F8C97FF7EBD525DAFA6512216F7047A62A93DC"
               "38A0165BDC67E250DCC96A0181DE935A70B38704DC71819F02FC5261FF7E1"
               "E5F11907678B0A3E519FF4C10A867B0C26CE02BE6960BA8621A87303C101C"
               "3F88798BB9F7739655946F8B5744E6B1EAF10B0C5621330F0079209033C69"
               "20DE2E2C8D324F0624463735D482BF291926C22A910F5B80FA25170B6B57D"
               "8D5928C7BCA3FE87461275F69BD5A1B83181DAAF43E05FC3C72C4E93111B6"
               "6205EBF49B28FEDFB7E7526CBDA658A332000000000000000000000000000"
               "0000000000000000000000000000000000000000000000000000000000000"
               "0000000000000000000000000000000000000",
               buffer));
1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025
}


TEST(DivideModuloIntBignum) {
  char buffer[kBufferSize];
  Bignum bignum;
  Bignum other;
  Bignum third;

  bignum.AssignUInt16(10);
  other.AssignUInt16(2);
  CHECK_EQ(5, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1026
  CHECK_EQ(0, strcmp("0", buffer));
1027 1028 1029 1030 1031 1032

  bignum.AssignUInt16(10);
  bignum.ShiftLeft(500);
  other.AssignUInt16(2);
  other.ShiftLeft(500);
  CHECK_EQ(5, bignum.DivideModuloIntBignum(other));
1033
  CHECK_EQ(0, strcmp("0", buffer));
1034 1035 1036 1037 1038

  bignum.AssignUInt16(11);
  other.AssignUInt16(2);
  CHECK_EQ(5, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1039
  CHECK_EQ(0, strcmp("1", buffer));
1040 1041 1042 1043 1044 1045 1046 1047 1048

  bignum.AssignUInt16(10);
  bignum.ShiftLeft(500);
  other.AssignUInt16(1);
  bignum.AddBignum(other);
  other.AssignUInt16(2);
  other.ShiftLeft(500);
  CHECK_EQ(5, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1049
  CHECK_EQ(0, strcmp("1", buffer));
1050 1051 1052 1053 1054 1055 1056 1057 1058

  bignum.AssignUInt16(10);
  bignum.ShiftLeft(500);
  other.AssignBignum(bignum);
  bignum.MultiplyByUInt32(0x1234);
  third.AssignUInt16(0xFFF);
  bignum.AddBignum(third);
  CHECK_EQ(0x1234, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1059
  CHECK_EQ(0, strcmp("FFF", buffer));
1060 1061 1062 1063 1064

  bignum.AssignUInt16(10);
  AssignHexString(&other, "1234567890");
  CHECK_EQ(0, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1065
  CHECK_EQ(0, strcmp("A", buffer));
1066 1067 1068 1069 1070

  AssignHexString(&bignum, "12345678");
  AssignHexString(&other, "3789012");
  CHECK_EQ(5, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1071
  CHECK_EQ(0, strcmp("D9861E", buffer));
1072 1073 1074 1075 1076

  AssignHexString(&bignum, "70000001");
  AssignHexString(&other, "1FFFFFFF");
  CHECK_EQ(3, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1077
  CHECK_EQ(0, strcmp("10000004", buffer));
1078 1079 1080 1081 1082

  AssignHexString(&bignum, "28000000");
  AssignHexString(&other, "12A05F20");
  CHECK_EQ(2, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1083
  CHECK_EQ(0, strcmp("2BF41C0", buffer));
1084 1085 1086 1087 1088 1089 1090 1091 1092

  bignum.AssignUInt16(10);
  bignum.ShiftLeft(500);
  other.AssignBignum(bignum);
  bignum.MultiplyByUInt32(0x1234);
  third.AssignUInt16(0xFFF);
  other.SubtractBignum(third);
  CHECK_EQ(0x1234, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1093
  CHECK_EQ(0, strcmp("1232DCC", buffer));
1094 1095
  CHECK_EQ(0, bignum.DivideModuloIntBignum(other));
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1096
  CHECK_EQ(0, strcmp("1232DCC", buffer));
1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402
}


TEST(Compare) {
  Bignum bignum1;
  Bignum bignum2;
  bignum1.AssignUInt16(1);
  bignum2.AssignUInt16(1);
  CHECK_EQ(0, Bignum::Compare(bignum1, bignum2));
  CHECK(Bignum::Equal(bignum1, bignum2));
  CHECK(Bignum::LessEqual(bignum1, bignum2));
  CHECK(!Bignum::Less(bignum1, bignum2));

  bignum1.AssignUInt16(0);
  bignum2.AssignUInt16(1);
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));
  CHECK(!Bignum::Equal(bignum1, bignum2));
  CHECK(!Bignum::Equal(bignum2, bignum1));
  CHECK(Bignum::LessEqual(bignum1, bignum2));
  CHECK(!Bignum::LessEqual(bignum2, bignum1));
  CHECK(Bignum::Less(bignum1, bignum2));
  CHECK(!Bignum::Less(bignum2, bignum1));

  AssignHexString(&bignum1, "1234567890ABCDEF12345");
  AssignHexString(&bignum2, "1234567890ABCDEF12345");
  CHECK_EQ(0, Bignum::Compare(bignum1, bignum2));

  AssignHexString(&bignum1, "1234567890ABCDEF12345");
  AssignHexString(&bignum2, "1234567890ABCDEF12346");
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));

  AssignHexString(&bignum1, "1234567890ABCDEF12345");
  bignum1.ShiftLeft(500);
  AssignHexString(&bignum2, "1234567890ABCDEF12345");
  bignum2.ShiftLeft(500);
  CHECK_EQ(0, Bignum::Compare(bignum1, bignum2));

  AssignHexString(&bignum1, "1234567890ABCDEF12345");
  bignum1.ShiftLeft(500);
  AssignHexString(&bignum2, "1234567890ABCDEF12346");
  bignum2.ShiftLeft(500);
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));

  bignum1.AssignUInt16(1);
  bignum1.ShiftLeft(64);
  AssignHexString(&bignum2, "10000000000000000");
  CHECK_EQ(0, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(0, Bignum::Compare(bignum2, bignum1));

  bignum1.AssignUInt16(1);
  bignum1.ShiftLeft(64);
  AssignHexString(&bignum2, "10000000000000001");
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));

  bignum1.AssignUInt16(1);
  bignum1.ShiftLeft(96);
  AssignHexString(&bignum2, "10000000000000001");
  bignum2.ShiftLeft(32);
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));

  AssignHexString(&bignum1, "FFFFFFFFFFFFFFFF");
  bignum2.AssignUInt16(1);
  bignum2.ShiftLeft(64);
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));

  AssignHexString(&bignum1, "FFFFFFFFFFFFFFFF");
  bignum1.ShiftLeft(32);
  bignum2.AssignUInt16(1);
  bignum2.ShiftLeft(96);
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));

  AssignHexString(&bignum1, "FFFFFFFFFFFFFFFF");
  bignum1.ShiftLeft(32);
  bignum2.AssignUInt16(1);
  bignum2.ShiftLeft(95);
  CHECK_EQ(+1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(-1, Bignum::Compare(bignum2, bignum1));

  AssignHexString(&bignum1, "FFFFFFFFFFFFFFFF");
  bignum1.ShiftLeft(32);
  bignum2.AssignUInt16(1);
  bignum2.ShiftLeft(100);
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));

  AssignHexString(&bignum1, "100000000000000");
  bignum2.AssignUInt16(1);
  bignum2.ShiftLeft(14*4);
  CHECK_EQ(0, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(0, Bignum::Compare(bignum2, bignum1));

  AssignHexString(&bignum1, "100000000000001");
  bignum2.AssignUInt16(1);
  bignum2.ShiftLeft(14*4);
  CHECK_EQ(+1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(-1, Bignum::Compare(bignum2, bignum1));

  AssignHexString(&bignum1, "200000000000000");
  bignum2.AssignUInt16(3);
  bignum2.ShiftLeft(14*4);
  CHECK_EQ(-1, Bignum::Compare(bignum1, bignum2));
  CHECK_EQ(+1, Bignum::Compare(bignum2, bignum1));
}


TEST(PlusCompare) {
  Bignum a;
  Bignum b;
  Bignum c;
  a.AssignUInt16(1);
  b.AssignUInt16(0);
  c.AssignUInt16(1);
  CHECK_EQ(0, Bignum::PlusCompare(a, b, c));
  CHECK(Bignum::PlusEqual(a, b, c));
  CHECK(Bignum::PlusLessEqual(a, b, c));
  CHECK(!Bignum::PlusLess(a, b, c));

  a.AssignUInt16(0);
  b.AssignUInt16(0);
  c.AssignUInt16(1);
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));
  CHECK_EQ(+1, Bignum::PlusCompare(c, b, a));
  CHECK(!Bignum::PlusEqual(a, b, c));
  CHECK(!Bignum::PlusEqual(c, b, a));
  CHECK(Bignum::PlusLessEqual(a, b, c));
  CHECK(!Bignum::PlusLessEqual(c, b, a));
  CHECK(Bignum::PlusLess(a, b, c));
  CHECK(!Bignum::PlusLess(c, b, a));

  AssignHexString(&a, "1234567890ABCDEF12345");
  b.AssignUInt16(1);
  AssignHexString(&c, "1234567890ABCDEF12345");
  CHECK_EQ(+1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890ABCDEF12344");
  b.AssignUInt16(1);
  AssignHexString(&c, "1234567890ABCDEF12345");
  CHECK_EQ(0, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4);
  AssignHexString(&b, "ABCDEF12345");
  AssignHexString(&c, "1234567890ABCDEF12345");
  CHECK_EQ(0, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4);
  AssignHexString(&b, "ABCDEF12344");
  AssignHexString(&c, "1234567890ABCDEF12345");
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4);
  AssignHexString(&b, "ABCDEF12346");
  AssignHexString(&c, "1234567890ABCDEF12345");
  CHECK_EQ(1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567891");
  a.ShiftLeft(11*4);
  AssignHexString(&b, "ABCDEF12345");
  AssignHexString(&c, "1234567890ABCDEF12345");
  CHECK_EQ(1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567889");
  a.ShiftLeft(11*4);
  AssignHexString(&b, "ABCDEF12345");
  AssignHexString(&c, "1234567890ABCDEF12345");
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF12345");
  c.ShiftLeft(32);
  CHECK_EQ(0, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12344");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF12345");
  c.ShiftLeft(32);
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12346");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF12345");
  c.ShiftLeft(32);
  CHECK_EQ(1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567891");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF12345");
  c.ShiftLeft(32);
  CHECK_EQ(1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567889");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF12345");
  c.ShiftLeft(32);
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF1234500000000");
  CHECK_EQ(0, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12344");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF1234500000000");
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12346");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF1234500000000");
  CHECK_EQ(1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567891");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF1234500000000");
  CHECK_EQ(1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567889");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  b.ShiftLeft(32);
  AssignHexString(&c, "1234567890ABCDEF1234500000000");
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  AssignHexString(&c, "123456789000000000ABCDEF12345");
  CHECK_EQ(0, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12346");
  AssignHexString(&c, "123456789000000000ABCDEF12345");
  CHECK_EQ(1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12344");
  AssignHexString(&c, "123456789000000000ABCDEF12345");
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  b.ShiftLeft(16);
  AssignHexString(&c, "12345678900000ABCDEF123450000");
  CHECK_EQ(0, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12344");
  b.ShiftLeft(16);
  AssignHexString(&c, "12345678900000ABCDEF123450000");
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12345");
  b.ShiftLeft(16);
  AssignHexString(&c, "12345678900000ABCDEF123450001");
  CHECK_EQ(-1, Bignum::PlusCompare(a, b, c));

  AssignHexString(&a, "1234567890");
  a.ShiftLeft(11*4 + 32);
  AssignHexString(&b, "ABCDEF12346");
  b.ShiftLeft(16);
  AssignHexString(&c, "12345678900000ABCDEF123450000");
  CHECK_EQ(+1, Bignum::PlusCompare(a, b, c));
}


TEST(Square) {
  Bignum bignum;
  char buffer[kBufferSize];

  bignum.AssignUInt16(1);
  bignum.Square();
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1403
  CHECK_EQ(0, strcmp("1", buffer));
1404 1405 1406 1407

  bignum.AssignUInt16(2);
  bignum.Square();
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1408
  CHECK_EQ(0, strcmp("4", buffer));
1409 1410 1411 1412

  bignum.AssignUInt16(10);
  bignum.Square();
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1413
  CHECK_EQ(0, strcmp("64", buffer));
1414 1415 1416 1417

  AssignHexString(&bignum, "FFFFFFF");
  bignum.Square();
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1418
  CHECK_EQ(0, strcmp("FFFFFFE0000001", buffer));
1419 1420 1421 1422

  AssignHexString(&bignum, "FFFFFFFFFFFFFF");
  bignum.Square();
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1423
  CHECK_EQ(0, strcmp("FFFFFFFFFFFFFE00000000000001", buffer));
1424 1425 1426 1427 1428 1429 1430 1431 1432
}


TEST(AssignPowerUInt16) {
  Bignum bignum;
  char buffer[kBufferSize];

  bignum.AssignPowerUInt16(1, 0);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1433
  CHECK_EQ(0, strcmp("1", buffer));
1434 1435 1436

  bignum.AssignPowerUInt16(1, 1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1437
  CHECK_EQ(0, strcmp("1", buffer));
1438 1439 1440

  bignum.AssignPowerUInt16(1, 2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1441
  CHECK_EQ(0, strcmp("1", buffer));
1442 1443 1444

  bignum.AssignPowerUInt16(2, 0);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1445
  CHECK_EQ(0, strcmp("1", buffer));
1446 1447 1448

  bignum.AssignPowerUInt16(2, 1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1449
  CHECK_EQ(0, strcmp("2", buffer));
1450 1451 1452

  bignum.AssignPowerUInt16(2, 2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1453
  CHECK_EQ(0, strcmp("4", buffer));
1454 1455 1456

  bignum.AssignPowerUInt16(16, 1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1457
  CHECK_EQ(0, strcmp("10", buffer));
1458 1459 1460

  bignum.AssignPowerUInt16(16, 2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1461
  CHECK_EQ(0, strcmp("100", buffer));
1462 1463 1464

  bignum.AssignPowerUInt16(16, 5);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1465
  CHECK_EQ(0, strcmp("100000", buffer));
1466 1467 1468

  bignum.AssignPowerUInt16(16, 8);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1469
  CHECK_EQ(0, strcmp("100000000", buffer));
1470 1471 1472

  bignum.AssignPowerUInt16(16, 16);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1473
  CHECK_EQ(0, strcmp("10000000000000000", buffer));
1474 1475 1476

  bignum.AssignPowerUInt16(16, 30);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1477
  CHECK_EQ(0, strcmp("1000000000000000000000000000000", buffer));
1478 1479 1480

  bignum.AssignPowerUInt16(10, 0);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1481
  CHECK_EQ(0, strcmp("1", buffer));
1482 1483 1484

  bignum.AssignPowerUInt16(10, 1);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1485
  CHECK_EQ(0, strcmp("A", buffer));
1486 1487 1488

  bignum.AssignPowerUInt16(10, 2);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1489
  CHECK_EQ(0, strcmp("64", buffer));
1490 1491 1492

  bignum.AssignPowerUInt16(10, 5);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1493
  CHECK_EQ(0, strcmp("186A0", buffer));
1494 1495 1496

  bignum.AssignPowerUInt16(10, 8);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1497
  CHECK_EQ(0, strcmp("5F5E100", buffer));
1498 1499 1500

  bignum.AssignPowerUInt16(10, 16);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1501
  CHECK_EQ(0, strcmp("2386F26FC10000", buffer));
1502 1503 1504

  bignum.AssignPowerUInt16(10, 30);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1505
  CHECK_EQ(0, strcmp("C9F2C9CD04674EDEA40000000", buffer));
1506 1507 1508

  bignum.AssignPowerUInt16(10, 31);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1509
  CHECK_EQ(0, strcmp("7E37BE2022C0914B2680000000", buffer));
1510 1511 1512

  bignum.AssignPowerUInt16(2, 0);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1513
  CHECK_EQ(0, strcmp("1", buffer));
1514 1515 1516

  bignum.AssignPowerUInt16(2, 100);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1517
  CHECK_EQ(0, strcmp("10000000000000000000000000", buffer));
1518 1519 1520

  bignum.AssignPowerUInt16(17, 0);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1521
  CHECK_EQ(0, strcmp("1", buffer));
1522 1523 1524

  bignum.AssignPowerUInt16(17, 99);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1525 1526 1527 1528
  CHECK_EQ(0, strcmp(
                  "1942BB9853FAD924A3D4DD92B89B940E0207BEF05DB9C26BC1B757"
                  "80BE0C5A2C2990E02A681224F34ED68558CE4C6E33760931",
                  buffer));
1529 1530 1531

  bignum.AssignPowerUInt16(0xFFFF, 99);
  CHECK(bignum.ToHexString(buffer, kBufferSize));
1532 1533 1534 1535 1536 1537 1538 1539 1540
  CHECK_EQ(0, strcmp(
                  "FF9D12F09B886C54E77E7439C7D2DED2D34F669654C0C2B6B8C288250"
                  "5A2211D0E3DC9A61831349EAE674B11D56E3049D7BD79DAAD6C9FA2BA"
                  "528E3A794299F2EE9146A324DAFE3E88967A0358233B543E233E575B9"
                  "DD4E3AA7942146426C328FF55BFD5C45E0901B1629260AF9AE2F310C5"
                  "50959FAF305C30116D537D80CF6EBDBC15C5694062AF1AC3D956D0A41"
                  "B7E1B79FF11E21D83387A1CE1F5882B31E4B5D8DE415BDBE6854466DF"
                  "343362267A7E8833119D31D02E18DB5B0E8F6A64B0ED0D0062FFFF",
                  buffer));
1541
}
1542

1543
}  // namespace test_bignum
1544 1545
}  // namespace internal
}  // namespace v8