Mercurial > vba-linux

annotate src/win32/7zip/7z/CPP/7zip/Compress/PpmdSubAlloc.h @ 1:f9f4f1b99eed

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