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