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