123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923 |
- #region Using
- using System;
- using System.IO;
- #endregion
- // This is a port of Dmitry Shkarin's PPMd Variant I Revision 1.
- // Ported by Michael Bone (mjbone03@yahoo.com.au).
- namespace SharpCompress.Compressors.PPMd.I1
- {
- /// <summary>
- /// The model.
- /// </summary>
- internal partial class Model
- {
- public const uint SIGNATURE = 0x84acaf8fU;
- public const char VARIANT = 'I';
- public const int MAXIMUM_ORDER = 16; // maximum allowed model order
- private const byte UPPER_FREQUENCY = 5;
- private const byte INTERVAL_BIT_COUNT = 7;
- private const byte PERIOD_BIT_COUNT = 7;
- private const byte TOTAL_BIT_COUNT = INTERVAL_BIT_COUNT + PERIOD_BIT_COUNT;
- private const uint INTERVAL = 1 << INTERVAL_BIT_COUNT;
- private const uint BINARY_SCALE = 1 << TOTAL_BIT_COUNT;
- private const uint MAXIMUM_FREQUENCY = 124;
- private const uint ORDER_BOUND = 9;
- private readonly See2Context[,] _see2Contexts;
- private readonly See2Context _emptySee2Context;
- private PpmContext _maximumContext;
- private readonly ushort[,] _binarySummary = new ushort[25, 64]; // binary SEE-contexts
- private readonly byte[] _numberStatisticsToBinarySummaryIndex = new byte[256];
- private readonly byte[] _probabilities = new byte[260];
- private readonly byte[] _characterMask = new byte[256];
- private byte _escapeCount;
- private int _modelOrder;
- private int _orderFall;
- private int _initialEscape;
- private int _initialRunLength;
- private int _runLength;
- private byte _previousSuccess;
- private byte _numberMasked;
- private ModelRestorationMethod _method;
- private PpmState _foundState; // found next state transition
- private Allocator _allocator;
- private Coder _coder;
- private PpmContext _minimumContext;
- private byte _numberStatistics;
- private readonly PpmState[] _decodeStates = new PpmState[256];
- private static readonly ushort[] INITIAL_BINARY_ESCAPES =
- {
- 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632,
- 0x6051
- };
- private static readonly byte[] EXPONENTIAL_ESCAPES = {25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2};
- #region Public Methods
- public Model()
- {
- // Construct the conversion table for number statistics. Initially it will contain the following values.
- //
- // 0 2 4 4 4 4 4 4 4 4 4 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
- // 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
- // 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
- // 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
- // 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
- // 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
- // 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
- // 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
- _numberStatisticsToBinarySummaryIndex[0] = 2 * 0;
- _numberStatisticsToBinarySummaryIndex[1] = 2 * 1;
- for (int index = 2; index < 11; index++)
- {
- _numberStatisticsToBinarySummaryIndex[index] = 2 * 2;
- }
- for (int index = 11; index < 256; index++)
- {
- _numberStatisticsToBinarySummaryIndex[index] = 2 * 3;
- }
- // Construct the probability table. Initially it will contain the following values (depending on the value of
- // the upper frequency).
- //
- // 00 01 02 03 04 05 06 06 07 07 07 08 08 08 08 09 09 09 09 09 10 10 10 10 10 10 11 11 11 11 11 11
- // 11 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 15 15 15 15
- // 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17
- // 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20
- // 20 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 22 22
- // 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23
- // 23 23 23 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 25 25
- // 25 25 25 25 25 25 25 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26
- // 26 26 27 27
- uint count = 1;
- uint step = 1;
- uint probability = UPPER_FREQUENCY;
- for (int index = 0; index < UPPER_FREQUENCY; index++)
- {
- _probabilities[index] = (byte)index;
- }
- for (int index = UPPER_FREQUENCY; index < 260; index++)
- {
- _probabilities[index] = (byte)probability;
- count--;
- if (count == 0)
- {
- step++;
- count = step;
- probability++;
- }
- }
- // Create the context array.
- _see2Contexts = new See2Context[24, 32];
- for (int index1 = 0; index1 < 24; index1++)
- {
- for (int index2 = 0; index2 < 32; index2++)
- {
- _see2Contexts[index1, index2] = new See2Context();
- }
- }
- // Set the signature (identifying the algorithm).
- _emptySee2Context = new See2Context();
- _emptySee2Context._summary = (ushort)(SIGNATURE & 0x0000ffff);
- _emptySee2Context._shift = (byte)((SIGNATURE >> 16) & 0x000000ff);
- _emptySee2Context._count = (byte)(SIGNATURE >> 24);
- }
- /// <summary>
- /// Encode (ie. compress) a given source stream, writing the encoded result to the target stream.
- /// </summary>
- public void Encode(Stream target, Stream source, PpmdProperties properties)
- {
- if (target == null)
- {
- throw new ArgumentNullException(nameof(target));
- }
- if (source == null)
- {
- throw new ArgumentNullException(nameof(source));
- }
- EncodeStart(properties);
- EncodeBlock(target, source, true);
- }
- internal Coder EncodeStart(PpmdProperties properties)
- {
- _allocator = properties._allocator;
- _coder = new Coder();
- _coder.RangeEncoderInitialize();
- StartModel(properties.ModelOrder, properties.RestorationMethod);
- return _coder;
- }
- internal void EncodeBlock(Stream target, Stream source, bool final)
- {
- while (true)
- {
- _minimumContext = _maximumContext;
- _numberStatistics = _minimumContext.NumberStatistics;
- int c = source.ReadByte();
- if (c < 0 && !final)
- {
- return;
- }
- if (_numberStatistics != 0)
- {
- EncodeSymbol1(c, _minimumContext);
- _coder.RangeEncodeSymbol();
- }
- else
- {
- EncodeBinarySymbol(c, _minimumContext);
- _coder.RangeShiftEncodeSymbol(TOTAL_BIT_COUNT);
- }
- while (_foundState == PpmState.ZERO)
- {
- _coder.RangeEncoderNormalize(target);
- do
- {
- _orderFall++;
- _minimumContext = _minimumContext.Suffix;
- if (_minimumContext == PpmContext.ZERO)
- {
- goto StopEncoding;
- }
- }
- while (_minimumContext.NumberStatistics == _numberMasked);
- EncodeSymbol2(c, _minimumContext);
- _coder.RangeEncodeSymbol();
- }
- if (_orderFall == 0 && (Pointer)_foundState.Successor >= _allocator._baseUnit)
- {
- _maximumContext = _foundState.Successor;
- }
- else
- {
- UpdateModel(_minimumContext);
- if (_escapeCount == 0)
- {
- ClearMask();
- }
- }
- _coder.RangeEncoderNormalize(target);
- }
- StopEncoding:
- _coder.RangeEncoderFlush(target);
- }
- /// <summary>
- /// Dencode (ie. decompress) a given source stream, writing the decoded result to the target stream.
- /// </summary>
- public void Decode(Stream target, Stream source, PpmdProperties properties)
- {
- if (target == null)
- {
- throw new ArgumentNullException(nameof(target));
- }
- if (source == null)
- {
- throw new ArgumentNullException(nameof(source));
- }
- DecodeStart(source, properties);
- byte[] buffer = new byte[65536];
- int read;
- while ((read = DecodeBlock(source, buffer, 0, buffer.Length)) != 0)
- {
- target.Write(buffer, 0, read);
- }
- }
- internal Coder DecodeStart(Stream source, PpmdProperties properties)
- {
- _allocator = properties._allocator;
- _coder = new Coder();
- _coder.RangeDecoderInitialize(source);
- StartModel(properties.ModelOrder, properties.RestorationMethod);
- _minimumContext = _maximumContext;
- _numberStatistics = _minimumContext.NumberStatistics;
- return _coder;
- }
- internal int DecodeBlock(Stream source, byte[] buffer, int offset, int count)
- {
- if (_minimumContext == PpmContext.ZERO)
- {
- return 0;
- }
- int total = 0;
- while (total < count)
- {
- if (_numberStatistics != 0)
- {
- DecodeSymbol1(_minimumContext);
- }
- else
- {
- DecodeBinarySymbol(_minimumContext);
- }
- _coder.RangeRemoveSubrange();
- while (_foundState == PpmState.ZERO)
- {
- _coder.RangeDecoderNormalize(source);
- do
- {
- _orderFall++;
- _minimumContext = _minimumContext.Suffix;
- if (_minimumContext == PpmContext.ZERO)
- {
- goto StopDecoding;
- }
- }
- while (_minimumContext.NumberStatistics == _numberMasked);
- DecodeSymbol2(_minimumContext);
- _coder.RangeRemoveSubrange();
- }
- buffer[offset] = _foundState.Symbol;
- offset++;
- total++;
- if (_orderFall == 0 && (Pointer)_foundState.Successor >= _allocator._baseUnit)
- {
- _maximumContext = _foundState.Successor;
- }
- else
- {
- UpdateModel(_minimumContext);
- if (_escapeCount == 0)
- {
- ClearMask();
- }
- }
- _minimumContext = _maximumContext;
- _numberStatistics = _minimumContext.NumberStatistics;
- _coder.RangeDecoderNormalize(source);
- }
- StopDecoding:
- return total;
- }
- #endregion
- #region Private Methods
- /// <summary>
- /// Initialise the model (unless the model order is set to 1 in which case the model should be cleared so that
- /// the statistics are carried over, allowing "solid" mode compression).
- /// </summary>
- private void StartModel(int modelOrder, ModelRestorationMethod modelRestorationMethod)
- {
- Array.Clear(_characterMask, 0, _characterMask.Length);
- _escapeCount = 1;
- // Compress in "solid" mode if the model order value is set to 1 (this will examine the current PPM context
- // structures to determine the value of orderFall).
- if (modelOrder < 2)
- {
- _orderFall = _modelOrder;
- for (PpmContext context = _maximumContext; context.Suffix != PpmContext.ZERO; context = context.Suffix)
- {
- _orderFall--;
- }
- return;
- }
- _modelOrder = modelOrder;
- _orderFall = modelOrder;
- _method = modelRestorationMethod;
- _allocator.Initialize();
- _initialRunLength = -((modelOrder < 12) ? modelOrder : 12) - 1;
- _runLength = _initialRunLength;
- // Allocate the context structure.
- _maximumContext = _allocator.AllocateContext();
- _maximumContext.Suffix = PpmContext.ZERO;
- _maximumContext.NumberStatistics = 255;
- _maximumContext.SummaryFrequency = (ushort)(_maximumContext.NumberStatistics + 2);
- _maximumContext.Statistics = _allocator.AllocateUnits(256 / 2);
- // allocates enough space for 256 PPM states (each is 6 bytes)
- _previousSuccess = 0;
- for (int index = 0; index < 256; index++)
- {
- PpmState state = _maximumContext.Statistics[index];
- state.Symbol = (byte)index;
- state.Frequency = 1;
- state.Successor = PpmContext.ZERO;
- }
- uint probability = 0;
- for (int index1 = 0; probability < 25; probability++)
- {
- while (_probabilities[index1] == probability)
- {
- index1++;
- }
- for (int index2 = 0; index2 < 8; index2++)
- {
- _binarySummary[probability, index2] =
- (ushort)(BINARY_SCALE - INITIAL_BINARY_ESCAPES[index2] / (index1 + 1));
- }
- for (int index2 = 8; index2 < 64; index2 += 8)
- {
- for (int index3 = 0; index3 < 8; index3++)
- {
- _binarySummary[probability, index2 + index3] = _binarySummary[probability, index3];
- }
- }
- }
- probability = 0;
- for (uint index1 = 0; probability < 24; probability++)
- {
- while (_probabilities[index1 + 3] == probability + 3)
- {
- index1++;
- }
- for (int index2 = 0; index2 < 32; index2++)
- {
- _see2Contexts[probability, index2].Initialize(2 * index1 + 5);
- }
- }
- }
- private void UpdateModel(PpmContext minimumContext)
- {
- PpmState state = PpmState.ZERO;
- PpmContext successor;
- PpmContext currentContext = _maximumContext;
- uint numberStatistics;
- uint ns1;
- uint cf;
- uint sf;
- uint s0;
- uint foundStateFrequency = _foundState.Frequency;
- byte foundStateSymbol = _foundState.Symbol;
- byte symbol;
- byte flag;
- PpmContext foundStateSuccessor = _foundState.Successor;
- PpmContext context = minimumContext.Suffix;
- if ((foundStateFrequency < MAXIMUM_FREQUENCY / 4) && (context != PpmContext.ZERO))
- {
- if (context.NumberStatistics != 0)
- {
- state = context.Statistics;
- if (state.Symbol != foundStateSymbol)
- {
- do
- {
- symbol = state[1].Symbol;
- state++;
- }
- while (symbol != foundStateSymbol);
- if (state[0].Frequency >= state[-1].Frequency)
- {
- Swap(state[0], state[-1]);
- state--;
- }
- }
- cf = (uint)((state.Frequency < MAXIMUM_FREQUENCY - 9) ? 2 : 0);
- state.Frequency += (byte)cf;
- context.SummaryFrequency += (byte)cf;
- }
- else
- {
- state = context.FirstState;
- state.Frequency += (byte)((state.Frequency < 32) ? 1 : 0);
- }
- }
- if (_orderFall == 0 && foundStateSuccessor != PpmContext.ZERO)
- {
- _foundState.Successor = CreateSuccessors(true, state, minimumContext);
- if (_foundState.Successor == PpmContext.ZERO)
- {
- goto RestartModel;
- }
- _maximumContext = _foundState.Successor;
- return;
- }
- _allocator._text[0] = foundStateSymbol;
- _allocator._text++;
- successor = _allocator._text;
- if (_allocator._text >= _allocator._baseUnit)
- {
- goto RestartModel;
- }
- if (foundStateSuccessor != PpmContext.ZERO)
- {
- if (foundStateSuccessor < _allocator._baseUnit)
- {
- foundStateSuccessor = CreateSuccessors(false, state, minimumContext);
- }
- }
- else
- {
- foundStateSuccessor = ReduceOrder(state, minimumContext);
- }
- if (foundStateSuccessor == PpmContext.ZERO)
- {
- goto RestartModel;
- }
- if (--_orderFall == 0)
- {
- successor = foundStateSuccessor;
- _allocator._text -= (_maximumContext != minimumContext) ? 1 : 0;
- }
- else if (_method > ModelRestorationMethod.Freeze)
- {
- successor = foundStateSuccessor;
- _allocator._text = _allocator._heap;
- _orderFall = 0;
- }
- numberStatistics = minimumContext.NumberStatistics;
- s0 = minimumContext.SummaryFrequency - numberStatistics - foundStateFrequency;
- flag = (byte)((foundStateSymbol >= 0x40) ? 0x08 : 0x00);
- for (; currentContext != minimumContext; currentContext = currentContext.Suffix)
- {
- ns1 = currentContext.NumberStatistics;
- if (ns1 != 0)
- {
- if ((ns1 & 1) != 0)
- {
- state = _allocator.ExpandUnits(currentContext.Statistics, (ns1 + 1) >> 1);
- if (state == PpmState.ZERO)
- {
- goto RestartModel;
- }
- currentContext.Statistics = state;
- }
- currentContext.SummaryFrequency += (ushort)((3 * ns1 + 1 < numberStatistics) ? 1 : 0);
- }
- else
- {
- state = _allocator.AllocateUnits(1);
- if (state == PpmState.ZERO)
- {
- goto RestartModel;
- }
- Copy(state, currentContext.FirstState);
- currentContext.Statistics = state;
- if (state.Frequency < MAXIMUM_FREQUENCY / 4 - 1)
- {
- state.Frequency += state.Frequency;
- }
- else
- {
- state.Frequency = (byte)(MAXIMUM_FREQUENCY - 4);
- }
- currentContext.SummaryFrequency =
- (ushort)(state.Frequency + _initialEscape + ((numberStatistics > 2) ? 1 : 0));
- }
- cf = (uint)(2 * foundStateFrequency * (currentContext.SummaryFrequency + 6));
- sf = s0 + currentContext.SummaryFrequency;
- if (cf < 6 * sf)
- {
- cf = (uint)(1 + ((cf > sf) ? 1 : 0) + ((cf >= 4 * sf) ? 1 : 0));
- currentContext.SummaryFrequency += 4;
- }
- else
- {
- cf = (uint)(4 + ((cf > 9 * sf) ? 1 : 0) + ((cf > 12 * sf) ? 1 : 0) + ((cf > 15 * sf) ? 1 : 0));
- currentContext.SummaryFrequency += (ushort)cf;
- }
- state = currentContext.Statistics + (++currentContext.NumberStatistics);
- state.Successor = successor;
- state.Symbol = foundStateSymbol;
- state.Frequency = (byte)cf;
- currentContext.Flags |= flag;
- }
- _maximumContext = foundStateSuccessor;
- return;
- RestartModel:
- RestoreModel(currentContext, minimumContext, foundStateSuccessor);
- }
- private PpmContext CreateSuccessors(bool skip, PpmState state, PpmContext context)
- {
- PpmContext upBranch = _foundState.Successor;
- PpmState[] states = new PpmState[MAXIMUM_ORDER];
- uint stateIndex = 0;
- byte symbol = _foundState.Symbol;
- if (!skip)
- {
- states[stateIndex++] = _foundState;
- if (context.Suffix == PpmContext.ZERO)
- {
- goto NoLoop;
- }
- }
- bool gotoLoopEntry = false;
- if (state != PpmState.ZERO)
- {
- context = context.Suffix;
- gotoLoopEntry = true;
- }
- do
- {
- if (gotoLoopEntry)
- {
- gotoLoopEntry = false;
- goto LoopEntry;
- }
- context = context.Suffix;
- if (context.NumberStatistics != 0)
- {
- byte temporary;
- state = context.Statistics;
- if (state.Symbol != symbol)
- {
- do
- {
- temporary = state[1].Symbol;
- state++;
- }
- while (temporary != symbol);
- }
- temporary = (byte)((state.Frequency < MAXIMUM_FREQUENCY - 9) ? 1 : 0);
- state.Frequency += temporary;
- context.SummaryFrequency += temporary;
- }
- else
- {
- state = context.FirstState;
- state.Frequency +=
- (byte)(((context.Suffix.NumberStatistics == 0) ? 1 : 0) & ((state.Frequency < 24) ? 1 : 0));
- }
- LoopEntry:
- if (state.Successor != upBranch)
- {
- context = state.Successor;
- break;
- }
- states[stateIndex++] = state;
- }
- while (context.Suffix != PpmContext.ZERO);
- NoLoop:
- if (stateIndex == 0)
- {
- return context;
- }
- byte localNumberStatistics = 0;
- byte localFlags = (byte)((symbol >= 0x40) ? 0x10 : 0x00);
- symbol = upBranch.NumberStatistics;
- byte localSymbol = symbol;
- byte localFrequency;
- PpmContext localSuccessor = ((Pointer)upBranch) + 1;
- localFlags |= (byte)((symbol >= 0x40) ? 0x08 : 0x00);
- if (context.NumberStatistics != 0)
- {
- state = context.Statistics;
- if (state.Symbol != symbol)
- {
- byte temporary;
- do
- {
- temporary = state[1].Symbol;
- state++;
- }
- while (temporary != symbol);
- }
- uint cf = (uint)(state.Frequency - 1);
- uint s0 = (uint)(context.SummaryFrequency - context.NumberStatistics - cf);
- localFrequency = (byte)(1 + ((2 * cf <= s0) ? (uint)((5 * cf > s0) ? 1 : 0) : ((cf + 2 * s0 - 3) / s0)));
- }
- else
- {
- localFrequency = context.FirstStateFrequency;
- }
- do
- {
- PpmContext currentContext = _allocator.AllocateContext();
- if (currentContext == PpmContext.ZERO)
- {
- return PpmContext.ZERO;
- }
- currentContext.NumberStatistics = localNumberStatistics;
- currentContext.Flags = localFlags;
- currentContext.FirstStateSymbol = localSymbol;
- currentContext.FirstStateFrequency = localFrequency;
- currentContext.FirstStateSuccessor = localSuccessor;
- currentContext.Suffix = context;
- context = currentContext;
- states[--stateIndex].Successor = context;
- }
- while (stateIndex != 0);
- return context;
- }
- private PpmContext ReduceOrder(PpmState state, PpmContext context)
- {
- PpmState currentState;
- PpmState[] states = new PpmState[MAXIMUM_ORDER];
- uint stateIndex = 0;
- PpmContext currentContext = context;
- PpmContext upBranch = _allocator._text;
- byte temporary;
- byte symbol = _foundState.Symbol;
- states[stateIndex++] = _foundState;
- _foundState.Successor = upBranch;
- _orderFall++;
- bool gotoLoopEntry = false;
- if (state != PpmState.ZERO)
- {
- context = context.Suffix;
- gotoLoopEntry = true;
- }
- while (true)
- {
- if (gotoLoopEntry)
- {
- gotoLoopEntry = false;
- goto LoopEntry;
- }
- if (context.Suffix == PpmContext.ZERO)
- {
- if (_method > ModelRestorationMethod.Freeze)
- {
- do
- {
- states[--stateIndex].Successor = context;
- }
- while (stateIndex != 0);
- _allocator._text = _allocator._heap + 1;
- _orderFall = 1;
- }
- return context;
- }
- context = context.Suffix;
- if (context.NumberStatistics != 0)
- {
- state = context.Statistics;
- if (state.Symbol != symbol)
- {
- do
- {
- temporary = state[1].Symbol;
- state++;
- }
- while (temporary != symbol);
- }
- temporary = (byte)((state.Frequency < MAXIMUM_FREQUENCY - 9) ? 2 : 0);
- state.Frequency += temporary;
- context.SummaryFrequency += temporary;
- }
- else
- {
- state = context.FirstState;
- state.Frequency += (byte)((state.Frequency < 32) ? 1 : 0);
- }
- LoopEntry:
- if (state.Successor != PpmContext.ZERO)
- {
- break;
- }
- states[stateIndex++] = state;
- state.Successor = upBranch;
- _orderFall++;
- }
- if (_method > ModelRestorationMethod.Freeze)
- {
- context = state.Successor;
- do
- {
- states[--stateIndex].Successor = context;
- }
- while (stateIndex != 0);
- _allocator._text = _allocator._heap + 1;
- _orderFall = 1;
- return context;
- }
- if (state.Successor <= upBranch)
- {
- currentState = _foundState;
- _foundState = state;
- state.Successor = CreateSuccessors(false, PpmState.ZERO, context);
- _foundState = currentState;
- }
- if (_orderFall == 1 && currentContext == _maximumContext)
- {
- _foundState.Successor = state.Successor;
- _allocator._text--;
- }
- return state.Successor;
- }
- private void RestoreModel(PpmContext context, PpmContext minimumContext, PpmContext foundStateSuccessor)
- {
- PpmContext currentContext;
- _allocator._text = _allocator._heap;
- for (currentContext = _maximumContext; currentContext != context; currentContext = currentContext.Suffix)
- {
- if (--currentContext.NumberStatistics == 0)
- {
- currentContext.Flags =
- (byte)
- ((currentContext.Flags & 0x10) + ((currentContext.Statistics.Symbol >= 0x40) ? 0x08 : 0x00));
- PpmState state = currentContext.Statistics;
- Copy(currentContext.FirstState, state);
- _allocator.SpecialFreeUnits(state);
- currentContext.FirstStateFrequency = (byte)((currentContext.FirstStateFrequency + 11) >> 3);
- }
- else
- {
- Refresh((uint)((currentContext.NumberStatistics + 3) >> 1), false, currentContext);
- }
- }
- for (; currentContext != minimumContext; currentContext = currentContext.Suffix)
- {
- if (currentContext.NumberStatistics == 0)
- {
- currentContext.FirstStateFrequency -= (byte)(currentContext.FirstStateFrequency >> 1);
- }
- else if ((currentContext.SummaryFrequency += 4) > 128 + 4 * currentContext.NumberStatistics)
- {
- Refresh((uint)((currentContext.NumberStatistics + 2) >> 1), true, currentContext);
- }
- }
- if (_method > ModelRestorationMethod.Freeze)
- {
- _maximumContext = foundStateSuccessor;
- _allocator._glueCount += (uint)(((_allocator._memoryNodes[1].Stamp & 1) == 0) ? 1 : 0);
- }
- else if (_method == ModelRestorationMethod.Freeze)
- {
- while (_maximumContext.Suffix != PpmContext.ZERO)
- {
- _maximumContext = _maximumContext.Suffix;
- }
- RemoveBinaryContexts(0, _maximumContext);
- _method = _method + 1;
- _allocator._glueCount = 0;
- _orderFall = _modelOrder;
- }
- else if (_method == ModelRestorationMethod.Restart ||
- _allocator.GetMemoryUsed() < (_allocator._allocatorSize >> 1))
- {
- StartModel(_modelOrder, _method);
- _escapeCount = 0;
- }
- else
- {
- while (_maximumContext.Suffix != PpmContext.ZERO)
- {
- _maximumContext = _maximumContext.Suffix;
- }
- do
- {
- CutOff(0, _maximumContext);
- _allocator.ExpandText();
- }
- while (_allocator.GetMemoryUsed() > 3 * (_allocator._allocatorSize >> 2));
- _allocator._glueCount = 0;
- _orderFall = _modelOrder;
- }
- }
- private static void Swap(PpmState state1, PpmState state2)
- {
- byte swapSymbol = state1.Symbol;
- byte swapFrequency = state1.Frequency;
- PpmContext swapSuccessor = state1.Successor;
- state1.Symbol = state2.Symbol;
- state1.Frequency = state2.Frequency;
- state1.Successor = state2.Successor;
- state2.Symbol = swapSymbol;
- state2.Frequency = swapFrequency;
- state2.Successor = swapSuccessor;
- }
- private static void Copy(PpmState state1, PpmState state2)
- {
- state1.Symbol = state2.Symbol;
- state1.Frequency = state2.Frequency;
- state1.Successor = state2.Successor;
- }
- private static int Mean(int sum, int shift, int round)
- {
- return (sum + (1 << (shift - round))) >> shift;
- }
- private void ClearMask()
- {
- _escapeCount = 1;
- Array.Clear(_characterMask, 0, _characterMask.Length);
- }
- #endregion
- }
- }
|