ReactOS  0.4.15-dev-439-g292f67a
hist.c File Reference
#include "mem.h"
#include "debug.h"
#include "error_private.h"
#include "hist.h"
#include <ntifs.h>
#include <ntddk.h>
Include dependency graph for hist.c:

Go to the source code of this file.

Macros

#define HIST_ALLOC_TAG   0x54534948
 

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, unsigned checkMax, unsigned *const workSpace)
 
size_t HIST_countFast_wksp (unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
 
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, unsigned *workSpace)
 
size_t HIST_count (unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
 

Macro Definition Documentation

◆ HIST_ALLOC_TAG

#define HIST_ALLOC_TAG   0x54534948

Definition at line 44 of file hist.c.

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 202 of file hist.c.

204 {
205  unsigned tmpCounters[HIST_WKSP_SIZE_U32];
206  return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters);
207 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define HIST_WKSP_SIZE_U32
Definition: hist.h:58
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
Definition: hist.c:193
GLenum src
Definition: glext.h:6340

◆ HIST_count_parallel_wksp()

static size_t HIST_count_parallel_wksp ( unsigned count,
unsigned maxSymbolValuePtr,
const void source,
size_t  sourceSize,
unsigned  checkMax,
unsigned *const  workSpace 
)
static

Definition at line 88 of file hist.c.

93 {
94  const BYTE* ip = (const BYTE*)source;
95  const BYTE* const iend = ip+sourceSize;
96  unsigned maxSymbolValue = *maxSymbolValuePtr;
97  unsigned max=0;
98  U32* const Counting1 = workSpace;
99  U32* const Counting2 = Counting1 + 256;
100  U32* const Counting3 = Counting2 + 256;
101  U32* const Counting4 = Counting3 + 256;
102 
103  memset(workSpace, 0, 4*256*sizeof(unsigned));
104 
105  /* safety checks */
106  if (!sourceSize) {
107  memset(count, 0, maxSymbolValue + 1);
108  *maxSymbolValuePtr = 0;
109  return 0;
110  }
111  if (!maxSymbolValue) maxSymbolValue = 255; /* 0 == default */
112 
113  /* by stripes of 16 bytes */
114  { U32 cached = MEM_read32(ip); ip += 4;
115  while (ip < iend-15) {
116  U32 c = cached; cached = MEM_read32(ip); ip += 4;
117  Counting1[(BYTE) c ]++;
118  Counting2[(BYTE)(c>>8) ]++;
119  Counting3[(BYTE)(c>>16)]++;
120  Counting4[ c>>24 ]++;
121  c = cached; cached = MEM_read32(ip); ip += 4;
122  Counting1[(BYTE) c ]++;
123  Counting2[(BYTE)(c>>8) ]++;
124  Counting3[(BYTE)(c>>16)]++;
125  Counting4[ c>>24 ]++;
126  c = cached; cached = MEM_read32(ip); ip += 4;
127  Counting1[(BYTE) c ]++;
128  Counting2[(BYTE)(c>>8) ]++;
129  Counting3[(BYTE)(c>>16)]++;
130  Counting4[ c>>24 ]++;
131  c = cached; cached = MEM_read32(ip); ip += 4;
132  Counting1[(BYTE) c ]++;
133  Counting2[(BYTE)(c>>8) ]++;
134  Counting3[(BYTE)(c>>16)]++;
135  Counting4[ c>>24 ]++;
136  }
137  ip-=4;
138  }
139 
140  /* finish last symbols */
141  while (ip<iend) Counting1[*ip++]++;
142 
143  if (checkMax) { /* verify stats will fit into destination table */
144  U32 s; for (s=255; s>maxSymbolValue; s--) {
145  Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
146  if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall);
147  } }
148 
149  { U32 s;
150  if (maxSymbolValue > 255) maxSymbolValue = 255;
151  for (s=0; s<=maxSymbolValue; s++) {
152  count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
153  if (count[s] > max) max = count[s];
154  } }
155 
156  while (!count[maxSymbolValue]) maxSymbolValue--;
157  *maxSymbolValuePtr = maxSymbolValue;
158  return (size_t)max;
159 }
#define max(a, b)
Definition: svc.c:63
#define ERROR(name)
Definition: error_private.h:53
GLuint GLuint GLsizei count
Definition: gl.h:1545
Definition: dhcpd.h:61
const GLubyte * c
Definition: glext.h:8905
MEM_STATIC U32 MEM_read32(const void *memPtr)
Definition: mem.h:169
GLdouble s
Definition: gl.h:2039
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 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 52 of file hist.c.

54 {
55  const BYTE* ip = (const BYTE*)src;
56  const BYTE* const end = ip + srcSize;
57  unsigned maxSymbolValue = *maxSymbolValuePtr;
58  unsigned largestCount=0;
59 
60  memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
61  if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
62 
63  while (ip<end) {
64  assert(*ip <= maxSymbolValue);
65  count[*ip++]++;
66  }
67 
68  while (!count[maxSymbolValue]) maxSymbolValue--;
69  *maxSymbolValuePtr = maxSymbolValue;
70 
71  { U32 s;
72  for (s=0; s<=maxSymbolValue; s++)
73  if (count[s] > largestCount) largestCount = count[s];
74  }
75 
76  return largestCount;
77 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define assert(x)
Definition: debug.h:53
GLuint GLuint end
Definition: gl.h:1545
Definition: dhcpd.h:61
GLdouble s
Definition: gl.h:2039
GLenum src
Definition: glext.h:6340
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 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,
unsigned workSpace 
)

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 must be a table of unsigned of size >= HIST_WKSP_SIZE_U32

Definition at line 193 of file hist.c.

195 {
196  if (*maxSymbolValuePtr < 255)
197  return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 1, workSpace);
198  *maxSymbolValuePtr = 255;
199  return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace);
200 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
size_t HIST_countFast_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
Definition: hist.c:164
static size_t HIST_count_parallel_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned checkMax, unsigned *const workSpace)
Definition: hist.c:88

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

◆ 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 174 of file hist.c.

176 {
177  unsigned* tmpCounters = ExAllocatePoolWithTag(NonPagedPool, sizeof(unsigned) * HIST_WKSP_SIZE_U32, HIST_ALLOC_TAG);
178  size_t ret;
179 
180  if (!tmpCounters)
181  return 0;
182 
183  ret = HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters);
184 
185  ExFreePool(tmpCounters);
186 
187  return ret;
188 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define HIST_WKSP_SIZE_U32
Definition: hist.h:58
size_t HIST_countFast_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
Definition: hist.c:164
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
int ret
#define HIST_ALLOC_TAG
Definition: hist.c:44
#define ExFreePool(addr)
Definition: env_spec_w32.h:352

◆ HIST_countFast_wksp()

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

HIST_countFast_wksp() : Same as HIST_countFast(), but using an externally provided scratch buffer. workSpace must be a table of unsigned of size >= HIST_WKSP_SIZE_U32

Definition at line 164 of file hist.c.

167 {
168  if (sourceSize < 1500) /* heuristic threshold */
169  return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
170  return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 0, workSpace);
171 }
GLuint GLuint GLsizei count
Definition: gl.h:1545
static size_t HIST_count_parallel_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned checkMax, unsigned *const workSpace)
Definition: hist.c:88
unsigned HIST_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
Definition: hist.c:52

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

◆ HIST_isError()

unsigned HIST_isError ( size_t  code)

tells if a return value is an error code

Definition at line 47 of file hist.c.

47 { return ERR_isError(code); }
ERR_STATIC unsigned ERR_isError(size_t code)
Definition: error_private.h:56