ReactOS  0.4.15-dev-5462-g4d0d22a
huf_compress.c File Reference
#include <string.h>
#include <stdio.h>
#include "compiler.h"
#include "bitstream.h"
#include "hist.h"
#include "fse.h"
#include "huf.h"
#include "error_private.h"
Include dependency graph for huf_compress.c:

Go to the source code of this file.

Classes

struct  HUF_CElt_s
 
struct  nodeElt_s
 
struct  rankPos
 
struct  HUF_buildCTable_wksp_tables
 
struct  HUF_compress_tables_t
 

Macros

#define FSE_STATIC_LINKING_ONLY   /* FSE_optimalTableLog_internal */
 
#define HUF_STATIC_LINKING_ONLY
 
#define HUF_isError   ERR_isError
 
#define HUF_STATIC_ASSERT(c)   DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
 
#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER   6
 
#define RANK_POSITION_TABLE_SIZE   32
 
#define STARTNODE   (HUF_SYMBOLVALUE_MAX+1)
 
#define HUF_FLUSHBITS(s)   BIT_flushBits(s)
 
#define HUF_FLUSHBITS_1(stream)   if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*2+7) HUF_FLUSHBITS(stream)
 
#define HUF_FLUSHBITS_2(stream)   if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*4+7) HUF_FLUSHBITS(stream)
 

Typedefs

typedef struct nodeElt_s nodeElt
 
typedef nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]
 

Enumerations

enum  HUF_nbStreams_e { HUF_singleStream, HUF_fourStreams }
 

Functions

unsigned HUF_optimalTableLog (unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
 
static size_t HUF_compressWeights (void *dst, size_t dstSize, const void *weightTable, size_t wtSize)
 
size_t HUF_writeCTable (void *dst, size_t maxDstSize, const HUF_CElt *CTable, unsigned maxSymbolValue, unsigned huffLog)
 
size_t HUF_readCTable (HUF_CElt *CTable, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize, unsigned *hasZeroWeights)
 
U32 HUF_getNbBits (const void *symbolTable, U32 symbolValue)
 
static U32 HUF_setMaxHeight (nodeElt *huffNode, U32 lastNonNull, U32 maxNbBits)
 
static void HUF_sort (nodeElt *huffNode, const unsigned *count, U32 maxSymbolValue, rankPos *rankPosition)
 
size_t HUF_buildCTable_wksp (HUF_CElt *tree, const unsigned *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
 
size_t HUF_buildCTable (HUF_CElt *tree, const unsigned *count, unsigned maxSymbolValue, unsigned maxNbBits)
 
size_t HUF_estimateCompressedSize (const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
 
int HUF_validateCTable (const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
 
size_t HUF_compressBound (size_t size)
 
FORCE_INLINE_TEMPLATE void HUF_encodeSymbol (BIT_CStream_t *bitCPtr, U32 symbol, const HUF_CElt *CTable)
 
FORCE_INLINE_TEMPLATE size_t HUF_compress1X_usingCTable_internal_body (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
 
static size_t HUF_compress1X_usingCTable_internal (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, const int bmi2)
 
size_t HUF_compress1X_usingCTable (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
 
static size_t HUF_compress4X_usingCTable_internal (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int bmi2)
 
size_t HUF_compress4X_usingCTable (void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
 
static size_t HUF_compressCTable_internal (BYTE *const ostart, BYTE *op, BYTE *const oend, const void *src, size_t srcSize, HUF_nbStreams_e nbStreams, const HUF_CElt *CTable, const int bmi2)
 
static size_t HUF_compress_internal (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, HUF_nbStreams_e nbStreams, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
 
size_t HUF_compress1X_wksp (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize)
 
size_t HUF_compress1X_repeat (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize, HUF_CElt *hufTable, HUF_repeat *repeat, int preferRepeat, int bmi2)
 
size_t HUF_compress1X (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
 
size_t HUF_compress4X_wksp (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize)
 
size_t HUF_compress4X_repeat (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize, HUF_CElt *hufTable, HUF_repeat *repeat, int preferRepeat, int bmi2)
 
size_t HUF_compress2 (void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
 
size_t HUF_compress (void *dst, size_t maxDstSize, const void *src, size_t srcSize)
 

Macro Definition Documentation

◆ FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY   /* FSE_optimalTableLog_internal */

Definition at line 31 of file huf_compress.c.

◆ HUF_FLUSHBITS

#define HUF_FLUSHBITS (   s)    BIT_flushBits(s)

Definition at line 449 of file huf_compress.c.

◆ HUF_FLUSHBITS_1

#define HUF_FLUSHBITS_1 (   stream)    if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*2+7) HUF_FLUSHBITS(stream)

Definition at line 451 of file huf_compress.c.

◆ HUF_FLUSHBITS_2

#define HUF_FLUSHBITS_2 (   stream)    if (sizeof((stream)->bitContainer)*8 < HUF_TABLELOG_MAX*4+7) HUF_FLUSHBITS(stream)

Definition at line 454 of file huf_compress.c.

◆ HUF_isError

#define HUF_isError   ERR_isError

Definition at line 41 of file huf_compress.c.

◆ HUF_STATIC_ASSERT

#define HUF_STATIC_ASSERT (   c)    DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */

Definition at line 42 of file huf_compress.c.

◆ HUF_STATIC_LINKING_ONLY

#define HUF_STATIC_LINKING_ONLY

Definition at line 33 of file huf_compress.c.

◆ MAX_FSE_TABLELOG_FOR_HUFF_HEADER

#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER   6

Definition at line 62 of file huf_compress.c.

◆ RANK_POSITION_TABLE_SIZE

#define RANK_POSITION_TABLE_SIZE   32

Definition at line 300 of file huf_compress.c.

◆ STARTNODE

#define STARTNODE   (HUF_SYMBOLVALUE_MAX+1)

HUF_buildCTable_wksp() : Same as HUF_buildCTable(), but using externally allocated scratch buffer. workSpace must be aligned on 4-bytes boundaries, and be at least as large as sizeof(HUF_buildCTable_wksp_tables).

Definition at line 336 of file huf_compress.c.

Typedef Documentation

◆ huffNodeTable

typedef nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]

Definition at line 298 of file huf_compress.c.

◆ nodeElt

Enumeration Type Documentation

◆ HUF_nbStreams_e

Enumerator
HUF_singleStream 
HUF_fourStreams 

Definition at line 610 of file huf_compress.c.

Function Documentation

◆ HUF_buildCTable()

size_t HUF_buildCTable ( HUF_CElt *  tree,
const unsigned count,
unsigned  maxSymbolValue,
unsigned  maxNbBits 
)

HUF_buildCTable() :

Returns
: maxNbBits Note : count is used before tree is written, so they can safely overlap

Definition at line 416 of file huf_compress.c.

417 {
418  HUF_buildCTable_wksp_tables workspace;
419  return HUF_buildCTable_wksp(tree, count, maxSymbolValue, maxNbBits, &workspace, sizeof(workspace));
420 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
size_t HUF_buildCTable_wksp(HUF_CElt *tree, const unsigned *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
Definition: huf_compress.c:338

◆ HUF_buildCTable_wksp()

size_t HUF_buildCTable_wksp ( HUF_CElt *  tree,
const unsigned count,
U32  maxSymbolValue,
U32  maxNbBits,
void workSpace,
size_t  wkspSize 
)

Definition at line 338 of file huf_compress.c.

339 {
340  HUF_buildCTable_wksp_tables* const wksp_tables = (HUF_buildCTable_wksp_tables*)workSpace;
341  nodeElt* const huffNode0 = wksp_tables->huffNodeTbl;
342  nodeElt* const huffNode = huffNode0+1;
343  int nonNullRank;
344  int lowS, lowN;
345  int nodeNb = STARTNODE;
346  int n, nodeRoot;
347 
348  /* safety checks */
349  if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
350  if (wkspSize < sizeof(HUF_buildCTable_wksp_tables))
351  return ERROR(workSpace_tooSmall);
352  if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT;
353  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX)
354  return ERROR(maxSymbolValue_tooLarge);
355  memset(huffNode0, 0, sizeof(huffNodeTable));
356 
357  /* sort, decreasing order */
358  HUF_sort(huffNode, count, maxSymbolValue, wksp_tables->rankPosition);
359 
360  /* init for parents */
361  nonNullRank = (int)maxSymbolValue;
362  while(huffNode[nonNullRank].count == 0) nonNullRank--;
363  lowS = nonNullRank; nodeRoot = nodeNb + lowS - 1; lowN = nodeNb;
364  huffNode[nodeNb].count = huffNode[lowS].count + huffNode[lowS-1].count;
365  huffNode[lowS].parent = huffNode[lowS-1].parent = (U16)nodeNb;
366  nodeNb++; lowS-=2;
367  for (n=nodeNb; n<=nodeRoot; n++) huffNode[n].count = (U32)(1U<<30);
368  huffNode0[0].count = (U32)(1U<<31); /* fake entry, strong barrier */
369 
370  /* create parents */
371  while (nodeNb <= nodeRoot) {
372  int const n1 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
373  int const n2 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
374  huffNode[nodeNb].count = huffNode[n1].count + huffNode[n2].count;
375  huffNode[n1].parent = huffNode[n2].parent = (U16)nodeNb;
376  nodeNb++;
377  }
378 
379  /* distribute weights (unlimited tree height) */
380  huffNode[nodeRoot].nbBits = 0;
381  for (n=nodeRoot-1; n>=STARTNODE; n--)
382  huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
383  for (n=0; n<=nonNullRank; n++)
384  huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
385 
386  /* enforce maxTableLog */
387  maxNbBits = HUF_setMaxHeight(huffNode, (U32)nonNullRank, maxNbBits);
388 
389  /* fill result into tree (val, nbBits) */
390  { U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0};
391  U16 valPerRank[HUF_TABLELOG_MAX+1] = {0};
392  int const alphabetSize = (int)(maxSymbolValue + 1);
393  if (maxNbBits > HUF_TABLELOG_MAX) return ERROR(GENERIC); /* check fit into table */
394  for (n=0; n<=nonNullRank; n++)
395  nbPerRank[huffNode[n].nbBits]++;
396  /* determine stating value per rank */
397  { U16 min = 0;
398  for (n=(int)maxNbBits; n>0; n--) {
399  valPerRank[n] = min; /* get starting value within each rank */
400  min += nbPerRank[n];
401  min >>= 1;
402  } }
403  for (n=0; n<alphabetSize; n++)
404  tree[huffNode[n].byte].nbBits = huffNode[n].nbBits; /* push nbBits per symbol, symbol order */
405  for (n=0; n<alphabetSize; n++)
406  tree[n].val = valPerRank[tree[n].nbBits]++; /* assign value within rank, symbol order */
407  }
408 
409  return maxNbBits;
410 }
#define ERROR(name)
Definition: error_private.h:53
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define U(x)
Definition: wordpad.c:45
GLdouble n
Definition: glext.h:7729
static void HUF_sort(nodeElt *huffNode, const unsigned *count, U32 maxSymbolValue, rankPos *rankPosition)
Definition: huf_compress.c:307
GLuint GLfloat * val
Definition: glext.h:7180
r parent
Definition: btrfs.c:3010
int n1
Definition: dwarfget.c:148
nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]
Definition: huf_compress.c:298
unsigned short U16
Definition: xxhash.c:194
rankPos rankPosition[RANK_POSITION_TABLE_SIZE]
Definition: huf_compress.c:304
int n2
Definition: dwarfget.c:148
#define min(a, b)
Definition: monoChain.cc:55
static U32 HUF_setMaxHeight(nodeElt *huffNode, U32 lastNonNull, U32 maxNbBits)
Definition: huf_compress.c:215
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
#define STARTNODE
Definition: huf_compress.c:336
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31

Referenced by HUF_buildCTable(), HUF_compress_internal(), and ZSTD_buildSuperBlockEntropy_literal().

◆ HUF_compress()

size_t HUF_compress ( void dst,
size_t  dstCapacity,
const void src,
size_t  srcSize 
)

HUF_compress() : Compress content from buffer 'src', of size 'srcSize', into buffer 'dst'. 'dst' buffer must be already allocated. Compression runs faster if dstCapacity >= HUF_compressBound(srcSize). srcSize must be <= HUF_BLOCKSIZE_MAX == 128 KB.

Returns
: size of compressed data (<= dstCapacity). Special values : if return == 0, srcData is not compressible => Nothing is stored within dst !!! if HUF_isError(return), compression failed (more details using HUF_getErrorName())

Definition at line 795 of file huf_compress.c.

796 {
797  return HUF_compress2(dst, maxDstSize, src, srcSize, 255, HUF_TABLELOG_DEFAULT);
798 }
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340
size_t HUF_compress2(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog)
Definition: huf_compress.c:787

◆ HUF_compress1X()

size_t HUF_compress1X ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  huffLog 
)

Definition at line 750 of file huf_compress.c.

753 {
754  unsigned workSpace[HUF_WORKSPACE_SIZE_U32];
755  return HUF_compress1X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace));
756 }
#define HUF_WORKSPACE_SIZE_U32
Definition: huf.h:94
size_t HUF_compress1X_wksp(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize)
Definition: huf_compress.c:727
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

◆ HUF_compress1X_repeat()

size_t HUF_compress1X_repeat ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  huffLog,
void workSpace,
size_t  wkspSize,
HUF_CElt *  hufTable,
HUF_repeat *  repeat,
int  preferRepeat,
int  bmi2 
)

Definition at line 738 of file huf_compress.c.

743 {
744  return HUF_compress_internal(dst, dstSize, src, srcSize,
745  maxSymbolValue, huffLog, HUF_singleStream,
746  workSpace, wkspSize, hufTable,
747  repeat, preferRepeat, bmi2);
748 }
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, HUF_nbStreams_e nbStreams, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:638
GLenum src
Definition: glext.h:6340
static int repeat
Definition: xmllint.c:137
GLenum GLenum dst
Definition: glext.h:6340

Referenced by ZSTD_compressLiterals().

◆ HUF_compress1X_usingCTable()

size_t HUF_compress1X_usingCTable ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
const HUF_CElt *  CTable 
)

Definition at line 546 of file huf_compress.c.

547 {
548  return HUF_compress1X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0);
549 }
static size_t HUF_compress1X_usingCTable_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, const int bmi2)
Definition: huf_compress.c:536
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

Referenced by ZSTD_compressSubBlock_literal().

◆ HUF_compress1X_usingCTable_internal()

static size_t HUF_compress1X_usingCTable_internal ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
const HUF_CElt *  CTable,
const int  bmi2 
)
static

Definition at line 536 of file huf_compress.c.

539 {
540  (void)bmi2;
541  return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable);
542 }
FORCE_INLINE_TEMPLATE size_t HUF_compress1X_usingCTable_internal_body(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable)
Definition: huf_compress.c:458
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

Referenced by HUF_compress1X_usingCTable(), HUF_compress4X_usingCTable_internal(), and HUF_compressCTable_internal().

◆ HUF_compress1X_usingCTable_internal_body()

FORCE_INLINE_TEMPLATE size_t HUF_compress1X_usingCTable_internal_body ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
const HUF_CElt *  CTable 
)

Definition at line 458 of file huf_compress.c.

461 {
462  const BYTE* ip = (const BYTE*) src;
463  BYTE* const ostart = (BYTE*)dst;
464  BYTE* const oend = ostart + dstSize;
465  BYTE* op = ostart;
466  size_t n;
467  BIT_CStream_t bitC;
468 
469  /* init */
470  if (dstSize < 8) return 0; /* not enough space to compress */
471  { size_t const initErr = BIT_initCStream(&bitC, op, (size_t)(oend-op));
472  if (HUF_isError(initErr)) return 0; }
473 
474  n = srcSize & ~3; /* join to mod 4 */
475  switch (srcSize & 3)
476  {
477  case 3 : HUF_encodeSymbol(&bitC, ip[n+ 2], CTable);
478  HUF_FLUSHBITS_2(&bitC);
479  /* fall-through */
480  case 2 : HUF_encodeSymbol(&bitC, ip[n+ 1], CTable);
481  HUF_FLUSHBITS_1(&bitC);
482  /* fall-through */
483  case 1 : HUF_encodeSymbol(&bitC, ip[n+ 0], CTable);
484  HUF_FLUSHBITS(&bitC);
485  /* fall-through */
486  case 0 : /* fall-through */
487  default: break;
488  }
489 
490  for (; n>0; n-=4) { /* note : n&3==0 at this stage */
491  HUF_encodeSymbol(&bitC, ip[n- 1], CTable);
492  HUF_FLUSHBITS_1(&bitC);
493  HUF_encodeSymbol(&bitC, ip[n- 2], CTable);
494  HUF_FLUSHBITS_2(&bitC);
495  HUF_encodeSymbol(&bitC, ip[n- 3], CTable);
496  HUF_FLUSHBITS_1(&bitC);
497  HUF_encodeSymbol(&bitC, ip[n- 4], CTable);
498  HUF_FLUSHBITS(&bitC);
499  }
500 
501  return BIT_closeCStream(&bitC);
502 }
#define HUF_FLUSHBITS_2(stream)
Definition: huf_compress.c:454
#define HUF_isError
Definition: huf_compress.c:41
GLdouble n
Definition: glext.h:7729
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:183
FORCE_INLINE_TEMPLATE void HUF_encodeSymbol(BIT_CStream_t *bitCPtr, U32 symbol, const HUF_CElt *CTable)
Definition: huf_compress.c:444
Definition: dhcpd.h:61
UINT op
Definition: effect.c:236
#define HUF_FLUSHBITS(s)
Definition: huf_compress.c:449
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
#define HUF_FLUSHBITS_1(stream)
Definition: huf_compress.c:451
GLenum GLenum dst
Definition: glext.h:6340
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:254

Referenced by HUF_compress1X_usingCTable_internal().

◆ HUF_compress1X_wksp()

size_t HUF_compress1X_wksp ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  huffLog,
void workSpace,
size_t  wkspSize 
)

Definition at line 727 of file huf_compress.c.

731 {
732  return HUF_compress_internal(dst, dstSize, src, srcSize,
733  maxSymbolValue, huffLog, HUF_singleStream,
734  workSpace, wkspSize,
735  NULL, NULL, 0, 0 /*bmi2*/);
736 }
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, HUF_nbStreams_e nbStreams, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:638
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340
#define NULL
Definition: types.h:112

Referenced by HUF_compress1X().

◆ HUF_compress2()

size_t HUF_compress2 ( void dst,
size_t  dstCapacity,
const void src,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  tableLog 
)

HUF_compress2() : Same as HUF_compress(), but offers control over maxSymbolValue and tableLog. maxSymbolValue must be <= HUF_SYMBOLVALUE_MAX . tableLog must be <= HUF_TABLELOG_MAX .

Definition at line 787 of file huf_compress.c.

790 {
791  unsigned workSpace[HUF_WORKSPACE_SIZE_U32];
792  return HUF_compress4X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(workSpace));
793 }
#define HUF_WORKSPACE_SIZE_U32
Definition: huf.h:94
size_t HUF_compress4X_wksp(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, void *workSpace, size_t wkspSize)
Definition: huf_compress.c:761
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

Referenced by HUF_compress().

◆ HUF_compress4X_repeat()

size_t HUF_compress4X_repeat ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  huffLog,
void workSpace,
size_t  wkspSize,
HUF_CElt *  hufTable,
HUF_repeat *  repeat,
int  preferRepeat,
int  bmi2 
)

Definition at line 775 of file huf_compress.c.

780 {
781  return HUF_compress_internal(dst, dstSize, src, srcSize,
782  maxSymbolValue, huffLog, HUF_fourStreams,
783  workSpace, wkspSize,
784  hufTable, repeat, preferRepeat, bmi2);
785 }
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, HUF_nbStreams_e nbStreams, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:638
GLenum src
Definition: glext.h:6340
static int repeat
Definition: xmllint.c:137
GLenum GLenum dst
Definition: glext.h:6340

Referenced by ZSTD_compressLiterals().

◆ HUF_compress4X_usingCTable()

size_t HUF_compress4X_usingCTable ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
const HUF_CElt *  CTable 
)

Definition at line 605 of file huf_compress.c.

606 {
607  return HUF_compress4X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0);
608 }
static size_t HUF_compress4X_usingCTable_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int bmi2)
Definition: huf_compress.c:553
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

Referenced by ZSTD_compressSubBlock_literal().

◆ HUF_compress4X_usingCTable_internal()

static size_t HUF_compress4X_usingCTable_internal ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
const HUF_CElt *  CTable,
int  bmi2 
)
static

Definition at line 553 of file huf_compress.c.

556 {
557  size_t const segmentSize = (srcSize+3)/4; /* first 3 segments */
558  const BYTE* ip = (const BYTE*) src;
559  const BYTE* const iend = ip + srcSize;
560  BYTE* const ostart = (BYTE*) dst;
561  BYTE* const oend = ostart + dstSize;
562  BYTE* op = ostart;
563 
564  if (dstSize < 6 + 1 + 1 + 1 + 8) return 0; /* minimum space to compress successfully */
565  if (srcSize < 12) return 0; /* no saving possible : too small input */
566  op += 6; /* jumpTable */
567 
568  assert(op <= oend);
569  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) );
570  if (cSize==0) return 0;
571  assert(cSize <= 65535);
572  MEM_writeLE16(ostart, (U16)cSize);
573  op += cSize;
574  }
575 
576  ip += segmentSize;
577  assert(op <= oend);
578  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) );
579  if (cSize==0) return 0;
580  assert(cSize <= 65535);
581  MEM_writeLE16(ostart+2, (U16)cSize);
582  op += cSize;
583  }
584 
585  ip += segmentSize;
586  assert(op <= oend);
587  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, segmentSize, CTable, bmi2) );
588  if (cSize==0) return 0;
589  assert(cSize <= 65535);
590  MEM_writeLE16(ostart+4, (U16)cSize);
591  op += cSize;
592  }
593 
594  ip += segmentSize;
595  assert(op <= oend);
596  assert(ip <= iend);
597  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, (size_t)(oend-op), ip, (size_t)(iend-ip), CTable, bmi2) );
598  if (cSize==0) return 0;
599  op += cSize;
600  }
601 
602  return (size_t)(op-ostart);
603 }
MEM_STATIC void MEM_writeLE16(void *memPtr, U16 val)
Definition: mem.h:324
#define CHECK_V_F(e, f)
Definition: error_private.h:61
static size_t HUF_compress1X_usingCTable_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, const int bmi2)
Definition: huf_compress.c:536
#define assert(x)
Definition: debug.h:53
Definition: dhcpd.h:61
UINT op
Definition: effect.c:236
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
unsigned short U16
Definition: xxhash.c:194
GLenum GLenum dst
Definition: glext.h:6340

Referenced by HUF_compress4X_usingCTable(), and HUF_compressCTable_internal().

◆ HUF_compress4X_wksp()

size_t HUF_compress4X_wksp ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  huffLog,
void workSpace,
size_t  wkspSize 
)

Definition at line 761 of file huf_compress.c.

765 {
766  return HUF_compress_internal(dst, dstSize, src, srcSize,
767  maxSymbolValue, huffLog, HUF_fourStreams,
768  workSpace, wkspSize,
769  NULL, NULL, 0, 0 /*bmi2*/);
770 }
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, HUF_nbStreams_e nbStreams, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:638
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340
#define NULL
Definition: types.h:112

Referenced by HUF_compress2().

◆ HUF_compress_internal()

static size_t HUF_compress_internal ( void dst,
size_t  dstSize,
const void src,
size_t  srcSize,
unsigned  maxSymbolValue,
unsigned  huffLog,
HUF_nbStreams_e  nbStreams,
void workSpace,
size_t  wkspSize,
HUF_CElt *  oldHufTable,
HUF_repeat *  repeat,
int  preferRepeat,
const int  bmi2 
)
static

Definition at line 638 of file huf_compress.c.

645 {
647  BYTE* const ostart = (BYTE*)dst;
648  BYTE* const oend = ostart + dstSize;
649  BYTE* op = ostart;
650 
652 
653  /* checks & inits */
654  if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
655  if (wkspSize < HUF_WORKSPACE_SIZE) return ERROR(workSpace_tooSmall);
656  if (!srcSize) return 0; /* Uncompressed */
657  if (!dstSize) return 0; /* cannot fit anything within dst budget */
658  if (srcSize > HUF_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); /* current block size limit */
659  if (huffLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
660  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
661  if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX;
662  if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT;
663 
664  /* Heuristic : If old table is valid, use it for small inputs */
665  if (preferRepeat && repeat && *repeat == HUF_repeat_valid) {
666  return HUF_compressCTable_internal(ostart, op, oend,
667  src, srcSize,
668  nbStreams, oldHufTable, bmi2);
669  }
670 
671  /* Scan input and build symbol stats */
672  { CHECK_V_F(largest, HIST_count_wksp (table->count, &maxSymbolValue, (const BYTE*)src, srcSize, workSpace, wkspSize) );
673  if (largest == srcSize) { *ostart = ((const BYTE*)src)[0]; return 1; } /* single symbol, rle */
674  if (largest <= (srcSize >> 7)+4) return 0; /* heuristic : probably not compressible enough */
675  }
676 
677  /* Check validity of previous table */
678  if ( repeat
679  && *repeat == HUF_repeat_check
680  && !HUF_validateCTable(oldHufTable, table->count, maxSymbolValue)) {
681  *repeat = HUF_repeat_none;
682  }
683  /* Heuristic : use existing table for small inputs */
684  if (preferRepeat && repeat && *repeat != HUF_repeat_none) {
685  return HUF_compressCTable_internal(ostart, op, oend,
686  src, srcSize,
687  nbStreams, oldHufTable, bmi2);
688  }
689 
690  /* Build Huffman Tree */
691  huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue);
692  { size_t const maxBits = HUF_buildCTable_wksp(table->CTable, table->count,
693  maxSymbolValue, huffLog,
694  &table->buildCTable_wksp, sizeof(table->buildCTable_wksp));
695  CHECK_F(maxBits);
696  huffLog = (U32)maxBits;
697  /* Zero unused symbols in CTable, so we can check it for validity */
698  memset(table->CTable + (maxSymbolValue + 1), 0,
699  sizeof(table->CTable) - ((maxSymbolValue + 1) * sizeof(HUF_CElt)));
700  }
701 
702  /* Write table description header */
703  { CHECK_V_F(hSize, HUF_writeCTable (op, dstSize, table->CTable, maxSymbolValue, huffLog) );
704  /* Check if using previous huffman table is beneficial */
705  if (repeat && *repeat != HUF_repeat_none) {
706  size_t const oldSize = HUF_estimateCompressedSize(oldHufTable, table->count, maxSymbolValue);
707  size_t const newSize = HUF_estimateCompressedSize(table->CTable, table->count, maxSymbolValue);
708  if (oldSize <= hSize + newSize || hSize + 12 >= srcSize) {
709  return HUF_compressCTable_internal(ostart, op, oend,
710  src, srcSize,
711  nbStreams, oldHufTable, bmi2);
712  } }
713 
714  /* Use the new huffman table */
715  if (hSize + 12ul >= srcSize) { return 0; }
716  op += hSize;
717  if (repeat) { *repeat = HUF_repeat_none; }
718  if (oldHufTable)
719  memcpy(oldHufTable, table->CTable, sizeof(table->CTable)); /* Save new table */
720  }
721  return HUF_compressCTable_internal(ostart, op, oend,
722  src, srcSize,
723  nbStreams, table->CTable, bmi2);
724 }
#define CHECK_F(f)
Definition: error_private.h:62
#define ERROR(name)
Definition: error_private.h:53
size_t HUF_buildCTable_wksp(HUF_CElt *tree, const unsigned *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
Definition: huf_compress.c:338
#define CHECK_V_F(e, f)
Definition: error_private.h:61
#define HUF_STATIC_ASSERT(c)
Definition: huf_compress.c:42
size_t HUF_writeCTable(void *dst, size_t maxDstSize, const HUF_CElt *CTable, unsigned maxSymbolValue, unsigned huffLog)
Definition: huf_compress.c:114
unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: huf_compress.c:48
#define HUF_BLOCKSIZE_MAX
Definition: huf.h:72
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:166
UINT op
Definition: effect.c:236
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
static int repeat
Definition: xmllint.c:137
GLenum GLenum dst
Definition: glext.h:6340
int HUF_validateCTable(const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
Definition: huf_compress.c:432
#define HUF_WORKSPACE_SIZE
Definition: huf.h:93
static size_t HUF_compressCTable_internal(BYTE *const ostart, BYTE *op, BYTE *const oend, const void *src, size_t srcSize, HUF_nbStreams_e nbStreams, const HUF_CElt *CTable, const int bmi2)
Definition: huf_compress.c:612
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
size_t HUF_estimateCompressedSize(const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
Definition: huf_compress.c:422

Referenced by HUF_compress1X_repeat(), HUF_compress1X_wksp(), HUF_compress4X_repeat(), and HUF_compress4X_wksp().

◆ HUF_compressBound()

size_t HUF_compressBound ( size_t  size)

maximum compressed size (worst case)

Definition at line 441 of file huf_compress.c.

441 { return HUF_COMPRESSBOUND(size); }
GLsizeiptr size
Definition: glext.h:5919

◆ HUF_compressCTable_internal()

static size_t HUF_compressCTable_internal ( BYTE *const  ostart,
BYTE op,
BYTE *const  oend,
const void src,
size_t  srcSize,
HUF_nbStreams_e  nbStreams,
const HUF_CElt *  CTable,
const int  bmi2 
)
static

Definition at line 612 of file huf_compress.c.

616 {
617  size_t const cSize = (nbStreams==HUF_singleStream) ?
618  HUF_compress1X_usingCTable_internal(op, (size_t)(oend - op), src, srcSize, CTable, bmi2) :
619  HUF_compress4X_usingCTable_internal(op, (size_t)(oend - op), src, srcSize, CTable, bmi2);
620  if (HUF_isError(cSize)) { return cSize; }
621  if (cSize==0) { return 0; } /* uncompressible */
622  op += cSize;
623  /* check compressibility */
624  assert(op >= ostart);
625  if ((size_t)(op-ostart) >= srcSize-1) { return 0; }
626  return (size_t)(op-ostart);
627 }
#define HUF_isError
Definition: huf_compress.c:41
static size_t HUF_compress1X_usingCTable_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, const int bmi2)
Definition: huf_compress.c:536
#define assert(x)
Definition: debug.h:53
UINT op
Definition: effect.c:236
static size_t HUF_compress4X_usingCTable_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, const HUF_CElt *CTable, int bmi2)
Definition: huf_compress.c:553
GLenum src
Definition: glext.h:6340

Referenced by HUF_compress_internal().

◆ HUF_compressWeights()

static size_t HUF_compressWeights ( void dst,
size_t  dstSize,
const void weightTable,
size_t  wtSize 
)
static

Definition at line 63 of file huf_compress.c.

64 {
65  BYTE* const ostart = (BYTE*) dst;
66  BYTE* op = ostart;
67  BYTE* const oend = ostart + dstSize;
68 
69  unsigned maxSymbolValue = HUF_TABLELOG_MAX;
71 
72  FSE_CTable CTable[FSE_CTABLE_SIZE_U32(MAX_FSE_TABLELOG_FOR_HUFF_HEADER, HUF_TABLELOG_MAX)];
73  BYTE scratchBuffer[1<<MAX_FSE_TABLELOG_FOR_HUFF_HEADER];
74 
75  unsigned count[HUF_TABLELOG_MAX+1];
76  S16 norm[HUF_TABLELOG_MAX+1];
77 
78  /* init conditions */
79  if (wtSize <= 1) return 0; /* Not compressible */
80 
81  /* Scan input and build symbol stats */
82  { unsigned const maxCount = HIST_count_simple(count, &maxSymbolValue, weightTable, wtSize); /* never fails */
83  if (maxCount == wtSize) return 1; /* only a single symbol in src : rle */
84  if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
85  }
86 
87  tableLog = FSE_optimalTableLog(tableLog, wtSize, maxSymbolValue);
88  CHECK_F( FSE_normalizeCount(norm, tableLog, count, wtSize, maxSymbolValue) );
89 
90  /* Write table description header */
91  { CHECK_V_F(hSize, FSE_writeNCount(op, (size_t)(oend-op), norm, maxSymbolValue, tableLog) );
92  op += hSize;
93  }
94 
95  /* Compress */
96  CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, sizeof(scratchBuffer)) );
97  { CHECK_V_F(cSize, FSE_compress_usingCTable(op, (size_t)(oend - op), weightTable, wtSize, CTable) );
98  if (cSize == 0) return 0; /* not enough space for compressed data */
99  op += cSize;
100  }
101 
102  return (size_t)(op-ostart);
103 }
FSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:342
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
Definition: fse_compress.c:69
FSE_PUBLIC_API size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:438
#define CHECK_F(f)
Definition: error_private.h:62
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER
Definition: huf_compress.c:62
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define CHECK_V_F(e, f)
Definition: error_private.h:61
unsigned FSE_CTable
Definition: fse.h:160
FSE_PUBLIC_API size_t FSE_compress_usingCTable(void *dst, size_t dstCapacity, const void *src, size_t srcSize, const FSE_CTable *ct)
Definition: fse_compress.c:616
UINT op
Definition: effect.c:236
unsigned HIST_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
Definition: hist.c:29
unsigned char BYTE
Definition: xxhash.c:193
GLenum GLenum dst
Definition: glext.h:6340
GLsizei maxCount
Definition: glext.h:6042
FSE_PUBLIC_API size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
Definition: fse_compress.c:291
signed short S16
Definition: mem.h:146
unsigned int U32
Definition: xxhash.c:195

Referenced by HUF_writeCTable().

◆ HUF_encodeSymbol()

FORCE_INLINE_TEMPLATE void HUF_encodeSymbol ( BIT_CStream_t bitCPtr,
U32  symbol,
const HUF_CElt *  CTable 
)

Definition at line 444 of file huf_compress.c.

445 {
446  BIT_addBitsFast(bitCPtr, CTable[symbol].val, CTable[symbol].nbBits);
447 }
GLuint GLfloat * val
Definition: glext.h:7180
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:211

Referenced by HUF_compress1X_usingCTable_internal_body().

◆ HUF_estimateCompressedSize()

size_t HUF_estimateCompressedSize ( const HUF_CElt *  CTable,
const unsigned count,
unsigned  maxSymbolValue 
)

Definition at line 422 of file huf_compress.c.

423 {
424  size_t nbBits = 0;
425  int s;
426  for (s = 0; s <= (int)maxSymbolValue; ++s) {
427  nbBits += CTable[s].nbBits * count[s];
428  }
429  return nbBits >> 3;
430 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLdouble s
Definition: gl.h:2039
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31

Referenced by HUF_compress_internal(), ZSTD_buildSuperBlockEntropy_literal(), and ZSTD_estimateSubBlockSize_literal().

◆ HUF_getNbBits()

U32 HUF_getNbBits ( const void symbolTable,
U32  symbolValue 
)

Definition at line 200 of file huf_compress.c.

201 {
202  const HUF_CElt* table = (const HUF_CElt*)symbolTable;
203  assert(symbolValue <= HUF_SYMBOLVALUE_MAX);
204  return table[symbolValue].nbBits;
205 }
#define assert(x)
Definition: debug.h:53

Referenced by ZSTD_rescaleFreqs().

◆ HUF_optimalTableLog()

unsigned HUF_optimalTableLog ( unsigned  maxTableLog,
size_t  srcSize,
unsigned  maxSymbolValue 
)

Definition at line 48 of file huf_compress.c.

49 {
50  return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 1);
51 }
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
Definition: fse_compress.c:328

Referenced by HUF_compress_internal(), and ZSTD_buildSuperBlockEntropy_literal().

◆ HUF_readCTable()

size_t HUF_readCTable ( HUF_CElt *  CTable,
unsigned maxSymbolValuePtr,
const void src,
size_t  srcSize,
unsigned hasZeroWeights 
)

Definition at line 150 of file huf_compress.c.

151 {
152  BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1]; /* init not required, even though some static analyzer may complain */
153  U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */
154  U32 tableLog = 0;
155  U32 nbSymbols = 0;
156 
157  /* get symbol weights */
158  CHECK_V_F(readSize, HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize));
159 
160  /* check result */
161  if (tableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
162  if (nbSymbols > *maxSymbolValuePtr+1) return ERROR(maxSymbolValue_tooSmall);
163 
164  /* Prepare base value per rank */
165  { U32 n, nextRankStart = 0;
166  for (n=1; n<=tableLog; n++) {
167  U32 current = nextRankStart;
168  nextRankStart += (rankVal[n] << (n-1));
169  rankVal[n] = current;
170  } }
171 
172  /* fill nbBits */
173  *hasZeroWeights = 0;
174  { U32 n; for (n=0; n<nbSymbols; n++) {
175  const U32 w = huffWeight[n];
176  *hasZeroWeights |= (w == 0);
177  CTable[n].nbBits = (BYTE)(tableLog + 1 - w) & -(w != 0);
178  } }
179 
180  /* fill val */
181  { U16 nbPerRank[HUF_TABLELOG_MAX+2] = {0}; /* support w=0=>n=tableLog+1 */
182  U16 valPerRank[HUF_TABLELOG_MAX+2] = {0};
183  { U32 n; for (n=0; n<nbSymbols; n++) nbPerRank[CTable[n].nbBits]++; }
184  /* determine stating value per rank */
185  valPerRank[tableLog+1] = 0; /* for w==0 */
186  { U16 min = 0;
187  U32 n; for (n=tableLog; n>0; n--) { /* start at n=tablelog <-> w=1 */
188  valPerRank[n] = min; /* get starting value within each rank */
189  min += nbPerRank[n];
190  min >>= 1;
191  } }
192  /* assign value within rank, symbol order */
193  { U32 n; for (n=0; n<nbSymbols; n++) CTable[n].val = valPerRank[CTable[n].nbBits]++; }
194  }
195 
196  *maxSymbolValuePtr = nbSymbols - 1;
197  return readSize;
198 }
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
#define ERROR(name)
Definition: error_private.h:53
#define CHECK_V_F(e, f)
Definition: error_private.h:61
GLdouble n
Definition: glext.h:7729
GLuint GLfloat * val
Definition: glext.h:7180
struct task_struct * current
Definition: linux.c:32
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
unsigned short U16
Definition: xxhash.c:194
#define min(a, b)
Definition: monoChain.cc:55
unsigned int U32
Definition: xxhash.c:195
size_t HUF_readStats(BYTE *huffWeight, size_t hwSize, U32 *rankStats, U32 *nbSymbolsPtr, U32 *tableLogPtr, const void *src, size_t srcSize)

Referenced by ZSTD_loadCEntropy().

◆ HUF_setMaxHeight()

static U32 HUF_setMaxHeight ( nodeElt huffNode,
U32  lastNonNull,
U32  maxNbBits 
)
static

Definition at line 215 of file huf_compress.c.

216 {
217  const U32 largestBits = huffNode[lastNonNull].nbBits;
218  if (largestBits <= maxNbBits) return largestBits; /* early exit : no elt > maxNbBits */
219 
220  /* there are several too large elements (at least >= 2) */
221  { int totalCost = 0;
222  const U32 baseCost = 1 << (largestBits - maxNbBits);
223  int n = (int)lastNonNull;
224 
225  while (huffNode[n].nbBits > maxNbBits) {
226  totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits));
227  huffNode[n].nbBits = (BYTE)maxNbBits;
228  n --;
229  } /* n stops at huffNode[n].nbBits <= maxNbBits */
230  while (huffNode[n].nbBits == maxNbBits) n--; /* n end at index of smallest symbol using < maxNbBits */
231 
232  /* renorm totalCost */
233  totalCost >>= (largestBits - maxNbBits); /* note : totalCost is necessarily a multiple of baseCost */
234 
235  /* repay normalized cost */
236  { U32 const noSymbol = 0xF0F0F0F0;
237  U32 rankLast[HUF_TABLELOG_MAX+2];
238 
239  /* Get pos of last (smallest) symbol per rank */
240  memset(rankLast, 0xF0, sizeof(rankLast));
241  { U32 currentNbBits = maxNbBits;
242  int pos;
243  for (pos=n ; pos >= 0; pos--) {
244  if (huffNode[pos].nbBits >= currentNbBits) continue;
245  currentNbBits = huffNode[pos].nbBits; /* < maxNbBits */
246  rankLast[maxNbBits-currentNbBits] = (U32)pos;
247  } }
248 
249  while (totalCost > 0) {
250  U32 nBitsToDecrease = BIT_highbit32((U32)totalCost) + 1;
251  for ( ; nBitsToDecrease > 1; nBitsToDecrease--) {
252  U32 const highPos = rankLast[nBitsToDecrease];
253  U32 const lowPos = rankLast[nBitsToDecrease-1];
254  if (highPos == noSymbol) continue;
255  if (lowPos == noSymbol) break;
256  { U32 const highTotal = huffNode[highPos].count;
257  U32 const lowTotal = 2 * huffNode[lowPos].count;
258  if (highTotal <= lowTotal) break;
259  } }
260  /* only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !) */
261  /* HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary */
262  while ((nBitsToDecrease<=HUF_TABLELOG_MAX) && (rankLast[nBitsToDecrease] == noSymbol))
263  nBitsToDecrease ++;
264  totalCost -= 1 << (nBitsToDecrease-1);
265  if (rankLast[nBitsToDecrease-1] == noSymbol)
266  rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease]; /* this rank is no longer empty */
267  huffNode[rankLast[nBitsToDecrease]].nbBits ++;
268  if (rankLast[nBitsToDecrease] == 0) /* special case, reached largest symbol */
269  rankLast[nBitsToDecrease] = noSymbol;
270  else {
271  rankLast[nBitsToDecrease]--;
272  if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
273  rankLast[nBitsToDecrease] = noSymbol; /* this rank is now empty */
274  } } /* while (totalCost > 0) */
275 
276  while (totalCost < 0) { /* Sometimes, cost correction overshoot */
277  if (rankLast[1] == noSymbol) { /* special case : no rank 1 symbol (using maxNbBits-1); let's create one from largest rank 0 (using maxNbBits) */
278  while (huffNode[n].nbBits == maxNbBits) n--;
279  huffNode[n+1].nbBits--;
280  assert(n >= 0);
281  rankLast[1] = (U32)(n+1);
282  totalCost++;
283  continue;
284  }
285  huffNode[ rankLast[1] + 1 ].nbBits--;
286  rankLast[1]++;
287  totalCost ++;
288  } } } /* there are several too large elements (at least >= 2) */
289 
290  return maxNbBits;
291 }
GLdouble n
Definition: glext.h:7729
#define assert(x)
Definition: debug.h:53
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
unsigned char BYTE
Definition: xxhash.c:193
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31

Referenced by HUF_buildCTable_wksp().

◆ HUF_sort()

static void HUF_sort ( nodeElt huffNode,
const unsigned count,
U32  maxSymbolValue,
rankPos rankPosition 
)
static

Definition at line 307 of file huf_compress.c.

308 {
309  U32 n;
310 
311  memset(rankPosition, 0, sizeof(*rankPosition) * RANK_POSITION_TABLE_SIZE);
312  for (n=0; n<=maxSymbolValue; n++) {
313  U32 r = BIT_highbit32(count[n] + 1);
314  rankPosition[r].base ++;
315  }
316  for (n=30; n>0; n--) rankPosition[n-1].base += rankPosition[n].base;
317  for (n=0; n<32; n++) rankPosition[n].current = rankPosition[n].base;
318  for (n=0; n<=maxSymbolValue; n++) {
319  U32 const c = count[n];
320  U32 const r = BIT_highbit32(c+1) + 1;
321  U32 pos = rankPosition[r].current++;
322  while ((pos > rankPosition[r].base) && (c > huffNode[pos-1].count)) {
323  huffNode[pos] = huffNode[pos-1];
324  pos--;
325  }
326  huffNode[pos].count = c;
327  huffNode[pos].byte = (BYTE)n;
328  }
329 }
U32 current
Definition: huf_compress.c:295
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLdouble n
Definition: glext.h:7729
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:139
const GLubyte * c
Definition: glext.h:8905
struct task_struct * current
Definition: linux.c:32
unsigned char BYTE
Definition: xxhash.c:193
#define c
Definition: ke_i.h:80
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
#define RANK_POSITION_TABLE_SIZE
Definition: huf_compress.c:300

Referenced by HUF_buildCTable_wksp().

◆ HUF_validateCTable()

int HUF_validateCTable ( const HUF_CElt *  CTable,
const unsigned count,
unsigned  maxSymbolValue 
)

Definition at line 432 of file huf_compress.c.

432  {
433  int bad = 0;
434  int s;
435  for (s = 0; s <= (int)maxSymbolValue; ++s) {
436  bad |= (count[s] != 0) & (CTable[s].nbBits == 0);
437  }
438  return !bad;
439 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLdouble s
Definition: gl.h:2039
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31

Referenced by HUF_compress_internal(), and ZSTD_buildSuperBlockEntropy_literal().

◆ HUF_writeCTable()

size_t HUF_writeCTable ( void dst,
size_t  maxDstSize,
const HUF_CElt *  CTable,
unsigned  maxSymbolValue,
unsigned  huffLog 
)

HUF_writeCTable() : CTable : Huffman tree to save, using huf representation.

Returns
: size of saved CTable

Definition at line 114 of file huf_compress.c.

116 {
117  BYTE bitsToWeight[HUF_TABLELOG_MAX + 1]; /* precomputed conversion table */
118  BYTE huffWeight[HUF_SYMBOLVALUE_MAX];
119  BYTE* op = (BYTE*)dst;
120  U32 n;
121 
122  /* check conditions */
123  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
124 
125  /* convert to weight */
126  bitsToWeight[0] = 0;
127  for (n=1; n<huffLog+1; n++)
128  bitsToWeight[n] = (BYTE)(huffLog + 1 - n);
129  for (n=0; n<maxSymbolValue; n++)
130  huffWeight[n] = bitsToWeight[CTable[n].nbBits];
131 
132  /* attempt weights compression by FSE */
133  { CHECK_V_F(hSize, HUF_compressWeights(op+1, maxDstSize-1, huffWeight, maxSymbolValue) );
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  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)((huffWeight[n] << 4) + huffWeight[n+1]);
146  return ((maxSymbolValue+1)/2) + 1;
147 }
#define ERROR(name)
Definition: error_private.h:53
#define CHECK_V_F(e, f)
Definition: error_private.h:61
GLdouble n
Definition: glext.h:7729
UINT op
Definition: effect.c:236
unsigned char BYTE
Definition: xxhash.c:193
static size_t HUF_compressWeights(void *dst, size_t dstSize, const void *weightTable, size_t wtSize)
Definition: huf_compress.c:63
GLenum GLenum dst
Definition: glext.h:6340
unsigned int U32
Definition: xxhash.c:195

Referenced by HUF_compress_internal(), and ZSTD_buildSuperBlockEntropy_literal().