third_party/libwebp/enc/token.c

   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 // Paginated token buffer
  11 //
  12 //  A 'token' is a bit value associated with a probability, either fixed
  13 // or a later-to-be-determined after statistics have been collected.
  14 // For dynamic probability, we just record the slot id (idx) for the probability
  15 // value in the final probability array (uint8_t* probas in VP8EmitTokens).
  16 //
  17 // Author: Skal (pascal.massimino@gmail.com)
  18
  19 #include <assert.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22
  23 #include "./cost.h"
  24 #include "./vp8enci.h"
  25
  26 #if !defined(DISABLE_TOKEN_BUFFER)
  27
  28 // we use pages to reduce the number of memcpy()
  29 #define MAX_NUM_TOKEN 8192          // max number of token per page
  30 #define FIXED_PROBA_BIT (1u << 14)
  31
  32 struct VP8Tokens {
  33   uint16_t tokens_[MAX_NUM_TOKEN];  // bit#15: bit
  34                                     // bit #14: constant proba or idx
  35                                     // bits 0..13: slot or constant proba
  36   VP8Tokens* next_;
  37 };
  38
  39 //------------------------------------------------------------------------------
  40
  41 void VP8TBufferInit(VP8TBuffer* const b) {
  42   b->tokens_ = NULL;
  43   b->pages_ = NULL;
  44   b->last_page_ = &b->pages_;
  45   b->left_ = 0;
  46   b->error_ = 0;
  47 }
  48
  49 void VP8TBufferClear(VP8TBuffer* const b) {
  50   if (b != NULL) {
  51     const VP8Tokens* p = b->pages_;
  52     while (p != NULL) {
  53       const VP8Tokens* const next = p->next_;
  54       free((void*)p);
  55       p = next;
  56     }
  57     VP8TBufferInit(b);
  58   }
  59 }
  60
  61 static int TBufferNewPage(VP8TBuffer* const b) {
  62   VP8Tokens* const page = b->error_ ? NULL : (VP8Tokens*)malloc(sizeof(*page));
  63   if (page == NULL) {
  64     b->error_ = 1;
  65     return 0;
  66   }
  67   *b->last_page_ = page;
  68   b->last_page_ = &page->next_;
  69   b->left_ = MAX_NUM_TOKEN;
  70   b->tokens_ = page->tokens_;
  71   page->next_ = NULL;
  72   return 1;
  73 }
  74
  75 //------------------------------------------------------------------------------
  76
  77 #define TOKEN_ID(t, b, ctx, p) \
  78     ((p) + NUM_PROBAS * ((ctx) + NUM_CTX * ((b) + NUM_BANDS * (t))))
  79
  80 static WEBP_INLINE int AddToken(VP8TBuffer* const b,
  81                                 int bit, uint32_t proba_idx) {
  82   assert(proba_idx < FIXED_PROBA_BIT);
  83   assert(bit == 0 || bit == 1);
  84   if (b->left_ > 0 || TBufferNewPage(b)) {
  85     const int slot = --b->left_;
  86     b->tokens_[slot] = (bit << 15) | proba_idx;
  87   }
  88   return bit;
  89 }
  90
  91 static WEBP_INLINE void AddConstantToken(VP8TBuffer* const b,
  92                                          int bit, int proba) {
  93   assert(proba < 256);
  94   assert(bit == 0 || bit == 1);
  95   if (b->left_ > 0 || TBufferNewPage(b)) {
  96     const int slot = --b->left_;
  97     b->tokens_[slot] = (bit << 15) | FIXED_PROBA_BIT | proba;
  98   }
  99 }
 100
 101 int VP8RecordCoeffTokens(int ctx, int coeff_type, int first, int last,
 102                          const int16_t* const coeffs,
 103                          VP8TBuffer* const tokens) {
 104   int n = first;
 105   uint32_t base_id = TOKEN_ID(coeff_type, n, ctx, 0);
 106   if (!AddToken(tokens, last >= 0, base_id + 0)) {
 107     return 0;
 108   }
 109
 110   while (n < 16) {
 111     const int c = coeffs[n++];
 112     const int sign = c < 0;
 113     int v = sign ? -c : c;
 114     if (!AddToken(tokens, v != 0, base_id + 1)) {
 115       ctx = 0;
 116       base_id = TOKEN_ID(coeff_type, VP8EncBands[n], ctx, 0);
 117       continue;
 118     }
 119     if (!AddToken(tokens, v > 1, base_id + 2)) {
 120       ctx = 1;
 121     } else {
 122       if (!AddToken(tokens, v > 4, base_id + 3)) {
 123         if (AddToken(tokens, v != 2, base_id + 4))
 124           AddToken(tokens, v == 4, base_id + 5);
 125       } else if (!AddToken(tokens, v > 10, base_id + 6)) {
 126         if (!AddToken(tokens, v > 6, base_id + 7)) {
 127           AddConstantToken(tokens, v == 6, 159);
 128         } else {
 129           AddConstantToken(tokens, v >= 9, 165);
 130           AddConstantToken(tokens, !(v & 1), 145);
 131         }
 132       } else {
 133         int mask;
 134         const uint8_t* tab;
 135         if (v < 3 + (8 << 1)) {          // VP8Cat3  (3b)
 136           AddToken(tokens, 0, base_id + 8);
 137           AddToken(tokens, 0, base_id + 9);
 138           v -= 3 + (8 << 0);
 139           mask = 1 << 2;
 140           tab = VP8Cat3;
 141         } else if (v < 3 + (8 << 2)) {   // VP8Cat4  (4b)
 142           AddToken(tokens, 0, base_id + 8);
 143           AddToken(tokens, 1, base_id + 9);
 144           v -= 3 + (8 << 1);
 145           mask = 1 << 3;
 146           tab = VP8Cat4;
 147         } else if (v < 3 + (8 << 3)) {   // VP8Cat5  (5b)
 148           AddToken(tokens, 1, base_id + 8);
 149           AddToken(tokens, 0, base_id + 10);
 150           v -= 3 + (8 << 2);
 151           mask = 1 << 4;
 152           tab = VP8Cat5;
 153         } else {                         // VP8Cat6 (11b)
 154           AddToken(tokens, 1, base_id + 8);
 155           AddToken(tokens, 1, base_id + 10);
 156           v -= 3 + (8 << 3);
 157           mask = 1 << 10;
 158           tab = VP8Cat6;
 159         }
 160         while (mask) {
 161           AddConstantToken(tokens, !!(v & mask), *tab++);
 162           mask >>= 1;
 163         }
 164       }
 165       ctx = 2;
 166     }
 167     AddConstantToken(tokens, sign, 128);
 168     base_id = TOKEN_ID(coeff_type, VP8EncBands[n], ctx, 0);
 169     if (n == 16 || !AddToken(tokens, n <= last, base_id + 0)) {
 170       return 1;   // EOB
 171     }
 172   }
 173   return 1;
 174 }
 175
 176 #undef TOKEN_ID
 177
 178 //------------------------------------------------------------------------------
 179 // This function works, but isn't currently used. Saved for later.
 180
 181 #if 0
 182
 183 static void Record(int bit, proba_t* const stats) {
 184   proba_t p = *stats;
 185   if (p >= 0xffff0000u) {               // an overflow is inbound.
 186     p = ((p + 1u) >> 1) & 0x7fff7fffu;  // -> divide the stats by 2.
 187   }
 188   // record bit count (lower 16 bits) and increment total count (upper 16 bits).
 189   p += 0x00010000u + bit;
 190   *stats = p;
 191 }
 192
 193 void VP8TokenToStats(const VP8TBuffer* const b, proba_t* const stats) {
 194   const VP8Tokens* p = b->pages_;
 195   while (p != NULL) {
 196     const int N = (p->next_ == NULL) ? b->left_ : 0;
 197     int n = MAX_NUM_TOKEN;
 198     while (n-- > N) {
 199       const uint16_t token = p->tokens_[n];
 200       if (!(token & FIXED_PROBA_BIT)) {
 201         Record((token >> 15) & 1, stats + (token & 0x3fffu));
 202       }
 203     }
 204     p = p->next_;
 205   }
 206 }
 207
 208 #endif   // 0
 209
 210 //------------------------------------------------------------------------------
 211 // Final coding pass, with known probabilities
 212
 213 int VP8EmitTokens(VP8TBuffer* const b, VP8BitWriter* const bw,
 214                   const uint8_t* const probas, int final_pass) {
 215   const VP8Tokens* p = b->pages_;
 216   (void)final_pass;
 217   if (b->error_) return 0;
 218   while (p != NULL) {
 219     const VP8Tokens* const next = p->next_;
 220     const int N = (next == NULL) ? b->left_ : 0;
 221     int n = MAX_NUM_TOKEN;
 222     while (n-- > N) {
 223       const uint16_t token = p->tokens_[n];
 224       const int bit = (token >> 15) & 1;
 225       if (token & FIXED_PROBA_BIT) {
 226         VP8PutBit(bw, bit, token & 0xffu);  // constant proba
 227       } else {
 228         VP8PutBit(bw, bit, probas[token & 0x3fffu]);
 229       }
 230     }
 231     if (final_pass) free((void*)p);
 232     p = next;
 233   }
 234   if (final_pass) b->pages_ = NULL;
 235   return 1;
 236 }
 237
 238 // Size estimation
 239 size_t VP8EstimateTokenSize(VP8TBuffer* const b, const uint8_t* const probas) {
 240   size_t size = 0;
 241   const VP8Tokens* p = b->pages_;
 242   if (b->error_) return 0;
 243   while (p != NULL) {
 244     const VP8Tokens* const next = p->next_;
 245     const int N = (next == NULL) ? b->left_ : 0;
 246     int n = MAX_NUM_TOKEN;
 247     while (n-- > N) {
 248       const uint16_t token = p->tokens_[n];
 249       const int bit = token & (1 << 15);
 250       if (token & FIXED_PROBA_BIT) {
 251         size += VP8BitCost(bit, token & 0xffu);
 252       } else {
 253         size += VP8BitCost(bit, probas[token & 0x3fffu]);
 254       }
 255     }
 256     p = next;
 257   }
 258   return size;
 259 }
 260
 261 //------------------------------------------------------------------------------
 262
 263 #else     // DISABLE_TOKEN_BUFFER
 264
 265 void VP8TBufferInit(VP8TBuffer* const b) {
 266   (void)b;
 267 }
 268 void VP8TBufferClear(VP8TBuffer* const b) {
 269   (void)b;
 270 }
 271
 272 #endif    // !DISABLE_TOKEN_BUFFER
 273