1 // Copyright 2011 Google Inc. All Rights Reserved.
2 //
3 // Use of this source code is governed by a BSD-style license
4 // that can be found in the COPYING file in the root of the source
5 // tree. An additional intellectual property rights grant can be found
6 // in the file PATENTS. All contributing project authors may
7 // be found in the AUTHORS file in the root of the source tree.
8 // -----------------------------------------------------------------------------
9 //
10 // Cost tables for level and modes
11 //
12 // Author: Skal (pascal.massimino@gmail.com)
13
14 #include "./cost.h"
15
16 //------------------------------------------------------------------------------
17 // Boolean-cost cost table
18
19 const uint16_t VP8EntropyCost[256] = {
20 1792, 1792, 1792, 1536, 1536, 1408, 1366, 1280, 1280, 1216,
21 1178, 1152, 1110, 1076, 1061, 1024, 1024, 992, 968, 951,
22 939, 911, 896, 878, 871, 854, 838, 820, 811, 794,
23 786, 768, 768, 752, 740, 732, 720, 709, 704, 690,
24 683, 672, 666, 655, 647, 640, 631, 622, 615, 607,
25 598, 592, 586, 576, 572, 564, 559, 555, 547, 541,
26 534, 528, 522, 512, 512, 504, 500, 494, 488, 483,
27 477, 473, 467, 461, 458, 452, 448, 443, 438, 434,
28 427, 424, 419, 415, 410, 406, 403, 399, 394, 390,
29 384, 384, 377, 374, 370, 366, 362, 359, 355, 351,
30 347, 342, 342, 336, 333, 330, 326, 323, 320, 316,
31 312, 308, 305, 302, 299, 296, 293, 288, 287, 283,
32 280, 277, 274, 272, 268, 266, 262, 256, 256, 256,
33 251, 248, 245, 242, 240, 237, 234, 232, 228, 226,
34 223, 221, 218, 216, 214, 211, 208, 205, 203, 201,
35 198, 196, 192, 191, 188, 187, 183, 181, 179, 176,
36 175, 171, 171, 168, 165, 163, 160, 159, 156, 154,
37 152, 150, 148, 146, 144, 142, 139, 138, 135, 133,
38 131, 128, 128, 125, 123, 121, 119, 117, 115, 113,
39 111, 110, 107, 105, 103, 102, 100, 98, 96, 94,
40 92, 91, 89, 86, 86, 83, 82, 80, 77, 76,
41 74, 73, 71, 69, 67, 66, 64, 63, 61, 59,
42 57, 55, 54, 52, 51, 49, 47, 46, 44, 43,
43 41, 40, 38, 36, 35, 33, 32, 30, 29, 27,
44 25, 24, 22, 21, 19, 18, 16, 15, 13, 12,
45 10, 9, 7, 6, 4, 3
46 };
47
48 //------------------------------------------------------------------------------
49 // Level cost tables
50
51 // For each given level, the following table gives the pattern of contexts to
52 // use for coding it (in [][0]) as well as the bit value to use for each
53 // context (in [][1]).
54 const uint16_t VP8LevelCodes[MAX_VARIABLE_LEVEL][2] = {
55 {0x001, 0x000}, {0x007, 0x001}, {0x00f, 0x005},
56 {0x00f, 0x00d}, {0x033, 0x003}, {0x033, 0x003}, {0x033, 0x023},
57 {0x033, 0x023}, {0x033, 0x023}, {0x033, 0x023}, {0x0d3, 0x013},
58 {0x0d3, 0x013}, {0x0d3, 0x013}, {0x0d3, 0x013}, {0x0d3, 0x013},
59 {0x0d3, 0x013}, {0x0d3, 0x013}, {0x0d3, 0x013}, {0x0d3, 0x093},
60 {0x0d3, 0x093}, {0x0d3, 0x093}, {0x0d3, 0x093}, {0x0d3, 0x093},
61 {0x0d3, 0x093}, {0x0d3, 0x093}, {0x0d3, 0x093}, {0x0d3, 0x093},
62 {0x0d3, 0x093}, {0x0d3, 0x093}, {0x0d3, 0x093}, {0x0d3, 0x093},
63 {0x0d3, 0x093}, {0x0d3, 0x093}, {0x0d3, 0x093}, {0x153, 0x053},
64 {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053},
65 {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053},
66 {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053},
67 {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053},
68 {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053},
69 {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053},
70 {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053},
71 {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x053}, {0x153, 0x153}
72 };
73
74 // fixed costs for coding levels, deduce from the coding tree.
75 // This is only the part that doesn't depend on the probability state.
76 const uint16_t VP8LevelFixedCosts[MAX_LEVEL + 1] = {
77 0, 256, 256, 256, 256, 432, 618, 630,
78 731, 640, 640, 828, 901, 948, 1021, 1101,
79 1174, 1221, 1294, 1042, 1085, 1115, 1158, 1202,
80 1245, 1275, 1318, 1337, 1380, 1410, 1453, 1497,
81 1540, 1570, 1613, 1280, 1295, 1317, 1332, 1358,
82 1373, 1395, 1410, 1454, 1469, 1491, 1506, 1532,
83 1547, 1569, 1584, 1601, 1616, 1638, 1653, 1679,
84 1694, 1716, 1731, 1775, 1790, 1812, 1827, 1853,
85 1868, 1890, 1905, 1727, 1733, 1742, 1748, 1759,
86 1765, 1774, 1780, 1800, 1806, 1815, 1821, 1832,
87 1838, 1847, 1853, 1878, 1884, 1893, 1899, 1910,
88 1916, 1925, 1931, 1951, 1957, 1966, 1972, 1983,
89 1989, 1998, 2004, 2027, 2033, 2042, 2048, 2059,
90 2065, 2074, 2080, 2100, 2106, 2115, 2121, 2132,
91 2138, 2147, 2153, 2178, 2184, 2193, 2199, 2210,
92 2216, 2225, 2231, 2251, 2257, 2266, 2272, 2283,
93 2289, 2298, 2304, 2168, 2174, 2183, 2189, 2200,
94 2206, 2215, 2221, 2241, 2247, 2256, 2262, 2273,
95 2279, 2288, 2294, 2319, 2325, 2334, 2340, 2351,
96 2357, 2366, 2372, 2392, 2398, 2407, 2413, 2424,
97 2430, 2439, 2445, 2468, 2474, 2483, 2489, 2500,
98 2506, 2515, 2521, 2541, 2547, 2556, 2562, 2573,
99 2579, 2588, 2594, 2619, 2625, 2634, 2640, 2651,
100 2657, 2666, 2672, 2692, 2698, 2707, 2713, 2724,
101 2730, 2739, 2745, 2540, 2546, 2555, 2561, 2572,
102 2578, 2587, 2593, 2613, 2619, 2628, 2634, 2645,
103 2651, 2660, 2666, 2691, 2697, 2706, 2712, 2723,
104 2729, 2738, 2744, 2764, 2770, 2779, 2785, 2796,
105 2802, 2811, 2817, 2840, 2846, 2855, 2861, 2872,
106 2878, 2887, 2893, 2913, 2919, 2928, 2934, 2945,
107 2951, 2960, 2966, 2991, 2997, 3006, 3012, 3023,
108 3029, 3038, 3044, 3064, 3070, 3079, 3085, 3096,
109 3102, 3111, 3117, 2981, 2987, 2996, 3002, 3013,
110 3019, 3028, 3034, 3054, 3060, 3069, 3075, 3086,
111 3092, 3101, 3107, 3132, 3138, 3147, 3153, 3164,
112 3170, 3179, 3185, 3205, 3211, 3220, 3226, 3237,
113 3243, 3252, 3258, 3281, 3287, 3296, 3302, 3313,
114 3319, 3328, 3334, 3354, 3360, 3369, 3375, 3386,
115 3392, 3401, 3407, 3432, 3438, 3447, 3453, 3464,
116 3470, 3479, 3485, 3505, 3511, 3520, 3526, 3537,
117 3543, 3552, 3558, 2816, 2822, 2831, 2837, 2848,
118 2854, 2863, 2869, 2889, 2895, 2904, 2910, 2921,
119 2927, 2936, 2942, 2967, 2973, 2982, 2988, 2999,
120 3005, 3014, 3020, 3040, 3046, 3055, 3061, 3072,
121 3078, 3087, 3093, 3116, 3122, 3131, 3137, 3148,
122 3154, 3163, 3169, 3189, 3195, 3204, 3210, 3221,
123 3227, 3236, 3242, 3267, 3273, 3282, 3288, 3299,
124 3305, 3314, 3320, 3340, 3346, 3355, 3361, 3372,
125 3378, 3387, 3393, 3257, 3263, 3272, 3278, 3289,
126 3295, 3304, 3310, 3330, 3336, 3345, 3351, 3362,
127 3368, 3377, 3383, 3408, 3414, 3423, 3429, 3440,
128 3446, 3455, 3461, 3481, 3487, 3496, 3502, 3513,
129 3519, 3528, 3534, 3557, 3563, 3572, 3578, 3589,
130 3595, 3604, 3610, 3630, 3636, 3645, 3651, 3662,
131 3668, 3677, 3683, 3708, 3714, 3723, 3729, 3740,
132 3746, 3755, 3761, 3781, 3787, 3796, 3802, 3813,
133 3819, 3828, 3834, 3629, 3635, 3644, 3650, 3661,
134 3667, 3676, 3682, 3702, 3708, 3717, 3723, 3734,
135 3740, 3749, 3755, 3780, 3786, 3795, 3801, 3812,
136 3818, 3827, 3833, 3853, 3859, 3868, 3874, 3885,
137 3891, 3900, 3906, 3929, 3935, 3944, 3950, 3961,
138 3967, 3976, 3982, 4002, 4008, 4017, 4023, 4034,
139 4040, 4049, 4055, 4080, 4086, 4095, 4101, 4112,
140 4118, 4127, 4133, 4153, 4159, 4168, 4174, 4185,
141 4191, 4200, 4206, 4070, 4076, 4085, 4091, 4102,
142 4108, 4117, 4123, 4143, 4149, 4158, 4164, 4175,
143 4181, 4190, 4196, 4221, 4227, 4236, 4242, 4253,
144 4259, 4268, 4274, 4294, 4300, 4309, 4315, 4326,
145 4332, 4341, 4347, 4370, 4376, 4385, 4391, 4402,
146 4408, 4417, 4423, 4443, 4449, 4458, 4464, 4475,
147 4481, 4490, 4496, 4521, 4527, 4536, 4542, 4553,
148 4559, 4568, 4574, 4594, 4600, 4609, 4615, 4626,
149 4632, 4641, 4647, 3515, 3521, 3530, 3536, 3547,
150 3553, 3562, 3568, 3588, 3594, 3603, 3609, 3620,
151 3626, 3635, 3641, 3666, 3672, 3681, 3687, 3698,
152 3704, 3713, 3719, 3739, 3745, 3754, 3760, 3771,
153 3777, 3786, 3792, 3815, 3821, 3830, 3836, 3847,
154 3853, 3862, 3868, 3888, 3894, 3903, 3909, 3920,
155 3926, 3935, 3941, 3966, 3972, 3981, 3987, 3998,
156 4004, 4013, 4019, 4039, 4045, 4054, 4060, 4071,
157 4077, 4086, 4092, 3956, 3962, 3971, 3977, 3988,
158 3994, 4003, 4009, 4029, 4035, 4044, 4050, 4061,
159 4067, 4076, 4082, 4107, 4113, 4122, 4128, 4139,
160 4145, 4154, 4160, 4180, 4186, 4195, 4201, 4212,
161 4218, 4227, 4233, 4256, 4262, 4271, 4277, 4288,
162 4294, 4303, 4309, 4329, 4335, 4344, 4350, 4361,
163 4367, 4376, 4382, 4407, 4413, 4422, 4428, 4439,
164 4445, 4454, 4460, 4480, 4486, 4495, 4501, 4512,
165 4518, 4527, 4533, 4328, 4334, 4343, 4349, 4360,
166 4366, 4375, 4381, 4401, 4407, 4416, 4422, 4433,
167 4439, 4448, 4454, 4479, 4485, 4494, 4500, 4511,
168 4517, 4526, 4532, 4552, 4558, 4567, 4573, 4584,
169 4590, 4599, 4605, 4628, 4634, 4643, 4649, 4660,
170 4666, 4675, 4681, 4701, 4707, 4716, 4722, 4733,
171 4739, 4748, 4754, 4779, 4785, 4794, 4800, 4811,
172 4817, 4826, 4832, 4852, 4858, 4867, 4873, 4884,
173 4890, 4899, 4905, 4769, 4775, 4784, 4790, 4801,
174 4807, 4816, 4822, 4842, 4848, 4857, 4863, 4874,
175 4880, 4889, 4895, 4920, 4926, 4935, 4941, 4952,
176 4958, 4967, 4973, 4993, 4999, 5008, 5014, 5025,
177 5031, 5040, 5046, 5069, 5075, 5084, 5090, 5101,
178 5107, 5116, 5122, 5142, 5148, 5157, 5163, 5174,
179 5180, 5189, 5195, 5220, 5226, 5235, 5241, 5252,
180 5258, 5267, 5273, 5293, 5299, 5308, 5314, 5325,
181 5331, 5340, 5346, 4604, 4610, 4619, 4625, 4636,
182 4642, 4651, 4657, 4677, 4683, 4692, 4698, 4709,
183 4715, 4724, 4730, 4755, 4761, 4770, 4776, 4787,
184 4793, 4802, 4808, 4828, 4834, 4843, 4849, 4860,
185 4866, 4875, 4881, 4904, 4910, 4919, 4925, 4936,
186 4942, 4951, 4957, 4977, 4983, 4992, 4998, 5009,
187 5015, 5024, 5030, 5055, 5061, 5070, 5076, 5087,
188 5093, 5102, 5108, 5128, 5134, 5143, 5149, 5160,
189 5166, 5175, 5181, 5045, 5051, 5060, 5066, 5077,
190 5083, 5092, 5098, 5118, 5124, 5133, 5139, 5150,
191 5156, 5165, 5171, 5196, 5202, 5211, 5217, 5228,
192 5234, 5243, 5249, 5269, 5275, 5284, 5290, 5301,
193 5307, 5316, 5322, 5345, 5351, 5360, 5366, 5377,
194 5383, 5392, 5398, 5418, 5424, 5433, 5439, 5450,
195 5456, 5465, 5471, 5496, 5502, 5511, 5517, 5528,
196 5534, 5543, 5549, 5569, 5575, 5584, 5590, 5601,
197 5607, 5616, 5622, 5417, 5423, 5432, 5438, 5449,
198 5455, 5464, 5470, 5490, 5496, 5505, 5511, 5522,
199 5528, 5537, 5543, 5568, 5574, 5583, 5589, 5600,
200 5606, 5615, 5621, 5641, 5647, 5656, 5662, 5673,
201 5679, 5688, 5694, 5717, 5723, 5732, 5738, 5749,
202 5755, 5764, 5770, 5790, 5796, 5805, 5811, 5822,
203 5828, 5837, 5843, 5868, 5874, 5883, 5889, 5900,
204 5906, 5915, 5921, 5941, 5947, 5956, 5962, 5973,
205 5979, 5988, 5994, 5858, 5864, 5873, 5879, 5890,
206 5896, 5905, 5911, 5931, 5937, 5946, 5952, 5963,
207 5969, 5978, 5984, 6009, 6015, 6024, 6030, 6041,
208 6047, 6056, 6062, 6082, 6088, 6097, 6103, 6114,
209 6120, 6129, 6135, 6158, 6164, 6173, 6179, 6190,
210 6196, 6205, 6211, 6231, 6237, 6246, 6252, 6263,
211 6269, 6278, 6284, 6309, 6315, 6324, 6330, 6341,
212 6347, 6356, 6362, 6382, 6388, 6397, 6403, 6414,
213 6420, 6429, 6435, 3515, 3521, 3530, 3536, 3547,
214 3553, 3562, 3568, 3588, 3594, 3603, 3609, 3620,
215 3626, 3635, 3641, 3666, 3672, 3681, 3687, 3698,
216 3704, 3713, 3719, 3739, 3745, 3754, 3760, 3771,
217 3777, 3786, 3792, 3815, 3821, 3830, 3836, 3847,
218 3853, 3862, 3868, 3888, 3894, 3903, 3909, 3920,
219 3926, 3935, 3941, 3966, 3972, 3981, 3987, 3998,
220 4004, 4013, 4019, 4039, 4045, 4054, 4060, 4071,
221 4077, 4086, 4092, 3956, 3962, 3971, 3977, 3988,
222 3994, 4003, 4009, 4029, 4035, 4044, 4050, 4061,
223 4067, 4076, 4082, 4107, 4113, 4122, 4128, 4139,
224 4145, 4154, 4160, 4180, 4186, 4195, 4201, 4212,
225 4218, 4227, 4233, 4256, 4262, 4271, 4277, 4288,
226 4294, 4303, 4309, 4329, 4335, 4344, 4350, 4361,
227 4367, 4376, 4382, 4407, 4413, 4422, 4428, 4439,
228 4445, 4454, 4460, 4480, 4486, 4495, 4501, 4512,
229 4518, 4527, 4533, 4328, 4334, 4343, 4349, 4360,
230 4366, 4375, 4381, 4401, 4407, 4416, 4422, 4433,
231 4439, 4448, 4454, 4479, 4485, 4494, 4500, 4511,
232 4517, 4526, 4532, 4552, 4558, 4567, 4573, 4584,
233 4590, 4599, 4605, 4628, 4634, 4643, 4649, 4660,
234 4666, 4675, 4681, 4701, 4707, 4716, 4722, 4733,
235 4739, 4748, 4754, 4779, 4785, 4794, 4800, 4811,
236 4817, 4826, 4832, 4852, 4858, 4867, 4873, 4884,
237 4890, 4899, 4905, 4769, 4775, 4784, 4790, 4801,
238 4807, 4816, 4822, 4842, 4848, 4857, 4863, 4874,
239 4880, 4889, 4895, 4920, 4926, 4935, 4941, 4952,
240 4958, 4967, 4973, 4993, 4999, 5008, 5014, 5025,
241 5031, 5040, 5046, 5069, 5075, 5084, 5090, 5101,
242 5107, 5116, 5122, 5142, 5148, 5157, 5163, 5174,
243 5180, 5189, 5195, 5220, 5226, 5235, 5241, 5252,
244 5258, 5267, 5273, 5293, 5299, 5308, 5314, 5325,
245 5331, 5340, 5346, 4604, 4610, 4619, 4625, 4636,
246 4642, 4651, 4657, 4677, 4683, 4692, 4698, 4709,
247 4715, 4724, 4730, 4755, 4761, 4770, 4776, 4787,
248 4793, 4802, 4808, 4828, 4834, 4843, 4849, 4860,
249 4866, 4875, 4881, 4904, 4910, 4919, 4925, 4936,
250 4942, 4951, 4957, 4977, 4983, 4992, 4998, 5009,
251 5015, 5024, 5030, 5055, 5061, 5070, 5076, 5087,
252 5093, 5102, 5108, 5128, 5134, 5143, 5149, 5160,
253 5166, 5175, 5181, 5045, 5051, 5060, 5066, 5077,
254 5083, 5092, 5098, 5118, 5124, 5133, 5139, 5150,
255 5156, 5165, 5171, 5196, 5202, 5211, 5217, 5228,
256 5234, 5243, 5249, 5269, 5275, 5284, 5290, 5301,
257 5307, 5316, 5322, 5345, 5351, 5360, 5366, 5377,
258 5383, 5392, 5398, 5418, 5424, 5433, 5439, 5450,
259 5456, 5465, 5471, 5496, 5502, 5511, 5517, 5528,
260 5534, 5543, 5549, 5569, 5575, 5584, 5590, 5601,
261 5607, 5616, 5622, 5417, 5423, 5432, 5438, 5449,
262 5455, 5464, 5470, 5490, 5496, 5505, 5511, 5522,
263 5528, 5537, 5543, 5568, 5574, 5583, 5589, 5600,
264 5606, 5615, 5621, 5641, 5647, 5656, 5662, 5673,
265 5679, 5688, 5694, 5717, 5723, 5732, 5738, 5749,
266 5755, 5764, 5770, 5790, 5796, 5805, 5811, 5822,
267 5828, 5837, 5843, 5868, 5874, 5883, 5889, 5900,
268 5906, 5915, 5921, 5941, 5947, 5956, 5962, 5973,
269 5979, 5988, 5994, 5858, 5864, 5873, 5879, 5890,
270 5896, 5905, 5911, 5931, 5937, 5946, 5952, 5963,
271 5969, 5978, 5984, 6009, 6015, 6024, 6030, 6041,
272 6047, 6056, 6062, 6082, 6088, 6097, 6103, 6114,
273 6120, 6129, 6135, 6158, 6164, 6173, 6179, 6190,
274 6196, 6205, 6211, 6231, 6237, 6246, 6252, 6263,
275 6269, 6278, 6284, 6309, 6315, 6324, 6330, 6341,
276 6347, 6356, 6362, 6382, 6388, 6397, 6403, 6414,
277 6420, 6429, 6435, 5303, 5309, 5318, 5324, 5335,
278 5341, 5350, 5356, 5376, 5382, 5391, 5397, 5408,
279 5414, 5423, 5429, 5454, 5460, 5469, 5475, 5486,
280 5492, 5501, 5507, 5527, 5533, 5542, 5548, 5559,
281 5565, 5574, 5580, 5603, 5609, 5618, 5624, 5635,
282 5641, 5650, 5656, 5676, 5682, 5691, 5697, 5708,
283 5714, 5723, 5729, 5754, 5760, 5769, 5775, 5786,
284 5792, 5801, 5807, 5827, 5833, 5842, 5848, 5859,
285 5865, 5874, 5880, 5744, 5750, 5759, 5765, 5776,
286 5782, 5791, 5797, 5817, 5823, 5832, 5838, 5849,
287 5855, 5864, 5870, 5895, 5901, 5910, 5916, 5927,
288 5933, 5942, 5948, 5968, 5974, 5983, 5989, 6000,
289 6006, 6015, 6021, 6044, 6050, 6059, 6065, 6076,
290 6082, 6091, 6097, 6117, 6123, 6132, 6138, 6149,
291 6155, 6164, 6170, 6195, 6201, 6210, 6216, 6227,
292 6233, 6242, 6248, 6268, 6274, 6283, 6289, 6300,
293 6306, 6315, 6321, 6116, 6122, 6131, 6137, 6148,
294 6154, 6163, 6169, 6189, 6195, 6204, 6210, 6221,
295 6227, 6236, 6242, 6267, 6273, 6282, 6288, 6299,
296 6305, 6314, 6320, 6340, 6346, 6355, 6361, 6372,
297 6378, 6387, 6393, 6416, 6422, 6431, 6437, 6448,
298 6454, 6463, 6469, 6489, 6495, 6504, 6510, 6521,
299 6527, 6536, 6542, 6567, 6573, 6582, 6588, 6599,
300 6605, 6614, 6620, 6640, 6646, 6655, 6661, 6672,
301 6678, 6687, 6693, 6557, 6563, 6572, 6578, 6589,
302 6595, 6604, 6610, 6630, 6636, 6645, 6651, 6662,
303 6668, 6677, 6683, 6708, 6714, 6723, 6729, 6740,
304 6746, 6755, 6761, 6781, 6787, 6796, 6802, 6813,
305 6819, 6828, 6834, 6857, 6863, 6872, 6878, 6889,
306 6895, 6904, 6910, 6930, 6936, 6945, 6951, 6962,
307 6968, 6977, 6983, 7008, 7014, 7023, 7029, 7040,
308 7046, 7055, 7061, 7081, 7087, 7096, 7102, 7113,
309 7119, 7128, 7134, 6392, 6398, 6407, 6413, 6424,
310 6430, 6439, 6445, 6465, 6471, 6480, 6486, 6497,
311 6503, 6512, 6518, 6543, 6549, 6558, 6564, 6575,
312 6581, 6590, 6596, 6616, 6622, 6631, 6637, 6648,
313 6654, 6663, 6669, 6692, 6698, 6707, 6713, 6724,
314 6730, 6739, 6745, 6765, 6771, 6780, 6786, 6797,
315 6803, 6812, 6818, 6843, 6849, 6858, 6864, 6875,
316 6881, 6890, 6896, 6916, 6922, 6931, 6937, 6948,
317 6954, 6963, 6969, 6833, 6839, 6848, 6854, 6865,
318 6871, 6880, 6886, 6906, 6912, 6921, 6927, 6938,
319 6944, 6953, 6959, 6984, 6990, 6999, 7005, 7016,
320 7022, 7031, 7037, 7057, 7063, 7072, 7078, 7089,
321 7095, 7104, 7110, 7133, 7139, 7148, 7154, 7165,
322 7171, 7180, 7186, 7206, 7212, 7221, 7227, 7238,
323 7244, 7253, 7259, 7284, 7290, 7299, 7305, 7316,
324 7322, 7331, 7337, 7357, 7363, 7372, 7378, 7389,
325 7395, 7404, 7410, 7205, 7211, 7220, 7226, 7237,
326 7243, 7252, 7258, 7278, 7284, 7293, 7299, 7310,
327 7316, 7325, 7331, 7356, 7362, 7371, 7377, 7388,
328 7394, 7403, 7409, 7429, 7435, 7444, 7450, 7461,
329 7467, 7476, 7482, 7505, 7511, 7520, 7526, 7537,
330 7543, 7552, 7558, 7578, 7584, 7593, 7599, 7610,
331 7616, 7625, 7631, 7656, 7662, 7671, 7677, 7688,
332 7694, 7703, 7709, 7729, 7735, 7744, 7750, 7761
333 };
334
VariableLevelCost(int level,const uint8_t probas[NUM_PROBAS])335 static int VariableLevelCost(int level, const uint8_t probas[NUM_PROBAS]) {
336 int pattern = VP8LevelCodes[level - 1][0];
337 int bits = VP8LevelCodes[level - 1][1];
338 int cost = 0;
339 int i;
340 for (i = 2; pattern; ++i) {
341 if (pattern & 1) {
342 cost += VP8BitCost(bits & 1, probas[i]);
343 }
344 bits >>= 1;
345 pattern >>= 1;
346 }
347 return cost;
348 }
349
350 //------------------------------------------------------------------------------
351 // Pre-calc level costs once for all
352
VP8CalculateLevelCosts(VP8Proba * const proba)353 void VP8CalculateLevelCosts(VP8Proba* const proba) {
354 int ctype, band, ctx;
355
356 if (!proba->dirty_) return; // nothing to do.
357
358 for (ctype = 0; ctype < NUM_TYPES; ++ctype) {
359 for (band = 0; band < NUM_BANDS; ++band) {
360 for (ctx = 0; ctx < NUM_CTX; ++ctx) {
361 const uint8_t* const p = proba->coeffs_[ctype][band][ctx];
362 uint16_t* const table = proba->level_cost_[ctype][band][ctx];
363 const int cost0 = (ctx > 0) ? VP8BitCost(1, p[0]) : 0;
364 const int cost_base = VP8BitCost(1, p[1]) + cost0;
365 int v;
366 table[0] = VP8BitCost(0, p[1]) + cost0;
367 for (v = 1; v <= MAX_VARIABLE_LEVEL; ++v) {
368 table[v] = cost_base + VariableLevelCost(v, p);
369 }
370 // Starting at level 67 and up, the variable part of the cost is
371 // actually constant.
372 }
373 }
374 }
375 proba->dirty_ = 0;
376 }
377
378 //------------------------------------------------------------------------------
379 // Mode cost tables.
380
381 // These are the fixed probabilities (in the coding trees) turned into bit-cost
382 // by calling VP8BitCost().
383 const uint16_t VP8FixedCostsUV[4] = { 302, 984, 439, 642 };
384 // note: these values include the fixed VP8BitCost(1, 145) mode selection cost.
385 const uint16_t VP8FixedCostsI16[4] = { 663, 919, 872, 919 };
386 const uint16_t VP8FixedCostsI4[NUM_BMODES][NUM_BMODES][NUM_BMODES] = {
387 { { 40, 1151, 1723, 1874, 2103, 2019, 1628, 1777, 2226, 2137 },
388 { 192, 469, 1296, 1308, 1849, 1794, 1781, 1703, 1713, 1522 },
389 { 142, 910, 762, 1684, 1849, 1576, 1460, 1305, 1801, 1657 },
390 { 559, 641, 1370, 421, 1182, 1569, 1612, 1725, 863, 1007 },
391 { 299, 1059, 1256, 1108, 636, 1068, 1581, 1883, 869, 1142 },
392 { 277, 1111, 707, 1362, 1089, 672, 1603, 1541, 1545, 1291 },
393 { 214, 781, 1609, 1303, 1632, 2229, 726, 1560, 1713, 918 },
394 { 152, 1037, 1046, 1759, 1983, 2174, 1358, 742, 1740, 1390 },
395 { 512, 1046, 1420, 753, 752, 1297, 1486, 1613, 460, 1207 },
396 { 424, 827, 1362, 719, 1462, 1202, 1199, 1476, 1199, 538 } },
397 { { 240, 402, 1134, 1491, 1659, 1505, 1517, 1555, 1979, 2099 },
398 { 467, 242, 960, 1232, 1714, 1620, 1834, 1570, 1676, 1391 },
399 { 500, 455, 463, 1507, 1699, 1282, 1564, 982, 2114, 2114 },
400 { 672, 643, 1372, 331, 1589, 1667, 1453, 1938, 996, 876 },
401 { 458, 783, 1037, 911, 738, 968, 1165, 1518, 859, 1033 },
402 { 504, 815, 504, 1139, 1219, 719, 1506, 1085, 1268, 1268 },
403 { 333, 630, 1445, 1239, 1883, 3672, 799, 1548, 1865, 598 },
404 { 399, 644, 746, 1342, 1856, 1350, 1493, 613, 1855, 1015 },
405 { 622, 749, 1205, 608, 1066, 1408, 1290, 1406, 546, 971 },
406 { 500, 753, 1041, 668, 1230, 1617, 1297, 1425, 1383, 523 } },
407 { { 394, 553, 523, 1502, 1536, 981, 1608, 1142, 1666, 2181 },
408 { 655, 430, 375, 1411, 1861, 1220, 1677, 1135, 1978, 1553 },
409 { 690, 640, 245, 1954, 2070, 1194, 1528, 982, 1972, 2232 },
410 { 559, 834, 741, 867, 1131, 980, 1225, 852, 1092, 784 },
411 { 690, 875, 516, 959, 673, 894, 1056, 1190, 1528, 1126 },
412 { 740, 951, 384, 1277, 1177, 492, 1579, 1155, 1846, 1513 },
413 { 323, 775, 1062, 1776, 3062, 1274, 813, 1188, 1372, 655 },
414 { 488, 971, 484, 1767, 1515, 1775, 1115, 503, 1539, 1461 },
415 { 740, 1006, 998, 709, 851, 1230, 1337, 788, 741, 721 },
416 { 522, 1073, 573, 1045, 1346, 887, 1046, 1146, 1203, 697 } },
417 { { 105, 864, 1442, 1009, 1934, 1840, 1519, 1920, 1673, 1579 },
418 { 534, 305, 1193, 683, 1388, 2164, 1802, 1894, 1264, 1170 },
419 { 305, 518, 877, 1108, 1426, 3215, 1425, 1064, 1320, 1242 },
420 { 683, 732, 1927, 257, 1493, 2048, 1858, 1552, 1055, 947 },
421 { 394, 814, 1024, 660, 959, 1556, 1282, 1289, 893, 1047 },
422 { 528, 615, 996, 940, 1201, 635, 1094, 2515, 803, 1358 },
423 { 347, 614, 1609, 1187, 3133, 1345, 1007, 1339, 1017, 667 },
424 { 218, 740, 878, 1605, 3650, 3650, 1345, 758, 1357, 1617 },
425 { 672, 750, 1541, 558, 1257, 1599, 1870, 2135, 402, 1087 },
426 { 592, 684, 1161, 430, 1092, 1497, 1475, 1489, 1095, 822 } },
427 { { 228, 1056, 1059, 1368, 752, 982, 1512, 1518, 987, 1782 },
428 { 494, 514, 818, 942, 965, 892, 1610, 1356, 1048, 1363 },
429 { 512, 648, 591, 1042, 761, 991, 1196, 1454, 1309, 1463 },
430 { 683, 749, 1043, 676, 841, 1396, 1133, 1138, 654, 939 },
431 { 622, 1101, 1126, 994, 361, 1077, 1203, 1318, 877, 1219 },
432 { 631, 1068, 857, 1650, 651, 477, 1650, 1419, 828, 1170 },
433 { 555, 727, 1068, 1335, 3127, 1339, 820, 1331, 1077, 429 },
434 { 504, 879, 624, 1398, 889, 889, 1392, 808, 891, 1406 },
435 { 683, 1602, 1289, 977, 578, 983, 1280, 1708, 406, 1122 },
436 { 399, 865, 1433, 1070, 1072, 764, 968, 1477, 1223, 678 } },
437 { { 333, 760, 935, 1638, 1010, 529, 1646, 1410, 1472, 2219 },
438 { 512, 494, 750, 1160, 1215, 610, 1870, 1868, 1628, 1169 },
439 { 572, 646, 492, 1934, 1208, 603, 1580, 1099, 1398, 1995 },
440 { 786, 789, 942, 581, 1018, 951, 1599, 1207, 731, 768 },
441 { 690, 1015, 672, 1078, 582, 504, 1693, 1438, 1108, 2897 },
442 { 768, 1267, 571, 2005, 1243, 244, 2881, 1380, 1786, 1453 },
443 { 452, 899, 1293, 903, 1311, 3100, 465, 1311, 1319, 813 },
444 { 394, 927, 942, 1103, 1358, 1104, 946, 593, 1363, 1109 },
445 { 559, 1005, 1007, 1016, 658, 1173, 1021, 1164, 623, 1028 },
446 { 564, 796, 632, 1005, 1014, 863, 2316, 1268, 938, 764 } },
447 { { 266, 606, 1098, 1228, 1497, 1243, 948, 1030, 1734, 1461 },
448 { 366, 585, 901, 1060, 1407, 1247, 876, 1134, 1620, 1054 },
449 { 452, 565, 542, 1729, 1479, 1479, 1016, 886, 2938, 1150 },
450 { 555, 1088, 1533, 950, 1354, 895, 834, 1019, 1021, 496 },
451 { 704, 815, 1193, 971, 973, 640, 1217, 2214, 832, 578 },
452 { 672, 1245, 579, 871, 875, 774, 872, 1273, 1027, 949 },
453 { 296, 1134, 2050, 1784, 1636, 3425, 442, 1550, 2076, 722 },
454 { 342, 982, 1259, 1846, 1848, 1848, 622, 568, 1847, 1052 },
455 { 555, 1064, 1304, 828, 746, 1343, 1075, 1329, 1078, 494 },
456 { 288, 1167, 1285, 1174, 1639, 1639, 833, 2254, 1304, 509 } },
457 { { 342, 719, 767, 1866, 1757, 1270, 1246, 550, 1746, 2151 },
458 { 483, 653, 694, 1509, 1459, 1410, 1218, 507, 1914, 1266 },
459 { 488, 757, 447, 2979, 1813, 1268, 1654, 539, 1849, 2109 },
460 { 522, 1097, 1085, 851, 1365, 1111, 851, 901, 961, 605 },
461 { 709, 716, 841, 728, 736, 945, 941, 862, 2845, 1057 },
462 { 512, 1323, 500, 1336, 1083, 681, 1342, 717, 1604, 1350 },
463 { 452, 1155, 1372, 1900, 1501, 3290, 311, 944, 1919, 922 },
464 { 403, 1520, 977, 2132, 1733, 3522, 1076, 276, 3335, 1547 },
465 { 559, 1374, 1101, 615, 673, 2462, 974, 795, 984, 984 },
466 { 547, 1122, 1062, 812, 1410, 951, 1140, 622, 1268, 651 } },
467 { { 165, 982, 1235, 938, 1334, 1366, 1659, 1578, 964, 1612 },
468 { 592, 422, 925, 847, 1139, 1112, 1387, 2036, 861, 1041 },
469 { 403, 837, 732, 770, 941, 1658, 1250, 809, 1407, 1407 },
470 { 896, 874, 1071, 381, 1568, 1722, 1437, 2192, 480, 1035 },
471 { 640, 1098, 1012, 1032, 684, 1382, 1581, 2106, 416, 865 },
472 { 559, 1005, 819, 914, 710, 770, 1418, 920, 838, 1435 },
473 { 415, 1258, 1245, 870, 1278, 3067, 770, 1021, 1287, 522 },
474 { 406, 990, 601, 1009, 1265, 1265, 1267, 759, 1017, 1277 },
475 { 968, 1182, 1329, 788, 1032, 1292, 1705, 1714, 203, 1403 },
476 { 732, 877, 1279, 471, 901, 1161, 1545, 1294, 755, 755 } },
477 { { 111, 931, 1378, 1185, 1933, 1648, 1148, 1714, 1873, 1307 },
478 { 406, 414, 1030, 1023, 1910, 1404, 1313, 1647, 1509, 793 },
479 { 342, 640, 575, 1088, 1241, 1349, 1161, 1350, 1756, 1502 },
480 { 559, 766, 1185, 357, 1682, 1428, 1329, 1897, 1219, 802 },
481 { 473, 909, 1164, 771, 719, 2508, 1427, 1432, 722, 782 },
482 { 342, 892, 785, 1145, 1150, 794, 1296, 1550, 973, 1057 },
483 { 208, 1036, 1326, 1343, 1606, 3395, 815, 1455, 1618, 712 },
484 { 228, 928, 890, 1046, 3499, 1711, 994, 829, 1720, 1318 },
485 { 768, 724, 1058, 636, 991, 1075, 1319, 1324, 616, 825 },
486 { 305, 1167, 1358, 899, 1587, 1587, 987, 1988, 1332, 501 } }
487 };
488
489 //------------------------------------------------------------------------------
490 // Mode costs
491
GetResidualCost(int ctx0,const VP8Residual * const res)492 static int GetResidualCost(int ctx0, const VP8Residual* const res) {
493 int n = res->first;
494 // should be prob[VP8EncBands[n]], but it's equivalent for n=0 or 1
495 const int p0 = res->prob[n][ctx0][0];
496 const uint16_t* t = res->cost[n][ctx0];
497 // bit_cost(1, p0) is already incorporated in t[] tables, but only if ctx != 0
498 // (as required by the syntax). For ctx0 == 0, we need to add it here or it'll
499 // be missing during the loop.
500 int cost = (ctx0 == 0) ? VP8BitCost(1, p0) : 0;
501
502 if (res->last < 0) {
503 return VP8BitCost(0, p0);
504 }
505 for (; n < res->last; ++n) {
506 const int v = abs(res->coeffs[n]);
507 const int b = VP8EncBands[n + 1];
508 const int ctx = (v >= 2) ? 2 : v;
509 cost += VP8LevelCost(t, v);
510 t = res->cost[b][ctx];
511 }
512 // Last coefficient is always non-zero
513 {
514 const int v = abs(res->coeffs[n]);
515 assert(v != 0);
516 cost += VP8LevelCost(t, v);
517 if (n < 15) {
518 const int b = VP8EncBands[n + 1];
519 const int ctx = (v == 1) ? 1 : 2;
520 const int last_p0 = res->prob[b][ctx][0];
521 cost += VP8BitCost(0, last_p0);
522 }
523 }
524 return cost;
525 }
526
527 //------------------------------------------------------------------------------
528 // init function
529
530 #if defined(WEBP_USE_MIPS32)
531 extern int VP8GetResidualCostMIPS32(int ctx0, const VP8Residual* const res);
532 #endif // WEBP_USE_MIPS32
533
534 // TODO(skal): this, and GetResidualCost(), should probably go somewhere
535 // under src/dsp/ at some point.
536 VP8GetResidualCostFunc VP8GetResidualCost;
537
VP8GetResidualCostInit(void)538 void VP8GetResidualCostInit(void) {
539 VP8GetResidualCost = GetResidualCost;
540 if (VP8GetCPUInfo != NULL) {
541 #if defined(WEBP_USE_MIPS32)
542 if (VP8GetCPUInfo(kMIPS32)) {
543 VP8GetResidualCost = VP8GetResidualCostMIPS32;
544 }
545 #endif
546 }
547 }
548
549 //------------------------------------------------------------------------------
550 // helper functions for residuals struct VP8Residual.
551
VP8InitResidual(int first,int coeff_type,VP8Encoder * const enc,VP8Residual * const res)552 void VP8InitResidual(int first, int coeff_type,
553 VP8Encoder* const enc, VP8Residual* const res) {
554 res->coeff_type = coeff_type;
555 res->prob = enc->proba_.coeffs_[coeff_type];
556 res->stats = enc->proba_.stats_[coeff_type];
557 res->cost = enc->proba_.level_cost_[coeff_type];
558 res->first = first;
559 }
560
SetResidualCoeffs(const int16_t * const coeffs,VP8Residual * const res)561 static void SetResidualCoeffs(const int16_t* const coeffs,
562 VP8Residual* const res) {
563 int n;
564 res->last = -1;
565 assert(res->first == 0 || coeffs[0] == 0);
566 for (n = 15; n >= 0; --n) {
567 if (coeffs[n]) {
568 res->last = n;
569 break;
570 }
571 }
572 res->coeffs = coeffs;
573 }
574
575 //------------------------------------------------------------------------------
576 // init function
577
578 #if defined(WEBP_USE_SSE2)
579 extern void VP8SetResidualCoeffsSSE2(const int16_t* const coeffs,
580 VP8Residual* const res);
581 #endif // WEBP_USE_SSE2
582
583 VP8SetResidualCoeffsFunc VP8SetResidualCoeffs;
584
VP8SetResidualCoeffsInit(void)585 void VP8SetResidualCoeffsInit(void) {
586 VP8SetResidualCoeffs = SetResidualCoeffs;
587 if (VP8GetCPUInfo != NULL) {
588 #if defined(WEBP_USE_SSE2)
589 if (VP8GetCPUInfo(kSSE2)) {
590 VP8SetResidualCoeffs = VP8SetResidualCoeffsSSE2;
591 }
592 #endif
593 }
594 }
595
596 //------------------------------------------------------------------------------
597 // Mode costs
598
VP8GetCostLuma4(VP8EncIterator * const it,const int16_t levels[16])599 int VP8GetCostLuma4(VP8EncIterator* const it, const int16_t levels[16]) {
600 const int x = (it->i4_ & 3), y = (it->i4_ >> 2);
601 VP8Residual res;
602 VP8Encoder* const enc = it->enc_;
603 int R = 0;
604 int ctx;
605
606 VP8InitResidual(0, 3, enc, &res);
607 ctx = it->top_nz_[x] + it->left_nz_[y];
608 VP8SetResidualCoeffs(levels, &res);
609 R += VP8GetResidualCost(ctx, &res);
610 return R;
611 }
612
VP8GetCostLuma16(VP8EncIterator * const it,const VP8ModeScore * const rd)613 int VP8GetCostLuma16(VP8EncIterator* const it, const VP8ModeScore* const rd) {
614 VP8Residual res;
615 VP8Encoder* const enc = it->enc_;
616 int x, y;
617 int R = 0;
618
619 VP8IteratorNzToBytes(it); // re-import the non-zero context
620
621 // DC
622 VP8InitResidual(0, 1, enc, &res);
623 VP8SetResidualCoeffs(rd->y_dc_levels, &res);
624 R += VP8GetResidualCost(it->top_nz_[8] + it->left_nz_[8], &res);
625
626 // AC
627 VP8InitResidual(1, 0, enc, &res);
628 for (y = 0; y < 4; ++y) {
629 for (x = 0; x < 4; ++x) {
630 const int ctx = it->top_nz_[x] + it->left_nz_[y];
631 VP8SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res);
632 R += VP8GetResidualCost(ctx, &res);
633 it->top_nz_[x] = it->left_nz_[y] = (res.last >= 0);
634 }
635 }
636 return R;
637 }
638
VP8GetCostUV(VP8EncIterator * const it,const VP8ModeScore * const rd)639 int VP8GetCostUV(VP8EncIterator* const it, const VP8ModeScore* const rd) {
640 VP8Residual res;
641 VP8Encoder* const enc = it->enc_;
642 int ch, x, y;
643 int R = 0;
644
645 VP8IteratorNzToBytes(it); // re-import the non-zero context
646
647 VP8InitResidual(0, 2, enc, &res);
648 for (ch = 0; ch <= 2; ch += 2) {
649 for (y = 0; y < 2; ++y) {
650 for (x = 0; x < 2; ++x) {
651 const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y];
652 VP8SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res);
653 R += VP8GetResidualCost(ctx, &res);
654 it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] = (res.last >= 0);
655 }
656 }
657 }
658 return R;
659 }
660
661
662 //------------------------------------------------------------------------------
663 // Recording of token probabilities.
664
665 // Record proba context used
Record(int bit,proba_t * const stats)666 static int Record(int bit, proba_t* const stats) {
667 proba_t p = *stats;
668 if (p >= 0xffff0000u) { // an overflow is inbound.
669 p = ((p + 1u) >> 1) & 0x7fff7fffu; // -> divide the stats by 2.
670 }
671 // record bit count (lower 16 bits) and increment total count (upper 16 bits).
672 p += 0x00010000u + bit;
673 *stats = p;
674 return bit;
675 }
676
677 // We keep the table-free variant around for reference, in case.
678 #define USE_LEVEL_CODE_TABLE
679
680 // Simulate block coding, but only record statistics.
681 // Note: no need to record the fixed probas.
VP8RecordCoeffs(int ctx,const VP8Residual * const res)682 int VP8RecordCoeffs(int ctx, const VP8Residual* const res) {
683 int n = res->first;
684 // should be stats[VP8EncBands[n]], but it's equivalent for n=0 or 1
685 proba_t* s = res->stats[n][ctx];
686 if (res->last < 0) {
687 Record(0, s + 0);
688 return 0;
689 }
690 while (n <= res->last) {
691 int v;
692 Record(1, s + 0); // order of record doesn't matter
693 while ((v = res->coeffs[n++]) == 0) {
694 Record(0, s + 1);
695 s = res->stats[VP8EncBands[n]][0];
696 }
697 Record(1, s + 1);
698 if (!Record(2u < (unsigned int)(v + 1), s + 2)) { // v = -1 or 1
699 s = res->stats[VP8EncBands[n]][1];
700 } else {
701 v = abs(v);
702 #if !defined(USE_LEVEL_CODE_TABLE)
703 if (!Record(v > 4, s + 3)) {
704 if (Record(v != 2, s + 4))
705 Record(v == 4, s + 5);
706 } else if (!Record(v > 10, s + 6)) {
707 Record(v > 6, s + 7);
708 } else if (!Record((v >= 3 + (8 << 2)), s + 8)) {
709 Record((v >= 3 + (8 << 1)), s + 9);
710 } else {
711 Record((v >= 3 + (8 << 3)), s + 10);
712 }
713 #else
714 if (v > MAX_VARIABLE_LEVEL) {
715 v = MAX_VARIABLE_LEVEL;
716 }
717
718 {
719 const int bits = VP8LevelCodes[v - 1][1];
720 int pattern = VP8LevelCodes[v - 1][0];
721 int i;
722 for (i = 0; (pattern >>= 1) != 0; ++i) {
723 const int mask = 2 << i;
724 if (pattern & 1) Record(!!(bits & mask), s + 3 + i);
725 }
726 }
727 #endif
728 s = res->stats[VP8EncBands[n]][2];
729 }
730 }
731 if (n < 16) Record(0, s + 0);
732 return 1;
733 }
734
735 //------------------------------------------------------------------------------
736