ReactOS 0.4.16-dev-109-gf4cb10f
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

Enumerator
trustInput 
checkMaxSymbolValue 

Definition at line 56 of file hist.c.

HIST_checkInput_e
Definition: hist.c:56
@ checkMaxSymbolValue
Definition: hist.c:56
@ trustInput
Definition: hist.c:56

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.

180{
181 unsigned tmpCounters[HIST_WKSP_SIZE_U32];
182 return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters));
183}
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLenum src
Definition: glext.h:6340
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:166
#define HIST_WKSP_SIZE_U32
Definition: hist.h:38

◆ 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.

71{
72 const BYTE* ip = (const BYTE*)source;
73 const BYTE* const iend = ip+sourceSize;
74 unsigned maxSymbolValue = *maxSymbolValuePtr;
75 unsigned max=0;
76 U32* const Counting1 = workSpace;
77 U32* const Counting2 = Counting1 + 256;
78 U32* const Counting3 = Counting2 + 256;
79 U32* const Counting4 = Counting3 + 256;
80
81 memset(workSpace, 0, 4*256*sizeof(unsigned));
82
83 /* safety checks */
84 if (!sourceSize) {
85 memset(count, 0, maxSymbolValue + 1);
86 *maxSymbolValuePtr = 0;
87 return 0;
88 }
89 if (!maxSymbolValue) maxSymbolValue = 255; /* 0 == default */
90
91 /* by stripes of 16 bytes */
92 { U32 cached = MEM_read32(ip); ip += 4;
93 while (ip < iend-15) {
94 U32 c = cached; cached = MEM_read32(ip); ip += 4;
95 Counting1[(BYTE) c ]++;
96 Counting2[(BYTE)(c>>8) ]++;
97 Counting3[(BYTE)(c>>16)]++;
98 Counting4[ c>>24 ]++;
99 c = cached; cached = MEM_read32(ip); ip += 4;
100 Counting1[(BYTE) c ]++;
101 Counting2[(BYTE)(c>>8) ]++;
102 Counting3[(BYTE)(c>>16)]++;
103 Counting4[ c>>24 ]++;
104 c = cached; cached = MEM_read32(ip); ip += 4;
105 Counting1[(BYTE) c ]++;
106 Counting2[(BYTE)(c>>8) ]++;
107 Counting3[(BYTE)(c>>16)]++;
108 Counting4[ c>>24 ]++;
109 c = cached; cached = MEM_read32(ip); ip += 4;
110 Counting1[(BYTE) c ]++;
111 Counting2[(BYTE)(c>>8) ]++;
112 Counting3[(BYTE)(c>>16)]++;
113 Counting4[ c>>24 ]++;
114 }
115 ip-=4;
116 }
117
118 /* finish last symbols */
119 while (ip<iend) Counting1[*ip++]++;
120
121 if (check) { /* verify stats will fit into destination table */
122 U32 s; for (s=255; s>maxSymbolValue; s--) {
123 Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
124 if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall);
125 } }
126
127 { U32 s;
128 if (maxSymbolValue > 255) maxSymbolValue = 255;
129 for (s=0; s<=maxSymbolValue; s++) {
130 count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
131 if (count[s] > max) max = count[s];
132 } }
133
134 while (!count[maxSymbolValue]) maxSymbolValue--;
135 *maxSymbolValuePtr = maxSymbolValue;
136 return (size_t)max;
137}
#define check(expected, result)
Definition: dplayx.c:32
MEM_STATIC U32 MEM_read32(const void *memPtr)
Definition: mem.h:242
#define ERROR(name)
Definition: error_private.h:53
GLdouble s
Definition: gl.h:2039
const GLubyte * c
Definition: glext.h:8905
#define memset(x, y, z)
Definition: compat.h:39
Definition: dhcpd.h:62
#define max(a, b)
Definition: svc.c:63
unsigned char BYTE
Definition: xxhash.c:193
unsigned int U32
Definition: xxhash.c:195

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.

31{
32 const BYTE* ip = (const BYTE*)src;
33 const BYTE* const end = ip + srcSize;
34 unsigned maxSymbolValue = *maxSymbolValuePtr;
35 unsigned largestCount=0;
36
37 memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
38 if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
39
40 while (ip<end) {
41 assert(*ip <= maxSymbolValue);
42 count[*ip++]++;
43 }
44
45 while (!count[maxSymbolValue]) maxSymbolValue--;
46 *maxSymbolValuePtr = maxSymbolValue;
47
48 { U32 s;
49 for (s=0; s<=maxSymbolValue; s++)
50 if (count[s] > largestCount) largestCount = count[s];
51 }
52
53 return largestCount;
54}
#define assert(x)
Definition: debug.h:53
GLuint GLuint end
Definition: gl.h:1545

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.

169{
170 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
171 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
172 if (*maxSymbolValuePtr < 255)
173 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);
174 *maxSymbolValuePtr = 255;
175 return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);
176}
static size_t HIST_count_parallel_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, HIST_checkInput_e check, U32 *const workSpace)
Definition: hist.c:66
size_t HIST_countFast_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:144
#define HIST_WKSP_SIZE
Definition: hist.h:39

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.

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

◆ 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.

147{
148 if (sourceSize < 1500) /* heuristic threshold */
149 return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
150 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
151 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
152 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);
153}
unsigned HIST_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
Definition: hist.c:29

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.

24{ return ERR_isError(code); }
ERR_STATIC unsigned ERR_isError(size_t code)
Definition: error_private.h:56
Definition: inflate.c:139