/*
  Copyright 2011-2021 David Robillard <d@drobilla.net>

  Permission to use, copy, modify, and/or distribute this software for any
  purpose with or without fee is hereby granted, provided that the above
  copyright notice and this permission notice appear in all copies.

  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/

#undef NDEBUG

#include "bigint.h"

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>

/* Some test data borrowed from http://github.com/google/double-conversion
   which uses a completely different bigint representation (so if these agree,
   everything is probably fine).  Others cases are either made up to hit the
   edges of the implementation, or interesting cases collected from testing the
   decimal implementation.  Almost everything here uses the hex representation
   so it is easy to dump into Python as a sanity check. */

static ExessBigint
bigint_from_hex(const char* str)
{
  ExessBigint num;
  exess_bigint_set_hex_string(&num, str);
  return num;
}

static bool
check_hex_equals(const char* const str, const ExessBigint* const num)
{
  const ExessBigint expected = bigint_from_hex(str);

  return exess_bigint_compare(&expected, num) == 0;
}

#define CHECK_HEXEQ(str, num) assert(check_hex_equals(str, num))

#define CHECK_SET(setter, value, expected)  \
  do {                                      \
    ExessBigint num;                        \
    exess_bigint_set_##setter(&num, value); \
    CHECK_HEXEQ(expected, &num);            \
  } while (0)

static void
test_set(void)
{
  CHECK_SET(u32, 0, "0");
  CHECK_SET(u32, 0xA, "A");
  CHECK_SET(u32, 0x20, "20");
  CHECK_SET(u32, 0x12345678, "12345678");

  CHECK_SET(u64, 0, "0");
  CHECK_SET(u64, 0xA, "A");
  CHECK_SET(u64, 0x20, "20");
  CHECK_SET(u64, 0x12345678, "12345678");
  CHECK_SET(u64, 0xFFFFFFFFFFFFFFFFull, "FFFFFFFFFFFFFFFF");
  CHECK_SET(u64, 0x123456789ABCDEF0ull, "123456789ABCDEF0");
  CHECK_SET(u64, 0x123456789ABCDEF0ull, "123456789ABCDEF0");

  CHECK_SET(decimal_string, "0", "0");
  CHECK_SET(decimal_string, "1", "1");
  CHECK_SET(decimal_string, "01234567890", "499602D2");
  CHECK_SET(decimal_string, "12345.67890", "499602D2");
  CHECK_SET(decimal_string, "12345.67890EOF", "499602D2");
  CHECK_SET(decimal_string, "012345678901", "2DFDC1C35");
  CHECK_SET(decimal_string, "12345.678901", "2DFDC1C35");
  CHECK_SET(decimal_string,
            "340282366920938463463374607431768211456",
            "100000000000000000000000000000000");

  CHECK_SET(hex_string, "0", "0");
  CHECK_SET(hex_string, "123456789ABCDEF0", "123456789ABCDEF0");

  const ExessBigint orig = bigint_from_hex("123456789ABCDEF01");
  ExessBigint       copy;
  exess_bigint_set(&copy, &orig);
  CHECK_HEXEQ("123456789ABCDEF01", &copy);
}

static void
check_left_shifted_bigit(const char*    value,
                         const unsigned amount,
                         const unsigned index,
                         const Bigit    expected)
{
  const ExessBigint num = bigint_from_hex(value);
  const Bigit actual    = exess_bigint_left_shifted_bigit(&num, amount, index);

  assert(expected == actual);
}

static void
test_left_shifted_bigit(void)
{
  check_left_shifted_bigit("0", 100, 1, 0x0);
  check_left_shifted_bigit("1", 0, 0, 0x1);
  check_left_shifted_bigit("1", 1, 0, 0x2);
  check_left_shifted_bigit("1", 4, 0, 0x10);
  check_left_shifted_bigit("1", 32, 0, 0x0);
  check_left_shifted_bigit("1", 32, 1, 0x1);
  check_left_shifted_bigit("1", 64, 0, 0x0);
  check_left_shifted_bigit("1", 64, 1, 0x0);
  check_left_shifted_bigit("1", 64, 2, 0x1);
  check_left_shifted_bigit("123456789ABCDEF", 64, 0, 0x0);
  check_left_shifted_bigit("123456789ABCDEF", 64, 1, 0x0);
  check_left_shifted_bigit("123456789ABCDEF", 64, 2, 0x89ABCDEF);
  check_left_shifted_bigit("123456789ABCDEF", 64, 3, 0x1234567);
  check_left_shifted_bigit("123456789ABCDEF", 64, 4, 0x0);
  check_left_shifted_bigit("123456789ABCDEF", 65, 0, 0x0);
  check_left_shifted_bigit("123456789ABCDEF", 65, 1, 0x0);
  check_left_shifted_bigit("123456789ABCDEF", 65, 2, 0x13579BDE);
  check_left_shifted_bigit("123456789ABCDEF", 65, 3, 0x2468ACF);
  check_left_shifted_bigit("123456789ABCDEF", 65, 4, 0x0);
}

static void
check_shift_left(const char* value, const unsigned amount, const char* expected)
{
  ExessBigint num = bigint_from_hex(value);
  exess_bigint_shift_left(&num, amount);
  CHECK_HEXEQ(expected, &num);
}

static void
test_shift_left(void)
{
  check_shift_left("0", 100, "0");
  check_shift_left("1", 1, "2");
  check_shift_left("1", 4, "10");
  check_shift_left("1", 32, "100000000");
  check_shift_left("1", 64, "10000000000000000");
  check_shift_left("123456789ABCDEF", 0, "123456789ABCDEF");
  check_shift_left("123456789ABCDEF", 64, "123456789ABCDEF0000000000000000");
  check_shift_left("123456789ABCDEF", 65, "2468ACF13579BDE0000000000000000");
  check_shift_left("16B8B5E06EDC79", 23, "B5C5AF0376E3C800000");
}

static void
check_add_u32(const char* value, const uint32_t rhs, const char* expected)
{
  ExessBigint num = bigint_from_hex(value);
  exess_bigint_add_u32(&num, rhs);
  CHECK_HEXEQ(expected, &num);
}

static void
test_add_u32(void)
{
  check_add_u32("0", 1, "1");
  check_add_u32("1", 1, "2");
  check_add_u32("FFFFFFF", 1, "10000000");
  check_add_u32("FFFFFFFFFFFFFF", 1, "100000000000000");

  check_add_u32("10000000000000000000000000000000000080000000",
                0x80000000,
                "10000000000000000000000000000000000100000000");

  check_add_u32("10000000000000000000000000000000000000000000",
                0x1,
                "10000000000000000000000000000000000000000001");
}

static void
check_add(const char* lhs_hex, const char* rhs_hex, const char* expected)
{
  ExessBigint       lhs = bigint_from_hex(lhs_hex);
  const ExessBigint rhs = bigint_from_hex(rhs_hex);

  exess_bigint_add(&lhs, &rhs);
  CHECK_HEXEQ(expected, &lhs);
}

static void
test_add(void)
{
  check_add("1", "0", "1");
  check_add("1", "1", "2");
  check_add("FFFFFFF", "1", "10000000");
  check_add("FFFFFFFFFFFFFF", "1", "100000000000000");
  check_add("1", "1000000000000", "1000000000001");
  check_add("FFFFFFF", "1000000000000", "100000FFFFFFF");

  check_add("10000000000000000000000000000000000000000000",
            "1",
            "10000000000000000000000000000000000000000001");

  check_add("10000000000000000000000000000000000000000000",
            "1000000000000",
            "10000000000000000000000000000001000000000000");

  check_add("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
            "1000000000000",
            "1000000000000000000000000000000FFFFFFFFFFFF");

  check_add("10000000000000000000000000",
            "1000000000000",
            "10000000000001000000000000");

  check_add(
    "1", "10000000000000000000000000000", "10000000000000000000000000001");

  check_add("FFFFFFF",
            "10000000000000000000000000000",
            "1000000000000000000000FFFFFFF");

  check_add("10000000000000000000000000000000000000000000",
            "10000000000000000000000000000",
            "10000000000000010000000000000000000000000000");

  check_add("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
            "10000000000000000000000000000",
            "100000000000000FFFFFFFFFFFFFFFFFFFFFFFFFFFF");

  check_add("10000000000000000000000000",
            "10000000000000000000000000000",
            "10010000000000000000000000000");
}

static void
check_subtract(const char* lhs_hex, const char* rhs_hex, const char* expected)
{
  ExessBigint       lhs = bigint_from_hex(lhs_hex);
  const ExessBigint rhs = bigint_from_hex(rhs_hex);

  exess_bigint_subtract(&lhs, &rhs);
  CHECK_HEXEQ(expected, &lhs);
}

static void
test_subtract(void)
{
  check_subtract("1", "0", "1");
  check_subtract("2", "0", "2");
  check_subtract("10000000", "1", "FFFFFFF");
  check_subtract("1FFFFFFFF00000000", "FFFFFFFF", "1FFFFFFFE00000001");
  check_subtract("100000000000000", "1", "FFFFFFFFFFFFFF");
  check_subtract("1000000000001", "1000000000000", "1");
  check_subtract("100000FFFFFFF", "1000000000000", "FFFFFFF");

  check_subtract(
    "11F2678326EA00000000", "0878678326EAC9000000", "979FFFFFFFF37000000");

  check_subtract("10000000000000000000000000000000000000000001",
                 "00000000000000000000000000000000000000000001",
                 "10000000000000000000000000000000000000000000");

  check_subtract("10000000000000000000000000000001000000000000",
                 "00000000000000000000000000000001000000000000",
                 "10000000000000000000000000000000000000000000");

  check_subtract("1000000000000000000000000000000FFFFFFFFFFFF",
                 "0000000000000000000000000000001000000000000",
                 " FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");

  check_subtract("10000000000000000000000000",
                 "00000000000001000000000000",
                 " FFFFFFFFFFFFF000000000000");

  check_subtract("10000000000000000000000000",
                 "1000000000000000000000000",
                 "F000000000000000000000000");

  check_subtract("FFFFFFF000000000000000",
                 "0000000000000800000000",
                 "FFFFFFEFFFFFF800000000");

  check_subtract("10000000000000000000000000000000000000000000",
                 "00000000000000000000000000000000000800000000",
                 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF800000000");

  check_subtract("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
                 "000000000000000000000000000000000800000000",
                 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFF");
}

static void
check_subtract_left_shifted(const char*    lhs_hex,
                            const char*    rhs_hex,
                            const unsigned amount,
                            const char*    expected)
{
  ExessBigint       lhs = bigint_from_hex(lhs_hex);
  const ExessBigint rhs = bigint_from_hex(rhs_hex);

  exess_bigint_subtract_left_shifted(&lhs, &rhs, amount);
  CHECK_HEXEQ(expected, &lhs);
}

static void
test_subtract_left_shifted(void)
{
  check_subtract_left_shifted("1", "0", 1, "1");
  check_subtract_left_shifted("10000000", "1", 1, "FFFFFFE");
  check_subtract_left_shifted("100000000", "40000000", 2, "0");
  check_subtract_left_shifted("1000000000000000", "400000000000000", 2, "0");
  check_subtract_left_shifted("1000000000000000", "800000000000000", 1, "0");
  check_subtract_left_shifted("1000000000000000", "F", 16, "FFFFFFFFFF10000");
  check_subtract_left_shifted("1000000000000000", "F", 24, "FFFFFFFF1000000");
  check_subtract_left_shifted("100000000000000", "1", 0, "FFFFFFFFFFFFFF");
  check_subtract_left_shifted("100000000000000", "1", 56, "0");

  check_subtract_left_shifted(
    "11F2678326EA00000000", "43C33C1937564800000", 1, "979FFFFFFFF37000000");
}

static void
check_multiply_u32(const char* value, const uint32_t rhs, const char* expected)
{
  ExessBigint num = bigint_from_hex(value);
  exess_bigint_multiply_u32(&num, rhs);
  CHECK_HEXEQ(expected, &num);
}

static void
test_multiply_u32(void)
{
  check_multiply_u32("0", 0x25, "0");
  check_multiply_u32("123456789ABCDEF", 0, "0");
  check_multiply_u32("2", 0x5, "A");
  check_multiply_u32("10000000", 0x9, "90000000");
  check_multiply_u32("100000000000000", 0xFFFF, "FFFF00000000000000");
  check_multiply_u32("100000000000000", 0xFFFFFFFF, "FFFFFFFF00000000000000");
  check_multiply_u32("1234567ABCD", 0xFFF, "12333335552433");
  check_multiply_u32("1234567ABCD", 0xFFFFFFF, "12345679998A985433");
  check_multiply_u32("FFFFFFFFFFFFFFFF", 0x2, "1FFFFFFFFFFFFFFFE");
  check_multiply_u32("FFFFFFFFFFFFFFFF", 0x4, "3FFFFFFFFFFFFFFFC");
  check_multiply_u32("FFFFFFFFFFFFFFFF", 0xF, "EFFFFFFFFFFFFFFF1");
  check_multiply_u32("FFFFFFFFFFFFFFFF", 0xFFFFFF, "FFFFFEFFFFFFFFFF000001");
  check_multiply_u32("377654D193A171", 10000000, "210EDD6D4CDD2580EE80");
  check_multiply_u32("2E3F36D108373C00000", 10, "1CE78242A52285800000");

  check_multiply_u32(
    "10000000000000000000000000", 0x00000002, "20000000000000000000000000");

  check_multiply_u32(
    "10000000000000000000000000", 0x0000000F, "F0000000000000000000000000");

  check_multiply_u32("FFFF0000000000000000000000000",
                     0xFFFF,
                     "FFFE00010000000000000000000000000");

  check_multiply_u32("FFFF0000000000000000000000000",
                     0xFFFFFFFF,
                     "FFFEFFFF00010000000000000000000000000");

  check_multiply_u32("FFFF0000000000000000000000000",
                     0xFFFFFFFF,
                     "FFFEFFFF00010000000000000000000000000");
}

static void
check_multiply_u64(const char* value, const uint64_t rhs, const char* expected)
{
  ExessBigint num = bigint_from_hex(value);
  exess_bigint_multiply_u64(&num, rhs);
  CHECK_HEXEQ(expected, &num);
}

static void
test_multiply_u64(void)
{
  check_multiply_u64("0", 0x25, "0");
  check_multiply_u64("123456789ABCDEF", 0, "0");
  check_multiply_u64("123456789ABCDEF", 1, "123456789ABCDEF");
  check_multiply_u64("2", 0x5, "A");
  check_multiply_u64("10000000", 0x9, "90000000");
  check_multiply_u64("100000000000000", 0xFFFF, "FFFF00000000000000");
  check_multiply_u64("1234567ABCD", 0xFFF, "12333335552433");
  check_multiply_u64("1234567ABCD", 0xFFFFFFFFFFull, "1234567ABCBDCBA985433");
  check_multiply_u64("FFFFFFFFFFFFFFFF", 0x2, "1FFFFFFFFFFFFFFFE");
  check_multiply_u64("FFFFFFFFFFFFFFFF", 0x4, "3FFFFFFFFFFFFFFFC");
  check_multiply_u64("FFFFFFFFFFFFFFFF", 0xF, "EFFFFFFFFFFFFFFF1");

  check_multiply_u64(
    "100000000000000", 0xFFFFFFFFFFFFFFFFull, "FFFFFFFFFFFFFFFF00000000000000");

  check_multiply_u64("FFFFFFFFFFFFFFFF",
                     0xFFFFFFFFFFFFFFFFull,
                     "FFFFFFFFFFFFFFFE0000000000000001");

  check_multiply_u64(
    "10000000000000000000000000", 0x00000002, "20000000000000000000000000");

  check_multiply_u64(
    "10000000000000000000000000", 0x0000000F, "F0000000000000000000000000");

  check_multiply_u64("FFFF0000000000000000000000000",
                     0xFFFF,
                     "FFFE00010000000000000000000000000");

  check_multiply_u64("FFFF0000000000000000000000000",
                     0xFFFFFFFF,
                     "FFFEFFFF00010000000000000000000000000");

  check_multiply_u64("FFFF0000000000000000000000000",
                     0xFFFFFFFFFFFFFFFFull,
                     "FFFEFFFFFFFFFFFF00010000000000000000000000000");

  check_multiply_u64(
    "377654D193A171", 0x8AC7230489E80000ull, "1E10EE4B11D15A7F3DE7F3C7680000");
}

static void
check_multiply_pow10(const char*    value,
                     const unsigned exponent,
                     const char*    expected)
{
  ExessBigint num = bigint_from_hex(value);
  exess_bigint_multiply_pow10(&num, exponent);
  CHECK_HEXEQ(expected, &num);
}

static void
test_multiply_pow10(void)
{
  check_multiply_pow10("0", 10, "0");
  check_multiply_pow10("1234", 0, "1234");
  check_multiply_pow10("4D2", 1, "3034");
  check_multiply_pow10("4D2", 2, "1E208");
  check_multiply_pow10("4D2", 3, "12D450");
  check_multiply_pow10("4D2", 4, "BC4B20");
  check_multiply_pow10("4D2", 5, "75AEF40");
  check_multiply_pow10("4D2", 6, "498D5880");
  check_multiply_pow10("4D2", 7, "2DF857500");
  check_multiply_pow10("4D2", 8, "1CBB369200");
  check_multiply_pow10("4D2", 9, "11F5021B400");
  check_multiply_pow10("4D2", 10, "B3921510800");
  check_multiply_pow10("4D2", 11, "703B4D2A5000");
  check_multiply_pow10("4D2", 12, "4625103A72000");
  check_multiply_pow10("4D2", 13, "2BD72A24874000");
  check_multiply_pow10("4D2", 14, "1B667A56D488000");
  check_multiply_pow10("4D2", 15, "11200C7644D50000");
  check_multiply_pow10("4D2", 16, "AB407C9EB0520000");
  check_multiply_pow10("4D2", 17, "6B084DE32E3340000");
  check_multiply_pow10("4D2", 18, "42E530ADFCE0080000");
  check_multiply_pow10("4D2", 19, "29CF3E6CBE0C0500000");
  check_multiply_pow10("4D2", 20, "1A218703F6C783200000");
  check_multiply_pow10("4D2", 21, "1054F4627A3CB1F400000");
  check_multiply_pow10("4D2", 22, "A3518BD8C65EF38800000");
  check_multiply_pow10("4D2", 23, "6612F7677BFB5835000000");
  check_multiply_pow10("4D2", 24, "3FCBDAA0AD7D17212000000");
  check_multiply_pow10("4D2", 25, "27DF68A46C6E2E74B4000000");
  check_multiply_pow10("4D2", 26, "18EBA166C3C4DD08F08000000");
  check_multiply_pow10("4D2", 27, "F9344E03A5B0A259650000000");
  check_multiply_pow10("4D2", 28, "9BC0B0C2478E6577DF20000000");
  check_multiply_pow10("4D2", 29, "61586E796CB8FF6AEB740000000");
  check_multiply_pow10("4D2", 30, "3CD7450BE3F39FA2D32880000000");
  check_multiply_pow10("4D2", 31, "26068B276E7843C5C3F9500000000");

  check_multiply_pow10("4D2",
                       50,
                       "149D1B4CFED03B23AB5F4E1196EF45C0"
                       "8000000000000");

  check_multiply_pow10("4D2",
                       100,
                       "5827249F27165024FBC47DFCA9359BF3"
                       "16332D1B91ACEECF471FBAB06D9B2000"
                       "0000000000000000000000");

  check_multiply_pow10("4D2",
                       305,
                       "AFBA390D657B0829339F5B98DC852A89"
                       "682758E01829EADFD016D1528D4D548B"
                       "80894B9ED9C2EC6A9CABB4881302A637"
                       "9FF3058908FEAC310C52FCA009799718"
                       "8260B0B2E2EC96E471B7892AD9B4F9F9"
                       "A448CBF150D2E87F3934000000000000"
                       "00000000000000000000000000000000"
                       "00000000000000000000000000000000");

  check_multiply_pow10("123456789ABCDEF0", 0, "123456789ABCDEF0");
  check_multiply_pow10("123456789ABCDEF0",
                       44,
                       "51A1AD66ACE4E5C79209330F58F52DE3"
                       "7CEFFF1F000000000000");
  check_multiply_pow10("123456789ABCDEF0",
                       88,
                       "16E0C6D18F4BFA7D0289B88382F56151"
                       "EB9DA5DB09D56C9BA5D8305619CEE057"
                       "4F00000000000000000000000");
  check_multiply_pow10("123456789ABCDEF0",
                       132,
                       "6696B1DA27BEA173B5EFCAABBB8492A9"
                       "2AE3D97F7EE3C7314FB7E2FF8AEFD329"
                       "F5F8202C22650BB79A7D9F3867F00000"
                       "00000000000000000000000000000");
  check_multiply_pow10("123456789ABCDEF0",
                       176,
                       "1CC05FF0499D8BC7D8EBE0C6DC2FDC09"
                       "E93765F3448235FB16AD09D98BBB3A0A"
                       "843372D33A318EE63DAE6998DA59EF34"
                       "B15C40A65B9B65ABF3CAF00000000000"
                       "00000000000000000000000000000000"
                       "00");
  check_multiply_pow10("123456789ABCDEF0",
                       220,
                       "80ED0FD9A6C0F56A495F466320D34E22"
                       "507FAA83F0519E7FF909FDDBDA184682"
                       "BB70D38D43284C828A3681540722E550"
                       "960567BAB1C25389C1BE7705228BE8CC"
                       "AF3EBD382829DF000000000000000000"
                       "00000000000000000000000000000000"
                       "000000");
  check_multiply_pow10("123456789ABCDEF0",
                       264,
                       "2421FD0F55C486D05211339D45EC2DC4"
                       "12AE7A64DDFE619DA81B73C069088D3E"
                       "83D7AA9F99B571815DE939A5275FB4A6"
                       "9D8930798C01FB96781B9D633BB59AD5"
                       "A7F322A7EC14154D1B8B5DF1718779A5"
                       "2291FE0F000000000000000000000000"
                       "00000000000000000000000000000000"
                       "00000000000");
  check_multiply_pow10("123456789ABCDEF0",
                       308,
                       "A206620F35C83E9E780ECC07DCAF13BB"
                       "0A7EE2E213747914340BC172D783BA56"
                       "661E8DCFFD03C398BD66F5570F445AC6"
                       "737126283C64AE1A289B9D8BB4531033"
                       "8C3E34DE2D534187092ABA1F4706100E"
                       "ECF66D14059461A05A9BEBBCCBA0F693"
                       "F0000000000000000000000000000000"
                       "00000000000000000000000000000000"
                       "000000000000000");
}

static void
check_divmod(const char*    lhs_hex,
             const char*    rhs_hex,
             const uint32_t expected_divisor,
             const char*    expected_mod_hex)
{
  ExessBigint       lhs     = bigint_from_hex(lhs_hex);
  const ExessBigint rhs     = bigint_from_hex(rhs_hex);
  const uint32_t    divisor = exess_bigint_divmod(&lhs, &rhs);

  assert(divisor == expected_divisor);
  CHECK_HEXEQ(expected_mod_hex, &lhs);
}

static void
test_divmod(void)
{
  check_divmod("A", "2", 5, "0");
  check_divmod("B", "2", 5, "1");
  check_divmod("C", "2", 6, "0");
  check_divmod("A", "1234567890", 0, "A");
  check_divmod("FFFFFFFF", "3", 0x55555555, "0");
  check_divmod("12345678", "3789012", 5, "D9861E");
  check_divmod("70000001", "1FFFFFFF", 3, "10000004");
  check_divmod("28000000", "12A05F20", 2, "2BF41C0");
  check_divmod("FFFFFFFFF", "FFFFFFFF", 16, "F");
  check_divmod("100000000000001", "FFFFFFF", 0x10000001, "2");
  check_divmod("40000000000002", "2FAF0800000000", 1, "1050F800000002");
  check_divmod("40000000000000", "40000000000000", 1, "0");

  check_divmod("43DE72C3DF858FC278A361EEB5A000000",
               "80000000000000000000000000000000",
               8,
               "3DE72C3DF858FC278A361EEB5A000000");

  check_divmod(
    "B5C5AF0376E3C800000", "43C33C1937564800000", 2, "2E3F36D108373800000");

  check_divmod("A0000000000000000000000000000000"
               "00000000000000000000000000000000"
               "00000000000000000000000000000000"
               "000000000000000000000000000000",
               "20000000000000000000000000000000"
               "00000000000000000000000000000000"
               "00000000000000000000000000000000"
               "000000000000000000000000000000",
               5,
               "0");

  check_divmod("A0000000000000000000000000000000"
               "00000000000000000000000000000000"
               "00000000000000000000000000000000"
               "000000000000000000000000000001",
               "20000000000000000000000000000000"
               "00000000000000000000000000000000"
               "00000000000000000000000000000000"
               "000000000000000000000000000000",
               5,
               "1");

  check_divmod("B6080000000000000000000000000000"
               "00000000000000000000000000000000"
               "00000000000000000000000000000000"
               "000000000000000000000000000000FF"
               "F",
               "A0000000000000000000000000000000"
               "00000000000000000000000000000000"
               "00000000000000000000000000000000"
               "000000000000000000000000000000",
               0x1234,
               "FFF");

  check_divmod("B6080000000000000000000000000000"
               "00000000000000000000000000000000"
               "00000000000000000000000000000000"
               "00000000000000000000000000000000"
               "0",
               "9FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
               "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
               "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
               "FFFFFFFFFFFFFFFFFFFFFFFFFFF001",
               0x1234,
               "1232DCC");
}

static void
check_compare(const char* lhs_hex, const char* rhs_hex, const int expected_cmp)
{
  const ExessBigint lhs = bigint_from_hex(lhs_hex);
  const ExessBigint rhs = bigint_from_hex(rhs_hex);
  const int         cmp = exess_bigint_compare(&lhs, &rhs);

  assert(cmp == expected_cmp);

  if (cmp) {
    const int rcmp = exess_bigint_compare(&rhs, &lhs);
    assert(rcmp == -cmp);
  }
}

static void
test_compare(void)
{
  check_compare("1", "1", 0);
  check_compare("0", "1", -1);
  check_compare("F", "FF", -1);
  check_compare("F", "FFFFFFFFF", -1);
  check_compare("10000000000000000", "10000000000000000", 0);
  check_compare("10000000000000000", "10000000000000001", -1);
  check_compare("FFFFFFFFFFFFFFFFF", "100000000000000000", -1);
  check_compare("10000000000000000", "10000000000000001", -1);
  check_compare("1234567890ABCDEF12345", "1234567890ABCDEF12345", 0);
  check_compare("1234567890ABCDEF12345", "1234567890ABCDEF12346", -1);

  const char* const huge = "123456789ABCDEF0123456789ABCDEF0"
                           "123456789ABCDEF0123456789ABCDEF0"
                           "123456789ABCDEF0123456789ABCDEF0"
                           "123456789ABCDEF0123456789ABCDEF0";

  const char* const huger = "123456789ABCDEF0123456789ABCDEF0"
                            "123456789ABCDEF0123456789ABCDEF0"
                            "123456789ABCDEF0123456789ABCDEF0"
                            "123456789ABCDEF0123456789ABCDEF1";

  check_compare(huge, huge, 0);
  check_compare(huger, huger, 0);
  check_compare(huge, huger, -1);
}

static void
check_plus_compare(const char* l_hex,
                   const char* p_hex,
                   const char* c_hex,
                   const int   expected_cmp)
{
  const ExessBigint l    = bigint_from_hex(l_hex);
  const ExessBigint p    = bigint_from_hex(p_hex);
  const ExessBigint c    = bigint_from_hex(c_hex);
  const int         cmp  = exess_bigint_plus_compare(&l, &p, &c);
  const int         rcmp = exess_bigint_plus_compare(&p, &l, &c);

  assert(cmp == expected_cmp);
  assert(rcmp == expected_cmp);
}

static void
test_plus_compare(void)
{
  check_plus_compare("1", "0", "1", 0);
  check_plus_compare("0", "0", "1", -1);
  check_plus_compare("FFFFFFFFF", "F", "F", 1);
  check_plus_compare("F", "F", "800000000", -1);
  check_plus_compare("F", "F", "80000000000000000", -1);
  check_plus_compare("800000000", "F", "80000000000000000", -1);
  check_plus_compare("2D79883D20000", "2D79883D20000", "5AF3107A40000", 0);
  check_plus_compare("20000000000000", "1", "20000000000000", +1);

  check_plus_compare(
    "0588A503282FE00000", "0588A503282FE00000", "0AD78EBC5AC6200000", +1);

  check_plus_compare("2F06018572BEADD1280000000",
                     "0204FCE5E3E25026110000000",
                     "4000000000000000000000000",
                     -1);

  check_plus_compare("1234567890ABCDEF12345",
                     "000000000000000000001",
                     "1234567890ABCDEF12345",
                     +1);

  check_plus_compare("1234567890ABCDEF12344",
                     "000000000000000000001",
                     "1234567890ABCDEF12345",
                     0);

  check_plus_compare("123456789000000000000",
                     "0000000000ABCDEF12345",
                     "1234567890ABCDEF12345",
                     0);

  check_plus_compare("123456789000000000000",
                     "0000000000ABCDEF12344",
                     "1234567890ABCDEF12345",
                     -1);

  check_plus_compare("123456789000000000000",
                     "0000000000ABCDEF12346",
                     "1234567890ABCDEF12345",
                     1);

  check_plus_compare("123456789100000000000",
                     "0000000000ABCDEF12345",
                     "1234567890ABCDEF12345",
                     1);

  check_plus_compare("123456788900000000000",
                     "0000000000ABCDEF12345",
                     "1234567890ABCDEF12345",
                     -1);

  check_plus_compare("12345678900000000000000000000",
                     "0000000000ABCDEF1234500000000",
                     "1234567890ABCDEF1234500000000",
                     0);

  check_plus_compare("12345678900000000000000000000",
                     "0000000000ABCDEF1234400000000",
                     "1234567890ABCDEF1234500000000",
                     -1);

  check_plus_compare("12345678900000000000000000000",
                     "0000000000ABCDEF1234600000000",
                     "1234567890ABCDEF1234500000000",
                     1);

  check_plus_compare("12345678910000000000000000000",
                     "0000000000ABCDEF1234500000000",
                     "1234567890ABCDEF1234500000000",
                     1);
  check_plus_compare("12345678890000000000000000000",
                     "0000000000ABCDEF1234500000000",
                     "1234567890ABCDEF1234500000000",
                     -1);

  check_plus_compare("12345678900000000000000000000",
                     "000000000000000000ABCDEF12345",
                     "123456789000000000ABCDEF12345",
                     0);

  check_plus_compare("12345678900000000000000000000",
                     "000000000000000000ABCDEF12346",
                     "123456789000000000ABCDEF12345",
                     1);

  check_plus_compare("12345678900000000000000000000",
                     "000000000000000000ABCDEF12344",
                     "123456789000000000ABCDEF12345",
                     -1);

  check_plus_compare("12345678900000000000000000000",
                     "000000000000000000ABCDEF12345",
                     "12345678900000ABCDEF123450000",
                     -1);

  check_plus_compare("12345678900000000000000000000",
                     "000000000000000000ABCDEF12344",
                     "12345678900000ABCDEF123450000",
                     -1);

  check_plus_compare("12345678900000000000000000000",
                     "000000000000000000ABCDEF12345",
                     "12345678900000ABCDEF123450001",
                     -1);

  check_plus_compare("12345678900000000000000000000",
                     "00000000000000ABCDEF123460000",
                     "12345678900000ABCDEF123450000",
                     1);
}

static void
check_pow10(const unsigned exponent, const char* expected)
{
  ExessBigint num;
  exess_bigint_set_pow10(&num, exponent);
  CHECK_HEXEQ(expected, &num);
}

static void
test_set_pow10(void)
{
  check_pow10(0, "1");
  check_pow10(1, "A");
  check_pow10(2, "64");
  check_pow10(5, "186A0");
  check_pow10(8, "5F5E100");
  check_pow10(16, "2386F26FC10000");
  check_pow10(30, "C9F2C9CD04674EDEA40000000");
  check_pow10(31, "7E37BE2022C0914B2680000000");
}

int
main(void)
{
  test_set();
  test_left_shifted_bigit();
  test_shift_left();
  test_add_u32();
  test_add();
  test_subtract();
  test_subtract_left_shifted();
  test_multiply_u32();
  test_multiply_u64();
  test_multiply_pow10();
  test_divmod();
  test_compare();
  test_plus_compare();
  test_set_pow10();

  return 0;
}