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 (at) 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 function. 220 void WebPFree(void* ptr) { 221 free(ptr); 222 } 223 224 //------------------------------------------------------------------------------ 225 226 void WebPCopyPlane(const uint8_t* src, int src_stride, 227 uint8_t* dst, int dst_stride, int width, int height) { 228 assert(src != NULL && dst != NULL); 229 assert(src_stride >= width && dst_stride >= width); 230 while (height-- > 0) { 231 memcpy(dst, src, width); 232 src += src_stride; 233 dst += dst_stride; 234 } 235 } 236 237 void WebPCopyPixels(const WebPPicture* const src, WebPPicture* const dst) { 238 assert(src != NULL && dst != NULL); 239 assert(src->width == dst->width && src->height == dst->height); 240 assert(src->use_argb && dst->use_argb); 241 WebPCopyPlane((uint8_t*)src->argb, 4 * src->argb_stride, (uint8_t*)dst->argb, 242 4 * dst->argb_stride, 4 * src->width, src->height); 243 } 244 245 //------------------------------------------------------------------------------ 246 247 #define COLOR_HASH_SIZE (MAX_PALETTE_SIZE * 4) 248 #define COLOR_HASH_RIGHT_SHIFT 22 // 32 - log2(COLOR_HASH_SIZE). 249 250 int WebPGetColorPalette(const WebPPicture* const pic, uint32_t* const palette) { 251 int i; 252 int x, y; 253 int num_colors = 0; 254 uint8_t in_use[COLOR_HASH_SIZE] = { 0 }; 255 uint32_t colors[COLOR_HASH_SIZE]; 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 = VP8LHashPix(last_pix, 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) 310 const 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