Model.cs 33 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923
  1. #region Using
  2. using System;
  3. using System.IO;
  4. #endregion
  5. // This is a port of Dmitry Shkarin's PPMd Variant I Revision 1.
  6. // Ported by Michael Bone (mjbone03@yahoo.com.au).
  7. namespace SharpCompress.Compressors.PPMd.I1
  8. {
  9. /// <summary>
  10. /// The model.
  11. /// </summary>
  12. internal partial class Model
  13. {
  14. public const uint SIGNATURE = 0x84acaf8fU;
  15. public const char VARIANT = 'I';
  16. public const int MAXIMUM_ORDER = 16; // maximum allowed model order
  17. private const byte UPPER_FREQUENCY = 5;
  18. private const byte INTERVAL_BIT_COUNT = 7;
  19. private const byte PERIOD_BIT_COUNT = 7;
  20. private const byte TOTAL_BIT_COUNT = INTERVAL_BIT_COUNT + PERIOD_BIT_COUNT;
  21. private const uint INTERVAL = 1 << INTERVAL_BIT_COUNT;
  22. private const uint BINARY_SCALE = 1 << TOTAL_BIT_COUNT;
  23. private const uint MAXIMUM_FREQUENCY = 124;
  24. private const uint ORDER_BOUND = 9;
  25. private readonly See2Context[,] _see2Contexts;
  26. private readonly See2Context _emptySee2Context;
  27. private PpmContext _maximumContext;
  28. private readonly ushort[,] _binarySummary = new ushort[25, 64]; // binary SEE-contexts
  29. private readonly byte[] _numberStatisticsToBinarySummaryIndex = new byte[256];
  30. private readonly byte[] _probabilities = new byte[260];
  31. private readonly byte[] _characterMask = new byte[256];
  32. private byte _escapeCount;
  33. private int _modelOrder;
  34. private int _orderFall;
  35. private int _initialEscape;
  36. private int _initialRunLength;
  37. private int _runLength;
  38. private byte _previousSuccess;
  39. private byte _numberMasked;
  40. private ModelRestorationMethod _method;
  41. private PpmState _foundState; // found next state transition
  42. private Allocator _allocator;
  43. private Coder _coder;
  44. private PpmContext _minimumContext;
  45. private byte _numberStatistics;
  46. private readonly PpmState[] _decodeStates = new PpmState[256];
  47. private static readonly ushort[] INITIAL_BINARY_ESCAPES =
  48. {
  49. 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632,
  50. 0x6051
  51. };
  52. private static readonly byte[] EXPONENTIAL_ESCAPES = {25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2};
  53. #region Public Methods
  54. public Model()
  55. {
  56. // Construct the conversion table for number statistics. Initially it will contain the following values.
  57. //
  58. // 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
  59. // 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
  60. // 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
  61. // 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
  62. // 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
  63. // 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
  64. // 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
  65. // 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
  66. _numberStatisticsToBinarySummaryIndex[0] = 2 * 0;
  67. _numberStatisticsToBinarySummaryIndex[1] = 2 * 1;
  68. for (int index = 2; index < 11; index++)
  69. {
  70. _numberStatisticsToBinarySummaryIndex[index] = 2 * 2;
  71. }
  72. for (int index = 11; index < 256; index++)
  73. {
  74. _numberStatisticsToBinarySummaryIndex[index] = 2 * 3;
  75. }
  76. // Construct the probability table. Initially it will contain the following values (depending on the value of
  77. // the upper frequency).
  78. //
  79. // 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
  80. // 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
  81. // 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
  82. // 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
  83. // 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
  84. // 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
  85. // 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
  86. // 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
  87. // 26 26 27 27
  88. uint count = 1;
  89. uint step = 1;
  90. uint probability = UPPER_FREQUENCY;
  91. for (int index = 0; index < UPPER_FREQUENCY; index++)
  92. {
  93. _probabilities[index] = (byte)index;
  94. }
  95. for (int index = UPPER_FREQUENCY; index < 260; index++)
  96. {
  97. _probabilities[index] = (byte)probability;
  98. count--;
  99. if (count == 0)
  100. {
  101. step++;
  102. count = step;
  103. probability++;
  104. }
  105. }
  106. // Create the context array.
  107. _see2Contexts = new See2Context[24, 32];
  108. for (int index1 = 0; index1 < 24; index1++)
  109. {
  110. for (int index2 = 0; index2 < 32; index2++)
  111. {
  112. _see2Contexts[index1, index2] = new See2Context();
  113. }
  114. }
  115. // Set the signature (identifying the algorithm).
  116. _emptySee2Context = new See2Context();
  117. _emptySee2Context._summary = (ushort)(SIGNATURE & 0x0000ffff);
  118. _emptySee2Context._shift = (byte)((SIGNATURE >> 16) & 0x000000ff);
  119. _emptySee2Context._count = (byte)(SIGNATURE >> 24);
  120. }
  121. /// <summary>
  122. /// Encode (ie. compress) a given source stream, writing the encoded result to the target stream.
  123. /// </summary>
  124. public void Encode(Stream target, Stream source, PpmdProperties properties)
  125. {
  126. if (target == null)
  127. {
  128. throw new ArgumentNullException(nameof(target));
  129. }
  130. if (source == null)
  131. {
  132. throw new ArgumentNullException(nameof(source));
  133. }
  134. EncodeStart(properties);
  135. EncodeBlock(target, source, true);
  136. }
  137. internal Coder EncodeStart(PpmdProperties properties)
  138. {
  139. _allocator = properties._allocator;
  140. _coder = new Coder();
  141. _coder.RangeEncoderInitialize();
  142. StartModel(properties.ModelOrder, properties.RestorationMethod);
  143. return _coder;
  144. }
  145. internal void EncodeBlock(Stream target, Stream source, bool final)
  146. {
  147. while (true)
  148. {
  149. _minimumContext = _maximumContext;
  150. _numberStatistics = _minimumContext.NumberStatistics;
  151. int c = source.ReadByte();
  152. if (c < 0 && !final)
  153. {
  154. return;
  155. }
  156. if (_numberStatistics != 0)
  157. {
  158. EncodeSymbol1(c, _minimumContext);
  159. _coder.RangeEncodeSymbol();
  160. }
  161. else
  162. {
  163. EncodeBinarySymbol(c, _minimumContext);
  164. _coder.RangeShiftEncodeSymbol(TOTAL_BIT_COUNT);
  165. }
  166. while (_foundState == PpmState.ZERO)
  167. {
  168. _coder.RangeEncoderNormalize(target);
  169. do
  170. {
  171. _orderFall++;
  172. _minimumContext = _minimumContext.Suffix;
  173. if (_minimumContext == PpmContext.ZERO)
  174. {
  175. goto StopEncoding;
  176. }
  177. }
  178. while (_minimumContext.NumberStatistics == _numberMasked);
  179. EncodeSymbol2(c, _minimumContext);
  180. _coder.RangeEncodeSymbol();
  181. }
  182. if (_orderFall == 0 && (Pointer)_foundState.Successor >= _allocator._baseUnit)
  183. {
  184. _maximumContext = _foundState.Successor;
  185. }
  186. else
  187. {
  188. UpdateModel(_minimumContext);
  189. if (_escapeCount == 0)
  190. {
  191. ClearMask();
  192. }
  193. }
  194. _coder.RangeEncoderNormalize(target);
  195. }
  196. StopEncoding:
  197. _coder.RangeEncoderFlush(target);
  198. }
  199. /// <summary>
  200. /// Dencode (ie. decompress) a given source stream, writing the decoded result to the target stream.
  201. /// </summary>
  202. public void Decode(Stream target, Stream source, PpmdProperties properties)
  203. {
  204. if (target == null)
  205. {
  206. throw new ArgumentNullException(nameof(target));
  207. }
  208. if (source == null)
  209. {
  210. throw new ArgumentNullException(nameof(source));
  211. }
  212. DecodeStart(source, properties);
  213. byte[] buffer = new byte[65536];
  214. int read;
  215. while ((read = DecodeBlock(source, buffer, 0, buffer.Length)) != 0)
  216. {
  217. target.Write(buffer, 0, read);
  218. }
  219. }
  220. internal Coder DecodeStart(Stream source, PpmdProperties properties)
  221. {
  222. _allocator = properties._allocator;
  223. _coder = new Coder();
  224. _coder.RangeDecoderInitialize(source);
  225. StartModel(properties.ModelOrder, properties.RestorationMethod);
  226. _minimumContext = _maximumContext;
  227. _numberStatistics = _minimumContext.NumberStatistics;
  228. return _coder;
  229. }
  230. internal int DecodeBlock(Stream source, byte[] buffer, int offset, int count)
  231. {
  232. if (_minimumContext == PpmContext.ZERO)
  233. {
  234. return 0;
  235. }
  236. int total = 0;
  237. while (total < count)
  238. {
  239. if (_numberStatistics != 0)
  240. {
  241. DecodeSymbol1(_minimumContext);
  242. }
  243. else
  244. {
  245. DecodeBinarySymbol(_minimumContext);
  246. }
  247. _coder.RangeRemoveSubrange();
  248. while (_foundState == PpmState.ZERO)
  249. {
  250. _coder.RangeDecoderNormalize(source);
  251. do
  252. {
  253. _orderFall++;
  254. _minimumContext = _minimumContext.Suffix;
  255. if (_minimumContext == PpmContext.ZERO)
  256. {
  257. goto StopDecoding;
  258. }
  259. }
  260. while (_minimumContext.NumberStatistics == _numberMasked);
  261. DecodeSymbol2(_minimumContext);
  262. _coder.RangeRemoveSubrange();
  263. }
  264. buffer[offset] = _foundState.Symbol;
  265. offset++;
  266. total++;
  267. if (_orderFall == 0 && (Pointer)_foundState.Successor >= _allocator._baseUnit)
  268. {
  269. _maximumContext = _foundState.Successor;
  270. }
  271. else
  272. {
  273. UpdateModel(_minimumContext);
  274. if (_escapeCount == 0)
  275. {
  276. ClearMask();
  277. }
  278. }
  279. _minimumContext = _maximumContext;
  280. _numberStatistics = _minimumContext.NumberStatistics;
  281. _coder.RangeDecoderNormalize(source);
  282. }
  283. StopDecoding:
  284. return total;
  285. }
  286. #endregion
  287. #region Private Methods
  288. /// <summary>
  289. /// Initialise the model (unless the model order is set to 1 in which case the model should be cleared so that
  290. /// the statistics are carried over, allowing "solid" mode compression).
  291. /// </summary>
  292. private void StartModel(int modelOrder, ModelRestorationMethod modelRestorationMethod)
  293. {
  294. Array.Clear(_characterMask, 0, _characterMask.Length);
  295. _escapeCount = 1;
  296. // Compress in "solid" mode if the model order value is set to 1 (this will examine the current PPM context
  297. // structures to determine the value of orderFall).
  298. if (modelOrder < 2)
  299. {
  300. _orderFall = _modelOrder;
  301. for (PpmContext context = _maximumContext; context.Suffix != PpmContext.ZERO; context = context.Suffix)
  302. {
  303. _orderFall--;
  304. }
  305. return;
  306. }
  307. _modelOrder = modelOrder;
  308. _orderFall = modelOrder;
  309. _method = modelRestorationMethod;
  310. _allocator.Initialize();
  311. _initialRunLength = -((modelOrder < 12) ? modelOrder : 12) - 1;
  312. _runLength = _initialRunLength;
  313. // Allocate the context structure.
  314. _maximumContext = _allocator.AllocateContext();
  315. _maximumContext.Suffix = PpmContext.ZERO;
  316. _maximumContext.NumberStatistics = 255;
  317. _maximumContext.SummaryFrequency = (ushort)(_maximumContext.NumberStatistics + 2);
  318. _maximumContext.Statistics = _allocator.AllocateUnits(256 / 2);
  319. // allocates enough space for 256 PPM states (each is 6 bytes)
  320. _previousSuccess = 0;
  321. for (int index = 0; index < 256; index++)
  322. {
  323. PpmState state = _maximumContext.Statistics[index];
  324. state.Symbol = (byte)index;
  325. state.Frequency = 1;
  326. state.Successor = PpmContext.ZERO;
  327. }
  328. uint probability = 0;
  329. for (int index1 = 0; probability < 25; probability++)
  330. {
  331. while (_probabilities[index1] == probability)
  332. {
  333. index1++;
  334. }
  335. for (int index2 = 0; index2 < 8; index2++)
  336. {
  337. _binarySummary[probability, index2] =
  338. (ushort)(BINARY_SCALE - INITIAL_BINARY_ESCAPES[index2] / (index1 + 1));
  339. }
  340. for (int index2 = 8; index2 < 64; index2 += 8)
  341. {
  342. for (int index3 = 0; index3 < 8; index3++)
  343. {
  344. _binarySummary[probability, index2 + index3] = _binarySummary[probability, index3];
  345. }
  346. }
  347. }
  348. probability = 0;
  349. for (uint index1 = 0; probability < 24; probability++)
  350. {
  351. while (_probabilities[index1 + 3] == probability + 3)
  352. {
  353. index1++;
  354. }
  355. for (int index2 = 0; index2 < 32; index2++)
  356. {
  357. _see2Contexts[probability, index2].Initialize(2 * index1 + 5);
  358. }
  359. }
  360. }
  361. private void UpdateModel(PpmContext minimumContext)
  362. {
  363. PpmState state = PpmState.ZERO;
  364. PpmContext successor;
  365. PpmContext currentContext = _maximumContext;
  366. uint numberStatistics;
  367. uint ns1;
  368. uint cf;
  369. uint sf;
  370. uint s0;
  371. uint foundStateFrequency = _foundState.Frequency;
  372. byte foundStateSymbol = _foundState.Symbol;
  373. byte symbol;
  374. byte flag;
  375. PpmContext foundStateSuccessor = _foundState.Successor;
  376. PpmContext context = minimumContext.Suffix;
  377. if ((foundStateFrequency < MAXIMUM_FREQUENCY / 4) && (context != PpmContext.ZERO))
  378. {
  379. if (context.NumberStatistics != 0)
  380. {
  381. state = context.Statistics;
  382. if (state.Symbol != foundStateSymbol)
  383. {
  384. do
  385. {
  386. symbol = state[1].Symbol;
  387. state++;
  388. }
  389. while (symbol != foundStateSymbol);
  390. if (state[0].Frequency >= state[-1].Frequency)
  391. {
  392. Swap(state[0], state[-1]);
  393. state--;
  394. }
  395. }
  396. cf = (uint)((state.Frequency < MAXIMUM_FREQUENCY - 9) ? 2 : 0);
  397. state.Frequency += (byte)cf;
  398. context.SummaryFrequency += (byte)cf;
  399. }
  400. else
  401. {
  402. state = context.FirstState;
  403. state.Frequency += (byte)((state.Frequency < 32) ? 1 : 0);
  404. }
  405. }
  406. if (_orderFall == 0 && foundStateSuccessor != PpmContext.ZERO)
  407. {
  408. _foundState.Successor = CreateSuccessors(true, state, minimumContext);
  409. if (_foundState.Successor == PpmContext.ZERO)
  410. {
  411. goto RestartModel;
  412. }
  413. _maximumContext = _foundState.Successor;
  414. return;
  415. }
  416. _allocator._text[0] = foundStateSymbol;
  417. _allocator._text++;
  418. successor = _allocator._text;
  419. if (_allocator._text >= _allocator._baseUnit)
  420. {
  421. goto RestartModel;
  422. }
  423. if (foundStateSuccessor != PpmContext.ZERO)
  424. {
  425. if (foundStateSuccessor < _allocator._baseUnit)
  426. {
  427. foundStateSuccessor = CreateSuccessors(false, state, minimumContext);
  428. }
  429. }
  430. else
  431. {
  432. foundStateSuccessor = ReduceOrder(state, minimumContext);
  433. }
  434. if (foundStateSuccessor == PpmContext.ZERO)
  435. {
  436. goto RestartModel;
  437. }
  438. if (--_orderFall == 0)
  439. {
  440. successor = foundStateSuccessor;
  441. _allocator._text -= (_maximumContext != minimumContext) ? 1 : 0;
  442. }
  443. else if (_method > ModelRestorationMethod.Freeze)
  444. {
  445. successor = foundStateSuccessor;
  446. _allocator._text = _allocator._heap;
  447. _orderFall = 0;
  448. }
  449. numberStatistics = minimumContext.NumberStatistics;
  450. s0 = minimumContext.SummaryFrequency - numberStatistics - foundStateFrequency;
  451. flag = (byte)((foundStateSymbol >= 0x40) ? 0x08 : 0x00);
  452. for (; currentContext != minimumContext; currentContext = currentContext.Suffix)
  453. {
  454. ns1 = currentContext.NumberStatistics;
  455. if (ns1 != 0)
  456. {
  457. if ((ns1 & 1) != 0)
  458. {
  459. state = _allocator.ExpandUnits(currentContext.Statistics, (ns1 + 1) >> 1);
  460. if (state == PpmState.ZERO)
  461. {
  462. goto RestartModel;
  463. }
  464. currentContext.Statistics = state;
  465. }
  466. currentContext.SummaryFrequency += (ushort)((3 * ns1 + 1 < numberStatistics) ? 1 : 0);
  467. }
  468. else
  469. {
  470. state = _allocator.AllocateUnits(1);
  471. if (state == PpmState.ZERO)
  472. {
  473. goto RestartModel;
  474. }
  475. Copy(state, currentContext.FirstState);
  476. currentContext.Statistics = state;
  477. if (state.Frequency < MAXIMUM_FREQUENCY / 4 - 1)
  478. {
  479. state.Frequency += state.Frequency;
  480. }
  481. else
  482. {
  483. state.Frequency = (byte)(MAXIMUM_FREQUENCY - 4);
  484. }
  485. currentContext.SummaryFrequency =
  486. (ushort)(state.Frequency + _initialEscape + ((numberStatistics > 2) ? 1 : 0));
  487. }
  488. cf = (uint)(2 * foundStateFrequency * (currentContext.SummaryFrequency + 6));
  489. sf = s0 + currentContext.SummaryFrequency;
  490. if (cf < 6 * sf)
  491. {
  492. cf = (uint)(1 + ((cf > sf) ? 1 : 0) + ((cf >= 4 * sf) ? 1 : 0));
  493. currentContext.SummaryFrequency += 4;
  494. }
  495. else
  496. {
  497. cf = (uint)(4 + ((cf > 9 * sf) ? 1 : 0) + ((cf > 12 * sf) ? 1 : 0) + ((cf > 15 * sf) ? 1 : 0));
  498. currentContext.SummaryFrequency += (ushort)cf;
  499. }
  500. state = currentContext.Statistics + (++currentContext.NumberStatistics);
  501. state.Successor = successor;
  502. state.Symbol = foundStateSymbol;
  503. state.Frequency = (byte)cf;
  504. currentContext.Flags |= flag;
  505. }
  506. _maximumContext = foundStateSuccessor;
  507. return;
  508. RestartModel:
  509. RestoreModel(currentContext, minimumContext, foundStateSuccessor);
  510. }
  511. private PpmContext CreateSuccessors(bool skip, PpmState state, PpmContext context)
  512. {
  513. PpmContext upBranch = _foundState.Successor;
  514. PpmState[] states = new PpmState[MAXIMUM_ORDER];
  515. uint stateIndex = 0;
  516. byte symbol = _foundState.Symbol;
  517. if (!skip)
  518. {
  519. states[stateIndex++] = _foundState;
  520. if (context.Suffix == PpmContext.ZERO)
  521. {
  522. goto NoLoop;
  523. }
  524. }
  525. bool gotoLoopEntry = false;
  526. if (state != PpmState.ZERO)
  527. {
  528. context = context.Suffix;
  529. gotoLoopEntry = true;
  530. }
  531. do
  532. {
  533. if (gotoLoopEntry)
  534. {
  535. gotoLoopEntry = false;
  536. goto LoopEntry;
  537. }
  538. context = context.Suffix;
  539. if (context.NumberStatistics != 0)
  540. {
  541. byte temporary;
  542. state = context.Statistics;
  543. if (state.Symbol != symbol)
  544. {
  545. do
  546. {
  547. temporary = state[1].Symbol;
  548. state++;
  549. }
  550. while (temporary != symbol);
  551. }
  552. temporary = (byte)((state.Frequency < MAXIMUM_FREQUENCY - 9) ? 1 : 0);
  553. state.Frequency += temporary;
  554. context.SummaryFrequency += temporary;
  555. }
  556. else
  557. {
  558. state = context.FirstState;
  559. state.Frequency +=
  560. (byte)(((context.Suffix.NumberStatistics == 0) ? 1 : 0) & ((state.Frequency < 24) ? 1 : 0));
  561. }
  562. LoopEntry:
  563. if (state.Successor != upBranch)
  564. {
  565. context = state.Successor;
  566. break;
  567. }
  568. states[stateIndex++] = state;
  569. }
  570. while (context.Suffix != PpmContext.ZERO);
  571. NoLoop:
  572. if (stateIndex == 0)
  573. {
  574. return context;
  575. }
  576. byte localNumberStatistics = 0;
  577. byte localFlags = (byte)((symbol >= 0x40) ? 0x10 : 0x00);
  578. symbol = upBranch.NumberStatistics;
  579. byte localSymbol = symbol;
  580. byte localFrequency;
  581. PpmContext localSuccessor = ((Pointer)upBranch) + 1;
  582. localFlags |= (byte)((symbol >= 0x40) ? 0x08 : 0x00);
  583. if (context.NumberStatistics != 0)
  584. {
  585. state = context.Statistics;
  586. if (state.Symbol != symbol)
  587. {
  588. byte temporary;
  589. do
  590. {
  591. temporary = state[1].Symbol;
  592. state++;
  593. }
  594. while (temporary != symbol);
  595. }
  596. uint cf = (uint)(state.Frequency - 1);
  597. uint s0 = (uint)(context.SummaryFrequency - context.NumberStatistics - cf);
  598. localFrequency = (byte)(1 + ((2 * cf <= s0) ? (uint)((5 * cf > s0) ? 1 : 0) : ((cf + 2 * s0 - 3) / s0)));
  599. }
  600. else
  601. {
  602. localFrequency = context.FirstStateFrequency;
  603. }
  604. do
  605. {
  606. PpmContext currentContext = _allocator.AllocateContext();
  607. if (currentContext == PpmContext.ZERO)
  608. {
  609. return PpmContext.ZERO;
  610. }
  611. currentContext.NumberStatistics = localNumberStatistics;
  612. currentContext.Flags = localFlags;
  613. currentContext.FirstStateSymbol = localSymbol;
  614. currentContext.FirstStateFrequency = localFrequency;
  615. currentContext.FirstStateSuccessor = localSuccessor;
  616. currentContext.Suffix = context;
  617. context = currentContext;
  618. states[--stateIndex].Successor = context;
  619. }
  620. while (stateIndex != 0);
  621. return context;
  622. }
  623. private PpmContext ReduceOrder(PpmState state, PpmContext context)
  624. {
  625. PpmState currentState;
  626. PpmState[] states = new PpmState[MAXIMUM_ORDER];
  627. uint stateIndex = 0;
  628. PpmContext currentContext = context;
  629. PpmContext upBranch = _allocator._text;
  630. byte temporary;
  631. byte symbol = _foundState.Symbol;
  632. states[stateIndex++] = _foundState;
  633. _foundState.Successor = upBranch;
  634. _orderFall++;
  635. bool gotoLoopEntry = false;
  636. if (state != PpmState.ZERO)
  637. {
  638. context = context.Suffix;
  639. gotoLoopEntry = true;
  640. }
  641. while (true)
  642. {
  643. if (gotoLoopEntry)
  644. {
  645. gotoLoopEntry = false;
  646. goto LoopEntry;
  647. }
  648. if (context.Suffix == PpmContext.ZERO)
  649. {
  650. if (_method > ModelRestorationMethod.Freeze)
  651. {
  652. do
  653. {
  654. states[--stateIndex].Successor = context;
  655. }
  656. while (stateIndex != 0);
  657. _allocator._text = _allocator._heap + 1;
  658. _orderFall = 1;
  659. }
  660. return context;
  661. }
  662. context = context.Suffix;
  663. if (context.NumberStatistics != 0)
  664. {
  665. state = context.Statistics;
  666. if (state.Symbol != symbol)
  667. {
  668. do
  669. {
  670. temporary = state[1].Symbol;
  671. state++;
  672. }
  673. while (temporary != symbol);
  674. }
  675. temporary = (byte)((state.Frequency < MAXIMUM_FREQUENCY - 9) ? 2 : 0);
  676. state.Frequency += temporary;
  677. context.SummaryFrequency += temporary;
  678. }
  679. else
  680. {
  681. state = context.FirstState;
  682. state.Frequency += (byte)((state.Frequency < 32) ? 1 : 0);
  683. }
  684. LoopEntry:
  685. if (state.Successor != PpmContext.ZERO)
  686. {
  687. break;
  688. }
  689. states[stateIndex++] = state;
  690. state.Successor = upBranch;
  691. _orderFall++;
  692. }
  693. if (_method > ModelRestorationMethod.Freeze)
  694. {
  695. context = state.Successor;
  696. do
  697. {
  698. states[--stateIndex].Successor = context;
  699. }
  700. while (stateIndex != 0);
  701. _allocator._text = _allocator._heap + 1;
  702. _orderFall = 1;
  703. return context;
  704. }
  705. if (state.Successor <= upBranch)
  706. {
  707. currentState = _foundState;
  708. _foundState = state;
  709. state.Successor = CreateSuccessors(false, PpmState.ZERO, context);
  710. _foundState = currentState;
  711. }
  712. if (_orderFall == 1 && currentContext == _maximumContext)
  713. {
  714. _foundState.Successor = state.Successor;
  715. _allocator._text--;
  716. }
  717. return state.Successor;
  718. }
  719. private void RestoreModel(PpmContext context, PpmContext minimumContext, PpmContext foundStateSuccessor)
  720. {
  721. PpmContext currentContext;
  722. _allocator._text = _allocator._heap;
  723. for (currentContext = _maximumContext; currentContext != context; currentContext = currentContext.Suffix)
  724. {
  725. if (--currentContext.NumberStatistics == 0)
  726. {
  727. currentContext.Flags =
  728. (byte)
  729. ((currentContext.Flags & 0x10) + ((currentContext.Statistics.Symbol >= 0x40) ? 0x08 : 0x00));
  730. PpmState state = currentContext.Statistics;
  731. Copy(currentContext.FirstState, state);
  732. _allocator.SpecialFreeUnits(state);
  733. currentContext.FirstStateFrequency = (byte)((currentContext.FirstStateFrequency + 11) >> 3);
  734. }
  735. else
  736. {
  737. Refresh((uint)((currentContext.NumberStatistics + 3) >> 1), false, currentContext);
  738. }
  739. }
  740. for (; currentContext != minimumContext; currentContext = currentContext.Suffix)
  741. {
  742. if (currentContext.NumberStatistics == 0)
  743. {
  744. currentContext.FirstStateFrequency -= (byte)(currentContext.FirstStateFrequency >> 1);
  745. }
  746. else if ((currentContext.SummaryFrequency += 4) > 128 + 4 * currentContext.NumberStatistics)
  747. {
  748. Refresh((uint)((currentContext.NumberStatistics + 2) >> 1), true, currentContext);
  749. }
  750. }
  751. if (_method > ModelRestorationMethod.Freeze)
  752. {
  753. _maximumContext = foundStateSuccessor;
  754. _allocator._glueCount += (uint)(((_allocator._memoryNodes[1].Stamp & 1) == 0) ? 1 : 0);
  755. }
  756. else if (_method == ModelRestorationMethod.Freeze)
  757. {
  758. while (_maximumContext.Suffix != PpmContext.ZERO)
  759. {
  760. _maximumContext = _maximumContext.Suffix;
  761. }
  762. RemoveBinaryContexts(0, _maximumContext);
  763. _method = _method + 1;
  764. _allocator._glueCount = 0;
  765. _orderFall = _modelOrder;
  766. }
  767. else if (_method == ModelRestorationMethod.Restart ||
  768. _allocator.GetMemoryUsed() < (_allocator._allocatorSize >> 1))
  769. {
  770. StartModel(_modelOrder, _method);
  771. _escapeCount = 0;
  772. }
  773. else
  774. {
  775. while (_maximumContext.Suffix != PpmContext.ZERO)
  776. {
  777. _maximumContext = _maximumContext.Suffix;
  778. }
  779. do
  780. {
  781. CutOff(0, _maximumContext);
  782. _allocator.ExpandText();
  783. }
  784. while (_allocator.GetMemoryUsed() > 3 * (_allocator._allocatorSize >> 2));
  785. _allocator._glueCount = 0;
  786. _orderFall = _modelOrder;
  787. }
  788. }
  789. private static void Swap(PpmState state1, PpmState state2)
  790. {
  791. byte swapSymbol = state1.Symbol;
  792. byte swapFrequency = state1.Frequency;
  793. PpmContext swapSuccessor = state1.Successor;
  794. state1.Symbol = state2.Symbol;
  795. state1.Frequency = state2.Frequency;
  796. state1.Successor = state2.Successor;
  797. state2.Symbol = swapSymbol;
  798. state2.Frequency = swapFrequency;
  799. state2.Successor = swapSuccessor;
  800. }
  801. private static void Copy(PpmState state1, PpmState state2)
  802. {
  803. state1.Symbol = state2.Symbol;
  804. state1.Frequency = state2.Frequency;
  805. state1.Successor = state2.Successor;
  806. }
  807. private static int Mean(int sum, int shift, int round)
  808. {
  809. return (sum + (1 << (shift - round))) >> shift;
  810. }
  811. private void ClearMask()
  812. {
  813. _escapeCount = 1;
  814. Array.Clear(_characterMask, 0, _characterMask.Length);
  815. }
  816. #endregion
  817. }
  818. }