1 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0-only
2 /* ******************************************************************
3 * hist : Histogram functions
4 * part of Finite State Entropy project
5 * Copyright (c) 2013-2020, Yann Collet, Facebook, Inc.
6 *
7 * You can contact the author at :
8 * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
9 * - Public forum : https://groups.google.com/forum/#!forum/lz4c
10 *
11 * This source code is licensed under both the BSD-style license (found in the
12 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
13 * in the COPYING file in the root directory of this source tree).
14 * You may select, at your option, one of the above-listed licenses.
15 ****************************************************************** */
16
17 /* --- dependencies --- */
18 #include "../common/mem.h" /* U32, BYTE, etc. */
19 #include "../common/debug.h" /* assert, DEBUGLOG */
20 #include "../common/error_private.h" /* ERROR */
21 #include "hist.h"
22
23
24 /* --- Error management --- */
HIST_isError(size_t code)25 unsigned HIST_isError(size_t code) { return ERR_isError(code); }
26
27 /*-**************************************************************
28 * Histogram functions
29 ****************************************************************/
HIST_count_simple(unsigned * count,unsigned * maxSymbolValuePtr,const void * src,size_t srcSize)30 unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
31 const void* src, size_t srcSize)
32 {
33 const BYTE* ip = (const BYTE*)src;
34 const BYTE* const end = ip + srcSize;
35 unsigned maxSymbolValue = *maxSymbolValuePtr;
36 unsigned largestCount=0;
37
38 memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
39 if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
40
41 while (ip<end) {
42 assert(*ip <= maxSymbolValue);
43 count[*ip++]++;
44 }
45
46 while (!count[maxSymbolValue]) maxSymbolValue--;
47 *maxSymbolValuePtr = maxSymbolValue;
48
49 { U32 s;
50 for (s=0; s<=maxSymbolValue; s++)
51 if (count[s] > largestCount) largestCount = count[s];
52 }
53
54 return largestCount;
55 }
56
57 typedef enum { trustInput, checkMaxSymbolValue } HIST_checkInput_e;
58
59 /* HIST_count_parallel_wksp() :
60 * store histogram into 4 intermediate tables, recombined at the end.
61 * this design makes better use of OoO cpus,
62 * and is noticeably faster when some values are heavily repeated.
63 * But it needs some additional workspace for intermediate tables.
64 * `workSpace` size must be a table of size >= HIST_WKSP_SIZE_U32.
65 * @return : largest histogram frequency,
66 * or an error code (notably when histogram would be larger than *maxSymbolValuePtr). */
HIST_count_parallel_wksp(unsigned * count,unsigned * maxSymbolValuePtr,const void * source,size_t sourceSize,HIST_checkInput_e check,U32 * const workSpace)67 static size_t HIST_count_parallel_wksp(
68 unsigned* count, unsigned* maxSymbolValuePtr,
69 const void* source, size_t sourceSize,
70 HIST_checkInput_e check,
71 U32* const workSpace)
72 {
73 const BYTE* ip = (const BYTE*)source;
74 const BYTE* const iend = ip+sourceSize;
75 unsigned maxSymbolValue = *maxSymbolValuePtr;
76 unsigned max=0;
77 U32* const Counting1 = workSpace;
78 U32* const Counting2 = Counting1 + 256;
79 U32* const Counting3 = Counting2 + 256;
80 U32* const Counting4 = Counting3 + 256;
81
82 memset(workSpace, 0, 4*256*sizeof(unsigned));
83
84 /* safety checks */
85 if (!sourceSize) {
86 memset(count, 0, maxSymbolValue + 1);
87 *maxSymbolValuePtr = 0;
88 return 0;
89 }
90 if (!maxSymbolValue) maxSymbolValue = 255; /* 0 == default */
91
92 /* by stripes of 16 bytes */
93 { U32 cached = MEM_read32(ip); ip += 4;
94 while (ip < iend-15) {
95 U32 c = cached; cached = MEM_read32(ip); ip += 4;
96 Counting1[(BYTE) c ]++;
97 Counting2[(BYTE)(c>>8) ]++;
98 Counting3[(BYTE)(c>>16)]++;
99 Counting4[ c>>24 ]++;
100 c = cached; cached = MEM_read32(ip); ip += 4;
101 Counting1[(BYTE) c ]++;
102 Counting2[(BYTE)(c>>8) ]++;
103 Counting3[(BYTE)(c>>16)]++;
104 Counting4[ c>>24 ]++;
105 c = cached; cached = MEM_read32(ip); ip += 4;
106 Counting1[(BYTE) c ]++;
107 Counting2[(BYTE)(c>>8) ]++;
108 Counting3[(BYTE)(c>>16)]++;
109 Counting4[ c>>24 ]++;
110 c = cached; cached = MEM_read32(ip); ip += 4;
111 Counting1[(BYTE) c ]++;
112 Counting2[(BYTE)(c>>8) ]++;
113 Counting3[(BYTE)(c>>16)]++;
114 Counting4[ c>>24 ]++;
115 }
116 ip-=4;
117 }
118
119 /* finish last symbols */
120 while (ip<iend) Counting1[*ip++]++;
121
122 if (check) { /* verify stats will fit into destination table */
123 U32 s; for (s=255; s>maxSymbolValue; s--) {
124 Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
125 if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall);
126 } }
127
128 { U32 s;
129 if (maxSymbolValue > 255) maxSymbolValue = 255;
130 for (s=0; s<=maxSymbolValue; s++) {
131 count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
132 if (count[s] > max) max = count[s];
133 } }
134
135 while (!count[maxSymbolValue]) maxSymbolValue--;
136 *maxSymbolValuePtr = maxSymbolValue;
137 return (size_t)max;
138 }
139
140 /* HIST_countFast_wksp() :
141 * Same as HIST_countFast(), but using an externally provided scratch buffer.
142 * `workSpace` is a writable buffer which must be 4-bytes aligned,
143 * `workSpaceSize` must be >= HIST_WKSP_SIZE
144 */
HIST_countFast_wksp(unsigned * count,unsigned * maxSymbolValuePtr,const void * source,size_t sourceSize,void * workSpace,size_t workSpaceSize)145 size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
146 const void* source, size_t sourceSize,
147 void* workSpace, size_t workSpaceSize)
148 {
149 if (sourceSize < 1500) /* heuristic threshold */
150 return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
151 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
152 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
153 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);
154 }
155
156 /* fast variant (unsafe : won't check if src contains values beyond count[] limit) */
HIST_countFast(unsigned * count,unsigned * maxSymbolValuePtr,const void * source,size_t sourceSize)157 size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
158 const void* source, size_t sourceSize)
159 {
160 unsigned tmpCounters[HIST_WKSP_SIZE_U32];
161 return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters, sizeof(tmpCounters));
162 }
163
164 /* HIST_count_wksp() :
165 * Same as HIST_count(), but using an externally provided scratch buffer.
166 * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */
HIST_count_wksp(unsigned * count,unsigned * maxSymbolValuePtr,const void * source,size_t sourceSize,void * workSpace,size_t workSpaceSize)167 size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
168 const void* source, size_t sourceSize,
169 void* workSpace, size_t workSpaceSize)
170 {
171 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
172 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
173 if (*maxSymbolValuePtr < 255)
174 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);
175 *maxSymbolValuePtr = 255;
176 return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);
177 }
178
HIST_count(unsigned * count,unsigned * maxSymbolValuePtr,const void * src,size_t srcSize)179 size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr,
180 const void* src, size_t srcSize)
181 {
182 unsigned tmpCounters[HIST_WKSP_SIZE_U32];
183 return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters));
184 }
185