src/third_party/libvpx/source/libvpx/vp9/encoder/vp9_encodemv.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 <math.h>
  12
  13 #include "vp9/common/vp9_common.h"
  14 #include "vp9/common/vp9_entropymode.h"
  15 #include "vp9/common/vp9_systemdependent.h"
  16 #include "vp9/encoder/vp9_encodemv.h"
  17
  18 #ifdef ENTROPY_STATS
  19 extern unsigned int active_section;
  20 #endif
  21
  22 static struct vp9_token mv_joint_encodings[MV_JOINTS];
  23 static struct vp9_token mv_class_encodings[MV_CLASSES];
  24 static struct vp9_token mv_fp_encodings[MV_FP_SIZE];
  25 static struct vp9_token mv_class0_encodings[CLASS0_SIZE];
  26
  27 void vp9_entropy_mv_init() {
  28   vp9_tokens_from_tree(mv_joint_encodings, vp9_mv_joint_tree);
  29   vp9_tokens_from_tree(mv_class_encodings, vp9_mv_class_tree);
  30   vp9_tokens_from_tree(mv_class0_encodings, vp9_mv_class0_tree);
  31   vp9_tokens_from_tree(mv_fp_encodings, vp9_mv_fp_tree);
  32 }
  33
  34 static void encode_mv_component(vp9_writer* w, int comp,
  35                                 const nmv_component* mvcomp, int usehp) {
  36   int offset;
  37   const int sign = comp < 0;
  38   const int mag = sign ? -comp : comp;
  39   const int mv_class = vp9_get_mv_class(mag - 1, &offset);
  40   const int d = offset >> 3;                // int mv data
  41   const int fr = (offset >> 1) & 3;         // fractional mv data
  42   const int hp = offset & 1;                // high precision mv data
  43
  44   assert(comp != 0);
  45
  46   // Sign
  47   vp9_write(w, sign, mvcomp->sign);
  48
  49   // Class
  50   vp9_write_token(w, vp9_mv_class_tree, mvcomp->classes,
  51                   &mv_class_encodings[mv_class]);
  52
  53   // Integer bits
  54   if (mv_class == MV_CLASS_0) {
  55     vp9_write_token(w, vp9_mv_class0_tree, mvcomp->class0,
  56                     &mv_class0_encodings[d]);
  57   } else {
  58     int i;
  59     const int n = mv_class + CLASS0_BITS - 1;  // number of bits
  60     for (i = 0; i < n; ++i)
  61       vp9_write(w, (d >> i) & 1, mvcomp->bits[i]);
  62   }
  63
  64   // Fractional bits
  65   vp9_write_token(w, vp9_mv_fp_tree,
  66                   mv_class == MV_CLASS_0 ?  mvcomp->class0_fp[d] : mvcomp->fp,
  67                   &mv_fp_encodings[fr]);
  68
  69   // High precision bit
  70   if (usehp)
  71     vp9_write(w, hp,
  72               mv_class == MV_CLASS_0 ? mvcomp->class0_hp : mvcomp->hp);
  73 }
  74
  75
  76 static void build_nmv_component_cost_table(int *mvcost,
  77                                            const nmv_component* const mvcomp,
  78                                            int usehp) {
  79   int i, v;
  80   int sign_cost[2], class_cost[MV_CLASSES], class0_cost[CLASS0_SIZE];
  81   int bits_cost[MV_OFFSET_BITS][2];
  82   int class0_fp_cost[CLASS0_SIZE][MV_FP_SIZE], fp_cost[MV_FP_SIZE];
  83   int class0_hp_cost[2], hp_cost[2];
  84
  85   sign_cost[0] = vp9_cost_zero(mvcomp->sign);
  86   sign_cost[1] = vp9_cost_one(mvcomp->sign);
  87   vp9_cost_tokens(class_cost, mvcomp->classes, vp9_mv_class_tree);
  88   vp9_cost_tokens(class0_cost, mvcomp->class0, vp9_mv_class0_tree);
  89   for (i = 0; i < MV_OFFSET_BITS; ++i) {
  90     bits_cost[i][0] = vp9_cost_zero(mvcomp->bits[i]);
  91     bits_cost[i][1] = vp9_cost_one(mvcomp->bits[i]);
  92   }
  93
  94   for (i = 0; i < CLASS0_SIZE; ++i)
  95     vp9_cost_tokens(class0_fp_cost[i], mvcomp->class0_fp[i], vp9_mv_fp_tree);
  96   vp9_cost_tokens(fp_cost, mvcomp->fp, vp9_mv_fp_tree);
  97
  98   if (usehp) {
  99     class0_hp_cost[0] = vp9_cost_zero(mvcomp->class0_hp);
 100     class0_hp_cost[1] = vp9_cost_one(mvcomp->class0_hp);
 101     hp_cost[0] = vp9_cost_zero(mvcomp->hp);
 102     hp_cost[1] = vp9_cost_one(mvcomp->hp);
 103   }
 104   mvcost[0] = 0;
 105   for (v = 1; v <= MV_MAX; ++v) {
 106     int z, c, o, d, e, f, cost = 0;
 107     z = v - 1;
 108     c = vp9_get_mv_class(z, &o);
 109     cost += class_cost[c];
 110     d = (o >> 3);               /* int mv data */
 111     f = (o >> 1) & 3;           /* fractional pel mv data */
 112     e = (o & 1);                /* high precision mv data */
 113     if (c == MV_CLASS_0) {
 114       cost += class0_cost[d];
 115     } else {
 116       int i, b;
 117       b = c + CLASS0_BITS - 1;  /* number of bits */
 118       for (i = 0; i < b; ++i)
 119         cost += bits_cost[i][((d >> i) & 1)];
 120     }
 121     if (c == MV_CLASS_0) {
 122       cost += class0_fp_cost[d][f];
 123     } else {
 124       cost += fp_cost[f];
 125     }
 126     if (usehp) {
 127       if (c == MV_CLASS_0) {
 128         cost += class0_hp_cost[e];
 129       } else {
 130         cost += hp_cost[e];
 131       }
 132     }
 133     mvcost[v] = cost + sign_cost[0];
 134     mvcost[-v] = cost + sign_cost[1];
 135   }
 136 }
 137
 138 static int update_mv(vp9_writer *w, const unsigned int ct[2], vp9_prob *cur_p,
 139                      vp9_prob upd_p) {
 140   const vp9_prob new_p = get_binary_prob(ct[0], ct[1]) | 1;
 141   const int update = cost_branch256(ct, *cur_p) + vp9_cost_zero(upd_p) >
 142                      cost_branch256(ct, new_p) + vp9_cost_one(upd_p) + 7 * 256;
 143   vp9_write(w, update, upd_p);
 144   if (update) {
 145     *cur_p = new_p;
 146     vp9_write_literal(w, new_p >> 1, 7);
 147   }
 148   return update;
 149 }
 150
 151 static void write_mv_update(const vp9_tree_index *tree,
 152                             vp9_prob probs[/*n - 1*/],
 153                             const unsigned int counts[/*n - 1*/],
 154                             int n, vp9_writer *w) {
 155   int i;
 156   unsigned int branch_ct[32][2];
 157
 158   // Assuming max number of probabilities <= 32
 159   assert(n <= 32);
 160
 161   vp9_tree_probs_from_distribution(tree, branch_ct, counts);
 162   for (i = 0; i < n - 1; ++i)
 163     update_mv(w, branch_ct[i], &probs[i], NMV_UPDATE_PROB);
 164 }
 165
 166 void vp9_write_nmv_probs(VP9_COMMON *cm, int usehp, vp9_writer *w) {
 167   int i, j;
 168   nmv_context *const mvc = &cm->fc.nmvc;
 169   nmv_context_counts *const counts = &cm->counts.mv;
 170
 171   write_mv_update(vp9_mv_joint_tree, mvc->joints, counts->joints, MV_JOINTS, w);
 172
 173   for (i = 0; i < 2; ++i) {
 174     nmv_component *comp = &mvc->comps[i];
 175     nmv_component_counts *comp_counts = &counts->comps[i];
 176
 177     update_mv(w, comp_counts->sign, &comp->sign, NMV_UPDATE_PROB);
 178     write_mv_update(vp9_mv_class_tree, comp->classes, comp_counts->classes,
 179                     MV_CLASSES, w);
 180     write_mv_update(vp9_mv_class0_tree, comp->class0, comp_counts->class0,
 181                     CLASS0_SIZE, w);
 182     for (j = 0; j < MV_OFFSET_BITS; ++j)
 183       update_mv(w, comp_counts->bits[j], &comp->bits[j], NMV_UPDATE_PROB);
 184   }
 185
 186   for (i = 0; i < 2; ++i) {
 187     for (j = 0; j < CLASS0_SIZE; ++j)
 188       write_mv_update(vp9_mv_fp_tree, mvc->comps[i].class0_fp[j],
 189                       counts->comps[i].class0_fp[j], MV_FP_SIZE, w);
 190
 191     write_mv_update(vp9_mv_fp_tree, mvc->comps[i].fp, counts->comps[i].fp,
 192                     MV_FP_SIZE, w);
 193   }
 194
 195   if (usehp) {
 196     for (i = 0; i < 2; ++i) {
 197       update_mv(w, counts->comps[i].class0_hp, &mvc->comps[i].class0_hp,
 198                 NMV_UPDATE_PROB);
 199       update_mv(w, counts->comps[i].hp, &mvc->comps[i].hp, NMV_UPDATE_PROB);
 200     }
 201   }
 202 }
 203
 204 void vp9_encode_mv(VP9_COMP* cpi, vp9_writer* w,
 205                    const MV* mv, const MV* ref,
 206                    const nmv_context* mvctx, int usehp) {
 207   const MV diff = {mv->row - ref->row,
 208                    mv->col - ref->col};
 209   const MV_JOINT_TYPE j = vp9_get_mv_joint(&diff);
 210   usehp = usehp && vp9_use_mv_hp(ref);
 211
 212   vp9_write_token(w, vp9_mv_joint_tree, mvctx->joints, &mv_joint_encodings[j]);
 213   if (mv_joint_vertical(j))
 214     encode_mv_component(w, diff.row, &mvctx->comps[0], usehp);
 215
 216   if (mv_joint_horizontal(j))
 217     encode_mv_component(w, diff.col, &mvctx->comps[1], usehp);
 218
 219   // If auto_mv_step_size is enabled then keep track of the largest
 220   // motion vector component used.
 221   if (!cpi->dummy_packing && cpi->sf.auto_mv_step_size) {
 222     unsigned int maxv = MAX(abs(mv->row), abs(mv->col)) >> 3;
 223     cpi->max_mv_magnitude = MAX(maxv, cpi->max_mv_magnitude);
 224   }
 225 }
 226
 227 void vp9_build_nmv_cost_table(int *mvjoint, int *mvcost[2],
 228                               const nmv_context* ctx, int usehp) {
 229   vp9_cost_tokens(mvjoint, ctx->joints, vp9_mv_joint_tree);
 230   build_nmv_component_cost_table(mvcost[0], &ctx->comps[0], usehp);
 231   build_nmv_component_cost_table(mvcost[1], &ctx->comps[1], usehp);
 232 }
 233
 234 static void inc_mvs(const int_mv mv[2], const MV ref[2], int is_compound,
 235                     nmv_context_counts *counts) {
 236   int i;
 237   for (i = 0; i < 1 + is_compound; ++i) {
 238     const MV diff = { mv[i].as_mv.row - ref[i].row,
 239                       mv[i].as_mv.col - ref[i].col };
 240     vp9_inc_mv(&diff, counts);
 241   }
 242 }
 243
 244 void vp9_update_mv_count(VP9_COMMON *cm, const MACROBLOCKD *xd,
 245                          const MV best_ref_mv[2]) {
 246   const MODE_INFO *mi = xd->mi_8x8[0];
 247   const MB_MODE_INFO *const mbmi = &mi->mbmi;
 248   const int is_compound = has_second_ref(mbmi);
 249   nmv_context_counts *counts = &cm->counts.mv;
 250
 251   if (mbmi->sb_type < BLOCK_8X8) {
 252     const int num_4x4_w = num_4x4_blocks_wide_lookup[mbmi->sb_type];
 253     const int num_4x4_h = num_4x4_blocks_high_lookup[mbmi->sb_type];
 254     int idx, idy;
 255
 256     for (idy = 0; idy < 2; idy += num_4x4_h) {
 257       for (idx = 0; idx < 2; idx += num_4x4_w) {
 258         const int i = idy * 2 + idx;
 259         if (mi->bmi[i].as_mode == NEWMV)
 260           inc_mvs(mi->bmi[i].as_mv, best_ref_mv, is_compound, counts);
 261       }
 262     }
 263   } else if (mbmi->mode == NEWMV) {
 264     inc_mvs(mbmi->mv, best_ref_mv, is_compound, counts);
 265   }
 266 }
 267