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
diff --git a/tests/bitmaps/Background.bmp b/tests/bitmaps/Background.bmp
new file mode 100644
index 0000000..a83c995
--- /dev/null
+++ b/tests/bitmaps/Background.bmp
Binary files differ
diff --git a/tests/bitmaps/TestBmpBlock.py b/tests/bitmaps/TestBmpBlock.py
index 77ef419..ced270e 100755
--- a/tests/bitmaps/TestBmpBlock.py
+++ b/tests/bitmaps/TestBmpBlock.py
@@ -19,7 +19,7 @@
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 @@
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 0000000..ba4a0e0
--- /dev/null
+++ b/tests/bitmaps/Word.bmp
Binary files differ
diff --git a/tests/bitmaps/case_simple.yaml b/tests/bitmaps/case_simple.yaml
new file mode 100644
index 0000000..5c8590d
--- /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 a424941..af0187b 100644
--- a/utility/Makefile
+++ b/utility/Makefile
@@ -65,8 +65,16 @@
${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 d7b9cbf..214beda 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 @@
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 @@
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 66b60d9..9f912d0 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 @@
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 @@
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 @@
/* 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 @@
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 @@
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 @@
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 @@
}
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 @@
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 0000000..b0cf4fb
--- /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 0000000..8ec4a08
--- /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 6a2f92b..c8caf1f 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 b73b663..099767a 100644
--- a/utility/include/bmpblk_utility.h
+++ b/utility/include/bmpblk_utility.h
@@ -64,6 +64,9 @@
/* 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 @@
/* 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 0000000..ddd8a90
--- /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
+ );
