lib/compression/lzxpress.c

   1 /*
   2  * Copyright (C) Matthieu Suiche 2008
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the author nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  */
  34
  35 #include "replace.h"
  36 #include "lzxpress.h"
  37
  38
  39 #define __BUF_POS_CONST(buf,ofs)(((const uint8_t *)buf)+(ofs))
  40 #define __PULL_BYTE(buf,ofs) \
  41         ((uint8_t)((*__BUF_POS_CONST(buf,ofs)) & 0xFF))
  42
  43 #ifndef PULL_LE_UINT16
  44 #define PULL_LE_UINT16(buf,ofs) ((uint16_t)( \
  45         ((uint16_t)(((uint16_t)(__PULL_BYTE(buf,(ofs)+0))) << 0)) | \
  46         ((uint16_t)(((uint16_t)(__PULL_BYTE(buf,(ofs)+1))) << 8)) \
  47 ))
  48 #endif
  49
  50 #ifndef PULL_LE_UINT32
  51 #define PULL_LE_UINT32(buf,ofs) ((uint32_t)( \
  52         ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+0))) <<  0)) | \
  53         ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+1))) <<  8)) | \
  54         ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+2))) << 16)) | \
  55         ((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+3))) << 24)) \
  56 ))
  57 #endif
  58
  59 ssize_t lzxpress_compress(const uint8_t *uncompressed,
  60                           uint32_t uncompressed_size,
  61                           uint8_t *compressed,
  62                           uint32_t max_compressed_size)
  63 {
  64         uint32_t uncompressed_pos, compressed_pos, byte_left;
  65         uint32_t max_offset, best_offset;
  66         int32_t offset;
  67         uint32_t max_len, len, best_len;
  68         const uint8_t *str1, *str2;
  69         uint32_t indic;
  70         uint8_t *indic_pos;
  71         uint32_t indic_bit, nibble_index;
  72
  73         uint32_t metadata_size;
  74         uint16_t metadata;
  75         uint16_t *dest;
  76
  77         if (!uncompressed_size) {
  78                 return 0;
  79         }
  80
  81         uncompressed_pos = 0;
  82         indic = 0;
  83         compressed_pos = sizeof(uint32_t);
  84         indic_pos = &compressed[0];
  85
  86         byte_left = uncompressed_size;
  87         indic_bit = 0;
  88         nibble_index = 0;
  89
  90         if (uncompressed_pos > XPRESS_BLOCK_SIZE)
  91                 return 0;
  92
  93         do {
  94                 bool found = false;
  95
  96                 max_offset = uncompressed_pos;
  97
  98                 str1 = &uncompressed[uncompressed_pos];
  99
 100                 best_len = 2;
 101                 best_offset = 0;
 102
 103                 max_offset = MIN(0x1FFF, max_offset);
 104
 105                 /* search for the longest match in the window for the lookahead buffer */
 106                 for (offset = 1; (uint32_t)offset <= max_offset; offset++) {
 107                         str2 = &str1[-offset];
 108
 109                         /* maximum len we can encode into metadata */
 110                         max_len = MIN((255 + 15 + 7 + 3), byte_left);
 111
 112                         for (len = 0; (len < max_len) && (str1[len] == str2[len]); len++);
 113
 114                         /*
 115                          * We check if len is better than the value found before, including the
 116                          * sequence of identical bytes
 117                          */
 118                         if (len > best_len) {
 119                                 found = true;
 120                                 best_len = len;
 121                                 best_offset = offset;
 122                         }
 123                 }
 124
 125                 if (found) {
 126                         metadata_size = 0;
 127                         dest = (uint16_t *)&compressed[compressed_pos];
 128
 129                         if (best_len < 10) {
 130                                 /* Classical meta-data */
 131                                 metadata = (uint16_t)(((best_offset - 1) << 3) | (best_len - 3));
 132                                 dest[metadata_size / sizeof(uint16_t)] = metadata;
 133                                 metadata_size += sizeof(uint16_t);
 134                         } else {
 135                                 metadata = (uint16_t)(((best_offset - 1) << 3) | 7);
 136                                 dest[metadata_size / sizeof(uint16_t)] = metadata;
 137                                 metadata_size = sizeof(uint16_t);
 138
 139                                 if (best_len < (15 + 7 + 3)) {
 140                                         /* Shared byte */
 141                                         if (!nibble_index) {
 142                                                 compressed[compressed_pos + metadata_size] = (best_len - (3 + 7)) & 0xF;
 143                                                 metadata_size += sizeof(uint8_t);
 144                                         } else {
 145                                                 compressed[nibble_index] &= 0xF;
 146                                                 compressed[nibble_index] |= (best_len - (3 + 7)) * 16;
 147                                         }
 148                                 } else if (best_len < (3 + 7 + 15 + 255)) {
 149                                         /* Shared byte */
 150                                         if (!nibble_index) {
 151                                                 compressed[compressed_pos + metadata_size] = 15;
 152                                                 metadata_size += sizeof(uint8_t);
 153                                         } else {
 154                                                 compressed[nibble_index] &= 0xF;
 155                                                 compressed[nibble_index] |= (15 * 16);
 156                                         }
 157
 158                                         /* Additional best_len */
 159                                         compressed[compressed_pos + metadata_size] = (best_len - (3 + 7 + 15)) & 0xFF;
 160                                         metadata_size += sizeof(uint8_t);
 161                                 } else {
 162                                         /* Shared byte */
 163                                         if (!nibble_index) {
 164                                                 compressed[compressed_pos + metadata_size] |= 15;
 165                                                 metadata_size += sizeof(uint8_t);
 166                                         } else {
 167                                                 compressed[nibble_index] |= 15 << 4;
 168                                         }
 169
 170                                         /* Additional best_len */
 171                                         compressed[compressed_pos + metadata_size] = 255;
 172
 173                                         metadata_size += sizeof(uint8_t);
 174
 175                                         compressed[compressed_pos + metadata_size] = (best_len - 3) & 0xFF;
 176                                         compressed[compressed_pos + metadata_size + 1] = ((best_len - 3) >> 8) & 0xFF;
 177                                         metadata_size += sizeof(uint16_t);
 178                                 }
 179                         }
 180
 181                         indic |= 1 << (32 - ((indic_bit % 32) + 1));
 182
 183                         if (best_len > 9) {
 184                                 if (nibble_index == 0) {
 185                                         nibble_index = compressed_pos + sizeof(uint16_t);
 186                                 } else {
 187                                         nibble_index = 0;
 188                                 }
 189                         }
 190
 191                         compressed_pos += metadata_size;
 192                         uncompressed_pos += best_len;
 193                         byte_left -= best_len;
 194                 } else {
 195                         compressed[compressed_pos++] = uncompressed[uncompressed_pos++];
 196                         byte_left--;
 197                 }
 198                 indic_bit++;
 199
 200                 if ((indic_bit - 1) % 32 > (indic_bit % 32)) {
 201                         *(uint32_t *)indic_pos = indic;
 202                         indic = 0;
 203                         indic_pos = &compressed[compressed_pos];
 204                         compressed_pos += sizeof(uint32_t);
 205                 }
 206         } while (byte_left > 3);
 207
 208         do {
 209                 compressed[compressed_pos] = uncompressed[uncompressed_pos];
 210                 indic_bit++;
 211
 212                 uncompressed_pos++;
 213                 compressed_pos++;
 214                 if (((indic_bit - 1) % 32) > (indic_bit % 32)){
 215                         *(uint32_t *)indic_pos = indic;
 216                         indic = 0;
 217                         indic_pos = &compressed[compressed_pos];
 218                         compressed_pos += sizeof(uint32_t);
 219                 }
 220         } while (uncompressed_pos < uncompressed_size);
 221
 222         if ((indic_bit % 32) > 0) {
 223                 for (; (indic_bit % 32) != 0; indic_bit++)
 224                         indic |= 0 << (32 - ((indic_bit % 32) + 1));
 225
 226                 *(uint32_t *)indic_pos = indic;
 227                 compressed_pos += sizeof(uint32_t);
 228         }
 229
 230         return compressed_pos;
 231 }
 232
 233 ssize_t lzxpress_decompress(const uint8_t *input,
 234                             uint32_t input_size,
 235                             uint8_t *output,
 236                             uint32_t max_output_size)
 237 {
 238         uint32_t output_index, input_index;
 239         uint32_t indicator, indicator_bit;
 240         uint32_t length;
 241         uint32_t offset;
 242         uint32_t nibble_index;
 243
 244         output_index = 0;
 245         input_index = 0;
 246         indicator = 0;
 247         indicator_bit = 0;
 248         length = 0;
 249         offset = 0;
 250         nibble_index = 0;
 251
 252         do {
 253                 if (indicator_bit == 0) {
 254                         indicator = PULL_LE_UINT32(input, input_index);
 255                         input_index += sizeof(uint32_t);
 256                         indicator_bit = 32;
 257                 }
 258                 indicator_bit--;
 259
 260                 /*
 261                  * check whether the bit specified by indicator_bit is set or not
 262                  * set in indicator. For example, if indicator_bit has value 4
 263                  * check whether the 4th bit of the value in indicator is set
 264                  */
 265                 if (((indicator >> indicator_bit) & 1) == 0) {
 266                         output[output_index] = input[input_index];
 267                         input_index += sizeof(uint8_t);
 268                         output_index += sizeof(uint8_t);
 269                 } else {
 270                         length = PULL_LE_UINT16(input, input_index);
 271                         input_index += sizeof(uint16_t);
 272                         offset = length / 8;
 273                         length = length % 8;
 274
 275                         if (length == 7) {
 276                                 if (nibble_index == 0) {
 277                                         nibble_index = input_index;
 278                                         length = input[input_index] % 16;
 279                                         input_index += sizeof(uint8_t);
 280                                 } else {
 281                                         length = input[nibble_index] / 16;
 282                                         nibble_index = 0;
 283                                 }
 284
 285                                 if (length == 15) {
 286                                         length = input[input_index];
 287                                         input_index += sizeof(uint8_t);
 288                                         if (length == 255) {
 289                                                 length = PULL_LE_UINT16(input, input_index);
 290                                                 input_index += sizeof(uint16_t);
 291                                                 length -= (15 + 7);
 292                                         }
 293                                         length += 15;
 294                                 }
 295                                 length += 7;
 296                         }
 297
 298                         length += 3;
 299
 300                         do {
 301                                 if ((output_index >= max_output_size) || ((offset + 1) > output_index)) break;
 302
 303                                 output[output_index] = output[output_index - offset - 1];
 304
 305                                 output_index += sizeof(uint8_t);
 306                                 length -= sizeof(uint8_t);
 307                         } while (length != 0);
 308                 }
 309         } while ((output_index < max_output_size) && (input_index < (input_size)));
 310
 311         return output_index;
 312 }