Enable EFIv1 compression in bmpbklk_utility.

This lets bmpbklk_utility generate BMPBLOCKs with EFIv1-compressed bitmaps.
It also adds the ability to display or unpack BMPBLOCK blobs.

The compression/decompression routines come from the tianocore EDK on
sourceforge and are written in C, so now there's a mix of C and C++, but it
works just fine.

BUG=chromium-os:11491
TEST=manual

cd src/platform/vboot_reference
make
make runbmptests

Review URL: http://codereview.chromium.org/6508006

Change-Id: Ie05e1a3fd42f4694447c8c440b2432af4ac0f601

12 files changed, 3121 insertions, 44 deletions

diff --git a/tests/bitmaps/Background.bmp b/tests/bitmaps/Background.bmp
new file mode 100644
index 00000000..a83c995c
--- /dev/null
+++ b/tests/bitmaps/Background.bmp
diff --git a/tests/bitmaps/TestBmpBlock.py b/tests/bitmaps/TestBmpBlock.py
index 77ef4199..ced270ee 100755
--- a/tests/bitmaps/TestBmpBlock.py
+++ b/tests/bitmaps/TestBmpBlock.py
@@ -19,7 +19,7 @@ def runprog(*args):
   return (p.returncode, out, err)
 
 
-class TestBmpBlock(unittest.TestCase):
+class TestFailures(unittest.TestCase):
 
   def testNoArgs(self):
     """Running with no args should print usage and fail."""
@@ -40,6 +40,72 @@ class TestBmpBlock(unittest.TestCase):
     self.assertNotEqual(0, rc)
     self.assertTrue(err.count("Unsupported image format"))
 
+  def testBadCompression(self):
+    """Wrong compression types should fail."""
+    rc, out, err = runprog(prog, '-z', '99', '-c', 'case_simple.yaml', 'FOO')
+    self.assertNotEqual(0, rc)
+    self.assertTrue(err.count("compression type"))
+
+
+class TestOverWrite(unittest.TestCase):
+
+  def setUp(self):
+    rc, out, err = runprog('/bin/rm', '-rf', './FOO_DIR', 'FOO')
+    self.assertEqual(0, rc)
+
+  def testOverwrite(self):
+    """Create, unpack, unpack again, with and without -f"""
+    rc, out, err = runprog(prog, '-c', 'case_simple.yaml', 'FOO')
+    self.assertEqual(0, rc)
+    rc, out, err = runprog(prog, '-x', '-d', './FOO_DIR', 'FOO')
+    self.assertEqual(0, rc)
+    rc, out, err = runprog(prog, '-x', '-d', './FOO_DIR', 'FOO')
+    self.assertNotEqual(0, rc)
+    self.assertTrue(err.count("File exists"))
+    rc, out, err = runprog(prog, '-x', '-d', './FOO_DIR', '-f', 'FOO')
+    self.assertEqual(0, rc)
+
+  def tearDown(self):
+    rc, out, err = runprog('/bin/rm', '-rf', './FOO_DIR', 'FOO')
+    self.assertEqual(0, rc)
+
+
+class TestPackUnpack(unittest.TestCase):
+
+  def setUp(self):
+    rc, out, err = runprog('/bin/rm', '-rf', './FOO_DIR', 'FOO')
+    self.assertEqual(0, rc)
+
+  def testPackUnpack(self):
+    """Create, unpack, recreate without compression"""
+    rc, out, err = runprog(prog, '-c', 'case_simple.yaml', 'FOO')
+    self.assertEqual(0, rc)
+    rc, out, err = runprog(prog, '-x', '-d', './FOO_DIR', 'FOO')
+    self.assertEqual(0, rc)
+    os.chdir('./FOO_DIR')
+    rc, out, err = runprog(prog, '-c', 'config.yaml', 'BAR')
+    self.assertEqual(0, rc)
+    rc, out, err = runprog('/usr/bin/cmp', '../FOO', 'BAR')
+    self.assertEqual(0, rc)
+    os.chdir('..')
+
+  def testPackUnpackZ(self):
+    """Create, unpack, recreate with explicit compression"""
+    rc, out, err = runprog(prog, '-z', '1', '-c', 'case_simple.yaml', 'FOO')
+    self.assertEqual(0, rc)
+    rc, out, err = runprog(prog, '-x', '-d', './FOO_DIR', 'FOO')
+    self.assertEqual(0, rc)
+    os.chdir('./FOO_DIR')
+    rc, out, err = runprog(prog, '-z', '1', '-c', 'config.yaml', 'BAR')
+    self.assertEqual(0, rc)
+    rc, out, err = runprog('/usr/bin/cmp', '../FOO', 'BAR')
+    self.assertEqual(0, rc)
+    os.chdir('..')
+
+  def tearDown(self):
+    rc, out, err = runprog('/bin/rm', '-rf', './FOO_DIR', 'FOO')
+    self.assertEqual(0, rc)
+
 
 # Run these tests
 if __name__ == '__main__':
diff --git a/tests/bitmaps/Word.bmp b/tests/bitmaps/Word.bmp
new file mode 100644
index 00000000..ba4a0e0c
--- /dev/null
+++ b/tests/bitmaps/Word.bmp
diff --git a/tests/bitmaps/case_simple.yaml b/tests/bitmaps/case_simple.yaml
new file mode 100644
index 00000000..5c8590db
--- /dev/null
+++ b/tests/bitmaps/case_simple.yaml
@@ -0,0 +1,27 @@
+
+bmpblock: 1.0
+
+images:
+  background:     Background.bmp
+  text:           Word.bmp
+
+screens:
+  scr_1:
+    - [0, 0, background]
+    - [45, 45, text ]
+
+  scr_2:
+    - [0, 0, background]
+    - [45, 400, text ]
+
+  scr_3:
+    - [0, 0, background]
+    - [400, 400, text ]
+
+  scr_4:
+    - [0, 0, background]
+    - [400, 45, text ]
+
+
+localizations:
+  - [ scr_1, scr_2, scr_3, scr_4 ]
diff --git a/utility/Makefile b/utility/Makefile
index a424941d..af0187b3 100644
--- a/utility/Makefile
+++ b/utility/Makefile
@@ -65,8 +65,16 @@ ${BUILD_ROOT}/bmpblk_utility.o: bmpblk_utility.cc
 ${BUILD_ROOT}/bmpblk_util.o: bmpblk_util.c
 	$(CC) $(CFLAGS) -c $< -o $@
 
+${BUILD_ROOT}/eficompress.o: eficompress.c
+	$(CC) $(CFLAGS) -c $< -o $@
+
+${BUILD_ROOT}/efidecompress.o: efidecompress.c
+	$(CC) $(CFLAGS) -c $< -o $@
+
 ${BUILD_ROOT}/bmpblk_utility: ${BUILD_ROOT}/bmpblk_utility.o \
-			      ${BUILD_ROOT}/bmpblk_util.o
+				${BUILD_ROOT}/bmpblk_util.o \
+				${BUILD_ROOT}/eficompress.o \
+				${BUILD_ROOT}/efidecompress.o
 	$(CXX) -DWITH_UTIL_MAIN -lyaml $(CFLAGS) $^ -o $@
 
 ${BUILD_ROOT}/load_kernel_test: load_kernel_test.c $(LIBS)
diff --git a/utility/bmpblk_util.c b/utility/bmpblk_util.c
index d7b9cbf8..214beda4 100644
--- a/utility/bmpblk_util.c
+++ b/utility/bmpblk_util.c
@@ -4,6 +4,7 @@
 
 #include <errno.h>
 #include <fcntl.h>
+#include <limits.h>
 #include <stdio.h>
 #include <string.h>
 #include <sys/mman.h>
@@ -12,6 +13,7 @@
 #include <unistd.h>
 
 #include "bmpblk_util.h"
+#include "eficompress.h"
 
 
 // Returns pointer to buffer containing entire file, sets length.
@@ -58,14 +60,105 @@ static void discard_file(void *ptr, size_t length) {
   munmap(ptr, length);
 }
 
+//////////////////////////////////////////////////////////////////////////////
 
-// Show what's inside
-int display_bmpblock(const char *infile) {
-  char *ptr;
+static int require_dir(const char *dirname) {
+  struct stat sbuf;
+
+  if (0 == stat(dirname, &sbuf)) {
+    // Something's there. Is it a directory?
+    if (S_ISDIR(sbuf.st_mode)) {
+      return 0;
+    }
+    fprintf(stderr, "%s already exists and is not a directory\n", dirname);
+    return 1;
+  }
+
+  // dirname doesn't exist. Try to create it.
+  if (ENOENT == errno) {
+    if (0 != mkdir(dirname, 0777)) {
+      fprintf(stderr, "Unable to create directory %s: %s\n",
+              dirname, strerror(errno));
+      return 1;
+    }
+    return 0;
+  }
+
+  fprintf(stderr, "Unable to stat %s: %s\n", dirname, strerror(errno));
+  return 1;
+}
+
+
+
+static void *do_efi_decompress(ImageInfo *img) {
+  void *ibuf;
+  void *sbuf;
+  void *obuf;
+  uint32_t isize;
+  uint32_t ssize;
+  uint32_t osize;
+  EFI_STATUS r;
+
+  ibuf = ((void *)img) + sizeof(ImageInfo);
+  isize = img->compressed_size;
+
+  r = EfiGetInfo(ibuf, isize, &osize, &ssize);
+  if (EFI_SUCCESS != r) {
+    fprintf(stderr, "EfiGetInfo() failed with code %d\n",
+            r);
+    return 0;
+  }
+
+  sbuf = malloc(ssize);
+  if (!sbuf) {
+    fprintf(stderr, "Can't allocate %d bytes: %s\n",
+            ssize,
+            strerror(errno));
+    return 0;
+  }
+
+  obuf = malloc(osize);
+  if (!obuf) {
+    fprintf(stderr, "Can't allocate %d bytes: %s\n",
+            osize,
+            strerror(errno));
+    free(sbuf);
+    return 0;
+  }
+
+  r = EfiDecompress(ibuf, isize, obuf, osize, sbuf, ssize);
+  if (r != EFI_SUCCESS) {
+    fprintf(stderr, "EfiDecompress failed with code %d\n", r);
+    free(obuf);
+    free(sbuf);
+    return 0;
+  }
+
+  free(sbuf);
+  return obuf;
+}
+
+
+// Show what's inside. If todir is NULL, just print. Otherwise unpack.
+int dump_bmpblock(const char *infile, int show_as_yaml,
+                  const char *todir, int overwrite) {
+  void *ptr, *data_ptr;
   size_t length = 0;
   BmpBlockHeader *hdr;
+  ImageInfo *img;
+  ScreenLayout *scr;
+  int loc_num;
+  int screen_num;
+  int i;
+  int offset;
+  int free_data;
+  char image_name[80];
+  char full_path_name[PATH_MAX];
+  int yfd, bfd;
+  FILE *yfp = stdout;
+  FILE *bfp = stdout;
 
-  ptr = (char *)read_entire_file(infile, &length);
+  ptr = (void *)read_entire_file(infile, &length);
   if (!ptr)
     return 1;
 
@@ -81,21 +174,163 @@ int display_bmpblock(const char *infile) {
     return 1;
   }
 
+  if (todir) {
+    // Unpacking everything. Create the output directory if needed.
+    if (0 != require_dir(todir)) {
+      discard_file(ptr, length);
+      return 1;
+    }
+
+    // Open yaml output.
+    show_as_yaml = 1;
+
+    sprintf(full_path_name, "%s/%s", todir, "config.yaml");
+    yfd = open(full_path_name,
+               O_WRONLY | O_CREAT | O_TRUNC | (overwrite ? 0 : O_EXCL),
+               0666);
+    if (yfd < 0) {
+      fprintf(stderr, "Unable to open %s: %s\n", full_path_name,
+              strerror(errno));
+      discard_file(ptr, length);
+      return 1;
+    }
+
+    yfp = fdopen(yfd, "wb");
+    if (!yfp) {
+      fprintf(stderr, "Unable to fdopen %s: %s\n", full_path_name,
+              strerror(errno));
+      close(yfd);
+      discard_file(ptr, length);
+      return 1;
+    }
+  }
+
   hdr = (BmpBlockHeader *)ptr;
-  printf("%s:\n", infile);
-  printf("  version %d.%d\n", hdr->major_version, hdr->minor_version);
-  printf("  %d screens\n", hdr->number_of_screenlayouts);
-  printf("  %d localizations\n", hdr->number_of_localizations);
-  printf("  %d discrete images\n", hdr->number_of_imageinfos);
+
+  if (!show_as_yaml) {
+    printf("%s:\n", infile);
+    printf("  version %d.%d\n", hdr->major_version, hdr->minor_version);
+    printf("  %d screens\n", hdr->number_of_screenlayouts);
+    printf("  %d localizations\n", hdr->number_of_localizations);
+    printf("  %d discrete images\n", hdr->number_of_imageinfos);
+    discard_file(ptr, length);
+    return 0;
+  }
+
+  // Write out yaml
+  fprintf(yfp, "bmpblock: %d.%d\n", hdr->major_version, hdr->minor_version);
+  fprintf(yfp, "images:\n");
+  offset = sizeof(BmpBlockHeader) +
+    (sizeof(ScreenLayout) *
+     hdr->number_of_localizations *
+     hdr->number_of_screenlayouts);
+  for(i=0; i<hdr->number_of_imageinfos; i++) {
+    img = (ImageInfo *)(ptr + offset);
+    sprintf(image_name, "img_%08x.bmp", offset);
+    fprintf(yfp, "  img_%08x: %s  # %dx%d  %d/%d\n", offset, image_name,
+            img->width, img->height,
+            img->compressed_size, img->original_size);
+    if (todir) {
+      sprintf(full_path_name, "%s/%s", todir, image_name);
+      bfd = open(full_path_name,
+                 O_WRONLY | O_CREAT | O_TRUNC | (overwrite ? 0 : O_EXCL),
+                 0666);
+      if (bfd < 0) {
+        fprintf(stderr, "Unable to open %s: %s\n", full_path_name,
+                strerror(errno));
+        fclose(yfp);
+        discard_file(ptr, length);
+        return 1;
+      }
+      bfp = fdopen(bfd, "wb");
+      if (!bfp) {
+        fprintf(stderr, "Unable to fdopen %s: %s\n", full_path_name,
+                strerror(errno));
+        close(bfd);
+        fclose(yfp);
+        discard_file(ptr, length);
+        return 1;
+      }
+      switch(img->compression) {
+      case COMPRESS_NONE:
+        data_ptr = ptr + offset + sizeof(ImageInfo);
+        free_data = 0;
+        break;
+      case COMPRESS_EFIv1:
+        data_ptr = do_efi_decompress(img);
+        if (!data_ptr) {
+          fclose(bfp);
+          fclose(yfp);
+          discard_file(ptr, length);
+          return 1;
+        }
+        free_data = 1;
+        break;
+      default:
+        fprintf(stderr, "Unsupported compression method encountered.\n");
+        fclose(bfp);
+        fclose(yfp);
+        discard_file(ptr, length);
+        return 1;
+      }
+      if (1 != fwrite(data_ptr, img->original_size, 1, bfp)) {
+        fprintf(stderr, "Unable to write %s: %s\n", full_path_name,
+                strerror(errno));
+        fclose(bfp);
+        fclose(yfp);
+        discard_file(ptr, length);
+        return 1;
+      }
+      fclose(bfp);
+      if (free_data)
+        free(data_ptr);
+    }
+    offset += sizeof(ImageInfo);
+    offset += img->compressed_size;
+    // 4-byte aligned
+    if ((offset & 3) > 0)
+      offset = (offset & ~3) + 4;
+  }
+  fprintf(yfp, "screens:\n");
+  for(loc_num = 0;
+      loc_num < hdr->number_of_localizations;
+      loc_num++) {
+    for(screen_num = 0;
+        screen_num < hdr->number_of_screenlayouts;
+        screen_num++) {
+      fprintf(yfp, "  scr_%d_%d:\n", loc_num, screen_num);
+      i = loc_num * hdr->number_of_screenlayouts + screen_num;
+      offset = sizeof(BmpBlockHeader) + i * sizeof(ScreenLayout);
+      scr = (ScreenLayout *)(ptr + offset);
+      for(i=0; i<MAX_IMAGE_IN_LAYOUT; i++) {
+        if (scr->images[i].image_info_offset) {
+          fprintf(yfp, "    - [%d, %d, img_%08x]\n",
+                  scr->images[i].x, scr->images[i].y,
+                  scr->images[i].image_info_offset);
+        }
+      }
+    }
+  }
+  fprintf(yfp, "localizations:\n");
+  for(loc_num = 0;
+      loc_num < hdr->number_of_localizations;
+      loc_num++) {
+    fprintf(yfp, "  - [");
+    for(screen_num = 0;
+        screen_num < hdr->number_of_screenlayouts;
+        screen_num++) {
+      fprintf(yfp, " scr_%d_%d", loc_num, screen_num);
+      if (screen_num != hdr->number_of_screenlayouts - 1)
+        fprintf(yfp, ",");
+    }
+    fprintf(yfp, " ]\n");
+  }
+
+  if (todir)
+    fclose(yfp);
 
   discard_file(ptr, length);
 
   return 0;
 }
 
-int extract_bmpblock(const char *infile, const char *dirname, int force) {
-    printf("extract parts from %s into %s %s overwriting\n",
-           infile, dirname, force ? "with" : "without");
-    printf("NOT YET IMPLEMENTED\n");
-    return 0;
-}
diff --git a/utility/bmpblk_utility.cc b/utility/bmpblk_utility.cc
index 66b60d9d..9f912d0b 100644
--- a/utility/bmpblk_utility.cc
+++ b/utility/bmpblk_utility.cc
@@ -16,6 +16,11 @@
 #include <string.h>
 #include <yaml.h>
 
+extern "C" {
+#include "eficompress.h"
+}
+
+
 /* BMP header, used to validate image requirements
  * See http://en.wikipedia.org/wiki/BMP_file_format
  */
@@ -67,6 +72,13 @@ void BmpBlockUtil::initialize() {
   config_.screens_map.clear();
   config_.localizations.clear();
   bmpblock_.clear();
+  set_compression_ = false;
+  compression_ = COMPRESS_NONE;
+}
+
+void BmpBlockUtil::force_compression(uint32_t compression) {
+  compression_ = compression;
+  set_compression_ = true;
 }
 
 void BmpBlockUtil::load_from_config(const char *filename) {
@@ -292,10 +304,31 @@ void BmpBlockUtil::load_all_image_files() {
     const string &content = read_image_file(it->second.filename.c_str());
     it->second.raw_content = content;
     it->second.data.original_size = content.size();
-    /* Use no compression as default */
-    it->second.data.compression = COMPRESS_NONE;
-    it->second.compressed_content = content;
-    it->second.data.compressed_size = content.size();
+    switch(compression_) {
+    case COMPRESS_NONE:
+      it->second.data.compression = compression_;
+      it->second.compressed_content = content;
+      it->second.data.compressed_size = content.size();
+      break;
+    case COMPRESS_EFIv1:
+      {
+        // The content will always compress smaller (so sez the docs).
+        uint32_t tmpsize = content.size();
+        uint8_t *tmpbuf = (uint8_t *)malloc(tmpsize);
+        // The size of the compressed content is also returned.
+        if (EFI_SUCCESS != EfiCompress((uint8_t *)content.c_str(), tmpsize,
+                                       tmpbuf, &tmpsize)) {
+          error("Unable to compress!\n");
+        }
+        it->second.data.compression = compression_;
+        it->second.compressed_content.assign((const char *)tmpbuf, tmpsize);
+        it->second.data.compressed_size = tmpsize;
+        free(tmpbuf);
+      }
+      break;
+    default:
+      error("Unsupported compression method attempted.\n");
+    }
   }
 }
 
@@ -409,7 +442,7 @@ void BmpBlockUtil::pack_bmpblock() {
 
   /* Compute the ImageInfo offsets from start of BMPBLOCK. */
   uint32_t current_offset = sizeof(BmpBlockHeader) +
-                            sizeof(ScreenLayout) * config_.images_map.size();
+                            sizeof(ScreenLayout) * config_.screens_map.size();
   for (StrImageConfigMap::iterator it = config_.images_map.begin();
        it != config_.images_map.end();
        ++it) {
@@ -507,7 +540,9 @@ static void usagehelp_exit(const char *prog_name) {
   printf(
     "To display the contents of a BMPBLOCK:\n"
     "\n"
-    "  %s BMPBLOCK\n"
+    "  %s [-y] BMPBLOCK\n"
+    "\n"
+    "    -y  = display as yaml\n"
     "\n", prog_name);
   printf(
     "To unpack a BMPBLOCK file:\n"
@@ -531,15 +566,17 @@ int main(int argc, char *argv[]) {
   else
     prog_name = argv[0];
 
-  int force = 0, extract_mode = 0;
+  int overwrite = 0, extract_mode = 0;
   int compression = 0;
+  int set_compression = 0;
   const char *config_fn = 0, *bmpblock_fn = 0, *extract_dir = ".";
+  int show_as_yaml = 0;
 
   int opt;
   opterr = 0;                           // quiet
   int errorcnt = 0;
   char *e = 0;
-  while ((opt = getopt(argc, argv, ":c:xz:fd:")) != -1) {
+  while ((opt = getopt(argc, argv, ":c:xz:fd:y")) != -1) {
     switch (opt) {
     case 'c':
       config_fn = optarg;
@@ -547,6 +584,9 @@ int main(int argc, char *argv[]) {
     case 'x':
       extract_mode = 1;
       break;
+    case 'y':
+      show_as_yaml = 1;
+      break;
     case 'z':
       compression = (int)strtoul(optarg, &e, 0);
       if (!*optarg || (e && *e)) {
@@ -556,12 +596,13 @@ int main(int argc, char *argv[]) {
       }
       if (compression >= MAX_COMPRESS) {
         fprintf(stderr, "%s: compression type must be less than %d\n",
-                prog_name, compression);
+                prog_name, MAX_COMPRESS);
         errorcnt++;
       }
+      set_compression = 1;
       break;
     case 'f':
-      force = 1;
+      overwrite = 1;
       break;
     case 'd':
       extract_dir= optarg;
@@ -594,27 +635,17 @@ int main(int argc, char *argv[]) {
   BmpBlockUtil util;
 
   if (config_fn) {
-    printf("compression is %d\n", compression);
+    if (set_compression)
+      util.force_compression(compression);
     util.load_from_config(config_fn);
     util.pack_bmpblock();
     util.write_to_bmpblock(bmpblock_fn);
-    printf("The BMPBLOCK is sucessfully created in: %s.\n",
-           bmpblock_fn);
   }
 
   else if (extract_mode) {
-    return extract_bmpblock(bmpblock_fn, extract_dir, force);
-    printf("extract parts from %s into %s %s overwriting\n",
-           bmpblock_fn, extract_dir, force ? "with" : "without");
-    /* TODO(waihong): Implement the list mode. */
-    error("Extract mode hasn't been implemented yet.\n");
-  }
-
-  else {
-    return display_bmpblock(bmpblock_fn);
-    printf("display content of %s\n", bmpblock_fn);
-    /* TODO(waihong): Implement the list mode. */
-    error("List mode hasn't been implemented yet.\n");
+    return dump_bmpblock(bmpblock_fn, 1, extract_dir, overwrite);
+  } else {
+    return dump_bmpblock(bmpblock_fn, show_as_yaml, 0, 0);
   }
 
   return 0;
diff --git a/utility/eficompress.c b/utility/eficompress.c
new file mode 100644
index 00000000..b0cf4fb3
--- /dev/null
+++ b/utility/eficompress.c
@@ -0,0 +1,1609 @@
+/* Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+/*++
+
+Copyright (c) 2006, Intel Corporation
+All rights reserved. This program and the accompanying materials
+are licensed and made available under the terms and conditions of the BSD License
+which accompanies this distribution.  The full text of the license may be found at
+http://opensource.org/licenses/bsd-license.php
+
+THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
+WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+
+Module Name:
+
+  EfiCompress.c
+
+Abstract:
+
+  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.
+
+--*/
+
+#include <errno.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include "eficompress.h"
+
+
+//
+// Macro Definitions
+//
+
+typedef INT16             NODE;
+#define UINT8_BIT         8
+#define THRESHOLD         3
+#define INIT_CRC          0
+#define WNDBIT            13
+#define WNDSIZ            (1U << 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
+
+Argements: (VOID)
+
+Returns:
+
+  EFI_SUCCESS           - Memory is allocated successfully
+  EFI_OUT_OF_RESOURCES  - Allocation fails
+
+--*/
+{
+  UINT32      i;
+
+  mText       = malloc (WNDSIZ * 2 + MAXMATCH);
+  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));
+
+  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. Travese 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
+
+Argments:
+
+  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/utility/efidecompress.c b/utility/efidecompress.c
new file mode 100644
index 00000000..8ec4a089
--- /dev/null
+++ b/utility/efidecompress.c
@@ -0,0 +1,1008 @@
+/* Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+/*++
+
+Copyright (c) 2004 - 2006, Intel Corporation
+All rights reserved. This program and the accompanying materials
+are licensed and made available under the terms and conditions of the BSD License
+which accompanies this distribution.  The full text of the license may be found at
+http://opensource.org/licenses/bsd-license.php
+
+THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
+WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+
+Module Name:
+
+  Decompress.c
+
+Abstract:
+
+  Decompressor. Algorithm Ported from OPSD code (Decomp.asm)
+
+--*/
+
+#include <errno.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include "eficompress.h"
+
+
+//
+// Decompression algorithm begins here
+//
+#define BITBUFSIZ 32
+#define MAXMATCH  256
+#define THRESHOLD 3
+#define CODE_BIT  16
+#define BAD_TABLE - 1
+
+//
+// C: Char&Len Set; P: Position Set; T: exTra Set
+//
+#define NC      (0xff + MAXMATCH + 2 - THRESHOLD)
+#define CBIT    9
+#define MAXPBIT 5
+#define TBIT    5
+#define MAXNP   ((1U << MAXPBIT) - 1)
+#define NT      (CODE_BIT + 3)
+#if NT > MAXNP
+#define NPT NT
+#else
+#define NPT MAXNP
+#endif
+
+typedef struct {
+  UINT8   *mSrcBase;  // Starting address of compressed data
+  UINT8   *mDstBase;  // Starting address of decompressed data
+  UINT32  mOutBuf;
+  UINT32  mInBuf;
+
+  UINT16  mBitCount;
+  UINT32  mBitBuf;
+  UINT32  mSubBitBuf;
+  UINT16  mBlockSize;
+  UINT32  mCompSize;
+  UINT32  mOrigSize;
+
+  UINT16  mBadTableFlag;
+
+  UINT16  mLeft[2 * NC - 1];
+  UINT16  mRight[2 * NC - 1];
+  UINT8   mCLen[NC];
+  UINT8   mPTLen[NPT];
+  UINT16  mCTable[4096];
+  UINT16  mPTTable[256];
+
+  //
+  // The length of the field 'Position Set Code Length Array Size' in Block Header.
+  // For EFI 1.1 de/compression algorithm, mPBit = 4
+  // For Tiano de/compression algorithm, mPBit = 5
+  //
+  UINT8   mPBit;
+} SCRATCH_DATA;
+
+STATIC
+VOID
+FillBuf (
+  IN  SCRATCH_DATA  *Sd,
+  IN  UINT16        NumOfBits
+  )
+/*++
+
+Routine Description:
+
+  Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
+
+Arguments:
+
+  Sd        - The global scratch data
+  NumOfBits  - The number of bits to shift and read.
+
+Returns: (VOID)
+
+--*/
+{
+  Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);
+
+  while (NumOfBits > Sd->mBitCount) {
+
+    Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));
+
+    if (Sd->mCompSize > 0) {
+      //
+      // Get 1 byte into SubBitBuf
+      //
+      Sd->mCompSize--;
+      Sd->mSubBitBuf  = 0;
+      Sd->mSubBitBuf  = Sd->mSrcBase[Sd->mInBuf++];
+      Sd->mBitCount   = 8;
+
+    } else {
+      //
+      // No more bits from the source, just pad zero bit.
+      //
+      Sd->mSubBitBuf  = 0;
+      Sd->mBitCount   = 8;
+
+    }
+  }
+
+  Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);
+  Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;
+}
+
+STATIC
+UINT32
+GetBits (
+  IN  SCRATCH_DATA  *Sd,
+  IN  UINT16        NumOfBits
+  )
+/*++
+
+Routine Description:
+
+  Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
+  NumOfBits of bits from source. Returns NumOfBits of bits that are
+  popped out.
+
+Arguments:
+
+  Sd            - The global scratch data.
+  NumOfBits     - The number of bits to pop and read.
+
+Returns:
+
+  The bits that are popped out.
+
+--*/
+{
+  UINT32  OutBits;
+
+  OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
+
+  FillBuf (Sd, NumOfBits);
+
+  return OutBits;
+}
+
+STATIC
+UINT16
+MakeTable (
+  IN  SCRATCH_DATA  *Sd,
+  IN  UINT16        NumOfChar,
+  IN  UINT8         *BitLen,
+  IN  UINT16        TableBits,
+  OUT UINT16        *Table
+  )
+/*++
+
+Routine Description:
+
+  Creates Huffman Code mapping table according to code length array.
+
+Arguments:
+
+  Sd        - The global scratch data
+  NumOfChar - Number of symbols in the symbol set
+  BitLen    - Code length array
+  TableBits - The width of the mapping table
+  Table     - The table
+
+Returns:
+
+  0         - OK.
+  BAD_TABLE - The table is corrupted.
+
+--*/
+{
+  UINT16  Count[17];
+  UINT16  Weight[17];
+  UINT16  Start[18];
+  UINT16  *Pointer;
+  UINT16  Index3;
+  UINT16  Index;
+  UINT16  Len;
+  UINT16  Char;
+  UINT16  JuBits;
+  UINT16  Avail;
+  UINT16  NextCode;
+  UINT16  Mask;
+
+  for (Index = 1; Index <= 16; Index++) {
+    Count[Index] = 0;
+  }
+
+  for (Index = 0; Index < NumOfChar; Index++) {
+    Count[BitLen[Index]]++;
+  }
+
+  Start[1] = 0;
+
+  for (Index = 1; Index <= 16; Index++) {
+    Start[Index + 1] = (UINT16) (Start[Index] + (Count[Index] << (16 - Index)));
+  }
+
+  if (Start[17] != 0) {
+    /*(1U << 16)*/
+    return (UINT16) BAD_TABLE;
+  }
+
+  JuBits = (UINT16) (16 - TableBits);
+
+  for (Index = 1; Index <= TableBits; Index++) {
+    Start[Index] >>= JuBits;
+    Weight[Index] = (UINT16) (1U << (TableBits - Index));
+  }
+
+  while (Index <= 16) {
+    Weight[Index] = (UINT16) (1U << (16 - Index));
+    Index++;
+  }
+
+  Index = (UINT16) (Start[TableBits + 1] >> JuBits);
+
+  if (Index != 0) {
+    Index3 = (UINT16) (1U << TableBits);
+    while (Index != Index3) {
+      Table[Index++] = 0;
+    }
+  }
+
+  Avail = NumOfChar;
+  Mask  = (UINT16) (1U << (15 - TableBits));
+
+  for (Char = 0; Char < NumOfChar; Char++) {
+
+    Len = BitLen[Char];
+    if (Len == 0) {
+      continue;
+    }
+
+    NextCode = (UINT16) (Start[Len] + Weight[Len]);
+
+    if (Len <= TableBits) {
+
+      for (Index = Start[Len]; Index < NextCode; Index++) {
+        Table[Index] = Char;
+      }
+
+    } else {
+
+      Index3  = Start[Len];
+      Pointer = &Table[Index3 >> JuBits];
+      Index   = (UINT16) (Len - TableBits);
+
+      while (Index != 0) {
+        if (*Pointer == 0) {
+          Sd->mRight[Avail]                     = Sd->mLeft[Avail] = 0;
+          *Pointer = Avail++;
+        }
+
+        if (Index3 & Mask) {
+          Pointer = &Sd->mRight[*Pointer];
+        } else {
+          Pointer = &Sd->mLeft[*Pointer];
+        }
+
+        Index3 <<= 1;
+        Index--;
+      }
+
+      *Pointer = Char;
+
+    }
+
+    Start[Len] = NextCode;
+  }
+  //
+  // Succeeds
+  //
+  return 0;
+}
+
+STATIC
+UINT32
+DecodeP (
+  IN  SCRATCH_DATA  *Sd
+  )
+/*++
+
+Routine Description:
+
+  Decodes a position value.
+
+Arguments:
+
+  Sd      - the global scratch data
+
+Returns:
+
+  The position value decoded.
+
+--*/
+{
+  UINT16  Val;
+  UINT32  Mask;
+  UINT32  Pos;
+
+  Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
+
+  if (Val >= MAXNP) {
+    Mask = 1U << (BITBUFSIZ - 1 - 8);
+
+    do {
+
+      if (Sd->mBitBuf & Mask) {
+        Val = Sd->mRight[Val];
+      } else {
+        Val = Sd->mLeft[Val];
+      }
+
+      Mask >>= 1;
+    } while (Val >= MAXNP);
+  }
+  //
+  // Advance what we have read
+  //
+  FillBuf (Sd, Sd->mPTLen[Val]);
+
+  Pos = Val;
+  if (Val > 1) {
+    Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
+  }
+
+  return Pos;
+}
+
+STATIC
+UINT16
+ReadPTLen (
+  IN  SCRATCH_DATA  *Sd,
+  IN  UINT16        nn,
+  IN  UINT16        nbit,
+  IN  UINT16        Special
+  )
+/*++
+
+Routine Description:
+
+  Reads code lengths for the Extra Set or the Position Set
+
+Arguments:
+
+  Sd        - The global scratch data
+  nn        - Number of symbols
+  nbit      - Number of bits needed to represent nn
+  Special   - The special symbol that needs to be taken care of
+
+Returns:
+
+  0         - OK.
+  BAD_TABLE - Table is corrupted.
+
+--*/
+{
+  UINT16  Number;
+  UINT16  CharC;
+  UINT16  Index;
+  UINT32  Mask;
+
+  Number = (UINT16) GetBits (Sd, nbit);
+
+  if (Number == 0) {
+    CharC = (UINT16) GetBits (Sd, nbit);
+
+    for (Index = 0; Index < 256; Index++) {
+      Sd->mPTTable[Index] = CharC;
+    }
+
+    for (Index = 0; Index < nn; Index++) {
+      Sd->mPTLen[Index] = 0;
+    }
+
+    return 0;
+  }
+
+  Index = 0;
+
+  while (Index < Number) {
+
+    CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
+
+    if (CharC == 7) {
+      Mask = 1U << (BITBUFSIZ - 1 - 3);
+      while (Mask & Sd->mBitBuf) {
+        Mask >>= 1;
+        CharC += 1;
+      }
+    }
+
+    FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
+
+    Sd->mPTLen[Index++] = (UINT8) CharC;
+
+    if (Index == Special) {
+      CharC = (UINT16) GetBits (Sd, 2);
+      while ((INT16) (--CharC) >= 0) {
+        Sd->mPTLen[Index++] = 0;
+      }
+    }
+  }
+
+  while (Index < nn) {
+    Sd->mPTLen[Index++] = 0;
+  }
+
+  return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
+}
+
+STATIC
+VOID
+ReadCLen (
+  SCRATCH_DATA  *Sd
+  )
+/*++
+
+Routine Description:
+
+  Reads code lengths for Char&Len Set.
+
+Arguments:
+
+  Sd    - the global scratch data
+
+Returns: (VOID)
+
+--*/
+{
+  UINT16  Number;
+  UINT16  CharC;
+  UINT16  Index;
+  UINT32  Mask;
+
+  Number = (UINT16) GetBits (Sd, CBIT);
+
+  if (Number == 0) {
+    CharC = (UINT16) GetBits (Sd, CBIT);
+
+    for (Index = 0; Index < NC; Index++) {
+      Sd->mCLen[Index] = 0;
+    }
+
+    for (Index = 0; Index < 4096; Index++) {
+      Sd->mCTable[Index] = CharC;
+    }
+
+    return ;
+  }
+
+  Index = 0;
+  while (Index < Number) {
+
+    CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
+    if (CharC >= NT) {
+      Mask = 1U << (BITBUFSIZ - 1 - 8);
+
+      do {
+
+        if (Mask & Sd->mBitBuf) {
+          CharC = Sd->mRight[CharC];
+        } else {
+          CharC = Sd->mLeft[CharC];
+        }
+
+        Mask >>= 1;
+
+      } while (CharC >= NT);
+    }
+    //
+    // Advance what we have read
+    //
+    FillBuf (Sd, Sd->mPTLen[CharC]);
+
+    if (CharC <= 2) {
+
+      if (CharC == 0) {
+        CharC = 1;
+      } else if (CharC == 1) {
+        CharC = (UINT16) (GetBits (Sd, 4) + 3);
+      } else if (CharC == 2) {
+        CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
+      }
+
+      while ((INT16) (--CharC) >= 0) {
+        Sd->mCLen[Index++] = 0;
+      }
+
+    } else {
+
+      Sd->mCLen[Index++] = (UINT8) (CharC - 2);
+
+    }
+  }
+
+  while (Index < NC) {
+    Sd->mCLen[Index++] = 0;
+  }
+
+  MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
+
+  return ;
+}
+
+STATIC
+UINT16
+DecodeC (
+  SCRATCH_DATA  *Sd
+  )
+/*++
+
+Routine Description:
+
+  Decode a character/length value.
+
+Arguments:
+
+  Sd    - The global scratch data.
+
+Returns:
+
+  The value decoded.
+
+--*/
+{
+  UINT16  Index2;
+  UINT32  Mask;
+
+  if (Sd->mBlockSize == 0) {
+    //
+    // Starting a new block
+    //
+    Sd->mBlockSize    = (UINT16) GetBits (Sd, 16);
+    Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
+    if (Sd->mBadTableFlag != 0) {
+      return 0;
+    }
+
+    ReadCLen (Sd);
+
+    Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
+    if (Sd->mBadTableFlag != 0) {
+      return 0;
+    }
+  }
+
+  Sd->mBlockSize--;
+  Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
+
+  if (Index2 >= NC) {
+    Mask = 1U << (BITBUFSIZ - 1 - 12);
+
+    do {
+      if (Sd->mBitBuf & Mask) {
+        Index2 = Sd->mRight[Index2];
+      } else {
+        Index2 = Sd->mLeft[Index2];
+      }
+
+      Mask >>= 1;
+    } while (Index2 >= NC);
+  }
+  //
+  // Advance what we have read
+  //
+  FillBuf (Sd, Sd->mCLen[Index2]);
+
+  return Index2;
+}
+
+STATIC
+VOID
+Decode (
+  SCRATCH_DATA  *Sd
+  )
+/*++
+
+Routine Description:
+
+  Decode the source data and put the resulting data into the destination buffer.
+
+Arguments:
+
+  Sd            - The global scratch data
+
+Returns: (VOID)
+
+ --*/
+{
+  UINT16  BytesRemain;
+  UINT32  DataIdx;
+  UINT16  CharC;
+
+  BytesRemain = (UINT16) (-1);
+
+  DataIdx     = 0;
+
+  for (;;) {
+    CharC = DecodeC (Sd);
+    if (Sd->mBadTableFlag != 0) {
+      return ;
+    }
+
+    if (CharC < 256) {
+      //
+      // Process an Original character
+      //
+      if (Sd->mOutBuf >= Sd->mOrigSize) {
+        return ;
+      } else {
+        Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
+      }
+
+    } else {
+      //
+      // Process a Pointer
+      //
+      CharC       = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));
+
+      BytesRemain = CharC;
+
+      DataIdx     = Sd->mOutBuf - DecodeP (Sd) - 1;
+
+      BytesRemain--;
+      while ((INT16) (BytesRemain) >= 0) {
+        Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
+        if (Sd->mOutBuf >= Sd->mOrigSize) {
+          return ;
+        }
+
+        BytesRemain--;
+      }
+    }
+  }
+
+  return ;
+}
+
+EFI_STATUS
+GetInfo (
+  IN      VOID    *Source,
+  IN      UINT32  SrcSize,
+  OUT     UINT32  *DstSize,
+  OUT     UINT32  *ScratchSize
+  )
+/*++
+
+Routine Description:
+
+  The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().
+
+Arguments:
+
+  Source      - The source buffer containing the compressed data.
+  SrcSize     - The size of source buffer
+  DstSize     - The size of destination buffer.
+  ScratchSize - The size of scratch buffer.
+
+Returns:
+
+  EFI_SUCCESS           - The size of destination buffer and the size of scratch buffer are successull retrieved.
+  EFI_INVALID_PARAMETER - The source data is corrupted
+
+--*/
+{
+  UINT8 *Src;
+
+  *ScratchSize  = sizeof (SCRATCH_DATA);
+
+  Src           = Source;
+  if (SrcSize < 8) {
+    return EFI_INVALID_PARAMETER;
+  }
+
+  *DstSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
+  return EFI_SUCCESS;
+}
+
+EFI_STATUS
+Decompress (
+  IN      VOID    *Source,
+  IN      UINT32  SrcSize,
+  IN OUT  VOID    *Destination,
+  IN      UINT32  DstSize,
+  IN OUT  VOID    *Scratch,
+  IN      UINT32  ScratchSize,
+  IN      UINT8   Version
+  )
+/*++
+
+Routine Description:
+
+  The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().
+
+Arguments:
+
+  Source      - The source buffer containing the compressed data.
+  SrcSize     - The size of source buffer
+  Destination - The destination buffer to store the decompressed data
+  DstSize     - The size of destination buffer.
+  Scratch     - The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.
+  ScratchSize - The size of scratch buffer.
+  Version     - The version of de/compression algorithm.
+                Version 1 for EFI 1.1 de/compression algorithm.
+                Version 2 for Tiano de/compression algorithm.
+
+Returns:
+
+  EFI_SUCCESS           - Decompression is successfull
+  EFI_INVALID_PARAMETER - The source data is corrupted
+
+--*/
+{
+  UINT32        Index;
+  UINT32        CompSize;
+  UINT32        OrigSize;
+  EFI_STATUS    Status;
+  SCRATCH_DATA  *Sd;
+  UINT8         *Src;
+  UINT8         *Dst;
+
+  Status  = EFI_SUCCESS;
+  Src     = Source;
+  Dst     = Destination;
+
+  if (ScratchSize < sizeof (SCRATCH_DATA)) {
+    return EFI_INVALID_PARAMETER;
+  }
+
+  Sd = (SCRATCH_DATA *) Scratch;
+
+  if (SrcSize < 8) {
+    return EFI_INVALID_PARAMETER;
+  }
+
+  CompSize  = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
+  OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
+
+  //
+  // If compressed file size is 0, return
+  //
+  if (OrigSize == 0) {
+    return Status;
+  }
+
+  if (SrcSize < CompSize + 8) {
+    return EFI_INVALID_PARAMETER;
+  }
+
+  if (DstSize != OrigSize) {
+    return EFI_INVALID_PARAMETER;
+  }
+
+  Src = Src + 8;
+
+  for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
+    ((UINT8 *) Sd)[Index] = 0;
+  }
+  //
+  // The length of the field 'Position Set Code Length Array Size' in Block Header.
+  // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
+  // For Tiano de/compression algorithm(Version 2), mPBit = 5
+  //
+  switch (Version) {
+  case 1:
+    Sd->mPBit = 4;
+    break;
+
+  case 2:
+    Sd->mPBit = 5;
+    break;
+
+  default:
+    //
+    // Currently, only have 2 versions
+    //
+    return EFI_INVALID_PARAMETER;
+  }
+
+  Sd->mSrcBase  = Src;
+  Sd->mDstBase  = Dst;
+  Sd->mCompSize = CompSize;
+  Sd->mOrigSize = OrigSize;
+
+  //
+  // Fill the first BITBUFSIZ bits
+  //
+  FillBuf (Sd, BITBUFSIZ);
+
+  //
+  // Decompress it
+  //
+  Decode (Sd);
+
+  if (Sd->mBadTableFlag != 0) {
+    //
+    // Something wrong with the source
+    //
+    Status = EFI_INVALID_PARAMETER;
+  }
+
+  return Status;
+}
+
+EFI_STATUS
+EFIAPI
+EfiGetInfo (
+  IN      VOID                    *Source,
+  IN      UINT32                  SrcSize,
+  OUT     UINT32                  *DstSize,
+  OUT     UINT32                  *ScratchSize
+  )
+/*++
+
+Routine Description:
+
+  The implementation is same as that  of EFI_DECOMPRESS_PROTOCOL.GetInfo().
+
+Arguments:
+
+  This        - The protocol instance pointer
+  Source      - The source buffer containing the compressed data.
+  SrcSize     - The size of source buffer
+  DstSize     - The size of destination buffer.
+  ScratchSize - The size of scratch buffer.
+
+Returns:
+
+  EFI_SUCCESS           - The size of destination buffer and the size of scratch buffer are successull retrieved.
+  EFI_INVALID_PARAMETER - The source data is corrupted
+
+--*/
+{
+  return GetInfo (
+          Source,
+          SrcSize,
+          DstSize,
+          ScratchSize
+          );
+}
+
+EFI_STATUS
+EFIAPI
+EfiDecompress (
+  IN      VOID                    *Source,
+  IN      UINT32                  SrcSize,
+  IN OUT  VOID                    *Destination,
+  IN      UINT32                  DstSize,
+  IN OUT  VOID                    *Scratch,
+  IN      UINT32                  ScratchSize
+  )
+/*++
+
+Routine Description:
+
+  The implementation is same as that of EFI_DECOMPRESS_PROTOCOL.Decompress().
+
+Arguments:
+
+  This        - The protocol instance pointer
+  Source      - The source buffer containing the compressed data.
+  SrcSize     - The size of source buffer
+  Destination - The destination buffer to store the decompressed data
+  DstSize     - The size of destination buffer.
+  Scratch     - The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.
+  ScratchSize - The size of scratch buffer.
+
+Returns:
+
+  EFI_SUCCESS           - Decompression is successfull
+  EFI_INVALID_PARAMETER - The source data is corrupted
+
+--*/
+{
+  //
+  // For EFI 1.1 de/compression algorithm, the version is 1.
+  //
+  return Decompress (
+          Source,
+          SrcSize,
+          Destination,
+          DstSize,
+          Scratch,
+          ScratchSize,
+          1
+          );
+}
+
+EFI_STATUS
+EFIAPI
+TianoGetInfo (
+  IN      VOID                          *Source,
+  IN      UINT32                        SrcSize,
+  OUT     UINT32                        *DstSize,
+  OUT     UINT32                        *ScratchSize
+  )
+/*++
+
+Routine Description:
+
+  The implementation is same as that of EFI_TIANO_DECOMPRESS_PROTOCOL.GetInfo().
+
+Arguments:
+
+  This        - The protocol instance pointer
+  Source      - The source buffer containing the compressed data.
+  SrcSize     - The size of source buffer
+  DstSize     - The size of destination buffer.
+  ScratchSize - The size of scratch buffer.
+
+Returns:
+
+  EFI_SUCCESS           - The size of destination buffer and the size of scratch buffer are successull retrieved.
+  EFI_INVALID_PARAMETER - The source data is corrupted
+
+--*/
+{
+  return GetInfo (
+          Source,
+          SrcSize,
+          DstSize,
+          ScratchSize
+          );
+}
+
+EFI_STATUS
+EFIAPI
+TianoDecompress (
+  IN      VOID                          *Source,
+  IN      UINT32                        SrcSize,
+  IN OUT  VOID                          *Destination,
+  IN      UINT32                        DstSize,
+  IN OUT  VOID                          *Scratch,
+  IN      UINT32                        ScratchSize
+  )
+/*++
+
+Routine Description:
+
+  The implementation is same as that  of EFI_TIANO_DECOMPRESS_PROTOCOL.Decompress().
+
+Arguments:
+
+  This        - The protocol instance pointer
+  Source      - The source buffer containing the compressed data.
+  SrcSize     - The size of source buffer
+  Destination - The destination buffer to store the decompressed data
+  DstSize     - The size of destination buffer.
+  Scratch     - The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.
+  ScratchSize - The size of scratch buffer.
+
+Returns:
+
+  EFI_SUCCESS           - Decompression is successfull
+  EFI_INVALID_PARAMETER - The source data is corrupted
+
+--*/
+{
+  //
+  // For Tiano de/compression algorithm, the version is 2.
+  //
+  return Decompress (
+          Source,
+          SrcSize,
+          Destination,
+          DstSize,
+          Scratch,
+          ScratchSize,
+          2
+          );
+}
diff --git a/utility/include/bmpblk_util.h b/utility/include/bmpblk_util.h
index 6a2f92bc..c8caf1fc 100644
--- a/utility/include/bmpblk_util.h
+++ b/utility/include/bmpblk_util.h
@@ -7,7 +7,7 @@
 
 #include "bmpblk_header.h"
 
-int display_bmpblock(const char *infile);
-int extract_bmpblock(const char *infile, const char *dirname, int force);
+int dump_bmpblock(const char *infile, int show_as_yaml,
+                  const char *todir, int overwrite);
 
 #endif // VBOOT_REFERENCE_BMPBLK_UTIL_H_
diff --git a/utility/include/bmpblk_utility.h b/utility/include/bmpblk_utility.h
index b73b6630..099767a5 100644
--- a/utility/include/bmpblk_utility.h
+++ b/utility/include/bmpblk_utility.h
@@ -64,6 +64,9 @@ class BmpBlockUtil {
   /* Write the bmpblock to a file */
   void write_to_bmpblock(const char *filename);
 
+  /* What compression to use for the images */
+  void force_compression(uint32_t compression);
+
  private:
   /* Clear all internal data. */
   void initialize();
@@ -105,6 +108,10 @@ class BmpBlockUtil {
 
   /* Internal variable for storing the content of BmpBlock. */
   string bmpblock_;
+
+  /* Internal variables to determine whether or not to specify compression */
+  bool set_compression_;                // true if we force it
+  uint32_t compression_;                // what we force it to
 };
 
 }  // namespace vboot_reference
diff --git a/utility/include/eficompress.h b/utility/include/eficompress.h
new file mode 100644
index 00000000..ddd8a90c
--- /dev/null
+++ b/utility/include/eficompress.h
@@ -0,0 +1,86 @@
+/* Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#define EFI_STATUS int
+#define VOID void
+#define INT16 int16_t
+#define UINT16 uint16_t
+#define INT8 int8_t
+#define UINT8 uint8_t
+#define INT32 int32_t
+#define UINT32 uint32_t
+#define STATIC static
+#define IN /**/
+#define OUT /**/
+#define EFIAPI /**/
+
+#define EFIERR(a) (a)
+#define EFI_SUCCESS               0
+#define EFI_LOAD_ERROR            EFIERR (1)
+#define EFI_INVALID_PARAMETER     EFIERR (2)
+#define EFI_UNSUPPORTED           EFIERR (3)
+#define EFI_BAD_BUFFER_SIZE       EFIERR (4)
+#define EFI_BUFFER_TOO_SMALL      EFIERR (5)
+#define EFI_NOT_READY             EFIERR (6)
+#define EFI_DEVICE_ERROR          EFIERR (7)
+#define EFI_WRITE_PROTECTED       EFIERR (8)
+#define EFI_OUT_OF_RESOURCES      EFIERR (9)
+#define EFI_VOLUME_CORRUPTED      EFIERR (10)
+#define EFI_VOLUME_FULL           EFIERR (11)
+#define EFI_NO_MEDIA              EFIERR (12)
+#define EFI_MEDIA_CHANGED         EFIERR (13)
+#define EFI_NOT_FOUND             EFIERR (14)
+#define EFI_ACCESS_DENIED         EFIERR (15)
+#define EFI_NO_RESPONSE           EFIERR (16)
+#define EFI_NO_MAPPING            EFIERR (17)
+#define EFI_TIMEOUT               EFIERR (18)
+#define EFI_NOT_STARTED           EFIERR (19)
+#define EFI_ALREADY_STARTED       EFIERR (20)
+#define EFI_ABORTED               EFIERR (21)
+#define EFI_ICMP_ERROR            EFIERR (22)
+#define EFI_TFTP_ERROR            EFIERR (23)
+#define EFI_PROTOCOL_ERROR        EFIERR (24)
+#define EFI_INCOMPATIBLE_VERSION  EFIERR (25)
+#define EFI_SECURITY_VIOLATION    EFIERR (26)
+#define EFI_CRC_ERROR             EFIERR (27)
+#define EFI_END_OF_MEDIA          EFIERR (28)
+#define EFI_END_OF_FILE           EFIERR (31)
+#define EFI_INVALID_LANGUAGE      EFIERR (32)
+
+#define EFIWARN(a) ((a)+EFI_INVALID_LANGUAGE)
+#define EFI_WARN_UNKNOWN_GLYPH    EFIWARN (1)
+#define EFI_WARN_DELETE_FAILURE   EFIWARN (2)
+#define EFI_WARN_WRITE_FAILURE    EFIWARN (3)
+#define EFI_WARN_BUFFER_TOO_SMALL EFIWARN (4)
+
+#define EFI_ERROR(Status) (Status != 0 && Status < EFIWARN(1))
+
+EFI_STATUS
+EfiCompress (
+  IN      UINT8   *SrcBuffer,
+  IN      UINT32  SrcSize,
+  IN      UINT8   *DstBuffer,
+  IN OUT  UINT32  *DstSize
+  );
+
+EFI_STATUS
+EFIAPI
+EfiGetInfo (
+  IN      VOID                    *Source,
+  IN      UINT32                  SrcSize,
+  OUT     UINT32                  *DstSize,
+  OUT     UINT32                  *ScratchSize
+  );
+
+EFI_STATUS
+EFIAPI
+EfiDecompress (
+  IN      VOID                    *Source,
+  IN      UINT32                  SrcSize,
+  IN OUT  VOID                    *Destination,
+  IN      UINT32                  DstSize,
+  IN OUT  VOID                    *Scratch,
+  IN      UINT32                  ScratchSize
+  );