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 |
171 | |