blob: 474df642c224a3c2d572222f8aec5e1cc3a304e5 [file] [log] [blame]
Julius Werner09f29212015-09-29 13:51:35 -07001/*
Benjamin Barenblat82ef8ad2016-06-17 09:49:24 -07002 * Copyright 2015-2016 Google Inc.
Julius Werner09f29212015-09-29 13:51:35 -07003 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. The name of the author may not be used to endorse or promote products
13 * derived from this software without specific prior written permission.
14 *
15 * Alternatively, this software may be distributed under the terms of the
16 * GNU General Public License ("GPL") version 2 as published by the Free
17 * Software Foundation.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31
32#include <commonlib/compression.h>
33#include <commonlib/endian.h>
34#include <commonlib/helpers.h>
35#include <stdint.h>
36#include <string.h>
37
38/* LZ4 comes with its own supposedly portable memory access functions, but they
39 * seem to be very inefficient in practice (at least on ARM64). Since coreboot
40 * knows about endinaness and allows some basic assumptions (such as unaligned
41 * access support), we can easily write the ones we need ourselves. */
42static uint16_t LZ4_readLE16(const void *src)
43{
44 return read_le16(src);
45}
46static void LZ4_copy8(void *dst, const void *src)
47{
48/* ARM32 needs to be a special snowflake to prevent GCC from coalescing the
49 * access into LDRD/STRD (which don't support unaligned accesses). */
50#ifdef __arm__ /* ARMv < 6 doesn't support unaligned accesses at all. */
51 #if defined(__COREBOOT_ARM_ARCH__) && __COREBOOT_ARM_ARCH__ < 6
52 int i;
53 for (i = 0; i < 8; i++)
54 ((uint8_t *)dst)[i] = ((uint8_t *)src)[i];
55 #else
56 uint32_t x0, x1;
Benjamin Barenblat82ef8ad2016-06-17 09:49:24 -070057 __asm__ ("ldr %[x0], [%[src]]"
58 : [x0]"=r"(x0)
59 : [src]"r"(src), "m"(*(const uint32_t *)src));
60 __asm__ ("ldr %[x1], [%[src], #4]"
61 : [x1]"=r"(x1)
62 : [src]"r"(src), "m"(*(const uint32_t *)(src + 4)));
63 __asm__ ("str %[x0], [%[dst]]"
64 : "=m"(*(uint32_t *)dst)
65 : [x0]"r"(x0), [dst]"r"(dst));
66 __asm__ ("str %[x1], [%[dst], #4]"
67 : "=m"(*(uint32_t *)(dst + 4))
68 : [x1]"r"(x1), [dst]"r"(dst));
Julius Werner09f29212015-09-29 13:51:35 -070069 #endif
wxjstz05782382017-06-09 17:10:32 +080070#elif defined(__riscv)
Jonathan Neuschäfer4acb0e72016-05-27 09:05:02 +020071 /* RISC-V implementations may trap on any unaligned access. */
72 int i;
73 for (i = 0; i < 8; i++)
74 ((uint8_t *)dst)[i] = ((uint8_t *)src)[i];
Julius Werner09f29212015-09-29 13:51:35 -070075#else
76 *(uint64_t *)dst = *(const uint64_t *)src;
77#endif
78}
79
80typedef uint8_t BYTE;
81typedef uint16_t U16;
82typedef uint32_t U32;
83typedef int32_t S32;
84typedef uint64_t U64;
85
Aaron Durbin75a62e72018-09-13 02:10:45 -060086#define FORCE_INLINE static __always_inline
Julius Werner09f29212015-09-29 13:51:35 -070087#define likely(expr) __builtin_expect((expr) != 0, 1)
88#define unlikely(expr) __builtin_expect((expr) != 0, 0)
89
90/* Unaltered (just removed unrelated code) from github.com/Cyan4973/lz4/dev. */
91#include "lz4.c.inc" /* #include for inlining, do not link! */
92
93#define LZ4F_MAGICNUMBER 0x184D2204
94
95struct lz4_frame_header {
96 uint32_t magic;
97 union {
98 uint8_t flags;
99 struct {
100 uint8_t reserved0 : 2;
101 uint8_t has_content_checksum : 1;
102 uint8_t has_content_size : 1;
103 uint8_t has_block_checksum : 1;
104 uint8_t independent_blocks : 1;
105 uint8_t version : 2;
106 };
107 };
108 union {
109 uint8_t block_descriptor;
110 struct {
111 uint8_t reserved1 : 4;
112 uint8_t max_block_size : 3;
113 uint8_t reserved2 : 1;
114 };
115 };
116 /* + uint64_t content_size iff has_content_size is set */
117 /* + uint8_t header_checksum */
Stefan Reinauer6a001132017-07-13 02:20:27 +0200118} __packed;
Julius Werner09f29212015-09-29 13:51:35 -0700119
120struct lz4_block_header {
121 union {
122 uint32_t raw;
123 struct {
124 uint32_t size : 31;
125 uint32_t not_compressed : 1;
126 };
127 };
128 /* + size bytes of data */
129 /* + uint32_t block_checksum iff has_block_checksum is set */
Stefan Reinauer6a001132017-07-13 02:20:27 +0200130} __packed;
Julius Werner09f29212015-09-29 13:51:35 -0700131
132size_t ulz4fn(const void *src, size_t srcn, void *dst, size_t dstn)
133{
134 const void *in = src;
135 void *out = dst;
136 size_t out_size = 0;
137 int has_block_checksum;
138
139 { /* With in-place decompression the header may become invalid later. */
140 const struct lz4_frame_header *h = in;
141
142 if (srcn < sizeof(*h) + sizeof(uint64_t) + sizeof(uint8_t))
143 return 0; /* input overrun */
144
145 /* We assume there's always only a single, standard frame. */
146 if (read_le32(&h->magic) != LZ4F_MAGICNUMBER || h->version != 1)
147 return 0; /* unknown format */
148 if (h->reserved0 || h->reserved1 || h->reserved2)
149 return 0; /* reserved must be zero */
150 if (!h->independent_blocks)
151 return 0; /* we don't support block dependency */
152 has_block_checksum = h->has_block_checksum;
153
154 in += sizeof(*h);
155 if (h->has_content_size)
156 in += sizeof(uint64_t);
157 in += sizeof(uint8_t);
158 }
159
160 while (1) {
Werner Zeh116485a2016-02-24 08:50:37 +0100161 struct lz4_block_header b = { { .raw = read_le32(in) } };
Julius Werner09f29212015-09-29 13:51:35 -0700162 in += sizeof(struct lz4_block_header);
163
164 if ((size_t)(in - src) + b.size > srcn)
165 break; /* input overrun */
166
167 if (!b.size) {
168 out_size = out - dst;
169 break; /* decompression successful */
170 }
171
172 if (b.not_compressed) {
Lee Leahy49fd42d2017-03-10 10:57:00 -0800173 size_t size = MIN((uintptr_t)b.size, (uintptr_t)dst
174 + dstn - (uintptr_t)out);
Julius Werner09f29212015-09-29 13:51:35 -0700175 memcpy(out, in, size);
176 if (size < b.size)
177 break; /* output overrun */
Lee Leahy72c60a42017-03-10 10:53:36 -0800178 out += size;
Julius Werner09f29212015-09-29 13:51:35 -0700179 } else {
180 /* constant folding essential, do not touch params! */
181 int ret = LZ4_decompress_generic(in, out, b.size,
182 dst + dstn - out, endOnInputSize,
183 full, 0, noDict, out, NULL, 0);
184 if (ret < 0)
185 break; /* decompression error */
Lee Leahy72c60a42017-03-10 10:53:36 -0800186 out += ret;
Julius Werner09f29212015-09-29 13:51:35 -0700187 }
188
189 in += b.size;
190 if (has_block_checksum)
191 in += sizeof(uint32_t);
192 }
193
194 return out_size;
195}
196
197size_t ulz4f(const void *src, void *dst)
198{
199 /* LZ4 uses signed size parameters, so can't just use ((u32)-1) here. */
200 return ulz4fn(src, 1*GiB, dst, 1*GiB);
201}