• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
PrintMemInfo(void)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 
Increment(int * const v)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 
AddMem(void * ptr,size_t size)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 
SubMem(void * ptr)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.
CheckSizeArgumentsOverflow(uint64_t nmemb,size_t 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 
WebPSafeMalloc(uint64_t nmemb,size_t size)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 
WebPSafeCalloc(uint64_t nmemb,size_t size)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 
WebPSafeFree(void * const ptr)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 
WebPMalloc(size_t size)221 void* WebPMalloc(size_t size) {
222   return WebPSafeMalloc(1, size);
223 }
224 
WebPFree(void * ptr)225 void WebPFree(void* ptr) {
226   WebPSafeFree(ptr);
227 }
228 
229 //------------------------------------------------------------------------------
230 
WebPCopyPlane(const uint8_t * src,int src_stride,uint8_t * dst,int dst_stride,int width,int height)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 
WebPCopyPixels(const WebPPicture * const src,WebPPicture * const dst)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 
WebPGetColorPalette(const WebPPicture * const pic,uint32_t * const palette)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