reedsolomon/gf16_test.go at master · klauspost/reedsolomon · GitHub

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package reedsolomon

import "testing"

var gf16 LowLevel

func TestGF16MulZero(t *testing.T) {
	// Anything multiplied by zero is zero.
	for _, v := range []uint16{0, 1, 2, 100, 65535} {
		if got := gf16.GF16Mul(v, 0); got != 0 {
			t.Errorf("GF16Mul(%d, 0) = %d, want 0", v, got)
		}
		if got := gf16.GF16Mul(0, v); got != 0 {
			t.Errorf("GF16Mul(0, %d) = %d, want 0", v, got)
		}
	}
}

func TestGF16MulOne(t *testing.T) {
	initConstants()
	// Multiplying by 1 (the multiplicative identity) is a no-op.
	// The identity element in GF(2^16) is 1 (expLUT[0]).
	one := uint16(expLUT[0])
	for _, v := range []uint16{1, 2, 7, 255, 1000, 65535} {
		if got := gf16.GF16Mul(v, one); got != v {
			t.Errorf("GF16Mul(%d, 1) = %d, want %d", v, got, v)
		}
		if got := gf16.GF16Mul(one, v); got != v {
			t.Errorf("GF16Mul(1, %d) = %d, want %d", v, got, v)
		}
	}
}

func TestGF16MulCommutativity(t *testing.T) {
	cases := [][2]uint16{
		{1, 2}, {3, 5}, {255, 256}, {1000, 2000}, {65534, 65535},
	}
	for _, c := range cases {
		a, b := c[0], c[1]
		ab := gf16.GF16Mul(a, b)
		ba := gf16.GF16Mul(b, a)
		if ab != ba {
			t.Errorf("GF16Mul(%d, %d) = %d != GF16Mul(%d, %d) = %d", a, b, ab, b, a, ba)
		}
	}
}

func TestGF16MulAssociativity(t *testing.T) {
	a, b, c := uint16(3), uint16(5), uint16(7)
	// (a*b)*c == a*(b*c)
	lhs := gf16.GF16Mul(gf16.GF16Mul(a, b), c)
	rhs := gf16.GF16Mul(a, gf16.GF16Mul(b, c))
	if lhs != rhs {
		t.Errorf("associativity failed: (%d*%d)*%d=%d, %d*(%d*%d)=%d", a, b, c, lhs, a, b, c, rhs)
	}
}

func TestGF16MulDistributivity(t *testing.T) {
	// Addition in GF(2^16) is XOR. Distributivity: a*(b^c) == a*b ^ a*c.
	cases := [][3]uint16{
		{3, 5, 7}, {255, 256, 1000}, {1, 2, 3}, {65534, 65535, 1},
	}
	for _, c := range cases {
		a, b, cc := c[0], c[1], c[2]
		lhs := gf16.GF16Mul(a, b^cc)
		rhs := gf16.GF16Mul(a, b) ^ gf16.GF16Mul(a, cc)
		if lhs != rhs {
			t.Errorf("distributivity failed: %d*(%d^%d)=%d, %d*%d^%d*%d=%d", a, b, cc, lhs, a, b, a, cc, rhs)
		}
	}
}

func TestGF16MulConsistentWithInternal(t *testing.T) {
	initConstants()
	// GF16Mul(a, b) should agree with the internal mulLog when b != 0.
	cases := [][2]uint16{
		{1, 2}, {3, 5}, {255, 256}, {1000, 2000},
	}
	for _, c := range cases {
		a, b := c[0], c[1]
		want := uint16(mulLog(ffe(a), logLUT[ffe(b)]))
		got := gf16.GF16Mul(a, b)
		if got != want {
			t.Errorf("GF16Mul(%d, %d) = %d, internal mulLog gives %d", a, b, got, want)
		}
	}
}