Add a new libtheora_info example program.
[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 DC coefficient is not preserved; it should be restored by the caller.*/
458 int oc_enc_tokenize_ac(oc_enc_ctx *_enc,int _pli,ptrdiff_t _fragi,
459  ogg_int16_t *_qdct,const ogg_uint16_t *_dequant,const ogg_int16_t *_dct,
460  int _zzi,oc_token_checkpoint **_stack,int _lambda,int _acmin){
461   oc_token_checkpoint *stack;
462   ogg_int64_t          zflags;
463   ogg_int64_t          nzflags;
464   ogg_int64_t          best_flags;
465   ogg_uint32_t         d2_accum[64];
466   oc_quant_token       tokens[64][2];
467   ogg_uint16_t        *eob_run;
468   const unsigned char *dct_fzig_zag;
469   ogg_uint32_t         cost;
470   int                  bits;
471   int                  eob;
472   int                  token;
473   int                  eb;
474   int                  next;
475   int                  huffi;
476   int                  zzi;
477   int                  ti;
478   int                  zzj;
479   int                  qc;
480   huffi=_enc->huff_idxs[_enc->state.frame_type][1][_pli+1>>1];
481   eob_run=_enc->eob_run[_pli];
482   memset(tokens[0],0,sizeof(tokens[0]));
483   best_flags=nzflags=0;
484   zflags=1;
485   d2_accum[0]=0;
486   zzj=64;
487   for(zzi=OC_MINI(_zzi,63);zzi>0;zzi--){
488     ogg_uint32_t best_cost;
489     int          best_bits=best_bits;
490     int          best_next=best_next;
491     int          best_token=best_token;
492     int          best_eb=best_eb;
493     int          best_qc=best_qc;
494     ogg_uint32_t d2;
495     int          dq;
496     int          qc_m;
497     int          e;
498     int          c;
499     int          s;
500     int          tj;
501     qc=_qdct[zzi];
502     s=-(qc<0);
503     qc_m=qc+s^s;
504     c=_dct[OC_FZIG_ZAG[zzi]];
505     /*The hard case: try a zero run.*/
506     if(qc_m<=1){
507       ogg_uint32_t sum_d2;
508       int          nzeros;
509       int          dc_reserve;
510       if(!qc_m){
511         /*Skip runs that are already quantized to zeros.
512           If we considered each zero coefficient in turn, we might
513            theoretically find a better way to partition long zero runs (e.g.,
514            a run of > 17 zeros followed by a 1 might be better coded as a short
515            zero run followed by a combo token, rather than the longer zero
516            token followed by a 1 value token), but zeros are so common that
517            this becomes very computationally expensive (quadratic instead of
518            linear in the number of coefficients), for a marginal gain.*/
519         while(zzi>1&&!_qdct[zzi-1])zzi--;
520         /*The distortion of coefficients originally quantized to zero is
521            treated as zero (since we'll never quantize them to anything else).*/
522         d2=0;
523       }
524       else{
525         d2=c*(ogg_int32_t)c;
526         c=c+s^s;
527       }
528       eob=eob_run[zzi];
529       nzeros=zzj-zzi;
530       zzj&=63;
531       sum_d2=d2+d2_accum[zzj];
532       d2_accum[zzi]=sum_d2;
533       /*We reserve 1 spot for combo run tokens that start in the 1st AC stack
534          to ensure they can be extended to include the DC coefficient if
535          necessary; this greatly simplifies stack-rewriting later on.*/
536       dc_reserve=zzi+62>>6;
537       best_cost=0xFFFFFFFF;
538       for(;;){
539         if(nzflags>>zzj&1){
540           int val;
541           int val_s;
542           int zzk;
543           int tk;
544           next=tokens[zzj][1].next;
545           tk=next&1;
546           zzk=next>>1;
547           /*Try a pure zero run to this point.*/
548           token=OC_DCT_SHORT_ZRL_TOKEN+(nzeros+55>>6);
549           bits=oc_token_bits(_enc,huffi,zzi,token);
550           d2=sum_d2-d2_accum[zzj];
551           cost=d2+_lambda*bits+tokens[zzj][1].cost;
552           if(cost<=best_cost){
553             best_next=(zzj<<1)+1;
554             best_token=token;
555             best_eb=nzeros-1;
556             best_cost=cost;
557             best_bits=bits+tokens[zzj][1].bits;
558             best_qc=0;
559           }
560           if(nzeros<17+dc_reserve){
561             val=_qdct[zzj];
562             val_s=-(val<0);
563             val=val+val_s^val_s;
564             if(val<=2){
565               /*Try a +/- 1 combo token.*/
566               token=OC_DCT_RUN_CAT1_TOKEN[nzeros-1];
567               eb=OC_DCT_RUN_CAT1_EB[nzeros-1][-val_s];
568               e=_dct[OC_FZIG_ZAG[zzj]]-(_dequant[zzj]+val_s^val_s);
569               d2=e*(ogg_int32_t)e+sum_d2-d2_accum[zzj];
570               bits=oc_token_bits(_enc,huffi,zzi,token);
571               cost=d2+_lambda*bits+tokens[zzk][tk].cost;
572               if(cost<=best_cost){
573                 best_next=next;
574                 best_token=token;
575                 best_eb=eb;
576                 best_cost=cost;
577                 best_bits=bits+tokens[zzk][tk].bits;
578                 best_qc=1+val_s^val_s;
579               }
580             }
581             if(nzeros<3+dc_reserve&&2<=val&&val<=4){
582               int sval;
583               /*Try a +/- 2/3 combo token.*/
584               token=OC_DCT_RUN_CAT2A+(nzeros>>1);
585               bits=oc_token_bits(_enc,huffi,zzi,token);
586               val=2+(val>2);
587               sval=val+val_s^val_s;
588               e=_dct[OC_FZIG_ZAG[zzj]]-_dequant[zzj]*sval;
589               d2=e*(ogg_int32_t)e+sum_d2-d2_accum[zzj];
590               cost=d2+_lambda*bits+tokens[zzk][tk].cost;
591               if(cost<=best_cost){
592                 best_cost=cost;
593                 best_bits=bits+tokens[zzk][tk].bits;
594                 best_next=next;
595                 best_token=token;
596                 best_eb=OC_DCT_RUN_CAT2_EB[nzeros-1][-val_s][val-2];
597                 best_qc=sval;
598               }
599             }
600           }
601           /*zzj can't be coded as a zero, so stop trying to extend the run.*/
602           if(!(zflags>>zzj&1))break;
603         }
604         /*We could try to consider _all_ potentially non-zero coefficients, but
605            if we already found a bunch of them not worth coding, it's fairly
606            unlikely they would now be worth coding from this position; skipping
607            them saves a lot of work.*/
608         zzj=(tokens[zzj][0].next>>1)-(tokens[zzj][0].qc!=0)&63;
609         if(zzj==0){
610           /*We made it all the way to the end of the block; try an EOB token.*/
611           if(eob<4095){
612             bits=oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob+1))
613              -(eob>0?oc_token_bits(_enc,huffi,zzi,oc_make_eob_token(eob)):0);
614           }
615           else bits=oc_token_bits(_enc,huffi,zzi,OC_DCT_EOB1_TOKEN);
616           cost=sum_d2+bits*_lambda;
617           /*If the best route so far is still a pure zero run to the end of the
618              block, force coding it as an EOB.
619             Even if it's not optimal for this block, it has a good chance of
620              getting combined with an EOB token from subsequent blocks, saving
621              bits overall.*/
622           if(cost<=best_cost||best_token<=OC_DCT_ZRL_TOKEN&&zzi+best_eb==63){
623             best_next=0;
624             /*This token is just a marker; in reality we may not emit any
625                tokens, but update eob_run[] instead.*/
626             best_token=OC_DCT_EOB1_TOKEN;
627             best_eb=0;
628             best_cost=cost;
629             best_bits=bits;
630             best_qc=0;
631           }
632           break;
633         }
634         nzeros=zzj-zzi;
635       }
636       tokens[zzi][0].next=(unsigned char)best_next;
637       tokens[zzi][0].token=(signed char)best_token;
638       tokens[zzi][0].eb=(ogg_int16_t)best_eb;
639       tokens[zzi][0].cost=best_cost;
640       tokens[zzi][0].bits=best_bits;
641       tokens[zzi][0].qc=best_qc;
642       zflags|=(ogg_int64_t)1<<zzi;
643       if(qc_m){
644         dq=_dequant[zzi];
645         if(zzi<_acmin)_lambda=0;
646         e=dq-c;
647         d2=e*(ogg_int32_t)e;
648         token=OC_ONE_TOKEN-s;
649         bits=oc_token_bits(_enc,huffi,zzi,token);
650         zzj=zzi+1&63;
651         tj=best_flags>>zzj&1;
652         next=(zzj<<1)+tj;
653         tokens[zzi][1].next=(unsigned char)next;
654         tokens[zzi][1].token=(signed char)token;
655         tokens[zzi][1].eb=0;
656         tokens[zzi][1].cost=d2+_lambda*bits+tokens[zzj][tj].cost;
657         tokens[zzi][1].bits=bits+tokens[zzj][tj].bits;
658         tokens[zzi][1].qc=1+s^s;
659         nzflags|=(ogg_int64_t)1<<zzi;
660         best_flags|=
661          (ogg_int64_t)(tokens[zzi][1].cost<tokens[zzi][0].cost)<<zzi;
662       }
663     }
664     else{
665       int alt_qc;
666       eob=eob_run[zzi];
667       if(zzi<_acmin)_lambda=0;
668       dq=_dequant[zzi];
669       /*No zero run can extend past this point.*/
670       d2_accum[zzi]=0;
671       e=qc*dq-c;
672       d2=e*(ogg_int32_t)e;
673       best_token=*(OC_DCT_VALUE_TOKEN_PTR+qc);
674       best_bits=oc_token_bits(_enc,huffi,zzi,best_token);
675       best_cost=d2+_lambda*best_bits;
676       alt_qc=*(OC_DCT_TRELLIS_ALT_VALUE_PTR+qc);
677       e=alt_qc*dq-c;
678       d2=e*(ogg_int32_t)e;
679       token=*(OC_DCT_VALUE_TOKEN_PTR+alt_qc);
680       bits=oc_token_bits(_enc,huffi,zzi,token);
681       cost=d2+_lambda*bits;
682       if(cost<best_cost){
683         best_token=token;
684         best_bits=bits;
685         best_cost=cost;
686         qc=alt_qc;
687       }
688       zzj=zzi+1&63;
689       tj=best_flags>>zzj&1;
690       next=(zzj<<1)+tj;
691       tokens[zzi][1].next=(unsigned char)next;
692       tokens[zzi][1].token=(signed char)best_token;
693       tokens[zzi][1].eb=*(OC_DCT_VALUE_EB_PTR+qc);
694       tokens[zzi][1].cost=best_cost+tokens[zzj][tj].cost;
695       tokens[zzi][1].bits=best_bits+tokens[zzj][tj].bits;
696       tokens[zzi][1].qc=qc;
697       nzflags|=(ogg_int64_t)1<<zzi;
698       best_flags|=(ogg_int64_t)1<<zzi;
699     }
700     zzj=zzi;
701   }
702   /*Emit the tokens from the best path through the trellis.*/
703   stack=*_stack;
704   /*We blow away the first entry here so that things vectorize better.
705     The DC coefficient is not actually stored in the array yet.*/
706   for(zzi=0;zzi<64;zzi++)_qdct[zzi]=0;
707   dct_fzig_zag=_enc->state.opt_data.dct_fzig_zag;
708   zzi=1;
709   ti=best_flags>>1&1;
710   bits=tokens[zzi][ti].bits;
711   do{
712     oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
713     eob=eob_run[zzi];
714     if(tokens[zzi][ti].token<OC_NDCT_EOB_TOKEN_MAX){
715       if(++eob>=4095){
716         oc_enc_token_log(_enc,_pli,zzi,OC_DCT_REPEAT_RUN3_TOKEN,eob);
717         eob=0;
718       }
719       eob_run[zzi]=eob;
720       /*We don't include the actual EOB cost for this block in the return value.
721         It is very likely to eventually be spread over several blocks, and
722          including it more harshly penalizes the first few blocks in a long EOB
723          run.
724         Omitting it here gives a small PSNR and SSIM gain.*/
725       bits-=tokens[zzi][ti].bits;
726       zzi=_zzi;
727       break;
728     }
729     /*Emit pending EOB run if any.*/
730     if(eob>0){
731       oc_enc_eob_log(_enc,_pli,zzi,eob);
732       eob_run[zzi]=0;
733     }
734     oc_enc_token_log(_enc,_pli,zzi,tokens[zzi][ti].token,tokens[zzi][ti].eb);
735     next=tokens[zzi][ti].next;
736     qc=tokens[zzi][ti].qc;
737     zzj=(next>>1)-1&63;
738     /*TODO: It may be worth saving the dequantized coefficient in the trellis
739        above; we had to compute it to measure the error anyway.*/
740     _qdct[dct_fzig_zag[zzj]]=(ogg_int16_t)(qc*(int)_dequant[zzj]);
741     zzi=next>>1;
742     ti=next&1;
743   }
744   while(zzi);
745   *_stack=stack;
746   return bits;
747 }
748
749 /*Simplistic R/D tokenizer.
750   This could be made more accurate by using more sophisticated
751    rate predictions for zeros.
752   It could be made faster by switching from R/D decisions to static
753    lambda-derived rounding biases.*/
754 int oc_enc_tokenize_ac_fast(oc_enc_ctx *_enc,int _pli,ptrdiff_t _fragi,
755  ogg_int16_t *_qdct,const ogg_uint16_t *_dequant,const ogg_int16_t *_dct,
756  int _zzi,oc_token_checkpoint **_stack,int _lambda,int _acmin){
757   /*Note that gcc will not always respect this alignment.
758     In this case it doesn't matter terribly much.*/
759   OC_ALIGN16(ogg_int16_t  coef[64]);
760   const unsigned char *dct_fzig_zag;
761   ogg_uint16_t        *eob_run;
762   oc_token_checkpoint *stack;
763   int                  huffi;
764   int                  zzi;
765   int                  zzj;
766   int                  zzk;
767   int                  total_bits;
768   int                  zr[4];
769   stack=*_stack;
770   total_bits=0;
771   /*The apparent bit-cost of coding a zero from observing the trellis
772      quantizer is pre-combined with lambda.
773     Four predictive cases are considered: the last optimized value is zero (+2)
774      or non-zero and the non-optimized value is zero (+1) or non-zero.*/
775   zr[0]=3*_lambda>>1;
776   zr[1]=_lambda;
777   zr[2]=4*_lambda;
778   zr[3]=7*_lambda>>1;
779   eob_run=_enc->eob_run[_pli];
780   dct_fzig_zag=_enc->state.opt_data.dct_fzig_zag;
781   huffi=_enc->huff_idxs[_enc->state.frame_type][1][_pli+1>>1];
782   memcpy(coef,_qdct,_zzi*sizeof(*coef));
783   for(zzj=0;zzj<64;zzj++)_qdct[zzj]=0;
784   for(zzj=zzi=1;zzj<_zzi&&!coef[zzj];zzj++);
785   while(zzj<_zzi){
786     int v;
787     int d0;
788     int d1;
789     int sign;
790     int k;
791     int eob;
792     int dq0;
793     int dq1;
794     int dd0;
795     int dd1;
796     int next_zero;
797     int eob_bits;
798     int dct_fzig_zzj;
799     dct_fzig_zzj=dct_fzig_zag[zzj];
800     v=_dct[OC_FZIG_ZAG[zzj]];
801     d0=coef[zzj];
802     eob=eob_run[zzi];
803     for(zzk=zzj+1;zzk<_zzi&&!coef[zzk];zzk++);
804     next_zero=zzk-zzj+62>>6;
805     dq0=d0*_dequant[zzj];
806     dd0=dq0-v;
807     dd0*=dd0;
808     sign=-(d0<0);
809     k=d0+sign^sign;
810     d1=(k-(zzj>_acmin))+sign^sign;
811     dq1=d1*_dequant[zzj];
812     dd1=dq1-v;
813     dd1*=dd1;
814     /*The cost of ending an eob run is included when the alternative is to
815        extend this eob run.
816       A per qi/zzi weight would probably be useful.
817       Including it in the overall tokenization cost was not helpful.
818       The same is true at the far end of the zero run plus token case.*/
819     if(eob>0&&d1==0&&zzk==_zzi){
820       eob_bits=oc_token_bits(_enc,huffi,zzi,OC_DCT_EOB1_TOKEN);
821     }
822     else eob_bits=0;
823     if(zzj==zzi){
824       /*No active zero run.*/
825       int best_token;
826       int best_eb;
827       int token;
828       int best_bits;
829       int bits;
830       int cost;
831       best_token=*(OC_DCT_VALUE_TOKEN_PTR+d0);
832       best_bits=oc_token_bits(_enc,huffi,zzi,best_token);
833       if(d1!=0){
834         token=*(OC_DCT_VALUE_TOKEN_PTR+d1);
835         bits=oc_token_bits(_enc,huffi,zzi,token);
836         cost=dd1+(bits+eob_bits)*_lambda;
837       }
838       else{
839         token=bits=0;
840         cost=dd1+zr[next_zero];
841       }
842       if((dd0+(best_bits+eob_bits)*_lambda)>cost){
843         _qdct[dct_fzig_zzj]=dq1;
844         if(d1==0){
845           zzj=zzk;
846           continue;
847         }
848         best_bits=bits;
849         best_token=token;
850         best_eb=*(OC_DCT_VALUE_EB_PTR+d1);
851       }
852       else{
853         best_eb=*(OC_DCT_VALUE_EB_PTR+d0);
854         _qdct[dct_fzig_zzj]=dq0;
855       }
856       oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
857       if(eob>0){
858         oc_enc_eob_log(_enc,_pli,zzi,eob);
859         eob_run[zzi]=0;
860       }
861       oc_enc_token_log(_enc,_pli,zzi,best_token,best_eb);
862       total_bits+=best_bits;
863     }
864     else{
865       int d;
866       int dc_reserve;
867       int best_token;
868       int best_eb;
869       int best_bits;
870       int best_cost;
871       int best_bits1;
872       int best_token1;
873       int best_eb1;
874       int zr_bits;
875       int eob2;
876       int eob_bits2;
877       int bits;
878       int token;
879       int nzeros;
880       nzeros=zzj-zzi;
881       dc_reserve=zzi+62>>6;
882       /*A zero run, followed by the value alone.*/
883       best_token=best_token1=OC_DCT_SHORT_ZRL_TOKEN+(nzeros+55>>6);
884       best_eb=best_eb1=nzeros-1;
885       eob2=eob_run[zzj];
886       eob_bits2=eob2>0?oc_token_bits(_enc,huffi,zzj,OC_DCT_EOB1_TOKEN):0;
887       zr_bits=oc_token_bits(_enc,huffi,zzi,best_token)+eob_bits2;
888       best_bits=zr_bits
889        +oc_token_bits(_enc,huffi,zzj,*(OC_DCT_VALUE_TOKEN_PTR+d0));
890       d=d0;
891       best_bits1=0;
892       if(d1!=0){
893         best_bits1=zr_bits
894          +oc_token_bits(_enc,huffi,zzj,*(OC_DCT_VALUE_TOKEN_PTR+d1));
895       }
896       if(nzeros<17+dc_reserve){
897         if(k<=2){
898           /*+/- 1 combo token.*/
899           token=OC_DCT_RUN_CAT1_TOKEN[nzeros-1];
900           bits=oc_token_bits(_enc,huffi,zzi,token);
901           if(k==2&&bits<=best_bits1){
902             best_bits1=bits;
903             best_token1=token;
904             best_eb1=OC_DCT_RUN_CAT1_EB[nzeros-1][-sign];
905           }
906           if(k==1&&bits<=best_bits){
907             best_bits=bits;
908             best_token=token;
909             best_eb=OC_DCT_RUN_CAT1_EB[nzeros-1][-sign];
910           }
911         }
912         if(nzeros<3+dc_reserve&&2<=k&&k<=4){
913           /*+/- 2/3 combo token.*/
914           token=OC_DCT_RUN_CAT2A+(nzeros>>1);
915           bits=oc_token_bits(_enc,huffi,zzi,token);
916           if(k==4&&bits<=best_bits1){
917             best_bits1=bits;
918             best_token1=token;
919             best_eb1=OC_DCT_RUN_CAT2_EB[nzeros-1][-sign][1];
920           }
921           if(k!=4&&bits<=best_bits){
922             best_bits=bits;
923             best_token=token;
924             best_eb=OC_DCT_RUN_CAT2_EB[nzeros-1][-sign][k-2];
925           }
926         }
927       }
928       best_cost=dd0+(best_bits+eob_bits)*_lambda;
929       if(d1==0&&(dd1+zr[2+next_zero])<=best_cost){
930         _qdct[dct_fzig_zzj]=0;
931         zzj=zzk;
932         continue;
933       }
934       if(d1!=0&&dd1+(best_bits1+eob_bits)*_lambda<best_cost){
935         best_bits=best_bits1;
936         best_token=best_token1;
937         best_eb=best_eb1;
938         d=d1;
939         _qdct[dct_fzig_zzj]=dq1;
940       }
941       else _qdct[dct_fzig_zzj]=dq0;
942       oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
943       if(eob){
944         oc_enc_eob_log(_enc,_pli,zzi,eob);
945         eob_run[zzi]=0;
946       }
947       oc_enc_token_log(_enc,_pli,zzi,best_token,best_eb);
948       /*If a zero run won vs. the combo token we still need to code this
949          value.*/
950       if(best_token<=OC_DCT_ZRL_TOKEN){
951         oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzj);
952         if(eob2){
953           oc_enc_eob_log(_enc,_pli,zzj,eob2);
954           /*The cost of any EOB run we disrupted is ignored because doing so
955              improved PSNR/SSIM by a small amount.*/
956           best_bits-=eob_bits2;
957           eob_run[zzj]=0;
958         }
959         oc_enc_token_log(_enc,_pli,zzj,
960          *(OC_DCT_VALUE_TOKEN_PTR+d),*(OC_DCT_VALUE_EB_PTR+d));
961       }
962       total_bits+=best_bits;
963     }
964     zzi=zzj+1;
965     zzj=zzk;
966   }
967   /*Code an EOB run to complete this block.
968     The cost of the EOB run is not included in the total as explained in
969      in a comment in the trellis tokenizer above.*/
970   if(zzi<64){
971     int eob;
972     eob=eob_run[zzi]+1;
973     oc_enc_tokenlog_checkpoint(_enc,stack++,_pli,zzi);
974     if(eob>=4095){
975       oc_enc_token_log(_enc,_pli,zzi,OC_DCT_REPEAT_RUN3_TOKEN,eob);
976       eob=0;
977     }
978     eob_run[zzi]=eob;
979   }
980   *_stack=stack;
981   return total_bits;
982 }
983
984 void oc_enc_pred_dc_frag_rows(oc_enc_ctx *_enc,
985  int _pli,int _fragy0,int _frag_yend){
986   const oc_fragment_plane *fplane;
987   const oc_fragment       *frags;
988   ogg_int16_t             *frag_dc;
989   ptrdiff_t                fragi;
990   int                     *pred_last;
991   int                      nhfrags;
992   int                      fragx;
993   int                      fragy;
994   fplane=_enc->state.fplanes+_pli;
995   frags=_enc->state.frags;
996   frag_dc=_enc->frag_dc;
997   pred_last=_enc->dc_pred_last[_pli];
998   nhfrags=fplane->nhfrags;
999   fragi=fplane->froffset+_fragy0*nhfrags;
1000   for(fragy=_fragy0;fragy<_frag_yend;fragy++){
1001     if(fragy==0){
1002       /*For the first row, all of the cases reduce to just using the previous
1003          predictor for the same reference frame.*/
1004       for(fragx=0;fragx<nhfrags;fragx++,fragi++){
1005         if(frags[fragi].coded){
1006           int refi;
1007           refi=frags[fragi].refi;
1008           frag_dc[fragi]=(ogg_int16_t)(frags[fragi].dc-pred_last[refi]);
1009           pred_last[refi]=frags[fragi].dc;
1010         }
1011       }
1012     }
1013     else{
1014       const oc_fragment *u_frags;
1015       int                l_ref;
1016       int                ul_ref;
1017       int                u_ref;
1018       u_frags=frags-nhfrags;
1019       l_ref=-1;
1020       ul_ref=-1;
1021       u_ref=u_frags[fragi].refi;
1022       for(fragx=0;fragx<nhfrags;fragx++,fragi++){
1023         int ur_ref;
1024         if(fragx+1>=nhfrags)ur_ref=-1;
1025         else ur_ref=u_frags[fragi+1].refi;
1026         if(frags[fragi].coded){
1027           int pred;
1028           int refi;
1029           refi=frags[fragi].refi;
1030           /*We break out a separate case based on which of our neighbors use
1031              the same reference frames.
1032             This is somewhat faster than trying to make a generic case which
1033              handles all of them, since it reduces lots of poorly predicted
1034              jumps to one switch statement, and also lets a number of the
1035              multiplications be optimized out by strength reduction.*/
1036           switch((l_ref==refi)|(ul_ref==refi)<<1|
1037            (u_ref==refi)<<2|(ur_ref==refi)<<3){
1038             default:pred=pred_last[refi];break;
1039             case  1:
1040             case  3:pred=frags[fragi-1].dc;break;
1041             case  2:pred=u_frags[fragi-1].dc;break;
1042             case  4:
1043             case  6:
1044             case 12:pred=u_frags[fragi].dc;break;
1045             case  5:pred=(frags[fragi-1].dc+u_frags[fragi].dc)/2;break;
1046             case  8:pred=u_frags[fragi+1].dc;break;
1047             case  9:
1048             case 11:
1049             case 13:{
1050               pred=(75*frags[fragi-1].dc+53*u_frags[fragi+1].dc)/128;
1051             }break;
1052             case 10:pred=(u_frags[fragi-1].dc+u_frags[fragi+1].dc)/2;break;
1053             case 14:{
1054               pred=(3*(u_frags[fragi-1].dc+u_frags[fragi+1].dc)
1055                +10*u_frags[fragi].dc)/16;
1056             }break;
1057             case  7:
1058             case 15:{
1059               int p0;
1060               int p1;
1061               int p2;
1062               p0=frags[fragi-1].dc;
1063               p1=u_frags[fragi-1].dc;
1064               p2=u_frags[fragi].dc;
1065               pred=(29*(p0+p2)-26*p1)/32;
1066               if(abs(pred-p2)>128)pred=p2;
1067               else if(abs(pred-p0)>128)pred=p0;
1068               else if(abs(pred-p1)>128)pred=p1;
1069             }break;
1070           }
1071           frag_dc[fragi]=(ogg_int16_t)(frags[fragi].dc-pred);
1072           pred_last[refi]=frags[fragi].dc;
1073           l_ref=refi;
1074         }
1075         else l_ref=-1;
1076         ul_ref=u_ref;
1077         u_ref=ur_ref;
1078       }
1079     }
1080   }
1081 }
1082
1083 void oc_enc_tokenize_dc_frag_list(oc_enc_ctx *_enc,int _pli,
1084  const ptrdiff_t *_coded_fragis,ptrdiff_t _ncoded_fragis,
1085  int _prev_ndct_tokens1,int _prev_eob_run1){
1086   const ogg_int16_t *frag_dc;
1087   ptrdiff_t          fragii;
1088   unsigned char     *dct_tokens0;
1089   unsigned char     *dct_tokens1;
1090   ogg_uint16_t      *extra_bits0;
1091   ogg_uint16_t      *extra_bits1;
1092   ptrdiff_t          ti0;
1093   ptrdiff_t          ti1r;
1094   ptrdiff_t          ti1w;
1095   int                eob_run0;
1096   int                eob_run1;
1097   int                neobs1;
1098   int                token;
1099   int                eb;
1100   int                token1=token1;
1101   int                eb1=eb1;
1102   /*Return immediately if there are no coded fragments; otherwise we'd flush
1103      any trailing EOB run into the AC 1 list and never read it back out.*/
1104   if(_ncoded_fragis<=0)return;
1105   frag_dc=_enc->frag_dc;
1106   dct_tokens0=_enc->dct_tokens[_pli][0];
1107   dct_tokens1=_enc->dct_tokens[_pli][1];
1108   extra_bits0=_enc->extra_bits[_pli][0];
1109   extra_bits1=_enc->extra_bits[_pli][1];
1110   ti0=_enc->ndct_tokens[_pli][0];
1111   ti1w=ti1r=_prev_ndct_tokens1;
1112   eob_run0=_enc->eob_run[_pli][0];
1113   /*Flush any trailing EOB run for the 1st AC coefficient.
1114     This is needed to allow us to track tokens to the end of the list.*/
1115   eob_run1=_enc->eob_run[_pli][1];
1116   if(eob_run1>0)oc_enc_eob_log(_enc,_pli,1,eob_run1);
1117   /*If there was an active EOB run at the start of the 1st AC stack, read it
1118      in and decode it.*/
1119   if(_prev_eob_run1>0){
1120     token1=dct_tokens1[ti1r];
1121     eb1=extra_bits1[ti1r];
1122     ti1r++;
1123     eob_run1=oc_decode_eob_token(token1,eb1);
1124     /*Consume the portion of the run that came before these fragments.*/
1125     neobs1=eob_run1-_prev_eob_run1;
1126   }
1127   else eob_run1=neobs1=0;
1128   for(fragii=0;fragii<_ncoded_fragis;fragii++){
1129     int val;
1130     /*All tokens in the 1st AC coefficient stack are regenerated as the DC
1131        coefficients are produced.
1132       This can be done in-place; stack 1 cannot get larger.*/
1133     if(!neobs1){
1134       /*There's no active EOB run in stack 1; read the next token.*/
1135       token1=dct_tokens1[ti1r];
1136       eb1=extra_bits1[ti1r];
1137       ti1r++;
1138       if(token1<OC_NDCT_EOB_TOKEN_MAX){
1139         neobs1=oc_decode_eob_token(token1,eb1);
1140         /*It's an EOB run; add it to the current (inactive) one.
1141           Because we may have moved entries to stack 0, we may have an
1142            opportunity to merge two EOB runs in stack 1.*/
1143         eob_run1+=neobs1;
1144       }
1145     }
1146     val=frag_dc[_coded_fragis[fragii]];
1147     if(val){
1148       /*There was a non-zero DC value, so there's no alteration to stack 1
1149          for this fragment; just code the stack 0 token.*/
1150       /*Flush any pending EOB run.*/
1151       if(eob_run0>0){
1152         token=oc_make_eob_token_full(eob_run0,&eb);
1153         dct_tokens0[ti0]=(unsigned char)token;
1154         extra_bits0[ti0]=(ogg_uint16_t)eb;
1155         ti0++;
1156         eob_run0=0;
1157       }
1158       dct_tokens0[ti0]=*(OC_DCT_VALUE_TOKEN_PTR+val);
1159       extra_bits0[ti0]=*(OC_DCT_VALUE_EB_PTR+val);
1160       ti0++;
1161     }
1162     else{
1163       /*Zero DC value; that means the entry in stack 1 might need to be coded
1164          from stack 0.
1165         This requires a stack 1 fixup.*/
1166       if(neobs1>0){
1167         /*We're in the middle of an active EOB run in stack 1.
1168           Move it to stack 0.*/
1169         if(++eob_run0>=4095){
1170           dct_tokens0[ti0]=OC_DCT_REPEAT_RUN3_TOKEN;
1171           extra_bits0[ti0]=eob_run0;
1172           ti0++;
1173           eob_run0=0;
1174         }
1175         eob_run1--;
1176       }
1177       else{
1178         /*No active EOB run in stack 1, so we can't extend one in stack 0.
1179           Flush it if we've got it.*/
1180         if(eob_run0>0){
1181           token=oc_make_eob_token_full(eob_run0,&eb);
1182           dct_tokens0[ti0]=(unsigned char)token;
1183           extra_bits0[ti0]=(ogg_uint16_t)eb;
1184           ti0++;
1185           eob_run0=0;
1186         }
1187         /*Stack 1 token is one of: a pure zero run token, a single
1188            coefficient token, or a zero run/coefficient combo token.
1189           A zero run token is expanded and moved to token stack 0, and the
1190            stack 1 entry dropped.
1191           A single coefficient value may be transformed into combo token that
1192            is moved to stack 0, or if it cannot be combined, it is left alone
1193            and a single length-1 zero run is emitted in stack 0.
1194           A combo token is extended and moved to stack 0.
1195           During AC coding, we restrict the run lengths on combo tokens for
1196            stack 1 to guarantee we can extend them.*/
1197         switch(token1){
1198           case OC_DCT_SHORT_ZRL_TOKEN:{
1199             if(eb1<7){
1200               dct_tokens0[ti0]=OC_DCT_SHORT_ZRL_TOKEN;
1201               extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1202               ti0++;
1203               /*Don't write the AC coefficient back out.*/
1204               continue;
1205             }
1206             /*Fall through.*/
1207           }
1208           case OC_DCT_ZRL_TOKEN:{
1209             dct_tokens0[ti0]=OC_DCT_ZRL_TOKEN;
1210             extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1211             ti0++;
1212             /*Don't write the AC coefficient back out.*/
1213           }continue;
1214           case OC_ONE_TOKEN:
1215           case OC_MINUS_ONE_TOKEN:{
1216             dct_tokens0[ti0]=OC_DCT_RUN_CAT1A;
1217             extra_bits0[ti0]=(ogg_uint16_t)(token1-OC_ONE_TOKEN);
1218             ti0++;
1219             /*Don't write the AC coefficient back out.*/
1220           }continue;
1221           case OC_TWO_TOKEN:
1222           case OC_MINUS_TWO_TOKEN:{
1223             dct_tokens0[ti0]=OC_DCT_RUN_CAT2A;
1224             extra_bits0[ti0]=(ogg_uint16_t)(token1-OC_TWO_TOKEN<<1);
1225             ti0++;
1226             /*Don't write the AC coefficient back out.*/
1227           }continue;
1228           case OC_DCT_VAL_CAT2:{
1229             dct_tokens0[ti0]=OC_DCT_RUN_CAT2A;
1230             extra_bits0[ti0]=(ogg_uint16_t)((eb1<<1)+1);
1231             ti0++;
1232             /*Don't write the AC coefficient back out.*/
1233           }continue;
1234           case OC_DCT_RUN_CAT1A:
1235           case OC_DCT_RUN_CAT1A+1:
1236           case OC_DCT_RUN_CAT1A+2:
1237           case OC_DCT_RUN_CAT1A+3:{
1238             dct_tokens0[ti0]=(unsigned char)(token1+1);
1239             extra_bits0[ti0]=(ogg_uint16_t)eb1;
1240             ti0++;
1241             /*Don't write the AC coefficient back out.*/
1242           }continue;
1243           case OC_DCT_RUN_CAT1A+4:{
1244             dct_tokens0[ti0]=OC_DCT_RUN_CAT1B;
1245             extra_bits0[ti0]=(ogg_uint16_t)(eb1<<2);
1246             ti0++;
1247             /*Don't write the AC coefficient back out.*/
1248           }continue;
1249           case OC_DCT_RUN_CAT1B:{
1250             if((eb1&3)<3){
1251               dct_tokens0[ti0]=OC_DCT_RUN_CAT1B;
1252               extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1253               ti0++;
1254               /*Don't write the AC coefficient back out.*/
1255               continue;
1256             }
1257             eb1=((eb1&4)<<1)-1;
1258             /*Fall through.*/
1259           }
1260           case OC_DCT_RUN_CAT1C:{
1261             dct_tokens0[ti0]=OC_DCT_RUN_CAT1C;
1262             extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1263             ti0++;
1264             /*Don't write the AC coefficient back out.*/
1265           }continue;
1266           case OC_DCT_RUN_CAT2A:{
1267             eb1=(eb1<<1)-1;
1268             /*Fall through.*/
1269           }
1270           case OC_DCT_RUN_CAT2B:{
1271             dct_tokens0[ti0]=OC_DCT_RUN_CAT2B;
1272             extra_bits0[ti0]=(ogg_uint16_t)(eb1+1);
1273             ti0++;
1274             /*Don't write the AC coefficient back out.*/
1275           }continue;
1276         }
1277         /*We can't merge tokens, write a short zero run and keep going.*/
1278         dct_tokens0[ti0]=OC_DCT_SHORT_ZRL_TOKEN;
1279         extra_bits0[ti0]=0;
1280         ti0++;
1281       }
1282     }
1283     if(!neobs1){
1284       /*Flush any (inactive) EOB run.*/
1285       if(eob_run1>0){
1286         token=oc_make_eob_token_full(eob_run1,&eb);
1287         dct_tokens1[ti1w]=(unsigned char)token;
1288         extra_bits1[ti1w]=(ogg_uint16_t)eb;
1289         ti1w++;
1290         eob_run1=0;
1291       }
1292       /*There's no active EOB run, so log the current token.*/
1293       dct_tokens1[ti1w]=(unsigned char)token1;
1294       extra_bits1[ti1w]=(ogg_uint16_t)eb1;
1295       ti1w++;
1296     }
1297     else{
1298       /*Otherwise consume one EOB from the current run.*/
1299       neobs1--;
1300       /*If we have more than 4095 EOBs outstanding in stack1, flush the run.*/
1301       if(eob_run1-neobs1>=4095){
1302         dct_tokens1[ti1w]=OC_DCT_REPEAT_RUN3_TOKEN;
1303         extra_bits1[ti1w]=4095;
1304         ti1w++;
1305         eob_run1-=4095;
1306       }
1307     }
1308   }
1309   /*Save the current state.*/
1310   _enc->ndct_tokens[_pli][0]=ti0;
1311   _enc->ndct_tokens[_pli][1]=ti1w;
1312   _enc->eob_run[_pli][0]=eob_run0;
1313   _enc->eob_run[_pli][1]=eob_run1;
1314 }
1315
1316 /*Final EOB run welding.*/
1317 void oc_enc_tokenize_finish(oc_enc_ctx *_enc){
1318   int pli;
1319   int zzi;
1320   /*Emit final EOB runs.*/
1321   for(pli=0;pli<3;pli++)for(zzi=0;zzi<64;zzi++){
1322     int eob_run;
1323     eob_run=_enc->eob_run[pli][zzi];
1324     if(eob_run>0)oc_enc_eob_log(_enc,pli,zzi,eob_run);
1325   }
1326   /*Merge the final EOB run of one token list with the start of the next, if
1327      possible.*/
1328   for(zzi=0;zzi<64;zzi++)for(pli=0;pli<3;pli++){
1329     int       old_tok1;
1330     int       old_tok2;
1331     int       old_eb1;
1332     int       old_eb2;
1333     int       new_tok;
1334     int       new_eb;
1335     int       zzj;
1336     int       plj;
1337     ptrdiff_t ti=ti;
1338     int       run_count;
1339     /*Make sure this coefficient has tokens at all.*/
1340     if(_enc->ndct_tokens[pli][zzi]<=0)continue;
1341     /*Ensure the first token is an EOB run.*/
1342     old_tok2=_enc->dct_tokens[pli][zzi][0];
1343     if(old_tok2>=OC_NDCT_EOB_TOKEN_MAX)continue;
1344     /*Search for a previous coefficient that has any tokens at all.*/
1345     old_tok1=OC_NDCT_EOB_TOKEN_MAX;
1346     for(zzj=zzi,plj=pli;zzj>=0;zzj--){
1347       while(plj-->0){
1348         ti=_enc->ndct_tokens[plj][zzj]-1;
1349         if(ti>=_enc->dct_token_offs[plj][zzj]){
1350           old_tok1=_enc->dct_tokens[plj][zzj][ti];
1351           break;
1352         }
1353       }
1354       if(plj>=0)break;
1355       plj=3;
1356     }
1357     /*Ensure its last token was an EOB run.*/
1358     if(old_tok1>=OC_NDCT_EOB_TOKEN_MAX)continue;
1359     /*Pull off the associated extra bits, if any, and decode the runs.*/
1360     old_eb1=_enc->extra_bits[plj][zzj][ti];
1361     old_eb2=_enc->extra_bits[pli][zzi][0];
1362     run_count=oc_decode_eob_token(old_tok1,old_eb1)
1363      +oc_decode_eob_token(old_tok2,old_eb2);
1364     /*We can't possibly combine these into one run.
1365       It might be possible to split them more optimally, but we'll just leave
1366        them as-is.*/
1367     if(run_count>=4096)continue;
1368     /*We CAN combine them into one run.*/
1369     new_tok=oc_make_eob_token_full(run_count,&new_eb);
1370     _enc->dct_tokens[plj][zzj][ti]=(unsigned char)new_tok;
1371     _enc->extra_bits[plj][zzj][ti]=(ogg_uint16_t)new_eb;
1372     _enc->dct_token_offs[pli][zzi]++;
1373   }
1374 }