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