Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1 | /* |
| 2 | ZSTD HC - High Compression Mode of Zstandard |
| 3 | Copyright (C) 2015, Yann Collet. |
| 4 | |
| 5 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) |
| 6 | |
| 7 | Redistribution and use in source and binary forms, with or without |
| 8 | modification, are permitted provided that the following conditions are |
| 9 | met: |
| 10 | |
| 11 | * Redistributions of source code must retain the above copyright |
| 12 | notice, this list of conditions and the following disclaimer. |
| 13 | * Redistributions in binary form must reproduce the above |
| 14 | copyright notice, this list of conditions and the following disclaimer |
| 15 | in the documentation and/or other materials provided with the |
| 16 | distribution. |
| 17 | |
| 18 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 19 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 20 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 21 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 22 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 23 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 24 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 25 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 26 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 27 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 28 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 29 | |
| 30 | You can contact the author at : |
| 31 | - Zstd source repository : https://www.zstd.net |
| 32 | */ |
| 33 | |
| 34 | |
Yann Collet | 4b100f4 | 2015-10-30 15:49:48 +0100 | [diff] [blame] | 35 | /* ******************************************************* |
| 36 | * Compiler specifics |
| 37 | *********************************************************/ |
| 38 | #ifdef _MSC_VER /* Visual Studio */ |
| 39 | # define FORCE_INLINE static __forceinline |
| 40 | # include <intrin.h> /* For Visual 2005 */ |
| 41 | # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ |
| 42 | # pragma warning(disable : 4324) /* disable: C4324: padded structure */ |
| 43 | #else |
| 44 | # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) |
| 45 | # ifdef __GNUC__ |
| 46 | # define FORCE_INLINE static inline __attribute__((always_inline)) |
| 47 | # else |
| 48 | # define FORCE_INLINE static inline |
| 49 | # endif |
| 50 | #endif |
| 51 | |
| 52 | |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 53 | /* ************************************* |
| 54 | * Includes |
| 55 | ***************************************/ |
| 56 | #include <stdlib.h> /* malloc */ |
| 57 | #include <string.h> /* memset */ |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 58 | #include "mem.h" |
| 59 | #include "fse_static.h" |
| 60 | #include "huff0.h" |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 61 | #include "zstd_static.h" |
Yann Collet | 3d9cf7a | 2015-10-29 17:15:14 +0100 | [diff] [blame] | 62 | #include "zstd_internal.h" |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 63 | |
| 64 | |
| 65 | /* ************************************* |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 66 | * Constants |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 67 | ***************************************/ |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 68 | static const U32 g_searchStrength = 8; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 69 | |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 70 | |
| 71 | /* ************************************* |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 72 | * Sequence storage |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 73 | ***************************************/ |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 74 | typedef struct { |
| 75 | void* buffer; |
| 76 | U32* offsetStart; |
| 77 | U32* offset; |
| 78 | BYTE* offCodeStart; |
| 79 | BYTE* offCode; |
| 80 | BYTE* litStart; |
| 81 | BYTE* lit; |
| 82 | BYTE* litLengthStart; |
| 83 | BYTE* litLength; |
| 84 | BYTE* matchLengthStart; |
| 85 | BYTE* matchLength; |
| 86 | BYTE* dumpsStart; |
| 87 | BYTE* dumps; |
| 88 | } seqStore_t; |
| 89 | |
| 90 | static void ZSTD_resetSeqStore(seqStore_t* ssPtr) |
| 91 | { |
| 92 | ssPtr->offset = ssPtr->offsetStart; |
| 93 | ssPtr->lit = ssPtr->litStart; |
| 94 | ssPtr->litLength = ssPtr->litLengthStart; |
| 95 | ssPtr->matchLength = ssPtr->matchLengthStart; |
| 96 | ssPtr->dumps = ssPtr->dumpsStart; |
| 97 | } |
| 98 | |
| 99 | |
| 100 | /* ************************************* |
| 101 | * Context memory management |
| 102 | ***************************************/ |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 103 | #define WORKPLACESIZE (BLOCKSIZE*3) |
| 104 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 105 | struct ZSTD_CCtx_s |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 106 | { |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 107 | const BYTE* nextSrc; /* next block here to continue on current prefix */ |
Yann Collet | eeb8ba1 | 2015-10-22 16:55:40 +0100 | [diff] [blame] | 108 | const BYTE* base; /* All regular indexes relative to this position */ |
| 109 | const BYTE* dictBase; /* extDict indexes relative to this position */ |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 110 | U32 dictLimit; /* below that point, need extDict */ |
Yann Collet | eeb8ba1 | 2015-10-22 16:55:40 +0100 | [diff] [blame] | 111 | U32 lowLimit; /* below that point, no more data */ |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 112 | U32 nextToUpdate; /* index from which to continue dictionary update */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 113 | ZSTD_parameters params; |
Yann Collet | 712def9 | 2015-10-29 18:41:45 +0100 | [diff] [blame] | 114 | void* workSpace; |
| 115 | size_t workSpaceSize; |
| 116 | |
| 117 | seqStore_t seqStore; /* sequences storage ptrs */ |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 118 | U32* hashTable; |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 119 | U32* contentTable; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 120 | }; |
| 121 | |
| 122 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 123 | ZSTD_CCtx* ZSTD_createCCtx(void) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 124 | { |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 125 | return (ZSTD_CCtx*) calloc(1, sizeof(ZSTD_CCtx)); |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 126 | } |
| 127 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 128 | size_t ZSTD_freeCCtx(ZSTD_CCtx* cctx) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 129 | { |
Yann Collet | 712def9 | 2015-10-29 18:41:45 +0100 | [diff] [blame] | 130 | free(cctx->workSpace); |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 131 | free(cctx); |
| 132 | return 0; |
| 133 | } |
| 134 | |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 135 | |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 136 | static unsigned ZSTD_highbit(U32 val); |
| 137 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 138 | /** ZSTD_validateParams |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 139 | correct params value to remain within authorized range |
| 140 | optimize for srcSize if srcSize > 0 */ |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 141 | void ZSTD_validateParams(ZSTD_parameters* params) |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 142 | { |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 143 | const U32 btPlus = (params->strategy == ZSTD_btlazy2); |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 144 | |
| 145 | /* validate params */ |
Yann Collet | 00fd7a2 | 2015-11-28 16:03:22 +0100 | [diff] [blame] | 146 | if (MEM_32bits()) if (params->windowLog > 25) params->windowLog = 25; /* 32 bits mode cannot flush > 24 bits */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 147 | if (params->windowLog > ZSTD_WINDOWLOG_MAX) params->windowLog = ZSTD_WINDOWLOG_MAX; |
| 148 | if (params->windowLog < ZSTD_WINDOWLOG_MIN) params->windowLog = ZSTD_WINDOWLOG_MIN; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 149 | |
| 150 | /* correct params, to use less memory */ |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 151 | if ((params->srcSize > 0) && (params->srcSize < (1<<ZSTD_WINDOWLOG_MAX))) |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 152 | { |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 153 | U32 srcLog = ZSTD_highbit((U32)(params->srcSize)-1) + 1; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 154 | if (params->windowLog > srcLog) params->windowLog = srcLog; |
| 155 | } |
| 156 | |
Yann Collet | 00fd7a2 | 2015-11-28 16:03:22 +0100 | [diff] [blame] | 157 | if (params->windowLog < ZSTD_WINDOWLOG_ABSOLUTEMIN) params->windowLog = ZSTD_WINDOWLOG_ABSOLUTEMIN; /* required for frame header */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 158 | if (params->contentLog > params->windowLog+btPlus) params->contentLog = params->windowLog+btPlus; /* <= ZSTD_CONTENTLOG_MAX */ |
| 159 | if (params->contentLog < ZSTD_CONTENTLOG_MIN) params->contentLog = ZSTD_CONTENTLOG_MIN; |
| 160 | if (params->hashLog > ZSTD_HASHLOG_MAX) params->hashLog = ZSTD_HASHLOG_MAX; |
| 161 | if (params->hashLog < ZSTD_HASHLOG_MIN) params->hashLog = ZSTD_HASHLOG_MIN; |
| 162 | if (params->searchLog > ZSTD_SEARCHLOG_MAX) params->searchLog = ZSTD_SEARCHLOG_MAX; |
| 163 | if (params->searchLog < ZSTD_SEARCHLOG_MIN) params->searchLog = ZSTD_SEARCHLOG_MIN; |
| 164 | if (params->searchLength> ZSTD_SEARCHLENGTH_MAX) params->searchLength = ZSTD_SEARCHLENGTH_MAX; |
| 165 | if (params->searchLength< ZSTD_SEARCHLENGTH_MIN) params->searchLength = ZSTD_SEARCHLENGTH_MIN; |
| 166 | if ((U32)params->strategy>(U32)ZSTD_btlazy2) params->strategy = ZSTD_btlazy2; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 167 | } |
| 168 | |
| 169 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 170 | static size_t ZSTD_resetCCtx_advanced (ZSTD_CCtx* zc, |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 171 | ZSTD_parameters params) |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 172 | { |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 173 | /* reserve table memory */ |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 174 | { |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 175 | const U32 contentLog = (params.strategy == ZSTD_fast) ? 1 : params.contentLog; |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 176 | const size_t tableSpace = ((1 << contentLog) + (1 << params.hashLog)) * sizeof(U32); |
Yann Collet | 712def9 | 2015-10-29 18:41:45 +0100 | [diff] [blame] | 177 | const size_t neededSpace = tableSpace + WORKPLACESIZE; |
| 178 | if (zc->workSpaceSize < neededSpace) |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 179 | { |
Yann Collet | 712def9 | 2015-10-29 18:41:45 +0100 | [diff] [blame] | 180 | free(zc->workSpace); |
| 181 | zc->workSpaceSize = neededSpace; |
| 182 | zc->workSpace = malloc(neededSpace); |
Yann Collet | 4114f95 | 2015-10-30 06:40:22 +0100 | [diff] [blame] | 183 | if (zc->workSpace == NULL) return ERROR(memory_allocation); |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 184 | } |
Yann Collet | 805a52a | 2015-11-06 10:52:17 +0100 | [diff] [blame] | 185 | memset(zc->workSpace, 0, tableSpace ); |
| 186 | zc->hashTable = (U32*)(zc->workSpace); |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 187 | zc->contentTable = zc->hashTable + ((size_t)1 << params.hashLog); |
| 188 | zc->seqStore.buffer = (void*) (zc->contentTable + ((size_t)1 << contentLog)); |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 189 | } |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 190 | |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 191 | zc->nextToUpdate = 1; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 192 | zc->nextSrc = NULL; |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 193 | zc->base = NULL; |
| 194 | zc->dictBase = NULL; |
| 195 | zc->dictLimit = 0; |
| 196 | zc->lowLimit = 0; |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 197 | zc->params = params; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 198 | zc->seqStore.offsetStart = (U32*) (zc->seqStore.buffer); |
| 199 | zc->seqStore.offCodeStart = (BYTE*) (zc->seqStore.offsetStart + (BLOCKSIZE>>2)); |
| 200 | zc->seqStore.litStart = zc->seqStore.offCodeStart + (BLOCKSIZE>>2); |
| 201 | zc->seqStore.litLengthStart = zc->seqStore.litStart + BLOCKSIZE; |
| 202 | zc->seqStore.matchLengthStart = zc->seqStore.litLengthStart + (BLOCKSIZE>>2); |
| 203 | zc->seqStore.dumpsStart = zc->seqStore.matchLengthStart + (BLOCKSIZE>>2); |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 204 | |
Yann Collet | 4114f95 | 2015-10-30 06:40:22 +0100 | [diff] [blame] | 205 | return 0; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 206 | } |
| 207 | |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 208 | |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 209 | /** ZSTD_reduceIndex |
| 210 | * rescale indexes to avoid future overflow (indexes are U32) */ |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 211 | static void ZSTD_reduceIndex (ZSTD_CCtx* zc, |
| 212 | const U32 reducerValue) |
| 213 | { |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 214 | const U32 contentLog = (zc->params.strategy == ZSTD_fast) ? 1 : zc->params.contentLog; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 215 | const U32 tableSpaceU32 = (1 << contentLog) + (1 << zc->params.hashLog); |
| 216 | U32* table32 = zc->hashTable; |
| 217 | U32 index; |
| 218 | |
| 219 | for (index=0 ; index < tableSpaceU32 ; index++) |
| 220 | { |
| 221 | if (table32[index] < reducerValue) table32[index] = 0; |
| 222 | else table32[index] -= reducerValue; |
| 223 | } |
| 224 | } |
| 225 | |
| 226 | |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 227 | /* ******************************************************* |
| 228 | * Block entropic compression |
| 229 | *********************************************************/ |
| 230 | size_t ZSTD_compressBound(size_t srcSize) /* maximum compressed size */ |
| 231 | { |
| 232 | return FSE_compressBound(srcSize) + 12; |
| 233 | } |
| 234 | |
| 235 | |
| 236 | size_t ZSTD_noCompressBlock (void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
| 237 | { |
| 238 | BYTE* const ostart = (BYTE* const)dst; |
| 239 | |
| 240 | if (srcSize + ZSTD_blockHeaderSize > maxDstSize) return ERROR(dstSize_tooSmall); |
| 241 | memcpy(ostart + ZSTD_blockHeaderSize, src, srcSize); |
| 242 | |
| 243 | /* Build header */ |
| 244 | ostart[0] = (BYTE)(srcSize>>16); |
| 245 | ostart[1] = (BYTE)(srcSize>>8); |
| 246 | ostart[2] = (BYTE) srcSize; |
| 247 | ostart[0] += (BYTE)(bt_raw<<6); /* is a raw (uncompressed) block */ |
| 248 | |
| 249 | return ZSTD_blockHeaderSize+srcSize; |
| 250 | } |
| 251 | |
| 252 | |
| 253 | static size_t ZSTD_noCompressLiterals (void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
| 254 | { |
| 255 | BYTE* const ostart = (BYTE* const)dst; |
| 256 | |
| 257 | if (srcSize + 3 > maxDstSize) return ERROR(dstSize_tooSmall); |
| 258 | |
| 259 | MEM_writeLE32(dst, ((U32)srcSize << 2) | IS_RAW); |
| 260 | memcpy(ostart + 3, src, srcSize); |
| 261 | return srcSize + 3; |
| 262 | } |
| 263 | |
| 264 | static size_t ZSTD_compressRleLiteralsBlock (void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
| 265 | { |
| 266 | BYTE* const ostart = (BYTE* const)dst; |
| 267 | |
| 268 | (void)maxDstSize; |
| 269 | MEM_writeLE32(dst, ((U32)srcSize << 2) | IS_RLE); /* note : maxDstSize > litHeaderSize > 4 */ |
| 270 | ostart[3] = *(const BYTE*)src; |
| 271 | return 4; |
| 272 | } |
| 273 | |
| 274 | size_t ZSTD_minGain(size_t srcSize) { return (srcSize >> 6) + 1; } |
| 275 | |
| 276 | static size_t ZSTD_compressLiterals (void* dst, size_t maxDstSize, |
| 277 | const void* src, size_t srcSize) |
| 278 | { |
| 279 | const size_t minGain = ZSTD_minGain(srcSize); |
| 280 | BYTE* const ostart = (BYTE*)dst; |
| 281 | size_t hsize; |
| 282 | static const size_t litHeaderSize = 5; |
| 283 | |
| 284 | if (maxDstSize < litHeaderSize+1) return ERROR(dstSize_tooSmall); /* not enough space for compression */ |
| 285 | |
| 286 | hsize = HUF_compress(ostart+litHeaderSize, maxDstSize-litHeaderSize, src, srcSize); |
| 287 | |
| 288 | if ((hsize==0) || (hsize >= srcSize - minGain)) return ZSTD_noCompressLiterals(dst, maxDstSize, src, srcSize); |
| 289 | if (hsize==1) return ZSTD_compressRleLiteralsBlock(dst, maxDstSize, src, srcSize); |
| 290 | |
| 291 | /* Build header */ |
| 292 | { |
| 293 | ostart[0] = (BYTE)(srcSize << 2); /* is a block, is compressed */ |
| 294 | ostart[1] = (BYTE)(srcSize >> 6); |
| 295 | ostart[2] = (BYTE)(srcSize >>14); |
| 296 | ostart[2] += (BYTE)(hsize << 5); |
| 297 | ostart[3] = (BYTE)(hsize >> 3); |
| 298 | ostart[4] = (BYTE)(hsize >>11); |
| 299 | } |
| 300 | |
| 301 | return hsize+litHeaderSize; |
| 302 | } |
| 303 | |
| 304 | |
| 305 | #define LITERAL_NOENTROPY 63 /* cheap heuristic */ |
| 306 | |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 307 | size_t ZSTD_compressSequences(void* dst, size_t maxDstSize, |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 308 | const seqStore_t* seqStorePtr, |
| 309 | size_t srcSize) |
| 310 | { |
| 311 | U32 count[MaxSeq+1]; |
| 312 | S16 norm[MaxSeq+1]; |
| 313 | size_t mostFrequent; |
| 314 | U32 max = 255; |
| 315 | U32 tableLog = 11; |
| 316 | U32 CTable_LitLength [FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL )]; |
| 317 | U32 CTable_OffsetBits [FSE_CTABLE_SIZE_U32(OffFSELog,MaxOff)]; |
| 318 | U32 CTable_MatchLength[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML )]; |
| 319 | U32 LLtype, Offtype, MLtype; /* compressed, raw or rle */ |
| 320 | const BYTE* const op_lit_start = seqStorePtr->litStart; |
| 321 | const BYTE* const llTable = seqStorePtr->litLengthStart; |
| 322 | const BYTE* const llPtr = seqStorePtr->litLength; |
| 323 | const BYTE* const mlTable = seqStorePtr->matchLengthStart; |
| 324 | const U32* const offsetTable = seqStorePtr->offsetStart; |
| 325 | BYTE* const offCodeTable = seqStorePtr->offCodeStart; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 326 | BYTE* const ostart = (BYTE*)dst; |
| 327 | BYTE* op = ostart; |
| 328 | BYTE* const oend = ostart + maxDstSize; |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 329 | const size_t nbSeq = llPtr - llTable; |
| 330 | const size_t minGain = ZSTD_minGain(srcSize); |
| 331 | const size_t maxCSize = srcSize - minGain; |
| 332 | BYTE* seqHead; |
| 333 | |
| 334 | |
| 335 | /* Compress literals */ |
| 336 | { |
| 337 | size_t cSize; |
| 338 | size_t litSize = seqStorePtr->lit - op_lit_start; |
| 339 | |
| 340 | if (litSize <= LITERAL_NOENTROPY) |
| 341 | cSize = ZSTD_noCompressLiterals(op, maxDstSize, op_lit_start, litSize); |
| 342 | else |
| 343 | cSize = ZSTD_compressLiterals(op, maxDstSize, op_lit_start, litSize); |
| 344 | if (ZSTD_isError(cSize)) return cSize; |
| 345 | op += cSize; |
| 346 | } |
| 347 | |
| 348 | /* Sequences Header */ |
| 349 | if ((oend-op) < MIN_SEQUENCES_SIZE) |
| 350 | return ERROR(dstSize_tooSmall); |
| 351 | MEM_writeLE16(op, (U16)nbSeq); op+=2; |
| 352 | seqHead = op; |
| 353 | |
| 354 | /* dumps : contains too large lengths */ |
| 355 | { |
| 356 | size_t dumpsLength = seqStorePtr->dumps - seqStorePtr->dumpsStart; |
| 357 | if (dumpsLength < 512) |
| 358 | { |
| 359 | op[0] = (BYTE)(dumpsLength >> 8); |
| 360 | op[1] = (BYTE)(dumpsLength); |
| 361 | op += 2; |
| 362 | } |
| 363 | else |
| 364 | { |
| 365 | op[0] = 2; |
| 366 | op[1] = (BYTE)(dumpsLength>>8); |
| 367 | op[2] = (BYTE)(dumpsLength); |
| 368 | op += 3; |
| 369 | } |
| 370 | if ((size_t)(oend-op) < dumpsLength+6) return ERROR(dstSize_tooSmall); |
| 371 | memcpy(op, seqStorePtr->dumpsStart, dumpsLength); |
| 372 | op += dumpsLength; |
| 373 | } |
| 374 | |
| 375 | /* CTable for Literal Lengths */ |
| 376 | max = MaxLL; |
| 377 | mostFrequent = FSE_countFast(count, &max, seqStorePtr->litLengthStart, nbSeq); |
| 378 | if ((mostFrequent == nbSeq) && (nbSeq > 2)) |
| 379 | { |
| 380 | *op++ = *(seqStorePtr->litLengthStart); |
| 381 | FSE_buildCTable_rle(CTable_LitLength, (BYTE)max); |
| 382 | LLtype = bt_rle; |
| 383 | } |
| 384 | else if ((nbSeq < 64) || (mostFrequent < (nbSeq >> (LLbits-1)))) |
| 385 | { |
| 386 | FSE_buildCTable_raw(CTable_LitLength, LLbits); |
| 387 | LLtype = bt_raw; |
| 388 | } |
| 389 | else |
| 390 | { |
| 391 | size_t NCountSize; |
| 392 | tableLog = FSE_optimalTableLog(LLFSELog, nbSeq, max); |
| 393 | FSE_normalizeCount(norm, tableLog, count, nbSeq, max); |
| 394 | NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */ |
| 395 | if (FSE_isError(NCountSize)) return ERROR(GENERIC); |
| 396 | op += NCountSize; |
| 397 | FSE_buildCTable(CTable_LitLength, norm, max, tableLog); |
| 398 | LLtype = bt_compressed; |
| 399 | } |
| 400 | |
| 401 | /* CTable for Offsets codes */ |
| 402 | { |
| 403 | /* create Offset codes */ |
| 404 | size_t i; |
| 405 | max = MaxOff; |
| 406 | for (i=0; i<nbSeq; i++) |
| 407 | { |
| 408 | offCodeTable[i] = (BYTE)ZSTD_highbit(offsetTable[i]) + 1; |
| 409 | if (offsetTable[i]==0) offCodeTable[i]=0; |
| 410 | } |
| 411 | mostFrequent = FSE_countFast(count, &max, offCodeTable, nbSeq); |
| 412 | } |
| 413 | if ((mostFrequent == nbSeq) && (nbSeq > 2)) |
| 414 | { |
| 415 | *op++ = *offCodeTable; |
| 416 | FSE_buildCTable_rle(CTable_OffsetBits, (BYTE)max); |
| 417 | Offtype = bt_rle; |
| 418 | } |
| 419 | else if ((nbSeq < 64) || (mostFrequent < (nbSeq >> (Offbits-1)))) |
| 420 | { |
| 421 | FSE_buildCTable_raw(CTable_OffsetBits, Offbits); |
| 422 | Offtype = bt_raw; |
| 423 | } |
| 424 | else |
| 425 | { |
| 426 | size_t NCountSize; |
| 427 | tableLog = FSE_optimalTableLog(OffFSELog, nbSeq, max); |
| 428 | FSE_normalizeCount(norm, tableLog, count, nbSeq, max); |
| 429 | NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */ |
| 430 | if (FSE_isError(NCountSize)) return ERROR(GENERIC); |
| 431 | op += NCountSize; |
| 432 | FSE_buildCTable(CTable_OffsetBits, norm, max, tableLog); |
| 433 | Offtype = bt_compressed; |
| 434 | } |
| 435 | |
| 436 | /* CTable for MatchLengths */ |
| 437 | max = MaxML; |
| 438 | mostFrequent = FSE_countFast(count, &max, seqStorePtr->matchLengthStart, nbSeq); |
| 439 | if ((mostFrequent == nbSeq) && (nbSeq > 2)) |
| 440 | { |
| 441 | *op++ = *seqStorePtr->matchLengthStart; |
| 442 | FSE_buildCTable_rle(CTable_MatchLength, (BYTE)max); |
| 443 | MLtype = bt_rle; |
| 444 | } |
| 445 | else if ((nbSeq < 64) || (mostFrequent < (nbSeq >> (MLbits-1)))) |
| 446 | { |
| 447 | FSE_buildCTable_raw(CTable_MatchLength, MLbits); |
| 448 | MLtype = bt_raw; |
| 449 | } |
| 450 | else |
| 451 | { |
| 452 | size_t NCountSize; |
| 453 | tableLog = FSE_optimalTableLog(MLFSELog, nbSeq, max); |
| 454 | FSE_normalizeCount(norm, tableLog, count, nbSeq, max); |
| 455 | NCountSize = FSE_writeNCount(op, oend-op, norm, max, tableLog); /* overflow protected */ |
| 456 | if (FSE_isError(NCountSize)) return ERROR(GENERIC); |
| 457 | op += NCountSize; |
| 458 | FSE_buildCTable(CTable_MatchLength, norm, max, tableLog); |
| 459 | MLtype = bt_compressed; |
| 460 | } |
| 461 | |
| 462 | seqHead[0] += (BYTE)((LLtype<<6) + (Offtype<<4) + (MLtype<<2)); |
| 463 | |
| 464 | /* Encoding Sequences */ |
| 465 | { |
| 466 | size_t streamSize, errorCode; |
| 467 | BIT_CStream_t blockStream; |
| 468 | FSE_CState_t stateMatchLength; |
| 469 | FSE_CState_t stateOffsetBits; |
| 470 | FSE_CState_t stateLitLength; |
| 471 | int i; |
| 472 | |
| 473 | errorCode = BIT_initCStream(&blockStream, op, oend-op); |
| 474 | if (ERR_isError(errorCode)) return ERROR(dstSize_tooSmall); /* not enough space remaining */ |
| 475 | FSE_initCState(&stateMatchLength, CTable_MatchLength); |
| 476 | FSE_initCState(&stateOffsetBits, CTable_OffsetBits); |
| 477 | FSE_initCState(&stateLitLength, CTable_LitLength); |
| 478 | |
| 479 | for (i=(int)nbSeq-1; i>=0; i--) |
| 480 | { |
| 481 | BYTE matchLength = mlTable[i]; |
| 482 | U32 offset = offsetTable[i]; |
| 483 | BYTE offCode = offCodeTable[i]; /* 32b*/ /* 64b*/ |
| 484 | U32 nbBits = (offCode-1) * (!!offCode); |
| 485 | BYTE litLength = llTable[i]; /* (7)*/ /* (7)*/ |
| 486 | FSE_encodeSymbol(&blockStream, &stateMatchLength, matchLength); /* 17 */ /* 17 */ |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 487 | if (MEM_32bits()) BIT_flushBits(&blockStream); /* 7 */ |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 488 | BIT_addBits(&blockStream, offset, nbBits); /* 32 */ /* 42 */ |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 489 | if (MEM_32bits()) BIT_flushBits(&blockStream); /* 7 */ |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 490 | FSE_encodeSymbol(&blockStream, &stateOffsetBits, offCode); /* 16 */ /* 51 */ |
| 491 | FSE_encodeSymbol(&blockStream, &stateLitLength, litLength); /* 26 */ /* 61 */ |
| 492 | BIT_flushBits(&blockStream); /* 7 */ /* 7 */ |
| 493 | } |
| 494 | |
| 495 | FSE_flushCState(&blockStream, &stateMatchLength); |
| 496 | FSE_flushCState(&blockStream, &stateOffsetBits); |
| 497 | FSE_flushCState(&blockStream, &stateLitLength); |
| 498 | |
| 499 | streamSize = BIT_closeCStream(&blockStream); |
| 500 | if (streamSize==0) return ERROR(dstSize_tooSmall); /* not enough space */ |
| 501 | op += streamSize; |
| 502 | } |
| 503 | |
| 504 | /* check compressibility */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 505 | if ((size_t)(op-ostart) >= maxCSize) return 0; |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 506 | |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 507 | return op - ostart; |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 508 | } |
| 509 | |
| 510 | |
| 511 | /** ZSTD_storeSeq |
| 512 | Store a sequence (literal length, literals, offset code and match length) into seqStore_t |
| 513 | @offsetCode : distance to match, or 0 == repCode |
| 514 | @matchCode : matchLength - MINMATCH |
| 515 | */ |
| 516 | MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, size_t offsetCode, size_t matchCode) |
| 517 | { |
| 518 | #if 0 |
| 519 | static const BYTE* g_start = NULL; |
| 520 | if (g_start==NULL) g_start = literals; |
| 521 | if (literals - g_start == 8695) |
| 522 | printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n", |
| 523 | (U32)(literals - g_start), (U32)litLength, (U32)matchCode+4, (U32)offsetCode); |
| 524 | #endif |
| 525 | |
| 526 | /* copy Literals */ |
| 527 | ZSTD_wildcopy(seqStorePtr->lit, literals, litLength); |
| 528 | seqStorePtr->lit += litLength; |
| 529 | |
| 530 | /* literal Length */ |
| 531 | if (litLength >= MaxLL) |
| 532 | { |
| 533 | *(seqStorePtr->litLength++) = MaxLL; |
| 534 | if (litLength<255 + MaxLL) |
| 535 | *(seqStorePtr->dumps++) = (BYTE)(litLength - MaxLL); |
| 536 | else |
| 537 | { |
| 538 | *(seqStorePtr->dumps++) = 255; |
| 539 | MEM_writeLE32(seqStorePtr->dumps, (U32)litLength); seqStorePtr->dumps += 3; |
| 540 | } |
| 541 | } |
| 542 | else *(seqStorePtr->litLength++) = (BYTE)litLength; |
| 543 | |
| 544 | /* match offset */ |
| 545 | *(seqStorePtr->offset++) = (U32)offsetCode; |
| 546 | |
| 547 | /* match Length */ |
| 548 | if (matchCode >= MaxML) |
| 549 | { |
| 550 | *(seqStorePtr->matchLength++) = MaxML; |
| 551 | if (matchCode < 255+MaxML) |
| 552 | *(seqStorePtr->dumps++) = (BYTE)(matchCode - MaxML); |
| 553 | else |
| 554 | { |
| 555 | *(seqStorePtr->dumps++) = 255; |
| 556 | MEM_writeLE32(seqStorePtr->dumps, (U32)matchCode); seqStorePtr->dumps += 3; |
| 557 | } |
| 558 | } |
| 559 | else *(seqStorePtr->matchLength++) = (BYTE)matchCode; |
| 560 | } |
| 561 | |
| 562 | |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 563 | /* ************************************* |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 564 | * Match length counter |
| 565 | ***************************************/ |
| 566 | static size_t ZSTD_read_ARCH(const void* p) { size_t r; memcpy(&r, p, sizeof(r)); return r; } |
| 567 | |
| 568 | static unsigned ZSTD_highbit(U32 val) |
| 569 | { |
| 570 | # if defined(_MSC_VER) /* Visual */ |
| 571 | unsigned long r=0; |
| 572 | _BitScanReverse(&r, val); |
| 573 | return (unsigned)r; |
| 574 | # elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */ |
| 575 | return 31 - __builtin_clz(val); |
| 576 | # else /* Software version */ |
| 577 | static const int DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; |
| 578 | U32 v = val; |
| 579 | int r; |
| 580 | v |= v >> 1; |
| 581 | v |= v >> 2; |
| 582 | v |= v >> 4; |
| 583 | v |= v >> 8; |
| 584 | v |= v >> 16; |
| 585 | r = DeBruijnClz[(U32)(v * 0x07C4ACDDU) >> 27]; |
| 586 | return r; |
| 587 | # endif |
| 588 | } |
| 589 | |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 590 | static unsigned ZSTD_NbCommonBytes (register size_t val) |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 591 | { |
| 592 | if (MEM_isLittleEndian()) |
| 593 | { |
| 594 | if (MEM_64bits()) |
| 595 | { |
| 596 | # if defined(_MSC_VER) && defined(_WIN64) |
| 597 | unsigned long r = 0; |
| 598 | _BitScanForward64( &r, (U64)val ); |
| 599 | return (int)(r>>3); |
| 600 | # elif defined(__GNUC__) && (__GNUC__ >= 3) |
| 601 | return (__builtin_ctzll((U64)val) >> 3); |
| 602 | # else |
| 603 | static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 }; |
| 604 | return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58]; |
| 605 | # endif |
| 606 | } |
| 607 | else /* 32 bits */ |
| 608 | { |
| 609 | # if defined(_MSC_VER) |
| 610 | unsigned long r=0; |
| 611 | _BitScanForward( &r, (U32)val ); |
| 612 | return (int)(r>>3); |
| 613 | # elif defined(__GNUC__) && (__GNUC__ >= 3) |
| 614 | return (__builtin_ctz((U32)val) >> 3); |
| 615 | # else |
| 616 | static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 }; |
| 617 | return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; |
| 618 | # endif |
| 619 | } |
| 620 | } |
| 621 | else /* Big Endian CPU */ |
| 622 | { |
| 623 | if (MEM_32bits()) |
| 624 | { |
| 625 | # if defined(_MSC_VER) && defined(_WIN64) |
| 626 | unsigned long r = 0; |
| 627 | _BitScanReverse64( &r, val ); |
| 628 | return (unsigned)(r>>3); |
| 629 | # elif defined(__GNUC__) && (__GNUC__ >= 3) |
| 630 | return (__builtin_clzll(val) >> 3); |
| 631 | # else |
| 632 | unsigned r; |
| 633 | const unsigned n32 = sizeof(size_t)*4; /* calculate this way due to compiler complaining in 32-bits mode */ |
| 634 | if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; } |
| 635 | if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } |
| 636 | r += (!val); |
| 637 | return r; |
| 638 | # endif |
| 639 | } |
| 640 | else /* 32 bits */ |
| 641 | { |
| 642 | # if defined(_MSC_VER) |
| 643 | unsigned long r = 0; |
| 644 | _BitScanReverse( &r, (unsigned long)val ); |
| 645 | return (unsigned)(r>>3); |
| 646 | # elif defined(__GNUC__) && (__GNUC__ >= 3) |
| 647 | return (__builtin_clz((U32)val) >> 3); |
| 648 | # else |
| 649 | unsigned r; |
| 650 | if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } |
| 651 | r += (!val); |
| 652 | return r; |
| 653 | # endif |
| 654 | } |
| 655 | } |
| 656 | } |
| 657 | |
| 658 | |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 659 | static size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit) |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 660 | { |
| 661 | const BYTE* const pStart = pIn; |
| 662 | |
| 663 | while ((pIn<pInLimit-(sizeof(size_t)-1))) |
| 664 | { |
| 665 | size_t diff = ZSTD_read_ARCH(pMatch) ^ ZSTD_read_ARCH(pIn); |
| 666 | if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; } |
| 667 | pIn += ZSTD_NbCommonBytes(diff); |
| 668 | return (size_t)(pIn - pStart); |
| 669 | } |
| 670 | |
| 671 | if (MEM_64bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; } |
| 672 | if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; } |
| 673 | if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++; |
| 674 | return (size_t)(pIn - pStart); |
| 675 | } |
| 676 | |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 677 | /** ZSTD_count_2segments |
| 678 | * can count match length with ip & match in potentially 2 different segments. |
| 679 | * convention : on reaching mEnd, match count continue starting from iStart |
| 680 | */ |
| 681 | static size_t ZSTD_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart) |
| 682 | { |
| 683 | size_t matchLength; |
| 684 | const BYTE* vEnd = ip + (mEnd - match); |
| 685 | if (vEnd > iEnd) vEnd = iEnd; |
| 686 | matchLength = ZSTD_count(ip, match, vEnd); |
| 687 | if (match + matchLength == mEnd) |
| 688 | matchLength += ZSTD_count(ip+matchLength, iStart, iEnd); |
| 689 | return matchLength; |
| 690 | } |
| 691 | |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 692 | |
| 693 | |
| 694 | /* ************************************* |
| 695 | * Hashes |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 696 | ***************************************/ |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 697 | |
Yann Collet | 4b100f4 | 2015-10-30 15:49:48 +0100 | [diff] [blame] | 698 | static const U32 prime4bytes = 2654435761U; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 699 | static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; } |
| 700 | static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); } |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 701 | |
Yann Collet | 4b100f4 | 2015-10-30 15:49:48 +0100 | [diff] [blame] | 702 | static const U64 prime5bytes = 889523592379ULL; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 703 | static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)((u * prime5bytes) << (64-40) >> (64-h)) ; } |
| 704 | static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_read64(p), h); } |
Yann Collet | 4b100f4 | 2015-10-30 15:49:48 +0100 | [diff] [blame] | 705 | |
| 706 | static const U64 prime6bytes = 227718039650203ULL; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 707 | static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)((u * prime6bytes) << (64-48) >> (64-h)) ; } |
| 708 | static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_read64(p), h); } |
Yann Collet | 4b100f4 | 2015-10-30 15:49:48 +0100 | [diff] [blame] | 709 | |
Yann Collet | 14983e7 | 2015-11-11 21:38:21 +0100 | [diff] [blame] | 710 | static const U64 prime7bytes = 58295818150454627ULL; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 711 | static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)((u * prime7bytes) << (64-56) >> (64-h)) ; } |
| 712 | static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_read64(p), h); } |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 713 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 714 | static size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls) |
Yann Collet | 4b100f4 | 2015-10-30 15:49:48 +0100 | [diff] [blame] | 715 | { |
| 716 | switch(mls) |
| 717 | { |
| 718 | default: |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 719 | case 4: return ZSTD_hash4Ptr(p, hBits); |
| 720 | case 5: return ZSTD_hash5Ptr(p, hBits); |
| 721 | case 6: return ZSTD_hash6Ptr(p, hBits); |
| 722 | case 7: return ZSTD_hash7Ptr(p, hBits); |
Yann Collet | 4b100f4 | 2015-10-30 15:49:48 +0100 | [diff] [blame] | 723 | } |
| 724 | } |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 725 | |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 726 | /* ************************************* |
| 727 | * Fast Scan |
| 728 | ***************************************/ |
| 729 | |
| 730 | FORCE_INLINE |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 731 | size_t ZSTD_compressBlock_fast_generic(ZSTD_CCtx* zc, |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 732 | void* dst, size_t maxDstSize, |
| 733 | const void* src, size_t srcSize, |
| 734 | const U32 mls) |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 735 | { |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 736 | U32* hashTable = zc->hashTable; |
| 737 | const U32 hBits = zc->params.hashLog; |
| 738 | seqStore_t* seqStorePtr = &(zc->seqStore); |
| 739 | const BYTE* const base = zc->base; |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 740 | const BYTE* const istart = (const BYTE*)src; |
Yann Collet | 805a52a | 2015-11-06 10:52:17 +0100 | [diff] [blame] | 741 | const BYTE* ip = istart; |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 742 | const BYTE* anchor = istart; |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 743 | const BYTE* const lowest = base + zc->dictLimit; |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 744 | const BYTE* const iend = istart + srcSize; |
| 745 | const BYTE* const ilimit = iend - 8; |
| 746 | |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 747 | size_t offset_2=REPCODE_STARTVALUE, offset_1=REPCODE_STARTVALUE; |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 748 | |
| 749 | |
| 750 | /* init */ |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 751 | ZSTD_resetSeqStore(seqStorePtr); |
Yann Collet | 6bcdeac | 2015-11-26 11:43:00 +0100 | [diff] [blame] | 752 | if (ip < base+4) |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 753 | { |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 754 | hashTable[ZSTD_hashPtr(base+1, hBits, mls)] = 1; |
| 755 | hashTable[ZSTD_hashPtr(base+2, hBits, mls)] = 2; |
| 756 | hashTable[ZSTD_hashPtr(base+3, hBits, mls)] = 3; |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 757 | ip = base+4; |
| 758 | } |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 759 | |
| 760 | /* Main Search Loop */ |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 761 | while (ip < ilimit) /* < instead of <=, because repcode check at (ip+1) */ |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 762 | { |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 763 | size_t mlCode; |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 764 | size_t offset; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 765 | const size_t h = ZSTD_hashPtr(ip, hBits, mls); |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 766 | const BYTE* match = base + hashTable[h]; |
| 767 | hashTable[h] = (U32)(ip-base); |
| 768 | |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 769 | if (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1)) /* note : by construction, offset_1 <= (ip-base) */ |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 770 | { |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 771 | mlCode = ZSTD_count(ip+1+MINMATCH, ip+1+MINMATCH-offset_1, iend); |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 772 | ip++; |
| 773 | offset = 0; |
| 774 | } |
| 775 | else |
| 776 | { |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 777 | if ( (match <= lowest) || |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 778 | (MEM_read32(match) != MEM_read32(ip)) ) |
| 779 | { |
| 780 | ip += ((ip-anchor) >> g_searchStrength) + 1; |
| 781 | continue; |
| 782 | } |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 783 | mlCode = ZSTD_count(ip+MINMATCH, match+MINMATCH, iend); |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 784 | offset = ip-match; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 785 | while ((ip>anchor) && (match>lowest) && (ip[-1] == match[-1])) { ip--; match--; mlCode++; } /* catch up */ |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 786 | offset_2 = offset_1; |
| 787 | offset_1 = offset; |
| 788 | } |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 789 | |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 790 | /* match found */ |
Yann Collet | 6bcdeac | 2015-11-26 11:43:00 +0100 | [diff] [blame] | 791 | ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset, mlCode); |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 792 | ip += mlCode + MINMATCH; |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 793 | anchor = ip; |
| 794 | |
| 795 | if (ip <= ilimit) |
| 796 | { |
| 797 | /* Fill Table */ |
Yann Collet | 6bcdeac | 2015-11-26 11:43:00 +0100 | [diff] [blame] | 798 | hashTable[ZSTD_hashPtr(ip-(mlCode+MINMATCH)+2, hBits, mls)] = (U32)(ip-(mlCode+MINMATCH)+2-base); /* here because ip-(mlCode+MINMATCH)+2 could be > iend-8 without ip <= ilimit check*/ |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 799 | hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base); |
| 800 | /* check immediate repcode */ |
| 801 | while ( (ip <= ilimit) |
| 802 | && (MEM_read32(ip) == MEM_read32(ip - offset_2)) ) |
| 803 | { |
| 804 | /* store sequence */ |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 805 | size_t rlCode = ZSTD_count(ip+MINMATCH, ip+MINMATCH-offset_2, iend); |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 806 | size_t tmpOff = offset_2; offset_2 = offset_1; offset_1 = tmpOff; /* swap offset_2 <=> offset_1 */ |
| 807 | hashTable[ZSTD_hashPtr(ip, hBits, mls)] = (U32)(ip-base); |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 808 | ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, rlCode); |
| 809 | ip += rlCode+MINMATCH; |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 810 | anchor = ip; |
| 811 | continue; /* faster when present ... (?) */ |
| 812 | } |
| 813 | } |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 814 | } |
| 815 | |
| 816 | /* Last Literals */ |
| 817 | { |
| 818 | size_t lastLLSize = iend - anchor; |
| 819 | memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| 820 | seqStorePtr->lit += lastLLSize; |
| 821 | } |
| 822 | |
| 823 | /* Finale compression stage */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 824 | return ZSTD_compressSequences(dst, maxDstSize, |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 825 | seqStorePtr, srcSize); |
| 826 | } |
| 827 | |
| 828 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 829 | size_t ZSTD_compressBlock_fast(ZSTD_CCtx* ctx, |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 830 | void* dst, size_t maxDstSize, |
| 831 | const void* src, size_t srcSize) |
| 832 | { |
| 833 | const U32 mls = ctx->params.searchLength; |
| 834 | switch(mls) |
| 835 | { |
| 836 | default: |
| 837 | case 4 : |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 838 | return ZSTD_compressBlock_fast_generic(ctx, dst, maxDstSize, src, srcSize, 4); |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 839 | case 5 : |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 840 | return ZSTD_compressBlock_fast_generic(ctx, dst, maxDstSize, src, srcSize, 5); |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 841 | case 6 : |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 842 | return ZSTD_compressBlock_fast_generic(ctx, dst, maxDstSize, src, srcSize, 6); |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 843 | case 7 : |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 844 | return ZSTD_compressBlock_fast_generic(ctx, dst, maxDstSize, src, srcSize, 7); |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 845 | } |
| 846 | } |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 847 | |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 848 | |
Yann Collet | 93a823c | 2015-11-13 15:08:43 +0100 | [diff] [blame] | 849 | //FORCE_INLINE |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 850 | size_t ZSTD_compressBlock_fast_extDict_generic(ZSTD_CCtx* ctx, |
| 851 | void* dst, size_t maxDstSize, |
| 852 | const void* src, size_t srcSize, |
| 853 | const U32 mls) |
| 854 | { |
| 855 | U32* hashTable = ctx->hashTable; |
| 856 | const U32 hBits = ctx->params.hashLog; |
| 857 | seqStore_t* seqStorePtr = &(ctx->seqStore); |
| 858 | const BYTE* const base = ctx->base; |
| 859 | const BYTE* const dictBase = ctx->dictBase; |
| 860 | const BYTE* const istart = (const BYTE*)src; |
| 861 | const BYTE* ip = istart; |
| 862 | const BYTE* anchor = istart; |
| 863 | const U32 lowLimit = ctx->lowLimit; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 864 | const BYTE* const dictStart = dictBase + lowLimit; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 865 | const U32 dictLimit = ctx->dictLimit; |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 866 | const BYTE* const lowPrefixPtr = base + dictLimit; |
| 867 | const BYTE* const dictEnd = dictBase + dictLimit; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 868 | const BYTE* const iend = istart + srcSize; |
| 869 | const BYTE* const ilimit = iend - 8; |
| 870 | |
Yann Collet | 138e89c | 2015-11-17 14:26:54 +0100 | [diff] [blame] | 871 | U32 offset_2=REPCODE_STARTVALUE, offset_1=REPCODE_STARTVALUE; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 872 | |
| 873 | |
| 874 | /* init */ |
| 875 | ZSTD_resetSeqStore(seqStorePtr); |
| 876 | { |
| 877 | /* skip first 4 positions to avoid read overflow during repcode match check */ |
| 878 | hashTable[ZSTD_hashPtr(ip+0, hBits, mls)] = (U32)(ip-base+0); |
| 879 | hashTable[ZSTD_hashPtr(ip+1, hBits, mls)] = (U32)(ip-base+1); |
| 880 | hashTable[ZSTD_hashPtr(ip+2, hBits, mls)] = (U32)(ip-base+2); |
| 881 | hashTable[ZSTD_hashPtr(ip+3, hBits, mls)] = (U32)(ip-base+3); |
| 882 | ip += 4; |
| 883 | } |
| 884 | |
| 885 | /* Main Search Loop */ |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 886 | while (ip < ilimit) /* < instead of <=, because (ip+1) */ |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 887 | { |
| 888 | const size_t h = ZSTD_hashPtr(ip, hBits, mls); |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 889 | const U32 matchIndex = hashTable[h]; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 890 | const BYTE* matchBase = matchIndex < dictLimit ? dictBase : base; |
Yann Collet | 6bcdeac | 2015-11-26 11:43:00 +0100 | [diff] [blame] | 891 | const BYTE* match = matchBase + matchIndex; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 892 | const U32 current = (U32)(ip-base); |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 893 | const U32 repIndex = current + 1 - offset_1; |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 894 | const BYTE* repBase = repIndex < dictLimit ? dictBase : base; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 895 | const BYTE* repMatch = repBase + repIndex; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 896 | size_t mlCode; |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 897 | U32 offset; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 898 | hashTable[h] = current; /* update hash table */ |
| 899 | |
| 900 | if ( ((repIndex <= dictLimit-4) || (repIndex >= dictLimit)) |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 901 | && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 902 | { |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 903 | const BYTE* repMatchEnd = repIndex < dictLimit ? dictEnd : iend; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 904 | mlCode = ZSTD_count_2segments(ip+1+MINMATCH, repMatch+MINMATCH, iend, repMatchEnd, lowPrefixPtr); |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 905 | ip++; |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 906 | offset = 0; |
| 907 | } |
| 908 | else |
| 909 | { |
| 910 | if ( (matchIndex < lowLimit) || |
| 911 | (MEM_read32(match) != MEM_read32(ip)) ) |
| 912 | { ip += ((ip-anchor) >> g_searchStrength) + 1; continue; } |
| 913 | { |
| 914 | const BYTE* matchEnd = matchIndex < dictLimit ? dictEnd : iend; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 915 | const BYTE* lowMatchPtr = matchIndex < dictLimit ? dictStart : lowPrefixPtr; |
| 916 | mlCode = ZSTD_count_2segments(ip+MINMATCH, match+MINMATCH, iend, matchEnd, lowPrefixPtr); |
| 917 | while ((ip>anchor) && (match>lowMatchPtr) && (ip[-1] == match[-1])) { ip--; match--; mlCode++; } /* catch up */ |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 918 | offset = current - matchIndex; |
| 919 | offset_2 = offset_1; |
| 920 | offset_1 = offset; |
| 921 | } |
| 922 | } |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 923 | |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 924 | /* found a match : store it */ |
| 925 | ZSTD_storeSeq(seqStorePtr, ip-anchor, anchor, offset, mlCode); |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 926 | ip += mlCode + MINMATCH; |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 927 | anchor = ip; |
| 928 | |
| 929 | if (ip <= ilimit) |
| 930 | { |
Yann Collet | 6bcdeac | 2015-11-26 11:43:00 +0100 | [diff] [blame] | 931 | /* Fill Table */ |
Yann Collet | 239cc28 | 2015-11-23 16:17:21 +0100 | [diff] [blame] | 932 | hashTable[ZSTD_hashPtr(base+current+2, hBits, mls)] = current+2; |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 933 | hashTable[ZSTD_hashPtr(ip-2, hBits, mls)] = (U32)(ip-2-base); |
| 934 | /* check immediate repcode */ |
| 935 | while (ip <= ilimit) |
| 936 | { |
| 937 | U32 current2 = (U32)(ip-base); |
| 938 | const U32 repIndex2 = current2 - offset_2; |
| 939 | const BYTE* repMatch2 = repIndex2 < dictLimit ? dictBase + repIndex2 : base + repIndex2; |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 940 | if ( ((repIndex2 <= dictLimit-4) || (repIndex2 >= dictLimit)) |
| 941 | && (MEM_read32(repMatch2) == MEM_read32(ip)) ) |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 942 | { |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 943 | const BYTE* const repEnd2 = repIndex2 < dictLimit ? dictEnd : iend; |
| 944 | size_t repLength2 = ZSTD_count_2segments(ip+MINMATCH, repMatch2+MINMATCH, iend, repEnd2, lowPrefixPtr); |
| 945 | U32 tmpOffset = offset_2; offset_2 = offset_1; offset_1 = tmpOffset; /* swap offset_2 <=> offset_1 */ |
| 946 | ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, repLength2); |
| 947 | hashTable[ZSTD_hashPtr(ip, hBits, mls)] = current2; |
| 948 | ip += repLength2+MINMATCH; |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 949 | anchor = ip; |
| 950 | continue; |
| 951 | } |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 952 | break; |
Yann Collet | 402fdcf | 2015-11-20 12:46:08 +0100 | [diff] [blame] | 953 | } |
| 954 | } |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 955 | } |
| 956 | |
| 957 | /* Last Literals */ |
| 958 | { |
| 959 | size_t lastLLSize = iend - anchor; |
| 960 | memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| 961 | seqStorePtr->lit += lastLLSize; |
| 962 | } |
| 963 | |
| 964 | /* Finale compression stage */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 965 | return ZSTD_compressSequences(dst, maxDstSize, |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 966 | seqStorePtr, srcSize); |
| 967 | } |
| 968 | |
| 969 | |
| 970 | size_t ZSTD_compressBlock_fast_extDict(ZSTD_CCtx* ctx, |
| 971 | void* dst, size_t maxDstSize, |
| 972 | const void* src, size_t srcSize) |
| 973 | { |
| 974 | const U32 mls = ctx->params.searchLength; |
| 975 | switch(mls) |
| 976 | { |
| 977 | default: |
| 978 | case 4 : |
| 979 | return ZSTD_compressBlock_fast_extDict_generic(ctx, dst, maxDstSize, src, srcSize, 4); |
| 980 | case 5 : |
| 981 | return ZSTD_compressBlock_fast_extDict_generic(ctx, dst, maxDstSize, src, srcSize, 5); |
| 982 | case 6 : |
| 983 | return ZSTD_compressBlock_fast_extDict_generic(ctx, dst, maxDstSize, src, srcSize, 6); |
| 984 | case 7 : |
| 985 | return ZSTD_compressBlock_fast_extDict_generic(ctx, dst, maxDstSize, src, srcSize, 7); |
| 986 | } |
| 987 | } |
| 988 | |
| 989 | |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 990 | /* ************************************* |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 991 | * Binary Tree search |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 992 | ***************************************/ |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 993 | /** ZSTD_insertBt1 : add one or multiple positions to tree |
Yann Collet | 6bcdeac | 2015-11-26 11:43:00 +0100 | [diff] [blame] | 994 | * @ip : assumed <= iend-8 |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 995 | * @return : nb of positions added */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 996 | static U32 ZSTD_insertBt1(ZSTD_CCtx* zc, const BYTE* const ip, const U32 mls, const BYTE* const iend, U32 nbCompares) |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 997 | { |
| 998 | U32* const hashTable = zc->hashTable; |
| 999 | const U32 hashLog = zc->params.hashLog; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1000 | const size_t h = ZSTD_hashPtr(ip, hashLog, mls); |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 1001 | U32* const bt = zc->contentTable; |
| 1002 | const U32 btLog = zc->params.contentLog - 1; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1003 | const U32 btMask= (1 << btLog) - 1; |
| 1004 | U32 matchIndex = hashTable[h]; |
| 1005 | size_t commonLengthSmaller=0, commonLengthLarger=0; |
| 1006 | const BYTE* const base = zc->base; |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1007 | const BYTE* match = base + matchIndex; |
| 1008 | U32 current = (U32)(ip-base); |
Yann Collet | e9eba60 | 2015-11-08 15:08:03 +0100 | [diff] [blame] | 1009 | const U32 btLow = btMask >= current ? 0 : current - btMask; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1010 | U32* smallerPtr = bt + 2*(current&btMask); |
| 1011 | U32* largerPtr = bt + 2*(current&btMask) + 1; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1012 | U32 dummy32; /* to be nullified at the end */ |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1013 | const U32 windowLow = zc->lowLimit; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1014 | |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 1015 | if ( (current-matchIndex == 1) /* RLE */ |
| 1016 | && (MEM_read64(match) == MEM_read64(ip)) ) |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1017 | { |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 1018 | size_t rleLength = ZSTD_count(ip+8, match+8, iend) + 8; |
Yann Collet | e9eba60 | 2015-11-08 15:08:03 +0100 | [diff] [blame] | 1019 | return (U32)(rleLength - mls); |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1020 | } |
| 1021 | |
| 1022 | hashTable[h] = (U32)(ip - base); /* Update Hash Table */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1023 | |
| 1024 | while (nbCompares-- && (matchIndex > windowLow)) |
| 1025 | { |
| 1026 | U32* nextPtr = bt + 2*(matchIndex & btMask); |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1027 | size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ |
| 1028 | |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1029 | match = base + matchIndex; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1030 | if (match[matchLength] == ip[matchLength]) |
| 1031 | matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1032 | |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1033 | if (ip+matchLength == iend) /* equal : no way to know if inf or sup */ |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 1034 | break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1035 | |
| 1036 | if (match[matchLength] < ip[matchLength]) |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1037 | { |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1038 | /* match is smaller than current */ |
| 1039 | *smallerPtr = matchIndex; /* update smaller idx */ |
| 1040 | commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1041 | if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1042 | smallerPtr = nextPtr+1; /* new "smaller" => larger of match */ |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1043 | matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1044 | } |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1045 | else |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1046 | { |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1047 | /* match is larger than current */ |
| 1048 | *largerPtr = matchIndex; |
| 1049 | commonLengthLarger = matchLength; |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1050 | if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1051 | largerPtr = nextPtr; |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1052 | matchIndex = nextPtr[0]; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1053 | } |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1054 | } |
| 1055 | |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1056 | *smallerPtr = *largerPtr = 0; |
Yann Collet | e9eba60 | 2015-11-08 15:08:03 +0100 | [diff] [blame] | 1057 | return 1; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1058 | } |
| 1059 | |
| 1060 | |
| 1061 | FORCE_INLINE /* inlining is important to hardwire a hot branch (template emulation) */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1062 | size_t ZSTD_insertBtAndFindBestMatch ( |
| 1063 | ZSTD_CCtx* zc, |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1064 | const BYTE* const ip, const BYTE* const iend, |
| 1065 | size_t* offsetPtr, |
| 1066 | U32 nbCompares, const U32 mls) |
| 1067 | { |
| 1068 | U32* const hashTable = zc->hashTable; |
| 1069 | const U32 hashLog = zc->params.hashLog; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1070 | const size_t h = ZSTD_hashPtr(ip, hashLog, mls); |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 1071 | U32* const bt = zc->contentTable; |
| 1072 | const U32 btLog = zc->params.contentLog - 1; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1073 | const U32 btMask= (1 << btLog) - 1; |
| 1074 | U32 matchIndex = hashTable[h]; |
| 1075 | size_t commonLengthSmaller=0, commonLengthLarger=0; |
| 1076 | const BYTE* const base = zc->base; |
| 1077 | const U32 current = (U32)(ip-base); |
| 1078 | const U32 btLow = btMask >= current ? 0 : current - btMask; |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1079 | const U32 windowLow = zc->lowLimit; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1080 | U32* smallerPtr = bt + 2*(current&btMask); |
| 1081 | U32* largerPtr = bt + 2*(current&btMask) + 1; |
Yann Collet | b241e9d | 2015-11-04 13:57:24 +0100 | [diff] [blame] | 1082 | size_t bestLength = 0; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1083 | U32 dummy32; /* to be nullified at the end */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1084 | |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1085 | hashTable[h] = (U32)(ip-base); /* Update Hash Table */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1086 | |
| 1087 | while (nbCompares-- && (matchIndex > windowLow)) |
| 1088 | { |
| 1089 | U32* nextPtr = bt + 2*(matchIndex & btMask); |
| 1090 | const BYTE* match = base + matchIndex; |
| 1091 | size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ |
| 1092 | |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1093 | if (match[matchLength] == ip[matchLength]) |
| 1094 | matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1095 | |
| 1096 | if (matchLength > bestLength) |
| 1097 | { |
Yann Collet | e8455f5 | 2015-11-04 17:41:20 +0100 | [diff] [blame] | 1098 | if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit(current-matchIndex+1) - ZSTD_highbit((U32)offsetPtr[0]+1)) ) |
Yann Collet | b241e9d | 2015-11-04 13:57:24 +0100 | [diff] [blame] | 1099 | bestLength = matchLength, *offsetPtr = current - matchIndex; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1100 | if (ip+matchLength == iend) /* equal : no way to know if inf or sup */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1101 | break; /* drop, to guarantee consistency (miss a little bit of compression) */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1102 | } |
| 1103 | |
| 1104 | if (match[matchLength] < ip[matchLength]) |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1105 | { |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1106 | /* match is smaller than current */ |
| 1107 | *smallerPtr = matchIndex; /* update smaller idx */ |
| 1108 | commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1109 | if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1110 | smallerPtr = nextPtr+1; /* new "smaller" => larger of match */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1111 | matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1112 | } |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1113 | else |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1114 | { |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1115 | /* match is larger than current */ |
| 1116 | *largerPtr = matchIndex; |
| 1117 | commonLengthLarger = matchLength; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1118 | if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1119 | largerPtr = nextPtr; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1120 | matchIndex = nextPtr[0]; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1121 | } |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1122 | } |
| 1123 | |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1124 | *smallerPtr = *largerPtr = 0; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1125 | |
| 1126 | zc->nextToUpdate = current+1; /* current has been inserted */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1127 | return bestLength; |
| 1128 | } |
| 1129 | |
| 1130 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1131 | static const BYTE* ZSTD_updateTree(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls) |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1132 | { |
| 1133 | const BYTE* const base = zc->base; |
| 1134 | const U32 target = (U32)(ip - base); |
| 1135 | U32 idx = zc->nextToUpdate; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1136 | |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1137 | for( ; idx < target ; ) |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1138 | idx += ZSTD_insertBt1(zc, base+idx, mls, iend, nbCompares); |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1139 | |
Yann Collet | f48e35c | 2015-11-07 01:13:31 +0100 | [diff] [blame] | 1140 | zc->nextToUpdate = idx; |
| 1141 | return base + idx; |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1142 | } |
| 1143 | |
| 1144 | |
| 1145 | /** Tree updater, providing best match */ |
| 1146 | FORCE_INLINE /* inlining is important to hardwire a hot branch (template emulation) */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1147 | size_t ZSTD_BtFindBestMatch ( |
| 1148 | ZSTD_CCtx* zc, |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1149 | const BYTE* const ip, const BYTE* const iLimit, |
| 1150 | size_t* offsetPtr, |
| 1151 | const U32 maxNbAttempts, const U32 mls) |
| 1152 | { |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1153 | const BYTE* nextToUpdate = ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls); |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 1154 | if (nextToUpdate > ip) /* RLE data */ |
| 1155 | { *offsetPtr = 1; return ZSTD_count(ip, ip-1, iLimit); } |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1156 | return ZSTD_insertBtAndFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls); |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1157 | } |
| 1158 | |
| 1159 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1160 | FORCE_INLINE size_t ZSTD_BtFindBestMatch_selectMLS ( |
| 1161 | ZSTD_CCtx* zc, /* Index table will be updated */ |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1162 | const BYTE* ip, const BYTE* const iLimit, |
| 1163 | size_t* offsetPtr, |
| 1164 | const U32 maxNbAttempts, const U32 matchLengthSearch) |
| 1165 | { |
| 1166 | switch(matchLengthSearch) |
| 1167 | { |
| 1168 | default : |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1169 | case 4 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4); |
| 1170 | case 5 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5); |
| 1171 | case 6 : return ZSTD_BtFindBestMatch(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6); |
Yann Collet | 96b9f0b | 2015-11-04 03:52:54 +0100 | [diff] [blame] | 1172 | } |
| 1173 | } |
| 1174 | |
| 1175 | |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1176 | /** ZSTD_insertBt1_extDict : add one or multiple positions to tree |
Yann Collet | 6bcdeac | 2015-11-26 11:43:00 +0100 | [diff] [blame] | 1177 | * @ip : assumed <= iend-8 |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1178 | * @return : nb of positions added */ |
| 1179 | static U32 ZSTD_insertBt1_extDict(ZSTD_CCtx* zc, const BYTE* const ip, const U32 mls, const BYTE* const iend, U32 nbCompares) |
| 1180 | { |
| 1181 | U32* const hashTable = zc->hashTable; |
| 1182 | const U32 hashLog = zc->params.hashLog; |
| 1183 | const size_t h = ZSTD_hashPtr(ip, hashLog, mls); |
| 1184 | U32* const bt = zc->contentTable; |
| 1185 | const U32 btLog = zc->params.contentLog - 1; |
| 1186 | const U32 btMask= (1 << btLog) - 1; |
| 1187 | U32 matchIndex = hashTable[h]; |
| 1188 | size_t commonLengthSmaller=0, commonLengthLarger=0; |
| 1189 | const BYTE* const base = zc->base; |
| 1190 | const BYTE* const dictBase = zc->dictBase; |
| 1191 | const U32 dictLimit = zc->dictLimit; |
| 1192 | const BYTE* const dictEnd = dictBase + dictLimit; |
| 1193 | const BYTE* const prefixStart = base + dictLimit; |
| 1194 | const BYTE* match = base + matchIndex; |
| 1195 | U32 current = (U32)(ip-base); |
| 1196 | const U32 btLow = btMask >= current ? 0 : current - btMask; |
| 1197 | U32* smallerPtr = bt + 2*(current&btMask); |
| 1198 | U32* largerPtr = bt + 2*(current&btMask) + 1; |
| 1199 | U32 dummy32; /* to be nullified at the end */ |
| 1200 | const U32 windowLow = zc->lowLimit; |
| 1201 | |
| 1202 | if ( (current-matchIndex == 1) /* RLE */ |
| 1203 | && (MEM_read64(match) == MEM_read64(ip)) ) |
| 1204 | { |
| 1205 | size_t rleLength = ZSTD_count(ip+8, match+8, iend) + 8; |
| 1206 | return (U32)(rleLength - mls); |
| 1207 | } |
| 1208 | |
| 1209 | hashTable[h] = (U32)(ip - base); /* Update Hash Table */ |
| 1210 | |
| 1211 | while (nbCompares-- && (matchIndex > windowLow)) |
| 1212 | { |
| 1213 | U32* nextPtr = bt + 2*(matchIndex & btMask); |
| 1214 | size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ |
| 1215 | |
| 1216 | if (matchIndex+matchLength >= dictLimit) |
| 1217 | { |
| 1218 | match = base + matchIndex; |
| 1219 | if (match[matchLength] == ip[matchLength]) |
| 1220 | matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1; |
| 1221 | } |
| 1222 | else |
| 1223 | { |
| 1224 | match = dictBase + matchIndex; |
| 1225 | matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart); |
Yann Collet | 225179d | 2015-11-23 16:52:22 +0100 | [diff] [blame] | 1226 | if (matchIndex+matchLength >= dictLimit) |
| 1227 | match = base + matchIndex; /* to prepare for next usage of match[matchLength] */ |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1228 | } |
| 1229 | |
| 1230 | if (ip+matchLength == iend) /* equal : no way to know if inf or sup */ |
| 1231 | break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */ |
| 1232 | |
| 1233 | if (match[matchLength] < ip[matchLength]) /* necessarily within correct buffer */ |
| 1234 | { |
| 1235 | /* match is smaller than current */ |
| 1236 | *smallerPtr = matchIndex; /* update smaller idx */ |
| 1237 | commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ |
| 1238 | if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
| 1239 | smallerPtr = nextPtr+1; /* new "smaller" => larger of match */ |
| 1240 | matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ |
| 1241 | } |
| 1242 | else |
| 1243 | { |
| 1244 | /* match is larger than current */ |
| 1245 | *largerPtr = matchIndex; |
| 1246 | commonLengthLarger = matchLength; |
| 1247 | if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
| 1248 | largerPtr = nextPtr; |
| 1249 | matchIndex = nextPtr[0]; |
| 1250 | } |
| 1251 | } |
| 1252 | |
| 1253 | *smallerPtr = *largerPtr = 0; |
| 1254 | return 1; |
| 1255 | } |
| 1256 | |
| 1257 | |
| 1258 | static const BYTE* ZSTD_updateTree_extDict(ZSTD_CCtx* zc, const BYTE* const ip, const BYTE* const iend, const U32 nbCompares, const U32 mls) |
| 1259 | { |
| 1260 | const BYTE* const base = zc->base; |
| 1261 | const U32 target = (U32)(ip - base); |
| 1262 | U32 idx = zc->nextToUpdate; |
| 1263 | |
| 1264 | for( ; idx < target ; ) |
| 1265 | idx += ZSTD_insertBt1_extDict(zc, base+idx, mls, iend, nbCompares); |
| 1266 | |
| 1267 | zc->nextToUpdate = idx; |
| 1268 | return base + idx; |
| 1269 | } |
| 1270 | |
| 1271 | |
| 1272 | FORCE_INLINE /* inlining is important to hardwire a hot branch (template emulation) */ |
| 1273 | size_t ZSTD_insertBtAndFindBestMatch_extDict ( |
| 1274 | ZSTD_CCtx* zc, |
| 1275 | const BYTE* const ip, const BYTE* const iend, |
| 1276 | size_t* offsetPtr, |
| 1277 | U32 nbCompares, const U32 mls) |
| 1278 | { |
| 1279 | U32* const hashTable = zc->hashTable; |
| 1280 | const U32 hashLog = zc->params.hashLog; |
| 1281 | const size_t h = ZSTD_hashPtr(ip, hashLog, mls); |
| 1282 | U32* const bt = zc->contentTable; |
| 1283 | const U32 btLog = zc->params.contentLog - 1; |
| 1284 | const U32 btMask= (1 << btLog) - 1; |
| 1285 | U32 matchIndex = hashTable[h]; |
| 1286 | size_t commonLengthSmaller=0, commonLengthLarger=0; |
| 1287 | const BYTE* const base = zc->base; |
| 1288 | const BYTE* const dictBase = zc->dictBase; |
| 1289 | const U32 dictLimit = zc->dictLimit; |
| 1290 | const BYTE* const dictEnd = dictBase + dictLimit; |
| 1291 | const BYTE* const prefixStart = base + dictLimit; |
| 1292 | const U32 current = (U32)(ip-base); |
| 1293 | const U32 btLow = btMask >= current ? 0 : current - btMask; |
| 1294 | const U32 windowLow = zc->lowLimit; |
| 1295 | U32* smallerPtr = bt + 2*(current&btMask); |
| 1296 | U32* largerPtr = bt + 2*(current&btMask) + 1; |
| 1297 | size_t bestLength = 0; |
| 1298 | U32 dummy32; /* to be nullified at the end */ |
| 1299 | |
| 1300 | hashTable[h] = (U32)(ip-base); /* Update Hash Table */ |
| 1301 | |
| 1302 | while (nbCompares-- && (matchIndex > windowLow)) |
| 1303 | { |
| 1304 | U32* nextPtr = bt + 2*(matchIndex & btMask); |
| 1305 | size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */ |
| 1306 | const BYTE* match; |
| 1307 | |
| 1308 | if (matchIndex+matchLength >= dictLimit) |
| 1309 | { |
| 1310 | match = base + matchIndex; |
| 1311 | if (match[matchLength] == ip[matchLength]) |
| 1312 | matchLength += ZSTD_count(ip+matchLength+1, match+matchLength+1, iend) +1; |
| 1313 | } |
| 1314 | else |
| 1315 | { |
| 1316 | match = dictBase + matchIndex; |
| 1317 | matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart); |
Yann Collet | 225179d | 2015-11-23 16:52:22 +0100 | [diff] [blame] | 1318 | if (matchIndex+matchLength >= dictLimit) |
| 1319 | match = base + matchIndex; /* to prepare for next usage of match[matchLength] */ |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1320 | } |
| 1321 | |
| 1322 | if (matchLength > bestLength) |
| 1323 | { |
| 1324 | if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit(current-matchIndex+1) - ZSTD_highbit((U32)offsetPtr[0]+1)) ) |
| 1325 | bestLength = matchLength, *offsetPtr = current - matchIndex; |
| 1326 | if (ip+matchLength == iend) /* equal : no way to know if inf or sup */ |
| 1327 | break; /* drop, to guarantee consistency (miss a little bit of compression) */ |
| 1328 | } |
| 1329 | |
| 1330 | if (match[matchLength] < ip[matchLength]) |
| 1331 | { |
| 1332 | /* match is smaller than current */ |
| 1333 | *smallerPtr = matchIndex; /* update smaller idx */ |
| 1334 | commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */ |
| 1335 | if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
| 1336 | smallerPtr = nextPtr+1; /* new "smaller" => larger of match */ |
| 1337 | matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */ |
| 1338 | } |
| 1339 | else |
| 1340 | { |
| 1341 | /* match is larger than current */ |
| 1342 | *largerPtr = matchIndex; |
| 1343 | commonLengthLarger = matchLength; |
| 1344 | if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */ |
| 1345 | largerPtr = nextPtr; |
| 1346 | matchIndex = nextPtr[0]; |
| 1347 | } |
| 1348 | } |
| 1349 | |
| 1350 | *smallerPtr = *largerPtr = 0; |
| 1351 | |
| 1352 | zc->nextToUpdate = current+1; /* current has been inserted */ |
| 1353 | return bestLength; |
| 1354 | } |
| 1355 | |
| 1356 | /** Tree updater, providing best match */ |
| 1357 | FORCE_INLINE /* inlining is important to hardwire a hot branch (template emulation) */ |
| 1358 | size_t ZSTD_BtFindBestMatch_extDict ( |
| 1359 | ZSTD_CCtx* zc, |
| 1360 | const BYTE* const ip, const BYTE* const iLimit, |
| 1361 | size_t* offsetPtr, |
| 1362 | const U32 maxNbAttempts, const U32 mls) |
| 1363 | { |
| 1364 | const BYTE* nextToUpdate = ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls); |
| 1365 | if (nextToUpdate > ip) /* RLE data */ |
| 1366 | { *offsetPtr = 1; return ZSTD_count(ip, ip-1, iLimit); } |
| 1367 | return ZSTD_insertBtAndFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, mls); |
| 1368 | } |
| 1369 | |
| 1370 | |
| 1371 | FORCE_INLINE size_t ZSTD_BtFindBestMatch_selectMLS_extDict ( |
| 1372 | ZSTD_CCtx* zc, /* Index table will be updated */ |
| 1373 | const BYTE* ip, const BYTE* const iLimit, |
| 1374 | size_t* offsetPtr, |
| 1375 | const U32 maxNbAttempts, const U32 matchLengthSearch) |
| 1376 | { |
| 1377 | switch(matchLengthSearch) |
| 1378 | { |
| 1379 | default : |
| 1380 | case 4 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4); |
| 1381 | case 5 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5); |
| 1382 | case 6 : return ZSTD_BtFindBestMatch_extDict(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6); |
| 1383 | } |
| 1384 | } |
| 1385 | |
| 1386 | |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1387 | /* *********************** |
| 1388 | * Hash Chain |
| 1389 | *************************/ |
| 1390 | |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 1391 | #define NEXT_IN_CHAIN(d, mask) chainTable[(d) & mask] |
| 1392 | |
Yann Collet | 6bcdeac | 2015-11-26 11:43:00 +0100 | [diff] [blame] | 1393 | /* Update chains up to ip (excluded) |
Yann Collet | 06eade5 | 2015-11-23 14:23:47 +0100 | [diff] [blame] | 1394 | Assumption : always within prefix (ie. not within extDict) */ |
| 1395 | static U32 ZSTD_insertAndFindFirstIndex (ZSTD_CCtx* zc, const BYTE* ip, U32 mls) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1396 | { |
| 1397 | U32* const hashTable = zc->hashTable; |
| 1398 | const U32 hashLog = zc->params.hashLog; |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 1399 | U32* const chainTable = zc->contentTable; |
| 1400 | const U32 chainMask = (1 << zc->params.contentLog) - 1; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1401 | const BYTE* const base = zc->base; |
| 1402 | const U32 target = (U32)(ip - base); |
| 1403 | U32 idx = zc->nextToUpdate; |
| 1404 | |
| 1405 | while(idx < target) |
| 1406 | { |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1407 | size_t h = ZSTD_hashPtr(base+idx, hashLog, mls); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1408 | NEXT_IN_CHAIN(idx, chainMask) = hashTable[h]; |
| 1409 | hashTable[h] = idx; |
| 1410 | idx++; |
| 1411 | } |
| 1412 | |
| 1413 | zc->nextToUpdate = target; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1414 | return hashTable[ZSTD_hashPtr(ip, hashLog, mls)]; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1415 | } |
| 1416 | |
| 1417 | |
| 1418 | FORCE_INLINE /* inlining is important to hardwire a hot branch (template emulation) */ |
Yann Collet | c1e52f0 | 2015-11-23 14:37:59 +0100 | [diff] [blame] | 1419 | size_t ZSTD_HcFindBestMatch_generic ( |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1420 | ZSTD_CCtx* zc, /* Index table will be updated */ |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1421 | const BYTE* const ip, const BYTE* const iLimit, |
| 1422 | size_t* offsetPtr, |
Yann Collet | c1e52f0 | 2015-11-23 14:37:59 +0100 | [diff] [blame] | 1423 | const U32 maxNbAttempts, const U32 mls, const U32 extDict) |
Yann Collet | 287b7d9 | 2015-11-22 13:24:05 +0100 | [diff] [blame] | 1424 | { |
Yann Collet | 1f44b3f | 2015-11-05 17:32:18 +0100 | [diff] [blame] | 1425 | U32* const chainTable = zc->contentTable; |
| 1426 | const U32 chainSize = (1 << zc->params.contentLog); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1427 | const U32 chainMask = chainSize-1; |
| 1428 | const BYTE* const base = zc->base; |
| 1429 | const BYTE* const dictBase = zc->dictBase; |
| 1430 | const U32 dictLimit = zc->dictLimit; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1431 | const BYTE* const prefixStart = base + dictLimit; |
| 1432 | const BYTE* const dictEnd = dictBase + dictLimit; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1433 | const U32 lowLimit = zc->lowLimit; |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1434 | const U32 current = (U32)(ip-base); |
| 1435 | const U32 minChain = current > chainSize ? current - chainSize : 0; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1436 | U32 matchIndex; |
| 1437 | const BYTE* match; |
| 1438 | int nbAttempts=maxNbAttempts; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1439 | size_t ml=MINMATCH-1; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1440 | |
| 1441 | /* HC4 match finder */ |
Yann Collet | c1e52f0 | 2015-11-23 14:37:59 +0100 | [diff] [blame] | 1442 | matchIndex = ZSTD_insertAndFindFirstIndex (zc, ip, mls); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1443 | |
| 1444 | while ((matchIndex>lowLimit) && (nbAttempts)) |
| 1445 | { |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1446 | size_t currentMl=0; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1447 | nbAttempts--; |
Yann Collet | c1e52f0 | 2015-11-23 14:37:59 +0100 | [diff] [blame] | 1448 | if ((!extDict) || matchIndex >= dictLimit) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1449 | { |
| 1450 | match = base + matchIndex; |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1451 | if (match[ml] == ip[ml]) /* potentially better */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1452 | currentMl = ZSTD_count(ip, match, iLimit); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1453 | } |
| 1454 | else |
| 1455 | { |
| 1456 | match = dictBase + matchIndex; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1457 | if (MEM_read32(match) == MEM_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */ |
| 1458 | currentMl = ZSTD_count_2segments(ip+MINMATCH, match+MINMATCH, iLimit, dictEnd, prefixStart) + MINMATCH; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1459 | } |
| 1460 | |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1461 | /* save best solution */ |
Yann Collet | 239cc28 | 2015-11-23 16:17:21 +0100 | [diff] [blame] | 1462 | if (currentMl > ml) { ml = currentMl; *offsetPtr = current - matchIndex; if (ip+currentMl == iLimit) break; /* best possible, and avoid read overflow*/ } |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1463 | |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1464 | if (matchIndex <= minChain) break; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1465 | matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask); |
| 1466 | } |
| 1467 | |
| 1468 | return ml; |
| 1469 | } |
| 1470 | |
| 1471 | |
Yann Collet | c1e52f0 | 2015-11-23 14:37:59 +0100 | [diff] [blame] | 1472 | FORCE_INLINE size_t ZSTD_HcFindBestMatch_selectMLS ( |
| 1473 | ZSTD_CCtx* zc, |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1474 | const BYTE* ip, const BYTE* const iLimit, |
| 1475 | size_t* offsetPtr, |
| 1476 | const U32 maxNbAttempts, const U32 matchLengthSearch) |
| 1477 | { |
| 1478 | switch(matchLengthSearch) |
| 1479 | { |
| 1480 | default : |
Yann Collet | c1e52f0 | 2015-11-23 14:37:59 +0100 | [diff] [blame] | 1481 | case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 0); |
| 1482 | case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 0); |
| 1483 | case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 0); |
| 1484 | } |
| 1485 | } |
| 1486 | |
| 1487 | |
| 1488 | FORCE_INLINE size_t ZSTD_HcFindBestMatch_extDict_selectMLS ( |
| 1489 | ZSTD_CCtx* zc, |
| 1490 | const BYTE* ip, const BYTE* const iLimit, |
| 1491 | size_t* offsetPtr, |
| 1492 | const U32 maxNbAttempts, const U32 matchLengthSearch) |
| 1493 | { |
| 1494 | switch(matchLengthSearch) |
| 1495 | { |
| 1496 | default : |
| 1497 | case 4 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 4, 1); |
| 1498 | case 5 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 5, 1); |
| 1499 | case 6 : return ZSTD_HcFindBestMatch_generic(zc, ip, iLimit, offsetPtr, maxNbAttempts, 6, 1); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1500 | } |
| 1501 | } |
| 1502 | |
| 1503 | |
Yann Collet | 287b7d9 | 2015-11-22 13:24:05 +0100 | [diff] [blame] | 1504 | /* ******************************* |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1505 | * Common parser - lazy strategy |
Yann Collet | 287b7d9 | 2015-11-22 13:24:05 +0100 | [diff] [blame] | 1506 | *********************************/ |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1507 | FORCE_INLINE |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1508 | size_t ZSTD_compressBlock_lazy_generic(ZSTD_CCtx* ctx, |
Yann Collet | c95f899 | 2015-11-19 17:28:35 +0100 | [diff] [blame] | 1509 | void* dst, size_t maxDstSize, const void* src, size_t srcSize, |
Yann Collet | 007c1c6 | 2015-11-22 02:42:28 +0100 | [diff] [blame] | 1510 | const U32 searchMethod, const U32 depth) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1511 | { |
| 1512 | seqStore_t* seqStorePtr = &(ctx->seqStore); |
| 1513 | const BYTE* const istart = (const BYTE*)src; |
| 1514 | const BYTE* ip = istart; |
| 1515 | const BYTE* anchor = istart; |
| 1516 | const BYTE* const iend = istart + srcSize; |
| 1517 | const BYTE* const ilimit = iend - 8; |
| 1518 | |
| 1519 | size_t offset_2=REPCODE_STARTVALUE, offset_1=REPCODE_STARTVALUE; |
| 1520 | const U32 maxSearches = 1 << ctx->params.searchLog; |
| 1521 | const U32 mls = ctx->params.searchLength; |
| 1522 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1523 | typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit, |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1524 | size_t* offsetPtr, |
| 1525 | U32 maxNbAttempts, U32 matchLengthSearch); |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1526 | searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1527 | |
| 1528 | /* init */ |
| 1529 | ZSTD_resetSeqStore(seqStorePtr); |
| 1530 | if (((ip-ctx->base) - ctx->dictLimit) < REPCODE_STARTVALUE) ip += REPCODE_STARTVALUE; |
| 1531 | |
| 1532 | /* Match Loop */ |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1533 | while (ip < ilimit) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1534 | { |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1535 | size_t matchLength=0; |
| 1536 | size_t offset=0; |
| 1537 | const BYTE* start=ip+1; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1538 | |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 1539 | /* check repCode */ |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1540 | if (MEM_read32(ip+1) == MEM_read32(ip+1 - offset_1)) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1541 | { |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 1542 | /* repcode : we take it */ |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1543 | matchLength = ZSTD_count(ip+1+MINMATCH, ip+1+MINMATCH-offset_1, iend) + MINMATCH; |
Yann Collet | 007c1c6 | 2015-11-22 02:42:28 +0100 | [diff] [blame] | 1544 | if (depth==0) goto _storeSequence; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1545 | } |
| 1546 | |
Yann Collet | fc2afcf | 2015-11-06 15:40:14 +0100 | [diff] [blame] | 1547 | { |
Yann Collet | 239cc28 | 2015-11-23 16:17:21 +0100 | [diff] [blame] | 1548 | /* first search (depth 0) */ |
| 1549 | size_t offsetFound = 99999999; |
| 1550 | size_t ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls); |
| 1551 | if (ml2 > matchLength) |
| 1552 | matchLength = ml2, start = ip, offset=offsetFound; |
| 1553 | } |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1554 | |
Yann Collet | 239cc28 | 2015-11-23 16:17:21 +0100 | [diff] [blame] | 1555 | if (matchLength < MINMATCH) |
| 1556 | { |
| 1557 | ip += ((ip-anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */ |
| 1558 | continue; |
| 1559 | } |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1560 | |
| 1561 | /* let's try to find a better solution */ |
Yann Collet | 007c1c6 | 2015-11-22 02:42:28 +0100 | [diff] [blame] | 1562 | if (depth>=1) |
| 1563 | while (ip<ilimit) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1564 | { |
| 1565 | ip ++; |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1566 | if ((offset) && (MEM_read32(ip) == MEM_read32(ip - offset_1))) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1567 | { |
Yann Collet | 007c1c6 | 2015-11-22 02:42:28 +0100 | [diff] [blame] | 1568 | size_t mlRep = ZSTD_count(ip+MINMATCH, ip+MINMATCH-offset_1, iend) + MINMATCH; |
| 1569 | int gain2 = (int)(mlRep * 3); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1570 | int gain1 = (int)(matchLength*3 - ZSTD_highbit((U32)offset+1) + 1); |
Yann Collet | 007c1c6 | 2015-11-22 02:42:28 +0100 | [diff] [blame] | 1571 | if ((mlRep >= MINMATCH) && (gain2 > gain1)) |
| 1572 | matchLength = mlRep, offset = 0, start = ip; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1573 | } |
| 1574 | { |
| 1575 | size_t offset2=999999; |
| 1576 | size_t ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls); |
Yann Collet | 007c1c6 | 2015-11-22 02:42:28 +0100 | [diff] [blame] | 1577 | int gain2 = (int)(ml2*4 - ZSTD_highbit((U32)offset2+1)); /* raw approx */ |
| 1578 | int gain1 = (int)(matchLength*4 - ZSTD_highbit((U32)offset+1) + 4); |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1579 | if ((ml2 >= MINMATCH) && (gain2 > gain1)) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1580 | { |
Yann Collet | 628065c | 2015-11-06 18:44:54 +0100 | [diff] [blame] | 1581 | matchLength = ml2, offset = offset2, start = ip; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1582 | continue; /* search a better one */ |
| 1583 | } |
| 1584 | } |
| 1585 | |
| 1586 | /* let's find an even better one */ |
Yann Collet | 007c1c6 | 2015-11-22 02:42:28 +0100 | [diff] [blame] | 1587 | if ((depth==2) && (ip<ilimit)) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1588 | { |
| 1589 | ip ++; |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1590 | if ((offset) && (MEM_read32(ip) == MEM_read32(ip - offset_1))) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1591 | { |
| 1592 | size_t ml2 = ZSTD_count(ip+MINMATCH, ip+MINMATCH-offset_1, iend) + MINMATCH; |
| 1593 | int gain2 = (int)(ml2 * 4); |
| 1594 | int gain1 = (int)(matchLength*4 - ZSTD_highbit((U32)offset+1) + 1); |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1595 | if ((ml2 >= MINMATCH) && (gain2 > gain1)) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1596 | matchLength = ml2, offset = 0, start = ip; |
| 1597 | } |
| 1598 | { |
| 1599 | size_t offset2=999999; |
| 1600 | size_t ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls); |
Yann Collet | 628065c | 2015-11-06 18:44:54 +0100 | [diff] [blame] | 1601 | int gain2 = (int)(ml2*4 - ZSTD_highbit((U32)offset2+1)); /* raw approx */ |
| 1602 | int gain1 = (int)(matchLength*4 - ZSTD_highbit((U32)offset+1) + 7); |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1603 | if ((ml2 >= MINMATCH) && (gain2 > gain1)) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1604 | { |
Yann Collet | 628065c | 2015-11-06 18:44:54 +0100 | [diff] [blame] | 1605 | matchLength = ml2, offset = offset2, start = ip; |
| 1606 | continue; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1607 | } |
| 1608 | } |
| 1609 | } |
| 1610 | break; /* nothing found : store previous solution */ |
| 1611 | } |
| 1612 | |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1613 | /* catch up */ |
Yann Collet | 628065c | 2015-11-06 18:44:54 +0100 | [diff] [blame] | 1614 | if (offset) |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1615 | { |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1616 | while ((start>anchor) && (start>ctx->base+offset) && (start[-1] == start[-1-offset])) /* only search for offset within prefix */ |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1617 | { start--; matchLength++; } |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 1618 | offset_2 = offset_1; offset_1 = offset; |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1619 | } |
| 1620 | |
| 1621 | /* store sequence */ |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1622 | _storeSequence: |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1623 | { |
| 1624 | size_t litLength = start - anchor; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1625 | ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, matchLength-MINMATCH); |
Yann Collet | 4baee50 | 2015-11-09 03:19:33 +0100 | [diff] [blame] | 1626 | anchor = ip = start + matchLength; |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1627 | } |
| 1628 | |
Yann Collet | 743402c | 2015-11-20 12:03:53 +0100 | [diff] [blame] | 1629 | /* check immediate repcode */ |
| 1630 | while ( (ip <= ilimit) |
| 1631 | && (MEM_read32(ip) == MEM_read32(ip - offset_2)) ) |
| 1632 | { |
| 1633 | /* store sequence */ |
| 1634 | matchLength = ZSTD_count(ip+MINMATCH, ip+MINMATCH-offset_2, iend); |
| 1635 | offset = offset_2; |
| 1636 | offset_2 = offset_1; |
| 1637 | offset_1 = offset; |
| 1638 | ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength); |
| 1639 | ip += matchLength+MINMATCH; |
| 1640 | anchor = ip; |
| 1641 | continue; /* faster when present ... (?) */ |
| 1642 | } |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1643 | } |
| 1644 | |
| 1645 | /* Last Literals */ |
| 1646 | { |
| 1647 | size_t lastLLSize = iend - anchor; |
| 1648 | memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| 1649 | seqStorePtr->lit += lastLLSize; |
| 1650 | } |
| 1651 | |
| 1652 | /* Final compression stage */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1653 | return ZSTD_compressSequences(dst, maxDstSize, |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1654 | seqStorePtr, srcSize); |
| 1655 | } |
| 1656 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1657 | size_t ZSTD_compressBlock_btlazy2(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1658 | { |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1659 | return ZSTD_compressBlock_lazy_generic(ctx, dst, maxDstSize, src, srcSize, 1, 2); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1660 | } |
| 1661 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1662 | size_t ZSTD_compressBlock_lazy2(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1663 | { |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1664 | return ZSTD_compressBlock_lazy_generic(ctx, dst, maxDstSize, src, srcSize, 0, 2); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1665 | } |
| 1666 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1667 | size_t ZSTD_compressBlock_lazy(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1668 | { |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1669 | return ZSTD_compressBlock_lazy_generic(ctx, dst, maxDstSize, src, srcSize, 0, 1); |
Yann Collet | 5106a76 | 2015-11-05 15:00:24 +0100 | [diff] [blame] | 1670 | } |
| 1671 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1672 | size_t ZSTD_compressBlock_greedy(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1673 | { |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1674 | return ZSTD_compressBlock_lazy_generic(ctx, dst, maxDstSize, src, srcSize, 0, 0); |
Yann Collet | be2010e | 2015-10-31 12:57:14 +0100 | [diff] [blame] | 1675 | } |
| 1676 | |
| 1677 | |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1678 | FORCE_INLINE |
| 1679 | size_t ZSTD_compressBlock_lazy_extDict_generic(ZSTD_CCtx* ctx, |
| 1680 | void* dst, size_t maxDstSize, const void* src, size_t srcSize, |
| 1681 | const U32 searchMethod, const U32 depth) |
| 1682 | { |
| 1683 | seqStore_t* seqStorePtr = &(ctx->seqStore); |
| 1684 | const BYTE* const istart = (const BYTE*)src; |
| 1685 | const BYTE* ip = istart; |
| 1686 | const BYTE* anchor = istart; |
| 1687 | const BYTE* const iend = istart + srcSize; |
| 1688 | const BYTE* const ilimit = iend - 8; |
| 1689 | const BYTE* const base = ctx->base; |
| 1690 | const U32 dictLimit = ctx->dictLimit; |
| 1691 | const BYTE* const prefixStart = base + dictLimit; |
| 1692 | const BYTE* const dictBase = ctx->dictBase; |
| 1693 | const BYTE* const dictEnd = dictBase + dictLimit; |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 1694 | const BYTE* const dictStart = dictBase + ctx->lowLimit; |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1695 | |
| 1696 | size_t offset_2=REPCODE_STARTVALUE, offset_1=REPCODE_STARTVALUE; |
| 1697 | const U32 maxSearches = 1 << ctx->params.searchLog; |
| 1698 | const U32 mls = ctx->params.searchLength; |
| 1699 | |
| 1700 | typedef size_t (*searchMax_f)(ZSTD_CCtx* zc, const BYTE* ip, const BYTE* iLimit, |
| 1701 | size_t* offsetPtr, |
| 1702 | U32 maxNbAttempts, U32 matchLengthSearch); |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1703 | searchMax_f searchMax = searchMethod ? ZSTD_BtFindBestMatch_selectMLS_extDict : ZSTD_HcFindBestMatch_extDict_selectMLS; |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1704 | |
| 1705 | /* init */ |
| 1706 | ZSTD_resetSeqStore(seqStorePtr); |
| 1707 | if (((ip-base) - dictLimit) < REPCODE_STARTVALUE) ip += REPCODE_STARTVALUE; |
| 1708 | |
| 1709 | /* Match Loop */ |
| 1710 | while (ip < ilimit) |
| 1711 | { |
| 1712 | size_t matchLength=0; |
| 1713 | size_t offset=0; |
| 1714 | const BYTE* start=ip+1; |
| 1715 | U32 current = (U32)(ip-base); |
| 1716 | |
| 1717 | /* check repCode */ |
| 1718 | { |
| 1719 | const U32 repIndex = (U32)(current+1 - offset_1); |
| 1720 | const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; |
| 1721 | const BYTE* const repMatch = repBase + repIndex; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1722 | if ((U32)((dictLimit-1) - repIndex) >= 3) /* intentional overflow */ |
Yann Collet | d7233d6 | 2015-11-22 14:40:51 +0100 | [diff] [blame] | 1723 | if (MEM_read32(ip+1) == MEM_read32(repMatch)) |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1724 | { |
| 1725 | /* repcode detected we should take it */ |
| 1726 | const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1727 | matchLength = ZSTD_count_2segments(ip+1+MINMATCH, repMatch+MINMATCH, iend, repEnd, prefixStart) + MINMATCH; |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1728 | if (depth==0) goto _storeSequence; |
| 1729 | } |
| 1730 | } |
| 1731 | |
| 1732 | { |
Yann Collet | 239cc28 | 2015-11-23 16:17:21 +0100 | [diff] [blame] | 1733 | /* first search (depth 0) */ |
| 1734 | size_t offsetFound = 99999999; |
| 1735 | size_t ml2 = searchMax(ctx, ip, iend, &offsetFound, maxSearches, mls); |
| 1736 | if (ml2 > matchLength) |
| 1737 | matchLength = ml2, start = ip, offset=offsetFound; |
| 1738 | } |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1739 | |
Yann Collet | 239cc28 | 2015-11-23 16:17:21 +0100 | [diff] [blame] | 1740 | if (matchLength < MINMATCH) |
| 1741 | { |
| 1742 | ip += ((ip-anchor) >> g_searchStrength) + 1; /* jump faster over incompressible sections */ |
| 1743 | continue; |
| 1744 | } |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1745 | |
| 1746 | /* let's try to find a better solution */ |
| 1747 | if (depth>=1) |
| 1748 | while (ip<ilimit) |
| 1749 | { |
| 1750 | ip ++; |
| 1751 | current++; |
| 1752 | /* check repCode */ |
| 1753 | if (offset) |
| 1754 | { |
| 1755 | const U32 repIndex = (U32)(current - offset_1); |
| 1756 | const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; |
| 1757 | const BYTE* const repMatch = repBase + repIndex; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1758 | if ((U32)((dictLimit-1) - repIndex) >= 3) /* intentional overflow */ |
Yann Collet | d7233d6 | 2015-11-22 14:40:51 +0100 | [diff] [blame] | 1759 | if (MEM_read32(ip) == MEM_read32(repMatch)) |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1760 | { |
| 1761 | /* repcode detected */ |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1762 | const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1763 | size_t repLength = ZSTD_count_2segments(ip+MINMATCH, repMatch+MINMATCH, iend, repEnd, prefixStart) + MINMATCH; |
| 1764 | int gain2 = (int)(repLength * 3); |
| 1765 | int gain1 = (int)(matchLength*3 - ZSTD_highbit((U32)offset+1) + 1); |
| 1766 | if ((repLength >= MINMATCH) && (gain2 > gain1)) |
| 1767 | matchLength = repLength, offset = 0, start = ip; |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1768 | } |
| 1769 | } |
| 1770 | |
| 1771 | /* search match, depth 1 */ |
| 1772 | { |
| 1773 | size_t offset2=999999; |
| 1774 | size_t ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls); |
| 1775 | int gain2 = (int)(ml2*4 - ZSTD_highbit((U32)offset2+1)); /* raw approx */ |
| 1776 | int gain1 = (int)(matchLength*4 - ZSTD_highbit((U32)offset+1) + 4); |
| 1777 | if ((ml2 >= MINMATCH) && (gain2 > gain1)) |
| 1778 | { |
| 1779 | matchLength = ml2, offset = offset2, start = ip; |
| 1780 | continue; /* search a better one */ |
| 1781 | } |
| 1782 | } |
| 1783 | |
| 1784 | /* let's find an even better one */ |
| 1785 | if ((depth==2) && (ip<ilimit)) |
| 1786 | { |
| 1787 | ip ++; |
| 1788 | current++; |
| 1789 | /* check repCode */ |
| 1790 | if (offset) |
| 1791 | { |
| 1792 | const U32 repIndex = (U32)(current - offset_1); |
| 1793 | const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; |
| 1794 | const BYTE* const repMatch = repBase + repIndex; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1795 | if ((U32)((dictLimit-1) - repIndex) >= 3) /* intentional overflow */ |
Yann Collet | d7233d6 | 2015-11-22 14:40:51 +0100 | [diff] [blame] | 1796 | if (MEM_read32(ip) == MEM_read32(repMatch)) |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1797 | { |
| 1798 | /* repcode detected */ |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1799 | const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1800 | size_t repLength = ZSTD_count_2segments(ip+MINMATCH, repMatch+MINMATCH, iend, repEnd, prefixStart) + MINMATCH; |
| 1801 | int gain2 = (int)(repLength * 4); |
| 1802 | int gain1 = (int)(matchLength*4 - ZSTD_highbit((U32)offset+1) + 1); |
| 1803 | if ((repLength >= MINMATCH) && (gain2 > gain1)) |
| 1804 | matchLength = repLength, offset = 0, start = ip; |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1805 | } |
| 1806 | } |
| 1807 | |
| 1808 | /* search match, depth 2 */ |
| 1809 | { |
| 1810 | size_t offset2=999999; |
| 1811 | size_t ml2 = searchMax(ctx, ip, iend, &offset2, maxSearches, mls); |
| 1812 | int gain2 = (int)(ml2*4 - ZSTD_highbit((U32)offset2+1)); /* raw approx */ |
| 1813 | int gain1 = (int)(matchLength*4 - ZSTD_highbit((U32)offset+1) + 7); |
| 1814 | if ((ml2 >= MINMATCH) && (gain2 > gain1)) |
| 1815 | { |
| 1816 | matchLength = ml2, offset = offset2, start = ip; |
| 1817 | continue; |
| 1818 | } |
| 1819 | } |
| 1820 | } |
| 1821 | break; /* nothing found : store previous solution */ |
| 1822 | } |
| 1823 | |
| 1824 | /* catch up */ |
| 1825 | if (offset) |
| 1826 | { |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 1827 | U32 matchIndex = (U32)((start-base) - offset); |
| 1828 | const BYTE* match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex; |
| 1829 | const BYTE* const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart; |
| 1830 | while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; } /* catch up */ |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1831 | offset_2 = offset_1; offset_1 = offset; |
| 1832 | } |
| 1833 | |
| 1834 | /* store sequence */ |
| 1835 | _storeSequence: |
| 1836 | { |
| 1837 | size_t litLength = start - anchor; |
| 1838 | ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, matchLength-MINMATCH); |
| 1839 | anchor = ip = start + matchLength; |
| 1840 | } |
| 1841 | |
| 1842 | /* check immediate repcode */ |
| 1843 | while (ip <= ilimit) |
| 1844 | { |
| 1845 | const U32 repIndex = (U32)((ip-base) - offset_2); |
| 1846 | const BYTE* const repBase = repIndex < dictLimit ? dictBase : base; |
| 1847 | const BYTE* const repMatch = repBase + repIndex; |
Yann Collet | 239cc28 | 2015-11-23 16:17:21 +0100 | [diff] [blame] | 1848 | if ((U32)((dictLimit-1) - repIndex) >= 3) /* intentional overflow */ |
Yann Collet | d7233d6 | 2015-11-22 14:40:51 +0100 | [diff] [blame] | 1849 | if (MEM_read32(ip) == MEM_read32(repMatch)) |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1850 | { |
| 1851 | /* repcode detected we should take it */ |
| 1852 | const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend; |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1853 | matchLength = ZSTD_count_2segments(ip+MINMATCH, repMatch+MINMATCH, iend, repEnd, prefixStart) + MINMATCH; |
| 1854 | offset = offset_2; offset_2 = offset_1; offset_1 = offset; /* swap offset history */ |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1855 | ZSTD_storeSeq(seqStorePtr, 0, anchor, 0, matchLength-MINMATCH); |
| 1856 | ip += matchLength; |
| 1857 | anchor = ip; |
| 1858 | continue; /* faster when present ... (?) */ |
| 1859 | } |
| 1860 | break; |
| 1861 | } |
| 1862 | } |
| 1863 | |
| 1864 | /* Last Literals */ |
| 1865 | { |
| 1866 | size_t lastLLSize = iend - anchor; |
| 1867 | memcpy(seqStorePtr->lit, anchor, lastLLSize); |
| 1868 | seqStorePtr->lit += lastLLSize; |
| 1869 | } |
| 1870 | |
| 1871 | /* Final compression stage */ |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1872 | return ZSTD_compressSequences(dst, maxDstSize, |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1873 | seqStorePtr, srcSize); |
| 1874 | } |
| 1875 | |
| 1876 | size_t ZSTD_compressBlock_greedy_extDict(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
| 1877 | { |
| 1878 | return ZSTD_compressBlock_lazy_extDict_generic(ctx, dst, maxDstSize, src, srcSize, 0, 0); |
| 1879 | } |
| 1880 | |
Yann Collet | b7fc88e | 2015-11-22 03:12:28 +0100 | [diff] [blame] | 1881 | size_t ZSTD_compressBlock_lazy_extDict(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
| 1882 | { |
| 1883 | return ZSTD_compressBlock_lazy_extDict_generic(ctx, dst, maxDstSize, src, srcSize, 0, 1); |
| 1884 | } |
Yann Collet | 9a24e59 | 2015-11-22 02:53:43 +0100 | [diff] [blame] | 1885 | |
Yann Collet | a85c77b | 2015-11-22 12:22:04 +0100 | [diff] [blame] | 1886 | size_t ZSTD_compressBlock_lazy2_extDict(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
| 1887 | { |
| 1888 | return ZSTD_compressBlock_lazy_extDict_generic(ctx, dst, maxDstSize, src, srcSize, 0, 2); |
| 1889 | } |
| 1890 | |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1891 | static size_t ZSTD_compressBlock_btlazy2_extDict(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1892 | { |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1893 | return ZSTD_compressBlock_lazy_extDict_generic(ctx, dst, maxDstSize, src, srcSize, 1, 2); |
Yann Collet | 5054ee0 | 2015-11-23 13:34:21 +0100 | [diff] [blame] | 1894 | } |
| 1895 | |
Yann Collet | 7a23179 | 2015-11-21 15:27:35 +0100 | [diff] [blame] | 1896 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1897 | typedef size_t (*ZSTD_blockCompressor) (ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize); |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1898 | |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1899 | static ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict) |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1900 | { |
Yann Collet | 7fe531e | 2015-11-29 02:38:09 +0100 | [diff] [blame] | 1901 | static const ZSTD_blockCompressor blockCompressor[2][5] = { |
| 1902 | { ZSTD_compressBlock_fast, ZSTD_compressBlock_greedy, ZSTD_compressBlock_lazy,ZSTD_compressBlock_lazy2, ZSTD_compressBlock_btlazy2 }, |
| 1903 | { ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_greedy_extDict, ZSTD_compressBlock_lazy_extDict,ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict } |
| 1904 | }; |
| 1905 | |
| 1906 | return blockCompressor[extDict][(U32)strat]; |
Yann Collet | 59d7063 | 2015-11-04 12:05:27 +0100 | [diff] [blame] | 1907 | } |
| 1908 | |
| 1909 | |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1910 | size_t ZSTD_compressBlock(ZSTD_CCtx* zc, void* dst, size_t maxDstSize, const void* src, size_t srcSize) |
Yann Collet | be2010e | 2015-10-31 12:57:14 +0100 | [diff] [blame] | 1911 | { |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1912 | ZSTD_blockCompressor blockCompressor = ZSTD_selectBlockCompressor(zc->params.strategy, zc->lowLimit < zc->dictLimit); |
Yann Collet | 7dfd56b | 2015-11-19 17:46:29 +0100 | [diff] [blame] | 1913 | if (srcSize < MIN_CBLOCK_SIZE+3) return 0; /* don't even attempt compression below a certain srcSize */ |
Yann Collet | 03526e1 | 2015-11-23 15:29:15 +0100 | [diff] [blame] | 1914 | return blockCompressor(zc, dst, maxDstSize, src, srcSize); |
Yann Collet | be2010e | 2015-10-31 12:57:14 +0100 | [diff] [blame] | 1915 | } |
| 1916 | |
| 1917 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 1918 | static size_t ZSTD_compress_generic (ZSTD_CCtx* ctxPtr, |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1919 | void* dst, size_t maxDstSize, |
| 1920 | const void* src, size_t srcSize) |
| 1921 | { |
Yann Collet | 3e35827 | 2015-11-04 18:19:39 +0100 | [diff] [blame] | 1922 | size_t blockSize = BLOCKSIZE; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1923 | size_t remaining = srcSize; |
| 1924 | const BYTE* ip = (const BYTE*)src; |
| 1925 | BYTE* const ostart = (BYTE*)dst; |
| 1926 | BYTE* op = ostart; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1927 | const U32 maxDist = 1 << ctxPtr->params.windowLog; |
Yann Collet | 9b11b46 | 2015-11-01 12:40:22 +0100 | [diff] [blame] | 1928 | |
Yann Collet | 3e35827 | 2015-11-04 18:19:39 +0100 | [diff] [blame] | 1929 | while (remaining) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1930 | { |
Yann Collet | 3e35827 | 2015-11-04 18:19:39 +0100 | [diff] [blame] | 1931 | size_t cSize; |
| 1932 | |
Yann Collet | 3137d1a | 2015-11-04 23:36:36 +0100 | [diff] [blame] | 1933 | if (maxDstSize < 3 + MIN_CBLOCK_SIZE) return ERROR(dstSize_tooSmall); /* not enough space to store compressed block */ |
Yann Collet | 3e35827 | 2015-11-04 18:19:39 +0100 | [diff] [blame] | 1934 | if (remaining < blockSize) blockSize = remaining; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1935 | |
| 1936 | if ((U32)(ip+blockSize - (ctxPtr->base + ctxPtr->lowLimit)) > maxDist) |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 1937 | { |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1938 | /* respect windowLog contract */ |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 1939 | ctxPtr->lowLimit = (U32)(ip+blockSize - ctxPtr->base) - maxDist; |
| 1940 | if (ctxPtr->dictLimit < ctxPtr->lowLimit) ctxPtr->dictLimit = ctxPtr->lowLimit; |
| 1941 | } |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1942 | |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1943 | cSize = ZSTD_compressBlock(ctxPtr, op+3, maxDstSize-3, ip, blockSize); |
Yann Collet | 3e35827 | 2015-11-04 18:19:39 +0100 | [diff] [blame] | 1944 | if (ZSTD_isError(cSize)) return cSize; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1945 | |
| 1946 | if (cSize == 0) |
| 1947 | { |
| 1948 | cSize = ZSTD_noCompressBlock(op, maxDstSize, ip, blockSize); /* block is not compressible */ |
| 1949 | } |
| 1950 | else |
| 1951 | { |
| 1952 | op[0] = (BYTE)(cSize>>16); |
| 1953 | op[1] = (BYTE)(cSize>>8); |
| 1954 | op[2] = (BYTE)cSize; |
Yann Collet | c95f899 | 2015-11-19 17:28:35 +0100 | [diff] [blame] | 1955 | op[0] += (BYTE)(bt_compressed << 6); /* is a compressed block */ |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1956 | cSize += 3; |
| 1957 | } |
| 1958 | |
| 1959 | remaining -= blockSize; |
Yann Collet | 3e35827 | 2015-11-04 18:19:39 +0100 | [diff] [blame] | 1960 | maxDstSize -= cSize; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1961 | ip += blockSize; |
| 1962 | op += cSize; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1963 | } |
| 1964 | |
| 1965 | return op-ostart; |
| 1966 | } |
| 1967 | |
| 1968 | |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 1969 | size_t ZSTD_compressContinue (ZSTD_CCtx* zc, |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 1970 | void* dst, size_t dstSize, |
| 1971 | const void* src, size_t srcSize) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1972 | { |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 1973 | const BYTE* const ip = (const BYTE*) src; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1974 | |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1975 | /* preemptive overflow correction */ |
Yann Collet | 3757273 | 2015-11-29 03:17:04 +0100 | [diff] [blame^] | 1976 | if ((zc->base > (const BYTE*)src) || (zc->lowLimit > (1<<30) )) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1977 | { |
Yann Collet | 7fe531e | 2015-11-29 02:38:09 +0100 | [diff] [blame] | 1978 | U32 correction = zc->lowLimit-1; |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 1979 | ZSTD_reduceIndex(zc, correction); |
| 1980 | zc->base += correction; |
| 1981 | zc->dictBase += correction; |
| 1982 | zc->lowLimit -= correction; |
| 1983 | zc->dictLimit -= correction; |
| 1984 | if (zc->nextToUpdate < correction) zc->nextToUpdate = 0; |
| 1985 | else zc->nextToUpdate -= correction; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 1986 | } |
| 1987 | |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1988 | /* Check if blocks follow each other */ |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 1989 | if (src != zc->nextSrc) |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1990 | { |
| 1991 | /* not contiguous */ |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 1992 | zc->lowLimit = zc->dictLimit; |
| 1993 | zc->dictLimit = (U32)(zc->nextSrc - zc->base); |
| 1994 | zc->dictBase = zc->base; |
| 1995 | zc->base += ip - zc->nextSrc; |
| 1996 | zc->nextToUpdate = zc->dictLimit; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 1997 | } |
| 1998 | |
| 1999 | /* input-dictionary overlap */ |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 2000 | if ((ip+srcSize > zc->dictBase + zc->lowLimit) && (ip < zc->dictBase + zc->dictLimit)) |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 2001 | { |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 2002 | zc->lowLimit = (U32)(ip + srcSize - zc->dictBase); |
| 2003 | if (zc->lowLimit > zc->dictLimit) zc->lowLimit = zc->dictLimit; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 2004 | } |
| 2005 | |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 2006 | zc->nextSrc = ip + srcSize; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 2007 | |
Yann Collet | c365215 | 2015-11-24 14:06:07 +0100 | [diff] [blame] | 2008 | return ZSTD_compress_generic (zc, dst, dstSize, src, srcSize); |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2009 | } |
| 2010 | |
| 2011 | |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 2012 | /** ZSTD_compressBegin_advanced |
| 2013 | * Write frame header, according to params |
| 2014 | * @return : nb of bytes written */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2015 | size_t ZSTD_compressBegin_advanced(ZSTD_CCtx* ctx, |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 2016 | void* dst, size_t maxDstSize, |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 2017 | ZSTD_parameters params) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2018 | { |
Yann Collet | 4114f95 | 2015-10-30 06:40:22 +0100 | [diff] [blame] | 2019 | size_t errorCode; |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 2020 | |
| 2021 | ZSTD_validateParams(¶ms); |
| 2022 | |
| 2023 | if (maxDstSize < ZSTD_frameHeaderSize_max) return ERROR(dstSize_tooSmall); |
| 2024 | errorCode = ZSTD_resetCCtx_advanced(ctx, params); |
Yann Collet | 4114f95 | 2015-10-30 06:40:22 +0100 | [diff] [blame] | 2025 | if (ZSTD_isError(errorCode)) return errorCode; |
Yann Collet | 89db5e0 | 2015-11-13 11:27:46 +0100 | [diff] [blame] | 2026 | |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 2027 | MEM_writeLE32(dst, ZSTD_MAGICNUMBER); /* Write Header */ |
| 2028 | ((BYTE*)dst)[4] = (BYTE)(params.windowLog - ZSTD_WINDOWLOG_ABSOLUTEMIN); |
| 2029 | return ZSTD_frameHeaderSize_min; |
| 2030 | } |
| 2031 | |
| 2032 | |
| 2033 | /** ZSTD_getParams |
| 2034 | * return ZSTD_parameters structure for a selected compression level and srcSize. |
| 2035 | * srcSizeHint value is optional, select 0 if not known */ |
| 2036 | ZSTD_parameters ZSTD_getParams(int compressionLevel, U64 srcSizeHint) |
| 2037 | { |
| 2038 | ZSTD_parameters result; |
| 2039 | int tableID = ((srcSizeHint-1) <= 128 KB); /* intentional underflow for srcSizeHint == 0 */ |
| 2040 | if (compressionLevel<=0) compressionLevel = 1; |
| 2041 | if (compressionLevel > ZSTD_MAX_CLEVEL) compressionLevel = ZSTD_MAX_CLEVEL; |
| 2042 | result = ZSTD_defaultParameters[tableID][compressionLevel]; |
| 2043 | result.srcSize = srcSizeHint; |
| 2044 | return result; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2045 | } |
| 2046 | |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 2047 | |
Yann Collet | 26fa696 | 2015-11-26 16:07:08 +0100 | [diff] [blame] | 2048 | size_t ZSTD_compressBegin(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, int compressionLevel) |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 2049 | { |
Yann Collet | 26fa696 | 2015-11-26 16:07:08 +0100 | [diff] [blame] | 2050 | return ZSTD_compressBegin_advanced(ctx, dst, maxDstSize, ZSTD_getParams(compressionLevel, 0)); |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 2051 | } |
| 2052 | |
| 2053 | |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 2054 | /** ZSTD_compressEnd |
| 2055 | * Write frame epilogue |
| 2056 | * @return : nb of bytes written into dst (or an error code) */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2057 | size_t ZSTD_compressEnd(ZSTD_CCtx* ctx, void* dst, size_t maxDstSize) |
Yann Collet | 2acb5d3 | 2015-10-29 16:49:43 +0100 | [diff] [blame] | 2058 | { |
| 2059 | BYTE* op = (BYTE*)dst; |
| 2060 | |
| 2061 | /* Sanity check */ |
| 2062 | (void)ctx; |
| 2063 | if (maxDstSize < 3) return ERROR(dstSize_tooSmall); |
| 2064 | |
| 2065 | /* End of frame */ |
| 2066 | op[0] = (BYTE)(bt_end << 6); |
| 2067 | op[1] = 0; |
| 2068 | op[2] = 0; |
| 2069 | |
| 2070 | return 3; |
| 2071 | } |
| 2072 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2073 | size_t ZSTD_compress_advanced (ZSTD_CCtx* ctx, |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 2074 | void* dst, size_t maxDstSize, |
| 2075 | const void* src, size_t srcSize, |
| 2076 | ZSTD_parameters params) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2077 | { |
| 2078 | BYTE* const ostart = (BYTE*)dst; |
| 2079 | BYTE* op = ostart; |
Yann Collet | 4114f95 | 2015-10-30 06:40:22 +0100 | [diff] [blame] | 2080 | size_t oSize; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2081 | |
| 2082 | /* Header */ |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 2083 | oSize = ZSTD_compressBegin_advanced(ctx, dst, maxDstSize, params); |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2084 | if(ZSTD_isError(oSize)) return oSize; |
| 2085 | op += oSize; |
| 2086 | maxDstSize -= oSize; |
| 2087 | |
| 2088 | /* body (compression) */ |
Yann Collet | 3d9cf7a | 2015-10-29 17:15:14 +0100 | [diff] [blame] | 2089 | ctx->base = (const BYTE*)src; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2090 | oSize = ZSTD_compress_generic (ctx, op, maxDstSize, src, srcSize); |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2091 | if(ZSTD_isError(oSize)) return oSize; |
| 2092 | op += oSize; |
| 2093 | maxDstSize -= oSize; |
| 2094 | |
| 2095 | /* Close frame */ |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2096 | oSize = ZSTD_compressEnd(ctx, op, maxDstSize); |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2097 | if(ZSTD_isError(oSize)) return oSize; |
| 2098 | op += oSize; |
| 2099 | |
| 2100 | return (op - ostart); |
| 2101 | } |
| 2102 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2103 | size_t ZSTD_compressCCtx (ZSTD_CCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize, int compressionLevel) |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 2104 | { |
Yann Collet | 88fcd29 | 2015-11-25 14:42:45 +0100 | [diff] [blame] | 2105 | return ZSTD_compress_advanced(ctx, dst, maxDstSize, src, srcSize, ZSTD_getParams(compressionLevel, srcSize)); |
Yann Collet | 083fcc8 | 2015-10-25 14:06:35 +0100 | [diff] [blame] | 2106 | } |
| 2107 | |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2108 | size_t ZSTD_compress(void* dst, size_t maxDstSize, const void* src, size_t srcSize, int compressionLevel) |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2109 | { |
Yann Collet | 44fe991 | 2015-10-29 22:02:40 +0100 | [diff] [blame] | 2110 | size_t result; |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2111 | ZSTD_CCtx ctxBody; |
Yann Collet | 712def9 | 2015-10-29 18:41:45 +0100 | [diff] [blame] | 2112 | memset(&ctxBody, 0, sizeof(ctxBody)); |
Yann Collet | 5be2dd2 | 2015-11-11 13:43:58 +0100 | [diff] [blame] | 2113 | result = ZSTD_compressCCtx(&ctxBody, dst, maxDstSize, src, srcSize, compressionLevel); |
Yann Collet | 26fa696 | 2015-11-26 16:07:08 +0100 | [diff] [blame] | 2114 | free(ctxBody.workSpace); /* can't free ctxBody, since it's on stack; free heap content */ |
Yann Collet | 44fe991 | 2015-10-29 22:02:40 +0100 | [diff] [blame] | 2115 | return result; |
Yann Collet | f3eca25 | 2015-10-22 15:31:46 +0100 | [diff] [blame] | 2116 | } |