hist.c File Reference

#include "mem.h"
#include "debug.h"
#include "error_private.h"
#include "hist.h"

Include dependency graph for hist.c:

Go to the source code of this file.

Enumerations
enum	HIST_checkInput_e { trustInput , checkMaxSymbolValue }

Functions
unsigned	HIST_isError (size_t code)
unsigned	HIST_count_simple (unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
static size_t	HIST_count_parallel_wksp (unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, HIST_checkInput_e check, U32 *const workSpace)
size_t	HIST_countFast_wksp (unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
size_t	HIST_countFast (unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize)
size_t	HIST_count_wksp (unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
size_t	HIST_count (unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)

Enumeration Type Documentation

HIST_checkInput_e

enum HIST_checkInput_e

Enumerator
trustInput
checkMaxSymbolValue

Definition at line 56 of file hist.c.

{ trustInput, checkMaxSymbolValue } HIST_checkInput_e;

Function Documentation

HIST_count()

size_t HIST_count	(	unsigned *	count,
		unsigned *	maxSymbolValuePtr,
		const void *	src,
		size_t	srcSize
	)

HIST_count(): Provides the precise count of each byte within a table 'count'. 'count' is a table of unsigned int, of minimum size (*maxSymbolValuePtr+1). Updates *maxSymbolValuePtr with actual largest symbol value detected.

Returns

: count of the most frequent symbol (which isn't identified). or an error code, which can be tested using HIST_isError(). note : if return == srcSize, there is only one symbol.

Definition at line 178 of file hist.c.

{
    unsigned tmpCounters[HIST_WKSP_SIZE_U32];
    return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters));
}

HIST_count_parallel_wksp()

static size_t HIST_count_parallel_wksp ( unsigned *  count, unsigned *  maxSymbolValuePtr, const void *  source, size_t  sourceSize, HIST_checkInput_e  check, U32 *const  workSpace  )

static

Definition at line 66 of file hist.c.

{
    const BYTE* ip = (const BYTE*)source;
    const BYTE* const iend = ip+sourceSize;
    unsigned maxSymbolValue = *maxSymbolValuePtr;
    unsigned max=0;
    U32* const Counting1 = workSpace;
    U32* const Counting2 = Counting1 + 256;
    U32* const Counting3 = Counting2 + 256;
    U32* const Counting4 = Counting3 + 256;
 
    memset(workSpace, 0, 4*256*sizeof(unsigned));
 
    /* safety checks */
    if (!sourceSize) {
        memset(count, 0, maxSymbolValue + 1);
        *maxSymbolValuePtr = 0;
        return 0;
    }
    if (!maxSymbolValue) maxSymbolValue = 255;            /* 0 == default */
 
    /* by stripes of 16 bytes */
    {   U32 cached = MEM_read32(ip); ip += 4;
        while (ip < iend-15) {
            U32 c = cached; cached = MEM_read32(ip); ip += 4;
            Counting1[(BYTE) c     ]++;
            Counting2[(BYTE)(c>>8) ]++;
            Counting3[(BYTE)(c>>16)]++;
            Counting4[       c>>24 ]++;
            c = cached; cached = MEM_read32(ip); ip += 4;
            Counting1[(BYTE) c     ]++;
            Counting2[(BYTE)(c>>8) ]++;
            Counting3[(BYTE)(c>>16)]++;
            Counting4[       c>>24 ]++;
            c = cached; cached = MEM_read32(ip); ip += 4;
            Counting1[(BYTE) c     ]++;
            Counting2[(BYTE)(c>>8) ]++;
            Counting3[(BYTE)(c>>16)]++;
            Counting4[       c>>24 ]++;
            c = cached; cached = MEM_read32(ip); ip += 4;
            Counting1[(BYTE) c     ]++;
            Counting2[(BYTE)(c>>8) ]++;
            Counting3[(BYTE)(c>>16)]++;
            Counting4[       c>>24 ]++;
        }
        ip-=4;
    }
 
    /* finish last symbols */
    while (ip<iend) Counting1[*ip++]++;
 
    if (check) {   /* verify stats will fit into destination table */
        U32 s; for (s=255; s>maxSymbolValue; s--) {
            Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
            if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall);
    }   }
 
    {   U32 s;
        if (maxSymbolValue > 255) maxSymbolValue = 255;
        for (s=0; s<=maxSymbolValue; s++) {
            count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
            if (count[s] > max) max = count[s];
    }   }
 
    while (!count[maxSymbolValue]) maxSymbolValue--;
    *maxSymbolValuePtr = maxSymbolValue;
    return (size_t)max;
}

Referenced by HIST_count_wksp(), and HIST_countFast_wksp().

HIST_count_simple()

unsigned HIST_count_simple	(	unsigned *	count,
		unsigned *	maxSymbolValuePtr,
		const void *	src,
		size_t	srcSize
	)

HIST_count_simple() : Same as HIST_countFast(), this function is unsafe, and will segfault if any value within src is > *maxSymbolValuePtr. It is also a bit slower for large inputs. However, it does not need any additional memory (not even on stack).

Returns

: count of the most frequent symbol. Note this function doesn't produce any error (i.e. it must succeed).

Definition at line 29 of file hist.c.

{
    const BYTE* ip = (const BYTE*)src;
    const BYTE* const end = ip + srcSize;
    unsigned maxSymbolValue = *maxSymbolValuePtr;
    unsigned largestCount=0;
 
    memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
    if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
 
    while (ip<end) {
        assert(*ip <= maxSymbolValue);
        count[*ip++]++;
    }
 
    while (!count[maxSymbolValue]) maxSymbolValue--;
    *maxSymbolValuePtr = maxSymbolValue;
 
    {   U32 s;
        for (s=0; s<=maxSymbolValue; s++)
            if (count[s] > largestCount) largestCount = count[s];
    }
 
    return largestCount;
}

Referenced by HIST_countFast_wksp(), HUF_compressWeights(), and ZSTD_rescaleFreqs().

HIST_count_wksp()

size_t HIST_count_wksp	(	unsigned *	count,
		unsigned *	maxSymbolValuePtr,
		const void *	src,
		size_t	srcSize,
		void *	workSpace,
		size_t	workSpaceSize
	)

HIST_count_wksp() : Same as HIST_count(), but using an externally provided scratch buffer. Benefit is this function will use very little stack space. workSpace is a writable buffer which must be 4-bytes aligned, workSpaceSize must be >= HIST_WKSP_SIZE

Definition at line 166 of file hist.c.

{
    if ((size_t)workSpace & 3) return ERROR(GENERIC);  /* must be aligned on 4-bytes boundaries */
    if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
    if (*maxSymbolValuePtr < 255)
        return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);
    *maxSymbolValuePtr = 255;
    return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);
}

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

HIST_countFast()

size_t HIST_countFast	(	unsigned *	count,
		unsigned *	maxSymbolValuePtr,
		const void *	src,
		size_t	srcSize
	)

HIST_countFast() : same as HIST_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr. This function is unsafe, and will segfault if any value within src is > *maxSymbolValuePtr

Definition at line 156 of file hist.c.

{
    unsigned tmpCounters[HIST_WKSP_SIZE_U32];
    return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters, sizeof(tmpCounters));
}

HIST_countFast_wksp()

size_t HIST_countFast_wksp	(	unsigned *	count,
		unsigned *	maxSymbolValuePtr,
		const void *	src,
		size_t	srcSize,
		void *	workSpace,
		size_t	workSpaceSize
	)

HIST_countFast_wksp() : Same as HIST_countFast(), but using an externally provided scratch buffer. workSpace is a writable buffer which must be 4-bytes aligned, workSpaceSize must be >= HIST_WKSP_SIZE

Definition at line 144 of file hist.c.

{
    if (sourceSize < 1500) /* heuristic threshold */
        return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
    if ((size_t)workSpace & 3) return ERROR(GENERIC);  /* must be aligned on 4-bytes boundaries */
    if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
    return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);
}

Referenced by HIST_count_wksp(), HIST_countFast(), ZSTD_buildSuperBlockEntropy_sequences(), ZSTD_compressSequences_internal(), and ZSTD_estimateSubBlockSize_symbolType().

HIST_isError()

unsigned HIST_isError

(

size_t

code

)

tells if a return value is an error code

Definition at line 24 of file hist.c.

{ return ERR_isError(code); }