granicus.if.org Git - libvpx/blob - vp9/encoder/vp9_tokenize.c

   1 /*
   2  *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  11 #include <assert.h>
  12 #include <math.h>
  13 #include <stdio.h>
  14 #include <string.h>
  15
  16 #include "vpx_mem/vpx_mem.h"
  17
  18 #include "vp9/common/vp9_entropy.h"
  19 #include "vp9/common/vp9_pred_common.h"
  20 #include "vp9/common/vp9_scan.h"
  21 #include "vp9/common/vp9_seg_common.h"
  22
  23 #include "vp9/encoder/vp9_cost.h"
  24 #include "vp9/encoder/vp9_encoder.h"
  25 #include "vp9/encoder/vp9_tokenize.h"
  26
  27 static const TOKENVALUE dct_cat_lt_10_value_tokens[] = {
  28   {9, 63}, {9, 61}, {9, 59}, {9, 57}, {9, 55}, {9, 53}, {9, 51}, {9, 49},
  29   {9, 47}, {9, 45}, {9, 43}, {9, 41}, {9, 39}, {9, 37}, {9, 35}, {9, 33},
  30   {9, 31}, {9, 29}, {9, 27}, {9, 25}, {9, 23}, {9, 21}, {9, 19}, {9, 17},
  31   {9, 15}, {9, 13}, {9, 11}, {9, 9}, {9, 7}, {9, 5}, {9, 3}, {9, 1},
  32   {8, 31}, {8, 29}, {8, 27}, {8, 25}, {8, 23}, {8, 21},
  33   {8, 19}, {8, 17}, {8, 15}, {8, 13}, {8, 11}, {8, 9},
  34   {8, 7}, {8, 5}, {8, 3}, {8, 1},
  35   {7, 15}, {7, 13}, {7, 11}, {7, 9}, {7, 7}, {7, 5}, {7, 3}, {7, 1},
  36   {6, 7}, {6, 5}, {6, 3}, {6, 1}, {5, 3}, {5, 1},
  37   {4, 1}, {3, 1}, {2, 1}, {1, 1}, {0, 0},
  38   {1, 0},  {2, 0}, {3, 0}, {4, 0},
  39   {5, 0}, {5, 2}, {6, 0}, {6, 2}, {6, 4}, {6, 6},
  40   {7, 0}, {7, 2}, {7, 4}, {7, 6}, {7, 8}, {7, 10}, {7, 12}, {7, 14},
  41   {8, 0}, {8, 2}, {8, 4}, {8, 6}, {8, 8}, {8, 10}, {8, 12},
  42   {8, 14}, {8, 16}, {8, 18}, {8, 20}, {8, 22}, {8, 24},
  43   {8, 26}, {8, 28}, {8, 30}, {9, 0}, {9, 2},
  44   {9, 4}, {9, 6}, {9, 8}, {9, 10}, {9, 12}, {9, 14}, {9, 16},
  45   {9, 18}, {9, 20}, {9, 22}, {9, 24}, {9, 26}, {9, 28},
  46   {9, 30}, {9, 32}, {9, 34}, {9, 36}, {9, 38}, {9, 40},
  47   {9, 42}, {9, 44}, {9, 46}, {9, 48}, {9, 50}, {9, 52},
  48   {9, 54}, {9, 56}, {9, 58}, {9, 60}, {9, 62}
  49 };
  50 const TOKENVALUE *vp9_dct_cat_lt_10_value_tokens = dct_cat_lt_10_value_tokens +
  51     (sizeof(dct_cat_lt_10_value_tokens) / sizeof(*dct_cat_lt_10_value_tokens))
  52     / 2;
  53
  54 // Array indices are identical to previously-existing CONTEXT_NODE indices
  55 const vpx_tree_index vp9_coef_tree[TREE_SIZE(ENTROPY_TOKENS)] = {
  56   -EOB_TOKEN, 2,                       // 0  = EOB
  57   -ZERO_TOKEN, 4,                      // 1  = ZERO
  58   -ONE_TOKEN, 6,                       // 2  = ONE
  59   8, 12,                               // 3  = LOW_VAL
  60   -TWO_TOKEN, 10,                      // 4  = TWO
  61   -THREE_TOKEN, -FOUR_TOKEN,           // 5  = THREE
  62   14, 16,                              // 6  = HIGH_LOW
  63   -CATEGORY1_TOKEN, -CATEGORY2_TOKEN,  // 7  = CAT_ONE
  64   18, 20,                              // 8  = CAT_THREEFOUR
  65   -CATEGORY3_TOKEN, -CATEGORY4_TOKEN,  // 9  = CAT_THREE
  66   -CATEGORY5_TOKEN, -CATEGORY6_TOKEN   // 10 = CAT_FIVE
  67 };
  68
  69 static const int16_t zero_cost[] = {0};
  70 static const int16_t sign_cost[1] = {512};
  71 static const int16_t cat1_cost[1 << 1] = {864, 1229};
  72 static const int16_t cat2_cost[1 << 2] = {1256, 1453, 1696, 1893};
  73 static const int16_t cat3_cost[1 << 3] = {1652, 1791, 1884, 2023,
  74                                           2195, 2334, 2427, 2566};
  75 static const int16_t cat4_cost[1 << 4] = {2079, 2160, 2218, 2299, 2395, 2476,
  76                                           2534, 2615, 2661, 2742, 2800, 2881,
  77                                           2977, 3058, 3116, 3197};
  78 static const int16_t cat5_cost[1 << 5] = {
  79     2553, 2576, 2622, 2645, 2703, 2726, 2772, 2795, 2894, 2917, 2963,
  80     2986, 3044, 3067, 3113, 3136, 3190, 3213, 3259, 3282, 3340, 3363,
  81     3409, 3432, 3531, 3554, 3600, 3623, 3681, 3704, 3750, 3773};
  82 const int16_t vp9_cat6_low_cost[256] = {
  83     3378, 3390, 3401, 3413, 3435, 3447, 3458, 3470, 3517, 3529, 3540, 3552,
  84     3574, 3586, 3597, 3609, 3671, 3683, 3694, 3706, 3728, 3740, 3751, 3763,
  85     3810, 3822, 3833, 3845, 3867, 3879, 3890, 3902, 3973, 3985, 3996, 4008,
  86     4030, 4042, 4053, 4065, 4112, 4124, 4135, 4147, 4169, 4181, 4192, 4204,
  87     4266, 4278, 4289, 4301, 4323, 4335, 4346, 4358, 4405, 4417, 4428, 4440,
  88     4462, 4474, 4485, 4497, 4253, 4265, 4276, 4288, 4310, 4322, 4333, 4345,
  89     4392, 4404, 4415, 4427, 4449, 4461, 4472, 4484, 4546, 4558, 4569, 4581,
  90     4603, 4615, 4626, 4638, 4685, 4697, 4708, 4720, 4742, 4754, 4765, 4777,
  91     4848, 4860, 4871, 4883, 4905, 4917, 4928, 4940, 4987, 4999, 5010, 5022,
  92     5044, 5056, 5067, 5079, 5141, 5153, 5164, 5176, 5198, 5210, 5221, 5233,
  93     5280, 5292, 5303, 5315, 5337, 5349, 5360, 5372, 4988, 5000, 5011, 5023,
  94     5045, 5057, 5068, 5080, 5127, 5139, 5150, 5162, 5184, 5196, 5207, 5219,
  95     5281, 5293, 5304, 5316, 5338, 5350, 5361, 5373, 5420, 5432, 5443, 5455,
  96     5477, 5489, 5500, 5512, 5583, 5595, 5606, 5618, 5640, 5652, 5663, 5675,
  97     5722, 5734, 5745, 5757, 5779, 5791, 5802, 5814, 5876, 5888, 5899, 5911,
  98     5933, 5945, 5956, 5968, 6015, 6027, 6038, 6050, 6072, 6084, 6095, 6107,
  99     5863, 5875, 5886, 5898, 5920, 5932, 5943, 5955, 6002, 6014, 6025, 6037,
 100     6059, 6071, 6082, 6094, 6156, 6168, 6179, 6191, 6213, 6225, 6236, 6248,
 101     6295, 6307, 6318, 6330, 6352, 6364, 6375, 6387, 6458, 6470, 6481, 6493,
 102     6515, 6527, 6538, 6550, 6597, 6609, 6620, 6632, 6654, 6666, 6677, 6689,
 103     6751, 6763, 6774, 6786, 6808, 6820, 6831, 6843, 6890, 6902, 6913, 6925,
 104     6947, 6959, 6970, 6982};
 105 const int vp9_cat6_high_cost[64] = {
 106     88,    2251,  2727,  4890,  3148,  5311,  5787,  7950,  3666,  5829,  6305,
 107     8468,  6726,  8889,  9365,  11528, 3666,  5829,  6305,  8468,  6726,  8889,
 108     9365,  11528, 7244,  9407,  9883,  12046, 10304, 12467, 12943, 15106, 3666,
 109     5829,  6305,  8468,  6726,  8889,  9365,  11528, 7244,  9407,  9883,  12046,
 110     10304, 12467, 12943, 15106, 7244,  9407,  9883,  12046, 10304, 12467, 12943,
 111     15106, 10822, 12985, 13461, 15624, 13882, 16045, 16521, 18684};
 112
 113 #if CONFIG_VP9_HIGHBITDEPTH
 114 const int vp9_cat6_high10_high_cost[256] = {
 115     94,    2257,  2733,  4896,  3154,  5317,  5793,  7956,  3672,  5835,  6311,
 116     8474,  6732,  8895,  9371,  11534, 3672,  5835,  6311,  8474,  6732,  8895,
 117     9371,  11534, 7250,  9413,  9889,  12052, 10310, 12473, 12949, 15112, 3672,
 118     5835,  6311,  8474,  6732,  8895,  9371,  11534, 7250,  9413,  9889,  12052,
 119     10310, 12473, 12949, 15112, 7250,  9413,  9889,  12052, 10310, 12473, 12949,
 120     15112, 10828, 12991, 13467, 15630, 13888, 16051, 16527, 18690, 4187,  6350,
 121     6826,  8989,  7247,  9410,  9886,  12049, 7765,  9928,  10404, 12567, 10825,
 122     12988, 13464, 15627, 7765,  9928,  10404, 12567, 10825, 12988, 13464, 15627,
 123     11343, 13506, 13982, 16145, 14403, 16566, 17042, 19205, 7765,  9928,  10404,
 124     12567, 10825, 12988, 13464, 15627, 11343, 13506, 13982, 16145, 14403, 16566,
 125     17042, 19205, 11343, 13506, 13982, 16145, 14403, 16566, 17042, 19205, 14921,
 126     17084, 17560, 19723, 17981, 20144, 20620, 22783, 4187,  6350,  6826,  8989,
 127     7247,  9410,  9886,  12049, 7765,  9928,  10404, 12567, 10825, 12988, 13464,
 128     15627, 7765,  9928,  10404, 12567, 10825, 12988, 13464, 15627, 11343, 13506,
 129     13982, 16145, 14403, 16566, 17042, 19205, 7765,  9928,  10404, 12567, 10825,
 130     12988, 13464, 15627, 11343, 13506, 13982, 16145, 14403, 16566, 17042, 19205,
 131     11343, 13506, 13982, 16145, 14403, 16566, 17042, 19205, 14921, 17084, 17560,
 132     19723, 17981, 20144, 20620, 22783, 8280,  10443, 10919, 13082, 11340, 13503,
 133     13979, 16142, 11858, 14021, 14497, 16660, 14918, 17081, 17557, 19720, 11858,
 134     14021, 14497, 16660, 14918, 17081, 17557, 19720, 15436, 17599, 18075, 20238,
 135     18496, 20659, 21135, 23298, 11858, 14021, 14497, 16660, 14918, 17081, 17557,
 136     19720, 15436, 17599, 18075, 20238, 18496, 20659, 21135, 23298, 15436, 17599,
 137     18075, 20238, 18496, 20659, 21135, 23298, 19014, 21177, 21653, 23816, 22074,
 138     24237, 24713, 26876};
 139 const int vp9_cat6_high12_high_cost[1024] = {
 140     100,   2263,  2739,  4902,  3160,  5323,  5799,  7962,  3678,  5841,  6317,
 141     8480,  6738,  8901,  9377,  11540, 3678,  5841,  6317,  8480,  6738,  8901,
 142     9377,  11540, 7256,  9419,  9895,  12058, 10316, 12479, 12955, 15118, 3678,
 143     5841,  6317,  8480,  6738,  8901,  9377,  11540, 7256,  9419,  9895,  12058,
 144     10316, 12479, 12955, 15118, 7256,  9419,  9895,  12058, 10316, 12479, 12955,
 145     15118, 10834, 12997, 13473, 15636, 13894, 16057, 16533, 18696, 4193,  6356,
 146     6832,  8995,  7253,  9416,  9892,  12055, 7771,  9934,  10410, 12573, 10831,
 147     12994, 13470, 15633, 7771,  9934,  10410, 12573, 10831, 12994, 13470, 15633,
 148     11349, 13512, 13988, 16151, 14409, 16572, 17048, 19211, 7771,  9934,  10410,
 149     12573, 10831, 12994, 13470, 15633, 11349, 13512, 13988, 16151, 14409, 16572,
 150     17048, 19211, 11349, 13512, 13988, 16151, 14409, 16572, 17048, 19211, 14927,
 151     17090, 17566, 19729, 17987, 20150, 20626, 22789, 4193,  6356,  6832,  8995,
 152     7253,  9416,  9892,  12055, 7771,  9934,  10410, 12573, 10831, 12994, 13470,
 153     15633, 7771,  9934,  10410, 12573, 10831, 12994, 13470, 15633, 11349, 13512,
 154     13988, 16151, 14409, 16572, 17048, 19211, 7771,  9934,  10410, 12573, 10831,
 155     12994, 13470, 15633, 11349, 13512, 13988, 16151, 14409, 16572, 17048, 19211,
 156     11349, 13512, 13988, 16151, 14409, 16572, 17048, 19211, 14927, 17090, 17566,
 157     19729, 17987, 20150, 20626, 22789, 8286,  10449, 10925, 13088, 11346, 13509,
 158     13985, 16148, 11864, 14027, 14503, 16666, 14924, 17087, 17563, 19726, 11864,
 159     14027, 14503, 16666, 14924, 17087, 17563, 19726, 15442, 17605, 18081, 20244,
 160     18502, 20665, 21141, 23304, 11864, 14027, 14503, 16666, 14924, 17087, 17563,
 161     19726, 15442, 17605, 18081, 20244, 18502, 20665, 21141, 23304, 15442, 17605,
 162     18081, 20244, 18502, 20665, 21141, 23304, 19020, 21183, 21659, 23822, 22080,
 163     24243, 24719, 26882, 4193,  6356,  6832,  8995,  7253,  9416,  9892,  12055,
 164     7771,  9934,  10410, 12573, 10831, 12994, 13470, 15633, 7771,  9934,  10410,
 165     12573, 10831, 12994, 13470, 15633, 11349, 13512, 13988, 16151, 14409, 16572,
 166     17048, 19211, 7771,  9934,  10410, 12573, 10831, 12994, 13470, 15633, 11349,
 167     13512, 13988, 16151, 14409, 16572, 17048, 19211, 11349, 13512, 13988, 16151,
 168     14409, 16572, 17048, 19211, 14927, 17090, 17566, 19729, 17987, 20150, 20626,
 169     22789, 8286,  10449, 10925, 13088, 11346, 13509, 13985, 16148, 11864, 14027,
 170     14503, 16666, 14924, 17087, 17563, 19726, 11864, 14027, 14503, 16666, 14924,
 171     17087, 17563, 19726, 15442, 17605, 18081, 20244, 18502, 20665, 21141, 23304,
 172     11864, 14027, 14503, 16666, 14924, 17087, 17563, 19726, 15442, 17605, 18081,
 173     20244, 18502, 20665, 21141, 23304, 15442, 17605, 18081, 20244, 18502, 20665,
 174     21141, 23304, 19020, 21183, 21659, 23822, 22080, 24243, 24719, 26882, 8286,
 175     10449, 10925, 13088, 11346, 13509, 13985, 16148, 11864, 14027, 14503, 16666,
 176     14924, 17087, 17563, 19726, 11864, 14027, 14503, 16666, 14924, 17087, 17563,
 177     19726, 15442, 17605, 18081, 20244, 18502, 20665, 21141, 23304, 11864, 14027,
 178     14503, 16666, 14924, 17087, 17563, 19726, 15442, 17605, 18081, 20244, 18502,
 179     20665, 21141, 23304, 15442, 17605, 18081, 20244, 18502, 20665, 21141, 23304,
 180     19020, 21183, 21659, 23822, 22080, 24243, 24719, 26882, 12379, 14542, 15018,
 181     17181, 15439, 17602, 18078, 20241, 15957, 18120, 18596, 20759, 19017, 21180,
 182     21656, 23819, 15957, 18120, 18596, 20759, 19017, 21180, 21656, 23819, 19535,
 183     21698, 22174, 24337, 22595, 24758, 25234, 27397, 15957, 18120, 18596, 20759,
 184     19017, 21180, 21656, 23819, 19535, 21698, 22174, 24337, 22595, 24758, 25234,
 185     27397, 19535, 21698, 22174, 24337, 22595, 24758, 25234, 27397, 23113, 25276,
 186     25752, 27915, 26173, 28336, 28812, 30975, 4193,  6356,  6832,  8995,  7253,
 187     9416,  9892,  12055, 7771,  9934,  10410, 12573, 10831, 12994, 13470, 15633,
 188     7771,  9934,  10410, 12573, 10831, 12994, 13470, 15633, 11349, 13512, 13988,
 189     16151, 14409, 16572, 17048, 19211, 7771,  9934,  10410, 12573, 10831, 12994,
 190     13470, 15633, 11349, 13512, 13988, 16151, 14409, 16572, 17048, 19211, 11349,
 191     13512, 13988, 16151, 14409, 16572, 17048, 19211, 14927, 17090, 17566, 19729,
 192     17987, 20150, 20626, 22789, 8286,  10449, 10925, 13088, 11346, 13509, 13985,
 193     16148, 11864, 14027, 14503, 16666, 14924, 17087, 17563, 19726, 11864, 14027,
 194     14503, 16666, 14924, 17087, 17563, 19726, 15442, 17605, 18081, 20244, 18502,
 195     20665, 21141, 23304, 11864, 14027, 14503, 16666, 14924, 17087, 17563, 19726,
 196     15442, 17605, 18081, 20244, 18502, 20665, 21141, 23304, 15442, 17605, 18081,
 197     20244, 18502, 20665, 21141, 23304, 19020, 21183, 21659, 23822, 22080, 24243,
 198     24719, 26882, 8286,  10449, 10925, 13088, 11346, 13509, 13985, 16148, 11864,
 199     14027, 14503, 16666, 14924, 17087, 17563, 19726, 11864, 14027, 14503, 16666,
 200     14924, 17087, 17563, 19726, 15442, 17605, 18081, 20244, 18502, 20665, 21141,
 201     23304, 11864, 14027, 14503, 16666, 14924, 17087, 17563, 19726, 15442, 17605,
 202     18081, 20244, 18502, 20665, 21141, 23304, 15442, 17605, 18081, 20244, 18502,
 203     20665, 21141, 23304, 19020, 21183, 21659, 23822, 22080, 24243, 24719, 26882,
 204     12379, 14542, 15018, 17181, 15439, 17602, 18078, 20241, 15957, 18120, 18596,
 205     20759, 19017, 21180, 21656, 23819, 15957, 18120, 18596, 20759, 19017, 21180,
 206     21656, 23819, 19535, 21698, 22174, 24337, 22595, 24758, 25234, 27397, 15957,
 207     18120, 18596, 20759, 19017, 21180, 21656, 23819, 19535, 21698, 22174, 24337,
 208     22595, 24758, 25234, 27397, 19535, 21698, 22174, 24337, 22595, 24758, 25234,
 209     27397, 23113, 25276, 25752, 27915, 26173, 28336, 28812, 30975, 8286,  10449,
 210     10925, 13088, 11346, 13509, 13985, 16148, 11864, 14027, 14503, 16666, 14924,
 211     17087, 17563, 19726, 11864, 14027, 14503, 16666, 14924, 17087, 17563, 19726,
 212     15442, 17605, 18081, 20244, 18502, 20665, 21141, 23304, 11864, 14027, 14503,
 213     16666, 14924, 17087, 17563, 19726, 15442, 17605, 18081, 20244, 18502, 20665,
 214     21141, 23304, 15442, 17605, 18081, 20244, 18502, 20665, 21141, 23304, 19020,
 215     21183, 21659, 23822, 22080, 24243, 24719, 26882, 12379, 14542, 15018, 17181,
 216     15439, 17602, 18078, 20241, 15957, 18120, 18596, 20759, 19017, 21180, 21656,
 217     23819, 15957, 18120, 18596, 20759, 19017, 21180, 21656, 23819, 19535, 21698,
 218     22174, 24337, 22595, 24758, 25234, 27397, 15957, 18120, 18596, 20759, 19017,
 219     21180, 21656, 23819, 19535, 21698, 22174, 24337, 22595, 24758, 25234, 27397,
 220     19535, 21698, 22174, 24337, 22595, 24758, 25234, 27397, 23113, 25276, 25752,
 221     27915, 26173, 28336, 28812, 30975, 12379, 14542, 15018, 17181, 15439, 17602,
 222     18078, 20241, 15957, 18120, 18596, 20759, 19017, 21180, 21656, 23819, 15957,
 223     18120, 18596, 20759, 19017, 21180, 21656, 23819, 19535, 21698, 22174, 24337,
 224     22595, 24758, 25234, 27397, 15957, 18120, 18596, 20759, 19017, 21180, 21656,
 225     23819, 19535, 21698, 22174, 24337, 22595, 24758, 25234, 27397, 19535, 21698,
 226     22174, 24337, 22595, 24758, 25234, 27397, 23113, 25276, 25752, 27915, 26173,
 227     28336, 28812, 30975, 16472, 18635, 19111, 21274, 19532, 21695, 22171, 24334,
 228     20050, 22213, 22689, 24852, 23110, 25273, 25749, 27912, 20050, 22213, 22689,
 229     24852, 23110, 25273, 25749, 27912, 23628, 25791, 26267, 28430, 26688, 28851,
 230     29327, 31490, 20050, 22213, 22689, 24852, 23110, 25273, 25749, 27912, 23628,
 231     25791, 26267, 28430, 26688, 28851, 29327, 31490, 23628, 25791, 26267, 28430,
 232     26688, 28851, 29327, 31490, 27206, 29369, 29845, 32008, 30266, 32429, 32905,
 233     35068};
 234 #endif
 235
 236 const vp9_extra_bit vp9_extra_bits[ENTROPY_TOKENS] = {
 237   {0, 0, 0, zero_cost},                          // ZERO_TOKEN
 238   {0, 0, 1, sign_cost},                          // ONE_TOKEN
 239   {0, 0, 2, sign_cost},                          // TWO_TOKEN
 240   {0, 0, 3, sign_cost},                          // THREE_TOKEN
 241   {0, 0, 4, sign_cost},                          // FOUR_TOKEN
 242   {vp9_cat1_prob, 1,  CAT1_MIN_VAL, cat1_cost},  // CATEGORY1_TOKEN
 243   {vp9_cat2_prob, 2,  CAT2_MIN_VAL, cat2_cost},  // CATEGORY2_TOKEN
 244   {vp9_cat3_prob, 3,  CAT3_MIN_VAL, cat3_cost},  // CATEGORY3_TOKEN
 245   {vp9_cat4_prob, 4,  CAT4_MIN_VAL, cat4_cost},  // CATEGORY4_TOKEN
 246   {vp9_cat5_prob, 5,  CAT5_MIN_VAL, cat5_cost},  // CATEGORY5_TOKEN
 247   {vp9_cat6_prob, 14, CAT6_MIN_VAL, 0},          // CATEGORY6_TOKEN
 248   {0, 0, 0, zero_cost}                           // EOB_TOKEN
 249 };
 250
 251 #if CONFIG_VP9_HIGHBITDEPTH
 252 const vp9_extra_bit vp9_extra_bits_high10[ENTROPY_TOKENS] = {
 253   {0, 0, 0, zero_cost},                             // ZERO
 254   {0, 0, 1, sign_cost},                             // ONE
 255   {0, 0, 2, sign_cost},                             // TWO
 256   {0, 0, 3, sign_cost},                             // THREE
 257   {0, 0, 4, sign_cost},                             // FOUR
 258   {vp9_cat1_prob, 1,  CAT1_MIN_VAL, cat1_cost},     // CAT1
 259   {vp9_cat2_prob, 2,  CAT2_MIN_VAL, cat2_cost},     // CAT2
 260   {vp9_cat3_prob, 3,  CAT3_MIN_VAL, cat3_cost},     // CAT3
 261   {vp9_cat4_prob, 4,  CAT4_MIN_VAL, cat4_cost},     // CAT4
 262   {vp9_cat5_prob, 5,  CAT5_MIN_VAL, cat5_cost},     // CAT5
 263   {vp9_cat6_prob_high12 + 2, 16, CAT6_MIN_VAL, 0},  // CAT6
 264   {0, 0, 0, zero_cost}                              // EOB
 265 };
 266 const vp9_extra_bit vp9_extra_bits_high12[ENTROPY_TOKENS] = {
 267   {0, 0, 0, zero_cost},                          // ZERO
 268   {0, 0, 1, sign_cost},                          // ONE
 269   {0, 0, 2, sign_cost},                          // TWO
 270   {0, 0, 3, sign_cost},                          // THREE
 271   {0, 0, 4, sign_cost},                          // FOUR
 272   {vp9_cat1_prob, 1,  CAT1_MIN_VAL, cat1_cost},  // CAT1
 273   {vp9_cat2_prob, 2,  CAT2_MIN_VAL, cat2_cost},  // CAT2
 274   {vp9_cat3_prob, 3,  CAT3_MIN_VAL, cat3_cost},  // CAT3
 275   {vp9_cat4_prob, 4,  CAT4_MIN_VAL, cat4_cost},  // CAT4
 276   {vp9_cat5_prob, 5,  CAT5_MIN_VAL, cat5_cost},  // CAT5
 277   {vp9_cat6_prob_high12, 18, CAT6_MIN_VAL, 0},   // CAT6
 278   {0, 0, 0, zero_cost}                           // EOB
 279 };
 280 #endif
 281
 282 const struct vp9_token vp9_coef_encodings[ENTROPY_TOKENS] = {
 283   {2, 2}, {6, 3}, {28, 5}, {58, 6}, {59, 6}, {60, 6}, {61, 6}, {124, 7},
 284   {125, 7}, {126, 7}, {127, 7}, {0, 1}
 285 };
 286
 287
 288 struct tokenize_b_args {
 289   VP9_COMP *cpi;
 290   ThreadData *td;
 291   TOKENEXTRA **tp;
 292 };
 293
 294 static void set_entropy_context_b(int plane, int block, BLOCK_SIZE plane_bsize,
 295                                   TX_SIZE tx_size, void *arg) {
 296   struct tokenize_b_args* const args = arg;
 297   ThreadData *const td = args->td;
 298   MACROBLOCK *const x = &td->mb;
 299   MACROBLOCKD *const xd = &x->e_mbd;
 300   struct macroblock_plane *p = &x->plane[plane];
 301   struct macroblockd_plane *pd = &xd->plane[plane];
 302   int aoff, loff;
 303   txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &aoff, &loff);
 304   vp9_set_contexts(xd, pd, plane_bsize, tx_size, p->eobs[block] > 0,
 305                    aoff, loff);
 306 }
 307
 308 static INLINE void add_token(TOKENEXTRA **t, const vpx_prob *context_tree,
 309                              int16_t token, EXTRABIT extra,
 310                              unsigned int *counts) {
 311   (*t)->context_tree = context_tree;
 312   (*t)->token = token;
 313   (*t)->extra = extra;
 314   (*t)++;
 315   ++counts[token];
 316 }
 317
 318 static INLINE void add_token_no_extra(TOKENEXTRA **t,
 319                                       const vpx_prob *context_tree,
 320                                       int16_t token,
 321                                       unsigned int *counts) {
 322   (*t)->context_tree = context_tree;
 323   (*t)->token = token;
 324   (*t)++;
 325   ++counts[token];
 326 }
 327
 328 static INLINE int get_tx_eob(const struct segmentation *seg, int segment_id,
 329                              TX_SIZE tx_size) {
 330   const int eob_max = 16 << (tx_size << 1);
 331   return segfeature_active(seg, segment_id, SEG_LVL_SKIP) ? 0 : eob_max;
 332 }
 333
 334 static void tokenize_b(int plane, int block, BLOCK_SIZE plane_bsize,
 335                        TX_SIZE tx_size, void *arg) {
 336   struct tokenize_b_args* const args = arg;
 337   VP9_COMP *cpi = args->cpi;
 338   ThreadData *const td = args->td;
 339   MACROBLOCK *const x = &td->mb;
 340   MACROBLOCKD *const xd = &x->e_mbd;
 341   TOKENEXTRA **tp = args->tp;
 342   uint8_t token_cache[32 * 32];
 343   struct macroblock_plane *p = &x->plane[plane];
 344   struct macroblockd_plane *pd = &xd->plane[plane];
 345   MODE_INFO *mi = xd->mi[0];
 346   int pt; /* near block/prev token context index */
 347   int c;
 348   TOKENEXTRA *t = *tp;        /* store tokens starting here */
 349   int eob = p->eobs[block];
 350   const PLANE_TYPE type = get_plane_type(plane);
 351   const tran_low_t *qcoeff = BLOCK_OFFSET(p->qcoeff, block);
 352   const int segment_id = mi->segment_id;
 353   const int16_t *scan, *nb;
 354   const scan_order *so;
 355   const int ref = is_inter_block(mi);
 356   unsigned int (*const counts)[COEFF_CONTEXTS][ENTROPY_TOKENS] =
 357       td->rd_counts.coef_counts[tx_size][type][ref];
 358   vpx_prob (*const coef_probs)[COEFF_CONTEXTS][UNCONSTRAINED_NODES] =
 359       cpi->common.fc->coef_probs[tx_size][type][ref];
 360   unsigned int (*const eob_branch)[COEFF_CONTEXTS] =
 361       td->counts->eob_branch[tx_size][type][ref];
 362   const uint8_t *const band = get_band_translate(tx_size);
 363   const int seg_eob = get_tx_eob(&cpi->common.seg, segment_id, tx_size);
 364   int16_t token;
 365   EXTRABIT extra;
 366   int aoff, loff;
 367   txfrm_block_to_raster_xy(plane_bsize, tx_size, block, &aoff, &loff);
 368
 369   pt = get_entropy_context(tx_size, pd->above_context + aoff,
 370                            pd->left_context + loff);
 371   so = get_scan(xd, tx_size, type, block);
 372   scan = so->scan;
 373   nb = so->neighbors;
 374   c = 0;
 375
 376   while (c < eob) {
 377     int v = 0;
 378     v = qcoeff[scan[c]];
 379     ++eob_branch[band[c]][pt];
 380
 381     while (!v) {
 382       add_token_no_extra(&t, coef_probs[band[c]][pt], ZERO_TOKEN,
 383                          counts[band[c]][pt]);
 384
 385       token_cache[scan[c]] = 0;
 386       ++c;
 387       pt = get_coef_context(nb, token_cache, c);
 388       v = qcoeff[scan[c]];
 389     }
 390
 391     vp9_get_token_extra(v, &token, &extra);
 392
 393     add_token(&t, coef_probs[band[c]][pt], token, extra,
 394               counts[band[c]][pt]);
 395
 396     token_cache[scan[c]] = vp9_pt_energy_class[token];
 397     ++c;
 398     pt = get_coef_context(nb, token_cache, c);
 399   }
 400   if (c < seg_eob) {
 401     ++eob_branch[band[c]][pt];
 402     add_token_no_extra(&t, coef_probs[band[c]][pt], EOB_TOKEN,
 403                        counts[band[c]][pt]);
 404   }
 405
 406   *tp = t;
 407
 408   vp9_set_contexts(xd, pd, plane_bsize, tx_size, c > 0, aoff, loff);
 409 }
 410
 411 struct is_skippable_args {
 412   uint16_t *eobs;
 413   int *skippable;
 414 };
 415 static void is_skippable(int plane, int block,
 416                          BLOCK_SIZE plane_bsize, TX_SIZE tx_size,
 417                          void *argv) {
 418   struct is_skippable_args *args = argv;
 419   (void)plane;
 420   (void)plane_bsize;
 421   (void)tx_size;
 422   args->skippable[0] &= (!args->eobs[block]);
 423 }
 424
 425 // TODO(yaowu): rewrite and optimize this function to remove the usage of
 426 //              vp9_foreach_transform_block() and simplify is_skippable().
 427 int vp9_is_skippable_in_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane) {
 428   int result = 1;
 429   struct is_skippable_args args = {x->plane[plane].eobs, &result};
 430   vp9_foreach_transformed_block_in_plane(&x->e_mbd, bsize, plane, is_skippable,
 431                                          &args);
 432   return result;
 433 }
 434
 435 static void has_high_freq_coeff(int plane, int block,
 436                                 BLOCK_SIZE plane_bsize, TX_SIZE tx_size,
 437                                 void *argv) {
 438   struct is_skippable_args *args = argv;
 439   int eobs = (tx_size == TX_4X4) ? 3 : 10;
 440   (void) plane;
 441   (void) plane_bsize;
 442
 443   *(args->skippable) |= (args->eobs[block] > eobs);
 444 }
 445
 446 int vp9_has_high_freq_in_plane(MACROBLOCK *x, BLOCK_SIZE bsize, int plane) {
 447   int result = 0;
 448   struct is_skippable_args args = {x->plane[plane].eobs, &result};
 449   vp9_foreach_transformed_block_in_plane(&x->e_mbd, bsize, plane,
 450                                          has_high_freq_coeff, &args);
 451   return result;
 452 }
 453
 454 void vp9_tokenize_sb(VP9_COMP *cpi, ThreadData *td, TOKENEXTRA **t,
 455                      int dry_run, BLOCK_SIZE bsize) {
 456   VP9_COMMON *const cm = &cpi->common;
 457   MACROBLOCK *const x = &td->mb;
 458   MACROBLOCKD *const xd = &x->e_mbd;
 459   MODE_INFO *const mi = xd->mi[0];
 460   const int ctx = vp9_get_skip_context(xd);
 461   const int skip_inc = !segfeature_active(&cm->seg, mi->segment_id,
 462                                           SEG_LVL_SKIP);
 463   struct tokenize_b_args arg = {cpi, td, t};
 464   if (mi->skip) {
 465     if (!dry_run)
 466       td->counts->skip[ctx][1] += skip_inc;
 467     reset_skip_context(xd, bsize);
 468     return;
 469   }
 470
 471   if (!dry_run) {
 472     td->counts->skip[ctx][0] += skip_inc;
 473     vp9_foreach_transformed_block(xd, bsize, tokenize_b, &arg);
 474   } else {
 475     vp9_foreach_transformed_block(xd, bsize, set_entropy_context_b, &arg);
 476   }
 477 }