/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/dec/common_dec.h" |
24 | | #include "src/dsp/dsp.h" |
25 | | #include "src/enc/cost_enc.h" |
26 | | #include "src/enc/vp8i_enc.h" |
27 | | #include "src/utils/bit_writer_utils.h" |
28 | | #include "src/utils/utils.h" |
29 | | #include "src/webp/types.h" |
30 | | |
31 | | #if !defined(DISABLE_TOKEN_BUFFER) |
32 | | |
33 | | // we use pages to reduce the number of memcpy() |
34 | 0 | #define MIN_PAGE_SIZE 8192 // minimum number of token per page |
35 | 0 | #define FIXED_PROBA_BIT (1u << 14) |
36 | | |
37 | | typedef uint16_t token_t; // bit #15: bit value |
38 | | // bit #14: flags for constant proba or idx |
39 | | // bits #0..13: slot or constant proba |
40 | | struct VP8Tokens { |
41 | | VP8Tokens* next; // pointer to next page |
42 | | }; |
43 | | // Token data is located in memory just after the 'next' field. |
44 | | // This macro is used to return their address and hide the trick. |
45 | 0 | #define TOKEN_DATA(p) ((const token_t*)&(p)[1]) |
46 | | |
47 | | //------------------------------------------------------------------------------ |
48 | | |
49 | 0 | void VP8TBufferInit(VP8TBuffer* const b, int page_size) { |
50 | 0 | b->tokens = NULL; |
51 | 0 | b->pages = NULL; |
52 | 0 | b->last_page = &b->pages; |
53 | 0 | b->left = 0; |
54 | 0 | b->page_size = (page_size < MIN_PAGE_SIZE) ? MIN_PAGE_SIZE : page_size; |
55 | 0 | b->error = 0; |
56 | 0 | } |
57 | | |
58 | 0 | void VP8TBufferClear(VP8TBuffer* const b) { |
59 | 0 | if (b != NULL) { |
60 | 0 | VP8Tokens* p = b->pages; |
61 | 0 | while (p != NULL) { |
62 | 0 | VP8Tokens* const next = p->next; |
63 | 0 | WebPSafeFree(p); |
64 | 0 | p = next; |
65 | 0 | } |
66 | 0 | VP8TBufferInit(b, b->page_size); |
67 | 0 | } |
68 | 0 | } |
69 | | |
70 | 0 | static int TBufferNewPage(VP8TBuffer* const b) { |
71 | 0 | VP8Tokens* page = NULL; |
72 | 0 | if (!b->error) { |
73 | 0 | const size_t size = sizeof(*page) + b->page_size * sizeof(token_t); |
74 | 0 | page = (VP8Tokens*)WebPSafeMalloc(1ULL, size); |
75 | 0 | } |
76 | 0 | if (page == NULL) { |
77 | 0 | b->error = 1; |
78 | 0 | return 0; |
79 | 0 | } |
80 | 0 | page->next = NULL; |
81 | |
|
82 | 0 | *b->last_page = page; |
83 | 0 | b->last_page = &page->next; |
84 | 0 | b->left = b->page_size; |
85 | 0 | b->tokens = (token_t*)TOKEN_DATA(page); |
86 | 0 | return 1; |
87 | 0 | } |
88 | | |
89 | | //------------------------------------------------------------------------------ |
90 | | |
91 | | #define TOKEN_ID(t, b, ctx) \ |
92 | 0 | (NUM_PROBAS * ((ctx) + NUM_CTX * ((b) + NUM_BANDS * (t)))) |
93 | | |
94 | | static WEBP_INLINE uint32_t AddToken(VP8TBuffer* const b, uint32_t bit, |
95 | | uint32_t proba_idx, |
96 | 0 | proba_t* const stats) { |
97 | 0 | assert(proba_idx < FIXED_PROBA_BIT); |
98 | 0 | assert(bit <= 1); |
99 | 0 | if (b->left > 0 || TBufferNewPage(b)) { |
100 | 0 | const int slot = --b->left; |
101 | 0 | b->tokens[slot] = (bit << 15) | proba_idx; |
102 | 0 | } |
103 | 0 | VP8RecordStats(bit, stats); |
104 | 0 | return bit; |
105 | 0 | } |
106 | | |
107 | | static WEBP_INLINE void AddConstantToken(VP8TBuffer* const b, |
108 | 0 | uint32_t bit, uint32_t proba) { |
109 | 0 | assert(proba < 256); |
110 | 0 | assert(bit <= 1); |
111 | 0 | if (b->left > 0 || TBufferNewPage(b)) { |
112 | 0 | const int slot = --b->left; |
113 | 0 | b->tokens[slot] = (bit << 15) | FIXED_PROBA_BIT | proba; |
114 | 0 | } |
115 | 0 | } |
116 | | |
117 | | int VP8RecordCoeffTokens(int ctx, const struct VP8Residual* const res, |
118 | 0 | VP8TBuffer* const tokens) { |
119 | 0 | const int16_t* const coeffs = res->coeffs; |
120 | 0 | const int coeff_type = res->coeff_type; |
121 | 0 | const int last = res->last; |
122 | 0 | int n = res->first; |
123 | 0 | uint32_t base_id = TOKEN_ID(coeff_type, n, ctx); |
124 | | // should be stats[VP8EncBands[n]], but it's equivalent for n=0 or 1 |
125 | 0 | proba_t* s = res->stats[n][ctx]; |
126 | 0 | if (!AddToken(tokens, last >= 0, base_id + 0, s + 0)) { |
127 | 0 | return 0; |
128 | 0 | } |
129 | | |
130 | 0 | while (n < 16) { |
131 | 0 | const int c = coeffs[n++]; |
132 | 0 | const int sign = c < 0; |
133 | 0 | const uint32_t v = sign ? -c : c; |
134 | 0 | if (!AddToken(tokens, v != 0, base_id + 1, s + 1)) { |
135 | 0 | base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 0); // ctx=0 |
136 | 0 | s = res->stats[VP8EncBands[n]][0]; |
137 | 0 | continue; |
138 | 0 | } |
139 | 0 | if (!AddToken(tokens, v > 1, base_id + 2, s + 2)) { |
140 | 0 | base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 1); // ctx=1 |
141 | 0 | s = res->stats[VP8EncBands[n]][1]; |
142 | 0 | } else { |
143 | 0 | if (!AddToken(tokens, v > 4, base_id + 3, s + 3)) { |
144 | 0 | if (AddToken(tokens, v != 2, base_id + 4, s + 4)) { |
145 | 0 | AddToken(tokens, v == 4, base_id + 5, s + 5); |
146 | 0 | } |
147 | 0 | } else if (!AddToken(tokens, v > 10, base_id + 6, s + 6)) { |
148 | 0 | if (!AddToken(tokens, v > 6, base_id + 7, s + 7)) { |
149 | 0 | AddConstantToken(tokens, v == 6, 159); |
150 | 0 | } else { |
151 | 0 | AddConstantToken(tokens, v >= 9, 165); |
152 | 0 | AddConstantToken(tokens, !(v & 1), 145); |
153 | 0 | } |
154 | 0 | } else { |
155 | 0 | int mask; |
156 | 0 | const uint8_t* tab; |
157 | 0 | uint32_t residue = v - 3; |
158 | 0 | if (residue < (8 << 1)) { // VP8Cat3 (3b) |
159 | 0 | AddToken(tokens, 0, base_id + 8, s + 8); |
160 | 0 | AddToken(tokens, 0, base_id + 9, s + 9); |
161 | 0 | residue -= (8 << 0); |
162 | 0 | mask = 1 << 2; |
163 | 0 | tab = VP8Cat3; |
164 | 0 | } else if (residue < (8 << 2)) { // VP8Cat4 (4b) |
165 | 0 | AddToken(tokens, 0, base_id + 8, s + 8); |
166 | 0 | AddToken(tokens, 1, base_id + 9, s + 9); |
167 | 0 | residue -= (8 << 1); |
168 | 0 | mask = 1 << 3; |
169 | 0 | tab = VP8Cat4; |
170 | 0 | } else if (residue < (8 << 3)) { // VP8Cat5 (5b) |
171 | 0 | AddToken(tokens, 1, base_id + 8, s + 8); |
172 | 0 | AddToken(tokens, 0, base_id + 10, s + 9); |
173 | 0 | residue -= (8 << 2); |
174 | 0 | mask = 1 << 4; |
175 | 0 | tab = VP8Cat5; |
176 | 0 | } else { // VP8Cat6 (11b) |
177 | 0 | AddToken(tokens, 1, base_id + 8, s + 8); |
178 | 0 | AddToken(tokens, 1, base_id + 10, s + 9); |
179 | 0 | residue -= (8 << 3); |
180 | 0 | mask = 1 << 10; |
181 | 0 | tab = VP8Cat6; |
182 | 0 | } |
183 | 0 | while (mask) { |
184 | 0 | AddConstantToken(tokens, !!(residue & mask), *tab++); |
185 | 0 | mask >>= 1; |
186 | 0 | } |
187 | 0 | } |
188 | 0 | base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 2); // ctx=2 |
189 | 0 | s = res->stats[VP8EncBands[n]][2]; |
190 | 0 | } |
191 | 0 | AddConstantToken(tokens, sign, 128); |
192 | 0 | if (n == 16 || !AddToken(tokens, n <= last, base_id + 0, s + 0)) { |
193 | 0 | return 1; // EOB |
194 | 0 | } |
195 | 0 | } |
196 | 0 | return 1; |
197 | 0 | } |
198 | | |
199 | | #undef TOKEN_ID |
200 | | |
201 | | //------------------------------------------------------------------------------ |
202 | | // Final coding pass, with known probabilities |
203 | | |
204 | | int VP8EmitTokens(VP8TBuffer* const b, VP8BitWriter* const bw, |
205 | 0 | const uint8_t* const probas, int final_pass) { |
206 | 0 | const VP8Tokens* p = b->pages; |
207 | 0 | assert(!b->error); |
208 | 0 | while (p != NULL) { |
209 | 0 | const VP8Tokens* const next = p->next; |
210 | 0 | const int N = (next == NULL) ? b->left : 0; |
211 | 0 | int n = b->page_size; |
212 | 0 | const token_t* const tokens = TOKEN_DATA(p); |
213 | 0 | while (n-- > N) { |
214 | 0 | const token_t token = tokens[n]; |
215 | 0 | const int bit = (token >> 15) & 1; |
216 | 0 | if (token & FIXED_PROBA_BIT) { |
217 | 0 | VP8PutBit(bw, bit, token & 0xffu); // constant proba |
218 | 0 | } else { |
219 | 0 | VP8PutBit(bw, bit, probas[token & 0x3fffu]); |
220 | 0 | } |
221 | 0 | } |
222 | 0 | if (final_pass) WebPSafeFree((void*)p); |
223 | 0 | p = next; |
224 | 0 | } |
225 | 0 | if (final_pass) b->pages = NULL; |
226 | 0 | return 1; |
227 | 0 | } |
228 | | |
229 | | // Size estimation |
230 | 0 | size_t VP8EstimateTokenSize(VP8TBuffer* const b, const uint8_t* const probas) { |
231 | 0 | size_t size = 0; |
232 | 0 | const VP8Tokens* p = b->pages; |
233 | 0 | assert(!b->error); |
234 | 0 | while (p != NULL) { |
235 | 0 | const VP8Tokens* const next = p->next; |
236 | 0 | const int N = (next == NULL) ? b->left : 0; |
237 | 0 | int n = b->page_size; |
238 | 0 | const token_t* const tokens = TOKEN_DATA(p); |
239 | 0 | while (n-- > N) { |
240 | 0 | const token_t token = tokens[n]; |
241 | 0 | const int bit = token & (1 << 15); |
242 | 0 | if (token & FIXED_PROBA_BIT) { |
243 | 0 | size += VP8BitCost(bit, token & 0xffu); |
244 | 0 | } else { |
245 | 0 | size += VP8BitCost(bit, probas[token & 0x3fffu]); |
246 | 0 | } |
247 | 0 | } |
248 | 0 | p = next; |
249 | 0 | } |
250 | 0 | return size; |
251 | 0 | } |
252 | | |
253 | | //------------------------------------------------------------------------------ |
254 | | |
255 | | #else // DISABLE_TOKEN_BUFFER |
256 | | |
257 | | void VP8TBufferInit(VP8TBuffer* const b, int page_size) { |
258 | | (void)b; |
259 | | (void)page_size; |
260 | | } |
261 | | void VP8TBufferClear(VP8TBuffer* const b) { |
262 | | (void)b; |
263 | | } |
264 | | |
265 | | #endif // !DISABLE_TOKEN_BUFFER |