TianoCompress.c 30 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746
  1. /** @file
  2. Compression routine. The compression algorithm is a mixture of LZ77 and Huffman
  3. coding. LZ77 transforms the source data into a sequence of Original Characters
  4. and Pointers to repeated strings. This sequence is further divided into Blocks
  5. and Huffman codings are applied to each Block.
  6. Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>
  7. SPDX-License-Identifier: BSD-2-Clause-Patent
  8. **/
  9. #include "Compress.h"
  10. //
  11. // Macro Definitions
  12. //
  13. #undef UINT8_MAX
  14. typedef INT32 NODE;
  15. #define UINT8_MAX 0xff
  16. #define UINT8_BIT 8
  17. #define THRESHOLD 3
  18. #define INIT_CRC 0
  19. #define WNDBIT 19
  20. #define WNDSIZ (1U << WNDBIT)
  21. #define MAXMATCH 256
  22. #define BLKSIZ (1U << 14) // 16 * 1024U
  23. #define PERC_FLAG 0x80000000U
  24. #define CODE_BIT 16
  25. #define NIL 0
  26. #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
  27. #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
  28. #define CRCPOLY 0xA001
  29. #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
  30. //
  31. // C: the Char&Len Set; P: the Position Set; T: the exTra Set
  32. //
  33. #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
  34. #define CBIT 9
  35. #define NP (WNDBIT + 1)
  36. #define PBIT 5
  37. #define NT (CODE_BIT + 3)
  38. #define TBIT 5
  39. #if NT > NP
  40. #define NPT NT
  41. #else
  42. #define NPT NP
  43. #endif
  44. //
  45. // Function Prototypes
  46. //
  47. STATIC
  48. VOID
  49. PutDword(
  50. IN UINT32 Data
  51. );
  52. STATIC
  53. EFI_STATUS
  54. AllocateMemory (
  55. VOID
  56. );
  57. STATIC
  58. VOID
  59. FreeMemory (
  60. VOID
  61. );
  62. STATIC
  63. VOID
  64. InitSlide (
  65. VOID
  66. );
  67. STATIC
  68. NODE
  69. Child (
  70. IN NODE NodeQ,
  71. IN UINT8 CharC
  72. );
  73. STATIC
  74. VOID
  75. MakeChild (
  76. IN NODE NodeQ,
  77. IN UINT8 CharC,
  78. IN NODE NodeR
  79. );
  80. STATIC
  81. VOID
  82. Split (
  83. IN NODE Old
  84. );
  85. STATIC
  86. VOID
  87. InsertNode (
  88. VOID
  89. );
  90. STATIC
  91. VOID
  92. DeleteNode (
  93. VOID
  94. );
  95. STATIC
  96. VOID
  97. GetNextMatch (
  98. VOID
  99. );
  100. STATIC
  101. EFI_STATUS
  102. Encode (
  103. VOID
  104. );
  105. STATIC
  106. VOID
  107. CountTFreq (
  108. VOID
  109. );
  110. STATIC
  111. VOID
  112. WritePTLen (
  113. IN INT32 Number,
  114. IN INT32 nbit,
  115. IN INT32 Special
  116. );
  117. STATIC
  118. VOID
  119. WriteCLen (
  120. VOID
  121. );
  122. STATIC
  123. VOID
  124. EncodeC (
  125. IN INT32 Value
  126. );
  127. STATIC
  128. VOID
  129. EncodeP (
  130. IN UINT32 Value
  131. );
  132. STATIC
  133. VOID
  134. SendBlock (
  135. VOID
  136. );
  137. STATIC
  138. VOID
  139. Output (
  140. IN UINT32 c,
  141. IN UINT32 p
  142. );
  143. STATIC
  144. VOID
  145. HufEncodeStart (
  146. VOID
  147. );
  148. STATIC
  149. VOID
  150. HufEncodeEnd (
  151. VOID
  152. );
  153. STATIC
  154. VOID
  155. MakeCrcTable (
  156. VOID
  157. );
  158. STATIC
  159. VOID
  160. PutBits (
  161. IN INT32 Number,
  162. IN UINT32 Value
  163. );
  164. STATIC
  165. INT32
  166. FreadCrc (
  167. OUT UINT8 *Pointer,
  168. IN INT32 Number
  169. );
  170. STATIC
  171. VOID
  172. InitPutBits (
  173. VOID
  174. );
  175. STATIC
  176. VOID
  177. CountLen (
  178. IN INT32 Index
  179. );
  180. STATIC
  181. VOID
  182. MakeLen (
  183. IN INT32 Root
  184. );
  185. STATIC
  186. VOID
  187. DownHeap (
  188. IN INT32 Index
  189. );
  190. STATIC
  191. VOID
  192. MakeCode (
  193. IN INT32 Number,
  194. IN UINT8 Len[ ],
  195. OUT UINT16 Code[]
  196. );
  197. STATIC
  198. INT32
  199. MakeTree (
  200. IN INT32 NParm,
  201. IN UINT16 FreqParm[],
  202. OUT UINT8 LenParm[ ],
  203. OUT UINT16 CodeParm[]
  204. );
  205. //
  206. // Global Variables
  207. //
  208. STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
  209. STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
  210. STATIC INT16 mHeap[NC + 1];
  211. STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
  212. STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
  213. STATIC UINT32 mCompSize, mOrigSize;
  214. STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],
  215. mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
  216. STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
  217. //
  218. // functions
  219. //
  220. EFI_STATUS
  221. TianoCompress (
  222. IN UINT8 *SrcBuffer,
  223. IN UINT32 SrcSize,
  224. IN UINT8 *DstBuffer,
  225. IN OUT UINT32 *DstSize
  226. )
  227. /*++
  228. Routine Description:
  229. The internal implementation of [Efi/Tiano]Compress().
  230. Arguments:
  231. SrcBuffer - The buffer storing the source data
  232. SrcSize - The size of source data
  233. DstBuffer - The buffer to store the compressed data
  234. DstSize - On input, the size of DstBuffer; On output,
  235. the size of the actual compressed data.
  236. Version - The version of de/compression algorithm.
  237. Version 1 for UEFI 2.0 de/compression algorithm.
  238. Version 2 for Tiano de/compression algorithm.
  239. Returns:
  240. EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
  241. DstSize contains the size needed.
  242. EFI_SUCCESS - Compression is successful.
  243. EFI_OUT_OF_RESOURCES - No resource to complete function.
  244. EFI_INVALID_PARAMETER - Parameter supplied is wrong.
  245. --*/
  246. {
  247. EFI_STATUS Status;
  248. //
  249. // Initializations
  250. //
  251. mBufSiz = 0;
  252. mBuf = NULL;
  253. mText = NULL;
  254. mLevel = NULL;
  255. mChildCount = NULL;
  256. mPosition = NULL;
  257. mParent = NULL;
  258. mPrev = NULL;
  259. mNext = NULL;
  260. mSrc = SrcBuffer;
  261. mSrcUpperLimit = mSrc + SrcSize;
  262. mDst = DstBuffer;
  263. mDstUpperLimit = mDst +*DstSize;
  264. PutDword (0L);
  265. PutDword (0L);
  266. MakeCrcTable ();
  267. mOrigSize = mCompSize = 0;
  268. mCrc = INIT_CRC;
  269. //
  270. // Compress it
  271. //
  272. Status = Encode ();
  273. if (EFI_ERROR (Status)) {
  274. return EFI_OUT_OF_RESOURCES;
  275. }
  276. //
  277. // Null terminate the compressed data
  278. //
  279. if (mDst < mDstUpperLimit) {
  280. *mDst++ = 0;
  281. }
  282. //
  283. // Fill in compressed size and original size
  284. //
  285. mDst = DstBuffer;
  286. PutDword (mCompSize + 1);
  287. PutDword (mOrigSize);
  288. //
  289. // Return
  290. //
  291. if (mCompSize + 1 + 8 > *DstSize) {
  292. *DstSize = mCompSize + 1 + 8;
  293. return EFI_BUFFER_TOO_SMALL;
  294. } else {
  295. *DstSize = mCompSize + 1 + 8;
  296. return EFI_SUCCESS;
  297. }
  298. }
  299. STATIC
  300. VOID
  301. PutDword (
  302. IN UINT32 Data
  303. )
  304. /*++
  305. Routine Description:
  306. Put a dword to output stream
  307. Arguments:
  308. Data - the dword to put
  309. Returns: (VOID)
  310. --*/
  311. {
  312. if (mDst < mDstUpperLimit) {
  313. *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
  314. }
  315. if (mDst < mDstUpperLimit) {
  316. *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
  317. }
  318. if (mDst < mDstUpperLimit) {
  319. *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
  320. }
  321. if (mDst < mDstUpperLimit) {
  322. *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
  323. }
  324. }
  325. STATIC
  326. EFI_STATUS
  327. AllocateMemory (
  328. VOID
  329. )
  330. /*++
  331. Routine Description:
  332. Allocate memory spaces for data structures used in compression process
  333. Arguments:
  334. VOID
  335. Returns:
  336. EFI_SUCCESS - Memory is allocated successfully
  337. EFI_OUT_OF_RESOURCES - Allocation fails
  338. --*/
  339. {
  340. UINT32 Index;
  341. mText = malloc (WNDSIZ * 2 + MAXMATCH);
  342. if (mText == NULL) {
  343. return EFI_OUT_OF_RESOURCES;
  344. }
  345. for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {
  346. mText[Index] = 0;
  347. }
  348. mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
  349. mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
  350. mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
  351. mParent = malloc (WNDSIZ * 2 * sizeof (*mParent));
  352. mPrev = malloc (WNDSIZ * 2 * sizeof (*mPrev));
  353. mNext = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));
  354. if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
  355. mParent == NULL || mPrev == NULL || mNext == NULL) {
  356. return EFI_OUT_OF_RESOURCES;
  357. }
  358. mBufSiz = BLKSIZ;
  359. mBuf = malloc (mBufSiz);
  360. while (mBuf == NULL) {
  361. mBufSiz = (mBufSiz / 10U) * 9U;
  362. if (mBufSiz < 4 * 1024U) {
  363. return EFI_OUT_OF_RESOURCES;
  364. }
  365. mBuf = malloc (mBufSiz);
  366. }
  367. mBuf[0] = 0;
  368. return EFI_SUCCESS;
  369. }
  370. VOID
  371. FreeMemory (
  372. VOID
  373. )
  374. /*++
  375. Routine Description:
  376. Called when compression is completed to free memory previously allocated.
  377. Arguments: (VOID)
  378. Returns: (VOID)
  379. --*/
  380. {
  381. if (mText != NULL) {
  382. free (mText);
  383. }
  384. if (mLevel != NULL) {
  385. free (mLevel);
  386. }
  387. if (mChildCount != NULL) {
  388. free (mChildCount);
  389. }
  390. if (mPosition != NULL) {
  391. free (mPosition);
  392. }
  393. if (mParent != NULL) {
  394. free (mParent);
  395. }
  396. if (mPrev != NULL) {
  397. free (mPrev);
  398. }
  399. if (mNext != NULL) {
  400. free (mNext);
  401. }
  402. if (mBuf != NULL) {
  403. free (mBuf);
  404. }
  405. return ;
  406. }
  407. STATIC
  408. VOID
  409. InitSlide (
  410. VOID
  411. )
  412. /*++
  413. Routine Description:
  414. Initialize String Info Log data structures
  415. Arguments: (VOID)
  416. Returns: (VOID)
  417. --*/
  418. {
  419. NODE Index;
  420. for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {
  421. mLevel[Index] = 1;
  422. mPosition[Index] = NIL; /* sentinel */
  423. }
  424. for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {
  425. mParent[Index] = NIL;
  426. }
  427. mAvail = 1;
  428. for (Index = 1; Index < WNDSIZ - 1; Index++) {
  429. mNext[Index] = (NODE) (Index + 1);
  430. }
  431. mNext[WNDSIZ - 1] = NIL;
  432. for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {
  433. mNext[Index] = NIL;
  434. }
  435. }
  436. STATIC
  437. NODE
  438. Child (
  439. IN NODE NodeQ,
  440. IN UINT8 CharC
  441. )
  442. /*++
  443. Routine Description:
  444. Find child node given the parent node and the edge character
  445. Arguments:
  446. NodeQ - the parent node
  447. CharC - the edge character
  448. Returns:
  449. The child node (NIL if not found)
  450. --*/
  451. {
  452. NODE NodeR;
  453. NodeR = mNext[HASH (NodeQ, CharC)];
  454. //
  455. // sentinel
  456. //
  457. mParent[NIL] = NodeQ;
  458. while (mParent[NodeR] != NodeQ) {
  459. NodeR = mNext[NodeR];
  460. }
  461. return NodeR;
  462. }
  463. STATIC
  464. VOID
  465. MakeChild (
  466. IN NODE Parent,
  467. IN UINT8 CharC,
  468. IN NODE Child
  469. )
  470. /*++
  471. Routine Description:
  472. Create a new child for a given parent node.
  473. Arguments:
  474. Parent - the parent node
  475. CharC - the edge character
  476. Child - the child node
  477. Returns: (VOID)
  478. --*/
  479. {
  480. NODE Node1;
  481. NODE Node2;
  482. Node1 = (NODE) HASH (Parent, CharC);
  483. Node2 = mNext[Node1];
  484. mNext[Node1] = Child;
  485. mNext[Child] = Node2;
  486. mPrev[Node2] = Child;
  487. mPrev[Child] = Node1;
  488. mParent[Child] = Parent;
  489. mChildCount[Parent]++;
  490. }
  491. STATIC
  492. VOID
  493. Split (
  494. NODE Old
  495. )
  496. /*++
  497. Routine Description:
  498. Split a node.
  499. Arguments:
  500. Old - the node to split
  501. Returns: (VOID)
  502. --*/
  503. {
  504. NODE New;
  505. NODE TempNode;
  506. New = mAvail;
  507. mAvail = mNext[New];
  508. mChildCount[New] = 0;
  509. TempNode = mPrev[Old];
  510. mPrev[New] = TempNode;
  511. mNext[TempNode] = New;
  512. TempNode = mNext[Old];
  513. mNext[New] = TempNode;
  514. mPrev[TempNode] = New;
  515. mParent[New] = mParent[Old];
  516. mLevel[New] = (UINT8) mMatchLen;
  517. mPosition[New] = mPos;
  518. MakeChild (New, mText[mMatchPos + mMatchLen], Old);
  519. MakeChild (New, mText[mPos + mMatchLen], mPos);
  520. }
  521. STATIC
  522. VOID
  523. InsertNode (
  524. VOID
  525. )
  526. /*++
  527. Routine Description:
  528. Insert string info for current position into the String Info Log
  529. Arguments: (VOID)
  530. Returns: (VOID)
  531. --*/
  532. {
  533. NODE NodeQ;
  534. NODE NodeR;
  535. NODE Index2;
  536. NODE NodeT;
  537. UINT8 CharC;
  538. UINT8 *t1;
  539. UINT8 *t2;
  540. if (mMatchLen >= 4) {
  541. //
  542. // We have just got a long match, the target tree
  543. // can be located by MatchPos + 1. Traverse the tree
  544. // from bottom up to get to a proper starting point.
  545. // The usage of PERC_FLAG ensures proper node deletion
  546. // in DeleteNode() later.
  547. //
  548. mMatchLen--;
  549. NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);
  550. NodeQ = mParent[NodeR];
  551. while (NodeQ == NIL) {
  552. NodeR = mNext[NodeR];
  553. NodeQ = mParent[NodeR];
  554. }
  555. while (mLevel[NodeQ] >= mMatchLen) {
  556. NodeR = NodeQ;
  557. NodeQ = mParent[NodeQ];
  558. }
  559. NodeT = NodeQ;
  560. while (mPosition[NodeT] < 0) {
  561. mPosition[NodeT] = mPos;
  562. NodeT = mParent[NodeT];
  563. }
  564. if (NodeT < WNDSIZ) {
  565. mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);
  566. }
  567. } else {
  568. //
  569. // Locate the target tree
  570. //
  571. NodeQ = (NODE) (mText[mPos] + WNDSIZ);
  572. CharC = mText[mPos + 1];
  573. NodeR = Child (NodeQ, CharC);
  574. if (NodeR == NIL) {
  575. MakeChild (NodeQ, CharC, mPos);
  576. mMatchLen = 1;
  577. return ;
  578. }
  579. mMatchLen = 2;
  580. }
  581. //
  582. // Traverse down the tree to find a match.
  583. // Update Position value along the route.
  584. // Node split or creation is involved.
  585. //
  586. for (;;) {
  587. if (NodeR >= WNDSIZ) {
  588. Index2 = MAXMATCH;
  589. mMatchPos = NodeR;
  590. } else {
  591. Index2 = mLevel[NodeR];
  592. mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
  593. }
  594. if (mMatchPos >= mPos) {
  595. mMatchPos -= WNDSIZ;
  596. }
  597. t1 = &mText[mPos + mMatchLen];
  598. t2 = &mText[mMatchPos + mMatchLen];
  599. while (mMatchLen < Index2) {
  600. if (*t1 != *t2) {
  601. Split (NodeR);
  602. return ;
  603. }
  604. mMatchLen++;
  605. t1++;
  606. t2++;
  607. }
  608. if (mMatchLen >= MAXMATCH) {
  609. break;
  610. }
  611. mPosition[NodeR] = mPos;
  612. NodeQ = NodeR;
  613. NodeR = Child (NodeQ, *t1);
  614. if (NodeR == NIL) {
  615. MakeChild (NodeQ, *t1, mPos);
  616. return ;
  617. }
  618. mMatchLen++;
  619. }
  620. NodeT = mPrev[NodeR];
  621. mPrev[mPos] = NodeT;
  622. mNext[NodeT] = mPos;
  623. NodeT = mNext[NodeR];
  624. mNext[mPos] = NodeT;
  625. mPrev[NodeT] = mPos;
  626. mParent[mPos] = NodeQ;
  627. mParent[NodeR] = NIL;
  628. //
  629. // Special usage of 'next'
  630. //
  631. mNext[NodeR] = mPos;
  632. }
  633. STATIC
  634. VOID
  635. DeleteNode (
  636. VOID
  637. )
  638. /*++
  639. Routine Description:
  640. Delete outdated string info. (The Usage of PERC_FLAG
  641. ensures a clean deletion)
  642. Arguments: (VOID)
  643. Returns: (VOID)
  644. --*/
  645. {
  646. NODE NodeQ;
  647. NODE NodeR;
  648. NODE NodeS;
  649. NODE NodeT;
  650. NODE NodeU;
  651. if (mParent[mPos] == NIL) {
  652. return ;
  653. }
  654. NodeR = mPrev[mPos];
  655. NodeS = mNext[mPos];
  656. mNext[NodeR] = NodeS;
  657. mPrev[NodeS] = NodeR;
  658. NodeR = mParent[mPos];
  659. mParent[mPos] = NIL;
  660. if (NodeR >= WNDSIZ) {
  661. return ;
  662. }
  663. mChildCount[NodeR]--;
  664. if (mChildCount[NodeR] > 1) {
  665. return ;
  666. }
  667. NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
  668. if (NodeT >= mPos) {
  669. NodeT -= WNDSIZ;
  670. }
  671. NodeS = NodeT;
  672. NodeQ = mParent[NodeR];
  673. NodeU = mPosition[NodeQ];
  674. while (NodeU & (UINT32) PERC_FLAG) {
  675. NodeU &= (UINT32)~PERC_FLAG;
  676. if (NodeU >= mPos) {
  677. NodeU -= WNDSIZ;
  678. }
  679. if (NodeU > NodeS) {
  680. NodeS = NodeU;
  681. }
  682. mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ);
  683. NodeQ = mParent[NodeQ];
  684. NodeU = mPosition[NodeQ];
  685. }
  686. if (NodeQ < WNDSIZ) {
  687. if (NodeU >= mPos) {
  688. NodeU -= WNDSIZ;
  689. }
  690. if (NodeU > NodeS) {
  691. NodeS = NodeU;
  692. }
  693. mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);
  694. }
  695. NodeS = Child (NodeR, mText[NodeT + mLevel[NodeR]]);
  696. NodeT = mPrev[NodeS];
  697. NodeU = mNext[NodeS];
  698. mNext[NodeT] = NodeU;
  699. mPrev[NodeU] = NodeT;
  700. NodeT = mPrev[NodeR];
  701. mNext[NodeT] = NodeS;
  702. mPrev[NodeS] = NodeT;
  703. NodeT = mNext[NodeR];
  704. mPrev[NodeT] = NodeS;
  705. mNext[NodeS] = NodeT;
  706. mParent[NodeS] = mParent[NodeR];
  707. mParent[NodeR] = NIL;
  708. mNext[NodeR] = mAvail;
  709. mAvail = NodeR;
  710. }
  711. STATIC
  712. VOID
  713. GetNextMatch (
  714. VOID
  715. )
  716. /*++
  717. Routine Description:
  718. Advance the current position (read in new data if needed).
  719. Delete outdated string info. Find a match string for current position.
  720. Arguments: (VOID)
  721. Returns: (VOID)
  722. --*/
  723. {
  724. INT32 Number;
  725. mRemainder--;
  726. mPos++;
  727. if (mPos == WNDSIZ * 2) {
  728. memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
  729. Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
  730. mRemainder += Number;
  731. mPos = WNDSIZ;
  732. }
  733. DeleteNode ();
  734. InsertNode ();
  735. }
  736. STATIC
  737. EFI_STATUS
  738. Encode (
  739. VOID
  740. )
  741. /*++
  742. Routine Description:
  743. The main controlling routine for compression process.
  744. Arguments: (VOID)
  745. Returns:
  746. EFI_SUCCESS - The compression is successful
  747. EFI_OUT_0F_RESOURCES - Not enough memory for compression process
  748. --*/
  749. {
  750. EFI_STATUS Status;
  751. INT32 LastMatchLen;
  752. NODE LastMatchPos;
  753. Status = AllocateMemory ();
  754. if (EFI_ERROR (Status)) {
  755. FreeMemory ();
  756. return Status;
  757. }
  758. InitSlide ();
  759. HufEncodeStart ();
  760. mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
  761. mMatchLen = 0;
  762. mPos = WNDSIZ;
  763. InsertNode ();
  764. if (mMatchLen > mRemainder) {
  765. mMatchLen = mRemainder;
  766. }
  767. while (mRemainder > 0) {
  768. LastMatchLen = mMatchLen;
  769. LastMatchPos = mMatchPos;
  770. GetNextMatch ();
  771. if (mMatchLen > mRemainder) {
  772. mMatchLen = mRemainder;
  773. }
  774. if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
  775. //
  776. // Not enough benefits are gained by outputting a pointer,
  777. // so just output the original character
  778. //
  779. Output (mText[mPos - 1], 0);
  780. } else {
  781. if (LastMatchLen == THRESHOLD) {
  782. if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {
  783. Output (mText[mPos - 1], 0);
  784. continue;
  785. }
  786. }
  787. //
  788. // Outputting a pointer is beneficial enough, do it.
  789. //
  790. Output (
  791. LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
  792. (mPos - LastMatchPos - 2) & (WNDSIZ - 1)
  793. );
  794. LastMatchLen--;
  795. while (LastMatchLen > 0) {
  796. GetNextMatch ();
  797. LastMatchLen--;
  798. }
  799. if (mMatchLen > mRemainder) {
  800. mMatchLen = mRemainder;
  801. }
  802. }
  803. }
  804. HufEncodeEnd ();
  805. FreeMemory ();
  806. return EFI_SUCCESS;
  807. }
  808. STATIC
  809. VOID
  810. CountTFreq (
  811. VOID
  812. )
  813. /*++
  814. Routine Description:
  815. Count the frequencies for the Extra Set
  816. Arguments: (VOID)
  817. Returns: (VOID)
  818. --*/
  819. {
  820. INT32 Index;
  821. INT32 Index3;
  822. INT32 Number;
  823. INT32 Count;
  824. for (Index = 0; Index < NT; Index++) {
  825. mTFreq[Index] = 0;
  826. }
  827. Number = NC;
  828. while (Number > 0 && mCLen[Number - 1] == 0) {
  829. Number--;
  830. }
  831. Index = 0;
  832. while (Index < Number) {
  833. Index3 = mCLen[Index++];
  834. if (Index3 == 0) {
  835. Count = 1;
  836. while (Index < Number && mCLen[Index] == 0) {
  837. Index++;
  838. Count++;
  839. }
  840. if (Count <= 2) {
  841. mTFreq[0] = (UINT16) (mTFreq[0] + Count);
  842. } else if (Count <= 18) {
  843. mTFreq[1]++;
  844. } else if (Count == 19) {
  845. mTFreq[0]++;
  846. mTFreq[1]++;
  847. } else {
  848. mTFreq[2]++;
  849. }
  850. } else {
  851. mTFreq[Index3 + 2]++;
  852. }
  853. }
  854. }
  855. STATIC
  856. VOID
  857. WritePTLen (
  858. IN INT32 Number,
  859. IN INT32 nbit,
  860. IN INT32 Special
  861. )
  862. /*++
  863. Routine Description:
  864. Outputs the code length array for the Extra Set or the Position Set.
  865. Arguments:
  866. Number - the number of symbols
  867. nbit - the number of bits needed to represent 'n'
  868. Special - the special symbol that needs to be take care of
  869. Returns: (VOID)
  870. --*/
  871. {
  872. INT32 Index;
  873. INT32 Index3;
  874. while (Number > 0 && mPTLen[Number - 1] == 0) {
  875. Number--;
  876. }
  877. PutBits (nbit, Number);
  878. Index = 0;
  879. while (Index < Number) {
  880. Index3 = mPTLen[Index++];
  881. if (Index3 <= 6) {
  882. PutBits (3, Index3);
  883. } else {
  884. PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);
  885. }
  886. if (Index == Special) {
  887. while (Index < 6 && mPTLen[Index] == 0) {
  888. Index++;
  889. }
  890. PutBits (2, (Index - 3) & 3);
  891. }
  892. }
  893. }
  894. STATIC
  895. VOID
  896. WriteCLen (
  897. VOID
  898. )
  899. /*++
  900. Routine Description:
  901. Outputs the code length array for Char&Length Set
  902. Arguments: (VOID)
  903. Returns: (VOID)
  904. --*/
  905. {
  906. INT32 Index;
  907. INT32 Index3;
  908. INT32 Number;
  909. INT32 Count;
  910. Number = NC;
  911. while (Number > 0 && mCLen[Number - 1] == 0) {
  912. Number--;
  913. }
  914. PutBits (CBIT, Number);
  915. Index = 0;
  916. while (Index < Number) {
  917. Index3 = mCLen[Index++];
  918. if (Index3 == 0) {
  919. Count = 1;
  920. while (Index < Number && mCLen[Index] == 0) {
  921. Index++;
  922. Count++;
  923. }
  924. if (Count <= 2) {
  925. for (Index3 = 0; Index3 < Count; Index3++) {
  926. PutBits (mPTLen[0], mPTCode[0]);
  927. }
  928. } else if (Count <= 18) {
  929. PutBits (mPTLen[1], mPTCode[1]);
  930. PutBits (4, Count - 3);
  931. } else if (Count == 19) {
  932. PutBits (mPTLen[0], mPTCode[0]);
  933. PutBits (mPTLen[1], mPTCode[1]);
  934. PutBits (4, 15);
  935. } else {
  936. PutBits (mPTLen[2], mPTCode[2]);
  937. PutBits (CBIT, Count - 20);
  938. }
  939. } else {
  940. PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);
  941. }
  942. }
  943. }
  944. STATIC
  945. VOID
  946. EncodeC (
  947. IN INT32 Value
  948. )
  949. {
  950. PutBits (mCLen[Value], mCCode[Value]);
  951. }
  952. STATIC
  953. VOID
  954. EncodeP (
  955. IN UINT32 Value
  956. )
  957. {
  958. UINT32 Index;
  959. UINT32 NodeQ;
  960. Index = 0;
  961. NodeQ = Value;
  962. while (NodeQ) {
  963. NodeQ >>= 1;
  964. Index++;
  965. }
  966. PutBits (mPTLen[Index], mPTCode[Index]);
  967. if (Index > 1) {
  968. PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));
  969. }
  970. }
  971. STATIC
  972. VOID
  973. SendBlock (
  974. VOID
  975. )
  976. /*++
  977. Routine Description:
  978. Huffman code the block and output it.
  979. Arguments:
  980. (VOID)
  981. Returns:
  982. (VOID)
  983. --*/
  984. {
  985. UINT32 Index;
  986. UINT32 Index2;
  987. UINT32 Index3;
  988. UINT32 Flags;
  989. UINT32 Root;
  990. UINT32 Pos;
  991. UINT32 Size;
  992. Flags = 0;
  993. Root = MakeTree (NC, mCFreq, mCLen, mCCode);
  994. Size = mCFreq[Root];
  995. PutBits (16, Size);
  996. if (Root >= NC) {
  997. CountTFreq ();
  998. Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
  999. if (Root >= NT) {
  1000. WritePTLen (NT, TBIT, 3);
  1001. } else {
  1002. PutBits (TBIT, 0);
  1003. PutBits (TBIT, Root);
  1004. }
  1005. WriteCLen ();
  1006. } else {
  1007. PutBits (TBIT, 0);
  1008. PutBits (TBIT, 0);
  1009. PutBits (CBIT, 0);
  1010. PutBits (CBIT, Root);
  1011. }
  1012. Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
  1013. if (Root >= NP) {
  1014. WritePTLen (NP, PBIT, -1);
  1015. } else {
  1016. PutBits (PBIT, 0);
  1017. PutBits (PBIT, Root);
  1018. }
  1019. Pos = 0;
  1020. for (Index = 0; Index < Size; Index++) {
  1021. if (Index % UINT8_BIT == 0) {
  1022. Flags = mBuf[Pos++];
  1023. } else {
  1024. Flags <<= 1;
  1025. }
  1026. if (Flags & (1U << (UINT8_BIT - 1))) {
  1027. EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));
  1028. Index3 = mBuf[Pos++];
  1029. for (Index2 = 0; Index2 < 3; Index2++) {
  1030. Index3 <<= UINT8_BIT;
  1031. Index3 += mBuf[Pos++];
  1032. }
  1033. EncodeP (Index3);
  1034. } else {
  1035. EncodeC (mBuf[Pos++]);
  1036. }
  1037. }
  1038. for (Index = 0; Index < NC; Index++) {
  1039. mCFreq[Index] = 0;
  1040. }
  1041. for (Index = 0; Index < NP; Index++) {
  1042. mPFreq[Index] = 0;
  1043. }
  1044. }
  1045. STATIC
  1046. VOID
  1047. Output (
  1048. IN UINT32 CharC,
  1049. IN UINT32 Pos
  1050. )
  1051. /*++
  1052. Routine Description:
  1053. Outputs an Original Character or a Pointer
  1054. Arguments:
  1055. CharC - The original character or the 'String Length' element of a Pointer
  1056. Pos - The 'Position' field of a Pointer
  1057. Returns: (VOID)
  1058. --*/
  1059. {
  1060. STATIC UINT32 CPos;
  1061. if ((mOutputMask >>= 1) == 0) {
  1062. mOutputMask = 1U << (UINT8_BIT - 1);
  1063. //
  1064. // Check the buffer overflow per outputing UINT8_BIT symbols
  1065. // which is an Original Character or a Pointer. The biggest
  1066. // symbol is a Pointer which occupies 5 bytes.
  1067. //
  1068. if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {
  1069. SendBlock ();
  1070. mOutputPos = 0;
  1071. }
  1072. CPos = mOutputPos++;
  1073. mBuf[CPos] = 0;
  1074. }
  1075. mBuf[mOutputPos++] = (UINT8) CharC;
  1076. mCFreq[CharC]++;
  1077. if (CharC >= (1U << UINT8_BIT)) {
  1078. mBuf[CPos] |= mOutputMask;
  1079. mBuf[mOutputPos++] = (UINT8) (Pos >> 24);
  1080. mBuf[mOutputPos++] = (UINT8) (Pos >> 16);
  1081. mBuf[mOutputPos++] = (UINT8) (Pos >> (UINT8_BIT));
  1082. mBuf[mOutputPos++] = (UINT8) Pos;
  1083. CharC = 0;
  1084. while (Pos) {
  1085. Pos >>= 1;
  1086. CharC++;
  1087. }
  1088. mPFreq[CharC]++;
  1089. }
  1090. }
  1091. STATIC
  1092. VOID
  1093. HufEncodeStart (
  1094. VOID
  1095. )
  1096. {
  1097. INT32 Index;
  1098. for (Index = 0; Index < NC; Index++) {
  1099. mCFreq[Index] = 0;
  1100. }
  1101. for (Index = 0; Index < NP; Index++) {
  1102. mPFreq[Index] = 0;
  1103. }
  1104. mOutputPos = mOutputMask = 0;
  1105. InitPutBits ();
  1106. return ;
  1107. }
  1108. STATIC
  1109. VOID
  1110. HufEncodeEnd (
  1111. VOID
  1112. )
  1113. {
  1114. SendBlock ();
  1115. //
  1116. // Flush remaining bits
  1117. //
  1118. PutBits (UINT8_BIT - 1, 0);
  1119. return ;
  1120. }
  1121. STATIC
  1122. VOID
  1123. MakeCrcTable (
  1124. VOID
  1125. )
  1126. {
  1127. UINT32 Index;
  1128. UINT32 Index2;
  1129. UINT32 Temp;
  1130. for (Index = 0; Index <= UINT8_MAX; Index++) {
  1131. Temp = Index;
  1132. for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {
  1133. if (Temp & 1) {
  1134. Temp = (Temp >> 1) ^ CRCPOLY;
  1135. } else {
  1136. Temp >>= 1;
  1137. }
  1138. }
  1139. mCrcTable[Index] = (UINT16) Temp;
  1140. }
  1141. }
  1142. STATIC
  1143. VOID
  1144. PutBits (
  1145. IN INT32 Number,
  1146. IN UINT32 Value
  1147. )
  1148. /*++
  1149. Routine Description:
  1150. Outputs rightmost n bits of x
  1151. Arguments:
  1152. Number - the rightmost n bits of the data is used
  1153. x - the data
  1154. Returns: (VOID)
  1155. --*/
  1156. {
  1157. UINT8 Temp;
  1158. while (Number >= mBitCount) {
  1159. //
  1160. // Number -= mBitCount should never equal to 32
  1161. //
  1162. Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));
  1163. if (mDst < mDstUpperLimit) {
  1164. *mDst++ = Temp;
  1165. }
  1166. mCompSize++;
  1167. mSubBitBuf = 0;
  1168. mBitCount = UINT8_BIT;
  1169. }
  1170. mSubBitBuf |= Value << (mBitCount -= Number);
  1171. }
  1172. STATIC
  1173. INT32
  1174. FreadCrc (
  1175. OUT UINT8 *Pointer,
  1176. IN INT32 Number
  1177. )
  1178. /*++
  1179. Routine Description:
  1180. Read in source data
  1181. Arguments:
  1182. Pointer - the buffer to hold the data
  1183. Number - number of bytes to read
  1184. Returns:
  1185. number of bytes actually read
  1186. --*/
  1187. {
  1188. INT32 Index;
  1189. for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {
  1190. *Pointer++ = *mSrc++;
  1191. }
  1192. Number = Index;
  1193. Pointer -= Number;
  1194. mOrigSize += Number;
  1195. Index--;
  1196. while (Index >= 0) {
  1197. UPDATE_CRC (*Pointer++);
  1198. Index--;
  1199. }
  1200. return Number;
  1201. }
  1202. STATIC
  1203. VOID
  1204. InitPutBits (
  1205. VOID
  1206. )
  1207. {
  1208. mBitCount = UINT8_BIT;
  1209. mSubBitBuf = 0;
  1210. }
  1211. STATIC
  1212. VOID
  1213. CountLen (
  1214. IN INT32 Index
  1215. )
  1216. /*++
  1217. Routine Description:
  1218. Count the number of each code length for a Huffman tree.
  1219. Arguments:
  1220. Index - the top node
  1221. Returns: (VOID)
  1222. --*/
  1223. {
  1224. STATIC INT32 Depth = 0;
  1225. if (Index < mN) {
  1226. mLenCnt[(Depth < 16) ? Depth : 16]++;
  1227. } else {
  1228. Depth++;
  1229. CountLen (mLeft[Index]);
  1230. CountLen (mRight[Index]);
  1231. Depth--;
  1232. }
  1233. }
  1234. STATIC
  1235. VOID
  1236. MakeLen (
  1237. IN INT32 Root
  1238. )
  1239. /*++
  1240. Routine Description:
  1241. Create code length array for a Huffman tree
  1242. Arguments:
  1243. Root - the root of the tree
  1244. Returns:
  1245. VOID
  1246. --*/
  1247. {
  1248. INT32 Index;
  1249. INT32 Index3;
  1250. UINT32 Cum;
  1251. for (Index = 0; Index <= 16; Index++) {
  1252. mLenCnt[Index] = 0;
  1253. }
  1254. CountLen (Root);
  1255. //
  1256. // Adjust the length count array so that
  1257. // no code will be generated longer than its designated length
  1258. //
  1259. Cum = 0;
  1260. for (Index = 16; Index > 0; Index--) {
  1261. Cum += mLenCnt[Index] << (16 - Index);
  1262. }
  1263. while (Cum != (1U << 16)) {
  1264. mLenCnt[16]--;
  1265. for (Index = 15; Index > 0; Index--) {
  1266. if (mLenCnt[Index] != 0) {
  1267. mLenCnt[Index]--;
  1268. mLenCnt[Index + 1] += 2;
  1269. break;
  1270. }
  1271. }
  1272. Cum--;
  1273. }
  1274. for (Index = 16; Index > 0; Index--) {
  1275. Index3 = mLenCnt[Index];
  1276. Index3--;
  1277. while (Index3 >= 0) {
  1278. mLen[*mSortPtr++] = (UINT8) Index;
  1279. Index3--;
  1280. }
  1281. }
  1282. }
  1283. STATIC
  1284. VOID
  1285. DownHeap (
  1286. IN INT32 Index
  1287. )
  1288. {
  1289. INT32 Index2;
  1290. INT32 Index3;
  1291. //
  1292. // priority queue: send Index-th entry down heap
  1293. //
  1294. Index3 = mHeap[Index];
  1295. Index2 = 2 * Index;
  1296. while (Index2 <= mHeapSize) {
  1297. if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {
  1298. Index2++;
  1299. }
  1300. if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {
  1301. break;
  1302. }
  1303. mHeap[Index] = mHeap[Index2];
  1304. Index = Index2;
  1305. Index2 = 2 * Index;
  1306. }
  1307. mHeap[Index] = (INT16) Index3;
  1308. }
  1309. STATIC
  1310. VOID
  1311. MakeCode (
  1312. IN INT32 Number,
  1313. IN UINT8 Len[ ],
  1314. OUT UINT16 Code[]
  1315. )
  1316. /*++
  1317. Routine Description:
  1318. Assign code to each symbol based on the code length array
  1319. Arguments:
  1320. Number - number of symbols
  1321. Len - the code length array
  1322. Code - stores codes for each symbol
  1323. Returns: (VOID)
  1324. --*/
  1325. {
  1326. INT32 Index;
  1327. UINT16 Start[18];
  1328. Start[1] = 0;
  1329. for (Index = 1; Index <= 16; Index++) {
  1330. Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);
  1331. }
  1332. for (Index = 0; Index < Number; Index++) {
  1333. Code[Index] = Start[Len[Index]]++;
  1334. }
  1335. }
  1336. STATIC
  1337. INT32
  1338. MakeTree (
  1339. IN INT32 NParm,
  1340. IN UINT16 FreqParm[],
  1341. OUT UINT8 LenParm[ ],
  1342. OUT UINT16 CodeParm[]
  1343. )
  1344. /*++
  1345. Routine Description:
  1346. Generates Huffman codes given a frequency distribution of symbols
  1347. Arguments:
  1348. NParm - number of symbols
  1349. FreqParm - frequency of each symbol
  1350. LenParm - code length for each symbol
  1351. CodeParm - code for each symbol
  1352. Returns:
  1353. Root of the Huffman tree.
  1354. --*/
  1355. {
  1356. INT32 Index;
  1357. INT32 Index2;
  1358. INT32 Index3;
  1359. INT32 Avail;
  1360. //
  1361. // make tree, calculate len[], return root
  1362. //
  1363. mN = NParm;
  1364. mFreq = FreqParm;
  1365. mLen = LenParm;
  1366. Avail = mN;
  1367. mHeapSize = 0;
  1368. mHeap[1] = 0;
  1369. for (Index = 0; Index < mN; Index++) {
  1370. mLen[Index] = 0;
  1371. if (mFreq[Index]) {
  1372. mHeapSize++;
  1373. mHeap[mHeapSize] = (INT16) Index;
  1374. }
  1375. }
  1376. if (mHeapSize < 2) {
  1377. CodeParm[mHeap[1]] = 0;
  1378. return mHeap[1];
  1379. }
  1380. for (Index = mHeapSize / 2; Index >= 1; Index--) {
  1381. //
  1382. // make priority queue
  1383. //
  1384. DownHeap (Index);
  1385. }
  1386. mSortPtr = CodeParm;
  1387. do {
  1388. Index = mHeap[1];
  1389. if (Index < mN) {
  1390. *mSortPtr++ = (UINT16) Index;
  1391. }
  1392. mHeap[1] = mHeap[mHeapSize--];
  1393. DownHeap (1);
  1394. Index2 = mHeap[1];
  1395. if (Index2 < mN) {
  1396. *mSortPtr++ = (UINT16) Index2;
  1397. }
  1398. Index3 = Avail++;
  1399. mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);
  1400. mHeap[1] = (INT16) Index3;
  1401. DownHeap (1);
  1402. mLeft[Index3] = (UINT16) Index;
  1403. mRight[Index3] = (UINT16) Index2;
  1404. } while (mHeapSize > 1);
  1405. mSortPtr = CodeParm;
  1406. MakeLen (Index3);
  1407. MakeCode (NParm, LenParm, CodeParm);
  1408. //
  1409. // return root
  1410. //
  1411. return Index3;
  1412. }