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, 185 insertions, 0 deletions

diff --git a/util/cbfstool/lz4/NEWS b/util/cbfstool/lz4/NEWS
new file mode 100644
index 0000000000..a1baead891
--- /dev/null
+++ b/util/cbfstool/lz4/NEWS
@@ -0,0 +1,185 @@
+r132
+Improved: Small decompression speed boost (+4%)
+Improved: Performance on ARMv6 and ARMv7
+Added : Debianization, by Evgeniy Polyakov
+Makefile: Safely protects lz4 version when selecting custom CFLAGS
+Makefile: Generates intermediate object files (*.o) for faster compilation on low power systems
+
+r131
+New    : Dos/DJGPP target, thanks to Louis Santillan (#114)
+Added  : Example using lz4frame library, by Zbigniew Jędrzejewski-Szmek (#118)
+Changed: xxhash symbols are modified (namespace emulation) within liblz4
+
+r130:
+Fixed  : incompatibility sparse mode vs console, reported by Yongwoon Cho (#105)
+Fixed  : LZ4IO exits too early when frame crc not present, reported by Yongwoon Cho (#106)
+Fixed  : incompatibility sparse mode vs append mode, reported by Takayuki Matsuoka (#110)
+Performance fix : big compression speed boost for clang (+30%)
+New    : cross-version test, by Takayuki Matsuoka
+
+r129:
+Added  : LZ4_compress_fast(), LZ4_compress_fast_continue()
+Added  : LZ4_compress_destSize()
+Changed: New lz4 and lz4hc compression API. Previous function prototypes still supported.
+Changed: Sparse file support enabled by default
+New    : LZ4 CLI improved performance compressing/decompressing multiple files (#86, kind contribution from Kyle J. Harper & Takayuki Matsuoka)
+Fixed  : GCC 4.9+ optimization bug - Reported by Markus Trippelsdorf, Greg Slazinski & Evan Nemerson
+Changed: Enums converted to LZ4F_ namespace convention - by Takayuki Matsuoka
+Added  : AppVeyor CI environment, for Visual tests - Suggested by Takayuki Matsuoka
+Modified:Obsolete functions generate warnings - Suggested by Evan Nemerson, contributed by Takayuki Matsuoka
+Fixed  : Bug #75 (unfinished stream), reported by Yongwoon Cho
+Updated: Documentation converted to MarkDown format
+
+r128:
+New    : lz4cli sparse file support (Requested by Neil Wilson, and contributed by Takayuki Matsuoka)
+New    : command -m, to compress multiple files in a single command (suggested by Kyle J. Harper)
+Fixed  : Restored lz4hc compression ratio (slightly lower since r124)
+New    : lz4 cli supports long commands (suggested by Takayuki Matsuoka)
+New    : lz4frame & lz4cli frame content size support
+New    : lz4frame supports skippable frames, as requested by Sergey Cherepanov
+Changed: Default "make install" directory is /usr/local, as notified by Ron Johnson
+New    : lz4 cli supports "pass-through" mode, requested by Neil Wilson
+New    : datagen can generate sparse files
+New    : scan-build tests, thanks to kind help by Takayuki Matsuoka
+New    : g++ compatibility tests
+New    : arm cross-compilation test, thanks to kind help by Takayuki Matsuoka
+Fixed  : Fuzzer + frametest compatibility with NetBSD (issue #48, reported by Thomas Klausner)
+Added  : Visual project directory
+Updated: Man page & Specification
+
+r127:
+N/A   : added a file on SVN
+
+r126:
+New   : lz4frame API is now integrated into liblz4
+Fixed : GCC 4.9 bug on highest performance settings, reported by Greg Slazinski
+Fixed : bug within LZ4 HC streaming mode, reported by James Boyle
+Fixed : older compiler don't like nameless unions, reported by Cheyi Lin
+Changed : lz4 is C90 compatible
+Changed : added -pedantic option, fixed a few mminor warnings
+
+r125:
+Changed : endian and alignment code
+Changed : directory structure : new "lib" directory
+Updated : lz4io, now uses lz4frame
+Improved: slightly improved decoding speed
+Fixed : LZ4_compress_limitedOutput(); Special thanks to Christopher Speller !
+Fixed : some alignment warnings under clang
+Fixed : deprecated function LZ4_slideInputBufferHC()
+
+r124:
+New : LZ4 HC streaming mode
+Fixed : LZ4F_compressBound() using null preferencesPtr
+Updated : xxHash to r38
+Updated library number, to 1.4.0
+
+r123:
+Added : experimental lz4frame API, thanks to Takayuki Matsuoka and Christopher Jackson for testings
+Fix : s390x support, thanks to Nobuhiro Iwamatsu
+Fix : test mode (-t) no longer requires confirmation, thanks to Thary Nguyen
+
+r122:
+Fix : AIX & AIX64 support (SamG)
+Fix : mips 64-bits support (lew van)
+Added : Examples directory, using code examples from Takayuki Matsuoka
+Updated : Framing specification, to v1.4.1
+Updated : xxHash, to r36
+
+r121:
+Added : Makefile : install for kFreeBSD and Hurd (Nobuhiro Iwamatsu)
+Fix : Makefile : install for OS-X and BSD, thanks to Takayuki Matsuoka
+
+r120:
+Modified : Streaming API, using strong types
+Added : LZ4_versionNumber(), thanks to Takayuki Matsuoka
+Fix : OS-X : library install name, thanks to Clemens Lang
+Updated : Makefile : synchronize library version number with lz4.h, thanks to Takayuki Matsuoka
+Updated : Makefile : stricter compilation flags
+Added : pkg-config, thanks to Zbigniew Jędrzejewski-Szmek (issue 135)
+Makefile : lz4-test only test native binaries, as suggested by Michał Górny (issue 136)
+Updated : xxHash to r35
+
+r119:
+Fix : Issue 134 : extended malicious address space overflow in 32-bits mode for some specific configurations
+
+r118:
+New : LZ4 Streaming API (Fast version), special thanks to Takayuki Matsuoka
+New : datagen : parametrable synthetic data generator for tests
+Improved : fuzzer, support more test cases, more parameters, ability to jump to specific test
+fix : support ppc64le platform (issue 131)
+fix : Issue 52 (malicious address space overflow in 32-bits mode when using large custom format)
+fix : Makefile : minor issue 130 : header files permissions
+
+r117:
+Added : man pages for lz4c and lz4cat
+Added : automated tests on Travis, thanks to Takayuki Matsuoka !
+fix : block-dependency command line (issue 127)
+fix : lz4fullbench (issue 128)
+
+r116:
+hotfix (issue 124 & 125)
+
+r115:
+Added : lz4cat utility, installed on POSX systems (issue 118)
+OS-X compatible compilation of dynamic library (issue 115)
+
+r114:
+Makefile : library correctly compiled with -O3 switch (issue 114)
+Makefile : library compilation compatible with clang
+Makefile : library is versioned and linked (issue 119)
+lz4.h : no more static inline prototypes (issue 116)
+man : improved header/footer (issue 111)
+Makefile : Use system default $(CC) & $(MAKE) variables (issue 112)
+xxhash : updated to r34
+
+r113:
+Large decompression speed improvement for GCC 32-bits. Thanks to Valery Croizier !
+LZ4HC : Compression Level is now a programmable parameter (CLI from 4 to 9)
+Separated IO routines from command line (lz4io.c)
+Version number into lz4.h (suggested by Francesc Alted)
+
+r112:
+quickfix
+
+r111 :
+Makefile : added capability to install libraries
+Modified Directory tree, to better separate libraries from programs.
+
+r110 :
+lz4 & lz4hc : added capability to allocate state & stream state with custom allocator (issue 99)
+fuzzer & fullbench : updated to test new functions
+man : documented -l command (Legacy format, for Linux kernel compression) (issue 102)
+cmake : improved version by Mika Attila, building programs and libraries (issue 100)
+xxHash : updated to r33
+Makefile : clean also delete local package .tar.gz
+
+r109 :
+lz4.c : corrected issue 98 (LZ4_compress_limitedOutput())
+Makefile : can specify version number from makefile
+
+r108 :
+lz4.c : corrected compression efficiency issue 97 in 64-bits chained mode (-BD) for streams > 4 GB (thanks Roman Strashkin for reporting)
+
+r107 :
+Makefile : support DESTDIR for staged installs. Thanks Jorge Aparicio.
+Makefile : make install installs both lz4 and lz4c (Jorge Aparicio)
+Makefile : removed -Wno-implicit-declaration compilation switch
+lz4cli.c : include <stduni.h> for isatty() (Luca Barbato)
+lz4.h : introduced LZ4_MAX_INPUT_SIZE constant (Shay Green)
+lz4.h : LZ4_compressBound() : unified macro and inline definitions (Shay Green)
+lz4.h : LZ4_decompressSafe_partial() : clarify comments (Shay Green)
+lz4.c : LZ4_compress() verify input size condition (Shay Green)
+bench.c : corrected a bug in free memory size evaluation
+cmake : install into bin/ directory (Richard Yao)
+cmake : check for just C compiler (Elan Ruusamae)
+
+r106 :
+Makefile : make dist modify text files in the package to respect Unix EoL convention
+lz4cli.c : corrected small display bug in HC mode
+
+r105 :
+Makefile : New install script and man page, contributed by Prasad Pandit
+lz4cli.c : Minor modifications, for easier extensibility
+COPYING  : added license file
+LZ4_Streaming_Format.odt : modified file name to remove white space characters
+Makefile : .exe suffix now properly added only for Windows target