Mercurial > vba-linux
comparison src/win32/7zip/7z/CPP/7zip/Compress/PpmdSubAlloc.h @ 1:f9f4f1b99eed
importing src directory
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sat, 03 Mar 2012 10:31:27 -0600 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
0:8ced16adf2e1 | 1:f9f4f1b99eed |
---|---|
1 // PpmdSubAlloc.h | |
2 // This code is based on Dmitry Shkarin's PPMdH code | |
3 | |
4 #ifndef __COMPRESS_PPMD_SUB_ALLOC_H | |
5 #define __COMPRESS_PPMD_SUB_ALLOC_H | |
6 | |
7 extern "C" | |
8 { | |
9 #include "../../../C/Alloc.h" | |
10 } | |
11 | |
12 #include "PpmdType.h" | |
13 | |
14 const UINT N1=4, N2=4, N3=4, N4=(128+3-1*N1-2*N2-3*N3)/4; | |
15 const UINT UNIT_SIZE=12, N_INDEXES=N1+N2+N3+N4; | |
16 | |
17 // Extra 1 * UNIT_SIZE for NULL support | |
18 // Extra 2 * UNIT_SIZE for s0 in GlueFreeBlocks() | |
19 const UInt32 kExtraSize = (UNIT_SIZE * 3); | |
20 const UInt32 kMaxMemBlockSize = 0xFFFFFFFF - kExtraSize; | |
21 | |
22 struct MEM_BLK | |
23 { | |
24 UInt16 Stamp, NU; | |
25 UInt32 Next, Prev; | |
26 void InsertAt(Byte *Base, UInt32 p) | |
27 { | |
28 Prev = p; | |
29 MEM_BLK *pp = (MEM_BLK *)(Base + p); | |
30 Next = pp->Next; | |
31 pp->Next = ((MEM_BLK *)(Base + Next))->Prev = (UInt32)((Byte *)this - Base); | |
32 } | |
33 void Remove(Byte *Base) | |
34 { | |
35 ((MEM_BLK *)(Base + Prev))->Next = Next; | |
36 ((MEM_BLK *)(Base + Next))->Prev = Prev; | |
37 } | |
38 }; | |
39 | |
40 | |
41 class CSubAllocator | |
42 { | |
43 UInt32 SubAllocatorSize; | |
44 Byte Indx2Units[N_INDEXES], Units2Indx[128], GlueCount; | |
45 UInt32 FreeList[N_INDEXES]; | |
46 | |
47 Byte *Base; | |
48 Byte *HeapStart, *LoUnit, *HiUnit; | |
49 public: | |
50 Byte *pText, *UnitsStart; | |
51 CSubAllocator(): | |
52 SubAllocatorSize(0), | |
53 GlueCount(0), | |
54 LoUnit(0), | |
55 HiUnit(0), | |
56 pText(0), | |
57 UnitsStart(0) | |
58 { | |
59 memset(Indx2Units, 0, sizeof(Indx2Units)); | |
60 memset(FreeList, 0, sizeof(FreeList)); | |
61 } | |
62 ~CSubAllocator() | |
63 { | |
64 StopSubAllocator(); | |
65 }; | |
66 | |
67 void *GetPtr(UInt32 offset) const { return (offset == 0) ? 0 : (void *)(Base + offset); } | |
68 void *GetPtrNoCheck(UInt32 offset) const { return (void *)(Base + offset); } | |
69 UInt32 GetOffset(void *ptr) const { return (ptr == 0) ? 0 : (UInt32)((Byte *)ptr - Base); } | |
70 UInt32 GetOffsetNoCheck(void *ptr) const { return (UInt32)((Byte *)ptr - Base); } | |
71 MEM_BLK *GetBlk(UInt32 offset) const { return (MEM_BLK *)(Base + offset); } | |
72 UInt32 *GetNode(UInt32 offset) const { return (UInt32 *)(Base + offset); } | |
73 | |
74 void InsertNode(void* p, int indx) | |
75 { | |
76 *(UInt32 *)p = FreeList[indx]; | |
77 FreeList[indx] = GetOffsetNoCheck(p); | |
78 } | |
79 | |
80 void* RemoveNode(int indx) | |
81 { | |
82 UInt32 offset = FreeList[indx]; | |
83 UInt32 *p = GetNode(offset); | |
84 FreeList[indx] = *p; | |
85 return (void *)p; | |
86 } | |
87 | |
88 UINT U2B(int NU) const { return (UINT)(NU) * UNIT_SIZE; } | |
89 | |
90 void SplitBlock(void* pv, int oldIndx, int newIndx) | |
91 { | |
92 int i, UDiff = Indx2Units[oldIndx] - Indx2Units[newIndx]; | |
93 Byte* p = ((Byte*)pv) + U2B(Indx2Units[newIndx]); | |
94 if (Indx2Units[i = Units2Indx[UDiff-1]] != UDiff) | |
95 { | |
96 InsertNode(p, --i); | |
97 p += U2B(i = Indx2Units[i]); | |
98 UDiff -= i; | |
99 } | |
100 InsertNode(p, Units2Indx[UDiff - 1]); | |
101 } | |
102 | |
103 UInt32 GetUsedMemory() const | |
104 { | |
105 UInt32 RetVal = SubAllocatorSize - (UInt32)(HiUnit - LoUnit) - (UInt32)(UnitsStart - pText); | |
106 for (UInt32 i = 0; i < N_INDEXES; i++) | |
107 for (UInt32 pn = FreeList[i]; pn != 0; RetVal -= (UInt32)Indx2Units[i] * UNIT_SIZE) | |
108 pn = *GetNode(pn); | |
109 return (RetVal >> 2); | |
110 } | |
111 | |
112 UInt32 GetSubAllocatorSize() const { return SubAllocatorSize; } | |
113 | |
114 void StopSubAllocator() | |
115 { | |
116 if (SubAllocatorSize != 0) | |
117 { | |
118 BigFree(Base); | |
119 SubAllocatorSize = 0; | |
120 Base = 0; | |
121 } | |
122 } | |
123 | |
124 bool StartSubAllocator(UInt32 size) | |
125 { | |
126 if (SubAllocatorSize == size) | |
127 return true; | |
128 StopSubAllocator(); | |
129 if (size == 0) | |
130 Base = 0; | |
131 else | |
132 { | |
133 if ((Base = (Byte *)::BigAlloc(size + kExtraSize)) == 0) | |
134 return false; | |
135 HeapStart = Base + UNIT_SIZE; // we need such code to support NULL; | |
136 } | |
137 SubAllocatorSize = size; | |
138 return true; | |
139 } | |
140 | |
141 void InitSubAllocator() | |
142 { | |
143 int i, k; | |
144 memset(FreeList, 0, sizeof(FreeList)); | |
145 HiUnit = (pText = HeapStart) + SubAllocatorSize; | |
146 UINT Diff = UNIT_SIZE * (SubAllocatorSize / 8 / UNIT_SIZE * 7); | |
147 LoUnit = UnitsStart = HiUnit - Diff; | |
148 for (i = 0, k=1; i < N1 ; i++, k += 1) Indx2Units[i] = (Byte)k; | |
149 for (k++; i < N1 + N2 ;i++, k += 2) Indx2Units[i] = (Byte)k; | |
150 for (k++; i < N1 + N2 + N3 ;i++,k += 3) Indx2Units[i] = (Byte)k; | |
151 for (k++; i < N1 + N2 + N3 + N4; i++, k += 4) Indx2Units[i] = (Byte)k; | |
152 GlueCount = 0; | |
153 for (k = i = 0; k < 128; k++) | |
154 { | |
155 i += (Indx2Units[i] < k+1); | |
156 Units2Indx[k] = (Byte)i; | |
157 } | |
158 } | |
159 | |
160 void GlueFreeBlocks() | |
161 { | |
162 UInt32 s0 = (UInt32)(HeapStart + SubAllocatorSize - Base); | |
163 | |
164 // We need add exta MEM_BLK with Stamp=0 | |
165 GetBlk(s0)->Stamp = 0; | |
166 s0 += UNIT_SIZE; | |
167 MEM_BLK *ps0 = GetBlk(s0); | |
168 | |
169 UInt32 p; | |
170 int i; | |
171 if (LoUnit != HiUnit) | |
172 *LoUnit=0; | |
173 ps0->Next = ps0->Prev = s0; | |
174 | |
175 for (i = 0; i < N_INDEXES; i++) | |
176 while (FreeList[i] != 0) | |
177 { | |
178 MEM_BLK *pp = (MEM_BLK *)RemoveNode(i); | |
179 pp->InsertAt(Base, s0); | |
180 pp->Stamp = 0xFFFF; | |
181 pp->NU = Indx2Units[i]; | |
182 } | |
183 for (p = ps0->Next; p != s0; p = GetBlk(p)->Next) | |
184 { | |
185 for (;;) | |
186 { | |
187 MEM_BLK *pp = GetBlk(p); | |
188 MEM_BLK *pp1 = GetBlk(p + pp->NU * UNIT_SIZE); | |
189 if (pp1->Stamp != 0xFFFF || int(pp->NU) + pp1->NU >= 0x10000) | |
190 break; | |
191 pp1->Remove(Base); | |
192 pp->NU = (UInt16)(pp->NU + pp1->NU); | |
193 } | |
194 } | |
195 while ((p = ps0->Next) != s0) | |
196 { | |
197 MEM_BLK *pp = GetBlk(p); | |
198 pp->Remove(Base); | |
199 int sz; | |
200 for (sz = pp->NU; sz > 128; sz -= 128, p += 128 * UNIT_SIZE) | |
201 InsertNode(Base + p, N_INDEXES - 1); | |
202 if (Indx2Units[i = Units2Indx[sz-1]] != sz) | |
203 { | |
204 int k = sz - Indx2Units[--i]; | |
205 InsertNode(Base + p + (sz - k) * UNIT_SIZE, k - 1); | |
206 } | |
207 InsertNode(Base + p, i); | |
208 } | |
209 } | |
210 void* AllocUnitsRare(int indx) | |
211 { | |
212 if ( !GlueCount ) | |
213 { | |
214 GlueCount = 255; | |
215 GlueFreeBlocks(); | |
216 if (FreeList[indx] != 0) | |
217 return RemoveNode(indx); | |
218 } | |
219 int i = indx; | |
220 do | |
221 { | |
222 if (++i == N_INDEXES) | |
223 { | |
224 GlueCount--; | |
225 i = U2B(Indx2Units[indx]); | |
226 return (UnitsStart - pText > i) ? (UnitsStart -= i) : (NULL); | |
227 } | |
228 } while (FreeList[i] == 0); | |
229 void* RetVal = RemoveNode(i); | |
230 SplitBlock(RetVal, i, indx); | |
231 return RetVal; | |
232 } | |
233 | |
234 void* AllocUnits(int NU) | |
235 { | |
236 int indx = Units2Indx[NU - 1]; | |
237 if (FreeList[indx] != 0) | |
238 return RemoveNode(indx); | |
239 void* RetVal = LoUnit; | |
240 LoUnit += U2B(Indx2Units[indx]); | |
241 if (LoUnit <= HiUnit) | |
242 return RetVal; | |
243 LoUnit -= U2B(Indx2Units[indx]); | |
244 return AllocUnitsRare(indx); | |
245 } | |
246 | |
247 void* AllocContext() | |
248 { | |
249 if (HiUnit != LoUnit) | |
250 return (HiUnit -= UNIT_SIZE); | |
251 if (FreeList[0] != 0) | |
252 return RemoveNode(0); | |
253 return AllocUnitsRare(0); | |
254 } | |
255 | |
256 void* ExpandUnits(void* oldPtr, int oldNU) | |
257 { | |
258 int i0=Units2Indx[oldNU - 1], i1=Units2Indx[oldNU - 1 + 1]; | |
259 if (i0 == i1) | |
260 return oldPtr; | |
261 void* ptr = AllocUnits(oldNU + 1); | |
262 if (ptr) | |
263 { | |
264 memcpy(ptr, oldPtr, U2B(oldNU)); | |
265 InsertNode(oldPtr, i0); | |
266 } | |
267 return ptr; | |
268 } | |
269 | |
270 void* ShrinkUnits(void* oldPtr, int oldNU, int newNU) | |
271 { | |
272 int i0 = Units2Indx[oldNU - 1], i1 = Units2Indx[newNU - 1]; | |
273 if (i0 == i1) | |
274 return oldPtr; | |
275 if (FreeList[i1] != 0) | |
276 { | |
277 void* ptr = RemoveNode(i1); | |
278 memcpy(ptr, oldPtr, U2B(newNU)); | |
279 InsertNode(oldPtr,i0); | |
280 return ptr; | |
281 } | |
282 else | |
283 { | |
284 SplitBlock(oldPtr, i0, i1); | |
285 return oldPtr; | |
286 } | |
287 } | |
288 | |
289 void FreeUnits(void* ptr, int oldNU) | |
290 { | |
291 InsertNode(ptr, Units2Indx[oldNU - 1]); | |
292 } | |
293 }; | |
294 | |
295 #endif |