CBZip2OutputStream.cs 57 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964
  1. using System.IO;
  2. /*
  3. * Copyright 2001,2004-2005 The Apache Software Foundation
  4. *
  5. * Licensed under the Apache License, Version 2.0 (the "License");
  6. * you may not use this file except in compliance with the License.
  7. * You may obtain a copy of the License at
  8. *
  9. * http://www.apache.org/licenses/LICENSE-2.0
  10. *
  11. * Unless required by applicable law or agreed to in writing, software
  12. * distributed under the License is distributed on an "AS IS" BASIS,
  13. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14. * See the License for the specific language governing permissions and
  15. * limitations under the License.
  16. */
  17. /*
  18. * This package is based on the work done by Keiron Liddle, Aftex Software
  19. * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
  20. * great code.
  21. */
  22. namespace SharpCompress.Compressors.BZip2
  23. {
  24. /**
  25. * An output stream that compresses into the BZip2 format (with the file
  26. * header chars) into another stream.
  27. *
  28. * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a>
  29. *
  30. * TODO: Update to BZip2 1.0.1
  31. * <b>NB:</b> note this class has been modified to add a leading BZ to the
  32. * start of the BZIP2 stream to make it compatible with other PGP programs.
  33. */
  34. internal class CBZip2OutputStream : Stream
  35. {
  36. protected const int SETMASK = (1 << 21);
  37. protected const int CLEARMASK = (~SETMASK);
  38. protected const int GREATER_ICOST = 15;
  39. protected const int LESSER_ICOST = 0;
  40. protected const int SMALL_THRESH = 20;
  41. protected const int DEPTH_THRESH = 10;
  42. /*
  43. If you are ever unlucky/improbable enough
  44. to get a stack overflow whilst sorting,
  45. increase the following constant and try
  46. again. In practice I have never seen the
  47. stack go above 27 elems, so the following
  48. limit seems very generous.
  49. */
  50. protected const int QSORT_STACK_SIZE = 1000;
  51. private bool finished;
  52. private static void Panic()
  53. {
  54. //System.out.Println("panic");
  55. //throw new CError();
  56. }
  57. private void MakeMaps()
  58. {
  59. int i;
  60. nInUse = 0;
  61. for (i = 0; i < 256; i++)
  62. {
  63. if (inUse[i])
  64. {
  65. seqToUnseq[nInUse] = (char)i;
  66. unseqToSeq[i] = (char)nInUse;
  67. nInUse++;
  68. }
  69. }
  70. }
  71. protected static void HbMakeCodeLengths(char[] len, int[] freq,
  72. int alphaSize, int maxLen)
  73. {
  74. /*
  75. Nodes and heap entries run from 1. Entry 0
  76. for both the heap and nodes is a sentinel.
  77. */
  78. int nNodes, nHeap, n1, n2, i, j, k;
  79. bool tooLong;
  80. int[] heap = new int[BZip2Constants.MAX_ALPHA_SIZE + 2];
  81. int[] weight = new int[BZip2Constants.MAX_ALPHA_SIZE * 2];
  82. int[] parent = new int[BZip2Constants.MAX_ALPHA_SIZE * 2];
  83. for (i = 0; i < alphaSize; i++)
  84. {
  85. weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
  86. }
  87. while (true)
  88. {
  89. nNodes = alphaSize;
  90. nHeap = 0;
  91. heap[0] = 0;
  92. weight[0] = 0;
  93. parent[0] = -2;
  94. for (i = 1; i <= alphaSize; i++)
  95. {
  96. parent[i] = -1;
  97. nHeap++;
  98. heap[nHeap] = i;
  99. {
  100. int zz, tmp;
  101. zz = nHeap;
  102. tmp = heap[zz];
  103. while (weight[tmp] < weight[heap[zz >> 1]])
  104. {
  105. heap[zz] = heap[zz >> 1];
  106. zz >>= 1;
  107. }
  108. heap[zz] = tmp;
  109. }
  110. }
  111. if (!(nHeap < (BZip2Constants.MAX_ALPHA_SIZE + 2)))
  112. {
  113. Panic();
  114. }
  115. while (nHeap > 1)
  116. {
  117. n1 = heap[1];
  118. heap[1] = heap[nHeap];
  119. nHeap--;
  120. {
  121. int zz = 0, yy = 0, tmp = 0;
  122. zz = 1;
  123. tmp = heap[zz];
  124. while (true)
  125. {
  126. yy = zz << 1;
  127. if (yy > nHeap)
  128. {
  129. break;
  130. }
  131. if (yy < nHeap
  132. && weight[heap[yy + 1]] < weight[heap[yy]])
  133. {
  134. yy++;
  135. }
  136. if (weight[tmp] < weight[heap[yy]])
  137. {
  138. break;
  139. }
  140. heap[zz] = heap[yy];
  141. zz = yy;
  142. }
  143. heap[zz] = tmp;
  144. }
  145. n2 = heap[1];
  146. heap[1] = heap[nHeap];
  147. nHeap--;
  148. {
  149. int zz = 0, yy = 0, tmp = 0;
  150. zz = 1;
  151. tmp = heap[zz];
  152. while (true)
  153. {
  154. yy = zz << 1;
  155. if (yy > nHeap)
  156. {
  157. break;
  158. }
  159. if (yy < nHeap
  160. && weight[heap[yy + 1]] < weight[heap[yy]])
  161. {
  162. yy++;
  163. }
  164. if (weight[tmp] < weight[heap[yy]])
  165. {
  166. break;
  167. }
  168. heap[zz] = heap[yy];
  169. zz = yy;
  170. }
  171. heap[zz] = tmp;
  172. }
  173. nNodes++;
  174. parent[n1] = parent[n2] = nNodes;
  175. weight[nNodes] = (int)((uint)((weight[n1] & 0xffffff00)
  176. + (weight[n2] & 0xffffff00))
  177. | (uint)(1 + (((weight[n1] & 0x000000ff) >
  178. (weight[n2] & 0x000000ff))
  179. ? (weight[n1] & 0x000000ff)
  180. : (weight[n2] & 0x000000ff))));
  181. parent[nNodes] = -1;
  182. nHeap++;
  183. heap[nHeap] = nNodes;
  184. {
  185. int zz = 0, tmp = 0;
  186. zz = nHeap;
  187. tmp = heap[zz];
  188. while (weight[tmp] < weight[heap[zz >> 1]])
  189. {
  190. heap[zz] = heap[zz >> 1];
  191. zz >>= 1;
  192. }
  193. heap[zz] = tmp;
  194. }
  195. }
  196. if (!(nNodes < (BZip2Constants.MAX_ALPHA_SIZE * 2)))
  197. {
  198. Panic();
  199. }
  200. tooLong = false;
  201. for (i = 1; i <= alphaSize; i++)
  202. {
  203. j = 0;
  204. k = i;
  205. while (parent[k] >= 0)
  206. {
  207. k = parent[k];
  208. j++;
  209. }
  210. len[i - 1] = (char)j;
  211. if (j > maxLen)
  212. {
  213. tooLong = true;
  214. }
  215. }
  216. if (!tooLong)
  217. {
  218. break;
  219. }
  220. for (i = 1; i < alphaSize; i++)
  221. {
  222. j = weight[i] >> 8;
  223. j = 1 + (j / 2);
  224. weight[i] = j << 8;
  225. }
  226. }
  227. }
  228. /*
  229. index of the last char in the block, so
  230. the block size == last + 1.
  231. */
  232. private int last;
  233. /*
  234. index in zptr[] of original string after sorting.
  235. */
  236. private int origPtr;
  237. /*
  238. always: in the range 0 .. 9.
  239. The current block size is 100000 * this number.
  240. */
  241. private readonly int blockSize100k;
  242. private bool blockRandomised;
  243. private int bytesOut;
  244. private int bsBuff;
  245. private int bsLive;
  246. private readonly CRC mCrc = new CRC();
  247. private readonly bool[] inUse = new bool[256];
  248. private int nInUse;
  249. private readonly char[] seqToUnseq = new char[256];
  250. private readonly char[] unseqToSeq = new char[256];
  251. private readonly char[] selector = new char[BZip2Constants.MAX_SELECTORS];
  252. private readonly char[] selectorMtf = new char[BZip2Constants.MAX_SELECTORS];
  253. private char[] block;
  254. private int[] quadrant;
  255. private int[] zptr;
  256. private short[] szptr;
  257. private int[] ftab;
  258. private int nMTF;
  259. private readonly int[] mtfFreq = new int[BZip2Constants.MAX_ALPHA_SIZE];
  260. /*
  261. * Used when sorting. If too many long comparisons
  262. * happen, we stop sorting, randomise the block
  263. * slightly, and try again.
  264. */
  265. private readonly int workFactor;
  266. private int workDone;
  267. private int workLimit;
  268. private bool firstAttempt;
  269. private int nBlocksRandomised;
  270. private int currentChar = -1;
  271. private int runLength;
  272. public CBZip2OutputStream(Stream inStream)
  273. : this(inStream, 9)
  274. {
  275. }
  276. public CBZip2OutputStream(Stream inStream, int inBlockSize)
  277. {
  278. block = null;
  279. quadrant = null;
  280. zptr = null;
  281. ftab = null;
  282. inStream.WriteByte((byte)'B');
  283. inStream.WriteByte((byte)'Z');
  284. BsSetStream(inStream);
  285. workFactor = 50;
  286. if (inBlockSize > 9)
  287. {
  288. inBlockSize = 9;
  289. }
  290. if (inBlockSize < 1)
  291. {
  292. inBlockSize = 1;
  293. }
  294. blockSize100k = inBlockSize;
  295. AllocateCompressStructures();
  296. Initialize();
  297. InitBlock();
  298. }
  299. /**
  300. *
  301. * modified by Oliver Merkel, 010128
  302. *
  303. */
  304. public override void WriteByte(byte bv)
  305. {
  306. int b = (256 + bv) % 256;
  307. if (currentChar != -1)
  308. {
  309. if (currentChar == b)
  310. {
  311. runLength++;
  312. if (runLength > 254)
  313. {
  314. WriteRun();
  315. currentChar = -1;
  316. runLength = 0;
  317. }
  318. }
  319. else
  320. {
  321. WriteRun();
  322. runLength = 1;
  323. currentChar = b;
  324. }
  325. }
  326. else
  327. {
  328. currentChar = b;
  329. runLength++;
  330. }
  331. }
  332. private void WriteRun()
  333. {
  334. if (last < allowableBlockSize)
  335. {
  336. inUse[currentChar] = true;
  337. for (int i = 0; i < runLength; i++)
  338. {
  339. mCrc.UpdateCRC((char)currentChar);
  340. }
  341. switch (runLength)
  342. {
  343. case 1:
  344. last++;
  345. block[last + 1] = (char)currentChar;
  346. break;
  347. case 2:
  348. last++;
  349. block[last + 1] = (char)currentChar;
  350. last++;
  351. block[last + 1] = (char)currentChar;
  352. break;
  353. case 3:
  354. last++;
  355. block[last + 1] = (char)currentChar;
  356. last++;
  357. block[last + 1] = (char)currentChar;
  358. last++;
  359. block[last + 1] = (char)currentChar;
  360. break;
  361. default:
  362. inUse[runLength - 4] = true;
  363. last++;
  364. block[last + 1] = (char)currentChar;
  365. last++;
  366. block[last + 1] = (char)currentChar;
  367. last++;
  368. block[last + 1] = (char)currentChar;
  369. last++;
  370. block[last + 1] = (char)currentChar;
  371. last++;
  372. block[last + 1] = (char)(runLength - 4);
  373. break;
  374. }
  375. }
  376. else
  377. {
  378. EndBlock();
  379. InitBlock();
  380. WriteRun();
  381. }
  382. }
  383. private bool disposed;
  384. protected override void Dispose(bool disposing)
  385. {
  386. if (disposing)
  387. {
  388. if (disposed)
  389. {
  390. return;
  391. }
  392. Finish();
  393. disposed = true;
  394. base.Dispose();
  395. bsStream?.Dispose();
  396. bsStream = null;
  397. }
  398. }
  399. public void Finish()
  400. {
  401. if (finished)
  402. {
  403. return;
  404. }
  405. if (runLength > 0)
  406. {
  407. WriteRun();
  408. }
  409. currentChar = -1;
  410. EndBlock();
  411. EndCompression();
  412. finished = true;
  413. Flush();
  414. }
  415. public override void Flush()
  416. {
  417. bsStream.Flush();
  418. }
  419. private int blockCRC, combinedCRC;
  420. private void Initialize()
  421. {
  422. bytesOut = 0;
  423. nBlocksRandomised = 0;
  424. /* Write `magic' bytes h indicating file-format == huffmanised,
  425. followed by a digit indicating blockSize100k.
  426. */
  427. BsPutUChar('h');
  428. BsPutUChar('0' + blockSize100k);
  429. combinedCRC = 0;
  430. }
  431. private int allowableBlockSize;
  432. private void InitBlock()
  433. {
  434. // blockNo++;
  435. mCrc.InitialiseCRC();
  436. last = -1;
  437. // ch = 0;
  438. for (int i = 0; i < 256; i++)
  439. {
  440. inUse[i] = false;
  441. }
  442. /* 20 is just a paranoia constant */
  443. allowableBlockSize = BZip2Constants.baseBlockSize * blockSize100k - 20;
  444. }
  445. private void EndBlock()
  446. {
  447. blockCRC = mCrc.GetFinalCRC();
  448. combinedCRC = (combinedCRC << 1) | (int)(((uint)combinedCRC) >> 31);
  449. combinedCRC ^= blockCRC;
  450. /* sort the block and establish posn of original string */
  451. DoReversibleTransformation();
  452. /*
  453. A 6-byte block header, the value chosen arbitrarily
  454. as 0x314159265359 :-). A 32 bit value does not really
  455. give a strong enough guarantee that the value will not
  456. appear by chance in the compressed datastream. Worst-case
  457. probability of this event, for a 900k block, is about
  458. 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
  459. For a compressed file of size 100Gb -- about 100000 blocks --
  460. only a 48-bit marker will do. NB: normal compression/
  461. decompression do *not* rely on these statistical properties.
  462. They are only important when trying to recover blocks from
  463. damaged files.
  464. */
  465. BsPutUChar(0x31);
  466. BsPutUChar(0x41);
  467. BsPutUChar(0x59);
  468. BsPutUChar(0x26);
  469. BsPutUChar(0x53);
  470. BsPutUChar(0x59);
  471. /* Now the block's CRC, so it is in a known place. */
  472. BsPutint(blockCRC);
  473. /* Now a single bit indicating randomisation. */
  474. if (blockRandomised)
  475. {
  476. BsW(1, 1);
  477. nBlocksRandomised++;
  478. }
  479. else
  480. {
  481. BsW(1, 0);
  482. }
  483. /* Finally, block's contents proper. */
  484. MoveToFrontCodeAndSend();
  485. }
  486. private void EndCompression()
  487. {
  488. /*
  489. Now another magic 48-bit number, 0x177245385090, to
  490. indicate the end of the last block. (Sqrt(pi), if
  491. you want to know. I did want to use e, but it contains
  492. too much repetition -- 27 18 28 18 28 46 -- for me
  493. to feel statistically comfortable. Call me paranoid.)
  494. */
  495. BsPutUChar(0x17);
  496. BsPutUChar(0x72);
  497. BsPutUChar(0x45);
  498. BsPutUChar(0x38);
  499. BsPutUChar(0x50);
  500. BsPutUChar(0x90);
  501. BsPutint(combinedCRC);
  502. BsFinishedWithStream();
  503. }
  504. private void HbAssignCodes(int[] code, char[] length, int minLen,
  505. int maxLen, int alphaSize)
  506. {
  507. int n, vec, i;
  508. vec = 0;
  509. for (n = minLen; n <= maxLen; n++)
  510. {
  511. for (i = 0; i < alphaSize; i++)
  512. {
  513. if (length[i] == n)
  514. {
  515. code[i] = vec;
  516. vec++;
  517. }
  518. }
  519. ;
  520. vec <<= 1;
  521. }
  522. }
  523. private void BsSetStream(Stream f)
  524. {
  525. bsStream = f;
  526. bsLive = 0;
  527. bsBuff = 0;
  528. bytesOut = 0;
  529. }
  530. private void BsFinishedWithStream()
  531. {
  532. while (bsLive > 0)
  533. {
  534. int ch = (bsBuff >> 24);
  535. try
  536. {
  537. bsStream.WriteByte((byte)ch); // write 8-bit
  538. }
  539. catch (IOException e)
  540. {
  541. throw e;
  542. }
  543. bsBuff <<= 8;
  544. bsLive -= 8;
  545. bytesOut++;
  546. }
  547. }
  548. private void BsW(int n, int v)
  549. {
  550. while (bsLive >= 8)
  551. {
  552. int ch = (bsBuff >> 24);
  553. try
  554. {
  555. bsStream.WriteByte((byte)ch); // write 8-bit
  556. }
  557. catch (IOException e)
  558. {
  559. throw e;
  560. }
  561. bsBuff <<= 8;
  562. bsLive -= 8;
  563. bytesOut++;
  564. }
  565. bsBuff |= (v << (32 - bsLive - n));
  566. bsLive += n;
  567. }
  568. private void BsPutUChar(int c)
  569. {
  570. BsW(8, c);
  571. }
  572. private void BsPutint(int u)
  573. {
  574. BsW(8, (u >> 24) & 0xff);
  575. BsW(8, (u >> 16) & 0xff);
  576. BsW(8, (u >> 8) & 0xff);
  577. BsW(8, u & 0xff);
  578. }
  579. private void BsPutIntVS(int numBits, int c)
  580. {
  581. BsW(numBits, c);
  582. }
  583. private void SendMTFValues()
  584. {
  585. char[][] len = CBZip2InputStream.InitCharArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE);
  586. int v, t, i, j, gs, ge, totc, bt, bc, iter;
  587. int nSelectors = 0, alphaSize, minLen, maxLen, selCtr;
  588. int nGroups; //, nBytes;
  589. alphaSize = nInUse + 2;
  590. for (t = 0; t < BZip2Constants.N_GROUPS; t++)
  591. {
  592. for (v = 0; v < alphaSize; v++)
  593. {
  594. len[t][v] = (char)GREATER_ICOST;
  595. }
  596. }
  597. /* Decide how many coding tables to use */
  598. if (nMTF <= 0)
  599. {
  600. Panic();
  601. }
  602. if (nMTF < 200)
  603. {
  604. nGroups = 2;
  605. }
  606. else if (nMTF < 600)
  607. {
  608. nGroups = 3;
  609. }
  610. else if (nMTF < 1200)
  611. {
  612. nGroups = 4;
  613. }
  614. else if (nMTF < 2400)
  615. {
  616. nGroups = 5;
  617. }
  618. else
  619. {
  620. nGroups = 6;
  621. }
  622. /* Generate an initial set of coding tables */
  623. {
  624. int nPart, remF, tFreq, aFreq;
  625. nPart = nGroups;
  626. remF = nMTF;
  627. gs = 0;
  628. while (nPart > 0)
  629. {
  630. tFreq = remF / nPart;
  631. ge = gs - 1;
  632. aFreq = 0;
  633. while (aFreq < tFreq && ge < alphaSize - 1)
  634. {
  635. ge++;
  636. aFreq += mtfFreq[ge];
  637. }
  638. if (ge > gs && nPart != nGroups && nPart != 1
  639. && ((nGroups - nPart) % 2 == 1))
  640. {
  641. aFreq -= mtfFreq[ge];
  642. ge--;
  643. }
  644. for (v = 0; v < alphaSize; v++)
  645. {
  646. if (v >= gs && v <= ge)
  647. {
  648. len[nPart - 1][v] = (char)LESSER_ICOST;
  649. }
  650. else
  651. {
  652. len[nPart - 1][v] = (char)GREATER_ICOST;
  653. }
  654. }
  655. nPart--;
  656. gs = ge + 1;
  657. remF -= aFreq;
  658. }
  659. }
  660. int[][] rfreq = CBZip2InputStream.InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE);
  661. int[] fave = new int[BZip2Constants.N_GROUPS];
  662. short[] cost = new short[BZip2Constants.N_GROUPS];
  663. /*
  664. Iterate up to N_ITERS times to improve the tables.
  665. */
  666. for (iter = 0; iter < BZip2Constants.N_ITERS; iter++)
  667. {
  668. for (t = 0; t < nGroups; t++)
  669. {
  670. fave[t] = 0;
  671. }
  672. for (t = 0; t < nGroups; t++)
  673. {
  674. for (v = 0; v < alphaSize; v++)
  675. {
  676. rfreq[t][v] = 0;
  677. }
  678. }
  679. nSelectors = 0;
  680. totc = 0;
  681. gs = 0;
  682. while (true)
  683. {
  684. /* Set group start & end marks. */
  685. if (gs >= nMTF)
  686. {
  687. break;
  688. }
  689. ge = gs + BZip2Constants.G_SIZE - 1;
  690. if (ge >= nMTF)
  691. {
  692. ge = nMTF - 1;
  693. }
  694. /*
  695. Calculate the cost of this group as coded
  696. by each of the coding tables.
  697. */
  698. for (t = 0; t < nGroups; t++)
  699. {
  700. cost[t] = 0;
  701. }
  702. if (nGroups == 6)
  703. {
  704. short cost0, cost1, cost2, cost3, cost4, cost5;
  705. cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
  706. for (i = gs; i <= ge; i++)
  707. {
  708. short icv = szptr[i];
  709. cost0 += (short)len[0][icv];
  710. cost1 += (short)len[1][icv];
  711. cost2 += (short)len[2][icv];
  712. cost3 += (short)len[3][icv];
  713. cost4 += (short)len[4][icv];
  714. cost5 += (short)len[5][icv];
  715. }
  716. cost[0] = cost0;
  717. cost[1] = cost1;
  718. cost[2] = cost2;
  719. cost[3] = cost3;
  720. cost[4] = cost4;
  721. cost[5] = cost5;
  722. }
  723. else
  724. {
  725. for (i = gs; i <= ge; i++)
  726. {
  727. short icv = szptr[i];
  728. for (t = 0; t < nGroups; t++)
  729. {
  730. cost[t] += (short)len[t][icv];
  731. }
  732. }
  733. }
  734. /*
  735. Find the coding table which is best for this group,
  736. and record its identity in the selector table.
  737. */
  738. bc = 999999999;
  739. bt = -1;
  740. for (t = 0; t < nGroups; t++)
  741. {
  742. if (cost[t] < bc)
  743. {
  744. bc = cost[t];
  745. bt = t;
  746. }
  747. }
  748. ;
  749. totc += bc;
  750. fave[bt]++;
  751. selector[nSelectors] = (char)bt;
  752. nSelectors++;
  753. /*
  754. Increment the symbol frequencies for the selected table.
  755. */
  756. for (i = gs; i <= ge; i++)
  757. {
  758. rfreq[bt][szptr[i]]++;
  759. }
  760. gs = ge + 1;
  761. }
  762. /*
  763. Recompute the tables based on the accumulated frequencies.
  764. */
  765. for (t = 0; t < nGroups; t++)
  766. {
  767. HbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20);
  768. }
  769. }
  770. rfreq = null;
  771. fave = null;
  772. cost = null;
  773. if (!(nGroups < 8))
  774. {
  775. Panic();
  776. }
  777. if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZip2Constants.G_SIZE))))
  778. {
  779. Panic();
  780. }
  781. /* Compute MTF values for the selectors. */
  782. {
  783. char[] pos = new char[BZip2Constants.N_GROUPS];
  784. char ll_i, tmp2, tmp;
  785. for (i = 0; i < nGroups; i++)
  786. {
  787. pos[i] = (char)i;
  788. }
  789. for (i = 0; i < nSelectors; i++)
  790. {
  791. ll_i = selector[i];
  792. j = 0;
  793. tmp = pos[j];
  794. while (ll_i != tmp)
  795. {
  796. j++;
  797. tmp2 = tmp;
  798. tmp = pos[j];
  799. pos[j] = tmp2;
  800. }
  801. pos[0] = tmp;
  802. selectorMtf[i] = (char)j;
  803. }
  804. }
  805. int[][] code = CBZip2InputStream.InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE);
  806. /* Assign actual codes for the tables. */
  807. for (t = 0; t < nGroups; t++)
  808. {
  809. minLen = 32;
  810. maxLen = 0;
  811. for (i = 0; i < alphaSize; i++)
  812. {
  813. if (len[t][i] > maxLen)
  814. {
  815. maxLen = len[t][i];
  816. }
  817. if (len[t][i] < minLen)
  818. {
  819. minLen = len[t][i];
  820. }
  821. }
  822. if (maxLen > 20)
  823. {
  824. Panic();
  825. }
  826. if (minLen < 1)
  827. {
  828. Panic();
  829. }
  830. HbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
  831. }
  832. /* Transmit the mapping table. */
  833. {
  834. bool[] inUse16 = new bool[16];
  835. for (i = 0; i < 16; i++)
  836. {
  837. inUse16[i] = false;
  838. for (j = 0; j < 16; j++)
  839. {
  840. if (inUse[i * 16 + j])
  841. {
  842. inUse16[i] = true;
  843. }
  844. }
  845. }
  846. //nBytes = bytesOut;
  847. for (i = 0; i < 16; i++)
  848. {
  849. if (inUse16[i])
  850. {
  851. BsW(1, 1);
  852. }
  853. else
  854. {
  855. BsW(1, 0);
  856. }
  857. }
  858. for (i = 0; i < 16; i++)
  859. {
  860. if (inUse16[i])
  861. {
  862. for (j = 0; j < 16; j++)
  863. {
  864. if (inUse[i * 16 + j])
  865. {
  866. BsW(1, 1);
  867. }
  868. else
  869. {
  870. BsW(1, 0);
  871. }
  872. }
  873. }
  874. }
  875. }
  876. /* Now the selectors. */
  877. //nBytes = bytesOut;
  878. BsW(3, nGroups);
  879. BsW(15, nSelectors);
  880. for (i = 0; i < nSelectors; i++)
  881. {
  882. for (j = 0; j < selectorMtf[i]; j++)
  883. {
  884. BsW(1, 1);
  885. }
  886. BsW(1, 0);
  887. }
  888. /* Now the coding tables. */
  889. //nBytes = bytesOut;
  890. for (t = 0; t < nGroups; t++)
  891. {
  892. int curr = len[t][0];
  893. BsW(5, curr);
  894. for (i = 0; i < alphaSize; i++)
  895. {
  896. while (curr < len[t][i])
  897. {
  898. BsW(2, 2);
  899. curr++; /* 10 */
  900. }
  901. while (curr > len[t][i])
  902. {
  903. BsW(2, 3);
  904. curr--; /* 11 */
  905. }
  906. BsW(1, 0);
  907. }
  908. }
  909. /* And finally, the block data proper */
  910. //nBytes = bytesOut;
  911. selCtr = 0;
  912. gs = 0;
  913. while (true)
  914. {
  915. if (gs >= nMTF)
  916. {
  917. break;
  918. }
  919. ge = gs + BZip2Constants.G_SIZE - 1;
  920. if (ge >= nMTF)
  921. {
  922. ge = nMTF - 1;
  923. }
  924. for (i = gs; i <= ge; i++)
  925. {
  926. BsW(len[selector[selCtr]][szptr[i]],
  927. code[selector[selCtr]][szptr[i]]);
  928. }
  929. gs = ge + 1;
  930. selCtr++;
  931. }
  932. if (!(selCtr == nSelectors))
  933. {
  934. Panic();
  935. }
  936. }
  937. private void MoveToFrontCodeAndSend()
  938. {
  939. BsPutIntVS(24, origPtr);
  940. GenerateMTFValues();
  941. SendMTFValues();
  942. }
  943. private Stream bsStream;
  944. private void SimpleSort(int lo, int hi, int d)
  945. {
  946. int i, j, h, bigN, hp;
  947. int v;
  948. bigN = hi - lo + 1;
  949. if (bigN < 2)
  950. {
  951. return;
  952. }
  953. hp = 0;
  954. while (incs[hp] < bigN)
  955. {
  956. hp++;
  957. }
  958. hp--;
  959. for (; hp >= 0; hp--)
  960. {
  961. h = incs[hp];
  962. i = lo + h;
  963. while (true)
  964. {
  965. /* copy 1 */
  966. if (i > hi)
  967. {
  968. break;
  969. }
  970. v = zptr[i];
  971. j = i;
  972. while (FullGtU(zptr[j - h] + d, v + d))
  973. {
  974. zptr[j] = zptr[j - h];
  975. j = j - h;
  976. if (j <= (lo + h - 1))
  977. {
  978. break;
  979. }
  980. }
  981. zptr[j] = v;
  982. i++;
  983. /* copy 2 */
  984. if (i > hi)
  985. {
  986. break;
  987. }
  988. v = zptr[i];
  989. j = i;
  990. while (FullGtU(zptr[j - h] + d, v + d))
  991. {
  992. zptr[j] = zptr[j - h];
  993. j = j - h;
  994. if (j <= (lo + h - 1))
  995. {
  996. break;
  997. }
  998. }
  999. zptr[j] = v;
  1000. i++;
  1001. /* copy 3 */
  1002. if (i > hi)
  1003. {
  1004. break;
  1005. }
  1006. v = zptr[i];
  1007. j = i;
  1008. while (FullGtU(zptr[j - h] + d, v + d))
  1009. {
  1010. zptr[j] = zptr[j - h];
  1011. j = j - h;
  1012. if (j <= (lo + h - 1))
  1013. {
  1014. break;
  1015. }
  1016. }
  1017. zptr[j] = v;
  1018. i++;
  1019. if (workDone > workLimit && firstAttempt)
  1020. {
  1021. return;
  1022. }
  1023. }
  1024. }
  1025. }
  1026. private void Vswap(int p1, int p2, int n)
  1027. {
  1028. int temp = 0;
  1029. while (n > 0)
  1030. {
  1031. temp = zptr[p1];
  1032. zptr[p1] = zptr[p2];
  1033. zptr[p2] = temp;
  1034. p1++;
  1035. p2++;
  1036. n--;
  1037. }
  1038. }
  1039. private char Med3(char a, char b, char c)
  1040. {
  1041. char t;
  1042. if (a > b)
  1043. {
  1044. t = a;
  1045. a = b;
  1046. b = t;
  1047. }
  1048. if (b > c)
  1049. {
  1050. t = b;
  1051. b = c;
  1052. c = t;
  1053. }
  1054. if (a > b)
  1055. {
  1056. b = a;
  1057. }
  1058. return b;
  1059. }
  1060. internal class StackElem
  1061. {
  1062. internal int ll;
  1063. internal int hh;
  1064. internal int dd;
  1065. }
  1066. private void QSort3(int loSt, int hiSt, int dSt)
  1067. {
  1068. int unLo, unHi, ltLo, gtHi, med, n, m;
  1069. int sp, lo, hi, d;
  1070. StackElem[] stack = new StackElem[QSORT_STACK_SIZE];
  1071. for (int count = 0; count < QSORT_STACK_SIZE; count++)
  1072. {
  1073. stack[count] = new StackElem();
  1074. }
  1075. sp = 0;
  1076. stack[sp].ll = loSt;
  1077. stack[sp].hh = hiSt;
  1078. stack[sp].dd = dSt;
  1079. sp++;
  1080. while (sp > 0)
  1081. {
  1082. if (sp >= QSORT_STACK_SIZE)
  1083. {
  1084. Panic();
  1085. }
  1086. sp--;
  1087. lo = stack[sp].ll;
  1088. hi = stack[sp].hh;
  1089. d = stack[sp].dd;
  1090. if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH)
  1091. {
  1092. SimpleSort(lo, hi, d);
  1093. if (workDone > workLimit && firstAttempt)
  1094. {
  1095. return;
  1096. }
  1097. continue;
  1098. }
  1099. med = Med3(block[zptr[lo] + d + 1],
  1100. block[zptr[hi] + d + 1],
  1101. block[zptr[(lo + hi) >> 1] + d + 1]);
  1102. unLo = ltLo = lo;
  1103. unHi = gtHi = hi;
  1104. while (true)
  1105. {
  1106. while (true)
  1107. {
  1108. if (unLo > unHi)
  1109. {
  1110. break;
  1111. }
  1112. n = block[zptr[unLo] + d + 1] - med;
  1113. if (n == 0)
  1114. {
  1115. int temp = 0;
  1116. temp = zptr[unLo];
  1117. zptr[unLo] = zptr[ltLo];
  1118. zptr[ltLo] = temp;
  1119. ltLo++;
  1120. unLo++;
  1121. continue;
  1122. }
  1123. ;
  1124. if (n > 0)
  1125. {
  1126. break;
  1127. }
  1128. unLo++;
  1129. }
  1130. while (true)
  1131. {
  1132. if (unLo > unHi)
  1133. {
  1134. break;
  1135. }
  1136. n = block[zptr[unHi] + d + 1] - med;
  1137. if (n == 0)
  1138. {
  1139. int temp = 0;
  1140. temp = zptr[unHi];
  1141. zptr[unHi] = zptr[gtHi];
  1142. zptr[gtHi] = temp;
  1143. gtHi--;
  1144. unHi--;
  1145. continue;
  1146. }
  1147. ;
  1148. if (n < 0)
  1149. {
  1150. break;
  1151. }
  1152. unHi--;
  1153. }
  1154. if (unLo > unHi)
  1155. {
  1156. break;
  1157. }
  1158. int tempx = zptr[unLo];
  1159. zptr[unLo] = zptr[unHi];
  1160. zptr[unHi] = tempx;
  1161. unLo++;
  1162. unHi--;
  1163. }
  1164. if (gtHi < ltLo)
  1165. {
  1166. stack[sp].ll = lo;
  1167. stack[sp].hh = hi;
  1168. stack[sp].dd = d + 1;
  1169. sp++;
  1170. continue;
  1171. }
  1172. n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo) : (unLo - ltLo);
  1173. Vswap(lo, unLo - n, n);
  1174. m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi) : (gtHi - unHi);
  1175. Vswap(unLo, hi - m + 1, m);
  1176. n = lo + unLo - ltLo - 1;
  1177. m = hi - (gtHi - unHi) + 1;
  1178. stack[sp].ll = lo;
  1179. stack[sp].hh = n;
  1180. stack[sp].dd = d;
  1181. sp++;
  1182. stack[sp].ll = n + 1;
  1183. stack[sp].hh = m - 1;
  1184. stack[sp].dd = d + 1;
  1185. sp++;
  1186. stack[sp].ll = m;
  1187. stack[sp].hh = hi;
  1188. stack[sp].dd = d;
  1189. sp++;
  1190. }
  1191. }
  1192. private void MainSort()
  1193. {
  1194. int i, j, ss, sb;
  1195. int[] runningOrder = new int[256];
  1196. int[] copy = new int[256];
  1197. bool[] bigDone = new bool[256];
  1198. int c1, c2;
  1199. int numQSorted;
  1200. /*
  1201. In the various block-sized structures, live data runs
  1202. from 0 to last+NUM_OVERSHOOT_BYTES inclusive. First,
  1203. set up the overshoot area for block.
  1204. */
  1205. // if (verbosity >= 4) fprintf ( stderr, " sort initialise ...\n" );
  1206. for (i = 0; i < BZip2Constants.NUM_OVERSHOOT_BYTES; i++)
  1207. {
  1208. block[last + i + 2] = block[(i % (last + 1)) + 1];
  1209. }
  1210. for (i = 0; i <= last + BZip2Constants.NUM_OVERSHOOT_BYTES; i++)
  1211. {
  1212. quadrant[i] = 0;
  1213. }
  1214. block[0] = block[last + 1];
  1215. if (last < 4000)
  1216. {
  1217. /*
  1218. Use SimpleSort(), since the full sorting mechanism
  1219. has quite a large constant overhead.
  1220. */
  1221. for (i = 0; i <= last; i++)
  1222. {
  1223. zptr[i] = i;
  1224. }
  1225. firstAttempt = false;
  1226. workDone = workLimit = 0;
  1227. SimpleSort(0, last, 0);
  1228. }
  1229. else
  1230. {
  1231. numQSorted = 0;
  1232. for (i = 0; i <= 255; i++)
  1233. {
  1234. bigDone[i] = false;
  1235. }
  1236. for (i = 0; i <= 65536; i++)
  1237. {
  1238. ftab[i] = 0;
  1239. }
  1240. c1 = block[0];
  1241. for (i = 0; i <= last; i++)
  1242. {
  1243. c2 = block[i + 1];
  1244. ftab[(c1 << 8) + c2]++;
  1245. c1 = c2;
  1246. }
  1247. for (i = 1; i <= 65536; i++)
  1248. {
  1249. ftab[i] += ftab[i - 1];
  1250. }
  1251. c1 = block[1];
  1252. for (i = 0; i < last; i++)
  1253. {
  1254. c2 = block[i + 2];
  1255. j = (c1 << 8) + c2;
  1256. c1 = c2;
  1257. ftab[j]--;
  1258. zptr[ftab[j]] = i;
  1259. }
  1260. j = ((block[last + 1]) << 8) + (block[1]);
  1261. ftab[j]--;
  1262. zptr[ftab[j]] = last;
  1263. /*
  1264. Now ftab contains the first loc of every small bucket.
  1265. Calculate the running order, from smallest to largest
  1266. big bucket.
  1267. */
  1268. for (i = 0; i <= 255; i++)
  1269. {
  1270. runningOrder[i] = i;
  1271. }
  1272. {
  1273. int vv;
  1274. int h = 1;
  1275. do
  1276. {
  1277. h = 3 * h + 1;
  1278. }
  1279. while (h <= 256);
  1280. do
  1281. {
  1282. h = h / 3;
  1283. for (i = h; i <= 255; i++)
  1284. {
  1285. vv = runningOrder[i];
  1286. j = i;
  1287. while ((ftab[((runningOrder[j - h]) + 1) << 8]
  1288. - ftab[(runningOrder[j - h]) << 8]) >
  1289. (ftab[((vv) + 1) << 8] - ftab[(vv) << 8]))
  1290. {
  1291. runningOrder[j] = runningOrder[j - h];
  1292. j = j - h;
  1293. if (j <= (h - 1))
  1294. {
  1295. break;
  1296. }
  1297. }
  1298. runningOrder[j] = vv;
  1299. }
  1300. }
  1301. while (h != 1);
  1302. }
  1303. /*
  1304. The main sorting loop.
  1305. */
  1306. for (i = 0; i <= 255; i++)
  1307. {
  1308. /*
  1309. Process big buckets, starting with the least full.
  1310. */
  1311. ss = runningOrder[i];
  1312. /*
  1313. Complete the big bucket [ss] by quicksorting
  1314. any unsorted small buckets [ss, j]. Hopefully
  1315. previous pointer-scanning phases have already
  1316. completed many of the small buckets [ss, j], so
  1317. we don't have to sort them at all.
  1318. */
  1319. for (j = 0; j <= 255; j++)
  1320. {
  1321. sb = (ss << 8) + j;
  1322. if (!((ftab[sb] & SETMASK) == SETMASK))
  1323. {
  1324. int lo = ftab[sb] & CLEARMASK;
  1325. int hi = (ftab[sb + 1] & CLEARMASK) - 1;
  1326. if (hi > lo)
  1327. {
  1328. QSort3(lo, hi, 2);
  1329. numQSorted += (hi - lo + 1);
  1330. if (workDone > workLimit && firstAttempt)
  1331. {
  1332. return;
  1333. }
  1334. }
  1335. ftab[sb] |= SETMASK;
  1336. }
  1337. }
  1338. /*
  1339. The ss big bucket is now done. Record this fact,
  1340. and update the quadrant descriptors. Remember to
  1341. update quadrants in the overshoot area too, if
  1342. necessary. The "if (i < 255)" test merely skips
  1343. this updating for the last bucket processed, since
  1344. updating for the last bucket is pointless.
  1345. */
  1346. bigDone[ss] = true;
  1347. if (i < 255)
  1348. {
  1349. int bbStart = ftab[ss << 8] & CLEARMASK;
  1350. int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart;
  1351. int shifts = 0;
  1352. while ((bbSize >> shifts) > 65534)
  1353. {
  1354. shifts++;
  1355. }
  1356. for (j = 0; j < bbSize; j++)
  1357. {
  1358. int a2update = zptr[bbStart + j];
  1359. int qVal = (j >> shifts);
  1360. quadrant[a2update] = qVal;
  1361. if (a2update < BZip2Constants.NUM_OVERSHOOT_BYTES)
  1362. {
  1363. quadrant[a2update + last + 1] = qVal;
  1364. }
  1365. }
  1366. if (!(((bbSize - 1) >> shifts) <= 65535))
  1367. {
  1368. Panic();
  1369. }
  1370. }
  1371. /*
  1372. Now scan this big bucket so as to synthesise the
  1373. sorted order for small buckets [t, ss] for all t != ss.
  1374. */
  1375. for (j = 0; j <= 255; j++)
  1376. {
  1377. copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
  1378. }
  1379. for (j = ftab[ss << 8] & CLEARMASK;
  1380. j < (ftab[(ss + 1) << 8] & CLEARMASK);
  1381. j++)
  1382. {
  1383. c1 = block[zptr[j]];
  1384. if (!bigDone[c1])
  1385. {
  1386. zptr[copy[c1]] = zptr[j] == 0 ? last : zptr[j] - 1;
  1387. copy[c1]++;
  1388. }
  1389. }
  1390. for (j = 0; j <= 255; j++)
  1391. {
  1392. ftab[(j << 8) + ss] |= SETMASK;
  1393. }
  1394. }
  1395. }
  1396. }
  1397. private void RandomiseBlock()
  1398. {
  1399. int i;
  1400. int rNToGo = 0;
  1401. int rTPos = 0;
  1402. for (i = 0; i < 256; i++)
  1403. {
  1404. inUse[i] = false;
  1405. }
  1406. for (i = 0; i <= last; i++)
  1407. {
  1408. if (rNToGo == 0)
  1409. {
  1410. rNToGo = (char)BZip2Constants.rNums[rTPos];
  1411. rTPos++;
  1412. if (rTPos == 512)
  1413. {
  1414. rTPos = 0;
  1415. }
  1416. }
  1417. rNToGo--;
  1418. block[i + 1] ^= (char)((rNToGo == 1) ? 1 : 0);
  1419. // handle 16 bit signed numbers
  1420. block[i + 1] &= (char)0xFF;
  1421. inUse[block[i + 1]] = true;
  1422. }
  1423. }
  1424. private void DoReversibleTransformation()
  1425. {
  1426. int i;
  1427. workLimit = workFactor * last;
  1428. workDone = 0;
  1429. blockRandomised = false;
  1430. firstAttempt = true;
  1431. MainSort();
  1432. if (workDone > workLimit && firstAttempt)
  1433. {
  1434. RandomiseBlock();
  1435. workLimit = workDone = 0;
  1436. blockRandomised = true;
  1437. firstAttempt = false;
  1438. MainSort();
  1439. }
  1440. origPtr = -1;
  1441. for (i = 0; i <= last; i++)
  1442. {
  1443. if (zptr[i] == 0)
  1444. {
  1445. origPtr = i;
  1446. break;
  1447. }
  1448. }
  1449. ;
  1450. if (origPtr == -1)
  1451. {
  1452. Panic();
  1453. }
  1454. }
  1455. private bool FullGtU(int i1, int i2)
  1456. {
  1457. int k;
  1458. char c1, c2;
  1459. int s1, s2;
  1460. c1 = block[i1 + 1];
  1461. c2 = block[i2 + 1];
  1462. if (c1 != c2)
  1463. {
  1464. return (c1 > c2);
  1465. }
  1466. i1++;
  1467. i2++;
  1468. c1 = block[i1 + 1];
  1469. c2 = block[i2 + 1];
  1470. if (c1 != c2)
  1471. {
  1472. return (c1 > c2);
  1473. }
  1474. i1++;
  1475. i2++;
  1476. c1 = block[i1 + 1];
  1477. c2 = block[i2 + 1];
  1478. if (c1 != c2)
  1479. {
  1480. return (c1 > c2);
  1481. }
  1482. i1++;
  1483. i2++;
  1484. c1 = block[i1 + 1];
  1485. c2 = block[i2 + 1];
  1486. if (c1 != c2)
  1487. {
  1488. return (c1 > c2);
  1489. }
  1490. i1++;
  1491. i2++;
  1492. c1 = block[i1 + 1];
  1493. c2 = block[i2 + 1];
  1494. if (c1 != c2)
  1495. {
  1496. return (c1 > c2);
  1497. }
  1498. i1++;
  1499. i2++;
  1500. c1 = block[i1 + 1];
  1501. c2 = block[i2 + 1];
  1502. if (c1 != c2)
  1503. {
  1504. return (c1 > c2);
  1505. }
  1506. i1++;
  1507. i2++;
  1508. k = last + 1;
  1509. do
  1510. {
  1511. c1 = block[i1 + 1];
  1512. c2 = block[i2 + 1];
  1513. if (c1 != c2)
  1514. {
  1515. return (c1 > c2);
  1516. }
  1517. s1 = quadrant[i1];
  1518. s2 = quadrant[i2];
  1519. if (s1 != s2)
  1520. {
  1521. return (s1 > s2);
  1522. }
  1523. i1++;
  1524. i2++;
  1525. c1 = block[i1 + 1];
  1526. c2 = block[i2 + 1];
  1527. if (c1 != c2)
  1528. {
  1529. return (c1 > c2);
  1530. }
  1531. s1 = quadrant[i1];
  1532. s2 = quadrant[i2];
  1533. if (s1 != s2)
  1534. {
  1535. return (s1 > s2);
  1536. }
  1537. i1++;
  1538. i2++;
  1539. c1 = block[i1 + 1];
  1540. c2 = block[i2 + 1];
  1541. if (c1 != c2)
  1542. {
  1543. return (c1 > c2);
  1544. }
  1545. s1 = quadrant[i1];
  1546. s2 = quadrant[i2];
  1547. if (s1 != s2)
  1548. {
  1549. return (s1 > s2);
  1550. }
  1551. i1++;
  1552. i2++;
  1553. c1 = block[i1 + 1];
  1554. c2 = block[i2 + 1];
  1555. if (c1 != c2)
  1556. {
  1557. return (c1 > c2);
  1558. }
  1559. s1 = quadrant[i1];
  1560. s2 = quadrant[i2];
  1561. if (s1 != s2)
  1562. {
  1563. return (s1 > s2);
  1564. }
  1565. i1++;
  1566. i2++;
  1567. if (i1 > last)
  1568. {
  1569. i1 -= last;
  1570. i1--;
  1571. }
  1572. ;
  1573. if (i2 > last)
  1574. {
  1575. i2 -= last;
  1576. i2--;
  1577. }
  1578. ;
  1579. k -= 4;
  1580. workDone++;
  1581. }
  1582. while (k >= 0);
  1583. return false;
  1584. }
  1585. /*
  1586. Knuth's increments seem to work better
  1587. than Incerpi-Sedgewick here. Possibly
  1588. because the number of elems to sort is
  1589. usually small, typically <= 20.
  1590. */
  1591. private readonly int[] incs =
  1592. {
  1593. 1, 4, 13, 40, 121, 364, 1093, 3280,
  1594. 9841, 29524, 88573, 265720,
  1595. 797161, 2391484
  1596. };
  1597. private void AllocateCompressStructures()
  1598. {
  1599. int n = BZip2Constants.baseBlockSize * blockSize100k;
  1600. block = new char[(n + 1 + BZip2Constants.NUM_OVERSHOOT_BYTES)];
  1601. quadrant = new int[(n + BZip2Constants.NUM_OVERSHOOT_BYTES)];
  1602. zptr = new int[n];
  1603. ftab = new int[65537];
  1604. if (block == null || quadrant == null || zptr == null
  1605. || ftab == null)
  1606. {
  1607. //int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
  1608. //compressOutOfMemory ( totalDraw, n );
  1609. }
  1610. /*
  1611. The back end needs a place to store the MTF values
  1612. whilst it calculates the coding tables. We could
  1613. put them in the zptr array. However, these values
  1614. will fit in a short, so we overlay szptr at the
  1615. start of zptr, in the hope of reducing the number
  1616. of cache misses induced by the multiple traversals
  1617. of the MTF values when calculating coding tables.
  1618. Seems to improve compression speed by about 1%.
  1619. */
  1620. // szptr = zptr;
  1621. szptr = new short[2 * n];
  1622. }
  1623. private void GenerateMTFValues()
  1624. {
  1625. char[] yy = new char[256];
  1626. int i, j;
  1627. char tmp;
  1628. char tmp2;
  1629. int zPend;
  1630. int wr;
  1631. int EOB;
  1632. MakeMaps();
  1633. EOB = nInUse + 1;
  1634. for (i = 0; i <= EOB; i++)
  1635. {
  1636. mtfFreq[i] = 0;
  1637. }
  1638. wr = 0;
  1639. zPend = 0;
  1640. for (i = 0; i < nInUse; i++)
  1641. {
  1642. yy[i] = (char)i;
  1643. }
  1644. for (i = 0; i <= last; i++)
  1645. {
  1646. char ll_i;
  1647. ll_i = unseqToSeq[block[zptr[i]]];
  1648. j = 0;
  1649. tmp = yy[j];
  1650. while (ll_i != tmp)
  1651. {
  1652. j++;
  1653. tmp2 = tmp;
  1654. tmp = yy[j];
  1655. yy[j] = tmp2;
  1656. }
  1657. ;
  1658. yy[0] = tmp;
  1659. if (j == 0)
  1660. {
  1661. zPend++;
  1662. }
  1663. else
  1664. {
  1665. if (zPend > 0)
  1666. {
  1667. zPend--;
  1668. while (true)
  1669. {
  1670. switch (zPend % 2)
  1671. {
  1672. case 0:
  1673. szptr[wr] = BZip2Constants.RUNA;
  1674. wr++;
  1675. mtfFreq[BZip2Constants.RUNA]++;
  1676. break;
  1677. case 1:
  1678. szptr[wr] = BZip2Constants.RUNB;
  1679. wr++;
  1680. mtfFreq[BZip2Constants.RUNB]++;
  1681. break;
  1682. }
  1683. ;
  1684. if (zPend < 2)
  1685. {
  1686. break;
  1687. }
  1688. zPend = (zPend - 2) / 2;
  1689. }
  1690. ;
  1691. zPend = 0;
  1692. }
  1693. szptr[wr] = (short)(j + 1);
  1694. wr++;
  1695. mtfFreq[j + 1]++;
  1696. }
  1697. }
  1698. if (zPend > 0)
  1699. {
  1700. zPend--;
  1701. while (true)
  1702. {
  1703. switch (zPend % 2)
  1704. {
  1705. case 0:
  1706. szptr[wr] = BZip2Constants.RUNA;
  1707. wr++;
  1708. mtfFreq[BZip2Constants.RUNA]++;
  1709. break;
  1710. case 1:
  1711. szptr[wr] = BZip2Constants.RUNB;
  1712. wr++;
  1713. mtfFreq[BZip2Constants.RUNB]++;
  1714. break;
  1715. }
  1716. if (zPend < 2)
  1717. {
  1718. break;
  1719. }
  1720. zPend = (zPend - 2) / 2;
  1721. }
  1722. }
  1723. szptr[wr] = (short)EOB;
  1724. wr++;
  1725. mtfFreq[EOB]++;
  1726. nMTF = wr;
  1727. }
  1728. public override int Read(byte[] buffer, int offset, int count)
  1729. {
  1730. return 0;
  1731. }
  1732. public override int ReadByte()
  1733. {
  1734. return -1;
  1735. }
  1736. public override long Seek(long offset, SeekOrigin origin)
  1737. {
  1738. return 0;
  1739. }
  1740. public override void SetLength(long value)
  1741. {
  1742. }
  1743. public override void Write(byte[] buffer, int offset, int count)
  1744. {
  1745. for (int k = 0; k < count; ++k)
  1746. {
  1747. WriteByte(buffer[k + offset]);
  1748. }
  1749. }
  1750. public override bool CanRead => false;
  1751. public override bool CanSeek => false;
  1752. public override bool CanWrite => true;
  1753. public override long Length => 0;
  1754. public override long Position { get { return 0; } set { } }
  1755. }
  1756. }