LzBinTree.cs 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424
  1. using System;
  2. using System.IO;
  3. namespace SharpCompress.Compressors.LZMA.LZ
  4. {
  5. internal class BinTree : InWindow
  6. {
  7. private UInt32 _cyclicBufferPos;
  8. private UInt32 _cyclicBufferSize;
  9. private UInt32 _matchMaxLen;
  10. private UInt32[] _son;
  11. private UInt32[] _hash;
  12. private UInt32 _cutValue = 0xFF;
  13. private UInt32 _hashMask;
  14. private UInt32 _hashSizeSum;
  15. private bool _hashArray = true;
  16. private const UInt32 K_HASH2_SIZE = 1 << 10;
  17. private const UInt32 K_HASH3_SIZE = 1 << 16;
  18. private const UInt32 K_BT2_HASH_SIZE = 1 << 16;
  19. private const UInt32 K_START_MAX_LEN = 1;
  20. private const UInt32 K_HASH3_OFFSET = K_HASH2_SIZE;
  21. private const UInt32 K_EMPTY_HASH_VALUE = 0;
  22. private const UInt32 K_MAX_VAL_FOR_NORMALIZE = ((UInt32)1 << 31) - 1;
  23. private UInt32 _kNumHashDirectBytes;
  24. private UInt32 _kMinMatchCheck = 4;
  25. private UInt32 _kFixHashSize = K_HASH2_SIZE + K_HASH3_SIZE;
  26. public void SetType(int numHashBytes)
  27. {
  28. _hashArray = (numHashBytes > 2);
  29. if (_hashArray)
  30. {
  31. _kNumHashDirectBytes = 0;
  32. _kMinMatchCheck = 4;
  33. _kFixHashSize = K_HASH2_SIZE + K_HASH3_SIZE;
  34. }
  35. else
  36. {
  37. _kNumHashDirectBytes = 2;
  38. _kMinMatchCheck = 2 + 1;
  39. _kFixHashSize = 0;
  40. }
  41. }
  42. public new void SetStream(Stream stream)
  43. {
  44. base.SetStream(stream);
  45. }
  46. public new void ReleaseStream()
  47. {
  48. base.ReleaseStream();
  49. }
  50. public new void Init()
  51. {
  52. base.Init();
  53. for (UInt32 i = 0; i < _hashSizeSum; i++)
  54. {
  55. _hash[i] = K_EMPTY_HASH_VALUE;
  56. }
  57. _cyclicBufferPos = 0;
  58. ReduceOffsets(-1);
  59. }
  60. public new void MovePos()
  61. {
  62. if (++_cyclicBufferPos >= _cyclicBufferSize)
  63. {
  64. _cyclicBufferPos = 0;
  65. }
  66. base.MovePos();
  67. if (_pos == K_MAX_VAL_FOR_NORMALIZE)
  68. {
  69. Normalize();
  70. }
  71. }
  72. public new Byte GetIndexByte(Int32 index)
  73. {
  74. return base.GetIndexByte(index);
  75. }
  76. public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit)
  77. {
  78. return base.GetMatchLen(index, distance, limit);
  79. }
  80. public new UInt32 GetNumAvailableBytes()
  81. {
  82. return base.GetNumAvailableBytes();
  83. }
  84. public void Create(UInt32 historySize, UInt32 keepAddBufferBefore,
  85. UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
  86. {
  87. if (historySize > K_MAX_VAL_FOR_NORMALIZE - 256)
  88. {
  89. throw new Exception();
  90. }
  91. _cutValue = 16 + (matchMaxLen >> 1);
  92. UInt32 windowReservSize = (historySize + keepAddBufferBefore +
  93. matchMaxLen + keepAddBufferAfter) / 2 + 256;
  94. base.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize);
  95. _matchMaxLen = matchMaxLen;
  96. UInt32 cyclicBufferSize = historySize + 1;
  97. if (_cyclicBufferSize != cyclicBufferSize)
  98. {
  99. _son = new UInt32[(_cyclicBufferSize = cyclicBufferSize) * 2];
  100. }
  101. UInt32 hs = K_BT2_HASH_SIZE;
  102. if (_hashArray)
  103. {
  104. hs = historySize - 1;
  105. hs |= (hs >> 1);
  106. hs |= (hs >> 2);
  107. hs |= (hs >> 4);
  108. hs |= (hs >> 8);
  109. hs >>= 1;
  110. hs |= 0xFFFF;
  111. if (hs > (1 << 24))
  112. {
  113. hs >>= 1;
  114. }
  115. _hashMask = hs;
  116. hs++;
  117. hs += _kFixHashSize;
  118. }
  119. if (hs != _hashSizeSum)
  120. {
  121. _hash = new UInt32[_hashSizeSum = hs];
  122. }
  123. }
  124. public UInt32 GetMatches(UInt32[] distances)
  125. {
  126. UInt32 lenLimit;
  127. if (_pos + _matchMaxLen <= _streamPos)
  128. {
  129. lenLimit = _matchMaxLen;
  130. }
  131. else
  132. {
  133. lenLimit = _streamPos - _pos;
  134. if (lenLimit < _kMinMatchCheck)
  135. {
  136. MovePos();
  137. return 0;
  138. }
  139. }
  140. UInt32 offset = 0;
  141. UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
  142. UInt32 cur = _bufferOffset + _pos;
  143. UInt32 maxLen = K_START_MAX_LEN; // to avoid items for len < hashSize;
  144. UInt32 hashValue, hash2Value = 0, hash3Value = 0;
  145. if (_hashArray)
  146. {
  147. UInt32 temp = Crc.TABLE[_bufferBase[cur]] ^ _bufferBase[cur + 1];
  148. hash2Value = temp & (K_HASH2_SIZE - 1);
  149. temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
  150. hash3Value = temp & (K_HASH3_SIZE - 1);
  151. hashValue = (temp ^ (Crc.TABLE[_bufferBase[cur + 3]] << 5)) & _hashMask;
  152. }
  153. else
  154. {
  155. hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8);
  156. }
  157. UInt32 curMatch = _hash[_kFixHashSize + hashValue];
  158. if (_hashArray)
  159. {
  160. UInt32 curMatch2 = _hash[hash2Value];
  161. UInt32 curMatch3 = _hash[K_HASH3_OFFSET + hash3Value];
  162. _hash[hash2Value] = _pos;
  163. _hash[K_HASH3_OFFSET + hash3Value] = _pos;
  164. if (curMatch2 > matchMinPos)
  165. {
  166. if (_bufferBase[_bufferOffset + curMatch2] == _bufferBase[cur])
  167. {
  168. distances[offset++] = maxLen = 2;
  169. distances[offset++] = _pos - curMatch2 - 1;
  170. }
  171. }
  172. if (curMatch3 > matchMinPos)
  173. {
  174. if (_bufferBase[_bufferOffset + curMatch3] == _bufferBase[cur])
  175. {
  176. if (curMatch3 == curMatch2)
  177. {
  178. offset -= 2;
  179. }
  180. distances[offset++] = maxLen = 3;
  181. distances[offset++] = _pos - curMatch3 - 1;
  182. curMatch2 = curMatch3;
  183. }
  184. }
  185. if (offset != 0 && curMatch2 == curMatch)
  186. {
  187. offset -= 2;
  188. maxLen = K_START_MAX_LEN;
  189. }
  190. }
  191. _hash[_kFixHashSize + hashValue] = _pos;
  192. UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
  193. UInt32 ptr1 = (_cyclicBufferPos << 1);
  194. UInt32 len0, len1;
  195. len0 = len1 = _kNumHashDirectBytes;
  196. if (_kNumHashDirectBytes != 0)
  197. {
  198. if (curMatch > matchMinPos)
  199. {
  200. if (_bufferBase[_bufferOffset + curMatch + _kNumHashDirectBytes] !=
  201. _bufferBase[cur + _kNumHashDirectBytes])
  202. {
  203. distances[offset++] = maxLen = _kNumHashDirectBytes;
  204. distances[offset++] = _pos - curMatch - 1;
  205. }
  206. }
  207. }
  208. UInt32 count = _cutValue;
  209. while (true)
  210. {
  211. if (curMatch <= matchMinPos || count-- == 0)
  212. {
  213. _son[ptr0] = _son[ptr1] = K_EMPTY_HASH_VALUE;
  214. break;
  215. }
  216. UInt32 delta = _pos - curMatch;
  217. UInt32 cyclicPos = ((delta <= _cyclicBufferPos)
  218. ? (_cyclicBufferPos - delta)
  219. : (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
  220. UInt32 pby1 = _bufferOffset + curMatch;
  221. UInt32 len = Math.Min(len0, len1);
  222. if (_bufferBase[pby1 + len] == _bufferBase[cur + len])
  223. {
  224. while (++len != lenLimit)
  225. {
  226. if (_bufferBase[pby1 + len] != _bufferBase[cur + len])
  227. {
  228. break;
  229. }
  230. }
  231. if (maxLen < len)
  232. {
  233. distances[offset++] = maxLen = len;
  234. distances[offset++] = delta - 1;
  235. if (len == lenLimit)
  236. {
  237. _son[ptr1] = _son[cyclicPos];
  238. _son[ptr0] = _son[cyclicPos + 1];
  239. break;
  240. }
  241. }
  242. }
  243. if (_bufferBase[pby1 + len] < _bufferBase[cur + len])
  244. {
  245. _son[ptr1] = curMatch;
  246. ptr1 = cyclicPos + 1;
  247. curMatch = _son[ptr1];
  248. len1 = len;
  249. }
  250. else
  251. {
  252. _son[ptr0] = curMatch;
  253. ptr0 = cyclicPos;
  254. curMatch = _son[ptr0];
  255. len0 = len;
  256. }
  257. }
  258. MovePos();
  259. return offset;
  260. }
  261. public void Skip(UInt32 num)
  262. {
  263. do
  264. {
  265. UInt32 lenLimit;
  266. if (_pos + _matchMaxLen <= _streamPos)
  267. {
  268. lenLimit = _matchMaxLen;
  269. }
  270. else
  271. {
  272. lenLimit = _streamPos - _pos;
  273. if (lenLimit < _kMinMatchCheck)
  274. {
  275. MovePos();
  276. continue;
  277. }
  278. }
  279. UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
  280. UInt32 cur = _bufferOffset + _pos;
  281. UInt32 hashValue;
  282. if (_hashArray)
  283. {
  284. UInt32 temp = Crc.TABLE[_bufferBase[cur]] ^ _bufferBase[cur + 1];
  285. UInt32 hash2Value = temp & (K_HASH2_SIZE - 1);
  286. _hash[hash2Value] = _pos;
  287. temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
  288. UInt32 hash3Value = temp & (K_HASH3_SIZE - 1);
  289. _hash[K_HASH3_OFFSET + hash3Value] = _pos;
  290. hashValue = (temp ^ (Crc.TABLE[_bufferBase[cur + 3]] << 5)) & _hashMask;
  291. }
  292. else
  293. {
  294. hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8);
  295. }
  296. UInt32 curMatch = _hash[_kFixHashSize + hashValue];
  297. _hash[_kFixHashSize + hashValue] = _pos;
  298. UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
  299. UInt32 ptr1 = (_cyclicBufferPos << 1);
  300. UInt32 len0, len1;
  301. len0 = len1 = _kNumHashDirectBytes;
  302. UInt32 count = _cutValue;
  303. while (true)
  304. {
  305. if (curMatch <= matchMinPos || count-- == 0)
  306. {
  307. _son[ptr0] = _son[ptr1] = K_EMPTY_HASH_VALUE;
  308. break;
  309. }
  310. UInt32 delta = _pos - curMatch;
  311. UInt32 cyclicPos = ((delta <= _cyclicBufferPos)
  312. ? (_cyclicBufferPos - delta)
  313. : (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
  314. UInt32 pby1 = _bufferOffset + curMatch;
  315. UInt32 len = Math.Min(len0, len1);
  316. if (_bufferBase[pby1 + len] == _bufferBase[cur + len])
  317. {
  318. while (++len != lenLimit)
  319. {
  320. if (_bufferBase[pby1 + len] != _bufferBase[cur + len])
  321. {
  322. break;
  323. }
  324. }
  325. if (len == lenLimit)
  326. {
  327. _son[ptr1] = _son[cyclicPos];
  328. _son[ptr0] = _son[cyclicPos + 1];
  329. break;
  330. }
  331. }
  332. if (_bufferBase[pby1 + len] < _bufferBase[cur + len])
  333. {
  334. _son[ptr1] = curMatch;
  335. ptr1 = cyclicPos + 1;
  336. curMatch = _son[ptr1];
  337. len1 = len;
  338. }
  339. else
  340. {
  341. _son[ptr0] = curMatch;
  342. ptr0 = cyclicPos;
  343. curMatch = _son[ptr0];
  344. len0 = len;
  345. }
  346. }
  347. MovePos();
  348. }
  349. while (--num != 0);
  350. }
  351. private void NormalizeLinks(UInt32[] items, UInt32 numItems, UInt32 subValue)
  352. {
  353. for (UInt32 i = 0; i < numItems; i++)
  354. {
  355. UInt32 value = items[i];
  356. if (value <= subValue)
  357. {
  358. value = K_EMPTY_HASH_VALUE;
  359. }
  360. else
  361. {
  362. value -= subValue;
  363. }
  364. items[i] = value;
  365. }
  366. }
  367. private void Normalize()
  368. {
  369. UInt32 subValue = _pos - _cyclicBufferSize;
  370. NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
  371. NormalizeLinks(_hash, _hashSizeSum, subValue);
  372. ReduceOffsets((Int32)subValue);
  373. }
  374. public void SetCutValue(UInt32 cutValue)
  375. {
  376. _cutValue = cutValue;
  377. }
  378. }
  379. }