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
56static int num_malloc_calls = 0;
57static int num_calloc_calls = 0;
58static int num_free_calls = 0;
59static int countdown_to_fail = 0; // 0 = off
60
61typedef struct MemBlock MemBlock;
62struct MemBlock {
63 void* ptr_;
64 size_t size_;
65 MemBlock* next_;
66};
67
68static MemBlock* all_blocks = NULL;
69static size_t total_mem = 0;
70static size_t total_mem_allocated = 0;
71static size_t high_water_mark = 0;
72static size_t mem_limit = 0;
73
74static int exit_registered = 0;
75
76static 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
91static 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
117static 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
139static 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.
168static 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
191void* 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
201void* 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
211void 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
221void* WebPMalloc(size_t size) {
222 return WebPSafeMalloc(1, size);
223}
224
225void WebPFree(void* ptr) {
226 WebPSafeFree(ptr);
227}
228
229//------------------------------------------------------------------------------
230
231void 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
242void 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
255int 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)
315const 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