src/commonlib/lz4_wrapper.c

   1 /*
   2  * Copyright 2015-2016 Google Inc.
   3  *
   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 #include <compiler.h>
  38
  39 /* LZ4 comes with its own supposedly portable memory access functions, but they
  40  * seem to be very inefficient in practice (at least on ARM64). Since coreboot
  41  * knows about endinaness and allows some basic assumptions (such as unaligned
  42  * access support), we can easily write the ones we need ourselves. */
  43 static uint16_t LZ4_readLE16(const void *src)
  44 {
  45         return read_le16(src);
  46 }
  47 static void LZ4_copy8(void *dst, const void *src)
  48 {
  49 /* ARM32 needs to be a special snowflake to prevent GCC from coalescing the
  50  * access into LDRD/STRD (which don't support unaligned accesses). */
  51 #ifdef __arm__  /* ARMv < 6 doesn't support unaligned accesses at all. */
  52         #if defined(__COREBOOT_ARM_ARCH__) && __COREBOOT_ARM_ARCH__ < 6
  53                 int i;
  54                 for (i = 0; i < 8; i++)
  55                         ((uint8_t *)dst)[i] = ((uint8_t *)src)[i];
  56         #else
  57                 uint32_t x0, x1;
  58                 __asm__ ("ldr %[x0], [%[src]]"
  59                         : [x0]"=r"(x0)
  60                         : [src]"r"(src), "m"(*(const uint32_t *)src));
  61                 __asm__ ("ldr %[x1], [%[src], #4]"
  62                         : [x1]"=r"(x1)
  63                         : [src]"r"(src), "m"(*(const uint32_t *)(src + 4)));
  64                 __asm__ ("str %[x0], [%[dst]]"
  65                         : "=m"(*(uint32_t *)dst)
  66                         : [x0]"r"(x0), [dst]"r"(dst));
  67                 __asm__ ("str %[x1], [%[dst], #4]"
  68                         : "=m"(*(uint32_t *)(dst + 4))
  69                         : [x1]"r"(x1), [dst]"r"(dst));
  70         #endif
  71 #elif defined(__riscv)
  72         /* RISC-V implementations may trap on any unaligned access. */
  73         int i;
  74         for (i = 0; i < 8; i++)
  75                 ((uint8_t *)dst)[i] = ((uint8_t *)src)[i];
  76 #else
  77         *(uint64_t *)dst = *(const uint64_t *)src;
  78 #endif
  79 }
  80
  81 typedef  uint8_t BYTE;
  82 typedef uint16_t U16;
  83 typedef uint32_t U32;
  84 typedef  int32_t S32;
  85 typedef uint64_t U64;
  86
  87 #define FORCE_INLINE static inline __attribute__((always_inline))
  88 #define likely(expr) __builtin_expect((expr) != 0, 1)
  89 #define unlikely(expr) __builtin_expect((expr) != 0, 0)
  90
  91 /* Unaltered (just removed unrelated code) from github.com/Cyan4973/lz4/dev. */
  92 #include "lz4.c.inc"    /* #include for inlining, do not link! */
  93
  94 #define LZ4F_MAGICNUMBER 0x184D2204
  95
  96 struct lz4_frame_header {
  97         uint32_t magic;
  98         union {
  99                 uint8_t flags;
 100                 struct {
 101                         uint8_t reserved0               : 2;
 102                         uint8_t has_content_checksum    : 1;
 103                         uint8_t has_content_size        : 1;
 104                         uint8_t has_block_checksum      : 1;
 105                         uint8_t independent_blocks      : 1;
 106                         uint8_t version                 : 2;
 107                 };
 108         };
 109         union {
 110                 uint8_t block_descriptor;
 111                 struct {
 112                         uint8_t reserved1               : 4;
 113                         uint8_t max_block_size          : 3;
 114                         uint8_t reserved2               : 1;
 115                 };
 116         };
 117         /* + uint64_t content_size iff has_content_size is set */
 118         /* + uint8_t header_checksum */
 119 } __packed;
 120
 121 struct lz4_block_header {
 122         union {
 123                 uint32_t raw;
 124                 struct {
 125                         uint32_t size           : 31;
 126                         uint32_t not_compressed : 1;
 127                 };
 128         };
 129         /* + size bytes of data */
 130         /* + uint32_t block_checksum iff has_block_checksum is set */
 131 } __packed;
 132
 133 size_t ulz4fn(const void *src, size_t srcn, void *dst, size_t dstn)
 134 {
 135         const void *in = src;
 136         void *out = dst;
 137         size_t out_size = 0;
 138         int has_block_checksum;
 139
 140         { /* With in-place decompression the header may become invalid later. */
 141                 const struct lz4_frame_header *h = in;
 142
 143                 if (srcn < sizeof(*h) + sizeof(uint64_t) + sizeof(uint8_t))
 144                         return 0;       /* input overrun */
 145
 146                 /* We assume there's always only a single, standard frame. */
 147                 if (read_le32(&h->magic) != LZ4F_MAGICNUMBER || h->version != 1)
 148                         return 0;       /* unknown format */
 149                 if (h->reserved0 || h->reserved1 || h->reserved2)
 150                         return 0;       /* reserved must be zero */
 151                 if (!h->independent_blocks)
 152                         return 0;       /* we don't support block dependency */
 153                 has_block_checksum = h->has_block_checksum;
 154
 155                 in += sizeof(*h);
 156                 if (h->has_content_size)
 157                         in += sizeof(uint64_t);
 158                 in += sizeof(uint8_t);
 159         }
 160
 161         while (1) {
 162                 struct lz4_block_header b = { { .raw = read_le32(in) } };
 163                 in += sizeof(struct lz4_block_header);
 164
 165                 if ((size_t)(in - src) + b.size > srcn)
 166                         break;                  /* input overrun */
 167
 168                 if (!b.size) {
 169                         out_size = out - dst;
 170                         break;                  /* decompression successful */
 171                 }
 172
 173                 if (b.not_compressed) {
 174                         size_t size = MIN((uintptr_t)b.size, (uintptr_t)dst
 175                                 + dstn - (uintptr_t)out);
 176                         memcpy(out, in, size);
 177                         if (size < b.size)
 178                                 break;          /* output overrun */
 179                         out += size;
 180                 } else {
 181                         /* constant folding essential, do not touch params! */
 182                         int ret = LZ4_decompress_generic(in, out, b.size,
 183                                         dst + dstn - out, endOnInputSize,
 184                                         full, 0, noDict, out, NULL, 0);
 185                         if (ret < 0)
 186                                 break;          /* decompression error */
 187                         out += ret;
 188                 }
 189
 190                 in += b.size;
 191                 if (has_block_checksum)
 192                         in += sizeof(uint32_t);
 193         }
 194
 195         return out_size;
 196 }
 197
 198 size_t ulz4f(const void *src, void *dst)
 199 {
 200         /* LZ4 uses signed size parameters, so can't just use ((u32)-1) here. */
 201         return ulz4fn(src, 1*GiB, dst, 1*GiB);
 202 }