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 (which simply contain a single address value, representing a location /// in the large array). Callers can then cast 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; /// /// Initializes static read-only arrays used by the . /// 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]; } /// /// Initialize or reset the memory allocator (so that the single, large array can be re-used without destroying /// and re-creating it). /// 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; } /// /// Start the allocator (create a single, large array of bytes). /// /// /// Note that .NET will create that array on the large object heap (because it is so large). /// /// 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; } } /// /// Stop the allocator (free the single, large array of bytes). This can safely be called multiple times (without /// intervening calls to ). /// /// /// Because the array is on the large object heap it may not be freed immediately. /// public void Stop() { if (_allocatorSize != 0) { _allocatorSize = 0; _memory = null; _heap = Pointer.ZERO; } } /// /// Determine how much memory (from the single, large array) is currenly in use. /// /// 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; } /// /// Allocate a given number of units from the single, large array. Each unit is bytes /// in size. /// /// /// 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); } /// /// Allocate enough space for a PpmContext instance in the single, large array. /// /// public Pointer AllocateContext() { if (_highUnit != _lowUnit) { return (_highUnit -= UNIT_SIZE); } if (_memoryNodes[0].Available) { return _memoryNodes[0].Remove(); } return AllocateUnitsRare(0); } /// /// Increase the size of an existing allocation (represented by a ). /// /// /// /// 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; } /// /// Decrease the size of an existing allocation (represented by a ). /// /// /// /// /// 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; } /// /// Free previously allocated space (the location and amount of space to free must be specified by using /// a to indicate the location and a number of units to indicate the amount). /// /// /// 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; } /// /// Expand the space allocated (in the single, large array) for the bytes of the data (ie. the "text") that is /// being encoded or decoded. /// 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 } }