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(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 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(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 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