"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 }