Test of different packet number recovery options

pn_test.go

package minq_test

import "testing"

func recoverMinq(expected uint64, pn uint64, size int) uint64 {
	// Mask off the top of the expected sequence number
	mask := uint64(1)
	mask = (mask << (uint8(size) * 8)) - 1
	expectedLow := mask & expected
	high := ^mask & expected
	match := high | pn

	// Exact match
	if expectedLow == pn {
		return match
	}

	if pn > expectedLow {
		if high == 0 {
			return match
		}
		wrap := (high - 1) | pn
		if (expected - wrap) <= (match - expected) {
			return wrap
		}
		return match
	}

	// expectedLow > pn
	wrap := (high + 1) | pn
	if (expected - match) <= (wrap - expected) {
		return match
	}
	return wrap
}

func recoverSpec(expected_pn uint64, truncated_pn uint64, size int) uint64 {
	pn_bits := uint(size * 8)
	pn_win := uint64(1) << pn_bits
	pn_hwin := pn_win / 2
	pn_mask := pn_win - 1
	// The incoming packet number should be greater than
	// expected_pn - pn_hwin and less than or equal to
	// expected_pn + pn_hwin
	//
	// This means we can't just strip the trailing bits from
	// expected_pn and add the truncated_pn because that might
	// yield a value outside the window.
	//
	// The following code calculates a candidate value and
	// makes sure it's within the packet number window.
	candidate_pn := (expected_pn & ^pn_mask) | truncated_pn
	// Note: I had to add an extra check here, otherwise the
	// test would pass when expected_pn-pn_hwin underflowed.
	// The original code only works in untyped languages.
	if (expected_pn >= pn_hwin) &&
		(candidate_pn <= expected_pn-pn_hwin) {
		return candidate_pn + pn_win
	}
	// Note the extra check for underflow when candidate_pn
	// is near zero.
	if (candidate_pn > expected_pn+pn_hwin) &&
		(candidate_pn > pn_win) {
		return candidate_pn - pn_win
	}
	return candidate_pn
}

func recoverMt(expected uint64, truncated uint64, size int) uint64 {
	fullRange := uint64(1) << uint(size<<3)
	mask := fullRange - 1
	cap := expected + fullRange/2
	pn := (cap & ^mask) | truncated
	if (truncated > cap&mask) && (pn >= fullRange) {
		pn -= fullRange
	}
	return pn
}

func absDiff(a uint64, b uint64) uint64 {
	if a > b {
		return a - b
	}
	return b - a
}

func recoverTest(t *testing.T, f func(expected uint64, pn uint64, size int) uint64,
	expected uint64, next uint64, truncated uint64, size int) {
	result := f(next, truncated, size)
	if result != expected {
		resultDifference := absDiff(result, next)
		expectedDifference := absDiff(expected, next)
		if resultDifference < expectedDifference {
			t.Logf("test error: expected distance is %x; result is closer at %x",
				expectedDifference, resultDifference)
			if resultDifference >= uint64(1)<<uint(2+size) {
				// The result can't be more than half the expressible range.
				t.Logf("result is still wrong though")
			}
		}

		t.Errorf("recover(0x%x, 0x%x, %d) got 0x%x; expected 0x%x",
			next, truncated, size, result, expected)
	}
}

var packetNumberTests = []struct {
	expected  uint64
	next      uint64
	truncated uint64
	size      int
}{
	// Test that we get 0 for an input of 0 up to half the range.
	{0, 0, 0, 1},
	{0, 0, 0, 2},
	{0, 0, 0, 4},
	{0, 0x7f, 0, 1},
	{0, 0x7fff, 0, 2},
	{0, 0x7fffffff, 0, 4},
	// Test that the crossover works.
	{0x100, 0x80, 0, 1},
	{0x10000, 0x8000, 0, 2},
	{0x100000000, 0x80000000, 0, 4},
	// And that the top of that range is OK.
	{0x100, 0x17f, 0, 1},
	{0x10000, 0x17fff, 0, 2},
	{0x100000000, 0x17fffffff, 0, 4},

	// Now test that increasing the input has the desired effect.
	{1, 0, 1, 1},
	{1, 0, 1, 2},
	{1, 0, 1, 4},
	{1, 0x80, 1, 1},
	{1, 0x8000, 1, 2},
	{1, 0x80000000, 1, 4},
	{0x101, 0x81, 1, 1},
	{0x10001, 0x8001, 1, 2},
	{0x100000001, 0x80000001, 1, 4},

	// These are special - the natural implementation underflows near zero for large inputs.
	{0xff, 0, 0xff, 1},
	{0xffff, 0, 0xffff, 2},
	{0xffffffff, 0, 0xffffffff, 4},
	// For higher values of the next packet number, the recovered value can be smaller.
	{0xff, 0x100, 0xff, 1},
	{0xffff, 0x10000, 0xffff, 2},
	{0xffffffff, 0x10000000, 0xffffffff, 4},
	{0xff, 0x17e, 0xff, 1},
	{0xffff, 0x17ffe, 0xffff, 2},
	{0xffffffff, 0x17ffffffe, 0xffffffff, 4},
	{0x1ff, 0x17f, 0xff, 1},
	{0x1ffff, 0x17fff, 0xffff, 2},
	{0x1ffffffff, 0x17fffffff, 0xffffffff, 4},
}

func TestPacketNumbersMinq(t *testing.T) {
	for _, tc := range packetNumberTests {
		recoverTest(t, recoverMinq, tc.expected, tc.next, tc.truncated, tc.size)
	}
}

func TestPacketNumbersSpec(t *testing.T) {
	for _, tc := range packetNumberTests {
		recoverTest(t, recoverSpec, tc.expected, tc.next, tc.truncated, tc.size)
	}
}

func TestPacketNumbersMt(t *testing.T) {
	for _, tc := range packetNumberTests {
		recoverTest(t, recoverMt, tc.expected, tc.next, tc.truncated, tc.size)
	}
}