summaryrefslogtreecommitdiff
path: root/vendor/github.com/DataDog/zstd/hist.c
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/DataDog/zstd/hist.c')
-rw-r--r--vendor/github.com/DataDog/zstd/hist.c203
1 files changed, 0 insertions, 203 deletions
diff --git a/vendor/github.com/DataDog/zstd/hist.c b/vendor/github.com/DataDog/zstd/hist.c
deleted file mode 100644
index 45b7babc1..000000000
--- a/vendor/github.com/DataDog/zstd/hist.c
+++ /dev/null
@@ -1,203 +0,0 @@
-/* ******************************************************************
- hist : Histogram functions
- part of Finite State Entropy project
- Copyright (C) 2013-present, Yann Collet.
-
- BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions are
- met:
-
- * Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
- * Redistributions in binary form must reproduce the above
- copyright notice, this list of conditions and the following disclaimer
- in the documentation and/or other materials provided with the
- distribution.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
- You can contact the author at :
- - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
- - Public forum : https://groups.google.com/forum/#!forum/lz4c
-****************************************************************** */
-
-/* --- dependencies --- */
-#include "mem.h" /* U32, BYTE, etc. */
-#include "debug.h" /* assert, DEBUGLOG */
-#include "error_private.h" /* ERROR */
-#include "hist.h"
-
-
-/* --- Error management --- */
-unsigned HIST_isError(size_t code) { return ERR_isError(code); }
-
-/*-**************************************************************
- * Histogram functions
- ****************************************************************/
-unsigned HIST_count_simple(unsigned* count, unsigned* maxSymbolValuePtr,
- const void* src, size_t srcSize)
-{
- const BYTE* ip = (const BYTE*)src;
- const BYTE* const end = ip + srcSize;
- unsigned maxSymbolValue = *maxSymbolValuePtr;
- unsigned largestCount=0;
-
- memset(count, 0, (maxSymbolValue+1) * sizeof(*count));
- if (srcSize==0) { *maxSymbolValuePtr = 0; return 0; }
-
- while (ip<end) {
- assert(*ip <= maxSymbolValue);
- count[*ip++]++;
- }
-
- while (!count[maxSymbolValue]) maxSymbolValue--;
- *maxSymbolValuePtr = maxSymbolValue;
-
- { U32 s;
- for (s=0; s<=maxSymbolValue; s++)
- if (count[s] > largestCount) largestCount = count[s];
- }
-
- return largestCount;
-}
-
-typedef enum { trustInput, checkMaxSymbolValue } HIST_checkInput_e;
-
-/* HIST_count_parallel_wksp() :
- * store histogram into 4 intermediate tables, recombined at the end.
- * this design makes better use of OoO cpus,
- * and is noticeably faster when some values are heavily repeated.
- * But it needs some additional workspace for intermediate tables.
- * `workSpace` size must be a table of size >= HIST_WKSP_SIZE_U32.
- * @return : largest histogram frequency,
- * or an error code (notably when histogram would be larger than *maxSymbolValuePtr). */
-static size_t HIST_count_parallel_wksp(
- unsigned* count, unsigned* maxSymbolValuePtr,
- const void* source, size_t sourceSize,
- HIST_checkInput_e check,
- U32* const workSpace)
-{
- const BYTE* ip = (const BYTE*)source;
- const BYTE* const iend = ip+sourceSize;
- unsigned maxSymbolValue = *maxSymbolValuePtr;
- unsigned max=0;
- U32* const Counting1 = workSpace;
- U32* const Counting2 = Counting1 + 256;
- U32* const Counting3 = Counting2 + 256;
- U32* const Counting4 = Counting3 + 256;
-
- memset(workSpace, 0, 4*256*sizeof(unsigned));
-
- /* safety checks */
- if (!sourceSize) {
- memset(count, 0, maxSymbolValue + 1);
- *maxSymbolValuePtr = 0;
- return 0;
- }
- if (!maxSymbolValue) maxSymbolValue = 255; /* 0 == default */
-
- /* by stripes of 16 bytes */
- { U32 cached = MEM_read32(ip); ip += 4;
- while (ip < iend-15) {
- U32 c = cached; cached = MEM_read32(ip); ip += 4;
- Counting1[(BYTE) c ]++;
- Counting2[(BYTE)(c>>8) ]++;
- Counting3[(BYTE)(c>>16)]++;
- Counting4[ c>>24 ]++;
- c = cached; cached = MEM_read32(ip); ip += 4;
- Counting1[(BYTE) c ]++;
- Counting2[(BYTE)(c>>8) ]++;
- Counting3[(BYTE)(c>>16)]++;
- Counting4[ c>>24 ]++;
- c = cached; cached = MEM_read32(ip); ip += 4;
- Counting1[(BYTE) c ]++;
- Counting2[(BYTE)(c>>8) ]++;
- Counting3[(BYTE)(c>>16)]++;
- Counting4[ c>>24 ]++;
- c = cached; cached = MEM_read32(ip); ip += 4;
- Counting1[(BYTE) c ]++;
- Counting2[(BYTE)(c>>8) ]++;
- Counting3[(BYTE)(c>>16)]++;
- Counting4[ c>>24 ]++;
- }
- ip-=4;
- }
-
- /* finish last symbols */
- while (ip<iend) Counting1[*ip++]++;
-
- if (check) { /* verify stats will fit into destination table */
- U32 s; for (s=255; s>maxSymbolValue; s--) {
- Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
- if (Counting1[s]) return ERROR(maxSymbolValue_tooSmall);
- } }
-
- { U32 s;
- if (maxSymbolValue > 255) maxSymbolValue = 255;
- for (s=0; s<=maxSymbolValue; s++) {
- count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
- if (count[s] > max) max = count[s];
- } }
-
- while (!count[maxSymbolValue]) maxSymbolValue--;
- *maxSymbolValuePtr = maxSymbolValue;
- return (size_t)max;
-}
-
-/* HIST_countFast_wksp() :
- * Same as HIST_countFast(), but using an externally provided scratch buffer.
- * `workSpace` is a writable buffer which must be 4-bytes aligned,
- * `workSpaceSize` must be >= HIST_WKSP_SIZE
- */
-size_t HIST_countFast_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
- const void* source, size_t sourceSize,
- void* workSpace, size_t workSpaceSize)
-{
- if (sourceSize < 1500) /* heuristic threshold */
- return HIST_count_simple(count, maxSymbolValuePtr, source, sourceSize);
- if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
- if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
- return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, trustInput, (U32*)workSpace);
-}
-
-/* fast variant (unsafe : won't check if src contains values beyond count[] limit) */
-size_t HIST_countFast(unsigned* count, unsigned* maxSymbolValuePtr,
- const void* source, size_t sourceSize)
-{
- unsigned tmpCounters[HIST_WKSP_SIZE_U32];
- return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, tmpCounters, sizeof(tmpCounters));
-}
-
-/* HIST_count_wksp() :
- * Same as HIST_count(), but using an externally provided scratch buffer.
- * `workSpace` size must be table of >= HIST_WKSP_SIZE_U32 unsigned */
-size_t HIST_count_wksp(unsigned* count, unsigned* maxSymbolValuePtr,
- const void* source, size_t sourceSize,
- void* workSpace, size_t workSpaceSize)
-{
- if ((size_t)workSpace & 3) return ERROR(GENERIC); /* must be aligned on 4-bytes boundaries */
- if (workSpaceSize < HIST_WKSP_SIZE) return ERROR(workSpace_tooSmall);
- if (*maxSymbolValuePtr < 255)
- return HIST_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, checkMaxSymbolValue, (U32*)workSpace);
- *maxSymbolValuePtr = 255;
- return HIST_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace, workSpaceSize);
-}
-
-size_t HIST_count(unsigned* count, unsigned* maxSymbolValuePtr,
- const void* src, size_t srcSize)
-{
- unsigned tmpCounters[HIST_WKSP_SIZE_U32];
- return HIST_count_wksp(count, maxSymbolValuePtr, src, srcSize, tmpCounters, sizeof(tmpCounters));
-}
generated by cgit v1.2.3-54-g00ecf (git 2.39.0) at 2024-11-17 15:22:21 +0000