14d3f1eafSConrad Meyer /* 24d3f1eafSConrad Meyer * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. 34d3f1eafSConrad Meyer * All rights reserved. 44d3f1eafSConrad Meyer * 54d3f1eafSConrad Meyer * This source code is licensed under both the BSD-style license (found in the 64d3f1eafSConrad Meyer * LICENSE file in the root directory of this source tree) and the GPLv2 (found 74d3f1eafSConrad Meyer * in the COPYING file in the root directory of this source tree). 84d3f1eafSConrad Meyer * You may select, at your option, one of the above-listed licenses. 94d3f1eafSConrad Meyer */ 104d3f1eafSConrad Meyer 114d3f1eafSConrad Meyer /*-************************************* 124d3f1eafSConrad Meyer * Dependencies 134d3f1eafSConrad Meyer ***************************************/ 144d3f1eafSConrad Meyer #include "zstd_compress_literals.h" 154d3f1eafSConrad Meyer 164d3f1eafSConrad Meyer size_t ZSTD_noCompressLiterals (void* dst, size_t dstCapacity, const void* src, size_t srcSize) 174d3f1eafSConrad Meyer { 184d3f1eafSConrad Meyer BYTE* const ostart = (BYTE* const)dst; 194d3f1eafSConrad Meyer U32 const flSize = 1 + (srcSize>31) + (srcSize>4095); 204d3f1eafSConrad Meyer 214d3f1eafSConrad Meyer RETURN_ERROR_IF(srcSize + flSize > dstCapacity, dstSize_tooSmall); 224d3f1eafSConrad Meyer 234d3f1eafSConrad Meyer switch(flSize) 244d3f1eafSConrad Meyer { 254d3f1eafSConrad Meyer case 1: /* 2 - 1 - 5 */ 264d3f1eafSConrad Meyer ostart[0] = (BYTE)((U32)set_basic + (srcSize<<3)); 274d3f1eafSConrad Meyer break; 284d3f1eafSConrad Meyer case 2: /* 2 - 2 - 12 */ 294d3f1eafSConrad Meyer MEM_writeLE16(ostart, (U16)((U32)set_basic + (1<<2) + (srcSize<<4))); 304d3f1eafSConrad Meyer break; 314d3f1eafSConrad Meyer case 3: /* 2 - 2 - 20 */ 324d3f1eafSConrad Meyer MEM_writeLE32(ostart, (U32)((U32)set_basic + (3<<2) + (srcSize<<4))); 334d3f1eafSConrad Meyer break; 344d3f1eafSConrad Meyer default: /* not necessary : flSize is {1,2,3} */ 354d3f1eafSConrad Meyer assert(0); 364d3f1eafSConrad Meyer } 374d3f1eafSConrad Meyer 384d3f1eafSConrad Meyer memcpy(ostart + flSize, src, srcSize); 394d3f1eafSConrad Meyer return srcSize + flSize; 404d3f1eafSConrad Meyer } 414d3f1eafSConrad Meyer 424d3f1eafSConrad Meyer size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t dstCapacity, const void* src, size_t srcSize) 434d3f1eafSConrad Meyer { 444d3f1eafSConrad Meyer BYTE* const ostart = (BYTE* const)dst; 454d3f1eafSConrad Meyer U32 const flSize = 1 + (srcSize>31) + (srcSize>4095); 464d3f1eafSConrad Meyer 474d3f1eafSConrad Meyer (void)dstCapacity; /* dstCapacity already guaranteed to be >=4, hence large enough */ 484d3f1eafSConrad Meyer 494d3f1eafSConrad Meyer switch(flSize) 504d3f1eafSConrad Meyer { 514d3f1eafSConrad Meyer case 1: /* 2 - 1 - 5 */ 524d3f1eafSConrad Meyer ostart[0] = (BYTE)((U32)set_rle + (srcSize<<3)); 534d3f1eafSConrad Meyer break; 544d3f1eafSConrad Meyer case 2: /* 2 - 2 - 12 */ 554d3f1eafSConrad Meyer MEM_writeLE16(ostart, (U16)((U32)set_rle + (1<<2) + (srcSize<<4))); 564d3f1eafSConrad Meyer break; 574d3f1eafSConrad Meyer case 3: /* 2 - 2 - 20 */ 584d3f1eafSConrad Meyer MEM_writeLE32(ostart, (U32)((U32)set_rle + (3<<2) + (srcSize<<4))); 594d3f1eafSConrad Meyer break; 604d3f1eafSConrad Meyer default: /* not necessary : flSize is {1,2,3} */ 614d3f1eafSConrad Meyer assert(0); 624d3f1eafSConrad Meyer } 634d3f1eafSConrad Meyer 644d3f1eafSConrad Meyer ostart[flSize] = *(const BYTE*)src; 654d3f1eafSConrad Meyer return flSize+1; 664d3f1eafSConrad Meyer } 674d3f1eafSConrad Meyer 684d3f1eafSConrad Meyer size_t ZSTD_compressLiterals (ZSTD_hufCTables_t const* prevHuf, 694d3f1eafSConrad Meyer ZSTD_hufCTables_t* nextHuf, 704d3f1eafSConrad Meyer ZSTD_strategy strategy, int disableLiteralCompression, 714d3f1eafSConrad Meyer void* dst, size_t dstCapacity, 724d3f1eafSConrad Meyer const void* src, size_t srcSize, 73*9cbefe25SConrad Meyer void* entropyWorkspace, size_t entropyWorkspaceSize, 744d3f1eafSConrad Meyer const int bmi2) 754d3f1eafSConrad Meyer { 764d3f1eafSConrad Meyer size_t const minGain = ZSTD_minGain(srcSize, strategy); 774d3f1eafSConrad Meyer size_t const lhSize = 3 + (srcSize >= 1 KB) + (srcSize >= 16 KB); 784d3f1eafSConrad Meyer BYTE* const ostart = (BYTE*)dst; 794d3f1eafSConrad Meyer U32 singleStream = srcSize < 256; 804d3f1eafSConrad Meyer symbolEncodingType_e hType = set_compressed; 814d3f1eafSConrad Meyer size_t cLitSize; 824d3f1eafSConrad Meyer 834d3f1eafSConrad Meyer DEBUGLOG(5,"ZSTD_compressLiterals (disableLiteralCompression=%i)", 844d3f1eafSConrad Meyer disableLiteralCompression); 854d3f1eafSConrad Meyer 864d3f1eafSConrad Meyer /* Prepare nextEntropy assuming reusing the existing table */ 874d3f1eafSConrad Meyer memcpy(nextHuf, prevHuf, sizeof(*prevHuf)); 884d3f1eafSConrad Meyer 894d3f1eafSConrad Meyer if (disableLiteralCompression) 904d3f1eafSConrad Meyer return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); 914d3f1eafSConrad Meyer 924d3f1eafSConrad Meyer /* small ? don't even attempt compression (speed opt) */ 934d3f1eafSConrad Meyer # define COMPRESS_LITERALS_SIZE_MIN 63 944d3f1eafSConrad Meyer { size_t const minLitSize = (prevHuf->repeatMode == HUF_repeat_valid) ? 6 : COMPRESS_LITERALS_SIZE_MIN; 954d3f1eafSConrad Meyer if (srcSize <= minLitSize) return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); 964d3f1eafSConrad Meyer } 974d3f1eafSConrad Meyer 984d3f1eafSConrad Meyer RETURN_ERROR_IF(dstCapacity < lhSize+1, dstSize_tooSmall, "not enough space for compression"); 994d3f1eafSConrad Meyer { HUF_repeat repeat = prevHuf->repeatMode; 1004d3f1eafSConrad Meyer int const preferRepeat = strategy < ZSTD_lazy ? srcSize <= 1024 : 0; 1014d3f1eafSConrad Meyer if (repeat == HUF_repeat_valid && lhSize == 3) singleStream = 1; 102*9cbefe25SConrad Meyer cLitSize = singleStream ? 103*9cbefe25SConrad Meyer HUF_compress1X_repeat( 104*9cbefe25SConrad Meyer ostart+lhSize, dstCapacity-lhSize, src, srcSize, 105*9cbefe25SConrad Meyer 255, 11, entropyWorkspace, entropyWorkspaceSize, 106*9cbefe25SConrad Meyer (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2) : 107*9cbefe25SConrad Meyer HUF_compress4X_repeat( 108*9cbefe25SConrad Meyer ostart+lhSize, dstCapacity-lhSize, src, srcSize, 109*9cbefe25SConrad Meyer 255, 11, entropyWorkspace, entropyWorkspaceSize, 110*9cbefe25SConrad Meyer (HUF_CElt*)nextHuf->CTable, &repeat, preferRepeat, bmi2); 1114d3f1eafSConrad Meyer if (repeat != HUF_repeat_none) { 1124d3f1eafSConrad Meyer /* reused the existing table */ 1134d3f1eafSConrad Meyer hType = set_repeat; 1144d3f1eafSConrad Meyer } 1154d3f1eafSConrad Meyer } 1164d3f1eafSConrad Meyer 1174d3f1eafSConrad Meyer if ((cLitSize==0) | (cLitSize >= srcSize - minGain) | ERR_isError(cLitSize)) { 1184d3f1eafSConrad Meyer memcpy(nextHuf, prevHuf, sizeof(*prevHuf)); 1194d3f1eafSConrad Meyer return ZSTD_noCompressLiterals(dst, dstCapacity, src, srcSize); 1204d3f1eafSConrad Meyer } 1214d3f1eafSConrad Meyer if (cLitSize==1) { 1224d3f1eafSConrad Meyer memcpy(nextHuf, prevHuf, sizeof(*prevHuf)); 1234d3f1eafSConrad Meyer return ZSTD_compressRleLiteralsBlock(dst, dstCapacity, src, srcSize); 1244d3f1eafSConrad Meyer } 1254d3f1eafSConrad Meyer 1264d3f1eafSConrad Meyer if (hType == set_compressed) { 1274d3f1eafSConrad Meyer /* using a newly constructed table */ 1284d3f1eafSConrad Meyer nextHuf->repeatMode = HUF_repeat_check; 1294d3f1eafSConrad Meyer } 1304d3f1eafSConrad Meyer 1314d3f1eafSConrad Meyer /* Build header */ 1324d3f1eafSConrad Meyer switch(lhSize) 1334d3f1eafSConrad Meyer { 1344d3f1eafSConrad Meyer case 3: /* 2 - 2 - 10 - 10 */ 1354d3f1eafSConrad Meyer { U32 const lhc = hType + ((!singleStream) << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<14); 1364d3f1eafSConrad Meyer MEM_writeLE24(ostart, lhc); 1374d3f1eafSConrad Meyer break; 1384d3f1eafSConrad Meyer } 1394d3f1eafSConrad Meyer case 4: /* 2 - 2 - 14 - 14 */ 1404d3f1eafSConrad Meyer { U32 const lhc = hType + (2 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<18); 1414d3f1eafSConrad Meyer MEM_writeLE32(ostart, lhc); 1424d3f1eafSConrad Meyer break; 1434d3f1eafSConrad Meyer } 1444d3f1eafSConrad Meyer case 5: /* 2 - 2 - 18 - 18 */ 1454d3f1eafSConrad Meyer { U32 const lhc = hType + (3 << 2) + ((U32)srcSize<<4) + ((U32)cLitSize<<22); 1464d3f1eafSConrad Meyer MEM_writeLE32(ostart, lhc); 1474d3f1eafSConrad Meyer ostart[4] = (BYTE)(cLitSize >> 10); 1484d3f1eafSConrad Meyer break; 1494d3f1eafSConrad Meyer } 1504d3f1eafSConrad Meyer default: /* not possible : lhSize is {3,4,5} */ 1514d3f1eafSConrad Meyer assert(0); 1524d3f1eafSConrad Meyer } 1534d3f1eafSConrad Meyer return lhSize+cLitSize; 1544d3f1eafSConrad Meyer } 155