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