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 <brotli/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 182
