xref: /freebsd/sys/contrib/zstd/lib/compress/zstd_compress_literals.c (revision 6966ac055c3b7a39266fb982493330df7a097997)
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* entropyWorkspace, size_t entropyWorkspaceSize,
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 ?
103             HUF_compress1X_repeat(
104                 ostart+lhSize, dstCapacity-lhSize, src, srcSize,
105                 255, 11, entropyWorkspace, entropyWorkspaceSize,
106                 (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2) :
107             HUF_compress4X_repeat(
108                 ostart+lhSize, dstCapacity-lhSize, src, srcSize,
109                 255, 11, entropyWorkspace, entropyWorkspaceSize,
110                 (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2);
111         if (repeat != HUF_repeat_none) {
112             /* reused the existing table */
113             hType = set_repeat;
114         }
115     }
116 
117     if ((cLitSize==0) | (cLitSize >= srcSize - minGain) | ERR_isError(cLitSize)) {
118         memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
119         return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize);
120     }
121     if (cLitSize==1) {
122         memcpy(nextHuf, prevHuf, sizeof(*prevHuf));
123         return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize);
124     }
125 
126     if (hType == set_compressed) {
127         /* using a newly constructed table */
128         nextHuf->repeatMode = HUF_repeat_check;
129     }
130 
131     /* Build header */
132     switch(lhSize)
133     {
134     case 3: /* 2 - 2 - 10 - 10 */
135         {   U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14);
136             MEM_writeLE24(ostart, lhc);
137             break;
138         }
139     case 4: /* 2 - 2 - 14 - 14 */
140         {   U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18);
141             MEM_writeLE32(ostart, lhc);
142             break;
143         }
144     case 5: /* 2 - 2 - 18 - 18 */
145         {   U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22);
146             MEM_writeLE32(ostart, lhc);
147             ostart[4] = (BYTE)(cLitSize >> 10);
148             break;
149         }
150     default:  /* not possible : lhSize is {3,4,5} */
151         assert(0);
152     }
153     return lhSize+cLitSize;
154 }
155