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