contrib/long_distance_matching/ldm_common.c

   1 #include <stdio.h>
   2
   3 #include "ldm.h"
   4
   5 /**
   6  * This function reads the header at the beginning of src and writes
   7  * the compressed and decompressed size to compressedSize and
   8  * decompressedSize.
   9  *
  10  * The header consists of 16 bytes: 8 bytes each in little-endian format
  11  * of the compressed size and the decompressed size.
  12  */
  13 void LDM_readHeader(const void *src, U64 *compressedSize,
  14                     U64 *decompressedSize) {
  15   const BYTE *ip = (const BYTE *)src;
  16   *compressedSize = MEM_readLE64(ip);
  17   *decompressedSize = MEM_readLE64(ip + 8);
  18 }
  19
  20 /**
  21  * Writes the 16-byte header (8-bytes each of the compressedSize and
  22  * decompressedSize in little-endian format) to memPtr.
  23  */
  24 void LDM_writeHeader(void *memPtr, U64 compressedSize,
  25                      U64 decompressedSize) {
  26   MEM_writeLE64(memPtr, compressedSize);
  27   MEM_writeLE64((BYTE *)memPtr + 8, decompressedSize);
  28 }
  29
  30 struct LDM_DCtx {
  31   size_t compressedSize;
  32   size_t maxDecompressedSize;
  33
  34   const BYTE *ibase;   /* Base of input */
  35   const BYTE *ip;      /* Current input position */
  36   const BYTE *iend;    /* End of source */
  37
  38   const BYTE *obase;   /* Base of output */
  39   BYTE *op;            /* Current output position */
  40   const BYTE *oend;    /* End of output */
  41 };
  42
  43 void LDM_initializeDCtx(LDM_DCtx *dctx,
  44                         const void *src, size_t compressedSize,
  45                         void *dst, size_t maxDecompressedSize) {
  46   dctx->compressedSize = compressedSize;
  47   dctx->maxDecompressedSize = maxDecompressedSize;
  48
  49   dctx->ibase = src;
  50   dctx->ip = (const BYTE *)src;
  51   dctx->iend = dctx->ip + dctx->compressedSize;
  52   dctx->op = dst;
  53   dctx->oend = dctx->op + dctx->maxDecompressedSize;
  54 }
  55
  56 size_t LDM_decompress(const void *src, size_t compressedSize,
  57                       void *dst, size_t maxDecompressedSize) {
  58
  59   LDM_DCtx dctx;
  60   LDM_initializeDCtx(&dctx, src, compressedSize, dst, maxDecompressedSize);
  61
  62   while (dctx.ip < dctx.iend) {
  63     BYTE *cpy;
  64     const BYTE *match;
  65     size_t length, offset;
  66
  67     /* Get the literal length. */
  68     const unsigned token = *(dctx.ip)++;
  69     if ((length = (token >> ML_BITS)) == RUN_MASK) {
  70       unsigned s;
  71       do {
  72         s = *(dctx.ip)++;
  73         length += s;
  74       } while (s == 255);
  75     }
  76
  77     /* Copy the literals. */
  78     cpy = dctx.op + length;
  79     memcpy(dctx.op, dctx.ip, length);
  80     dctx.ip += length;
  81     dctx.op = cpy;
  82
  83     //TODO: dynamic offset size?
  84     /* Encode the offset. */
  85     offset = MEM_read32(dctx.ip);
  86     dctx.ip += LDM_OFFSET_SIZE;
  87     match = dctx.op - offset;
  88
  89     /* Get the match length. */
  90     length = token & ML_MASK;
  91     if (length == ML_MASK) {
  92       unsigned s;
  93       do {
  94         s = *(dctx.ip)++;
  95         length += s;
  96       } while (s == 255);
  97     }
  98     length += LDM_MIN_MATCH_LENGTH;
  99
 100     /* Copy match. */
 101     cpy = dctx.op + length;
 102
 103     // TODO: this can be made more efficient.
 104     while (match < cpy - offset && dctx.op < dctx.oend) {
 105       *(dctx.op)++ = *match++;
 106     }
 107   }
 108   return dctx.op - (BYTE *)dst;
 109 }