EfiCompress.c 26 KB

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