unrarsrc  6.1.7
About: unrar extracts, views and tests the contents of archives created with the RAR archiver.
  Fossies Dox: unrarsrc-6.1.7.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

suballoc.cpp
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of PPMd project *
3 * Written and distributed to public domain by Dmitry Shkarin 1997, *
4 * 1999-2000 *
5 * Contents: memory allocation routines *
6 ****************************************************************************/
7
8static const uint UNIT_SIZE=Max(sizeof(RARPPM_CONTEXT),sizeof(RARPPM_MEM_BLK));
9static const uint FIXED_UNIT_SIZE=12;
10
12{
13 Clean();
14}
15
16
18{
20}
21
22
23inline void SubAllocator::InsertNode(void* p,int indx)
24{
25 ((RAR_NODE*) p)->next=FreeList[indx].next;
26 FreeList[indx].next=(RAR_NODE*) p;
27}
28
29
30inline void* SubAllocator::RemoveNode(int indx)
31{
32 RAR_NODE* RetVal=FreeList[indx].next;
33 FreeList[indx].next=RetVal->next;
34 return RetVal;
35}
36
37
38inline uint SubAllocator::U2B(int NU)
39{
40 // We calculate the size of units in bytes based on real UNIT_SIZE.
41 // In original implementation it was 8*NU+4*NU.
42 return UNIT_SIZE*NU;
43}
44
45
46
47// Calculate RARPPM_MEM_BLK+Items address. Real RARPPM_MEM_BLK size must be
48// equal to UNIT_SIZE, so we cannot just add Items to RARPPM_MEM_BLK address.
50{
51 return((RARPPM_MEM_BLK*)( ((byte *)(BasePtr))+U2B(Items) ));
52}
53
54
55inline void SubAllocator::SplitBlock(void* pv,int OldIndx,int NewIndx)
56{
57 int i, UDiff=Indx2Units[OldIndx]-Indx2Units[NewIndx];
58 byte* p=((byte*) pv)+U2B(Indx2Units[NewIndx]);
59 if (Indx2Units[i=Units2Indx[UDiff-1]] != UDiff)
60 {
61 InsertNode(p,--i);
62 p += U2B(i=Indx2Units[i]);
63 UDiff -= i;
64 }
65 InsertNode(p,Units2Indx[UDiff-1]);
66}
67
68
70{
71 if ( SubAllocatorSize )
72 {
74 free(HeapStart);
75 }
76}
77
78
80{
81 uint t=SASize << 20;
82 if (SubAllocatorSize == t)
83 return true;
85
86 // Original algorithm expects FIXED_UNIT_SIZE, but actual structure size
87 // can be larger. So let's recalculate the allocated size and add two more
88 // units: one as reserve for HeapEnd overflow checks and another
89 // to provide the space to correctly align UnitsStart.
91 if ((HeapStart=(byte *)malloc(AllocSize)) == NULL)
92 {
94 return false;
95 }
96
97 // HeapEnd did not present in original algorithm. We added it to control
98 // invalid memory access attempts when processing corrupt archived data.
99 HeapEnd=HeapStart+AllocSize-UNIT_SIZE;
100
102 return true;
103}
104
105
107{
108 int i, k;
109 memset(FreeList,0,sizeof(FreeList));
111
112 // Original algorithm operates with 12 byte FIXED_UNIT_SIZE, but actual
113 // size of RARPPM_MEM_BLK and RARPPM_CONTEXT structures can exceed this value
114 // because of alignment and larger pointer fields size.
115 // So we define UNIT_SIZE for this larger size and adjust memory
116 // pointers accordingly.
117
118 // Size2 is (HiUnit-LoUnit) memory area size to allocate as originally
119 // supposed by compression algorithm. It is 7/8 of total allocated size.
121
122 // RealSize2 is the real adjusted size of (HiUnit-LoUnit) memory taking
123 // into account that our UNIT_SIZE can be larger than FIXED_UNIT_SIZE.
124 uint RealSize2=Size2/FIXED_UNIT_SIZE*UNIT_SIZE;
125
126 // Size1 is the size of memory area from HeapStart to FakeUnitsStart
127 // as originally supposed by compression algorithm. This area can contain
128 // different data types, both single symbols and structures.
129 uint Size1=SubAllocatorSize-Size2;
130
131 // Real size of this area. We correct it according to UNIT_SIZE vs
132 // FIXED_UNIT_SIZE difference. Also we add one more UNIT_SIZE
133 // to compensate a possible reminder from Size1/FIXED_UNIT_SIZE,
134 // which would be lost otherwise. We add UNIT_SIZE instead of
135 // this Size1%FIXED_UNIT_SIZE reminder, because it allows to align
136 // UnitsStart easily and adding more than reminder is ok for algorithm.
137 uint RealSize1=Size1/FIXED_UNIT_SIZE*UNIT_SIZE+UNIT_SIZE;
138
139 // RealSize1 must be divided by UNIT_SIZE without a reminder, so UnitsStart
140 // is aligned to UNIT_SIZE. It is important for those architectures,
141 // where a proper memory alignment is mandatory. Since we produce RealSize1
142 // multiplying by UNIT_SIZE, this condition is always true. So LoUnit,
143 // UnitsStart, HeapStart are properly aligned,
144 LoUnit=UnitsStart=HeapStart+RealSize1;
145
146 // When we reach FakeUnitsStart, we restart the model. It is where
147 // the original algorithm expected to see UnitsStart. Real UnitsStart
148 // can have a larger value.
150
151 HiUnit=LoUnit+RealSize2;
152 for (i=0,k=1;i < N1 ;i++,k += 1)
153 Indx2Units[i]=k;
154 for (k++;i < N1+N2 ;i++,k += 2)
155 Indx2Units[i]=k;
156 for (k++;i < N1+N2+N3 ;i++,k += 3)
157 Indx2Units[i]=k;
158 for (k++;i < N1+N2+N3+N4;i++,k += 4)
159 Indx2Units[i]=k;
160 for (GlueCount=k=i=0;k < 128;k++)
161 {
162 i += (Indx2Units[i] < k+1);
163 Units2Indx[k]=i;
164 }
165}
166
167
169{
170 RARPPM_MEM_BLK s0, * p, * p1;
171 int i, k, sz;
172 if (LoUnit != HiUnit)
173 *LoUnit=0;
174 for (i=0, s0.next=s0.prev=&s0;i < N_INDEXES;i++)
175 while ( FreeList[i].next )
176 {
178 p->insertAt(&s0);
179 p->Stamp=0xFFFF;
180 p->NU=Indx2Units[i];
181 }
182 for (p=s0.next;p != &s0;p=p->next)
183 while ((p1=MBPtr(p,p->NU))->Stamp == 0xFFFF && int(p->NU)+p1->NU < 0x10000)
184 {
185 p1->remove();
186 p->NU += p1->NU;
187 }
188 while ((p=s0.next) != &s0)
189 {
190 for (p->remove(), sz=p->NU;sz > 128;sz -= 128, p=MBPtr(p,128))
192 if (Indx2Units[i=Units2Indx[sz-1]] != sz)
193 {
194 k=sz-Indx2Units[--i];
195 InsertNode(MBPtr(p,sz-k),k-1);
196 }
197 InsertNode(p,i);
198 }
199}
200
202{
203 if ( !GlueCount )
204 {
205 GlueCount = 255;
207 if ( FreeList[indx].next )
208 return RemoveNode(indx);
209 }
210 int i=indx;
211 do
212 {
213 if (++i == N_INDEXES)
214 {
215 GlueCount--;
216 i=U2B(Indx2Units[indx]);
217 int j=FIXED_UNIT_SIZE*Indx2Units[indx];
218 if (FakeUnitsStart - pText > j)
219 {
220 FakeUnitsStart -= j;
221 UnitsStart -= i;
222 return UnitsStart;
223 }
224 return NULL;
225 }
226 } while ( !FreeList[i].next );
227 void* RetVal=RemoveNode(i);
228 SplitBlock(RetVal,i,indx);
229 return RetVal;
230}
231
232
233inline void* SubAllocator::AllocUnits(int NU)
234{
235 int indx=Units2Indx[NU-1];
236 if ( FreeList[indx].next )
237 return RemoveNode(indx);
238 void* RetVal=LoUnit;
239 LoUnit += U2B(Indx2Units[indx]);
240 if (LoUnit <= HiUnit)
241 return RetVal;
242 LoUnit -= U2B(Indx2Units[indx]);
243 return AllocUnitsRare(indx);
244}
245
246
248{
249 if (HiUnit != LoUnit)
250 return (HiUnit -= UNIT_SIZE);
251 if ( FreeList->next )
252 return RemoveNode(0);
253 return AllocUnitsRare(0);
254}
255
256
257void* SubAllocator::ExpandUnits(void* OldPtr,int OldNU)
258{
259 int i0=Units2Indx[OldNU-1], i1=Units2Indx[OldNU-1+1];
260 if (i0 == i1)
261 return OldPtr;
262 void* ptr=AllocUnits(OldNU+1);
263 if ( ptr )
264 {
265 memcpy(ptr,OldPtr,U2B(OldNU));
266 InsertNode(OldPtr,i0);
267 }
268 return ptr;
269}
270
271
272void* SubAllocator::ShrinkUnits(void* OldPtr,int OldNU,int NewNU)
273{
274 int i0=Units2Indx[OldNU-1], i1=Units2Indx[NewNU-1];
275 if (i0 == i1)
276 return OldPtr;
277 if ( FreeList[i1].next )
278 {
279 void* ptr=RemoveNode(i1);
280 memcpy(ptr,OldPtr,U2B(NewNU));
281 InsertNode(OldPtr,i0);
282 return ptr;
283 }
284 else
285 {
286 SplitBlock(OldPtr,i0,i1);
287 return OldPtr;
288 }
289}
290
291
292void SubAllocator::FreeUnits(void* ptr,int OldNU)
293{
294 InsertNode(ptr,Units2Indx[OldNU-1]);
295}
ErrorHandler ErrHandler
void MemoryError()
Definition: errhnd.cpp:22
void InsertNode(void *p, int indx)
Definition: suballoc.cpp:23
byte * HeapStart
Definition: suballoc.hpp:66
long SubAllocatorSize
Definition: suballoc.hpp:64
void Clean()
Definition: suballoc.cpp:17
byte * pText
Definition: suballoc.hpp:82
void * ExpandUnits(void *ptr, int OldNU)
Definition: suballoc.cpp:257
byte Units2Indx[128]
Definition: suballoc.hpp:65
void FreeUnits(void *ptr, int OldNU)
Definition: suballoc.cpp:292
uint U2B(int NU)
Definition: suballoc.cpp:38
void InitSubAllocator()
Definition: suballoc.cpp:106
byte * HeapEnd
Definition: suballoc.hpp:82
static const int N4
Definition: suballoc.hpp:48
struct RAR_NODE FreeList[N_INDEXES]
Definition: suballoc.hpp:67
byte * FakeUnitsStart
Definition: suballoc.hpp:82
byte * HiUnit
Definition: suballoc.hpp:66
static const int N1
Definition: suballoc.hpp:48
void * ShrinkUnits(void *ptr, int OldNU, int NewNU)
Definition: suballoc.cpp:272
RARPPM_MEM_BLK * MBPtr(RARPPM_MEM_BLK *BasePtr, int Items)
Definition: suballoc.cpp:49
void SplitBlock(void *pv, int OldIndx, int NewIndx)
Definition: suballoc.cpp:55
void StopSubAllocator()
Definition: suballoc.cpp:69
byte * LoUnit
Definition: suballoc.hpp:66
void * RemoveNode(int indx)
Definition: suballoc.cpp:30
bool StartSubAllocator(int SASize)
Definition: suballoc.cpp:79
void GlueFreeBlocks()
Definition: suballoc.cpp:168
byte Indx2Units[N_INDEXES]
Definition: suballoc.hpp:65
static const int N2
Definition: suballoc.hpp:48
byte * UnitsStart
Definition: suballoc.hpp:82
void * AllocContext()
Definition: suballoc.cpp:247
static const int N3
Definition: suballoc.hpp:48
void * AllocUnitsRare(int indx)
Definition: suballoc.cpp:201
static const int N_INDEXES
Definition: suballoc.hpp:49
void * AllocUnits(int NU)
Definition: suballoc.cpp:233
byte GlueCount
Definition: suballoc.hpp:65
#define Max(x, y)
Definition: rardefs.hpp:5
unsigned int uint
Definition: rartypes.hpp:8
void remove()
Definition: suballoc.hpp:29
RARPPM_MEM_BLK * next
Definition: suballoc.hpp:23
void insertAt(RARPPM_MEM_BLK *p)
Definition: suballoc.hpp:24
RARPPM_MEM_BLK * prev
Definition: suballoc.hpp:23
ushort Stamp
Definition: suballoc.hpp:22
static const uint FIXED_UNIT_SIZE
Definition: suballoc.cpp:9
static const uint UNIT_SIZE
Definition: suballoc.cpp:8