jixel 0.2.8

Tiny JPEG XL encoder
Documentation
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
/*
 * // Copyright (c) Radzivon Bartoshyk 5/2026. All rights reserved.
 * //
 * // Redistribution and use in source and binary forms, with or without modification,
 * // are permitted provided that the following conditions are met:
 * //
 * // 1.  Redistributions of source code must retain the above copyright notice, this
 * // list of conditions and the following disclaimer.
 * //
 * // 2.  Redistributions in binary form must reproduce the above copyright notice,
 * // this list of conditions and the following disclaimer in the documentation
 * // and/or other materials provided with the distribution.
 * //
 * // 3.  Neither the name of the copyright holder nor the names of its
 * // contributors may be used to endorse or promote products derived from
 * // this software without specific prior written permission.
 * //
 * // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

pub(crate) const K_NON_ZERO_BUCKETS: usize = 37;
pub(crate) const K_ZERO_DENSITY_CONTEXT_COUNT: usize = 458;
pub(crate) const K_NUM_BLOCK_CTXS: usize = 4;
pub(crate) const K_NUM_AC_CONTEXTS: usize =
    K_NUM_BLOCK_CTXS * (K_NON_ZERO_BUCKETS + K_ZERO_DENSITY_CONTEXT_COUNT); // 1980

pub(crate) const K_NUM_AC_STRATEGY_CODES: usize = 27;

/// Frequency-band context per zigzag position. Index 0 is unused (DC).
pub(crate) static K_COEFF_FREQ_CONTEXT: [u16; 64] = [
    0xBAD, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19,
    19, 20, 20, 21, 21, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27,
    27, 27, 27, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30,
];

/// Remaining-nonzeros context bucket.
pub(crate) static K_COEFF_NUM_NONZERO_CONTEXT: [u16; 64] = [
    0xBAD, 0, 31, 62, 62, 93, 93, 93, 93, 123, 123, 123, 123, 152, 152, 152, 152, 152, 152, 152,
    152, 180, 180, 180, 180, 180, 180, 180, 180, 180, 180, 180, 180, 206, 206, 206, 206, 206, 206,
    206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206, 206,
    206, 206, 206, 206, 206, 206,
];

/// Static block context map signaled in WriteDCGlobal.
pub(crate) static K_COMPACT_BLOCK_CONTEXT_MAP: [u8; 39] = [
    0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, // Y
    2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, // X
    2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, // B
];

#[rustfmt::skip]
pub(crate) static K_BLOCK_CONTEXT_MAP: [u8; 81] = [
    // X row. Position 4 = DCT16X16 (decoder ctx 2). Position 5 = DCT32X32
    // (ord 3, ctx 2). Position 3 = DCT4X4, positions 12,13 = DCT4X8/DCT8X4 (all ord 1, ctx 2). Positions 6, 7 = DCT16X8/8X16 (ctx 3).
    // Positions 10, 11 = DCT32X16/DCT16X32 (ord 6, ctx 3); position 18 = DCT64X64 (shape 7, ctx 3).
    2, 0, 0, 2, 2, 2, 3, 3, 0, 0, 3, 3, 2, 2,
    0, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0,
    // Y row. Position 4 = DCT16X16 (decoder ctx 0). Positions 6, 7 = DCT16X8/8X16 (ctx 1).
    // Positions 10, 11 = DCT32X16/DCT16X32 (ord 6, ctx 1); position 18 = DCT64X64 (shape 7, ctx 1).
    0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0,
    0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,
    // B row. Position 4 = DCT16X16 (decoder ctx 2). Position 5 = DCT32X32
    // (ord 3, ctx 2). Position 3 = DCT4X4, positions 12,13 = DCT4X8/DCT8X4 (all ord 1, ctx 2). Positions 6, 7 = DCT16X8/8X16 (ctx 3).
    // Positions 10, 11 = DCT32X16/DCT16X32 (ord 6, ctx 3); position 18 = DCT64X64 (shape 7, ctx 3).
    2, 0, 0, 2, 2, 2, 3, 3, 0, 0, 3, 3, 2, 2,
    0, 0, 0, 0, 3, 3, 3, 0, 0, 0, 0, 0, 0,
];

#[inline]
pub(crate) fn block_context(c: usize, ac_strategy_code: u8) -> u32 {
    K_BLOCK_CONTEXT_MAP[c * K_NUM_AC_STRATEGY_CODES + ac_strategy_code as usize] as u32
}

#[inline]
pub(crate) fn non_zero_context(non_zeros: u32, block_ctx: u32) -> u32 {
    let bucket = if non_zeros < 8 {
        non_zeros
    } else if non_zeros >= 64 {
        36
    } else {
        4 + non_zeros / 2
    };
    bucket * K_NUM_BLOCK_CTXS as u32 + block_ctx
}

/// 8x8 specialization: covered_blocks = 1, log2_covered_blocks = 0, so
/// nonzeros_left and k pass through directly.
#[inline]
pub(crate) fn zero_density_context_8x8(nonzeros_left: usize, k: usize, prev: usize) -> usize {
    (K_COEFF_NUM_NONZERO_CONTEXT[nonzeros_left] as usize + K_COEFF_FREQ_CONTEXT[k] as usize) * 2
        + prev
}

/// General `zero_density_context` from libjxl-tiny. For 8x8 use
/// `zero_density_context_8x8`. For multi-block transforms, `covered_blocks` is
/// the number of 8x8 sub-blocks (2 for DCT16X8/DCT8X16) and `log2_covered_blocks`
/// is `log2(covered_blocks)` (1 for the rectangular pair).
#[inline]
pub(crate) fn zero_density_context(
    nonzeros_left: usize,
    k: usize,
    covered_blocks: usize,
    log2_covered_blocks: usize,
    prev: usize,
) -> usize {
    let nz = (nonzeros_left + covered_blocks - 1) >> log2_covered_blocks;
    let kk = k >> log2_covered_blocks;
    (K_COEFF_NUM_NONZERO_CONTEXT[nz] as usize + K_COEFF_FREQ_CONTEXT[kk] as usize) * 2 + prev
}

#[inline]
pub(crate) const fn zero_density_contexts_offset(block_ctx: u32) -> u32 {
    K_NUM_BLOCK_CTXS as u32 * K_NON_ZERO_BUCKETS as u32
        + K_ZERO_DENSITY_CONTEXT_COUNT as u32 * block_ctx
}

/// 8x8 zigzag order. Coefficient at zigzag position k is at raw index
/// K_COEFF_ORDER_8X8[k].
#[rustfmt::skip]
pub(crate) static K_COEFF_ORDER_8X8: [u8; 64] = [
    0,   1,   8,   16, 9,   2,   3,   10,
    17,  24,  32,  25, 18,  11,  4,   5,
    12,  19,  26,  33, 40,  48,  41,  34,
    27,  20,  13,  6,  7,   14,  21,  28,
    35,  42,  49,  56, 57,  50,  43,  36,
    29,  22,  15,  23, 30,  37,  44,  51,
    58,  59,  52,  45, 38,  31,  39,  46,
    53,  60,  61,  54, 47,  55,  62,  63,
];

/// 16x8 / 8x16 coefficient order (shared, libjxl-tiny `kCoeffOrders` offset 64).
/// 128 entries. Positions 0 and 1 are LF positions; HF positions are zigzagged
/// over the 16x8 grid.
#[rustfmt::skip]
pub(crate) static K_COEFF_ORDER_16X8: [u8; 128] = [
    0,   1,   16,  2,   3,   17,  32,  18,  4,   5,   19,
    33,  48,  34,  20,  6,   7,   21,  35,  49,  64,  50,  36,  22,  8,   9,
    23,  37,  51,  65,  80,  66,  52,  38,  24,  10,  11,  25,  39,  53,  67,
    81,  96,  82,  68,  54,  40,  26,  12,  13,  27,  41,  55,  69,  83,  97,
    112, 98,  84,  70,  56,  42,  28,  14,  15,  29,  43,  57,  71,  85,  99,
    113, 114, 100, 86,  72,  58,  44,  30,  31,  45,  59,  73,  87,  101, 115,
    116, 102, 88,  74,  60,  46,  47,  61,  75,  89,  103, 117, 118, 104, 90,
    76,  62,  63,  77,  91,  105, 119, 120, 106, 92,  78,  79,  93,  107, 121,
    122, 108, 94,  95,  109, 123, 124, 110, 111, 125, 126, 127,
];

#[rustfmt::skip]
pub(crate) static  K_COEFF_ORDER_16X16: [u8; 256] = [
       0,    1,   16,   17,   32,    2,    3,   18,
      33,   48,   64,   49,   34,   19,    4,    5,
      20,   35,   50,   65,   80,   96,   81,   66,
      51,   36,   21,    6,    7,   22,   37,   52,
      67,   82,   97,  112,  128,  113,   98,   83,
      68,   53,   38,   23,    8,    9,   24,   39,
      54,   69,   84,   99,  114,  129,  144,  160,
     145,  130,  115,  100,   85,   70,   55,   40,
      25,   10,   11,   26,   41,   56,   71,   86,
     101,  116,  131,  146,  161,  176,  192,  177,
     162,  147,  132,  117,  102,   87,   72,   57,
      42,   27,   12,   13,   28,   43,   58,   73,
      88,  103,  118,  133,  148,  163,  178,  193,
     208,  224,  209,  194,  179,  164,  149,  134,
     119,  104,   89,   74,   59,   44,   29,   14,
      15,   30,   45,   60,   75,   90,  105,  120,
     135,  150,  165,  180,  195,  210,  225,  240,
     241,  226,  211,  196,  181,  166,  151,  136,
     121,  106,   91,   76,   61,   46,   31,   47,
      62,   77,   92,  107,  122,  137,  152,  167,
     182,  197,  212,  227,  242,  243,  228,  213,
     198,  183,  168,  153,  138,  123,  108,   93,
      78,   63,   79,   94,  109,  124,  139,  154,
     169,  184,  199,  214,  229,  244,  245,  230,
     215,  200,  185,  170,  155,  140,  125,  110,
      95,  111,  126,  141,  156,  171,  186,  201,
     216,  231,  246,  247,  232,  217,  202,  187,
     172,  157,  142,  127,  143,  158,  173,  188,
     203,  218,  233,  248,  249,  234,  219,  204,
     189,  174,  159,  175,  190,  205,  220,  235,
     250,  251,  236,  221,  206,  191,  207,  222,
     237,  252,  253,  238,  223,  239,  254,  255,
];

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

/// Natural coefficient order for DCT32X16 and DCT16X32 (shared, libjxl
/// `QuantTable::DCT16X32` geometry).
pub(crate) static K_COEFF_ORDER_32X16: [u16; 512] = [
    0, 1, 2, 3, 32, 33, 34, 35, 64, 4, 5, 65, 96, 66, 36, 6, 7, 37, 67, 97, 128, 98, 68, 38, 8, 9,
    39, 69, 99, 129, 160, 130, 100, 70, 40, 10, 11, 41, 71, 101, 131, 161, 192, 162, 132, 102, 72,
    42, 12, 13, 43, 73, 103, 133, 163, 193, 224, 194, 164, 134, 104, 74, 44, 14, 15, 45, 75, 105,
    135, 165, 195, 225, 256, 226, 196, 166, 136, 106, 76, 46, 16, 17, 47, 77, 107, 137, 167, 197,
    227, 257, 288, 258, 228, 198, 168, 138, 108, 78, 48, 18, 19, 49, 79, 109, 139, 169, 199, 229,
    259, 289, 320, 290, 260, 230, 200, 170, 140, 110, 80, 50, 20, 21, 51, 81, 111, 141, 171, 201,
    231, 261, 291, 321, 352, 322, 292, 262, 232, 202, 172, 142, 112, 82, 52, 22, 23, 53, 83, 113,
    143, 173, 203, 233, 263, 293, 323, 353, 384, 354, 324, 294, 264, 234, 204, 174, 144, 114, 84,
    54, 24, 25, 55, 85, 115, 145, 175, 205, 235, 265, 295, 325, 355, 385, 416, 386, 356, 326, 296,
    266, 236, 206, 176, 146, 116, 86, 56, 26, 27, 57, 87, 117, 147, 177, 207, 237, 267, 297, 327,
    357, 387, 417, 448, 418, 388, 358, 328, 298, 268, 238, 208, 178, 148, 118, 88, 58, 28, 29, 59,
    89, 119, 149, 179, 209, 239, 269, 299, 329, 359, 389, 419, 449, 480, 450, 420, 390, 360, 330,
    300, 270, 240, 210, 180, 150, 120, 90, 60, 30, 31, 61, 91, 121, 151, 181, 211, 241, 271, 301,
    331, 361, 391, 421, 451, 481, 482, 452, 422, 392, 362, 332, 302, 272, 242, 212, 182, 152, 122,
    92, 62, 63, 93, 123, 153, 183, 213, 243, 273, 303, 333, 363, 393, 423, 453, 483, 484, 454, 424,
    394, 364, 334, 304, 274, 244, 214, 184, 154, 124, 94, 95, 125, 155, 185, 215, 245, 275, 305,
    335, 365, 395, 425, 455, 485, 486, 456, 426, 396, 366, 336, 306, 276, 246, 216, 186, 156, 126,
    127, 157, 187, 217, 247, 277, 307, 337, 367, 397, 427, 457, 487, 488, 458, 428, 398, 368, 338,
    308, 278, 248, 218, 188, 158, 159, 189, 219, 249, 279, 309, 339, 369, 399, 429, 459, 489, 490,
    460, 430, 400, 370, 340, 310, 280, 250, 220, 190, 191, 221, 251, 281, 311, 341, 371, 401, 431,
    461, 491, 492, 462, 432, 402, 372, 342, 312, 282, 252, 222, 223, 253, 283, 313, 343, 373, 403,
    433, 463, 493, 494, 464, 434, 404, 374, 344, 314, 284, 254, 255, 285, 315, 345, 375, 405, 435,
    465, 495, 496, 466, 436, 406, 376, 346, 316, 286, 287, 317, 347, 377, 407, 437, 467, 497, 498,
    468, 438, 408, 378, 348, 318, 319, 349, 379, 409, 439, 469, 499, 500, 470, 440, 410, 380, 350,
    351, 381, 411, 441, 471, 501, 502, 472, 442, 412, 382, 383, 413, 443, 473, 503, 504, 474, 444,
    414, 415, 445, 475, 505, 506, 476, 446, 447, 477, 507, 508, 478, 479, 509, 510, 511,
];

/// Natural order for DCT64X32/DCT32X64 in normalized 32-row × 64-column layout.
/// Literal table (see `K_COEFF_ORDER_64X64` above for the same treatment); the
/// generating zig-zag recurrence lives in the tests as an oracle.
pub(crate) static K_COEFF_ORDER_64X32: [u16; 2048] = [
    0, 1, 2, 3, 4, 5, 6, 7, 64, 65, 66, 67, 68, 69, 70, 71, 128, 129, 130, 131, 132, 133, 134, 135,
    192, 193, 194, 195, 196, 197, 198, 199, 256, 8, 9, 257, 320, 258, 72, 10, 11, 73, 259, 321,
    384, 322, 260, 136, 74, 12, 13, 75, 137, 261, 323, 385, 448, 386, 324, 262, 200, 138, 76, 14,
    15, 77, 139, 201, 263, 325, 387, 449, 512, 450, 388, 326, 264, 202, 140, 78, 16, 17, 79, 141,
    203, 265, 327, 389, 451, 513, 576, 514, 452, 390, 328, 266, 204, 142, 80, 18, 19, 81, 143, 205,
    267, 329, 391, 453, 515, 577, 640, 578, 516, 454, 392, 330, 268, 206, 144, 82, 20, 21, 83, 145,
    207, 269, 331, 393, 455, 517, 579, 641, 704, 642, 580, 518, 456, 394, 332, 270, 208, 146, 84,
    22, 23, 85, 147, 209, 271, 333, 395, 457, 519, 581, 643, 705, 768, 706, 644, 582, 520, 458,
    396, 334, 272, 210, 148, 86, 24, 25, 87, 149, 211, 273, 335, 397, 459, 521, 583, 645, 707, 769,
    832, 770, 708, 646, 584, 522, 460, 398, 336, 274, 212, 150, 88, 26, 27, 89, 151, 213, 275, 337,
    399, 461, 523, 585, 647, 709, 771, 833, 896, 834, 772, 710, 648, 586, 524, 462, 400, 338, 276,
    214, 152, 90, 28, 29, 91, 153, 215, 277, 339, 401, 463, 525, 587, 649, 711, 773, 835, 897, 960,
    898, 836, 774, 712, 650, 588, 526, 464, 402, 340, 278, 216, 154, 92, 30, 31, 93, 155, 217, 279,
    341, 403, 465, 527, 589, 651, 713, 775, 837, 899, 961, 1024, 962, 900, 838, 776, 714, 652, 590,
    528, 466, 404, 342, 280, 218, 156, 94, 32, 33, 95, 157, 219, 281, 343, 405, 467, 529, 591, 653,
    715, 777, 839, 901, 963, 1025, 1088, 1026, 964, 902, 840, 778, 716, 654, 592, 530, 468, 406,
    344, 282, 220, 158, 96, 34, 35, 97, 159, 221, 283, 345, 407, 469, 531, 593, 655, 717, 779, 841,
    903, 965, 1027, 1089, 1152, 1090, 1028, 966, 904, 842, 780, 718, 656, 594, 532, 470, 408, 346,
    284, 222, 160, 98, 36, 37, 99, 161, 223, 285, 347, 409, 471, 533, 595, 657, 719, 781, 843, 905,
    967, 1029, 1091, 1153, 1216, 1154, 1092, 1030, 968, 906, 844, 782, 720, 658, 596, 534, 472,
    410, 348, 286, 224, 162, 100, 38, 39, 101, 163, 225, 287, 349, 411, 473, 535, 597, 659, 721,
    783, 845, 907, 969, 1031, 1093, 1155, 1217, 1280, 1218, 1156, 1094, 1032, 970, 908, 846, 784,
    722, 660, 598, 536, 474, 412, 350, 288, 226, 164, 102, 40, 41, 103, 165, 227, 289, 351, 413,
    475, 537, 599, 661, 723, 785, 847, 909, 971, 1033, 1095, 1157, 1219, 1281, 1344, 1282, 1220,
    1158, 1096, 1034, 972, 910, 848, 786, 724, 662, 600, 538, 476, 414, 352, 290, 228, 166, 104,
    42, 43, 105, 167, 229, 291, 353, 415, 477, 539, 601, 663, 725, 787, 849, 911, 973, 1035, 1097,
    1159, 1221, 1283, 1345, 1408, 1346, 1284, 1222, 1160, 1098, 1036, 974, 912, 850, 788, 726, 664,
    602, 540, 478, 416, 354, 292, 230, 168, 106, 44, 45, 107, 169, 231, 293, 355, 417, 479, 541,
    603, 665, 727, 789, 851, 913, 975, 1037, 1099, 1161, 1223, 1285, 1347, 1409, 1472, 1410, 1348,
    1286, 1224, 1162, 1100, 1038, 976, 914, 852, 790, 728, 666, 604, 542, 480, 418, 356, 294, 232,
    170, 108, 46, 47, 109, 171, 233, 295, 357, 419, 481, 543, 605, 667, 729, 791, 853, 915, 977,
    1039, 1101, 1163, 1225, 1287, 1349, 1411, 1473, 1536, 1474, 1412, 1350, 1288, 1226, 1164, 1102,
    1040, 978, 916, 854, 792, 730, 668, 606, 544, 482, 420, 358, 296, 234, 172, 110, 48, 49, 111,
    173, 235, 297, 359, 421, 483, 545, 607, 669, 731, 793, 855, 917, 979, 1041, 1103, 1165, 1227,
    1289, 1351, 1413, 1475, 1537, 1600, 1538, 1476, 1414, 1352, 1290, 1228, 1166, 1104, 1042, 980,
    918, 856, 794, 732, 670, 608, 546, 484, 422, 360, 298, 236, 174, 112, 50, 51, 113, 175, 237,
    299, 361, 423, 485, 547, 609, 671, 733, 795, 857, 919, 981, 1043, 1105, 1167, 1229, 1291, 1353,
    1415, 1477, 1539, 1601, 1664, 1602, 1540, 1478, 1416, 1354, 1292, 1230, 1168, 1106, 1044, 982,
    920, 858, 796, 734, 672, 610, 548, 486, 424, 362, 300, 238, 176, 114, 52, 53, 115, 177, 239,
    301, 363, 425, 487, 549, 611, 673, 735, 797, 859, 921, 983, 1045, 1107, 1169, 1231, 1293, 1355,
    1417, 1479, 1541, 1603, 1665, 1728, 1666, 1604, 1542, 1480, 1418, 1356, 1294, 1232, 1170, 1108,
    1046, 984, 922, 860, 798, 736, 674, 612, 550, 488, 426, 364, 302, 240, 178, 116, 54, 55, 117,
    179, 241, 303, 365, 427, 489, 551, 613, 675, 737, 799, 861, 923, 985, 1047, 1109, 1171, 1233,
    1295, 1357, 1419, 1481, 1543, 1605, 1667, 1729, 1792, 1730, 1668, 1606, 1544, 1482, 1420, 1358,
    1296, 1234, 1172, 1110, 1048, 986, 924, 862, 800, 738, 676, 614, 552, 490, 428, 366, 304, 242,
    180, 118, 56, 57, 119, 181, 243, 305, 367, 429, 491, 553, 615, 677, 739, 801, 863, 925, 987,
    1049, 1111, 1173, 1235, 1297, 1359, 1421, 1483, 1545, 1607, 1669, 1731, 1793, 1856, 1794, 1732,
    1670, 1608, 1546, 1484, 1422, 1360, 1298, 1236, 1174, 1112, 1050, 988, 926, 864, 802, 740, 678,
    616, 554, 492, 430, 368, 306, 244, 182, 120, 58, 59, 121, 183, 245, 307, 369, 431, 493, 555,
    617, 679, 741, 803, 865, 927, 989, 1051, 1113, 1175, 1237, 1299, 1361, 1423, 1485, 1547, 1609,
    1671, 1733, 1795, 1857, 1920, 1858, 1796, 1734, 1672, 1610, 1548, 1486, 1424, 1362, 1300, 1238,
    1176, 1114, 1052, 990, 928, 866, 804, 742, 680, 618, 556, 494, 432, 370, 308, 246, 184, 122,
    60, 61, 123, 185, 247, 309, 371, 433, 495, 557, 619, 681, 743, 805, 867, 929, 991, 1053, 1115,
    1177, 1239, 1301, 1363, 1425, 1487, 1549, 1611, 1673, 1735, 1797, 1859, 1921, 1984, 1922, 1860,
    1798, 1736, 1674, 1612, 1550, 1488, 1426, 1364, 1302, 1240, 1178, 1116, 1054, 992, 930, 868,
    806, 744, 682, 620, 558, 496, 434, 372, 310, 248, 186, 124, 62, 63, 125, 187, 249, 311, 373,
    435, 497, 559, 621, 683, 745, 807, 869, 931, 993, 1055, 1117, 1179, 1241, 1303, 1365, 1427,
    1489, 1551, 1613, 1675, 1737, 1799, 1861, 1923, 1985, 1986, 1924, 1862, 1800, 1738, 1676, 1614,
    1552, 1490, 1428, 1366, 1304, 1242, 1180, 1118, 1056, 994, 932, 870, 808, 746, 684, 622, 560,
    498, 436, 374, 312, 250, 188, 126, 127, 189, 251, 313, 375, 437, 499, 561, 623, 685, 747, 809,
    871, 933, 995, 1057, 1119, 1181, 1243, 1305, 1367, 1429, 1491, 1553, 1615, 1677, 1739, 1801,
    1863, 1925, 1987, 1988, 1926, 1864, 1802, 1740, 1678, 1616, 1554, 1492, 1430, 1368, 1306, 1244,
    1182, 1120, 1058, 996, 934, 872, 810, 748, 686, 624, 562, 500, 438, 376, 314, 252, 190, 191,
    253, 315, 377, 439, 501, 563, 625, 687, 749, 811, 873, 935, 997, 1059, 1121, 1183, 1245, 1307,
    1369, 1431, 1493, 1555, 1617, 1679, 1741, 1803, 1865, 1927, 1989, 1990, 1928, 1866, 1804, 1742,
    1680, 1618, 1556, 1494, 1432, 1370, 1308, 1246, 1184, 1122, 1060, 998, 936, 874, 812, 750, 688,
    626, 564, 502, 440, 378, 316, 254, 255, 317, 379, 441, 503, 565, 627, 689, 751, 813, 875, 937,
    999, 1061, 1123, 1185, 1247, 1309, 1371, 1433, 1495, 1557, 1619, 1681, 1743, 1805, 1867, 1929,
    1991, 1992, 1930, 1868, 1806, 1744, 1682, 1620, 1558, 1496, 1434, 1372, 1310, 1248, 1186, 1124,
    1062, 1000, 938, 876, 814, 752, 690, 628, 566, 504, 442, 380, 318, 319, 381, 443, 505, 567,
    629, 691, 753, 815, 877, 939, 1001, 1063, 1125, 1187, 1249, 1311, 1373, 1435, 1497, 1559, 1621,
    1683, 1745, 1807, 1869, 1931, 1993, 1994, 1932, 1870, 1808, 1746, 1684, 1622, 1560, 1498, 1436,
    1374, 1312, 1250, 1188, 1126, 1064, 1002, 940, 878, 816, 754, 692, 630, 568, 506, 444, 382,
    383, 445, 507, 569, 631, 693, 755, 817, 879, 941, 1003, 1065, 1127, 1189, 1251, 1313, 1375,
    1437, 1499, 1561, 1623, 1685, 1747, 1809, 1871, 1933, 1995, 1996, 1934, 1872, 1810, 1748, 1686,
    1624, 1562, 1500, 1438, 1376, 1314, 1252, 1190, 1128, 1066, 1004, 942, 880, 818, 756, 694, 632,
    570, 508, 446, 447, 509, 571, 633, 695, 757, 819, 881, 943, 1005, 1067, 1129, 1191, 1253, 1315,
    1377, 1439, 1501, 1563, 1625, 1687, 1749, 1811, 1873, 1935, 1997, 1998, 1936, 1874, 1812, 1750,
    1688, 1626, 1564, 1502, 1440, 1378, 1316, 1254, 1192, 1130, 1068, 1006, 944, 882, 820, 758,
    696, 634, 572, 510, 511, 573, 635, 697, 759, 821, 883, 945, 1007, 1069, 1131, 1193, 1255, 1317,
    1379, 1441, 1503, 1565, 1627, 1689, 1751, 1813, 1875, 1937, 1999, 2000, 1938, 1876, 1814, 1752,
    1690, 1628, 1566, 1504, 1442, 1380, 1318, 1256, 1194, 1132, 1070, 1008, 946, 884, 822, 760,
    698, 636, 574, 575, 637, 699, 761, 823, 885, 947, 1009, 1071, 1133, 1195, 1257, 1319, 1381,
    1443, 1505, 1567, 1629, 1691, 1753, 1815, 1877, 1939, 2001, 2002, 1940, 1878, 1816, 1754, 1692,
    1630, 1568, 1506, 1444, 1382, 1320, 1258, 1196, 1134, 1072, 1010, 948, 886, 824, 762, 700, 638,
    639, 701, 763, 825, 887, 949, 1011, 1073, 1135, 1197, 1259, 1321, 1383, 1445, 1507, 1569, 1631,
    1693, 1755, 1817, 1879, 1941, 2003, 2004, 1942, 1880, 1818, 1756, 1694, 1632, 1570, 1508, 1446,
    1384, 1322, 1260, 1198, 1136, 1074, 1012, 950, 888, 826, 764, 702, 703, 765, 827, 889, 951,
    1013, 1075, 1137, 1199, 1261, 1323, 1385, 1447, 1509, 1571, 1633, 1695, 1757, 1819, 1881, 1943,
    2005, 2006, 1944, 1882, 1820, 1758, 1696, 1634, 1572, 1510, 1448, 1386, 1324, 1262, 1200, 1138,
    1076, 1014, 952, 890, 828, 766, 767, 829, 891, 953, 1015, 1077, 1139, 1201, 1263, 1325, 1387,
    1449, 1511, 1573, 1635, 1697, 1759, 1821, 1883, 1945, 2007, 2008, 1946, 1884, 1822, 1760, 1698,
    1636, 1574, 1512, 1450, 1388, 1326, 1264, 1202, 1140, 1078, 1016, 954, 892, 830, 831, 893, 955,
    1017, 1079, 1141, 1203, 1265, 1327, 1389, 1451, 1513, 1575, 1637, 1699, 1761, 1823, 1885, 1947,
    2009, 2010, 1948, 1886, 1824, 1762, 1700, 1638, 1576, 1514, 1452, 1390, 1328, 1266, 1204, 1142,
    1080, 1018, 956, 894, 895, 957, 1019, 1081, 1143, 1205, 1267, 1329, 1391, 1453, 1515, 1577,
    1639, 1701, 1763, 1825, 1887, 1949, 2011, 2012, 1950, 1888, 1826, 1764, 1702, 1640, 1578, 1516,
    1454, 1392, 1330, 1268, 1206, 1144, 1082, 1020, 958, 959, 1021, 1083, 1145, 1207, 1269, 1331,
    1393, 1455, 1517, 1579, 1641, 1703, 1765, 1827, 1889, 1951, 2013, 2014, 1952, 1890, 1828, 1766,
    1704, 1642, 1580, 1518, 1456, 1394, 1332, 1270, 1208, 1146, 1084, 1022, 1023, 1085, 1147, 1209,
    1271, 1333, 1395, 1457, 1519, 1581, 1643, 1705, 1767, 1829, 1891, 1953, 2015, 2016, 1954, 1892,
    1830, 1768, 1706, 1644, 1582, 1520, 1458, 1396, 1334, 1272, 1210, 1148, 1086, 1087, 1149, 1211,
    1273, 1335, 1397, 1459, 1521, 1583, 1645, 1707, 1769, 1831, 1893, 1955, 2017, 2018, 1956, 1894,
    1832, 1770, 1708, 1646, 1584, 1522, 1460, 1398, 1336, 1274, 1212, 1150, 1151, 1213, 1275, 1337,
    1399, 1461, 1523, 1585, 1647, 1709, 1771, 1833, 1895, 1957, 2019, 2020, 1958, 1896, 1834, 1772,
    1710, 1648, 1586, 1524, 1462, 1400, 1338, 1276, 1214, 1215, 1277, 1339, 1401, 1463, 1525, 1587,
    1649, 1711, 1773, 1835, 1897, 1959, 2021, 2022, 1960, 1898, 1836, 1774, 1712, 1650, 1588, 1526,
    1464, 1402, 1340, 1278, 1279, 1341, 1403, 1465, 1527, 1589, 1651, 1713, 1775, 1837, 1899, 1961,
    2023, 2024, 1962, 1900, 1838, 1776, 1714, 1652, 1590, 1528, 1466, 1404, 1342, 1343, 1405, 1467,
    1529, 1591, 1653, 1715, 1777, 1839, 1901, 1963, 2025, 2026, 1964, 1902, 1840, 1778, 1716, 1654,
    1592, 1530, 1468, 1406, 1407, 1469, 1531, 1593, 1655, 1717, 1779, 1841, 1903, 1965, 2027, 2028,
    1966, 1904, 1842, 1780, 1718, 1656, 1594, 1532, 1470, 1471, 1533, 1595, 1657, 1719, 1781, 1843,
    1905, 1967, 2029, 2030, 1968, 1906, 1844, 1782, 1720, 1658, 1596, 1534, 1535, 1597, 1659, 1721,
    1783, 1845, 1907, 1969, 2031, 2032, 1970, 1908, 1846, 1784, 1722, 1660, 1598, 1599, 1661, 1723,
    1785, 1847, 1909, 1971, 2033, 2034, 1972, 1910, 1848, 1786, 1724, 1662, 1663, 1725, 1787, 1849,
    1911, 1973, 2035, 2036, 1974, 1912, 1850, 1788, 1726, 1727, 1789, 1851, 1913, 1975, 2037, 2038,
    1976, 1914, 1852, 1790, 1791, 1853, 1915, 1977, 2039, 2040, 1978, 1916, 1854, 1855, 1917, 1979,
    2041, 2042, 1980, 1918, 1919, 1981, 2043, 2044, 1982, 1983, 2045, 2046, 2047,
];

/// Natural JPEG XL coefficient order for an 8x8-block (64x64 pixel) DCT.
pub(crate) static K_COEFF_ORDER_64X64: [u16; 4096] = [
    0, 1, 2, 3, 4, 5, 6, 7, 64, 65, 66, 67, 68, 69, 70, 71, 128, 129, 130, 131, 132, 133, 134, 135,
    192, 193, 194, 195, 196, 197, 198, 199, 256, 257, 258, 259, 260, 261, 262, 263, 320, 321, 322,
    323, 324, 325, 326, 327, 384, 385, 386, 387, 388, 389, 390, 391, 448, 449, 450, 451, 452, 453,
    454, 455, 512, 8, 9, 72, 513, 576, 640, 577, 514, 136, 73, 10, 11, 74, 137, 200, 515, 578, 641,
    704, 768, 705, 642, 579, 516, 264, 201, 138, 75, 12, 13, 76, 139, 202, 265, 328, 517, 580, 643,
    706, 769, 832, 896, 833, 770, 707, 644, 581, 518, 392, 329, 266, 203, 140, 77, 14, 15, 78, 141,
    204, 267, 330, 393, 456, 519, 582, 645, 708, 771, 834, 897, 960, 1024, 961, 898, 835, 772, 709,
    646, 583, 520, 457, 394, 331, 268, 205, 142, 79, 16, 17, 80, 143, 206, 269, 332, 395, 458, 521,
    584, 647, 710, 773, 836, 899, 962, 1025, 1088, 1152, 1089, 1026, 963, 900, 837, 774, 711, 648,
    585, 522, 459, 396, 333, 270, 207, 144, 81, 18, 19, 82, 145, 208, 271, 334, 397, 460, 523, 586,
    649, 712, 775, 838, 901, 964, 1027, 1090, 1153, 1216, 1280, 1217, 1154, 1091, 1028, 965, 902,
    839, 776, 713, 650, 587, 524, 461, 398, 335, 272, 209, 146, 83, 20, 21, 84, 147, 210, 273, 336,
    399, 462, 525, 588, 651, 714, 777, 840, 903, 966, 1029, 1092, 1155, 1218, 1281, 1344, 1408,
    1345, 1282, 1219, 1156, 1093, 1030, 967, 904, 841, 778, 715, 652, 589, 526, 463, 400, 337, 274,
    211, 148, 85, 22, 23, 86, 149, 212, 275, 338, 401, 464, 527, 590, 653, 716, 779, 842, 905, 968,
    1031, 1094, 1157, 1220, 1283, 1346, 1409, 1472, 1536, 1473, 1410, 1347, 1284, 1221, 1158, 1095,
    1032, 969, 906, 843, 780, 717, 654, 591, 528, 465, 402, 339, 276, 213, 150, 87, 24, 25, 88,
    151, 214, 277, 340, 403, 466, 529, 592, 655, 718, 781, 844, 907, 970, 1033, 1096, 1159, 1222,
    1285, 1348, 1411, 1474, 1537, 1600, 1664, 1601, 1538, 1475, 1412, 1349, 1286, 1223, 1160, 1097,
    1034, 971, 908, 845, 782, 719, 656, 593, 530, 467, 404, 341, 278, 215, 152, 89, 26, 27, 90,
    153, 216, 279, 342, 405, 468, 531, 594, 657, 720, 783, 846, 909, 972, 1035, 1098, 1161, 1224,
    1287, 1350, 1413, 1476, 1539, 1602, 1665, 1728, 1792, 1729, 1666, 1603, 1540, 1477, 1414, 1351,
    1288, 1225, 1162, 1099, 1036, 973, 910, 847, 784, 721, 658, 595, 532, 469, 406, 343, 280, 217,
    154, 91, 28, 29, 92, 155, 218, 281, 344, 407, 470, 533, 596, 659, 722, 785, 848, 911, 974,
    1037, 1100, 1163, 1226, 1289, 1352, 1415, 1478, 1541, 1604, 1667, 1730, 1793, 1856, 1920, 1857,
    1794, 1731, 1668, 1605, 1542, 1479, 1416, 1353, 1290, 1227, 1164, 1101, 1038, 975, 912, 849,
    786, 723, 660, 597, 534, 471, 408, 345, 282, 219, 156, 93, 30, 31, 94, 157, 220, 283, 346, 409,
    472, 535, 598, 661, 724, 787, 850, 913, 976, 1039, 1102, 1165, 1228, 1291, 1354, 1417, 1480,
    1543, 1606, 1669, 1732, 1795, 1858, 1921, 1984, 2048, 1985, 1922, 1859, 1796, 1733, 1670, 1607,
    1544, 1481, 1418, 1355, 1292, 1229, 1166, 1103, 1040, 977, 914, 851, 788, 725, 662, 599, 536,
    473, 410, 347, 284, 221, 158, 95, 32, 33, 96, 159, 222, 285, 348, 411, 474, 537, 600, 663, 726,
    789, 852, 915, 978, 1041, 1104, 1167, 1230, 1293, 1356, 1419, 1482, 1545, 1608, 1671, 1734,
    1797, 1860, 1923, 1986, 2049, 2112, 2176, 2113, 2050, 1987, 1924, 1861, 1798, 1735, 1672, 1609,
    1546, 1483, 1420, 1357, 1294, 1231, 1168, 1105, 1042, 979, 916, 853, 790, 727, 664, 601, 538,
    475, 412, 349, 286, 223, 160, 97, 34, 35, 98, 161, 224, 287, 350, 413, 476, 539, 602, 665, 728,
    791, 854, 917, 980, 1043, 1106, 1169, 1232, 1295, 1358, 1421, 1484, 1547, 1610, 1673, 1736,
    1799, 1862, 1925, 1988, 2051, 2114, 2177, 2240, 2304, 2241, 2178, 2115, 2052, 1989, 1926, 1863,
    1800, 1737, 1674, 1611, 1548, 1485, 1422, 1359, 1296, 1233, 1170, 1107, 1044, 981, 918, 855,
    792, 729, 666, 603, 540, 477, 414, 351, 288, 225, 162, 99, 36, 37, 100, 163, 226, 289, 352,
    415, 478, 541, 604, 667, 730, 793, 856, 919, 982, 1045, 1108, 1171, 1234, 1297, 1360, 1423,
    1486, 1549, 1612, 1675, 1738, 1801, 1864, 1927, 1990, 2053, 2116, 2179, 2242, 2305, 2368, 2432,
    2369, 2306, 2243, 2180, 2117, 2054, 1991, 1928, 1865, 1802, 1739, 1676, 1613, 1550, 1487, 1424,
    1361, 1298, 1235, 1172, 1109, 1046, 983, 920, 857, 794, 731, 668, 605, 542, 479, 416, 353, 290,
    227, 164, 101, 38, 39, 102, 165, 228, 291, 354, 417, 480, 543, 606, 669, 732, 795, 858, 921,
    984, 1047, 1110, 1173, 1236, 1299, 1362, 1425, 1488, 1551, 1614, 1677, 1740, 1803, 1866, 1929,
    1992, 2055, 2118, 2181, 2244, 2307, 2370, 2433, 2496, 2560, 2497, 2434, 2371, 2308, 2245, 2182,
    2119, 2056, 1993, 1930, 1867, 1804, 1741, 1678, 1615, 1552, 1489, 1426, 1363, 1300, 1237, 1174,
    1111, 1048, 985, 922, 859, 796, 733, 670, 607, 544, 481, 418, 355, 292, 229, 166, 103, 40, 41,
    104, 167, 230, 293, 356, 419, 482, 545, 608, 671, 734, 797, 860, 923, 986, 1049, 1112, 1175,
    1238, 1301, 1364, 1427, 1490, 1553, 1616, 1679, 1742, 1805, 1868, 1931, 1994, 2057, 2120, 2183,
    2246, 2309, 2372, 2435, 2498, 2561, 2624, 2688, 2625, 2562, 2499, 2436, 2373, 2310, 2247, 2184,
    2121, 2058, 1995, 1932, 1869, 1806, 1743, 1680, 1617, 1554, 1491, 1428, 1365, 1302, 1239, 1176,
    1113, 1050, 987, 924, 861, 798, 735, 672, 609, 546, 483, 420, 357, 294, 231, 168, 105, 42, 43,
    106, 169, 232, 295, 358, 421, 484, 547, 610, 673, 736, 799, 862, 925, 988, 1051, 1114, 1177,
    1240, 1303, 1366, 1429, 1492, 1555, 1618, 1681, 1744, 1807, 1870, 1933, 1996, 2059, 2122, 2185,
    2248, 2311, 2374, 2437, 2500, 2563, 2626, 2689, 2752, 2816, 2753, 2690, 2627, 2564, 2501, 2438,
    2375, 2312, 2249, 2186, 2123, 2060, 1997, 1934, 1871, 1808, 1745, 1682, 1619, 1556, 1493, 1430,
    1367, 1304, 1241, 1178, 1115, 1052, 989, 926, 863, 800, 737, 674, 611, 548, 485, 422, 359, 296,
    233, 170, 107, 44, 45, 108, 171, 234, 297, 360, 423, 486, 549, 612, 675, 738, 801, 864, 927,
    990, 1053, 1116, 1179, 1242, 1305, 1368, 1431, 1494, 1557, 1620, 1683, 1746, 1809, 1872, 1935,
    1998, 2061, 2124, 2187, 2250, 2313, 2376, 2439, 2502, 2565, 2628, 2691, 2754, 2817, 2880, 2944,
    2881, 2818, 2755, 2692, 2629, 2566, 2503, 2440, 2377, 2314, 2251, 2188, 2125, 2062, 1999, 1936,
    1873, 1810, 1747, 1684, 1621, 1558, 1495, 1432, 1369, 1306, 1243, 1180, 1117, 1054, 991, 928,
    865, 802, 739, 676, 613, 550, 487, 424, 361, 298, 235, 172, 109, 46, 47, 110, 173, 236, 299,
    362, 425, 488, 551, 614, 677, 740, 803, 866, 929, 992, 1055, 1118, 1181, 1244, 1307, 1370,
    1433, 1496, 1559, 1622, 1685, 1748, 1811, 1874, 1937, 2000, 2063, 2126, 2189, 2252, 2315, 2378,
    2441, 2504, 2567, 2630, 2693, 2756, 2819, 2882, 2945, 3008, 3072, 3009, 2946, 2883, 2820, 2757,
    2694, 2631, 2568, 2505, 2442, 2379, 2316, 2253, 2190, 2127, 2064, 2001, 1938, 1875, 1812, 1749,
    1686, 1623, 1560, 1497, 1434, 1371, 1308, 1245, 1182, 1119, 1056, 993, 930, 867, 804, 741, 678,
    615, 552, 489, 426, 363, 300, 237, 174, 111, 48, 49, 112, 175, 238, 301, 364, 427, 490, 553,
    616, 679, 742, 805, 868, 931, 994, 1057, 1120, 1183, 1246, 1309, 1372, 1435, 1498, 1561, 1624,
    1687, 1750, 1813, 1876, 1939, 2002, 2065, 2128, 2191, 2254, 2317, 2380, 2443, 2506, 2569, 2632,
    2695, 2758, 2821, 2884, 2947, 3010, 3073, 3136, 3200, 3137, 3074, 3011, 2948, 2885, 2822, 2759,
    2696, 2633, 2570, 2507, 2444, 2381, 2318, 2255, 2192, 2129, 2066, 2003, 1940, 1877, 1814, 1751,
    1688, 1625, 1562, 1499, 1436, 1373, 1310, 1247, 1184, 1121, 1058, 995, 932, 869, 806, 743, 680,
    617, 554, 491, 428, 365, 302, 239, 176, 113, 50, 51, 114, 177, 240, 303, 366, 429, 492, 555,
    618, 681, 744, 807, 870, 933, 996, 1059, 1122, 1185, 1248, 1311, 1374, 1437, 1500, 1563, 1626,
    1689, 1752, 1815, 1878, 1941, 2004, 2067, 2130, 2193, 2256, 2319, 2382, 2445, 2508, 2571, 2634,
    2697, 2760, 2823, 2886, 2949, 3012, 3075, 3138, 3201, 3264, 3328, 3265, 3202, 3139, 3076, 3013,
    2950, 2887, 2824, 2761, 2698, 2635, 2572, 2509, 2446, 2383, 2320, 2257, 2194, 2131, 2068, 2005,
    1942, 1879, 1816, 1753, 1690, 1627, 1564, 1501, 1438, 1375, 1312, 1249, 1186, 1123, 1060, 997,
    934, 871, 808, 745, 682, 619, 556, 493, 430, 367, 304, 241, 178, 115, 52, 53, 116, 179, 242,
    305, 368, 431, 494, 557, 620, 683, 746, 809, 872, 935, 998, 1061, 1124, 1187, 1250, 1313, 1376,
    1439, 1502, 1565, 1628, 1691, 1754, 1817, 1880, 1943, 2006, 2069, 2132, 2195, 2258, 2321, 2384,
    2447, 2510, 2573, 2636, 2699, 2762, 2825, 2888, 2951, 3014, 3077, 3140, 3203, 3266, 3329, 3392,
    3456, 3393, 3330, 3267, 3204, 3141, 3078, 3015, 2952, 2889, 2826, 2763, 2700, 2637, 2574, 2511,
    2448, 2385, 2322, 2259, 2196, 2133, 2070, 2007, 1944, 1881, 1818, 1755, 1692, 1629, 1566, 1503,
    1440, 1377, 1314, 1251, 1188, 1125, 1062, 999, 936, 873, 810, 747, 684, 621, 558, 495, 432,
    369, 306, 243, 180, 117, 54, 55, 118, 181, 244, 307, 370, 433, 496, 559, 622, 685, 748, 811,
    874, 937, 1000, 1063, 1126, 1189, 1252, 1315, 1378, 1441, 1504, 1567, 1630, 1693, 1756, 1819,
    1882, 1945, 2008, 2071, 2134, 2197, 2260, 2323, 2386, 2449, 2512, 2575, 2638, 2701, 2764, 2827,
    2890, 2953, 3016, 3079, 3142, 3205, 3268, 3331, 3394, 3457, 3520, 3584, 3521, 3458, 3395, 3332,
    3269, 3206, 3143, 3080, 3017, 2954, 2891, 2828, 2765, 2702, 2639, 2576, 2513, 2450, 2387, 2324,
    2261, 2198, 2135, 2072, 2009, 1946, 1883, 1820, 1757, 1694, 1631, 1568, 1505, 1442, 1379, 1316,
    1253, 1190, 1127, 1064, 1001, 938, 875, 812, 749, 686, 623, 560, 497, 434, 371, 308, 245, 182,
    119, 56, 57, 120, 183, 246, 309, 372, 435, 498, 561, 624, 687, 750, 813, 876, 939, 1002, 1065,
    1128, 1191, 1254, 1317, 1380, 1443, 1506, 1569, 1632, 1695, 1758, 1821, 1884, 1947, 2010, 2073,
    2136, 2199, 2262, 2325, 2388, 2451, 2514, 2577, 2640, 2703, 2766, 2829, 2892, 2955, 3018, 3081,
    3144, 3207, 3270, 3333, 3396, 3459, 3522, 3585, 3648, 3712, 3649, 3586, 3523, 3460, 3397, 3334,
    3271, 3208, 3145, 3082, 3019, 2956, 2893, 2830, 2767, 2704, 2641, 2578, 2515, 2452, 2389, 2326,
    2263, 2200, 2137, 2074, 2011, 1948, 1885, 1822, 1759, 1696, 1633, 1570, 1507, 1444, 1381, 1318,
    1255, 1192, 1129, 1066, 1003, 940, 877, 814, 751, 688, 625, 562, 499, 436, 373, 310, 247, 184,
    121, 58, 59, 122, 185, 248, 311, 374, 437, 500, 563, 626, 689, 752, 815, 878, 941, 1004, 1067,
    1130, 1193, 1256, 1319, 1382, 1445, 1508, 1571, 1634, 1697, 1760, 1823, 1886, 1949, 2012, 2075,
    2138, 2201, 2264, 2327, 2390, 2453, 2516, 2579, 2642, 2705, 2768, 2831, 2894, 2957, 3020, 3083,
    3146, 3209, 3272, 3335, 3398, 3461, 3524, 3587, 3650, 3713, 3776, 3840, 3777, 3714, 3651, 3588,
    3525, 3462, 3399, 3336, 3273, 3210, 3147, 3084, 3021, 2958, 2895, 2832, 2769, 2706, 2643, 2580,
    2517, 2454, 2391, 2328, 2265, 2202, 2139, 2076, 2013, 1950, 1887, 1824, 1761, 1698, 1635, 1572,
    1509, 1446, 1383, 1320, 1257, 1194, 1131, 1068, 1005, 942, 879, 816, 753, 690, 627, 564, 501,
    438, 375, 312, 249, 186, 123, 60, 61, 124, 187, 250, 313, 376, 439, 502, 565, 628, 691, 754,
    817, 880, 943, 1006, 1069, 1132, 1195, 1258, 1321, 1384, 1447, 1510, 1573, 1636, 1699, 1762,
    1825, 1888, 1951, 2014, 2077, 2140, 2203, 2266, 2329, 2392, 2455, 2518, 2581, 2644, 2707, 2770,
    2833, 2896, 2959, 3022, 3085, 3148, 3211, 3274, 3337, 3400, 3463, 3526, 3589, 3652, 3715, 3778,
    3841, 3904, 3968, 3905, 3842, 3779, 3716, 3653, 3590, 3527, 3464, 3401, 3338, 3275, 3212, 3149,
    3086, 3023, 2960, 2897, 2834, 2771, 2708, 2645, 2582, 2519, 2456, 2393, 2330, 2267, 2204, 2141,
    2078, 2015, 1952, 1889, 1826, 1763, 1700, 1637, 1574, 1511, 1448, 1385, 1322, 1259, 1196, 1133,
    1070, 1007, 944, 881, 818, 755, 692, 629, 566, 503, 440, 377, 314, 251, 188, 125, 62, 63, 126,
    189, 252, 315, 378, 441, 504, 567, 630, 693, 756, 819, 882, 945, 1008, 1071, 1134, 1197, 1260,
    1323, 1386, 1449, 1512, 1575, 1638, 1701, 1764, 1827, 1890, 1953, 2016, 2079, 2142, 2205, 2268,
    2331, 2394, 2457, 2520, 2583, 2646, 2709, 2772, 2835, 2898, 2961, 3024, 3087, 3150, 3213, 3276,
    3339, 3402, 3465, 3528, 3591, 3654, 3717, 3780, 3843, 3906, 3969, 4032, 4033, 3970, 3907, 3844,
    3781, 3718, 3655, 3592, 3529, 3466, 3403, 3340, 3277, 3214, 3151, 3088, 3025, 2962, 2899, 2836,
    2773, 2710, 2647, 2584, 2521, 2458, 2395, 2332, 2269, 2206, 2143, 2080, 2017, 1954, 1891, 1828,
    1765, 1702, 1639, 1576, 1513, 1450, 1387, 1324, 1261, 1198, 1135, 1072, 1009, 946, 883, 820,
    757, 694, 631, 568, 505, 442, 379, 316, 253, 190, 127, 191, 254, 317, 380, 443, 506, 569, 632,
    695, 758, 821, 884, 947, 1010, 1073, 1136, 1199, 1262, 1325, 1388, 1451, 1514, 1577, 1640,
    1703, 1766, 1829, 1892, 1955, 2018, 2081, 2144, 2207, 2270, 2333, 2396, 2459, 2522, 2585, 2648,
    2711, 2774, 2837, 2900, 2963, 3026, 3089, 3152, 3215, 3278, 3341, 3404, 3467, 3530, 3593, 3656,
    3719, 3782, 3845, 3908, 3971, 4034, 4035, 3972, 3909, 3846, 3783, 3720, 3657, 3594, 3531, 3468,
    3405, 3342, 3279, 3216, 3153, 3090, 3027, 2964, 2901, 2838, 2775, 2712, 2649, 2586, 2523, 2460,
    2397, 2334, 2271, 2208, 2145, 2082, 2019, 1956, 1893, 1830, 1767, 1704, 1641, 1578, 1515, 1452,
    1389, 1326, 1263, 1200, 1137, 1074, 1011, 948, 885, 822, 759, 696, 633, 570, 507, 444, 381,
    318, 255, 319, 382, 445, 508, 571, 634, 697, 760, 823, 886, 949, 1012, 1075, 1138, 1201, 1264,
    1327, 1390, 1453, 1516, 1579, 1642, 1705, 1768, 1831, 1894, 1957, 2020, 2083, 2146, 2209, 2272,
    2335, 2398, 2461, 2524, 2587, 2650, 2713, 2776, 2839, 2902, 2965, 3028, 3091, 3154, 3217, 3280,
    3343, 3406, 3469, 3532, 3595, 3658, 3721, 3784, 3847, 3910, 3973, 4036, 4037, 3974, 3911, 3848,
    3785, 3722, 3659, 3596, 3533, 3470, 3407, 3344, 3281, 3218, 3155, 3092, 3029, 2966, 2903, 2840,
    2777, 2714, 2651, 2588, 2525, 2462, 2399, 2336, 2273, 2210, 2147, 2084, 2021, 1958, 1895, 1832,
    1769, 1706, 1643, 1580, 1517, 1454, 1391, 1328, 1265, 1202, 1139, 1076, 1013, 950, 887, 824,
    761, 698, 635, 572, 509, 446, 383, 447, 510, 573, 636, 699, 762, 825, 888, 951, 1014, 1077,
    1140, 1203, 1266, 1329, 1392, 1455, 1518, 1581, 1644, 1707, 1770, 1833, 1896, 1959, 2022, 2085,
    2148, 2211, 2274, 2337, 2400, 2463, 2526, 2589, 2652, 2715, 2778, 2841, 2904, 2967, 3030, 3093,
    3156, 3219, 3282, 3345, 3408, 3471, 3534, 3597, 3660, 3723, 3786, 3849, 3912, 3975, 4038, 4039,
    3976, 3913, 3850, 3787, 3724, 3661, 3598, 3535, 3472, 3409, 3346, 3283, 3220, 3157, 3094, 3031,
    2968, 2905, 2842, 2779, 2716, 2653, 2590, 2527, 2464, 2401, 2338, 2275, 2212, 2149, 2086, 2023,
    1960, 1897, 1834, 1771, 1708, 1645, 1582, 1519, 1456, 1393, 1330, 1267, 1204, 1141, 1078, 1015,
    952, 889, 826, 763, 700, 637, 574, 511, 575, 638, 701, 764, 827, 890, 953, 1016, 1079, 1142,
    1205, 1268, 1331, 1394, 1457, 1520, 1583, 1646, 1709, 1772, 1835, 1898, 1961, 2024, 2087, 2150,
    2213, 2276, 2339, 2402, 2465, 2528, 2591, 2654, 2717, 2780, 2843, 2906, 2969, 3032, 3095, 3158,
    3221, 3284, 3347, 3410, 3473, 3536, 3599, 3662, 3725, 3788, 3851, 3914, 3977, 4040, 4041, 3978,
    3915, 3852, 3789, 3726, 3663, 3600, 3537, 3474, 3411, 3348, 3285, 3222, 3159, 3096, 3033, 2970,
    2907, 2844, 2781, 2718, 2655, 2592, 2529, 2466, 2403, 2340, 2277, 2214, 2151, 2088, 2025, 1962,
    1899, 1836, 1773, 1710, 1647, 1584, 1521, 1458, 1395, 1332, 1269, 1206, 1143, 1080, 1017, 954,
    891, 828, 765, 702, 639, 703, 766, 829, 892, 955, 1018, 1081, 1144, 1207, 1270, 1333, 1396,
    1459, 1522, 1585, 1648, 1711, 1774, 1837, 1900, 1963, 2026, 2089, 2152, 2215, 2278, 2341, 2404,
    2467, 2530, 2593, 2656, 2719, 2782, 2845, 2908, 2971, 3034, 3097, 3160, 3223, 3286, 3349, 3412,
    3475, 3538, 3601, 3664, 3727, 3790, 3853, 3916, 3979, 4042, 4043, 3980, 3917, 3854, 3791, 3728,
    3665, 3602, 3539, 3476, 3413, 3350, 3287, 3224, 3161, 3098, 3035, 2972, 2909, 2846, 2783, 2720,
    2657, 2594, 2531, 2468, 2405, 2342, 2279, 2216, 2153, 2090, 2027, 1964, 1901, 1838, 1775, 1712,
    1649, 1586, 1523, 1460, 1397, 1334, 1271, 1208, 1145, 1082, 1019, 956, 893, 830, 767, 831, 894,
    957, 1020, 1083, 1146, 1209, 1272, 1335, 1398, 1461, 1524, 1587, 1650, 1713, 1776, 1839, 1902,
    1965, 2028, 2091, 2154, 2217, 2280, 2343, 2406, 2469, 2532, 2595, 2658, 2721, 2784, 2847, 2910,
    2973, 3036, 3099, 3162, 3225, 3288, 3351, 3414, 3477, 3540, 3603, 3666, 3729, 3792, 3855, 3918,
    3981, 4044, 4045, 3982, 3919, 3856, 3793, 3730, 3667, 3604, 3541, 3478, 3415, 3352, 3289, 3226,
    3163, 3100, 3037, 2974, 2911, 2848, 2785, 2722, 2659, 2596, 2533, 2470, 2407, 2344, 2281, 2218,
    2155, 2092, 2029, 1966, 1903, 1840, 1777, 1714, 1651, 1588, 1525, 1462, 1399, 1336, 1273, 1210,
    1147, 1084, 1021, 958, 895, 959, 1022, 1085, 1148, 1211, 1274, 1337, 1400, 1463, 1526, 1589,
    1652, 1715, 1778, 1841, 1904, 1967, 2030, 2093, 2156, 2219, 2282, 2345, 2408, 2471, 2534, 2597,
    2660, 2723, 2786, 2849, 2912, 2975, 3038, 3101, 3164, 3227, 3290, 3353, 3416, 3479, 3542, 3605,
    3668, 3731, 3794, 3857, 3920, 3983, 4046, 4047, 3984, 3921, 3858, 3795, 3732, 3669, 3606, 3543,
    3480, 3417, 3354, 3291, 3228, 3165, 3102, 3039, 2976, 2913, 2850, 2787, 2724, 2661, 2598, 2535,
    2472, 2409, 2346, 2283, 2220, 2157, 2094, 2031, 1968, 1905, 1842, 1779, 1716, 1653, 1590, 1527,
    1464, 1401, 1338, 1275, 1212, 1149, 1086, 1023, 1087, 1150, 1213, 1276, 1339, 1402, 1465, 1528,
    1591, 1654, 1717, 1780, 1843, 1906, 1969, 2032, 2095, 2158, 2221, 2284, 2347, 2410, 2473, 2536,
    2599, 2662, 2725, 2788, 2851, 2914, 2977, 3040, 3103, 3166, 3229, 3292, 3355, 3418, 3481, 3544,
    3607, 3670, 3733, 3796, 3859, 3922, 3985, 4048, 4049, 3986, 3923, 3860, 3797, 3734, 3671, 3608,
    3545, 3482, 3419, 3356, 3293, 3230, 3167, 3104, 3041, 2978, 2915, 2852, 2789, 2726, 2663, 2600,
    2537, 2474, 2411, 2348, 2285, 2222, 2159, 2096, 2033, 1970, 1907, 1844, 1781, 1718, 1655, 1592,
    1529, 1466, 1403, 1340, 1277, 1214, 1151, 1215, 1278, 1341, 1404, 1467, 1530, 1593, 1656, 1719,
    1782, 1845, 1908, 1971, 2034, 2097, 2160, 2223, 2286, 2349, 2412, 2475, 2538, 2601, 2664, 2727,
    2790, 2853, 2916, 2979, 3042, 3105, 3168, 3231, 3294, 3357, 3420, 3483, 3546, 3609, 3672, 3735,
    3798, 3861, 3924, 3987, 4050, 4051, 3988, 3925, 3862, 3799, 3736, 3673, 3610, 3547, 3484, 3421,
    3358, 3295, 3232, 3169, 3106, 3043, 2980, 2917, 2854, 2791, 2728, 2665, 2602, 2539, 2476, 2413,
    2350, 2287, 2224, 2161, 2098, 2035, 1972, 1909, 1846, 1783, 1720, 1657, 1594, 1531, 1468, 1405,
    1342, 1279, 1343, 1406, 1469, 1532, 1595, 1658, 1721, 1784, 1847, 1910, 1973, 2036, 2099, 2162,
    2225, 2288, 2351, 2414, 2477, 2540, 2603, 2666, 2729, 2792, 2855, 2918, 2981, 3044, 3107, 3170,
    3233, 3296, 3359, 3422, 3485, 3548, 3611, 3674, 3737, 3800, 3863, 3926, 3989, 4052, 4053, 3990,
    3927, 3864, 3801, 3738, 3675, 3612, 3549, 3486, 3423, 3360, 3297, 3234, 3171, 3108, 3045, 2982,
    2919, 2856, 2793, 2730, 2667, 2604, 2541, 2478, 2415, 2352, 2289, 2226, 2163, 2100, 2037, 1974,
    1911, 1848, 1785, 1722, 1659, 1596, 1533, 1470, 1407, 1471, 1534, 1597, 1660, 1723, 1786, 1849,
    1912, 1975, 2038, 2101, 2164, 2227, 2290, 2353, 2416, 2479, 2542, 2605, 2668, 2731, 2794, 2857,
    2920, 2983, 3046, 3109, 3172, 3235, 3298, 3361, 3424, 3487, 3550, 3613, 3676, 3739, 3802, 3865,
    3928, 3991, 4054, 4055, 3992, 3929, 3866, 3803, 3740, 3677, 3614, 3551, 3488, 3425, 3362, 3299,
    3236, 3173, 3110, 3047, 2984, 2921, 2858, 2795, 2732, 2669, 2606, 2543, 2480, 2417, 2354, 2291,
    2228, 2165, 2102, 2039, 1976, 1913, 1850, 1787, 1724, 1661, 1598, 1535, 1599, 1662, 1725, 1788,
    1851, 1914, 1977, 2040, 2103, 2166, 2229, 2292, 2355, 2418, 2481, 2544, 2607, 2670, 2733, 2796,
    2859, 2922, 2985, 3048, 3111, 3174, 3237, 3300, 3363, 3426, 3489, 3552, 3615, 3678, 3741, 3804,
    3867, 3930, 3993, 4056, 4057, 3994, 3931, 3868, 3805, 3742, 3679, 3616, 3553, 3490, 3427, 3364,
    3301, 3238, 3175, 3112, 3049, 2986, 2923, 2860, 2797, 2734, 2671, 2608, 2545, 2482, 2419, 2356,
    2293, 2230, 2167, 2104, 2041, 1978, 1915, 1852, 1789, 1726, 1663, 1727, 1790, 1853, 1916, 1979,
    2042, 2105, 2168, 2231, 2294, 2357, 2420, 2483, 2546, 2609, 2672, 2735, 2798, 2861, 2924, 2987,
    3050, 3113, 3176, 3239, 3302, 3365, 3428, 3491, 3554, 3617, 3680, 3743, 3806, 3869, 3932, 3995,
    4058, 4059, 3996, 3933, 3870, 3807, 3744, 3681, 3618, 3555, 3492, 3429, 3366, 3303, 3240, 3177,
    3114, 3051, 2988, 2925, 2862, 2799, 2736, 2673, 2610, 2547, 2484, 2421, 2358, 2295, 2232, 2169,
    2106, 2043, 1980, 1917, 1854, 1791, 1855, 1918, 1981, 2044, 2107, 2170, 2233, 2296, 2359, 2422,
    2485, 2548, 2611, 2674, 2737, 2800, 2863, 2926, 2989, 3052, 3115, 3178, 3241, 3304, 3367, 3430,
    3493, 3556, 3619, 3682, 3745, 3808, 3871, 3934, 3997, 4060, 4061, 3998, 3935, 3872, 3809, 3746,
    3683, 3620, 3557, 3494, 3431, 3368, 3305, 3242, 3179, 3116, 3053, 2990, 2927, 2864, 2801, 2738,
    2675, 2612, 2549, 2486, 2423, 2360, 2297, 2234, 2171, 2108, 2045, 1982, 1919, 1983, 2046, 2109,
    2172, 2235, 2298, 2361, 2424, 2487, 2550, 2613, 2676, 2739, 2802, 2865, 2928, 2991, 3054, 3117,
    3180, 3243, 3306, 3369, 3432, 3495, 3558, 3621, 3684, 3747, 3810, 3873, 3936, 3999, 4062, 4063,
    4000, 3937, 3874, 3811, 3748, 3685, 3622, 3559, 3496, 3433, 3370, 3307, 3244, 3181, 3118, 3055,
    2992, 2929, 2866, 2803, 2740, 2677, 2614, 2551, 2488, 2425, 2362, 2299, 2236, 2173, 2110, 2047,
    2111, 2174, 2237, 2300, 2363, 2426, 2489, 2552, 2615, 2678, 2741, 2804, 2867, 2930, 2993, 3056,
    3119, 3182, 3245, 3308, 3371, 3434, 3497, 3560, 3623, 3686, 3749, 3812, 3875, 3938, 4001, 4064,
    4065, 4002, 3939, 3876, 3813, 3750, 3687, 3624, 3561, 3498, 3435, 3372, 3309, 3246, 3183, 3120,
    3057, 2994, 2931, 2868, 2805, 2742, 2679, 2616, 2553, 2490, 2427, 2364, 2301, 2238, 2175, 2239,
    2302, 2365, 2428, 2491, 2554, 2617, 2680, 2743, 2806, 2869, 2932, 2995, 3058, 3121, 3184, 3247,
    3310, 3373, 3436, 3499, 3562, 3625, 3688, 3751, 3814, 3877, 3940, 4003, 4066, 4067, 4004, 3941,
    3878, 3815, 3752, 3689, 3626, 3563, 3500, 3437, 3374, 3311, 3248, 3185, 3122, 3059, 2996, 2933,
    2870, 2807, 2744, 2681, 2618, 2555, 2492, 2429, 2366, 2303, 2367, 2430, 2493, 2556, 2619, 2682,
    2745, 2808, 2871, 2934, 2997, 3060, 3123, 3186, 3249, 3312, 3375, 3438, 3501, 3564, 3627, 3690,
    3753, 3816, 3879, 3942, 4005, 4068, 4069, 4006, 3943, 3880, 3817, 3754, 3691, 3628, 3565, 3502,
    3439, 3376, 3313, 3250, 3187, 3124, 3061, 2998, 2935, 2872, 2809, 2746, 2683, 2620, 2557, 2494,
    2431, 2495, 2558, 2621, 2684, 2747, 2810, 2873, 2936, 2999, 3062, 3125, 3188, 3251, 3314, 3377,
    3440, 3503, 3566, 3629, 3692, 3755, 3818, 3881, 3944, 4007, 4070, 4071, 4008, 3945, 3882, 3819,
    3756, 3693, 3630, 3567, 3504, 3441, 3378, 3315, 3252, 3189, 3126, 3063, 3000, 2937, 2874, 2811,
    2748, 2685, 2622, 2559, 2623, 2686, 2749, 2812, 2875, 2938, 3001, 3064, 3127, 3190, 3253, 3316,
    3379, 3442, 3505, 3568, 3631, 3694, 3757, 3820, 3883, 3946, 4009, 4072, 4073, 4010, 3947, 3884,
    3821, 3758, 3695, 3632, 3569, 3506, 3443, 3380, 3317, 3254, 3191, 3128, 3065, 3002, 2939, 2876,
    2813, 2750, 2687, 2751, 2814, 2877, 2940, 3003, 3066, 3129, 3192, 3255, 3318, 3381, 3444, 3507,
    3570, 3633, 3696, 3759, 3822, 3885, 3948, 4011, 4074, 4075, 4012, 3949, 3886, 3823, 3760, 3697,
    3634, 3571, 3508, 3445, 3382, 3319, 3256, 3193, 3130, 3067, 3004, 2941, 2878, 2815, 2879, 2942,
    3005, 3068, 3131, 3194, 3257, 3320, 3383, 3446, 3509, 3572, 3635, 3698, 3761, 3824, 3887, 3950,
    4013, 4076, 4077, 4014, 3951, 3888, 3825, 3762, 3699, 3636, 3573, 3510, 3447, 3384, 3321, 3258,
    3195, 3132, 3069, 3006, 2943, 3007, 3070, 3133, 3196, 3259, 3322, 3385, 3448, 3511, 3574, 3637,
    3700, 3763, 3826, 3889, 3952, 4015, 4078, 4079, 4016, 3953, 3890, 3827, 3764, 3701, 3638, 3575,
    3512, 3449, 3386, 3323, 3260, 3197, 3134, 3071, 3135, 3198, 3261, 3324, 3387, 3450, 3513, 3576,
    3639, 3702, 3765, 3828, 3891, 3954, 4017, 4080, 4081, 4018, 3955, 3892, 3829, 3766, 3703, 3640,
    3577, 3514, 3451, 3388, 3325, 3262, 3199, 3263, 3326, 3389, 3452, 3515, 3578, 3641, 3704, 3767,
    3830, 3893, 3956, 4019, 4082, 4083, 4020, 3957, 3894, 3831, 3768, 3705, 3642, 3579, 3516, 3453,
    3390, 3327, 3391, 3454, 3517, 3580, 3643, 3706, 3769, 3832, 3895, 3958, 4021, 4084, 4085, 4022,
    3959, 3896, 3833, 3770, 3707, 3644, 3581, 3518, 3455, 3519, 3582, 3645, 3708, 3771, 3834, 3897,
    3960, 4023, 4086, 4087, 4024, 3961, 3898, 3835, 3772, 3709, 3646, 3583, 3647, 3710, 3773, 3836,
    3899, 3962, 4025, 4088, 4089, 4026, 3963, 3900, 3837, 3774, 3711, 3775, 3838, 3901, 3964, 4027,
    4090, 4091, 4028, 3965, 3902, 3839, 3903, 3966, 4029, 4092, 4093, 4030, 3967, 4031, 4094, 4095,
];

#[inline]
pub(crate) fn coeff_order_64x64() -> &'static [u16] {
    &K_COEFF_ORDER_64X64
}

#[cfg(test)]
mod tests {
    use super::{K_COEFF_ORDER_64X32, K_COEFF_ORDER_64X64, block_context, coeff_order_64x64};

    #[test]
    fn dct64_coefficient_order_is_static_permutation() {
        assert!(std::ptr::eq(
            coeff_order_64x64().as_ptr(),
            K_COEFF_ORDER_64X64.as_ptr()
        ));
        let mut sorted = K_COEFF_ORDER_64X64;
        sorted.sort_unstable();
        for (index, value) in sorted.into_iter().enumerate() {
            assert_eq!(value as usize, index);
        }
    }

    /// Reference implementation of the DCT64X32/DCT32X64 zig-zag order. This
    /// used to run as a `const fn` at compile time; the shipped table is now a
    /// literal, so keep the recurrence here to prove the literal still matches.
    fn reference_coeff_order_64x32() -> [u16; 2048] {
        let mut out = [0u16; 2048];
        let mut cur = 32usize;
        for diagonal in 0..64usize {
            for j in 0..=diagonal {
                let (mut x, mut y) = (j, diagonal - j);
                if diagonal & 1 != 0 {
                    std::mem::swap(&mut x, &mut y);
                }
                if y & 1 == 0 {
                    y >>= 1;
                    let value = if x < 8 && y < 4 {
                        y * 8 + x
                    } else {
                        cur += 1;
                        cur - 1
                    };
                    out[value] = (y * 64 + x) as u16;
                }
            }
        }
        for ip in (1..64usize).rev() {
            let diagonal = ip - 1;
            for j in 0..=diagonal {
                let (mut x, mut y) = (63 - (diagonal - j), 63 - j);
                if diagonal & 1 != 0 {
                    std::mem::swap(&mut x, &mut y);
                }
                if y & 1 == 0 {
                    y >>= 1;
                    out[cur] = (y * 64 + x) as u16;
                    cur += 1;
                }
            }
        }
        out
    }

    #[test]
    fn dct64x32_literal_table_matches_the_generating_recurrence() {
        let want = reference_coeff_order_64x32();
        for (i, (&got, &want)) in K_COEFF_ORDER_64X32.iter().zip(want.iter()).enumerate() {
            assert_eq!(got, want, "K_COEFF_ORDER_64X32[{i}]");
        }
    }

    #[test]
    fn dct64x32_coefficient_order_is_static_permutation() {
        let mut sorted = K_COEFF_ORDER_64X32;
        sorted.sort_unstable();
        for (index, value) in sorted.into_iter().enumerate() {
            assert_eq!(value as usize, index);
        }
    }

    #[test]
    fn dct64_uses_large_shape_entropy_contexts() {
        const DCT64X64_CODE: u8 = 18;
        assert_eq!(block_context(0, DCT64X64_CODE), 3); // X
        assert_eq!(block_context(1, DCT64X64_CODE), 1); // Y
        assert_eq!(block_context(2, DCT64X64_CODE), 3); // B
        for code in [19, 20] {
            assert_eq!(block_context(0, code), 3);
            assert_eq!(block_context(1, code), 1);
            assert_eq!(block_context(2, code), 3);
        }
    }
}