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 "./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
VP8TBufferInit(VP8TBuffer * const b)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
VP8TBufferClear(VP8TBuffer * const b)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
TBufferNewPage(VP8TBuffer * const b)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
AddToken(VP8TBuffer * const b,int bit,uint32_t proba_idx)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
AddConstantToken(VP8TBuffer * const b,int bit,int proba)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
VP8RecordCoeffTokens(int ctx,int coeff_type,int first,int last,const int16_t * const coeffs,VP8TBuffer * const tokens)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
VP8EmitTokens(VP8TBuffer * const b,VP8BitWriter * const bw,const uint8_t * const probas,int final_pass)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