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