"Fossies" - the Fresh Open Source Software Archive 
Member "unrar/suballoc.cpp" (4 May 2022, 7911 Bytes) of package /linux/misc/unrarsrc-6.1.7.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "suballoc.cpp" see the
Fossies "Dox" file reference documentation.
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
8 static const uint UNIT_SIZE=Max(sizeof(RARPPM_CONTEXT),sizeof(RARPPM_MEM_BLK));
9 static const uint FIXED_UNIT_SIZE=12;
10
11 SubAllocator::SubAllocator()
12 {
13 Clean();
14 }
15
16
17 void SubAllocator::Clean()
18 {
19 SubAllocatorSize=0;
20 }
21
22
23 inline 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
30 inline 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
38 inline 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.
49 inline RARPPM_MEM_BLK* SubAllocator::MBPtr(RARPPM_MEM_BLK *BasePtr,int Items)
50 {
51 return((RARPPM_MEM_BLK*)( ((byte *)(BasePtr))+U2B(Items) ));
52 }
53
54
55 inline 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
69 void SubAllocator::StopSubAllocator()
70 {
71 if ( SubAllocatorSize )
72 {
73 SubAllocatorSize=0;
74 free(HeapStart);
75 }
76 }
77
78
79 bool SubAllocator::StartSubAllocator(int SASize)
80 {
81 uint t=SASize << 20;
82 if (SubAllocatorSize == t)
83 return true;
84 StopSubAllocator();
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.
90 uint AllocSize=t/FIXED_UNIT_SIZE*UNIT_SIZE+2*UNIT_SIZE;
91 if ((HeapStart=(byte *)malloc(AllocSize)) == NULL)
92 {
93 ErrHandler.MemoryError();
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
101 SubAllocatorSize=t;
102 return true;
103 }
104
105
106 void SubAllocator::InitSubAllocator()
107 {
108 int i, k;
109 memset(FreeList,0,sizeof(FreeList));
110 pText=HeapStart;
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.
120 uint Size2=FIXED_UNIT_SIZE*(SubAllocatorSize/8/FIXED_UNIT_SIZE*7);
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.
149 FakeUnitsStart=HeapStart+Size1;
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
168 inline void SubAllocator::GlueFreeBlocks()
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 {
177 p=(RARPPM_MEM_BLK*)RemoveNode(i);
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))
191 InsertNode(p,N_INDEXES-1);
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
201 void* SubAllocator::AllocUnitsRare(int indx)
202 {
203 if ( !GlueCount )
204 {
205 GlueCount = 255;
206 GlueFreeBlocks();
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
233 inline 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
247 void* SubAllocator::AllocContext()
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
257 void* 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
272 void* 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
292 void SubAllocator::FreeUnits(void* ptr,int OldNU)
293 {
294 InsertNode(ptr,Units2Indx[OldNU-1]);
295 }