#include "divide.hpp"

#include <array>
#include <bit>
#include <cstdlib>
#include <iostream>
#include <random>

namespace {
using I = std::int32_t;
using W = std::int64_t;
constexpr I lo = std::numeric_limits<I>::min();
constexpr I hi = std::numeric_limits<I>::max();

static_assert(Divide(3)(7) == 2);
static_assert(Divide(3)(-7) == -2);
static_assert(Divide(-3)(7) == -2);
static_assert(Divide(-3)(-7) == 2);
static_assert(Divide(1)(lo) == lo);
static_assert(Divide(-1)(hi) == -hi);
static_assert(Divide(2)(-3) == -1);
static_assert(Divide(-2)(lo) == 1'073'741'824);
static_assert(Divide(lo)(lo) == 1);
static_assert(Divide(lo)(hi) == 0);
static_assert(Divide(hi)(lo) == -1);

std::uint64_t checks = 0;

void check(const Divide& divide, I denominator, I numerator) {
    // The reference expression would have undefined behavior for this pair.
    if (numerator == lo && denominator == -1) {
        return;
    }
    const I expected = numerator / denominator;
    const I actual = divide(numerator);
    if (actual != expected) {
        std::cerr << numerator << " / " << denominator << ": expected "
                  << expected << ", got " << actual << '\n';
        std::exit(EXIT_FAILURE);
    }
    ++checks;
}

// Exercise both sides of quotient transitions, including transitions near
// the ends of the input range where reciprocal-rounding errors are largest.
void check_boundaries(I denominator, std::mt19937& random) {
    const Divide divide(denominator);
    constexpr std::array<I, 17> numerators{
        lo, lo + 1, lo + 2, lo + 3, -65'537, -65'536, -65'535, -1, 0,
        1, 65'535, 65'536, 65'537, hi - 3, hi - 2, hi - 1, hi
    };
    for (const I numerator : numerators) {
        check(divide, denominator, numerator);
    }

    const W magnitude = denominator < 0 ? -W{denominator} : W{denominator};
    const W last_quotient = (W{hi} + 1) / magnitude;
    const std::array<W, 7> quotients{
        0, 1, 2, 3, last_quotient / 2, last_quotient - 1, last_quotient
    };
    for (const W quotient : quotients) {
        for (const W sign : {-1, 1}) {
            for (const W offset : {-2, -1, 0, 1, 2}) {
                const W numerator = sign * quotient * magnitude + offset;
                if (numerator >= lo && numerator <= hi) {
                    check(divide, denominator, static_cast<I>(numerator));
                }
            }
        }
    }

    for (int i = 0; i < 32; ++i) {
        const auto bits = static_cast<std::uint32_t>(random());
        check(divide, denominator, std::bit_cast<I>(bits));
    }
}
} // namespace

int main() {
    bool rejected_zero = false;
    try {
        const Divide invalid(0);
        (void)invalid;
    } catch (const std::invalid_argument&) {
        rejected_zero = true;
    }
    if (!rejected_zero) {
        std::cerr << "Divide(0) was accepted\n";
        return EXIT_FAILURE;
    }

    // Exhaust every signed 16-bit numerator with divisors -128..128, except 0.
    for (I denominator = -128; denominator <= 128; ++denominator) {
        if (denominator == 0) {
            continue;
        }
        const Divide divide(denominator);
        for (I numerator = -32'768; numerator <= 32'767; ++numerator) {
            check(divide, denominator, numerator);
        }
    }

    std::mt19937 random(0xD171DEu);

    // Every small divisor, with full-width numerator boundaries.
    for (I denominator = -65'536; denominator <= 65'536; ++denominator) {
        if (denominator != 0) {
            check_boundaries(denominator, random);
        }
    }

    // All powers of two and nearby divisors, in both signs.
    for (int bit = 0; bit <= 31; ++bit) {
        for (const W offset : {-2, -1, 0, 1, 2}) {
            const W magnitude = (W{1} << bit) + offset;
            for (const W sign : {-1, 1}) {
                const W denominator = sign * magnitude;
                if (denominator != 0 && denominator >= lo && denominator <= hi) {
                    check_boundaries(static_cast<I>(denominator), random);
                }
            }
        }
    }

    // Random full-width divisors, each reused with boundary and random inputs.
    for (int i = 0; i < 100'000; ++i) {
        const auto bits = static_cast<std::uint32_t>(random());
        const I denominator = std::bit_cast<I>(bits);
        if (denominator != 0) {
            check_boundaries(denominator, random);
        }
    }

    std::cout << "Passed " << checks << " comparisons against built-in division\n";
}