diff options
Diffstat (limited to '7zip/Compress/PPMD/PPMDSubAlloc.h')
| -rwxr-xr-x | 7zip/Compress/PPMD/PPMDSubAlloc.h | 147 |
1 files changed, 90 insertions, 57 deletions
diff --git a/7zip/Compress/PPMD/PPMDSubAlloc.h b/7zip/Compress/PPMD/PPMDSubAlloc.h index 5a333fe3..fd64d577 100755 --- a/7zip/Compress/PPMD/PPMDSubAlloc.h +++ b/7zip/Compress/PPMD/PPMDSubAlloc.h @@ -11,39 +11,47 @@ const UINT N1=4, N2=4, N3=4, N4=(128+3-1*N1-2*N2-3*N3)/4; const UINT UNIT_SIZE=12, N_INDEXES=N1+N2+N3+N4; -#pragma pack(1) +// Extra 1 * UNIT_SIZE for NULL support +// Extra 2 * UNIT_SIZE for s0 in GlueFreeBlocks() +const UInt32 kExtraSize = (UNIT_SIZE * 3); +const UInt32 kMaxMemBlockSize = 0xFFFFFFFF - kExtraSize; + struct MEM_BLK { UInt16 Stamp, NU; - MEM_BLK *Next, *Prev; - void InsertAt(MEM_BLK* p) + UInt32 Next, Prev; + void InsertAt(Byte *Base, UInt32 p) { - Next = (Prev = p)->Next; - p->Next = Next->Prev = this; + Prev = p; + MEM_BLK *pp = (MEM_BLK *)(Base + p); + Next = pp->Next; + pp->Next = ((MEM_BLK *)(Base + Next))->Prev = (Byte *)this - Base; } - void Remove() + void Remove(Byte *Base) { - Prev->Next=Next; - Next->Prev=Prev; + ((MEM_BLK *)(Base + Prev))->Next = Next; + ((MEM_BLK *)(Base + Next))->Prev = Prev; } -} _PACK_ATTR; -#pragma pack() +}; class CSubAllocator { UInt32 SubAllocatorSize; Byte Indx2Units[N_INDEXES], Units2Indx[128], GlueCount; - struct NODE { NODE* Next; } FreeList[N_INDEXES]; + UInt32 FreeList[N_INDEXES]; + + Byte *Base; + Byte *HeapStart, *LoUnit, *HiUnit; public: - Byte* HeapStart, *pText, *UnitsStart, *LoUnit, *HiUnit; + Byte *pText, *UnitsStart; CSubAllocator(): SubAllocatorSize(0), GlueCount(0), - pText(0), - UnitsStart(0), LoUnit(0), - HiUnit(0) + HiUnit(0), + pText(0), + UnitsStart(0) { memset(Indx2Units, 0, sizeof(Indx2Units)); memset(FreeList, 0, sizeof(FreeList)); @@ -53,21 +61,28 @@ public: StopSubAllocator(); }; + void *GetPtr(UInt32 offset) const { return (offset == 0) ? 0 : (void *)(Base + offset); } + void *GetPtrNoCheck(UInt32 offset) const { return (void *)(Base + offset); } + UInt32 GetOffset(void *ptr) const { return (ptr == 0) ? 0 : (UInt32)((Byte *)ptr - Base); } + UInt32 GetOffsetNoCheck(void *ptr) const { return (UInt32)((Byte *)ptr - Base); } + MEM_BLK *GetBlk(UInt32 offset) const { return (MEM_BLK *)(Base + offset); } + UInt32 *GetNode(UInt32 offset) const { return (UInt32 *)(Base + offset); } void InsertNode(void* p, int indx) { - ((NODE*) p)->Next = FreeList[indx].Next; - FreeList[indx].Next = (NODE*)p; + *(UInt32 *)p = FreeList[indx]; + FreeList[indx] = GetOffsetNoCheck(p); } void* RemoveNode(int indx) { - NODE* RetVal = FreeList[indx].Next; - FreeList[indx].Next = RetVal->Next; - return RetVal; + UInt32 offset = FreeList[indx]; + UInt32 *p = GetNode(offset); + FreeList[indx] = *p; + return (void *)p; } - UINT U2B(int NU) { return 8 * NU + 4 * NU; } + UINT U2B(int NU) const { return (UINT)(NU) * UNIT_SIZE; } void SplitBlock(void* pv, int oldIndx, int newIndx) { @@ -82,25 +97,22 @@ public: InsertNode(p, Units2Indx[UDiff - 1]); } - UInt32 GetUsedMemory() + UInt32 GetUsedMemory() const { - UInt32 i, k, RetVal = SubAllocatorSize - (UInt32)(HiUnit - LoUnit) - (UInt32)(UnitsStart - pText); - for (k = i = 0; i < N_INDEXES; i++, k = 0) - { - for (NODE* pn = FreeList + i;(pn = pn->Next) != NULL; k++) - ; - RetVal -= UNIT_SIZE*Indx2Units[i] * k; - } + UInt32 RetVal = SubAllocatorSize - (UInt32)(HiUnit - LoUnit) - (UInt32)(UnitsStart - pText); + for (UInt32 i = 0; i < N_INDEXES; i++) + for (UInt32 pn = FreeList[i]; pn != 0; RetVal -= (UInt32)Indx2Units[i] * UNIT_SIZE) + pn = *GetNode(pn); return (RetVal >> 2); } void StopSubAllocator() { - if ( SubAllocatorSize ) + if (SubAllocatorSize != 0) { - BigFree(HeapStart); + BigFree(Base); SubAllocatorSize = 0; - HeapStart = 0; + Base = 0; } } @@ -110,10 +122,13 @@ public: return true; StopSubAllocator(); if (size == 0) - HeapStart = 0; + Base = 0; else - if ((HeapStart = (Byte *)::BigAlloc(size)) == 0) + { + if ((Base = (Byte *)::BigAlloc(size + kExtraSize)) == 0) return false; + HeapStart = Base + UNIT_SIZE; // we need such code to support NULL; + } SubAllocatorSize = size; return true; } @@ -138,34 +153,52 @@ public: void GlueFreeBlocks() { - MEM_BLK s0, *p, *p1; - int i, k, sz; + UInt32 s0 = (UInt32)(HeapStart + SubAllocatorSize - Base); + + // We need add exta MEM_BLK with Stamp=0 + GetBlk(s0)->Stamp = 0; + s0 += UNIT_SIZE; + MEM_BLK *ps0 = GetBlk(s0); + + UInt32 p; + int i; if (LoUnit != HiUnit) *LoUnit=0; - for (i = 0, s0.Next = s0.Prev = &s0; i < N_INDEXES; i++) - while ( FreeList[i].Next ) + ps0->Next = ps0->Prev = s0; + + for (i = 0; i < N_INDEXES; i++) + while (FreeList[i] != 0) { - p = (MEM_BLK*) RemoveNode(i); - p->InsertAt(&s0); - p->Stamp = 0xFFFF; - p->NU = Indx2Units[i]; + MEM_BLK *pp = (MEM_BLK *)RemoveNode(i); + pp->InsertAt(Base, s0); + pp->Stamp = 0xFFFF; + pp->NU = Indx2Units[i]; } - for (p=s0.Next; p != &s0; p =p->Next) - while ((p1 = p + p->NU)->Stamp == 0xFFFF && int(p->NU) + p1->NU < 0x10000) + for (p = ps0->Next; p != s0; p = GetBlk(p)->Next) + { + while (true) { - p1->Remove(); - p->NU += p1->NU; + MEM_BLK *pp = GetBlk(p); + MEM_BLK *pp1 = GetBlk(p + pp->NU * UNIT_SIZE); + if (pp1->Stamp != 0xFFFF || int(pp->NU) + pp1->NU >= 0x10000) + break; + pp1->Remove(Base); + pp->NU += pp1->NU; } - while ((p=s0.Next) != &s0) + } + while ((p = ps0->Next) != s0) { - for (p->Remove(), sz=p->NU; sz > 128; sz -= 128, p += 128) - InsertNode(p, N_INDEXES - 1); + MEM_BLK *pp = GetBlk(p); + pp->Remove(Base); + int sz; + for (sz = pp->NU; sz > 128; sz -= 128, p += 128 * UNIT_SIZE) + InsertNode(Base + p, N_INDEXES - 1); if (Indx2Units[i = Units2Indx[sz-1]] != sz) { - k = sz-Indx2Units[--i]; - InsertNode(p + (sz - k), k - 1); + int k = sz - Indx2Units[--i]; + InsertNode(Base + p + (sz - k) * UNIT_SIZE, k - 1); } - InsertNode(p,i); + InsertNode(Base + p, i); } } void* AllocUnitsRare(int indx) @@ -174,7 +207,7 @@ public: { GlueCount = 255; GlueFreeBlocks(); - if (FreeList[indx].Next) + if (FreeList[indx] != 0) return RemoveNode(indx); } int i = indx; @@ -186,7 +219,7 @@ public: i = U2B(Indx2Units[indx]); return (UnitsStart - pText > i) ? (UnitsStart -= i) : (NULL); } - } while (!FreeList[i].Next); + } while (FreeList[i] == 0); void* RetVal = RemoveNode(i); SplitBlock(RetVal, i, indx); return RetVal; @@ -195,7 +228,7 @@ public: void* AllocUnits(int NU) { int indx = Units2Indx[NU - 1]; - if (FreeList[indx].Next) + if (FreeList[indx] != 0) return RemoveNode(indx); void* RetVal = LoUnit; LoUnit += U2B(Indx2Units[indx]); @@ -209,7 +242,7 @@ public: { if (HiUnit != LoUnit) return (HiUnit -= UNIT_SIZE); - if (FreeList->Next) + if (FreeList[0] != 0) return RemoveNode(0); return AllocUnitsRare(0); } @@ -233,7 +266,7 @@ public: int i0 = Units2Indx[oldNU - 1], i1 = Units2Indx[newNU - 1]; if (i0 == i1) return oldPtr; - if ( FreeList[i1].Next ) + if (FreeList[i1] != 0) { void* ptr = RemoveNode(i1); memcpy(ptr, oldPtr, U2B(newNU)); |