projects/linux·blob master · refs

176 lines · 6.9 KiB

1// SPDX-License-Identifier: GPL-2.0+ OR BSD-3-Clause
2/* ******************************************************************
3 * hist : Histogram functions
4 * part of Finite State Entropy project
5 * Copyright (c) Meta Platforms, Inc. and affiliates.
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 --- */
25unsigned HIST_isError(size_t code) { return ERR_isError(code); }
26
27/*-**************************************************************
28 * Histogram functions
29 ****************************************************************/
30void HIST_add(unsigned* count, const void* src, size_t srcSize)
31{
32 const BYTE* ip = (const BYTE*)src;
33 const BYTE* const end = ip + srcSize;
34
35 while (ip<end) {
36 count[*ip++]++;
37 }
38}
39
40unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
41 const void* src, size_t srcSize)
42{
43 const BYTE* ip = (const BYTE*)src;
44 const BYTE* const end = ip + srcSize;
45 unsigned maxSymbolValue = *maxSymbolValuePtr;
46 unsigned largestCount=0;
47
48 ZSTD_memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
49 if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
50
51 while (ip<end) {
52 assert(*ip <= maxSymbolValue);
53 count[*ip++]++;
54 }
55
56 while (!count[maxSymbolValue]) maxSymbolValue--;
57 *maxSymbolValuePtr = maxSymbolValue;
58
59 { U32 s;
60 for (s=0; s<=maxSymbolValue; s++)
61 if (count[s] > largestCount) largestCount = count[s];
62 }
63
64 return largestCount;
65}
66
67typedef enum { trustInput, checkMaxSymbolValue } HIST_checkInput_e;
68
69/* HIST_count_parallel_wksp() :
70 * store histogram into 4 intermediate tables, recombined at the end.
71 * this design makes better use of OoO cpus,
72 * and is noticeably faster when some values are heavily repeated.
73 * But it needs some additional workspace for intermediate tables.
74 * `workSpace` must be a U32 table of size >= HIST_WKSP_SIZE_U32.
75 * @return : largest histogram frequency,
76 * or an error code (notably when histogram's alphabet is larger than *maxSymbolValuePtr) */
77static size_t HIST_count_parallel_wksp(
78 unsigned* count, unsigned* maxSymbolValuePtr,
79 const void* source, size_t sourceSize,
80 HIST_checkInput_e check,
81 U32* const workSpace)
82{
83 const BYTE* ip = (const BYTE*)source;
84 const BYTE* const iend = ip+sourceSize;
85 size_t const countSize = (*maxSymbolValuePtr + 1) * sizeof(*count);
86 unsigned max=0;
87 U32* const Counting1 = workSpace;
88 U32* const Counting2 = Counting1 + 256;
89 U32* const Counting3 = Counting2 + 256;
90 U32* const Counting4 = Counting3 + 256;
91
92 /* safety checks */
93 assert(*maxSymbolValuePtr <= 255);
94 if (!sourceSize) {
95 ZSTD_memset(count, 0, countSize);
96 *maxSymbolValuePtr = 0;
97 return 0;
98 }
99 ZSTD_memset(workSpace, 0, 4*256*sizeof(unsigned));
100
101 /* by stripes of 16 bytes */
102 { U32 cached = MEM_read32(ip); ip += 4;
103 while (ip < iend-15) {
104 U32 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 c = cached; cached = MEM_read32(ip); ip += 4;
115 Counting1[(BYTE) c ]++;
116 Counting2[(BYTE)(c>>8) ]++;
117 Counting3[(BYTE)(c>>16)]++;
118 Counting4[ c>>24 ]++;
119 c = cached; cached = MEM_read32(ip); ip += 4;
120 Counting1[(BYTE) c ]++;
121 Counting2[(BYTE)(c>>8) ]++;
122 Counting3[(BYTE)(c>>16)]++;
123 Counting4[ c>>24 ]++;
124 }
125 ip-=4;
126 }
127
128 /* finish last symbols */
129 while (ip<iend) Counting1[*ip++]++;
130
131 { U32 s;
132 for (s=0; s<256; s++) {
133 Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
134 if (Counting1[s] > max) max = Counting1[s];
135 } }
136
137 { unsigned maxSymbolValue = 255;
138 while (!Counting1[maxSymbolValue]) maxSymbolValue--;
139 if (check && maxSymbolValue > *maxSymbolValuePtr) return ERROR(maxSymbolValue_tooSmall);
140 *maxSymbolValuePtr = maxSymbolValue;
141 ZSTD_memmove(count, Counting1, countSize); /* in case count & Counting1 are overlapping */
142 }
143 return (size_t)max;
144}
145
146/* HIST_countFast_wksp() :
147 * Same as HIST_countFast(), but using an externally provided scratch buffer.
148 * `workSpace` is a writable buffer which must be 4-bytes aligned,
149 * `workSpaceSize` must be >= HIST_WKSP_SIZE
150 */
151size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
152 const void* source, size_t sourceSize,
153 void* workSpace, size_t workSpaceSize)
154{
155 if (sourceSize < 1500) /* heuristic threshold */
156 return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
157 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
158 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
159 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);
160}
161
162/* HIST_count_wksp() :
163 * Same as HIST_count(), but using an externally provided scratch buffer.
164 * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */
165size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
166 const void* source, size_t sourceSize,
167 void* workSpace, size_t workSpaceSize)
168{
169 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
170 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
171 if (*maxSymbolValuePtr < 255)
172 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);
173 *maxSymbolValuePtr = 255;
174 return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);
175}
176