Allocator.cs 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489
  1. namespace SharpCompress.Compressors.PPMd.I1
  2. {
  3. /// Allocate a single, large array and then provide sections of this array to callers. Callers are provided with
  4. /// instances of <see cref="Pointer"/> (which simply contain a single address value, representing a location
  5. /// in the large array). Callers can then cast <see cref="Pointer"/> to one of the following structures (all
  6. /// of which also simply contain a single address value):
  7. internal class Allocator
  8. {
  9. private const uint UNIT_SIZE = 12;
  10. private const uint LOCAL_OFFSET = 4; // reserve the first four bytes for Pointer.Zero
  11. private const uint NODE_OFFSET = LOCAL_OFFSET + MemoryNode.SIZE; // reserve space for a single memory node
  12. private const uint HEAP_OFFSET = NODE_OFFSET + INDEX_COUNT * MemoryNode.SIZE;
  13. // reserve space for the array of memory nodes
  14. private const uint N1 = 4;
  15. private const uint N2 = 4;
  16. private const uint N3 = 4;
  17. private const uint N4 = (128 + 3 - 1 * N1 - 2 * N2 - 3 * N3) / 4;
  18. private const uint INDEX_COUNT = N1 + N2 + N3 + N4;
  19. private static readonly byte[] INDEX_TO_UNITS;
  20. private static readonly byte[] UNITS_TO_INDEX;
  21. public uint _allocatorSize;
  22. public uint _glueCount;
  23. public Pointer _baseUnit;
  24. public Pointer _lowUnit;
  25. public Pointer _highUnit;
  26. public Pointer _text;
  27. public Pointer _heap;
  28. public MemoryNode[] _memoryNodes;
  29. public byte[] _memory;
  30. /// <summary>
  31. /// Initializes static read-only arrays used by the <see cref="Allocator"/>.
  32. /// </summary>
  33. static Allocator()
  34. {
  35. // Construct the static index to units lookup array. It will contain the following values.
  36. //
  37. // 1 2 3 4 6 8 10 12 15 18 21 24 28 32 36 40 44 48 52 56 60 64 68 72 76 80 84 88 92 96 100 104 108
  38. // 112 116 120 124 128
  39. uint index;
  40. uint unitCount;
  41. INDEX_TO_UNITS = new byte[INDEX_COUNT];
  42. for (index = 0, unitCount = 1; index < N1; index++, unitCount += 1)
  43. {
  44. INDEX_TO_UNITS[index] = (byte)unitCount;
  45. }
  46. for (unitCount++; index < N1 + N2; index++, unitCount += 2)
  47. {
  48. INDEX_TO_UNITS[index] = (byte)unitCount;
  49. }
  50. for (unitCount++; index < N1 + N2 + N3; index++, unitCount += 3)
  51. {
  52. INDEX_TO_UNITS[index] = (byte)unitCount;
  53. }
  54. for (unitCount++; index < N1 + N2 + N3 + N4; index++, unitCount += 4)
  55. {
  56. INDEX_TO_UNITS[index] = (byte)unitCount;
  57. }
  58. // Construct the static units to index lookup array. It will contain the following values.
  59. //
  60. // 00 01 02 03 04 04 05 05 06 06 07 07 08 08 08 09 09 09 10 10 10 11 11 11 12 12 12 12 13 13 13 13
  61. // 14 14 14 14 15 15 15 15 16 16 16 16 17 17 17 17 18 18 18 18 19 19 19 19 20 20 20 20 21 21 21 21
  62. // 22 22 22 22 23 23 23 23 24 24 24 24 25 25 25 25 26 26 26 26 27 27 27 27 28 28 28 28 29 29 29 29
  63. // 30 30 30 30 31 31 31 31 32 32 32 32 33 33 33 33 34 34 34 34 35 35 35 35 36 36 36 36 37 37 37 37
  64. UNITS_TO_INDEX = new byte[128];
  65. for (unitCount = index = 0; unitCount < 128; unitCount++)
  66. {
  67. index += (uint)((INDEX_TO_UNITS[index] < unitCount + 1) ? 1 : 0);
  68. UNITS_TO_INDEX[unitCount] = (byte)index;
  69. }
  70. }
  71. #region Public Methods
  72. public Allocator()
  73. {
  74. _memoryNodes = new MemoryNode[INDEX_COUNT];
  75. }
  76. /// <summary>
  77. /// Initialize or reset the memory allocator (so that the single, large array can be re-used without destroying
  78. /// and re-creating it).
  79. /// </summary>
  80. public void Initialize()
  81. {
  82. for (int index = 0; index < INDEX_COUNT; index++)
  83. {
  84. _memoryNodes[index] = new MemoryNode((uint)(NODE_OFFSET + index * MemoryNode.SIZE), _memory);
  85. _memoryNodes[index].Stamp = 0;
  86. _memoryNodes[index].Next = MemoryNode.ZERO;
  87. _memoryNodes[index].UnitCount = 0;
  88. }
  89. _text = _heap;
  90. uint difference = UNIT_SIZE * (_allocatorSize / 8 / UNIT_SIZE * 7);
  91. _highUnit = _heap + _allocatorSize;
  92. _lowUnit = _highUnit - difference;
  93. _baseUnit = _highUnit - difference;
  94. _glueCount = 0;
  95. }
  96. /// <summary>
  97. /// Start the allocator (create a single, large array of bytes).
  98. /// </summary>
  99. /// <remarks>
  100. /// Note that .NET will create that array on the large object heap (because it is so large).
  101. /// </remarks>
  102. /// <param name="allocatorSize"></param>
  103. public void Start(int allocatorSize)
  104. {
  105. uint size = (uint)allocatorSize;
  106. if (_allocatorSize != size)
  107. {
  108. Stop();
  109. _memory = new byte[HEAP_OFFSET + size]; // the single, large array of bytes
  110. _heap = new Pointer(HEAP_OFFSET, _memory); // reserve bytes in the range 0 .. HeapOffset - 1
  111. _allocatorSize = size;
  112. }
  113. }
  114. /// <summary>
  115. /// Stop the allocator (free the single, large array of bytes). This can safely be called multiple times (without
  116. /// intervening calls to <see cref="Start"/>).
  117. /// </summary>
  118. /// <remarks>
  119. /// Because the array is on the large object heap it may not be freed immediately.
  120. /// </remarks>
  121. public void Stop()
  122. {
  123. if (_allocatorSize != 0)
  124. {
  125. _allocatorSize = 0;
  126. _memory = null;
  127. _heap = Pointer.ZERO;
  128. }
  129. }
  130. /// <summary>
  131. /// Determine how much memory (from the single, large array) is currenly in use.
  132. /// </summary>
  133. /// <returns></returns>
  134. public uint GetMemoryUsed()
  135. {
  136. uint memoryUsed = _allocatorSize - (_highUnit - _lowUnit) - (_baseUnit - _text);
  137. for (uint index = 0; index < INDEX_COUNT; index++)
  138. {
  139. memoryUsed -= UNIT_SIZE * INDEX_TO_UNITS[index] * _memoryNodes[index].Stamp;
  140. }
  141. return memoryUsed;
  142. }
  143. /// <summary>
  144. /// Allocate a given number of units from the single, large array. Each unit is <see cref="UNIT_SIZE"/> bytes
  145. /// in size.
  146. /// </summary>
  147. /// <param name="unitCount"></param>
  148. /// <returns></returns>
  149. public Pointer AllocateUnits(uint unitCount)
  150. {
  151. uint index = UNITS_TO_INDEX[unitCount - 1];
  152. if (_memoryNodes[index].Available)
  153. {
  154. return _memoryNodes[index].Remove();
  155. }
  156. Pointer allocatedBlock = _lowUnit;
  157. _lowUnit += INDEX_TO_UNITS[index] * UNIT_SIZE;
  158. if (_lowUnit <= _highUnit)
  159. {
  160. return allocatedBlock;
  161. }
  162. _lowUnit -= INDEX_TO_UNITS[index] * UNIT_SIZE;
  163. return AllocateUnitsRare(index);
  164. }
  165. /// <summary>
  166. /// Allocate enough space for a PpmContext instance in the single, large array.
  167. /// </summary>
  168. /// <returns></returns>
  169. public Pointer AllocateContext()
  170. {
  171. if (_highUnit != _lowUnit)
  172. {
  173. return (_highUnit -= UNIT_SIZE);
  174. }
  175. if (_memoryNodes[0].Available)
  176. {
  177. return _memoryNodes[0].Remove();
  178. }
  179. return AllocateUnitsRare(0);
  180. }
  181. /// <summary>
  182. /// Increase the size of an existing allocation (represented by a <see cref="Pointer"/>).
  183. /// </summary>
  184. /// <param name="oldPointer"></param>
  185. /// <param name="oldUnitCount"></param>
  186. /// <returns></returns>
  187. public Pointer ExpandUnits(Pointer oldPointer, uint oldUnitCount)
  188. {
  189. uint oldIndex = UNITS_TO_INDEX[oldUnitCount - 1];
  190. uint newIndex = UNITS_TO_INDEX[oldUnitCount];
  191. if (oldIndex == newIndex)
  192. {
  193. return oldPointer;
  194. }
  195. Pointer pointer = AllocateUnits(oldUnitCount + 1);
  196. if (pointer != Pointer.ZERO)
  197. {
  198. CopyUnits(pointer, oldPointer, oldUnitCount);
  199. _memoryNodes[oldIndex].Insert(oldPointer, oldUnitCount);
  200. }
  201. return pointer;
  202. }
  203. /// <summary>
  204. /// Decrease the size of an existing allocation (represented by a <see cref="Pointer"/>).
  205. /// </summary>
  206. /// <param name="oldPointer"></param>
  207. /// <param name="oldUnitCount"></param>
  208. /// <param name="newUnitCount"></param>
  209. /// <returns></returns>
  210. public Pointer ShrinkUnits(Pointer oldPointer, uint oldUnitCount, uint newUnitCount)
  211. {
  212. uint oldIndex = UNITS_TO_INDEX[oldUnitCount - 1];
  213. uint newIndex = UNITS_TO_INDEX[newUnitCount - 1];
  214. if (oldIndex == newIndex)
  215. {
  216. return oldPointer;
  217. }
  218. if (_memoryNodes[newIndex].Available)
  219. {
  220. Pointer pointer = _memoryNodes[newIndex].Remove();
  221. CopyUnits(pointer, oldPointer, newUnitCount);
  222. _memoryNodes[oldIndex].Insert(oldPointer, INDEX_TO_UNITS[oldIndex]);
  223. return pointer;
  224. }
  225. SplitBlock(oldPointer, oldIndex, newIndex);
  226. return oldPointer;
  227. }
  228. /// <summary>
  229. /// Free previously allocated space (the location and amount of space to free must be specified by using
  230. /// a <see cref="Pointer"/> to indicate the location and a number of units to indicate the amount).
  231. /// </summary>
  232. /// <param name="pointer"></param>
  233. /// <param name="unitCount"></param>
  234. public void FreeUnits(Pointer pointer, uint unitCount)
  235. {
  236. uint index = UNITS_TO_INDEX[unitCount - 1];
  237. _memoryNodes[index].Insert(pointer, INDEX_TO_UNITS[index]);
  238. }
  239. public void SpecialFreeUnits(Pointer pointer)
  240. {
  241. if (pointer != _baseUnit)
  242. {
  243. _memoryNodes[0].Insert(pointer, 1);
  244. }
  245. else
  246. {
  247. MemoryNode memoryNode = pointer;
  248. memoryNode.Stamp = uint.MaxValue;
  249. _baseUnit += UNIT_SIZE;
  250. }
  251. }
  252. public Pointer MoveUnitsUp(Pointer oldPointer, uint unitCount)
  253. {
  254. uint index = UNITS_TO_INDEX[unitCount - 1];
  255. if (oldPointer > _baseUnit + 16 * 1024 || oldPointer > _memoryNodes[index].Next)
  256. {
  257. return oldPointer;
  258. }
  259. Pointer pointer = _memoryNodes[index].Remove();
  260. CopyUnits(pointer, oldPointer, unitCount);
  261. unitCount = INDEX_TO_UNITS[index];
  262. if (oldPointer != _baseUnit)
  263. {
  264. _memoryNodes[index].Insert(oldPointer, unitCount);
  265. }
  266. else
  267. {
  268. _baseUnit += unitCount * UNIT_SIZE;
  269. }
  270. return pointer;
  271. }
  272. /// <summary>
  273. /// Expand the space allocated (in the single, large array) for the bytes of the data (ie. the "text") that is
  274. /// being encoded or decoded.
  275. /// </summary>
  276. public void ExpandText()
  277. {
  278. MemoryNode memoryNode;
  279. uint[] counts = new uint[INDEX_COUNT];
  280. while ((memoryNode = _baseUnit).Stamp == uint.MaxValue)
  281. {
  282. _baseUnit = memoryNode + memoryNode.UnitCount;
  283. counts[UNITS_TO_INDEX[memoryNode.UnitCount - 1]]++;
  284. memoryNode.Stamp = 0;
  285. }
  286. for (uint index = 0; index < INDEX_COUNT; index++)
  287. {
  288. for (memoryNode = _memoryNodes[index]; counts[index] != 0; memoryNode = memoryNode.Next)
  289. {
  290. while (memoryNode.Next.Stamp == 0)
  291. {
  292. memoryNode.Unlink();
  293. _memoryNodes[index].Stamp--;
  294. if (--counts[index] == 0)
  295. {
  296. break;
  297. }
  298. }
  299. }
  300. }
  301. }
  302. #endregion
  303. #region Private Methods
  304. private Pointer AllocateUnitsRare(uint index)
  305. {
  306. if (_glueCount == 0)
  307. {
  308. GlueFreeBlocks();
  309. if (_memoryNodes[index].Available)
  310. {
  311. return _memoryNodes[index].Remove();
  312. }
  313. }
  314. uint oldIndex = index;
  315. do
  316. {
  317. if (++oldIndex == INDEX_COUNT)
  318. {
  319. _glueCount--;
  320. oldIndex = INDEX_TO_UNITS[index] * UNIT_SIZE;
  321. return (_baseUnit - _text > oldIndex) ? (_baseUnit -= oldIndex) : Pointer.ZERO;
  322. }
  323. }
  324. while (!_memoryNodes[oldIndex].Available);
  325. Pointer allocatedBlock = _memoryNodes[oldIndex].Remove();
  326. SplitBlock(allocatedBlock, oldIndex, index);
  327. return allocatedBlock;
  328. }
  329. private void SplitBlock(Pointer pointer, uint oldIndex, uint newIndex)
  330. {
  331. uint unitCountDifference = (uint)(INDEX_TO_UNITS[oldIndex] - INDEX_TO_UNITS[newIndex]);
  332. Pointer newPointer = pointer + INDEX_TO_UNITS[newIndex] * UNIT_SIZE;
  333. uint index = UNITS_TO_INDEX[unitCountDifference - 1];
  334. if (INDEX_TO_UNITS[index] != unitCountDifference)
  335. {
  336. uint unitCount = INDEX_TO_UNITS[--index];
  337. _memoryNodes[index].Insert(newPointer, unitCount);
  338. newPointer += unitCount * UNIT_SIZE;
  339. unitCountDifference -= unitCount;
  340. }
  341. _memoryNodes[UNITS_TO_INDEX[unitCountDifference - 1]].Insert(newPointer, unitCountDifference);
  342. }
  343. private void GlueFreeBlocks()
  344. {
  345. MemoryNode memoryNode = new MemoryNode(LOCAL_OFFSET, _memory);
  346. memoryNode.Stamp = 0;
  347. memoryNode.Next = MemoryNode.ZERO;
  348. memoryNode.UnitCount = 0;
  349. MemoryNode memoryNode0;
  350. MemoryNode memoryNode1;
  351. MemoryNode memoryNode2;
  352. if (_lowUnit != _highUnit)
  353. {
  354. _lowUnit[0] = 0;
  355. }
  356. // Find all unused memory nodes.
  357. memoryNode1 = memoryNode;
  358. for (uint index = 0; index < INDEX_COUNT; index++)
  359. {
  360. while (_memoryNodes[index].Available)
  361. {
  362. memoryNode0 = _memoryNodes[index].Remove();
  363. if (memoryNode0.UnitCount != 0)
  364. {
  365. while ((memoryNode2 = memoryNode0 + memoryNode0.UnitCount).Stamp == uint.MaxValue)
  366. {
  367. memoryNode0.UnitCount = memoryNode0.UnitCount + memoryNode2.UnitCount;
  368. memoryNode2.UnitCount = 0;
  369. }
  370. memoryNode1.Link(memoryNode0);
  371. memoryNode1 = memoryNode0;
  372. }
  373. }
  374. }
  375. // Coalesce the memory represented by the unused memory nodes.
  376. while (memoryNode.Available)
  377. {
  378. memoryNode0 = memoryNode.Remove();
  379. uint unitCount = memoryNode0.UnitCount;
  380. if (unitCount != 0)
  381. {
  382. for (; unitCount > 128; unitCount -= 128, memoryNode0 += 128)
  383. {
  384. _memoryNodes[INDEX_COUNT - 1].Insert(memoryNode0, 128);
  385. }
  386. uint index = UNITS_TO_INDEX[unitCount - 1];
  387. if (INDEX_TO_UNITS[index] != unitCount)
  388. {
  389. uint unitCountDifference = unitCount - INDEX_TO_UNITS[--index];
  390. _memoryNodes[unitCountDifference - 1].Insert(memoryNode0 + (unitCount - unitCountDifference),
  391. unitCountDifference);
  392. }
  393. _memoryNodes[index].Insert(memoryNode0, INDEX_TO_UNITS[index]);
  394. }
  395. }
  396. _glueCount = 1 << 13;
  397. }
  398. private void CopyUnits(Pointer target, Pointer source, uint unitCount)
  399. {
  400. do
  401. {
  402. target[0] = source[0];
  403. target[1] = source[1];
  404. target[2] = source[2];
  405. target[3] = source[3];
  406. target[4] = source[4];
  407. target[5] = source[5];
  408. target[6] = source[6];
  409. target[7] = source[7];
  410. target[8] = source[8];
  411. target[9] = source[9];
  412. target[10] = source[10];
  413. target[11] = source[11];
  414. target += UNIT_SIZE;
  415. source += UNIT_SIZE;
  416. }
  417. while (--unitCount != 0);
  418. }
  419. #endregion
  420. }
  421. }