Merge remote-tracking branch 'upstream/master'

1 files changed, 319 insertions, 448 deletions

diff --git a/drivers/webp/enc/frame.c b/drivers/webp/enc/frame.c
index 2582244c6c..bdd360069b 100644
--- a/drivers/webp/enc/frame.c
+++ b/drivers/webp/enc/frame.c
@@ -1,10 +1,8 @@
 // Copyright 2011 Google Inc. All Rights Reserved.
 //
-// Use of this source code is governed by a BSD-style license
-// that can be found in the COPYING file in the root of the source
-// tree. An additional intellectual property rights grant can be found
-// in the file PATENTS. All contributing project authors may
-// be found in the AUTHORS file in the root of the source tree.
+// This code is licensed under the same terms as WebM:
+//  Software License Agreement:  http://www.webmproject.org/license/software/
+//  Additional IP Rights Grant:  http://www.webmproject.org/license/additional/
 // -----------------------------------------------------------------------------
 //
 //   frame coding and analysis
@@ -18,7 +16,10 @@
 
 #include "./vp8enci.h"
 #include "./cost.h"
-#include "../webp/format_constants.h"  // RIFF constants
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
 
 #define SEGMENT_VISU 0
 #define DEBUG_SEARCH 0    // useful to track search convergence
@@ -37,63 +38,6 @@ typedef struct {
 } VP8Residual;
 
 //------------------------------------------------------------------------------
-// multi-pass convergence
-
-#define HEADER_SIZE_ESTIMATE (RIFF_HEADER_SIZE + CHUNK_HEADER_SIZE +  \
-                              VP8_FRAME_HEADER_SIZE)
-#define DQ_LIMIT 0.4  // convergence is considered reached if dq < DQ_LIMIT
-// we allow 2k of extra head-room in PARTITION0 limit.
-#define PARTITION0_SIZE_LIMIT ((VP8_MAX_PARTITION0_SIZE - 2048ULL) << 11)
-
-typedef struct {  // struct for organizing convergence in either size or PSNR
-  int is_first;
-  float dq;
-  float q, last_q;
-  double value, last_value;   // PSNR or size
-  double target;
-  int do_size_search;
-} PassStats;
-
-static int InitPassStats(const VP8Encoder* const enc, PassStats* const s) {
-  const uint64_t target_size = (uint64_t)enc->config_->target_size;
-  const int do_size_search = (target_size != 0);
-  const float target_PSNR = enc->config_->target_PSNR;
-
-  s->is_first = 1;
-  s->dq = 10.f;
-  s->q = s->last_q = enc->config_->quality;
-  s->target = do_size_search ? (double)target_size
-            : (target_PSNR > 0.) ? target_PSNR
-            : 40.;   // default, just in case
-  s->value = s->last_value = 0.;
-  s->do_size_search = do_size_search;
-  return do_size_search;
-}
-
-static float Clamp(float v, float min, float max) {
-  return (v < min) ? min : (v > max) ? max : v;
-}
-
-static float ComputeNextQ(PassStats* const s) {
-  float dq;
-  if (s->is_first) {
-    dq = (s->value > s->target) ? -s->dq : s->dq;
-    s->is_first = 0;
-  } else if (s->value != s->last_value) {
-    const double slope = (s->target - s->value) / (s->last_value - s->value);
-    dq = (float)(slope * (s->last_q - s->q));
-  } else {
-    dq = 0.;  // we're done?!
-  }
-  // Limit variable to avoid large swings.
-  s->dq = Clamp(dq, -30.f, 30.f);
-  s->last_q = s->q;
-  s->last_value = s->value;
-  s->q = Clamp(s->q + s->dq, 0.f, 100.f);
-  return s->q;
-}
-
-//------------------------------------------------------------------------------
 // Tables for level coding
 
 const uint8_t VP8EncBands[16 + 1] = {
@@ -101,10 +45,10 @@ const uint8_t VP8EncBands[16 + 1] = {
   0  // sentinel
 };
 
-const uint8_t VP8Cat3[] = { 173, 148, 140 };
-const uint8_t VP8Cat4[] = { 176, 155, 140, 135 };
-const uint8_t VP8Cat5[] = { 180, 157, 141, 134, 130 };
-const uint8_t VP8Cat6[] =
+static const uint8_t kCat3[] = { 173, 148, 140 };
+static const uint8_t kCat4[] = { 176, 155, 140, 135 };
+static const uint8_t kCat5[] = { 180, 157, 141, 134, 130 };
+static const uint8_t kCat6[] =
     { 254, 254, 243, 230, 196, 177, 153, 140, 133, 130, 129 };
 
 //------------------------------------------------------------------------------
@@ -169,15 +113,14 @@ static int Record(int bit, proba_t* const stats) {
 // Note: no need to record the fixed probas.
 static int RecordCoeffs(int ctx, const VP8Residual* const res) {
   int n = res->first;
-  // should be stats[VP8EncBands[n]], but it's equivalent for n=0 or 1
-  proba_t* s = res->stats[n][ctx];
+  proba_t* s = res->stats[VP8EncBands[n]][ctx];
   if (res->last  < 0) {
     Record(0, s + 0);
     return 0;
   }
   while (n <= res->last) {
     int v;
-    Record(1, s + 0);  // order of record doesn't matter
+    Record(1, s + 0);
     while ((v = res->coeffs[n++]) == 0) {
       Record(0, s + 1);
       s = res->stats[VP8EncBands[n]][0];
@@ -231,7 +174,8 @@ static int BranchCost(int nb, int total, int proba) {
   return nb * VP8BitCost(1, proba) + (total - nb) * VP8BitCost(0, proba);
 }
 
-static int FinalizeTokenProbas(VP8Proba* const proba) {
+static int FinalizeTokenProbas(VP8Encoder* const enc) {
+  VP8Proba* const proba = &enc->proba_;
   int has_changed = 0;
   int size = 0;
   int t, b, c, p;
@@ -268,47 +212,6 @@ static int FinalizeTokenProbas(VP8Proba* const proba) {
 }
 
 //------------------------------------------------------------------------------
-// Finalize Segment probability based on the coding tree
-
-static int GetProba(int a, int b) {
-  const int total = a + b;
-  return (total == 0) ? 255     // that's the default probability.
-                      : (255 * a + total / 2) / total;  // rounded proba
-}
-
-static void SetSegmentProbas(VP8Encoder* const enc) {
-  int p[NUM_MB_SEGMENTS] = { 0 };
-  int n;
-
-  for (n = 0; n < enc->mb_w_ * enc->mb_h_; ++n) {
-    const VP8MBInfo* const mb = &enc->mb_info_[n];
-    p[mb->segment_]++;
-  }
-  if (enc->pic_->stats != NULL) {
-    for (n = 0; n < NUM_MB_SEGMENTS; ++n) {
-      enc->pic_->stats->segment_size[n] = p[n];
-    }
-  }
-  if (enc->segment_hdr_.num_segments_ > 1) {
-    uint8_t* const probas = enc->proba_.segments_;
-    probas[0] = GetProba(p[0] + p[1], p[2] + p[3]);
-    probas[1] = GetProba(p[0], p[1]);
-    probas[2] = GetProba(p[2], p[3]);
-
-    enc->segment_hdr_.update_map_ =
-        (probas[0] != 255) || (probas[1] != 255) || (probas[2] != 255);
-    enc->segment_hdr_.size_ =
-        p[0] * (VP8BitCost(0, probas[0]) + VP8BitCost(0, probas[1])) +
-        p[1] * (VP8BitCost(0, probas[0]) + VP8BitCost(1, probas[1])) +
-        p[2] * (VP8BitCost(1, probas[0]) + VP8BitCost(0, probas[2])) +
-        p[3] * (VP8BitCost(1, probas[0]) + VP8BitCost(1, probas[2]));
-  } else {
-    enc->segment_hdr_.update_map_ = 0;
-    enc->segment_hdr_.size_ = 0;
-  }
-}
-
-//------------------------------------------------------------------------------
 // helper functions for residuals struct VP8Residual.
 
 static void InitResidual(int first, int coeff_type,
@@ -336,38 +239,39 @@ static void SetResidualCoeffs(const int16_t* const coeffs,
 //------------------------------------------------------------------------------
 // Mode costs
 
-static int GetResidualCost(int ctx0, const VP8Residual* const res) {
+static int GetResidualCost(int ctx, const VP8Residual* const res) {
   int n = res->first;
-  // should be prob[VP8EncBands[n]], but it's equivalent for n=0 or 1
-  int p0 = res->prob[n][ctx0][0];
-  const uint16_t* t = res->cost[n][ctx0];
+  int p0 = res->prob[VP8EncBands[n]][ctx][0];
+  const uint16_t* t = res->cost[VP8EncBands[n]][ctx];
   int cost;
 
   if (res->last < 0) {
     return VP8BitCost(0, p0);
   }
-  cost = VP8BitCost(1, p0);
-  for (; n < res->last; ++n) {
-    const int v = abs(res->coeffs[n]);
+  cost = 0;
+  while (n <= res->last) {
+    const int v = res->coeffs[n];
     const int b = VP8EncBands[n + 1];
-    const int ctx = (v >= 2) ? 2 : v;
-    cost += VP8LevelCost(t, v);
-    t = res->cost[b][ctx];
-    // the masking trick is faster than "if (v) cost += ..." with clang
-    cost += (v ? ~0U : 0) & VP8BitCost(1, res->prob[b][ctx][0]);
-  }
-  // Last coefficient is always non-zero
-  {
-    const int v = abs(res->coeffs[n]);
-    assert(v != 0);
-    cost += VP8LevelCost(t, v);
-    if (n < 15) {
-      const int b = VP8EncBands[n + 1];
-      const int ctx = (v == 1) ? 1 : 2;
-      const int last_p0 = res->prob[b][ctx][0];
-      cost += VP8BitCost(0, last_p0);
+    ++n;
+    if (v == 0) {
+      // short-case for VP8LevelCost(t, 0) (note: VP8LevelFixedCosts[0] == 0):
+      cost += t[0];
+      t = res->cost[b][0];
+      continue;
+    }
+    cost += VP8BitCost(1, p0);
+    if (2u >= (unsigned int)(v + 1)) {   // v = -1 or 1
+      // short-case for "VP8LevelCost(t, 1)" (256 is VP8LevelFixedCosts[1]):
+      cost += 256 + t[1];
+      p0 = res->prob[b][1][0];
+      t = res->cost[b][1];
+    } else {
+      cost += VP8LevelCost(t, abs(v));
+      p0 = res->prob[b][2][0];
+      t = res->cost[b][2];
     }
   }
+  if (n < 16) cost += VP8BitCost(0, p0);
   return cost;
 }
 
@@ -438,8 +342,7 @@ int VP8GetCostUV(VP8EncIterator* const it, const VP8ModeScore* const rd) {
 
 static int PutCoeffs(VP8BitWriter* const bw, int ctx, const VP8Residual* res) {
   int n = res->first;
-  // should be prob[VP8EncBands[n]], but it's equivalent for n=0 or 1
-  const uint8_t* p = res->prob[n][ctx];
+  const uint8_t* p = res->prob[VP8EncBands[n]][ctx];
   if (!VP8PutBit(bw, res->last >= 0, p[0])) {
     return 0;
   }
@@ -468,30 +371,30 @@ static int PutCoeffs(VP8BitWriter* const bw, int ctx, const VP8Residual* res) {
       } else {
         int mask;
         const uint8_t* tab;
-        if (v < 3 + (8 << 1)) {          // VP8Cat3  (3b)
+        if (v < 3 + (8 << 1)) {          // kCat3  (3b)
           VP8PutBit(bw, 0, p[8]);
           VP8PutBit(bw, 0, p[9]);
           v -= 3 + (8 << 0);
           mask = 1 << 2;
-          tab = VP8Cat3;
-        } else if (v < 3 + (8 << 2)) {   // VP8Cat4  (4b)
+          tab = kCat3;
+        } else if (v < 3 + (8 << 2)) {   // kCat4  (4b)
           VP8PutBit(bw, 0, p[8]);
           VP8PutBit(bw, 1, p[9]);
           v -= 3 + (8 << 1);
           mask = 1 << 3;
-          tab = VP8Cat4;
-        } else if (v < 3 + (8 << 3)) {   // VP8Cat5  (5b)
+          tab = kCat4;
+        } else if (v < 3 + (8 << 3)) {   // kCat5  (5b)
           VP8PutBit(bw, 1, p[8]);
           VP8PutBit(bw, 0, p[10]);
           v -= 3 + (8 << 2);
           mask = 1 << 4;
-          tab = VP8Cat5;
-        } else {                         // VP8Cat6 (11b)
+          tab = kCat5;
+        } else {                         // kCat6 (11b)
           VP8PutBit(bw, 1, p[8]);
           VP8PutBit(bw, 1, p[10]);
           v -= 3 + (8 << 3);
           mask = 1 << 10;
-          tab = VP8Cat6;
+          tab = kCat6;
         }
         while (mask) {
           VP8PutBit(bw, !!(v & mask), *tab++);
@@ -508,7 +411,8 @@ static int PutCoeffs(VP8BitWriter* const bw, int ctx, const VP8Residual* res) {
   return 1;
 }
 
-static void CodeResiduals(VP8BitWriter* const bw, VP8EncIterator* const it,
+static void CodeResiduals(VP8BitWriter* const bw,
+                          VP8EncIterator* const it,
                           const VP8ModeScore* const rd) {
   int x, y, ch;
   VP8Residual res;
@@ -608,23 +512,146 @@ static void RecordResiduals(VP8EncIterator* const it,
 //------------------------------------------------------------------------------
 // Token buffer
 
-#if !defined(DISABLE_TOKEN_BUFFER)
+#ifdef USE_TOKEN_BUFFER
+
+void VP8TBufferInit(VP8TBuffer* const b) {
+  b->rows_ = NULL;
+  b->tokens_ = NULL;
+  b->last_ = &b->rows_;
+  b->left_ = 0;
+  b->error_ = 0;
+}
+
+int VP8TBufferNewPage(VP8TBuffer* const b) {
+  VP8Tokens* const page = b->error_ ? NULL : (VP8Tokens*)malloc(sizeof(*page));
+  if (page == NULL) {
+    b->error_ = 1;
+    return 0;
+  }
+  *b->last_ = page;
+  b->last_ = &page->next_;
+  b->left_ = MAX_NUM_TOKEN;
+  b->tokens_ = page->tokens_;
+  return 1;
+}
+
+void VP8TBufferClear(VP8TBuffer* const b) {
+  if (b != NULL) {
+    const VP8Tokens* p = b->rows_;
+    while (p != NULL) {
+      const VP8Tokens* const next = p->next_;
+      free((void*)p);
+      p = next;
+    }
+    VP8TBufferInit(b);
+  }
+}
+
+int VP8EmitTokens(const VP8TBuffer* const b, VP8BitWriter* const bw,
+                  const uint8_t* const probas) {
+  VP8Tokens* p = b->rows_;
+  if (b->error_) return 0;
+  while (p != NULL) {
+    const int N = (p->next_ == NULL) ? b->left_ : 0;
+    int n = MAX_NUM_TOKEN;
+    while (n-- > N) {
+      VP8PutBit(bw, (p->tokens_[n] >> 15) & 1, probas[p->tokens_[n] & 0x7fff]);
+    }
+    p = p->next_;
+  }
+  return 1;
+}
+
+#define TOKEN_ID(b, ctx, p) ((p) + NUM_PROBAS * ((ctx) + (b) * NUM_CTX))
+
+static int RecordCoeffTokens(int ctx, const VP8Residual* const res,
+                             VP8TBuffer* tokens) {
+  int n = res->first;
+  int b = VP8EncBands[n];
+  if (!VP8AddToken(tokens, res->last >= 0, TOKEN_ID(b, ctx, 0))) {
+    return 0;
+  }
+
+  while (n < 16) {
+    const int c = res->coeffs[n++];
+    const int sign = c < 0;
+    int v = sign ? -c : c;
+    const int base_id = TOKEN_ID(b, ctx, 0);
+    if (!VP8AddToken(tokens, v != 0, base_id + 1)) {
+      b = VP8EncBands[n];
+      ctx = 0;
+      continue;
+    }
+    if (!VP8AddToken(tokens, v > 1, base_id + 2)) {
+      b = VP8EncBands[n];
+      ctx = 1;
+    } else {
+      if (!VP8AddToken(tokens, v > 4, base_id + 3)) {
+        if (VP8AddToken(tokens, v != 2, base_id + 4))
+          VP8AddToken(tokens, v == 4, base_id + 5);
+      } else if (!VP8AddToken(tokens, v > 10, base_id + 6)) {
+        if (!VP8AddToken(tokens, v > 6, base_id + 7)) {
+//          VP8AddToken(tokens, v == 6, 159);
+        } else {
+//          VP8AddToken(tokens, v >= 9, 165);
+//          VP8AddToken(tokens, !(v & 1), 145);
+        }
+      } else {
+        int mask;
+        const uint8_t* tab;
+        if (v < 3 + (8 << 1)) {          // kCat3  (3b)
+          VP8AddToken(tokens, 0, base_id + 8);
+          VP8AddToken(tokens, 0, base_id + 9);
+          v -= 3 + (8 << 0);
+          mask = 1 << 2;
+          tab = kCat3;
+        } else if (v < 3 + (8 << 2)) {   // kCat4  (4b)
+          VP8AddToken(tokens, 0, base_id + 8);
+          VP8AddToken(tokens, 1, base_id + 9);
+          v -= 3 + (8 << 1);
+          mask = 1 << 3;
+          tab = kCat4;
+        } else if (v < 3 + (8 << 3)) {   // kCat5  (5b)
+          VP8AddToken(tokens, 1, base_id + 8);
+          VP8AddToken(tokens, 0, base_id + 10);
+          v -= 3 + (8 << 2);
+          mask = 1 << 4;
+          tab = kCat5;
+        } else {                         // kCat6 (11b)
+          VP8AddToken(tokens, 1, base_id + 8);
+          VP8AddToken(tokens, 1, base_id + 10);
+          v -= 3 + (8 << 3);
+          mask = 1 << 10;
+          tab = kCat6;
+        }
+        while (mask) {
+          // VP8AddToken(tokens, !!(v & mask), *tab++);
+          mask >>= 1;
+        }
+      }
+      ctx = 2;
+    }
+    b = VP8EncBands[n];
+    // VP8PutBitUniform(bw, sign);
+    if (n == 16 || !VP8AddToken(tokens, n <= res->last, TOKEN_ID(b, ctx, 0))) {
+      return 1;   // EOB
+    }
+  }
+  return 1;
+}
 
-static void RecordTokens(VP8EncIterator* const it, const VP8ModeScore* const rd,
-                         VP8TBuffer* const tokens) {
+static void RecordTokens(VP8EncIterator* const it,
+                         const VP8ModeScore* const rd, VP8TBuffer tokens[2]) {
   int x, y, ch;
   VP8Residual res;
   VP8Encoder* const enc = it->enc_;
 
   VP8IteratorNzToBytes(it);
   if (it->mb_->type_ == 1) {   // i16x16
-    const int ctx = it->top_nz_[8] + it->left_nz_[8];
     InitResidual(0, 1, enc, &res);
     SetResidualCoeffs(rd->y_dc_levels, &res);
-    it->top_nz_[8] = it->left_nz_[8] =
-        VP8RecordCoeffTokens(ctx, 1,
-                             res.first, res.last, res.coeffs, tokens);
-    RecordCoeffs(ctx, &res);
+// TODO(skal): FIX ->    it->top_nz_[8] = it->left_nz_[8] =
+      RecordCoeffTokens(it->top_nz_[8] + it->left_nz_[8], &res, &tokens[0]);
     InitResidual(1, 0, enc, &res);
   } else {
     InitResidual(0, 3, enc, &res);
@@ -636,9 +663,7 @@ static void RecordTokens(VP8EncIterator* const it, const VP8ModeScore* const rd,
       const int ctx = it->top_nz_[x] + it->left_nz_[y];
       SetResidualCoeffs(rd->y_ac_levels[x + y * 4], &res);
       it->top_nz_[x] = it->left_nz_[y] =
-          VP8RecordCoeffTokens(ctx, res.coeff_type,
-                               res.first, res.last, res.coeffs, tokens);
-      RecordCoeffs(ctx, &res);
+          RecordCoeffTokens(ctx, &res, &tokens[0]);
     }
   }
 
@@ -650,16 +675,13 @@ static void RecordTokens(VP8EncIterator* const it, const VP8ModeScore* const rd,
         const int ctx = it->top_nz_[4 + ch + x] + it->left_nz_[4 + ch + y];
         SetResidualCoeffs(rd->uv_levels[ch * 2 + x + y * 2], &res);
         it->top_nz_[4 + ch + x] = it->left_nz_[4 + ch + y] =
-            VP8RecordCoeffTokens(ctx, 2,
-                                 res.first, res.last, res.coeffs, tokens);
-        RecordCoeffs(ctx, &res);
+            RecordCoeffTokens(ctx, &res, &tokens[1]);
       }
     }
   }
-  VP8IteratorBytesToNz(it);
 }
 
-#endif    // !DISABLE_TOKEN_BUFFER
+#endif    // USE_TOKEN_BUFFER
 
 //------------------------------------------------------------------------------
 // ExtraInfo map / Debug function
@@ -675,10 +697,7 @@ static void SetBlock(uint8_t* p, int value, int size) {
 #endif
 
 static void ResetSSE(VP8Encoder* const enc) {
-  enc->sse_[0] = 0;
-  enc->sse_[1] = 0;
-  enc->sse_[2] = 0;
-  // Note: enc->sse_[3] is managed by alpha.c
+  memset(enc->sse_, 0, sizeof(enc->sse_));
   enc->sse_count_ = 0;
 }
 
@@ -717,7 +736,6 @@ static void StoreSideInfo(const VP8EncIterator* const it) {
         const int b = (int)((it->luma_bits_ + it->uv_bits_ + 7) >> 3);
         *info = (b > 255) ? 255 : b; break;
       }
-      case 7: *info = mb->alpha_; break;
       default: *info = 0; break;
     };
   }
@@ -728,149 +746,62 @@ static void StoreSideInfo(const VP8EncIterator* const it) {
 #endif
 }
 
-static double GetPSNR(uint64_t mse, uint64_t size) {
-  return (mse > 0 && size > 0) ? 10. * log10(255. * 255. * size / mse) : 99;
-}
-
 //------------------------------------------------------------------------------
-//  StatLoop(): only collect statistics (number of skips, token usage, ...).
-//  This is used for deciding optimal probabilities. It also modifies the
-//  quantizer value if some target (size, PSNR) was specified.
+// Main loops
+//
+//  VP8EncLoop(): does the final bitstream coding.
 
-static void SetLoopParams(VP8Encoder* const enc, float q) {
-  // Make sure the quality parameter is inside valid bounds
-  q = Clamp(q, 0.f, 100.f);
+static void ResetAfterSkip(VP8EncIterator* const it) {
+  if (it->mb_->type_ == 1) {
+    *it->nz_ = 0;  // reset all predictors
+    it->left_nz_[8] = 0;
+  } else {
+    *it->nz_ &= (1 << 24);  // preserve the dc_nz bit
+  }
+}
 
-  VP8SetSegmentParams(enc, q);      // setup segment quantizations and filters
-  SetSegmentProbas(enc);            // compute segment probabilities
+int VP8EncLoop(VP8Encoder* const enc) {
+  int i, s, p;
+  int ok = 1;
+  VP8EncIterator it;
+  VP8ModeScore info;
+  const int dont_use_skip = !enc->proba_.use_skip_proba_;
+  const int rd_opt = enc->rd_opt_level_;
+  const int kAverageBytesPerMB = 5;     // TODO: have a kTable[quality/10]
+  const int bytes_per_parts =
+    enc->mb_w_ * enc->mb_h_ * kAverageBytesPerMB / enc->num_parts_;
+
+  // Initialize the bit-writers
+  for (p = 0; p < enc->num_parts_; ++p) {
+    VP8BitWriterInit(enc->parts_ + p, bytes_per_parts);
+  }
 
   ResetStats(enc);
   ResetSSE(enc);
-}
-
-static uint64_t OneStatPass(VP8Encoder* const enc, VP8RDLevel rd_opt,
-                            int nb_mbs, int percent_delta,
-                            PassStats* const s) {
-  VP8EncIterator it;
-  uint64_t size = 0;
-  uint64_t size_p0 = 0;
-  uint64_t distortion = 0;
-  const uint64_t pixel_count = nb_mbs * 384;
 
   VP8IteratorInit(enc, &it);
-  SetLoopParams(enc, s->q);
+  VP8InitFilter(&it);
   do {
-    VP8ModeScore info;
-    VP8IteratorImport(&it, NULL);
-    if (VP8Decimate(&it, &info, rd_opt)) {
-      // Just record the number of skips and act like skip_proba is not used.
-      enc->proba_.nb_skip_++;
+    VP8IteratorImport(&it);
+    // Warning! order is important: first call VP8Decimate() and
+    // *then* decide how to code the skip decision if there's one.
+    if (!VP8Decimate(&it, &info, rd_opt) || dont_use_skip) {
+      CodeResiduals(it.bw_, &it, &info);
+    } else {   // reset predictors after a skip
+      ResetAfterSkip(&it);
     }
-    RecordResiduals(&it, &info);
-    size += info.R + info.H;
-    size_p0 += info.H;
-    distortion += info.D;
-    if (percent_delta && !VP8IteratorProgress(&it, percent_delta))
-      return 0;
-    VP8IteratorSaveBoundary(&it);
-  } while (VP8IteratorNext(&it) && --nb_mbs > 0);
-
-  size_p0 += enc->segment_hdr_.size_;
-  if (s->do_size_search) {
-    size += FinalizeSkipProba(enc);
-    size += FinalizeTokenProbas(&enc->proba_);
-    size = ((size + size_p0 + 1024) >> 11) + HEADER_SIZE_ESTIMATE;
-    s->value = (double)size;
-  } else {
-    s->value = GetPSNR(distortion, pixel_count);
-  }
-  return size_p0;
-}
-
-static int StatLoop(VP8Encoder* const enc) {
-  const int method = enc->method_;
-  const int do_search = enc->do_search_;
-  const int fast_probe = ((method == 0 || method == 3) && !do_search);
-  int num_pass_left = enc->config_->pass;
-  const int task_percent = 20;
-  const int percent_per_pass =
-      (task_percent + num_pass_left / 2) / num_pass_left;
-  const int final_percent = enc->percent_ + task_percent;
-  const VP8RDLevel rd_opt =
-      (method >= 3 || do_search) ? RD_OPT_BASIC : RD_OPT_NONE;
-  int nb_mbs = enc->mb_w_ * enc->mb_h_;
-  PassStats stats;
-
-  InitPassStats(enc, &stats);
-  ResetTokenStats(enc);
-
-  // Fast mode: quick analysis pass over few mbs. Better than nothing.
-  if (fast_probe) {
-    if (method == 3) {  // we need more stats for method 3 to be reliable.
-      nb_mbs = (nb_mbs > 200) ? nb_mbs >> 1 : 100;
-    } else {
-      nb_mbs = (nb_mbs > 200) ? nb_mbs >> 2 : 50;
+#ifdef WEBP_EXPERIMENTAL_FEATURES
+    if (enc->use_layer_) {
+      VP8EncCodeLayerBlock(&it);
     }
-  }
-
-  while (num_pass_left-- > 0) {
-    const int is_last_pass = (fabs(stats.dq) <= DQ_LIMIT) ||
-                             (num_pass_left == 0) ||
-                             (enc->max_i4_header_bits_ == 0);
-    const uint64_t size_p0 =
-        OneStatPass(enc, rd_opt, nb_mbs, percent_per_pass, &stats);
-    if (size_p0 == 0) return 0;
-#if (DEBUG_SEARCH > 0)
-    printf("#%d value:%.1lf -> %.1lf   q:%.2f -> %.2f\n",
-           num_pass_left, stats.last_value, stats.value, stats.last_q, stats.q);
 #endif
-    if (enc->max_i4_header_bits_ > 0 && size_p0 > PARTITION0_SIZE_LIMIT) {
-      ++num_pass_left;
-      enc->max_i4_header_bits_ >>= 1;  // strengthen header bit limitation...
-      continue;                        // ...and start over
-    }
-    if (is_last_pass) {
-      break;
-    }
-    // If no target size: just do several pass without changing 'q'
-    if (do_search) {
-      ComputeNextQ(&stats);
-      if (fabs(stats.dq) <= DQ_LIMIT) break;
-    }
-  }
-  if (!do_search || !stats.do_size_search) {
-    // Need to finalize probas now, since it wasn't done during the search.
-    FinalizeSkipProba(enc);
-    FinalizeTokenProbas(&enc->proba_);
-  }
-  VP8CalculateLevelCosts(&enc->proba_);  // finalize costs
-  return WebPReportProgress(enc->pic_, final_percent, &enc->percent_);
-}
-
-//------------------------------------------------------------------------------
-// Main loops
-//
-
-static const int kAverageBytesPerMB[8] = { 50, 24, 16, 9, 7, 5, 3, 2 };
-
-static int PreLoopInitialize(VP8Encoder* const enc) {
-  int p;
-  int ok = 1;
-  const int average_bytes_per_MB = kAverageBytesPerMB[enc->base_quant_ >> 4];
-  const int bytes_per_parts =
-      enc->mb_w_ * enc->mb_h_ * average_bytes_per_MB / enc->num_parts_;
-  // Initialize the bit-writers
-  for (p = 0; ok && p < enc->num_parts_; ++p) {
-    ok = VP8BitWriterInit(enc->parts_ + p, bytes_per_parts);
-  }
-  if (!ok) VP8EncFreeBitWriters(enc);  // malloc error occurred
-  return ok;
-}
+    StoreSideInfo(&it);
+    VP8StoreFilterStats(&it);
+    VP8IteratorExport(&it);
+    ok = VP8IteratorProgress(&it, 20);
+  } while (ok && VP8IteratorNext(&it, it.yuv_out_));
 
-static int PostLoopFinalize(VP8EncIterator* const it, int ok) {
-  VP8Encoder* const enc = it->enc_;
   if (ok) {      // Finalize the partitions, check for extra errors.
-    int p;
     for (p = 0; p < enc->num_parts_; ++p) {
       VP8BitWriterFinish(enc->parts_ + p);
       ok &= !enc->parts_[p].error_;
@@ -878,191 +809,131 @@ static int PostLoopFinalize(VP8EncIterator* const it, int ok) {
   }
 
   if (ok) {      // All good. Finish up.
-    if (enc->pic_->stats != NULL) {  // finalize byte counters...
-      int i, s;
+    if (enc->pic_->stats) {           // finalize byte counters...
       for (i = 0; i <= 2; ++i) {
         for (s = 0; s < NUM_MB_SEGMENTS; ++s) {
-          enc->residual_bytes_[i][s] = (int)((it->bit_count_[s][i] + 7) >> 3);
+          enc->residual_bytes_[i][s] = (int)((it.bit_count_[s][i] + 7) >> 3);
         }
       }
     }
-    VP8AdjustFilterStrength(it);     // ...and store filter stats.
+    VP8AdjustFilterStrength(&it);     // ...and store filter stats.
   } else {
     // Something bad happened -> need to do some memory cleanup.
     VP8EncFreeBitWriters(enc);
   }
+
   return ok;
 }
 
 //------------------------------------------------------------------------------
-//  VP8EncLoop(): does the final bitstream coding.
+//  VP8StatLoop(): only collect statistics (number of skips, token usage, ...)
+//                 This is used for deciding optimal probabilities. It also
+//                 modifies the quantizer value if some target (size, PNSR)
+//                 was specified.
 
-static void ResetAfterSkip(VP8EncIterator* const it) {
-  if (it->mb_->type_ == 1) {
-    *it->nz_ = 0;  // reset all predictors
-    it->left_nz_[8] = 0;
-  } else {
-    *it->nz_ &= (1 << 24);  // preserve the dc_nz bit
-  }
-}
+#define kHeaderSizeEstimate (15 + 20 + 10)      // TODO: fix better
 
-int VP8EncLoop(VP8Encoder* const enc) {
+static int OneStatPass(VP8Encoder* const enc, float q, int rd_opt, int nb_mbs,
+                       float* const PSNR, int percent_delta) {
   VP8EncIterator it;
-  int ok = PreLoopInitialize(enc);
-  if (!ok) return 0;
+  uint64_t size = 0;
+  uint64_t distortion = 0;
+  const uint64_t pixel_count = nb_mbs * 384;
 
-  StatLoop(enc);  // stats-collection loop
+  // Make sure the quality parameter is inside valid bounds
+  if (q < 0.) {
+    q = 0;
+  } else if (q > 100.) {
+    q = 100;
+  }
+
+  VP8SetSegmentParams(enc, q);      // setup segment quantizations and filters
+
+  ResetStats(enc);
+  ResetTokenStats(enc);
 
   VP8IteratorInit(enc, &it);
-  VP8InitFilter(&it);
   do {
     VP8ModeScore info;
-    const int dont_use_skip = !enc->proba_.use_skip_proba_;
-    const VP8RDLevel rd_opt = enc->rd_opt_level_;
-
-    VP8IteratorImport(&it, NULL);
-    // Warning! order is important: first call VP8Decimate() and
-    // *then* decide how to code the skip decision if there's one.
-    if (!VP8Decimate(&it, &info, rd_opt) || dont_use_skip) {
-      CodeResiduals(it.bw_, &it, &info);
-    } else {   // reset predictors after a skip
-      ResetAfterSkip(&it);
-    }
-#ifdef WEBP_EXPERIMENTAL_FEATURES
-    if (enc->use_layer_) {
-      VP8EncCodeLayerBlock(&it);
+    VP8IteratorImport(&it);
+    if (VP8Decimate(&it, &info, rd_opt)) {
+      // Just record the number of skips and act like skip_proba is not used.
+      enc->proba_.nb_skip_++;
     }
-#endif
-    StoreSideInfo(&it);
-    VP8StoreFilterStats(&it);
-    VP8IteratorExport(&it);
-    ok = VP8IteratorProgress(&it, 20);
-    VP8IteratorSaveBoundary(&it);
-  } while (ok && VP8IteratorNext(&it));
+    RecordResiduals(&it, &info);
+    size += info.R;
+    distortion += info.D;
+    if (percent_delta && !VP8IteratorProgress(&it, percent_delta))
+      return 0;
+  } while (VP8IteratorNext(&it, it.yuv_out_) && --nb_mbs > 0);
+  size += FinalizeSkipProba(enc);
+  size += FinalizeTokenProbas(enc);
+  size += enc->segment_hdr_.size_;
+  size = ((size + 1024) >> 11) + kHeaderSizeEstimate;
 
-  return PostLoopFinalize(&it, ok);
+  if (PSNR) {
+    *PSNR = (float)(10.* log10(255. * 255. * pixel_count / distortion));
+  }
+  return (int)size;
 }
 
-//------------------------------------------------------------------------------
-// Single pass using Token Buffer.
-
-#if !defined(DISABLE_TOKEN_BUFFER)
+// successive refinement increments.
+static const int dqs[] = { 20, 15, 10, 8, 6, 4, 2, 1, 0 };
 
-#define MIN_COUNT 96  // minimum number of macroblocks before updating stats
+int VP8StatLoop(VP8Encoder* const enc) {
+  const int do_search =
+    (enc->config_->target_size > 0 || enc->config_->target_PSNR > 0);
+  const int fast_probe = (enc->method_ < 2 && !do_search);
+  float q = enc->config_->quality;
+  const int max_passes = enc->config_->pass;
+  const int task_percent = 20;
+  const int percent_per_pass = (task_percent + max_passes / 2) / max_passes;
+  const int final_percent = enc->percent_ + task_percent;
+  int pass;
+  int nb_mbs;
 
-int VP8EncTokenLoop(VP8Encoder* const enc) {
-  // Roughly refresh the proba eight times per pass
-  int max_count = (enc->mb_w_ * enc->mb_h_) >> 3;
-  int num_pass_left = enc->config_->pass;
-  const int do_search = enc->do_search_;
-  VP8EncIterator it;
-  VP8Proba* const proba = &enc->proba_;
-  const VP8RDLevel rd_opt = enc->rd_opt_level_;
-  const uint64_t pixel_count = enc->mb_w_ * enc->mb_h_ * 384;
-  PassStats stats;
-  int ok;
-
-  InitPassStats(enc, &stats);
-  ok = PreLoopInitialize(enc);
-  if (!ok) return 0;
-
-  if (max_count < MIN_COUNT) max_count = MIN_COUNT;
-
-  assert(enc->num_parts_ == 1);
-  assert(enc->use_tokens_);
-  assert(proba->use_skip_proba_ == 0);
-  assert(rd_opt >= RD_OPT_BASIC);   // otherwise, token-buffer won't be useful
-  assert(num_pass_left > 0);
-
-  while (ok && num_pass_left-- > 0) {
-    const int is_last_pass = (fabs(stats.dq) <= DQ_LIMIT) ||
-                             (num_pass_left == 0) ||
-                             (enc->max_i4_header_bits_ == 0);
-    uint64_t size_p0 = 0;
-    uint64_t distortion = 0;
-    int cnt = max_count;
-    VP8IteratorInit(enc, &it);
-    SetLoopParams(enc, stats.q);
-    if (is_last_pass) {
-      ResetTokenStats(enc);
-      VP8InitFilter(&it);  // don't collect stats until last pass (too costly)
-    }
-    VP8TBufferClear(&enc->tokens_);
-    do {
-      VP8ModeScore info;
-      VP8IteratorImport(&it, NULL);
-      if (--cnt < 0) {
-        FinalizeTokenProbas(proba);
-        VP8CalculateLevelCosts(proba);  // refresh cost tables for rd-opt
-        cnt = max_count;
-      }
-      VP8Decimate(&it, &info, rd_opt);
-      RecordTokens(&it, &info, &enc->tokens_);
-      size_p0 += info.H;
-      distortion += info.D;
-#ifdef WEBP_EXPERIMENTAL_FEATURES
-      if (enc->use_layer_) {
-        VP8EncCodeLayerBlock(&it);
-      }
-#endif
-      if (is_last_pass) {
-        StoreSideInfo(&it);
-        VP8StoreFilterStats(&it);
-        VP8IteratorExport(&it);
-        ok = VP8IteratorProgress(&it, 20);
+  // Fast mode: quick analysis pass over few mbs. Better than nothing.
+  nb_mbs = enc->mb_w_ * enc->mb_h_;
+  if (fast_probe && nb_mbs > 100) nb_mbs = 100;
+
+  // No target size: just do several pass without changing 'q'
+  if (!do_search) {
+    for (pass = 0; pass < max_passes; ++pass) {
+      const int rd_opt = (enc->method_ > 2);
+      if (!OneStatPass(enc, q, rd_opt, nb_mbs, NULL, percent_per_pass)) {
+        return 0;
       }
-      VP8IteratorSaveBoundary(&it);
-    } while (ok && VP8IteratorNext(&it));
-    if (!ok) break;
-
-    size_p0 += enc->segment_hdr_.size_;
-    if (stats.do_size_search) {
-      uint64_t size = FinalizeTokenProbas(&enc->proba_);
-      size += VP8EstimateTokenSize(&enc->tokens_,
-                                   (const uint8_t*)proba->coeffs_);
-      size = (size + size_p0 + 1024) >> 11;  // -> size in bytes
-      size += HEADER_SIZE_ESTIMATE;
-      stats.value = (double)size;
-    } else {  // compute and store PSNR
-      stats.value = GetPSNR(distortion, pixel_count);
     }
-
-#if (DEBUG_SEARCH > 0)
-    printf("#%2d metric:%.1lf -> %.1lf   last_q=%.2lf q=%.2lf dq=%.2lf\n",
-           num_pass_left, stats.last_value, stats.value,
-           stats.last_q, stats.q, stats.dq);
+  } else {
+    // binary search for a size close to target
+    for (pass = 0; pass < max_passes && (dqs[pass] > 0); ++pass) {
+      const int rd_opt = 1;
+      float PSNR;
+      int criterion;
+      const int size = OneStatPass(enc, q, rd_opt, nb_mbs, &PSNR,
+                                   percent_per_pass);
+#if DEBUG_SEARCH
+      printf("#%d size=%d PSNR=%.2f q=%.2f\n", pass, size, PSNR, q);
 #endif
-    if (size_p0 > PARTITION0_SIZE_LIMIT) {
-      ++num_pass_left;
-      enc->max_i4_header_bits_ >>= 1;  // strengthen header bit limitation...
-      continue;                        // ...and start over
-    }
-    if (is_last_pass) {
-      break;   // done
-    }
-    if (do_search) {
-      ComputeNextQ(&stats);  // Adjust q
-    }
-  }
-  if (ok) {
-    if (!stats.do_size_search) {
-      FinalizeTokenProbas(&enc->proba_);
+      if (!size) return 0;
+      if (enc->config_->target_PSNR > 0) {
+        criterion = (PSNR < enc->config_->target_PSNR);
+      } else {
+        criterion = (size < enc->config_->target_size);
+      }
+      // dichotomize
+      if (criterion) {
+        q += dqs[pass];
+      } else {
+        q -= dqs[pass];
+      }
     }
-    ok = VP8EmitTokens(&enc->tokens_, enc->parts_ + 0,
-                       (const uint8_t*)proba->coeffs_, 1);
   }
-  ok = ok && WebPReportProgress(enc->pic_, enc->percent_ + 20, &enc->percent_);
-  return PostLoopFinalize(&it, ok);
-}
-
-#else
-
-int VP8EncTokenLoop(VP8Encoder* const enc) {
-  (void)enc;
-  return 0;   // we shouldn't be here.
+  return WebPReportProgress(enc->pic_, final_percent, &enc->percent_);
 }
 
-#endif    // DISABLE_TOKEN_BUFFER
-
 //------------------------------------------------------------------------------
 
+#if defined(__cplusplus) || defined(c_plusplus)
+}    // extern "C"
+#endif