TianoCompress.c 54 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800
  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.
  5. This sequence is further divided into Blocks and Huffman codings are applied to
  6. each Block.
  7. Copyright (c) 2007 - 2018, Intel Corporation. All rights reserved.<BR>
  8. This program and the accompanying materials
  9. are licensed and made available under the terms and conditions of the BSD License
  10. which accompanies this distribution. The full text of the license may be found at
  11. http://opensource.org/licenses/bsd-license.php
  12. THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  13. WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  14. **/
  15. #include "Compress.h"
  16. #include "Decompress.h"
  17. #include "TianoCompress.h"
  18. #include "EfiUtilityMsgs.h"
  19. #include "ParseInf.h"
  20. #include <stdio.h>
  21. #include "assert.h"
  22. //
  23. // Macro Definitions
  24. //
  25. static BOOLEAN VerboseMode = FALSE;
  26. static BOOLEAN QuietMode = FALSE;
  27. #undef UINT8_MAX
  28. #define UINT8_MAX 0xff
  29. #define UINT8_BIT 8
  30. #define THRESHOLD 3
  31. #define INIT_CRC 0
  32. #define WNDBIT 19
  33. #define WNDSIZ (1U << WNDBIT)
  34. #define MAXMATCH 256
  35. #define BLKSIZ (1U << 14) // 16 * 1024U
  36. #define PERC_FLAG 0x80000000U
  37. #define CODE_BIT 16
  38. #define NIL 0
  39. #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
  40. #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
  41. #define CRCPOLY 0xA001
  42. #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
  43. //
  44. // C: the Char&Len Set; P: the Position Set; T: the exTra Set
  45. //
  46. //#define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
  47. #define CBIT 9
  48. #define NP (WNDBIT + 1)
  49. #define PBIT 5
  50. //#define NT (CODE_BIT + 3)
  51. //#define TBIT 5
  52. //#if NT > NP
  53. //#define NPT NT
  54. //#else
  55. //#define NPT NP
  56. //#endif
  57. //
  58. // Global Variables
  59. //
  60. STATIC BOOLEAN ENCODE = FALSE;
  61. STATIC BOOLEAN DECODE = FALSE;
  62. STATIC BOOLEAN UEFIMODE = FALSE;
  63. STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
  64. STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
  65. STATIC INT16 mHeap[NC + 1];
  66. STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
  67. STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
  68. STATIC UINT32 mCompSize, mOrigSize;
  69. STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],
  70. mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
  71. STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
  72. static UINT64 DebugLevel;
  73. static BOOLEAN DebugMode;
  74. //
  75. // functions
  76. //
  77. EFI_STATUS
  78. TianoCompress (
  79. IN UINT8 *SrcBuffer,
  80. IN UINT32 SrcSize,
  81. IN UINT8 *DstBuffer,
  82. IN OUT UINT32 *DstSize
  83. )
  84. /*++
  85. Routine Description:
  86. The internal implementation of [Efi/Tiano]Compress().
  87. Arguments:
  88. SrcBuffer - The buffer storing the source data
  89. SrcSize - The size of source data
  90. DstBuffer - The buffer to store the compressed data
  91. Version - The version of de/compression algorithm.
  92. Version 1 for EFI 1.1 de/compression algorithm.
  93. Version 2 for Tiano de/compression algorithm.
  94. Returns:
  95. EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
  96. DstSize contains the size needed.
  97. EFI_SUCCESS - Compression is successful.
  98. EFI_OUT_OF_RESOURCES - No resource to complete function.
  99. EFI_INVALID_PARAMETER - Parameter supplied is wrong.
  100. --*/
  101. {
  102. EFI_STATUS Status;
  103. //
  104. // Initializations
  105. //
  106. mBufSiz = 0;
  107. mBuf = NULL;
  108. mText = NULL;
  109. mLevel = NULL;
  110. mChildCount = NULL;
  111. mPosition = NULL;
  112. mParent = NULL;
  113. mPrev = NULL;
  114. mNext = NULL;
  115. mSrc = SrcBuffer;
  116. mSrcUpperLimit = mSrc + SrcSize;
  117. mDst = DstBuffer;
  118. mDstUpperLimit = mDst +*DstSize;
  119. PutDword (0L);
  120. PutDword (0L);
  121. MakeCrcTable ();
  122. mOrigSize = mCompSize = 0;
  123. mCrc = INIT_CRC;
  124. //
  125. // Compress it
  126. //
  127. Status = Encode ();
  128. if (EFI_ERROR (Status)) {
  129. return EFI_OUT_OF_RESOURCES;
  130. }
  131. //
  132. // Null terminate the compressed data
  133. //
  134. if (mDst < mDstUpperLimit) {
  135. *mDst++ = 0;
  136. }
  137. //
  138. // Fill in compressed size and original size
  139. //
  140. mDst = DstBuffer;
  141. PutDword (mCompSize + 1);
  142. PutDword (mOrigSize);
  143. //
  144. // Return
  145. //
  146. if (mCompSize + 1 + 8 > *DstSize) {
  147. *DstSize = mCompSize + 1 + 8;
  148. return EFI_BUFFER_TOO_SMALL;
  149. } else {
  150. *DstSize = mCompSize + 1 + 8;
  151. return EFI_SUCCESS;
  152. }
  153. }
  154. STATIC
  155. VOID
  156. PutDword (
  157. IN UINT32 Data
  158. )
  159. /*++
  160. Routine Description:
  161. Put a dword to output stream
  162. Arguments:
  163. Data - the dword to put
  164. Returns: (VOID)
  165. --*/
  166. {
  167. if (mDst < mDstUpperLimit) {
  168. *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
  169. }
  170. if (mDst < mDstUpperLimit) {
  171. *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
  172. }
  173. if (mDst < mDstUpperLimit) {
  174. *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
  175. }
  176. if (mDst < mDstUpperLimit) {
  177. *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
  178. }
  179. }
  180. STATIC
  181. EFI_STATUS
  182. AllocateMemory (
  183. VOID
  184. )
  185. /*++
  186. Routine Description:
  187. Allocate memory spaces for data structures used in compression process
  188. Arguments:
  189. VOID
  190. Returns:
  191. EFI_SUCCESS - Memory is allocated successfully
  192. EFI_OUT_OF_RESOURCES - Allocation fails
  193. --*/
  194. {
  195. UINT32 Index;
  196. mText = malloc (WNDSIZ * 2 + MAXMATCH);
  197. if (mText == NULL) {
  198. Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");
  199. return EFI_OUT_OF_RESOURCES;
  200. }
  201. for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {
  202. mText[Index] = 0;
  203. }
  204. mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
  205. mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
  206. mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
  207. mParent = malloc (WNDSIZ * 2 * sizeof (*mParent));
  208. mPrev = malloc (WNDSIZ * 2 * sizeof (*mPrev));
  209. mNext = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));
  210. if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
  211. mParent == NULL || mPrev == NULL || mNext == NULL) {
  212. Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");
  213. return EFI_OUT_OF_RESOURCES;
  214. }
  215. mBufSiz = BLKSIZ;
  216. mBuf = malloc (mBufSiz);
  217. while (mBuf == NULL) {
  218. mBufSiz = (mBufSiz / 10U) * 9U;
  219. if (mBufSiz < 4 * 1024U) {
  220. return EFI_OUT_OF_RESOURCES;
  221. }
  222. mBuf = malloc (mBufSiz);
  223. }
  224. mBuf[0] = 0;
  225. return EFI_SUCCESS;
  226. }
  227. VOID
  228. FreeMemory (
  229. VOID
  230. )
  231. /*++
  232. Routine Description:
  233. Called when compression is completed to free memory previously allocated.
  234. Arguments: (VOID)
  235. Returns: (VOID)
  236. --*/
  237. {
  238. if (mText != NULL) {
  239. free (mText);
  240. }
  241. if (mLevel != NULL) {
  242. free (mLevel);
  243. }
  244. if (mChildCount != NULL) {
  245. free (mChildCount);
  246. }
  247. if (mPosition != NULL) {
  248. free (mPosition);
  249. }
  250. if (mParent != NULL) {
  251. free (mParent);
  252. }
  253. if (mPrev != NULL) {
  254. free (mPrev);
  255. }
  256. if (mNext != NULL) {
  257. free (mNext);
  258. }
  259. if (mBuf != NULL) {
  260. free (mBuf);
  261. }
  262. return ;
  263. }
  264. STATIC
  265. VOID
  266. InitSlide (
  267. VOID
  268. )
  269. /*++
  270. Routine Description:
  271. Initialize String Info Log data structures
  272. Arguments: (VOID)
  273. Returns: (VOID)
  274. --*/
  275. {
  276. NODE Index;
  277. for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {
  278. mLevel[Index] = 1;
  279. mPosition[Index] = NIL; // sentinel
  280. }
  281. for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {
  282. mParent[Index] = NIL;
  283. }
  284. mAvail = 1;
  285. for (Index = 1; Index < WNDSIZ - 1; Index++) {
  286. mNext[Index] = (NODE) (Index + 1);
  287. }
  288. mNext[WNDSIZ - 1] = NIL;
  289. for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {
  290. mNext[Index] = NIL;
  291. }
  292. }
  293. STATIC
  294. NODE
  295. Child (
  296. IN NODE NodeQ,
  297. IN UINT8 CharC
  298. )
  299. /*++
  300. Routine Description:
  301. Find child node given the parent node and the edge character
  302. Arguments:
  303. NodeQ - the parent node
  304. CharC - the edge character
  305. Returns:
  306. The child node (NIL if not found)
  307. --*/
  308. {
  309. NODE NodeR;
  310. NodeR = mNext[HASH (NodeQ, CharC)];
  311. //
  312. // sentinel
  313. //
  314. mParent[NIL] = NodeQ;
  315. while (mParent[NodeR] != NodeQ) {
  316. NodeR = mNext[NodeR];
  317. }
  318. return NodeR;
  319. }
  320. STATIC
  321. VOID
  322. MakeChild (
  323. IN NODE Parent,
  324. IN UINT8 CharC,
  325. IN NODE Child
  326. )
  327. /*++
  328. Routine Description:
  329. Create a new child for a given parent node.
  330. Arguments:
  331. Parent - the parent node
  332. CharC - the edge character
  333. Child - the child node
  334. Returns: (VOID)
  335. --*/
  336. {
  337. NODE Node1;
  338. NODE Node2;
  339. Node1 = (NODE) HASH (Parent, CharC);
  340. Node2 = mNext[Node1];
  341. mNext[Node1] = Child;
  342. mNext[Child] = Node2;
  343. mPrev[Node2] = Child;
  344. mPrev[Child] = Node1;
  345. mParent[Child] = Parent;
  346. mChildCount[Parent]++;
  347. }
  348. STATIC
  349. VOID
  350. Split (
  351. NODE Old
  352. )
  353. /*++
  354. Routine Description:
  355. Split a node.
  356. Arguments:
  357. Old - the node to split
  358. Returns: (VOID)
  359. --*/
  360. {
  361. NODE New;
  362. NODE TempNode;
  363. New = mAvail;
  364. mAvail = mNext[New];
  365. mChildCount[New] = 0;
  366. TempNode = mPrev[Old];
  367. mPrev[New] = TempNode;
  368. mNext[TempNode] = New;
  369. TempNode = mNext[Old];
  370. mNext[New] = TempNode;
  371. mPrev[TempNode] = New;
  372. mParent[New] = mParent[Old];
  373. mLevel[New] = (UINT8) mMatchLen;
  374. mPosition[New] = mPos;
  375. MakeChild (New, mText[mMatchPos + mMatchLen], Old);
  376. MakeChild (New, mText[mPos + mMatchLen], mPos);
  377. }
  378. STATIC
  379. VOID
  380. InsertNode (
  381. VOID
  382. )
  383. /*++
  384. Routine Description:
  385. Insert string info for current position into the String Info Log
  386. Arguments: (VOID)
  387. Returns: (VOID)
  388. --*/
  389. {
  390. NODE NodeQ;
  391. NODE NodeR;
  392. NODE Index2;
  393. NODE NodeT;
  394. UINT8 CharC;
  395. UINT8 *t1;
  396. UINT8 *t2;
  397. if (mMatchLen >= 4) {
  398. //
  399. // We have just got a long match, the target tree
  400. // can be located by MatchPos + 1. Traverse the tree
  401. // from bottom up to get to a proper starting point.
  402. // The usage of PERC_FLAG ensures proper node deletion
  403. // in DeleteNode() later.
  404. //
  405. mMatchLen--;
  406. NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);
  407. NodeQ = mParent[NodeR];
  408. while (NodeQ == NIL) {
  409. NodeR = mNext[NodeR];
  410. NodeQ = mParent[NodeR];
  411. }
  412. while (mLevel[NodeQ] >= mMatchLen) {
  413. NodeR = NodeQ;
  414. NodeQ = mParent[NodeQ];
  415. }
  416. NodeT = NodeQ;
  417. while (mPosition[NodeT] < 0) {
  418. mPosition[NodeT] = mPos;
  419. NodeT = mParent[NodeT];
  420. }
  421. if (NodeT < WNDSIZ) {
  422. mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);
  423. }
  424. } else {
  425. //
  426. // Locate the target tree
  427. //
  428. NodeQ = (NODE) (mText[mPos] + WNDSIZ);
  429. CharC = mText[mPos + 1];
  430. NodeR = Child (NodeQ, CharC);
  431. if (NodeR == NIL) {
  432. MakeChild (NodeQ, CharC, mPos);
  433. mMatchLen = 1;
  434. return ;
  435. }
  436. mMatchLen = 2;
  437. }
  438. //
  439. // Traverse down the tree to find a match.
  440. // Update Position value along the route.
  441. // Node split or creation is involved.
  442. //
  443. for (;;) {
  444. if (NodeR >= WNDSIZ) {
  445. Index2 = MAXMATCH;
  446. mMatchPos = NodeR;
  447. } else {
  448. Index2 = mLevel[NodeR];
  449. mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
  450. }
  451. if (mMatchPos >= mPos) {
  452. mMatchPos -= WNDSIZ;
  453. }
  454. t1 = &mText[mPos + mMatchLen];
  455. t2 = &mText[mMatchPos + mMatchLen];
  456. while (mMatchLen < Index2) {
  457. if (*t1 != *t2) {
  458. Split (NodeR);
  459. return ;
  460. }
  461. mMatchLen++;
  462. t1++;
  463. t2++;
  464. }
  465. if (mMatchLen >= MAXMATCH) {
  466. break;
  467. }
  468. mPosition[NodeR] = mPos;
  469. NodeQ = NodeR;
  470. NodeR = Child (NodeQ, *t1);
  471. if (NodeR == NIL) {
  472. MakeChild (NodeQ, *t1, mPos);
  473. return ;
  474. }
  475. mMatchLen++;
  476. }
  477. NodeT = mPrev[NodeR];
  478. mPrev[mPos] = NodeT;
  479. mNext[NodeT] = mPos;
  480. NodeT = mNext[NodeR];
  481. mNext[mPos] = NodeT;
  482. mPrev[NodeT] = mPos;
  483. mParent[mPos] = NodeQ;
  484. mParent[NodeR] = NIL;
  485. //
  486. // Special usage of 'next'
  487. //
  488. mNext[NodeR] = mPos;
  489. }
  490. STATIC
  491. VOID
  492. DeleteNode (
  493. VOID
  494. )
  495. /*++
  496. Routine Description:
  497. Delete outdated string info. (The Usage of PERC_FLAG
  498. ensures a clean deletion)
  499. Arguments: (VOID)
  500. Returns: (VOID)
  501. --*/
  502. {
  503. NODE NodeQ;
  504. NODE NodeR;
  505. NODE NodeS;
  506. NODE NodeT;
  507. NODE NodeU;
  508. if (mParent[mPos] == NIL) {
  509. return ;
  510. }
  511. NodeR = mPrev[mPos];
  512. NodeS = mNext[mPos];
  513. mNext[NodeR] = NodeS;
  514. mPrev[NodeS] = NodeR;
  515. NodeR = mParent[mPos];
  516. mParent[mPos] = NIL;
  517. if (NodeR >= WNDSIZ) {
  518. return ;
  519. }
  520. mChildCount[NodeR]--;
  521. if (mChildCount[NodeR] > 1) {
  522. return ;
  523. }
  524. NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
  525. if (NodeT >= mPos) {
  526. NodeT -= WNDSIZ;
  527. }
  528. NodeS = NodeT;
  529. NodeQ = mParent[NodeR];
  530. NodeU = mPosition[NodeQ];
  531. while (NodeU & (UINT32) PERC_FLAG) {
  532. NodeU &= (UINT32)~PERC_FLAG;
  533. if (NodeU >= mPos) {
  534. NodeU -= WNDSIZ;
  535. }
  536. if (NodeU > NodeS) {
  537. NodeS = NodeU;
  538. }
  539. mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ);
  540. NodeQ = mParent[NodeQ];
  541. NodeU = mPosition[NodeQ];
  542. }
  543. if (NodeQ < WNDSIZ) {
  544. if (NodeU >= mPos) {
  545. NodeU -= WNDSIZ;
  546. }
  547. if (NodeU > NodeS) {
  548. NodeS = NodeU;
  549. }
  550. mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);
  551. }
  552. NodeS = Child (NodeR, mText[NodeT + mLevel[NodeR]]);
  553. NodeT = mPrev[NodeS];
  554. NodeU = mNext[NodeS];
  555. mNext[NodeT] = NodeU;
  556. mPrev[NodeU] = NodeT;
  557. NodeT = mPrev[NodeR];
  558. mNext[NodeT] = NodeS;
  559. mPrev[NodeS] = NodeT;
  560. NodeT = mNext[NodeR];
  561. mPrev[NodeT] = NodeS;
  562. mNext[NodeS] = NodeT;
  563. mParent[NodeS] = mParent[NodeR];
  564. mParent[NodeR] = NIL;
  565. mNext[NodeR] = mAvail;
  566. mAvail = NodeR;
  567. }
  568. STATIC
  569. VOID
  570. GetNextMatch (
  571. VOID
  572. )
  573. /*++
  574. Routine Description:
  575. Advance the current position (read in new data if needed).
  576. Delete outdated string info. Find a match string for current position.
  577. Arguments: (VOID)
  578. Returns: (VOID)
  579. --*/
  580. {
  581. INT32 Number;
  582. mRemainder--;
  583. mPos++;
  584. if (mPos == WNDSIZ * 2) {
  585. memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
  586. Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
  587. mRemainder += Number;
  588. mPos = WNDSIZ;
  589. }
  590. DeleteNode ();
  591. InsertNode ();
  592. }
  593. STATIC
  594. EFI_STATUS
  595. Encode (
  596. VOID
  597. )
  598. /*++
  599. Routine Description:
  600. The main controlling routine for compression process.
  601. Arguments: (VOID)
  602. Returns:
  603. EFI_SUCCESS - The compression is successful
  604. EFI_OUT_0F_RESOURCES - Not enough memory for compression process
  605. --*/
  606. {
  607. EFI_STATUS Status;
  608. INT32 LastMatchLen;
  609. NODE LastMatchPos;
  610. Status = AllocateMemory ();
  611. if (EFI_ERROR (Status)) {
  612. FreeMemory ();
  613. return Status;
  614. }
  615. InitSlide ();
  616. HufEncodeStart ();
  617. mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
  618. mMatchLen = 0;
  619. mPos = WNDSIZ;
  620. InsertNode ();
  621. if (mMatchLen > mRemainder) {
  622. mMatchLen = mRemainder;
  623. }
  624. while (mRemainder > 0) {
  625. LastMatchLen = mMatchLen;
  626. LastMatchPos = mMatchPos;
  627. GetNextMatch ();
  628. if (mMatchLen > mRemainder) {
  629. mMatchLen = mRemainder;
  630. }
  631. if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
  632. //
  633. // Not enough benefits are gained by outputting a pointer,
  634. // so just output the original character
  635. //
  636. Output (mText[mPos - 1], 0);
  637. } else {
  638. if (LastMatchLen == THRESHOLD) {
  639. if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {
  640. Output (mText[mPos - 1], 0);
  641. continue;
  642. }
  643. }
  644. //
  645. // Outputting a pointer is beneficial enough, do it.
  646. //
  647. Output (
  648. LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
  649. (mPos - LastMatchPos - 2) & (WNDSIZ - 1)
  650. );
  651. LastMatchLen--;
  652. while (LastMatchLen > 0) {
  653. GetNextMatch ();
  654. LastMatchLen--;
  655. }
  656. if (mMatchLen > mRemainder) {
  657. mMatchLen = mRemainder;
  658. }
  659. }
  660. }
  661. HufEncodeEnd ();
  662. FreeMemory ();
  663. return EFI_SUCCESS;
  664. }
  665. STATIC
  666. VOID
  667. CountTFreq (
  668. VOID
  669. )
  670. /*++
  671. Routine Description:
  672. Count the frequencies for the Extra Set
  673. Arguments: (VOID)
  674. Returns: (VOID)
  675. --*/
  676. {
  677. INT32 Index;
  678. INT32 Index3;
  679. INT32 Number;
  680. INT32 Count;
  681. for (Index = 0; Index < NT; Index++) {
  682. mTFreq[Index] = 0;
  683. }
  684. Number = NC;
  685. while (Number > 0 && mCLen[Number - 1] == 0) {
  686. Number--;
  687. }
  688. Index = 0;
  689. while (Index < Number) {
  690. Index3 = mCLen[Index++];
  691. if (Index3 == 0) {
  692. Count = 1;
  693. while (Index < Number && mCLen[Index] == 0) {
  694. Index++;
  695. Count++;
  696. }
  697. if (Count <= 2) {
  698. mTFreq[0] = (UINT16) (mTFreq[0] + Count);
  699. } else if (Count <= 18) {
  700. mTFreq[1]++;
  701. } else if (Count == 19) {
  702. mTFreq[0]++;
  703. mTFreq[1]++;
  704. } else {
  705. mTFreq[2]++;
  706. }
  707. } else {
  708. mTFreq[Index3 + 2]++;
  709. }
  710. }
  711. }
  712. STATIC
  713. VOID
  714. WritePTLen (
  715. IN INT32 Number,
  716. IN INT32 nbit,
  717. IN INT32 Special
  718. )
  719. /*++
  720. Routine Description:
  721. Outputs the code length array for the Extra Set or the Position Set.
  722. Arguments:
  723. Number - the number of symbols
  724. nbit - the number of bits needed to represent 'n'
  725. Special - the special symbol that needs to be take care of
  726. Returns: (VOID)
  727. --*/
  728. {
  729. INT32 Index;
  730. INT32 Index3;
  731. while (Number > 0 && mPTLen[Number - 1] == 0) {
  732. Number--;
  733. }
  734. PutBits (nbit, Number);
  735. Index = 0;
  736. while (Index < Number) {
  737. Index3 = mPTLen[Index++];
  738. if (Index3 <= 6) {
  739. PutBits (3, Index3);
  740. } else {
  741. PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);
  742. }
  743. if (Index == Special) {
  744. while (Index < 6 && mPTLen[Index] == 0) {
  745. Index++;
  746. }
  747. PutBits (2, (Index - 3) & 3);
  748. }
  749. }
  750. }
  751. STATIC
  752. VOID
  753. WriteCLen (
  754. VOID
  755. )
  756. /*++
  757. Routine Description:
  758. Outputs the code length array for Char&Length Set
  759. Arguments: (VOID)
  760. Returns: (VOID)
  761. --*/
  762. {
  763. INT32 Index;
  764. INT32 Index3;
  765. INT32 Number;
  766. INT32 Count;
  767. Number = NC;
  768. while (Number > 0 && mCLen[Number - 1] == 0) {
  769. Number--;
  770. }
  771. PutBits (CBIT, Number);
  772. Index = 0;
  773. while (Index < Number) {
  774. Index3 = mCLen[Index++];
  775. if (Index3 == 0) {
  776. Count = 1;
  777. while (Index < Number && mCLen[Index] == 0) {
  778. Index++;
  779. Count++;
  780. }
  781. if (Count <= 2) {
  782. for (Index3 = 0; Index3 < Count; Index3++) {
  783. PutBits (mPTLen[0], mPTCode[0]);
  784. }
  785. } else if (Count <= 18) {
  786. PutBits (mPTLen[1], mPTCode[1]);
  787. PutBits (4, Count - 3);
  788. } else if (Count == 19) {
  789. PutBits (mPTLen[0], mPTCode[0]);
  790. PutBits (mPTLen[1], mPTCode[1]);
  791. PutBits (4, 15);
  792. } else {
  793. PutBits (mPTLen[2], mPTCode[2]);
  794. PutBits (CBIT, Count - 20);
  795. }
  796. } else {
  797. PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);
  798. }
  799. }
  800. }
  801. STATIC
  802. VOID
  803. EncodeC (
  804. IN INT32 Value
  805. )
  806. {
  807. PutBits (mCLen[Value], mCCode[Value]);
  808. }
  809. STATIC
  810. VOID
  811. EncodeP (
  812. IN UINT32 Value
  813. )
  814. {
  815. UINT32 Index;
  816. UINT32 NodeQ;
  817. Index = 0;
  818. NodeQ = Value;
  819. while (NodeQ) {
  820. NodeQ >>= 1;
  821. Index++;
  822. }
  823. PutBits (mPTLen[Index], mPTCode[Index]);
  824. if (Index > 1) {
  825. PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));
  826. }
  827. }
  828. STATIC
  829. VOID
  830. SendBlock (
  831. VOID
  832. )
  833. /*++
  834. Routine Description:
  835. Huffman code the block and output it.
  836. Arguments:
  837. (VOID)
  838. Returns:
  839. (VOID)
  840. --*/
  841. {
  842. UINT32 Index;
  843. UINT32 Index2;
  844. UINT32 Index3;
  845. UINT32 Flags;
  846. UINT32 Root;
  847. UINT32 Pos;
  848. UINT32 Size;
  849. Flags = 0;
  850. Root = MakeTree (NC, mCFreq, mCLen, mCCode);
  851. Size = mCFreq[Root];
  852. PutBits (16, Size);
  853. if (Root >= NC) {
  854. CountTFreq ();
  855. Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
  856. if (Root >= NT) {
  857. WritePTLen (NT, TBIT, 3);
  858. } else {
  859. PutBits (TBIT, 0);
  860. PutBits (TBIT, Root);
  861. }
  862. WriteCLen ();
  863. } else {
  864. PutBits (TBIT, 0);
  865. PutBits (TBIT, 0);
  866. PutBits (CBIT, 0);
  867. PutBits (CBIT, Root);
  868. }
  869. Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
  870. if (Root >= NP) {
  871. WritePTLen (NP, PBIT, -1);
  872. } else {
  873. PutBits (PBIT, 0);
  874. PutBits (PBIT, Root);
  875. }
  876. Pos = 0;
  877. for (Index = 0; Index < Size; Index++) {
  878. if (Index % UINT8_BIT == 0) {
  879. Flags = mBuf[Pos++];
  880. } else {
  881. Flags <<= 1;
  882. }
  883. if (Flags & (1U << (UINT8_BIT - 1))) {
  884. EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));
  885. Index3 = mBuf[Pos++];
  886. for (Index2 = 0; Index2 < 3; Index2++) {
  887. Index3 <<= UINT8_BIT;
  888. Index3 += mBuf[Pos++];
  889. }
  890. EncodeP (Index3);
  891. } else {
  892. EncodeC (mBuf[Pos++]);
  893. }
  894. }
  895. for (Index = 0; Index < NC; Index++) {
  896. mCFreq[Index] = 0;
  897. }
  898. for (Index = 0; Index < NP; Index++) {
  899. mPFreq[Index] = 0;
  900. }
  901. }
  902. STATIC
  903. VOID
  904. Output (
  905. IN UINT32 CharC,
  906. IN UINT32 Pos
  907. )
  908. /*++
  909. Routine Description:
  910. Outputs an Original Character or a Pointer
  911. Arguments:
  912. CharC - The original character or the 'String Length' element of a Pointer
  913. Pos - The 'Position' field of a Pointer
  914. Returns: (VOID)
  915. --*/
  916. {
  917. STATIC UINT32 CPos;
  918. if ((mOutputMask >>= 1) == 0) {
  919. mOutputMask = 1U << (UINT8_BIT - 1);
  920. //
  921. // Check the buffer overflow per outputing UINT8_BIT symbols
  922. // which is an Original Character or a Pointer. The biggest
  923. // symbol is a Pointer which occupies 5 bytes.
  924. //
  925. if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {
  926. SendBlock ();
  927. mOutputPos = 0;
  928. }
  929. CPos = mOutputPos++;
  930. mBuf[CPos] = 0;
  931. }
  932. mBuf[mOutputPos++] = (UINT8) CharC;
  933. mCFreq[CharC]++;
  934. if (CharC >= (1U << UINT8_BIT)) {
  935. mBuf[CPos] |= mOutputMask;
  936. mBuf[mOutputPos++] = (UINT8) (Pos >> 24);
  937. mBuf[mOutputPos++] = (UINT8) (Pos >> 16);
  938. mBuf[mOutputPos++] = (UINT8) (Pos >> (UINT8_BIT));
  939. mBuf[mOutputPos++] = (UINT8) Pos;
  940. CharC = 0;
  941. while (Pos) {
  942. Pos >>= 1;
  943. CharC++;
  944. }
  945. mPFreq[CharC]++;
  946. }
  947. }
  948. STATIC
  949. VOID
  950. HufEncodeStart (
  951. VOID
  952. )
  953. {
  954. INT32 Index;
  955. for (Index = 0; Index < NC; Index++) {
  956. mCFreq[Index] = 0;
  957. }
  958. for (Index = 0; Index < NP; Index++) {
  959. mPFreq[Index] = 0;
  960. }
  961. mOutputPos = mOutputMask = 0;
  962. InitPutBits ();
  963. return ;
  964. }
  965. STATIC
  966. VOID
  967. HufEncodeEnd (
  968. VOID
  969. )
  970. {
  971. SendBlock ();
  972. //
  973. // Flush remaining bits
  974. //
  975. PutBits (UINT8_BIT - 1, 0);
  976. return ;
  977. }
  978. STATIC
  979. VOID
  980. MakeCrcTable (
  981. VOID
  982. )
  983. {
  984. UINT32 Index;
  985. UINT32 Index2;
  986. UINT32 Temp;
  987. for (Index = 0; Index <= UINT8_MAX; Index++) {
  988. Temp = Index;
  989. for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {
  990. if (Temp & 1) {
  991. Temp = (Temp >> 1) ^ CRCPOLY;
  992. } else {
  993. Temp >>= 1;
  994. }
  995. }
  996. mCrcTable[Index] = (UINT16) Temp;
  997. }
  998. }
  999. STATIC
  1000. VOID
  1001. PutBits (
  1002. IN INT32 Number,
  1003. IN UINT32 Value
  1004. )
  1005. /*++
  1006. Routine Description:
  1007. Outputs rightmost n bits of x
  1008. Arguments:
  1009. Number - the rightmost n bits of the data is used
  1010. x - the data
  1011. Returns: (VOID)
  1012. --*/
  1013. {
  1014. UINT8 Temp;
  1015. while (Number >= mBitCount) {
  1016. //
  1017. // Number -= mBitCount should never equal to 32
  1018. //
  1019. Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));
  1020. if (mDst < mDstUpperLimit) {
  1021. *mDst++ = Temp;
  1022. }
  1023. mCompSize++;
  1024. mSubBitBuf = 0;
  1025. mBitCount = UINT8_BIT;
  1026. }
  1027. mSubBitBuf |= Value << (mBitCount -= Number);
  1028. }
  1029. STATIC
  1030. INT32
  1031. FreadCrc (
  1032. OUT UINT8 *Pointer,
  1033. IN INT32 Number
  1034. )
  1035. /*++
  1036. Routine Description:
  1037. Read in source data
  1038. Arguments:
  1039. Pointer - the buffer to hold the data
  1040. Number - number of bytes to read
  1041. Returns:
  1042. number of bytes actually read
  1043. --*/
  1044. {
  1045. INT32 Index;
  1046. for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {
  1047. *Pointer++ = *mSrc++;
  1048. }
  1049. Number = Index;
  1050. Pointer -= Number;
  1051. mOrigSize += Number;
  1052. Index--;
  1053. while (Index >= 0) {
  1054. UPDATE_CRC (*Pointer++);
  1055. Index--;
  1056. }
  1057. return Number;
  1058. }
  1059. STATIC
  1060. VOID
  1061. InitPutBits (
  1062. VOID
  1063. )
  1064. {
  1065. mBitCount = UINT8_BIT;
  1066. mSubBitBuf = 0;
  1067. }
  1068. STATIC
  1069. VOID
  1070. CountLen (
  1071. IN INT32 Index
  1072. )
  1073. /*++
  1074. Routine Description:
  1075. Count the number of each code length for a Huffman tree.
  1076. Arguments:
  1077. Index - the top node
  1078. Returns: (VOID)
  1079. --*/
  1080. {
  1081. STATIC INT32 Depth = 0;
  1082. if (Index < mN) {
  1083. mLenCnt[(Depth < 16) ? Depth : 16]++;
  1084. } else {
  1085. Depth++;
  1086. CountLen (mLeft[Index]);
  1087. CountLen (mRight[Index]);
  1088. Depth--;
  1089. }
  1090. }
  1091. STATIC
  1092. VOID
  1093. MakeLen (
  1094. IN INT32 Root
  1095. )
  1096. /*++
  1097. Routine Description:
  1098. Create code length array for a Huffman tree
  1099. Arguments:
  1100. Root - the root of the tree
  1101. Returns:
  1102. VOID
  1103. --*/
  1104. {
  1105. INT32 Index;
  1106. INT32 Index3;
  1107. UINT32 Cum;
  1108. for (Index = 0; Index <= 16; Index++) {
  1109. mLenCnt[Index] = 0;
  1110. }
  1111. CountLen (Root);
  1112. //
  1113. // Adjust the length count array so that
  1114. // no code will be generated longer than its designated length
  1115. //
  1116. Cum = 0;
  1117. for (Index = 16; Index > 0; Index--) {
  1118. Cum += mLenCnt[Index] << (16 - Index);
  1119. }
  1120. while (Cum != (1U << 16)) {
  1121. mLenCnt[16]--;
  1122. for (Index = 15; Index > 0; Index--) {
  1123. if (mLenCnt[Index] != 0) {
  1124. mLenCnt[Index]--;
  1125. mLenCnt[Index + 1] += 2;
  1126. break;
  1127. }
  1128. }
  1129. Cum--;
  1130. }
  1131. for (Index = 16; Index > 0; Index--) {
  1132. Index3 = mLenCnt[Index];
  1133. Index3--;
  1134. while (Index3 >= 0) {
  1135. mLen[*mSortPtr++] = (UINT8) Index;
  1136. Index3--;
  1137. }
  1138. }
  1139. }
  1140. STATIC
  1141. VOID
  1142. DownHeap (
  1143. IN INT32 Index
  1144. )
  1145. {
  1146. INT32 Index2;
  1147. INT32 Index3;
  1148. //
  1149. // priority queue: send Index-th entry down heap
  1150. //
  1151. Index3 = mHeap[Index];
  1152. Index2 = 2 * Index;
  1153. while (Index2 <= mHeapSize) {
  1154. if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {
  1155. Index2++;
  1156. }
  1157. if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {
  1158. break;
  1159. }
  1160. mHeap[Index] = mHeap[Index2];
  1161. Index = Index2;
  1162. Index2 = 2 * Index;
  1163. }
  1164. mHeap[Index] = (INT16) Index3;
  1165. }
  1166. STATIC
  1167. VOID
  1168. MakeCode (
  1169. IN INT32 Number,
  1170. IN UINT8 Len[ ],
  1171. OUT UINT16 Code[]
  1172. )
  1173. /*++
  1174. Routine Description:
  1175. Assign code to each symbol based on the code length array
  1176. Arguments:
  1177. Number - number of symbols
  1178. Len - the code length array
  1179. Code - stores codes for each symbol
  1180. Returns: (VOID)
  1181. --*/
  1182. {
  1183. INT32 Index;
  1184. UINT16 Start[18];
  1185. Start[1] = 0;
  1186. for (Index = 1; Index <= 16; Index++) {
  1187. Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);
  1188. }
  1189. for (Index = 0; Index < Number; Index++) {
  1190. Code[Index] = Start[Len[Index]]++;
  1191. }
  1192. }
  1193. STATIC
  1194. INT32
  1195. MakeTree (
  1196. IN INT32 NParm,
  1197. IN UINT16 FreqParm[],
  1198. OUT UINT8 LenParm[ ],
  1199. OUT UINT16 CodeParm[]
  1200. )
  1201. /*++
  1202. Routine Description:
  1203. Generates Huffman codes given a frequency distribution of symbols
  1204. Arguments:
  1205. NParm - number of symbols
  1206. FreqParm - frequency of each symbol
  1207. LenParm - code length for each symbol
  1208. CodeParm - code for each symbol
  1209. Returns:
  1210. Root of the Huffman tree.
  1211. --*/
  1212. {
  1213. INT32 Index;
  1214. INT32 Index2;
  1215. INT32 Index3;
  1216. INT32 Avail;
  1217. //
  1218. // make tree, calculate len[], return root
  1219. //
  1220. mN = NParm;
  1221. mFreq = FreqParm;
  1222. mLen = LenParm;
  1223. Avail = mN;
  1224. mHeapSize = 0;
  1225. mHeap[1] = 0;
  1226. for (Index = 0; Index < mN; Index++) {
  1227. mLen[Index] = 0;
  1228. if (mFreq[Index]) {
  1229. mHeapSize++;
  1230. mHeap[mHeapSize] = (INT16) Index;
  1231. }
  1232. }
  1233. if (mHeapSize < 2) {
  1234. CodeParm[mHeap[1]] = 0;
  1235. return mHeap[1];
  1236. }
  1237. for (Index = mHeapSize / 2; Index >= 1; Index--) {
  1238. //
  1239. // make priority queue
  1240. //
  1241. DownHeap (Index);
  1242. }
  1243. mSortPtr = CodeParm;
  1244. do {
  1245. Index = mHeap[1];
  1246. if (Index < mN) {
  1247. *mSortPtr++ = (UINT16) Index;
  1248. }
  1249. mHeap[1] = mHeap[mHeapSize--];
  1250. DownHeap (1);
  1251. Index2 = mHeap[1];
  1252. if (Index2 < mN) {
  1253. *mSortPtr++ = (UINT16) Index2;
  1254. }
  1255. Index3 = Avail++;
  1256. mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);
  1257. mHeap[1] = (INT16) Index3;
  1258. DownHeap (1);
  1259. mLeft[Index3] = (UINT16) Index;
  1260. mRight[Index3] = (UINT16) Index2;
  1261. } while (mHeapSize > 1);
  1262. mSortPtr = CodeParm;
  1263. MakeLen (Index3);
  1264. MakeCode (NParm, LenParm, CodeParm);
  1265. //
  1266. // return root
  1267. //
  1268. return Index3;
  1269. }
  1270. EFI_STATUS
  1271. GetFileContents (
  1272. IN char *InputFileName,
  1273. OUT UINT8 *FileBuffer,
  1274. OUT UINT32 *BufferLength
  1275. )
  1276. /*++
  1277. Routine Description:
  1278. Get the contents of file specified in InputFileName
  1279. into FileBuffer.
  1280. Arguments:
  1281. InputFileName - Name of the input file.
  1282. FileBuffer - Output buffer to contain data
  1283. BufferLength - Actual length of the data
  1284. Returns:
  1285. EFI_SUCCESS on successful return
  1286. EFI_ABORTED if unable to open input file.
  1287. --*/
  1288. {
  1289. UINTN Size;
  1290. UINTN FileSize;
  1291. FILE *InputFile;
  1292. Size = 0;
  1293. //
  1294. // Copy the file contents to the output buffer.
  1295. //
  1296. InputFile = fopen (LongFilePath (InputFileName), "rb");
  1297. if (InputFile == NULL) {
  1298. Error (NULL, 0, 0001, "Error opening file: %s", InputFileName);
  1299. return EFI_ABORTED;
  1300. }
  1301. fseek (InputFile, 0, SEEK_END);
  1302. FileSize = ftell (InputFile);
  1303. fseek (InputFile, 0, SEEK_SET);
  1304. //
  1305. // Now read the contents of the file into the buffer
  1306. //
  1307. if (FileSize > 0 && FileBuffer != NULL) {
  1308. if (fread (FileBuffer, FileSize, 1, InputFile) != 1) {
  1309. Error (NULL, 0, 0004, "Error reading contents of input file: %s", InputFileName);
  1310. fclose (InputFile);
  1311. return EFI_ABORTED;
  1312. }
  1313. }
  1314. fclose (InputFile);
  1315. Size += (UINTN) FileSize;
  1316. *BufferLength = Size;
  1317. if (FileBuffer != NULL) {
  1318. return EFI_SUCCESS;
  1319. } else {
  1320. return EFI_BUFFER_TOO_SMALL;
  1321. }
  1322. }
  1323. VOID
  1324. Version (
  1325. VOID
  1326. )
  1327. /*++
  1328. Routine Description:
  1329. Displays the standard utility information to SDTOUT
  1330. Arguments:
  1331. None
  1332. Returns:
  1333. None
  1334. --*/
  1335. {
  1336. fprintf (stdout, "%s Version %d.%d %s \n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION, __BUILD_VERSION);
  1337. }
  1338. VOID
  1339. Usage (
  1340. VOID
  1341. )
  1342. /*++
  1343. Routine Description:
  1344. Displays the utility usage syntax to STDOUT
  1345. Arguments:
  1346. None
  1347. Returns:
  1348. None
  1349. --*/
  1350. {
  1351. //
  1352. // Summary usage
  1353. //
  1354. fprintf (stdout, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME);
  1355. //
  1356. // Copyright declaration
  1357. //
  1358. fprintf (stdout, "Copyright (c) 2007 - 2018, Intel Corporation. All rights reserved.\n\n");
  1359. //
  1360. // Details Option
  1361. //
  1362. fprintf (stdout, "Options:\n");
  1363. fprintf (stdout, " --uefi\n\
  1364. Enable UefiCompress, use TianoCompress when without this option\n");
  1365. fprintf (stdout, " -o FileName, --output FileName\n\
  1366. File will be created to store the output content.\n");
  1367. fprintf (stdout, " -v, --verbose\n\
  1368. Turn on verbose output with informational messages.\n");
  1369. fprintf (stdout, " -q, --quiet\n\
  1370. Disable all messages except key message and fatal error\n");
  1371. fprintf (stdout, " --debug [0-9]\n\
  1372. Enable debug messages, at input debug level.\n");
  1373. fprintf (stdout, " --version\n\
  1374. Show program's version number and exit.\n");
  1375. fprintf (stdout, " -h, --help\n\
  1376. Show this help message and exit.\n");
  1377. }
  1378. int
  1379. main (
  1380. int argc,
  1381. char *argv[]
  1382. )
  1383. /*++
  1384. Routine Description:
  1385. Main
  1386. Arguments:
  1387. command line parameters
  1388. Returns:
  1389. EFI_SUCCESS Section header successfully generated and section concatenated.
  1390. EFI_ABORTED Could not generate the section
  1391. EFI_OUT_OF_RESOURCES No resource to complete the operation.
  1392. --*/
  1393. {
  1394. FILE *OutputFile;
  1395. char *OutputFileName;
  1396. char *InputFileName;
  1397. FILE *InputFile;
  1398. EFI_STATUS Status;
  1399. UINT8 *FileBuffer;
  1400. UINT8 *OutBuffer;
  1401. UINT32 InputLength;
  1402. UINT32 DstSize;
  1403. SCRATCH_DATA *Scratch;
  1404. UINT8 *Src;
  1405. UINT32 OrigSize;
  1406. UINT32 CompSize;
  1407. SetUtilityName(UTILITY_NAME);
  1408. FileBuffer = NULL;
  1409. Src = NULL;
  1410. OutBuffer = NULL;
  1411. Scratch = NULL;
  1412. OrigSize = 0;
  1413. CompSize = 0;
  1414. InputLength = 0;
  1415. InputFileName = NULL;
  1416. OutputFileName = NULL;
  1417. InputFile = NULL;
  1418. OutputFile = NULL;
  1419. DstSize=0;
  1420. DebugLevel = 0;
  1421. DebugMode = FALSE;
  1422. //
  1423. // Verify the correct number of arguments
  1424. //
  1425. if (argc == 1) {
  1426. Error (NULL, 0, 1001, "Missing options", "No input options specified.");
  1427. Usage();
  1428. return 0;
  1429. }
  1430. if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) {
  1431. Usage();
  1432. return 0;
  1433. }
  1434. if ((strcmp(argv[1], "--version") == 0)) {
  1435. Version();
  1436. return 0;
  1437. }
  1438. argc--;
  1439. argv++;
  1440. if (strcmp(argv[0],"-e") == 0) {
  1441. //
  1442. // encode the input file
  1443. //
  1444. ENCODE = TRUE;
  1445. argc--;
  1446. argv++;
  1447. } else if (strcmp(argv[0], "-d") == 0) {
  1448. //
  1449. // decode the input file
  1450. //
  1451. DECODE = TRUE;
  1452. argc--;
  1453. argv++;
  1454. } else {
  1455. //
  1456. // Error command line
  1457. //
  1458. Error (NULL, 0, 1003, "Invalid option value", "the options specified are not recognized.");
  1459. Usage();
  1460. return 1;
  1461. }
  1462. while (argc > 0) {
  1463. if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) {
  1464. VerboseMode = TRUE;
  1465. argc--;
  1466. argv++;
  1467. continue;
  1468. }
  1469. if (stricmp(argv[0], "--uefi") == 0) {
  1470. UEFIMODE = TRUE;
  1471. argc--;
  1472. argv++;
  1473. continue;
  1474. }
  1475. if (stricmp (argv[0], "--debug") == 0) {
  1476. argc-=2;
  1477. argv++;
  1478. Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel);
  1479. if (DebugLevel > 9) {
  1480. Error (NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]);
  1481. goto ERROR;
  1482. }
  1483. if (DebugLevel>=5 && DebugLevel <=9){
  1484. DebugMode = TRUE;
  1485. } else {
  1486. DebugMode = FALSE;
  1487. }
  1488. argv++;
  1489. continue;
  1490. }
  1491. if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--quiet") == 0)) {
  1492. QuietMode = TRUE;
  1493. argc--;
  1494. argv++;
  1495. continue;
  1496. }
  1497. if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) {
  1498. if (argv[1] == NULL || argv[1][0] == '-') {
  1499. Error (NULL, 0, 1003, "Invalid option value", "Output File name is missing for -o option");
  1500. goto ERROR;
  1501. }
  1502. OutputFileName = argv[1];
  1503. argc -=2;
  1504. argv +=2;
  1505. continue;
  1506. }
  1507. if (argv[0][0]!='-') {
  1508. InputFileName = argv[0];
  1509. argc--;
  1510. argv++;
  1511. continue;
  1512. }
  1513. Error (NULL, 0, 1000, "Unknown option", argv[0]);
  1514. goto ERROR;
  1515. }
  1516. if (InputFileName == NULL) {
  1517. Error (NULL, 0, 1001, "Missing options", "No input files specified.");
  1518. goto ERROR;
  1519. }
  1520. //
  1521. // All Parameters has been parsed, now set the message print level
  1522. //
  1523. if (QuietMode) {
  1524. SetPrintLevel(40);
  1525. } else if (VerboseMode) {
  1526. SetPrintLevel(15);
  1527. } else if (DebugMode) {
  1528. SetPrintLevel(DebugLevel);
  1529. }
  1530. if (VerboseMode) {
  1531. VerboseMsg("%s tool start.\n", UTILITY_NAME);
  1532. }
  1533. Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA));
  1534. if (Scratch == NULL) {
  1535. Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
  1536. goto ERROR;
  1537. }
  1538. InputFile = fopen (LongFilePath (InputFileName), "rb");
  1539. if (InputFile == NULL) {
  1540. Error (NULL, 0, 0001, "Error opening input file", InputFileName);
  1541. goto ERROR;
  1542. }
  1543. Status = GetFileContents(
  1544. InputFileName,
  1545. FileBuffer,
  1546. &InputLength);
  1547. if (Status == EFI_BUFFER_TOO_SMALL) {
  1548. FileBuffer = (UINT8 *) malloc (InputLength);
  1549. if (FileBuffer == NULL) {
  1550. Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
  1551. goto ERROR;
  1552. }
  1553. Status = GetFileContents (
  1554. InputFileName,
  1555. FileBuffer,
  1556. &InputLength
  1557. );
  1558. }
  1559. if (EFI_ERROR(Status)) {
  1560. Error (NULL, 0, 0004, "Error getting contents of file: %s", InputFileName);
  1561. goto ERROR;
  1562. }
  1563. if (OutputFileName == NULL) {
  1564. OutputFileName = DEFAULT_OUTPUT_FILE;
  1565. }
  1566. OutputFile = fopen (LongFilePath (OutputFileName), "wb");
  1567. if (OutputFile == NULL) {
  1568. Error (NULL, 0, 0001, "Error opening output file for writing", OutputFileName);
  1569. goto ERROR;
  1570. }
  1571. if (ENCODE) {
  1572. //
  1573. // First call TianoCompress to get DstSize
  1574. //
  1575. if (DebugMode) {
  1576. DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding", NULL);
  1577. }
  1578. if (UEFIMODE) {
  1579. Status = EfiCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
  1580. } else {
  1581. Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
  1582. }
  1583. if (Status == EFI_BUFFER_TOO_SMALL) {
  1584. OutBuffer = (UINT8 *) malloc (DstSize);
  1585. if (OutBuffer == NULL) {
  1586. Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
  1587. goto ERROR;
  1588. }
  1589. }
  1590. if (UEFIMODE) {
  1591. Status = EfiCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
  1592. } else {
  1593. Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
  1594. }
  1595. if (Status != EFI_SUCCESS) {
  1596. Error (NULL, 0, 0007, "Error compressing file", NULL);
  1597. goto ERROR;
  1598. }
  1599. if (OutBuffer == NULL) {
  1600. Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
  1601. goto ERROR;
  1602. }
  1603. fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile);
  1604. fclose(OutputFile);
  1605. fclose(InputFile);
  1606. free(Scratch);
  1607. free(FileBuffer);
  1608. free(OutBuffer);
  1609. if (DebugMode) {
  1610. DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Successful!\n", NULL);
  1611. }
  1612. if (VerboseMode) {
  1613. VerboseMsg("Encoding successful\n");
  1614. }
  1615. return 0;
  1616. }
  1617. else if (DECODE) {
  1618. if (DebugMode) {
  1619. DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding\n", NULL);
  1620. }
  1621. if (UEFIMODE) {
  1622. Status = Extract((VOID *)FileBuffer, InputLength, (VOID *)&OutBuffer, &DstSize, 1);
  1623. if (Status != EFI_SUCCESS) {
  1624. goto ERROR;
  1625. }
  1626. fwrite(OutBuffer, (size_t)(DstSize), 1, OutputFile);
  1627. } else {
  1628. if (InputLength < 8){
  1629. Error (NULL, 0, 3000, "Invalid", "The input file %s is too small.", InputFileName);
  1630. goto ERROR;
  1631. }
  1632. //
  1633. // Get Compressed file original size
  1634. //
  1635. Src = (UINT8 *)FileBuffer;
  1636. OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
  1637. CompSize = Src[0] + (Src[1] << 8) + (Src[2] <<16) + (Src[3] <<24);
  1638. //
  1639. // Allocate OutputBuffer
  1640. //
  1641. if (InputLength < CompSize + 8 || (CompSize + 8) < 8) {
  1642. Error (NULL, 0, 3000, "Invalid", "The input file %s data is invalid.", InputFileName);
  1643. goto ERROR;
  1644. }
  1645. OutBuffer = (UINT8 *)malloc(OrigSize);
  1646. if (OutBuffer == NULL) {
  1647. Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
  1648. goto ERROR;
  1649. }
  1650. Status = TDecompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2);
  1651. if (Status != EFI_SUCCESS) {
  1652. goto ERROR;
  1653. }
  1654. fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile);
  1655. }
  1656. fclose(OutputFile);
  1657. fclose(InputFile);
  1658. if (Scratch != NULL) {
  1659. free(Scratch);
  1660. }
  1661. if (FileBuffer != NULL) {
  1662. free(FileBuffer);
  1663. }
  1664. if (OutBuffer != NULL) {
  1665. free(OutBuffer);
  1666. }
  1667. if (DebugMode) {
  1668. DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding successful!\n", NULL);
  1669. }
  1670. if (VerboseMode) {
  1671. VerboseMsg("Decoding successful\n");
  1672. }
  1673. return 0;
  1674. }
  1675. ERROR:
  1676. if (DebugMode) {
  1677. if (ENCODE) {
  1678. DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Error\n", NULL);
  1679. } else if (DECODE) {
  1680. DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding Error\n", NULL);
  1681. }
  1682. }
  1683. if (OutputFile != NULL) {
  1684. fclose(OutputFile);
  1685. }
  1686. if (InputFile != NULL) {
  1687. fclose (InputFile);
  1688. }
  1689. if (Scratch != NULL) {
  1690. free(Scratch);
  1691. }
  1692. if (FileBuffer != NULL) {
  1693. free(FileBuffer);
  1694. }
  1695. if (OutBuffer != NULL) {
  1696. free(OutBuffer);
  1697. }
  1698. if (VerboseMode) {
  1699. VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ());
  1700. }
  1701. return GetUtilityStatus ();
  1702. }
  1703. VOID
  1704. FillBuf (
  1705. IN SCRATCH_DATA *Sd,
  1706. IN UINT16 NumOfBits
  1707. )
  1708. /*++
  1709. Routine Description:
  1710. Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
  1711. Arguments:
  1712. Sd - The global scratch data
  1713. NumOfBits - The number of bits to shift and read.
  1714. Returns: (VOID)
  1715. --*/
  1716. {
  1717. Sd->mBitBuf = (UINT32) (((UINT64)Sd->mBitBuf) << NumOfBits);
  1718. while (NumOfBits > Sd->mBitCount) {
  1719. Sd->mBitBuf |= (UINT32) (((UINT64)Sd->mSubBitBuf) << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));
  1720. if (Sd->mCompSize > 0) {
  1721. //
  1722. // Get 1 byte into SubBitBuf
  1723. //
  1724. Sd->mCompSize--;
  1725. Sd->mSubBitBuf = 0;
  1726. Sd->mSubBitBuf = Sd->mSrcBase[Sd->mInBuf++];
  1727. Sd->mBitCount = 8;
  1728. } else {
  1729. //
  1730. // No more bits from the source, just pad zero bit.
  1731. //
  1732. Sd->mSubBitBuf = 0;
  1733. Sd->mBitCount = 8;
  1734. }
  1735. }
  1736. Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);
  1737. Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;
  1738. }
  1739. UINT32
  1740. GetBits (
  1741. IN SCRATCH_DATA *Sd,
  1742. IN UINT16 NumOfBits
  1743. )
  1744. /*++
  1745. Routine Description:
  1746. Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
  1747. NumOfBits of bits from source. Returns NumOfBits of bits that are
  1748. popped out.
  1749. Arguments:
  1750. Sd - The global scratch data.
  1751. NumOfBits - The number of bits to pop and read.
  1752. Returns:
  1753. The bits that are popped out.
  1754. --*/
  1755. {
  1756. UINT32 OutBits;
  1757. OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
  1758. FillBuf (Sd, NumOfBits);
  1759. return OutBits;
  1760. }
  1761. UINT16
  1762. MakeTable (
  1763. IN SCRATCH_DATA *Sd,
  1764. IN UINT16 NumOfChar,
  1765. IN UINT8 *BitLen,
  1766. IN UINT16 TableBits,
  1767. OUT UINT16 *Table
  1768. )
  1769. /*++
  1770. Routine Description:
  1771. Creates Huffman Code mapping table according to code length array.
  1772. Arguments:
  1773. Sd - The global scratch data
  1774. NumOfChar - Number of symbols in the symbol set
  1775. BitLen - Code length array
  1776. TableBits - The width of the mapping table
  1777. Table - The table
  1778. Returns:
  1779. 0 - OK.
  1780. BAD_TABLE - The table is corrupted.
  1781. --*/
  1782. {
  1783. UINT16 Count[17];
  1784. UINT16 Weight[17];
  1785. UINT16 Start[18];
  1786. UINT16 *Pointer;
  1787. UINT16 Index3;
  1788. UINT16 Index;
  1789. UINT16 Len;
  1790. UINT16 Char;
  1791. UINT16 JuBits;
  1792. UINT16 Avail;
  1793. UINT16 NextCode;
  1794. UINT16 Mask;
  1795. UINT16 WordOfStart;
  1796. UINT16 WordOfCount;
  1797. UINT16 MaxTableLength;
  1798. for (Index = 0; Index <= 16; Index++) {
  1799. Count[Index] = 0;
  1800. }
  1801. for (Index = 0; Index < NumOfChar; Index++) {
  1802. if (BitLen[Index] > 16) {
  1803. return (UINT16) BAD_TABLE;
  1804. }
  1805. Count[BitLen[Index]]++;
  1806. }
  1807. Start[0] = 0;
  1808. Start[1] = 0;
  1809. for (Index = 1; Index <= 16; Index++) {
  1810. WordOfStart = Start[Index];
  1811. WordOfCount = Count[Index];
  1812. Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));
  1813. }
  1814. if (Start[17] != 0) {
  1815. //
  1816. //(1U << 16)
  1817. //
  1818. return (UINT16) BAD_TABLE;
  1819. }
  1820. JuBits = (UINT16) (16 - TableBits);
  1821. Weight[0] = 0;
  1822. for (Index = 1; Index <= TableBits; Index++) {
  1823. Start[Index] >>= JuBits;
  1824. Weight[Index] = (UINT16) (1U << (TableBits - Index));
  1825. }
  1826. while (Index <= 16) {
  1827. Weight[Index] = (UINT16) (1U << (16 - Index));
  1828. Index++;
  1829. }
  1830. Index = (UINT16) (Start[TableBits + 1] >> JuBits);
  1831. if (Index != 0) {
  1832. Index3 = (UINT16) (1U << TableBits);
  1833. while (Index != Index3) {
  1834. Table[Index++] = 0;
  1835. }
  1836. }
  1837. Avail = NumOfChar;
  1838. Mask = (UINT16) (1U << (15 - TableBits));
  1839. MaxTableLength = (UINT16) (1U << TableBits);
  1840. for (Char = 0; Char < NumOfChar; Char++) {
  1841. Len = BitLen[Char];
  1842. if (Len == 0 || Len >= 17) {
  1843. continue;
  1844. }
  1845. NextCode = (UINT16) (Start[Len] + Weight[Len]);
  1846. if (Len <= TableBits) {
  1847. for (Index = Start[Len]; Index < NextCode; Index++) {
  1848. if (Index >= MaxTableLength) {
  1849. return (UINT16) BAD_TABLE;
  1850. }
  1851. Table[Index] = Char;
  1852. }
  1853. } else {
  1854. Index3 = Start[Len];
  1855. Pointer = &Table[Index3 >> JuBits];
  1856. Index = (UINT16) (Len - TableBits);
  1857. while (Index != 0) {
  1858. if (*Pointer == 0) {
  1859. Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
  1860. *Pointer = Avail++;
  1861. }
  1862. if (Index3 & Mask) {
  1863. Pointer = &Sd->mRight[*Pointer];
  1864. } else {
  1865. Pointer = &Sd->mLeft[*Pointer];
  1866. }
  1867. Index3 <<= 1;
  1868. Index--;
  1869. }
  1870. *Pointer = Char;
  1871. }
  1872. Start[Len] = NextCode;
  1873. }
  1874. //
  1875. // Succeeds
  1876. //
  1877. return 0;
  1878. }
  1879. UINT32
  1880. DecodeP (
  1881. IN SCRATCH_DATA *Sd
  1882. )
  1883. /*++
  1884. Routine Description:
  1885. Decodes a position value.
  1886. Arguments:
  1887. Sd - the global scratch data
  1888. Returns:
  1889. The position value decoded.
  1890. --*/
  1891. {
  1892. UINT16 Val;
  1893. UINT32 Mask;
  1894. UINT32 Pos;
  1895. Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
  1896. if (Val >= MAXNP) {
  1897. Mask = 1U << (BITBUFSIZ - 1 - 8);
  1898. do {
  1899. if (Sd->mBitBuf & Mask) {
  1900. Val = Sd->mRight[Val];
  1901. } else {
  1902. Val = Sd->mLeft[Val];
  1903. }
  1904. Mask >>= 1;
  1905. } while (Val >= MAXNP);
  1906. }
  1907. //
  1908. // Advance what we have read
  1909. //
  1910. FillBuf (Sd, Sd->mPTLen[Val]);
  1911. Pos = Val;
  1912. if (Val > 1) {
  1913. Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
  1914. }
  1915. return Pos;
  1916. }
  1917. UINT16
  1918. ReadPTLen (
  1919. IN SCRATCH_DATA *Sd,
  1920. IN UINT16 nn,
  1921. IN UINT16 nbit,
  1922. IN UINT16 Special
  1923. )
  1924. /*++
  1925. Routine Description:
  1926. Reads code lengths for the Extra Set or the Position Set
  1927. Arguments:
  1928. Sd - The global scratch data
  1929. nn - Number of symbols
  1930. nbit - Number of bits needed to represent nn
  1931. Special - The special symbol that needs to be taken care of
  1932. Returns:
  1933. 0 - OK.
  1934. BAD_TABLE - Table is corrupted.
  1935. --*/
  1936. {
  1937. UINT16 Number;
  1938. UINT16 CharC;
  1939. volatile UINT16 Index;
  1940. UINT32 Mask;
  1941. assert (nn <= NPT);
  1942. Number = (UINT16) GetBits (Sd, nbit);
  1943. if (Number == 0) {
  1944. CharC = (UINT16) GetBits (Sd, nbit);
  1945. for (Index = 0; Index < 256; Index++) {
  1946. Sd->mPTTable[Index] = CharC;
  1947. }
  1948. for (Index = 0; Index < nn; Index++) {
  1949. Sd->mPTLen[Index] = 0;
  1950. }
  1951. return 0;
  1952. }
  1953. Index = 0;
  1954. while (Index < Number) {
  1955. CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
  1956. if (CharC == 7) {
  1957. Mask = 1U << (BITBUFSIZ - 1 - 3);
  1958. while (Mask & Sd->mBitBuf) {
  1959. Mask >>= 1;
  1960. CharC += 1;
  1961. }
  1962. }
  1963. FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
  1964. Sd->mPTLen[Index++] = (UINT8) CharC;
  1965. if (Index == Special) {
  1966. CharC = (UINT16) GetBits (Sd, 2);
  1967. while ((INT16) (--CharC) >= 0) {
  1968. Sd->mPTLen[Index++] = 0;
  1969. }
  1970. }
  1971. }
  1972. while (Index < nn) {
  1973. Sd->mPTLen[Index++] = 0;
  1974. }
  1975. return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
  1976. }
  1977. VOID
  1978. ReadCLen (
  1979. SCRATCH_DATA *Sd
  1980. )
  1981. /*++
  1982. Routine Description:
  1983. Reads code lengths for Char&Len Set.
  1984. Arguments:
  1985. Sd - the global scratch data
  1986. Returns: (VOID)
  1987. --*/
  1988. {
  1989. UINT16 Number;
  1990. UINT16 CharC;
  1991. volatile UINT16 Index;
  1992. UINT32 Mask;
  1993. Number = (UINT16) GetBits (Sd, CBIT);
  1994. if (Number == 0) {
  1995. CharC = (UINT16) GetBits (Sd, CBIT);
  1996. for (Index = 0; Index < NC; Index++) {
  1997. Sd->mCLen[Index] = 0;
  1998. }
  1999. for (Index = 0; Index < 4096; Index++) {
  2000. Sd->mCTable[Index] = CharC;
  2001. }
  2002. return ;
  2003. }
  2004. Index = 0;
  2005. while (Index < Number) {
  2006. CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
  2007. if (CharC >= NT) {
  2008. Mask = 1U << (BITBUFSIZ - 1 - 8);
  2009. do {
  2010. if (Mask & Sd->mBitBuf) {
  2011. CharC = Sd->mRight[CharC];
  2012. } else {
  2013. CharC = Sd->mLeft[CharC];
  2014. }
  2015. Mask >>= 1;
  2016. } while (CharC >= NT);
  2017. }
  2018. //
  2019. // Advance what we have read
  2020. //
  2021. FillBuf (Sd, Sd->mPTLen[CharC]);
  2022. if (CharC <= 2) {
  2023. if (CharC == 0) {
  2024. CharC = 1;
  2025. } else if (CharC == 1) {
  2026. CharC = (UINT16) (GetBits (Sd, 4) + 3);
  2027. } else if (CharC == 2) {
  2028. CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
  2029. }
  2030. while ((INT16) (--CharC) >= 0) {
  2031. Sd->mCLen[Index++] = 0;
  2032. }
  2033. } else {
  2034. Sd->mCLen[Index++] = (UINT8) (CharC - 2);
  2035. }
  2036. }
  2037. while (Index < NC) {
  2038. Sd->mCLen[Index++] = 0;
  2039. }
  2040. MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
  2041. return ;
  2042. }
  2043. UINT16
  2044. DecodeC (
  2045. SCRATCH_DATA *Sd
  2046. )
  2047. /*++
  2048. Routine Description:
  2049. Decode a character/length value.
  2050. Arguments:
  2051. Sd - The global scratch data.
  2052. Returns:
  2053. The value decoded.
  2054. --*/
  2055. {
  2056. UINT16 Index2;
  2057. UINT32 Mask;
  2058. if (Sd->mBlockSize == 0) {
  2059. //
  2060. // Starting a new block
  2061. //
  2062. Sd->mBlockSize = (UINT16) GetBits (Sd, 16);
  2063. Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
  2064. if (Sd->mBadTableFlag != 0) {
  2065. return 0;
  2066. }
  2067. ReadCLen (Sd);
  2068. Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
  2069. if (Sd->mBadTableFlag != 0) {
  2070. return 0;
  2071. }
  2072. }
  2073. Sd->mBlockSize--;
  2074. Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
  2075. if (Index2 >= NC) {
  2076. Mask = 1U << (BITBUFSIZ - 1 - 12);
  2077. do {
  2078. if (Sd->mBitBuf & Mask) {
  2079. Index2 = Sd->mRight[Index2];
  2080. } else {
  2081. Index2 = Sd->mLeft[Index2];
  2082. }
  2083. Mask >>= 1;
  2084. } while (Index2 >= NC);
  2085. }
  2086. //
  2087. // Advance what we have read
  2088. //
  2089. FillBuf (Sd, Sd->mCLen[Index2]);
  2090. return Index2;
  2091. }
  2092. VOID
  2093. Decode (
  2094. SCRATCH_DATA *Sd
  2095. )
  2096. /*++
  2097. Routine Description:
  2098. Decode the source data and put the resulting data into the destination buffer.
  2099. Arguments:
  2100. Sd - The global scratch data
  2101. Returns: (VOID)
  2102. --*/
  2103. {
  2104. UINT16 BytesRemain;
  2105. UINT32 DataIdx;
  2106. UINT16 CharC;
  2107. BytesRemain = (UINT16) (-1);
  2108. DataIdx = 0;
  2109. for (;;) {
  2110. CharC = DecodeC (Sd);
  2111. if (Sd->mBadTableFlag != 0) {
  2112. goto Done ;
  2113. }
  2114. if (CharC < 256) {
  2115. //
  2116. // Process an Original character
  2117. //
  2118. if (Sd->mOutBuf >= Sd->mOrigSize) {
  2119. goto Done ;
  2120. } else {
  2121. Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
  2122. }
  2123. } else {
  2124. //
  2125. // Process a Pointer
  2126. //
  2127. CharC = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));
  2128. BytesRemain = CharC;
  2129. DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;
  2130. BytesRemain--;
  2131. while ((INT16) (BytesRemain) >= 0) {
  2132. if (Sd->mOutBuf >= Sd->mOrigSize) {
  2133. goto Done ;
  2134. }
  2135. if (DataIdx >= Sd->mOrigSize) {
  2136. Sd->mBadTableFlag = (UINT16) BAD_TABLE;
  2137. goto Done ;
  2138. }
  2139. Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
  2140. BytesRemain--;
  2141. }
  2142. //
  2143. // Once mOutBuf is fully filled, directly return
  2144. //
  2145. if (Sd->mOutBuf >= Sd->mOrigSize) {
  2146. goto Done ;
  2147. }
  2148. }
  2149. }
  2150. Done:
  2151. return ;
  2152. }
  2153. RETURN_STATUS
  2154. EFIAPI
  2155. TDecompress (
  2156. IN VOID *Source,
  2157. IN OUT VOID *Destination,
  2158. IN OUT VOID *Scratch,
  2159. IN UINT32 Version
  2160. )
  2161. /*++
  2162. Routine Description:
  2163. The internal implementation of Decompress().
  2164. Arguments:
  2165. Source - The source buffer containing the compressed data.
  2166. Destination - The destination buffer to store the decompressed data
  2167. Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
  2168. Version - 1 for EFI1.1 Decompress algorithm, 2 for Tiano Decompress algorithm
  2169. Returns:
  2170. RETURN_SUCCESS - Decompression is successful
  2171. RETURN_INVALID_PARAMETER - The source data is corrupted
  2172. --*/
  2173. {
  2174. volatile UINT32 Index;
  2175. UINT32 CompSize;
  2176. UINT32 OrigSize;
  2177. SCRATCH_DATA *Sd;
  2178. CONST UINT8 *Src;
  2179. UINT8 *Dst;
  2180. //
  2181. // Verify input is not NULL
  2182. //
  2183. assert(Source);
  2184. // assert(Destination);
  2185. assert(Scratch);
  2186. Src = (UINT8 *)Source;
  2187. Dst = (UINT8 *)Destination;
  2188. Sd = (SCRATCH_DATA *) Scratch;
  2189. CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
  2190. OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
  2191. //
  2192. // If compressed file size is 0, return
  2193. //
  2194. if (OrigSize == 0) {
  2195. return RETURN_SUCCESS;
  2196. }
  2197. Src = Src + 8;
  2198. for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
  2199. ((UINT8 *) Sd)[Index] = 0;
  2200. }
  2201. //
  2202. // The length of the field 'Position Set Code Length Array Size' in Block Header.
  2203. // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
  2204. // For Tiano de/compression algorithm(Version 2), mPBit = 5
  2205. //
  2206. switch (Version) {
  2207. case 1 :
  2208. Sd->mPBit = 4;
  2209. break;
  2210. case 2 :
  2211. Sd->mPBit = 5;
  2212. break;
  2213. default:
  2214. assert(FALSE);
  2215. }
  2216. Sd->mSrcBase = (UINT8 *)Src;
  2217. Sd->mDstBase = Dst;
  2218. Sd->mCompSize = CompSize;
  2219. Sd->mOrigSize = OrigSize;
  2220. //
  2221. // Fill the first BITBUFSIZ bits
  2222. //
  2223. FillBuf (Sd, BITBUFSIZ);
  2224. //
  2225. // Decompress it
  2226. //
  2227. Decode (Sd);
  2228. if (Sd->mBadTableFlag != 0) {
  2229. //
  2230. // Something wrong with the source
  2231. //
  2232. return RETURN_INVALID_PARAMETER;
  2233. }
  2234. return RETURN_SUCCESS;
  2235. }