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 "src/enc/cost_enc.h" |
24 | #include "src/enc/vp8i_enc.h" |
25 | #include "src/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 | } |
143 | } else if (!AddToken(tokens, v > 10, base_id + 6, s + 6)) { |
144 | if (!AddToken(tokens, v > 6, base_id + 7, s + 7)) { |
145 | AddConstantToken(tokens, v == 6, 159); |
146 | } else { |
147 | AddConstantToken(tokens, v >= 9, 165); |
148 | AddConstantToken(tokens, !(v & 1), 145); |
149 | } |
150 | } else { |
151 | int mask; |
152 | const uint8_t* tab; |
153 | uint32_t residue = v - 3; |
154 | if (residue < (8 << 1)) { // VP8Cat3 (3b) |
155 | AddToken(tokens, 0, base_id + 8, s + 8); |
156 | AddToken(tokens, 0, base_id + 9, s + 9); |
157 | residue -= (8 << 0); |
158 | mask = 1 << 2; |
159 | tab = VP8Cat3; |
160 | } else if (residue < (8 << 2)) { // VP8Cat4 (4b) |
161 | AddToken(tokens, 0, base_id + 8, s + 8); |
162 | AddToken(tokens, 1, base_id + 9, s + 9); |
163 | residue -= (8 << 1); |
164 | mask = 1 << 3; |
165 | tab = VP8Cat4; |
166 | } else if (residue < (8 << 3)) { // VP8Cat5 (5b) |
167 | AddToken(tokens, 1, base_id + 8, s + 8); |
168 | AddToken(tokens, 0, base_id + 10, s + 9); |
169 | residue -= (8 << 2); |
170 | mask = 1 << 4; |
171 | tab = VP8Cat5; |
172 | } else { // VP8Cat6 (11b) |
173 | AddToken(tokens, 1, base_id + 8, s + 8); |
174 | AddToken(tokens, 1, base_id + 10, s + 9); |
175 | residue -= (8 << 3); |
176 | mask = 1 << 10; |
177 | tab = VP8Cat6; |
178 | } |
179 | while (mask) { |
180 | AddConstantToken(tokens, !!(residue & mask), *tab++); |
181 | mask >>= 1; |
182 | } |
183 | } |
184 | base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 2); // ctx=2 |
185 | s = res->stats[VP8EncBands[n]][2]; |
186 | } |
187 | AddConstantToken(tokens, sign, 128); |
188 | if (n == 16 || !AddToken(tokens, n <= last, base_id + 0, s + 0)) { |
189 | return 1; // EOB |
190 | } |
191 | } |
192 | return 1; |
193 | } |
194 | |
195 | #undef TOKEN_ID |
196 | |
197 | //------------------------------------------------------------------------------ |
198 | // Final coding pass, with known probabilities |
199 | |
200 | int VP8EmitTokens(VP8TBuffer* const b, VP8BitWriter* const bw, |
201 | const uint8_t* const probas, int final_pass) { |
202 | const VP8Tokens* p = b->pages_; |
203 | assert(!b->error_); |
204 | while (p != NULL) { |
205 | const VP8Tokens* const next = p->next_; |
206 | const int N = (next == NULL) ? b->left_ : 0; |
207 | int n = b->page_size_; |
208 | const token_t* const tokens = TOKEN_DATA(p); |
209 | while (n-- > N) { |
210 | const token_t token = tokens[n]; |
211 | const int bit = (token >> 15) & 1; |
212 | if (token & FIXED_PROBA_BIT) { |
213 | VP8PutBit(bw, bit, token & 0xffu); // constant proba |
214 | } else { |
215 | VP8PutBit(bw, bit, probas[token & 0x3fffu]); |
216 | } |
217 | } |
218 | if (final_pass) WebPSafeFree((void*)p); |
219 | p = next; |
220 | } |
221 | if (final_pass) b->pages_ = NULL; |
222 | return 1; |
223 | } |
224 | |
225 | // Size estimation |
226 | size_t VP8EstimateTokenSize(VP8TBuffer* const b, const uint8_t* const probas) { |
227 | size_t size = 0; |
228 | const VP8Tokens* p = b->pages_; |
229 | assert(!b->error_); |
230 | while (p != NULL) { |
231 | const VP8Tokens* const next = p->next_; |
232 | const int N = (next == NULL) ? b->left_ : 0; |
233 | int n = b->page_size_; |
234 | const token_t* const tokens = TOKEN_DATA(p); |
235 | while (n-- > N) { |
236 | const token_t token = tokens[n]; |
237 | const int bit = token & (1 << 15); |
238 | if (token & FIXED_PROBA_BIT) { |
239 | size += VP8BitCost(bit, token & 0xffu); |
240 | } else { |
241 | size += VP8BitCost(bit, probas[token & 0x3fffu]); |
242 | } |
243 | } |
244 | p = next; |
245 | } |
246 | return size; |
247 | } |
248 | |
249 | //------------------------------------------------------------------------------ |
250 | |
251 | #else // DISABLE_TOKEN_BUFFER |
252 | |
253 | void VP8TBufferInit(VP8TBuffer* const b, int page_size) { |
254 | (void)b; |
255 | (void)page_size; |
256 | } |
257 | void VP8TBufferClear(VP8TBuffer* const b) { |
258 | (void)b; |
259 | } |
260 | |
261 | #endif // !DISABLE_TOKEN_BUFFER |
262 | |
263 | |