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 | |
16 | size_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(memPtr: ostart, val: (U16)((U32)set_basic + (1<<2) + (srcSize<<4))); |
30 | break; |
31 | case 3: /* 2 - 2 - 20 */ |
32 | MEM_writeLE32(memPtr: ostart, val32: (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 | |
43 | size_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(memPtr: ostart, val: (U16)((U32)set_rle + (1<<2) + (srcSize<<4))); |
57 | break; |
58 | case 3: /* 2 - 2 - 20 */ |
59 | MEM_writeLE32(memPtr: ostart, val32: (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 | unsigned suspectUncompressible) |
78 | { |
79 | size_t const minGain = ZSTD_minGain(srcSize, strat: 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 | dst: ostart+lhSize, dstSize: dstCapacity-lhSize, src, srcSize, |
108 | HUF_SYMBOLVALUE_MAX, HUF_TABLELOG_DEFAULT, workSpace: entropyWorkspace, wkspSize: entropyWorkspaceSize, |
109 | hufTable: (HUF_CElt*)nextHuf->CTable, repeat: &repeat, preferRepeat, bmi2, suspectUncompressible) : |
110 | HUF_compress4X_repeat( |
111 | dst: ostart+lhSize, dstSize: dstCapacity-lhSize, src, srcSize, |
112 | HUF_SYMBOLVALUE_MAX, HUF_TABLELOG_DEFAULT, workSpace: entropyWorkspace, wkspSize: entropyWorkspaceSize, |
113 | hufTable: (HUF_CElt*)nextHuf->CTable, repeat: &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(code: 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(memPtr: ostart, val: 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(memPtr: ostart, val32: 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(memPtr: ostart, val32: 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 | |