cbfs: Add LZ4 in-place decompression support for pre-RAM stages

This patch ports the LZ4 decompression code that debuted in libpayload
last year to coreboot for use in CBFS stages (upgrading the base
algorithm to LZ4's dev branch to access the new in-place decompression
checks). This is especially useful for pre-RAM stages in constrained
SRAM-based systems, which previously could not be compressed due to
the size requirements of the LZMA scratchpad and bounce buffer. The
LZ4 algorithm offers a very lean decompressor function and in-place
decompression support to achieve roughly the same boot speed gains
(trading compression ratio for decompression time) with nearly no
memory overhead.

For now we only activate it for the stages that had previously not been
compressed at all on non-XIP (read: non-x86) boards. In the future we
may also consider replacing LZMA completely for certain boards, since
which algorithm wins out on boot speed depends on board-specific
parameters (architecture, processor speed, SPI transfer rate, etc.).

BRANCH=None
BUG=None
TEST=Built and booted Oak, Jerry, Nyan and Falco. Measured boot time on
Oak to be about ~20ms faster (cutting load times for affected stages
almost in half).

Change-Id: Iec256c0e6d585d1b69985461939884a54e3ab900
Signed-off-by: Julius Werner <jwerner@chromium.org>
Reviewed-on: https://review.coreboot.org/13638
Tested-by: build bot (Jenkins)
Reviewed-by: Aaron Durbin <adurbin@chromium.org>

13 files changed, 604 insertions, 44 deletions

diff --git a/src/Kconfig b/src/Kconfig
index 4cceb141c7..3def65b758 100644
--- a/src/Kconfig
+++ b/src/Kconfig
@@ -156,6 +156,17 @@ config COMPRESS_RAMSTAGE
 	  that decompression might slow down booting if the boot flash
 	  is connected through a slow link (i.e. SPI).
 
+config COMPRESS_PRERAM_STAGES
+	bool "Compress romstage and verstage with LZ4"
+	default y if !ARCH_X86
+	default n
+	help
+	  Compress romstage and (if it exists) verstage with LZ4 to save flash
+	  space and speed up boot, since the time for reading the image from SPI
+	  (and in the vboot case verifying it) is usually much greater than the
+	  time spent decompressing. Doesn't work for XIP stages (assume all
+	  ARCH_X86 for now) for obvious reasons.
+
 config INCLUDE_CONFIG_FILE
 	bool "Include the coreboot .config file into the ROM image"
 	default y
diff --git a/src/commonlib/Makefile.inc b/src/commonlib/Makefile.inc
index 19f9ba3b8d..2752922067 100644
--- a/src/commonlib/Makefile.inc
+++ b/src/commonlib/Makefile.inc
@@ -16,3 +16,8 @@ verstage-y += cbfs.c
 romstage-y += cbfs.c
 ramstage-y += cbfs.c
 smm-y += cbfs.c
+
+bootblock-y += lz4_wrapper.c
+verstage-y += lz4_wrapper.c
+romstage-y += lz4_wrapper.c
+ramstage-y += lz4_wrapper.c
diff --git a/src/commonlib/include/commonlib/cbfs_serialized.h b/src/commonlib/include/commonlib/cbfs_serialized.h
index bea5d6bb9d..c1a1c3b542 100644
--- a/src/commonlib/include/commonlib/cbfs_serialized.h
+++ b/src/commonlib/include/commonlib/cbfs_serialized.h
@@ -56,6 +56,7 @@
 
 #define CBFS_COMPRESS_NONE  0
 #define CBFS_COMPRESS_LZMA  1
+#define CBFS_COMPRESS_LZ4   2
 
 /** These are standard component types for well known
     components (i.e - those that coreboot needs to consume.
diff --git a/src/commonlib/include/commonlib/compression.h b/src/commonlib/include/commonlib/compression.h
new file mode 100644
index 0000000000..428ee42e65
--- /dev/null
+++ b/src/commonlib/include/commonlib/compression.h
@@ -0,0 +1,34 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright 2016 Google Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ */
+
+#ifndef _COMMONLIB_COMPRESSION_H_
+#define _COMMONLIB_COMPRESSION_H_
+
+#include <stddef.h>
+
+/* Decompresses an LZ4F image (multiple LZ4 blocks with frame header) from src
+ * to dst, ensuring that it doesn't read more than srcn bytes and doesn't write
+ * more than dstn. Buffer sizes must stay below 2GB. Can decompress files loaded
+ * to the end of a buffer in-place, as long as buffer is larger than the final
+ * output size. (Usually just a few bytes, but may be up to (8 + dstn/255) in
+ * worst case. Will reliably return an error if buffer was too small.)
+ * Returns amount of decompressed bytes, or 0 on error.
+ */
+size_t ulz4fn(const void *src, size_t srcn, void *dst, size_t dstn);
+
+/* Same as ulz4fn() but does not perform any bounds checks. */
+size_t ulz4f(const void *src, void *dst);
+
+#endif	/* _COMMONLIB_COMPRESSION_H_ */
diff --git a/src/commonlib/include/commonlib/timestamp_serialized.h b/src/commonlib/include/commonlib/timestamp_serialized.h
index 6ce087924d..c665964a0d 100644
--- a/src/commonlib/include/commonlib/timestamp_serialized.h
+++ b/src/commonlib/include/commonlib/timestamp_serialized.h
@@ -47,6 +47,8 @@ enum timestamp_id {
 	TS_END_COPYROM = 14,
 	TS_START_ULZMA = 15,
 	TS_END_ULZMA = 16,
+	TS_START_ULZ4F = 17,
+	TS_END_ULZ4F = 18,
 	TS_DEVICE_ENUMERATE = 30,
 	TS_DEVICE_CONFIGURE = 40,
 	TS_DEVICE_ENABLE = 50,
diff --git a/src/commonlib/lz4.c.inc b/src/commonlib/lz4.c.inc
new file mode 100644
index 0000000000..b3be4e5b44
--- /dev/null
+++ b/src/commonlib/lz4.c.inc
@@ -0,0 +1,280 @@
+/*
+   LZ4 - Fast LZ compression algorithm
+   Copyright (C) 2011-2015, Yann Collet.
+
+   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions are
+   met:
+
+       * Redistributions of source code must retain the above copyright
+   notice, this list of conditions and the following disclaimer.
+       * Redistributions in binary form must reproduce the above
+   copyright notice, this list of conditions and the following disclaimer
+   in the documentation and/or other materials provided with the
+   distribution.
+
+   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+   You can contact the author at :
+   - LZ4 source repository : https://github.com/Cyan4973/lz4
+   - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
+*/
+
+
+/**************************************
+*  Reading and writing into memory
+**************************************/
+
+/* customized variant of memcpy, which can overwrite up to 7 bytes beyond dstEnd */
+static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
+{
+    BYTE* d = (BYTE*)dstPtr;
+    const BYTE* s = (const BYTE*)srcPtr;
+    BYTE* const e = (BYTE*)dstEnd;
+
+#if 0
+    const size_t l2 = 8 - (((size_t)d) & (sizeof(void*)-1));
+    LZ4_copy8(d,s); if (d>e-9) return;
+    d+=l2; s+=l2;
+#endif /* join to align */
+
+    do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
+}
+
+
+/**************************************
+*  Common Constants
+**************************************/
+#define MINMATCH 4
+
+#define WILDCOPYLENGTH 8
+#define LASTLITERALS 5
+#define MFLIMIT (WILDCOPYLENGTH+MINMATCH)
+static const int LZ4_minLength = (MFLIMIT+1);
+
+#define KB *(1 <<10)
+#define MB *(1 <<20)
+#define GB *(1U<<30)
+
+#define MAXD_LOG 16
+#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
+
+#define ML_BITS  4
+#define ML_MASK  ((1U<<ML_BITS)-1)
+#define RUN_BITS (8-ML_BITS)
+#define RUN_MASK ((1U<<RUN_BITS)-1)
+
+
+/**************************************
+*  Local Structures and types
+**************************************/
+typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
+typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
+typedef enum { full = 0, partial = 1 } earlyEnd_directive;
+
+
+
+/*******************************
+*  Decompression functions
+*******************************/
+/*
+ * This generic decompression function cover all use cases.
+ * It shall be instantiated several times, using different sets of directives
+ * Note that it is essential this generic function is really inlined,
+ * in order to remove useless branches during compilation optimization.
+ */
+FORCE_INLINE int LZ4_decompress_generic(
+                 const char* const source,
+                 char* const dest,
+                 int inputSize,
+                 int outputSize,         /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
+
+                 int endOnInput,         /* endOnOutputSize, endOnInputSize */
+                 int partialDecoding,    /* full, partial */
+                 int targetOutputSize,   /* only used if partialDecoding==partial */
+                 int dict,               /* noDict, withPrefix64k, usingExtDict */
+                 const BYTE* const lowPrefix,  /* == dest if dict == noDict */
+                 const BYTE* const dictStart,  /* only if dict==usingExtDict */
+                 const size_t dictSize         /* note : = 0 if noDict */
+                 )
+{
+    /* Local Variables */
+    const BYTE* ip = (const BYTE*) source;
+    const BYTE* const iend = ip + inputSize;
+
+    BYTE* op = (BYTE*) dest;
+    BYTE* const oend = op + outputSize;
+    BYTE* cpy;
+    BYTE* oexit = op + targetOutputSize;
+    const BYTE* const lowLimit = lowPrefix - dictSize;
+
+    const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
+    const unsigned dec32table[] = {4, 1, 2, 1, 4, 4, 4, 4};
+    const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
+
+    const int safeDecode = (endOnInput==endOnInputSize);
+    const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
+    const int inPlaceDecode = ((ip >= op) && (ip < oend));
+
+
+    /* Special cases */
+    if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT;                         /* targetOutputSize too high => decode everything */
+    if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1;  /* Empty output buffer */
+    if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
+
+
+    /* Main Loop */
+    while (1)
+    {
+        unsigned token;
+        size_t length;
+        const BYTE* match;
+        size_t offset;
+
+        if (unlikely((inPlaceDecode) && (op + WILDCOPYLENGTH > ip))) goto _output_error;   /* output stream ran over input stream */
+
+        /* get literal length */
+        token = *ip++;
+        if ((length=(token>>ML_BITS)) == RUN_MASK)
+        {
+            unsigned s;
+            do
+            {
+                s = *ip++;
+                length += s;
+            }
+            while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) && (s==255) );
+            if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error;   /* overflow detection */
+            if ((safeDecode) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error;   /* overflow detection */
+        }
+
+        /* copy literals */
+        cpy = op+length;
+        if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
+            || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)))
+        {
+            if (partialDecoding)
+            {
+                if (cpy > oend) goto _output_error;                           /* Error : write attempt beyond end of output buffer */
+                if ((endOnInput) && (ip+length > iend)) goto _output_error;   /* Error : read attempt beyond end of input buffer */
+            }
+            else
+            {
+                if ((!endOnInput) && (cpy != oend)) goto _output_error;       /* Error : block decoding must stop exactly there */
+                if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error;   /* Error : input must be consumed */
+            }
+            memmove(op, ip, length);
+            ip += length;
+            op += length;
+            break;     /* Necessarily EOF, due to parsing restrictions */
+        }
+        LZ4_wildCopy(op, ip, cpy);
+        ip += length; op = cpy;
+
+        /* get offset */
+        offset = LZ4_readLE16(ip); ip+=2;
+        match = op - offset;
+        if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error;   /* Error : offset outside buffers */
+
+        /* get matchlength */
+        length = token & ML_MASK;
+        if (length == ML_MASK)
+        {
+            unsigned s;
+            do
+            {
+                if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
+                s = *ip++;
+                length += s;
+            } while (s==255);
+            if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error;   /* overflow detection */
+        }
+        length += MINMATCH;
+
+        /* check external dictionary */
+        if ((dict==usingExtDict) && (match < lowPrefix))
+        {
+            if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error;   /* doesn't respect parsing restriction */
+
+            if (length <= (size_t)(lowPrefix-match))
+            {
+                /* match can be copied as a single segment from external dictionary */
+                match = dictEnd - (lowPrefix-match);
+                memmove(op, match, length); op += length;
+            }
+            else
+            {
+                /* match encompass external dictionary and current block */
+                size_t copySize = (size_t)(lowPrefix-match);
+                memcpy(op, dictEnd - copySize, copySize);
+                op += copySize;
+                copySize = length - copySize;
+                if (copySize > (size_t)(op-lowPrefix))   /* overlap copy */
+                {
+                    BYTE* const endOfMatch = op + copySize;
+                    const BYTE* copyFrom = lowPrefix;
+                    while (op < endOfMatch) *op++ = *copyFrom++;
+                }
+                else
+                {
+                    memcpy(op, lowPrefix, copySize);
+                    op += copySize;
+                }
+            }
+            continue;
+        }
+
+        /* copy match within block */
+        cpy = op + length;
+        if (unlikely(offset<8))
+        {
+            const int dec64 = dec64table[offset];
+            op[0] = match[0];
+            op[1] = match[1];
+            op[2] = match[2];
+            op[3] = match[3];
+            match += dec32table[offset];
+            memcpy(op+4, match, 4);
+            match -= dec64;
+        } else { LZ4_copy8(op, match); match+=8; }
+        op += 8;
+
+        if (unlikely(cpy>oend-12))
+        {
+            BYTE* const oCopyLimit = oend-(WILDCOPYLENGTH-1);
+            if (cpy > oend-LASTLITERALS) goto _output_error;    /* Error : last LASTLITERALS bytes must be literals (uncompressed) */
+            if (op < oCopyLimit)
+            {
+                LZ4_wildCopy(op, match, oCopyLimit);
+                match += oCopyLimit - op;
+                op = oCopyLimit;
+            }
+            while (op<cpy) *op++ = *match++;
+        }
+        else
+            LZ4_wildCopy(op, match, cpy);
+        op=cpy;   /* correction */
+    }
+
+    /* end of decoding */
+    if (endOnInput)
+       return (int) (((char*)op)-dest);     /* Nb of output bytes decoded */
+    else
+       return (int) (((const char*)ip)-source);   /* Nb of input bytes read */
+
+    /* Overflow error detected */
+_output_error:
+    return (int) (-(((const char*)ip)-source))-1;
+}
diff --git a/src/commonlib/lz4_wrapper.c b/src/commonlib/lz4_wrapper.c
new file mode 100644
index 0000000000..ea7b90d8fd
--- /dev/null
+++ b/src/commonlib/lz4_wrapper.c
@@ -0,0 +1,193 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote products
+ *    derived from this software without specific prior written permission.
+ *
+ * Alternatively, this software may be distributed under the terms of the
+ * GNU General Public License ("GPL") version 2 as published by the Free
+ * Software Foundation.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <commonlib/compression.h>
+#include <commonlib/endian.h>
+#include <commonlib/helpers.h>
+#include <stdint.h>
+#include <string.h>
+
+/* LZ4 comes with its own supposedly portable memory access functions, but they
+ * seem to be very inefficient in practice (at least on ARM64). Since coreboot
+ * knows about endinaness and allows some basic assumptions (such as unaligned
+ * access support), we can easily write the ones we need ourselves. */
+static uint16_t LZ4_readLE16(const void *src)
+{
+	return read_le16(src);
+}
+static void LZ4_copy8(void *dst, const void *src)
+{
+/* ARM32 needs to be a special snowflake to prevent GCC from coalescing the
+ * access into LDRD/STRD (which don't support unaligned accesses). */
+#ifdef __arm__	/* ARMv < 6 doesn't support unaligned accesses at all. */
+	#if defined(__COREBOOT_ARM_ARCH__) && __COREBOOT_ARM_ARCH__ < 6
+		int i;
+		for (i = 0; i < 8; i++)
+			((uint8_t *)dst)[i] = ((uint8_t *)src)[i];
+	#else
+		uint32_t x0, x1;
+		asm volatile (
+			"ldr %[x0], [%[src]]\n\t"
+			"ldr %[x1], [%[src], #4]\n\t"
+			"str %[x0], [%[dst]]\n\t"
+			"str %[x1], [%[dst], #4]\n\t"
+			: [x0]"=r"(x0), [x1]"=r"(x1)
+			: [src]"r"(src), [dst]"r"(dst)
+			: "memory" );
+	#endif
+#else
+	*(uint64_t *)dst = *(const uint64_t *)src;
+#endif
+}
+
+typedef  uint8_t BYTE;
+typedef uint16_t U16;
+typedef uint32_t U32;
+typedef  int32_t S32;
+typedef uint64_t U64;
+
+#define FORCE_INLINE static inline __attribute__((always_inline))
+#define likely(expr) __builtin_expect((expr) != 0, 1)
+#define unlikely(expr) __builtin_expect((expr) != 0, 0)
+
+/* Unaltered (just removed unrelated code) from github.com/Cyan4973/lz4/dev. */
+#include "lz4.c.inc"	/* #include for inlining, do not link! */
+
+#define LZ4F_MAGICNUMBER 0x184D2204
+
+struct lz4_frame_header {
+	uint32_t magic;
+	union {
+		uint8_t flags;
+		struct {
+			uint8_t reserved0		: 2;
+			uint8_t has_content_checksum	: 1;
+			uint8_t has_content_size	: 1;
+			uint8_t has_block_checksum	: 1;
+			uint8_t independent_blocks	: 1;
+			uint8_t version			: 2;
+		};
+	};
+	union {
+		uint8_t block_descriptor;
+		struct {
+			uint8_t reserved1		: 4;
+			uint8_t max_block_size		: 3;
+			uint8_t reserved2		: 1;
+		};
+	};
+	/* + uint64_t content_size iff has_content_size is set */
+	/* + uint8_t header_checksum */
+} __attribute__((packed));
+
+struct lz4_block_header {
+	union {
+		uint32_t raw;
+		struct {
+			uint32_t size		: 31;
+			uint32_t not_compressed	: 1;
+		};
+	};
+	/* + size bytes of data */
+	/* + uint32_t block_checksum iff has_block_checksum is set */
+} __attribute__((packed));
+
+size_t ulz4fn(const void *src, size_t srcn, void *dst, size_t dstn)
+{
+	const void *in = src;
+	void *out = dst;
+	size_t out_size = 0;
+	int has_block_checksum;
+
+	{ /* With in-place decompression the header may become invalid later. */
+		const struct lz4_frame_header *h = in;
+
+		if (srcn < sizeof(*h) + sizeof(uint64_t) + sizeof(uint8_t))
+			return 0;	/* input overrun */
+
+		/* We assume there's always only a single, standard frame. */
+		if (read_le32(&h->magic) != LZ4F_MAGICNUMBER || h->version != 1)
+			return 0;	/* unknown format */
+		if (h->reserved0 || h->reserved1 || h->reserved2)
+			return 0;	/* reserved must be zero */
+		if (!h->independent_blocks)
+			return 0;	/* we don't support block dependency */
+		has_block_checksum = h->has_block_checksum;
+
+		in += sizeof(*h);
+		if (h->has_content_size)
+			in += sizeof(uint64_t);
+		in += sizeof(uint8_t);
+	}
+
+	while (1) {
+		struct lz4_block_header b = { .raw = read_le32(in) };
+		in += sizeof(struct lz4_block_header);
+
+		if ((size_t)(in - src) + b.size > srcn)
+			break;			/* input overrun */
+
+		if (!b.size) {
+			out_size = out - dst;
+			break;			/* decompression successful */
+		}
+
+		if (b.not_compressed) {
+			size_t size = MIN((uint32_t)b.size, dst + dstn - out);
+			memcpy(out, in, size);
+			if (size < b.size)
+				break;		/* output overrun */
+			else
+				out += size;
+		} else {
+			/* constant folding essential, do not touch params! */
+			int ret = LZ4_decompress_generic(in, out, b.size,
+					dst + dstn - out, endOnInputSize,
+					full, 0, noDict, out, NULL, 0);
+			if (ret < 0)
+				break;		/* decompression error */
+			else
+				out += ret;
+		}
+
+		in += b.size;
+		if (has_block_checksum)
+			in += sizeof(uint32_t);
+	}
+
+	return out_size;
+}
+
+size_t ulz4f(const void *src, void *dst)
+{
+	/* LZ4 uses signed size parameters, so can't just use ((u32)-1) here. */
+	return ulz4fn(src, 1*GiB, dst, 1*GiB);
+}
diff --git a/src/include/cbfs.h b/src/include/cbfs.h
index 0d95387940..2d1921898a 100644
--- a/src/include/cbfs.h
+++ b/src/include/cbfs.h
@@ -35,6 +35,14 @@ int cbfs_boot_locate(struct cbfsf *fh, const char *name, uint32_t *type);
  * the mapping and sets the size of the file. */
 void *cbfs_boot_map_with_leak(const char *name, uint32_t type, size_t *size);
 
+/* Load |in_size| bytes from |rdev| at |offset| to the |buffer_size| bytes
+ * large |buffer|, decompressing it according to |compression| in the process.
+ * Returns the decompressed file size, or 0 on error.
+ * LZMA files will be mapped for decompression. LZ4 files will be decompressed
+ * in-place with the buffer size requirements outlined in compression.h. */
+size_t cbfs_load_and_decompress(const struct region_device *rdev, size_t offset,
+	size_t in_size, void *buffer, size_t buffer_size, uint32_t compression);
+
 /* Load stage into memory filling in prog. Return 0 on success. < 0 on error. */
 int cbfs_prog_stage_load(struct prog *prog);
 
diff --git a/src/lib/cbfs.c b/src/lib/cbfs.c
index 55a8536a36..82bfa2d8ad 100644
--- a/src/lib/cbfs.c
+++ b/src/lib/cbfs.c
@@ -19,9 +19,11 @@
 #include <stdlib.h>
 #include <boot_device.h>
 #include <cbfs.h>
+#include <commonlib/compression.h>
 #include <endian.h>
 #include <lib.h>
 #include <symbols.h>
+#include <timestamp.h>
 
 #define ERROR(x...) printk(BIOS_ERR, "CBFS: " x)
 #define LOG(x...) printk(BIOS_INFO, "CBFS: " x)
@@ -68,13 +70,57 @@ void *cbfs_boot_map_with_leak(const char *name, uint32_t type, size_t *size)
 	return rdev_mmap(&fh.data, 0, fsize);
 }
 
-static size_t inflate(void *src, void *dst)
+size_t cbfs_load_and_decompress(const struct region_device *rdev, size_t offset,
+	size_t in_size, void *buffer, size_t buffer_size, uint32_t compression)
 {
-	if (ENV_BOOTBLOCK || ENV_VERSTAGE)
-		return 0;
-	if (ENV_ROMSTAGE && !IS_ENABLED(CONFIG_COMPRESS_RAMSTAGE))
+	size_t out_size;
+
+	switch (compression) {
+	case CBFS_COMPRESS_NONE:
+		if (rdev_readat(rdev, buffer, offset, in_size) != in_size)
+			return 0;
+		return in_size;
+
+	case CBFS_COMPRESS_LZ4:
+		if ((ENV_BOOTBLOCK || ENV_VERSTAGE) &&
+		    !IS_ENABLED(CONFIG_COMPRESS_PRERAM_STAGES))
+			return 0;
+
+		/* Load the compressed image to the end of the available memory
+		 * area for in-place decompression. It is the responsibility of
+		 * the caller to ensure that buffer_size is large enough
+		 * (see compression.h, guaranteed by cbfstool for stages). */
+		void *compr_start = buffer + buffer_size - in_size;
+		if (rdev_readat(rdev, compr_start, offset, in_size) != in_size)
+			return 0;
+
+		timestamp_add_now(TS_START_ULZ4F);
+		out_size = ulz4fn(compr_start, in_size, buffer, buffer_size);
+		timestamp_add_now(TS_END_ULZ4F);
+		return out_size;
+
+	case CBFS_COMPRESS_LZMA:
+		if (ENV_BOOTBLOCK || ENV_VERSTAGE)
+			return 0;
+		if (ENV_ROMSTAGE && !IS_ENABLED(CONFIG_COMPRESS_RAMSTAGE))
+			return 0;
+
+		void *map = rdev_mmap(rdev, offset, in_size);
+		if (map == NULL)
+			return 0;
+
+		/* Note: timestamp not useful for memory-mapped media (x86) */
+		timestamp_add_now(TS_START_ULZMA);
+		out_size = ulzman(map, in_size, buffer, buffer_size);
+		timestamp_add_now(TS_END_ULZMA);
+
+		rdev_munmap(rdev, map);
+
+		return out_size;
+
+	default:
 		return 0;
-	return ulzma(src, dst);
+	}
 }
 
 static inline int tohex4(unsigned int c)
@@ -152,22 +198,9 @@ int cbfs_prog_stage_load(struct prog *pstage)
 			goto out;
 	}
 
-	if (stage.compression == CBFS_COMPRESS_NONE) {
-		if (rdev_readat(fh, load, foffset, fsize) != fsize)
-			return -1;
-	} else if (stage.compression == CBFS_COMPRESS_LZMA) {
-		void *map = rdev_mmap(fh, foffset, fsize);
-
-		if (map == NULL)
-			return -1;
-
-		fsize = inflate(map, load);
-
-		rdev_munmap(fh, map);
-
-		if (!fsize)
-			return -1;
-	} else
+	fsize = cbfs_load_and_decompress(fh, foffset, fsize, load,
+					 stage.memlen, stage.compression);
+	if (!fsize)
 		return -1;
 
 	/* Clear area not covered by file. */
diff --git a/src/lib/lzma.c b/src/lib/lzma.c
index 5566cd5dfc..d0b4c355b1 100644
--- a/src/lib/lzma.c
+++ b/src/lib/lzma.c
@@ -29,8 +29,6 @@ size_t ulzman(const void *src, size_t srcn, void *dst, size_t dstn)
 	MAYBE_STATIC unsigned char scratchpad[15980];
 	const unsigned char *cp;
 
-	/* Note: these timestamps aren't useful for memory-mapped media (x86) */
-	timestamp_add_now(TS_START_ULZMA);
 	memcpy(properties, src, LZMA_PROPERTIES_SIZE);
 	/* The outSize in LZMA stream is a 64bit integer stored in little-endian
 	 * (ref: lzma.cc@LZMACompress: put_64). To prevent accessing by
@@ -55,7 +53,6 @@ size_t ulzman(const void *src, size_t srcn, void *dst, size_t dstn)
 		printk(BIOS_WARNING, "lzma: Decoding error = %d\n", res);
 		return 0;
 	}
-	timestamp_add_now(TS_END_ULZMA);
 	return outProcessed;
 }
 
diff --git a/src/lib/rmodule.c b/src/lib/rmodule.c
index 628195cafa..585fb5f2ef 100644
--- a/src/lib/rmodule.c
+++ b/src/lib/rmodule.c
@@ -259,8 +259,6 @@ int rmodule_stage_load(struct rmod_stage_load *rsl)
 	struct cbfs_stage stage;
 	void *rmod_loc;
 	struct region_device *fh;
-	const int use_lzma = ENV_RAMSTAGE
-		|| (ENV_ROMSTAGE && IS_ENABLED(CONFIG_COMPRESS_RAMSTAGE));
 
 	if (rsl->prog == NULL || prog_name(rsl->prog) == NULL)
 		return -1;
@@ -284,24 +282,8 @@ int rmodule_stage_load(struct rmod_stage_load *rsl)
 	printk(BIOS_INFO, "Decompressing stage %s @ 0x%p (%d bytes)\n",
 	       prog_name(rsl->prog), rmod_loc, stage.memlen);
 
-	if (stage.compression == CBFS_COMPRESS_NONE) {
-		if (rdev_readat(fh, rmod_loc, sizeof(stage), stage.len) !=
-		    stage.len)
-			return -1;
-	} else if (use_lzma && (stage.compression == CBFS_COMPRESS_LZMA)) {
-		size_t fsize;
-		void *map = rdev_mmap(fh, sizeof(stage), stage.len);
-
-		if (map == NULL)
-			return -1;
-
-		fsize = ulzman(map, stage.len, rmod_loc, stage.memlen);
-
-		rdev_munmap(fh, map);
-
-		if (!fsize)
-			return -1;
-	} else
+	if (!cbfs_load_and_decompress(fh, sizeof(stage), stage.len, rmod_loc,
+				      stage.memlen, stage.compression))
 		return -1;
 
 	if (rmodule_parse(rmod_loc, &rmod_stage))
diff --git a/src/lib/selfboot.c b/src/lib/selfboot.c
index f3a1e52728..7d3e2dd5f6 100644
--- a/src/lib/selfboot.c
+++ b/src/lib/selfboot.c
@@ -14,6 +14,7 @@
  * GNU General Public License for more details.
  */
 
+#include <commonlib/compression.h>
 #include <console/console.h>
 #include <cpu/cpu.h>
 #include <endian.h>
@@ -25,6 +26,7 @@
 #include <lib.h>
 #include <bootmem.h>
 #include <program_loading.h>
+#include <timestamp.h>
 
 static const unsigned long lb_start = (unsigned long)&_program;
 static const unsigned long lb_end = (unsigned long)&_eprogram;
@@ -386,7 +388,18 @@ static int load_self_segments(
 			switch(ptr->compression) {
 				case CBFS_COMPRESS_LZMA: {
 					printk(BIOS_DEBUG, "using LZMA\n");
+					timestamp_add_now(TS_START_ULZMA);
 					len = ulzman(src, len, dest, memsz);
+					timestamp_add_now(TS_END_ULZMA);
+					if (!len) /* Decompression Error. */
+						return 0;
+					break;
+				}
+				case CBFS_COMPRESS_LZ4: {
+					printk(BIOS_DEBUG, "using LZ4\n");
+					timestamp_add_now(TS_START_ULZ4F);
+					len = ulz4fn(src, len, dest, memsz);
+					timestamp_add_now(TS_END_ULZ4F);
 					if (!len) /* Decompression Error. */
 						return 0;
 					break;
diff --git a/src/vendorcode/google/chromeos/vboot2/Makefile.inc b/src/vendorcode/google/chromeos/vboot2/Makefile.inc
index 61cf71df5a..2ca8a1adc3 100644
--- a/src/vendorcode/google/chromeos/vboot2/Makefile.inc
+++ b/src/vendorcode/google/chromeos/vboot2/Makefile.inc
@@ -72,6 +72,7 @@ ifeq ($(CONFIG_SEPARATE_VERSTAGE),y)
 cbfs-files-$(CONFIG_SEPARATE_VERSTAGE) += $(CONFIG_CBFS_PREFIX)/verstage
 $(CONFIG_CBFS_PREFIX)/verstage-file := $(objcbfs)/verstage.elf
 $(CONFIG_CBFS_PREFIX)/verstage-type := stage
+$(CONFIG_CBFS_PREFIX)/verstage-compression := $(CBFS_PRERAM_COMPRESS_FLAG)
 # Verstage on x86 expected to be xip.
 ifeq ($(CONFIG_ARCH_VERSTAGE_X86_32)$(CONFIG_ARCH_VERSTAGE_X86_64),y)
 $(CONFIG_CBFS_PREFIX)/verstage-options := -a 64 --xip -S ".car.data"