1*01826a49SYabin Cui /* ****************************************************************** 2*01826a49SYabin Cui * hist : Histogram functions 3*01826a49SYabin Cui * part of Finite State Entropy project 4*01826a49SYabin Cui * Copyright (c) Meta Platforms, Inc. and affiliates. 5*01826a49SYabin Cui * 6*01826a49SYabin Cui * You can contact the author at : 7*01826a49SYabin Cui * - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy 8*01826a49SYabin Cui * - Public forum : https://groups.google.com/forum/#!forum/lz4c 9*01826a49SYabin Cui * 10*01826a49SYabin Cui * This source code is licensed under both the BSD-style license (found in the 11*01826a49SYabin Cui * LICENSE file in the root directory of this source tree) and the GPLv2 (found 12*01826a49SYabin Cui * in the COPYING file in the root directory of this source tree). 13*01826a49SYabin Cui * You may select, at your option, one of the above-listed licenses. 14*01826a49SYabin Cui ****************************************************************** */ 15*01826a49SYabin Cui 16*01826a49SYabin Cui /* --- dependencies --- */ 17*01826a49SYabin Cui #include "../common/zstd_deps.h" /* size_t */ 18*01826a49SYabin Cui 19*01826a49SYabin Cui 20*01826a49SYabin Cui /* --- simple histogram functions --- */ 21*01826a49SYabin Cui 22*01826a49SYabin Cui /*! HIST_count(): 23*01826a49SYabin Cui * Provides the precise count of each byte within a table 'count'. 24*01826a49SYabin Cui * 'count' is a table of unsigned int, of minimum size (*maxSymbolValuePtr+1). 25*01826a49SYabin Cui * Updates *maxSymbolValuePtr with actual largest symbol value detected. 26*01826a49SYabin Cui * @return : count of the most frequent symbol (which isn't identified). 27*01826a49SYabin Cui * or an error code, which can be tested using HIST_isError(). 28*01826a49SYabin Cui * note : if return == srcSize, there is only one symbol. 29*01826a49SYabin Cui */ 30*01826a49SYabin Cui size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr, 31*01826a49SYabin Cui const void* src, size_t srcSize); 32*01826a49SYabin Cui 33*01826a49SYabin Cui unsigned HIST_isError(size_t code); /**< tells if a return value is an error code */ 34*01826a49SYabin Cui 35*01826a49SYabin Cui 36*01826a49SYabin Cui /* --- advanced histogram functions --- */ 37*01826a49SYabin Cui 38*01826a49SYabin Cui #define HIST_WKSP_SIZE_U32 1024 39*01826a49SYabin Cui #define HIST_WKSP_SIZE (HIST_WKSP_SIZE_U32 * sizeof(unsigned)) 40*01826a49SYabin Cui /** HIST_count_wksp() : 41*01826a49SYabin Cui * Same as HIST_count(), but using an externally provided scratch buffer. 42*01826a49SYabin Cui * Benefit is this function will use very little stack space. 43*01826a49SYabin Cui * `workSpace` is a writable buffer which must be 4-bytes aligned, 44*01826a49SYabin Cui * `workSpaceSize` must be >= HIST_WKSP_SIZE 45*01826a49SYabin Cui */ 46*01826a49SYabin Cui size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr, 47*01826a49SYabin Cui const void* src, size_t srcSize, 48*01826a49SYabin Cui void* workSpace, size_t workSpaceSize); 49*01826a49SYabin Cui 50*01826a49SYabin Cui /** HIST_countFast() : 51*01826a49SYabin Cui * same as HIST_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr. 52*01826a49SYabin Cui * This function is unsafe, and will segfault if any value within `src` is `> *maxSymbolValuePtr` 53*01826a49SYabin Cui */ 54*01826a49SYabin Cui size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr, 55*01826a49SYabin Cui const void* src, size_t srcSize); 56*01826a49SYabin Cui 57*01826a49SYabin Cui /** HIST_countFast_wksp() : 58*01826a49SYabin Cui * Same as HIST_countFast(), but using an externally provided scratch buffer. 59*01826a49SYabin Cui * `workSpace` is a writable buffer which must be 4-bytes aligned, 60*01826a49SYabin Cui * `workSpaceSize` must be >= HIST_WKSP_SIZE 61*01826a49SYabin Cui */ 62*01826a49SYabin Cui size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr, 63*01826a49SYabin Cui const void* src, size_t srcSize, 64*01826a49SYabin Cui void* workSpace, size_t workSpaceSize); 65*01826a49SYabin Cui 66*01826a49SYabin Cui /*! HIST_count_simple() : 67*01826a49SYabin Cui * Same as HIST_countFast(), this function is unsafe, 68*01826a49SYabin Cui * and will segfault if any value within `src` is `> *maxSymbolValuePtr`. 69*01826a49SYabin Cui * It is also a bit slower for large inputs. 70*01826a49SYabin Cui * However, it does not need any additional memory (not even on stack). 71*01826a49SYabin Cui * @return : count of the most frequent symbol. 72*01826a49SYabin Cui * Note this function doesn't produce any error (i.e. it must succeed). 73*01826a49SYabin Cui */ 74*01826a49SYabin Cui unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr, 75*01826a49SYabin Cui const void* src, size_t srcSize); 76