Move zig-zagging from quantization into the fDCT.
[theora.git] / lib / tokenize.c
1 /********************************************************************
2  *                                                                  *
3  * THIS FILE IS PART OF THE OggTheora SOFTWARE CODEC SOURCE CODE.   *
4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
7  *                                                                  *
8  * THE Theora SOURCE CODE IS COPYRIGHT (C) 2002-2009                *
9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
10  *                                                                  *
11  ********************************************************************
12
13   function:
14   last mod: $Id$
15
16  ********************************************************************/
17 #include <stdlib.h>
18 #include <string.h>
19 #include "encint.h"
20
21
22
23 static unsigned char OC_DCT_EOB_TOKEN[31]={
24   0,1,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5
25 };
26
27 static int oc_make_eob_token(int _run_count){
28   return _run_count<32?OC_DCT_EOB_TOKEN[_run_count-1]:OC_DCT_REPEAT_RUN3_TOKEN;
29 }
30
31 static unsigned char OC_DCT_EOB_EB[31]={
32   0,0,0,0,1,2,3,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
33 };
34
35 static int oc_make_eob_token_full(int _run_count,int *_eb){
36   if(_run_count<32){
37     *_eb=OC_DCT_EOB_EB[_run_count-1];
38     return OC_DCT_EOB_TOKEN[_run_count-1];
39   }
40   else{
41     *_eb=_run_count;
42     return OC_DCT_REPEAT_RUN3_TOKEN;
43   }
44 }
45
46 /*Returns the number of blocks ended by an EOB token.*/
47 static int oc_decode_eob_token(int _token,int _eb){
48   return (0x20820C41U>>_token*5&0x1F)+_eb;
49 }
50
51 /*Some tables for fast construction of value tokens.*/
52
53 static const unsigned char OC_DCT_VALUE_TOKEN[1161]={
54   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
55   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
56   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
57   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
58   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
59   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
60   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
61   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
62   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
63   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
64   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
65   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
66   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
67   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
68   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
69   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
70   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
71   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
72   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
73   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
74   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
75   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
76   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
77   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
78   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
79   22,22,22,22,22,22,22,22,22,22,22,22,21,21,21,21,21,21,21,21,
80   21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,
81   21,21,21,21,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,
82   19,19,19,19,19,19,19,19,18,18,18,18,17,17,16,15,14,13,12,10,
83    7,
84    9,11,13,14,15,16,17,17,18,18,18,18,19,19,19,19,19,19,19,19,
85   20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,21,21,21,21,
86   21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,
87   21,21,21,21,21,21,21,21,22,22,22,22,22,22,22,22,22,22,22,22,
88   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
89   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
90   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
91   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
92   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
93   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
94   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
95   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
96   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
97   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
98   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
99   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
100   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
101   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
102   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
103   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
104   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
105   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
106   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
107   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
108   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
109   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
110   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
111   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,
112   22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22
113 };
114
115 static const ogg_uint16_t OC_DCT_VALUE_EB[1161]={
116   1023,1022,1021,1020,1019,1018,1017,1016,1015,1014,
117   1013,1012,1011,1010,1009,1008,1007,1006,1005,1004,
118   1003,1002,1001,1000, 999, 998, 997, 996, 995, 994,
119    993, 992, 991, 990, 989, 988, 987, 986, 985, 984,
120    983, 982, 981, 980, 979, 978, 977, 976, 975, 974,
121    973, 972, 971, 970, 969, 968, 967, 966, 965, 964,
122    963, 962, 961, 960, 959, 958, 957, 956, 955, 954,
123    953, 952, 951, 950, 949, 948, 947, 946, 945, 944,
124    943, 942, 941, 940, 939, 938, 937, 936, 935, 934,
125    933, 932, 931, 930, 929, 928, 927, 926, 925, 924,
126    923, 922, 921, 920, 919, 918, 917, 916, 915, 914,
127    913, 912, 911, 910, 909, 908, 907, 906, 905, 904,
128    903, 902, 901, 900, 899, 898, 897, 896, 895, 894,
129    893, 892, 891, 890, 889, 888, 887, 886, 885, 884,
130    883, 882, 881, 880, 879, 878, 877, 876, 875, 874,
131    873, 872, 871, 870, 869, 868, 867, 866, 865, 864,
132    863, 862, 861, 860, 859, 858, 857, 856, 855, 854,
133    853, 852, 851, 850, 849, 848, 847, 846, 845, 844,
134    843, 842, 841, 840, 839, 838, 837, 836, 835, 834,
135    833, 832, 831, 830, 829, 828, 827, 826, 825, 824,
136    823, 822, 821, 820, 819, 818, 817, 816, 815, 814,
137    813, 812, 811, 810, 809, 808, 807, 806, 805, 804,
138    803, 802, 801, 800, 799, 798, 797, 796, 795, 794,
139    793, 792, 791, 790, 789, 788, 787, 786, 785, 784,
140    783, 782, 781, 780, 779, 778, 777, 776, 775, 774,
141    773, 772, 771, 770, 769, 768, 767, 766, 765, 764,
142    763, 762, 761, 760, 759, 758, 757, 756, 755, 754,
143    753, 752, 751, 750, 749, 748, 747, 746, 745, 744,
144    743, 742, 741, 740, 739, 738, 737, 736, 735, 734,
145    733, 732, 731, 730, 729, 728, 727, 726, 725, 724,
146    723, 722, 721, 720, 719, 718, 717, 716, 715, 714,
147    713, 712, 711, 710, 709, 708, 707, 706, 705, 704,
148    703, 702, 701, 700, 699, 698, 697, 696, 695, 694,
149    693, 692, 691, 690, 689, 688, 687, 686, 685, 684,
150    683, 682, 681, 680, 679, 678, 677, 676, 675, 674,
151    673, 672, 671, 670, 669, 668, 667, 666, 665, 664,
152    663, 662, 661, 660, 659, 658, 657, 656, 655, 654,
153    653, 652, 651, 650, 649, 648, 647, 646, 645, 644,
154    643, 642, 641, 640, 639, 638, 637, 636, 635, 634,
155    633, 632, 631, 630, 629, 628, 627, 626, 625, 624,
156    623, 622, 621, 620, 619, 618, 617, 616, 615, 614,
157    613, 612, 611, 610, 609, 608, 607, 606, 605, 604,
158    603, 602, 601, 600, 599, 598, 597, 596, 595, 594,
159    593, 592, 591, 590, 589, 588, 587, 586, 585, 584,
160    583, 582, 581, 580, 579, 578, 577, 576, 575, 574,
161    573, 572, 571, 570, 569, 568, 567, 566, 565, 564,
162    563, 562, 561, 560, 559, 558, 557, 556, 555, 554,
163    553, 552, 551, 550, 549, 548, 547, 546, 545, 544,
164    543, 542, 541, 540, 539, 538, 537, 536, 535, 534,
165    533, 532, 531, 530, 529, 528, 527, 526, 525, 524,
166    523, 522, 521, 520, 519, 518, 517, 516, 515, 514,
167    513, 512,  63,  62,  61,  60,  59,  58,  57,  56,
168     55,  54,  53,  52,  51,  50,  49,  48,  47,  46,
169     45,  44,  43,  42,  41,  40,  39,  38,  37,  36,
170     35,  34,  33,  32,  31,  30,  29,  28,  27,  26,
171     25,  24,  23,  22,  21,  20,  19,  18,  17,  16,
172     15,  14,  13,  12,  11,  10,   9,   8,   7,   6,
173      5,   4,   3,   2,   1,   1,   1,   1,   0,   0,
174      0,
175      0,   0,   0,   0,   0,   0,   0,   1,   0,   1,
176      2,   3,   0,   1,   2,   3,   4,   5,   6,   7,
177      0,   1,   2,   3,   4,   5,   6,   7,   8,   9,
178     10,  11,  12,  13,  14,  15,   0,   1,   2,   3,
179      4,   5,   6,   7,   8,   9,  10,  11,  12,  13,
180     14,  15,  16,  17,  18,  19,  20,  21,  22,  23,
181     24,  25,  26,  27,  28,  29,  30,  31,   0,   1,
182      2,   3,   4,   5,   6,   7,   8,   9,  10,  11,
183     12,  13,  14,  15,  16,  17,  18,  19,  20,  21,
184     22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
185     32,  33,  34,  35,  36,  37,  38,  39,  40,  41,
186     42,  43,  44,  45,  46,  47,  48,  49,  50,  51,
187     52,  53,  54,  55,  56,  57,  58,  59,  60,  61,
188     62,  63,  64,  65,  66,  67,  68,  69,  70,  71,
189     72,  73,  74,  75,  76,  77,  78,  79,  80,  81,
190     82,  83,  84,  85,  86,  87,  88,  89,  90,  91,
191     92,  93,  94,  95,  96,  97,  98,  99, 100, 101,
192    102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
193    112, 113, 114, 115, 116, 117, 118, 119, 120, 121,
194    122, 123, 124, 125, 126, 127, 128, 129, 130, 131,
195    132, 133, 134, 135, 136, 137, 138, 139, 140, 141,
196    142, 143, 144, 145, 146, 147, 148, 149, 150, 151,
197    152, 153, 154, 155, 156, 157, 158, 159, 160, 161,
198    162, 163, 164, 165, 166, 167, 168, 169, 170, 171,
199    172, 173, 174, 175, 176, 177, 178, 179, 180, 181,
200    182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
201    192, 193, 194, 195, 196, 197, 198, 199, 200, 201,
202    202, 203, 204, 205, 206, 207, 208, 209, 210, 211,
203    212, 213, 214, 215, 216, 217, 218, 219, 220, 221,
204    222, 223, 224, 225, 226, 227, 228, 229, 230, 231,
205    232, 233, 234, 235, 236, 237, 238, 239, 240, 241,
206    242, 243, 244, 245, 246, 247, 248, 249, 250, 251,
207    252, 253, 254, 255, 256, 257, 258, 259, 260, 261,
208    262, 263, 264, 265, 266, 267, 268, 269, 270, 271,
209    272, 273, 274, 275, 276, 277, 278, 279, 280, 281,
210    282, 283, 284, 285, 286, 287, 288, 289, 290, 291,
211    292, 293, 294, 295, 296, 297, 298, 299, 300, 301,
212    302, 303, 304, 305, 306, 307, 308, 309, 310, 311,
213    312, 313, 314, 315, 316, 317, 318, 319, 320, 321,
214    322, 323, 324, 325, 326, 327, 328, 329, 330, 331,
215    332, 333, 334, 335, 336, 337, 338, 339, 340, 341,
216    342, 343, 344, 345, 346, 347, 348, 349, 350, 351,
217    352, 353, 354, 355, 356, 357, 358, 359, 360, 361,
218    362, 363, 364, 365, 366, 367, 368, 369, 370, 371,
219    372, 373, 374, 375, 376, 377, 378, 379, 380, 381,
220    382, 383, 384, 385, 386, 387, 388, 389, 390, 391,
221    392, 393, 394, 395, 396, 397, 398, 399, 400, 401,
222    402, 403, 404, 405, 406, 407, 408, 409, 410, 411,
223    412, 413, 414, 415, 416, 417, 418, 419, 420, 421,
224    422, 423, 424, 425, 426, 427, 428, 429, 430, 431,
225    432, 433, 434, 435, 436, 437, 438, 439, 440, 441,
226    442, 443, 444, 445, 446, 447, 448, 449, 450, 451,
227    452, 453, 454, 455, 456, 457, 458, 459, 460, 461,
228    462, 463, 464, 465, 466, 467, 468, 469, 470, 471,
229    472, 473, 474, 475, 476, 477, 478, 479, 480, 481,
230    482, 483, 484, 485, 486, 487, 488, 489, 490, 491,
231    492, 493, 494, 495, 496, 497, 498, 499, 500, 501,
232    502, 503, 504, 505, 506, 507, 508, 509, 510, 511
233 };
234
235 /*The first DCT coefficient that both has a smaller magnitude and gets coded
236    with a different token.*/
237 static const ogg_int16_t OC_DCT_TRELLIS_ALT_VALUE[1161]={
238    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
239    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
240    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
241    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
242    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
243    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
244    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
245    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
246    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
247    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
248    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
249    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
250    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
251    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
252    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
253    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
254    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
255    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
256    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
257    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
258    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
259    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
260    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
261    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
262    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
263    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
264    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
265    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
266    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
267    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
268    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
269    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
270    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
271    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
272    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
273    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
274    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
275    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
276    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
277    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
278    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
279    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
280    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
281    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
282    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
283    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
284    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
285    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
286    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
287    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
288    -68, -68, -68, -68, -68, -68, -68, -68, -68, -68,
289    -68, -68, -36, -36, -36, -36, -36, -36, -36, -36,
290    -36, -36, -36, -36, -36, -36, -36, -36, -36, -36,
291    -36, -36, -36, -36, -36, -36, -36, -36, -36, -36,
292    -36, -36, -36, -36, -20, -20, -20, -20, -20, -20,
293    -20, -20, -20, -20, -20, -20, -20, -20, -20, -20,
294    -12, -12, -12, -12, -12, -12, -12, -12,  -8,  -8,
295     -8,  -8,  -6,  -6,  -5,  -4,  -3,  -2,  -1,   0,
296      0,
297      0,   1,   2,   3,   4,   5,   6,   6,   8,   8,
298      8,   8,  12,  12,  12,  12,  12,  12,  12,  12,
299     20,  20,  20,  20,  20,  20,  20,  20,  20,  20,
300     20,  20,  20,  20,  20,  20,  36,  36,  36,  36,
301     36,  36,  36,  36,  36,  36,  36,  36,  36,  36,
302     36,  36,  36,  36,  36,  36,  36,  36,  36,  36,
303     36,  36,  36,  36,  36,  36,  36,  36,  68,  68,
304     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
305     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
306     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
307     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
308     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
309     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
310     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
311     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
312     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
313     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
314     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
315     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
316     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
317     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
318     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
319     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
320     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
321     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
322     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
323     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
324     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
325     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
326     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
327     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
328     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
329     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
330     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
331     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
332     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
333     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
334     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
335     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
336     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
337     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
338     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
339     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
340     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
341     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
342     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
343     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
344     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
345     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
346     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
347     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
348     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
349     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
350     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
351     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
352     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
353     68,  68,  68,  68,  68,  68,  68,  68,  68,  68,
354     68,  68,  68,  68,  68,  68,  68,  68,  68,  68
355 };
356
357 #define OC_DCT_VALUE_TOKEN_PTR (OC_DCT_VALUE_TOKEN+580)
358 #define OC_DCT_VALUE_EB_PTR (OC_DCT_VALUE_EB+580)
359 #define OC_DCT_TRELLIS_ALT_VALUE_PTR (OC_DCT_TRELLIS_ALT_VALUE+580)
360
361 /*Some tables for fast construction of combo tokens.*/
362
363 static const unsigned char OC_DCT_RUN_CAT1_TOKEN[17]={
364   23,24,25,26,27,28,28,28,28,29,29,29,29,29,29,29,29
365 };
366
367 static const unsigned char OC_DCT_RUN_CAT1_EB[17][2]={
368   {0,1},{0,1},{0, 1},{0, 1},{0, 1},{0, 4},{1, 5},{2, 6},{3,7},
369   {0,8},{1,9},{2,10},{3,11},{4,12},{5,13},{6,14},{7,15}
370 };
371
372 static const unsigned char OC_DCT_RUN_CAT2_EB[3][2][2]={
373   { {0,1},{2,3} },{ {0,2},{4,6} },{ {1,3},{5,7} }
374 };
375
376 /*Token logging to allow a few fragments of efficient rollback.
377   Late SKIP analysis is tied up in the tokenization process, so we need to be
378    able to undo a fragment's tokens on a whim.*/
379
380 static const unsigned char OC_ZZI_HUFF_OFFSET[64]={
381    0,16,16,16,16,16,32,32,
382   32,32,32,32,32,32,32,48,
383   48,48,48,48,48,48,48,48,
384   48,48,48,48,64,64,64,64,
385   64,64,64,64,64,64,64,64,
386   64,64,64,64,64,64,64,64,
387   64,64,64,64,64,64,64,64
388 };
389
390 static int oc_token_bits(oc_enc_ctx *_enc,int _huffi,int _zzi,int _token){
391   return _enc->huff_codes[_huffi+OC_ZZI_HUFF_OFFSET[_zzi]][_token].nbits
392    +OC_DCT_TOKEN_EXTRA_BITS[_token];
393 }
394
395 static void oc_enc_tokenlog_checkpoint(oc_enc_ctx *_enc,
396  oc_token_checkpoint *_cp,int _pli,int _zzi){
397   _cp->pli=_pli;
398   _cp->zzi=_zzi;
399   _cp->eob_run=_enc->eob_run[_pli][_zzi];
400   _cp->ndct_tokens=_enc->ndct_tokens[_pli][_zzi];
401 }
402
403 void oc_enc_tokenlog_rollback(oc_enc_ctx *_enc,
404  const oc_token_checkpoint *_stack,int _n){
405   int i;
406   for(i=_n;i-->0;){
407     int pli;
408     int zzi;
409     pli=_stack[i].pli;
410     zzi=_stack[i].zzi;
411     _enc->eob_run[pli][zzi]=_stack[i].eob_run;
412     _enc->ndct_tokens[pli][zzi]=_stack[i].ndct_tokens;
413   }
414 }
415
416 static void oc_enc_token_log(oc_enc_ctx *_enc,
417  int _pli,int _zzi,int _token,int _eb){
418   ptrdiff_t ti;
419   ti=_enc->ndct_tokens[_pli][_zzi]++;
420   _enc->dct_tokens[_pli][_zzi][ti]=(unsigned char)_token;
421   _enc->extra_bits[_pli][_zzi][ti]=(ogg_uint16_t)_eb;
422 }
423
424 static void oc_enc_eob_log(oc_enc_ctx *_enc,
425  int _pli,int _zzi,int _run_count){
426   int token;
427   int eb;
428   token=oc_make_eob_token_full(_run_count,&eb);
429   oc_enc_token_log(_enc,_pli,_zzi,token,eb);
430 }
431
432
433 void oc_enc_tokenize_start(oc_enc_ctx *_enc){
434   memset(_enc->ndct_tokens,0,sizeof(_enc->ndct_tokens));
435   memset(_enc->eob_run,0,sizeof(_enc->eob_run));
436   memset(_enc->dct_token_offs,0,sizeof(_enc->dct_token_offs));
437   memset(_enc->dc_pred_last,0,sizeof(_enc->dc_pred_last));
438 }
439
440 typedef struct oc_quant_token oc_quant_token;
441
442 /*A single node in the Viterbi trellis.
443   We maintain up to 2 of these per coefficient:
444     - A token to code if the value is zero (EOB, zero run, or combo token).
445     - A token to code if the value is not zero (DCT value token).*/
446 struct oc_quant_token{
447   unsigned char next;
448   signed char   token;
449   ogg_int16_t   eb;
450   ogg_uint32_t  cost;
451   int           bits;
452   int           qc;
453 };
454
455 /*Tokenizes the AC coefficients, possibly adjusting the quantization, and then
456    dequantizes and de-zig-zags the result.
457   The AC coefficients of _idct must be pre-initialized to zero.*/
458 int oc_enc_tokenize_ac(oc_enc_ctx *_enc,int _pli,ptrdiff_t _fragi,
459  ogg_int16_t *_idct,const ogg_int16_t *_qdct,
460  const ogg_uint16_t *_dequant,const ogg_int16_t *_dct,
461  int _zzi,oc_token_checkpoint **_stack,int _lambda,int _acmin){
462   oc_token_checkpoint *stack;
463   ogg_int64_t          zflags;
464   ogg_int64_t          nzflags;
465   ogg_int64_t          best_flags;
466   ogg_uint32_t         d2_accum[64];
467   oc_quant_token       tokens[64][2];
468   ogg_uint16_t        *eob_run;
469   const unsigned char *dct_fzig_zag;
470   ogg_uint32_t         cost;
471   int                  bits;
472   int                  eob;
473   int                  token;
474   int                  eb;
475   int                  next;
476   int                  huffi;
477   int                  zzi;
478   int                  ti;
479   int                  zzj;
480   int                  qc;
481   huffi=_enc->huff_idxs[_enc->state.frame_type][1][_pli+1>>1];
482   eob_run=_enc->eob_run[_pli];
483   memset(tokens[0],0,sizeof(tokens[0]));
484   best_flags=nzflags=0;
485   zflags=1;
486   d2_accum[0]=0;
487   zzj=64;
488   for(zzi=OC_MINI(_zzi,63);zzi>0;zzi--){
489     ogg_uint32_t best_cost;
490     int          best_bits=best_bits;
491     int          best_next=best_next;
492     int          best_token=best_token;
493     int          best_eb=best_eb;
494     int          best_qc=best_qc;
495     ogg_uint32_t d2;
496     int          dq;
497     int          qc_m;
498     int          e;
499     int          c;
500     int          s;
501     int          tj;
502     qc=_qdct[zzi];
503     s=-(qc<0);
504     qc_m=qc+s^s;
505     c=_dct[zzi];
506     /*The hard case: try a zero run.*/
507     if(qc_m<=1){
508       ogg_uint32_t sum_d2;
509       int          nzeros;
510       int          dc_reserve;
511       if(!qc_m){
512         /*Skip runs that are already quantized to zeros.
513           If we considered each zero coefficient in turn, we might
514            theoretically find a better way to partition long zero runs (e.g.,
515            a run of > 17 zeros followed by a 1 might be better coded as a short
516            zero run followed by a combo token, rather than the longer zero
517            token followed by a 1 value token), but zeros are so common that
518            this becomes very computationally expensive (quadratic instead of
519            linear in the number of coefficients), for a marginal gain.*/
520         while(zzi>1&&!_qdct[zzi-1])zzi--;
521         /*The distortion of coefficients originally quantized to zero is
522            treated as zero (since we'll never quantize them to anything else).*/
523         d2=0;
524       }
525       else{
526         d2=c*(ogg_int32_t)c;
527         c=c+s^s;
528       }
529       eob=eob_run[zzi];
530       nzeros=zzj-zzi;
531       zzj&=63;
532       sum_d2=d2+d2_accum[zzj];
533       d2_accum[zzi]=sum_d2;
534       /*We reserve 1 spot for combo run tokens that start in the 1st AC stack
535          to ensure they can be extended to include the DC coefficient if
536          necessary; this greatly simplifies stack-rewriting later on.*/
537       dc_reserve=zzi+62>>6;
538       best_cost=0xFFFFFFFF;
539       for(;;){
540         if(nzflags>>zzj&1){
541           int val;
542           int val_s;
543           int zzk;
544           int tk;
545           next=tokens[zzj][1].next;
546           tk=next&1;
547           zzk=next>>1;
548           /*Try a pure zero run to this point.*/
549           token=OC_DCT_SHORT_ZRL_TOKEN+(nzeros+55>>6);
550           bits=oc_token_bits(_enc,huffi,zzi,token);
551           d2=sum_d2-d2_accum[zzj];
552           cost=d2+_lambda*bits+tokens[zzj][1].cost;
553           if(cost<=best_cost){
554             best_next=(zzj<<1)+1;
555             best_token=token;
556             best_eb=nzeros-1;
557             best_cost=cost;
558             best_bits=bits+tokens[zzj][1].bits;
559             best_qc=0;
560           }
561           if(nzeros<17+dc_reserve){
562             val=_qdct[zzj];
563             val_s=-(val<0);
564             val=val+val_s^val_s;
565             if(val<=2){
566               /*Try a +/- 1 combo token.*/
567               token=OC_DCT_RUN_CAT1_TOKEN[nzeros-1];
568               eb=OC_DCT_RUN_CAT1_EB[nzeros-1][-val_s];
569               e=_dct[zzj]-(_dequant[zzj]+val_s^val_s);
570               d2=e*(ogg_int32_t)e+sum_d2-d2_accum[zzj];
571               bits=oc_token_bits(_enc,huffi,zzi,token);
572               cost=d2+_lambda*bits+tokens[zzk][tk].cost;
573               if(cost<=best_cost){
574                 best_next=next;
575                 best_token=token;
576                 best_eb=eb;
577                 best_cost=cost;
578                 best_bits=bits+tokens[zzk][tk].bits;
579                 best_qc=1+val_s^val_s;
580               }
581             }
582             if(nzeros<3+dc_reserve&&2<=val&&val<=4){
583               int sval;
584               /*Try a +/- 2/3 combo token.*/
585               token=OC_DCT_RUN_CAT2A+(nzeros>>1);
586               bits=oc_token_bits(_enc,huffi,zzi,token);
587               val=2+(val>2);
588               sval=val+val_s^val_s;
589               e=_dct[zzj]-_dequant[zzj]*sval;
590               d2=e*(ogg_int32_t)e+sum_d2-d2_accum[zzj];
591               cost=d2+_lambda*bits+tokens[zzk][tk].cost;
592               if(cost<=best_cost){
593                 best_cost=cost;
594                 best_bits=bits+tokens[zzk][tk].bits;
595                 best_next=next;
596                 best_token=token;
597                 best_eb=OC_DCT_RUN_CAT2_EB[nzeros-1][-val_s][val-2];
598                 best_qc=sval;
599               }
600             }
601           }
602           /*zzj can't be coded as a zero, so stop trying to extend the run.*/
603           if(!(zflags>>zzj&1))break;
604         }
605         /*We could try to consider _all_ potentially non-zero coefficients, but
606            if we already found a bunch of them not worth coding, it's fairly
607            unlikely they would now be worth coding from this position; skipping
608            them saves a lot of work.*/
609         zzj=(tokens[zzj][0].next>>1)-(tokens[zzj][0].qc!=0)&63;
610         if(zzj==0){
611           /*We made it all the way to the end of the block; try an EOB token.*/
612           if(eob<4095){
613             bits=oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob+1))
614              -(eob>0?oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob)):0);
615           }
616           else bits=oc_token_bits(_enc,huffi,zzi,OC_DCT_EOB1_TOKEN);
617           cost=sum_d2+bits*_lambda;
618           /*If the best route so far is still a pure zero run to the end of the
619              block, force coding it as an EOB.
620             Even if it's not optimal for this block, it has a good chance of
621              getting combined with an EOB token from subsequent blocks, saving
622              bits overall.*/
623           if(cost<=best_cost||best_token<=OC_DCT_ZRL_TOKEN&&zzi+best_eb==63){
624             best_next=0;
625             /*This token is just a marker; in reality we may not emit any
626                tokens, but update eob_run[] instead.*/
627             best_token=OC_DCT_EOB1_TOKEN;
628             best_eb=0;
629             best_cost=cost;
630             best_bits=bits;
631             best_qc=0;
632           }
633           break;
634         }
635         nzeros=zzj-zzi;
636       }
637       tokens[zzi][0].next=(unsigned char)best_next;
638       tokens[zzi][0].token=(signed char)best_token;
639       tokens[zzi][0].eb=(ogg_int16_t)best_eb;
640       tokens[zzi][0].cost=best_cost;
641       tokens[zzi][0].bits=best_bits;
642       tokens[zzi][0].qc=best_qc;
643       zflags|=(ogg_int64_t)1<<zzi;
644       if(qc_m){
645         dq=_dequant[zzi];
646         if(zzi<_acmin)_lambda=0;
647         e=dq-c;
648         d2=e*(ogg_int32_t)e;
649         token=OC_ONE_TOKEN-s;
650         bits=oc_token_bits(_enc,huffi,zzi,token);
651         zzj=zzi+1&63;
652         tj=best_flags>>zzj&1;
653         next=(zzj<<1)+tj;
654         tokens[zzi][1].next=(unsigned char)next;
655         tokens[zzi][1].token=(signed char)token;
656         tokens[zzi][1].eb=0;
657         tokens[zzi][1].cost=d2+_lambda*bits+tokens[zzj][tj].cost;
658         tokens[zzi][1].bits=bits+tokens[zzj][tj].bits;
659         tokens[zzi][1].qc=1+s^s;
660         nzflags|=(ogg_int64_t)1<<zzi;
661         best_flags|=
662          (ogg_int64_t)(tokens[zzi][1].cost<tokens[zzi][0].cost)<<zzi;
663       }
664     }
665     else{
666       int alt_qc;
667       eob=eob_run[zzi];
668       if(zzi<_acmin)_lambda=0;
669       dq=_dequant[zzi];
670       /*No zero run can extend past this point.*/
671       d2_accum[zzi]=0;
672       e=qc*dq-c;
673       d2=e*(ogg_int32_t)e;
674       best_token=*(OC_DCT_VALUE_TOKEN_PTR+qc);
675       best_bits=oc_token_bits(_enc,huffi,zzi,best_token);
676       best_cost=d2+_lambda*best_bits;
677       alt_qc=*(OC_DCT_TRELLIS_ALT_VALUE_PTR+qc);
678       e=alt_qc*dq-c;
679       d2=e*(ogg_int32_t)e;
680       token=*(OC_DCT_VALUE_TOKEN_PTR+alt_qc);
681       bits=oc_token_bits(_enc,huffi,zzi,token);
682       cost=d2+_lambda*bits;
683       if(cost<best_cost){
684         best_token=token;
685         best_bits=bits;
686         best_cost=cost;
687         qc=alt_qc;
688       }
689       zzj=zzi+1&63;
690       tj=best_flags>>zzj&1;
691       next=(zzj<<1)+tj;
692       tokens[zzi][1].next=(unsigned char)next;
693       tokens[zzi][1].token=(signed char)best_token;
694       tokens[zzi][1].eb=*(OC_DCT_VALUE_EB_PTR+qc);
695       tokens[zzi][1].cost=best_cost+tokens[zzj][tj].cost;
696       tokens[zzi][1].bits=best_bits+tokens[zzj][tj].bits;
697       tokens[zzi][1].qc=qc;
698       nzflags|=(ogg_int64_t)1<<zzi;
699       best_flags|=(ogg_int64_t)1<<zzi;
700     }
701     zzj=zzi;
702   }
703   /*Emit the tokens from the best path through the trellis.*/
704   stack=*_stack;
705   dct_fzig_zag=_enc->state.opt_data.dct_fzig_zag;
706   zzi=1;
707   ti=best_flags>>1&1;
708   bits=tokens[zzi][ti].bits;
709   do{
710     oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
711     eob=eob_run[zzi];
712     if(tokens[zzi][ti].token<OC_NDCT_EOB_TOKEN_MAX){
713       if(++eob>=4095){
714         oc_enc_token_log(_enc,_pli,zzi,OC_DCT_REPEAT_RUN3_TOKEN,eob);
715         eob=0;
716       }
717       eob_run[zzi]=eob;
718       /*We don't include the actual EOB cost for this block in the return value.
719         It is very likely to eventually be spread over several blocks, and
720          including it more harshly penalizes the first few blocks in a long EOB
721          run.
722         Omitting it here gives a small PSNR and SSIM gain.*/
723       bits-=tokens[zzi][ti].bits;
724       zzi=_zzi;
725       break;
726     }
727     /*Emit pending EOB run if any.*/
728     if(eob>0){
729       oc_enc_eob_log(_enc,_pli,zzi,eob);
730       eob_run[zzi]=0;
731     }
732     oc_enc_token_log(_enc,_pli,zzi,tokens[zzi][ti].token,tokens[zzi][ti].eb);
733     next=tokens[zzi][ti].next;
734     qc=tokens[zzi][ti].qc;
735     zzj=(next>>1)-1&63;
736     /*TODO: It may be worth saving the dequantized coefficient in the trellis
737        above; we had to compute it to measure the error anyway.*/
738     _idct[dct_fzig_zag[zzj]]=(ogg_int16_t)(qc*(int)_dequant[zzj]);
739     zzi=next>>1;
740     ti=next&1;
741   }
742   while(zzi);
743   *_stack=stack;
744   return bits;
745 }
746
747 /*Simplistic R/D tokenizer.
748   The AC coefficients of _idct must be pre-initialized to zero.
749   This could be made more accurate by using more sophisticated
750    rate predictions for zeros.
751   It could be made faster by switching from R/D decisions to static
752    lambda-derived rounding biases.*/
753 int oc_enc_tokenize_ac_fast(oc_enc_ctx *_enc,int _pli,ptrdiff_t _fragi,
754  ogg_int16_t *_idct,const ogg_int16_t *_qdct,
755  const ogg_uint16_t *_dequant,const ogg_int16_t *_dct,
756  int _zzi,oc_token_checkpoint **_stack,int _lambda,int _acmin){
757   const unsigned char *dct_fzig_zag;
758   ogg_uint16_t        *eob_run;
759   oc_token_checkpoint *stack;
760   int                  huffi;
761   int                  zzi;
762   int                  zzj;
763   int                  zzk;
764   int                  total_bits;
765   int                  zr[4];
766   stack=*_stack;
767   total_bits=0;
768   /*The apparent bit-cost of coding a zero from observing the trellis
769      quantizer is pre-combined with lambda.
770     Four predictive cases are considered: the last optimized value is zero (+2)
771      or non-zero and the non-optimized value is zero (+1) or non-zero.*/
772   zr[0]=3*_lambda>>1;
773   zr[1]=_lambda;
774   zr[2]=4*_lambda;
775   zr[3]=7*_lambda>>1;
776   eob_run=_enc->eob_run[_pli];
777   dct_fzig_zag=_enc->state.opt_data.dct_fzig_zag;
778   huffi=_enc->huff_idxs[_enc->state.frame_type][1][_pli+1>>1];
779   for(zzj=zzi=1;zzj<_zzi&&!_qdct[zzj];zzj++);
780   while(zzj<_zzi){
781     int v;
782     int d0;
783     int d1;
784     int sign;
785     int k;
786     int eob;
787     int dq0;
788     int dq1;
789     int dd0;
790     int dd1;
791     int next_zero;
792     int eob_bits;
793     int dct_fzig_zzj;
794     dct_fzig_zzj=dct_fzig_zag[zzj];
795     v=_dct[zzj];
796     d0=_qdct[zzj];
797     eob=eob_run[zzi];
798     for(zzk=zzj+1;zzk<_zzi&&!_qdct[zzk];zzk++);
799     next_zero=zzk-zzj+62>>6;
800     dq0=d0*_dequant[zzj];
801     dd0=dq0-v;
802     dd0*=dd0;
803     sign=-(d0<0);
804     k=d0+sign^sign;
805     d1=(k-(zzj>_acmin))+sign^sign;
806     dq1=d1*_dequant[zzj];
807     dd1=dq1-v;
808     dd1*=dd1;
809     /*The cost of ending an eob run is included when the alternative is to
810        extend this eob run.
811       A per qi/zzi weight would probably be useful.
812       Including it in the overall tokenization cost was not helpful.
813       The same is true at the far end of the zero run plus token case.*/
814     if(eob>0&&d1==0&&zzk==_zzi){
815       eob_bits=oc_token_bits(_enc,huffi,zzi,OC_DCT_EOB1_TOKEN);
816     }
817     else eob_bits=0;
818     if(zzj==zzi){
819       /*No active zero run.*/
820       int best_token;
821       int best_eb;
822       int token;
823       int best_bits;
824       int bits;
825       int cost;
826       best_token=*(OC_DCT_VALUE_TOKEN_PTR+d0);
827       best_bits=oc_token_bits(_enc,huffi,zzi,best_token);
828       if(d1!=0){
829         token=*(OC_DCT_VALUE_TOKEN_PTR+d1);
830         bits=oc_token_bits(_enc,huffi,zzi,token);
831         cost=dd1+(bits+eob_bits)*_lambda;
832       }
833       else{
834         token=bits=0;
835         cost=dd1+zr[next_zero];
836       }
837       if((dd0+(best_bits+eob_bits)*_lambda)>cost){
838         _idct[dct_fzig_zzj]=dq1;
839         if(d1==0){
840           zzj=zzk;
841           continue;
842         }
843         best_bits=bits;
844         best_token=token;
845         best_eb=*(OC_DCT_VALUE_EB_PTR+d1);
846       }
847       else{
848         best_eb=*(OC_DCT_VALUE_EB_PTR+d0);
849         _idct[dct_fzig_zzj]=dq0;
850       }
851       oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
852       if(eob>0){
853         oc_enc_eob_log(_enc,_pli,zzi,eob);
854         eob_run[zzi]=0;
855       }
856       oc_enc_token_log(_enc,_pli,zzi,best_token,best_eb);
857       total_bits+=best_bits;
858     }
859     else{
860       int d;
861       int dc_reserve;
862       int best_token;
863       int best_eb;
864       int best_bits;
865       int best_cost;
866       int best_bits1;
867       int best_token1;
868       int best_eb1;
869       int zr_bits;
870       int eob2;
871       int eob_bits2;
872       int bits;
873       int token;
874       int nzeros;
875       nzeros=zzj-zzi;
876       dc_reserve=zzi+62>>6;
877       /*A zero run, followed by the value alone.*/
878       best_token=best_token1=OC_DCT_SHORT_ZRL_TOKEN+(nzeros+55>>6);
879       best_eb=best_eb1=nzeros-1;
880       eob2=eob_run[zzj];
881       eob_bits2=eob2>0?oc_token_bits(_enc,huffi,zzj,OC_DCT_EOB1_TOKEN):0;
882       zr_bits=oc_token_bits(_enc,huffi,zzi,best_token)+eob_bits2;
883       best_bits=zr_bits
884        +oc_token_bits(_enc,huffi,zzj,*(OC_DCT_VALUE_TOKEN_PTR+d0));
885       d=d0;
886       best_bits1=0;
887       if(d1!=0){
888         best_bits1=zr_bits
889          +oc_token_bits(_enc,huffi,zzj,*(OC_DCT_VALUE_TOKEN_PTR+d1));
890       }
891       if(nzeros<17+dc_reserve){
892         if(k<=2){
893           /*+/- 1 combo token.*/
894           token=OC_DCT_RUN_CAT1_TOKEN[nzeros-1];
895           bits=oc_token_bits(_enc,huffi,zzi,token);
896           if(k==2&&bits<=best_bits1){
897             best_bits1=bits;
898             best_token1=token;
899             best_eb1=OC_DCT_RUN_CAT1_EB[nzeros-1][-sign];
900           }
901           if(k==1&&bits<=best_bits){
902             best_bits=bits;
903             best_token=token;
904             best_eb=OC_DCT_RUN_CAT1_EB[nzeros-1][-sign];
905           }
906         }
907         if(nzeros<3+dc_reserve&&2<=k&&k<=4){
908           /*+/- 2/3 combo token.*/
909           token=OC_DCT_RUN_CAT2A+(nzeros>>1);
910           bits=oc_token_bits(_enc,huffi,zzi,token);
911           if(k==4&&bits<=best_bits1){
912             best_bits1=bits;
913             best_token1=token;
914             best_eb1=OC_DCT_RUN_CAT2_EB[nzeros-1][-sign][1];
915           }
916           if(k!=4&&bits<=best_bits){
917             best_bits=bits;
918             best_token=token;
919             best_eb=OC_DCT_RUN_CAT2_EB[nzeros-1][-sign][k-2];
920           }
921         }
922       }
923       best_cost=dd0+(best_bits+eob_bits)*_lambda;
924       if(d1==0&&(dd1+zr[2+next_zero])<=best_cost){
925         zzj=zzk;
926         continue;
927       }
928       if(d1!=0&&dd1+(best_bits1+eob_bits)*_lambda<best_cost){
929         best_bits=best_bits1;
930         best_token=best_token1;
931         best_eb=best_eb1;
932         d=d1;
933         _idct[dct_fzig_zzj]=dq1;
934       }
935       else _idct[dct_fzig_zzj]=dq0;
936       oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
937       if(eob){
938         oc_enc_eob_log(_enc,_pli,zzi,eob);
939         eob_run[zzi]=0;
940       }
941       oc_enc_token_log(_enc,_pli,zzi,best_token,best_eb);
942       /*If a zero run won vs. the combo token we still need to code this
943          value.*/
944       if(best_token<=OC_DCT_ZRL_TOKEN){
945         oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzj);
946         if(eob2){
947           oc_enc_eob_log(_enc,_pli,zzj,eob2);
948           /*The cost of any EOB run we disrupted is ignored because doing so
949              improved PSNR/SSIM by a small amount.*/
950           best_bits-=eob_bits2;
951           eob_run[zzj]=0;
952         }
953         oc_enc_token_log(_enc,_pli,zzj,
954          *(OC_DCT_VALUE_TOKEN_PTR+d),*(OC_DCT_VALUE_EB_PTR+d));
955       }
956       total_bits+=best_bits;
957     }
958     zzi=zzj+1;
959     zzj=zzk;
960   }
961   /*Code an EOB run to complete this block.
962     The cost of the EOB run is not included in the total as explained in
963      in a comment in the trellis tokenizer above.*/
964   if(zzi<64){
965     int eob;
966     eob=eob_run[zzi]+1;
967     oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
968     if(eob>=4095){
969       oc_enc_token_log(_enc,_pli,zzi,OC_DCT_REPEAT_RUN3_TOKEN,eob);
970       eob=0;
971     }
972     eob_run[zzi]=eob;
973   }
974   *_stack=stack;
975   return total_bits;
976 }
977
978 void oc_enc_pred_dc_frag_rows(oc_enc_ctx *_enc,
979  int _pli,int _fragy0,int _frag_yend){
980   const oc_fragment_plane *fplane;
981   const oc_fragment       *frags;
982   ogg_int16_t             *frag_dc;
983   ptrdiff_t                fragi;
984   int                     *pred_last;
985   int                      nhfrags;
986   int                      fragx;
987   int                      fragy;
988   fplane=_enc->state.fplanes+_pli;
989   frags=_enc->state.frags;
990   frag_dc=_enc->frag_dc;
991   pred_last=_enc->dc_pred_last[_pli];
992   nhfrags=fplane->nhfrags;
993   fragi=fplane->froffset+_fragy0*nhfrags;
994   for(fragy=_fragy0;fragy<_frag_yend;fragy++){
995     if(fragy==0){
996       /*For the first row, all of the cases reduce to just using the previous
997          predictor for the same reference frame.*/
998       for(fragx=0;fragx<nhfrags;fragx++,fragi++){
999         if(frags[fragi].coded){
1000           int refi;
1001           refi=frags[fragi].refi;
1002           frag_dc[fragi]=(ogg_int16_t)(frags[fragi].dc-pred_last[refi]);
1003           pred_last[refi]=frags[fragi].dc;
1004         }
1005       }
1006     }
1007     else{
1008       const oc_fragment *u_frags;
1009       int                l_ref;
1010       int                ul_ref;
1011       int                u_ref;
1012       u_frags=frags-nhfrags;
1013       l_ref=-1;
1014       ul_ref=-1;
1015       u_ref=u_frags[fragi].refi;
1016       for(fragx=0;fragx<nhfrags;fragx++,fragi++){
1017         int ur_ref;
1018         if(fragx+1>=nhfrags)ur_ref=-1;
1019         else ur_ref=u_frags[fragi+1].refi;
1020         if(frags[fragi].coded){
1021           int pred;
1022           int refi;
1023           refi=frags[fragi].refi;
1024           /*We break out a separate case based on which of our neighbors use
1025              the same reference frames.
1026             This is somewhat faster than trying to make a generic case which
1027              handles all of them, since it reduces lots of poorly predicted
1028              jumps to one switch statement, and also lets a number of the
1029              multiplications be optimized out by strength reduction.*/
1030           switch((l_ref==refi)|(ul_ref==refi)<<1|
1031            (u_ref==refi)<<2|(ur_ref==refi)<<3){
1032             default:pred=pred_last[refi];break;
1033             case  1:
1034             case  3:pred=frags[fragi-1].dc;break;
1035             case  2:pred=u_frags[fragi-1].dc;break;
1036             case  4:
1037             case  6:
1038             case 12:pred=u_frags[fragi].dc;break;
1039             case  5:pred=(frags[fragi-1].dc+u_frags[fragi].dc)/2;break;
1040             case  8:pred=u_frags[fragi+1].dc;break;
1041             case  9:
1042             case 11:
1043             case 13:{
1044               pred=(75*frags[fragi-1].dc+53*u_frags[fragi+1].dc)/128;
1045             }break;
1046             case 10:pred=(u_frags[fragi-1].dc+u_frags[fragi+1].dc)/2;break;
1047             case 14:{
1048               pred=(3*(u_frags[fragi-1].dc+u_frags[fragi+1].dc)
1049                +10*u_frags[fragi].dc)/16;
1050             }break;
1051             case  7:
1052             case 15:{
1053               int p0;
1054               int p1;
1055               int p2;
1056               p0=frags[fragi-1].dc;
1057               p1=u_frags[fragi-1].dc;
1058               p2=u_frags[fragi].dc;
1059               pred=(29*(p0+p2)-26*p1)/32;
1060               if(abs(pred-p2)>128)pred=p2;
1061               else if(abs(pred-p0)>128)pred=p0;
1062               else if(abs(pred-p1)>128)pred=p1;
1063             }break;
1064           }
1065           frag_dc[fragi]=(ogg_int16_t)(frags[fragi].dc-pred);
1066           pred_last[refi]=frags[fragi].dc;
1067           l_ref=refi;
1068         }
1069         else l_ref=-1;
1070         ul_ref=u_ref;
1071         u_ref=ur_ref;
1072       }
1073     }
1074   }
1075 }
1076
1077 void oc_enc_tokenize_dc_frag_list(oc_enc_ctx *_enc,int _pli,
1078  const ptrdiff_t *_coded_fragis,ptrdiff_t _ncoded_fragis,
1079  int _prev_ndct_tokens1,int _prev_eob_run1){
1080   const ogg_int16_t *frag_dc;
1081   ptrdiff_t          fragii;
1082   unsigned char     *dct_tokens0;
1083   unsigned char     *dct_tokens1;
1084   ogg_uint16_t      *extra_bits0;
1085   ogg_uint16_t      *extra_bits1;
1086   ptrdiff_t          ti0;
1087   ptrdiff_t          ti1r;
1088   ptrdiff_t          ti1w;
1089   int                eob_run0;
1090   int                eob_run1;
1091   int                neobs1;
1092   int                token;
1093   int                eb;
1094   int                token1=token1;
1095   int                eb1=eb1;
1096   /*Return immediately if there are no coded fragments; otherwise we'd flush
1097      any trailing EOB run into the AC 1 list and never read it back out.*/
1098   if(_ncoded_fragis<=0)return;
1099   frag_dc=_enc->frag_dc;
1100   dct_tokens0=_enc->dct_tokens[_pli][0];
1101   dct_tokens1=_enc->dct_tokens[_pli][1];
1102   extra_bits0=_enc->extra_bits[_pli][0];
1103   extra_bits1=_enc->extra_bits[_pli][1];
1104   ti0=_enc->ndct_tokens[_pli][0];
1105   ti1w=ti1r=_prev_ndct_tokens1;
1106   eob_run0=_enc->eob_run[_pli][0];
1107   /*Flush any trailing EOB run for the 1st AC coefficient.
1108     This is needed to allow us to track tokens to the end of the list.*/
1109   eob_run1=_enc->eob_run[_pli][1];
1110   if(eob_run1>0)oc_enc_eob_log(_enc,_pli,1,eob_run1);
1111   /*If there was an active EOB run at the start of the 1st AC stack, read it
1112      in and decode it.*/
1113   if(_prev_eob_run1>0){
1114     token1=dct_tokens1[ti1r];
1115     eb1=extra_bits1[ti1r];
1116     ti1r++;
1117     eob_run1=oc_decode_eob_token(token1,eb1);
1118     /*Consume the portion of the run that came before these fragments.*/
1119     neobs1=eob_run1-_prev_eob_run1;
1120   }
1121   else eob_run1=neobs1=0;
1122   for(fragii=0;fragii<_ncoded_fragis;fragii++){
1123     int val;
1124     /*All tokens in the 1st AC coefficient stack are regenerated as the DC
1125        coefficients are produced.
1126       This can be done in-place; stack 1 cannot get larger.*/
1127     if(!neobs1){
1128       /*There's no active EOB run in stack 1; read the next token.*/
1129       token1=dct_tokens1[ti1r];
1130       eb1=extra_bits1[ti1r];
1131       ti1r++;
1132       if(token1<OC_NDCT_EOB_TOKEN_MAX){
1133         neobs1=oc_decode_eob_token(token1,eb1);
1134         /*It's an EOB run; add it to the current (inactive) one.
1135           Because we may have moved entries to stack 0, we may have an
1136            opportunity to merge two EOB runs in stack 1.*/
1137         eob_run1+=neobs1;
1138       }
1139     }
1140     val=frag_dc[_coded_fragis[fragii]];
1141     if(val){
1142       /*There was a non-zero DC value, so there's no alteration to stack 1
1143          for this fragment; just code the stack 0 token.*/
1144       /*Flush any pending EOB run.*/
1145       if(eob_run0>0){
1146         token=oc_make_eob_token_full(eob_run0,&eb);
1147         dct_tokens0[ti0]=(unsigned char)token;
1148         extra_bits0[ti0]=(ogg_uint16_t)eb;
1149         ti0++;
1150         eob_run0=0;
1151       }
1152       dct_tokens0[ti0]=*(OC_DCT_VALUE_TOKEN_PTR+val);
1153       extra_bits0[ti0]=*(OC_DCT_VALUE_EB_PTR+val);
1154       ti0++;
1155     }
1156     else{
1157       /*Zero DC value; that means the entry in stack 1 might need to be coded
1158          from stack 0.
1159         This requires a stack 1 fixup.*/
1160       if(neobs1>0){
1161         /*We're in the middle of an active EOB run in stack 1.
1162           Move it to stack 0.*/
1163         if(++eob_run0>=4095){
1164           dct_tokens0[ti0]=OC_DCT_REPEAT_RUN3_TOKEN;
1165           extra_bits0[ti0]=eob_run0;
1166           ti0++;
1167           eob_run0=0;
1168         }
1169         eob_run1--;
1170       }
1171       else{
1172         /*No active EOB run in stack 1, so we can't extend one in stack 0.
1173           Flush it if we've got it.*/
1174         if(eob_run0>0){
1175           token=oc_make_eob_token_full(eob_run0,&eb);
1176           dct_tokens0[ti0]=(unsigned char)token;
1177           extra_bits0[ti0]=(ogg_uint16_t)eb;
1178           ti0++;
1179           eob_run0=0;
1180         }
1181         /*Stack 1 token is one of: a pure zero run token, a single
1182            coefficient token, or a zero run/coefficient combo token.
1183           A zero run token is expanded and moved to token stack 0, and the
1184            stack 1 entry dropped.
1185           A single coefficient value may be transformed into combo token that
1186            is moved to stack 0, or if it cannot be combined, it is left alone
1187            and a single length-1 zero run is emitted in stack 0.
1188           A combo token is extended and moved to stack 0.
1189           During AC coding, we restrict the run lengths on combo tokens for
1190            stack 1 to guarantee we can extend them.*/
1191         switch(token1){
1192           case OC_DCT_SHORT_ZRL_TOKEN:{
1193             if(eb1<7){
1194               dct_tokens0[ti0]=OC_DCT_SHORT_ZRL_TOKEN;
1195               extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1196               ti0++;
1197               /*Don't write the AC coefficient back out.*/
1198               continue;
1199             }
1200             /*Fall through.*/
1201           }
1202           case OC_DCT_ZRL_TOKEN:{
1203             dct_tokens0[ti0]=OC_DCT_ZRL_TOKEN;
1204             extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1205             ti0++;
1206             /*Don't write the AC coefficient back out.*/
1207           }continue;
1208           case OC_ONE_TOKEN:
1209           case OC_MINUS_ONE_TOKEN:{
1210             dct_tokens0[ti0]=OC_DCT_RUN_CAT1A;
1211             extra_bits0[ti0]=(ogg_uint16_t)(token1-OC_ONE_TOKEN);
1212             ti0++;
1213             /*Don't write the AC coefficient back out.*/
1214           }continue;
1215           case OC_TWO_TOKEN:
1216           case OC_MINUS_TWO_TOKEN:{
1217             dct_tokens0[ti0]=OC_DCT_RUN_CAT2A;
1218             extra_bits0[ti0]=(ogg_uint16_t)(token1-OC_TWO_TOKEN<<1);
1219             ti0++;
1220             /*Don't write the AC coefficient back out.*/
1221           }continue;
1222           case OC_DCT_VAL_CAT2:{
1223             dct_tokens0[ti0]=OC_DCT_RUN_CAT2A;
1224             extra_bits0[ti0]=(ogg_uint16_t)((eb1<<1)+1);
1225             ti0++;
1226             /*Don't write the AC coefficient back out.*/
1227           }continue;
1228           case OC_DCT_RUN_CAT1A:
1229           case OC_DCT_RUN_CAT1A+1:
1230           case OC_DCT_RUN_CAT1A+2:
1231           case OC_DCT_RUN_CAT1A+3:{
1232             dct_tokens0[ti0]=(unsigned char)(token1+1);
1233             extra_bits0[ti0]=(ogg_uint16_t)eb1;
1234             ti0++;
1235             /*Don't write the AC coefficient back out.*/
1236           }continue;
1237           case OC_DCT_RUN_CAT1A+4:{
1238             dct_tokens0[ti0]=OC_DCT_RUN_CAT1B;
1239             extra_bits0[ti0]=(ogg_uint16_t)(eb1<<2);
1240             ti0++;
1241             /*Don't write the AC coefficient back out.*/
1242           }continue;
1243           case OC_DCT_RUN_CAT1B:{
1244             if((eb1&3)<3){
1245               dct_tokens0[ti0]=OC_DCT_RUN_CAT1B;
1246               extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1247               ti0++;
1248               /*Don't write the AC coefficient back out.*/
1249               continue;
1250             }
1251             eb1=((eb1&4)<<1)-1;
1252             /*Fall through.*/
1253           }
1254           case OC_DCT_RUN_CAT1C:{
1255             dct_tokens0[ti0]=OC_DCT_RUN_CAT1C;
1256             extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1257             ti0++;
1258             /*Don't write the AC coefficient back out.*/
1259           }continue;
1260           case OC_DCT_RUN_CAT2A:{
1261             eb1=(eb1<<1)-1;
1262             /*Fall through.*/
1263           }
1264           case OC_DCT_RUN_CAT2B:{
1265             dct_tokens0[ti0]=OC_DCT_RUN_CAT2B;
1266             extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1267             ti0++;
1268             /*Don't write the AC coefficient back out.*/
1269           }continue;
1270         }
1271         /*We can't merge tokens, write a short zero run and keep going.*/
1272         dct_tokens0[ti0]=OC_DCT_SHORT_ZRL_TOKEN;
1273         extra_bits0[ti0]=0;
1274         ti0++;
1275       }
1276     }
1277     if(!neobs1){
1278       /*Flush any (inactive) EOB run.*/
1279       if(eob_run1>0){
1280         token=oc_make_eob_token_full(eob_run1,&eb);
1281         dct_tokens1[ti1w]=(unsigned char)token;
1282         extra_bits1[ti1w]=(ogg_uint16_t)eb;
1283         ti1w++;
1284         eob_run1=0;
1285       }
1286       /*There's no active EOB run, so log the current token.*/
1287       dct_tokens1[ti1w]=(unsigned char)token1;
1288       extra_bits1[ti1w]=(ogg_uint16_t)eb1;
1289       ti1w++;
1290     }
1291     else{
1292       /*Otherwise consume one EOB from the current run.*/
1293       neobs1--;
1294       /*If we have more than 4095 EOBs outstanding in stack1, flush the run.*/
1295       if(eob_run1-neobs1>=4095){
1296         dct_tokens1[ti1w]=OC_DCT_REPEAT_RUN3_TOKEN;
1297         extra_bits1[ti1w]=4095;
1298         ti1w++;
1299         eob_run1-=4095;
1300       }
1301     }
1302   }
1303   /*Save the current state.*/
1304   _enc->ndct_tokens[_pli][0]=ti0;
1305   _enc->ndct_tokens[_pli][1]=ti1w;
1306   _enc->eob_run[_pli][0]=eob_run0;
1307   _enc->eob_run[_pli][1]=eob_run1;
1308 }
1309
1310 /*Final EOB run welding.*/
1311 void oc_enc_tokenize_finish(oc_enc_ctx *_enc){
1312   int pli;
1313   int zzi;
1314   /*Emit final EOB runs.*/
1315   for(pli=0;pli<3;pli++)for(zzi=0;zzi<64;zzi++){
1316     int eob_run;
1317     eob_run=_enc->eob_run[pli][zzi];
1318     if(eob_run>0)oc_enc_eob_log(_enc,pli,zzi,eob_run);
1319   }
1320   /*Merge the final EOB run of one token list with the start of the next, if
1321      possible.*/
1322   for(zzi=0;zzi<64;zzi++)for(pli=0;pli<3;pli++){
1323     int       old_tok1;
1324     int       old_tok2;
1325     int       old_eb1;
1326     int       old_eb2;
1327     int       new_tok;
1328     int       new_eb;
1329     int       zzj;
1330     int       plj;
1331     ptrdiff_t ti=ti;
1332     int       run_count;
1333     /*Make sure this coefficient has tokens at all.*/
1334     if(_enc->ndct_tokens[pli][zzi]<=0)continue;
1335     /*Ensure the first token is an EOB run.*/
1336     old_tok2=_enc->dct_tokens[pli][zzi][0];
1337     if(old_tok2>=OC_NDCT_EOB_TOKEN_MAX)continue;
1338     /*Search for a previous coefficient that has any tokens at all.*/
1339     old_tok1=OC_NDCT_EOB_TOKEN_MAX;
1340     for(zzj=zzi,plj=pli;zzj>=0;zzj--){
1341       while(plj-->0){
1342         ti=_enc->ndct_tokens[plj][zzj]-1;
1343         if(ti>=_enc->dct_token_offs[plj][zzj]){
1344           old_tok1=_enc->dct_tokens[plj][zzj][ti];
1345           break;
1346         }
1347       }
1348       if(plj>=0)break;
1349       plj=3;
1350     }
1351     /*Ensure its last token was an EOB run.*/
1352     if(old_tok1>=OC_NDCT_EOB_TOKEN_MAX)continue;
1353     /*Pull off the associated extra bits, if any, and decode the runs.*/
1354     old_eb1=_enc->extra_bits[plj][zzj][ti];
1355     old_eb2=_enc->extra_bits[pli][zzi][0];
1356     run_count=oc_decode_eob_token(old_tok1,old_eb1)
1357      +oc_decode_eob_token(old_tok2,old_eb2);
1358     /*We can't possibly combine these into one run.
1359       It might be possible to split them more optimally, but we'll just leave
1360        them as-is.*/
1361     if(run_count>=4096)continue;
1362     /*We CAN combine them into one run.*/
1363     new_tok=oc_make_eob_token_full(run_count,&new_eb);
1364     _enc->dct_tokens[plj][zzj][ti]=(unsigned char)new_tok;
1365     _enc->extra_bits[plj][zzj][ti]=(ogg_uint16_t)new_eb;
1366     _enc->dct_token_offs[pli][zzi]++;
1367   }
1368 }