-
Notifications
You must be signed in to change notification settings - Fork 13
/
varintdecode.c
2302 lines (2121 loc) · 109 KB
/
varintdecode.c
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#include "varintdecode.h"
#include <x86intrin.h>
#if defined(_MSC_VER)
#define ALIGNED(x) __declspec(align(x))
#else
#if defined(__GNUC__)
#define ALIGNED(x) __attribute__ ((aligned(x)))
#endif
#endif
#if defined(_MSC_VER)
# include <intrin.h>
/* 64-bit needs extending */
# define SIMDCOMP_CTZ(result, mask) do { \
unsigned long index; \
if (!_BitScanForward(&(index), (mask))) { \
(result) = 32U; \
} else { \
(result) = (uint32_t)(index); \
} \
} while (0)
#else
# define SIMDCOMP_CTZ(result, mask) \
result = __builtin_ctz(mask)
#endif
typedef struct index_bytes_consumed {
uint8_t index;
uint8_t bytes_consumed;
} index_bytes_consumed;
static index_bytes_consumed combined_lookup[] ALIGNED(0x1000) = {
{0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {48, 8}, {82, 6},
{160, 5}, {4, 7}, {40, 8}, {24, 8}, {127, 7}, {70, 6}, {109, 7},
{148, 5}, {165, 6}, {2, 7}, {36, 8}, {20, 8}, {121, 7}, {12, 8},
{56, 9}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {136, 8},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {34, 8}, {18, 8},
{119, 7}, {10, 8}, {52, 9}, {83, 7}, {160, 5}, {6, 8}, {44, 9},
{28, 9}, {130, 8}, {71, 7}, {112, 8}, {148, 5}, {166, 7}, {64, 4},
{93, 7}, {75, 7}, {124, 8}, {69, 7}, {106, 8}, {88, 8}, {162, 7},
{145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0},
{0, 0}, {0, 6}, {33, 8}, {17, 8}, {118, 6}, {9, 8}, {50, 9},
{82, 6}, {160, 5}, {5, 8}, {42, 9}, {26, 9}, {128, 8}, {70, 6},
{110, 8}, {148, 5}, {165, 6}, {3, 8}, {38, 9}, {22, 9}, {122, 8},
{14, 9}, {60, 10}, {86, 8}, {161, 6}, {66, 6}, {98, 8}, {80, 8},
{139, 9}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5},
{73, 5}, {120, 8}, {67, 5}, {102, 8}, {84, 8}, {160, 5}, {65, 5},
{96, 8}, {78, 8}, {133, 9}, {72, 8}, {115, 9}, {148, 5}, {167, 8},
{64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4},
{163, 8}, {145, 2}, {150, 3}, {146, 3}, {159, 8}, {0, 2}, {0, 0},
{0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7},
{49, 9}, {82, 6}, {160, 5}, {4, 7}, {41, 9}, {25, 9}, {127, 7},
{70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {37, 9}, {21, 9},
{121, 7}, {13, 9}, {58, 10}, {85, 7}, {161, 6}, {66, 6}, {97, 7},
{79, 7}, {137, 9}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7},
{35, 9}, {19, 9}, {119, 7}, {11, 9}, {54, 10}, {83, 7}, {160, 5},
{7, 9}, {46, 10}, {30, 10}, {131, 9}, {71, 7}, {113, 9}, {148, 5},
{166, 7}, {64, 4}, {93, 7}, {75, 7}, {125, 9}, {69, 7}, {107, 9},
{89, 9}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2},
{154, 7}, {0, 0}, {0, 0}, {0, 6}, {91, 5}, {73, 5}, {118, 6},
{67, 5}, {100, 6}, {82, 6}, {160, 5}, {65, 5}, {94, 6}, {76, 6},
{129, 9}, {70, 6}, {111, 9}, {148, 5}, {165, 6}, {64, 4}, {92, 6},
{74, 6}, {123, 9}, {68, 6}, {105, 9}, {87, 9}, {161, 6}, {66, 6},
{99, 9}, {81, 9}, {142, 10}, {145, 2}, {153, 6}, {149, 6}, {0, 0},
{64, 4}, {91, 5}, {73, 5}, {155, 4}, {67, 5}, {151, 4}, {147, 4},
{160, 5}, {65, 5}, {150, 3}, {146, 3}, {156, 5}, {145, 2}, {152, 5},
{148, 5}, {168, 9}, {64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2},
{151, 4}, {147, 4}, {164, 9}, {0, 2}, {0, 3}, {0, 3}, {0, 0},
{0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7},
{118, 6}, {8, 7}, {48, 8}, {82, 6}, {160, 5}, {4, 7}, {40, 8},
{24, 8}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7},
{36, 8}, {20, 8}, {121, 7}, {12, 8}, {57, 10}, {85, 7}, {161, 6},
{66, 6}, {97, 7}, {79, 7}, {136, 8}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {1, 7}, {34, 8}, {18, 8}, {119, 7}, {10, 8}, {53, 10},
{83, 7}, {160, 5}, {6, 8}, {45, 10}, {29, 10}, {130, 8}, {71, 7},
{112, 8}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {124, 8},
{69, 7}, {106, 8}, {88, 8}, {162, 7}, {145, 2}, {150, 3}, {146, 3},
{158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {33, 8},
{17, 8}, {118, 6}, {9, 8}, {51, 10}, {82, 6}, {160, 5}, {5, 8},
{43, 10}, {27, 10}, {128, 8}, {70, 6}, {110, 8}, {148, 5}, {165, 6},
{3, 8}, {39, 10}, {23, 10}, {122, 8}, {15, 10}, {62, 11}, {86, 8},
{161, 6}, {66, 6}, {98, 8}, {80, 8}, {140, 10}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5}, {120, 8}, {67, 5},
{102, 8}, {84, 8}, {160, 5}, {65, 5}, {96, 8}, {78, 8}, {134, 10},
{72, 8}, {116, 10}, {148, 5}, {167, 8}, {64, 4}, {150, 3}, {146, 3},
{155, 4}, {145, 2}, {151, 4}, {147, 4}, {163, 8}, {145, 2}, {150, 3},
{146, 3}, {159, 8}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6},
{32, 7}, {16, 7}, {118, 6}, {8, 7}, {100, 6}, {82, 6}, {160, 5},
{4, 7}, {94, 6}, {76, 6}, {127, 7}, {70, 6}, {109, 7}, {148, 5},
{165, 6}, {2, 7}, {92, 6}, {74, 6}, {121, 7}, {68, 6}, {103, 7},
{85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {138, 10}, {145, 2},
{153, 6}, {149, 6}, {0, 0}, {1, 7}, {91, 5}, {73, 5}, {119, 7},
{67, 5}, {101, 7}, {83, 7}, {160, 5}, {65, 5}, {95, 7}, {77, 7},
{132, 10}, {71, 7}, {114, 10}, {148, 5}, {166, 7}, {64, 4}, {93, 7},
{75, 7}, {126, 10}, {69, 7}, {108, 10}, {90, 10}, {162, 7}, {145, 2},
{150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0},
{0, 6}, {91, 5}, {73, 5}, {118, 6}, {67, 5}, {100, 6}, {82, 6},
{160, 5}, {65, 5}, {94, 6}, {76, 6}, {156, 5}, {70, 6}, {152, 5},
{148, 5}, {165, 6}, {64, 4}, {92, 6}, {74, 6}, {155, 4}, {68, 6},
{151, 4}, {147, 4}, {161, 6}, {66, 6}, {150, 3}, {146, 3}, {157, 6},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5},
{155, 4}, {67, 5}, {151, 4}, {147, 4}, {160, 5}, {65, 5}, {150, 3},
{146, 3}, {156, 5}, {145, 2}, {152, 5}, {148, 5}, {169, 10}, {0, 4},
{0, 3}, {0, 3}, {0, 4}, {0, 2}, {0, 4}, {0, 4}, {0, 0},
{0, 2}, {0, 3}, {0, 3}, {0, 0}, {0, 2}, {0, 0}, {0, 0},
{0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {48, 8},
{82, 6}, {160, 5}, {4, 7}, {40, 8}, {24, 8}, {127, 7}, {70, 6},
{109, 7}, {148, 5}, {165, 6}, {2, 7}, {36, 8}, {20, 8}, {121, 7},
{12, 8}, {56, 9}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7},
{136, 8}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {34, 8},
{18, 8}, {119, 7}, {10, 8}, {52, 9}, {83, 7}, {160, 5}, {6, 8},
{44, 9}, {28, 9}, {130, 8}, {71, 7}, {112, 8}, {148, 5}, {166, 7},
{64, 4}, {93, 7}, {75, 7}, {124, 8}, {69, 7}, {106, 8}, {88, 8},
{162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7},
{0, 0}, {0, 0}, {0, 6}, {33, 8}, {17, 8}, {118, 6}, {9, 8},
{50, 9}, {82, 6}, {160, 5}, {5, 8}, {42, 9}, {26, 9}, {128, 8},
{70, 6}, {110, 8}, {148, 5}, {165, 6}, {3, 8}, {38, 9}, {22, 9},
{122, 8}, {14, 9}, {61, 11}, {86, 8}, {161, 6}, {66, 6}, {98, 8},
{80, 8}, {139, 9}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4},
{91, 5}, {73, 5}, {120, 8}, {67, 5}, {102, 8}, {84, 8}, {160, 5},
{65, 5}, {96, 8}, {78, 8}, {133, 9}, {72, 8}, {115, 9}, {148, 5},
{167, 8}, {64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4},
{147, 4}, {163, 8}, {145, 2}, {150, 3}, {146, 3}, {159, 8}, {0, 2},
{0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6},
{8, 7}, {49, 9}, {82, 6}, {160, 5}, {4, 7}, {41, 9}, {25, 9},
{127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {37, 9},
{21, 9}, {121, 7}, {13, 9}, {59, 11}, {85, 7}, {161, 6}, {66, 6},
{97, 7}, {79, 7}, {137, 9}, {145, 2}, {153, 6}, {149, 6}, {0, 0},
{1, 7}, {35, 9}, {19, 9}, {119, 7}, {11, 9}, {55, 11}, {83, 7},
{160, 5}, {7, 9}, {47, 11}, {31, 11}, {131, 9}, {71, 7}, {113, 9},
{148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {125, 9}, {69, 7},
{107, 9}, {89, 9}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7},
{145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {91, 5}, {73, 5},
{118, 6}, {67, 5}, {100, 6}, {82, 6}, {160, 5}, {65, 5}, {94, 6},
{76, 6}, {129, 9}, {70, 6}, {111, 9}, {148, 5}, {165, 6}, {64, 4},
{92, 6}, {74, 6}, {123, 9}, {68, 6}, {105, 9}, {87, 9}, {161, 6},
{66, 6}, {99, 9}, {81, 9}, {143, 11}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {64, 4}, {91, 5}, {73, 5}, {155, 4}, {67, 5}, {151, 4},
{147, 4}, {160, 5}, {65, 5}, {150, 3}, {146, 3}, {156, 5}, {145, 2},
{152, 5}, {148, 5}, {168, 9}, {64, 4}, {150, 3}, {146, 3}, {155, 4},
{145, 2}, {151, 4}, {147, 4}, {164, 9}, {0, 2}, {0, 3}, {0, 3},
{0, 0}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7},
{16, 7}, {118, 6}, {8, 7}, {48, 8}, {82, 6}, {160, 5}, {4, 7},
{40, 8}, {24, 8}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6},
{2, 7}, {36, 8}, {20, 8}, {121, 7}, {12, 8}, {103, 7}, {85, 7},
{161, 6}, {66, 6}, {97, 7}, {79, 7}, {136, 8}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {1, 7}, {34, 8}, {18, 8}, {119, 7}, {10, 8},
{101, 7}, {83, 7}, {160, 5}, {6, 8}, {95, 7}, {77, 7}, {130, 8},
{71, 7}, {112, 8}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7},
{124, 8}, {69, 7}, {106, 8}, {88, 8}, {162, 7}, {145, 2}, {150, 3},
{146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6},
{33, 8}, {17, 8}, {118, 6}, {9, 8}, {100, 6}, {82, 6}, {160, 5},
{5, 8}, {94, 6}, {76, 6}, {128, 8}, {70, 6}, {110, 8}, {148, 5},
{165, 6}, {3, 8}, {92, 6}, {74, 6}, {122, 8}, {68, 6}, {104, 8},
{86, 8}, {161, 6}, {66, 6}, {98, 8}, {80, 8}, {141, 11}, {145, 2},
{153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5}, {120, 8},
{67, 5}, {102, 8}, {84, 8}, {160, 5}, {65, 5}, {96, 8}, {78, 8},
{135, 11}, {72, 8}, {117, 11}, {148, 5}, {167, 8}, {64, 4}, {150, 3},
{146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4}, {163, 8}, {145, 2},
{150, 3}, {146, 3}, {159, 8}, {0, 2}, {0, 0}, {0, 0}, {0, 0},
{0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {100, 6}, {82, 6},
{160, 5}, {4, 7}, {94, 6}, {76, 6}, {127, 7}, {70, 6}, {109, 7},
{148, 5}, {165, 6}, {2, 7}, {92, 6}, {74, 6}, {121, 7}, {68, 6},
{103, 7}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {157, 6},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {91, 5}, {73, 5},
{119, 7}, {67, 5}, {101, 7}, {83, 7}, {160, 5}, {65, 5}, {95, 7},
{77, 7}, {156, 5}, {71, 7}, {152, 5}, {148, 5}, {166, 7}, {64, 4},
{93, 7}, {75, 7}, {155, 4}, {69, 7}, {151, 4}, {147, 4}, {162, 7},
{145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0},
{0, 0}, {0, 6}, {91, 5}, {73, 5}, {118, 6}, {67, 5}, {100, 6},
{82, 6}, {160, 5}, {65, 5}, {94, 6}, {76, 6}, {156, 5}, {70, 6},
{152, 5}, {148, 5}, {165, 6}, {64, 4}, {92, 6}, {74, 6}, {155, 4},
{68, 6}, {151, 4}, {147, 4}, {161, 6}, {66, 6}, {150, 3}, {146, 3},
{157, 6}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {0, 4}, {0, 5},
{0, 5}, {0, 4}, {0, 5}, {0, 4}, {0, 4}, {0, 5}, {0, 5},
{0, 3}, {0, 3}, {0, 5}, {0, 2}, {0, 5}, {0, 5}, {0, 0},
{0, 4}, {0, 3}, {0, 3}, {0, 4}, {0, 2}, {0, 4}, {0, 4},
{0, 0}, {0, 2}, {0, 3}, {0, 3}, {0, 0}, {0, 2}, {0, 0},
{0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7},
{48, 8}, {82, 6}, {160, 5}, {4, 7}, {40, 8}, {24, 8}, {127, 7},
{70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {36, 8}, {20, 8},
{121, 7}, {12, 8}, {56, 9}, {85, 7}, {161, 6}, {66, 6}, {97, 7},
{79, 7}, {136, 8}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7},
{34, 8}, {18, 8}, {119, 7}, {10, 8}, {52, 9}, {83, 7}, {160, 5},
{6, 8}, {44, 9}, {28, 9}, {130, 8}, {71, 7}, {112, 8}, {148, 5},
{166, 7}, {64, 4}, {93, 7}, {75, 7}, {124, 8}, {69, 7}, {106, 8},
{88, 8}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2},
{154, 7}, {0, 0}, {0, 0}, {0, 6}, {33, 8}, {17, 8}, {118, 6},
{9, 8}, {50, 9}, {82, 6}, {160, 5}, {5, 8}, {42, 9}, {26, 9},
{128, 8}, {70, 6}, {110, 8}, {148, 5}, {165, 6}, {3, 8}, {38, 9},
{22, 9}, {122, 8}, {14, 9}, {60, 10}, {86, 8}, {161, 6}, {66, 6},
{98, 8}, {80, 8}, {139, 9}, {145, 2}, {153, 6}, {149, 6}, {0, 0},
{64, 4}, {91, 5}, {73, 5}, {120, 8}, {67, 5}, {102, 8}, {84, 8},
{160, 5}, {65, 5}, {96, 8}, {78, 8}, {133, 9}, {72, 8}, {115, 9},
{148, 5}, {167, 8}, {64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2},
{151, 4}, {147, 4}, {163, 8}, {145, 2}, {150, 3}, {146, 3}, {159, 8},
{0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7},
{118, 6}, {8, 7}, {49, 9}, {82, 6}, {160, 5}, {4, 7}, {41, 9},
{25, 9}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7},
{37, 9}, {21, 9}, {121, 7}, {13, 9}, {58, 10}, {85, 7}, {161, 6},
{66, 6}, {97, 7}, {79, 7}, {137, 9}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {1, 7}, {35, 9}, {19, 9}, {119, 7}, {11, 9}, {54, 10},
{83, 7}, {160, 5}, {7, 9}, {46, 10}, {30, 10}, {131, 9}, {71, 7},
{113, 9}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {125, 9},
{69, 7}, {107, 9}, {89, 9}, {162, 7}, {145, 2}, {150, 3}, {146, 3},
{158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {91, 5},
{73, 5}, {118, 6}, {67, 5}, {100, 6}, {82, 6}, {160, 5}, {65, 5},
{94, 6}, {76, 6}, {129, 9}, {70, 6}, {111, 9}, {148, 5}, {165, 6},
{64, 4}, {92, 6}, {74, 6}, {123, 9}, {68, 6}, {105, 9}, {87, 9},
{161, 6}, {66, 6}, {99, 9}, {81, 9}, {142, 10}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5}, {155, 4}, {67, 5},
{151, 4}, {147, 4}, {160, 5}, {65, 5}, {150, 3}, {146, 3}, {156, 5},
{145, 2}, {152, 5}, {148, 5}, {168, 9}, {64, 4}, {150, 3}, {146, 3},
{155, 4}, {145, 2}, {151, 4}, {147, 4}, {164, 9}, {0, 2}, {0, 3},
{0, 3}, {0, 0}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6},
{32, 7}, {16, 7}, {118, 6}, {8, 7}, {48, 8}, {82, 6}, {160, 5},
{4, 7}, {40, 8}, {24, 8}, {127, 7}, {70, 6}, {109, 7}, {148, 5},
{165, 6}, {2, 7}, {36, 8}, {20, 8}, {121, 7}, {12, 8}, {57, 10},
{85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {136, 8}, {145, 2},
{153, 6}, {149, 6}, {0, 0}, {1, 7}, {34, 8}, {18, 8}, {119, 7},
{10, 8}, {53, 10}, {83, 7}, {160, 5}, {6, 8}, {45, 10}, {29, 10},
{130, 8}, {71, 7}, {112, 8}, {148, 5}, {166, 7}, {64, 4}, {93, 7},
{75, 7}, {124, 8}, {69, 7}, {106, 8}, {88, 8}, {162, 7}, {145, 2},
{150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0},
{0, 6}, {33, 8}, {17, 8}, {118, 6}, {9, 8}, {51, 10}, {82, 6},
{160, 5}, {5, 8}, {43, 10}, {27, 10}, {128, 8}, {70, 6}, {110, 8},
{148, 5}, {165, 6}, {3, 8}, {39, 10}, {23, 10}, {122, 8}, {15, 10},
{63, 12}, {86, 8}, {161, 6}, {66, 6}, {98, 8}, {80, 8}, {140, 10},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5},
{120, 8}, {67, 5}, {102, 8}, {84, 8}, {160, 5}, {65, 5}, {96, 8},
{78, 8}, {134, 10}, {72, 8}, {116, 10}, {148, 5}, {167, 8}, {64, 4},
{150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4}, {163, 8},
{145, 2}, {150, 3}, {146, 3}, {159, 8}, {0, 2}, {0, 0}, {0, 0},
{0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {100, 6},
{82, 6}, {160, 5}, {4, 7}, {94, 6}, {76, 6}, {127, 7}, {70, 6},
{109, 7}, {148, 5}, {165, 6}, {2, 7}, {92, 6}, {74, 6}, {121, 7},
{68, 6}, {103, 7}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7},
{138, 10}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {91, 5},
{73, 5}, {119, 7}, {67, 5}, {101, 7}, {83, 7}, {160, 5}, {65, 5},
{95, 7}, {77, 7}, {132, 10}, {71, 7}, {114, 10}, {148, 5}, {166, 7},
{64, 4}, {93, 7}, {75, 7}, {126, 10}, {69, 7}, {108, 10}, {90, 10},
{162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7},
{0, 0}, {0, 0}, {0, 6}, {91, 5}, {73, 5}, {118, 6}, {67, 5},
{100, 6}, {82, 6}, {160, 5}, {65, 5}, {94, 6}, {76, 6}, {156, 5},
{70, 6}, {152, 5}, {148, 5}, {165, 6}, {64, 4}, {92, 6}, {74, 6},
{155, 4}, {68, 6}, {151, 4}, {147, 4}, {161, 6}, {66, 6}, {150, 3},
{146, 3}, {157, 6}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4},
{91, 5}, {73, 5}, {155, 4}, {67, 5}, {151, 4}, {147, 4}, {160, 5},
{65, 5}, {150, 3}, {146, 3}, {156, 5}, {145, 2}, {152, 5}, {148, 5},
{169, 10}, {0, 4}, {0, 3}, {0, 3}, {0, 4}, {0, 2}, {0, 4},
{0, 4}, {0, 0}, {0, 2}, {0, 3}, {0, 3}, {0, 0}, {0, 2},
{0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6},
{8, 7}, {48, 8}, {82, 6}, {160, 5}, {4, 7}, {40, 8}, {24, 8},
{127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {36, 8},
{20, 8}, {121, 7}, {12, 8}, {56, 9}, {85, 7}, {161, 6}, {66, 6},
{97, 7}, {79, 7}, {136, 8}, {145, 2}, {153, 6}, {149, 6}, {0, 0},
{1, 7}, {34, 8}, {18, 8}, {119, 7}, {10, 8}, {52, 9}, {83, 7},
{160, 5}, {6, 8}, {44, 9}, {28, 9}, {130, 8}, {71, 7}, {112, 8},
{148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {124, 8}, {69, 7},
{106, 8}, {88, 8}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7},
{145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {33, 8}, {17, 8},
{118, 6}, {9, 8}, {50, 9}, {82, 6}, {160, 5}, {5, 8}, {42, 9},
{26, 9}, {128, 8}, {70, 6}, {110, 8}, {148, 5}, {165, 6}, {3, 8},
{38, 9}, {22, 9}, {122, 8}, {14, 9}, {104, 8}, {86, 8}, {161, 6},
{66, 6}, {98, 8}, {80, 8}, {139, 9}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {64, 4}, {91, 5}, {73, 5}, {120, 8}, {67, 5}, {102, 8},
{84, 8}, {160, 5}, {65, 5}, {96, 8}, {78, 8}, {133, 9}, {72, 8},
{115, 9}, {148, 5}, {167, 8}, {64, 4}, {150, 3}, {146, 3}, {155, 4},
{145, 2}, {151, 4}, {147, 4}, {163, 8}, {145, 2}, {150, 3}, {146, 3},
{159, 8}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7},
{16, 7}, {118, 6}, {8, 7}, {49, 9}, {82, 6}, {160, 5}, {4, 7},
{41, 9}, {25, 9}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6},
{2, 7}, {37, 9}, {21, 9}, {121, 7}, {13, 9}, {103, 7}, {85, 7},
{161, 6}, {66, 6}, {97, 7}, {79, 7}, {137, 9}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {1, 7}, {35, 9}, {19, 9}, {119, 7}, {11, 9},
{101, 7}, {83, 7}, {160, 5}, {7, 9}, {95, 7}, {77, 7}, {131, 9},
{71, 7}, {113, 9}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7},
{125, 9}, {69, 7}, {107, 9}, {89, 9}, {162, 7}, {145, 2}, {150, 3},
{146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6},
{91, 5}, {73, 5}, {118, 6}, {67, 5}, {100, 6}, {82, 6}, {160, 5},
{65, 5}, {94, 6}, {76, 6}, {129, 9}, {70, 6}, {111, 9}, {148, 5},
{165, 6}, {64, 4}, {92, 6}, {74, 6}, {123, 9}, {68, 6}, {105, 9},
{87, 9}, {161, 6}, {66, 6}, {99, 9}, {81, 9}, {144, 12}, {145, 2},
{153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5}, {155, 4},
{67, 5}, {151, 4}, {147, 4}, {160, 5}, {65, 5}, {150, 3}, {146, 3},
{156, 5}, {145, 2}, {152, 5}, {148, 5}, {168, 9}, {64, 4}, {150, 3},
{146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4}, {164, 9}, {0, 2},
{0, 3}, {0, 3}, {0, 0}, {0, 2}, {0, 0}, {0, 0}, {0, 0},
{0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {48, 8}, {82, 6},
{160, 5}, {4, 7}, {40, 8}, {24, 8}, {127, 7}, {70, 6}, {109, 7},
{148, 5}, {165, 6}, {2, 7}, {36, 8}, {20, 8}, {121, 7}, {12, 8},
{103, 7}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {136, 8},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {34, 8}, {18, 8},
{119, 7}, {10, 8}, {101, 7}, {83, 7}, {160, 5}, {6, 8}, {95, 7},
{77, 7}, {130, 8}, {71, 7}, {112, 8}, {148, 5}, {166, 7}, {64, 4},
{93, 7}, {75, 7}, {124, 8}, {69, 7}, {106, 8}, {88, 8}, {162, 7},
{145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0},
{0, 0}, {0, 6}, {33, 8}, {17, 8}, {118, 6}, {9, 8}, {100, 6},
{82, 6}, {160, 5}, {5, 8}, {94, 6}, {76, 6}, {128, 8}, {70, 6},
{110, 8}, {148, 5}, {165, 6}, {3, 8}, {92, 6}, {74, 6}, {122, 8},
{68, 6}, {104, 8}, {86, 8}, {161, 6}, {66, 6}, {98, 8}, {80, 8},
{157, 6}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5},
{73, 5}, {120, 8}, {67, 5}, {102, 8}, {84, 8}, {160, 5}, {65, 5},
{96, 8}, {78, 8}, {156, 5}, {72, 8}, {152, 5}, {148, 5}, {167, 8},
{64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4},
{163, 8}, {145, 2}, {150, 3}, {146, 3}, {159, 8}, {0, 2}, {0, 0},
{0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7},
{100, 6}, {82, 6}, {160, 5}, {4, 7}, {94, 6}, {76, 6}, {127, 7},
{70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {92, 6}, {74, 6},
{121, 7}, {68, 6}, {103, 7}, {85, 7}, {161, 6}, {66, 6}, {97, 7},
{79, 7}, {157, 6}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7},
{91, 5}, {73, 5}, {119, 7}, {67, 5}, {101, 7}, {83, 7}, {160, 5},
{65, 5}, {95, 7}, {77, 7}, {156, 5}, {71, 7}, {152, 5}, {148, 5},
{166, 7}, {64, 4}, {93, 7}, {75, 7}, {155, 4}, {69, 7}, {151, 4},
{147, 4}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2},
{154, 7}, {0, 0}, {0, 0}, {0, 6}, {0, 5}, {0, 5}, {0, 6},
{0, 5}, {0, 6}, {0, 6}, {0, 5}, {0, 5}, {0, 6}, {0, 6},
{0, 5}, {0, 6}, {0, 5}, {0, 5}, {0, 6}, {0, 4}, {0, 6},
{0, 6}, {0, 4}, {0, 6}, {0, 4}, {0, 4}, {0, 6}, {0, 6},
{0, 3}, {0, 3}, {0, 6}, {0, 2}, {0, 6}, {0, 6}, {0, 0},
{0, 4}, {0, 5}, {0, 5}, {0, 4}, {0, 5}, {0, 4}, {0, 4},
{0, 5}, {0, 5}, {0, 3}, {0, 3}, {0, 5}, {0, 2}, {0, 5},
{0, 5}, {0, 0}, {0, 4}, {0, 3}, {0, 3}, {0, 4}, {0, 2},
{0, 4}, {0, 4}, {0, 0}, {0, 2}, {0, 3}, {0, 3}, {0, 0},
{0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7},
{118, 6}, {8, 7}, {48, 8}, {82, 6}, {160, 5}, {4, 7}, {40, 8},
{24, 8}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7},
{36, 8}, {20, 8}, {121, 7}, {12, 8}, {56, 9}, {85, 7}, {161, 6},
{66, 6}, {97, 7}, {79, 7}, {136, 8}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {1, 7}, {34, 8}, {18, 8}, {119, 7}, {10, 8}, {52, 9},
{83, 7}, {160, 5}, {6, 8}, {44, 9}, {28, 9}, {130, 8}, {71, 7},
{112, 8}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {124, 8},
{69, 7}, {106, 8}, {88, 8}, {162, 7}, {145, 2}, {150, 3}, {146, 3},
{158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {33, 8},
{17, 8}, {118, 6}, {9, 8}, {50, 9}, {82, 6}, {160, 5}, {5, 8},
{42, 9}, {26, 9}, {128, 8}, {70, 6}, {110, 8}, {148, 5}, {165, 6},
{3, 8}, {38, 9}, {22, 9}, {122, 8}, {14, 9}, {60, 10}, {86, 8},
{161, 6}, {66, 6}, {98, 8}, {80, 8}, {139, 9}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5}, {120, 8}, {67, 5},
{102, 8}, {84, 8}, {160, 5}, {65, 5}, {96, 8}, {78, 8}, {133, 9},
{72, 8}, {115, 9}, {148, 5}, {167, 8}, {64, 4}, {150, 3}, {146, 3},
{155, 4}, {145, 2}, {151, 4}, {147, 4}, {163, 8}, {145, 2}, {150, 3},
{146, 3}, {159, 8}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6},
{32, 7}, {16, 7}, {118, 6}, {8, 7}, {49, 9}, {82, 6}, {160, 5},
{4, 7}, {41, 9}, {25, 9}, {127, 7}, {70, 6}, {109, 7}, {148, 5},
{165, 6}, {2, 7}, {37, 9}, {21, 9}, {121, 7}, {13, 9}, {58, 10},
{85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {137, 9}, {145, 2},
{153, 6}, {149, 6}, {0, 0}, {1, 7}, {35, 9}, {19, 9}, {119, 7},
{11, 9}, {54, 10}, {83, 7}, {160, 5}, {7, 9}, {46, 10}, {30, 10},
{131, 9}, {71, 7}, {113, 9}, {148, 5}, {166, 7}, {64, 4}, {93, 7},
{75, 7}, {125, 9}, {69, 7}, {107, 9}, {89, 9}, {162, 7}, {145, 2},
{150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0},
{0, 6}, {91, 5}, {73, 5}, {118, 6}, {67, 5}, {100, 6}, {82, 6},
{160, 5}, {65, 5}, {94, 6}, {76, 6}, {129, 9}, {70, 6}, {111, 9},
{148, 5}, {165, 6}, {64, 4}, {92, 6}, {74, 6}, {123, 9}, {68, 6},
{105, 9}, {87, 9}, {161, 6}, {66, 6}, {99, 9}, {81, 9}, {142, 10},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5},
{155, 4}, {67, 5}, {151, 4}, {147, 4}, {160, 5}, {65, 5}, {150, 3},
{146, 3}, {156, 5}, {145, 2}, {152, 5}, {148, 5}, {168, 9}, {64, 4},
{150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4}, {164, 9},
{0, 2}, {0, 3}, {0, 3}, {0, 0}, {0, 2}, {0, 0}, {0, 0},
{0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {48, 8},
{82, 6}, {160, 5}, {4, 7}, {40, 8}, {24, 8}, {127, 7}, {70, 6},
{109, 7}, {148, 5}, {165, 6}, {2, 7}, {36, 8}, {20, 8}, {121, 7},
{12, 8}, {57, 10}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7},
{136, 8}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {34, 8},
{18, 8}, {119, 7}, {10, 8}, {53, 10}, {83, 7}, {160, 5}, {6, 8},
{45, 10}, {29, 10}, {130, 8}, {71, 7}, {112, 8}, {148, 5}, {166, 7},
{64, 4}, {93, 7}, {75, 7}, {124, 8}, {69, 7}, {106, 8}, {88, 8},
{162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7},
{0, 0}, {0, 0}, {0, 6}, {33, 8}, {17, 8}, {118, 6}, {9, 8},
{51, 10}, {82, 6}, {160, 5}, {5, 8}, {43, 10}, {27, 10}, {128, 8},
{70, 6}, {110, 8}, {148, 5}, {165, 6}, {3, 8}, {39, 10}, {23, 10},
{122, 8}, {15, 10}, {62, 11}, {86, 8}, {161, 6}, {66, 6}, {98, 8},
{80, 8}, {140, 10}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4},
{91, 5}, {73, 5}, {120, 8}, {67, 5}, {102, 8}, {84, 8}, {160, 5},
{65, 5}, {96, 8}, {78, 8}, {134, 10}, {72, 8}, {116, 10}, {148, 5},
{167, 8}, {64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4},
{147, 4}, {163, 8}, {145, 2}, {150, 3}, {146, 3}, {159, 8}, {0, 2},
{0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6},
{8, 7}, {100, 6}, {82, 6}, {160, 5}, {4, 7}, {94, 6}, {76, 6},
{127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {92, 6},
{74, 6}, {121, 7}, {68, 6}, {103, 7}, {85, 7}, {161, 6}, {66, 6},
{97, 7}, {79, 7}, {138, 10}, {145, 2}, {153, 6}, {149, 6}, {0, 0},
{1, 7}, {91, 5}, {73, 5}, {119, 7}, {67, 5}, {101, 7}, {83, 7},
{160, 5}, {65, 5}, {95, 7}, {77, 7}, {132, 10}, {71, 7}, {114, 10},
{148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {126, 10}, {69, 7},
{108, 10}, {90, 10}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7},
{145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {91, 5}, {73, 5},
{118, 6}, {67, 5}, {100, 6}, {82, 6}, {160, 5}, {65, 5}, {94, 6},
{76, 6}, {156, 5}, {70, 6}, {152, 5}, {148, 5}, {165, 6}, {64, 4},
{92, 6}, {74, 6}, {155, 4}, {68, 6}, {151, 4}, {147, 4}, {161, 6},
{66, 6}, {150, 3}, {146, 3}, {157, 6}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {64, 4}, {91, 5}, {73, 5}, {155, 4}, {67, 5}, {151, 4},
{147, 4}, {160, 5}, {65, 5}, {150, 3}, {146, 3}, {156, 5}, {145, 2},
{152, 5}, {148, 5}, {169, 10}, {0, 4}, {0, 3}, {0, 3}, {0, 4},
{0, 2}, {0, 4}, {0, 4}, {0, 0}, {0, 2}, {0, 3}, {0, 3},
{0, 0}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7},
{16, 7}, {118, 6}, {8, 7}, {48, 8}, {82, 6}, {160, 5}, {4, 7},
{40, 8}, {24, 8}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6},
{2, 7}, {36, 8}, {20, 8}, {121, 7}, {12, 8}, {56, 9}, {85, 7},
{161, 6}, {66, 6}, {97, 7}, {79, 7}, {136, 8}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {1, 7}, {34, 8}, {18, 8}, {119, 7}, {10, 8},
{52, 9}, {83, 7}, {160, 5}, {6, 8}, {44, 9}, {28, 9}, {130, 8},
{71, 7}, {112, 8}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7},
{124, 8}, {69, 7}, {106, 8}, {88, 8}, {162, 7}, {145, 2}, {150, 3},
{146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6},
{33, 8}, {17, 8}, {118, 6}, {9, 8}, {50, 9}, {82, 6}, {160, 5},
{5, 8}, {42, 9}, {26, 9}, {128, 8}, {70, 6}, {110, 8}, {148, 5},
{165, 6}, {3, 8}, {38, 9}, {22, 9}, {122, 8}, {14, 9}, {61, 11},
{86, 8}, {161, 6}, {66, 6}, {98, 8}, {80, 8}, {139, 9}, {145, 2},
{153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5}, {120, 8},
{67, 5}, {102, 8}, {84, 8}, {160, 5}, {65, 5}, {96, 8}, {78, 8},
{133, 9}, {72, 8}, {115, 9}, {148, 5}, {167, 8}, {64, 4}, {150, 3},
{146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4}, {163, 8}, {145, 2},
{150, 3}, {146, 3}, {159, 8}, {0, 2}, {0, 0}, {0, 0}, {0, 0},
{0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {49, 9}, {82, 6},
{160, 5}, {4, 7}, {41, 9}, {25, 9}, {127, 7}, {70, 6}, {109, 7},
{148, 5}, {165, 6}, {2, 7}, {37, 9}, {21, 9}, {121, 7}, {13, 9},
{59, 11}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {137, 9},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {35, 9}, {19, 9},
{119, 7}, {11, 9}, {55, 11}, {83, 7}, {160, 5}, {7, 9}, {47, 11},
{31, 11}, {131, 9}, {71, 7}, {113, 9}, {148, 5}, {166, 7}, {64, 4},
{93, 7}, {75, 7}, {125, 9}, {69, 7}, {107, 9}, {89, 9}, {162, 7},
{145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0},
{0, 0}, {0, 6}, {91, 5}, {73, 5}, {118, 6}, {67, 5}, {100, 6},
{82, 6}, {160, 5}, {65, 5}, {94, 6}, {76, 6}, {129, 9}, {70, 6},
{111, 9}, {148, 5}, {165, 6}, {64, 4}, {92, 6}, {74, 6}, {123, 9},
{68, 6}, {105, 9}, {87, 9}, {161, 6}, {66, 6}, {99, 9}, {81, 9},
{143, 11}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5},
{73, 5}, {155, 4}, {67, 5}, {151, 4}, {147, 4}, {160, 5}, {65, 5},
{150, 3}, {146, 3}, {156, 5}, {145, 2}, {152, 5}, {148, 5}, {168, 9},
{64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4},
{164, 9}, {0, 2}, {0, 3}, {0, 3}, {0, 0}, {0, 2}, {0, 0},
{0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7},
{48, 8}, {82, 6}, {160, 5}, {4, 7}, {40, 8}, {24, 8}, {127, 7},
{70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {36, 8}, {20, 8},
{121, 7}, {12, 8}, {103, 7}, {85, 7}, {161, 6}, {66, 6}, {97, 7},
{79, 7}, {136, 8}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7},
{34, 8}, {18, 8}, {119, 7}, {10, 8}, {101, 7}, {83, 7}, {160, 5},
{6, 8}, {95, 7}, {77, 7}, {130, 8}, {71, 7}, {112, 8}, {148, 5},
{166, 7}, {64, 4}, {93, 7}, {75, 7}, {124, 8}, {69, 7}, {106, 8},
{88, 8}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2},
{154, 7}, {0, 0}, {0, 0}, {0, 6}, {33, 8}, {17, 8}, {118, 6},
{9, 8}, {100, 6}, {82, 6}, {160, 5}, {5, 8}, {94, 6}, {76, 6},
{128, 8}, {70, 6}, {110, 8}, {148, 5}, {165, 6}, {3, 8}, {92, 6},
{74, 6}, {122, 8}, {68, 6}, {104, 8}, {86, 8}, {161, 6}, {66, 6},
{98, 8}, {80, 8}, {141, 11}, {145, 2}, {153, 6}, {149, 6}, {0, 0},
{64, 4}, {91, 5}, {73, 5}, {120, 8}, {67, 5}, {102, 8}, {84, 8},
{160, 5}, {65, 5}, {96, 8}, {78, 8}, {135, 11}, {72, 8}, {117, 11},
{148, 5}, {167, 8}, {64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2},
{151, 4}, {147, 4}, {163, 8}, {145, 2}, {150, 3}, {146, 3}, {159, 8},
{0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7},
{118, 6}, {8, 7}, {100, 6}, {82, 6}, {160, 5}, {4, 7}, {94, 6},
{76, 6}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7},
{92, 6}, {74, 6}, {121, 7}, {68, 6}, {103, 7}, {85, 7}, {161, 6},
{66, 6}, {97, 7}, {79, 7}, {157, 6}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {1, 7}, {91, 5}, {73, 5}, {119, 7}, {67, 5}, {101, 7},
{83, 7}, {160, 5}, {65, 5}, {95, 7}, {77, 7}, {156, 5}, {71, 7},
{152, 5}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {155, 4},
{69, 7}, {151, 4}, {147, 4}, {162, 7}, {145, 2}, {150, 3}, {146, 3},
{158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {91, 5},
{73, 5}, {118, 6}, {67, 5}, {100, 6}, {82, 6}, {160, 5}, {65, 5},
{94, 6}, {76, 6}, {156, 5}, {70, 6}, {152, 5}, {148, 5}, {165, 6},
{64, 4}, {92, 6}, {74, 6}, {155, 4}, {68, 6}, {151, 4}, {147, 4},
{161, 6}, {66, 6}, {150, 3}, {146, 3}, {157, 6}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {0, 4}, {0, 5}, {0, 5}, {0, 4}, {0, 5},
{0, 4}, {0, 4}, {0, 5}, {0, 5}, {0, 3}, {0, 3}, {0, 5},
{0, 2}, {0, 5}, {0, 5}, {0, 0}, {0, 4}, {0, 3}, {0, 3},
{0, 4}, {0, 2}, {0, 4}, {0, 4}, {0, 0}, {0, 2}, {0, 3},
{0, 3}, {0, 0}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6},
{32, 7}, {16, 7}, {118, 6}, {8, 7}, {48, 8}, {82, 6}, {160, 5},
{4, 7}, {40, 8}, {24, 8}, {127, 7}, {70, 6}, {109, 7}, {148, 5},
{165, 6}, {2, 7}, {36, 8}, {20, 8}, {121, 7}, {12, 8}, {56, 9},
{85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {136, 8}, {145, 2},
{153, 6}, {149, 6}, {0, 0}, {1, 7}, {34, 8}, {18, 8}, {119, 7},
{10, 8}, {52, 9}, {83, 7}, {160, 5}, {6, 8}, {44, 9}, {28, 9},
{130, 8}, {71, 7}, {112, 8}, {148, 5}, {166, 7}, {64, 4}, {93, 7},
{75, 7}, {124, 8}, {69, 7}, {106, 8}, {88, 8}, {162, 7}, {145, 2},
{150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0},
{0, 6}, {33, 8}, {17, 8}, {118, 6}, {9, 8}, {50, 9}, {82, 6},
{160, 5}, {5, 8}, {42, 9}, {26, 9}, {128, 8}, {70, 6}, {110, 8},
{148, 5}, {165, 6}, {3, 8}, {38, 9}, {22, 9}, {122, 8}, {14, 9},
{60, 10}, {86, 8}, {161, 6}, {66, 6}, {98, 8}, {80, 8}, {139, 9},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5},
{120, 8}, {67, 5}, {102, 8}, {84, 8}, {160, 5}, {65, 5}, {96, 8},
{78, 8}, {133, 9}, {72, 8}, {115, 9}, {148, 5}, {167, 8}, {64, 4},
{150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4}, {163, 8},
{145, 2}, {150, 3}, {146, 3}, {159, 8}, {0, 2}, {0, 0}, {0, 0},
{0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {49, 9},
{82, 6}, {160, 5}, {4, 7}, {41, 9}, {25, 9}, {127, 7}, {70, 6},
{109, 7}, {148, 5}, {165, 6}, {2, 7}, {37, 9}, {21, 9}, {121, 7},
{13, 9}, {58, 10}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7},
{137, 9}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {35, 9},
{19, 9}, {119, 7}, {11, 9}, {54, 10}, {83, 7}, {160, 5}, {7, 9},
{46, 10}, {30, 10}, {131, 9}, {71, 7}, {113, 9}, {148, 5}, {166, 7},
{64, 4}, {93, 7}, {75, 7}, {125, 9}, {69, 7}, {107, 9}, {89, 9},
{162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7},
{0, 0}, {0, 0}, {0, 6}, {91, 5}, {73, 5}, {118, 6}, {67, 5},
{100, 6}, {82, 6}, {160, 5}, {65, 5}, {94, 6}, {76, 6}, {129, 9},
{70, 6}, {111, 9}, {148, 5}, {165, 6}, {64, 4}, {92, 6}, {74, 6},
{123, 9}, {68, 6}, {105, 9}, {87, 9}, {161, 6}, {66, 6}, {99, 9},
{81, 9}, {142, 10}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4},
{91, 5}, {73, 5}, {155, 4}, {67, 5}, {151, 4}, {147, 4}, {160, 5},
{65, 5}, {150, 3}, {146, 3}, {156, 5}, {145, 2}, {152, 5}, {148, 5},
{168, 9}, {64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4},
{147, 4}, {164, 9}, {0, 2}, {0, 3}, {0, 3}, {0, 0}, {0, 2},
{0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6},
{8, 7}, {48, 8}, {82, 6}, {160, 5}, {4, 7}, {40, 8}, {24, 8},
{127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {36, 8},
{20, 8}, {121, 7}, {12, 8}, {57, 10}, {85, 7}, {161, 6}, {66, 6},
{97, 7}, {79, 7}, {136, 8}, {145, 2}, {153, 6}, {149, 6}, {0, 0},
{1, 7}, {34, 8}, {18, 8}, {119, 7}, {10, 8}, {53, 10}, {83, 7},
{160, 5}, {6, 8}, {45, 10}, {29, 10}, {130, 8}, {71, 7}, {112, 8},
{148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {124, 8}, {69, 7},
{106, 8}, {88, 8}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7},
{145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {33, 8}, {17, 8},
{118, 6}, {9, 8}, {51, 10}, {82, 6}, {160, 5}, {5, 8}, {43, 10},
{27, 10}, {128, 8}, {70, 6}, {110, 8}, {148, 5}, {165, 6}, {3, 8},
{39, 10}, {23, 10}, {122, 8}, {15, 10}, {104, 8}, {86, 8}, {161, 6},
{66, 6}, {98, 8}, {80, 8}, {140, 10}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {64, 4}, {91, 5}, {73, 5}, {120, 8}, {67, 5}, {102, 8},
{84, 8}, {160, 5}, {65, 5}, {96, 8}, {78, 8}, {134, 10}, {72, 8},
{116, 10}, {148, 5}, {167, 8}, {64, 4}, {150, 3}, {146, 3}, {155, 4},
{145, 2}, {151, 4}, {147, 4}, {163, 8}, {145, 2}, {150, 3}, {146, 3},
{159, 8}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7},
{16, 7}, {118, 6}, {8, 7}, {100, 6}, {82, 6}, {160, 5}, {4, 7},
{94, 6}, {76, 6}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6},
{2, 7}, {92, 6}, {74, 6}, {121, 7}, {68, 6}, {103, 7}, {85, 7},
{161, 6}, {66, 6}, {97, 7}, {79, 7}, {138, 10}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {1, 7}, {91, 5}, {73, 5}, {119, 7}, {67, 5},
{101, 7}, {83, 7}, {160, 5}, {65, 5}, {95, 7}, {77, 7}, {132, 10},
{71, 7}, {114, 10}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7},
{126, 10}, {69, 7}, {108, 10}, {90, 10}, {162, 7}, {145, 2}, {150, 3},
{146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6},
{91, 5}, {73, 5}, {118, 6}, {67, 5}, {100, 6}, {82, 6}, {160, 5},
{65, 5}, {94, 6}, {76, 6}, {156, 5}, {70, 6}, {152, 5}, {148, 5},
{165, 6}, {64, 4}, {92, 6}, {74, 6}, {155, 4}, {68, 6}, {151, 4},
{147, 4}, {161, 6}, {66, 6}, {150, 3}, {146, 3}, {157, 6}, {145, 2},
{153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5}, {155, 4},
{67, 5}, {151, 4}, {147, 4}, {160, 5}, {65, 5}, {150, 3}, {146, 3},
{156, 5}, {145, 2}, {152, 5}, {148, 5}, {169, 10}, {0, 4}, {0, 3},
{0, 3}, {0, 4}, {0, 2}, {0, 4}, {0, 4}, {0, 0}, {0, 2},
{0, 3}, {0, 3}, {0, 0}, {0, 2}, {0, 0}, {0, 0}, {0, 0},
{0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7}, {48, 8}, {82, 6},
{160, 5}, {4, 7}, {40, 8}, {24, 8}, {127, 7}, {70, 6}, {109, 7},
{148, 5}, {165, 6}, {2, 7}, {36, 8}, {20, 8}, {121, 7}, {12, 8},
{56, 9}, {85, 7}, {161, 6}, {66, 6}, {97, 7}, {79, 7}, {136, 8},
{145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7}, {34, 8}, {18, 8},
{119, 7}, {10, 8}, {52, 9}, {83, 7}, {160, 5}, {6, 8}, {44, 9},
{28, 9}, {130, 8}, {71, 7}, {112, 8}, {148, 5}, {166, 7}, {64, 4},
{93, 7}, {75, 7}, {124, 8}, {69, 7}, {106, 8}, {88, 8}, {162, 7},
{145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2}, {154, 7}, {0, 0},
{0, 0}, {0, 6}, {33, 8}, {17, 8}, {118, 6}, {9, 8}, {50, 9},
{82, 6}, {160, 5}, {5, 8}, {42, 9}, {26, 9}, {128, 8}, {70, 6},
{110, 8}, {148, 5}, {165, 6}, {3, 8}, {38, 9}, {22, 9}, {122, 8},
{14, 9}, {104, 8}, {86, 8}, {161, 6}, {66, 6}, {98, 8}, {80, 8},
{139, 9}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {64, 4}, {91, 5},
{73, 5}, {120, 8}, {67, 5}, {102, 8}, {84, 8}, {160, 5}, {65, 5},
{96, 8}, {78, 8}, {133, 9}, {72, 8}, {115, 9}, {148, 5}, {167, 8},
{64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2}, {151, 4}, {147, 4},
{163, 8}, {145, 2}, {150, 3}, {146, 3}, {159, 8}, {0, 2}, {0, 0},
{0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7}, {118, 6}, {8, 7},
{49, 9}, {82, 6}, {160, 5}, {4, 7}, {41, 9}, {25, 9}, {127, 7},
{70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7}, {37, 9}, {21, 9},
{121, 7}, {13, 9}, {103, 7}, {85, 7}, {161, 6}, {66, 6}, {97, 7},
{79, 7}, {137, 9}, {145, 2}, {153, 6}, {149, 6}, {0, 0}, {1, 7},
{35, 9}, {19, 9}, {119, 7}, {11, 9}, {101, 7}, {83, 7}, {160, 5},
{7, 9}, {95, 7}, {77, 7}, {131, 9}, {71, 7}, {113, 9}, {148, 5},
{166, 7}, {64, 4}, {93, 7}, {75, 7}, {125, 9}, {69, 7}, {107, 9},
{89, 9}, {162, 7}, {145, 2}, {150, 3}, {146, 3}, {158, 7}, {145, 2},
{154, 7}, {0, 0}, {0, 0}, {0, 6}, {91, 5}, {73, 5}, {118, 6},
{67, 5}, {100, 6}, {82, 6}, {160, 5}, {65, 5}, {94, 6}, {76, 6},
{129, 9}, {70, 6}, {111, 9}, {148, 5}, {165, 6}, {64, 4}, {92, 6},
{74, 6}, {123, 9}, {68, 6}, {105, 9}, {87, 9}, {161, 6}, {66, 6},
{99, 9}, {81, 9}, {157, 6}, {145, 2}, {153, 6}, {149, 6}, {0, 0},
{64, 4}, {91, 5}, {73, 5}, {155, 4}, {67, 5}, {151, 4}, {147, 4},
{160, 5}, {65, 5}, {150, 3}, {146, 3}, {156, 5}, {145, 2}, {152, 5},
{148, 5}, {168, 9}, {64, 4}, {150, 3}, {146, 3}, {155, 4}, {145, 2},
{151, 4}, {147, 4}, {164, 9}, {0, 2}, {0, 3}, {0, 3}, {0, 0},
{0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6}, {32, 7}, {16, 7},
{118, 6}, {8, 7}, {48, 8}, {82, 6}, {160, 5}, {4, 7}, {40, 8},
{24, 8}, {127, 7}, {70, 6}, {109, 7}, {148, 5}, {165, 6}, {2, 7},
{36, 8}, {20, 8}, {121, 7}, {12, 8}, {103, 7}, {85, 7}, {161, 6},
{66, 6}, {97, 7}, {79, 7}, {136, 8}, {145, 2}, {153, 6}, {149, 6},
{0, 0}, {1, 7}, {34, 8}, {18, 8}, {119, 7}, {10, 8}, {101, 7},
{83, 7}, {160, 5}, {6, 8}, {95, 7}, {77, 7}, {130, 8}, {71, 7},
{112, 8}, {148, 5}, {166, 7}, {64, 4}, {93, 7}, {75, 7}, {124, 8},
{69, 7}, {106, 8}, {88, 8}, {162, 7}, {145, 2}, {150, 3}, {146, 3},
{158, 7}, {145, 2}, {154, 7}, {0, 0}, {0, 0}, {0, 6}, {33, 8},
{17, 8}, {118, 6}, {9, 8}, {100, 6}, {82, 6}, {160, 5}, {5, 8},
{94, 6}, {76, 6}, {128, 8}, {70, 6}, {110, 8}, {148, 5}, {165, 6},
{3, 8}, {92, 6}, {74, 6}, {122, 8}, {68, 6}, {104, 8}, {86, 8},
{161, 6}, {66, 6}, {98, 8}, {80, 8}, {157, 6}, {145, 2}, {153, 6},
{149, 6}, {0, 0}, {64, 4}, {91, 5}, {73, 5}, {120, 8}, {67, 5},
{102, 8}, {84, 8}, {160, 5}, {65, 5}, {96, 8}, {78, 8}, {156, 5},
{72, 8}, {152, 5}, {148, 5}, {167, 8}, {64, 4}, {150, 3}, {146, 3},
{155, 4}, {145, 2}, {151, 4}, {147, 4}, {163, 8}, {145, 2}, {150, 3},
{146, 3}, {159, 8}, {0, 2}, {0, 0}, {0, 0}, {0, 0}, {0, 6},
{0, 7}, {0, 7}, {0, 6}, {0, 7}, {0, 6}, {0, 6}, {0, 5},
{0, 7}, {0, 6}, {0, 6}, {0, 7}, {0, 6}, {0, 7}, {0, 5},
{0, 6}, {0, 7}, {0, 6}, {0, 6}, {0, 7}, {0, 6}, {0, 7},
{0, 7}, {0, 6}, {0, 6}, {0, 7}, {0, 7}, {0, 6}, {0, 2},
{0, 6}, {0, 6}, {0, 0}, {0, 7}, {0, 5}, {0, 5}, {0, 7},
{0, 5}, {0, 7}, {0, 7}, {0, 5}, {0, 5}, {0, 7}, {0, 7},
{0, 5}, {0, 7}, {0, 5}, {0, 5}, {0, 7}, {0, 4}, {0, 7},
{0, 7}, {0, 4}, {0, 7}, {0, 4}, {0, 4}, {0, 7}, {0, 2},
{0, 3}, {0, 3}, {0, 7}, {0, 2}, {0, 7}, {0, 0}, {0, 0},
{0, 6}, {0, 5}, {0, 5}, {0, 6}, {0, 5}, {0, 6}, {0, 6},
{0, 5}, {0, 5}, {0, 6}, {0, 6}, {0, 5}, {0, 6}, {0, 5},
{0, 5}, {0, 6}, {0, 4}, {0, 6}, {0, 6}, {0, 4}, {0, 6},
{0, 4}, {0, 4}, {0, 6}, {0, 6}, {0, 3}, {0, 3}, {0, 6},
{0, 2}, {0, 6}, {0, 6}, {0, 0}, {0, 4}, {0, 5}, {0, 5},
{0, 4}, {0, 5}, {0, 4}, {0, 4}, {0, 5}, {0, 5}, {0, 3},
{0, 3}, {0, 5}, {0, 2}, {0, 5}, {0, 5}, {0, 0}, {0, 4},
{0, 3}, {0, 3}, {0, 4}, {0, 2}, {0, 4}, {0, 4}, {0, 0},
{0, 2}, {0, 3}, {0, 3}, {0, 0}, {0, 2}, {0, 0}, {0, 0},
{0, 0}
};
static const int8_t vectorsrawbytes[] ALIGNED(0x1000) = {
0, -1, 4, -1, 1, -1, 5, -1, 2, -1, -1, -1, 3, -1, -1, -1, // 0
0, -1, 4, -1, 1, -1, 5, 6, 2, -1, -1, -1, 3, -1, -1, -1, // 1
0, -1, 4, 5, 1, -1, 6, -1, 2, -1, -1, -1, 3, -1, -1, -1, // 2
0, -1, 4, 5, 1, -1, 6, 7, 2, -1, -1, -1, 3, -1, -1, -1, // 3
0, -1, 5, -1, 1, -1, 6, -1, 2, -1, -1, -1, 3, 4, -1, -1, // 4
0, -1, 5, -1, 1, -1, 6, 7, 2, -1, -1, -1, 3, 4, -1, -1, // 5
0, -1, 5, 6, 1, -1, 7, -1, 2, -1, -1, -1, 3, 4, -1, -1, // 6
0, -1, 5, 6, 1, -1, 7, 8, 2, -1, -1, -1, 3, 4, -1, -1, // 7
0, -1, 5, -1, 1, -1, 6, -1, 2, 3, -1, -1, 4, -1, -1, -1, // 8
0, -1, 5, -1, 1, -1, 6, 7, 2, 3, -1, -1, 4, -1, -1, -1, // 9
0, -1, 5, 6, 1, -1, 7, -1, 2, 3, -1, -1, 4, -1, -1, -1, // 10
0, -1, 5, 6, 1, -1, 7, 8, 2, 3, -1, -1, 4, -1, -1, -1, // 11
0, -1, 6, -1, 1, -1, 7, -1, 2, 3, -1, -1, 4, 5, -1, -1, // 12
0, -1, 6, -1, 1, -1, 7, 8, 2, 3, -1, -1, 4, 5, -1, -1, // 13
0, -1, 6, 7, 1, -1, 8, -1, 2, 3, -1, -1, 4, 5, -1, -1, // 14
0, -1, 6, 7, 1, -1, 8, 9, 2, 3, -1, -1, 4, 5, -1, -1, // 15
0, -1, 5, -1, 1, 2, 6, -1, 3, -1, -1, -1, 4, -1, -1, -1, // 16
0, -1, 5, -1, 1, 2, 6, 7, 3, -1, -1, -1, 4, -1, -1, -1, // 17
0, -1, 5, 6, 1, 2, 7, -1, 3, -1, -1, -1, 4, -1, -1, -1, // 18
0, -1, 5, 6, 1, 2, 7, 8, 3, -1, -1, -1, 4, -1, -1, -1, // 19
0, -1, 6, -1, 1, 2, 7, -1, 3, -1, -1, -1, 4, 5, -1, -1, // 20
0, -1, 6, -1, 1, 2, 7, 8, 3, -1, -1, -1, 4, 5, -1, -1, // 21
0, -1, 6, 7, 1, 2, 8, -1, 3, -1, -1, -1, 4, 5, -1, -1, // 22
0, -1, 6, 7, 1, 2, 8, 9, 3, -1, -1, -1, 4, 5, -1, -1, // 23
0, -1, 6, -1, 1, 2, 7, -1, 3, 4, -1, -1, 5, -1, -1, -1, // 24
0, -1, 6, -1, 1, 2, 7, 8, 3, 4, -1, -1, 5, -1, -1, -1, // 25
0, -1, 6, 7, 1, 2, 8, -1, 3, 4, -1, -1, 5, -1, -1, -1, // 26
0, -1, 6, 7, 1, 2, 8, 9, 3, 4, -1, -1, 5, -1, -1, -1, // 27
0, -1, 7, -1, 1, 2, 8, -1, 3, 4, -1, -1, 5, 6, -1, -1, // 28
0, -1, 7, -1, 1, 2, 8, 9, 3, 4, -1, -1, 5, 6, -1, -1, // 29
0, -1, 7, 8, 1, 2, 9, -1, 3, 4, -1, -1, 5, 6, -1, -1, // 30
0, -1, 7, 8, 1, 2, 9, 10, 3, 4, -1, -1, 5, 6, -1, -1, // 31
0, 1, 5, -1, 2, -1, 6, -1, 3, -1, -1, -1, 4, -1, -1, -1, // 32
0, 1, 5, -1, 2, -1, 6, 7, 3, -1, -1, -1, 4, -1, -1, -1, // 33
0, 1, 5, 6, 2, -1, 7, -1, 3, -1, -1, -1, 4, -1, -1, -1, // 34
0, 1, 5, 6, 2, -1, 7, 8, 3, -1, -1, -1, 4, -1, -1, -1, // 35
0, 1, 6, -1, 2, -1, 7, -1, 3, -1, -1, -1, 4, 5, -1, -1, // 36
0, 1, 6, -1, 2, -1, 7, 8, 3, -1, -1, -1, 4, 5, -1, -1, // 37
0, 1, 6, 7, 2, -1, 8, -1, 3, -1, -1, -1, 4, 5, -1, -1, // 38
0, 1, 6, 7, 2, -1, 8, 9, 3, -1, -1, -1, 4, 5, -1, -1, // 39
0, 1, 6, -1, 2, -1, 7, -1, 3, 4, -1, -1, 5, -1, -1, -1, // 40
0, 1, 6, -1, 2, -1, 7, 8, 3, 4, -1, -1, 5, -1, -1, -1, // 41
0, 1, 6, 7, 2, -1, 8, -1, 3, 4, -1, -1, 5, -1, -1, -1, // 42
0, 1, 6, 7, 2, -1, 8, 9, 3, 4, -1, -1, 5, -1, -1, -1, // 43
0, 1, 7, -1, 2, -1, 8, -1, 3, 4, -1, -1, 5, 6, -1, -1, // 44
0, 1, 7, -1, 2, -1, 8, 9, 3, 4, -1, -1, 5, 6, -1, -1, // 45
0, 1, 7, 8, 2, -1, 9, -1, 3, 4, -1, -1, 5, 6, -1, -1, // 46
0, 1, 7, 8, 2, -1, 9, 10, 3, 4, -1, -1, 5, 6, -1, -1, // 47
0, 1, 6, -1, 2, 3, 7, -1, 4, -1, -1, -1, 5, -1, -1, -1, // 48
0, 1, 6, -1, 2, 3, 7, 8, 4, -1, -1, -1, 5, -1, -1, -1, // 49
0, 1, 6, 7, 2, 3, 8, -1, 4, -1, -1, -1, 5, -1, -1, -1, // 50
0, 1, 6, 7, 2, 3, 8, 9, 4, -1, -1, -1, 5, -1, -1, -1, // 51
0, 1, 7, -1, 2, 3, 8, -1, 4, -1, -1, -1, 5, 6, -1, -1, // 52
0, 1, 7, -1, 2, 3, 8, 9, 4, -1, -1, -1, 5, 6, -1, -1, // 53
0, 1, 7, 8, 2, 3, 9, -1, 4, -1, -1, -1, 5, 6, -1, -1, // 54
0, 1, 7, 8, 2, 3, 9, 10, 4, -1, -1, -1, 5, 6, -1, -1, // 55
0, 1, 7, -1, 2, 3, 8, -1, 4, 5, -1, -1, 6, -1, -1, -1, // 56
0, 1, 7, -1, 2, 3, 8, 9, 4, 5, -1, -1, 6, -1, -1, -1, // 57
0, 1, 7, 8, 2, 3, 9, -1, 4, 5, -1, -1, 6, -1, -1, -1, // 58
0, 1, 7, 8, 2, 3, 9, 10, 4, 5, -1, -1, 6, -1, -1, -1, // 59
0, 1, 8, -1, 2, 3, 9, -1, 4, 5, -1, -1, 6, 7, -1, -1, // 60
0, 1, 8, -1, 2, 3, 9, 10, 4, 5, -1, -1, 6, 7, -1, -1, // 61
0, 1, 8, 9, 2, 3, 10, -1, 4, 5, -1, -1, 6, 7, -1, -1, // 62
0, 1, 8, 9, 2, 3, 10, 11, 4, 5, -1, -1, 6, 7, -1, -1, // 63
0, -1, -1, -1, 1, -1, -1, -1, 2, -1, -1, -1, 3, -1, -1, -1, // 64
0, -1, -1, -1, 1, -1, -1, -1, 2, -1, -1, -1, 3, 4, -1, -1, // 65
0, -1, -1, -1, 1, -1, -1, -1, 2, -1, -1, -1, 3, 4, 5, -1, // 66
0, -1, -1, -1, 1, -1, -1, -1, 2, 3, -1, -1, 4, -1, -1, -1, // 67
0, -1, -1, -1, 1, -1, -1, -1, 2, 3, -1, -1, 4, 5, -1, -1, // 68
0, -1, -1, -1, 1, -1, -1, -1, 2, 3, -1, -1, 4, 5, 6, -1, // 69
0, -1, -1, -1, 1, -1, -1, -1, 2, 3, 4, -1, 5, -1, -1, -1, // 70
0, -1, -1, -1, 1, -1, -1, -1, 2, 3, 4, -1, 5, 6, -1, -1, // 71
0, -1, -1, -1, 1, -1, -1, -1, 2, 3, 4, -1, 5, 6, 7, -1, // 72
0, -1, -1, -1, 1, 2, -1, -1, 3, -1, -1, -1, 4, -1, -1, -1, // 73
0, -1, -1, -1, 1, 2, -1, -1, 3, -1, -1, -1, 4, 5, -1, -1, // 74
0, -1, -1, -1, 1, 2, -1, -1, 3, -1, -1, -1, 4, 5, 6, -1, // 75
0, -1, -1, -1, 1, 2, -1, -1, 3, 4, -1, -1, 5, -1, -1, -1, // 76
0, -1, -1, -1, 1, 2, -1, -1, 3, 4, -1, -1, 5, 6, -1, -1, // 77
0, -1, -1, -1, 1, 2, -1, -1, 3, 4, -1, -1, 5, 6, 7, -1, // 78
0, -1, -1, -1, 1, 2, -1, -1, 3, 4, 5, -1, 6, -1, -1, -1, // 79
0, -1, -1, -1, 1, 2, -1, -1, 3, 4, 5, -1, 6, 7, -1, -1, // 80
0, -1, -1, -1, 1, 2, -1, -1, 3, 4, 5, -1, 6, 7, 8, -1, // 81
0, -1, -1, -1, 1, 2, 3, -1, 4, -1, -1, -1, 5, -1, -1, -1, // 82
0, -1, -1, -1, 1, 2, 3, -1, 4, -1, -1, -1, 5, 6, -1, -1, // 83
0, -1, -1, -1, 1, 2, 3, -1, 4, -1, -1, -1, 5, 6, 7, -1, // 84
0, -1, -1, -1, 1, 2, 3, -1, 4, 5, -1, -1, 6, -1, -1, -1, // 85
0, -1, -1, -1, 1, 2, 3, -1, 4, 5, -1, -1, 6, 7, -1, -1, // 86
0, -1, -1, -1, 1, 2, 3, -1, 4, 5, -1, -1, 6, 7, 8, -1, // 87
0, -1, -1, -1, 1, 2, 3, -1, 4, 5, 6, -1, 7, -1, -1, -1, // 88
0, -1, -1, -1, 1, 2, 3, -1, 4, 5, 6, -1, 7, 8, -1, -1, // 89
0, -1, -1, -1, 1, 2, 3, -1, 4, 5, 6, -1, 7, 8, 9, -1, // 90
0, 1, -1, -1, 2, -1, -1, -1, 3, -1, -1, -1, 4, -1, -1, -1, // 91
0, 1, -1, -1, 2, -1, -1, -1, 3, -1, -1, -1, 4, 5, -1, -1, // 92
0, 1, -1, -1, 2, -1, -1, -1, 3, -1, -1, -1, 4, 5, 6, -1, // 93
0, 1, -1, -1, 2, -1, -1, -1, 3, 4, -1, -1, 5, -1, -1, -1, // 94
0, 1, -1, -1, 2, -1, -1, -1, 3, 4, -1, -1, 5, 6, -1, -1, // 95
0, 1, -1, -1, 2, -1, -1, -1, 3, 4, -1, -1, 5, 6, 7, -1, // 96
0, 1, -1, -1, 2, -1, -1, -1, 3, 4, 5, -1, 6, -1, -1, -1, // 97
0, 1, -1, -1, 2, -1, -1, -1, 3, 4, 5, -1, 6, 7, -1, -1, // 98
0, 1, -1, -1, 2, -1, -1, -1, 3, 4, 5, -1, 6, 7, 8, -1, // 99
0, 1, -1, -1, 2, 3, -1, -1, 4, -1, -1, -1, 5, -1, -1, -1, // 100
0, 1, -1, -1, 2, 3, -1, -1, 4, -1, -1, -1, 5, 6, -1, -1, // 101
0, 1, -1, -1, 2, 3, -1, -1, 4, -1, -1, -1, 5, 6, 7, -1, // 102
0, 1, -1, -1, 2, 3, -1, -1, 4, 5, -1, -1, 6, -1, -1, -1, // 103
0, 1, -1, -1, 2, 3, -1, -1, 4, 5, -1, -1, 6, 7, -1, -1, // 104
0, 1, -1, -1, 2, 3, -1, -1, 4, 5, -1, -1, 6, 7, 8, -1, // 105
0, 1, -1, -1, 2, 3, -1, -1, 4, 5, 6, -1, 7, -1, -1, -1, // 106
0, 1, -1, -1, 2, 3, -1, -1, 4, 5, 6, -1, 7, 8, -1, -1, // 107
0, 1, -1, -1, 2, 3, -1, -1, 4, 5, 6, -1, 7, 8, 9, -1, // 108
0, 1, -1, -1, 2, 3, 4, -1, 5, -1, -1, -1, 6, -1, -1, -1, // 109
0, 1, -1, -1, 2, 3, 4, -1, 5, -1, -1, -1, 6, 7, -1, -1, // 110
0, 1, -1, -1, 2, 3, 4, -1, 5, -1, -1, -1, 6, 7, 8, -1, // 111
0, 1, -1, -1, 2, 3, 4, -1, 5, 6, -1, -1, 7, -1, -1, -1, // 112
0, 1, -1, -1, 2, 3, 4, -1, 5, 6, -1, -1, 7, 8, -1, -1, // 113
0, 1, -1, -1, 2, 3, 4, -1, 5, 6, -1, -1, 7, 8, 9, -1, // 114
0, 1, -1, -1, 2, 3, 4, -1, 5, 6, 7, -1, 8, -1, -1, -1, // 115
0, 1, -1, -1, 2, 3, 4, -1, 5, 6, 7, -1, 8, 9, -1, -1, // 116
0, 1, -1, -1, 2, 3, 4, -1, 5, 6, 7, -1, 8, 9, 10, -1, // 117
0, 1, 2, -1, 3, -1, -1, -1, 4, -1, -1, -1, 5, -1, -1, -1, // 118
0, 1, 2, -1, 3, -1, -1, -1, 4, -1, -1, -1, 5, 6, -1, -1, // 119
0, 1, 2, -1, 3, -1, -1, -1, 4, -1, -1, -1, 5, 6, 7, -1, // 120
0, 1, 2, -1, 3, -1, -1, -1, 4, 5, -1, -1, 6, -1, -1, -1, // 121
0, 1, 2, -1, 3, -1, -1, -1, 4, 5, -1, -1, 6, 7, -1, -1, // 122
0, 1, 2, -1, 3, -1, -1, -1, 4, 5, -1, -1, 6, 7, 8, -1, // 123
0, 1, 2, -1, 3, -1, -1, -1, 4, 5, 6, -1, 7, -1, -1, -1, // 124
0, 1, 2, -1, 3, -1, -1, -1, 4, 5, 6, -1, 7, 8, -1, -1, // 125
0, 1, 2, -1, 3, -1, -1, -1, 4, 5, 6, -1, 7, 8, 9, -1, // 126
0, 1, 2, -1, 3, 4, -1, -1, 5, -1, -1, -1, 6, -1, -1, -1, // 127
0, 1, 2, -1, 3, 4, -1, -1, 5, -1, -1, -1, 6, 7, -1, -1, // 128
0, 1, 2, -1, 3, 4, -1, -1, 5, -1, -1, -1, 6, 7, 8, -1, // 129
0, 1, 2, -1, 3, 4, -1, -1, 5, 6, -1, -1, 7, -1, -1, -1, // 130
0, 1, 2, -1, 3, 4, -1, -1, 5, 6, -1, -1, 7, 8, -1, -1, // 131
0, 1, 2, -1, 3, 4, -1, -1, 5, 6, -1, -1, 7, 8, 9, -1, // 132
0, 1, 2, -1, 3, 4, -1, -1, 5, 6, 7, -1, 8, -1, -1, -1, // 133
0, 1, 2, -1, 3, 4, -1, -1, 5, 6, 7, -1, 8, 9, -1, -1, // 134
0, 1, 2, -1, 3, 4, -1, -1, 5, 6, 7, -1, 8, 9, 10, -1, // 135
0, 1, 2, -1, 3, 4, 5, -1, 6, -1, -1, -1, 7, -1, -1, -1, // 136
0, 1, 2, -1, 3, 4, 5, -1, 6, -1, -1, -1, 7, 8, -1, -1, // 137
0, 1, 2, -1, 3, 4, 5, -1, 6, -1, -1, -1, 7, 8, 9, -1, // 138
0, 1, 2, -1, 3, 4, 5, -1, 6, 7, -1, -1, 8, -1, -1, -1, // 139
0, 1, 2, -1, 3, 4, 5, -1, 6, 7, -1, -1, 8, 9, -1, -1, // 140
0, 1, 2, -1, 3, 4, 5, -1, 6, 7, -1, -1, 8, 9, 10, -1, // 141
0, 1, 2, -1, 3, 4, 5, -1, 6, 7, 8, -1, 9, -1, -1, -1, // 142
0, 1, 2, -1, 3, 4, 5, -1, 6, 7, 8, -1, 9, 10, -1, -1, // 143
0, 1, 2, -1, 3, 4, 5, -1, 6, 7, 8, -1, 9, 10, 11, -1, // 144
-1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1, 1, // 145
-1, -1, -1, -1, -1, -1, -1, 0, 2, -1, -1, -1, -1, -1, -1, 1, // 146
-1, -1, -1, -1, -1, -1, -1, 0, 2, -1, 3, -1, -1, -1, -1, 1, // 147
-1, -1, -1, -1, -1, -1, -1, 0, 2, -1, 3, -1, 4, -1, -1, 1, // 148
-1, -1, -1, -1, -1, -1, -1, 0, 2, -1, 3, -1, 4, -1, 5, 1, // 149
1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1, 2, // 150
1, -1, -1, -1, -1, -1, -1, 0, 3, -1, -1, -1, -1, -1, -1, 2, // 151
1, -1, -1, -1, -1, -1, -1, 0, 3, -1, 4, -1, -1, -1, -1, 2, // 152
1, -1, -1, -1, -1, -1, -1, 0, 3, -1, 4, -1, 5, -1, -1, 2, // 153
1, -1, -1, -1, -1, -1, -1, 0, 3, -1, 4, -1, 5, -1, 6, 2, // 154
1, -1, 2, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1, 3, // 155
1, -1, 2, -1, -1, -1, -1, 0, 4, -1, -1, -1, -1, -1, -1, 3, // 156
1, -1, 2, -1, -1, -1, -1, 0, 4, -1, 5, -1, -1, -1, -1, 3, // 157
1, -1, 2, -1, -1, -1, -1, 0, 4, -1, 5, -1, 6, -1, -1, 3, // 158
1, -1, 2, -1, -1, -1, -1, 0, 4, -1, 5, -1, 6, -1, 7, 3, // 159
1, -1, 2, -1, 3, -1, -1, 0, -1, -1, -1, -1, -1, -1, -1, 4, // 160
1, -1, 2, -1, 3, -1, -1, 0, 5, -1, -1, -1, -1, -1, -1, 4, // 161
1, -1, 2, -1, 3, -1, -1, 0, 5, -1, 6, -1, -1, -1, -1, 4, // 162
1, -1, 2, -1, 3, -1, -1, 0, 5, -1, 6, -1, 7, -1, -1, 4, // 163
1, -1, 2, -1, 3, -1, -1, 0, 5, -1, 6, -1, 7, -1, 8, 4, // 164
1, -1, 2, -1, 3, -1, 4, 0, -1, -1, -1, -1, -1, -1, -1, 5, // 165
1, -1, 2, -1, 3, -1, 4, 0, 6, -1, -1, -1, -1, -1, -1, 5, // 166
1, -1, 2, -1, 3, -1, 4, 0, 6, -1, 7, -1, -1, -1, -1, 5, // 167
1, -1, 2, -1, 3, -1, 4, 0, 6, -1, 7, -1, 8, -1, -1, 5, // 168
1, -1, 2, -1, 3, -1, 4, 0, 6, -1, 7, -1, 8, -1, 9, 5, // 169
};
static const __m128i* vectors = (const __m128i*)vectorsrawbytes;
static int read_int(const uint8_t* in, uint32_t* out) {
*out = in[0] & 0x7F;
if (in[0] < 128) {
return 1;
}
*out = ((in[1] & 0x7FU) << 7) | *out;
if (in[1] < 128) {
return 2;
}
*out = ((in[2] & 0x7FU) << 14) | *out;
if (in[2] < 128) {
return 3;
}
*out = ((in[3] & 0x7FU) << 21) | *out;
if (in[3] < 128) {
return 4;
}
*out = ((in[4] & 0x7FU) << 28) | *out;
return 5;
}
static inline int read_int_delta(const uint8_t* in, uint32_t* out, uint32_t* prev) {
*out = in[0] & 0x7F;
if (in[0] < 128) {
*prev += *out;
*out = *prev;
return 1;
}
*out = ((in[1] & 0x7FU) << 7) | *out;
if (in[1] < 128) {
*prev += *out;
*out = *prev;
return 2;
}
*out = ((in[2] & 0x7FU) << 14) | *out;
if (in[2] < 128) {
*prev += *out;
*out = *prev;
return 3;
}
*out = ((in[3] & 0x7FU) << 21) | *out;
if (in[3] < 128) {
*prev += *out;
*out = *prev;
return 4;
}
*out = ((in[4] & 0x7FU) << 28) | *out;
*prev += *out;
*out = *prev;
return 5;
}
static uint64_t masked_vbyte_read_group(const uint8_t* in, uint32_t* out,
uint64_t mask, uint64_t* ints_read) {
__m128i initial = _mm_lddqu_si128((const __m128i *) (in));
__m128i * mout = (__m128i *) out;
if (!(mask & 0xFFFF)) {
__m128i result = _mm_cvtepi8_epi32(initial);
_mm_storeu_si128(mout, result);
initial = _mm_srli_si128(initial, 4);
result = _mm_cvtepi8_epi32(initial);
_mm_storeu_si128(mout + 1, result);
initial = _mm_srli_si128(initial, 4);
result = _mm_cvtepi8_epi32(initial);
_mm_storeu_si128(mout + 2, result);
initial = _mm_srli_si128(initial, 4);
result = _mm_cvtepi8_epi32(initial);
_mm_storeu_si128(mout + 3, result);
*ints_read = 16;
return 16;
}
uint32_t low_12_bits = mask & 0xFFF;
// combine index and bytes consumed into a single lookup
index_bytes_consumed combined = combined_lookup[low_12_bits];
uint64_t consumed = combined.bytes_consumed;
uint8_t index = combined.index;
__m128i shuffle_vector = vectors[index];
if (index < 64) {
*ints_read = 6;
__m128i bytes_to_decode = _mm_shuffle_epi8(initial, shuffle_vector);
__m128i low_bytes = _mm_and_si128(bytes_to_decode,
_mm_set1_epi16(0x007F));
__m128i high_bytes = _mm_and_si128(bytes_to_decode,
_mm_set1_epi16(0x7F00));
__m128i high_bytes_shifted = _mm_srli_epi16(high_bytes, 1);
__m128i packed_result = _mm_or_si128(low_bytes, high_bytes_shifted);
__m128i unpacked_result_a = _mm_and_si128(packed_result,
_mm_set1_epi32(0x0000FFFF));
_mm_storeu_si128(mout, unpacked_result_a);
__m128i unpacked_result_b = _mm_srli_epi32(packed_result, 16);
_mm_storel_epi64(mout+1, unpacked_result_b);
//_mm_storeu_si128(mout + 1, unpacked_result_b); // maybe faster to write 16 bytes?
return consumed;
}
if (index < 145) {
*ints_read = 4;
__m128i bytes_to_decode = _mm_shuffle_epi8(initial, shuffle_vector);
__m128i low_bytes = _mm_and_si128(bytes_to_decode,
_mm_set1_epi32(0x0000007F));
__m128i middle_bytes = _mm_and_si128(bytes_to_decode,
_mm_set1_epi32(0x00007F00));
__m128i high_bytes = _mm_and_si128(bytes_to_decode,
_mm_set1_epi32(0x007F0000));
__m128i middle_bytes_shifted = _mm_srli_epi32(middle_bytes, 1);
__m128i high_bytes_shifted = _mm_srli_epi32(high_bytes, 2);
__m128i low_middle = _mm_or_si128(low_bytes, middle_bytes_shifted);
__m128i result = _mm_or_si128(low_middle, high_bytes_shifted);
_mm_storeu_si128(mout, result);
return consumed;
}
*ints_read = 2;
__m128i data_bits = _mm_and_si128(initial, _mm_set1_epi8(0x7F));
__m128i bytes_to_decode = _mm_shuffle_epi8(data_bits, shuffle_vector);
__m128i split_bytes = _mm_mullo_epi16(bytes_to_decode,
_mm_setr_epi16(128, 64, 32, 16, 128, 64, 32, 16));
__m128i shifted_split_bytes = _mm_slli_epi64(split_bytes, 8);
__m128i recombined = _mm_or_si128(split_bytes, shifted_split_bytes);
__m128i low_byte = _mm_srli_epi64(bytes_to_decode, 56);
__m128i result_evens = _mm_or_si128(recombined, low_byte);
__m128i result = _mm_shuffle_epi8(result_evens,
_mm_setr_epi8(0, 2, 4, 6, 8, 10, 12, 14, -1, -1, -1, -1, -1, -1, -1,
-1));
_mm_storel_epi64(mout, result);
//_mm_storeu_si128(mout, result); // maybe faster to write 16 bytes?
return consumed;
}
static inline __m128i PrefixSum(__m128i curr, __m128i prev) {
__m128i Add = _mm_slli_si128(curr, 4); // Cycle 1: [- A B C] (already done)
prev = _mm_shuffle_epi32(prev, 0xff); // Cycle 2: [P P P P]
curr = _mm_add_epi32(curr, Add); // Cycle 2: [A AB BC CD]
Add = _mm_slli_si128(curr, 8); // Cycle 3: [- - A AB]
curr = _mm_add_epi32(curr, prev); // Cycle 3: [PA PAB PBC PCD]
curr = _mm_add_epi32(curr, Add); // Cycle 4: [PA PAB PABC PABCD]
return curr;
}
// only the first two ints of curr are meaningful, rest is garbage to beignored
static inline __m128i PrefixSum2ints(__m128i curr, __m128i prev) {
__m128i Add = _mm_slli_si128(curr, 4); // Cycle 1: [- A B G] (already done)
prev = _mm_shuffle_epi32(prev, 0xff); // Cycle 2: [P P P P]
curr = _mm_add_epi32(curr, Add); // Cycle 2: [A AB BG GG]
curr = _mm_shuffle_epi32(curr, 0x54); //Cycle 3:[A AB AB AB]
curr = _mm_add_epi32(curr, prev); // Cycle 4: [PA PAB PAB PAB]
return curr;
}
static uint64_t masked_vbyte_read_group_delta(const uint8_t* in, uint32_t* out,
uint64_t mask, uint64_t* ints_read, __m128i * prev) {
__m128i initial = _mm_lddqu_si128((const __m128i *) (in));
__m128i * mout = (__m128i *) out;
if (!(mask & 0xFFFF)) {
__m128i result = _mm_cvtepi8_epi32(initial);
*prev = PrefixSum(result, *prev);
_mm_storeu_si128(mout, *prev);
initial = _mm_srli_si128(initial, 4);
result = _mm_cvtepi8_epi32(initial);
*prev = PrefixSum(result, *prev);
_mm_storeu_si128(mout + 1, *prev);
initial = _mm_srli_si128(initial, 4);
result = _mm_cvtepi8_epi32(initial);
*prev = PrefixSum(result, *prev);
_mm_storeu_si128(mout + 2, *prev);
initial = _mm_srli_si128(initial, 4);
result = _mm_cvtepi8_epi32(initial);
*prev = PrefixSum(result, *prev);
_mm_storeu_si128(mout + 3, *prev);
*ints_read = 16;
return 16;
}
uint32_t low_12_bits = mask & 0xFFF;
// combine index and bytes consumed into a single lookup
index_bytes_consumed combined = combined_lookup[low_12_bits];
uint64_t consumed = combined.bytes_consumed;
uint8_t index = combined.index;
__m128i shuffle_vector = vectors[index];
if (index < 64) {
*ints_read = 6;
__m128i bytes_to_decode = _mm_shuffle_epi8(initial, shuffle_vector);
__m128i low_bytes = _mm_and_si128(bytes_to_decode,
_mm_set1_epi16(0x007F));
__m128i high_bytes = _mm_and_si128(bytes_to_decode,
_mm_set1_epi16(0x7F00));
__m128i high_bytes_shifted = _mm_srli_epi16(high_bytes, 1);
__m128i packed_result = _mm_or_si128(low_bytes, high_bytes_shifted);
__m128i unpacked_result_a = _mm_and_si128(packed_result,
_mm_set1_epi32(0x0000FFFF));