1 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0-only 2 /* ****************************************************************** 3 * Huffman encoder, part of New Generation Entropy library 4 * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc. 5 * 6 * You can contact the author at : 7 * - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy 8 * - Public forum : https://groups.google.com/forum/#!forum/lz4c 9 * 10 * This source code is licensed under both the BSD-style license (found in the 11 * LICENSE file in the root directory of this source tree) and the GPLv2 (found 12 * in the COPYING file in the root directory of this source tree). 13 * You may select, at your option, one of the above-listed licenses. 14 ****************************************************************** */ 15 16 /* ************************************************************** 17 * Compiler specifics 18 ****************************************************************/ 19 #ifdef _MSC_VER /* Visual Studio */ 20 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 21 #endif 22 23 24 /* ************************************************************** 25 * Includes 26 ****************************************************************/ 27 #include <string.h> /* memcpy, memset */ 28 #include <stdio.h> /* printf (debug) */ 29 #include "../common/compiler.h" 30 #include "../common/bitstream.h" 31 #include "hist.h" 32 #define FSE_STATIC_LINKING_ONLY /* FSE_optimalTableLog_internal */ 33 #include "../common/fse.h" /* header compression */ 34 #define HUF_STATIC_LINKING_ONLY 35 #include "../common/huf.h" 36 #include "../common/error_private.h" 37 38 39 /* ************************************************************** 40 * Error Management 41 ****************************************************************/ 42 #define HUF_isError ERR_isError 43 #define HUF_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */ 44 45 46 /* ************************************************************** 47 * Utils 48 ****************************************************************/ 49 unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue) 50 { 51 return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 1); 52 } 53 54 55 /* ******************************************************* 56 * HUF : Huffman block compression 57 *********************************************************/ 58 /* HUF_compressWeights() : 59 * Same as FSE_compress(), but dedicated to huff0's weights compression. 60 * The use case needs much less stack memory. 61 * Note : all elements within weightTable are supposed to be <= HUF_TABLELOG_MAX. 62 */ 63 #define MAX_FSE_TABLELOG_FOR_HUFF_HEADER 6 64 static size_t HUF_compressWeights (void* dst, size_t dstSize, const void* weightTable, size_t wtSize) 65 { 66 BYTE* const ostart = (BYTE*) dst; 67 BYTE* op = ostart; 68 BYTE* const oend = ostart + dstSize; 69 70 unsigned maxSymbolValue = HUF_TABLELOG_MAX; 71 U32 tableLog = MAX_FSE_TABLELOG_FOR_HUFF_HEADER; 72 73 FSE_CTable CTable[FSE_CTABLE_SIZE_U32(MAX_FSE_TABLELOG_FOR_HUFF_HEADER, HUF_TABLELOG_MAX)]; 74 BYTE scratchBuffer[1<<MAX_FSE_TABLELOG_FOR_HUFF_HEADER]; 75 76 unsigned count[HUF_TABLELOG_MAX+1]; 77 S16 norm[HUF_TABLELOG_MAX+1]; 78 79 /* init conditions */ 80 if (wtSize <= 1) return 0; /* Not compressible */ 81 82 /* Scan input and build symbol stats */ 83 { unsigned const maxCount = HIST_count_simple(count, &maxSymbolValue, weightTable, wtSize); /* never fails */ 84 if (maxCount == wtSize) return 1; /* only a single symbol in src : rle */ 85 if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */ 86 } 87 88 tableLog = FSE_optimalTableLog(tableLog, wtSize, maxSymbolValue); 89 CHECK_F( FSE_normalizeCount(norm, tableLog, count, wtSize, maxSymbolValue) ); 90 91 /* Write table description header */ 92 { CHECK_V_F(hSize, FSE_writeNCount(op, (size_t)(oend-op), norm, maxSymbolValue, tableLog) ); 93 op += hSize; 94 } 95 96 /* Compress */ 97 CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, sizeof(scratchBuffer)) ); 98 { CHECK_V_F(cSize, FSE_compress_usingCTable(op, (size_t)(oend - op), weightTable, wtSize, CTable) ); 99 if (cSize == 0) return 0; /* not enough space for compressed data */ 100 op += cSize; 101 } 102 103 return (size_t)(op-ostart); 104 } 105 106 107 struct HUF_CElt_s { 108 U16 val; 109 BYTE nbBits; 110 }; /* typedef'd to HUF_CElt within "huf.h" */ 111 112 /*! HUF_writeCTable() : 113 `CTable` : Huffman tree to save, using huf representation. 114 @return : size of saved CTable */ 115 size_t HUF_writeCTable (void* dst, size_t maxDstSize, 116 const HUF_CElt* CTable, unsigned maxSymbolValue, unsigned huffLog) 117 { 118 BYTE bitsToWeight[HUF_TABLELOG_MAX + 1]; /* precomputed conversion table */ 119 BYTE huffWeight[HUF_SYMBOLVALUE_MAX]; 120 BYTE* op = (BYTE*)dst; 121 U32 n; 122 123 /* check conditions */ 124 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge); 125 126 /* convert to weight */ 127 bitsToWeight[0] = 0; 128 for (n=1; n<huffLog+1; n++) 129 bitsToWeight[n] = (BYTE)(huffLog + 1 - n); 130 for (n=0; n<maxSymbolValue; n++) 131 huffWeight[n] = bitsToWeight[CTable[n].nbBits]; 132 133 /* attempt weights compression by FSE */ 134 { CHECK_V_F(hSize, HUF_compressWeights(op+1, maxDstSize-1, huffWeight, maxSymbolValue) ); 135 if ((hSize>1) & (hSize < maxSymbolValue/2)) { /* FSE compressed */ 136 op[0] = (BYTE)hSize; 137 return hSize+1; 138 } } 139 140 /* write raw values as 4-bits (max : 15) */ 141 if (maxSymbolValue > (256-128)) return ERROR(GENERIC); /* should not happen : likely means source cannot be compressed */ 142 if (((maxSymbolValue+1)/2) + 1 > maxDstSize) return ERROR(dstSize_tooSmall); /* not enough space within dst buffer */ 143 op[0] = (BYTE)(128 /*special case*/ + (maxSymbolValue-1)); 144 huffWeight[maxSymbolValue] = 0; /* to be sure it doesn't cause msan issue in final combination */ 145 for (n=0; n<maxSymbolValue; n+=2) 146 op[(n/2)+1] = (BYTE)((huffWeight[n] << 4) + huffWeight[n+1]); 147 return ((maxSymbolValue+1)/2) + 1; 148 } 149 150 151 size_t HUF_readCTable (HUF_CElt* CTable, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize, unsigned* hasZeroWeights) 152 { 153 BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1]; /* init not required, even though some static analyzer may complain */ 154 U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */ 155 U32 tableLog = 0; 156 U32 nbSymbols = 0; 157 158 /* get symbol weights */ 159 CHECK_V_F(readSize, HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize)); 160 161 /* check result */ 162 if (tableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge); 163 if (nbSymbols > *maxSymbolValuePtr+1) return ERROR(maxSymbolValue_tooSmall); 164 165 /* Prepare base value per rank */ 166 { U32 n, nextRankStart = 0; 167 for (n=1; n<=tableLog; n++) { 168 U32 current = nextRankStart; 169 nextRankStart += (rankVal[n] << (n-1)); 170 rankVal[n] = current; 171 } } 172 173 /* fill nbBits */ 174 *hasZeroWeights = 0; 175 { U32 n; for (n=0; n<nbSymbols; n++) { 176 const U32 w = huffWeight[n]; 177 *hasZeroWeights |= (w == 0); 178 CTable[n].nbBits = (BYTE)(tableLog + 1 - w) & -(w != 0); 179 } } 180 181 /* fill val */ 182 { U16 nbPerRank[HUF_TABLELOG_MAX+2] = {0}; /* support w=0=>n=tableLog+1 */ 183 U16 valPerRank[HUF_TABLELOG_MAX+2] = {0}; 184 { U32 n; for (n=0; n<nbSymbols; n++) nbPerRank[CTable[n].nbBits]++; } 185 /* determine stating value per rank */ 186 valPerRank[tableLog+1] = 0; /* for w==0 */ 187 { U16 min = 0; 188 U32 n; for (n=tableLog; n>0; n--) { /* start at n=tablelog <-> w=1 */ 189 valPerRank[n] = min; /* get starting value within each rank */ 190 min += nbPerRank[n]; 191 min >>= 1; 192 } } 193 /* assign value within rank, symbol order */ 194 { U32 n; for (n=0; n<nbSymbols; n++) CTable[n].val = valPerRank[CTable[n].nbBits]++; } 195 } 196 197 *maxSymbolValuePtr = nbSymbols - 1; 198 return readSize; 199 } 200 201 U32 HUF_getNbBits(const void* symbolTable, U32 symbolValue) 202 { 203 const HUF_CElt* table = (const HUF_CElt*)symbolTable; 204 assert(symbolValue <= HUF_SYMBOLVALUE_MAX); 205 return table[symbolValue].nbBits; 206 } 207 208 209 typedef struct nodeElt_s { 210 U32 count; 211 U16 parent; 212 BYTE byte; 213 BYTE nbBits; 214 } nodeElt; 215 216 static U32 HUF_setMaxHeight(nodeElt* huffNode, U32 lastNonNull, U32 maxNbBits) 217 { 218 const U32 largestBits = huffNode[lastNonNull].nbBits; 219 if (largestBits <= maxNbBits) return largestBits; /* early exit : no elt > maxNbBits */ 220 221 /* there are several too large elements (at least >= 2) */ 222 { int totalCost = 0; 223 const U32 baseCost = 1 << (largestBits - maxNbBits); 224 int n = (int)lastNonNull; 225 226 while (huffNode[n].nbBits > maxNbBits) { 227 totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits)); 228 huffNode[n].nbBits = (BYTE)maxNbBits; 229 n --; 230 } /* n stops at huffNode[n].nbBits <= maxNbBits */ 231 while (huffNode[n].nbBits == maxNbBits) n--; /* n end at index of smallest symbol using < maxNbBits */ 232 233 /* renorm totalCost */ 234 totalCost >>= (largestBits - maxNbBits); /* note : totalCost is necessarily a multiple of baseCost */ 235 236 /* repay normalized cost */ 237 { U32 const noSymbol = 0xF0F0F0F0; 238 U32 rankLast[HUF_TABLELOG_MAX+2]; 239 240 /* Get pos of last (smallest) symbol per rank */ 241 memset(rankLast, 0xF0, sizeof(rankLast)); 242 { U32 currentNbBits = maxNbBits; 243 int pos; 244 for (pos=n ; pos >= 0; pos--) { 245 if (huffNode[pos].nbBits >= currentNbBits) continue; 246 currentNbBits = huffNode[pos].nbBits; /* < maxNbBits */ 247 rankLast[maxNbBits-currentNbBits] = (U32)pos; 248 } } 249 250 while (totalCost > 0) { 251 U32 nBitsToDecrease = BIT_highbit32((U32)totalCost) + 1; 252 for ( ; nBitsToDecrease > 1; nBitsToDecrease--) { 253 U32 const highPos = rankLast[nBitsToDecrease]; 254 U32 const lowPos = rankLast[nBitsToDecrease-1]; 255 if (highPos == noSymbol) continue; 256 if (lowPos == noSymbol) break; 257 { U32 const highTotal = huffNode[highPos].count; 258 U32 const lowTotal = 2 * huffNode[lowPos].count; 259 if (highTotal <= lowTotal) break; 260 } } 261 /* only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !) */ 262 /* HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary */ 263 while ((nBitsToDecrease<=HUF_TABLELOG_MAX) && (rankLast[nBitsToDecrease] == noSymbol)) 264 nBitsToDecrease ++; 265 totalCost -= 1 << (nBitsToDecrease-1); 266 if (rankLast[nBitsToDecrease-1] == noSymbol) 267 rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease]; /* this rank is no longer empty */ 268 huffNode[rankLast[nBitsToDecrease]].nbBits ++; 269 if (rankLast[nBitsToDecrease] == 0) /* special case, reached largest symbol */ 270 rankLast[nBitsToDecrease] = noSymbol; 271 else { 272 rankLast[nBitsToDecrease]--; 273 if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease) 274 rankLast[nBitsToDecrease] = noSymbol; /* this rank is now empty */ 275 } } /* while (totalCost > 0) */ 276 277 while (totalCost < 0) { /* Sometimes, cost correction overshoot */ 278 if (rankLast[1] == noSymbol) { /* special case : no rank 1 symbol (using maxNbBits-1); let's create one from largest rank 0 (using maxNbBits) */ 279 while (huffNode[n].nbBits == maxNbBits) n--; 280 huffNode[n+1].nbBits--; 281 assert(n >= 0); 282 rankLast[1] = (U32)(n+1); 283 totalCost++; 284 continue; 285 } 286 huffNode[ rankLast[1] + 1 ].nbBits--; 287 rankLast[1]++; 288 totalCost ++; 289 } } } /* there are several too large elements (at least >= 2) */ 290 291 return maxNbBits; 292 } 293 294 typedef struct { 295 U32 base; 296 U32 current; 297 } rankPos; 298 299 typedef nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]; 300 301 #define RANK_POSITION_TABLE_SIZE 32 302 303 typedef struct { 304 huffNodeTable huffNodeTbl; 305 rankPos rankPosition[RANK_POSITION_TABLE_SIZE]; 306 } HUF_buildCTable_wksp_tables; 307 308 static void HUF_sort(nodeElt* huffNode, const unsigned* count, U32 maxSymbolValue, rankPos* rankPosition) 309 { 310 U32 n; 311 312 memset(rankPosition, 0, sizeof(*rankPosition) * RANK_POSITION_TABLE_SIZE); 313 for (n=0; n<=maxSymbolValue; n++) { 314 U32 r = BIT_highbit32(count[n] + 1); 315 rankPosition[r].base ++; 316 } 317 for (n=30; n>0; n--) rankPosition[n-1].base += rankPosition[n].base; 318 for (n=0; n<32; n++) rankPosition[n].current = rankPosition[n].base; 319 for (n=0; n<=maxSymbolValue; n++) { 320 U32 const c = count[n]; 321 U32 const r = BIT_highbit32(c+1) + 1; 322 U32 pos = rankPosition[r].current++; 323 while ((pos > rankPosition[r].base) && (c > huffNode[pos-1].count)) { 324 huffNode[pos] = huffNode[pos-1]; 325 pos--; 326 } 327 huffNode[pos].count = c; 328 huffNode[pos].byte = (BYTE)n; 329 } 330 } 331 332 333 /** HUF_buildCTable_wksp() : 334 * Same as HUF_buildCTable(), but using externally allocated scratch buffer. 335 * `workSpace` must be aligned on 4-bytes boundaries, and be at least as large as sizeof(HUF_buildCTable_wksp_tables). 336 */ 337 #define STARTNODE (HUF_SYMBOLVALUE_MAX+1) 338 339 size_t HUF_buildCTable_wksp (HUF_CElt* tree, const unsigned* count, U32 maxSymbolValue, U32 maxNbBits, void* workSpace, size_t wkspSize) 340 { 341 HUF_buildCTable_wksp_tables* const wksp_tables = (HUF_buildCTable_wksp_tables*)workSpace; 342 nodeElt* const huffNode0 = wksp_tables->huffNodeTbl; 343 nodeElt* const huffNode = huffNode0+1; 344 int nonNullRank; 345 int lowS, lowN; 346 int nodeNb = STARTNODE; 347 int n, nodeRoot; 348 349 /* safety checks */ 350 if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */ 351 if (wkspSize < sizeof(HUF_buildCTable_wksp_tables)) 352 return ERROR(workSpace_tooSmall); 353 if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT; 354 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) 355 return ERROR(maxSymbolValue_tooLarge); 356 memset(huffNode0, 0, sizeof(huffNodeTable)); 357 358 /* sort, decreasing order */ 359 HUF_sort(huffNode, count, maxSymbolValue, wksp_tables->rankPosition); 360 361 /* init for parents */ 362 nonNullRank = (int)maxSymbolValue; 363 while(huffNode[nonNullRank].count == 0) nonNullRank--; 364 lowS = nonNullRank; nodeRoot = nodeNb + lowS - 1; lowN = nodeNb; 365 huffNode[nodeNb].count = huffNode[lowS].count + huffNode[lowS-1].count; 366 huffNode[lowS].parent = huffNode[lowS-1].parent = (U16)nodeNb; 367 nodeNb++; lowS-=2; 368 for (n=nodeNb; n<=nodeRoot; n++) huffNode[n].count = (U32)(1U<<30); 369 huffNode0[0].count = (U32)(1U<<31); /* fake entry, strong barrier */ 370 371 /* create parents */ 372 while (nodeNb <= nodeRoot) { 373 int const n1 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++; 374 int const n2 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++; 375 huffNode[nodeNb].count = huffNode[n1].count + huffNode[n2].count; 376 huffNode[n1].parent = huffNode[n2].parent = (U16)nodeNb; 377 nodeNb++; 378 } 379 380 /* distribute weights (unlimited tree height) */ 381 huffNode[nodeRoot].nbBits = 0; 382 for (n=nodeRoot-1; n>=STARTNODE; n--) 383 huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1; 384 for (n=0; n<=nonNullRank; n++) 385 huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1; 386 387 /* enforce maxTableLog */ 388 maxNbBits = HUF_setMaxHeight(huffNode, (U32)nonNullRank, maxNbBits); 389 390 /* fill result into tree (val, nbBits) */ 391 { U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0}; 392 U16 valPerRank[HUF_TABLELOG_MAX+1] = {0}; 393 int const alphabetSize = (int)(maxSymbolValue + 1); 394 if (maxNbBits > HUF_TABLELOG_MAX) return ERROR(GENERIC); /* check fit into table */ 395 for (n=0; n<=nonNullRank; n++) 396 nbPerRank[huffNode[n].nbBits]++; 397 /* determine stating value per rank */ 398 { U16 min = 0; 399 for (n=(int)maxNbBits; n>0; n--) { 400 valPerRank[n] = min; /* get starting value within each rank */ 401 min += nbPerRank[n]; 402 min >>= 1; 403 } } 404 for (n=0; n<alphabetSize; n++) 405 tree[huffNode[n].byte].nbBits = huffNode[n].nbBits; /* push nbBits per symbol, symbol order */ 406 for (n=0; n<alphabetSize; n++) 407 tree[n].val = valPerRank[tree[n].nbBits]++; /* assign value within rank, symbol order */ 408 } 409 410 return maxNbBits; 411 } 412 413 /** HUF_buildCTable() : 414 * @return : maxNbBits 415 * Note : count is used before tree is written, so they can safely overlap 416 */ 417 size_t HUF_buildCTable (HUF_CElt* tree, const unsigned* count, unsigned maxSymbolValue, unsigned maxNbBits) 418 { 419 HUF_buildCTable_wksp_tables workspace; 420 return HUF_buildCTable_wksp(tree, count, maxSymbolValue, maxNbBits, &workspace, sizeof(workspace)); 421 } 422 423 size_t HUF_estimateCompressedSize(const HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue) 424 { 425 size_t nbBits = 0; 426 int s; 427 for (s = 0; s <= (int)maxSymbolValue; ++s) { 428 nbBits += CTable[s].nbBits * count[s]; 429 } 430 return nbBits >> 3; 431 } 432 433 int HUF_validateCTable(const HUF_CElt* CTable, const unsigned* count, unsigned maxSymbolValue) { 434 int bad = 0; 435 int s; 436 for (s = 0; s <= (int)maxSymbolValue; ++s) { 437 bad |= (count[s] != 0) & (CTable[s].nbBits == 0); 438 } 439 return !bad; 440 } 441 442 size_t HUF_compressBound(size_t size) { return HUF_COMPRESSBOUND(size); } 443 444 FORCE_INLINE_TEMPLATE void 445 HUF_encodeSymbol(BIT_CStream_t* bitCPtr, U32 symbol, const HUF_CElt* CTable) 446 { 447 BIT_addBitsFast(bitCPtr, CTable[symbol].val, CTable[symbol].nbBits); 448 } 449 450 #define HUF_FLUSHBITS(s) BIT_flushBits(s) 451 452 #define HUF_FLUSHBITS_1(stream) \ 453 if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*2+7) HUF_FLUSHBITS(stream) 454 455 #define HUF_FLUSHBITS_2(stream) \ 456 if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*4+7) HUF_FLUSHBITS(stream) 457 458 FORCE_INLINE_TEMPLATE size_t 459 HUF_compress1X_usingCTable_internal_body(void* dst, size_t dstSize, 460 const void* src, size_t srcSize, 461 const HUF_CElt* CTable) 462 { 463 const BYTE* ip = (const BYTE*) src; 464 BYTE* const ostart = (BYTE*)dst; 465 BYTE* const oend = ostart + dstSize; 466 BYTE* op = ostart; 467 size_t n; 468 BIT_CStream_t bitC; 469 470 /* init */ 471 if (dstSize < 8) return 0; /* not enough space to compress */ 472 { size_t const initErr = BIT_initCStream(&bitC, op, (size_t)(oend-op)); 473 if (HUF_isError(initErr)) return 0; } 474 475 n = srcSize & ~3; /* join to mod 4 */ 476 switch (srcSize & 3) 477 { 478 case 3 : HUF_encodeSymbol(&bitC, ip[n+ 2], CTable); 479 HUF_FLUSHBITS_2(&bitC); 480 /* fall-through */ 481 case 2 : HUF_encodeSymbol(&bitC, ip[n+ 1], CTable); 482 HUF_FLUSHBITS_1(&bitC); 483 /* fall-through */ 484 case 1 : HUF_encodeSymbol(&bitC, ip[n+ 0], CTable); 485 HUF_FLUSHBITS(&bitC); 486 /* fall-through */ 487 case 0 : /* fall-through */ 488 default: break; 489 } 490 491 for (; n>0; n-=4) { /* note : n&3==0 at this stage */ 492 HUF_encodeSymbol(&bitC, ip[n- 1], CTable); 493 HUF_FLUSHBITS_1(&bitC); 494 HUF_encodeSymbol(&bitC, ip[n- 2], CTable); 495 HUF_FLUSHBITS_2(&bitC); 496 HUF_encodeSymbol(&bitC, ip[n- 3], CTable); 497 HUF_FLUSHBITS_1(&bitC); 498 HUF_encodeSymbol(&bitC, ip[n- 4], CTable); 499 HUF_FLUSHBITS(&bitC); 500 } 501 502 return BIT_closeCStream(&bitC); 503 } 504 505 #if DYNAMIC_BMI2 506 507 static TARGET_ATTRIBUTE("bmi2") size_t 508 HUF_compress1X_usingCTable_internal_bmi2(void* dst, size_t dstSize, 509 const void* src, size_t srcSize, 510 const HUF_CElt* CTable) 511 { 512 return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable); 513 } 514 515 static size_t 516 HUF_compress1X_usingCTable_internal_default(void* dst, size_t dstSize, 517 const void* src, size_t srcSize, 518 const HUF_CElt* CTable) 519 { 520 return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable); 521 } 522 523 static size_t 524 HUF_compress1X_usingCTable_internal(void* dst, size_t dstSize, 525 const void* src, size_t srcSize, 526 const HUF_CElt* CTable, const int bmi2) 527 { 528 if (bmi2) { 529 return HUF_compress1X_usingCTable_internal_bmi2(dst, dstSize, src, srcSize, CTable); 530 } 531 return HUF_compress1X_usingCTable_internal_default(dst, dstSize, src, srcSize, CTable); 532 } 533 534 #else 535 536 static size_t 537 HUF_compress1X_usingCTable_internal(void* dst, size_t dstSize, 538 const void* src, size_t srcSize, 539 const HUF_CElt* CTable, const int bmi2) 540 { 541 (void)bmi2; 542 return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable); 543 } 544 545 #endif 546 547 size_t HUF_compress1X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable) 548 { 549 return HUF_compress1X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0); 550 } 551 552 553 static size_t 554 HUF_compress4X_usingCTable_internal(void* dst, size_t dstSize, 555 const void* src, size_t srcSize, 556 const HUF_CElt* CTable, int bmi2) 557 { 558 size_t const segmentSize = (srcSize+3)/4; /* first 3 segments */ 559 const BYTE* ip = (const BYTE*) src; 560 const BYTE* const iend = ip + srcSize; 561 BYTE* const ostart = (BYTE*) dst; 562 BYTE* const oend = ostart + dstSize; 563 BYTE* op = ostart; 564 565 if (dstSize < 6 + 1 + 1 + 1 + 8) return 0; /* minimum space to compress successfully */ 566 if (srcSize < 12) return 0; /* no saving possible : too small input */ 567 op += 6; /* jumpTable */ 568 569 assert(op <= oend); 570 { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) ); 571 if (cSize==0) return 0; 572 assert(cSize <= 65535); 573 MEM_writeLE16(ostart, (U16)cSize); 574 op += cSize; 575 } 576 577 ip += segmentSize; 578 assert(op <= oend); 579 { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) ); 580 if (cSize==0) return 0; 581 assert(cSize <= 65535); 582 MEM_writeLE16(ostart+2, (U16)cSize); 583 op += cSize; 584 } 585 586 ip += segmentSize; 587 assert(op <= oend); 588 { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) ); 589 if (cSize==0) return 0; 590 assert(cSize <= 65535); 591 MEM_writeLE16(ostart+4, (U16)cSize); 592 op += cSize; 593 } 594 595 ip += segmentSize; 596 assert(op <= oend); 597 assert(ip <= iend); 598 { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, (size_t)(iend-ip), CTable, bmi2) ); 599 if (cSize==0) return 0; 600 op += cSize; 601 } 602 603 return (size_t)(op-ostart); 604 } 605 606 size_t HUF_compress4X_usingCTable(void* dst, size_t dstSize, const void* src, size_t srcSize, const HUF_CElt* CTable) 607 { 608 return HUF_compress4X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0); 609 } 610 611 typedef enum { HUF_singleStream, HUF_fourStreams } HUF_nbStreams_e; 612 613 static size_t HUF_compressCTable_internal( 614 BYTE* const ostart, BYTE* op, BYTE* const oend, 615 const void* src, size_t srcSize, 616 HUF_nbStreams_e nbStreams, const HUF_CElt* CTable, const int bmi2) 617 { 618 size_t const cSize = (nbStreams==HUF_singleStream) ? 619 HUF_compress1X_usingCTable_internal(op, (size_t)(oend - op), src, srcSize, CTable, bmi2) : 620 HUF_compress4X_usingCTable_internal(op, (size_t)(oend - op), src, srcSize, CTable, bmi2); 621 if (HUF_isError(cSize)) { return cSize; } 622 if (cSize==0) { return 0; } /* uncompressible */ 623 op += cSize; 624 /* check compressibility */ 625 assert(op >= ostart); 626 if ((size_t)(op-ostart) >= srcSize-1) { return 0; } 627 return (size_t)(op-ostart); 628 } 629 630 typedef struct { 631 unsigned count[HUF_SYMBOLVALUE_MAX + 1]; 632 HUF_CElt CTable[HUF_SYMBOLVALUE_MAX + 1]; 633 HUF_buildCTable_wksp_tables buildCTable_wksp; 634 } HUF_compress_tables_t; 635 636 /* HUF_compress_internal() : 637 * `workSpace` must a table of at least HUF_WORKSPACE_SIZE_U32 unsigned */ 638 static size_t 639 HUF_compress_internal (void* dst, size_t dstSize, 640 const void* src, size_t srcSize, 641 unsigned maxSymbolValue, unsigned huffLog, 642 HUF_nbStreams_e nbStreams, 643 void* workSpace, size_t wkspSize, 644 HUF_CElt* oldHufTable, HUF_repeat* repeat, int preferRepeat, 645 const int bmi2) 646 { 647 HUF_compress_tables_t* const table = (HUF_compress_tables_t*)workSpace; 648 BYTE* const ostart = (BYTE*)dst; 649 BYTE* const oend = ostart + dstSize; 650 BYTE* op = ostart; 651 652 HUF_STATIC_ASSERT(sizeof(*table) <= HUF_WORKSPACE_SIZE); 653 654 /* checks & inits */ 655 if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */ 656 if (wkspSize < HUF_WORKSPACE_SIZE) return ERROR(workSpace_tooSmall); 657 if (!srcSize) return 0; /* Uncompressed */ 658 if (!dstSize) return 0; /* cannot fit anything within dst budget */ 659 if (srcSize > HUF_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); /* current block size limit */ 660 if (huffLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge); 661 if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge); 662 if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX; 663 if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT; 664 665 /* Heuristic : If old table is valid, use it for small inputs */ 666 if (preferRepeat && repeat && *repeat == HUF_repeat_valid) { 667 return HUF_compressCTable_internal(ostart, op, oend, 668 src, srcSize, 669 nbStreams, oldHufTable, bmi2); 670 } 671 672 /* Scan input and build symbol stats */ 673 { CHECK_V_F(largest, HIST_count_wksp (table->count, &maxSymbolValue, (const BYTE*)src, srcSize, workSpace, wkspSize) ); 674 if (largest == srcSize) { *ostart = ((const BYTE*)src)[0]; return 1; } /* single symbol, rle */ 675 if (largest <= (srcSize >> 7)+4) return 0; /* heuristic : probably not compressible enough */ 676 } 677 678 /* Check validity of previous table */ 679 if ( repeat 680 && *repeat == HUF_repeat_check 681 && !HUF_validateCTable(oldHufTable, table->count, maxSymbolValue)) { 682 *repeat = HUF_repeat_none; 683 } 684 /* Heuristic : use existing table for small inputs */ 685 if (preferRepeat && repeat && *repeat != HUF_repeat_none) { 686 return HUF_compressCTable_internal(ostart, op, oend, 687 src, srcSize, 688 nbStreams, oldHufTable, bmi2); 689 } 690 691 /* Build Huffman Tree */ 692 huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue); 693 { size_t const maxBits = HUF_buildCTable_wksp(table->CTable, table->count, 694 maxSymbolValue, huffLog, 695 &table->buildCTable_wksp, sizeof(table->buildCTable_wksp)); 696 CHECK_F(maxBits); 697 huffLog = (U32)maxBits; 698 /* Zero unused symbols in CTable, so we can check it for validity */ 699 memset(table->CTable + (maxSymbolValue + 1), 0, 700 sizeof(table->CTable) - ((maxSymbolValue + 1) * sizeof(HUF_CElt))); 701 } 702 703 /* Write table description header */ 704 { CHECK_V_F(hSize, HUF_writeCTable (op, dstSize, table->CTable, maxSymbolValue, huffLog) ); 705 /* Check if using previous huffman table is beneficial */ 706 if (repeat && *repeat != HUF_repeat_none) { 707 size_t const oldSize = HUF_estimateCompressedSize(oldHufTable, table->count, maxSymbolValue); 708 size_t const newSize = HUF_estimateCompressedSize(table->CTable, table->count, maxSymbolValue); 709 if (oldSize <= hSize + newSize || hSize + 12 >= srcSize) { 710 return HUF_compressCTable_internal(ostart, op, oend, 711 src, srcSize, 712 nbStreams, oldHufTable, bmi2); 713 } } 714 715 /* Use the new huffman table */ 716 if (hSize + 12ul >= srcSize) { return 0; } 717 op += hSize; 718 if (repeat) { *repeat = HUF_repeat_none; } 719 if (oldHufTable) 720 memcpy(oldHufTable, table->CTable, sizeof(table->CTable)); /* Save new table */ 721 } 722 return HUF_compressCTable_internal(ostart, op, oend, 723 src, srcSize, 724 nbStreams, table->CTable, bmi2); 725 } 726 727 728 size_t HUF_compress1X_wksp (void* dst, size_t dstSize, 729 const void* src, size_t srcSize, 730 unsigned maxSymbolValue, unsigned huffLog, 731 void* workSpace, size_t wkspSize) 732 { 733 return HUF_compress_internal(dst, dstSize, src, srcSize, 734 maxSymbolValue, huffLog, HUF_singleStream, 735 workSpace, wkspSize, 736 NULL, NULL, 0, 0 /*bmi2*/); 737 } 738 739 size_t HUF_compress1X_repeat (void* dst, size_t dstSize, 740 const void* src, size_t srcSize, 741 unsigned maxSymbolValue, unsigned huffLog, 742 void* workSpace, size_t wkspSize, 743 HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat, int bmi2) 744 { 745 return HUF_compress_internal(dst, dstSize, src, srcSize, 746 maxSymbolValue, huffLog, HUF_singleStream, 747 workSpace, wkspSize, hufTable, 748 repeat, preferRepeat, bmi2); 749 } 750 751 size_t HUF_compress1X (void* dst, size_t dstSize, 752 const void* src, size_t srcSize, 753 unsigned maxSymbolValue, unsigned huffLog) 754 { 755 unsigned workSpace[HUF_WORKSPACE_SIZE_U32]; 756 return HUF_compress1X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace)); 757 } 758 759 /* HUF_compress4X_repeat(): 760 * compress input using 4 streams. 761 * provide workspace to generate compression tables */ 762 size_t HUF_compress4X_wksp (void* dst, size_t dstSize, 763 const void* src, size_t srcSize, 764 unsigned maxSymbolValue, unsigned huffLog, 765 void* workSpace, size_t wkspSize) 766 { 767 return HUF_compress_internal(dst, dstSize, src, srcSize, 768 maxSymbolValue, huffLog, HUF_fourStreams, 769 workSpace, wkspSize, 770 NULL, NULL, 0, 0 /*bmi2*/); 771 } 772 773 /* HUF_compress4X_repeat(): 774 * compress input using 4 streams. 775 * re-use an existing huffman compression table */ 776 size_t HUF_compress4X_repeat (void* dst, size_t dstSize, 777 const void* src, size_t srcSize, 778 unsigned maxSymbolValue, unsigned huffLog, 779 void* workSpace, size_t wkspSize, 780 HUF_CElt* hufTable, HUF_repeat* repeat, int preferRepeat, int bmi2) 781 { 782 return HUF_compress_internal(dst, dstSize, src, srcSize, 783 maxSymbolValue, huffLog, HUF_fourStreams, 784 workSpace, wkspSize, 785 hufTable, repeat, preferRepeat, bmi2); 786 } 787 788 size_t HUF_compress2 (void* dst, size_t dstSize, 789 const void* src, size_t srcSize, 790 unsigned maxSymbolValue, unsigned huffLog) 791 { 792 unsigned workSpace[HUF_WORKSPACE_SIZE_U32]; 793 return HUF_compress4X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace)); 794 } 795 796 size_t HUF_compress (void* dst, size_t maxDstSize, const void* src, size_t srcSize) 797 { 798 return HUF_compress2(dst, maxDstSize, src, srcSize, 255, HUF_TABLELOG_DEFAULT); 799 } 800