summaryrefslogtreecommitdiff
path: root/src/commonlib
diff options
context:
space:
mode:
Diffstat (limited to 'src/commonlib')
-rw-r--r--src/commonlib/Makefile.inc5
-rw-r--r--src/commonlib/include/commonlib/cbfs_serialized.h1
-rw-r--r--src/commonlib/include/commonlib/compression.h34
-rw-r--r--src/commonlib/include/commonlib/timestamp_serialized.h2
-rw-r--r--src/commonlib/lz4.c.inc280
-rw-r--r--src/commonlib/lz4_wrapper.c193
6 files changed, 515 insertions, 0 deletions
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);
+}