1 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0-only
2 /*
3 * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc.
4 * All rights reserved.
5 *
6 * This source code is licensed under both the BSD-style license (found in the
7 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
8 * in the COPYING file in the root directory of this source tree).
9 * You may select, at your option, one of the above-listed licenses.
10 */
11
12 /*-*************************************
13 * Dependencies
14 ***************************************/
15 #include "zstd_compress_literals.h"
16
ZSTD_noCompressLiterals(void * dst,size_t dstCapacity,const void * src,size_t srcSize)17 size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
18 {
19 BYTE* const ostart = (BYTE* const)dst;
20 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
21
22 RETURN_ERROR_IF(srcSize + flSize > dstCapacity, dstSize_tooSmall, "");
23
24 switch(flSize)
25 {
26 case 1: /* 2 - 1 - 5 */
27 ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3));
28 break;
29 case 2: /* 2 - 2 - 12 */
30 MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4)));
31 break;
32 case 3: /* 2 - 2 - 20 */
33 MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4)));
34 break;
35 default: /* not necessary : flSize is {1,2,3} */
36 assert(0);
37 }
38
39 memcpy(ostart + flSize, src, srcSize);
40 DEBUGLOG(5, "Raw literals: %u -> %u", (U32)srcSize, (U32)(srcSize + flSize));
41 return srcSize + flSize;
42 }
43
ZSTD_compressRleLiteralsBlock(void * dst,size_t dstCapacity,const void * src,size_t srcSize)44 size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize)
45 {
46 BYTE* const ostart = (BYTE* const)dst;
47 U32 const flSize = 1 + (srcSize>31) + (srcSize>4095);
48
49 (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */
50
51 switch(flSize)
52 {
53 case 1: /* 2 - 1 - 5 */
54 ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3));
55 break;
56 case 2: /* 2 - 2 - 12 */
57 MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4)));
58 break;
59 case 3: /* 2 - 2 - 20 */
60 MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4)));
61 break;
62 default: /* not necessary : flSize is {1,2,3} */
63 assert(0);
64 }
65
66 ostart[flSize] = *(const BYTE*)src;
67 DEBUGLOG(5, "RLE literals: %u -> %u", (U32)srcSize, (U32)flSize + 1);
68 return flSize+1;
69 }
70
ZSTD_compressLiterals(ZSTD_hufCTables_t const * prevHuf,ZSTD_hufCTables_t * nextHuf,ZSTD_strategy strategy,int disableLiteralCompression,void * dst,size_t dstCapacity,const void * src,size_t srcSize,void * entropyWorkspace,size_t entropyWorkspaceSize,const int bmi2)71 size_t ZSTD_compressLiterals (ZSTD_hufCTables_t const* prevHuf,
72 ZSTD_hufCTables_t* nextHuf,
73 ZSTD_strategy strategy, int disableLiteralCompression,
74 void* dst, size_t dstCapacity,
75 const void* src, size_t srcSize,
76 void* entropyWorkspace, size_t entropyWorkspaceSize,
77 const int bmi2)
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 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) :
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);
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 memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
123 return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
124 }
125 if (cLitSize==1) {
126 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