SubAllocator.cs 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451
  1. using System;
  2. using System.Text;
  3. namespace SharpCompress.Compressors.PPMd.H
  4. {
  5. internal class SubAllocator
  6. {
  7. public virtual int FakeUnitsStart { get => _fakeUnitsStart; set => _fakeUnitsStart = value; }
  8. public virtual int HeapEnd => _heapEnd;
  9. public virtual int PText { get => _pText; set => _pText = value; }
  10. public virtual int UnitsStart { get => _unitsStart; set => _unitsStart = value; }
  11. public virtual byte[] Heap => _heap;
  12. //UPGRADE_NOTE: Final was removed from the declaration of 'N4 '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  13. public const int N1 = 4;
  14. public const int N2 = 4;
  15. public const int N3 = 4;
  16. public static readonly int N4 = (128 + 3 - 1 * N1 - 2 * N2 - 3 * N3) / 4;
  17. //UPGRADE_NOTE: Final was removed from the declaration of 'N_INDEXES '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  18. public static readonly int N_INDEXES = N1 + N2 + N3 + N4;
  19. //UPGRADE_NOTE: Final was removed from the declaration of 'UNIT_SIZE '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  20. //UPGRADE_NOTE: The initialization of 'UNIT_SIZE' was moved to static method 'SharpCompress.Unpack.PPM.SubAllocator'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1005'"
  21. public static readonly int UNIT_SIZE;
  22. public const int FIXED_UNIT_SIZE = 12;
  23. private int _subAllocatorSize;
  24. // byte Indx2Units[N_INDEXES], Units2Indx[128], GlueCount;
  25. private readonly int[] _indx2Units = new int[N_INDEXES];
  26. private readonly int[] _units2Indx = new int[128];
  27. private int _glueCount;
  28. // byte *HeapStart,*LoUnit, *HiUnit;
  29. private int _heapStart, _loUnit, _hiUnit;
  30. //UPGRADE_NOTE: Final was removed from the declaration of 'freeList '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  31. private readonly RarNode[] _freeList = new RarNode[N_INDEXES];
  32. // byte *pText, *UnitsStart,*HeapEnd,*FakeUnitsStart;
  33. private int _pText, _unitsStart, _heapEnd, _fakeUnitsStart;
  34. private byte[] _heap;
  35. private int _freeListPos;
  36. private int _tempMemBlockPos;
  37. // Temp fields
  38. private RarNode _tempRarNode;
  39. private RarMemBlock _tempRarMemBlock1;
  40. private RarMemBlock _tempRarMemBlock2;
  41. private RarMemBlock _tempRarMemBlock3;
  42. public SubAllocator()
  43. {
  44. Clean();
  45. }
  46. public virtual void Clean()
  47. {
  48. _subAllocatorSize = 0;
  49. }
  50. private void InsertNode(int p, int indx)
  51. {
  52. RarNode temp = _tempRarNode;
  53. temp.Address = p;
  54. temp.SetNext(_freeList[indx].GetNext());
  55. _freeList[indx].SetNext(temp);
  56. }
  57. public virtual void IncPText()
  58. {
  59. _pText++;
  60. }
  61. private int RemoveNode(int indx)
  62. {
  63. int retVal = _freeList[indx].GetNext();
  64. RarNode temp = _tempRarNode;
  65. temp.Address = retVal;
  66. _freeList[indx].SetNext(temp.GetNext());
  67. return retVal;
  68. }
  69. private int U2B(int nu)
  70. {
  71. return UNIT_SIZE * nu;
  72. }
  73. /* memblockptr */
  74. private int MbPtr(int basePtr, int items)
  75. {
  76. return (basePtr + U2B(items));
  77. }
  78. private void SplitBlock(int pv, int oldIndx, int newIndx)
  79. {
  80. int i, uDiff = _indx2Units[oldIndx] - _indx2Units[newIndx];
  81. int p = pv + U2B(_indx2Units[newIndx]);
  82. if (_indx2Units[i = _units2Indx[uDiff - 1]] != uDiff)
  83. {
  84. InsertNode(p, --i);
  85. p += U2B(i = _indx2Units[i]);
  86. uDiff -= i;
  87. }
  88. InsertNode(p, _units2Indx[uDiff - 1]);
  89. }
  90. public virtual void StopSubAllocator()
  91. {
  92. if (_subAllocatorSize != 0)
  93. {
  94. _subAllocatorSize = 0;
  95. //ArrayFactory.BYTES_FACTORY.recycle(heap);
  96. _heap = null;
  97. _heapStart = 1;
  98. // rarfree(HeapStart);
  99. // Free temp fields
  100. _tempRarNode = null;
  101. _tempRarMemBlock1 = null;
  102. _tempRarMemBlock2 = null;
  103. _tempRarMemBlock3 = null;
  104. }
  105. }
  106. public virtual int GetAllocatedMemory()
  107. {
  108. return _subAllocatorSize;
  109. }
  110. public virtual bool StartSubAllocator(int saSize)
  111. {
  112. int t = saSize;
  113. if (_subAllocatorSize == t)
  114. {
  115. return true;
  116. }
  117. StopSubAllocator();
  118. int allocSize = t / FIXED_UNIT_SIZE * UNIT_SIZE + UNIT_SIZE;
  119. // adding space for freelist (needed for poiters)
  120. // 1+ for null pointer
  121. int realAllocSize = 1 + allocSize + 4 * N_INDEXES;
  122. // adding space for an additional memblock
  123. _tempMemBlockPos = realAllocSize;
  124. realAllocSize += RarMemBlock.SIZE;
  125. _heap = new byte[realAllocSize];
  126. _heapStart = 1;
  127. _heapEnd = _heapStart + allocSize - UNIT_SIZE;
  128. _subAllocatorSize = t;
  129. // Bug fixed
  130. _freeListPos = _heapStart + allocSize;
  131. //UPGRADE_ISSUE: The following fragment of code could not be parsed and was not converted. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1156'"
  132. //assert(realAllocSize - tempMemBlockPos == RarMemBlock.size): realAllocSize
  133. //+ + tempMemBlockPos + + RarMemBlock.size;
  134. // Init freeList
  135. for (int i = 0, pos = _freeListPos; i < _freeList.Length; i++, pos += RarNode.SIZE)
  136. {
  137. _freeList[i] = new RarNode(_heap);
  138. _freeList[i].Address = pos;
  139. }
  140. // Init temp fields
  141. _tempRarNode = new RarNode(_heap);
  142. _tempRarMemBlock1 = new RarMemBlock(_heap);
  143. _tempRarMemBlock2 = new RarMemBlock(_heap);
  144. _tempRarMemBlock3 = new RarMemBlock(_heap);
  145. return true;
  146. }
  147. private void GlueFreeBlocks()
  148. {
  149. RarMemBlock s0 = _tempRarMemBlock1;
  150. s0.Address = _tempMemBlockPos;
  151. RarMemBlock p = _tempRarMemBlock2;
  152. RarMemBlock p1 = _tempRarMemBlock3;
  153. int i, k, sz;
  154. if (_loUnit != _hiUnit)
  155. {
  156. _heap[_loUnit] = 0;
  157. }
  158. for (i = 0, s0.SetPrev(s0), s0.SetNext(s0); i < N_INDEXES; i++)
  159. {
  160. while (_freeList[i].GetNext() != 0)
  161. {
  162. p.Address = RemoveNode(i); // =(RAR_MEM_BLK*)RemoveNode(i);
  163. p.InsertAt(s0); // p->insertAt(&s0);
  164. p.Stamp = 0xFFFF; // p->Stamp=0xFFFF;
  165. p.SetNu(_indx2Units[i]); // p->NU=Indx2Units[i];
  166. }
  167. }
  168. for (p.Address = s0.GetNext(); p.Address != s0.Address; p.Address = p.GetNext())
  169. {
  170. // while ((p1=MBPtr(p,p->NU))->Stamp == 0xFFFF && int(p->NU)+p1->NU
  171. // < 0x10000)
  172. // Bug fixed
  173. p1.Address = MbPtr(p.Address, p.GetNu());
  174. while (p1.Stamp == 0xFFFF && p.GetNu() + p1.GetNu() < 0x10000)
  175. {
  176. p1.Remove();
  177. p.SetNu(p.GetNu() + p1.GetNu()); // ->NU += p1->NU;
  178. p1.Address = MbPtr(p.Address, p.GetNu());
  179. }
  180. }
  181. // while ((p=s0.next) != &s0)
  182. // Bug fixed
  183. p.Address = s0.GetNext();
  184. while (p.Address != s0.Address)
  185. {
  186. for (p.Remove(), sz = p.GetNu(); sz > 128; sz -= 128, p.Address = MbPtr(p.Address, 128))
  187. {
  188. InsertNode(p.Address, N_INDEXES - 1);
  189. }
  190. if (_indx2Units[i = _units2Indx[sz - 1]] != sz)
  191. {
  192. k = sz - _indx2Units[--i];
  193. InsertNode(MbPtr(p.Address, sz - k), k - 1);
  194. }
  195. InsertNode(p.Address, i);
  196. p.Address = s0.GetNext();
  197. }
  198. }
  199. private int AllocUnitsRare(int indx)
  200. {
  201. if (_glueCount == 0)
  202. {
  203. _glueCount = 255;
  204. GlueFreeBlocks();
  205. if (_freeList[indx].GetNext() != 0)
  206. {
  207. return RemoveNode(indx);
  208. }
  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 (0);
  225. }
  226. }
  227. while (_freeList[i].GetNext() == 0);
  228. int retVal = RemoveNode(i);
  229. SplitBlock(retVal, i, indx);
  230. return retVal;
  231. }
  232. public virtual int AllocUnits(int nu)
  233. {
  234. int indx = _units2Indx[nu - 1];
  235. if (_freeList[indx].GetNext() != 0)
  236. {
  237. return RemoveNode(indx);
  238. }
  239. int retVal = _loUnit;
  240. _loUnit += U2B(_indx2Units[indx]);
  241. if (_loUnit <= _hiUnit)
  242. {
  243. return retVal;
  244. }
  245. _loUnit -= U2B(_indx2Units[indx]);
  246. return AllocUnitsRare(indx);
  247. }
  248. public virtual int AllocContext()
  249. {
  250. if (_hiUnit != _loUnit)
  251. {
  252. return (_hiUnit -= UNIT_SIZE);
  253. }
  254. if (_freeList[0].GetNext() != 0)
  255. {
  256. return RemoveNode(0);
  257. }
  258. return AllocUnitsRare(0);
  259. }
  260. public virtual int ExpandUnits(int oldPtr, int oldNu)
  261. {
  262. int i0 = _units2Indx[oldNu - 1];
  263. int i1 = _units2Indx[oldNu - 1 + 1];
  264. if (i0 == i1)
  265. {
  266. return oldPtr;
  267. }
  268. int ptr = AllocUnits(oldNu + 1);
  269. if (ptr != 0)
  270. {
  271. // memcpy(ptr,OldPtr,U2B(OldNU));
  272. Array.Copy(_heap, oldPtr, _heap, ptr, U2B(oldNu));
  273. InsertNode(oldPtr, i0);
  274. }
  275. return ptr;
  276. }
  277. public virtual int ShrinkUnits(int oldPtr, int oldNu, int newNu)
  278. {
  279. // System.out.println("SubAllocator.shrinkUnits(" + OldPtr + ", " +
  280. // OldNU + ", " + NewNU + ")");
  281. int i0 = _units2Indx[oldNu - 1];
  282. int i1 = _units2Indx[newNu - 1];
  283. if (i0 == i1)
  284. {
  285. return oldPtr;
  286. }
  287. if (_freeList[i1].GetNext() != 0)
  288. {
  289. int ptr = RemoveNode(i1);
  290. // memcpy(ptr,OldPtr,U2B(NewNU));
  291. // for (int i = 0; i < U2B(NewNU); i++) {
  292. // heap[ptr + i] = heap[OldPtr + i];
  293. // }
  294. Array.Copy(_heap, oldPtr, _heap, ptr, U2B(newNu));
  295. InsertNode(oldPtr, i0);
  296. return ptr;
  297. }
  298. SplitBlock(oldPtr, i0, i1);
  299. return oldPtr;
  300. }
  301. public virtual void FreeUnits(int ptr, int oldNu)
  302. {
  303. InsertNode(ptr, _units2Indx[oldNu - 1]);
  304. }
  305. public virtual void DecPText(int dPText)
  306. {
  307. PText = PText - dPText;
  308. }
  309. public virtual void InitSubAllocator()
  310. {
  311. int i, k;
  312. Utility.Fill(_heap, _freeListPos, _freeListPos + SizeOfFreeList(), (byte)0);
  313. _pText = _heapStart;
  314. int size2 = FIXED_UNIT_SIZE * (_subAllocatorSize / 8 / FIXED_UNIT_SIZE * 7);
  315. int realSize2 = size2 / FIXED_UNIT_SIZE * UNIT_SIZE;
  316. int size1 = _subAllocatorSize - size2;
  317. int realSize1 = size1 / FIXED_UNIT_SIZE * UNIT_SIZE + size1 % FIXED_UNIT_SIZE;
  318. _hiUnit = _heapStart + _subAllocatorSize;
  319. _loUnit = _unitsStart = _heapStart + realSize1;
  320. _fakeUnitsStart = _heapStart + size1;
  321. _hiUnit = _loUnit + realSize2;
  322. for (i = 0, k = 1; i < N1; i++, k += 1)
  323. {
  324. _indx2Units[i] = k & 0xff;
  325. }
  326. for (k++; i < N1 + N2; i++, k += 2)
  327. {
  328. _indx2Units[i] = k & 0xff;
  329. }
  330. for (k++; i < N1 + N2 + N3; i++, k += 3)
  331. {
  332. _indx2Units[i] = k & 0xff;
  333. }
  334. for (k++; i < (N1 + N2 + N3 + N4); i++, k += 4)
  335. {
  336. _indx2Units[i] = k & 0xff;
  337. }
  338. for (_glueCount = 0, k = 0, i = 0; k < 128; k++)
  339. {
  340. i += ((_indx2Units[i] < (k + 1)) ? 1 : 0);
  341. _units2Indx[k] = i & 0xff;
  342. }
  343. }
  344. private int SizeOfFreeList()
  345. {
  346. return _freeList.Length * RarNode.SIZE;
  347. }
  348. // Debug
  349. // public void dumpHeap() {
  350. // File file = new File("P:\\test\\heapdumpj");
  351. // OutputStream out = null;
  352. // try {
  353. // out = new FileOutputStream(file);
  354. // out.write(heap, heapStart, heapEnd - heapStart);
  355. // out.flush();
  356. // System.out.println("Heap dumped to " + file.getAbsolutePath());
  357. // }
  358. // catch (IOException e) {
  359. // e.printStackTrace();
  360. // }
  361. // finally {
  362. // FileUtil.close(out);
  363. // }
  364. // }
  365. // Debug
  366. public override String ToString()
  367. {
  368. StringBuilder buffer = new StringBuilder();
  369. buffer.Append("SubAllocator[");
  370. buffer.Append("\n subAllocatorSize=");
  371. buffer.Append(_subAllocatorSize);
  372. buffer.Append("\n glueCount=");
  373. buffer.Append(_glueCount);
  374. buffer.Append("\n heapStart=");
  375. buffer.Append(_heapStart);
  376. buffer.Append("\n loUnit=");
  377. buffer.Append(_loUnit);
  378. buffer.Append("\n hiUnit=");
  379. buffer.Append(_hiUnit);
  380. buffer.Append("\n pText=");
  381. buffer.Append(_pText);
  382. buffer.Append("\n unitsStart=");
  383. buffer.Append(_unitsStart);
  384. buffer.Append("\n]");
  385. return buffer.ToString();
  386. }
  387. static SubAllocator()
  388. {
  389. UNIT_SIZE = Math.Max(PpmContext.SIZE, RarMemBlock.SIZE);
  390. }
  391. }
  392. }