[efi] Compress EFI ROM imageseficompress

Use the reference implementation of the EFI compression algorithm
(taken from the EDK2 codebase, with minor bugfixes to allow
compilation with -Werror) to compress EFI ROM images.

Inspired-by: Laszlo Ersek <lersek@redhat.com>
Signed-off-by: Michael Brown <mcb30@ipxe.org>

4 files changed, 1652 insertions, 6 deletions

diff --git a/src/Makefile.efi b/src/Makefile.efi
index 4b35381..11e29dd 100644
--- a/src/Makefile.efi
+++ b/src/Makefile.efi
@@ -43,7 +43,7 @@ $(BIN)/%.drv.efi : $(BIN)/%.efidrv
 
 $(BIN)/%.efirom : $(BIN)/%.efidrv $(EFIROM)
 	$(QM)$(ECHO) "  [FINISH] $@"
-	$(Q)$(EFIROM) -v $(TGT_PCI_VENDOR) -d $(TGT_PCI_DEVICE) $< $@
+	$(Q)$(EFIROM) -v $(TGT_PCI_VENDOR) -d $(TGT_PCI_DEVICE) -c $< $@
 
 $(BIN)/efidrv.cab : $(BIN)/alldrv.efis # $(ALL_drv.efi) is not yet defined
 	$(QM)$(ECHO) "  [CAB] $@"
diff --git a/src/Makefile.housekeeping b/src/Makefile.housekeeping
index 8e769c6..2c2c8a1 100644
--- a/src/Makefile.housekeeping
+++ b/src/Makefile.housekeeping
@@ -1425,7 +1425,7 @@ $(ELF2EFI64) : util/elf2efi.c $(MAKEDEPS)
 	$(Q)$(HOST_CC) $(HOST_CFLAGS) -idirafter include -DEFI_TARGET64 $< -o $@
 CLEANUP += $(ELF2EFI64)
 
-$(EFIROM) : util/efirom.c $(MAKEDEPS)
+$(EFIROM) : util/efirom.c util/eficompress.c $(MAKEDEPS)
 	$(QM)$(ECHO) "  [HOSTCC] $@"
 	$(Q)$(HOST_CC) $(HOST_CFLAGS) -idirafter include -o $@ $<
 CLEANUP += $(EFIROM)
diff --git a/src/util/eficompress.c b/src/util/eficompress.c
new file mode 100644
index 0000000..4fd74cc
--- /dev/null
+++ b/src/util/eficompress.c
@@ -0,0 +1,1588 @@
+/** @file
+Compression routine. The compression algorithm is a mixture of LZ77 and Huffman
+coding. LZ77 transforms the source data into a sequence of Original Characters
+and Pointers to repeated strings. This sequence is further divided into Blocks
+and Huffman codings are applied to each Block.
+
+Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>
+SPDX-License-Identifier: BSD-2-Clause-Patent
+
+**/
+
+//
+// Macro Definitions
+//
+
+#undef UINT8_MAX
+typedef INT16             NODE;
+#define UINT8_MAX         0xff
+#define UINT8_BIT         8
+#define THRESHOLD         3
+#define INIT_CRC          0
+#define WNDBIT            13
+#define WNDSIZ            (1 << WNDBIT)
+#define MAXMATCH          256
+#define PERC_FLAG         0x8000U
+#define CODE_BIT          16
+#define NIL               0
+#define MAX_HASH_VAL      (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
+#define HASH(p, c)        ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
+#define CRCPOLY           0xA001
+#define UPDATE_CRC(c)     mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
+
+//
+// C: the Char&Len Set; P: the Position Set; T: the exTra Set
+//
+
+#define NC                (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
+#define CBIT              9
+#define NP                (WNDBIT + 1)
+#define PBIT              4
+#define NT                (CODE_BIT + 3)
+#define TBIT              5
+#if NT > NP
+  #define                 NPT NT
+#else
+  #define                 NPT NP
+#endif
+
+//
+// Function Prototypes
+//
+
+STATIC
+VOID
+PutDword(
+  IN UINT32 Data
+  );
+
+STATIC
+EFI_STATUS
+AllocateMemory (
+  );
+
+STATIC
+VOID
+FreeMemory (
+  );
+
+STATIC
+VOID
+InitSlide (
+  );
+
+STATIC
+NODE
+Child (
+  IN NODE q,
+  IN UINT8 c
+  );
+
+STATIC
+VOID
+MakeChild (
+  IN NODE q,
+  IN UINT8 c,
+  IN NODE r
+  );
+
+STATIC
+VOID
+Split (
+  IN NODE Old
+  );
+
+STATIC
+VOID
+InsertNode (
+  );
+
+STATIC
+VOID
+DeleteNode (
+  );
+
+STATIC
+VOID
+GetNextMatch (
+  );
+
+STATIC
+EFI_STATUS
+Encode (
+  );
+
+STATIC
+VOID
+CountTFreq (
+  );
+
+STATIC
+VOID
+WritePTLen (
+  IN INT32 n,
+  IN INT32 nbit,
+  IN INT32 Special
+  );
+
+STATIC
+VOID
+WriteCLen (
+  );
+
+STATIC
+VOID
+EncodeC (
+  IN INT32 c
+  );
+
+STATIC
+VOID
+EncodeP (
+  IN UINT32 p
+  );
+
+STATIC
+VOID
+SendBlock (
+  );
+
+STATIC
+VOID
+Output (
+  IN UINT32 c,
+  IN UINT32 p
+  );
+
+STATIC
+VOID
+HufEncodeStart (
+  );
+
+STATIC
+VOID
+HufEncodeEnd (
+  );
+
+STATIC
+VOID
+MakeCrcTable (
+  );
+
+STATIC
+VOID
+PutBits (
+  IN INT32 n,
+  IN UINT32 x
+  );
+
+STATIC
+INT32
+FreadCrc (
+  OUT UINT8 *p,
+  IN  INT32 n
+  );
+
+STATIC
+VOID
+InitPutBits (
+  );
+
+STATIC
+VOID
+CountLen (
+  IN INT32 i
+  );
+
+STATIC
+VOID
+MakeLen (
+  IN INT32 Root
+  );
+
+STATIC
+VOID
+DownHeap (
+  IN INT32 i
+  );
+
+STATIC
+VOID
+MakeCode (
+  IN  INT32 n,
+  IN  UINT8 Len[],
+  OUT UINT16 Code[]
+  );
+
+STATIC
+INT32
+MakeTree (
+  IN  INT32   NParm,
+  IN  UINT16  FreqParm[],
+  OUT UINT8   LenParm[],
+  OUT UINT16  CodeParm[]
+  );
+
+
+//
+//  Global Variables
+//
+
+STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
+
+STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
+STATIC INT16  mHeap[NC + 1];
+STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
+STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
+STATIC UINT32 mCompSize, mOrigSize;
+
+STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1],
+              mCrcTable[UINT8_MAX + 1], mCFreq[2 * NC - 1],mCCode[NC],
+              mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
+
+STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
+
+
+//
+// functions
+//
+
+EFI_STATUS
+EfiCompress (
+  IN      UINT8   *SrcBuffer,
+  IN      UINT32  SrcSize,
+  IN      UINT8   *DstBuffer,
+  IN OUT  UINT32  *DstSize
+  )
+/*++
+
+Routine Description:
+
+  The main compression routine.
+
+Arguments:
+
+  SrcBuffer   - The buffer storing the source data
+  SrcSize     - The size of source data
+  DstBuffer   - The buffer to store the compressed data
+  DstSize     - On input, the size of DstBuffer; On output,
+                the size of the actual compressed data.
+
+Returns:
+
+  EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,
+                DstSize contains the size needed.
+  EFI_SUCCESS           - Compression is successful.
+
+--*/
+{
+  EFI_STATUS Status = EFI_SUCCESS;
+
+  //
+  // Initializations
+  //
+  mBufSiz = 0;
+  mBuf = NULL;
+  mText       = NULL;
+  mLevel      = NULL;
+  mChildCount = NULL;
+  mPosition   = NULL;
+  mParent     = NULL;
+  mPrev       = NULL;
+  mNext       = NULL;
+
+
+  mSrc = SrcBuffer;
+  mSrcUpperLimit = mSrc + SrcSize;
+  mDst = DstBuffer;
+  mDstUpperLimit = mDst + *DstSize;
+
+  PutDword(0L);
+  PutDword(0L);
+
+  MakeCrcTable ();
+
+  mOrigSize = mCompSize = 0;
+  mCrc = INIT_CRC;
+
+  //
+  // Compress it
+  //
+
+  Status = Encode();
+  if (EFI_ERROR (Status)) {
+    return EFI_OUT_OF_RESOURCES;
+  }
+
+  //
+  // Null terminate the compressed data
+  //
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = 0;
+  }
+
+  //
+  // Fill in compressed size and original size
+  //
+  mDst = DstBuffer;
+  PutDword(mCompSize+1);
+  PutDword(mOrigSize);
+
+  //
+  // Return
+  //
+
+  if (mCompSize + 1 + 8 > *DstSize) {
+    *DstSize = mCompSize + 1 + 8;
+    return EFI_BUFFER_TOO_SMALL;
+  } else {
+    *DstSize = mCompSize + 1 + 8;
+    return EFI_SUCCESS;
+  }
+
+}
+
+STATIC
+VOID
+PutDword(
+  IN UINT32 Data
+  )
+/*++
+
+Routine Description:
+
+  Put a dword to output stream
+
+Arguments:
+
+  Data    - the dword to put
+
+Returns: (VOID)
+
+--*/
+{
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = (UINT8)(((UINT8)(Data        )) & 0xff);
+  }
+
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = (UINT8)(((UINT8)(Data >> 0x08)) & 0xff);
+  }
+
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = (UINT8)(((UINT8)(Data >> 0x10)) & 0xff);
+  }
+
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = (UINT8)(((UINT8)(Data >> 0x18)) & 0xff);
+  }
+}
+
+STATIC
+EFI_STATUS
+AllocateMemory ()
+/*++
+
+Routine Description:
+
+  Allocate memory spaces for data structures used in compression process
+
+Arguments: (VOID)
+
+Returns:
+
+  EFI_SUCCESS           - Memory is allocated successfully
+  EFI_OUT_OF_RESOURCES  - Allocation fails
+
+--*/
+{
+  UINT32      i;
+
+  mText       = malloc (WNDSIZ * 2 + MAXMATCH);
+  if (mText == NULL) {
+    return EFI_OUT_OF_RESOURCES;
+  }
+  for (i = 0 ; i < WNDSIZ * 2 + MAXMATCH; i ++) {
+    mText[i] = 0;
+  }
+
+  mLevel      = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mLevel));
+  mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mChildCount));
+  mPosition   = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mPosition));
+  mParent     = malloc (WNDSIZ * 2 * sizeof(*mParent));
+  mPrev       = malloc (WNDSIZ * 2 * sizeof(*mPrev));
+  mNext       = malloc ((MAX_HASH_VAL + 1) * sizeof(*mNext));
+  if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
+    mParent == NULL || mPrev == NULL || mNext == NULL) {
+    return EFI_OUT_OF_RESOURCES;
+  }
+
+  mBufSiz = 16 * 1024U;
+  while ((mBuf = malloc(mBufSiz)) == NULL) {
+    mBufSiz = (mBufSiz / 10U) * 9U;
+    if (mBufSiz < 4 * 1024U) {
+      return EFI_OUT_OF_RESOURCES;
+    }
+  }
+  mBuf[0] = 0;
+
+  return EFI_SUCCESS;
+}
+
+VOID
+FreeMemory ()
+/*++
+
+Routine Description:
+
+  Called when compression is completed to free memory previously allocated.
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  if (mText) {
+    free (mText);
+  }
+
+  if (mLevel) {
+    free (mLevel);
+  }
+
+  if (mChildCount) {
+    free (mChildCount);
+  }
+
+  if (mPosition) {
+    free (mPosition);
+  }
+
+  if (mParent) {
+    free (mParent);
+  }
+
+  if (mPrev) {
+    free (mPrev);
+  }
+
+  if (mNext) {
+    free (mNext);
+  }
+
+  if (mBuf) {
+    free (mBuf);
+  }
+
+  return;
+}
+
+
+STATIC
+VOID
+InitSlide ()
+/*++
+
+Routine Description:
+
+  Initialize String Info Log data structures
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  NODE i;
+
+  for (i = WNDSIZ; i <= WNDSIZ + UINT8_MAX; i++) {
+    mLevel[i] = 1;
+    mPosition[i] = NIL;  /* sentinel */
+  }
+  for (i = WNDSIZ; i < WNDSIZ * 2; i++) {
+    mParent[i] = NIL;
+  }
+  mAvail = 1;
+  for (i = 1; i < WNDSIZ - 1; i++) {
+    mNext[i] = (NODE)(i + 1);
+  }
+
+  mNext[WNDSIZ - 1] = NIL;
+  for (i = WNDSIZ * 2; i <= MAX_HASH_VAL; i++) {
+    mNext[i] = NIL;
+  }
+}
+
+
+STATIC
+NODE
+Child (
+  IN NODE q,
+  IN UINT8 c
+  )
+/*++
+
+Routine Description:
+
+  Find child node given the parent node and the edge character
+
+Arguments:
+
+  q       - the parent node
+  c       - the edge character
+
+Returns:
+
+  The child node (NIL if not found)
+
+--*/
+{
+  NODE r;
+
+  r = mNext[HASH(q, c)];
+  mParent[NIL] = q;  /* sentinel */
+  while (mParent[r] != q) {
+    r = mNext[r];
+  }
+
+  return r;
+}
+
+STATIC
+VOID
+MakeChild (
+  IN NODE q,
+  IN UINT8 c,
+  IN NODE r
+  )
+/*++
+
+Routine Description:
+
+  Create a new child for a given parent node.
+
+Arguments:
+
+  q       - the parent node
+  c       - the edge character
+  r       - the child node
+
+Returns: (VOID)
+
+--*/
+{
+  NODE h, t;
+
+  h = (NODE)HASH(q, c);
+  t = mNext[h];
+  mNext[h] = r;
+  mNext[r] = t;
+  mPrev[t] = r;
+  mPrev[r] = h;
+  mParent[r] = q;
+  mChildCount[q]++;
+}
+
+STATIC
+VOID
+Split (
+  NODE Old
+  )
+/*++
+
+Routine Description:
+
+  Split a node.
+
+Arguments:
+
+  Old     - the node to split
+
+Returns: (VOID)
+
+--*/
+{
+  NODE New, t;
+
+  New = mAvail;
+  mAvail = mNext[New];
+  mChildCount[New] = 0;
+  t = mPrev[Old];
+  mPrev[New] = t;
+  mNext[t] = New;
+  t = mNext[Old];
+  mNext[New] = t;
+  mPrev[t] = New;
+  mParent[New] = mParent[Old];
+  mLevel[New] = (UINT8)mMatchLen;
+  mPosition[New] = mPos;
+  MakeChild(New, mText[mMatchPos + mMatchLen], Old);
+  MakeChild(New, mText[mPos + mMatchLen], mPos);
+}
+
+STATIC
+VOID
+InsertNode ()
+/*++
+
+Routine Description:
+
+  Insert string info for current position into the String Info Log
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  NODE q, r, j, t;
+  UINT8 c, *t1, *t2;
+
+  if (mMatchLen >= 4) {
+
+    //
+    // We have just got a long match, the target tree
+    // can be located by MatchPos + 1. Traverse the tree
+    // from bottom up to get to a proper starting point.
+    // The usage of PERC_FLAG ensures proper node deletion
+    // in DeleteNode() later.
+    //
+
+    mMatchLen--;
+    r = (INT16)((mMatchPos + 1) | WNDSIZ);
+    while ((q = mParent[r]) == NIL) {
+      r = mNext[r];
+    }
+    while (mLevel[q] >= mMatchLen) {
+      r = q;  q = mParent[q];
+    }
+    t = q;
+    while (mPosition[t] < 0) {
+      mPosition[t] = mPos;
+      t = mParent[t];
+    }
+    if (t < WNDSIZ) {
+      mPosition[t] = (NODE)(mPos | PERC_FLAG);
+    }
+  } else {
+
+    //
+    // Locate the target tree
+    //
+
+    q = (INT16)(mText[mPos] + WNDSIZ);
+    c = mText[mPos + 1];
+    if ((r = Child(q, c)) == NIL) {
+      MakeChild(q, c, mPos);
+      mMatchLen = 1;
+      return;
+    }
+    mMatchLen = 2;
+  }
+
+  //
+  // Traverse down the tree to find a match.
+  // Update Position value along the route.
+  // Node split or creation is involved.
+  //
+
+  for ( ; ; ) {
+    if (r >= WNDSIZ) {
+      j = MAXMATCH;
+      mMatchPos = r;
+    } else {
+      j = mLevel[r];
+      mMatchPos = (NODE)(mPosition[r] & ~PERC_FLAG);
+    }
+    if (mMatchPos >= mPos) {
+      mMatchPos -= WNDSIZ;
+    }
+    t1 = &mText[mPos + mMatchLen];
+    t2 = &mText[mMatchPos + mMatchLen];
+    while (mMatchLen < j) {
+      if (*t1 != *t2) {
+        Split(r);
+        return;
+      }
+      mMatchLen++;
+      t1++;
+      t2++;
+    }
+    if (mMatchLen >= MAXMATCH) {
+      break;
+    }
+    mPosition[r] = mPos;
+    q = r;
+    if ((r = Child(q, *t1)) == NIL) {
+      MakeChild(q, *t1, mPos);
+      return;
+    }
+    mMatchLen++;
+  }
+  t = mPrev[r];
+  mPrev[mPos] = t;
+  mNext[t] = mPos;
+  t = mNext[r];
+  mNext[mPos] = t;
+  mPrev[t] = mPos;
+  mParent[mPos] = q;
+  mParent[r] = NIL;
+
+  //
+  // Special usage of 'next'
+  //
+  mNext[r] = mPos;
+
+}
+
+STATIC
+VOID
+DeleteNode ()
+/*++
+
+Routine Description:
+
+  Delete outdated string info. (The Usage of PERC_FLAG
+  ensures a clean deletion)
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  NODE q, r, s, t, u;
+
+  if (mParent[mPos] == NIL) {
+    return;
+  }
+
+  r = mPrev[mPos];
+  s = mNext[mPos];
+  mNext[r] = s;
+  mPrev[s] = r;
+  r = mParent[mPos];
+  mParent[mPos] = NIL;
+  if (r >= WNDSIZ || --mChildCount[r] > 1) {
+    return;
+  }
+  t = (NODE)(mPosition[r] & ~PERC_FLAG);
+  if (t >= mPos) {
+    t -= WNDSIZ;
+  }
+  s = t;
+  q = mParent[r];
+  while ((u = mPosition[q]) & PERC_FLAG) {
+    u &= ~PERC_FLAG;
+    if (u >= mPos) {
+      u -= WNDSIZ;
+    }
+    if (u > s) {
+      s = u;
+    }
+    mPosition[q] = (INT16)(s | WNDSIZ);
+    q = mParent[q];
+  }
+  if (q < WNDSIZ) {
+    if (u >= mPos) {
+      u -= WNDSIZ;
+    }
+    if (u > s) {
+      s = u;
+    }
+    mPosition[q] = (INT16)(s | WNDSIZ | PERC_FLAG);
+  }
+  s = Child(r, mText[t + mLevel[r]]);
+  t = mPrev[s];
+  u = mNext[s];
+  mNext[t] = u;
+  mPrev[u] = t;
+  t = mPrev[r];
+  mNext[t] = s;
+  mPrev[s] = t;
+  t = mNext[r];
+  mPrev[t] = s;
+  mNext[s] = t;
+  mParent[s] = mParent[r];
+  mParent[r] = NIL;
+  mNext[r] = mAvail;
+  mAvail = r;
+}
+
+STATIC
+VOID
+GetNextMatch ()
+/*++
+
+Routine Description:
+
+  Advance the current position (read in new data if needed).
+  Delete outdated string info. Find a match string for current position.
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  INT32 n;
+
+  mRemainder--;
+  if (++mPos == WNDSIZ * 2) {
+    memmove(&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
+    n = FreadCrc(&mText[WNDSIZ + MAXMATCH], WNDSIZ);
+    mRemainder += n;
+    mPos = WNDSIZ;
+  }
+  DeleteNode();
+  InsertNode();
+}
+
+STATIC
+EFI_STATUS
+Encode ()
+/*++
+
+Routine Description:
+
+  The main controlling routine for compression process.
+
+Arguments: (VOID)
+
+Returns:
+
+  EFI_SUCCESS           - The compression is successful
+  EFI_OUT_0F_RESOURCES  - Not enough memory for compression process
+
+--*/
+{
+  EFI_STATUS  Status;
+  INT32       LastMatchLen;
+  NODE        LastMatchPos;
+
+  Status = AllocateMemory();
+  if (EFI_ERROR(Status)) {
+    FreeMemory();
+    return Status;
+  }
+
+  InitSlide();
+
+  HufEncodeStart();
+
+  mRemainder = FreadCrc(&mText[WNDSIZ], WNDSIZ + MAXMATCH);
+
+  mMatchLen = 0;
+  mPos = WNDSIZ;
+  InsertNode();
+  if (mMatchLen > mRemainder) {
+    mMatchLen = mRemainder;
+  }
+  while (mRemainder > 0) {
+    LastMatchLen = mMatchLen;
+    LastMatchPos = mMatchPos;
+    GetNextMatch();
+    if (mMatchLen > mRemainder) {
+      mMatchLen = mRemainder;
+    }
+
+    if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
+
+      //
+      // Not enough benefits are gained by outputting a pointer,
+      // so just output the original character
+      //
+
+      Output(mText[mPos - 1], 0);
+    } else {
+
+      //
+      // Outputting a pointer is beneficial enough, do it.
+      //
+
+      Output(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
+             (mPos - LastMatchPos - 2) & (WNDSIZ - 1));
+      while (--LastMatchLen > 0) {
+        GetNextMatch();
+      }
+      if (mMatchLen > mRemainder) {
+        mMatchLen = mRemainder;
+      }
+    }
+  }
+
+  HufEncodeEnd();
+  FreeMemory();
+  return EFI_SUCCESS;
+}
+
+STATIC
+VOID
+CountTFreq ()
+/*++
+
+Routine Description:
+
+  Count the frequencies for the Extra Set
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  INT32 i, k, n, Count;
+
+  for (i = 0; i < NT; i++) {
+    mTFreq[i] = 0;
+  }
+  n = NC;
+  while (n > 0 && mCLen[n - 1] == 0) {
+    n--;
+  }
+  i = 0;
+  while (i < n) {
+    k = mCLen[i++];
+    if (k == 0) {
+      Count = 1;
+      while (i < n && mCLen[i] == 0) {
+        i++;
+        Count++;
+      }
+      if (Count <= 2) {
+        mTFreq[0] = (UINT16)(mTFreq[0] + Count);
+      } else if (Count <= 18) {
+        mTFreq[1]++;
+      } else if (Count == 19) {
+        mTFreq[0]++;
+        mTFreq[1]++;
+      } else {
+        mTFreq[2]++;
+      }
+    } else {
+      mTFreq[k + 2]++;
+    }
+  }
+}
+
+STATIC
+VOID
+WritePTLen (
+  IN INT32 n,
+  IN INT32 nbit,
+  IN INT32 Special
+  )
+/*++
+
+Routine Description:
+
+  Outputs the code length array for the Extra Set or the Position Set.
+
+Arguments:
+
+  n       - the number of symbols
+  nbit    - the number of bits needed to represent 'n'
+  Special - the special symbol that needs to be take care of
+
+Returns: (VOID)
+
+--*/
+{
+  INT32 i, k;
+
+  while (n > 0 && mPTLen[n - 1] == 0) {
+    n--;
+  }
+  PutBits(nbit, n);
+  i = 0;
+  while (i < n) {
+    k = mPTLen[i++];
+    if (k <= 6) {
+      PutBits(3, k);
+    } else {
+      PutBits(k - 3, (1U << (k - 3)) - 2);
+    }
+    if (i == Special) {
+      while (i < 6 && mPTLen[i] == 0) {
+        i++;
+      }
+      PutBits(2, (i - 3) & 3);
+    }
+  }
+}
+
+STATIC
+VOID
+WriteCLen ()
+/*++
+
+Routine Description:
+
+  Outputs the code length array for Char&Length Set
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  INT32 i, k, n, Count;
+
+  n = NC;
+  while (n > 0 && mCLen[n - 1] == 0) {
+    n--;
+  }
+  PutBits(CBIT, n);
+  i = 0;
+  while (i < n) {
+    k = mCLen[i++];
+    if (k == 0) {
+      Count = 1;
+      while (i < n && mCLen[i] == 0) {
+        i++;
+        Count++;
+      }
+      if (Count <= 2) {
+        for (k = 0; k < Count; k++) {
+          PutBits(mPTLen[0], mPTCode[0]);
+        }
+      } else if (Count <= 18) {
+        PutBits(mPTLen[1], mPTCode[1]);
+        PutBits(4, Count - 3);
+      } else if (Count == 19) {
+        PutBits(mPTLen[0], mPTCode[0]);
+        PutBits(mPTLen[1], mPTCode[1]);
+        PutBits(4, 15);
+      } else {
+        PutBits(mPTLen[2], mPTCode[2]);
+        PutBits(CBIT, Count - 20);
+      }
+    } else {
+      PutBits(mPTLen[k + 2], mPTCode[k + 2]);
+    }
+  }
+}
+
+STATIC
+VOID
+EncodeC (
+  IN INT32 c
+  )
+{
+  PutBits(mCLen[c], mCCode[c]);
+}
+
+STATIC
+VOID
+EncodeP (
+  IN UINT32 p
+  )
+{
+  UINT32 c, q;
+
+  c = 0;
+  q = p;
+  while (q) {
+    q >>= 1;
+    c++;
+  }
+  PutBits(mPTLen[c], mPTCode[c]);
+  if (c > 1) {
+    PutBits(c - 1, p & (0xFFFFU >> (17 - c)));
+  }
+}
+
+STATIC
+VOID
+SendBlock ()
+/*++
+
+Routine Description:
+
+  Huffman code the block and output it.
+
+Argument: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  UINT32 i, k, Flags, Root, Pos, Size;
+  Flags = 0;
+
+  Root = MakeTree(NC, mCFreq, mCLen, mCCode);
+  Size = mCFreq[Root];
+  PutBits(16, Size);
+  if (Root >= NC) {
+    CountTFreq();
+    Root = MakeTree(NT, mTFreq, mPTLen, mPTCode);
+    if (Root >= NT) {
+      WritePTLen(NT, TBIT, 3);
+    } else {
+      PutBits(TBIT, 0);
+      PutBits(TBIT, Root);
+    }
+    WriteCLen();
+  } else {
+    PutBits(TBIT, 0);
+    PutBits(TBIT, 0);
+    PutBits(CBIT, 0);
+    PutBits(CBIT, Root);
+  }
+  Root = MakeTree(NP, mPFreq, mPTLen, mPTCode);
+  if (Root >= NP) {
+    WritePTLen(NP, PBIT, -1);
+  } else {
+    PutBits(PBIT, 0);
+    PutBits(PBIT, Root);
+  }
+  Pos = 0;
+  for (i = 0; i < Size; i++) {
+    if (i % UINT8_BIT == 0) {
+      Flags = mBuf[Pos++];
+    } else {
+      Flags <<= 1;
+    }
+    if (Flags & (1U << (UINT8_BIT - 1))) {
+      EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
+      k = mBuf[Pos++] << UINT8_BIT;
+      k += mBuf[Pos++];
+      EncodeP(k);
+    } else {
+      EncodeC(mBuf[Pos++]);
+    }
+  }
+  for (i = 0; i < NC; i++) {
+    mCFreq[i] = 0;
+  }
+  for (i = 0; i < NP; i++) {
+    mPFreq[i] = 0;
+  }
+}
+
+
+STATIC
+VOID
+Output (
+  IN UINT32 c,
+  IN UINT32 p
+  )
+/*++
+
+Routine Description:
+
+  Outputs an Original Character or a Pointer
+
+Arguments:
+
+  c     - The original character or the 'String Length' element of a Pointer
+  p     - The 'Position' field of a Pointer
+
+Returns: (VOID)
+
+--*/
+{
+  STATIC UINT32 CPos;
+
+  if ((mOutputMask >>= 1) == 0) {
+    mOutputMask = 1U << (UINT8_BIT - 1);
+    if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
+      SendBlock();
+      mOutputPos = 0;
+    }
+    CPos = mOutputPos++;
+    mBuf[CPos] = 0;
+  }
+  mBuf[mOutputPos++] = (UINT8) c;
+  mCFreq[c]++;
+  if (c >= (1U << UINT8_BIT)) {
+    mBuf[CPos] |= mOutputMask;
+    mBuf[mOutputPos++] = (UINT8)(p >> UINT8_BIT);
+    mBuf[mOutputPos++] = (UINT8) p;
+    c = 0;
+    while (p) {
+      p >>= 1;
+      c++;
+    }
+    mPFreq[c]++;
+  }
+}
+
+STATIC
+VOID
+HufEncodeStart ()
+{
+  INT32 i;
+
+  for (i = 0; i < NC; i++) {
+    mCFreq[i] = 0;
+  }
+  for (i = 0; i < NP; i++) {
+    mPFreq[i] = 0;
+  }
+  mOutputPos = mOutputMask = 0;
+  InitPutBits();
+  return;
+}
+
+STATIC
+VOID
+HufEncodeEnd ()
+{
+  SendBlock();
+
+  //
+  // Flush remaining bits
+  //
+  PutBits(UINT8_BIT - 1, 0);
+
+  return;
+}
+
+
+STATIC
+VOID
+MakeCrcTable ()
+{
+  UINT32 i, j, r;
+
+  for (i = 0; i <= UINT8_MAX; i++) {
+    r = i;
+    for (j = 0; j < UINT8_BIT; j++) {
+      if (r & 1) {
+        r = (r >> 1) ^ CRCPOLY;
+      } else {
+        r >>= 1;
+      }
+    }
+    mCrcTable[i] = (UINT16)r;
+  }
+}
+
+STATIC
+VOID
+PutBits (
+  IN INT32 n,
+  IN UINT32 x
+  )
+/*++
+
+Routine Description:
+
+  Outputs rightmost n bits of x
+
+Arguments:
+
+  n   - the rightmost n bits of the data is used
+  x   - the data
+
+Returns: (VOID)
+
+--*/
+{
+  UINT8 Temp;
+
+  if (n < mBitCount) {
+    mSubBitBuf |= x << (mBitCount -= n);
+  } else {
+
+    Temp = (UINT8)(mSubBitBuf | (x >> (n -= mBitCount)));
+    if (mDst < mDstUpperLimit) {
+      *mDst++ = Temp;
+    }
+    mCompSize++;
+
+    if (n < UINT8_BIT) {
+      mSubBitBuf = x << (mBitCount = UINT8_BIT - n);
+    } else {
+
+      Temp = (UINT8)(x >> (n - UINT8_BIT));
+      if (mDst < mDstUpperLimit) {
+        *mDst++ = Temp;
+      }
+      mCompSize++;
+
+      mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - n);
+    }
+  }
+}
+
+STATIC
+INT32
+FreadCrc (
+  OUT UINT8 *p,
+  IN  INT32 n
+  )
+/*++
+
+Routine Description:
+
+  Read in source data
+
+Arguments:
+
+  p   - the buffer to hold the data
+  n   - number of bytes to read
+
+Returns:
+
+  number of bytes actually read
+
+--*/
+{
+  INT32 i;
+
+  for (i = 0; mSrc < mSrcUpperLimit && i < n; i++) {
+    *p++ = *mSrc++;
+  }
+  n = i;
+
+  p -= n;
+  mOrigSize += n;
+  while (--i >= 0) {
+    UPDATE_CRC(*p++);
+  }
+  return n;
+}
+
+
+STATIC
+VOID
+InitPutBits ()
+{
+  mBitCount = UINT8_BIT;
+  mSubBitBuf = 0;
+}
+
+STATIC
+VOID
+CountLen (
+  IN INT32 i
+  )
+/*++
+
+Routine Description:
+
+  Count the number of each code length for a Huffman tree.
+
+Arguments:
+
+  i   - the top node
+
+Returns: (VOID)
+
+--*/
+{
+  STATIC INT32 Depth = 0;
+
+  if (i < mN) {
+    mLenCnt[(Depth < 16) ? Depth : 16]++;
+  } else {
+    Depth++;
+    CountLen(mLeft [i]);
+    CountLen(mRight[i]);
+    Depth--;
+  }
+}
+
+STATIC
+VOID
+MakeLen (
+  IN INT32 Root
+  )
+/*++
+
+Routine Description:
+
+  Create code length array for a Huffman tree
+
+Arguments:
+
+  Root   - the root of the tree
+
+--*/
+{
+  INT32 i, k;
+  UINT32 Cum;
+
+  for (i = 0; i <= 16; i++) {
+    mLenCnt[i] = 0;
+  }
+  CountLen(Root);
+
+  //
+  // Adjust the length count array so that
+  // no code will be generated longer than its designated length
+  //
+
+  Cum = 0;
+  for (i = 16; i > 0; i--) {
+    Cum += mLenCnt[i] << (16 - i);
+  }
+  while (Cum != (1U << 16)) {
+    mLenCnt[16]--;
+    for (i = 15; i > 0; i--) {
+      if (mLenCnt[i] != 0) {
+        mLenCnt[i]--;
+        mLenCnt[i+1] += 2;
+        break;
+      }
+    }
+    Cum--;
+  }
+  for (i = 16; i > 0; i--) {
+    k = mLenCnt[i];
+    while (--k >= 0) {
+      mLen[*mSortPtr++] = (UINT8)i;
+    }
+  }
+}
+
+STATIC
+VOID
+DownHeap (
+  IN INT32 i
+  )
+{
+  INT32 j, k;
+
+  //
+  // priority queue: send i-th entry down heap
+  //
+
+  k = mHeap[i];
+  while ((j = 2 * i) <= mHeapSize) {
+    if (j < mHeapSize && mFreq[mHeap[j]] > mFreq[mHeap[j + 1]]) {
+      j++;
+    }
+    if (mFreq[k] <= mFreq[mHeap[j]]) {
+      break;
+    }
+    mHeap[i] = mHeap[j];
+    i = j;
+  }
+  mHeap[i] = (INT16)k;
+}
+
+STATIC
+VOID
+MakeCode (
+  IN  INT32 n,
+  IN  UINT8 Len[],
+  OUT UINT16 Code[]
+  )
+/*++
+
+Routine Description:
+
+  Assign code to each symbol based on the code length array
+
+Arguments:
+
+  n     - number of symbols
+  Len   - the code length array
+  Code  - stores codes for each symbol
+
+Returns: (VOID)
+
+--*/
+{
+  INT32    i;
+  UINT16   Start[18];
+
+  Start[1] = 0;
+  for (i = 1; i <= 16; i++) {
+    Start[i + 1] = (UINT16)((Start[i] + mLenCnt[i]) << 1);
+  }
+  for (i = 0; i < n; i++) {
+    Code[i] = Start[Len[i]]++;
+  }
+}
+
+STATIC
+INT32
+MakeTree (
+  IN  INT32   NParm,
+  IN  UINT16  FreqParm[],
+  OUT UINT8   LenParm[],
+  OUT UINT16  CodeParm[]
+  )
+/*++
+
+Routine Description:
+
+  Generates Huffman codes given a frequency distribution of symbols
+
+Arguments:
+
+  NParm    - number of symbols
+  FreqParm - frequency of each symbol
+  LenParm  - code length for each symbol
+  CodeParm - code for each symbol
+
+Returns:
+
+  Root of the Huffman tree.
+
+--*/
+{
+  INT32 i, j, k, Avail;
+
+  //
+  // make tree, calculate len[], return root
+  //
+
+  mN = NParm;
+  mFreq = FreqParm;
+  mLen = LenParm;
+  Avail = mN;
+  mHeapSize = 0;
+  mHeap[1] = 0;
+  for (i = 0; i < mN; i++) {
+    mLen[i] = 0;
+    if (mFreq[i]) {
+      mHeap[++mHeapSize] = (INT16)i;
+    }
+  }
+  if (mHeapSize < 2) {
+    CodeParm[mHeap[1]] = 0;
+    return mHeap[1];
+  }
+  for (i = mHeapSize / 2; i >= 1; i--) {
+
+    //
+    // make priority queue
+    //
+    DownHeap(i);
+  }
+  mSortPtr = CodeParm;
+  do {
+    i = mHeap[1];
+    if (i < mN) {
+      *mSortPtr++ = (UINT16)i;
+    }
+    mHeap[1] = mHeap[mHeapSize--];
+    DownHeap(1);
+    j = mHeap[1];
+    if (j < mN) {
+      *mSortPtr++ = (UINT16)j;
+    }
+    k = Avail++;
+    mFreq[k] = (UINT16)(mFreq[i] + mFreq[j]);
+    mHeap[1] = (INT16)k;
+    DownHeap(1);
+    mLeft[k] = (UINT16)i;
+    mRight[k] = (UINT16)j;
+  } while (mHeapSize > 1);
+
+  mSortPtr = CodeParm;
+  MakeLen(k);
+  MakeCode(NParm, LenParm, CodeParm);
+
+  //
+  // return root
+  //
+  return k;
+}
+
diff --git a/src/util/efirom.c b/src/util/efirom.c
index 8fa15ca..95feaf2 100644
--- a/src/util/efirom.c
+++ b/src/util/efirom.c
@@ -34,10 +34,17 @@
 
 #define eprintf(...) fprintf ( stderr, __VA_ARGS__ )
 
+/* Round up ROM size */
+#define ROM_SIZE( len ) ( ( (len) + 511 ) & ~511 )
+
+/* Include the EDK2 compression code */
+#include "eficompress.c"
+
 /** Command-line options */
 struct options {
 	uint16_t vendor;
 	uint16_t device;
+	int compress;
 };
 
 /**
@@ -95,6 +102,35 @@ static void read_pe_info ( void *pe, uint16_t *machine,
 }
 
 /**
+ * Attempt to compress EFI data in-place
+ *
+ * @v data		Data to be compressed
+ * @v max_len		Length of data
+ * @ret len		Length after attempted compression
+ */
+static size_t efi_compress ( void *data, size_t max_len ) {
+	void *tmp;
+	UINT32 len;
+
+	/* Allocate temporary buffer for compressed data */
+	tmp = xmalloc ( max_len );
+
+	/* Attempt compression */
+	len = max_len;
+	if ( ( EfiCompress ( data, max_len, tmp, &len ) == 0 ) &&
+	     ( len < max_len ) ) {
+		memcpy ( data, tmp, len );
+	} else {
+		len = max_len;
+	}
+
+	/* Free temporary buffer */
+	free ( tmp );
+
+	return len;
+}
+
+/**
  * Convert EFI image to ROM image
  *
  * @v pe		EFI file
@@ -109,10 +145,14 @@ static void make_efi_rom ( FILE *pe, FILE *rom, struct options *opts ) {
 	struct stat pe_stat;
 	size_t pe_size;
 	size_t rom_size;
+	size_t compressed_size;
 	void *buf;
 	void *payload;
 	unsigned int i;
+	uint16_t machine;
+	uint16_t subsystem;
 	uint8_t checksum;
+	int compressed;
 
 	/* Determine PE file size */
 	if ( fstat ( fileno ( pe ), &pe_stat ) != 0 ) {
@@ -123,7 +163,7 @@ static void make_efi_rom ( FILE *pe, FILE *rom, struct options *opts ) {
 	pe_size = pe_stat.st_size;
 
 	/* Determine ROM file size */
-	rom_size = ( ( pe_size + sizeof ( *headers ) + 511 ) & ~511 );
+	rom_size = ROM_SIZE ( sizeof ( *headers ) + pe_size );
 
 	/* Allocate ROM buffer and read in PE file */
 	buf = xmalloc ( rom_size );
@@ -136,12 +176,26 @@ static void make_efi_rom ( FILE *pe, FILE *rom, struct options *opts ) {
 		exit ( 1 );
 	}
 
+	/* Parse PE headers */
+	read_pe_info ( payload, &machine, &subsystem );
+
+	/* Compress the image, if requested */
+	if ( opts->compress ) {
+		compressed_size = efi_compress ( payload, pe_size );
+		rom_size = ROM_SIZE ( sizeof ( *headers ) + compressed_size );
+		compressed = ( compressed_size < pe_size );
+	} else {
+		compressed = 0;
+	}
+
 	/* Construct ROM header */
 	headers->rom.Signature = PCI_EXPANSION_ROM_HEADER_SIGNATURE;
 	headers->rom.InitializationSize = ( rom_size / 512 );
 	headers->rom.EfiSignature = EFI_PCI_EXPANSION_ROM_HEADER_EFISIGNATURE;
-	read_pe_info ( payload, &headers->rom.EfiMachineType,
-		       &headers->rom.EfiSubsystem );
+	headers->rom.EfiSubsystem = subsystem;
+	headers->rom.EfiMachineType = machine;
+	headers->rom.CompressionType =
+		( compressed ? EFI_PCI_EXPANSION_ROM_HEADER_COMPRESSED : 0 );
 	headers->rom.EfiImageHeaderOffset = sizeof ( *headers );
 	headers->rom.PcirOffset =
 		offsetof ( typeof ( *headers ), pci );
@@ -194,11 +248,12 @@ static int parse_options ( const int argc, char **argv,
 		static struct option long_options[] = {
 			{ "vendor", required_argument, NULL, 'v' },
 			{ "device", required_argument, NULL, 'd' },
+			{ "compress", 0, NULL, 'c' },
 			{ "help", 0, NULL, 'h' },
 			{ 0, 0, 0, 0 }
 		};
 
-		if ( ( c = getopt_long ( argc, argv, "v:d:h",
+		if ( ( c = getopt_long ( argc, argv, "v:d:ch",
 					 long_options,
 					 &option_index ) ) == -1 ) {
 			break;
@@ -219,6 +274,9 @@ static int parse_options ( const int argc, char **argv,
 				exit ( 2 );
 			}
 			break;
+		case 'c':
+			opts->compress = 1;
+			break;
 		case 'h':
 			print_help ( argv[0] );
 			exit ( 0 );