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