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