| OLD | NEW |
|---|
| (Empty) |
| 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 value | |
| 34 // bit #14: flags for 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) ((const 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 VP8Tokens* p = b->pages_; | |
| 57 while (p != NULL) { | |
| 58 VP8Tokens* const next = p->next_; | |
| 59 WebPSafeFree(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 if (!b->error_) { | |
| 69 const size_t size = sizeof(*page) + b->page_size_ * sizeof(token_t); | |
| 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_t*)TOKEN_DATA(page); | |
| 82 return 1; | |
| 83 } | |
| 84 | |
| 85 //------------------------------------------------------------------------------ | |
| 86 | |
| 87 #define TOKEN_ID(t, b, ctx) \ | |
| 88 (NUM_PROBAS * ((ctx) + NUM_CTX * ((b) + NUM_BANDS * (t)))) | |
| 89 | |
| 90 static WEBP_INLINE uint32_t AddToken(VP8TBuffer* const b, uint32_t bit, | |
| 91 uint32_t proba_idx, | |
| 92 proba_t* const stats) { | |
| 93 assert(proba_idx < FIXED_PROBA_BIT); | |
| 94 assert(bit <= 1); | |
| 95 if (b->left_ > 0 || TBufferNewPage(b)) { | |
| 96 const int slot = --b->left_; | |
| 97 b->tokens_[slot] = (bit << 15) | proba_idx; | |
| 98 } | |
| 99 VP8RecordStats(bit, stats); | |
| 100 return bit; | |
| 101 } | |
| 102 | |
| 103 static WEBP_INLINE void AddConstantToken(VP8TBuffer* const b, | |
| 104 uint32_t bit, uint32_t proba) { | |
| 105 assert(proba < 256); | |
| 106 assert(bit <= 1); | |
| 107 if (b->left_ > 0 || TBufferNewPage(b)) { | |
| 108 const int slot = --b->left_; | |
| 109 b->tokens_[slot] = (bit << 15) | FIXED_PROBA_BIT | proba; | |
| 110 } | |
| 111 } | |
| 112 | |
| 113 int VP8RecordCoeffTokens(int ctx, const struct VP8Residual* const res, | |
| 114 VP8TBuffer* const tokens) { | |
| 115 const int16_t* const coeffs = res->coeffs; | |
| 116 const int coeff_type = res->coeff_type; | |
| 117 const int last = res->last; | |
| 118 int n = res->first; | |
| 119 uint32_t base_id = TOKEN_ID(coeff_type, n, ctx); | |
| 120 // should be stats[VP8EncBands[n]], but it's equivalent for n=0 or 1 | |
| 121 proba_t* s = res->stats[n][ctx]; | |
| 122 if (!AddToken(tokens, last >= 0, base_id + 0, s + 0)) { | |
| 123 return 0; | |
| 124 } | |
| 125 | |
| 126 while (n < 16) { | |
| 127 const int c = coeffs[n++]; | |
| 128 const int sign = c < 0; | |
| 129 const uint32_t v = sign ? -c : c; | |
| 130 if (!AddToken(tokens, v != 0, base_id + 1, s + 1)) { | |
| 131 base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 0); // ctx=0 | |
| 132 s = res->stats[VP8EncBands[n]][0]; | |
| 133 continue; | |
| 134 } | |
| 135 if (!AddToken(tokens, v > 1, base_id + 2, s + 2)) { | |
| 136 base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 1); // ctx=1 | |
| 137 s = res->stats[VP8EncBands[n]][1]; | |
| 138 } else { | |
| 139 if (!AddToken(tokens, v > 4, base_id + 3, s + 3)) { | |
| 140 if (AddToken(tokens, v != 2, base_id + 4, s + 4)) | |
| 141 AddToken(tokens, v == 4, base_id + 5, s + 5); | |
| 142 } else if (!AddToken(tokens, v > 10, base_id + 6, s + 6)) { | |
| 143 if (!AddToken(tokens, v > 6, base_id + 7, s + 7)) { | |
| 144 AddConstantToken(tokens, v == 6, 159); | |
| 145 } else { | |
| 146 AddConstantToken(tokens, v >= 9, 165); | |
| 147 AddConstantToken(tokens, !(v & 1), 145); | |
| 148 } | |
| 149 } else { | |
| 150 int mask; | |
| 151 const uint8_t* tab; | |
| 152 uint32_t residue = v - 3; | |
| 153 if (residue < (8 << 1)) { // VP8Cat3 (3b) | |
| 154 AddToken(tokens, 0, base_id + 8, s + 8); | |
| 155 AddToken(tokens, 0, base_id + 9, s + 9); | |
| 156 residue -= (8 << 0); | |
| 157 mask = 1 << 2; | |
| 158 tab = VP8Cat3; | |
| 159 } else if (residue < (8 << 2)) { // VP8Cat4 (4b) | |
| 160 AddToken(tokens, 0, base_id + 8, s + 8); | |
| 161 AddToken(tokens, 1, base_id + 9, s + 9); | |
| 162 residue -= (8 << 1); | |
| 163 mask = 1 << 3; | |
| 164 tab = VP8Cat4; | |
| 165 } else if (residue < (8 << 3)) { // VP8Cat5 (5b) | |
| 166 AddToken(tokens, 1, base_id + 8, s + 8); | |
| 167 AddToken(tokens, 0, base_id + 10, s + 9); | |
| 168 residue -= (8 << 2); | |
| 169 mask = 1 << 4; | |
| 170 tab = VP8Cat5; | |
| 171 } else { // VP8Cat6 (11b) | |
| 172 AddToken(tokens, 1, base_id + 8, s + 8); | |
| 173 AddToken(tokens, 1, base_id + 10, s + 9); | |
| 174 residue -= (8 << 3); | |
| 175 mask = 1 << 10; | |
| 176 tab = VP8Cat6; | |
| 177 } | |
| 178 while (mask) { | |
| 179 AddConstantToken(tokens, !!(residue & mask), *tab++); | |
| 180 mask >>= 1; | |
| 181 } | |
| 182 } | |
| 183 base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 2); // ctx=2 | |
| 184 s = res->stats[VP8EncBands[n]][2]; | |
| 185 } | |
| 186 AddConstantToken(tokens, sign, 128); | |
| 187 if (n == 16 || !AddToken(tokens, n <= last, base_id + 0, s + 0)) { | |
| 188 return 1; // EOB | |
| 189 } | |
| 190 } | |
| 191 return 1; | |
| 192 } | |
| 193 | |
| 194 #undef TOKEN_ID | |
| 195 | |
| 196 //------------------------------------------------------------------------------ | |
| 197 // This function works, but isn't currently used. Saved for later. | |
| 198 | |
| 199 #if 0 | |
| 200 | |
| 201 static void Record(int bit, proba_t* const stats) { | |
| 202 proba_t p = *stats; | |
| 203 if (p >= 0xffff0000u) { // an overflow is inbound. | |
| 204 p = ((p + 1u) >> 1) & 0x7fff7fffu; // -> divide the stats by 2. | |
| 205 } | |
| 206 // record bit count (lower 16 bits) and increment total count (upper 16 bits). | |
| 207 p += 0x00010000u + bit; | |
| 208 *stats = p; | |
| 209 } | |
| 210 | |
| 211 void VP8TokenToStats(const VP8TBuffer* const b, proba_t* const stats) { | |
| 212 const VP8Tokens* p = b->pages_; | |
| 213 while (p != NULL) { | |
| 214 const int N = (p->next_ == NULL) ? b->left_ : 0; | |
| 215 int n = MAX_NUM_TOKEN; | |
| 216 const token_t* const tokens = TOKEN_DATA(p); | |
| 217 while (n-- > N) { | |
| 218 const token_t token = tokens[n]; | |
| 219 if (!(token & FIXED_PROBA_BIT)) { | |
| 220 Record((token >> 15) & 1, stats + (token & 0x3fffu)); | |
| 221 } | |
| 222 } | |
| 223 p = p->next_; | |
| 224 } | |
| 225 } | |
| 226 | |
| 227 #endif // 0 | |
| 228 | |
| 229 //------------------------------------------------------------------------------ | |
| 230 // Final coding pass, with known probabilities | |
| 231 | |
| 232 int VP8EmitTokens(VP8TBuffer* const b, VP8BitWriter* const bw, | |
| 233 const uint8_t* const probas, int final_pass) { | |
| 234 const VP8Tokens* p = b->pages_; | |
| 235 assert(!b->error_); | |
| 236 while (p != NULL) { | |
| 237 const VP8Tokens* const next = p->next_; | |
| 238 const int N = (next == NULL) ? b->left_ : 0; | |
| 239 int n = b->page_size_; | |
| 240 const token_t* const tokens = TOKEN_DATA(p); | |
| 241 while (n-- > N) { | |
| 242 const token_t token = tokens[n]; | |
| 243 const int bit = (token >> 15) & 1; | |
| 244 if (token & FIXED_PROBA_BIT) { | |
| 245 VP8PutBit(bw, bit, token & 0xffu); // constant proba | |
| 246 } else { | |
| 247 VP8PutBit(bw, bit, probas[token & 0x3fffu]); | |
| 248 } | |
| 249 } | |
| 250 if (final_pass) WebPSafeFree((void*)p); | |
| 251 p = next; | |
| 252 } | |
| 253 if (final_pass) b->pages_ = NULL; | |
| 254 return 1; | |
| 255 } | |
| 256 | |
| 257 // Size estimation | |
| 258 size_t VP8EstimateTokenSize(VP8TBuffer* const b, const uint8_t* const probas) { | |
| 259 size_t size = 0; | |
| 260 const VP8Tokens* p = b->pages_; | |
| 261 assert(!b->error_); | |
| 262 while (p != NULL) { | |
| 263 const VP8Tokens* const next = p->next_; | |
| 264 const int N = (next == NULL) ? b->left_ : 0; | |
| 265 int n = b->page_size_; | |
| 266 const token_t* const tokens = TOKEN_DATA(p); | |
| 267 while (n-- > N) { | |
| 268 const token_t token = tokens[n]; | |
| 269 const int bit = token & (1 << 15); | |
| 270 if (token & FIXED_PROBA_BIT) { | |
| 271 size += VP8BitCost(bit, token & 0xffu); | |
| 272 } else { | |
| 273 size += VP8BitCost(bit, probas[token & 0x3fffu]); | |
| 274 } | |
| 275 } | |
| 276 p = next; | |
| 277 } | |
| 278 return size; | |
| 279 } | |
| 280 | |
| 281 //------------------------------------------------------------------------------ | |
| 282 | |
| 283 #else // DISABLE_TOKEN_BUFFER | |
| 284 | |
| 285 void VP8TBufferInit(VP8TBuffer* const b) { | |
| 286 (void)b; | |
| 287 } | |
| 288 void VP8TBufferClear(VP8TBuffer* const b) { | |
| 289 (void)b; | |
| 290 } | |
| 291 | |
| 292 #endif // !DISABLE_TOKEN_BUFFER | |
| 293 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2651883004:
libwebp-0.6.0-rc1 (Closed)
