diff options
Diffstat (limited to 'src/commonlib')
| -rw-r--r-- | src/commonlib/Makefile.inc | 5 | ||||
| -rw-r--r-- | src/commonlib/include/commonlib/cbfs_serialized.h | 1 | ||||
| -rw-r--r-- | src/commonlib/include/commonlib/compression.h | 34 | ||||
| -rw-r--r-- | src/commonlib/include/commonlib/timestamp_serialized.h | 2 | ||||
| -rw-r--r-- | src/commonlib/lz4.c.inc | 280 | ||||
| -rw-r--r-- | src/commonlib/lz4_wrapper.c | 193 |
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); +} |