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>

1 files changed, 303 insertions, 0 deletions

diff --git a/util/cbfstool/lz4/lib/lz4frame.h b/util/cbfstool/lz4/lib/lz4frame.h
new file mode 100644
index 0000000000..c039e5d559
--- /dev/null
+++ b/util/cbfstool/lz4/lib/lz4frame.h
@@ -0,0 +1,303 @@
+/*
+   LZ4 auto-framing library
+   Header File
+   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
+*/
+
+/* LZ4F is a stand-alone API to create LZ4-compressed frames
+ * conformant with specification v1.5.1.
+ * All related operations, including memory management, are handled internally by the library.
+ * You don't need lz4.h when using lz4frame.h.
+ * */
+
+#pragma once
+
+#if defined (__cplusplus)
+extern "C" {
+#endif
+
+/**************************************
+*  Includes
+**************************************/
+#include <stddef.h>   /* size_t */
+
+
+/**************************************
+*  Error management
+**************************************/
+typedef size_t LZ4F_errorCode_t;
+
+unsigned    LZ4F_isError(LZ4F_errorCode_t code);
+const char* LZ4F_getErrorName(LZ4F_errorCode_t code);   /* return error code string; useful for debugging */
+
+
+/**************************************
+*  Frame compression types
+**************************************/
+//#define LZ4F_DISABLE_OBSOLETE_ENUMS
+#ifndef LZ4F_DISABLE_OBSOLETE_ENUMS
+#  define LZ4F_OBSOLETE_ENUM(x) ,x
+#else
+#  define LZ4F_OBSOLETE_ENUM(x)
+#endif
+
+typedef enum {
+    LZ4F_default=0,
+    LZ4F_max64KB=4,
+    LZ4F_max256KB=5,
+    LZ4F_max1MB=6,
+    LZ4F_max4MB=7
+    LZ4F_OBSOLETE_ENUM(max64KB = LZ4F_max64KB)
+    LZ4F_OBSOLETE_ENUM(max256KB = LZ4F_max256KB)
+    LZ4F_OBSOLETE_ENUM(max1MB = LZ4F_max1MB)
+    LZ4F_OBSOLETE_ENUM(max4MB = LZ4F_max4MB)
+} LZ4F_blockSizeID_t;
+
+typedef enum {
+    LZ4F_blockLinked=0,
+    LZ4F_blockIndependent
+    LZ4F_OBSOLETE_ENUM(blockLinked = LZ4F_blockLinked)
+    LZ4F_OBSOLETE_ENUM(blockIndependent = LZ4F_blockIndependent)
+} LZ4F_blockMode_t;
+
+typedef enum {
+    LZ4F_noContentChecksum=0,
+    LZ4F_contentChecksumEnabled
+    LZ4F_OBSOLETE_ENUM(noContentChecksum = LZ4F_noContentChecksum)
+    LZ4F_OBSOLETE_ENUM(contentChecksumEnabled = LZ4F_contentChecksumEnabled)
+} LZ4F_contentChecksum_t;
+
+typedef enum {
+    LZ4F_frame=0,
+    LZ4F_skippableFrame
+    LZ4F_OBSOLETE_ENUM(skippableFrame = LZ4F_skippableFrame)
+} LZ4F_frameType_t;
+
+#ifndef LZ4F_DISABLE_OBSOLETE_ENUMS
+typedef LZ4F_blockSizeID_t blockSizeID_t;
+typedef LZ4F_blockMode_t blockMode_t;
+typedef LZ4F_frameType_t frameType_t;
+typedef LZ4F_contentChecksum_t contentChecksum_t;
+#endif
+
+typedef struct {
+  LZ4F_blockSizeID_t     blockSizeID;           /* max64KB, max256KB, max1MB, max4MB ; 0 == default */
+  LZ4F_blockMode_t       blockMode;             /* blockLinked, blockIndependent ; 0 == default */
+  LZ4F_contentChecksum_t contentChecksumFlag;   /* noContentChecksum, contentChecksumEnabled ; 0 == default  */
+  LZ4F_frameType_t       frameType;             /* LZ4F_frame, skippableFrame ; 0 == default */
+  unsigned long long     contentSize;           /* Size of uncompressed (original) content ; 0 == unknown */
+  unsigned               reserved[2];           /* must be zero for forward compatibility */
+} LZ4F_frameInfo_t;
+
+typedef struct {
+  LZ4F_frameInfo_t frameInfo;
+  int      compressionLevel;       /* 0 == default (fast mode); values above 16 count as 16; values below 0 count as 0 */
+  unsigned autoFlush;              /* 1 == always flush (reduce need for tmp buffer) */
+  unsigned reserved[4];            /* must be zero for forward compatibility */
+} LZ4F_preferences_t;
+
+
+/***********************************
+*  Simple compression function
+***********************************/
+size_t LZ4F_compressFrameBound(size_t srcSize, const LZ4F_preferences_t* preferencesPtr);
+
+size_t LZ4F_compressFrame(void* dstBuffer, size_t dstMaxSize, const void* srcBuffer, size_t srcSize, const LZ4F_preferences_t* preferencesPtr);
+/* LZ4F_compressFrame()
+ * Compress an entire srcBuffer into a valid LZ4 frame, as defined by specification v1.5.1
+ * The most important rule is that dstBuffer MUST be large enough (dstMaxSize) to ensure compression completion even in worst case.
+ * You can get the minimum value of dstMaxSize by using LZ4F_compressFrameBound()
+ * If this condition is not respected, LZ4F_compressFrame() will fail (result is an errorCode)
+ * The LZ4F_preferences_t structure is optional : you can provide NULL as argument. All preferences will be set to default.
+ * The result of the function is the number of bytes written into dstBuffer.
+ * The function outputs an error code if it fails (can be tested using LZ4F_isError())
+ */
+
+
+
+/**********************************
+*  Advanced compression functions
+**********************************/
+typedef struct LZ4F_cctx_s* LZ4F_compressionContext_t;   /* must be aligned on 8-bytes */
+
+typedef struct {
+  unsigned stableSrc;    /* 1 == src content will remain available on future calls to LZ4F_compress(); avoid saving src content within tmp buffer as future dictionary */
+  unsigned reserved[3];
+} LZ4F_compressOptions_t;
+
+/* Resource Management */
+
+#define LZ4F_VERSION 100
+LZ4F_errorCode_t LZ4F_createCompressionContext(LZ4F_compressionContext_t* cctxPtr, unsigned version);
+LZ4F_errorCode_t LZ4F_freeCompressionContext(LZ4F_compressionContext_t cctx);
+/* LZ4F_createCompressionContext() :
+ * The first thing to do is to create a compressionContext object, which will be used in all compression operations.
+ * This is achieved using LZ4F_createCompressionContext(), which takes as argument a version and an LZ4F_preferences_t structure.
+ * The version provided MUST be LZ4F_VERSION. It is intended to track potential version differences between different binaries.
+ * The function will provide a pointer to a fully allocated LZ4F_compressionContext_t object.
+ * If the result LZ4F_errorCode_t is not zero, there was an error during context creation.
+ * Object can release its memory using LZ4F_freeCompressionContext();
+ */
+
+
+/* Compression */
+
+size_t LZ4F_compressBegin(LZ4F_compressionContext_t cctx, void* dstBuffer, size_t dstMaxSize, const LZ4F_preferences_t* prefsPtr);
+/* LZ4F_compressBegin() :
+ * will write the frame header into dstBuffer.
+ * dstBuffer must be large enough to accommodate a header (dstMaxSize). Maximum header size is 15 bytes.
+ * The LZ4F_preferences_t structure is optional : you can provide NULL as argument, all preferences will then be set to default.
+ * The result of the function is the number of bytes written into dstBuffer for the header
+ * or an error code (can be tested using LZ4F_isError())
+ */
+
+size_t LZ4F_compressBound(size_t srcSize, const LZ4F_preferences_t* prefsPtr);
+/* LZ4F_compressBound() :
+ * Provides the minimum size of Dst buffer given srcSize to handle worst case situations.
+ * Different preferences can produce different results.
+ * prefsPtr is optional : you can provide NULL as argument, all preferences will then be set to cover worst case.
+ * This function includes frame termination cost (4 bytes, or 8 if frame checksum is enabled)
+ */
+
+size_t LZ4F_compressUpdate(LZ4F_compressionContext_t cctx, void* dstBuffer, size_t dstMaxSize, const void* srcBuffer, size_t srcSize, const LZ4F_compressOptions_t* cOptPtr);
+/* LZ4F_compressUpdate()
+ * LZ4F_compressUpdate() can be called repetitively to compress as much data as necessary.
+ * The most important rule is that dstBuffer MUST be large enough (dstMaxSize) to ensure compression completion even in worst case.
+ * You can get the minimum value of dstMaxSize by using LZ4F_compressBound().
+ * If this condition is not respected, LZ4F_compress() will fail (result is an errorCode).
+ * LZ4F_compressUpdate() doesn't guarantee error recovery, so you have to reset compression context when an error occurs.
+ * The LZ4F_compressOptions_t structure is optional : you can provide NULL as argument.
+ * The result of the function is the number of bytes written into dstBuffer : it can be zero, meaning input data was just buffered.
+ * The function outputs an error code if it fails (can be tested using LZ4F_isError())
+ */
+
+size_t LZ4F_flush(LZ4F_compressionContext_t cctx, void* dstBuffer, size_t dstMaxSize, const LZ4F_compressOptions_t* cOptPtr);
+/* LZ4F_flush()
+ * Should you need to generate compressed data immediately, without waiting for the current block to be filled,
+ * you can call LZ4_flush(), which will immediately compress any remaining data buffered within cctx.
+ * Note that dstMaxSize must be large enough to ensure the operation will be successful.
+ * LZ4F_compressOptions_t structure is optional : you can provide NULL as argument.
+ * The result of the function is the number of bytes written into dstBuffer
+ * (it can be zero, this means there was no data left within cctx)
+ * The function outputs an error code if it fails (can be tested using LZ4F_isError())
+ */
+
+size_t LZ4F_compressEnd(LZ4F_compressionContext_t cctx, void* dstBuffer, size_t dstMaxSize, const LZ4F_compressOptions_t* cOptPtr);
+/* LZ4F_compressEnd()
+ * When you want to properly finish the compressed frame, just call LZ4F_compressEnd().
+ * It will flush whatever data remained within compressionContext (like LZ4_flush())
+ * but also properly finalize the frame, with an endMark and a checksum.
+ * The result of the function is the number of bytes written into dstBuffer (necessarily >= 4 (endMark), or 8 if optional frame checksum is enabled)
+ * The function outputs an error code if it fails (can be tested using LZ4F_isError())
+ * The LZ4F_compressOptions_t structure is optional : you can provide NULL as argument.
+ * A successful call to LZ4F_compressEnd() makes cctx available again for next compression task.
+ */
+
+
+/***********************************
+*  Decompression functions
+***********************************/
+
+typedef struct LZ4F_dctx_s* LZ4F_decompressionContext_t;   /* must be aligned on 8-bytes */
+
+typedef struct {
+  unsigned stableDst;       /* guarantee that decompressed data will still be there on next function calls (avoid storage into tmp buffers) */
+  unsigned reserved[3];
+} LZ4F_decompressOptions_t;
+
+
+/* Resource management */
+
+LZ4F_errorCode_t LZ4F_createDecompressionContext(LZ4F_decompressionContext_t* dctxPtr, unsigned version);
+LZ4F_errorCode_t LZ4F_freeDecompressionContext(LZ4F_decompressionContext_t dctx);
+/* LZ4F_createDecompressionContext() :
+ * The first thing to do is to create an LZ4F_decompressionContext_t object, which will be used in all decompression operations.
+ * This is achieved using LZ4F_createDecompressionContext().
+ * The version provided MUST be LZ4F_VERSION. It is intended to track potential breaking differences between different versions.
+ * The function will provide a pointer to a fully allocated and initialized LZ4F_decompressionContext_t object.
+ * The result is an errorCode, which can be tested using LZ4F_isError().
+ * dctx memory can be released using LZ4F_freeDecompressionContext();
+ * The result of LZ4F_freeDecompressionContext() is indicative of the current state of decompressionContext when being released.
+ * That is, it should be == 0 if decompression has been completed fully and correctly.
+ */
+
+
+/* Decompression */
+
+size_t LZ4F_getFrameInfo(LZ4F_decompressionContext_t dctx,
+                         LZ4F_frameInfo_t* frameInfoPtr,
+                         const void* srcBuffer, size_t* srcSizePtr);
+/* LZ4F_getFrameInfo()
+ * This function decodes frame header information (such as max blockSize, frame checksum, etc.).
+ * Its usage is optional. The objective is to extract frame header information, typically for allocation purposes.
+ * A header size is variable and can be from 7 to 15 bytes. It's also possible to input more bytes than that.
+ * The number of bytes read from srcBuffer will be updated within *srcSizePtr (necessarily <= original value).
+ * (note that LZ4F_getFrameInfo() can also be used anytime *after* starting decompression, in this case 0 input byte is enough)
+ * Frame header info is *copied into* an already allocated LZ4F_frameInfo_t structure.
+ * The function result is an hint about how many srcSize bytes LZ4F_decompress() expects for next call,
+ *                        or an error code which can be tested using LZ4F_isError()
+ *                        (typically, when there is not enough src bytes to fully decode the frame header)
+ * Decompression is expected to resume from where it stopped (srcBuffer + *srcSizePtr)
+ */
+
+size_t LZ4F_decompress(LZ4F_decompressionContext_t dctx,
+                       void* dstBuffer, size_t* dstSizePtr,
+                       const void* srcBuffer, size_t* srcSizePtr,
+                       const LZ4F_decompressOptions_t* dOptPtr);
+/* LZ4F_decompress()
+ * Call this function repetitively to regenerate data compressed within srcBuffer.
+ * The function will attempt to decode *srcSizePtr bytes from srcBuffer, into dstBuffer of maximum size *dstSizePtr.
+ *
+ * The number of bytes regenerated into dstBuffer will be provided within *dstSizePtr (necessarily <= original value).
+ *
+ * The number of bytes read from srcBuffer will be provided within *srcSizePtr (necessarily <= original value).
+ * If number of bytes read is < number of bytes provided, then decompression operation is not completed.
+ * It typically happens when dstBuffer is not large enough to contain all decoded data.
+ * LZ4F_decompress() must be called again, starting from where it stopped (srcBuffer + *srcSizePtr)
+ * The function will check this condition, and refuse to continue if it is not respected.
+ *
+ * dstBuffer is supposed to be flushed between each call to the function, since its content will be overwritten.
+ * dst arguments can be changed at will with each consecutive call to the function.
+ *
+ * The function result is an hint of how many srcSize bytes LZ4F_decompress() expects for next call.
+ * Schematically, it's the size of the current (or remaining) compressed block + header of next block.
+ * Respecting the hint provides some boost to performance, since it does skip intermediate buffers.
+ * This is just a hint, you can always provide any srcSize you want.
+ * When a frame is fully decoded, the function result will be 0 (no more data expected).
+ * If decompression failed, function result is an error code, which can be tested using LZ4F_isError().
+ *
+ * After a frame is fully decoded, dctx can be used again to decompress another frame.
+ */
+
+
+#if defined (__cplusplus)
+}
+#endif