ReactOS  0.4.15-dev-1201-gb2cf5a4
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 <ntifs.h>
#include <ntddk.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_compress_tables_t
 

Macros

#define FSE_STATIC_LINKING_ONLY   /* FSE_optimalTableLog_internal */
 
#define HUF_STATIC_LINKING_ONLY
 
#define HUFC_ALLOC_TAG   0x63465548
 
#define HUF_isError   ERR_isError
 
#define HUF_STATIC_ASSERT(c)   DEBUG_STATIC_ASSERT(c) /* use only *after* variable declarations */
 
#define CHECK_V_F(e, f)   size_t const e = f; if (ERR_isError(e)) return e
 
#define CHECK_F(f)   { CHECK_V_F(_var_err__, f); }
 
#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER   6
 
#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]
 

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, U32 maxSymbolValue, U32 huffLog)
 
size_t HUF_readCTable (HUF_CElt *CTable, U32 *maxSymbolValuePtr, const void *src, size_t srcSize)
 
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 U32 *count, U32 maxSymbolValue)
 
size_t HUF_buildCTable_wksp (HUF_CElt *tree, const U32 *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
 
size_t HUF_buildCTable (HUF_CElt *tree, const U32 *count, U32 maxSymbolValue, U32 maxNbBits)
 
static size_t HUF_estimateCompressedSize (HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
 
static 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, unsigned singleStream, 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, unsigned singleStream, 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

◆ CHECK_F

#define CHECK_F (   f)    { CHECK_V_F(_var_err__, f); }

Definition at line 68 of file huf_compress.c.

◆ CHECK_V_F

#define CHECK_V_F (   e,
  f 
)    size_t const e = f; if (ERR_isError(e)) return e

Definition at line 67 of file huf_compress.c.

◆ FSE_STATIC_LINKING_ONLY

#define FSE_STATIC_LINKING_ONLY   /* FSE_optimalTableLog_internal */

Definition at line 51 of file huf_compress.c.

◆ HUF_FLUSHBITS

#define HUF_FLUSHBITS (   s)    BIT_flushBits(s)

Definition at line 470 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 472 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 475 of file huf_compress.c.

◆ HUF_isError

#define HUF_isError   ERR_isError

Definition at line 65 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 66 of file huf_compress.c.

◆ HUF_STATIC_LINKING_ONLY

#define HUF_STATIC_LINKING_ONLY

Definition at line 53 of file huf_compress.c.

◆ HUFC_ALLOC_TAG

#define HUFC_ALLOC_TAG   0x63465548

Definition at line 59 of file huf_compress.c.

◆ MAX_FSE_TABLELOG_FOR_HUFF_HEADER

#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER   6

Definition at line 88 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 a table of HUF_CTABLE_WORKSPACE_SIZE_U32 unsigned.

Definition at line 352 of file huf_compress.c.

Typedef Documentation

◆ huffNodeTable

typedef nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]

Definition at line 353 of file huf_compress.c.

◆ nodeElt

Function Documentation

◆ HUF_buildCTable()

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

HUF_buildCTable() :

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

Definition at line 428 of file huf_compress.c.

429 {
431  size_t ret;
432 
433  if (!nodeTable)
434  return 0;
435 
436  ret = HUF_buildCTable_wksp(tree, count, maxSymbolValue, maxNbBits, nodeTable, sizeof(huffNodeTable));
437 
438  ExFreePool(nodeTable);
439 
440  return ret;
441 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
size_t HUF_buildCTable_wksp(HUF_CElt *tree, const U32 *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
Definition: huf_compress.c:354
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define HUFC_ALLOC_TAG
Definition: huf_compress.c:59
int ret
nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]
Definition: huf_compress.c:353
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

◆ HUF_buildCTable_wksp()

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

Definition at line 354 of file huf_compress.c.

355 {
356  nodeElt* const huffNode0 = (nodeElt*)workSpace;
357  nodeElt* const huffNode = huffNode0+1;
358  U32 n, nonNullRank;
359  int lowS, lowN;
360  U16 nodeNb = STARTNODE;
361  U32 nodeRoot;
362 
363  /* safety checks */
364  if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
365  if (wkspSize < sizeof(huffNodeTable)) return ERROR(workSpace_tooSmall);
366  if (maxNbBits == 0) maxNbBits = HUF_TABLELOG_DEFAULT;
367  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
368  memset(huffNode0, 0, sizeof(huffNodeTable));
369 
370  /* sort, decreasing order */
371  HUF_sort(huffNode, count, maxSymbolValue);
372 
373  /* init for parents */
374  nonNullRank = maxSymbolValue;
375  while(huffNode[nonNullRank].count == 0) nonNullRank--;
376  lowS = nonNullRank; nodeRoot = nodeNb + lowS - 1; lowN = nodeNb;
377  huffNode[nodeNb].count = huffNode[lowS].count + huffNode[lowS-1].count;
378  huffNode[lowS].parent = huffNode[lowS-1].parent = nodeNb;
379  nodeNb++; lowS-=2;
380  for (n=nodeNb; n<=nodeRoot; n++) huffNode[n].count = (U32)(1U<<30);
381  huffNode0[0].count = (U32)(1U<<31); /* fake entry, strong barrier */
382 
383  /* create parents */
384  while (nodeNb <= nodeRoot) {
385  U32 n1 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
386  U32 n2 = (huffNode[lowS].count < huffNode[lowN].count) ? lowS-- : lowN++;
387  huffNode[nodeNb].count = huffNode[n1].count + huffNode[n2].count;
388  huffNode[n1].parent = huffNode[n2].parent = nodeNb;
389  nodeNb++;
390  }
391 
392  /* distribute weights (unlimited tree height) */
393  huffNode[nodeRoot].nbBits = 0;
394  for (n=nodeRoot-1; n>=STARTNODE; n--)
395  huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
396  for (n=0; n<=nonNullRank; n++)
397  huffNode[n].nbBits = huffNode[ huffNode[n].parent ].nbBits + 1;
398 
399  /* enforce maxTableLog */
400  maxNbBits = HUF_setMaxHeight(huffNode, nonNullRank, maxNbBits);
401 
402  /* fill result into tree (val, nbBits) */
403  { U16 nbPerRank[HUF_TABLELOG_MAX+1] = {0};
404  U16 valPerRank[HUF_TABLELOG_MAX+1] = {0};
405  if (maxNbBits > HUF_TABLELOG_MAX) return ERROR(GENERIC); /* check fit into table */
406  for (n=0; n<=nonNullRank; n++)
407  nbPerRank[huffNode[n].nbBits]++;
408  /* determine stating value per rank */
409  { U16 min = 0;
410  for (n=maxNbBits; n>0; n--) {
411  valPerRank[n] = min; /* get starting value within each rank */
412  min += nbPerRank[n];
413  min >>= 1;
414  } }
415  for (n=0; n<=maxSymbolValue; n++)
416  tree[huffNode[n].byte].nbBits = huffNode[n].nbBits; /* push nbBits per symbol, symbol order */
417  for (n=0; n<=maxSymbolValue; n++)
418  tree[n].val = valPerRank[tree[n].nbBits]++; /* assign value within rank, symbol order */
419  }
420 
421  return maxNbBits;
422 }
#define ERROR(name)
Definition: error_private.h:53
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define U(x)
Definition: wordpad.c:45
static void HUF_sort(nodeElt *huffNode, const U32 *count, U32 maxSymbolValue)
Definition: huf_compress.c:322
GLdouble n
Definition: glext.h:7729
GLuint GLfloat * val
Definition: glext.h:7180
r parent
Definition: btrfs.c:2944
int n1
Definition: dwarfget.c:148
nodeElt huffNodeTable[HUF_CTABLE_WORKSPACE_SIZE_U32]
Definition: huf_compress.c:353
unsigned short U16
Definition: xxhash.c:194
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:239
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
#define STARTNODE
Definition: huf_compress.c:352

Referenced by HUF_buildCTable(), and HUF_compress_internal().

◆ 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 824 of file huf_compress.c.

825 {
826  return HUF_compress2(dst, maxDstSize, src, srcSize, 255, HUF_TABLELOG_DEFAULT);
827 }
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:807

◆ HUF_compress1X()

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

Definition at line 761 of file huf_compress.c.

764 {
765  unsigned* workSpace = ExAllocatePoolWithTag(NonPagedPool, sizeof(unsigned) * HUF_WORKSPACE_SIZE_U32, HUFC_ALLOC_TAG);
766  size_t ret;
767 
768  if (!workSpace)
769  return 0;
770 
771  ret = HUF_compress1X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(unsigned) * HUF_WORKSPACE_SIZE_U32);
772 
773  ExFreePool(workSpace);
774 
775  return ret;
776 }
#define HUF_WORKSPACE_SIZE_U32
Definition: huf.h:114
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define HUFC_ALLOC_TAG
Definition: huf_compress.c:59
int ret
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:738
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

◆ 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 749 of file huf_compress.c.

754 {
755  return HUF_compress_internal(dst, dstSize, src, srcSize,
756  maxSymbolValue, huffLog, 1 /*single stream*/,
757  workSpace, wkspSize, hufTable,
758  repeat, preferRepeat, bmi2);
759 }
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, unsigned singleStream, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:651
GLenum src
Definition: glext.h:6340
static int repeat
Definition: xmllint.c:143
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 567 of file huf_compress.c.

568 {
569  return HUF_compress1X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0);
570 }
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:557
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

◆ 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 557 of file huf_compress.c.

560 {
561  (void)bmi2;
562  return HUF_compress1X_usingCTable_internal_body(dst, dstSize, src, srcSize, CTable);
563 }
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:479
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 479 of file huf_compress.c.

482 {
483  const BYTE* ip = (const BYTE*) src;
484  BYTE* const ostart = (BYTE*)dst;
485  BYTE* const oend = ostart + dstSize;
486  BYTE* op = ostart;
487  size_t n;
488  BIT_CStream_t bitC;
489 
490  /* init */
491  if (dstSize < 8) return 0; /* not enough space to compress */
492  { size_t const initErr = BIT_initCStream(&bitC, op, oend-op);
493  if (HUF_isError(initErr)) return 0; }
494 
495  n = srcSize & ~3; /* join to mod 4 */
496  switch (srcSize & 3)
497  {
498  case 3 : HUF_encodeSymbol(&bitC, ip[n+ 2], CTable);
499  HUF_FLUSHBITS_2(&bitC);
500  /* fall-through */
501  case 2 : HUF_encodeSymbol(&bitC, ip[n+ 1], CTable);
502  HUF_FLUSHBITS_1(&bitC);
503  /* fall-through */
504  case 1 : HUF_encodeSymbol(&bitC, ip[n+ 0], CTable);
505  HUF_FLUSHBITS(&bitC);
506  /* fall-through */
507  case 0 : /* fall-through */
508  default: break;
509  }
510 
511  for (; n>0; n-=4) { /* note : n&3==0 at this stage */
512  HUF_encodeSymbol(&bitC, ip[n- 1], CTable);
513  HUF_FLUSHBITS_1(&bitC);
514  HUF_encodeSymbol(&bitC, ip[n- 2], CTable);
515  HUF_FLUSHBITS_2(&bitC);
516  HUF_encodeSymbol(&bitC, ip[n- 3], CTable);
517  HUF_FLUSHBITS_1(&bitC);
518  HUF_encodeSymbol(&bitC, ip[n- 4], CTable);
519  HUF_FLUSHBITS(&bitC);
520  }
521 
522  return BIT_closeCStream(&bitC);
523 }
#define HUF_FLUSHBITS_2(stream)
Definition: huf_compress.c:475
#define HUF_isError
Definition: huf_compress.c:65
GLdouble n
Definition: glext.h:7729
MEM_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, size_t dstCapacity)
Definition: bitstream.h:199
FORCE_INLINE_TEMPLATE void HUF_encodeSymbol(BIT_CStream_t *bitCPtr, U32 symbol, const HUF_CElt *CTable)
Definition: huf_compress.c:465
Definition: dhcpd.h:61
UINT op
Definition: effect.c:224
#define HUF_FLUSHBITS(s)
Definition: huf_compress.c:470
GLenum src
Definition: glext.h:6340
unsigned char BYTE
Definition: xxhash.c:193
#define HUF_FLUSHBITS_1(stream)
Definition: huf_compress.c:472
GLenum GLenum dst
Definition: glext.h:6340
MEM_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
Definition: bitstream.h:269

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 738 of file huf_compress.c.

742 {
743  return HUF_compress_internal(dst, dstSize, src, srcSize,
744  maxSymbolValue, huffLog, 1 /*single stream*/,
745  workSpace, wkspSize,
746  NULL, NULL, 0, 0 /*bmi2*/);
747 }
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, unsigned singleStream, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:651
smooth NULL
Definition: ftsmooth.c:416
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

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 807 of file huf_compress.c.

810 {
811  unsigned* workSpace = ExAllocatePoolWithTag(NonPagedPool, sizeof(unsigned) * HUF_WORKSPACE_SIZE_U32, HUFC_ALLOC_TAG);
812  size_t ret;
813 
814  if (!workSpace)
815  return 0;
816 
817  ret = HUF_compress4X_wksp(dst, dstSize, src, srcSize, maxSymbolValue, huffLog, workSpace, sizeof(unsigned) * HUF_WORKSPACE_SIZE_U32);
818 
819  ExFreePool(workSpace);
820 
821  return ret;
822 }
#define HUF_WORKSPACE_SIZE_U32
Definition: huf.h:114
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:781
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define HUFC_ALLOC_TAG
Definition: huf_compress.c:59
int ret
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

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 795 of file huf_compress.c.

800 {
801  return HUF_compress_internal(dst, dstSize, src, srcSize,
802  maxSymbolValue, huffLog, 0 /* 4 streams */,
803  workSpace, wkspSize,
804  hufTable, repeat, preferRepeat, bmi2);
805 }
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, unsigned singleStream, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:651
GLenum src
Definition: glext.h:6340
static int repeat
Definition: xmllint.c:143
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 621 of file huf_compress.c.

622 {
623  return HUF_compress4X_usingCTable_internal(dst, dstSize, src, srcSize, CTable, /* bmi2 */ 0);
624 }
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:574
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

◆ 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 574 of file huf_compress.c.

577 {
578  size_t const segmentSize = (srcSize+3)/4; /* first 3 segments */
579  const BYTE* ip = (const BYTE*) src;
580  const BYTE* const iend = ip + srcSize;
581  BYTE* const ostart = (BYTE*) dst;
582  BYTE* const oend = ostart + dstSize;
583  BYTE* op = ostart;
584 
585  if (dstSize < 6 + 1 + 1 + 1 + 8) return 0; /* minimum space to compress successfully */
586  if (srcSize < 12) return 0; /* no saving possible : too small input */
587  op += 6; /* jumpTable */
588 
589  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, oend-op, ip, segmentSize, CTable, bmi2) );
590  if (cSize==0) return 0;
591  assert(cSize <= 65535);
592  MEM_writeLE16(ostart, (U16)cSize);
593  op += cSize;
594  }
595 
596  ip += segmentSize;
597  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, oend-op, ip, segmentSize, CTable, bmi2) );
598  if (cSize==0) return 0;
599  assert(cSize <= 65535);
600  MEM_writeLE16(ostart+2, (U16)cSize);
601  op += cSize;
602  }
603 
604  ip += segmentSize;
605  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, oend-op, ip, segmentSize, CTable, bmi2) );
606  if (cSize==0) return 0;
607  assert(cSize <= 65535);
608  MEM_writeLE16(ostart+4, (U16)cSize);
609  op += cSize;
610  }
611 
612  ip += segmentSize;
613  { CHECK_V_F(cSize, HUF_compress1X_usingCTable_internal(op, oend-op, ip, iend-ip, CTable, bmi2) );
614  if (cSize==0) return 0;
615  op += cSize;
616  }
617 
618  return op-ostart;
619 }
MEM_STATIC void MEM_writeLE16(void *memPtr, U16 val)
Definition: mem.h:251
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:557
#define assert(x)
Definition: debug.h:53
#define CHECK_V_F(e, f)
Definition: huf_compress.c:67
Definition: dhcpd.h:61
UINT op
Definition: effect.c:224
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 781 of file huf_compress.c.

785 {
786  return HUF_compress_internal(dst, dstSize, src, srcSize,
787  maxSymbolValue, huffLog, 0 /*4 streams*/,
788  workSpace, wkspSize,
789  NULL, NULL, 0, 0 /*bmi2*/);
790 }
static size_t HUF_compress_internal(void *dst, size_t dstSize, const void *src, size_t srcSize, unsigned maxSymbolValue, unsigned huffLog, unsigned singleStream, void *workSpace, size_t wkspSize, HUF_CElt *oldHufTable, HUF_repeat *repeat, int preferRepeat, const int bmi2)
Definition: huf_compress.c:651
smooth NULL
Definition: ftsmooth.c:416
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

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,
unsigned  singleStream,
void workSpace,
size_t  wkspSize,
HUF_CElt *  oldHufTable,
HUF_repeat *  repeat,
int  preferRepeat,
const int  bmi2 
)
static

Definition at line 651 of file huf_compress.c.

659 {
661  BYTE* const ostart = (BYTE*)dst;
662  BYTE* const oend = ostart + dstSize;
663  BYTE* op = ostart;
664 
665  /* checks & inits */
666  if (((size_t)workSpace & 3) != 0) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
667  if (wkspSize < sizeof(*table)) return ERROR(workSpace_tooSmall);
668  if (!srcSize) return 0; /* Uncompressed */
669  if (!dstSize) return 0; /* cannot fit anything within dst budget */
670  if (srcSize > HUF_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); /* current block size limit */
671  if (huffLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
672  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
673  if (!maxSymbolValue) maxSymbolValue = HUF_SYMBOLVALUE_MAX;
674  if (!huffLog) huffLog = HUF_TABLELOG_DEFAULT;
675 
676  /* Heuristic : If old table is valid, use it for small inputs */
677  if (preferRepeat && repeat && *repeat == HUF_repeat_valid) {
678  return HUF_compressCTable_internal(ostart, op, oend,
679  src, srcSize,
680  singleStream, oldHufTable, bmi2);
681  }
682 
683  /* Scan input and build symbol stats */
684  { CHECK_V_F(largest, HIST_count_wksp (table->count, &maxSymbolValue, (const BYTE*)src, srcSize, table->count) );
685  if (largest == srcSize) { *ostart = ((const BYTE*)src)[0]; return 1; } /* single symbol, rle */
686  if (largest <= (srcSize >> 7)+4) return 0; /* heuristic : probably not compressible enough */
687  }
688 
689  /* Check validity of previous table */
690  if ( repeat
691  && *repeat == HUF_repeat_check
692  && !HUF_validateCTable(oldHufTable, table->count, maxSymbolValue)) {
693  *repeat = HUF_repeat_none;
694  }
695  /* Heuristic : use existing table for small inputs */
696  if (preferRepeat && repeat && *repeat != HUF_repeat_none) {
697  return HUF_compressCTable_internal(ostart, op, oend,
698  src, srcSize,
699  singleStream, oldHufTable, bmi2);
700  }
701 
702  /* Build Huffman Tree */
703  huffLog = HUF_optimalTableLog(huffLog, srcSize, maxSymbolValue);
704  { CHECK_V_F(maxBits, HUF_buildCTable_wksp(table->CTable, table->count,
705  maxSymbolValue, huffLog,
706  table->nodeTable, sizeof(table->nodeTable)) );
707  huffLog = (U32)maxBits;
708  /* Zero unused symbols in CTable, so we can check it for validity */
709  memset(table->CTable + (maxSymbolValue + 1), 0,
710  sizeof(table->CTable) - ((maxSymbolValue + 1) * sizeof(HUF_CElt)));
711  }
712 
713  /* Write table description header */
714  { CHECK_V_F(hSize, HUF_writeCTable (op, dstSize, table->CTable, maxSymbolValue, huffLog) );
715  /* Check if using previous huffman table is beneficial */
716  if (repeat && *repeat != HUF_repeat_none) {
717  size_t const oldSize = HUF_estimateCompressedSize(oldHufTable, table->count, maxSymbolValue);
718  size_t const newSize = HUF_estimateCompressedSize(table->CTable, table->count, maxSymbolValue);
719  if (oldSize <= hSize + newSize || hSize + 12 >= srcSize) {
720  return HUF_compressCTable_internal(ostart, op, oend,
721  src, srcSize,
722  singleStream, oldHufTable, bmi2);
723  } }
724 
725  /* Use the new huffman table */
726  if (hSize + 12ul >= srcSize) { return 0; }
727  op += hSize;
728  if (repeat) { *repeat = HUF_repeat_none; }
729  if (oldHufTable)
730  memcpy(oldHufTable, table->CTable, sizeof(table->CTable)); /* Save new table */
731  }
732  return HUF_compressCTable_internal(ostart, op, oend,
733  src, srcSize,
734  singleStream, table->CTable, bmi2);
735 }
size_t HUF_writeCTable(void *dst, size_t maxDstSize, const HUF_CElt *CTable, U32 maxSymbolValue, U32 huffLog)
Definition: huf_compress.c:140
#define ERROR(name)
Definition: error_private.h:53
#define CHECK_V_F(e, f)
Definition: huf_compress.c:67
size_t HUF_buildCTable_wksp(HUF_CElt *tree, const U32 *count, U32 maxSymbolValue, U32 maxNbBits, void *workSpace, size_t wkspSize)
Definition: huf_compress.c:354
unsigned HUF_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: huf_compress.c:74
#define HUF_BLOCKSIZE_MAX
Definition: huf.h:92
static size_t HUF_estimateCompressedSize(HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
Definition: huf_compress.c:443
UINT op
Definition: effect.c:224
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
Definition: hist.c:193
#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:143
GLenum GLenum dst
Definition: glext.h:6340
static int HUF_validateCTable(const HUF_CElt *CTable, const unsigned *count, unsigned maxSymbolValue)
Definition: huf_compress.c:453
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
static size_t HUF_compressCTable_internal(BYTE *const ostart, BYTE *op, BYTE *const oend, const void *src, size_t srcSize, unsigned singleStream, const HUF_CElt *CTable, const int bmi2)
Definition: huf_compress.c:627

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 462 of file huf_compress.c.

462 { 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,
unsigned  singleStream,
const HUF_CElt *  CTable,
const int  bmi2 
)
static

Definition at line 627 of file huf_compress.c.

631 {
632  size_t const cSize = singleStream ?
633  HUF_compress1X_usingCTable_internal(op, oend - op, src, srcSize, CTable, bmi2) :
634  HUF_compress4X_usingCTable_internal(op, oend - op, src, srcSize, CTable, bmi2);
635  if (HUF_isError(cSize)) { return cSize; }
636  if (cSize==0) { return 0; } /* uncompressible */
637  op += cSize;
638  /* check compressibility */
639  if ((size_t)(op-ostart) >= srcSize-1) { return 0; }
640  return op-ostart;
641 }
#define HUF_isError
Definition: huf_compress.c:65
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:557
UINT op
Definition: effect.c:224
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:574
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 89 of file huf_compress.c.

90 {
91  BYTE* const ostart = (BYTE*) dst;
92  BYTE* op = ostart;
93  BYTE* const oend = ostart + dstSize;
94 
95  U32 maxSymbolValue = HUF_TABLELOG_MAX;
97 
98  FSE_CTable CTable[FSE_CTABLE_SIZE_U32(MAX_FSE_TABLELOG_FOR_HUFF_HEADER, HUF_TABLELOG_MAX)];
99  BYTE scratchBuffer[1<<MAX_FSE_TABLELOG_FOR_HUFF_HEADER];
100 
101  U32 count[HUF_TABLELOG_MAX+1];
102  S16 norm[HUF_TABLELOG_MAX+1];
103 
104  /* init conditions */
105  if (wtSize <= 1) return 0; /* Not compressible */
106 
107  /* Scan input and build symbol stats */
108  { unsigned const maxCount = HIST_count_simple(count, &maxSymbolValue, weightTable, wtSize); /* never fails */
109  if (maxCount == wtSize) return 1; /* only a single symbol in src : rle */
110  if (maxCount == 1) return 0; /* each symbol present maximum once => not compressible */
111  }
112 
113  tableLog = FSE_optimalTableLog(tableLog, wtSize, maxSymbolValue);
114  CHECK_F( FSE_normalizeCount(norm, tableLog, count, wtSize, maxSymbolValue) );
115 
116  /* Write table description header */
117  { CHECK_V_F(hSize, FSE_writeNCount(op, oend-op, norm, maxSymbolValue, tableLog) );
118  op += hSize;
119  }
120 
121  /* Compress */
122  CHECK_F( FSE_buildCTable_wksp(CTable, norm, maxSymbolValue, tableLog, scratchBuffer, sizeof(scratchBuffer)) );
123  { CHECK_V_F(cSize, FSE_compress_usingCTable(op, oend - op, weightTable, wtSize, CTable) );
124  if (cSize == 0) return 0; /* not enough space for compressed data */
125  op += cSize;
126  }
127 
128  return op-ostart;
129 }
FSE_PUBLIC_API unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:371
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workSpace, size_t wkspSize)
Definition: fse_compress.c:89
FSE_PUBLIC_API size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t srcSize, unsigned maxSymbolValue)
Definition: fse_compress.c:467
_Tp _STLP_CALL norm(const complex< _Tp > &__z)
Definition: _complex.h:741
#define MAX_FSE_TABLELOG_FOR_HUFF_HEADER
Definition: huf_compress.c:88
GLuint GLuint GLsizei count
Definition: gl.h:1545
unsigned FSE_CTable
Definition: fse.h:180
#define CHECK_V_F(e, f)
Definition: huf_compress.c:67
#define CHECK_F(f)
Definition: huf_compress.c:68
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:645
UINT op
Definition: effect.c:224
unsigned HIST_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
Definition: hist.c:52
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:320
signed short S16
Definition: mem.h:73
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 465 of file huf_compress.c.

466 {
467  BIT_addBitsFast(bitCPtr, CTable[symbol].val, CTable[symbol].nbBits);
468 }
GLuint GLfloat * val
Definition: glext.h:7180
MEM_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned nbBits)
Definition: bitstream.h:227

Referenced by HUF_compress1X_usingCTable_internal_body().

◆ HUF_estimateCompressedSize()

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

Definition at line 443 of file huf_compress.c.

444 {
445  size_t nbBits = 0;
446  int s;
447  for (s = 0; s <= (int)maxSymbolValue; ++s) {
448  nbBits += CTable[s].nbBits * count[s];
449  }
450  return nbBits >> 3;
451 }
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().

◆ HUF_getNbBits()

U32 HUF_getNbBits ( const void symbolTable,
U32  symbolValue 
)

Definition at line 224 of file huf_compress.c.

225 {
226  const HUF_CElt* table = (const HUF_CElt*)symbolTable;
227  assert(symbolValue <= HUF_SYMBOLVALUE_MAX);
228  return table[symbolValue].nbBits;
229 }
#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 74 of file huf_compress.c.

75 {
76  return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 1);
77 }
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
Definition: fse_compress.c:357

Referenced by HUF_compress_internal().

◆ HUF_readCTable()

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

Definition at line 176 of file huf_compress.c.

177 {
178  BYTE huffWeight[HUF_SYMBOLVALUE_MAX + 1]; /* init not required, even though some static analyzer may complain */
179  U32 rankVal[HUF_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */
180  U32 tableLog = 0;
181  U32 nbSymbols = 0;
182 
183  /* get symbol weights */
184  CHECK_V_F(readSize, HUF_readStats(huffWeight, HUF_SYMBOLVALUE_MAX+1, rankVal, &nbSymbols, &tableLog, src, srcSize));
185 
186  /* check result */
187  if (tableLog > HUF_TABLELOG_MAX) return ERROR(tableLog_tooLarge);
188  if (nbSymbols > *maxSymbolValuePtr+1) return ERROR(maxSymbolValue_tooSmall);
189 
190  /* Prepare base value per rank */
191  { U32 n, nextRankStart = 0;
192  for (n=1; n<=tableLog; n++) {
193  U32 current = nextRankStart;
194  nextRankStart += (rankVal[n] << (n-1));
195  rankVal[n] = current;
196  } }
197 
198  /* fill nbBits */
199  { U32 n; for (n=0; n<nbSymbols; n++) {
200  const U32 w = huffWeight[n];
201  CTable[n].nbBits = (BYTE)(tableLog + 1 - w);
202  } }
203 
204  /* fill val */
205  { U16 nbPerRank[HUF_TABLELOG_MAX+2] = {0}; /* support w=0=>n=tableLog+1 */
206  U16 valPerRank[HUF_TABLELOG_MAX+2] = {0};
207  { U32 n; for (n=0; n<nbSymbols; n++) nbPerRank[CTable[n].nbBits]++; }
208  /* determine stating value per rank */
209  valPerRank[tableLog+1] = 0; /* for w==0 */
210  { U16 min = 0;
211  U32 n; for (n=tableLog; n>0; n--) { /* start at n=tablelog <-> w=1 */
212  valPerRank[n] = min; /* get starting value within each rank */
213  min += nbPerRank[n];
214  min >>= 1;
215  } }
216  /* assign value within rank, symbol order */
217  { U32 n; for (n=0; n<nbSymbols; n++) CTable[n].val = valPerRank[CTable[n].nbBits]++; }
218  }
219 
220  *maxSymbolValuePtr = nbSymbols - 1;
221  return readSize;
222 }
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
#define ERROR(name)
Definition: error_private.h:53
GLdouble n
Definition: glext.h:7729
#define CHECK_V_F(e, f)
Definition: huf_compress.c:67
GLuint GLfloat * val
Definition: glext.h:7180
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
struct task_struct * current
Definition: linux.c:32
size_t HUF_readStats(BYTE *huffWeight, size_t hwSize, U32 *rankStats, U32 *nbSymbolsPtr, U32 *tableLogPtr, const void *src, size_t srcSize)

Referenced by ZSTD_loadZstdDictionary().

◆ HUF_setMaxHeight()

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

Definition at line 239 of file huf_compress.c.

240 {
241  const U32 largestBits = huffNode[lastNonNull].nbBits;
242  if (largestBits <= maxNbBits) return largestBits; /* early exit : no elt > maxNbBits */
243 
244  /* there are several too large elements (at least >= 2) */
245  { int totalCost = 0;
246  const U32 baseCost = 1 << (largestBits - maxNbBits);
247  U32 n = lastNonNull;
248 
249  while (huffNode[n].nbBits > maxNbBits) {
250  totalCost += baseCost - (1 << (largestBits - huffNode[n].nbBits));
251  huffNode[n].nbBits = (BYTE)maxNbBits;
252  n --;
253  } /* n stops at huffNode[n].nbBits <= maxNbBits */
254  while (huffNode[n].nbBits == maxNbBits) n--; /* n end at index of smallest symbol using < maxNbBits */
255 
256  /* renorm totalCost */
257  totalCost >>= (largestBits - maxNbBits); /* note : totalCost is necessarily a multiple of baseCost */
258 
259  /* repay normalized cost */
260  { U32 const noSymbol = 0xF0F0F0F0;
261  U32 rankLast[HUF_TABLELOG_MAX+2];
262  int pos;
263 
264  /* Get pos of last (smallest) symbol per rank */
265  memset(rankLast, 0xF0, sizeof(rankLast));
266  { U32 currentNbBits = maxNbBits;
267  for (pos=n ; pos >= 0; pos--) {
268  if (huffNode[pos].nbBits >= currentNbBits) continue;
269  currentNbBits = huffNode[pos].nbBits; /* < maxNbBits */
270  rankLast[maxNbBits-currentNbBits] = pos;
271  } }
272 
273  while (totalCost > 0) {
274  U32 nBitsToDecrease = BIT_highbit32(totalCost) + 1;
275  for ( ; nBitsToDecrease > 1; nBitsToDecrease--) {
276  U32 highPos = rankLast[nBitsToDecrease];
277  U32 lowPos = rankLast[nBitsToDecrease-1];
278  if (highPos == noSymbol) continue;
279  if (lowPos == noSymbol) break;
280  { U32 const highTotal = huffNode[highPos].count;
281  U32 const lowTotal = 2 * huffNode[lowPos].count;
282  if (highTotal <= lowTotal) break;
283  } }
284  /* only triggered when no more rank 1 symbol left => find closest one (note : there is necessarily at least one !) */
285  /* HUF_MAX_TABLELOG test just to please gcc 5+; but it should not be necessary */
286  while ((nBitsToDecrease<=HUF_TABLELOG_MAX) && (rankLast[nBitsToDecrease] == noSymbol))
287  nBitsToDecrease ++;
288  totalCost -= 1 << (nBitsToDecrease-1);
289  if (rankLast[nBitsToDecrease-1] == noSymbol)
290  rankLast[nBitsToDecrease-1] = rankLast[nBitsToDecrease]; /* this rank is no longer empty */
291  huffNode[rankLast[nBitsToDecrease]].nbBits ++;
292  if (rankLast[nBitsToDecrease] == 0) /* special case, reached largest symbol */
293  rankLast[nBitsToDecrease] = noSymbol;
294  else {
295  rankLast[nBitsToDecrease]--;
296  if (huffNode[rankLast[nBitsToDecrease]].nbBits != maxNbBits-nBitsToDecrease)
297  rankLast[nBitsToDecrease] = noSymbol; /* this rank is now empty */
298  } } /* while (totalCost > 0) */
299 
300  while (totalCost < 0) { /* Sometimes, cost correction overshoot */
301  if (rankLast[1] == noSymbol) { /* special case : no rank 1 symbol (using maxNbBits-1); let's create one from largest rank 0 (using maxNbBits) */
302  while (huffNode[n].nbBits == maxNbBits) n--;
303  huffNode[n+1].nbBits--;
304  rankLast[1] = n+1;
305  totalCost++;
306  continue;
307  }
308  huffNode[ rankLast[1] + 1 ].nbBits--;
309  rankLast[1]++;
310  totalCost ++;
311  } } } /* there are several too large elements (at least >= 2) */
312 
313  return maxNbBits;
314 }
GLdouble n
Definition: glext.h:7729
MEM_STATIC unsigned BIT_highbit32(U32 val)
Definition: bitstream.h:156
unsigned char BYTE
Definition: xxhash.c:193
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195

Referenced by HUF_buildCTable_wksp().

◆ HUF_sort()

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

Definition at line 322 of file huf_compress.c.

323 {
324  rankPos rank[32];
325  U32 n;
326 
327  memset(rank, 0, sizeof(rank));
328  for (n=0; n<=maxSymbolValue; n++) {
329  U32 r = BIT_highbit32(count[n] + 1);
330  rank[r].base ++;
331  }
332  for (n=30; n>0; n--) rank[n-1].base += rank[n].base;
333  for (n=0; n<32; n++) rank[n].current = rank[n].base;
334  for (n=0; n<=maxSymbolValue; n++) {
335  U32 const c = count[n];
336  U32 const r = BIT_highbit32(c+1) + 1;
337  U32 pos = rank[r].current++;
338  while ((pos > rank[r].base) && (c > huffNode[pos-1].count)) {
339  huffNode[pos] = huffNode[pos-1];
340  pos--;
341  }
342  huffNode[pos].count = c;
343  huffNode[pos].byte = (BYTE)n;
344  }
345 }
U32 current
Definition: huf_compress.c:319
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:156
const GLubyte * c
Definition: glext.h:8905
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
struct task_struct * current
Definition: linux.c:32

Referenced by HUF_buildCTable_wksp().

◆ HUF_validateCTable()

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

Definition at line 453 of file huf_compress.c.

453  {
454  int bad = 0;
455  int s;
456  for (s = 0; s <= (int)maxSymbolValue; ++s) {
457  bad |= (count[s] != 0) & (CTable[s].nbBits == 0);
458  }
459  return !bad;
460 }
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().

◆ HUF_writeCTable()

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

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

Returns
: size of saved CTable

Definition at line 140 of file huf_compress.c.

142 {
143  BYTE bitsToWeight[HUF_TABLELOG_MAX + 1]; /* precomputed conversion table */
144  BYTE huffWeight[HUF_SYMBOLVALUE_MAX];
145  BYTE* op = (BYTE*)dst;
146  U32 n;
147 
148  /* check conditions */
149  if (maxSymbolValue > HUF_SYMBOLVALUE_MAX) return ERROR(maxSymbolValue_tooLarge);
150 
151  /* convert to weight */
152  bitsToWeight[0] = 0;
153  for (n=1; n<huffLog+1; n++)
154  bitsToWeight[n] = (BYTE)(huffLog + 1 - n);
155  for (n=0; n<maxSymbolValue; n++)
156  huffWeight[n] = bitsToWeight[CTable[n].nbBits];
157 
158  /* attempt weights compression by FSE */
159  { CHECK_V_F(hSize, HUF_compressWeights(op+1, maxDstSize-1, huffWeight, maxSymbolValue) );
160  if ((hSize>1) & (hSize < maxSymbolValue/2)) { /* FSE compressed */
161  op[0] = (BYTE)hSize;
162  return hSize+1;
163  } }
164 
165  /* write raw values as 4-bits (max : 15) */
166  if (maxSymbolValue > (256-128)) return ERROR(GENERIC); /* should not happen : likely means source cannot be compressed */
167  if (((maxSymbolValue+1)/2) + 1 > maxDstSize) return ERROR(dstSize_tooSmall); /* not enough space within dst buffer */
168  op[0] = (BYTE)(128 /*special case*/ + (maxSymbolValue-1));
169  huffWeight[maxSymbolValue] = 0; /* to be sure it doesn't cause msan issue in final combination */
170  for (n=0; n<maxSymbolValue; n+=2)
171  op[(n/2)+1] = (BYTE)((huffWeight[n] << 4) + huffWeight[n+1]);
172  return ((maxSymbolValue+1)/2) + 1;
173 }
#define ERROR(name)
Definition: error_private.h:53
GLdouble n
Definition: glext.h:7729
#define CHECK_V_F(e, f)
Definition: huf_compress.c:67
UINT op
Definition: effect.c:224
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:89
GLenum GLenum dst
Definition: glext.h:6340
unsigned int U32
Definition: xxhash.c:195

Referenced by HUF_compress_internal().