1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * Additional copyright for this file:
8 * Copyright (C) 1994-1998 Revolution Software Ltd.
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
23 */
24
25 // The new memory manager, now only used by the resource manager. The original
26 // one would allocated a 12 MB memory pool at startup, which may have been
27 // appropriate for the original Playstation version but didn't work very well
28 // with our PocketPC version.
29 //
30 // There is one thing that prevents us from replacing the whole memory manager
31 // with the standard memory allocation functions: Broken Sword II absolutely,
32 // positively needs to be able to encode pointers as 32-bit integers. The
33 // original engine did this simply by casting between pointers and integers,
34 // but as far as I know that's not a very portable thing to do.
35 //
36 // If it had only used pointers as opcode parameters it would have been
37 // possible, albeit messy, to extend the stack data type. However, there is
38 // code in walker.cpp that obviously violates that assumption, and there are
39 // probably other cases as well.
40 //
41 // Instead, we take advantage of the fact that the original memory manager
42 // could only handle up to 999 blocks of memory. That means we can encode a
43 // pointer as a 10-bit id and a 22-bit offset into the block. Judging by early
44 // testing, both should be plenty.
45 //
46 // The number zero is used to represent the NULL pointer.
47
48 #include "common/textconsole.h"
49
50 #include "sword2/sword2.h"
51 #include "sword2/memory.h"
52
53 namespace Sword2 {
54
MemoryManager()55 MemoryManager::MemoryManager() {
56 // The id stack contains all the possible ids for the memory blocks.
57 // We use this to ensure that no two blocks ever have the same id.
58
59 // The memory blocks are stored in an array, indexed on the block's
60 // id. This means that given a block id we can find the pointer with a
61 // simple array lookup.
62
63 // The memory block index is an array of pointers to the memory block
64 // array, sorted on the memory block's pointer. This means that given
65 // a pointer into a memory block we can find its id with binary
66 // searching.
67 //
68 // A balanced tree might have been more efficient - the index has to
69 // be re-sorted every time a block is allocated or freed - but such
70 // beasts are tricky to implement. Anyway, it wouldn't have made
71 // encoding or decoding pointers any faster, and these are by far the
72 // most common operations.
73
74 _idStack = (int16 *)malloc(MAX_MEMORY_BLOCKS * sizeof(int16));
75 _memBlocks = (MemBlock *)malloc(MAX_MEMORY_BLOCKS * sizeof(MemBlock));
76 _memBlockIndex = (MemBlock **)malloc(MAX_MEMORY_BLOCKS * sizeof(MemBlock *));
77
78 _totAlloc = 0;
79 _numBlocks = 0;
80
81 for (int i = 0; i < MAX_MEMORY_BLOCKS; i++) {
82 _idStack[i] = MAX_MEMORY_BLOCKS - i - 1;
83 _memBlocks[i].ptr = NULL;
84 _memBlockIndex[i] = NULL;
85 }
86
87 _idStackPtr = MAX_MEMORY_BLOCKS;
88 }
89
~MemoryManager()90 MemoryManager::~MemoryManager() {
91 for (int i = 0; i < MAX_MEMORY_BLOCKS; i++)
92 free(_memBlocks[i].ptr);
93 free(_memBlocks);
94 free(_memBlockIndex);
95 free(_idStack);
96 }
97
encodePtr(byte * ptr)98 int32 MemoryManager::encodePtr(byte *ptr) {
99 if (ptr == NULL)
100 return 0;
101
102 int idx = findPointerInIndex(ptr);
103
104 assert(idx != -1);
105
106 uint32 id = _memBlockIndex[idx]->id;
107 uint32 offset = ptr - _memBlocks[id].ptr;
108
109 assert(id < 0x03ff);
110 assert(offset <= 0x003fffff);
111 assert(offset < _memBlocks[id].size);
112
113 return ((id + 1) << 22) | (ptr - _memBlocks[id].ptr);
114 }
115
decodePtr(int32 n)116 byte *MemoryManager::decodePtr(int32 n) {
117 if (n == 0)
118 return NULL;
119
120 uint32 id = ((n & 0xffc00000) >> 22) - 1;
121 uint32 offset = n & 0x003fffff;
122
123 assert(_memBlocks[id].ptr);
124 assert(offset < _memBlocks[id].size);
125
126 return _memBlocks[id].ptr + offset;
127 }
128
findExactPointerInIndex(byte * ptr)129 int16 MemoryManager::findExactPointerInIndex(byte *ptr) {
130 int left = 0;
131 int right = _numBlocks - 1;
132
133 while (right >= left) {
134 int n = (left + right) / 2;
135
136 if (_memBlockIndex[n]->ptr == ptr)
137 return n;
138
139 if (_memBlockIndex[n]->ptr > ptr)
140 right = n - 1;
141 else
142 left = n + 1;
143 }
144
145 return -1;
146 }
147
findPointerInIndex(byte * ptr)148 int16 MemoryManager::findPointerInIndex(byte *ptr) {
149 int left = 0;
150 int right = _numBlocks - 1;
151
152 while (right >= left) {
153 int n = (left + right) / 2;
154
155 if (_memBlockIndex[n]->ptr <= ptr && _memBlockIndex[n]->ptr + _memBlockIndex[n]->size > ptr)
156 return n;
157
158 if (_memBlockIndex[n]->ptr > ptr)
159 right = n - 1;
160 else
161 left = n + 1;
162 }
163
164 return -1;
165 }
166
findInsertionPointInIndex(byte * ptr)167 int16 MemoryManager::findInsertionPointInIndex(byte *ptr) {
168 if (_numBlocks == 0)
169 return 0;
170
171 int left = 0;
172 int right = _numBlocks - 1;
173 int n = 0;
174
175 while (right >= left) {
176 n = (left + right) / 2;
177
178 if (_memBlockIndex[n]->ptr == ptr)
179 return -1;
180
181 if (_memBlockIndex[n]->ptr > ptr)
182 right = n - 1;
183 else
184 left = n + 1;
185 }
186
187 if (_memBlockIndex[n]->ptr < ptr)
188 n++;
189
190 return n;
191 }
192
memAlloc(uint32 size,int16 uid)193 byte *MemoryManager::memAlloc(uint32 size, int16 uid) {
194 assert(_idStackPtr > 0);
195
196 // Get the new block's id from the stack.
197 int16 id = _idStack[--_idStackPtr];
198
199 // Allocate the new memory block
200 byte *ptr = (byte *)malloc(size);
201
202 assert(ptr);
203
204 _memBlocks[id].id = id;
205 _memBlocks[id].uid = uid;
206 _memBlocks[id].ptr = ptr;
207 _memBlocks[id].size = size;
208
209 // Update the memory block index.
210 int16 idx = findInsertionPointInIndex(ptr);
211
212 assert(idx != -1);
213
214 for (int i = _numBlocks; i > idx; i--)
215 _memBlockIndex[i] = _memBlockIndex[i - 1];
216
217 _memBlockIndex[idx] = &_memBlocks[id];
218 _numBlocks++;
219 _totAlloc += size;
220
221 return _memBlocks[id].ptr;
222 }
223
memFree(byte * ptr)224 void MemoryManager::memFree(byte *ptr) {
225 int16 idx = findExactPointerInIndex(ptr);
226
227 if (idx == -1) {
228 warning("Freeing non-allocated pointer %p", (void *)ptr);
229 return;
230 }
231
232 // Put back the id on the stack
233 _idStack[_idStackPtr++] = _memBlockIndex[idx]->id;
234
235 // Release the memory block
236 free(_memBlockIndex[idx]->ptr);
237 _memBlockIndex[idx]->ptr = NULL;
238
239 _totAlloc -= _memBlockIndex[idx]->size;
240
241 // Remove the memory block from the index
242 _numBlocks--;
243
244 for (int i = idx; i < _numBlocks; i++)
245 _memBlockIndex[i] = _memBlockIndex[i + 1];
246 }
247
248 } // End of namespace Sword2
249