zstd/compress/zstd_compress_literals.c

0001 /*
0002  * Copyright (c) Yann Collet, Facebook, Inc.
0003  * All rights reserved.
0004  *
0005  * This source code is licensed under both the BSD-style license (found in the
0006  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
0007  * in the COPYING file in the root directory of this source tree).
0008  * You may select, at your option, one of the above-listed licenses.
0009  */
0010
0011  /*-*************************************
0012  *  Dependencies
0013  ***************************************/
0014 #include "zstd_compress_literals.h"
0015
0016 size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
0017 {
0018     BYTE* const ostart = (BYTE*)dst;
0019     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);
0020
0021     RETURN_ERROR_IF(srcSize + flSize > dstCapacity, dstSize_tooSmall, "");
0022
0023     switch(flSize)
0024     {
0025         case 1: /* 2 - 1 - 5 */
0026             ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));
0027             break;
0028         case 2: /* 2 - 2 - 12 */
0029             MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));
0030             break;
0031         case 3: /* 2 - 2 - 20 */
0032             MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));
0033             break;
0034         default:   /* not necessary : flSize is {1,2,3} */
0035             assert(0);
0036     }
0037
0038     ZSTD_memcpy(ostart + flSize, src, srcSize);
0039     DEBUGLOG(5, "Raw literals: %u -> %u", (U32)srcSize, (U32)(srcSize + flSize));
0040     return srcSize + flSize;
0041 }
0042
0043 size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
0044 {
0045     BYTE* const ostart = (BYTE*)dst;
0046     U32   const flSize = 1 + (srcSize>31) + (srcSize>4095);
0047
0048     (void)dstCapacity;  /* dstCapacity already guaranteed to be >=4, hence large enough */
0049
0050     switch(flSize)
0051     {
0052         case 1: /* 2 - 1 - 5 */
0053             ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));
0054             break;
0055         case 2: /* 2 - 2 - 12 */
0056             MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));
0057             break;
0058         case 3: /* 2 - 2 - 20 */
0059             MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));
0060             break;
0061         default:   /* not necessary : flSize is {1,2,3} */
0062             assert(0);
0063     }
0064
0065     ostart[flSize] = *(const BYTE*)src;
0066     DEBUGLOG(5, "RLE literals: %u -> %u", (U32)srcSize, (U32)flSize + 1);
0067     return flSize+1;
0068 }
0069
0070 size_t ZSTD_compressLiterals (ZSTD_hufCTables_t const* prevHuf,
0071                               ZSTD_hufCTables_t* nextHuf,
0072                               ZSTD_strategy strategy, int disableLiteralCompression,
0073                               void* dst, size_t dstCapacity,
0074                         const void* src, size_t srcSize,
0075                               void* entropyWorkspace, size_t entropyWorkspaceSize,
0076                         const int bmi2)
0077 {
0078     size_t const minGain = ZSTD_minGain(srcSize, strategy);
0079     size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
0080     BYTE*  const ostart = (BYTE*)dst;
0081     U32 singleStream = srcSize < 256;
0082     symbolEncodingType_e hType = set_compressed;
0083     size_t cLitSize;
0084
0085     DEBUGLOG(5,"ZSTD_compressLiterals (disableLiteralCompression=%i srcSize=%u)",
0086                 disableLiteralCompression, (U32)srcSize);
0087
0088     /* Prepare nextEntropy assuming reusing the existing table */
0089     ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
0090
0091     if (disableLiteralCompression)
0092         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
0093
0094     /* small ? don't even attempt compression (speed opt) */
0095 #   define COMPRESS_LITERALS_SIZE_MIN 63
0096     {   size_t const minLitSize = (prevHuf->repeatMode == HUF_repeat_valid) ? 6 : COMPRESS_LITERALS_SIZE_MIN;
0097         if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
0098     }
0099
0100     RETURN_ERROR_IF(dstCapacity < lhSize+1, dstSize_tooSmall, "not enough space for compression");
0101     {   HUF_repeat repeat = prevHuf->repeatMode;
0102         int const preferRepeat = strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
0103         if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;
0104         cLitSize = singleStream ?
0105             HUF_compress1X_repeat(
0106                 ostart+lhSize, dstCapacity-lhSize, src, srcSize,
0107                 HUF_SYMBOLVALUE_MAX, HUF_TABLELOG_DEFAULT, entropyWorkspace, entropyWorkspaceSize,
0108                 (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2) :
0109             HUF_compress4X_repeat(
0110                 ostart+lhSize, dstCapacity-lhSize, src, srcSize,
0111                 HUF_SYMBOLVALUE_MAX, HUF_TABLELOG_DEFAULT, entropyWorkspace, entropyWorkspaceSize,
0112                 (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2);
0113         if (repeat != HUF_repeat_none) {
0114             /* reused the existing table */
0115             DEBUGLOG(5, "Reusing previous huffman table");
0116             hType = set_repeat;
0117         }
0118     }
0119
0120     if ((cLitSize==0) | (cLitSize >= srcSize - minGain) | ERR_isError(cLitSize)) {
0121         ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
0122         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
0123     }
0124     if (cLitSize==1) {
0125         ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
0126         return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
0127     }
0128
0129     if (hType == set_compressed) {
0130         /* using a newly constructed table */
0131         nextHuf->repeatMode = HUF_repeat_check;
0132     }
0133
0134     /* Build header */
0135     switch(lhSize)
0136     {
0137     case 3: /* 2 - 2 - 10 - 10 */
0138         {   U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
0139             MEM_writeLE24(ostart, lhc);
0140             break;
0141         }
0142     case 4: /* 2 - 2 - 14 - 14 */
0143         {   U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
0144             MEM_writeLE32(ostart, lhc);
0145             break;
0146         }
0147     case 5: /* 2 - 2 - 18 - 18 */
0148         {   U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
0149             MEM_writeLE32(ostart, lhc);
0150             ostart[4] = (BYTE)(cLitSize >> 10);
0151             break;
0152         }
0153     default:  /* not possible : lhSize is {3,4,5} */
0154         assert(0);
0155     }
0156     DEBUGLOG(5, "Compressed literals: %u -> %u", (U32)srcSize, (U32)(lhSize+cLitSize));
0157     return lhSize+cLitSize;
0158 }