BaseTools/Source/C/BrotliCompress/enc/memory.c

   1 /* Copyright 2015 Google Inc. All Rights Reserved.
   2
   3    Distributed under MIT license.
   4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
   5 */
   6
   7 /* Algorithms for distributing the literals and commands of a metablock between
   8    block types and contexts. */
   9
  10 #include "./memory.h"
  11
  12 #include <stdlib.h>  /* exit, free, malloc */
  13 #include <string.h>  /* memcpy */
  14
  15 #include "../common/platform.h"
  16 #include <brotli/types.h>
  17
  18 #if defined(__cplusplus) || defined(c_plusplus)
  19 extern "C" {
  20 #endif
  21
  22 #define MAX_PERM_ALLOCATED 128
  23 #define MAX_NEW_ALLOCATED 64
  24 #define MAX_NEW_FREED 64
  25
  26 #define PERM_ALLOCATED_OFFSET 0
  27 #define NEW_ALLOCATED_OFFSET MAX_PERM_ALLOCATED
  28 #define NEW_FREED_OFFSET (MAX_PERM_ALLOCATED + MAX_NEW_ALLOCATED)
  29
  30 void BrotliInitMemoryManager(
  31     MemoryManager* m, brotli_alloc_func alloc_func, brotli_free_func free_func,
  32     void* opaque) {
  33   if (!alloc_func) {
  34     m->alloc_func = BrotliDefaultAllocFunc;
  35     m->free_func = BrotliDefaultFreeFunc;
  36     m->opaque = 0;
  37   } else {
  38     m->alloc_func = alloc_func;
  39     m->free_func = free_func;
  40     m->opaque = opaque;
  41   }
  42 #if !defined(BROTLI_ENCODER_EXIT_ON_OOM)
  43   m->is_oom = BROTLI_FALSE;
  44   m->perm_allocated = 0;
  45   m->new_allocated = 0;
  46   m->new_freed = 0;
  47 #endif  /* BROTLI_ENCODER_EXIT_ON_OOM */
  48 }
  49
  50 #if defined(BROTLI_ENCODER_EXIT_ON_OOM)
  51
  52 void* BrotliAllocate(MemoryManager* m, size_t n) {
  53   void* result = m->alloc_func(m->opaque, n);
  54   if (!result) exit(EXIT_FAILURE);
  55   return result;
  56 }
  57
  58 void BrotliFree(MemoryManager* m, void* p) {
  59   m->free_func(m->opaque, p);
  60 }
  61
  62 void BrotliWipeOutMemoryManager(MemoryManager* m) {
  63   BROTLI_UNUSED(m);
  64 }
  65
  66 #else  /* BROTLI_ENCODER_EXIT_ON_OOM */
  67
  68 static void SortPointers(void** items, const size_t n) {
  69   /* Shell sort. */
  70   static const size_t gaps[] = {23, 10, 4, 1};
  71   int g = 0;
  72   for (; g < 4; ++g) {
  73     size_t gap = gaps[g];
  74     size_t i;
  75     for (i = gap; i < n; ++i) {
  76       size_t j = i;
  77       void* tmp = items[i];
  78       for (; j >= gap && tmp < items[j - gap]; j -= gap) {
  79         items[j] = items[j - gap];
  80       }
  81       items[j] = tmp;
  82     }
  83   }
  84 }
  85
  86 static size_t Annihilate(void** a, size_t a_len, void** b, size_t b_len) {
  87   size_t a_read_index = 0;
  88   size_t b_read_index = 0;
  89   size_t a_write_index = 0;
  90   size_t b_write_index = 0;
  91   size_t annihilated = 0;
  92   while (a_read_index < a_len && b_read_index < b_len) {
  93     if (a[a_read_index] == b[b_read_index]) {
  94       a_read_index++;
  95       b_read_index++;
  96       annihilated++;
  97     } else if (a[a_read_index] < b[b_read_index]) {
  98       a[a_write_index++] = a[a_read_index++];
  99     } else {
 100       b[b_write_index++] = b[b_read_index++];
 101     }
 102   }
 103   while (a_read_index < a_len) a[a_write_index++] = a[a_read_index++];
 104   while (b_read_index < b_len) b[b_write_index++] = b[b_read_index++];
 105   return annihilated;
 106 }
 107
 108 static void CollectGarbagePointers(MemoryManager* m) {
 109   size_t annihilated;
 110   SortPointers(m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated);
 111   SortPointers(m->pointers + NEW_FREED_OFFSET, m->new_freed);
 112   annihilated = Annihilate(
 113       m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated,
 114       m->pointers + NEW_FREED_OFFSET, m->new_freed);
 115   m->new_allocated -= annihilated;
 116   m->new_freed -= annihilated;
 117
 118   if (m->new_freed != 0) {
 119     annihilated = Annihilate(
 120         m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated,
 121         m->pointers + NEW_FREED_OFFSET, m->new_freed);
 122     m->perm_allocated -= annihilated;
 123     m->new_freed -= annihilated;
 124     BROTLI_DCHECK(m->new_freed == 0);
 125   }
 126
 127   if (m->new_allocated != 0) {
 128     BROTLI_DCHECK(m->perm_allocated + m->new_allocated <= MAX_PERM_ALLOCATED);
 129     memcpy(m->pointers + PERM_ALLOCATED_OFFSET + m->perm_allocated,
 130            m->pointers + NEW_ALLOCATED_OFFSET,
 131            sizeof(void*) * m->new_allocated);
 132     m->perm_allocated += m->new_allocated;
 133     m->new_allocated = 0;
 134     SortPointers(m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated);
 135   }
 136 }
 137
 138 void* BrotliAllocate(MemoryManager* m, size_t n) {
 139   void* result = m->alloc_func(m->opaque, n);
 140   if (!result) {
 141     m->is_oom = BROTLI_TRUE;
 142     return NULL;
 143   }
 144   if (m->new_allocated == MAX_NEW_ALLOCATED) CollectGarbagePointers(m);
 145   m->pointers[NEW_ALLOCATED_OFFSET + (m->new_allocated++)] = result;
 146   return result;
 147 }
 148
 149 void BrotliFree(MemoryManager* m, void* p) {
 150   if (!p) return;
 151   m->free_func(m->opaque, p);
 152   if (m->new_freed == MAX_NEW_FREED) CollectGarbagePointers(m);
 153   m->pointers[NEW_FREED_OFFSET + (m->new_freed++)] = p;
 154 }
 155
 156 void BrotliWipeOutMemoryManager(MemoryManager* m) {
 157   size_t i;
 158   CollectGarbagePointers(m);
 159   /* Now all unfreed pointers are in perm-allocated list. */
 160   for (i = 0; i < m->perm_allocated; ++i) {
 161     m->free_func(m->opaque, m->pointers[PERM_ALLOCATED_OFFSET + i]);
 162   }
 163   m->perm_allocated = 0;
 164 }
 165
 166 #endif  /* BROTLI_ENCODER_EXIT_ON_OOM */
 167
 168 #if defined(__cplusplus) || defined(c_plusplus)
 169 }  /* extern "C" */
 170 #endif