1// Copyright 2013 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package bytes_test
6
7import (
8	. "bytes"
9	"fmt"
10	"testing"
11)
12
13var compareTests = []struct {
14	a, b []byte
15	i    int
16}{
17	{[]byte(""), []byte(""), 0},
18	{[]byte("a"), []byte(""), 1},
19	{[]byte(""), []byte("a"), -1},
20	{[]byte("abc"), []byte("abc"), 0},
21	{[]byte("abd"), []byte("abc"), 1},
22	{[]byte("abc"), []byte("abd"), -1},
23	{[]byte("ab"), []byte("abc"), -1},
24	{[]byte("abc"), []byte("ab"), 1},
25	{[]byte("x"), []byte("ab"), 1},
26	{[]byte("ab"), []byte("x"), -1},
27	{[]byte("x"), []byte("a"), 1},
28	{[]byte("b"), []byte("x"), -1},
29	// test runtime·memeq's chunked implementation
30	{[]byte("abcdefgh"), []byte("abcdefgh"), 0},
31	{[]byte("abcdefghi"), []byte("abcdefghi"), 0},
32	{[]byte("abcdefghi"), []byte("abcdefghj"), -1},
33	{[]byte("abcdefghj"), []byte("abcdefghi"), 1},
34	// nil tests
35	{nil, nil, 0},
36	{[]byte(""), nil, 0},
37	{nil, []byte(""), 0},
38	{[]byte("a"), nil, 1},
39	{nil, []byte("a"), -1},
40}
41
42func TestCompare(t *testing.T) {
43	for _, tt := range compareTests {
44		numShifts := 16
45		buffer := make([]byte, len(tt.b)+numShifts)
46		// vary the input alignment of tt.b
47		for offset := 0; offset <= numShifts; offset++ {
48			shiftedB := buffer[offset : len(tt.b)+offset]
49			copy(shiftedB, tt.b)
50			cmp := Compare(tt.a, shiftedB)
51			if cmp != tt.i {
52				t.Errorf(`Compare(%q, %q), offset %d = %v; want %v`, tt.a, tt.b, offset, cmp, tt.i)
53			}
54		}
55	}
56}
57
58func TestCompareIdenticalSlice(t *testing.T) {
59	var b = []byte("Hello Gophers!")
60	if Compare(b, b) != 0 {
61		t.Error("b != b")
62	}
63	if Compare(b, b[:1]) != 1 {
64		t.Error("b > b[:1] failed")
65	}
66}
67
68func TestCompareBytes(t *testing.T) {
69	lengths := make([]int, 0) // lengths to test in ascending order
70	for i := 0; i <= 128; i++ {
71		lengths = append(lengths, i)
72	}
73	lengths = append(lengths, 256, 512, 1024, 1333, 4095, 4096, 4097)
74
75	if !testing.Short() {
76		lengths = append(lengths, 65535, 65536, 65537, 99999)
77	}
78
79	n := lengths[len(lengths)-1]
80	a := make([]byte, n+1)
81	b := make([]byte, n+1)
82	for _, len := range lengths {
83		// randomish but deterministic data. No 0 or 255.
84		for i := 0; i < len; i++ {
85			a[i] = byte(1 + 31*i%254)
86			b[i] = byte(1 + 31*i%254)
87		}
88		// data past the end is different
89		for i := len; i <= n; i++ {
90			a[i] = 8
91			b[i] = 9
92		}
93		cmp := Compare(a[:len], b[:len])
94		if cmp != 0 {
95			t.Errorf(`CompareIdentical(%d) = %d`, len, cmp)
96		}
97		if len > 0 {
98			cmp = Compare(a[:len-1], b[:len])
99			if cmp != -1 {
100				t.Errorf(`CompareAshorter(%d) = %d`, len, cmp)
101			}
102			cmp = Compare(a[:len], b[:len-1])
103			if cmp != 1 {
104				t.Errorf(`CompareBshorter(%d) = %d`, len, cmp)
105			}
106		}
107		for k := 0; k < len; k++ {
108			b[k] = a[k] - 1
109			cmp = Compare(a[:len], b[:len])
110			if cmp != 1 {
111				t.Errorf(`CompareAbigger(%d,%d) = %d`, len, k, cmp)
112			}
113			b[k] = a[k] + 1
114			cmp = Compare(a[:len], b[:len])
115			if cmp != -1 {
116				t.Errorf(`CompareBbigger(%d,%d) = %d`, len, k, cmp)
117			}
118			b[k] = a[k]
119		}
120	}
121}
122
123func TestEndianBaseCompare(t *testing.T) {
124	// This test compares byte slices that are almost identical, except one
125	// difference that for some j, a[j]>b[j] and a[j+1]<b[j+1]. If the implementation
126	// compares large chunks with wrong endianness, it gets wrong result.
127	// no vector register is larger than 512 bytes for now
128	const maxLength = 512
129	a := make([]byte, maxLength)
130	b := make([]byte, maxLength)
131	// randomish but deterministic data. No 0 or 255.
132	for i := 0; i < maxLength; i++ {
133		a[i] = byte(1 + 31*i%254)
134		b[i] = byte(1 + 31*i%254)
135	}
136	for i := 2; i <= maxLength; i <<= 1 {
137		for j := 0; j < i-1; j++ {
138			a[j] = b[j] - 1
139			a[j+1] = b[j+1] + 1
140			cmp := Compare(a[:i], b[:i])
141			if cmp != -1 {
142				t.Errorf(`CompareBbigger(%d,%d) = %d`, i, j, cmp)
143			}
144			a[j] = b[j] + 1
145			a[j+1] = b[j+1] - 1
146			cmp = Compare(a[:i], b[:i])
147			if cmp != 1 {
148				t.Errorf(`CompareAbigger(%d,%d) = %d`, i, j, cmp)
149			}
150			a[j] = b[j]
151			a[j+1] = b[j+1]
152		}
153	}
154}
155
156func BenchmarkCompareBytesEqual(b *testing.B) {
157	b1 := []byte("Hello Gophers!")
158	b2 := []byte("Hello Gophers!")
159	for i := 0; i < b.N; i++ {
160		if Compare(b1, b2) != 0 {
161			b.Fatal("b1 != b2")
162		}
163	}
164}
165
166func BenchmarkCompareBytesToNil(b *testing.B) {
167	b1 := []byte("Hello Gophers!")
168	var b2 []byte
169	for i := 0; i < b.N; i++ {
170		if Compare(b1, b2) != 1 {
171			b.Fatal("b1 > b2 failed")
172		}
173	}
174}
175
176func BenchmarkCompareBytesEmpty(b *testing.B) {
177	b1 := []byte("")
178	b2 := b1
179	for i := 0; i < b.N; i++ {
180		if Compare(b1, b2) != 0 {
181			b.Fatal("b1 != b2")
182		}
183	}
184}
185
186func BenchmarkCompareBytesIdentical(b *testing.B) {
187	b1 := []byte("Hello Gophers!")
188	b2 := b1
189	for i := 0; i < b.N; i++ {
190		if Compare(b1, b2) != 0 {
191			b.Fatal("b1 != b2")
192		}
193	}
194}
195
196func BenchmarkCompareBytesSameLength(b *testing.B) {
197	b1 := []byte("Hello Gophers!")
198	b2 := []byte("Hello, Gophers")
199	for i := 0; i < b.N; i++ {
200		if Compare(b1, b2) != -1 {
201			b.Fatal("b1 < b2 failed")
202		}
203	}
204}
205
206func BenchmarkCompareBytesDifferentLength(b *testing.B) {
207	b1 := []byte("Hello Gophers!")
208	b2 := []byte("Hello, Gophers!")
209	for i := 0; i < b.N; i++ {
210		if Compare(b1, b2) != -1 {
211			b.Fatal("b1 < b2 failed")
212		}
213	}
214}
215
216func benchmarkCompareBytesBigUnaligned(b *testing.B, offset int) {
217	b.StopTimer()
218	b1 := make([]byte, 0, 1<<20)
219	for len(b1) < 1<<20 {
220		b1 = append(b1, "Hello Gophers!"...)
221	}
222	b2 := append([]byte("12345678")[:offset], b1...)
223	b.StartTimer()
224	for j := 0; j < b.N; j++ {
225		if Compare(b1, b2[offset:]) != 0 {
226			b.Fatal("b1 != b2")
227		}
228	}
229	b.SetBytes(int64(len(b1)))
230}
231
232func BenchmarkCompareBytesBigUnaligned(b *testing.B) {
233	for i := 1; i < 8; i++ {
234		b.Run(fmt.Sprintf("offset=%d", i), func(b *testing.B) {
235			benchmarkCompareBytesBigUnaligned(b, i)
236		})
237	}
238}
239
240func benchmarkCompareBytesBigBothUnaligned(b *testing.B, offset int) {
241	b.StopTimer()
242	pattern := []byte("Hello Gophers!")
243	b1 := make([]byte, 0, 1<<20+len(pattern))
244	for len(b1) < 1<<20 {
245		b1 = append(b1, pattern...)
246	}
247	b2 := make([]byte, len(b1))
248	copy(b2, b1)
249	b.StartTimer()
250	for j := 0; j < b.N; j++ {
251		if Compare(b1[offset:], b2[offset:]) != 0 {
252			b.Fatal("b1 != b2")
253		}
254	}
255	b.SetBytes(int64(len(b1[offset:])))
256}
257
258func BenchmarkCompareBytesBigBothUnaligned(b *testing.B) {
259	for i := 0; i < 8; i++ {
260		b.Run(fmt.Sprintf("offset=%d", i), func(b *testing.B) {
261			benchmarkCompareBytesBigBothUnaligned(b, i)
262		})
263	}
264}
265
266func BenchmarkCompareBytesBig(b *testing.B) {
267	b.StopTimer()
268	b1 := make([]byte, 0, 1<<20)
269	for len(b1) < 1<<20 {
270		b1 = append(b1, "Hello Gophers!"...)
271	}
272	b2 := append([]byte{}, b1...)
273	b.StartTimer()
274	for i := 0; i < b.N; i++ {
275		if Compare(b1, b2) != 0 {
276			b.Fatal("b1 != b2")
277		}
278	}
279	b.SetBytes(int64(len(b1)))
280}
281
282func BenchmarkCompareBytesBigIdentical(b *testing.B) {
283	b.StopTimer()
284	b1 := make([]byte, 0, 1<<20)
285	for len(b1) < 1<<20 {
286		b1 = append(b1, "Hello Gophers!"...)
287	}
288	b2 := b1
289	b.StartTimer()
290	for i := 0; i < b.N; i++ {
291		if Compare(b1, b2) != 0 {
292			b.Fatal("b1 != b2")
293		}
294	}
295	b.SetBytes(int64(len(b1)))
296}
297