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