ReactOS  0.4.15-dev-5112-g22d8c0f
hist.c
Go to the documentation of this file.
1 /* ******************************************************************
2  * hist : Histogram functions
3  * part of Finite State Entropy project
4  * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc.
5  *
6  * You can contact the author at :
7  * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
8  * - Public forum : https://groups.google.com/forum/#!forum/lz4c
9  *
10  * This source code is licensed under both the BSD-style license (found in the
11  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
12  * in the COPYING file in the root directory of this source tree).
13  * You may select, at your option, one of the above-listed licenses.
14 ****************************************************************** */
15 
16 /* --- dependencies --- */
17 #include "mem.h" /* U32, BYTE, etc. */
18 #include "debug.h" /* assert, DEBUGLOG */
19 #include "error_private.h" /* ERROR */
20 #include "hist.h"
21 
22 
23 /* --- Error management --- */
24 unsigned HIST_isError(size_t code) { return ERR_isError(code); }
25 
26 /*-**************************************************************
27  * Histogram functions
28  ****************************************************************/
29 unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
30  const void* src, size_t srcSize)
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 }
55 
57 
58 /* HIST_count_parallel_wksp() :
59  * store histogram into 4 intermediate tables, recombined at the end.
60  * this design makes better use of OoO cpus,
61  * and is noticeably faster when some values are heavily repeated.
62  * But it needs some additional workspace for intermediate tables.
63  * `workSpace` size must be a table of size >= HIST_WKSP_SIZE_U32.
64  * @return : largest histogram frequency,
65  * or an error code (notably when histogram would be larger than *maxSymbolValuePtr). */
67  unsigned* count, unsigned* maxSymbolValuePtr,
68  const void* source, size_t sourceSize,
70  U32* const workSpace)
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 }
138 
139 /* HIST_countFast_wksp() :
140  * Same as HIST_countFast(), but using an externally provided scratch buffer.
141  * `workSpace` is a writable buffer which must be 4-bytes aligned,
142  * `workSpaceSize` must be >= HIST_WKSP_SIZE
143  */
144 size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
145  const void* source, size_t sourceSize,
146  void* workSpace, size_t workSpaceSize)
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 }
154 
155 /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */
156 size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
157  const void* source, size_t sourceSize)
158 {
159  unsigned tmpCounters[HIST_WKSP_SIZE_U32];
160  return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters, sizeof(tmpCounters));
161 }
162 
163 /* HIST_count_wksp() :
164  * Same as HIST_count(), but using an externally provided scratch buffer.
165  * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */
166 size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
167  const void* source, size_t sourceSize,
168  void* workSpace, size_t workSpaceSize)
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 }
177 
178 size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr,
179  const void* src, size_t srcSize)
180 {
181  unsigned tmpCounters[HIST_WKSP_SIZE_U32];
182  return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters));
183 }
#define max(a, b)
Definition: svc.c:63
HIST_checkInput_e
Definition: hist.c:56
size_t HIST_count(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
Definition: hist.c:178
#define HIST_WKSP_SIZE
Definition: hist.h:39
#define ERROR(name)
Definition: error_private.h:53
GLuint GLuint GLsizei count
Definition: gl.h:1545
#define assert(x)
Definition: debug.h:53
#define HIST_WKSP_SIZE_U32
Definition: hist.h:38
unsigned HIST_isError(size_t code)
Definition: hist.c:24
ERR_STATIC unsigned ERR_isError(size_t code)
Definition: error_private.h:56
size_t HIST_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:166
Definition: dhcpd.h:61
const GLubyte * c
Definition: glext.h:8905
size_t HIST_countFast(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize)
Definition: hist.c:156
void check(CONTEXT *pContext)
Definition: NtContinue.c:68
GLuint GLuint end
Definition: gl.h:1545
MEM_STATIC U32 MEM_read32(const void *memPtr)
Definition: mem.h:242
GLdouble s
Definition: gl.h:2039
unsigned HIST_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
Definition: hist.c:29
GLenum src
Definition: glext.h:6340
Definition: inflate.c:139
unsigned char BYTE
Definition: xxhash.c:193
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
#define memset(x, y, z)
Definition: compat.h:39
unsigned int U32
Definition: xxhash.c:195
size_t HIST_countFast_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, void *workSpace, size_t workSpaceSize)
Definition: hist.c:144