#include "t.h"

void blk256_cmp_test_1()
{
	blk256_t x, e;
	blk256_set(&x, 0, 0, 0, 0, 0);
	blk256_set(&e, 0, 0, 0, 0, 0);

	int c = blk256_cmp(&e, &x);
	assert_int_equal(0, c);
}

void blk256_cmp_test_2()
{
	blk256_t x, e;
	blk256_set(&x, 0, 0, 0, 0, 0);
	blk256_set(&e, 0, 0, 0, 0, 1);

	int c = blk256_cmp(&e, &x);
	assert_int_equal(1, c);
}

void blk256_cmp_test_3()
{
	blk256_t x, e;
	blk256_set(&x, 0, 0, 0, 0, 1);
	blk256_set(&e, 0, 0, 0, 0, 0);

	int c = blk256_cmp(&e, &x);
	assert_int_equal(-1, c);
}

void blk256_one_one_two()
{
	blk256_t x, y;
	blk256_set(&x, 0, 0, 0, 0, 1);
	blk256_set(&y, 0, 0, 0, 0, 1);

	blk256_add(&x, &x, &y);

	assert_true(!x.mx && !x.x[3] && !x.x[2]	&& !x.x[1] &&  x.x[0] == 2);
}

void blk256_two()
{
	blk256_t x, y;
	blk256_set(&x, 0, 0, 0, 0, 1);
	blk256_set(&y, 0, 0, 0, 1, 0);

	blk256_add(&x, &x, &y);

	assert_true(!x.mx && !x.x[3] && !x.x[2] &&  x.x[1] == 1	&&  x.x[0] == 1);
}

void blk256_overflow1()
{
	blk256_t x, y;
	blk256_set(&x, 0, 0, 0, 0, u64(~0));
	blk256_set(&y, 0, 0, 0, 0, 1);

	blk256_add(&x, &x, &y);

	assert_true(!x.mx && !x.x[3] && !x.x[2]	&&  x.x[1] == 1	&& !x.x[0]);
}

void blk256_overflow_all()
{
	blk256_t x, y;
	blk256_set(&x, 0, u64(~0), u64(~0), u64(~0), u64(~0));
	blk256_set(&y, 0, 0, 0, 0, 1);

	blk256_add(&x, &x, &y);

	assert_true(x.mx == 1 && !x.x[3] && !x.x[2] && !x.x[1] && !x.x[0]);
}

void blk256_overflow_some()
{
	blk256_t x, y;
	blk256_set(&x, 0, 0, u64(~0), 0, u64(~0));
	blk256_set(&y, 0, 0,       1, 0,       1);

	blk256_add(&x, &x, &y);

	assert_true(!x.mx && x.x[3] == 1 && !x.x[2] &&  x.x[1] == 1 && !x.x[0]);
}

void blk256_add_neg()
{
	/**
	 * Observed the following error
	 * q  : {0, [0, 0, 2338623232362770432, 0]}
	 * t  : {2, [0, 0, 223, 0]}
	 * q+t: {2, [0, 0, 2338623232362770432, 0]}
	 */
	blk256_t x, y, r, e;

	blk256_set(&x, 0, 0, 0, 2338623232362770432, 0);
	blk256_set(&y, 2, 0, 0, 223, 0);
	blk256_set(&e, 0, 0, 0, 2338623232362770209, 0);

	blk256_add(&r, &x, &y);

	assert_blk256_eq(e, r);
}

void blk256_add_blk128_1()
{
	blk256_t x;
	blk128_t y;
	blk256_set(&x, 0, 0, u64(~0), 0, u64(~0));
	blk128_set(&y, 0, 1);

	blk256_add_blk128(&x, &x, &y);

	assert_true(!x.mx && !x.x[3] && x.x[2] == u64(~0) && x.x[1] == 1 && !x.x[0]);
}

void blk256_sub_simple()
{
	blk256_t x, y,e;
	blk256_set(&x, 0, 0, 0, 0, 7);
	blk256_set(&y, 0, 0, 0, 0, 5);
	blk256_set(&e, 0, 0, 0, 0, 2);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_mx()
{
	blk256_t x, y,e;
	blk256_set(&x, 1, 0, 0, 0, 0);
	blk256_set(&y, 0, 0, 0, 0, 1);
	blk256_set(&e, 0, UINT64_MAX, UINT64_MAX, UINT64_MAX, UINT64_MAX);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_no_carry()
{
	blk256_t x, y,e;
	blk256_set(&x, 1, 42, 34, 53, 4);
	blk256_set(&y, 0, 5, 2, 34, 1);
	blk256_set(&e, 1, 37, 32, 19, 3);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_some_carry()
{
	blk256_t x, y,e;
	blk256_set(&x, 0, 0, 1, 2342350, 982735987);
	blk256_set(&y, 0, 0, 0, UINT64_MAX, UINT64_MAX - 2);
	blk256_set(&e, 0, 0, 0, 2342350, 982735990);
	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_add_blk128_2()
{
	blk256_t x;
	blk128_t y;
	blk256_set(&x, 0, 0, u64(~0), u64(~0), u64(~0));
	blk128_set(&y, 0, 1);

	blk256_add_blk128(&x, &x, &y);

	assert_true(!x.mx && x.x[3] == 1 && !x.x[2] && !x.x[1] && !x.x[0]);
}

void blk256_sub_u64_1()
{
	blk256_t v;
	blk256_set(&v, 0, 0, 1, 0, 0);

	blk256_sub_u64(&v, &v, u64(3));
	assert_true(!v.mx && !v.x[3] && !v.x[2] && v.x[1] == UINT64_MAX && v.x[0] == UINT64_MAX - 2);
}

void blk256_div_large()
{
	/**
	 * x = 1 << 256
	 * y = (1 << 128) - 3
	 *
	 * x div y should be
	 *
	 * q = (1 << 128) + 3
	 * r = 9
	 */
	blk256_t x, q;
	blk128_t y = {UINT64_MAX, UINT64_MAX - 2};
	blk128_t r;
	blk256_set(&x, 1, 0, 0, 0, 0);

	blk256_div_blk128(&q, &r, &x, &y);

	if (!q.mx && !q.x[3] && q.x[2] == 1 && !q.x[1] && q.x[0] == 3
			&& !r.hi && r.lo == 9)
		assert_true(1);
	else {
		assert_fail("Expected q = {0, [0, 1, 0, 3]} and r = [0, 9]");
		blk256_print("q", q);
		blk128_print("r", r);
	}
}

void blk256_div_simple()
{
	/**
	 * Scenario: We have [5, 7]. Composed we get (5 << 128) + 12.
	 *           We divide by (B-3)
	 *
	 * Expect:
	 * q = 5
	 * r = 27
	 */
	blk256_t x, q;
	blk128_t y = {UINT64_MAX, UINT64_MAX - 2};
	blk128_t r;
	blk256_set(&x, 0, 0, 5, 0, 12);

	blk256_div_blk128(&q, &r, &x, &y);

	if (!q.mx && !q.x[3] && !q.x[2] && !q.x[1] && q.x[0] == 5
			&& !r.hi && r.lo == 27)
		assert_true(1);
	else {
		assert_fail("Expected q = {0, [0, 1, 0, 3]} and r = [0, 9]");
		blk256_print("q", q);
		blk128_print("r", r);
	}
}

void blk256_mul_test()
{
	/**
	 * x = 2 << 64 | 2 << 32
	 * y = (1 << 128) - 3
	 *
	 * x*y = 680564734000333251844597425582597210112
	 *
	 * in 64-bit chunks is
	 *
	 * (2,8589934591,18446744073709551609,18446744047939747840)
	 */
	blk256_t x, e;
	blk256_set(&x, 0, 0, 0, u64(2), u64(2) << 32);

	blk128_t y = {UINT64_MAX, UINT64_MAX - 2};

	blk256_set(&e, 0, 2, 8589934591, u64c(18446744073709551609), u64c(18446744047939747840));

	blk256_mul_blk128(&x, &x, &y);
	assert_blk256_eq(e, x);
}

void blk256_mult_blk128_neg()
{
	/**
	 * Multiply with a negative number
	 */
	blk256_t x, e;
	blk128_t y = {0, 2};
	blk256_set(&x, 2, 0, 0, 0, 1); /* -1 */

	blk256_mul_blk128(&x, &x, &y);

	blk256_set(&e, 2, 0, 0, 0, 2); /* -2 */

	assert_blk256_eq(e, x);
}


void blk256_sub_negatives()
{
	/**
	 * Subtract a negative number from a negative number, like (-6) - (-48)
	 * should be 42
	 */
	blk256_t x, y, e;
	blk256_set(&x, 2, 0, 0, 0, 6);
	blk256_set(&y, 2, 0, 0, 0, 45);
	blk256_set(&e, 0, 0, 0, 0, 39);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_simple_1()
{
	blk256_t x, y, e;
	blk256_set(&x, 0, 0, 0, 0, 6);
	blk256_set(&y, 0, 0, 0, 0, 45);
	blk256_set(&e, 2, 0, 0, 0, 39);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_simple_2()
{
	/**
	 * x = -1, 0,0,0,1
	 * y = -1, 0,0,0,2
	 *
	 * expect 1, 1,1,1,1
	 */
	blk256_t x, y, e;
	blk256_set(&x, 2, 0, 0, 0, 1);
	blk256_set(&y, 2, 0, 0, 0, 2);
	blk256_set(&e, 0, 0, 0, 0, 1);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_simple_3()
{
	/**
	 * x = -1, 0,0,0,2
	 * y = -1, 0,0,0,1
	 *
	 * expect 1, 1,1,1,1
	 */
	blk256_t x, y, e;
	blk256_set(&x, 2, 0, 0, 0, 2);
	blk256_set(&y, 2, 0, 0, 0, 1);
	blk256_set(&e, 2, 0, 0, 0, 1);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_simple_4()
{
	/**
	 * x = 1, 0,0,0,2
	 * y = 1, 0,0,0,1
	 *
	 * expect 1, 1,1,1,1
	 */
	blk256_t x, y, e;
	blk256_set(&x, 0, 0, 0, 0, 2);
	blk256_set(&y, 0, 0, 0, 0, 1);
	blk256_set(&e, 0, 0, 0, 0, 1);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_simple_5()
{
	/**
	 * x = 1, 0,0,0,1
	 * y = 1, 0,0,0,2
	 *
	 * expect 1, 1,1,1,1
	 */
	blk256_t x, y, e;
	blk256_set(&x, 0, 0, 0, 0, 1);
	blk256_set(&y, 0, 0, 0, 0, 2);
	blk256_set(&e, 2, 0, 0, 0, 1);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_large()
{
	/**
	 * x = 1,1,1,1
	 * y = 2,2,2,2
	 *
	 * expect -1, 1,1,1,1
	 */
	blk256_t x, y, e;
	blk256_set(&x, 0, 1, 1, 1, 1);
	blk256_set(&y, 0, 2, 2, 2, 2);
	blk256_set(&e, 2, 1, 1, 1, 1);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_large_neg()
{
	/**
	 * x = -1, 1,1,1,1
	 * y = -1, 2,2,2,2
	 *
	 * expect 1, 1,1,1,1
	 */
	blk256_t x, y, e;
	blk256_set(&x, 2, 1, 1, 1, 1);
	blk256_set(&y, 2, 2, 2, 2, 2);
	blk256_set(&e, 0, 1, 1, 1, 1);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}

void blk256_sub_pos_from_neg()
{
	/**
	 * x = -1, 1,1,1,1
	 * y = 2,2,2,2
	 *
	 * expect -1, 3,3,3,3
	 */
	blk256_t x, y, e;
	blk256_set(&x, 2, 1, 1, 1, 1);
	blk256_set(&y, 0, 2, 2, 2, 2);
	blk256_set(&e, 2, 3, 3, 3, 3);

	blk256_sub(&x, &x, &y);

	assert_blk256_eq(e, x);
}


void blk256_div_neg_zero()
{
	/**
	 * This divsion could cause t = -0
	 * x = (0,0,2308765963911831668,6998711947288649773)
	 * y = (11575093333181722688,17146911512793096475)
	 */

	blk256_t x, q;
	blk128_t y = {u64c(18446744073709551615), u64c(18446744073709551613)};
	blk128_t r;

	blk256_set(&x, 0, 2308765963911831668, 6998711947288649773, 4648795441446227683, u64c(14597519744636698772));

	/* Compute x / y = q*y + r */
	blk256_div_blk128(&q, &r, &x, &y);

	/* Assert something
	 * */
	if (!q.mx && !q.x[3] && !q.x[2]
			&& q.x[1] == 2308765963911831668
			&& q.x[0] == 6998711947288649773
			&& r.hi == 11575093333181722688ULL
			&& r.lo == 17146911512793096475ULL)
		assert_true(1);
	else {
		assert_fail("Division failed");
		printf("Expected:\nq = (0,0,2308765963911831668,6998711947288649773)\n");
		printf("r = (11575093333181722688,17146911512793096475)\nBut got:\n");
		blk256_print("q", q);
		blk128_print("r", r);
	}
}

void blk256_div_flip_flop()
{
	/**
	 * This particular case caused a kind of "flip-flop", where division
	 * would bounce back and forth from negative to positive.
	 */

	blk256_t x, q;
	blk128_t y = {u64c(18446744073709551615), u64c(18446744073709551610)};
	blk128_t r;

	blk256_set(&x, 0, 2338623232362770208, 2968197749036490859, u64c(9499753957944579205), u64c(10687495549587570827));

	/* Compute x / y = q*y + r */
	blk256_div_blk128(&q, &r, &x, &y);

	/* Assert something */
	if (!q.mx && !q.x[3] && !q.x[2]
	    && q.x[1] == 2338623232362770208
	    && q.x[0] == 2968197749036490860
	    && r.hi == u64c(5084749278411648838)
	    && r.lo == u64c(10049937970096964371))
		assert_true(1);
	else {
		assert_fail("Division failed");
		printf("Expected q = (0,0,2338623232362770208,2968197749036490860)\n");
		printf("         r = (5084749278411648838,10049937970096964371)\n");
		blk256_print("q", q);
		blk128_print("r", r);
	}
}

void blk256_div_neg_in_range()
{
	/*
	 * In our iteration, we may land in the range -d < r < 0, and on the
	 * next round, our conversion should give a divisor of -1. The following
	 * example demonstrates this.
	 *
	 * x: {0, [8747512699207249768, 2334383527001289760, 17135862152534659036, 9333095474287842381]}
	 * y: [18446744073709551615, 18446744073709551601]
	 *
	 * Coincidentally, y = (1 << 128) - 15, ie i=5
	 */

	blk256_t x, q;
	blk128_t y = {u64c(18446744073709551615), u64c(18446744073709551601)};
	blk128_t r;

	blk256_set(&x, 0, 8747512699207249768, 2334383527001289760, u64c(17135862152534659036), u64c(9333095474287842381));

	/* Compute x / y = q*y + r */
	blk256_div_blk128(&q, &r, &x, &y);

	if (!q.mx && !q.x[3] && !q.x[2]
			&& q.x[1] == 8747512699207249768
			&& q.x[0] == 2334383527001289768
			&& r.hi == 774600050966992630
			&& r.lo == 7455360231888085669)
		assert_true(1);
	else {
		assert_fail("Division failed");
		printf("Expected:\nq = ((0,0,8747512699207249768,2334383527001289768)\n");
		printf("r = (774600050966992630,7455360231888085669)\nBut got:\n");
		blk256_print("q", q);
		blk128_print("r", r);
	}
}

void blk256_tests()
{
	test_fixture_start();

	run_test(blk256_cmp_test_1);
	run_test(blk256_cmp_test_2);
	run_test(blk256_cmp_test_3);

	run_test(blk256_one_one_two);
	run_test(blk256_two);
	run_test(blk256_overflow1);
	run_test(blk256_overflow_all);
	run_test(blk256_overflow_some);
	run_test(blk256_add_neg);
	run_test(blk256_add_blk128_1);
	run_test(blk256_add_blk128_2);

	run_test(blk256_sub_simple);
	run_test(blk256_sub_no_carry);
	run_test(blk256_sub_some_carry);
	run_test(blk256_sub_mx);
	run_test(blk256_sub_u64_1);
	run_test(blk256_div_simple);
	run_test(blk256_div_large);
	run_test(blk256_mul_test);
	run_test(blk256_mult_blk128_neg);
	run_test(blk256_sub_negatives);
	run_test(blk256_sub_simple_1);
	run_test(blk256_sub_simple_2);
	run_test(blk256_sub_simple_3);
	run_test(blk256_sub_simple_4);
	run_test(blk256_sub_simple_5);
	run_test(blk256_sub_large);
	run_test(blk256_sub_large_neg);
	run_test(blk256_sub_pos_from_neg);

	run_test(blk256_div_neg_zero);
	run_test(blk256_div_flip_flop);
	run_test(blk256_div_neg_in_range);

	test_fixture_end();
}