/src/libwebp/src/enc/token_enc.c
Line | Count | Source (jump to first uncovered line) |
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 | 0 | #define MIN_PAGE_SIZE 8192 // minimum number of token per page |
31 | 0 | #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 | 0 | #define TOKEN_DATA(p) ((const token_t*)&(p)[1]) |
42 | | |
43 | | //------------------------------------------------------------------------------ |
44 | | |
45 | 0 | void VP8TBufferInit(VP8TBuffer* const b, int page_size) { |
46 | 0 | b->tokens_ = NULL; |
47 | 0 | b->pages_ = NULL; |
48 | 0 | b->last_page_ = &b->pages_; |
49 | 0 | b->left_ = 0; |
50 | 0 | b->page_size_ = (page_size < MIN_PAGE_SIZE) ? MIN_PAGE_SIZE : page_size; |
51 | 0 | b->error_ = 0; |
52 | 0 | } |
53 | | |
54 | 0 | void VP8TBufferClear(VP8TBuffer* const b) { |
55 | 0 | if (b != NULL) { |
56 | 0 | VP8Tokens* p = b->pages_; |
57 | 0 | while (p != NULL) { |
58 | 0 | VP8Tokens* const next = p->next_; |
59 | 0 | WebPSafeFree(p); |
60 | 0 | p = next; |
61 | 0 | } |
62 | 0 | VP8TBufferInit(b, b->page_size_); |
63 | 0 | } |
64 | 0 | } |
65 | | |
66 | 0 | static int TBufferNewPage(VP8TBuffer* const b) { |
67 | 0 | VP8Tokens* page = NULL; |
68 | 0 | if (!b->error_) { |
69 | 0 | const size_t size = sizeof(*page) + b->page_size_ * sizeof(token_t); |
70 | 0 | page = (VP8Tokens*)WebPSafeMalloc(1ULL, size); |
71 | 0 | } |
72 | 0 | if (page == NULL) { |
73 | 0 | b->error_ = 1; |
74 | 0 | return 0; |
75 | 0 | } |
76 | 0 | page->next_ = NULL; |
77 | |
|
78 | 0 | *b->last_page_ = page; |
79 | 0 | b->last_page_ = &page->next_; |
80 | 0 | b->left_ = b->page_size_; |
81 | 0 | b->tokens_ = (token_t*)TOKEN_DATA(page); |
82 | 0 | return 1; |
83 | 0 | } |
84 | | |
85 | | //------------------------------------------------------------------------------ |
86 | | |
87 | | #define TOKEN_ID(t, b, ctx) \ |
88 | 0 | (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 | 0 | proba_t* const stats) { |
93 | 0 | assert(proba_idx < FIXED_PROBA_BIT); |
94 | 0 | assert(bit <= 1); |
95 | 0 | if (b->left_ > 0 || TBufferNewPage(b)) { |
96 | 0 | const int slot = --b->left_; |
97 | 0 | b->tokens_[slot] = (bit << 15) | proba_idx; |
98 | 0 | } |
99 | 0 | VP8RecordStats(bit, stats); |
100 | 0 | return bit; |
101 | 0 | } |
102 | | |
103 | | static WEBP_INLINE void AddConstantToken(VP8TBuffer* const b, |
104 | 0 | uint32_t bit, uint32_t proba) { |
105 | 0 | assert(proba < 256); |
106 | 0 | assert(bit <= 1); |
107 | 0 | if (b->left_ > 0 || TBufferNewPage(b)) { |
108 | 0 | const int slot = --b->left_; |
109 | 0 | b->tokens_[slot] = (bit << 15) | FIXED_PROBA_BIT | proba; |
110 | 0 | } |
111 | 0 | } |
112 | | |
113 | | int VP8RecordCoeffTokens(int ctx, const struct VP8Residual* const res, |
114 | 0 | VP8TBuffer* const tokens) { |
115 | 0 | const int16_t* const coeffs = res->coeffs; |
116 | 0 | const int coeff_type = res->coeff_type; |
117 | 0 | const int last = res->last; |
118 | 0 | int n = res->first; |
119 | 0 | 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 | 0 | proba_t* s = res->stats[n][ctx]; |
122 | 0 | if (!AddToken(tokens, last >= 0, base_id + 0, s + 0)) { |
123 | 0 | return 0; |
124 | 0 | } |
125 | | |
126 | 0 | while (n < 16) { |
127 | 0 | const int c = coeffs[n++]; |
128 | 0 | const int sign = c < 0; |
129 | 0 | const uint32_t v = sign ? -c : c; |
130 | 0 | if (!AddToken(tokens, v != 0, base_id + 1, s + 1)) { |
131 | 0 | base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 0); // ctx=0 |
132 | 0 | s = res->stats[VP8EncBands[n]][0]; |
133 | 0 | continue; |
134 | 0 | } |
135 | 0 | if (!AddToken(tokens, v > 1, base_id + 2, s + 2)) { |
136 | 0 | base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 1); // ctx=1 |
137 | 0 | s = res->stats[VP8EncBands[n]][1]; |
138 | 0 | } else { |
139 | 0 | if (!AddToken(tokens, v > 4, base_id + 3, s + 3)) { |
140 | 0 | if (AddToken(tokens, v != 2, base_id + 4, s + 4)) { |
141 | 0 | AddToken(tokens, v == 4, base_id + 5, s + 5); |
142 | 0 | } |
143 | 0 | } else if (!AddToken(tokens, v > 10, base_id + 6, s + 6)) { |
144 | 0 | if (!AddToken(tokens, v > 6, base_id + 7, s + 7)) { |
145 | 0 | AddConstantToken(tokens, v == 6, 159); |
146 | 0 | } else { |
147 | 0 | AddConstantToken(tokens, v >= 9, 165); |
148 | 0 | AddConstantToken(tokens, !(v & 1), 145); |
149 | 0 | } |
150 | 0 | } else { |
151 | 0 | int mask; |
152 | 0 | const uint8_t* tab; |
153 | 0 | uint32_t residue = v - 3; |
154 | 0 | if (residue < (8 << 1)) { // VP8Cat3 (3b) |
155 | 0 | AddToken(tokens, 0, base_id + 8, s + 8); |
156 | 0 | AddToken(tokens, 0, base_id + 9, s + 9); |
157 | 0 | residue -= (8 << 0); |
158 | 0 | mask = 1 << 2; |
159 | 0 | tab = VP8Cat3; |
160 | 0 | } else if (residue < (8 << 2)) { // VP8Cat4 (4b) |
161 | 0 | AddToken(tokens, 0, base_id + 8, s + 8); |
162 | 0 | AddToken(tokens, 1, base_id + 9, s + 9); |
163 | 0 | residue -= (8 << 1); |
164 | 0 | mask = 1 << 3; |
165 | 0 | tab = VP8Cat4; |
166 | 0 | } else if (residue < (8 << 3)) { // VP8Cat5 (5b) |
167 | 0 | AddToken(tokens, 1, base_id + 8, s + 8); |
168 | 0 | AddToken(tokens, 0, base_id + 10, s + 9); |
169 | 0 | residue -= (8 << 2); |
170 | 0 | mask = 1 << 4; |
171 | 0 | tab = VP8Cat5; |
172 | 0 | } else { // VP8Cat6 (11b) |
173 | 0 | AddToken(tokens, 1, base_id + 8, s + 8); |
174 | 0 | AddToken(tokens, 1, base_id + 10, s + 9); |
175 | 0 | residue -= (8 << 3); |
176 | 0 | mask = 1 << 10; |
177 | 0 | tab = VP8Cat6; |
178 | 0 | } |
179 | 0 | while (mask) { |
180 | 0 | AddConstantToken(tokens, !!(residue & mask), *tab++); |
181 | 0 | mask >>= 1; |
182 | 0 | } |
183 | 0 | } |
184 | 0 | base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 2); // ctx=2 |
185 | 0 | s = res->stats[VP8EncBands[n]][2]; |
186 | 0 | } |
187 | 0 | AddConstantToken(tokens, sign, 128); |
188 | 0 | if (n == 16 || !AddToken(tokens, n <= last, base_id + 0, s + 0)) { |
189 | 0 | return 1; // EOB |
190 | 0 | } |
191 | 0 | } |
192 | 0 | return 1; |
193 | 0 | } |
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 | 0 | const uint8_t* const probas, int final_pass) { |
202 | 0 | const VP8Tokens* p = b->pages_; |
203 | 0 | assert(!b->error_); |
204 | 0 | while (p != NULL) { |
205 | 0 | const VP8Tokens* const next = p->next_; |
206 | 0 | const int N = (next == NULL) ? b->left_ : 0; |
207 | 0 | int n = b->page_size_; |
208 | 0 | const token_t* const tokens = TOKEN_DATA(p); |
209 | 0 | while (n-- > N) { |
210 | 0 | const token_t token = tokens[n]; |
211 | 0 | const int bit = (token >> 15) & 1; |
212 | 0 | if (token & FIXED_PROBA_BIT) { |
213 | 0 | VP8PutBit(bw, bit, token & 0xffu); // constant proba |
214 | 0 | } else { |
215 | 0 | VP8PutBit(bw, bit, probas[token & 0x3fffu]); |
216 | 0 | } |
217 | 0 | } |
218 | 0 | if (final_pass) WebPSafeFree((void*)p); |
219 | 0 | p = next; |
220 | 0 | } |
221 | 0 | if (final_pass) b->pages_ = NULL; |
222 | 0 | return 1; |
223 | 0 | } |
224 | | |
225 | | // Size estimation |
226 | 0 | size_t VP8EstimateTokenSize(VP8TBuffer* const b, const uint8_t* const probas) { |
227 | 0 | size_t size = 0; |
228 | 0 | const VP8Tokens* p = b->pages_; |
229 | 0 | assert(!b->error_); |
230 | 0 | while (p != NULL) { |
231 | 0 | const VP8Tokens* const next = p->next_; |
232 | 0 | const int N = (next == NULL) ? b->left_ : 0; |
233 | 0 | int n = b->page_size_; |
234 | 0 | const token_t* const tokens = TOKEN_DATA(p); |
235 | 0 | while (n-- > N) { |
236 | 0 | const token_t token = tokens[n]; |
237 | 0 | const int bit = token & (1 << 15); |
238 | 0 | if (token & FIXED_PROBA_BIT) { |
239 | 0 | size += VP8BitCost(bit, token & 0xffu); |
240 | 0 | } else { |
241 | 0 | size += VP8BitCost(bit, probas[token & 0x3fffu]); |
242 | 0 | } |
243 | 0 | } |
244 | 0 | p = next; |
245 | 0 | } |
246 | 0 | return size; |
247 | 0 | } |
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 | | |