LzmaEncoder.cs 70 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797
  1. using System;
  2. using System.IO;
  3. using SharpCompress.Compressors.LZMA.LZ;
  4. using SharpCompress.Compressors.LZMA.RangeCoder;
  5. namespace SharpCompress.Compressors.LZMA
  6. {
  7. internal class Encoder : ICoder, ISetCoderProperties, IWriteCoderProperties
  8. {
  9. private enum EMatchFinderType
  10. {
  11. Bt2,
  12. Bt4
  13. }
  14. private const UInt32 K_IFINITY_PRICE = 0xFFFFFFF;
  15. private static readonly Byte[] G_FAST_POS = new Byte[1 << 11];
  16. static Encoder()
  17. {
  18. const Byte kFastSlots = 22;
  19. int c = 2;
  20. G_FAST_POS[0] = 0;
  21. G_FAST_POS[1] = 1;
  22. for (Byte slotFast = 2; slotFast < kFastSlots; slotFast++)
  23. {
  24. UInt32 k = ((UInt32)1 << ((slotFast >> 1) - 1));
  25. for (UInt32 j = 0; j < k; j++, c++)
  26. {
  27. G_FAST_POS[c] = slotFast;
  28. }
  29. }
  30. }
  31. private static UInt32 GetPosSlot(UInt32 pos)
  32. {
  33. if (pos < (1 << 11))
  34. {
  35. return G_FAST_POS[pos];
  36. }
  37. if (pos < (1 << 21))
  38. {
  39. return (UInt32)(G_FAST_POS[pos >> 10] + 20);
  40. }
  41. return (UInt32)(G_FAST_POS[pos >> 20] + 40);
  42. }
  43. private static UInt32 GetPosSlot2(UInt32 pos)
  44. {
  45. if (pos < (1 << 17))
  46. {
  47. return (UInt32)(G_FAST_POS[pos >> 6] + 12);
  48. }
  49. if (pos < (1 << 27))
  50. {
  51. return (UInt32)(G_FAST_POS[pos >> 16] + 32);
  52. }
  53. return (UInt32)(G_FAST_POS[pos >> 26] + 52);
  54. }
  55. private Base.State _state = new Base.State();
  56. private Byte _previousByte;
  57. private readonly UInt32[] _repDistances = new UInt32[Base.K_NUM_REP_DISTANCES];
  58. private void BaseInit()
  59. {
  60. _state.Init();
  61. _previousByte = 0;
  62. for (UInt32 i = 0; i < Base.K_NUM_REP_DISTANCES; i++)
  63. {
  64. _repDistances[i] = 0;
  65. }
  66. }
  67. private const int K_DEFAULT_DICTIONARY_LOG_SIZE = 22;
  68. private const UInt32 K_NUM_FAST_BYTES_DEFAULT = 0x20;
  69. private class LiteralEncoder
  70. {
  71. public struct Encoder2
  72. {
  73. private BitEncoder[] _encoders;
  74. public void Create()
  75. {
  76. _encoders = new BitEncoder[0x300];
  77. }
  78. public void Init()
  79. {
  80. for (int i = 0; i < 0x300; i++)
  81. {
  82. _encoders[i].Init();
  83. }
  84. }
  85. public void Encode(RangeCoder.Encoder rangeEncoder, byte symbol)
  86. {
  87. uint context = 1;
  88. for (int i = 7; i >= 0; i--)
  89. {
  90. uint bit = (uint)((symbol >> i) & 1);
  91. _encoders[context].Encode(rangeEncoder, bit);
  92. context = (context << 1) | bit;
  93. }
  94. }
  95. public void EncodeMatched(RangeCoder.Encoder rangeEncoder, byte matchByte, byte symbol)
  96. {
  97. uint context = 1;
  98. bool same = true;
  99. for (int i = 7; i >= 0; i--)
  100. {
  101. uint bit = (uint)((symbol >> i) & 1);
  102. uint state = context;
  103. if (same)
  104. {
  105. uint matchBit = (uint)((matchByte >> i) & 1);
  106. state += ((1 + matchBit) << 8);
  107. same = (matchBit == bit);
  108. }
  109. _encoders[state].Encode(rangeEncoder, bit);
  110. context = (context << 1) | bit;
  111. }
  112. }
  113. public uint GetPrice(bool matchMode, byte matchByte, byte symbol)
  114. {
  115. uint price = 0;
  116. uint context = 1;
  117. int i = 7;
  118. if (matchMode)
  119. {
  120. for (; i >= 0; i--)
  121. {
  122. uint matchBit = (uint)(matchByte >> i) & 1;
  123. uint bit = (uint)(symbol >> i) & 1;
  124. price += _encoders[((1 + matchBit) << 8) + context].GetPrice(bit);
  125. context = (context << 1) | bit;
  126. if (matchBit != bit)
  127. {
  128. i--;
  129. break;
  130. }
  131. }
  132. }
  133. for (; i >= 0; i--)
  134. {
  135. uint bit = (uint)(symbol >> i) & 1;
  136. price += _encoders[context].GetPrice(bit);
  137. context = (context << 1) | bit;
  138. }
  139. return price;
  140. }
  141. }
  142. private Encoder2[] _coders;
  143. private int _numPrevBits;
  144. private int _numPosBits;
  145. private uint _posMask;
  146. public void Create(int numPosBits, int numPrevBits)
  147. {
  148. if (_coders != null && _numPrevBits == numPrevBits && _numPosBits == numPosBits)
  149. {
  150. return;
  151. }
  152. _numPosBits = numPosBits;
  153. _posMask = ((uint)1 << numPosBits) - 1;
  154. _numPrevBits = numPrevBits;
  155. uint numStates = (uint)1 << (_numPrevBits + _numPosBits);
  156. _coders = new Encoder2[numStates];
  157. for (uint i = 0; i < numStates; i++)
  158. {
  159. _coders[i].Create();
  160. }
  161. }
  162. public void Init()
  163. {
  164. uint numStates = (uint)1 << (_numPrevBits + _numPosBits);
  165. for (uint i = 0; i < numStates; i++)
  166. {
  167. _coders[i].Init();
  168. }
  169. }
  170. public Encoder2 GetSubCoder(UInt32 pos, Byte prevByte)
  171. {
  172. return _coders[((pos & _posMask) << _numPrevBits) + (uint)(prevByte >> (8 - _numPrevBits))];
  173. }
  174. }
  175. private class LenEncoder
  176. {
  177. private BitEncoder _choice = new BitEncoder();
  178. private BitEncoder _choice2 = new BitEncoder();
  179. private readonly BitTreeEncoder[] _lowCoder = new BitTreeEncoder[Base.K_NUM_POS_STATES_ENCODING_MAX];
  180. private readonly BitTreeEncoder[] _midCoder = new BitTreeEncoder[Base.K_NUM_POS_STATES_ENCODING_MAX];
  181. private BitTreeEncoder _highCoder = new BitTreeEncoder(Base.K_NUM_HIGH_LEN_BITS);
  182. public LenEncoder()
  183. {
  184. for (UInt32 posState = 0; posState < Base.K_NUM_POS_STATES_ENCODING_MAX; posState++)
  185. {
  186. _lowCoder[posState] = new BitTreeEncoder(Base.K_NUM_LOW_LEN_BITS);
  187. _midCoder[posState] = new BitTreeEncoder(Base.K_NUM_MID_LEN_BITS);
  188. }
  189. }
  190. public void Init(UInt32 numPosStates)
  191. {
  192. _choice.Init();
  193. _choice2.Init();
  194. for (UInt32 posState = 0; posState < numPosStates; posState++)
  195. {
  196. _lowCoder[posState].Init();
  197. _midCoder[posState].Init();
  198. }
  199. _highCoder.Init();
  200. }
  201. public void Encode(RangeCoder.Encoder rangeEncoder, UInt32 symbol, UInt32 posState)
  202. {
  203. if (symbol < Base.K_NUM_LOW_LEN_SYMBOLS)
  204. {
  205. _choice.Encode(rangeEncoder, 0);
  206. _lowCoder[posState].Encode(rangeEncoder, symbol);
  207. }
  208. else
  209. {
  210. symbol -= Base.K_NUM_LOW_LEN_SYMBOLS;
  211. _choice.Encode(rangeEncoder, 1);
  212. if (symbol < Base.K_NUM_MID_LEN_SYMBOLS)
  213. {
  214. _choice2.Encode(rangeEncoder, 0);
  215. _midCoder[posState].Encode(rangeEncoder, symbol);
  216. }
  217. else
  218. {
  219. _choice2.Encode(rangeEncoder, 1);
  220. _highCoder.Encode(rangeEncoder, symbol - Base.K_NUM_MID_LEN_SYMBOLS);
  221. }
  222. }
  223. }
  224. public void SetPrices(UInt32 posState, UInt32 numSymbols, UInt32[] prices, UInt32 st)
  225. {
  226. UInt32 a0 = _choice.GetPrice0();
  227. UInt32 a1 = _choice.GetPrice1();
  228. UInt32 b0 = a1 + _choice2.GetPrice0();
  229. UInt32 b1 = a1 + _choice2.GetPrice1();
  230. UInt32 i = 0;
  231. for (i = 0; i < Base.K_NUM_LOW_LEN_SYMBOLS; i++)
  232. {
  233. if (i >= numSymbols)
  234. {
  235. return;
  236. }
  237. prices[st + i] = a0 + _lowCoder[posState].GetPrice(i);
  238. }
  239. for (; i < Base.K_NUM_LOW_LEN_SYMBOLS + Base.K_NUM_MID_LEN_SYMBOLS; i++)
  240. {
  241. if (i >= numSymbols)
  242. {
  243. return;
  244. }
  245. prices[st + i] = b0 + _midCoder[posState].GetPrice(i - Base.K_NUM_LOW_LEN_SYMBOLS);
  246. }
  247. for (; i < numSymbols; i++)
  248. {
  249. prices[st + i] = b1 + _highCoder.GetPrice(i - Base.K_NUM_LOW_LEN_SYMBOLS - Base.K_NUM_MID_LEN_SYMBOLS);
  250. }
  251. }
  252. }
  253. private const UInt32 K_NUM_LEN_SPEC_SYMBOLS = Base.K_NUM_LOW_LEN_SYMBOLS + Base.K_NUM_MID_LEN_SYMBOLS;
  254. private class LenPriceTableEncoder : LenEncoder
  255. {
  256. private readonly UInt32[] _prices = new UInt32[Base.K_NUM_LEN_SYMBOLS << Base.K_NUM_POS_STATES_BITS_ENCODING_MAX];
  257. private UInt32 _tableSize;
  258. private readonly UInt32[] _counters = new UInt32[Base.K_NUM_POS_STATES_ENCODING_MAX];
  259. public void SetTableSize(UInt32 tableSize)
  260. {
  261. _tableSize = tableSize;
  262. }
  263. public UInt32 GetPrice(UInt32 symbol, UInt32 posState)
  264. {
  265. return _prices[posState * Base.K_NUM_LEN_SYMBOLS + symbol];
  266. }
  267. private void UpdateTable(UInt32 posState)
  268. {
  269. SetPrices(posState, _tableSize, _prices, posState * Base.K_NUM_LEN_SYMBOLS);
  270. _counters[posState] = _tableSize;
  271. }
  272. public void UpdateTables(UInt32 numPosStates)
  273. {
  274. for (UInt32 posState = 0; posState < numPosStates; posState++)
  275. {
  276. UpdateTable(posState);
  277. }
  278. }
  279. public new void Encode(RangeCoder.Encoder rangeEncoder, UInt32 symbol, UInt32 posState)
  280. {
  281. base.Encode(rangeEncoder, symbol, posState);
  282. if (--_counters[posState] == 0)
  283. {
  284. UpdateTable(posState);
  285. }
  286. }
  287. }
  288. private const UInt32 K_NUM_OPTS = 1 << 12;
  289. private class Optimal
  290. {
  291. public Base.State _state;
  292. public bool _prev1IsChar;
  293. public bool _prev2;
  294. public UInt32 _posPrev2;
  295. public UInt32 _backPrev2;
  296. public UInt32 _price;
  297. public UInt32 _posPrev;
  298. public UInt32 _backPrev;
  299. public UInt32 _backs0;
  300. public UInt32 _backs1;
  301. public UInt32 _backs2;
  302. public UInt32 _backs3;
  303. public void MakeAsChar()
  304. {
  305. _backPrev = 0xFFFFFFFF;
  306. _prev1IsChar = false;
  307. }
  308. public void MakeAsShortRep()
  309. {
  310. _backPrev = 0;
  311. ;
  312. _prev1IsChar = false;
  313. }
  314. public bool IsShortRep()
  315. {
  316. return (_backPrev == 0);
  317. }
  318. }
  319. private readonly Optimal[] _optimum = new Optimal[K_NUM_OPTS];
  320. private BinTree _matchFinder;
  321. private readonly RangeCoder.Encoder _rangeEncoder = new RangeCoder.Encoder();
  322. private readonly BitEncoder[] _isMatch =
  323. new BitEncoder[Base.K_NUM_STATES << Base.K_NUM_POS_STATES_BITS_MAX];
  324. private readonly BitEncoder[] _isRep = new BitEncoder[Base.K_NUM_STATES];
  325. private readonly BitEncoder[] _isRepG0 = new BitEncoder[Base.K_NUM_STATES];
  326. private readonly BitEncoder[] _isRepG1 = new BitEncoder[Base.K_NUM_STATES];
  327. private readonly BitEncoder[] _isRepG2 = new BitEncoder[Base.K_NUM_STATES];
  328. private readonly BitEncoder[] _isRep0Long =
  329. new BitEncoder[Base.K_NUM_STATES << Base.K_NUM_POS_STATES_BITS_MAX];
  330. private readonly BitTreeEncoder[] _posSlotEncoder = new BitTreeEncoder[Base.K_NUM_LEN_TO_POS_STATES];
  331. private readonly BitEncoder[] _posEncoders =
  332. new BitEncoder[Base.K_NUM_FULL_DISTANCES - Base.K_END_POS_MODEL_INDEX];
  333. private BitTreeEncoder _posAlignEncoder = new BitTreeEncoder(Base.K_NUM_ALIGN_BITS);
  334. private readonly LenPriceTableEncoder _lenEncoder = new LenPriceTableEncoder();
  335. private readonly LenPriceTableEncoder _repMatchLenEncoder = new LenPriceTableEncoder();
  336. private readonly LiteralEncoder _literalEncoder = new LiteralEncoder();
  337. private readonly UInt32[] _matchDistances = new UInt32[Base.K_MATCH_MAX_LEN * 2 + 2];
  338. private UInt32 _numFastBytes = K_NUM_FAST_BYTES_DEFAULT;
  339. private UInt32 _longestMatchLength;
  340. private UInt32 _numDistancePairs;
  341. private UInt32 _additionalOffset;
  342. private UInt32 _optimumEndIndex;
  343. private UInt32 _optimumCurrentIndex;
  344. private bool _longestMatchWasFound;
  345. private readonly UInt32[] _posSlotPrices = new UInt32[1 << (Base.K_NUM_POS_SLOT_BITS + Base.K_NUM_LEN_TO_POS_STATES_BITS)];
  346. private readonly UInt32[] _distancesPrices = new UInt32[Base.K_NUM_FULL_DISTANCES << Base.K_NUM_LEN_TO_POS_STATES_BITS];
  347. private readonly UInt32[] _alignPrices = new UInt32[Base.K_ALIGN_TABLE_SIZE];
  348. private UInt32 _alignPriceCount;
  349. private UInt32 _distTableSize = (K_DEFAULT_DICTIONARY_LOG_SIZE * 2);
  350. private int _posStateBits = 2;
  351. private UInt32 _posStateMask = (4 - 1);
  352. private int _numLiteralPosStateBits;
  353. private int _numLiteralContextBits = 3;
  354. private UInt32 _dictionarySize = (1 << K_DEFAULT_DICTIONARY_LOG_SIZE);
  355. private UInt32 _dictionarySizePrev = 0xFFFFFFFF;
  356. private UInt32 _numFastBytesPrev = 0xFFFFFFFF;
  357. private Int64 _nowPos64;
  358. private bool _finished;
  359. private Stream _inStream;
  360. private EMatchFinderType _matchFinderType = EMatchFinderType.Bt4;
  361. private bool _writeEndMark;
  362. private bool _needReleaseMfStream;
  363. private bool _processingMode;
  364. private void Create()
  365. {
  366. if (_matchFinder == null)
  367. {
  368. BinTree bt = new BinTree();
  369. int numHashBytes = 4;
  370. if (_matchFinderType == EMatchFinderType.Bt2)
  371. {
  372. numHashBytes = 2;
  373. }
  374. bt.SetType(numHashBytes);
  375. _matchFinder = bt;
  376. }
  377. _literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits);
  378. if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)
  379. {
  380. return;
  381. }
  382. _matchFinder.Create(_dictionarySize, K_NUM_OPTS, _numFastBytes, Base.K_MATCH_MAX_LEN + 1 + K_NUM_OPTS);
  383. _dictionarySizePrev = _dictionarySize;
  384. _numFastBytesPrev = _numFastBytes;
  385. }
  386. public Encoder()
  387. {
  388. for (int i = 0; i < K_NUM_OPTS; i++)
  389. {
  390. _optimum[i] = new Optimal();
  391. }
  392. for (int i = 0; i < Base.K_NUM_LEN_TO_POS_STATES; i++)
  393. {
  394. _posSlotEncoder[i] = new BitTreeEncoder(Base.K_NUM_POS_SLOT_BITS);
  395. }
  396. }
  397. private void SetWriteEndMarkerMode(bool writeEndMarker)
  398. {
  399. _writeEndMark = writeEndMarker;
  400. }
  401. private void Init()
  402. {
  403. BaseInit();
  404. _rangeEncoder.Init();
  405. uint i;
  406. for (i = 0; i < Base.K_NUM_STATES; i++)
  407. {
  408. for (uint j = 0; j <= _posStateMask; j++)
  409. {
  410. uint complexState = (i << Base.K_NUM_POS_STATES_BITS_MAX) + j;
  411. _isMatch[complexState].Init();
  412. _isRep0Long[complexState].Init();
  413. }
  414. _isRep[i].Init();
  415. _isRepG0[i].Init();
  416. _isRepG1[i].Init();
  417. _isRepG2[i].Init();
  418. }
  419. _literalEncoder.Init();
  420. for (i = 0; i < Base.K_NUM_LEN_TO_POS_STATES; i++)
  421. {
  422. _posSlotEncoder[i].Init();
  423. }
  424. for (i = 0; i < Base.K_NUM_FULL_DISTANCES - Base.K_END_POS_MODEL_INDEX; i++)
  425. {
  426. _posEncoders[i].Init();
  427. }
  428. _lenEncoder.Init((UInt32)1 << _posStateBits);
  429. _repMatchLenEncoder.Init((UInt32)1 << _posStateBits);
  430. _posAlignEncoder.Init();
  431. _longestMatchWasFound = false;
  432. _optimumEndIndex = 0;
  433. _optimumCurrentIndex = 0;
  434. _additionalOffset = 0;
  435. }
  436. private void ReadMatchDistances(out UInt32 lenRes, out UInt32 numDistancePairs)
  437. {
  438. lenRes = 0;
  439. numDistancePairs = _matchFinder.GetMatches(_matchDistances);
  440. if (numDistancePairs > 0)
  441. {
  442. lenRes = _matchDistances[numDistancePairs - 2];
  443. if (lenRes == _numFastBytes)
  444. {
  445. lenRes += _matchFinder.GetMatchLen((int)lenRes - 1, _matchDistances[numDistancePairs - 1],
  446. Base.K_MATCH_MAX_LEN - lenRes);
  447. }
  448. }
  449. _additionalOffset++;
  450. }
  451. private void MovePos(UInt32 num)
  452. {
  453. if (num > 0)
  454. {
  455. _matchFinder.Skip(num);
  456. _additionalOffset += num;
  457. }
  458. }
  459. private UInt32 GetRepLen1Price(Base.State state, UInt32 posState)
  460. {
  461. return _isRepG0[state._index].GetPrice0() +
  462. _isRep0Long[(state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState].GetPrice0();
  463. }
  464. private UInt32 GetPureRepPrice(UInt32 repIndex, Base.State state, UInt32 posState)
  465. {
  466. UInt32 price;
  467. if (repIndex == 0)
  468. {
  469. price = _isRepG0[state._index].GetPrice0();
  470. price += _isRep0Long[(state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState].GetPrice1();
  471. }
  472. else
  473. {
  474. price = _isRepG0[state._index].GetPrice1();
  475. if (repIndex == 1)
  476. {
  477. price += _isRepG1[state._index].GetPrice0();
  478. }
  479. else
  480. {
  481. price += _isRepG1[state._index].GetPrice1();
  482. price += _isRepG2[state._index].GetPrice(repIndex - 2);
  483. }
  484. }
  485. return price;
  486. }
  487. private UInt32 GetRepPrice(UInt32 repIndex, UInt32 len, Base.State state, UInt32 posState)
  488. {
  489. UInt32 price = _repMatchLenEncoder.GetPrice(len - Base.K_MATCH_MIN_LEN, posState);
  490. return price + GetPureRepPrice(repIndex, state, posState);
  491. }
  492. private UInt32 GetPosLenPrice(UInt32 pos, UInt32 len, UInt32 posState)
  493. {
  494. UInt32 price;
  495. UInt32 lenToPosState = Base.GetLenToPosState(len);
  496. if (pos < Base.K_NUM_FULL_DISTANCES)
  497. {
  498. price = _distancesPrices[(lenToPosState * Base.K_NUM_FULL_DISTANCES) + pos];
  499. }
  500. else
  501. {
  502. price = _posSlotPrices[(lenToPosState << Base.K_NUM_POS_SLOT_BITS) + GetPosSlot2(pos)] +
  503. _alignPrices[pos & Base.K_ALIGN_MASK];
  504. }
  505. return price + _lenEncoder.GetPrice(len - Base.K_MATCH_MIN_LEN, posState);
  506. }
  507. private UInt32 Backward(out UInt32 backRes, UInt32 cur)
  508. {
  509. _optimumEndIndex = cur;
  510. UInt32 posMem = _optimum[cur]._posPrev;
  511. UInt32 backMem = _optimum[cur]._backPrev;
  512. do
  513. {
  514. if (_optimum[cur]._prev1IsChar)
  515. {
  516. _optimum[posMem].MakeAsChar();
  517. _optimum[posMem]._posPrev = posMem - 1;
  518. if (_optimum[cur]._prev2)
  519. {
  520. _optimum[posMem - 1]._prev1IsChar = false;
  521. _optimum[posMem - 1]._posPrev = _optimum[cur]._posPrev2;
  522. _optimum[posMem - 1]._backPrev = _optimum[cur]._backPrev2;
  523. }
  524. }
  525. UInt32 posPrev = posMem;
  526. UInt32 backCur = backMem;
  527. backMem = _optimum[posPrev]._backPrev;
  528. posMem = _optimum[posPrev]._posPrev;
  529. _optimum[posPrev]._backPrev = backCur;
  530. _optimum[posPrev]._posPrev = cur;
  531. cur = posPrev;
  532. }
  533. while (cur > 0);
  534. backRes = _optimum[0]._backPrev;
  535. _optimumCurrentIndex = _optimum[0]._posPrev;
  536. return _optimumCurrentIndex;
  537. }
  538. private readonly UInt32[] _reps = new UInt32[Base.K_NUM_REP_DISTANCES];
  539. private readonly UInt32[] _repLens = new UInt32[Base.K_NUM_REP_DISTANCES];
  540. private UInt32 GetOptimum(UInt32 position, out UInt32 backRes)
  541. {
  542. if (_optimumEndIndex != _optimumCurrentIndex)
  543. {
  544. UInt32 lenRes = _optimum[_optimumCurrentIndex]._posPrev - _optimumCurrentIndex;
  545. backRes = _optimum[_optimumCurrentIndex]._backPrev;
  546. _optimumCurrentIndex = _optimum[_optimumCurrentIndex]._posPrev;
  547. return lenRes;
  548. }
  549. _optimumCurrentIndex = _optimumEndIndex = 0;
  550. UInt32 lenMain, numDistancePairs;
  551. if (!_longestMatchWasFound)
  552. {
  553. ReadMatchDistances(out lenMain, out numDistancePairs);
  554. }
  555. else
  556. {
  557. lenMain = _longestMatchLength;
  558. numDistancePairs = _numDistancePairs;
  559. _longestMatchWasFound = false;
  560. }
  561. UInt32 numAvailableBytes = _matchFinder.GetNumAvailableBytes() + 1;
  562. if (numAvailableBytes < 2)
  563. {
  564. backRes = 0xFFFFFFFF;
  565. return 1;
  566. }
  567. if (numAvailableBytes > Base.K_MATCH_MAX_LEN)
  568. {
  569. numAvailableBytes = Base.K_MATCH_MAX_LEN;
  570. }
  571. UInt32 repMaxIndex = 0;
  572. UInt32 i;
  573. for (i = 0; i < Base.K_NUM_REP_DISTANCES; i++)
  574. {
  575. _reps[i] = _repDistances[i];
  576. _repLens[i] = _matchFinder.GetMatchLen(0 - 1, _reps[i], Base.K_MATCH_MAX_LEN);
  577. if (_repLens[i] > _repLens[repMaxIndex])
  578. {
  579. repMaxIndex = i;
  580. }
  581. }
  582. if (_repLens[repMaxIndex] >= _numFastBytes)
  583. {
  584. backRes = repMaxIndex;
  585. UInt32 lenRes = _repLens[repMaxIndex];
  586. MovePos(lenRes - 1);
  587. return lenRes;
  588. }
  589. if (lenMain >= _numFastBytes)
  590. {
  591. backRes = _matchDistances[numDistancePairs - 1] + Base.K_NUM_REP_DISTANCES;
  592. MovePos(lenMain - 1);
  593. return lenMain;
  594. }
  595. Byte currentByte = _matchFinder.GetIndexByte(0 - 1);
  596. Byte matchByte = _matchFinder.GetIndexByte((Int32)(0 - _repDistances[0] - 1 - 1));
  597. if (lenMain < 2 && currentByte != matchByte && _repLens[repMaxIndex] < 2)
  598. {
  599. backRes = 0xFFFFFFFF;
  600. return 1;
  601. }
  602. _optimum[0]._state = _state;
  603. UInt32 posState = (position & _posStateMask);
  604. _optimum[1]._price = _isMatch[(_state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState].GetPrice0() +
  605. _literalEncoder.GetSubCoder(position, _previousByte)
  606. .GetPrice(!_state.IsCharState(), matchByte, currentByte);
  607. _optimum[1].MakeAsChar();
  608. UInt32 matchPrice = _isMatch[(_state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState].GetPrice1();
  609. UInt32 repMatchPrice = matchPrice + _isRep[_state._index].GetPrice1();
  610. if (matchByte == currentByte)
  611. {
  612. UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);
  613. if (shortRepPrice < _optimum[1]._price)
  614. {
  615. _optimum[1]._price = shortRepPrice;
  616. _optimum[1].MakeAsShortRep();
  617. }
  618. }
  619. UInt32 lenEnd = ((lenMain >= _repLens[repMaxIndex]) ? lenMain : _repLens[repMaxIndex]);
  620. if (lenEnd < 2)
  621. {
  622. backRes = _optimum[1]._backPrev;
  623. return 1;
  624. }
  625. _optimum[1]._posPrev = 0;
  626. _optimum[0]._backs0 = _reps[0];
  627. _optimum[0]._backs1 = _reps[1];
  628. _optimum[0]._backs2 = _reps[2];
  629. _optimum[0]._backs3 = _reps[3];
  630. UInt32 len = lenEnd;
  631. do
  632. {
  633. _optimum[len--]._price = K_IFINITY_PRICE;
  634. }
  635. while (len >= 2);
  636. for (i = 0; i < Base.K_NUM_REP_DISTANCES; i++)
  637. {
  638. UInt32 repLen = _repLens[i];
  639. if (repLen < 2)
  640. {
  641. continue;
  642. }
  643. UInt32 price = repMatchPrice + GetPureRepPrice(i, _state, posState);
  644. do
  645. {
  646. UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(repLen - 2, posState);
  647. Optimal optimum = _optimum[repLen];
  648. if (curAndLenPrice < optimum._price)
  649. {
  650. optimum._price = curAndLenPrice;
  651. optimum._posPrev = 0;
  652. optimum._backPrev = i;
  653. optimum._prev1IsChar = false;
  654. }
  655. }
  656. while (--repLen >= 2);
  657. }
  658. UInt32 normalMatchPrice = matchPrice + _isRep[_state._index].GetPrice0();
  659. len = ((_repLens[0] >= 2) ? _repLens[0] + 1 : 2);
  660. if (len <= lenMain)
  661. {
  662. UInt32 offs = 0;
  663. while (len > _matchDistances[offs])
  664. {
  665. offs += 2;
  666. }
  667. for (;; len++)
  668. {
  669. UInt32 distance = _matchDistances[offs + 1];
  670. UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(distance, len, posState);
  671. Optimal optimum = _optimum[len];
  672. if (curAndLenPrice < optimum._price)
  673. {
  674. optimum._price = curAndLenPrice;
  675. optimum._posPrev = 0;
  676. optimum._backPrev = distance + Base.K_NUM_REP_DISTANCES;
  677. optimum._prev1IsChar = false;
  678. }
  679. if (len == _matchDistances[offs])
  680. {
  681. offs += 2;
  682. if (offs == numDistancePairs)
  683. {
  684. break;
  685. }
  686. }
  687. }
  688. }
  689. UInt32 cur = 0;
  690. while (true)
  691. {
  692. cur++;
  693. if (cur == lenEnd)
  694. {
  695. return Backward(out backRes, cur);
  696. }
  697. UInt32 newLen;
  698. ReadMatchDistances(out newLen, out numDistancePairs);
  699. if (newLen >= _numFastBytes)
  700. {
  701. _numDistancePairs = numDistancePairs;
  702. _longestMatchLength = newLen;
  703. _longestMatchWasFound = true;
  704. return Backward(out backRes, cur);
  705. }
  706. position++;
  707. UInt32 posPrev = _optimum[cur]._posPrev;
  708. Base.State state;
  709. if (_optimum[cur]._prev1IsChar)
  710. {
  711. posPrev--;
  712. if (_optimum[cur]._prev2)
  713. {
  714. state = _optimum[_optimum[cur]._posPrev2]._state;
  715. if (_optimum[cur]._backPrev2 < Base.K_NUM_REP_DISTANCES)
  716. {
  717. state.UpdateRep();
  718. }
  719. else
  720. {
  721. state.UpdateMatch();
  722. }
  723. }
  724. else
  725. {
  726. state = _optimum[posPrev]._state;
  727. }
  728. state.UpdateChar();
  729. }
  730. else
  731. {
  732. state = _optimum[posPrev]._state;
  733. }
  734. if (posPrev == cur - 1)
  735. {
  736. if (_optimum[cur].IsShortRep())
  737. {
  738. state.UpdateShortRep();
  739. }
  740. else
  741. {
  742. state.UpdateChar();
  743. }
  744. }
  745. else
  746. {
  747. UInt32 pos;
  748. if (_optimum[cur]._prev1IsChar && _optimum[cur]._prev2)
  749. {
  750. posPrev = _optimum[cur]._posPrev2;
  751. pos = _optimum[cur]._backPrev2;
  752. state.UpdateRep();
  753. }
  754. else
  755. {
  756. pos = _optimum[cur]._backPrev;
  757. if (pos < Base.K_NUM_REP_DISTANCES)
  758. {
  759. state.UpdateRep();
  760. }
  761. else
  762. {
  763. state.UpdateMatch();
  764. }
  765. }
  766. Optimal opt = _optimum[posPrev];
  767. if (pos < Base.K_NUM_REP_DISTANCES)
  768. {
  769. if (pos == 0)
  770. {
  771. _reps[0] = opt._backs0;
  772. _reps[1] = opt._backs1;
  773. _reps[2] = opt._backs2;
  774. _reps[3] = opt._backs3;
  775. }
  776. else if (pos == 1)
  777. {
  778. _reps[0] = opt._backs1;
  779. _reps[1] = opt._backs0;
  780. _reps[2] = opt._backs2;
  781. _reps[3] = opt._backs3;
  782. }
  783. else if (pos == 2)
  784. {
  785. _reps[0] = opt._backs2;
  786. _reps[1] = opt._backs0;
  787. _reps[2] = opt._backs1;
  788. _reps[3] = opt._backs3;
  789. }
  790. else
  791. {
  792. _reps[0] = opt._backs3;
  793. _reps[1] = opt._backs0;
  794. _reps[2] = opt._backs1;
  795. _reps[3] = opt._backs2;
  796. }
  797. }
  798. else
  799. {
  800. _reps[0] = (pos - Base.K_NUM_REP_DISTANCES);
  801. _reps[1] = opt._backs0;
  802. _reps[2] = opt._backs1;
  803. _reps[3] = opt._backs2;
  804. }
  805. }
  806. _optimum[cur]._state = state;
  807. _optimum[cur]._backs0 = _reps[0];
  808. _optimum[cur]._backs1 = _reps[1];
  809. _optimum[cur]._backs2 = _reps[2];
  810. _optimum[cur]._backs3 = _reps[3];
  811. UInt32 curPrice = _optimum[cur]._price;
  812. currentByte = _matchFinder.GetIndexByte(0 - 1);
  813. matchByte = _matchFinder.GetIndexByte((Int32)(0 - _reps[0] - 1 - 1));
  814. posState = (position & _posStateMask);
  815. UInt32 curAnd1Price = curPrice +
  816. _isMatch[(state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState].GetPrice0() +
  817. _literalEncoder.GetSubCoder(position, _matchFinder.GetIndexByte(0 - 2)).
  818. GetPrice(!state.IsCharState(), matchByte, currentByte);
  819. Optimal nextOptimum = _optimum[cur + 1];
  820. bool nextIsChar = false;
  821. if (curAnd1Price < nextOptimum._price)
  822. {
  823. nextOptimum._price = curAnd1Price;
  824. nextOptimum._posPrev = cur;
  825. nextOptimum.MakeAsChar();
  826. nextIsChar = true;
  827. }
  828. matchPrice = curPrice + _isMatch[(state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState].GetPrice1();
  829. repMatchPrice = matchPrice + _isRep[state._index].GetPrice1();
  830. if (matchByte == currentByte &&
  831. !(nextOptimum._posPrev < cur && nextOptimum._backPrev == 0))
  832. {
  833. UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState);
  834. if (shortRepPrice <= nextOptimum._price)
  835. {
  836. nextOptimum._price = shortRepPrice;
  837. nextOptimum._posPrev = cur;
  838. nextOptimum.MakeAsShortRep();
  839. nextIsChar = true;
  840. }
  841. }
  842. UInt32 numAvailableBytesFull = _matchFinder.GetNumAvailableBytes() + 1;
  843. numAvailableBytesFull = Math.Min(K_NUM_OPTS - 1 - cur, numAvailableBytesFull);
  844. numAvailableBytes = numAvailableBytesFull;
  845. if (numAvailableBytes < 2)
  846. {
  847. continue;
  848. }
  849. if (numAvailableBytes > _numFastBytes)
  850. {
  851. numAvailableBytes = _numFastBytes;
  852. }
  853. if (!nextIsChar && matchByte != currentByte)
  854. {
  855. // try Literal + rep0
  856. UInt32 t = Math.Min(numAvailableBytesFull - 1, _numFastBytes);
  857. UInt32 lenTest2 = _matchFinder.GetMatchLen(0, _reps[0], t);
  858. if (lenTest2 >= 2)
  859. {
  860. Base.State state2 = state;
  861. state2.UpdateChar();
  862. UInt32 posStateNext = (position + 1) & _posStateMask;
  863. UInt32 nextRepMatchPrice = curAnd1Price +
  864. _isMatch[(state2._index << Base.K_NUM_POS_STATES_BITS_MAX) + posStateNext]
  865. .GetPrice1() +
  866. _isRep[state2._index].GetPrice1();
  867. {
  868. UInt32 offset = cur + 1 + lenTest2;
  869. while (lenEnd < offset)
  870. {
  871. _optimum[++lenEnd]._price = K_IFINITY_PRICE;
  872. }
  873. UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(
  874. 0, lenTest2, state2, posStateNext);
  875. Optimal optimum = _optimum[offset];
  876. if (curAndLenPrice < optimum._price)
  877. {
  878. optimum._price = curAndLenPrice;
  879. optimum._posPrev = cur + 1;
  880. optimum._backPrev = 0;
  881. optimum._prev1IsChar = true;
  882. optimum._prev2 = false;
  883. }
  884. }
  885. }
  886. }
  887. UInt32 startLen = 2; // speed optimization
  888. for (UInt32 repIndex = 0; repIndex < Base.K_NUM_REP_DISTANCES; repIndex++)
  889. {
  890. UInt32 lenTest = _matchFinder.GetMatchLen(0 - 1, _reps[repIndex], numAvailableBytes);
  891. if (lenTest < 2)
  892. {
  893. continue;
  894. }
  895. UInt32 lenTestTemp = lenTest;
  896. do
  897. {
  898. while (lenEnd < cur + lenTest)
  899. {
  900. _optimum[++lenEnd]._price = K_IFINITY_PRICE;
  901. }
  902. UInt32 curAndLenPrice = repMatchPrice + GetRepPrice(repIndex, lenTest, state, posState);
  903. Optimal optimum = _optimum[cur + lenTest];
  904. if (curAndLenPrice < optimum._price)
  905. {
  906. optimum._price = curAndLenPrice;
  907. optimum._posPrev = cur;
  908. optimum._backPrev = repIndex;
  909. optimum._prev1IsChar = false;
  910. }
  911. }
  912. while (--lenTest >= 2);
  913. lenTest = lenTestTemp;
  914. if (repIndex == 0)
  915. {
  916. startLen = lenTest + 1;
  917. }
  918. // if (_maxMode)
  919. if (lenTest < numAvailableBytesFull)
  920. {
  921. UInt32 t = Math.Min(numAvailableBytesFull - 1 - lenTest, _numFastBytes);
  922. UInt32 lenTest2 = _matchFinder.GetMatchLen((Int32)lenTest, _reps[repIndex], t);
  923. if (lenTest2 >= 2)
  924. {
  925. Base.State state2 = state;
  926. state2.UpdateRep();
  927. UInt32 posStateNext = (position + lenTest) & _posStateMask;
  928. UInt32 curAndLenCharPrice =
  929. repMatchPrice + GetRepPrice(repIndex, lenTest, state, posState) +
  930. _isMatch[(state2._index << Base.K_NUM_POS_STATES_BITS_MAX) + posStateNext].GetPrice0() +
  931. _literalEncoder.GetSubCoder(position + lenTest,
  932. _matchFinder.GetIndexByte((Int32)lenTest - 1 - 1))
  933. .GetPrice(true,
  934. _matchFinder.GetIndexByte(
  935. (Int32)lenTest - 1 - (Int32)(_reps[repIndex] + 1)),
  936. _matchFinder.GetIndexByte((Int32)lenTest - 1));
  937. state2.UpdateChar();
  938. posStateNext = (position + lenTest + 1) & _posStateMask;
  939. UInt32 nextMatchPrice = curAndLenCharPrice +
  940. _isMatch[(state2._index << Base.K_NUM_POS_STATES_BITS_MAX) + posStateNext]
  941. .GetPrice1();
  942. UInt32 nextRepMatchPrice = nextMatchPrice + _isRep[state2._index].GetPrice1();
  943. // for(; lenTest2 >= 2; lenTest2--)
  944. {
  945. UInt32 offset = lenTest + 1 + lenTest2;
  946. while (lenEnd < cur + offset)
  947. {
  948. _optimum[++lenEnd]._price = K_IFINITY_PRICE;
  949. }
  950. UInt32 curAndLenPrice = nextRepMatchPrice +
  951. GetRepPrice(0, lenTest2, state2, posStateNext);
  952. Optimal optimum = _optimum[cur + offset];
  953. if (curAndLenPrice < optimum._price)
  954. {
  955. optimum._price = curAndLenPrice;
  956. optimum._posPrev = cur + lenTest + 1;
  957. optimum._backPrev = 0;
  958. optimum._prev1IsChar = true;
  959. optimum._prev2 = true;
  960. optimum._posPrev2 = cur;
  961. optimum._backPrev2 = repIndex;
  962. }
  963. }
  964. }
  965. }
  966. }
  967. if (newLen > numAvailableBytes)
  968. {
  969. newLen = numAvailableBytes;
  970. for (numDistancePairs = 0; newLen > _matchDistances[numDistancePairs]; numDistancePairs += 2)
  971. {
  972. ;
  973. }
  974. _matchDistances[numDistancePairs] = newLen;
  975. numDistancePairs += 2;
  976. }
  977. if (newLen >= startLen)
  978. {
  979. normalMatchPrice = matchPrice + _isRep[state._index].GetPrice0();
  980. while (lenEnd < cur + newLen)
  981. {
  982. _optimum[++lenEnd]._price = K_IFINITY_PRICE;
  983. }
  984. UInt32 offs = 0;
  985. while (startLen > _matchDistances[offs])
  986. {
  987. offs += 2;
  988. }
  989. for (UInt32 lenTest = startLen;; lenTest++)
  990. {
  991. UInt32 curBack = _matchDistances[offs + 1];
  992. UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(curBack, lenTest, posState);
  993. Optimal optimum = _optimum[cur + lenTest];
  994. if (curAndLenPrice < optimum._price)
  995. {
  996. optimum._price = curAndLenPrice;
  997. optimum._posPrev = cur;
  998. optimum._backPrev = curBack + Base.K_NUM_REP_DISTANCES;
  999. optimum._prev1IsChar = false;
  1000. }
  1001. if (lenTest == _matchDistances[offs])
  1002. {
  1003. if (lenTest < numAvailableBytesFull)
  1004. {
  1005. UInt32 t = Math.Min(numAvailableBytesFull - 1 - lenTest, _numFastBytes);
  1006. UInt32 lenTest2 = _matchFinder.GetMatchLen((Int32)lenTest, curBack, t);
  1007. if (lenTest2 >= 2)
  1008. {
  1009. Base.State state2 = state;
  1010. state2.UpdateMatch();
  1011. UInt32 posStateNext = (position + lenTest) & _posStateMask;
  1012. UInt32 curAndLenCharPrice = curAndLenPrice +
  1013. _isMatch[
  1014. (state2._index << Base.K_NUM_POS_STATES_BITS_MAX) +
  1015. posStateNext].GetPrice0() +
  1016. _literalEncoder.GetSubCoder(position + lenTest,
  1017. _matchFinder.GetIndexByte(
  1018. (Int32)lenTest - 1 - 1))
  1019. .
  1020. GetPrice(true,
  1021. _matchFinder.GetIndexByte(
  1022. (Int32)lenTest -
  1023. (Int32)(curBack + 1) - 1),
  1024. _matchFinder.GetIndexByte(
  1025. (Int32)lenTest - 1));
  1026. state2.UpdateChar();
  1027. posStateNext = (position + lenTest + 1) & _posStateMask;
  1028. UInt32 nextMatchPrice = curAndLenCharPrice +
  1029. _isMatch[
  1030. (state2._index << Base.K_NUM_POS_STATES_BITS_MAX) +
  1031. posStateNext].GetPrice1();
  1032. UInt32 nextRepMatchPrice = nextMatchPrice + _isRep[state2._index].GetPrice1();
  1033. UInt32 offset = lenTest + 1 + lenTest2;
  1034. while (lenEnd < cur + offset)
  1035. {
  1036. _optimum[++lenEnd]._price = K_IFINITY_PRICE;
  1037. }
  1038. curAndLenPrice = nextRepMatchPrice + GetRepPrice(0, lenTest2, state2, posStateNext);
  1039. optimum = _optimum[cur + offset];
  1040. if (curAndLenPrice < optimum._price)
  1041. {
  1042. optimum._price = curAndLenPrice;
  1043. optimum._posPrev = cur + lenTest + 1;
  1044. optimum._backPrev = 0;
  1045. optimum._prev1IsChar = true;
  1046. optimum._prev2 = true;
  1047. optimum._posPrev2 = cur;
  1048. optimum._backPrev2 = curBack + Base.K_NUM_REP_DISTANCES;
  1049. }
  1050. }
  1051. }
  1052. offs += 2;
  1053. if (offs == numDistancePairs)
  1054. {
  1055. break;
  1056. }
  1057. }
  1058. }
  1059. }
  1060. }
  1061. }
  1062. private bool ChangePair(UInt32 smallDist, UInt32 bigDist)
  1063. {
  1064. const int kDif = 7;
  1065. return (smallDist < ((UInt32)(1) << (32 - kDif)) && bigDist >= (smallDist << kDif));
  1066. }
  1067. private void WriteEndMarker(UInt32 posState)
  1068. {
  1069. if (!_writeEndMark)
  1070. {
  1071. return;
  1072. }
  1073. _isMatch[(_state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState].Encode(_rangeEncoder, 1);
  1074. _isRep[_state._index].Encode(_rangeEncoder, 0);
  1075. _state.UpdateMatch();
  1076. UInt32 len = Base.K_MATCH_MIN_LEN;
  1077. _lenEncoder.Encode(_rangeEncoder, len - Base.K_MATCH_MIN_LEN, posState);
  1078. UInt32 posSlot = (1 << Base.K_NUM_POS_SLOT_BITS) - 1;
  1079. UInt32 lenToPosState = Base.GetLenToPosState(len);
  1080. _posSlotEncoder[lenToPosState].Encode(_rangeEncoder, posSlot);
  1081. int footerBits = 30;
  1082. UInt32 posReduced = (((UInt32)1) << footerBits) - 1;
  1083. _rangeEncoder.EncodeDirectBits(posReduced >> Base.K_NUM_ALIGN_BITS, footerBits - Base.K_NUM_ALIGN_BITS);
  1084. _posAlignEncoder.ReverseEncode(_rangeEncoder, posReduced & Base.K_ALIGN_MASK);
  1085. }
  1086. private void Flush(UInt32 nowPos)
  1087. {
  1088. ReleaseMfStream();
  1089. WriteEndMarker(nowPos & _posStateMask);
  1090. _rangeEncoder.FlushData();
  1091. _rangeEncoder.FlushStream();
  1092. }
  1093. public void CodeOneBlock(out Int64 inSize, out Int64 outSize, out bool finished)
  1094. {
  1095. inSize = 0;
  1096. outSize = 0;
  1097. finished = true;
  1098. if (_inStream != null)
  1099. {
  1100. _matchFinder.SetStream(_inStream);
  1101. _needReleaseMfStream = true;
  1102. _inStream = null;
  1103. }
  1104. if (_finished)
  1105. {
  1106. return;
  1107. }
  1108. _finished = true;
  1109. Int64 progressPosValuePrev = _nowPos64;
  1110. if (_nowPos64 == 0)
  1111. {
  1112. if (_trainSize > 0)
  1113. {
  1114. for (; _trainSize > 0 && (!_processingMode || !_matchFinder.IsDataStarved); _trainSize--)
  1115. {
  1116. _matchFinder.Skip(1);
  1117. }
  1118. if (_trainSize == 0)
  1119. {
  1120. _previousByte = _matchFinder.GetIndexByte(-1);
  1121. }
  1122. }
  1123. if (_processingMode && _matchFinder.IsDataStarved)
  1124. {
  1125. _finished = false;
  1126. return;
  1127. }
  1128. if (_matchFinder.GetNumAvailableBytes() == 0)
  1129. {
  1130. Flush((UInt32)_nowPos64);
  1131. return;
  1132. }
  1133. UInt32 len, numDistancePairs; // it's not used
  1134. ReadMatchDistances(out len, out numDistancePairs);
  1135. UInt32 posState = (UInt32)(_nowPos64) & _posStateMask;
  1136. _isMatch[(_state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState].Encode(_rangeEncoder, 0);
  1137. _state.UpdateChar();
  1138. Byte curByte = _matchFinder.GetIndexByte((Int32)(0 - _additionalOffset));
  1139. _literalEncoder.GetSubCoder((UInt32)(_nowPos64), _previousByte).Encode(_rangeEncoder, curByte);
  1140. _previousByte = curByte;
  1141. _additionalOffset--;
  1142. _nowPos64++;
  1143. }
  1144. if (_processingMode && _matchFinder.IsDataStarved)
  1145. {
  1146. _finished = false;
  1147. return;
  1148. }
  1149. if (_matchFinder.GetNumAvailableBytes() == 0)
  1150. {
  1151. Flush((UInt32)_nowPos64);
  1152. return;
  1153. }
  1154. while (true)
  1155. {
  1156. if (_processingMode && _matchFinder.IsDataStarved)
  1157. {
  1158. _finished = false;
  1159. return;
  1160. }
  1161. UInt32 pos;
  1162. UInt32 len = GetOptimum((UInt32)_nowPos64, out pos);
  1163. UInt32 posState = ((UInt32)_nowPos64) & _posStateMask;
  1164. UInt32 complexState = (_state._index << Base.K_NUM_POS_STATES_BITS_MAX) + posState;
  1165. if (len == 1 && pos == 0xFFFFFFFF)
  1166. {
  1167. _isMatch[complexState].Encode(_rangeEncoder, 0);
  1168. Byte curByte = _matchFinder.GetIndexByte((Int32)(0 - _additionalOffset));
  1169. LiteralEncoder.Encoder2 subCoder = _literalEncoder.GetSubCoder((UInt32)_nowPos64, _previousByte);
  1170. if (!_state.IsCharState())
  1171. {
  1172. Byte matchByte =
  1173. _matchFinder.GetIndexByte((Int32)(0 - _repDistances[0] - 1 - _additionalOffset));
  1174. subCoder.EncodeMatched(_rangeEncoder, matchByte, curByte);
  1175. }
  1176. else
  1177. {
  1178. subCoder.Encode(_rangeEncoder, curByte);
  1179. }
  1180. _previousByte = curByte;
  1181. _state.UpdateChar();
  1182. }
  1183. else
  1184. {
  1185. _isMatch[complexState].Encode(_rangeEncoder, 1);
  1186. if (pos < Base.K_NUM_REP_DISTANCES)
  1187. {
  1188. _isRep[_state._index].Encode(_rangeEncoder, 1);
  1189. if (pos == 0)
  1190. {
  1191. _isRepG0[_state._index].Encode(_rangeEncoder, 0);
  1192. if (len == 1)
  1193. {
  1194. _isRep0Long[complexState].Encode(_rangeEncoder, 0);
  1195. }
  1196. else
  1197. {
  1198. _isRep0Long[complexState].Encode(_rangeEncoder, 1);
  1199. }
  1200. }
  1201. else
  1202. {
  1203. _isRepG0[_state._index].Encode(_rangeEncoder, 1);
  1204. if (pos == 1)
  1205. {
  1206. _isRepG1[_state._index].Encode(_rangeEncoder, 0);
  1207. }
  1208. else
  1209. {
  1210. _isRepG1[_state._index].Encode(_rangeEncoder, 1);
  1211. _isRepG2[_state._index].Encode(_rangeEncoder, pos - 2);
  1212. }
  1213. }
  1214. if (len == 1)
  1215. {
  1216. _state.UpdateShortRep();
  1217. }
  1218. else
  1219. {
  1220. _repMatchLenEncoder.Encode(_rangeEncoder, len - Base.K_MATCH_MIN_LEN, posState);
  1221. _state.UpdateRep();
  1222. }
  1223. UInt32 distance = _repDistances[pos];
  1224. if (pos != 0)
  1225. {
  1226. for (UInt32 i = pos; i >= 1; i--)
  1227. {
  1228. _repDistances[i] = _repDistances[i - 1];
  1229. }
  1230. _repDistances[0] = distance;
  1231. }
  1232. }
  1233. else
  1234. {
  1235. _isRep[_state._index].Encode(_rangeEncoder, 0);
  1236. _state.UpdateMatch();
  1237. _lenEncoder.Encode(_rangeEncoder, len - Base.K_MATCH_MIN_LEN, posState);
  1238. pos -= Base.K_NUM_REP_DISTANCES;
  1239. UInt32 posSlot = GetPosSlot(pos);
  1240. UInt32 lenToPosState = Base.GetLenToPosState(len);
  1241. _posSlotEncoder[lenToPosState].Encode(_rangeEncoder, posSlot);
  1242. if (posSlot >= Base.K_START_POS_MODEL_INDEX)
  1243. {
  1244. int footerBits = (int)((posSlot >> 1) - 1);
  1245. UInt32 baseVal = ((2 | (posSlot & 1)) << footerBits);
  1246. UInt32 posReduced = pos - baseVal;
  1247. if (posSlot < Base.K_END_POS_MODEL_INDEX)
  1248. {
  1249. BitTreeEncoder.ReverseEncode(_posEncoders,
  1250. baseVal - posSlot - 1, _rangeEncoder, footerBits,
  1251. posReduced);
  1252. }
  1253. else
  1254. {
  1255. _rangeEncoder.EncodeDirectBits(posReduced >> Base.K_NUM_ALIGN_BITS,
  1256. footerBits - Base.K_NUM_ALIGN_BITS);
  1257. _posAlignEncoder.ReverseEncode(_rangeEncoder, posReduced & Base.K_ALIGN_MASK);
  1258. _alignPriceCount++;
  1259. }
  1260. }
  1261. UInt32 distance = pos;
  1262. for (UInt32 i = Base.K_NUM_REP_DISTANCES - 1; i >= 1; i--)
  1263. {
  1264. _repDistances[i] = _repDistances[i - 1];
  1265. }
  1266. _repDistances[0] = distance;
  1267. _matchPriceCount++;
  1268. }
  1269. _previousByte = _matchFinder.GetIndexByte((Int32)(len - 1 - _additionalOffset));
  1270. }
  1271. _additionalOffset -= len;
  1272. _nowPos64 += len;
  1273. if (_additionalOffset == 0)
  1274. {
  1275. // if (!_fastMode)
  1276. if (_matchPriceCount >= (1 << 7))
  1277. {
  1278. FillDistancesPrices();
  1279. }
  1280. if (_alignPriceCount >= Base.K_ALIGN_TABLE_SIZE)
  1281. {
  1282. FillAlignPrices();
  1283. }
  1284. inSize = _nowPos64;
  1285. outSize = _rangeEncoder.GetProcessedSizeAdd();
  1286. if (_processingMode && _matchFinder.IsDataStarved)
  1287. {
  1288. _finished = false;
  1289. return;
  1290. }
  1291. if (_matchFinder.GetNumAvailableBytes() == 0)
  1292. {
  1293. Flush((UInt32)_nowPos64);
  1294. return;
  1295. }
  1296. if (_nowPos64 - progressPosValuePrev >= (1 << 12))
  1297. {
  1298. _finished = false;
  1299. finished = false;
  1300. return;
  1301. }
  1302. }
  1303. }
  1304. }
  1305. private void ReleaseMfStream()
  1306. {
  1307. if (_matchFinder != null && _needReleaseMfStream)
  1308. {
  1309. _matchFinder.ReleaseStream();
  1310. _needReleaseMfStream = false;
  1311. }
  1312. }
  1313. private void SetOutStream(Stream outStream)
  1314. {
  1315. _rangeEncoder.SetStream(outStream);
  1316. }
  1317. private void ReleaseOutStream()
  1318. {
  1319. _rangeEncoder.ReleaseStream();
  1320. }
  1321. private void ReleaseStreams()
  1322. {
  1323. ReleaseMfStream();
  1324. ReleaseOutStream();
  1325. }
  1326. public void SetStreams(Stream inStream, Stream outStream,
  1327. Int64 inSize, Int64 outSize)
  1328. {
  1329. _inStream = inStream;
  1330. _finished = false;
  1331. Create();
  1332. SetOutStream(outStream);
  1333. Init();
  1334. _matchFinder.Init();
  1335. // if (!_fastMode)
  1336. {
  1337. FillDistancesPrices();
  1338. FillAlignPrices();
  1339. }
  1340. _lenEncoder.SetTableSize(_numFastBytes + 1 - Base.K_MATCH_MIN_LEN);
  1341. _lenEncoder.UpdateTables((UInt32)1 << _posStateBits);
  1342. _repMatchLenEncoder.SetTableSize(_numFastBytes + 1 - Base.K_MATCH_MIN_LEN);
  1343. _repMatchLenEncoder.UpdateTables((UInt32)1 << _posStateBits);
  1344. _nowPos64 = 0;
  1345. }
  1346. public void Code(Stream inStream, Stream outStream,
  1347. Int64 inSize, Int64 outSize, ICodeProgress progress)
  1348. {
  1349. _needReleaseMfStream = false;
  1350. _processingMode = false;
  1351. try
  1352. {
  1353. SetStreams(inStream, outStream, inSize, outSize);
  1354. while (true)
  1355. {
  1356. Int64 processedInSize;
  1357. Int64 processedOutSize;
  1358. bool finished;
  1359. CodeOneBlock(out processedInSize, out processedOutSize, out finished);
  1360. if (finished)
  1361. {
  1362. return;
  1363. }
  1364. if (progress != null)
  1365. {
  1366. progress.SetProgress(processedInSize, processedOutSize);
  1367. }
  1368. }
  1369. }
  1370. finally
  1371. {
  1372. ReleaseStreams();
  1373. }
  1374. }
  1375. public long Code(Stream inStream, bool final)
  1376. {
  1377. _matchFinder.SetStream(inStream);
  1378. _processingMode = !final;
  1379. try
  1380. {
  1381. while (true)
  1382. {
  1383. Int64 processedInSize;
  1384. Int64 processedOutSize;
  1385. bool finished;
  1386. CodeOneBlock(out processedInSize, out processedOutSize, out finished);
  1387. if (finished)
  1388. {
  1389. return processedInSize;
  1390. }
  1391. }
  1392. }
  1393. finally
  1394. {
  1395. _matchFinder.ReleaseStream();
  1396. if (final)
  1397. {
  1398. ReleaseStreams();
  1399. }
  1400. }
  1401. }
  1402. public void Train(Stream trainStream)
  1403. {
  1404. if (_nowPos64 > 0)
  1405. {
  1406. throw new InvalidOperationException();
  1407. }
  1408. _trainSize = (uint)trainStream.Length;
  1409. if (_trainSize > 0)
  1410. {
  1411. _matchFinder.SetStream(trainStream);
  1412. for (; _trainSize > 0 && !_matchFinder.IsDataStarved; _trainSize--)
  1413. {
  1414. _matchFinder.Skip(1);
  1415. }
  1416. if (_trainSize == 0)
  1417. {
  1418. _previousByte = _matchFinder.GetIndexByte(-1);
  1419. }
  1420. _matchFinder.ReleaseStream();
  1421. }
  1422. }
  1423. private const int K_PROP_SIZE = 5;
  1424. private readonly Byte[] _properties = new Byte[K_PROP_SIZE];
  1425. public void WriteCoderProperties(Stream outStream)
  1426. {
  1427. _properties[0] = (Byte)((_posStateBits * 5 + _numLiteralPosStateBits) * 9 + _numLiteralContextBits);
  1428. for (int i = 0; i < 4; i++)
  1429. {
  1430. _properties[1 + i] = (Byte)((_dictionarySize >> (8 * i)) & 0xFF);
  1431. }
  1432. outStream.Write(_properties, 0, K_PROP_SIZE);
  1433. }
  1434. private readonly UInt32[] _tempPrices = new UInt32[Base.K_NUM_FULL_DISTANCES];
  1435. private UInt32 _matchPriceCount;
  1436. private void FillDistancesPrices()
  1437. {
  1438. for (UInt32 i = Base.K_START_POS_MODEL_INDEX; i < Base.K_NUM_FULL_DISTANCES; i++)
  1439. {
  1440. UInt32 posSlot = GetPosSlot(i);
  1441. int footerBits = (int)((posSlot >> 1) - 1);
  1442. UInt32 baseVal = ((2 | (posSlot & 1)) << footerBits);
  1443. _tempPrices[i] = BitTreeEncoder.ReverseGetPrice(_posEncoders,
  1444. baseVal - posSlot - 1, footerBits, i - baseVal);
  1445. }
  1446. for (UInt32 lenToPosState = 0; lenToPosState < Base.K_NUM_LEN_TO_POS_STATES; lenToPosState++)
  1447. {
  1448. UInt32 posSlot;
  1449. BitTreeEncoder encoder = _posSlotEncoder[lenToPosState];
  1450. UInt32 st = (lenToPosState << Base.K_NUM_POS_SLOT_BITS);
  1451. for (posSlot = 0; posSlot < _distTableSize; posSlot++)
  1452. {
  1453. _posSlotPrices[st + posSlot] = encoder.GetPrice(posSlot);
  1454. }
  1455. for (posSlot = Base.K_END_POS_MODEL_INDEX; posSlot < _distTableSize; posSlot++)
  1456. {
  1457. _posSlotPrices[st + posSlot] += ((((posSlot >> 1) - 1) - Base.K_NUM_ALIGN_BITS) <<
  1458. BitEncoder.K_NUM_BIT_PRICE_SHIFT_BITS);
  1459. }
  1460. UInt32 st2 = lenToPosState * Base.K_NUM_FULL_DISTANCES;
  1461. UInt32 i;
  1462. for (i = 0; i < Base.K_START_POS_MODEL_INDEX; i++)
  1463. {
  1464. _distancesPrices[st2 + i] = _posSlotPrices[st + i];
  1465. }
  1466. for (; i < Base.K_NUM_FULL_DISTANCES; i++)
  1467. {
  1468. _distancesPrices[st2 + i] = _posSlotPrices[st + GetPosSlot(i)] + _tempPrices[i];
  1469. }
  1470. }
  1471. _matchPriceCount = 0;
  1472. }
  1473. private void FillAlignPrices()
  1474. {
  1475. for (UInt32 i = 0; i < Base.K_ALIGN_TABLE_SIZE; i++)
  1476. {
  1477. _alignPrices[i] = _posAlignEncoder.ReverseGetPrice(i);
  1478. }
  1479. _alignPriceCount = 0;
  1480. }
  1481. private static readonly string[] K_MATCH_FINDER_I_DS =
  1482. {
  1483. "BT2",
  1484. "BT4"
  1485. };
  1486. private static int FindMatchFinder(string s)
  1487. {
  1488. for (int m = 0; m < K_MATCH_FINDER_I_DS.Length; m++)
  1489. {
  1490. if (s == K_MATCH_FINDER_I_DS[m])
  1491. {
  1492. return m;
  1493. }
  1494. }
  1495. return -1;
  1496. }
  1497. public void SetCoderProperties(CoderPropId[] propIDs, object[] properties)
  1498. {
  1499. for (UInt32 i = 0; i < properties.Length; i++)
  1500. {
  1501. object prop = properties[i];
  1502. switch (propIDs[i])
  1503. {
  1504. case CoderPropId.NumFastBytes:
  1505. {
  1506. if (!(prop is Int32))
  1507. {
  1508. throw new InvalidParamException();
  1509. }
  1510. Int32 numFastBytes = (Int32)prop;
  1511. if (numFastBytes < 5 || numFastBytes > Base.K_MATCH_MAX_LEN)
  1512. {
  1513. throw new InvalidParamException();
  1514. }
  1515. _numFastBytes = (UInt32)numFastBytes;
  1516. break;
  1517. }
  1518. case CoderPropId.Algorithm:
  1519. {
  1520. /*
  1521. if (!(prop is Int32))
  1522. throw new InvalidParamException();
  1523. Int32 maximize = (Int32)prop;
  1524. _fastMode = (maximize == 0);
  1525. _maxMode = (maximize >= 2);
  1526. */
  1527. break;
  1528. }
  1529. case CoderPropId.MatchFinder:
  1530. {
  1531. if (!(prop is String))
  1532. {
  1533. throw new InvalidParamException();
  1534. }
  1535. EMatchFinderType matchFinderIndexPrev = _matchFinderType;
  1536. int m = FindMatchFinder(((string)prop).ToUpper());
  1537. if (m < 0)
  1538. {
  1539. throw new InvalidParamException();
  1540. }
  1541. _matchFinderType = (EMatchFinderType)m;
  1542. if (_matchFinder != null && matchFinderIndexPrev != _matchFinderType)
  1543. {
  1544. _dictionarySizePrev = 0xFFFFFFFF;
  1545. _matchFinder = null;
  1546. }
  1547. break;
  1548. }
  1549. case CoderPropId.DictionarySize:
  1550. {
  1551. const int kDicLogSizeMaxCompress = 30;
  1552. if (!(prop is Int32))
  1553. {
  1554. throw new InvalidParamException();
  1555. }
  1556. ;
  1557. Int32 dictionarySize = (Int32)prop;
  1558. if (dictionarySize < (UInt32)(1 << Base.K_DIC_LOG_SIZE_MIN) ||
  1559. dictionarySize > (UInt32)(1 << kDicLogSizeMaxCompress))
  1560. {
  1561. throw new InvalidParamException();
  1562. }
  1563. _dictionarySize = (UInt32)dictionarySize;
  1564. int dicLogSize;
  1565. for (dicLogSize = 0; dicLogSize < (UInt32)kDicLogSizeMaxCompress; dicLogSize++)
  1566. {
  1567. if (dictionarySize <= ((UInt32)(1) << dicLogSize))
  1568. {
  1569. break;
  1570. }
  1571. }
  1572. _distTableSize = (UInt32)dicLogSize * 2;
  1573. break;
  1574. }
  1575. case CoderPropId.PosStateBits:
  1576. {
  1577. if (!(prop is Int32))
  1578. {
  1579. throw new InvalidParamException();
  1580. }
  1581. Int32 v = (Int32)prop;
  1582. if (v < 0 || v > (UInt32)Base.K_NUM_POS_STATES_BITS_ENCODING_MAX)
  1583. {
  1584. throw new InvalidParamException();
  1585. }
  1586. _posStateBits = v;
  1587. _posStateMask = (((UInt32)1) << _posStateBits) - 1;
  1588. break;
  1589. }
  1590. case CoderPropId.LitPosBits:
  1591. {
  1592. if (!(prop is Int32))
  1593. {
  1594. throw new InvalidParamException();
  1595. }
  1596. Int32 v = (Int32)prop;
  1597. if (v < 0 || v > Base.K_NUM_LIT_POS_STATES_BITS_ENCODING_MAX)
  1598. {
  1599. throw new InvalidParamException();
  1600. }
  1601. _numLiteralPosStateBits = v;
  1602. break;
  1603. }
  1604. case CoderPropId.LitContextBits:
  1605. {
  1606. if (!(prop is Int32))
  1607. {
  1608. throw new InvalidParamException();
  1609. }
  1610. Int32 v = (Int32)prop;
  1611. if (v < 0 || v > Base.K_NUM_LIT_CONTEXT_BITS_MAX)
  1612. {
  1613. throw new InvalidParamException();
  1614. }
  1615. ;
  1616. _numLiteralContextBits = v;
  1617. break;
  1618. }
  1619. case CoderPropId.EndMarker:
  1620. {
  1621. if (!(prop is Boolean))
  1622. {
  1623. throw new InvalidParamException();
  1624. }
  1625. SetWriteEndMarkerMode((Boolean)prop);
  1626. break;
  1627. }
  1628. default:
  1629. throw new InvalidParamException();
  1630. }
  1631. }
  1632. }
  1633. private uint _trainSize;
  1634. public void SetTrainSize(uint trainSize)
  1635. {
  1636. _trainSize = trainSize;
  1637. }
  1638. }
  1639. }