--- /dev/null
+/* Copyright 2015 Google Inc. All Rights Reserved.\r
+\r
+ Distributed under MIT license.\r
+ See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
+*/\r
+\r
+/* Algorithms for distributing the literals and commands of a metablock between\r
+ block types and contexts. */\r
+\r
+#include "./memory.h"\r
+\r
+#include <assert.h>\r
+#include <stdlib.h> /* exit, free, malloc */\r
+#include <string.h> /* memcpy */\r
+\r
+#include "../common/types.h"\r
+#include "./port.h"\r
+\r
+#if defined(__cplusplus) || defined(c_plusplus)\r
+extern "C" {\r
+#endif\r
+\r
+#define MAX_PERM_ALLOCATED 128\r
+#define MAX_NEW_ALLOCATED 64\r
+#define MAX_NEW_FREED 64\r
+\r
+#define PERM_ALLOCATED_OFFSET 0\r
+#define NEW_ALLOCATED_OFFSET MAX_PERM_ALLOCATED\r
+#define NEW_FREED_OFFSET (MAX_PERM_ALLOCATED + MAX_NEW_ALLOCATED)\r
+\r
+static void* DefaultAllocFunc(void* opaque, size_t size) {\r
+ BROTLI_UNUSED(opaque);\r
+ return malloc(size);\r
+}\r
+\r
+static void DefaultFreeFunc(void* opaque, void* address) {\r
+ BROTLI_UNUSED(opaque);\r
+ free(address);\r
+}\r
+\r
+void BrotliInitMemoryManager(\r
+ MemoryManager* m, brotli_alloc_func alloc_func, brotli_free_func free_func,\r
+ void* opaque) {\r
+ if (!alloc_func) {\r
+ m->alloc_func = DefaultAllocFunc;\r
+ m->free_func = DefaultFreeFunc;\r
+ m->opaque = 0;\r
+ } else {\r
+ m->alloc_func = alloc_func;\r
+ m->free_func = free_func;\r
+ m->opaque = opaque;\r
+ }\r
+#if !defined(BROTLI_ENCODER_EXIT_ON_OOM)\r
+ m->is_oom = BROTLI_FALSE;\r
+ m->perm_allocated = 0;\r
+ m->new_allocated = 0;\r
+ m->new_freed = 0;\r
+#endif /* BROTLI_ENCODER_EXIT_ON_OOM */\r
+}\r
+\r
+#if defined(BROTLI_ENCODER_EXIT_ON_OOM)\r
+\r
+void* BrotliAllocate(MemoryManager* m, size_t n) {\r
+ void* result = m->alloc_func(m->opaque, n);\r
+ if (!result) exit(EXIT_FAILURE);\r
+ return result;\r
+}\r
+\r
+void BrotliFree(MemoryManager* m, void* p) {\r
+ m->free_func(m->opaque, p);\r
+}\r
+\r
+void BrotliWipeOutMemoryManager(MemoryManager* m) {\r
+ BROTLI_UNUSED(m);\r
+}\r
+\r
+#else /* BROTLI_ENCODER_EXIT_ON_OOM */\r
+\r
+static void SortPointers(void** items, const size_t n) {\r
+ /* Shell sort. */\r
+ static const size_t gaps[] = {23, 10, 4, 1};\r
+ int g = 0;\r
+ for (; g < 4; ++g) {\r
+ size_t gap = gaps[g];\r
+ size_t i;\r
+ for (i = gap; i < n; ++i) {\r
+ size_t j = i;\r
+ void* tmp = items[i];\r
+ for (; j >= gap && tmp < items[j - gap]; j -= gap) {\r
+ items[j] = items[j - gap];\r
+ }\r
+ items[j] = tmp;\r
+ }\r
+ }\r
+}\r
+\r
+static size_t Annihilate(void** a, size_t a_len, void** b, size_t b_len) {\r
+ size_t a_read_index = 0;\r
+ size_t b_read_index = 0;\r
+ size_t a_write_index = 0;\r
+ size_t b_write_index = 0;\r
+ size_t annihilated = 0;\r
+ while (a_read_index < a_len && b_read_index < b_len) {\r
+ if (a[a_read_index] == b[b_read_index]) {\r
+ a_read_index++;\r
+ b_read_index++;\r
+ annihilated++;\r
+ } else if (a[a_read_index] < b[b_read_index]) {\r
+ a[a_write_index++] = a[a_read_index++];\r
+ } else {\r
+ b[b_write_index++] = b[b_read_index++];\r
+ }\r
+ }\r
+ while (a_read_index < a_len) a[a_write_index++] = a[a_read_index++];\r
+ while (b_read_index < b_len) b[b_write_index++] = b[b_read_index++];\r
+ return annihilated;\r
+}\r
+\r
+static void CollectGarbagePointers(MemoryManager* m) {\r
+ size_t annihilated;\r
+ SortPointers(m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated);\r
+ SortPointers(m->pointers + NEW_FREED_OFFSET, m->new_freed);\r
+ annihilated = Annihilate(\r
+ m->pointers + NEW_ALLOCATED_OFFSET, m->new_allocated,\r
+ m->pointers + NEW_FREED_OFFSET, m->new_freed);\r
+ m->new_allocated -= annihilated;\r
+ m->new_freed -= annihilated;\r
+\r
+ if (m->new_freed != 0) {\r
+ annihilated = Annihilate(\r
+ m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated,\r
+ m->pointers + NEW_FREED_OFFSET, m->new_freed);\r
+ m->perm_allocated -= annihilated;\r
+ m->new_freed -= annihilated;\r
+ assert(m->new_freed == 0);\r
+ }\r
+\r
+ if (m->new_allocated != 0) {\r
+ assert(m->perm_allocated + m->new_allocated <= MAX_PERM_ALLOCATED);\r
+ memcpy(m->pointers + PERM_ALLOCATED_OFFSET + m->perm_allocated,\r
+ m->pointers + NEW_ALLOCATED_OFFSET,\r
+ sizeof(void*) * m->new_allocated);\r
+ m->perm_allocated += m->new_allocated;\r
+ m->new_allocated = 0;\r
+ SortPointers(m->pointers + PERM_ALLOCATED_OFFSET, m->perm_allocated);\r
+ }\r
+}\r
+\r
+void* BrotliAllocate(MemoryManager* m, size_t n) {\r
+ void* result = m->alloc_func(m->opaque, n);\r
+ if (!result) {\r
+ m->is_oom = BROTLI_TRUE;\r
+ return NULL;\r
+ }\r
+ if (m->new_allocated == MAX_NEW_ALLOCATED) CollectGarbagePointers(m);\r
+ m->pointers[NEW_ALLOCATED_OFFSET + (m->new_allocated++)] = result;\r
+ return result;\r
+}\r
+\r
+void BrotliFree(MemoryManager* m, void* p) {\r
+ if (!p) return;\r
+ m->free_func(m->opaque, p);\r
+ if (m->new_freed == MAX_NEW_FREED) CollectGarbagePointers(m);\r
+ m->pointers[NEW_FREED_OFFSET + (m->new_freed++)] = p;\r
+}\r
+\r
+void BrotliWipeOutMemoryManager(MemoryManager* m) {\r
+ size_t i;\r
+ CollectGarbagePointers(m);\r
+ /* Now all unfreed pointers are in perm-allocated list. */\r
+ for (i = 0; i < m->perm_allocated; ++i) {\r
+ m->free_func(m->opaque, m->pointers[PERM_ALLOCATED_OFFSET + i]);\r
+ }\r
+ m->perm_allocated = 0;\r
+}\r
+\r
+#endif /* BROTLI_ENCODER_EXIT_ON_OOM */\r
+\r
+#if defined(__cplusplus) || defined(c_plusplus)\r
+} /* extern "C" */\r
+#endif\r
projects / mirror_edk2.git / blobdiff