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