vp8/encoder/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
  12 #include "common.h"
  13 #include "encodemv.h"
  14 #include "entropymode.h"
  15 #include "systemdependent.h"
  16
  17 #include <math.h>
  18
  19 #ifdef ENTROPY_STATS
  20 extern unsigned int active_section;
  21 #endif
  22
  23 static void encode_mvcomponent(
  24     vp8_writer *const w,
  25     const int v,
  26     const struct mv_context *mvc
  27 )
  28 {
  29     const vp8_prob *p = mvc->prob;
  30     const int x = v < 0 ? -v : v;
  31
  32     if (x < mvnum_short)     // Small
  33     {
  34         vp8_write(w, 0, p [mvpis_short]);
  35         vp8_treed_write(w, vp8_small_mvtree, p + MVPshort, x, 3);
  36
  37         if (!x)
  38             return;         // no sign bit
  39     }
  40     else                    // Large
  41     {
  42         int i = 0;
  43
  44         vp8_write(w, 1, p [mvpis_short]);
  45
  46         do
  47             vp8_write(w, (x >> i) & 1, p [MVPbits + i]);
  48
  49         while (++i < 3);
  50
  51         i = mvlong_width - 1;  /* Skip bit 3, which is sometimes implicit */
  52
  53         do
  54             vp8_write(w, (x >> i) & 1, p [MVPbits + i]);
  55
  56         while (--i > 3);
  57
  58         if (x & 0xFFF0)
  59             vp8_write(w, (x >> 3) & 1, p [MVPbits + 3]);
  60     }
  61
  62     vp8_write(w, v < 0, p [MVPsign]);
  63 }
  64 #if 0
  65 static int max_mv_r = 0;
  66 static int max_mv_c = 0;
  67 #endif
  68 void vp8_encode_motion_vector(vp8_writer *w, const MV *mv, const MV_CONTEXT *mvc)
  69 {
  70
  71 #if 0
  72     {
  73         if (abs(mv->row >> 1) > max_mv_r)
  74         {
  75             FILE *f = fopen("maxmv.stt", "a");
  76             max_mv_r = abs(mv->row >> 1);
  77             fprintf(f, "New Mv Row Max %6d\n", (mv->row >> 1));
  78
  79             if ((abs(mv->row) / 2) != max_mv_r)
  80                 fprintf(f, "MV Row conversion error %6d\n", abs(mv->row) / 2);
  81
  82             fclose(f);
  83         }
  84
  85         if (abs(mv->col >> 1) > max_mv_c)
  86         {
  87             FILE *f = fopen("maxmv.stt", "a");
  88             fprintf(f, "New Mv Col Max %6d\n", (mv->col >> 1));
  89             max_mv_c = abs(mv->col >> 1);
  90             fclose(f);
  91         }
  92     }
  93 #endif
  94
  95     encode_mvcomponent(w, mv->row >> 1, &mvc[0]);
  96     encode_mvcomponent(w, mv->col >> 1, &mvc[1]);
  97 }
  98
  99
 100 static unsigned int cost_mvcomponent(const int v, const struct mv_context *mvc)
 101 {
 102     const vp8_prob *p = mvc->prob;
 103     const int x = v;   //v<0? -v:v;
 104     unsigned int cost;
 105
 106     if (x < mvnum_short)
 107     {
 108         cost = vp8_cost_zero(p [mvpis_short])
 109                + vp8_treed_cost(vp8_small_mvtree, p + MVPshort, x, 3);
 110
 111         if (!x)
 112             return cost;
 113     }
 114     else
 115     {
 116         int i = 0;
 117         cost = vp8_cost_one(p [mvpis_short]);
 118
 119         do
 120             cost += vp8_cost_bit(p [MVPbits + i], (x >> i) & 1);
 121
 122         while (++i < 3);
 123
 124         i = mvlong_width - 1;  /* Skip bit 3, which is sometimes implicit */
 125
 126         do
 127             cost += vp8_cost_bit(p [MVPbits + i], (x >> i) & 1);
 128
 129         while (--i > 3);
 130
 131         if (x & 0xFFF0)
 132             cost += vp8_cost_bit(p [MVPbits + 3], (x >> 3) & 1);
 133     }
 134
 135     return cost;   // + vp8_cost_bit( p [MVPsign], v < 0);
 136 }
 137 //#define M_LOG2_E 0.693147180559945309417
 138 //#define log2f(x) (log (x) / (float) M_LOG2_E)
 139
 140 void vp8_build_component_cost_table(int *mvcost[2], int *mvsadcost[2], const MV_CONTEXT *mvc, int mvc_flag[2])
 141 {
 142     int i = 1;   //-mv_max;
 143     unsigned int cost0 = 0;
 144     unsigned int cost1 = 0;
 145
 146     vp8_clear_system_state();
 147 #if 0
 148     mvsadcost [0] [0] = 300;
 149     mvsadcost [1] [0] = 300;
 150
 151     do
 152     {
 153         double z = 256 * (2 * (log2f(2 * i) + .6));
 154         mvsadcost [0][i] = (int) z;
 155         mvsadcost [1][i] = (int) z;
 156         mvsadcost [0][-i] = (int) z;
 157         mvsadcost [1][-i] = (int) z;
 158     }
 159     while (++i <= mv_max);
 160
 161 #endif
 162
 163     i = 1;
 164
 165     if (mvc_flag[0])
 166     {
 167         mvcost [0] [0] = cost_mvcomponent(0, &mvc[0]);
 168
 169         do
 170         {
 171             //mvcost [0] [i] = cost_mvcomponent( i, &mvc[0]);
 172             cost0 = cost_mvcomponent(i, &mvc[0]);
 173
 174             mvcost [0] [i] = cost0 + vp8_cost_zero(mvc[0].prob[MVPsign]);
 175             mvcost [0] [-i] = cost0 + vp8_cost_one(mvc[0].prob[MVPsign]);
 176         }
 177         while (++i <= mv_max);
 178     }
 179
 180     i = 1;
 181
 182     if (mvc_flag[1])
 183     {
 184         mvcost [1] [0] = cost_mvcomponent(0, &mvc[1]);
 185
 186         do
 187         {
 188             //mvcost [1] [i] = cost_mvcomponent( i, mvc[1]);
 189             cost1 = cost_mvcomponent(i, &mvc[1]);
 190
 191             mvcost [1] [i] = cost1 + vp8_cost_zero(mvc[1].prob[MVPsign]);
 192             mvcost [1] [-i] = cost1 + vp8_cost_one(mvc[1].prob[MVPsign]);
 193         }
 194         while (++i <= mv_max);
 195     }
 196
 197     /*
 198         i=-mv_max;
 199         do
 200         {
 201             mvcost [0] [i] = cost_mvcomponent( i, mvc[0]);
 202             mvcost [1] [i] = cost_mvcomponent( i, mvc[1]);
 203         }
 204         while( ++i <= mv_max);
 205     */
 206 }
 207
 208
 209 // Motion vector probability table update depends on benefit.
 210 // Small correction allows for the fact that an update to an MV probability
 211 // may have benefit in subsequent frames as well as the current one.
 212
 213 #define MV_PROB_UPDATE_CORRECTION   -1
 214
 215
 216 __inline static void calc_prob(vp8_prob *p, const unsigned int ct[2])
 217 {
 218     const unsigned int tot = ct[0] + ct[1];
 219
 220     if (tot)
 221     {
 222         const vp8_prob x = ((ct[0] * 255) / tot) & -2;
 223         *p = x ? x : 1;
 224     }
 225 }
 226
 227 static void update(
 228     vp8_writer *const w,
 229     const unsigned int ct[2],
 230     vp8_prob *const cur_p,
 231     const vp8_prob new_p,
 232     const vp8_prob update_p,
 233     int *updated
 234 )
 235 {
 236     const int cur_b = vp8_cost_branch(ct, *cur_p);
 237     const int new_b = vp8_cost_branch(ct, new_p);
 238     const int cost = 7 + MV_PROB_UPDATE_CORRECTION + ((vp8_cost_one(update_p) - vp8_cost_zero(update_p) + 128) >> 8);
 239
 240     if (cur_b - new_b > cost)
 241     {
 242         *cur_p = new_p;
 243         vp8_write(w, 1, update_p);
 244         vp8_write_literal(w, new_p >> 1, 7);
 245         *updated = 1;
 246
 247     }
 248     else
 249         vp8_write(w, 0, update_p);
 250 }
 251
 252 static void write_component_probs(
 253     vp8_writer *const w,
 254     struct mv_context *cur_mvc,
 255     const struct mv_context *default_mvc_,
 256     const struct mv_context *update_mvc,
 257     const unsigned int events [MVvals],
 258     unsigned int rc,
 259     int *updated
 260 )
 261 {
 262     vp8_prob *Pcur = cur_mvc->prob;
 263     const vp8_prob *default_mvc = default_mvc_->prob;
 264     const vp8_prob *Pupdate = update_mvc->prob;
 265     unsigned int is_short_ct[2], sign_ct[2];
 266
 267     unsigned int bit_ct [mvlong_width] [2];
 268
 269     unsigned int short_ct  [mvnum_short];
 270     unsigned int short_bct [mvnum_short-1] [2];
 271
 272     vp8_prob Pnew [MVPcount];
 273
 274     (void) rc;
 275     vp8_copy_array(Pnew, default_mvc, MVPcount);
 276
 277     vp8_zero(is_short_ct)
 278     vp8_zero(sign_ct)
 279     vp8_zero(bit_ct)
 280     vp8_zero(short_ct)
 281     vp8_zero(short_bct)
 282
 283
 284     //j=0
 285     {
 286         const int c = events [mv_max];
 287
 288         is_short_ct [0] += c;     // Short vector
 289         short_ct [0] += c;       // Magnitude distribution
 290     }
 291
 292     //j: 1 ~ mv_max (1023)
 293     {
 294         int j = 1;
 295
 296         do
 297         {
 298             const int c1 = events [mv_max + j];  //positive
 299             const int c2 = events [mv_max - j];  //negative
 300             const int c  = c1 + c2;
 301             int a = j;
 302
 303             sign_ct [0] += c1;
 304             sign_ct [1] += c2;
 305
 306             if (a < mvnum_short)
 307             {
 308                 is_short_ct [0] += c;     // Short vector
 309                 short_ct [a] += c;       // Magnitude distribution
 310             }
 311             else
 312             {
 313                 int k = mvlong_width - 1;
 314                 is_short_ct [1] += c;     // Long vector
 315
 316                 /*  bit 3 not always encoded. */
 317                 do
 318                     bit_ct [k] [(a >> k) & 1] += c;
 319
 320                 while (--k >= 0);
 321             }
 322         }
 323         while (++j <= mv_max);
 324     }
 325
 326     /*
 327     {
 328         int j = -mv_max;
 329         do
 330         {
 331
 332             const int c = events [mv_max + j];
 333             int a = j;
 334
 335             if( j < 0)
 336             {
 337                 sign_ct [1] += c;
 338                 a = -j;
 339             }
 340             else if( j)
 341                 sign_ct [0] += c;
 342
 343             if( a < mvnum_short)
 344             {
 345                 is_short_ct [0] += c;     // Short vector
 346                 short_ct [a] += c;       // Magnitude distribution
 347             }
 348             else
 349             {
 350                 int k = mvlong_width - 1;
 351                 is_short_ct [1] += c;     // Long vector
 352
 353                 //  bit 3 not always encoded.
 354
 355                 do
 356                     bit_ct [k] [(a >> k) & 1] += c;
 357                 while( --k >= 0);
 358             }
 359         } while( ++j <= mv_max);
 360     }
 361     */
 362
 363     calc_prob(Pnew + mvpis_short, is_short_ct);
 364
 365     calc_prob(Pnew + MVPsign, sign_ct);
 366
 367     {
 368         vp8_prob p [mvnum_short - 1];    /* actually only need branch ct */
 369         int j = 0;
 370
 371         vp8_tree_probs_from_distribution(
 372             8, vp8_small_mvencodings, vp8_small_mvtree,
 373             p, short_bct, short_ct,
 374             256, 1
 375         );
 376
 377         do
 378             calc_prob(Pnew + MVPshort + j, short_bct[j]);
 379
 380         while (++j < mvnum_short - 1);
 381     }
 382
 383     {
 384         int j = 0;
 385
 386         do
 387             calc_prob(Pnew + MVPbits + j, bit_ct[j]);
 388
 389         while (++j < mvlong_width);
 390     }
 391
 392     update(w, is_short_ct, Pcur + mvpis_short, Pnew[mvpis_short], *Pupdate++, updated);
 393
 394     update(w, sign_ct, Pcur + MVPsign, Pnew[MVPsign], *Pupdate++, updated);
 395
 396     {
 397         const vp8_prob *const new_p = Pnew + MVPshort;
 398         vp8_prob *const cur_p = Pcur + MVPshort;
 399
 400         int j = 0;
 401
 402         do
 403
 404             update(w, short_bct[j], cur_p + j, new_p[j], *Pupdate++, updated);
 405
 406         while (++j < mvnum_short - 1);
 407     }
 408
 409     {
 410         const vp8_prob *const new_p = Pnew + MVPbits;
 411         vp8_prob *const cur_p = Pcur + MVPbits;
 412
 413         int j = 0;
 414
 415         do
 416
 417             update(w, bit_ct[j], cur_p + j, new_p[j], *Pupdate++, updated);
 418
 419         while (++j < mvlong_width);
 420     }
 421 }
 422
 423 void vp8_write_mvprobs(VP8_COMP *cpi)
 424 {
 425     vp8_writer *const w  = & cpi->bc;
 426     MV_CONTEXT *mvc = cpi->common.fc.mvc;
 427     int flags[2] = {0, 0};
 428 #ifdef ENTROPY_STATS
 429     active_section = 4;
 430 #endif
 431     write_component_probs(
 432         w, &mvc[0], &vp8_default_mv_context[0], &vp8_mv_update_probs[0], cpi->MVcount[0], 0, &flags[0]
 433     );
 434     write_component_probs(
 435         w, &mvc[1], &vp8_default_mv_context[1], &vp8_mv_update_probs[1], cpi->MVcount[1], 1, &flags[1]
 436     );
 437
 438     if (flags[0] || flags[1])
 439         vp8_build_component_cost_table(cpi->mb.mvcost, cpi->mb.mvsadcost, (const MV_CONTEXT *) cpi->common.fc.mvc, flags);
 440
 441 #ifdef ENTROPY_STATS
 442     active_section = 5;
 443 #endif
 444 }