1 | // Copyright 2012 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 | // Misc. common utility functions |
11 | // |
12 | // Author: Skal (pascal.massimino@gmail.com) |
13 | |
14 | #include <stdlib.h> |
15 | #include <string.h> // for memcpy() |
16 | #include "src/webp/decode.h" |
17 | #include "src/webp/encode.h" |
18 | #include "src/webp/format_constants.h" // for MAX_PALETTE_SIZE |
19 | #include "src/utils/color_cache_utils.h" |
20 | #include "src/utils/utils.h" |
21 | |
22 | // If PRINT_MEM_INFO is defined, extra info (like total memory used, number of |
23 | // alloc/free etc) is printed. For debugging/tuning purpose only (it's slow, |
24 | // and not multi-thread safe!). |
25 | // An interesting alternative is valgrind's 'massif' tool: |
26 | // http://valgrind.org/docs/manual/ms-manual.html |
27 | // Here is an example command line: |
28 | /* valgrind --tool=massif --massif-out-file=massif.out \ |
29 | --stacks=yes --alloc-fn=WebPSafeMalloc --alloc-fn=WebPSafeCalloc |
30 | ms_print massif.out |
31 | */ |
32 | // In addition: |
33 | // * if PRINT_MEM_TRAFFIC is defined, all the details of the malloc/free cycles |
34 | // are printed. |
35 | // * if MALLOC_FAIL_AT is defined, the global environment variable |
36 | // $MALLOC_FAIL_AT is used to simulate a memory error when calloc or malloc |
37 | // is called for the nth time. Example usage: |
38 | // export MALLOC_FAIL_AT=50 && ./examples/cwebp input.png |
39 | // * if MALLOC_LIMIT is defined, the global environment variable $MALLOC_LIMIT |
40 | // sets the maximum amount of memory (in bytes) made available to libwebp. |
41 | // This can be used to emulate environment with very limited memory. |
42 | // Example: export MALLOC_LIMIT=64000000 && ./examples/dwebp picture.webp |
43 | |
44 | // #define PRINT_MEM_INFO |
45 | // #define PRINT_MEM_TRAFFIC |
46 | // #define MALLOC_FAIL_AT |
47 | // #define MALLOC_LIMIT |
48 | |
49 | //------------------------------------------------------------------------------ |
50 | // Checked memory allocation |
51 | |
52 | #if defined(PRINT_MEM_INFO) |
53 | |
54 | #include <stdio.h> |
55 | |
56 | static int num_malloc_calls = 0; |
57 | static int num_calloc_calls = 0; |
58 | static int num_free_calls = 0; |
59 | static int countdown_to_fail = 0; // 0 = off |
60 | |
61 | typedef struct MemBlock MemBlock; |
62 | struct MemBlock { |
63 | void* ptr_; |
64 | size_t size_; |
65 | MemBlock* next_; |
66 | }; |
67 | |
68 | static MemBlock* all_blocks = NULL; |
69 | static size_t total_mem = 0; |
70 | static size_t total_mem_allocated = 0; |
71 | static size_t high_water_mark = 0; |
72 | static size_t mem_limit = 0; |
73 | |
74 | static int exit_registered = 0; |
75 | |
76 | static void PrintMemInfo(void) { |
77 | fprintf(stderr, "\nMEMORY INFO:\n" ); |
78 | fprintf(stderr, "num calls to: malloc = %4d\n" , num_malloc_calls); |
79 | fprintf(stderr, " calloc = %4d\n" , num_calloc_calls); |
80 | fprintf(stderr, " free = %4d\n" , num_free_calls); |
81 | fprintf(stderr, "total_mem: %u\n" , (uint32_t)total_mem); |
82 | fprintf(stderr, "total_mem allocated: %u\n" , (uint32_t)total_mem_allocated); |
83 | fprintf(stderr, "high-water mark: %u\n" , (uint32_t)high_water_mark); |
84 | while (all_blocks != NULL) { |
85 | MemBlock* b = all_blocks; |
86 | all_blocks = b->next_; |
87 | free(b); |
88 | } |
89 | } |
90 | |
91 | static void Increment(int* const v) { |
92 | if (!exit_registered) { |
93 | #if defined(MALLOC_FAIL_AT) |
94 | { |
95 | const char* const malloc_fail_at_str = getenv("MALLOC_FAIL_AT" ); |
96 | if (malloc_fail_at_str != NULL) { |
97 | countdown_to_fail = atoi(malloc_fail_at_str); |
98 | } |
99 | } |
100 | #endif |
101 | #if defined(MALLOC_LIMIT) |
102 | { |
103 | const char* const malloc_limit_str = getenv("MALLOC_LIMIT" ); |
104 | if (malloc_limit_str != NULL) { |
105 | mem_limit = atoi(malloc_limit_str); |
106 | } |
107 | } |
108 | #endif |
109 | (void)countdown_to_fail; |
110 | (void)mem_limit; |
111 | atexit(PrintMemInfo); |
112 | exit_registered = 1; |
113 | } |
114 | ++*v; |
115 | } |
116 | |
117 | static void AddMem(void* ptr, size_t size) { |
118 | if (ptr != NULL) { |
119 | MemBlock* const b = (MemBlock*)malloc(sizeof(*b)); |
120 | if (b == NULL) abort(); |
121 | b->next_ = all_blocks; |
122 | all_blocks = b; |
123 | b->ptr_ = ptr; |
124 | b->size_ = size; |
125 | total_mem += size; |
126 | total_mem_allocated += size; |
127 | #if defined(PRINT_MEM_TRAFFIC) |
128 | #if defined(MALLOC_FAIL_AT) |
129 | fprintf(stderr, "fail-count: %5d [mem=%u]\n" , |
130 | num_malloc_calls + num_calloc_calls, (uint32_t)total_mem); |
131 | #else |
132 | fprintf(stderr, "Mem: %u (+%u)\n" , (uint32_t)total_mem, (uint32_t)size); |
133 | #endif |
134 | #endif |
135 | if (total_mem > high_water_mark) high_water_mark = total_mem; |
136 | } |
137 | } |
138 | |
139 | static void SubMem(void* ptr) { |
140 | if (ptr != NULL) { |
141 | MemBlock** b = &all_blocks; |
142 | // Inefficient search, but that's just for debugging. |
143 | while (*b != NULL && (*b)->ptr_ != ptr) b = &(*b)->next_; |
144 | if (*b == NULL) { |
145 | fprintf(stderr, "Invalid pointer free! (%p)\n" , ptr); |
146 | abort(); |
147 | } |
148 | { |
149 | MemBlock* const block = *b; |
150 | *b = block->next_; |
151 | total_mem -= block->size_; |
152 | #if defined(PRINT_MEM_TRAFFIC) |
153 | fprintf(stderr, "Mem: %u (-%u)\n" , |
154 | (uint32_t)total_mem, (uint32_t)block->size_); |
155 | #endif |
156 | free(block); |
157 | } |
158 | } |
159 | } |
160 | |
161 | #else |
162 | #define Increment(v) do {} while (0) |
163 | #define AddMem(p, s) do {} while (0) |
164 | #define SubMem(p) do {} while (0) |
165 | #endif |
166 | |
167 | // Returns 0 in case of overflow of nmemb * size. |
168 | static int CheckSizeArgumentsOverflow(uint64_t nmemb, size_t size) { |
169 | const uint64_t total_size = nmemb * size; |
170 | if (nmemb == 0) return 1; |
171 | if ((uint64_t)size > WEBP_MAX_ALLOCABLE_MEMORY / nmemb) return 0; |
172 | if (total_size != (size_t)total_size) return 0; |
173 | #if defined(PRINT_MEM_INFO) && defined(MALLOC_FAIL_AT) |
174 | if (countdown_to_fail > 0 && --countdown_to_fail == 0) { |
175 | return 0; // fake fail! |
176 | } |
177 | #endif |
178 | #if defined(MALLOC_LIMIT) |
179 | if (mem_limit > 0) { |
180 | const uint64_t new_total_mem = (uint64_t)total_mem + total_size; |
181 | if (new_total_mem != (size_t)new_total_mem || |
182 | new_total_mem > mem_limit) { |
183 | return 0; // fake fail! |
184 | } |
185 | } |
186 | #endif |
187 | |
188 | return 1; |
189 | } |
190 | |
191 | void* WebPSafeMalloc(uint64_t nmemb, size_t size) { |
192 | void* ptr; |
193 | Increment(&num_malloc_calls); |
194 | if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL; |
195 | assert(nmemb * size > 0); |
196 | ptr = malloc((size_t)(nmemb * size)); |
197 | AddMem(ptr, (size_t)(nmemb * size)); |
198 | return ptr; |
199 | } |
200 | |
201 | void* WebPSafeCalloc(uint64_t nmemb, size_t size) { |
202 | void* ptr; |
203 | Increment(&num_calloc_calls); |
204 | if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL; |
205 | assert(nmemb * size > 0); |
206 | ptr = calloc((size_t)nmemb, size); |
207 | AddMem(ptr, (size_t)(nmemb * size)); |
208 | return ptr; |
209 | } |
210 | |
211 | void WebPSafeFree(void* const ptr) { |
212 | if (ptr != NULL) { |
213 | Increment(&num_free_calls); |
214 | SubMem(ptr); |
215 | } |
216 | free(ptr); |
217 | } |
218 | |
219 | // Public API functions. |
220 | |
221 | void* WebPMalloc(size_t size) { |
222 | return WebPSafeMalloc(1, size); |
223 | } |
224 | |
225 | void WebPFree(void* ptr) { |
226 | WebPSafeFree(ptr); |
227 | } |
228 | |
229 | //------------------------------------------------------------------------------ |
230 | |
231 | void WebPCopyPlane(const uint8_t* src, int src_stride, |
232 | uint8_t* dst, int dst_stride, int width, int height) { |
233 | assert(src != NULL && dst != NULL); |
234 | assert(src_stride >= width && dst_stride >= width); |
235 | while (height-- > 0) { |
236 | memcpy(dst, src, width); |
237 | src += src_stride; |
238 | dst += dst_stride; |
239 | } |
240 | } |
241 | |
242 | void WebPCopyPixels(const WebPPicture* const src, WebPPicture* const dst) { |
243 | assert(src != NULL && dst != NULL); |
244 | assert(src->width == dst->width && src->height == dst->height); |
245 | assert(src->use_argb && dst->use_argb); |
246 | WebPCopyPlane((uint8_t*)src->argb, 4 * src->argb_stride, (uint8_t*)dst->argb, |
247 | 4 * dst->argb_stride, 4 * src->width, src->height); |
248 | } |
249 | |
250 | //------------------------------------------------------------------------------ |
251 | |
252 | #define COLOR_HASH_SIZE (MAX_PALETTE_SIZE * 4) |
253 | #define COLOR_HASH_RIGHT_SHIFT 22 // 32 - log2(COLOR_HASH_SIZE). |
254 | |
255 | int WebPGetColorPalette(const WebPPicture* const pic, uint32_t* const palette) { |
256 | int i; |
257 | int x, y; |
258 | int num_colors = 0; |
259 | uint8_t in_use[COLOR_HASH_SIZE] = { 0 }; |
260 | uint32_t colors[COLOR_HASH_SIZE]; |
261 | const uint32_t* argb = pic->argb; |
262 | const int width = pic->width; |
263 | const int height = pic->height; |
264 | uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0] |
265 | assert(pic != NULL); |
266 | assert(pic->use_argb); |
267 | |
268 | for (y = 0; y < height; ++y) { |
269 | for (x = 0; x < width; ++x) { |
270 | int key; |
271 | if (argb[x] == last_pix) { |
272 | continue; |
273 | } |
274 | last_pix = argb[x]; |
275 | key = VP8LHashPix(last_pix, COLOR_HASH_RIGHT_SHIFT); |
276 | while (1) { |
277 | if (!in_use[key]) { |
278 | colors[key] = last_pix; |
279 | in_use[key] = 1; |
280 | ++num_colors; |
281 | if (num_colors > MAX_PALETTE_SIZE) { |
282 | return MAX_PALETTE_SIZE + 1; // Exact count not needed. |
283 | } |
284 | break; |
285 | } else if (colors[key] == last_pix) { |
286 | break; // The color is already there. |
287 | } else { |
288 | // Some other color sits here, so do linear conflict resolution. |
289 | ++key; |
290 | key &= (COLOR_HASH_SIZE - 1); // Key mask. |
291 | } |
292 | } |
293 | } |
294 | argb += pic->argb_stride; |
295 | } |
296 | |
297 | if (palette != NULL) { // Fill the colors into palette. |
298 | num_colors = 0; |
299 | for (i = 0; i < COLOR_HASH_SIZE; ++i) { |
300 | if (in_use[i]) { |
301 | palette[num_colors] = colors[i]; |
302 | ++num_colors; |
303 | } |
304 | } |
305 | } |
306 | return num_colors; |
307 | } |
308 | |
309 | #undef COLOR_HASH_SIZE |
310 | #undef COLOR_HASH_RIGHT_SHIFT |
311 | |
312 | //------------------------------------------------------------------------------ |
313 | |
314 | #if defined(WEBP_NEED_LOG_TABLE_8BIT) |
315 | const uint8_t WebPLogTable8bit[256] = { // 31 ^ clz(i) |
316 | 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, |
317 | 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
318 | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, |
319 | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, |
320 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, |
321 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, |
322 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, |
323 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, |
324 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
325 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
326 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
327 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
328 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
329 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
330 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, |
331 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 |
332 | }; |
333 | #endif |
334 | |
335 | //------------------------------------------------------------------------------ |
336 | |