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