text: // Copyright 2012 Google Inc. All Rights Reserved.
  //
  // Use of this source code is governed by a BSD-style license
  // that can be found in the COPYING file in the root of the source
  // tree. An additional intellectual property rights grant can be found
  // in the file PATENTS. All contributing project authors may
  // be found in the AUTHORS file in the root of the source tree.
  // -----------------------------------------------------------------------------
  //
  // Misc. common utility functions
  //
  // Author: Skal (pascal.massimino@gmail.com)
  
  #include <stdlib.h>
  #include <string.h>  // for memcpy()
  #include "src/webp/decode.h"
  #include "src/webp/encode.h"
  #include "src/webp/format_constants.h"  // for MAX_PALETTE_SIZE
  #include "src/utils/color_cache_utils.h"
  #include "src/utils/utils.h"
  
  // If PRINT_MEM_INFO is defined, extra info (like total memory used, number of
  // alloc/free etc) is printed. For debugging/tuning purpose only (it's slow,
  // and not multi-thread safe!).
  // An interesting alternative is valgrind's 'massif' tool:
  //    http://valgrind.org/docs/manual/ms-manual.html
  // Here is an example command line:
  /*    valgrind --tool=massif --massif-out-file=massif.out \
                 --stacks=yes --alloc-fn=WebPSafeMalloc --alloc-fn=WebPSafeCalloc
        ms_print massif.out
  */
  // In addition:
  // * if PRINT_MEM_TRAFFIC is defined, all the details of the malloc/free cycles
  //   are printed.
  // * if MALLOC_FAIL_AT is defined, the global environment variable
  //   $MALLOC_FAIL_AT is used to simulate a memory error when calloc or malloc
  //   is called for the nth time. Example usage:
  //   export MALLOC_FAIL_AT=50 && ./examples/cwebp input.png
  // * if MALLOC_LIMIT is defined, the global environment variable $MALLOC_LIMIT
  //   sets the maximum amount of memory (in bytes) made available to libwebp.
  //   This can be used to emulate environment with very limited memory.
  //   Example: export MALLOC_LIMIT=64000000 && ./examples/dwebp picture.webp
  
  // #define PRINT_MEM_INFO
  // #define PRINT_MEM_TRAFFIC
  // #define MALLOC_FAIL_AT
  // #define MALLOC_LIMIT
  
  //------------------------------------------------------------------------------
  // Checked memory allocation
  
  #if defined(PRINT_MEM_INFO)
  
  #include <stdio.h>
  
  static int num_malloc_calls = 0;
  static int num_calloc_calls = 0;
  static int num_free_calls = 0;
  static int countdown_to_fail = 0;     // 0 = off
  
  typedef struct MemBlock MemBlock;
  struct MemBlock {
    void* ptr_;
    size_t size_;
    MemBlock* next_;
  };
  
  static MemBlock* all_blocks = NULL;
  static size_t total_mem = 0;
  static size_t total_mem_allocated = 0;
  static size_t high_water_mark = 0;
  static size_t mem_limit = 0;
  
  static int exit_registered = 0;
  
  static void PrintMemInfo(void) {
    fprintf(stderr, "\nMEMORY INFO:\n");
    fprintf(stderr, "num calls to: malloc = %4d\n", num_malloc_calls);
    fprintf(stderr, "              calloc = %4d\n", num_calloc_calls);
    fprintf(stderr, "              free   = %4d\n", num_free_calls);
    fprintf(stderr, "total_mem: %u\n", (uint32_t)total_mem);
    fprintf(stderr, "total_mem allocated: %u\n", (uint32_t)total_mem_allocated);
    fprintf(stderr, "high-water mark: %u\n", (uint32_t)high_water_mark);
    while (all_blocks != NULL) {
      MemBlock* b = all_blocks;
      all_blocks = b->next_;
      free(b);
    }
  }
  
  static void Increment(int* const v) {
    if (!exit_registered) {
  #if defined(MALLOC_FAIL_AT)
      {
        const char* const malloc_fail_at_str = getenv("MALLOC_FAIL_AT");
        if (malloc_fail_at_str != NULL) {
          countdown_to_fail = atoi(malloc_fail_at_str);
        }
      }
  #endif
  #if defined(MALLOC_LIMIT)
      {
        const char* const malloc_limit_str = getenv("MALLOC_LIMIT");
        if (malloc_limit_str != NULL) {
          mem_limit = atoi(malloc_limit_str);
        }
      }
  #endif
      (void)countdown_to_fail;
      (void)mem_limit;
      atexit(PrintMemInfo);
      exit_registered = 1;
    }
    ++*v;
  }
  
  static void AddMem(void* ptr, size_t size) {
    if (ptr != NULL) {
      MemBlock* const b = (MemBlock*)malloc(sizeof(*b));
      if (b == NULL) abort();
      b->next_ = all_blocks;
      all_blocks = b;
      b->ptr_ = ptr;
      b->size_ = size;
      total_mem += size;
      total_mem_allocated += size;
  #if defined(PRINT_MEM_TRAFFIC)
  #if defined(MALLOC_FAIL_AT)
      fprintf(stderr, "fail-count: %5d [mem=%u]\n",
              num_malloc_calls + num_calloc_calls, (uint32_t)total_mem);
  #else
      fprintf(stderr, "Mem: %u (+%u)\n", (uint32_t)total_mem, (uint32_t)size);
  #endif
  #endif
      if (total_mem > high_water_mark) high_water_mark = total_mem;
    }
  }
  
  static void SubMem(void* ptr) {
    if (ptr != NULL) {
      MemBlock** b = &all_blocks;
      // Inefficient search, but that's just for debugging.
      while (*b != NULL && (*b)->ptr_ != ptr) b = &(*b)->next_;
      if (*b == NULL) {
        fprintf(stderr, "Invalid pointer free! (%p)\n", ptr);
        abort();
      }
      {
        MemBlock* const block = *b;
        *b = block->next_;
        total_mem -= block->size_;
  #if defined(PRINT_MEM_TRAFFIC)
        fprintf(stderr, "Mem: %u (-%u)\n",
                (uint32_t)total_mem, (uint32_t)block->size_);
  #endif
        free(block);
      }
    }
  }
  
  #else
  #define Increment(v) do {} while (0)
  #define AddMem(p, s) do {} while (0)
  #define SubMem(p)    do {} while (0)
  #endif
  
  // Returns 0 in case of overflow of nmemb * size.
  static int CheckSizeArgumentsOverflow(uint64_t nmemb, size_t size) {
    const uint64_t total_size = nmemb * size;
    if (nmemb == 0) return 1;
    if ((uint64_t)size > WEBP_MAX_ALLOCABLE_MEMORY / nmemb) return 0;
    if (total_size != (size_t)total_size) return 0;
  #if defined(PRINT_MEM_INFO) && defined(MALLOC_FAIL_AT)
    if (countdown_to_fail > 0 && --countdown_to_fail == 0) {
      return 0;    // fake fail!
    }
  #endif
  #if defined(MALLOC_LIMIT)
    if (mem_limit > 0) {
      const uint64_t new_total_mem = (uint64_t)total_mem + total_size;
      if (new_total_mem != (size_t)new_total_mem ||
          new_total_mem > mem_limit) {
        return 0;   // fake fail!
      }
    }
  #endif
  
    return 1;
  }
  
  void* WebPSafeMalloc(uint64_t nmemb, size_t size) {
    void* ptr;
    Increment(&num_malloc_calls);
    if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL;
    assert(nmemb * size > 0);
    ptr = malloc((size_t)(nmemb * size));
    AddMem(ptr, (size_t)(nmemb * size));
    return ptr;
  }
  
  void* WebPSafeCalloc(uint64_t nmemb, size_t size) {
    void* ptr;
    Increment(&num_calloc_calls);
    if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL;
    assert(nmemb * size > 0);
    ptr = calloc((size_t)nmemb, size);
    AddMem(ptr, (size_t)(nmemb * size));
    return ptr;
  }
  
  void WebPSafeFree(void* const ptr) {
    if (ptr != NULL) {
      Increment(&num_free_calls);
      SubMem(ptr);
    }
    free(ptr);
  }
  
  // Public API function.
  void WebPFree(void* ptr) {
    free(ptr);
  }
  
  //------------------------------------------------------------------------------
  
  void WebPCopyPlane(const uint8_t* src, int src_stride,
                     uint8_t* dst, int dst_stride, int width, int height) {
    assert(src != NULL && dst != NULL);
    assert(src_stride >= width && dst_stride >= width);
    while (height-- > 0) {
      memcpy(dst, src, width);
      src += src_stride;
      dst += dst_stride;
    }
  }
  
  void WebPCopyPixels(const WebPPicture* const src, WebPPicture* const dst) {
    assert(src != NULL && dst != NULL);
    assert(src->width == dst->width && src->height == dst->height);
    assert(src->use_argb && dst->use_argb);
    WebPCopyPlane((uint8_t*)src->argb, 4 * src->argb_stride, (uint8_t*)dst->argb,
                  4 * dst->argb_stride, 4 * src->width, src->height);
  }
  
  //------------------------------------------------------------------------------
  
  #define COLOR_HASH_SIZE         (MAX_PALETTE_SIZE * 4)
  #define COLOR_HASH_RIGHT_SHIFT  22  // 32 - log2(COLOR_HASH_SIZE).
  
  int WebPGetColorPalette(const WebPPicture* const pic, uint32_t* const palette) {
    int i;
    int x, y;
    int num_colors = 0;
    uint8_t in_use[COLOR_HASH_SIZE] = { 0 };
    uint32_t colors[COLOR_HASH_SIZE];
    const uint32_t* argb = pic->argb;
    const int width = pic->width;
    const int height = pic->height;
    uint32_t last_pix = ~argb[0];   // so we're sure that last_pix != argb[0]
    assert(pic != NULL);
    assert(pic->use_argb);
  
    for (y = 0; y < height; ++y) {
      for (x = 0; x < width; ++x) {
        int key;
        if (argb[x] == last_pix) {
          continue;
        }
        last_pix = argb[x];
        key = VP8LHashPix(last_pix, COLOR_HASH_RIGHT_SHIFT);
        while (1) {
          if (!in_use[key]) {
            colors[key] = last_pix;
            in_use[key] = 1;
            ++num_colors;
            if (num_colors > MAX_PALETTE_SIZE) {
              return MAX_PALETTE_SIZE + 1;  // Exact count not needed.
            }
            break;
          } else if (colors[key] == last_pix) {
            break;  // The color is already there.
          } else {
            // Some other color sits here, so do linear conflict resolution.
            ++key;
            key &= (COLOR_HASH_SIZE - 1);  // Key mask.
          }
        }
      }
      argb += pic->argb_stride;
    }
  
    if (palette != NULL) {  // Fill the colors into palette.
      num_colors = 0;
      for (i = 0; i < COLOR_HASH_SIZE; ++i) {
        if (in_use[i]) {
          palette[num_colors] = colors[i];
          ++num_colors;
        }
      }
    }
    return num_colors;
  }
  
  #undef COLOR_HASH_SIZE
  #undef COLOR_HASH_RIGHT_SHIFT
  
  //------------------------------------------------------------------------------
  
  #if defined(WEBP_NEED_LOG_TABLE_8BIT)
  const uint8_t WebPLogTable8bit[256] = {   // 31 ^ clz(i)
    0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
  };
  #endif
  
  //------------------------------------------------------------------------------
  