1package tsm1
2
3import (
4	"fmt"
5	"math"
6	"math/rand"
7	"reflect"
8	"testing"
9	"testing/quick"
10)
11
12func Test_IntegerEncoder_NoValues(t *testing.T) {
13	enc := NewIntegerEncoder(0)
14	b, err := enc.Bytes()
15	if err != nil {
16		t.Fatalf("unexpected error: %v", err)
17	}
18
19	if len(b) > 0 {
20		t.Fatalf("unexpected length: exp 0, got %v", len(b))
21	}
22
23	var dec IntegerDecoder
24	dec.SetBytes(b)
25	if dec.Next() {
26		t.Fatalf("unexpected next value: got true, exp false")
27	}
28}
29
30func Test_IntegerEncoder_One(t *testing.T) {
31	enc := NewIntegerEncoder(1)
32	v1 := int64(1)
33
34	enc.Write(1)
35	b, err := enc.Bytes()
36	if err != nil {
37		t.Fatalf("unexpected error: %v", err)
38	}
39
40	if got := b[0] >> 4; intCompressedSimple != got {
41		t.Fatalf("encoding type mismatch: exp uncompressed, got %v", got)
42	}
43
44	var dec IntegerDecoder
45	dec.SetBytes(b)
46	if !dec.Next() {
47		t.Fatalf("unexpected next value: got true, exp false")
48	}
49
50	if v1 != dec.Read() {
51		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v1)
52	}
53}
54
55func Test_IntegerEncoder_Two(t *testing.T) {
56	enc := NewIntegerEncoder(2)
57	var v1, v2 int64 = 1, 2
58
59	enc.Write(v1)
60	enc.Write(v2)
61
62	b, err := enc.Bytes()
63	if err != nil {
64		t.Fatalf("unexpected error: %v", err)
65	}
66
67	if got := b[0] >> 4; intCompressedSimple != got {
68		t.Fatalf("encoding type mismatch: exp uncompressed, got %v", got)
69	}
70
71	var dec IntegerDecoder
72	dec.SetBytes(b)
73	if !dec.Next() {
74		t.Fatalf("unexpected next value: got true, exp false")
75	}
76
77	if v1 != dec.Read() {
78		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v1)
79	}
80
81	if !dec.Next() {
82		t.Fatalf("unexpected next value: got true, exp false")
83	}
84
85	if v2 != dec.Read() {
86		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v2)
87	}
88}
89
90func Test_IntegerEncoder_Negative(t *testing.T) {
91	enc := NewIntegerEncoder(3)
92	var v1, v2, v3 int64 = -2, 0, 1
93
94	enc.Write(v1)
95	enc.Write(v2)
96	enc.Write(v3)
97
98	b, err := enc.Bytes()
99	if err != nil {
100		t.Fatalf("unexpected error: %v", err)
101	}
102
103	if got := b[0] >> 4; intCompressedSimple != got {
104		t.Fatalf("encoding type mismatch: exp uncompressed, got %v", got)
105	}
106
107	var dec IntegerDecoder
108	dec.SetBytes(b)
109	if !dec.Next() {
110		t.Fatalf("unexpected next value: got true, exp false")
111	}
112
113	if v1 != dec.Read() {
114		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v1)
115	}
116
117	if !dec.Next() {
118		t.Fatalf("unexpected next value: got true, exp false")
119	}
120
121	if v2 != dec.Read() {
122		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v2)
123	}
124
125	if !dec.Next() {
126		t.Fatalf("unexpected next value: got true, exp false")
127	}
128
129	if v3 != dec.Read() {
130		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v3)
131	}
132}
133
134func Test_IntegerEncoder_Large_Range(t *testing.T) {
135	enc := NewIntegerEncoder(2)
136	var v1, v2 int64 = math.MinInt64, math.MaxInt64
137	enc.Write(v1)
138	enc.Write(v2)
139	b, err := enc.Bytes()
140	if err != nil {
141		t.Fatalf("unexpected error: %v", err)
142	}
143
144	if got := b[0] >> 4; intUncompressed != got {
145		t.Fatalf("encoding type mismatch: exp uncompressed, got %v", got)
146	}
147
148	var dec IntegerDecoder
149	dec.SetBytes(b)
150	if !dec.Next() {
151		t.Fatalf("unexpected next value: got true, exp false")
152	}
153
154	if v1 != dec.Read() {
155		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v1)
156	}
157
158	if !dec.Next() {
159		t.Fatalf("unexpected next value: got true, exp false")
160	}
161
162	if v2 != dec.Read() {
163		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v2)
164	}
165}
166
167func Test_IntegerEncoder_Uncompressed(t *testing.T) {
168	enc := NewIntegerEncoder(3)
169	var v1, v2, v3 int64 = 0, 1, 1 << 60
170
171	enc.Write(v1)
172	enc.Write(v2)
173	enc.Write(v3)
174
175	b, err := enc.Bytes()
176	if err != nil {
177		t.Fatalf("expected error: %v", err)
178	}
179
180	// 1 byte header + 3 * 8 byte values
181	if exp := 25; len(b) != exp {
182		t.Fatalf("length mismatch: got %v, exp %v", len(b), exp)
183	}
184
185	if got := b[0] >> 4; intUncompressed != got {
186		t.Fatalf("encoding type mismatch: exp uncompressed, got %v", got)
187	}
188
189	var dec IntegerDecoder
190	dec.SetBytes(b)
191	if !dec.Next() {
192		t.Fatalf("unexpected next value: got true, exp false")
193	}
194
195	if v1 != dec.Read() {
196		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v1)
197	}
198
199	if !dec.Next() {
200		t.Fatalf("unexpected next value: got true, exp false")
201	}
202
203	if v2 != dec.Read() {
204		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v2)
205	}
206
207	if !dec.Next() {
208		t.Fatalf("unexpected next value: got true, exp false")
209	}
210
211	if v3 != dec.Read() {
212		t.Fatalf("read value mismatch: got %v, exp %v", dec.Read(), v3)
213	}
214}
215
216func Test_IntegerEncoder_NegativeUncompressed(t *testing.T) {
217	values := []int64{
218		-2352281900722994752, 1438442655375607923, -4110452567888190110,
219		-1221292455668011702, -1941700286034261841, -2836753127140407751,
220		1432686216250034552, 3663244026151507025, -3068113732684750258,
221		-1949953187327444488, 3713374280993588804, 3226153669854871355,
222		-2093273755080502606, 1006087192578600616, -2272122301622271655,
223		2533238229511593671, -4450454445568858273, 2647789901083530435,
224		2761419461769776844, -1324397441074946198, -680758138988210958,
225		94468846694902125, -2394093124890745254, -2682139311758778198,
226	}
227	enc := NewIntegerEncoder(256)
228	for _, v := range values {
229		enc.Write(v)
230	}
231
232	b, err := enc.Bytes()
233	if err != nil {
234		t.Fatalf("expected error: %v", err)
235	}
236
237	if got := b[0] >> 4; intUncompressed != got {
238		t.Fatalf("encoding type mismatch: exp uncompressed, got %v", got)
239	}
240
241	var dec IntegerDecoder
242	dec.SetBytes(b)
243
244	i := 0
245	for dec.Next() {
246		if i > len(values) {
247			t.Fatalf("read too many values: got %v, exp %v", i, len(values))
248		}
249
250		if values[i] != dec.Read() {
251			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), values[i])
252		}
253		i += 1
254	}
255
256	if i != len(values) {
257		t.Fatalf("failed to read enough values: got %v, exp %v", i, len(values))
258	}
259}
260
261func Test_IntegerEncoder_AllNegative(t *testing.T) {
262	enc := NewIntegerEncoder(3)
263	values := []int64{
264		-10, -5, -1,
265	}
266
267	for _, v := range values {
268		enc.Write(v)
269	}
270
271	b, err := enc.Bytes()
272	if err != nil {
273		t.Fatalf("unexpected error: %v", err)
274	}
275
276	if got := b[0] >> 4; intCompressedSimple != got {
277		t.Fatalf("encoding type mismatch: exp uncompressed, got %v", got)
278	}
279
280	var dec IntegerDecoder
281	dec.SetBytes(b)
282	i := 0
283	for dec.Next() {
284		if i > len(values) {
285			t.Fatalf("read too many values: got %v, exp %v", i, len(values))
286		}
287
288		if values[i] != dec.Read() {
289			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), values[i])
290		}
291		i += 1
292	}
293
294	if i != len(values) {
295		t.Fatalf("failed to read enough values: got %v, exp %v", i, len(values))
296	}
297}
298
299func Test_IntegerEncoder_CounterPacked(t *testing.T) {
300	enc := NewIntegerEncoder(16)
301	values := []int64{
302		1e15, 1e15 + 1, 1e15 + 2, 1e15 + 3, 1e15 + 4, 1e15 + 6,
303	}
304
305	for _, v := range values {
306		enc.Write(v)
307	}
308
309	b, err := enc.Bytes()
310	if err != nil {
311		t.Fatalf("unexpected error: %v", err)
312	}
313
314	if b[0]>>4 != intCompressedSimple {
315		t.Fatalf("unexpected encoding format: expected simple, got %v", b[0]>>4)
316	}
317
318	// Should use 1 header byte + 2, 8 byte words if delta-encoding is used based on
319	// values sizes.  Without delta-encoding, we'd get 49 bytes.
320	if exp := 17; len(b) != exp {
321		t.Fatalf("encoded length mismatch: got %v, exp %v", len(b), exp)
322	}
323
324	var dec IntegerDecoder
325	dec.SetBytes(b)
326	i := 0
327	for dec.Next() {
328		if i > len(values) {
329			t.Fatalf("read too many values: got %v, exp %v", i, len(values))
330		}
331
332		if values[i] != dec.Read() {
333			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), values[i])
334		}
335		i += 1
336	}
337
338	if i != len(values) {
339		t.Fatalf("failed to read enough values: got %v, exp %v", i, len(values))
340	}
341}
342
343func Test_IntegerEncoder_CounterRLE(t *testing.T) {
344	enc := NewIntegerEncoder(16)
345	values := []int64{
346		1e15, 1e15 + 1, 1e15 + 2, 1e15 + 3, 1e15 + 4, 1e15 + 5,
347	}
348
349	for _, v := range values {
350		enc.Write(v)
351	}
352
353	b, err := enc.Bytes()
354	if err != nil {
355		t.Fatalf("unexpected error: %v", err)
356	}
357
358	if b[0]>>4 != intCompressedRLE {
359		t.Fatalf("unexpected encoding format: expected RLE, got %v", b[0]>>4)
360	}
361
362	// Should use 1 header byte, 8 byte first value, 1 var-byte for delta and 1 var-byte for
363	// count of deltas in this particular RLE.
364	if exp := 11; len(b) != exp {
365		t.Fatalf("encoded length mismatch: got %v, exp %v", len(b), exp)
366	}
367
368	var dec IntegerDecoder
369	dec.SetBytes(b)
370	i := 0
371	for dec.Next() {
372		if i > len(values) {
373			t.Fatalf("read too many values: got %v, exp %v", i, len(values))
374		}
375
376		if values[i] != dec.Read() {
377			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), values[i])
378		}
379		i += 1
380	}
381
382	if i != len(values) {
383		t.Fatalf("failed to read enough values: got %v, exp %v", i, len(values))
384	}
385}
386
387func Test_IntegerEncoder_Descending(t *testing.T) {
388	enc := NewIntegerEncoder(16)
389	values := []int64{
390		7094, 4472, 1850,
391	}
392
393	for _, v := range values {
394		enc.Write(v)
395	}
396
397	b, err := enc.Bytes()
398	if err != nil {
399		t.Fatalf("unexpected error: %v", err)
400	}
401
402	if b[0]>>4 != intCompressedRLE {
403		t.Fatalf("unexpected encoding format: expected simple, got %v", b[0]>>4)
404	}
405
406	// Should use 1 header byte, 8 byte first value, 1 var-byte for delta and 1 var-byte for
407	// count of deltas in this particular RLE.
408	if exp := 12; len(b) != exp {
409		t.Fatalf("encoded length mismatch: got %v, exp %v", len(b), exp)
410	}
411
412	var dec IntegerDecoder
413	dec.SetBytes(b)
414	i := 0
415	for dec.Next() {
416		if i > len(values) {
417			t.Fatalf("read too many values: got %v, exp %v", i, len(values))
418		}
419
420		if values[i] != dec.Read() {
421			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), values[i])
422		}
423		i += 1
424	}
425
426	if i != len(values) {
427		t.Fatalf("failed to read enough values: got %v, exp %v", i, len(values))
428	}
429}
430
431func Test_IntegerEncoder_Flat(t *testing.T) {
432	enc := NewIntegerEncoder(16)
433	values := []int64{
434		1, 1, 1, 1,
435	}
436
437	for _, v := range values {
438		enc.Write(v)
439	}
440
441	b, err := enc.Bytes()
442	if err != nil {
443		t.Fatalf("unexpected error: %v", err)
444	}
445
446	if b[0]>>4 != intCompressedRLE {
447		t.Fatalf("unexpected encoding format: expected simple, got %v", b[0]>>4)
448	}
449
450	// Should use 1 header byte, 8 byte first value, 1 var-byte for delta and 1 var-byte for
451	// count of deltas in this particular RLE.
452	if exp := 11; len(b) != exp {
453		t.Fatalf("encoded length mismatch: got %v, exp %v", len(b), exp)
454	}
455
456	var dec IntegerDecoder
457	dec.SetBytes(b)
458	i := 0
459	for dec.Next() {
460		if i > len(values) {
461			t.Fatalf("read too many values: got %v, exp %v", i, len(values))
462		}
463
464		if values[i] != dec.Read() {
465			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), values[i])
466		}
467		i += 1
468	}
469
470	if i != len(values) {
471		t.Fatalf("failed to read enough values: got %v, exp %v", i, len(values))
472	}
473}
474
475func Test_IntegerEncoder_MinMax(t *testing.T) {
476	enc := NewIntegerEncoder(2)
477	values := []int64{
478		math.MinInt64, math.MaxInt64,
479	}
480
481	for _, v := range values {
482		enc.Write(v)
483	}
484
485	b, err := enc.Bytes()
486	if err != nil {
487		t.Fatalf("unexpected error: %v", err)
488	}
489
490	if b[0]>>4 != intUncompressed {
491		t.Fatalf("unexpected encoding format: expected simple, got %v", b[0]>>4)
492	}
493
494	if exp := 17; len(b) != exp {
495		t.Fatalf("encoded length mismatch: got %v, exp %v", len(b), exp)
496	}
497
498	var dec IntegerDecoder
499	dec.SetBytes(b)
500	i := 0
501	for dec.Next() {
502		if i > len(values) {
503			t.Fatalf("read too many values: got %v, exp %v", i, len(values))
504		}
505
506		if values[i] != dec.Read() {
507			t.Fatalf("read value %d mismatch: got %v, exp %v", i, dec.Read(), values[i])
508		}
509		i += 1
510	}
511
512	if i != len(values) {
513		t.Fatalf("failed to read enough values: got %v, exp %v", i, len(values))
514	}
515}
516
517func Test_IntegerEncoder_Quick(t *testing.T) {
518	quick.Check(func(values []int64) bool {
519		expected := values
520		if values == nil {
521			expected = []int64{} // is this really expected?
522		}
523
524		// Write values to encoder.
525		enc := NewIntegerEncoder(1024)
526		for _, v := range values {
527			enc.Write(v)
528		}
529
530		// Retrieve encoded bytes from encoder.
531		buf, err := enc.Bytes()
532		if err != nil {
533			t.Fatal(err)
534		}
535
536		// Read values out of decoder.
537		got := make([]int64, 0, len(values))
538		var dec IntegerDecoder
539		dec.SetBytes(buf)
540		for dec.Next() {
541			if err := dec.Error(); err != nil {
542				t.Fatal(err)
543			}
544			got = append(got, dec.Read())
545		}
546
547		// Verify that input and output values match.
548		if !reflect.DeepEqual(expected, got) {
549			t.Fatalf("mismatch:\n\nexp=%#v\n\ngot=%#v\n\n", expected, got)
550		}
551
552		return true
553	}, nil)
554}
555
556func Test_IntegerDecoder_Corrupt(t *testing.T) {
557	cases := []string{
558		"",                     // Empty
559		"\x00abc",              // Uncompressed: less than 8 bytes
560		"\x10abc",              // Packed: less than 8 bytes
561		"\x20abc",              // RLE: less than 8 bytes
562		"\x2012345678\x90",     // RLE: valid starting value but invalid delta value
563		"\x2012345678\x01\x90", // RLE: valid starting, valid delta value, invalid repeat value
564	}
565
566	for _, c := range cases {
567		var dec IntegerDecoder
568		dec.SetBytes([]byte(c))
569		if dec.Next() {
570			t.Fatalf("exp next == false, got true")
571		}
572	}
573}
574
575func BenchmarkIntegerEncoderRLE(b *testing.B) {
576	enc := NewIntegerEncoder(1024)
577	x := make([]int64, 1024)
578	for i := 0; i < len(x); i++ {
579		x[i] = int64(i)
580		enc.Write(x[i])
581	}
582
583	b.ResetTimer()
584	for i := 0; i < b.N; i++ {
585		enc.Bytes()
586	}
587}
588
589func BenchmarkIntegerEncoderPackedSimple(b *testing.B) {
590	enc := NewIntegerEncoder(1024)
591	x := make([]int64, 1024)
592	for i := 0; i < len(x); i++ {
593		// Small amount of randomness prevents RLE from being used
594		x[i] = int64(i) + int64(rand.Intn(10))
595		enc.Write(x[i])
596	}
597
598	b.ResetTimer()
599	for i := 0; i < b.N; i++ {
600		enc.Bytes()
601		enc.Reset()
602		for i := 0; i < len(x); i++ {
603			enc.Write(x[i])
604		}
605	}
606}
607
608func BenchmarkIntegerBatch_DecodeAllUncompressed(b *testing.B) {
609	benchmarks := []struct {
610		n int
611	}{
612		{5},
613		{55},
614		{555},
615		{1000},
616	}
617
618	values := []int64{
619		-2352281900722994752, 1438442655375607923, -4110452567888190110,
620		-1221292455668011702, -1941700286034261841, -2836753127140407751,
621		1432686216250034552, 3663244026151507025, -3068113732684750258,
622		-1949953187327444488, 3713374280993588804, 3226153669854871355,
623		-2093273755080502606, 1006087192578600616, -2272122301622271655,
624		2533238229511593671, -4450454445568858273, 2647789901083530435,
625		2761419461769776844, -1324397441074946198, -680758138988210958,
626		94468846694902125, -2394093124890745254, -2682139311758778198,
627	}
628
629	for _, bm := range benchmarks {
630		rand.Seed(int64(bm.n * 1e3))
631
632		enc := NewIntegerEncoder(bm.n)
633		for i := 0; i < bm.n; i++ {
634			enc.Write(values[rand.Int()%len(values)])
635		}
636		bytes, _ := enc.Bytes()
637
638		b.Run(fmt.Sprintf("%d", bm.n), func(b *testing.B) {
639			b.SetBytes(int64(len(bytes)))
640			b.ReportAllocs()
641
642			dst := make([]int64, bm.n)
643			for i := 0; i < b.N; i++ {
644				var dec IntegerDecoder
645				dec.SetBytes(bytes)
646				var n int
647				for dec.Next() {
648					dst[n] = dec.Read()
649					n++
650				}
651			}
652		})
653	}
654}
655
656func BenchmarkIntegerBatch_DecodeAllPackedSimple(b *testing.B) {
657	benchmarks := []struct {
658		n int
659	}{
660		{5},
661		{55},
662		{555},
663		{1000},
664	}
665	for _, bm := range benchmarks {
666		rand.Seed(int64(bm.n * 1e3))
667
668		enc := NewIntegerEncoder(bm.n)
669		for i := 0; i < bm.n; i++ {
670			// Small amount of randomness prevents RLE from being used
671			enc.Write(int64(i) + int64(rand.Intn(10)))
672		}
673		bytes, _ := enc.Bytes()
674
675		b.Run(fmt.Sprintf("%d", bm.n), func(b *testing.B) {
676			b.SetBytes(int64(len(bytes)))
677			b.ReportAllocs()
678
679			dst := make([]int64, bm.n)
680			for i := 0; i < b.N; i++ {
681				var dec IntegerDecoder
682				dec.SetBytes(bytes)
683				var n int
684				for dec.Next() {
685					dst[n] = dec.Read()
686					n++
687				}
688			}
689		})
690	}
691}
692
693func BenchmarkIntegerBatch_DecodeAllRLE(b *testing.B) {
694	benchmarks := []struct {
695		n     int
696		delta int64
697	}{
698		{5, 1},
699		{55, 1},
700		{555, 1},
701		{1000, 1},
702		{1000, 0},
703	}
704	for _, bm := range benchmarks {
705		enc := NewIntegerEncoder(bm.n)
706		acc := int64(0)
707		for i := 0; i < bm.n; i++ {
708			enc.Write(acc)
709			acc += bm.delta
710		}
711		bytes, _ := enc.Bytes()
712
713		b.Run(fmt.Sprintf("%d_delta_%d", bm.n, bm.delta), func(b *testing.B) {
714			b.SetBytes(int64(len(bytes)))
715			b.ReportAllocs()
716
717			dst := make([]int64, bm.n)
718			for i := 0; i < b.N; i++ {
719				var dec IntegerDecoder
720				dec.SetBytes(bytes)
721				var n int
722				for dec.Next() {
723					dst[n] = dec.Read()
724					n++
725				}
726			}
727		})
728	}
729}
730