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