123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489 |
- namespace SharpCompress.Compressors.PPMd.I1
- {
- /// Allocate a single, large array and then provide sections of this array to callers. Callers are provided with
- /// instances of <see cref="Pointer"/> (which simply contain a single address value, representing a location
- /// in the large array). Callers can then cast <see cref="Pointer"/> to one of the following structures (all
- /// of which also simply contain a single address value):
- internal class Allocator
- {
- private const uint UNIT_SIZE = 12;
- private const uint LOCAL_OFFSET = 4; // reserve the first four bytes for Pointer.Zero
- private const uint NODE_OFFSET = LOCAL_OFFSET + MemoryNode.SIZE; // reserve space for a single memory node
- private const uint HEAP_OFFSET = NODE_OFFSET + INDEX_COUNT * MemoryNode.SIZE;
- // reserve space for the array of memory nodes
- private const uint N1 = 4;
- private const uint N2 = 4;
- private const uint N3 = 4;
- private const uint N4 = (128 + 3 - 1 * N1 - 2 * N2 - 3 * N3) / 4;
- private const uint INDEX_COUNT = N1 + N2 + N3 + N4;
- private static readonly byte[] INDEX_TO_UNITS;
- private static readonly byte[] UNITS_TO_INDEX;
- public uint _allocatorSize;
- public uint _glueCount;
- public Pointer _baseUnit;
- public Pointer _lowUnit;
- public Pointer _highUnit;
- public Pointer _text;
- public Pointer _heap;
- public MemoryNode[] _memoryNodes;
- public byte[] _memory;
- /// <summary>
- /// Initializes static read-only arrays used by the <see cref="Allocator"/>.
- /// </summary>
- static Allocator()
- {
- // Construct the static index to units lookup array. It will contain the following values.
- //
- // 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
- // 112 116 120 124 128
- uint index;
- uint unitCount;
- INDEX_TO_UNITS = new byte[INDEX_COUNT];
- for (index = 0, unitCount = 1; index < N1; index++, unitCount += 1)
- {
- INDEX_TO_UNITS[index] = (byte)unitCount;
- }
- for (unitCount++; index < N1 + N2; index++, unitCount += 2)
- {
- INDEX_TO_UNITS[index] = (byte)unitCount;
- }
- for (unitCount++; index < N1 + N2 + N3; index++, unitCount += 3)
- {
- INDEX_TO_UNITS[index] = (byte)unitCount;
- }
- for (unitCount++; index < N1 + N2 + N3 + N4; index++, unitCount += 4)
- {
- INDEX_TO_UNITS[index] = (byte)unitCount;
- }
- // Construct the static units to index lookup array. It will contain the following values.
- //
- // 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
- // 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
- // 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
- // 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
- UNITS_TO_INDEX = new byte[128];
- for (unitCount = index = 0; unitCount < 128; unitCount++)
- {
- index += (uint)((INDEX_TO_UNITS[index] < unitCount + 1) ? 1 : 0);
- UNITS_TO_INDEX[unitCount] = (byte)index;
- }
- }
- #region Public Methods
- public Allocator()
- {
- _memoryNodes = new MemoryNode[INDEX_COUNT];
- }
- /// <summary>
- /// Initialize or reset the memory allocator (so that the single, large array can be re-used without destroying
- /// and re-creating it).
- /// </summary>
- public void Initialize()
- {
- for (int index = 0; index < INDEX_COUNT; index++)
- {
- _memoryNodes[index] = new MemoryNode((uint)(NODE_OFFSET + index * MemoryNode.SIZE), _memory);
- _memoryNodes[index].Stamp = 0;
- _memoryNodes[index].Next = MemoryNode.ZERO;
- _memoryNodes[index].UnitCount = 0;
- }
- _text = _heap;
- uint difference = UNIT_SIZE * (_allocatorSize / 8 / UNIT_SIZE * 7);
- _highUnit = _heap + _allocatorSize;
- _lowUnit = _highUnit - difference;
- _baseUnit = _highUnit - difference;
- _glueCount = 0;
- }
- /// <summary>
- /// Start the allocator (create a single, large array of bytes).
- /// </summary>
- /// <remarks>
- /// Note that .NET will create that array on the large object heap (because it is so large).
- /// </remarks>
- /// <param name="allocatorSize"></param>
- public void Start(int allocatorSize)
- {
- uint size = (uint)allocatorSize;
- if (_allocatorSize != size)
- {
- Stop();
- _memory = new byte[HEAP_OFFSET + size]; // the single, large array of bytes
- _heap = new Pointer(HEAP_OFFSET, _memory); // reserve bytes in the range 0 .. HeapOffset - 1
- _allocatorSize = size;
- }
- }
- /// <summary>
- /// Stop the allocator (free the single, large array of bytes). This can safely be called multiple times (without
- /// intervening calls to <see cref="Start"/>).
- /// </summary>
- /// <remarks>
- /// Because the array is on the large object heap it may not be freed immediately.
- /// </remarks>
- public void Stop()
- {
- if (_allocatorSize != 0)
- {
- _allocatorSize = 0;
- _memory = null;
- _heap = Pointer.ZERO;
- }
- }
- /// <summary>
- /// Determine how much memory (from the single, large array) is currenly in use.
- /// </summary>
- /// <returns></returns>
- public uint GetMemoryUsed()
- {
- uint memoryUsed = _allocatorSize - (_highUnit - _lowUnit) - (_baseUnit - _text);
- for (uint index = 0; index < INDEX_COUNT; index++)
- {
- memoryUsed -= UNIT_SIZE * INDEX_TO_UNITS[index] * _memoryNodes[index].Stamp;
- }
- return memoryUsed;
- }
- /// <summary>
- /// Allocate a given number of units from the single, large array. Each unit is <see cref="UNIT_SIZE"/> bytes
- /// in size.
- /// </summary>
- /// <param name="unitCount"></param>
- /// <returns></returns>
- public Pointer AllocateUnits(uint unitCount)
- {
- uint index = UNITS_TO_INDEX[unitCount - 1];
- if (_memoryNodes[index].Available)
- {
- return _memoryNodes[index].Remove();
- }
- Pointer allocatedBlock = _lowUnit;
- _lowUnit += INDEX_TO_UNITS[index] * UNIT_SIZE;
- if (_lowUnit <= _highUnit)
- {
- return allocatedBlock;
- }
- _lowUnit -= INDEX_TO_UNITS[index] * UNIT_SIZE;
- return AllocateUnitsRare(index);
- }
- /// <summary>
- /// Allocate enough space for a PpmContext instance in the single, large array.
- /// </summary>
- /// <returns></returns>
- public Pointer AllocateContext()
- {
- if (_highUnit != _lowUnit)
- {
- return (_highUnit -= UNIT_SIZE);
- }
- if (_memoryNodes[0].Available)
- {
- return _memoryNodes[0].Remove();
- }
- return AllocateUnitsRare(0);
- }
- /// <summary>
- /// Increase the size of an existing allocation (represented by a <see cref="Pointer"/>).
- /// </summary>
- /// <param name="oldPointer"></param>
- /// <param name="oldUnitCount"></param>
- /// <returns></returns>
- public Pointer ExpandUnits(Pointer oldPointer, uint oldUnitCount)
- {
- uint oldIndex = UNITS_TO_INDEX[oldUnitCount - 1];
- uint newIndex = UNITS_TO_INDEX[oldUnitCount];
- if (oldIndex == newIndex)
- {
- return oldPointer;
- }
- Pointer pointer = AllocateUnits(oldUnitCount + 1);
- if (pointer != Pointer.ZERO)
- {
- CopyUnits(pointer, oldPointer, oldUnitCount);
- _memoryNodes[oldIndex].Insert(oldPointer, oldUnitCount);
- }
- return pointer;
- }
- /// <summary>
- /// Decrease the size of an existing allocation (represented by a <see cref="Pointer"/>).
- /// </summary>
- /// <param name="oldPointer"></param>
- /// <param name="oldUnitCount"></param>
- /// <param name="newUnitCount"></param>
- /// <returns></returns>
- public Pointer ShrinkUnits(Pointer oldPointer, uint oldUnitCount, uint newUnitCount)
- {
- uint oldIndex = UNITS_TO_INDEX[oldUnitCount - 1];
- uint newIndex = UNITS_TO_INDEX[newUnitCount - 1];
- if (oldIndex == newIndex)
- {
- return oldPointer;
- }
- if (_memoryNodes[newIndex].Available)
- {
- Pointer pointer = _memoryNodes[newIndex].Remove();
- CopyUnits(pointer, oldPointer, newUnitCount);
- _memoryNodes[oldIndex].Insert(oldPointer, INDEX_TO_UNITS[oldIndex]);
- return pointer;
- }
- SplitBlock(oldPointer, oldIndex, newIndex);
- return oldPointer;
- }
- /// <summary>
- /// Free previously allocated space (the location and amount of space to free must be specified by using
- /// a <see cref="Pointer"/> to indicate the location and a number of units to indicate the amount).
- /// </summary>
- /// <param name="pointer"></param>
- /// <param name="unitCount"></param>
- public void FreeUnits(Pointer pointer, uint unitCount)
- {
- uint index = UNITS_TO_INDEX[unitCount - 1];
- _memoryNodes[index].Insert(pointer, INDEX_TO_UNITS[index]);
- }
- public void SpecialFreeUnits(Pointer pointer)
- {
- if (pointer != _baseUnit)
- {
- _memoryNodes[0].Insert(pointer, 1);
- }
- else
- {
- MemoryNode memoryNode = pointer;
- memoryNode.Stamp = uint.MaxValue;
- _baseUnit += UNIT_SIZE;
- }
- }
- public Pointer MoveUnitsUp(Pointer oldPointer, uint unitCount)
- {
- uint index = UNITS_TO_INDEX[unitCount - 1];
- if (oldPointer > _baseUnit + 16 * 1024 || oldPointer > _memoryNodes[index].Next)
- {
- return oldPointer;
- }
- Pointer pointer = _memoryNodes[index].Remove();
- CopyUnits(pointer, oldPointer, unitCount);
- unitCount = INDEX_TO_UNITS[index];
- if (oldPointer != _baseUnit)
- {
- _memoryNodes[index].Insert(oldPointer, unitCount);
- }
- else
- {
- _baseUnit += unitCount * UNIT_SIZE;
- }
- return pointer;
- }
- /// <summary>
- /// Expand the space allocated (in the single, large array) for the bytes of the data (ie. the "text") that is
- /// being encoded or decoded.
- /// </summary>
- public void ExpandText()
- {
- MemoryNode memoryNode;
- uint[] counts = new uint[INDEX_COUNT];
- while ((memoryNode = _baseUnit).Stamp == uint.MaxValue)
- {
- _baseUnit = memoryNode + memoryNode.UnitCount;
- counts[UNITS_TO_INDEX[memoryNode.UnitCount - 1]]++;
- memoryNode.Stamp = 0;
- }
- for (uint index = 0; index < INDEX_COUNT; index++)
- {
- for (memoryNode = _memoryNodes[index]; counts[index] != 0; memoryNode = memoryNode.Next)
- {
- while (memoryNode.Next.Stamp == 0)
- {
- memoryNode.Unlink();
- _memoryNodes[index].Stamp--;
- if (--counts[index] == 0)
- {
- break;
- }
- }
- }
- }
- }
- #endregion
- #region Private Methods
- private Pointer AllocateUnitsRare(uint index)
- {
- if (_glueCount == 0)
- {
- GlueFreeBlocks();
- if (_memoryNodes[index].Available)
- {
- return _memoryNodes[index].Remove();
- }
- }
- uint oldIndex = index;
- do
- {
- if (++oldIndex == INDEX_COUNT)
- {
- _glueCount--;
- oldIndex = INDEX_TO_UNITS[index] * UNIT_SIZE;
- return (_baseUnit - _text > oldIndex) ? (_baseUnit -= oldIndex) : Pointer.ZERO;
- }
- }
- while (!_memoryNodes[oldIndex].Available);
- Pointer allocatedBlock = _memoryNodes[oldIndex].Remove();
- SplitBlock(allocatedBlock, oldIndex, index);
- return allocatedBlock;
- }
- private void SplitBlock(Pointer pointer, uint oldIndex, uint newIndex)
- {
- uint unitCountDifference = (uint)(INDEX_TO_UNITS[oldIndex] - INDEX_TO_UNITS[newIndex]);
- Pointer newPointer = pointer + INDEX_TO_UNITS[newIndex] * UNIT_SIZE;
- uint index = UNITS_TO_INDEX[unitCountDifference - 1];
- if (INDEX_TO_UNITS[index] != unitCountDifference)
- {
- uint unitCount = INDEX_TO_UNITS[--index];
- _memoryNodes[index].Insert(newPointer, unitCount);
- newPointer += unitCount * UNIT_SIZE;
- unitCountDifference -= unitCount;
- }
- _memoryNodes[UNITS_TO_INDEX[unitCountDifference - 1]].Insert(newPointer, unitCountDifference);
- }
- private void GlueFreeBlocks()
- {
- MemoryNode memoryNode = new MemoryNode(LOCAL_OFFSET, _memory);
- memoryNode.Stamp = 0;
- memoryNode.Next = MemoryNode.ZERO;
- memoryNode.UnitCount = 0;
- MemoryNode memoryNode0;
- MemoryNode memoryNode1;
- MemoryNode memoryNode2;
- if (_lowUnit != _highUnit)
- {
- _lowUnit[0] = 0;
- }
- // Find all unused memory nodes.
- memoryNode1 = memoryNode;
- for (uint index = 0; index < INDEX_COUNT; index++)
- {
- while (_memoryNodes[index].Available)
- {
- memoryNode0 = _memoryNodes[index].Remove();
- if (memoryNode0.UnitCount != 0)
- {
- while ((memoryNode2 = memoryNode0 + memoryNode0.UnitCount).Stamp == uint.MaxValue)
- {
- memoryNode0.UnitCount = memoryNode0.UnitCount + memoryNode2.UnitCount;
- memoryNode2.UnitCount = 0;
- }
- memoryNode1.Link(memoryNode0);
- memoryNode1 = memoryNode0;
- }
- }
- }
- // Coalesce the memory represented by the unused memory nodes.
- while (memoryNode.Available)
- {
- memoryNode0 = memoryNode.Remove();
- uint unitCount = memoryNode0.UnitCount;
- if (unitCount != 0)
- {
- for (; unitCount > 128; unitCount -= 128, memoryNode0 += 128)
- {
- _memoryNodes[INDEX_COUNT - 1].Insert(memoryNode0, 128);
- }
- uint index = UNITS_TO_INDEX[unitCount - 1];
- if (INDEX_TO_UNITS[index] != unitCount)
- {
- uint unitCountDifference = unitCount - INDEX_TO_UNITS[--index];
- _memoryNodes[unitCountDifference - 1].Insert(memoryNode0 + (unitCount - unitCountDifference),
- unitCountDifference);
- }
- _memoryNodes[index].Insert(memoryNode0, INDEX_TO_UNITS[index]);
- }
- }
- _glueCount = 1 << 13;
- }
- private void CopyUnits(Pointer target, Pointer source, uint unitCount)
- {
- do
- {
- target[0] = source[0];
- target[1] = source[1];
- target[2] = source[2];
- target[3] = source[3];
- target[4] = source[4];
- target[5] = source[5];
- target[6] = source[6];
- target[7] = source[7];
- target[8] = source[8];
- target[9] = source[9];
- target[10] = source[10];
- target[11] = source[11];
- target += UNIT_SIZE;
- source += UNIT_SIZE;
- }
- while (--unitCount != 0);
- }
- #endregion
- }
- }
|