OLD | NEW |
1 // Copyright 2011 Google Inc. All Rights Reserved. | 1 // Copyright 2011 Google Inc. All Rights Reserved. |
2 // | 2 // |
3 // Use of this source code is governed by a BSD-style license | 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 | 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 | 5 // tree. An additional intellectual property rights grant can be found |
6 // in the file PATENTS. All contributing project authors may | 6 // in the file PATENTS. All contributing project authors may |
7 // be found in the AUTHORS file in the root of the source tree. | 7 // be found in the AUTHORS file in the root of the source tree. |
8 // ----------------------------------------------------------------------------- | 8 // ----------------------------------------------------------------------------- |
9 // | 9 // |
10 // Paginated token buffer | 10 // Paginated token buffer |
(...skipping 12 matching lines...) Expand all Loading... |
23 #include "./cost.h" | 23 #include "./cost.h" |
24 #include "./vp8enci.h" | 24 #include "./vp8enci.h" |
25 #include "../utils/utils.h" | 25 #include "../utils/utils.h" |
26 | 26 |
27 #if !defined(DISABLE_TOKEN_BUFFER) | 27 #if !defined(DISABLE_TOKEN_BUFFER) |
28 | 28 |
29 // we use pages to reduce the number of memcpy() | 29 // we use pages to reduce the number of memcpy() |
30 #define MIN_PAGE_SIZE 8192 // minimum number of token per page | 30 #define MIN_PAGE_SIZE 8192 // minimum number of token per page |
31 #define FIXED_PROBA_BIT (1u << 14) | 31 #define FIXED_PROBA_BIT (1u << 14) |
32 | 32 |
33 typedef uint16_t token_t; // bit#15: bit | 33 typedef uint16_t token_t; // bit #15: bit value |
34 // bit #14: constant proba or idx | 34 // bit #14: flags for constant proba or idx |
35 // bits 0..13: slot or constant proba | 35 // bits #0..13: slot or constant proba |
36 struct VP8Tokens { | 36 struct VP8Tokens { |
37 VP8Tokens* next_; // pointer to next page | 37 VP8Tokens* next_; // pointer to next page |
38 }; | 38 }; |
39 // Token data is located in memory just after the next_ field. | 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. | 40 // This macro is used to return their address and hide the trick. |
41 #define TOKEN_DATA(p) ((token_t*)&(p)[1]) | 41 #define TOKEN_DATA(p) ((const token_t*)&(p)[1]) |
42 | 42 |
43 //------------------------------------------------------------------------------ | 43 //------------------------------------------------------------------------------ |
44 | 44 |
45 void VP8TBufferInit(VP8TBuffer* const b, int page_size) { | 45 void VP8TBufferInit(VP8TBuffer* const b, int page_size) { |
46 b->tokens_ = NULL; | 46 b->tokens_ = NULL; |
47 b->pages_ = NULL; | 47 b->pages_ = NULL; |
48 b->last_page_ = &b->pages_; | 48 b->last_page_ = &b->pages_; |
49 b->left_ = 0; | 49 b->left_ = 0; |
50 b->page_size_ = (page_size < MIN_PAGE_SIZE) ? MIN_PAGE_SIZE : page_size; | 50 b->page_size_ = (page_size < MIN_PAGE_SIZE) ? MIN_PAGE_SIZE : page_size; |
51 b->error_ = 0; | 51 b->error_ = 0; |
52 } | 52 } |
53 | 53 |
54 void VP8TBufferClear(VP8TBuffer* const b) { | 54 void VP8TBufferClear(VP8TBuffer* const b) { |
55 if (b != NULL) { | 55 if (b != NULL) { |
56 const VP8Tokens* p = b->pages_; | 56 VP8Tokens* p = b->pages_; |
57 while (p != NULL) { | 57 while (p != NULL) { |
58 const VP8Tokens* const next = p->next_; | 58 VP8Tokens* const next = p->next_; |
59 WebPSafeFree((void*)p); | 59 WebPSafeFree(p); |
60 p = next; | 60 p = next; |
61 } | 61 } |
62 VP8TBufferInit(b, b->page_size_); | 62 VP8TBufferInit(b, b->page_size_); |
63 } | 63 } |
64 } | 64 } |
65 | 65 |
66 static int TBufferNewPage(VP8TBuffer* const b) { | 66 static int TBufferNewPage(VP8TBuffer* const b) { |
67 VP8Tokens* page = NULL; | 67 VP8Tokens* page = NULL; |
68 const size_t size = sizeof(*page) + b->page_size_ * sizeof(token_t); | |
69 if (!b->error_) { | 68 if (!b->error_) { |
| 69 const size_t size = sizeof(*page) + b->page_size_ * sizeof(token_t); |
70 page = (VP8Tokens*)WebPSafeMalloc(1ULL, size); | 70 page = (VP8Tokens*)WebPSafeMalloc(1ULL, size); |
71 } | 71 } |
72 if (page == NULL) { | 72 if (page == NULL) { |
73 b->error_ = 1; | 73 b->error_ = 1; |
74 return 0; | 74 return 0; |
75 } | 75 } |
76 page->next_ = NULL; | 76 page->next_ = NULL; |
77 | 77 |
78 *b->last_page_ = page; | 78 *b->last_page_ = page; |
79 b->last_page_ = &page->next_; | 79 b->last_page_ = &page->next_; |
80 b->left_ = b->page_size_; | 80 b->left_ = b->page_size_; |
81 b->tokens_ = TOKEN_DATA(page); | 81 b->tokens_ = (token_t*)TOKEN_DATA(page); |
82 return 1; | 82 return 1; |
83 } | 83 } |
84 | 84 |
85 //------------------------------------------------------------------------------ | 85 //------------------------------------------------------------------------------ |
86 | 86 |
87 #define TOKEN_ID(t, b, ctx, p) \ | 87 #define TOKEN_ID(t, b, ctx) \ |
88 ((p) + NUM_PROBAS * ((ctx) + NUM_CTX * ((b) + NUM_BANDS * (t)))) | 88 (NUM_PROBAS * ((ctx) + NUM_CTX * ((b) + NUM_BANDS * (t)))) |
89 | 89 |
90 static WEBP_INLINE int AddToken(VP8TBuffer* const b, | 90 static WEBP_INLINE uint32_t AddToken(VP8TBuffer* const b, |
91 int bit, uint32_t proba_idx) { | 91 uint32_t bit, uint32_t proba_idx) { |
92 assert(proba_idx < FIXED_PROBA_BIT); | 92 assert(proba_idx < FIXED_PROBA_BIT); |
93 assert(bit == 0 || bit == 1); | 93 assert(bit <= 1); |
94 if (b->left_ > 0 || TBufferNewPage(b)) { | 94 if (b->left_ > 0 || TBufferNewPage(b)) { |
95 const int slot = --b->left_; | 95 const int slot = --b->left_; |
96 b->tokens_[slot] = (bit << 15) | proba_idx; | 96 b->tokens_[slot] = (bit << 15) | proba_idx; |
97 } | 97 } |
98 return bit; | 98 return bit; |
99 } | 99 } |
100 | 100 |
101 static WEBP_INLINE void AddConstantToken(VP8TBuffer* const b, | 101 static WEBP_INLINE void AddConstantToken(VP8TBuffer* const b, |
102 int bit, int proba) { | 102 uint32_t bit, uint32_t proba) { |
103 assert(proba < 256); | 103 assert(proba < 256); |
104 assert(bit == 0 || bit == 1); | 104 assert(bit <= 1); |
105 if (b->left_ > 0 || TBufferNewPage(b)) { | 105 if (b->left_ > 0 || TBufferNewPage(b)) { |
106 const int slot = --b->left_; | 106 const int slot = --b->left_; |
107 b->tokens_[slot] = (bit << 15) | FIXED_PROBA_BIT | proba; | 107 b->tokens_[slot] = (bit << 15) | FIXED_PROBA_BIT | proba; |
108 } | 108 } |
109 } | 109 } |
110 | 110 |
111 int VP8RecordCoeffTokens(int ctx, int coeff_type, int first, int last, | 111 int VP8RecordCoeffTokens(const int ctx, const int coeff_type, |
| 112 int first, int last, |
112 const int16_t* const coeffs, | 113 const int16_t* const coeffs, |
113 VP8TBuffer* const tokens) { | 114 VP8TBuffer* const tokens) { |
114 int n = first; | 115 int n = first; |
115 uint32_t base_id = TOKEN_ID(coeff_type, n, ctx, 0); | 116 uint32_t base_id = TOKEN_ID(coeff_type, n, ctx); |
116 if (!AddToken(tokens, last >= 0, base_id + 0)) { | 117 if (!AddToken(tokens, last >= 0, base_id + 0)) { |
117 return 0; | 118 return 0; |
118 } | 119 } |
119 | 120 |
120 while (n < 16) { | 121 while (n < 16) { |
121 const int c = coeffs[n++]; | 122 const int c = coeffs[n++]; |
122 const int sign = c < 0; | 123 const int sign = c < 0; |
123 int v = sign ? -c : c; | 124 const uint32_t v = sign ? -c : c; |
124 if (!AddToken(tokens, v != 0, base_id + 1)) { | 125 if (!AddToken(tokens, v != 0, base_id + 1)) { |
125 ctx = 0; | 126 base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 0); // ctx=0 |
126 base_id = TOKEN_ID(coeff_type, VP8EncBands[n], ctx, 0); | |
127 continue; | 127 continue; |
128 } | 128 } |
129 if (!AddToken(tokens, v > 1, base_id + 2)) { | 129 if (!AddToken(tokens, v > 1, base_id + 2)) { |
130 ctx = 1; | 130 base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 1); // ctx=1 |
131 } else { | 131 } else { |
132 if (!AddToken(tokens, v > 4, base_id + 3)) { | 132 if (!AddToken(tokens, v > 4, base_id + 3)) { |
133 if (AddToken(tokens, v != 2, base_id + 4)) | 133 if (AddToken(tokens, v != 2, base_id + 4)) |
134 AddToken(tokens, v == 4, base_id + 5); | 134 AddToken(tokens, v == 4, base_id + 5); |
135 } else if (!AddToken(tokens, v > 10, base_id + 6)) { | 135 } else if (!AddToken(tokens, v > 10, base_id + 6)) { |
136 if (!AddToken(tokens, v > 6, base_id + 7)) { | 136 if (!AddToken(tokens, v > 6, base_id + 7)) { |
137 AddConstantToken(tokens, v == 6, 159); | 137 AddConstantToken(tokens, v == 6, 159); |
138 } else { | 138 } else { |
139 AddConstantToken(tokens, v >= 9, 165); | 139 AddConstantToken(tokens, v >= 9, 165); |
140 AddConstantToken(tokens, !(v & 1), 145); | 140 AddConstantToken(tokens, !(v & 1), 145); |
141 } | 141 } |
142 } else { | 142 } else { |
143 int mask; | 143 int mask; |
144 const uint8_t* tab; | 144 const uint8_t* tab; |
145 if (v < 3 + (8 << 1)) { // VP8Cat3 (3b) | 145 uint32_t residue = v - 3; |
| 146 if (residue < (8 << 1)) { // VP8Cat3 (3b) |
146 AddToken(tokens, 0, base_id + 8); | 147 AddToken(tokens, 0, base_id + 8); |
147 AddToken(tokens, 0, base_id + 9); | 148 AddToken(tokens, 0, base_id + 9); |
148 v -= 3 + (8 << 0); | 149 residue -= (8 << 0); |
149 mask = 1 << 2; | 150 mask = 1 << 2; |
150 tab = VP8Cat3; | 151 tab = VP8Cat3; |
151 } else if (v < 3 + (8 << 2)) { // VP8Cat4 (4b) | 152 } else if (residue < (8 << 2)) { // VP8Cat4 (4b) |
152 AddToken(tokens, 0, base_id + 8); | 153 AddToken(tokens, 0, base_id + 8); |
153 AddToken(tokens, 1, base_id + 9); | 154 AddToken(tokens, 1, base_id + 9); |
154 v -= 3 + (8 << 1); | 155 residue -= (8 << 1); |
155 mask = 1 << 3; | 156 mask = 1 << 3; |
156 tab = VP8Cat4; | 157 tab = VP8Cat4; |
157 } else if (v < 3 + (8 << 3)) { // VP8Cat5 (5b) | 158 } else if (residue < (8 << 3)) { // VP8Cat5 (5b) |
158 AddToken(tokens, 1, base_id + 8); | 159 AddToken(tokens, 1, base_id + 8); |
159 AddToken(tokens, 0, base_id + 10); | 160 AddToken(tokens, 0, base_id + 10); |
160 v -= 3 + (8 << 2); | 161 residue -= (8 << 2); |
161 mask = 1 << 4; | 162 mask = 1 << 4; |
162 tab = VP8Cat5; | 163 tab = VP8Cat5; |
163 } else { // VP8Cat6 (11b) | 164 } else { // VP8Cat6 (11b) |
164 AddToken(tokens, 1, base_id + 8); | 165 AddToken(tokens, 1, base_id + 8); |
165 AddToken(tokens, 1, base_id + 10); | 166 AddToken(tokens, 1, base_id + 10); |
166 v -= 3 + (8 << 3); | 167 residue -= (8 << 3); |
167 mask = 1 << 10; | 168 mask = 1 << 10; |
168 tab = VP8Cat6; | 169 tab = VP8Cat6; |
169 } | 170 } |
170 while (mask) { | 171 while (mask) { |
171 AddConstantToken(tokens, !!(v & mask), *tab++); | 172 AddConstantToken(tokens, !!(residue & mask), *tab++); |
172 mask >>= 1; | 173 mask >>= 1; |
173 } | 174 } |
174 } | 175 } |
175 ctx = 2; | 176 base_id = TOKEN_ID(coeff_type, VP8EncBands[n], 2); // ctx=2 |
176 } | 177 } |
177 AddConstantToken(tokens, sign, 128); | 178 AddConstantToken(tokens, sign, 128); |
178 base_id = TOKEN_ID(coeff_type, VP8EncBands[n], ctx, 0); | |
179 if (n == 16 || !AddToken(tokens, n <= last, base_id + 0)) { | 179 if (n == 16 || !AddToken(tokens, n <= last, base_id + 0)) { |
180 return 1; // EOB | 180 return 1; // EOB |
181 } | 181 } |
182 } | 182 } |
183 return 1; | 183 return 1; |
184 } | 184 } |
185 | 185 |
186 #undef TOKEN_ID | 186 #undef TOKEN_ID |
187 | 187 |
188 //------------------------------------------------------------------------------ | 188 //------------------------------------------------------------------------------ |
(...skipping 28 matching lines...) Expand all Loading... |
217 } | 217 } |
218 | 218 |
219 #endif // 0 | 219 #endif // 0 |
220 | 220 |
221 //------------------------------------------------------------------------------ | 221 //------------------------------------------------------------------------------ |
222 // Final coding pass, with known probabilities | 222 // Final coding pass, with known probabilities |
223 | 223 |
224 int VP8EmitTokens(VP8TBuffer* const b, VP8BitWriter* const bw, | 224 int VP8EmitTokens(VP8TBuffer* const b, VP8BitWriter* const bw, |
225 const uint8_t* const probas, int final_pass) { | 225 const uint8_t* const probas, int final_pass) { |
226 const VP8Tokens* p = b->pages_; | 226 const VP8Tokens* p = b->pages_; |
227 (void)final_pass; | |
228 assert(!b->error_); | 227 assert(!b->error_); |
229 while (p != NULL) { | 228 while (p != NULL) { |
230 const VP8Tokens* const next = p->next_; | 229 const VP8Tokens* const next = p->next_; |
231 const int N = (next == NULL) ? b->left_ : 0; | 230 const int N = (next == NULL) ? b->left_ : 0; |
232 int n = b->page_size_; | 231 int n = b->page_size_; |
233 const token_t* const tokens = TOKEN_DATA(p); | 232 const token_t* const tokens = TOKEN_DATA(p); |
234 while (n-- > N) { | 233 while (n-- > N) { |
235 const token_t token = tokens[n]; | 234 const token_t token = tokens[n]; |
236 const int bit = (token >> 15) & 1; | 235 const int bit = (token >> 15) & 1; |
237 if (token & FIXED_PROBA_BIT) { | 236 if (token & FIXED_PROBA_BIT) { |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
277 | 276 |
278 void VP8TBufferInit(VP8TBuffer* const b) { | 277 void VP8TBufferInit(VP8TBuffer* const b) { |
279 (void)b; | 278 (void)b; |
280 } | 279 } |
281 void VP8TBufferClear(VP8TBuffer* const b) { | 280 void VP8TBufferClear(VP8TBuffer* const b) { |
282 (void)b; | 281 (void)b; |
283 } | 282 } |
284 | 283 |
285 #endif // !DISABLE_TOKEN_BUFFER | 284 #endif // !DISABLE_TOKEN_BUFFER |
286 | 285 |
OLD | NEW |