166 lines · c
1/* ******************************************************************2 * hist : Histogram functions3 * part of Finite State Entropy project4 * Copyright (c) Yann Collet, Facebook, Inc.5 *6 * You can contact the author at :7 * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy8 * - Public forum : https://groups.google.com/forum/#!forum/lz4c9 *10 * This source code is licensed under both the BSD-style license (found in the11 * LICENSE file in the root directory of this source tree) and the GPLv2 (found12 * 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 "../common/mem.h" /* U32, BYTE, etc. */18#include "../common/debug.h" /* assert, DEBUGLOG */19#include "../common/error_private.h" /* ERROR */20#include "hist.h"21 22 23/* --- Error management --- */24unsigned HIST_isError(size_t code) { return ERR_isError(code); }25 26/*-**************************************************************27 * Histogram functions28 ****************************************************************/29unsigned 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 ZSTD_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 56typedef enum { trustInput, checkMaxSymbolValue } HIST_checkInput_e;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` must be a U32 table of size >= HIST_WKSP_SIZE_U32.64 * @return : largest histogram frequency,65 * or an error code (notably when histogram's alphabet is larger than *maxSymbolValuePtr) */66static size_t HIST_count_parallel_wksp(67 unsigned* count, unsigned* maxSymbolValuePtr,68 const void* source, size_t sourceSize,69 HIST_checkInput_e check,70 U32* const workSpace)71{72 const BYTE* ip = (const BYTE*)source;73 const BYTE* const iend = ip+sourceSize;74 size_t const countSize = (*maxSymbolValuePtr + 1) * sizeof(*count);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 /* safety checks */82 assert(*maxSymbolValuePtr <= 255);83 if (!sourceSize) {84 ZSTD_memset(count, 0, countSize);85 *maxSymbolValuePtr = 0;86 return 0;87 }88 ZSTD_memset(workSpace, 0, 4*256*sizeof(unsigned));89 90 /* by stripes of 16 bytes */91 { U32 cached = MEM_read32(ip); ip += 4;92 while (ip < iend-15) {93 U32 c = cached; cached = MEM_read32(ip); ip += 4;94 Counting1[(BYTE) c ]++;95 Counting2[(BYTE)(c>>8) ]++;96 Counting3[(BYTE)(c>>16)]++;97 Counting4[ c>>24 ]++;98 c = cached; cached = MEM_read32(ip); ip += 4;99 Counting1[(BYTE) c ]++;100 Counting2[(BYTE)(c>>8) ]++;101 Counting3[(BYTE)(c>>16)]++;102 Counting4[ c>>24 ]++;103 c = cached; cached = MEM_read32(ip); ip += 4;104 Counting1[(BYTE) c ]++;105 Counting2[(BYTE)(c>>8) ]++;106 Counting3[(BYTE)(c>>16)]++;107 Counting4[ c>>24 ]++;108 c = cached; cached = MEM_read32(ip); ip += 4;109 Counting1[(BYTE) c ]++;110 Counting2[(BYTE)(c>>8) ]++;111 Counting3[(BYTE)(c>>16)]++;112 Counting4[ c>>24 ]++;113 }114 ip-=4;115 }116 117 /* finish last symbols */118 while (ip<iend) Counting1[*ip++]++;119 120 { U32 s;121 for (s=0; s<256; s++) {122 Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];123 if (Counting1[s] > max) max = Counting1[s];124 } }125 126 { unsigned maxSymbolValue = 255;127 while (!Counting1[maxSymbolValue]) maxSymbolValue--;128 if (check && maxSymbolValue > *maxSymbolValuePtr) return ERROR(maxSymbolValue_tooSmall);129 *maxSymbolValuePtr = maxSymbolValue;130 ZSTD_memmove(count, Counting1, countSize); /* in case count & Counting1 are overlapping */131 }132 return (size_t)max;133}134 135/* HIST_countFast_wksp() :136 * Same as HIST_countFast(), but using an externally provided scratch buffer.137 * `workSpace` is a writable buffer which must be 4-bytes aligned,138 * `workSpaceSize` must be >= HIST_WKSP_SIZE139 */140size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,141 const void* source, size_t sourceSize,142 void* workSpace, size_t workSpaceSize)143{144 if (sourceSize < 1500) /* heuristic threshold */145 return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);146 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */147 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);148 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);149}150 151/* HIST_count_wksp() :152 * Same as HIST_count(), but using an externally provided scratch buffer.153 * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */154size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,155 const void* source, size_t sourceSize,156 void* workSpace, size_t workSpaceSize)157{158 if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */159 if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);160 if (*maxSymbolValuePtr < 255)161 return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);162 *maxSymbolValuePtr = 255;163 return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);164}165 166