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// https://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 > 1
105 mem_limit = (size_t)MALLOC_LIMIT;
106#endif
107 if (malloc_limit_str != NULL) {
108 mem_limit = atoi(malloc_limit_str);
109 }
110 }
111#endif
112 (void)countdown_to_fail;
113 (void)mem_limit;
114 atexit(PrintMemInfo);
115 exit_registered = 1;
116 }
117 ++*v;
118}
119
120static void AddMem(void* ptr, size_t size) {
121 if (ptr != NULL) {
122 MemBlock* const b = (MemBlock*)malloc(sizeof(*b));
123 if (b == NULL) abort();
124 b->next_ = all_blocks;
125 all_blocks = b;
126 b->ptr_ = ptr;
127 b->size_ = size;
128 total_mem += size;
129 total_mem_allocated += size;
130#if defined(PRINT_MEM_TRAFFIC)
131#if defined(MALLOC_FAIL_AT)
132 fprintf(stderr, "fail-count: %5d [mem=%u]\n",
133 num_malloc_calls + num_calloc_calls, (uint32_t)total_mem);
134#else
135 fprintf(stderr, "Mem: %u (+%u)\n", (uint32_t)total_mem, (uint32_t)size);
136#endif
137#endif
138 if (total_mem > high_water_mark) high_water_mark = total_mem;
139 }
140}
141
142static void SubMem(void* ptr) {
143 if (ptr != NULL) {
144 MemBlock** b = &all_blocks;
145 // Inefficient search, but that's just for debugging.
146 while (*b != NULL && (*b)->ptr_ != ptr) b = &(*b)->next_;
147 if (*b == NULL) {
148 fprintf(stderr, "Invalid pointer free! (%p)\n", ptr);
149 abort();
150 }
151 {
152 MemBlock* const block = *b;
153 *b = block->next_;
154 total_mem -= block->size_;
155#if defined(PRINT_MEM_TRAFFIC)
156 fprintf(stderr, "Mem: %u (-%u)\n",
157 (uint32_t)total_mem, (uint32_t)block->size_);
158#endif
159 free(block);
160 }
161 }
162}
163
164#else
165#define Increment(v) do {} while (0)
166#define AddMem(p, s) do {} while (0)
167#define SubMem(p) do {} while (0)
168#endif
169
170// Returns 0 in case of overflow of nmemb * size.
171static int CheckSizeArgumentsOverflow(uint64_t nmemb, size_t size) {
172 const uint64_t total_size = nmemb * size;
173 if (nmemb == 0) return 1;
174 if ((uint64_t)size > WEBP_MAX_ALLOCABLE_MEMORY / nmemb) return 0;
175 if (!CheckSizeOverflow(total_size)) return 0;
176#if defined(PRINT_MEM_INFO) && defined(MALLOC_FAIL_AT)
177 if (countdown_to_fail > 0 && --countdown_to_fail == 0) {
178 return 0; // fake fail!
179 }
180#endif
181#if defined(PRINT_MEM_INFO) && defined(MALLOC_LIMIT)
182 if (mem_limit > 0) {
183 const uint64_t new_total_mem = (uint64_t)total_mem + total_size;
184 if (!CheckSizeOverflow(new_total_mem) ||
185 new_total_mem > mem_limit) {
186 return 0; // fake fail!
187 }
188 }
189#endif
190
191 return 1;
192}
193
194void* WebPSafeMalloc(uint64_t nmemb, size_t size) {
195 void* ptr;
196 Increment(&num_malloc_calls);
197 if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL;
198 assert(nmemb * size > 0);
199 ptr = malloc((size_t)(nmemb * size));
200 AddMem(ptr, (size_t)(nmemb * size));
201 return ptr;
202}
203
204void* WebPSafeCalloc(uint64_t nmemb, size_t size) {
205 void* ptr;
206 Increment(&num_calloc_calls);
207 if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL;
208 assert(nmemb * size > 0);
209 ptr = calloc((size_t)nmemb, size);
210 AddMem(ptr, (size_t)(nmemb * size));
211 return ptr;
212}
213
214void WebPSafeFree(void* const ptr) {
215 if (ptr != NULL) {
216 Increment(&num_free_calls);
217 SubMem(ptr);
218 }
219 free(ptr);
220}
221
222// Public API functions.
223
224void* WebPMalloc(size_t size) {
225 return WebPSafeMalloc(1, size);
226}
227
228void WebPFree(void* ptr) {
229 WebPSafeFree(ptr);
230}
231
232//------------------------------------------------------------------------------
233
234void WebPCopyPlane(const uint8_t* src, int src_stride,
235 uint8_t* dst, int dst_stride, int width, int height) {
236 assert(src != NULL && dst != NULL);
237 assert(abs(src_stride) >= width && abs(dst_stride) >= width);
238 while (height-- > 0) {
239 memcpy(dst, src, width);
240 src += src_stride;
241 dst += dst_stride;
242 }
243}
244
245void WebPCopyPixels(const WebPPicture* const src, WebPPicture* const dst) {
246 assert(src != NULL && dst != NULL);
247 assert(src->width == dst->width && src->height == dst->height);
248 assert(src->use_argb && dst->use_argb);
249 WebPCopyPlane((uint8_t*)src->argb, 4 * src->argb_stride, (uint8_t*)dst->argb,
250 4 * dst->argb_stride, 4 * src->width, src->height);
251}
252
253//------------------------------------------------------------------------------
254
255#define COLOR_HASH_SIZE (MAX_PALETTE_SIZE * 4)
256#define COLOR_HASH_RIGHT_SHIFT 22 // 32 - log2(COLOR_HASH_SIZE).
257
258int WebPGetColorPalette(const WebPPicture* const pic, uint32_t* const palette) {
259 int i;
260 int x, y;
261 int num_colors = 0;
262 uint8_t in_use[COLOR_HASH_SIZE] = { 0 };
263 uint32_t colors[COLOR_HASH_SIZE];
264 const uint32_t* argb = pic->argb;
265 const int width = pic->width;
266 const int height = pic->height;
267 uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0]
268 assert(pic != NULL);
269 assert(pic->use_argb);
270
271 for (y = 0; y < height; ++y) {
272 for (x = 0; x < width; ++x) {
273 int key;
274 if (argb[x] == last_pix) {
275 continue;
276 }
277 last_pix = argb[x];
278 key = VP8LHashPix(last_pix, COLOR_HASH_RIGHT_SHIFT);
279 while (1) {
280 if (!in_use[key]) {
281 colors[key] = last_pix;
282 in_use[key] = 1;
283 ++num_colors;
284 if (num_colors > MAX_PALETTE_SIZE) {
285 return MAX_PALETTE_SIZE + 1; // Exact count not needed.
286 }
287 break;
288 } else if (colors[key] == last_pix) {
289 break; // The color is already there.
290 } else {
291 // Some other color sits here, so do linear conflict resolution.
292 ++key;
293 key &= (COLOR_HASH_SIZE - 1); // Key mask.
294 }
295 }
296 }
297 argb += pic->argb_stride;
298 }
299
300 if (palette != NULL) { // Fill the colors into palette.
301 num_colors = 0;
302 for (i = 0; i < COLOR_HASH_SIZE; ++i) {
303 if (in_use[i]) {
304 palette[num_colors] = colors[i];
305 ++num_colors;
306 }
307 }
308 }
309 return num_colors;
310}
311
312#undef COLOR_HASH_SIZE
313#undef COLOR_HASH_RIGHT_SHIFT
314
315//------------------------------------------------------------------------------
316
317#if defined(WEBP_NEED_LOG_TABLE_8BIT)
318const uint8_t WebPLogTable8bit[256] = { // 31 ^ clz(i)
319 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
320 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
321 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
322 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
323 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
324 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
325 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
326 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
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 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
333 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
334 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
335};
336#endif
337
338//------------------------------------------------------------------------------
339