module/zstd/lib/compress/zstd_compress_literals.c

   1 /*
   2  * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under both the BSD-style license (found in the
   6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
   7  * in the COPYING file in the root directory of this source tree).
   8  * You may select, at your option, one of the above-listed licenses.
   9  */
  10
  11  /*-*************************************
  12  *  Dependencies
  13  ***************************************/
  14 #include "zstd_compress_literals.h"
  15
  16 size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
  17 {
  18     BYTE* const ostart = (BYTE* const)dst;
  19     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);
  20
  21     RETURN_ERROR_IF(srcSize + flSize > dstCapacity, dstSize_tooSmall, "");
  22
  23     switch(flSize)
  24     {
  25         case 1: /* 2 - 1 - 5 */
  26             ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));
  27             break;
  28         case 2: /* 2 - 2 - 12 */
  29             MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));
  30             break;
  31         case 3: /* 2 - 2 - 20 */
  32             MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));
  33             break;
  34         default:   /* not necessary : flSize is {1,2,3} */
  35             assert(0);
  36     }
  37
  38     memcpy(ostart + flSize, src, srcSize);
  39     DEBUGLOG(5, "Raw literals: %u -> %u", (U32)srcSize, (U32)(srcSize + flSize));
  40     return srcSize + flSize;
  41 }
  42
  43 size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
  44 {
  45     BYTE* const ostart = (BYTE* const)dst;
  46     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);
  47
  48     (void)dstCapacity;  /* dstCapacity already guaranteed to be >=4, hence large enough */
  49
  50     switch(flSize)
  51     {
  52         case 1: /* 2 - 1 - 5 */
  53             ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));
  54             break;
  55         case 2: /* 2 - 2 - 12 */
  56             MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));
  57             break;
  58         case 3: /* 2 - 2 - 20 */
  59             MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));
  60             break;
  61         default:   /* not necessary : flSize is {1,2,3} */
  62             assert(0);
  63     }
  64
  65     ostart[flSize] = *(const BYTE*)src;
  66     DEBUGLOG(5, "RLE literals: %u -> %u", (U32)srcSize, (U32)flSize + 1);
  67     return flSize+1;
  68 }
  69
  70 size_t ZSTD_compressLiterals (ZSTD_hufCTables_t const* prevHuf,
  71                               ZSTD_hufCTables_t* nextHuf,
  72                               ZSTD_strategy strategy, int disableLiteralCompression,
  73                               void* dst, size_t dstCapacity,
  74                         const void* src, size_t srcSize,
  75                               void* entropyWorkspace, size_t entropyWorkspaceSize,
  76                         const int bmi2)
  77 {
  78     size_t const minGain = ZSTD_minGain(srcSize, strategy);
  79     size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
  80     BYTE*  const ostart = (BYTE*)dst;
  81     U32 singleStream = srcSize < 256;
  82     symbolEncodingType_e hType = set_compressed;
  83     size_t cLitSize;
  84
  85     DEBUGLOG(5,"ZSTD_compressLiterals (disableLiteralCompression=%i srcSize=%u)",
  86                 disableLiteralCompression, (U32)srcSize);
  87
  88     /* Prepare nextEntropy assuming reusing the existing table */
  89     memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
  90
  91     if (disableLiteralCompression)
  92         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
  93
  94     /* small ? don't even attempt compression (speed opt) */
  95 #   define COMPRESS_LITERALS_SIZE_MIN 63
  96     {   size_t const minLitSize = (prevHuf->repeatMode == HUF_repeat_valid) ? 6 : COMPRESS_LITERALS_SIZE_MIN;
  97         if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
  98     }
  99
 100     RETURN_ERROR_IF(dstCapacity < lhSize+1, dstSize_tooSmall, "not enough space for compression");
 101     {   HUF_repeat repeat = prevHuf->repeatMode;
 102         int const preferRepeat = strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
 103         if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;
 104         cLitSize = singleStream ?
 105             HUF_compress1X_repeat(
 106                 ostart+lhSize, dstCapacity-lhSize, src, srcSize,
 107                 HUF_SYMBOLVALUE_MAX, HUF_TABLELOG_DEFAULT, entropyWorkspace, entropyWorkspaceSize,
 108                 (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2) :
 109             HUF_compress4X_repeat(
 110                 ostart+lhSize, dstCapacity-lhSize, src, srcSize,
 111                 HUF_SYMBOLVALUE_MAX, HUF_TABLELOG_DEFAULT, entropyWorkspace, entropyWorkspaceSize,
 112                 (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2);
 113         if (repeat != HUF_repeat_none) {
 114             /* reused the existing table */
 115             DEBUGLOG(5, "Reusing previous huffman table");
 116             hType = set_repeat;
 117         }
 118     }
 119
 120     if ((cLitSize==0) | (cLitSize >= srcSize - minGain) | ERR_isError(cLitSize)) {
 121         memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
 122         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
 123     }
 124     if (cLitSize==1) {
 125         memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
 126         return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
 127     }
 128
 129     if (hType == set_compressed) {
 130         /* using a newly constructed table */
 131         nextHuf->repeatMode = HUF_repeat_check;
 132     }
 133
 134     /* Build header */
 135     switch(lhSize)
 136     {
 137     case 3: /* 2 - 2 - 10 - 10 */
 138         {   U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
 139             MEM_writeLE24(ostart, lhc);
 140             break;
 141         }
 142     case 4: /* 2 - 2 - 14 - 14 */
 143         {   U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
 144             MEM_writeLE32(ostart, lhc);
 145             break;
 146         }
 147     case 5: /* 2 - 2 - 18 - 18 */
 148         {   U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
 149             MEM_writeLE32(ostart, lhc);
 150             ostart[4] = (BYTE)(cLitSize >> 10);
 151             break;
 152         }
 153     default:  /* not possible : lhSize is {3,4,5} */
 154         assert(0);
 155     }
 156     DEBUGLOG(5, "Compressed literals: %u -> %u", (U32)srcSize, (U32)(lhSize+cLitSize));
 157     return lhSize+cLitSize;
 158 }