1 /*

     2  * Copyright (c) 2016-present, 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     return srcSize + flSize;

    40 }

    41 

    42 size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)

    43 {

    44     BYTE* const ostart = (BYTE* const)dst;

    45     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);

    46 

    47     (void)dstCapacity;  /* dstCapacity already guaranteed to be >=4, hence large enough */

    48 

    49     switch(flSize)

    50     {

    51         case 1: /* 2 - 1 - 5 */

    52             ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));

    53             break;

    54         case 2: /* 2 - 2 - 12 */

    55             MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));

    56             break;

    57         case 3: /* 2 - 2 - 20 */

    58             MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));

    59             break;

    60         default:   /* not necessary : flSize is {1,2,3} */

    61             assert(0);

    62     }

    63 

    64     ostart[flSize] = *(const BYTE*)src;

    65     return flSize+1;

    66 }

    67 

    68 size_t ZSTD_compressLiterals (ZSTD_hufCTables_t const* prevHuf,

    69                               ZSTD_hufCTables_t* nextHuf,

    70                               ZSTD_strategy strategy, int disableLiteralCompression,

    71                               void* dst, size_t dstCapacity,

    72                         const void* src, size_t srcSize,

    73                               void* workspace, size_t wkspSize,

    74                         const int bmi2)

    75 {

    76     size_t const minGain = ZSTD_minGain(srcSize, strategy);

    77     size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);

    78     BYTE*  const ostart = (BYTE*)dst;

    79     U32 singleStream = srcSize < 256;

    80     symbolEncodingType_e hType = set_compressed;

    81     size_t cLitSize;

    82 

    83     DEBUGLOG(5,"ZSTD_compressLiterals (disableLiteralCompression=%i)",

    84                 disableLiteralCompression);

    85 

    86     /* Prepare nextEntropy assuming reusing the existing table */

    87     memcpy(nextHuf, prevHuf, sizeof(*prevHuf));

    88 

    89     if (disableLiteralCompression)

    90         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);

    91 

    92     /* small ? don't even attempt compression (speed opt) */

    93 #   define COMPRESS_LITERALS_SIZE_MIN 63

    94     {   size_t const minLitSize = (prevHuf->repeatMode == HUF_repeat_valid) ? 6 : COMPRESS_LITERALS_SIZE_MIN;

    95         if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);

    96     }

    97 

    98     RETURN_ERROR_IF(dstCapacity < lhSize+1, dstSize_tooSmall, "not enough space for compression");

    99     {   HUF_repeat repeat = prevHuf->repeatMode;

   100         int const preferRepeat = strategy < ZSTD_lazy ? srcSize <= 1024 : 0;

   101         if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;

   102         cLitSize = singleStream ? HUF_compress1X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,

   103                                       workspace, wkspSize, (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2)

   104                                 : HUF_compress4X_repeat(ostart+lhSize, dstCapacity-lhSize, src, srcSize, 255, 11,

   105                                       workspace, wkspSize, (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2);

   106         if (repeat != HUF_repeat_none) {

   107             /* reused the existing table */

   108             hType = set_repeat;

   109         }

   110     }

   111 

   112     if ((cLitSize==0) | (cLitSize >= srcSize - minGain) | ERR_isError(cLitSize)) {

   113         memcpy(nextHuf, prevHuf, sizeof(*prevHuf));

   114         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);

   115     }

   116     if (cLitSize==1) {

   117         memcpy(nextHuf, prevHuf, sizeof(*prevHuf));

   118         return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);

   119     }

   120 

   121     if (hType == set_compressed) {

   122         /* using a newly constructed table */

   123         nextHuf->repeatMode = HUF_repeat_check;

   124     }

   125 

   126     /* Build header */

   127     switch(lhSize)

   128     {

   129     case 3: /* 2 - 2 - 10 - 10 */

   130         {   U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);

   131             MEM_writeLE24(ostart, lhc);

   132             break;

   133         }

   134     case 4: /* 2 - 2 - 14 - 14 */

   135         {   U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);

   136             MEM_writeLE32(ostart, lhc);

   137             break;

   138         }

   139     case 5: /* 2 - 2 - 18 - 18 */

   140         {   U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);

   141             MEM_writeLE32(ostart, lhc);

   142             ostart[4] = (BYTE)(cLitSize >> 10);

   143             break;

   144         }

   145     default:  /* not possible : lhSize is {3,4,5} */

   146         assert(0);

   147     }

   148     return lhSize+cLitSize;

   149 }