1/*
2 * Copyright (c) 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
16size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
17{
18    BYTE* const ostart = (BYTE*)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    ZSTD_memcpy(ostart + flSize, src, srcSize);
39    DEBUGLOG(5, "Raw literals: %u -> %u", (U32)srcSize, (U32)(srcSize + flSize));
40    return srcSize + flSize;
41}
42
43size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
44{
45    BYTE* const ostart = (BYTE*)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
70size_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                        unsigned suspectUncompressible)
78{
79    size_t const minGain = ZSTD_minGain(srcSize, strategy);
80    size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB);
81    BYTE*  const ostart = (BYTE*)dst;
82    U32 singleStream = srcSize < 256;
83    symbolEncodingType_e hType = set_compressed;
84    size_t cLitSize;
85
86    DEBUGLOG(5,"ZSTD_compressLiterals (disableLiteralCompression=%i srcSize=%u)",
87                disableLiteralCompression, (U32)srcSize);
88
89    /* Prepare nextEntropy assuming reusing the existing table */
90    ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
91
92    if (disableLiteralCompression)
93        return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
94
95    /* small ? don't even attempt compression (speed opt) */
96#   define COMPRESS_LITERALS_SIZE_MIN 63
97    {   size_t const minLitSize = (prevHuf->repeatMode == HUF_repeat_valid) ? 6 : COMPRESS_LITERALS_SIZE_MIN;
98        if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
99    }
100
101    RETURN_ERROR_IF(dstCapacity < lhSize+1, dstSize_tooSmall, "not enough space for compression");
102    {   HUF_repeat repeat = prevHuf->repeatMode;
103        int const preferRepeat = strategy < ZSTD_lazy ? srcSize <= 1024 : 0;
104        if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1;
105        cLitSize = singleStream ?
106            HUF_compress1X_repeat(
107                ostart+lhSize, dstCapacity-lhSize, src, srcSize,
108                HUF_SYMBOLVALUE_MAX, HUF_TABLELOG_DEFAULT, entropyWorkspace, entropyWorkspaceSize,
109                (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2, suspectUncompressible) :
110            HUF_compress4X_repeat(
111                ostart+lhSize, dstCapacity-lhSize, src, srcSize,
112                HUF_SYMBOLVALUE_MAX, HUF_TABLELOG_DEFAULT, entropyWorkspace, entropyWorkspaceSize,
113                (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2, suspectUncompressible);
114        if (repeat != HUF_repeat_none) {
115            /* reused the existing table */
116            DEBUGLOG(5, "Reusing previous huffman table");
117            hType = set_repeat;
118        }
119    }
120
121    if ((cLitSize==0) || (cLitSize >= srcSize - minGain) || ERR_isError(cLitSize)) {
122        ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
123        return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
124    }
125    if (cLitSize==1) {
126        ZSTD_memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
127        return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
128    }
129
130    if (hType == set_compressed) {
131        /* using a newly constructed table */
132        nextHuf->repeatMode = HUF_repeat_check;
133    }
134
135    /* Build header */
136    switch(lhSize)
137    {
138    case 3: /* 2 - 2 - 10 - 10 */
139        {   U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
140            MEM_writeLE24(ostart, lhc);
141            break;
142        }
143    case 4: /* 2 - 2 - 14 - 14 */
144        {   U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
145            MEM_writeLE32(ostart, lhc);
146            break;
147        }
148    case 5: /* 2 - 2 - 18 - 18 */
149        {   U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
150            MEM_writeLE32(ostart, lhc);
151            ostart[4] = (BYTE)(cLitSize >> 10);
152            break;
153        }
154    default:  /* not possible : lhSize is {3,4,5} */
155        assert(0);
156    }
157    DEBUGLOG(5, "Compressed literals: %u -> %u", (U32)srcSize, (U32)(lhSize+cLitSize));
158    return lhSize+cLitSize;
159}
160