1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/win32/7zip/7z/CPP/7zip/Compress/PpmdSubAlloc.h	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,295 @@
     1.4 +// PpmdSubAlloc.h
     1.5 +// This code is based on Dmitry Shkarin's PPMdH code
     1.6 +
     1.7 +#ifndef __COMPRESS_PPMD_SUB_ALLOC_H
     1.8 +#define __COMPRESS_PPMD_SUB_ALLOC_H
     1.9 +
    1.10 +extern "C"
    1.11 +{
    1.12 +#include "../../../C/Alloc.h"
    1.13 +}
    1.14 +
    1.15 +#include "PpmdType.h"
    1.16 +
    1.17 +const UINT N1=4, N2=4, N3=4, N4=(128+3-1*N1-2*N2-3*N3)/4;
    1.18 +const UINT UNIT_SIZE=12, N_INDEXES=N1+N2+N3+N4;
    1.19 +
    1.20 +// Extra 1 * UNIT_SIZE for NULL support
    1.21 +// Extra 2 * UNIT_SIZE for s0 in GlueFreeBlocks()
    1.22 +const UInt32 kExtraSize = (UNIT_SIZE * 3);
    1.23 +const UInt32 kMaxMemBlockSize = 0xFFFFFFFF - kExtraSize;
    1.24 +
    1.25 +struct MEM_BLK
    1.26 +{
    1.27 +  UInt16 Stamp, NU;
    1.28 +  UInt32 Next, Prev;
    1.29 +  void InsertAt(Byte *Base, UInt32 p)
    1.30 +  {
    1.31 +    Prev = p;
    1.32 +    MEM_BLK *pp = (MEM_BLK *)(Base + p);
    1.33 +    Next = pp->Next;
    1.34 +    pp->Next = ((MEM_BLK *)(Base + Next))->Prev = (UInt32)((Byte *)this - Base);
    1.35 +  }
    1.36 +  void Remove(Byte *Base)
    1.37 +  {
    1.38 +    ((MEM_BLK *)(Base + Prev))->Next = Next;
    1.39 +    ((MEM_BLK *)(Base + Next))->Prev = Prev;
    1.40 +  }
    1.41 +};
    1.42 +
    1.43 +
    1.44 +class CSubAllocator
    1.45 +{
    1.46 +  UInt32 SubAllocatorSize;
    1.47 +  Byte Indx2Units[N_INDEXES], Units2Indx[128], GlueCount;
    1.48 +  UInt32 FreeList[N_INDEXES];
    1.49 +
    1.50 +  Byte *Base;
    1.51 +  Byte *HeapStart, *LoUnit, *HiUnit;
    1.52 +public:
    1.53 +  Byte *pText, *UnitsStart;
    1.54 +  CSubAllocator():
    1.55 +    SubAllocatorSize(0),
    1.56 +    GlueCount(0),
    1.57 +    LoUnit(0),
    1.58 +    HiUnit(0),
    1.59 +    pText(0),
    1.60 +    UnitsStart(0)
    1.61 +  {
    1.62 +    memset(Indx2Units, 0, sizeof(Indx2Units));
    1.63 +    memset(FreeList, 0, sizeof(FreeList));
    1.64 +  }
    1.65 +  ~CSubAllocator()
    1.66 +  {
    1.67 +    StopSubAllocator();
    1.68 +  };
    1.69 +
    1.70 +  void *GetPtr(UInt32 offset) const { return (offset == 0) ? 0 : (void *)(Base + offset); }
    1.71 +  void *GetPtrNoCheck(UInt32 offset) const { return (void *)(Base + offset); }
    1.72 +  UInt32 GetOffset(void *ptr) const { return (ptr == 0) ? 0 : (UInt32)((Byte *)ptr - Base); }
    1.73 +  UInt32 GetOffsetNoCheck(void *ptr) const { return (UInt32)((Byte *)ptr - Base); }
    1.74 +  MEM_BLK *GetBlk(UInt32 offset) const { return (MEM_BLK *)(Base + offset); }
    1.75 +  UInt32 *GetNode(UInt32 offset) const { return (UInt32 *)(Base + offset); }
    1.76 +
    1.77 +  void InsertNode(void* p, int indx)
    1.78 +  {
    1.79 +    *(UInt32 *)p = FreeList[indx];
    1.80 +    FreeList[indx] = GetOffsetNoCheck(p);
    1.81 +  }
    1.82 +
    1.83 +  void* RemoveNode(int indx)
    1.84 +  {
    1.85 +    UInt32 offset = FreeList[indx];
    1.86 +    UInt32 *p = GetNode(offset);
    1.87 +    FreeList[indx] = *p;
    1.88 +    return (void *)p;
    1.89 +  }
    1.90 +  
    1.91 +  UINT U2B(int NU) const { return (UINT)(NU) * UNIT_SIZE; }
    1.92 +  
    1.93 +  void SplitBlock(void* pv, int oldIndx, int newIndx)
    1.94 +  {
    1.95 +    int i, UDiff = Indx2Units[oldIndx] - Indx2Units[newIndx];
    1.96 +    Byte* p = ((Byte*)pv) + U2B(Indx2Units[newIndx]);
    1.97 +    if (Indx2Units[i = Units2Indx[UDiff-1]] != UDiff)
    1.98 +    {
    1.99 +      InsertNode(p, --i);
   1.100 +      p += U2B(i = Indx2Units[i]);
   1.101 +      UDiff -= i;
   1.102 +    }
   1.103 +    InsertNode(p, Units2Indx[UDiff - 1]);
   1.104 +  }
   1.105 +  
   1.106 +  UInt32 GetUsedMemory() const
   1.107 +  {
   1.108 +    UInt32 RetVal = SubAllocatorSize - (UInt32)(HiUnit - LoUnit) - (UInt32)(UnitsStart - pText);
   1.109 +    for (UInt32 i = 0; i < N_INDEXES; i++)
   1.110 +      for (UInt32 pn = FreeList[i]; pn != 0; RetVal -= (UInt32)Indx2Units[i] * UNIT_SIZE)
   1.111 +        pn = *GetNode(pn);
   1.112 +    return (RetVal >> 2);
   1.113 +  }
   1.114 +  
   1.115 +  UInt32 GetSubAllocatorSize() const { return SubAllocatorSize; }
   1.116 +
   1.117 +  void StopSubAllocator()
   1.118 +  {
   1.119 +    if (SubAllocatorSize != 0)
   1.120 +    {
   1.121 +      BigFree(Base);
   1.122 +      SubAllocatorSize = 0;
   1.123 +      Base = 0;
   1.124 +    }
   1.125 +  }
   1.126 +
   1.127 +  bool StartSubAllocator(UInt32 size)
   1.128 +  {
   1.129 +    if (SubAllocatorSize == size)
   1.130 +      return true;
   1.131 +    StopSubAllocator();
   1.132 +    if (size == 0)
   1.133 +      Base = 0;
   1.134 +    else
   1.135 +    {
   1.136 +      if ((Base = (Byte *)::BigAlloc(size + kExtraSize)) == 0)
   1.137 +        return false;
   1.138 +      HeapStart = Base + UNIT_SIZE; // we need such code to support NULL;
   1.139 +    }
   1.140 +    SubAllocatorSize = size;
   1.141 +    return true;
   1.142 +  }
   1.143 +
   1.144 +  void InitSubAllocator()
   1.145 +  {
   1.146 +    int i, k;
   1.147 +    memset(FreeList, 0, sizeof(FreeList));
   1.148 +    HiUnit = (pText = HeapStart) + SubAllocatorSize;
   1.149 +    UINT Diff = UNIT_SIZE * (SubAllocatorSize / 8 / UNIT_SIZE * 7);
   1.150 +    LoUnit = UnitsStart = HiUnit - Diff;
   1.151 +    for (i = 0, k=1; i < N1 ; i++, k += 1)        Indx2Units[i] = (Byte)k;
   1.152 +    for (k++; i < N1 + N2      ;i++, k += 2)      Indx2Units[i] = (Byte)k;
   1.153 +    for (k++; i < N1 + N2 + N3   ;i++,k += 3)     Indx2Units[i] = (Byte)k;
   1.154 +    for (k++; i < N1 + N2 + N3 + N4; i++, k += 4) Indx2Units[i] = (Byte)k;
   1.155 +    GlueCount = 0;
   1.156 +    for (k = i = 0; k < 128; k++)
   1.157 +    {
   1.158 +      i += (Indx2Units[i] < k+1);
   1.159 +        Units2Indx[k] = (Byte)i;
   1.160 +    }
   1.161 +  }
   1.162 +  
   1.163 +  void GlueFreeBlocks()
   1.164 +  {
   1.165 +    UInt32 s0 = (UInt32)(HeapStart + SubAllocatorSize - Base);
   1.166 +
   1.167 +    // We need add exta MEM_BLK with Stamp=0
   1.168 +    GetBlk(s0)->Stamp = 0;
   1.169 +    s0 += UNIT_SIZE;
   1.170 +    MEM_BLK *ps0 = GetBlk(s0);
   1.171 +
   1.172 +    UInt32 p;
   1.173 +    int i;
   1.174 +    if (LoUnit != HiUnit)
   1.175 +      *LoUnit=0;
   1.176 +    ps0->Next = ps0->Prev = s0;
   1.177 +
   1.178 +    for (i = 0; i < N_INDEXES; i++)
   1.179 +      while (FreeList[i] != 0)
   1.180 +      {
   1.181 +        MEM_BLK *pp = (MEM_BLK *)RemoveNode(i);
   1.182 +        pp->InsertAt(Base, s0);
   1.183 +        pp->Stamp = 0xFFFF;
   1.184 +        pp->NU = Indx2Units[i];
   1.185 +      }
   1.186 +    for (p = ps0->Next; p != s0; p = GetBlk(p)->Next)
   1.187 +    {
   1.188 +      for (;;)
   1.189 +      {
   1.190 +        MEM_BLK *pp = GetBlk(p);
   1.191 +        MEM_BLK *pp1 = GetBlk(p + pp->NU * UNIT_SIZE);
   1.192 +        if (pp1->Stamp != 0xFFFF || int(pp->NU) + pp1->NU >= 0x10000)
   1.193 +          break;
   1.194 +        pp1->Remove(Base);
   1.195 +        pp->NU = (UInt16)(pp->NU + pp1->NU);
   1.196 +      }
   1.197 +    }
   1.198 +    while ((p = ps0->Next) != s0)
   1.199 +    {
   1.200 +      MEM_BLK *pp = GetBlk(p);
   1.201 +      pp->Remove(Base);
   1.202 +      int sz;
   1.203 +      for (sz = pp->NU; sz > 128; sz -= 128, p += 128 * UNIT_SIZE)
   1.204 +        InsertNode(Base + p, N_INDEXES - 1);
   1.205 +      if (Indx2Units[i = Units2Indx[sz-1]] != sz)
   1.206 +      {
   1.207 +        int k = sz - Indx2Units[--i];
   1.208 +        InsertNode(Base + p + (sz - k) * UNIT_SIZE, k - 1);
   1.209 +      }
   1.210 +      InsertNode(Base + p, i);
   1.211 +    }
   1.212 +  }
   1.213 +  void* AllocUnitsRare(int indx)
   1.214 +  {
   1.215 +    if ( !GlueCount )
   1.216 +    {
   1.217 +      GlueCount = 255;
   1.218 +      GlueFreeBlocks();
   1.219 +      if (FreeList[indx] != 0)
   1.220 +        return RemoveNode(indx);
   1.221 +    }
   1.222 +    int i = indx;
   1.223 +    do
   1.224 +    {
   1.225 +      if (++i == N_INDEXES)
   1.226 +      {
   1.227 +        GlueCount--;
   1.228 +        i = U2B(Indx2Units[indx]);
   1.229 +        return (UnitsStart - pText > i) ? (UnitsStart -= i) : (NULL);
   1.230 +      }
   1.231 +    } while (FreeList[i] == 0);
   1.232 +    void* RetVal = RemoveNode(i);
   1.233 +    SplitBlock(RetVal, i, indx);
   1.234 +    return RetVal;
   1.235 +  }
   1.236 +  
   1.237 +  void* AllocUnits(int NU)
   1.238 +  {
   1.239 +    int indx = Units2Indx[NU - 1];
   1.240 +    if (FreeList[indx] != 0)
   1.241 +      return RemoveNode(indx);
   1.242 +    void* RetVal = LoUnit;
   1.243 +    LoUnit += U2B(Indx2Units[indx]);
   1.244 +    if (LoUnit <= HiUnit)
   1.245 +      return RetVal;
   1.246 +    LoUnit -= U2B(Indx2Units[indx]);
   1.247 +    return AllocUnitsRare(indx);
   1.248 +  }
   1.249 +  
   1.250 +  void* AllocContext()
   1.251 +  {
   1.252 +    if (HiUnit != LoUnit)
   1.253 +      return (HiUnit -= UNIT_SIZE);
   1.254 +    if (FreeList[0] != 0)
   1.255 +      return RemoveNode(0);
   1.256 +    return AllocUnitsRare(0);
   1.257 +  }
   1.258 +  
   1.259 +  void* ExpandUnits(void* oldPtr, int oldNU)
   1.260 +  {
   1.261 +    int i0=Units2Indx[oldNU - 1], i1=Units2Indx[oldNU - 1 + 1];
   1.262 +    if (i0 == i1)
   1.263 +      return oldPtr;
   1.264 +    void* ptr = AllocUnits(oldNU + 1);
   1.265 +    if (ptr)
   1.266 +    {
   1.267 +      memcpy(ptr, oldPtr, U2B(oldNU));
   1.268 +      InsertNode(oldPtr, i0);
   1.269 +    }
   1.270 +    return ptr;
   1.271 +  }
   1.272 +  
   1.273 +  void* ShrinkUnits(void* oldPtr, int oldNU, int newNU)
   1.274 +  {
   1.275 +    int i0 = Units2Indx[oldNU - 1], i1 = Units2Indx[newNU - 1];
   1.276 +    if (i0 == i1)
   1.277 +      return oldPtr;
   1.278 +    if (FreeList[i1] != 0)
   1.279 +    {
   1.280 +      void* ptr = RemoveNode(i1);
   1.281 +      memcpy(ptr, oldPtr, U2B(newNU));
   1.282 +      InsertNode(oldPtr,i0);
   1.283 +      return ptr;
   1.284 +    }
   1.285 +    else
   1.286 +    {
   1.287 +      SplitBlock(oldPtr, i0, i1);
   1.288 +      return oldPtr;
   1.289 +    }
   1.290 +  }
   1.291 +  
   1.292 +  void FreeUnits(void* ptr, int oldNU)
   1.293 +  {
   1.294 +    InsertNode(ptr, Units2Indx[oldNU - 1]);
   1.295 +  }
   1.296 +};
   1.297 +
   1.298 +#endif