mercurial-scm/hg: contrib/python-zstandard/zstd/dictBuilder/fastcover.c annotate

annotate contrib/python-zstandard/zstd/dictBuilder/fastcover.c @ 53042:cdd7bf612c7b stable tip

bundle-spec: properly format boolean parameter (issue6960) This was breaking automatic clone bundle generation. This changeset fixes it and add a test to catch it in the future.

author	Pierre-Yves David <pierre-yves.david@octobus.net>
date	Tue, 11 Mar 2025 02:29:42 +0100
parents	69de49c4e39c
children

rev	line source
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1 /-************************************
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	2 * Dependencies
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	3 ***************************************/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	4 #include <stdio.h> /* fprintf */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	5 #include <stdlib.h> /* malloc, free, qsort */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	6 #include <string.h> /* memset */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	7 #include <time.h> /* clock */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	8
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	9 #include "mem.h" /* read */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	10 #include "pool.h"
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	11 #include "threading.h"
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	12 #include "cover.h"
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	13 #include "zstd_internal.h" /* includes zstd.h */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	14 #ifndef ZDICT_STATIC_LINKING_ONLY
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	15 #define ZDICT_STATIC_LINKING_ONLY
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	16 #endif
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	17 #include "zdict.h"
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	18
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	19
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	20 /-************************************
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	21 * Constants
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	22 ***************************************/
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	23 #define FASTCOVER_MAX_SAMPLES_SIZE (sizeof(size_t) == 8 ? ((unsigned)-1) : ((unsigned)1 GB))
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	24 #define FASTCOVER_MAX_F 31
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	25 #define FASTCOVER_MAX_ACCEL 10
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	26 #define DEFAULT_SPLITPOINT 0.75
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	27 #define DEFAULT_F 20
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	28 #define DEFAULT_ACCEL 1
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	29
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	30
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	31 /-************************************
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	32 * Console display
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	33 ***************************************/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	34 static int g_displayLevel = 2;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	35 #define DISPLAY(...) \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	36 { \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	37 fprintf(stderr, __VA_ARGS__); \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	38 fflush(stderr); \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	39 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	40 #define LOCALDISPLAYLEVEL(displayLevel, l, ...) \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	41 if (displayLevel >= l) { \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	42 DISPLAY(__VA_ARGS__); \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	43 } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	44 #define DISPLAYLEVEL(l, ...) LOCALDISPLAYLEVEL(g_displayLevel, l, __VA_ARGS__)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	45
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	46 #define LOCALDISPLAYUPDATE(displayLevel, l, ...) \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	47 if (displayLevel >= l) { \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	48 if ((clock() - g_time > refreshRate) \|\| (displayLevel >= 4)) { \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49 g_time = clock(); \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	50 DISPLAY(__VA_ARGS__); \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 } \
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	53 #define DISPLAYUPDATE(l, ...) LOCALDISPLAYUPDATE(g_displayLevel, l, __VA_ARGS__)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	54 static const clock_t refreshRate = CLOCKS_PER_SEC * 15 / 100;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	55 static clock_t g_time = 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	56
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	57
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	58 /-************************************
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	59 * Hash Functions
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	60 ***************************************/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	61 static const U64 prime6bytes = 227718039650203ULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	62 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	63 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	64
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	65 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	66 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	67 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	68
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	69
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	70 /**
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	71 * Hash the d-byte value pointed to by p and mod 2^f
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	72 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	73 static size_t FASTCOVER_hashPtrToIndex(const void* p, U32 h, unsigned d) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	74 if (d == 6) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	75 return ZSTD_hash6Ptr(p, h) & ((1 << h) - 1);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	76 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	77 return ZSTD_hash8Ptr(p, h) & ((1 << h) - 1);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	78 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	79
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	80
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	81 /-************************************
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	82 * Acceleration
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	83 ***************************************/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	84 typedef struct {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	85 unsigned finalize; /* Percentage of training samples used for ZDICT_finalizeDictionary */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	86 unsigned skip; /* Number of dmer skipped between each dmer counted in computeFrequency */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	87 } FASTCOVER_accel_t;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	88
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	89
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	90 static const FASTCOVER_accel_t FASTCOVER_defaultAccelParameters[FASTCOVER_MAX_ACCEL+1] = {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	91 { 100, 0 }, /* accel = 0, should not happen because accel = 0 defaults to accel = 1 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	92 { 100, 0 }, /* accel = 1 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	93 { 50, 1 }, /* accel = 2 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	94 { 34, 2 }, /* accel = 3 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	95 { 25, 3 }, /* accel = 4 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	96 { 20, 4 }, /* accel = 5 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	97 { 17, 5 }, /* accel = 6 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	98 { 14, 6 }, /* accel = 7 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	99 { 13, 7 }, /* accel = 8 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	100 { 11, 8 }, /* accel = 9 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	101 { 10, 9 }, /* accel = 10 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	102 };
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	103
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	104
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	105 /-************************************
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	106 * Context
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	107 ***************************************/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	108 typedef struct {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	109 const BYTE *samples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	110 size_t *offsets;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	111 const size_t *samplesSizes;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	112 size_t nbSamples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	113 size_t nbTrainSamples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	114 size_t nbTestSamples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	115 size_t nbDmers;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	116 U32 *freqs;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	117 unsigned d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	118 unsigned f;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	119 FASTCOVER_accel_t accelParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	120 } FASTCOVER_ctx_t;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	121
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	122
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	123 /-************************************
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	124 * Helper functions
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	125 ***************************************/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	126 /**
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127 * Selects the best segment in an epoch.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128 * Segments of are scored according to the function:
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 *
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 * Let F(d) be the frequency of all dmers with hash value d.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	131 * Let S_i be hash value of the dmer at position i of segment S which has length k.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132 *
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	133 * Score(S) = F(S_1) + F(S_2) + ... + F(S_{k-d+1})
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	134 *
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	135 * Once the dmer with hash value d is in the dictionary we set F(d) = 0.
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	137 static COVER_segment_t FASTCOVER_selectSegment(const FASTCOVER_ctx_t *ctx,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	138 U32 *freqs, U32 begin, U32 end,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	139 ZDICT_cover_params_t parameters,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	140 U16* segmentFreqs) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	141 /* Constants */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142 const U32 k = parameters.k;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	143 const U32 d = parameters.d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	144 const U32 f = ctx->f;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	145 const U32 dmersInK = k - d + 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	147 /* Try each segment (activeSegment) and save the best (bestSegment) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	148 COVER_segment_t bestSegment = {0, 0, 0};
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	149 COVER_segment_t activeSegment;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	150
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	151 /* Reset the activeDmers in the segment */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	152 /* The activeSegment starts at the beginning of the epoch. */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	153 activeSegment.begin = begin;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	154 activeSegment.end = begin;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	155 activeSegment.score = 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	156
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	157 /* Slide the activeSegment through the whole epoch.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	158 * Save the best segment in bestSegment.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	159 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	160 while (activeSegment.end < end) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	161 /* Get hash value of current dmer */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	162 const size_t idx = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.end, f, d);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	163
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	164 /* Add frequency of this index to score if this is the first occurrence of index in active segment */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	165 if (segmentFreqs[idx] == 0) {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	166 activeSegment.score += freqs[idx];
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	167 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	168 /* Increment end of segment and segmentFreqs*/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	169 activeSegment.end += 1;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	170 segmentFreqs[idx] += 1;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	171 /* If the window is now too large, drop the first position */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	172 if (activeSegment.end - activeSegment.begin == dmersInK + 1) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	173 /* Get hash value of the dmer to be eliminated from active segment */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	174 const size_t delIndex = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.begin, f, d);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	175 segmentFreqs[delIndex] -= 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	176 /* Subtract frequency of this index from score if this is the last occurrence of this index in active segment */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	177 if (segmentFreqs[delIndex] == 0) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	178 activeSegment.score -= freqs[delIndex];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	179 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	180 /* Increment start of segment */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	181 activeSegment.begin += 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	182 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	183
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	184 /* If this segment is the best so far save it */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	185 if (activeSegment.score > bestSegment.score) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	186 bestSegment = activeSegment;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	187 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	188 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	189
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	190 /* Zero out rest of segmentFreqs array */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	191 while (activeSegment.begin < end) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	192 const size_t delIndex = FASTCOVER_hashPtrToIndex(ctx->samples + activeSegment.begin, f, d);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	193 segmentFreqs[delIndex] -= 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	194 activeSegment.begin += 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	195 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	196
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	197 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	198 /* Zero the frequency of hash value of each dmer covered by the chosen segment. */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	199 U32 pos;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	200 for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	201 const size_t i = FASTCOVER_hashPtrToIndex(ctx->samples + pos, f, d);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	202 freqs[i] = 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	203 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	204 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	205
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	206 return bestSegment;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	207 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	208
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	209
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	210 static int FASTCOVER_checkParameters(ZDICT_cover_params_t parameters,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	211 size_t maxDictSize, unsigned f,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	212 unsigned accel) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	213 /* k, d, and f are required parameters */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	214 if (parameters.d == 0 \|\| parameters.k == 0) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	215 return 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	216 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	217 /* d has to be 6 or 8 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	218 if (parameters.d != 6 && parameters.d != 8) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	219 return 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	220 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	221 /* k <= maxDictSize */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	222 if (parameters.k > maxDictSize) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	223 return 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	224 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	225 /* d <= k */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	226 if (parameters.d > parameters.k) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	227 return 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	228 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	229 /* 0 < f <= FASTCOVER_MAX_F*/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	230 if (f > FASTCOVER_MAX_F \|\| f == 0) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	231 return 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	232 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	233 /* 0 < splitPoint <= 1 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	234 if (parameters.splitPoint <= 0 \|\| parameters.splitPoint > 1) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	235 return 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 /* 0 < accel <= 10 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238 if (accel > 10 \|\| accel == 0) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	239 return 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241 return 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	242 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	245 /**
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246 * Clean up a context initialized with `FASTCOVER_ctx_init()`.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	248 static void
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249 FASTCOVER_ctx_destroy(FASTCOVER_ctx_t* ctx)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251 if (!ctx) return;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 free(ctx->freqs);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254 ctx->freqs = NULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256 free(ctx->offsets);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 ctx->offsets = NULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261 /**
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262 * Calculate for frequency of hash value of each dmer in ctx->samples
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	264 static void
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 FASTCOVER_computeFrequency(U32* freqs, const FASTCOVER_ctx_t* ctx)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267 const unsigned f = ctx->f;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	268 const unsigned d = ctx->d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 const unsigned skip = ctx->accelParams.skip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 const unsigned readLength = MAX(d, 8);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 size_t i;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272 assert(ctx->nbTrainSamples >= 5);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273 assert(ctx->nbTrainSamples <= ctx->nbSamples);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	274 for (i = 0; i < ctx->nbTrainSamples; i++) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	275 size_t start = ctx->offsets[i]; /* start of current dmer */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	276 size_t const currSampleEnd = ctx->offsets[i+1];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	277 while (start + readLength <= currSampleEnd) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278 const size_t dmerIndex = FASTCOVER_hashPtrToIndex(ctx->samples + start, f, d);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	279 freqs[dmerIndex]++;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 start = start + skip + 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	281 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	282 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	285
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 /**
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	287 * Prepare a context for dictionary building.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	288 * The context is only dependent on the parameter `d` and can used multiple
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 * times.
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	290 * Returns 0 on success or error code on error.
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	291 * The context must be destroyed with `FASTCOVER_ctx_destroy()`.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	292 */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	293 static size_t
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	294 FASTCOVER_ctx_init(FASTCOVER_ctx_t* ctx,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	295 const void* samplesBuffer,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296 const size_t* samplesSizes, unsigned nbSamples,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 unsigned d, double splitPoint, unsigned f,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298 FASTCOVER_accel_t accelParams)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 const BYTE* const samples = (const BYTE*)samplesBuffer;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	301 const size_t totalSamplesSize = COVER_sum(samplesSizes, nbSamples);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302 /* Split samples into testing and training sets */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	303 const unsigned nbTrainSamples = splitPoint < 1.0 ? (unsigned)((double)nbSamples * splitPoint) : nbSamples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	304 const unsigned nbTestSamples = splitPoint < 1.0 ? nbSamples - nbTrainSamples : nbSamples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	305 const size_t trainingSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes, nbTrainSamples) : totalSamplesSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	306 const size_t testSamplesSize = splitPoint < 1.0 ? COVER_sum(samplesSizes + nbTrainSamples, nbTestSamples) : totalSamplesSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	307
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	308 /* Checks */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309 if (totalSamplesSize < MAX(d, sizeof(U64)) \|\|
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 totalSamplesSize >= (size_t)FASTCOVER_MAX_SAMPLES_SIZE) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	311 DISPLAYLEVEL(1, "Total samples size is too large (%u MB), maximum size is %u MB\n",
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	312 (unsigned)(totalSamplesSize >> 20), (FASTCOVER_MAX_SAMPLES_SIZE >> 20));
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	313 return ERROR(srcSize_wrong);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	316 /* Check if there are at least 5 training samples */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	317 if (nbTrainSamples < 5) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	318 DISPLAYLEVEL(1, "Total number of training samples is %u and is invalid\n", nbTrainSamples);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	319 return ERROR(srcSize_wrong);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	320 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	321
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322 /* Check if there's testing sample */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323 if (nbTestSamples < 1) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324 DISPLAYLEVEL(1, "Total number of testing samples is %u and is invalid.\n", nbTestSamples);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	325 return ERROR(srcSize_wrong);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	327
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	328 /* Zero the context */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	329 memset(ctx, 0, sizeof(*ctx));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	330 DISPLAYLEVEL(2, "Training on %u samples of total size %u\n", nbTrainSamples,
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	331 (unsigned)trainingSamplesSize);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	332 DISPLAYLEVEL(2, "Testing on %u samples of total size %u\n", nbTestSamples,
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	333 (unsigned)testSamplesSize);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	334
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	335 ctx->samples = samples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	336 ctx->samplesSizes = samplesSizes;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	337 ctx->nbSamples = nbSamples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	338 ctx->nbTrainSamples = nbTrainSamples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	339 ctx->nbTestSamples = nbTestSamples;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	340 ctx->nbDmers = trainingSamplesSize - MAX(d, sizeof(U64)) + 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	341 ctx->d = d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	342 ctx->f = f;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	343 ctx->accelParams = accelParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	344
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	345 /* The offsets of each file */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	346 ctx->offsets = (size_t*)calloc((nbSamples + 1), sizeof(size_t));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	347 if (ctx->offsets == NULL) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348 DISPLAYLEVEL(1, "Failed to allocate scratch buffers \n");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	349 FASTCOVER_ctx_destroy(ctx);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	350 return ERROR(memory_allocation);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	351 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	352
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	353 /* Fill offsets from the samplesSizes */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	354 { U32 i;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	355 ctx->offsets[0] = 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	356 assert(nbSamples >= 5);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	357 for (i = 1; i <= nbSamples; ++i) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	358 ctx->offsets[i] = ctx->offsets[i - 1] + samplesSizes[i - 1];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	359 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	360 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	361
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	362 /* Initialize frequency array of size 2^f */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	363 ctx->freqs = (U32*)calloc(((U64)1 << f), sizeof(U32));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	364 if (ctx->freqs == NULL) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	365 DISPLAYLEVEL(1, "Failed to allocate frequency table \n");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	366 FASTCOVER_ctx_destroy(ctx);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	367 return ERROR(memory_allocation);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	368 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	369
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	370 DISPLAYLEVEL(2, "Computing frequencies\n");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 FASTCOVER_computeFrequency(ctx->freqs, ctx);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	372
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	373 return 0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	374 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	375
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	376
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	377 /**
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	378 * Given the prepared context build the dictionary.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	379 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	380 static size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	381 FASTCOVER_buildDictionary(const FASTCOVER_ctx_t* ctx,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	382 U32* freqs,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	383 void* dictBuffer, size_t dictBufferCapacity,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	384 ZDICT_cover_params_t parameters,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	385 U16* segmentFreqs)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	386 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	387 BYTE const dict = (BYTE )dictBuffer;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	388 size_t tail = dictBufferCapacity;
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	389 /* Divide the data into epochs. We will select one segment from each epoch. */
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	390 const COVER_epoch_info_t epochs = COVER_computeEpochs(
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	391 (U32)dictBufferCapacity, (U32)ctx->nbDmers, parameters.k, 1);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	392 const size_t maxZeroScoreRun = 10;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	393 size_t zeroScoreRun = 0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	394 size_t epoch;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	395 DISPLAYLEVEL(2, "Breaking content into %u epochs of size %u\n",
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	396 (U32)epochs.num, (U32)epochs.size);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	397 /* Loop through the epochs until there are no more segments or the dictionary
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	398 * is full.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	399 */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	400 for (epoch = 0; tail > 0; epoch = (epoch + 1) % epochs.num) {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	401 const U32 epochBegin = (U32)(epoch * epochs.size);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	402 const U32 epochEnd = epochBegin + epochs.size;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	403 size_t segmentSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	404 /* Select a segment */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	405 COVER_segment_t segment = FASTCOVER_selectSegment(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	406 ctx, freqs, epochBegin, epochEnd, parameters, segmentFreqs);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	407
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	408 /* If the segment covers no dmers, then we are out of content.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	409 * There may be new content in other epochs, for continue for some time.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	410 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	411 if (segment.score == 0) {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	412 if (++zeroScoreRun >= maxZeroScoreRun) {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	413 break;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	414 }
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	415 continue;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	416 }
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	417 zeroScoreRun = 0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	418
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	419 /* Trim the segment if necessary and if it is too small then we are done */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	420 segmentSize = MIN(segment.end - segment.begin + parameters.d - 1, tail);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	421 if (segmentSize < parameters.d) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	422 break;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	423 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	424
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	425 /* We fill the dictionary from the back to allow the best segments to be
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	426 * referenced with the smallest offsets.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	427 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	428 tail -= segmentSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	429 memcpy(dict + tail, ctx->samples + segment.begin, segmentSize);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	430 DISPLAYUPDATE(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	431 2, "\r%u%% ",
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	432 (unsigned)(((dictBufferCapacity - tail) * 100) / dictBufferCapacity));
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	433 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	434 DISPLAYLEVEL(2, "\r%79s\r", "");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	435 return tail;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	436 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	437
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	438 /**
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	439 * Parameters for FASTCOVER_tryParameters().
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	440 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	441 typedef struct FASTCOVER_tryParameters_data_s {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	442 const FASTCOVER_ctx_t* ctx;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	443 COVER_best_t* best;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	444 size_t dictBufferCapacity;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	445 ZDICT_cover_params_t parameters;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	446 } FASTCOVER_tryParameters_data_t;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	447
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	448
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	449 /**
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	450 * Tries a set of parameters and updates the COVER_best_t with the results.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	451 * This function is thread safe if zstd is compiled with multithreaded support.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	452 * It takes its parameters as an OWNING opaque pointer to support threading.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	453 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	454 static void FASTCOVER_tryParameters(void *opaque)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	456 /* Save parameters as local variables */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	457 FASTCOVER_tryParameters_data_t const data = (FASTCOVER_tryParameters_data_t )opaque;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	458 const FASTCOVER_ctx_t *const ctx = data->ctx;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	459 const ZDICT_cover_params_t parameters = data->parameters;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 size_t dictBufferCapacity = data->dictBufferCapacity;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	461 size_t totalCompressedSize = ERROR(GENERIC);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	462 /* Initialize array to keep track of frequency of dmer within activeSegment */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	463 U16* segmentFreqs = (U16 *)calloc(((U64)1 << ctx->f), sizeof(U16));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	464 /* Allocate space for hash table, dict, and freqs */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	465 BYTE const dict = (BYTE const)malloc(dictBufferCapacity);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	466 COVER_dictSelection_t selection = COVER_dictSelectionError(ERROR(GENERIC));
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	467 U32 freqs = (U32) malloc(((U64)1 << ctx->f) * sizeof(U32));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	468 if (!segmentFreqs \|\| !dict \|\| !freqs) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	469 DISPLAYLEVEL(1, "Failed to allocate buffers: out of memory\n");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	470 goto _cleanup;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	471 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	472 /* Copy the frequencies because we need to modify them */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	473 memcpy(freqs, ctx->freqs, ((U64)1 << ctx->f) * sizeof(U32));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	474 /* Build the dictionary */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	475 { const size_t tail = FASTCOVER_buildDictionary(ctx, freqs, dict, dictBufferCapacity,
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	476 parameters, segmentFreqs);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	477
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478 const unsigned nbFinalizeSamples = (unsigned)(ctx->nbTrainSamples * ctx->accelParams.finalize / 100);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	479 selection = COVER_selectDict(dict + tail, dictBufferCapacity - tail,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	480 ctx->samples, ctx->samplesSizes, nbFinalizeSamples, ctx->nbTrainSamples, ctx->nbSamples, parameters, ctx->offsets,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	481 totalCompressedSize);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	482
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	483 if (COVER_dictSelectionIsError(selection)) {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	484 DISPLAYLEVEL(1, "Failed to select dictionary\n");
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	485 goto _cleanup;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	487 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488 _cleanup:
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	489 free(dict);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	490 COVER_best_finish(data->best, parameters, selection);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	491 free(data);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	492 free(segmentFreqs);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	493 COVER_dictSelectionFree(selection);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	494 free(freqs);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	495 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	496
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	497
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	498 static void
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	499 FASTCOVER_convertToCoverParams(ZDICT_fastCover_params_t fastCoverParams,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	500 ZDICT_cover_params_t* coverParams)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	501 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502 coverParams->k = fastCoverParams.k;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 coverParams->d = fastCoverParams.d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	504 coverParams->steps = fastCoverParams.steps;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505 coverParams->nbThreads = fastCoverParams.nbThreads;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	506 coverParams->splitPoint = fastCoverParams.splitPoint;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	507 coverParams->zParams = fastCoverParams.zParams;
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	508 coverParams->shrinkDict = fastCoverParams.shrinkDict;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	509 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	510
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	511
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	512 static void
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	513 FASTCOVER_convertToFastCoverParams(ZDICT_cover_params_t coverParams,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	514 ZDICT_fastCover_params_t* fastCoverParams,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	515 unsigned f, unsigned accel)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	516 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	517 fastCoverParams->k = coverParams.k;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	518 fastCoverParams->d = coverParams.d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	519 fastCoverParams->steps = coverParams.steps;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	520 fastCoverParams->nbThreads = coverParams.nbThreads;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	521 fastCoverParams->splitPoint = coverParams.splitPoint;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	522 fastCoverParams->f = f;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	523 fastCoverParams->accel = accel;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	524 fastCoverParams->zParams = coverParams.zParams;
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	525 fastCoverParams->shrinkDict = coverParams.shrinkDict;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	526 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	527
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	528
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	529 ZDICTLIB_API size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	530 ZDICT_trainFromBuffer_fastCover(void* dictBuffer, size_t dictBufferCapacity,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	531 const void* samplesBuffer,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	532 const size_t* samplesSizes, unsigned nbSamples,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	533 ZDICT_fastCover_params_t parameters)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	534 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	535 BYTE* const dict = (BYTE*)dictBuffer;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	536 FASTCOVER_ctx_t ctx;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	537 ZDICT_cover_params_t coverParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	538 FASTCOVER_accel_t accelParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	539 /* Initialize global data */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	540 g_displayLevel = parameters.zParams.notificationLevel;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	541 /* Assign splitPoint and f if not provided */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	542 parameters.splitPoint = 1.0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	543 parameters.f = parameters.f == 0 ? DEFAULT_F : parameters.f;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	544 parameters.accel = parameters.accel == 0 ? DEFAULT_ACCEL : parameters.accel;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	545 /* Convert to cover parameter */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	546 memset(&coverParams, 0 , sizeof(coverParams));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	547 FASTCOVER_convertToCoverParams(parameters, &coverParams);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	548 /* Checks */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	549 if (!FASTCOVER_checkParameters(coverParams, dictBufferCapacity, parameters.f,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	550 parameters.accel)) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	551 DISPLAYLEVEL(1, "FASTCOVER parameters incorrect\n");
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	552 return ERROR(parameter_outOfBound);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	553 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	554 if (nbSamples == 0) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	555 DISPLAYLEVEL(1, "FASTCOVER must have at least one input file\n");
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	556 return ERROR(srcSize_wrong);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	557 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	558 if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	559 DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n",
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	560 ZDICT_DICTSIZE_MIN);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	561 return ERROR(dstSize_tooSmall);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	562 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	563 /* Assign corresponding FASTCOVER_accel_t to accelParams*/
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	564 accelParams = FASTCOVER_defaultAccelParameters[parameters.accel];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	565 /* Initialize context */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	566 {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	567 size_t const initVal = FASTCOVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	568 coverParams.d, parameters.splitPoint, parameters.f,
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	569 accelParams);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	570 if (ZSTD_isError(initVal)) {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	571 DISPLAYLEVEL(1, "Failed to initialize context\n");
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	572 return initVal;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	573 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	574 }
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	575 COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.nbDmers, g_displayLevel);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	576 /* Build the dictionary */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	577 DISPLAYLEVEL(2, "Building dictionary\n");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	578 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	579 /* Initialize array to keep track of frequency of dmer within activeSegment */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	580 U16* segmentFreqs = (U16 *)calloc(((U64)1 << parameters.f), sizeof(U16));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	581 const size_t tail = FASTCOVER_buildDictionary(&ctx, ctx.freqs, dictBuffer,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	582 dictBufferCapacity, coverParams, segmentFreqs);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	583 const unsigned nbFinalizeSamples = (unsigned)(ctx.nbTrainSamples * ctx.accelParams.finalize / 100);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	584 const size_t dictionarySize = ZDICT_finalizeDictionary(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	585 dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	586 samplesBuffer, samplesSizes, nbFinalizeSamples, coverParams.zParams);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	587 if (!ZSTD_isError(dictionarySize)) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	588 DISPLAYLEVEL(2, "Constructed dictionary of size %u\n",
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	589 (unsigned)dictionarySize);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	590 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	591 FASTCOVER_ctx_destroy(&ctx);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	592 free(segmentFreqs);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	593 return dictionarySize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	594 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	595 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	596
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	597
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	598 ZDICTLIB_API size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	599 ZDICT_optimizeTrainFromBuffer_fastCover(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	600 void* dictBuffer, size_t dictBufferCapacity,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	601 const void* samplesBuffer,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	602 const size_t* samplesSizes, unsigned nbSamples,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	603 ZDICT_fastCover_params_t* parameters)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	604 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	605 ZDICT_cover_params_t coverParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	606 FASTCOVER_accel_t accelParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	607 /* constants */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	608 const unsigned nbThreads = parameters->nbThreads;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	609 const double splitPoint =
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	610 parameters->splitPoint <= 0.0 ? DEFAULT_SPLITPOINT : parameters->splitPoint;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	611 const unsigned kMinD = parameters->d == 0 ? 6 : parameters->d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	612 const unsigned kMaxD = parameters->d == 0 ? 8 : parameters->d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	613 const unsigned kMinK = parameters->k == 0 ? 50 : parameters->k;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	614 const unsigned kMaxK = parameters->k == 0 ? 2000 : parameters->k;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	615 const unsigned kSteps = parameters->steps == 0 ? 40 : parameters->steps;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	616 const unsigned kStepSize = MAX((kMaxK - kMinK) / kSteps, 1);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	617 const unsigned kIterations =
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	618 (1 + (kMaxD - kMinD) / 2) * (1 + (kMaxK - kMinK) / kStepSize);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	619 const unsigned f = parameters->f == 0 ? DEFAULT_F : parameters->f;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	620 const unsigned accel = parameters->accel == 0 ? DEFAULT_ACCEL : parameters->accel;
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	621 const unsigned shrinkDict = 0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	622 /* Local variables */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	623 const int displayLevel = parameters->zParams.notificationLevel;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	624 unsigned iteration = 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	625 unsigned d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	626 unsigned k;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	627 COVER_best_t best;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	628 POOL_ctx *pool = NULL;
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	629 int warned = 0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	630 /* Checks */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	631 if (splitPoint <= 0 \|\| splitPoint > 1) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	632 LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect splitPoint\n");
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	633 return ERROR(parameter_outOfBound);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	634 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	635 if (accel == 0 \|\| accel > FASTCOVER_MAX_ACCEL) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	636 LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect accel\n");
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	637 return ERROR(parameter_outOfBound);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	638 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	639 if (kMinK < kMaxD \|\| kMaxK < kMinK) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	640 LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect k\n");
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	641 return ERROR(parameter_outOfBound);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	642 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	643 if (nbSamples == 0) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	644 LOCALDISPLAYLEVEL(displayLevel, 1, "FASTCOVER must have at least one input file\n");
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	645 return ERROR(srcSize_wrong);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	646 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	647 if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	648 LOCALDISPLAYLEVEL(displayLevel, 1, "dictBufferCapacity must be at least %u\n",
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	649 ZDICT_DICTSIZE_MIN);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	650 return ERROR(dstSize_tooSmall);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	651 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	652 if (nbThreads > 1) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	653 pool = POOL_create(nbThreads, 1);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	654 if (!pool) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	655 return ERROR(memory_allocation);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	656 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	657 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	658 /* Initialization */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	659 COVER_best_init(&best);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	660 memset(&coverParams, 0 , sizeof(coverParams));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	661 FASTCOVER_convertToCoverParams(*parameters, &coverParams);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	662 accelParams = FASTCOVER_defaultAccelParameters[accel];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	663 /* Turn down global display level to clean up display at level 2 and below */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	664 g_displayLevel = displayLevel == 0 ? 0 : displayLevel - 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	665 /* Loop through d first because each new value needs a new context */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	666 LOCALDISPLAYLEVEL(displayLevel, 2, "Trying %u different sets of parameters\n",
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	667 kIterations);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	668 for (d = kMinD; d <= kMaxD; d += 2) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	669 /* Initialize the context for this value of d */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	670 FASTCOVER_ctx_t ctx;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	671 LOCALDISPLAYLEVEL(displayLevel, 3, "d=%u\n", d);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	672 {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	673 size_t const initVal = FASTCOVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples, d, splitPoint, f, accelParams);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	674 if (ZSTD_isError(initVal)) {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	675 LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to initialize context\n");
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	676 COVER_best_destroy(&best);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	677 POOL_free(pool);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	678 return initVal;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	679 }
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	680 }
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	681 if (!warned) {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	682 COVER_warnOnSmallCorpus(dictBufferCapacity, ctx.nbDmers, displayLevel);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	683 warned = 1;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	684 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	685 /* Loop through k reusing the same context */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	686 for (k = kMinK; k <= kMaxK; k += kStepSize) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	687 /* Prepare the arguments */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	688 FASTCOVER_tryParameters_data_t data = (FASTCOVER_tryParameters_data_t )malloc(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	689 sizeof(FASTCOVER_tryParameters_data_t));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	690 LOCALDISPLAYLEVEL(displayLevel, 3, "k=%u\n", k);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	691 if (!data) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	692 LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to allocate parameters\n");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	693 COVER_best_destroy(&best);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	694 FASTCOVER_ctx_destroy(&ctx);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	695 POOL_free(pool);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	696 return ERROR(memory_allocation);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	697 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	698 data->ctx = &ctx;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	699 data->best = &best;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	700 data->dictBufferCapacity = dictBufferCapacity;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	701 data->parameters = coverParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	702 data->parameters.k = k;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	703 data->parameters.d = d;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	704 data->parameters.splitPoint = splitPoint;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	705 data->parameters.steps = kSteps;
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	706 data->parameters.shrinkDict = shrinkDict;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	707 data->parameters.zParams.notificationLevel = g_displayLevel;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	708 /* Check the parameters */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	709 if (!FASTCOVER_checkParameters(data->parameters, dictBufferCapacity,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	710 data->ctx->f, accel)) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	711 DISPLAYLEVEL(1, "FASTCOVER parameters incorrect\n");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	712 free(data);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	713 continue;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	714 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	715 /* Call the function and pass ownership of data to it */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	716 COVER_best_start(&best);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	717 if (pool) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	718 POOL_add(pool, &FASTCOVER_tryParameters, data);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	719 } else {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	720 FASTCOVER_tryParameters(data);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	721 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	722 /* Print status */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	723 LOCALDISPLAYUPDATE(displayLevel, 2, "\r%u%% ",
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	724 (unsigned)((iteration * 100) / kIterations));
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	725 ++iteration;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	726 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	727 COVER_best_wait(&best);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	728 FASTCOVER_ctx_destroy(&ctx);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	729 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	730 LOCALDISPLAYLEVEL(displayLevel, 2, "\r%79s\r", "");
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	731 /* Fill the output buffer and parameters with output of the best parameters */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	732 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	733 const size_t dictSize = best.dictSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	734 if (ZSTD_isError(best.compressedSize)) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	735 const size_t compressedSize = best.compressedSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	736 COVER_best_destroy(&best);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	737 POOL_free(pool);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	738 return compressedSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	739 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	740 FASTCOVER_convertToFastCoverParams(best.parameters, parameters, f, accel);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	741 memcpy(dictBuffer, best.dict, dictSize);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	742 COVER_best_destroy(&best);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	743 POOL_free(pool);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	744 return dictSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	745 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	746
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	747 }

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/dictBuilder/fastcover.c @ 53042:cdd7bf612c7b stable tip