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

annotate contrib/python-zstandard/zstd/dictBuilder/cover.c @ 35320:d901a88891fe

rebase: rerun a rebase on-disk if IMM merge conflicts arise Differential Revision: https://phab.mercurial-scm.org/D1249

author	Phil Cohen <phillco@fb.com>
date	Fri, 08 Dec 2017 12:14:38 -0800
parents	c32454d69b85
children	b1fb341d8a61

rev	line source
30895 c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	3 * All rights reserved.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	4 *
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	5 * This source code is licensed under the BSD-style license found in the
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	6 * LICENSE file in the root directory of this source tree. An additional grant
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	7 * of patent rights can be found in the PATENTS file in the same directory.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	8 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	9
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	10 /-************************************
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	11 * Dependencies
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	12 ***************************************/
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	13 #include <stdio.h> /* fprintf */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	14 #include <stdlib.h> /* malloc, free, qsort */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	15 #include <string.h> /* memset */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	16 #include <time.h> /* clock */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	17
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	18 #include "mem.h" /* read */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	19 #include "pool.h"
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	20 #include "threading.h"
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	21 #include "zstd_internal.h" /* includes zstd.h */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	22 #ifndef ZDICT_STATIC_LINKING_ONLY
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	23 #define ZDICT_STATIC_LINKING_ONLY
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	24 #endif
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	25 #include "zdict.h"
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	26
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	27 /-************************************
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	28 * Constants
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	29 ***************************************/
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	30 #define COVER_MAX_SAMPLES_SIZE (sizeof(size_t) == 8 ? ((U32)-1) : ((U32)1 GB))
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	31
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	32 /-************************************
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	33 * Console display
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	34 ***************************************/
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	35 static int g_displayLevel = 2;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	36 #define DISPLAY(...) \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	37 { \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	38 fprintf(stderr, __VA_ARGS__); \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	39 fflush(stderr); \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	40 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	41 #define LOCALDISPLAYLEVEL(displayLevel, l, ...) \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	42 if (displayLevel >= l) { \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	43 DISPLAY(__VA_ARGS__); \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	44 } /* 0 : no display; 1: errors; 2: default; 3: details; 4: debug */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	45 #define DISPLAYLEVEL(l, ...) LOCALDISPLAYLEVEL(g_displayLevel, l, __VA_ARGS__)
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	46
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	47 #define LOCALDISPLAYUPDATE(displayLevel, l, ...) \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	48 if (displayLevel >= l) { \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49 if ((clock() - g_time > refreshRate) \|\| (displayLevel >= 4)) { \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	50 g_time = clock(); \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 DISPLAY(__VA_ARGS__); \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 if (displayLevel >= 4) \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	53 fflush(stdout); \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	54 } \
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	55 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	56 #define DISPLAYUPDATE(l, ...) LOCALDISPLAYUPDATE(g_displayLevel, l, __VA_ARGS__)
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	57 static const clock_t refreshRate = CLOCKS_PER_SEC * 15 / 100;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	58 static clock_t g_time = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	59
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	60 /-************************************
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	61 * Hash table
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	62 ***************************************
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	63 * A small specialized hash map for storing activeDmers.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	64 * The map does not resize, so if it becomes full it will loop forever.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	65 * Thus, the map must be large enough to store every value.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	66 * The map implements linear probing and keeps its load less than 0.5.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	67 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	68
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	69 #define MAP_EMPTY_VALUE ((U32)-1)
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	70 typedef struct COVER_map_pair_t_s {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	71 U32 key;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	72 U32 value;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	73 } COVER_map_pair_t;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	74
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	75 typedef struct COVER_map_s {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	76 COVER_map_pair_t *data;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	77 U32 sizeLog;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	78 U32 size;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	79 U32 sizeMask;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	80 } COVER_map_t;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	81
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	82 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	83 * Clear the map.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	84 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	85 static void COVER_map_clear(COVER_map_t *map) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	86 memset(map->data, MAP_EMPTY_VALUE, map->size * sizeof(COVER_map_pair_t));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	87 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	88
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	89 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	90 * Initializes a map of the given size.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	91 * Returns 1 on success and 0 on failure.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	92 * The map must be destroyed with COVER_map_destroy().
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	93 * The map is only guaranteed to be large enough to hold size elements.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	94 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	95 static int COVER_map_init(COVER_map_t *map, U32 size) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	96 map->sizeLog = ZSTD_highbit32(size) + 2;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	97 map->size = (U32)1 << map->sizeLog;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	98 map->sizeMask = map->size - 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	99 map->data = (COVER_map_pair_t )malloc(map->size sizeof(COVER_map_pair_t));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	100 if (!map->data) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	101 map->sizeLog = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	102 map->size = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	103 return 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	104 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	105 COVER_map_clear(map);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	106 return 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	107 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	108
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	109 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	110 * Internal hash function
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	111 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	112 static const U32 prime4bytes = 2654435761U;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	113 static U32 COVER_map_hash(COVER_map_t *map, U32 key) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	114 return (key * prime4bytes) >> (32 - map->sizeLog);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	115 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	116
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	117 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	118 * Helper function that returns the index that a key should be placed into.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	119 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	120 static U32 COVER_map_index(COVER_map_t *map, U32 key) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	121 const U32 hash = COVER_map_hash(map, key);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	122 U32 i;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	123 for (i = hash;; i = (i + 1) & map->sizeMask) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	124 COVER_map_pair_t *pos = &map->data[i];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	125 if (pos->value == MAP_EMPTY_VALUE) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	126 return i;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128 if (pos->key == key) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 return i;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	131 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	133
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	134 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	135 * Returns the pointer to the value for key.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 * If key is not in the map, it is inserted and the value is set to 0.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	137 * The map must not be full.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	138 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	139 static U32 COVER_map_at(COVER_map_t map, U32 key) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	140 COVER_map_pair_t *pos = &map->data[COVER_map_index(map, key)];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	141 if (pos->value == MAP_EMPTY_VALUE) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142 pos->key = key;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	143 pos->value = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	144 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	145 return &pos->value;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	147
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	148 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	149 * Deletes key from the map if present.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	150 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	151 static void COVER_map_remove(COVER_map_t *map, U32 key) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	152 U32 i = COVER_map_index(map, key);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	153 COVER_map_pair_t *del = &map->data[i];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	154 U32 shift = 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	155 if (del->value == MAP_EMPTY_VALUE) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	156 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	157 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	158 for (i = (i + 1) & map->sizeMask;; i = (i + 1) & map->sizeMask) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	159 COVER_map_pair_t *const pos = &map->data[i];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	160 /* If the position is empty we are done */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	161 if (pos->value == MAP_EMPTY_VALUE) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	162 del->value = MAP_EMPTY_VALUE;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	163 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	164 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	165 /* If pos can be moved to del do so */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	166 if (((i - COVER_map_hash(map, pos->key)) & map->sizeMask) >= shift) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	167 del->key = pos->key;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	168 del->value = pos->value;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	169 del = pos;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	170 shift = 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	171 } else {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	172 ++shift;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	173 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	174 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	175 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	176
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	177 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	178 * Destroyes a map that is inited with COVER_map_init().
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	179 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	180 static void COVER_map_destroy(COVER_map_t *map) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	181 if (map->data) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	182 free(map->data);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	183 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	184 map->data = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	185 map->size = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	186 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	187
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	188 /-************************************
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	189 * Context
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	190 ***************************************/
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	191
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	192 typedef struct {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	193 const BYTE *samples;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	194 size_t *offsets;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	195 const size_t *samplesSizes;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	196 size_t nbSamples;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	197 U32 *suffix;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	198 size_t suffixSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	199 U32 *freqs;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	200 U32 *dmerAt;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	201 unsigned d;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	202 } COVER_ctx_t;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	203
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	204 /* We need a global context for qsort... */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	205 static COVER_ctx_t *g_ctx = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	206
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	207 /-************************************
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	208 * Helper functions
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	209 ***************************************/
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	210
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	211 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	212 * Returns the sum of the sample sizes.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	213 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	214 static size_t COVER_sum(const size_t *samplesSizes, unsigned nbSamples) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	215 size_t sum = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	216 size_t i;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	217 for (i = 0; i < nbSamples; ++i) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	218 sum += samplesSizes[i];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	219 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	220 return sum;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	221 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	222
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	223 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	224 * Returns -1 if the dmer at lp is less than the dmer at rp.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	225 * Return 0 if the dmers at lp and rp are equal.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	226 * Returns 1 if the dmer at lp is greater than the dmer at rp.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	227 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	228 static int COVER_cmp(COVER_ctx_t ctx, const void lp, const void *rp) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	229 const U32 lhs = (const U32 )lp;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	230 const U32 rhs = (const U32 )rp;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	231 return memcmp(ctx->samples + lhs, ctx->samples + rhs, ctx->d);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	232 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	233
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	234 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	235 * Same as COVER_cmp() except ties are broken by pointer value
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 * NOTE: g_ctx must be set to call this function. A global is required because
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 * qsort doesn't take an opaque pointer.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	239 static int COVER_strict_cmp(const void lp, const void rp) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 int result = COVER_cmp(g_ctx, lp, rp);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241 if (result == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	242 result = lp < rp ? -1 : 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244 return result;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	245 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	248 * Returns the first pointer in [first, last) whose element does not compare
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249 * less than value. If no such element exists it returns last.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251 static const size_t COVER_lower_bound(const size_t first, const size_t *last,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252 size_t value) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 size_t count = last - first;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254 while (count != 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255 size_t step = count / 2;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256 const size_t *ptr = first;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 ptr += step;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258 if (*ptr < value) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259 first = ++ptr;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 count -= step + 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261 } else {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262 count = step;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	264 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 return first;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	268 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 * Generic groupBy function.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 * Groups an array sorted by cmp into groups with equivalent values.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 * Calls grp for each group.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273 static void
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	274 COVER_groupBy(const void data, size_t count, size_t size, COVER_ctx_t ctx,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	275 int (cmp)(COVER_ctx_t , const void , const void ),
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	276 void (grp)(COVER_ctx_t , const void , const void )) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	277 const BYTE ptr = (const BYTE )data;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278 size_t num = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	279 while (num < count) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 const BYTE *grpEnd = ptr + size;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	281 ++num;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	282 while (num < count && cmp(ctx, ptr, grpEnd) == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 grpEnd += size;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284 ++num;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	285 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 grp(ctx, ptr, grpEnd);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	287 ptr = grpEnd;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	288 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	290
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	291 /-************************************
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	292 * Cover functions
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	293 ***************************************/
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	294
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	295 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296 * Called on each group of positions with the same dmer.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 * Counts the frequency of each dmer and saves it in the suffix array.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298 * Fills `ctx->dmerAt`.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 static void COVER_group(COVER_ctx_t ctx, const void group,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	301 const void *groupEnd) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302 /* The group consists of all the positions with the same first d bytes. */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	303 const U32 grpPtr = (const U32 )group;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	304 const U32 grpEnd = (const U32 )groupEnd;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	305 /* The dmerId is how we will reference this dmer.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	306 * This allows us to map the whole dmer space to a much smaller space, the
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	307 * size of the suffix array.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	308 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309 const U32 dmerId = (U32)(grpPtr - ctx->suffix);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 /* Count the number of samples this dmer shows up in */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	311 U32 freq = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	312 /* Details */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	313 const size_t *curOffsetPtr = ctx->offsets;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 const size_t *offsetsEnd = ctx->offsets + ctx->nbSamples;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315 /* Once *grpPtr >= curSampleEnd this occurrence of the dmer is in a
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	316 * different sample than the last.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	317 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	318 size_t curSampleEnd = ctx->offsets[0];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	319 for (; grpPtr != grpEnd; ++grpPtr) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	320 /* Save the dmerId for this position so we can get back to it. */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	321 ctx->dmerAt[*grpPtr] = dmerId;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322 /* Dictionaries only help for the first reference to the dmer.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323 * After that zstd can reference the match from the previous reference.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324 * So only count each dmer once for each sample it is in.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	325 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326 if (*grpPtr < curSampleEnd) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	327 continue;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	328 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	329 freq += 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	330 /* Binary search to find the end of the sample *grpPtr is in.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	331 * In the common case that grpPtr + 1 == grpEnd we can skip the binary
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	332 * search because the loop is over.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	333 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	334 if (grpPtr + 1 != grpEnd) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	335 const size_t *sampleEndPtr =
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	336 COVER_lower_bound(curOffsetPtr, offsetsEnd, *grpPtr);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	337 curSampleEnd = *sampleEndPtr;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	338 curOffsetPtr = sampleEndPtr + 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	339 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	340 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	341 /* At this point we are never going to look at this segment of the suffix
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	342 * array again. We take advantage of this fact to save memory.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	343 * We store the frequency of the dmer in the first position of the group,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	344 * which is dmerId.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	345 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	346 ctx->suffix[dmerId] = freq;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	347 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	349 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	350 * A segment is a range in the source as well as the score of the segment.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	351 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	352 typedef struct {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	353 U32 begin;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	354 U32 end;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	355 double score;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	356 } COVER_segment_t;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	357
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	358 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	359 * Selects the best segment in an epoch.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	360 * Segments of are scored according to the function:
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	361 *
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	362 * Let F(d) be the frequency of dmer d.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	363 * Let S_i be the dmer at position i of segment S which has length k.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	364 *
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	365 * Score(S) = F(S_1) + F(S_2) + ... + F(S_{k-d+1})
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	366 *
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	367 * Once the dmer d is in the dictionay we set F(d) = 0.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	368 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	369 static COVER_segment_t COVER_selectSegment(const COVER_ctx_t ctx, U32 freqs,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	370 COVER_map_t *activeDmers, U32 begin,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 U32 end, COVER_params_t parameters) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	372 /* Constants */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	373 const U32 k = parameters.k;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	374 const U32 d = parameters.d;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	375 const U32 dmersInK = k - d + 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	376 /* Try each segment (activeSegment) and save the best (bestSegment) */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	377 COVER_segment_t bestSegment = {0, 0, 0};
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	378 COVER_segment_t activeSegment;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	379 /* Reset the activeDmers in the segment */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	380 COVER_map_clear(activeDmers);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	381 /* The activeSegment starts at the beginning of the epoch. */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	382 activeSegment.begin = begin;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	383 activeSegment.end = begin;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	384 activeSegment.score = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	385 /* Slide the activeSegment through the whole epoch.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	386 * Save the best segment in bestSegment.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	387 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	388 while (activeSegment.end < end) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	389 /* The dmerId for the dmer at the next position */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	390 U32 newDmer = ctx->dmerAt[activeSegment.end];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	391 /* The entry in activeDmers for this dmerId */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	392 U32 *newDmerOcc = COVER_map_at(activeDmers, newDmer);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	393 /* If the dmer isn't already present in the segment add its score. */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	394 if (*newDmerOcc == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	395 /* The paper suggest using the L-0.5 norm, but experiments show that it
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	396 * doesn't help.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	397 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	398 activeSegment.score += freqs[newDmer];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	399 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	400 /* Add the dmer to the segment */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	401 activeSegment.end += 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	402 *newDmerOcc += 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	403
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	404 /* If the window is now too large, drop the first position */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	405 if (activeSegment.end - activeSegment.begin == dmersInK + 1) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	406 U32 delDmer = ctx->dmerAt[activeSegment.begin];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	407 U32 *delDmerOcc = COVER_map_at(activeDmers, delDmer);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	408 activeSegment.begin += 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	409 *delDmerOcc -= 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	410 /* If this is the last occurence of the dmer, subtract its score */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	411 if (*delDmerOcc == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	412 COVER_map_remove(activeDmers, delDmer);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	413 activeSegment.score -= freqs[delDmer];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	414 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	415 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	416
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	417 /* If this segment is the best so far save it */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	418 if (activeSegment.score > bestSegment.score) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	419 bestSegment = activeSegment;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	420 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	421 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	422 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	423 /* Trim off the zero frequency head and tail from the segment. */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	424 U32 newBegin = bestSegment.end;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	425 U32 newEnd = bestSegment.begin;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	426 U32 pos;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	427 for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	428 U32 freq = freqs[ctx->dmerAt[pos]];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	429 if (freq != 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	430 newBegin = MIN(newBegin, pos);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	431 newEnd = pos + 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	432 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	433 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	434 bestSegment.begin = newBegin;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	435 bestSegment.end = newEnd;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	436 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	437 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	438 /* Zero out the frequency of each dmer covered by the chosen segment. */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	439 U32 pos;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	440 for (pos = bestSegment.begin; pos != bestSegment.end; ++pos) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	441 freqs[ctx->dmerAt[pos]] = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	442 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	443 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	444 return bestSegment;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	445 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	446
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	447 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	448 * Check the validity of the parameters.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	449 * Returns non-zero if the parameters are valid and 0 otherwise.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	450 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	451 static int COVER_checkParameters(COVER_params_t parameters) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	452 /* k and d are required parameters */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	453 if (parameters.d == 0 \|\| parameters.k == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	454 return 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	456 /* d <= k */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	457 if (parameters.d > parameters.k) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	458 return 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	459 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 return 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	461 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	462
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	463 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	464 * Clean up a context initialized with `COVER_ctx_init()`.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	465 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	466 static void COVER_ctx_destroy(COVER_ctx_t *ctx) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	467 if (!ctx) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	468 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	469 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	470 if (ctx->suffix) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	471 free(ctx->suffix);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	472 ctx->suffix = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	473 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	474 if (ctx->freqs) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	475 free(ctx->freqs);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	476 ctx->freqs = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	477 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478 if (ctx->dmerAt) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	479 free(ctx->dmerAt);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	480 ctx->dmerAt = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	481 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	482 if (ctx->offsets) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	483 free(ctx->offsets);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	484 ctx->offsets = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	485 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	487
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	489 * Prepare a context for dictionary building.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	490 * The context is only dependent on the parameter `d` and can used multiple
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	491 * times.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	492 * Returns 1 on success or zero on error.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	493 * The context must be destroyed with `COVER_ctx_destroy()`.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	494 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	495 static int COVER_ctx_init(COVER_ctx_t ctx, const void samplesBuffer,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	496 const size_t *samplesSizes, unsigned nbSamples,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	497 unsigned d) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	498 const BYTE const samples = (const BYTE )samplesBuffer;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	499 const size_t totalSamplesSize = COVER_sum(samplesSizes, nbSamples);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	500 /* Checks */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	501 if (totalSamplesSize < d \|\|
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502 totalSamplesSize >= (size_t)COVER_MAX_SAMPLES_SIZE) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 DISPLAYLEVEL(1, "Total samples size is too large, maximum size is %u MB\n",
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	504 (COVER_MAX_SAMPLES_SIZE >> 20));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505 return 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	506 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	507 /* Zero the context */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	508 memset(ctx, 0, sizeof(*ctx));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	509 DISPLAYLEVEL(2, "Training on %u samples of total size %u\n", nbSamples,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	510 (U32)totalSamplesSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	511 ctx->samples = samples;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	512 ctx->samplesSizes = samplesSizes;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	513 ctx->nbSamples = nbSamples;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	514 /* Partial suffix array */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	515 ctx->suffixSize = totalSamplesSize - d + 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	516 ctx->suffix = (U32 )malloc(ctx->suffixSize sizeof(U32));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	517 /* Maps index to the dmerID */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	518 ctx->dmerAt = (U32 )malloc(ctx->suffixSize sizeof(U32));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	519 /* The offsets of each file */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	520 ctx->offsets = (size_t )malloc((nbSamples + 1) sizeof(size_t));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	521 if (!ctx->suffix \|\| !ctx->dmerAt \|\| !ctx->offsets) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	522 DISPLAYLEVEL(1, "Failed to allocate scratch buffers\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	523 COVER_ctx_destroy(ctx);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	524 return 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	525 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	526 ctx->freqs = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	527 ctx->d = d;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	528
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	529 /* Fill offsets from the samlesSizes */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	530 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	531 U32 i;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	532 ctx->offsets[0] = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	533 for (i = 1; i <= nbSamples; ++i) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	534 ctx->offsets[i] = ctx->offsets[i - 1] + samplesSizes[i - 1];
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	535 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	536 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	537 DISPLAYLEVEL(2, "Constructing partial suffix array\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	538 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	539 /* suffix is a partial suffix array.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	540 * It only sorts suffixes by their first parameters.d bytes.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	541 * The sort is stable, so each dmer group is sorted by position in input.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	542 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	543 U32 i;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	544 for (i = 0; i < ctx->suffixSize; ++i) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	545 ctx->suffix[i] = i;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	546 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	547 /* qsort doesn't take an opaque pointer, so pass as a global */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	548 g_ctx = ctx;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	549 qsort(ctx->suffix, ctx->suffixSize, sizeof(U32), &COVER_strict_cmp);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	550 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	551 DISPLAYLEVEL(2, "Computing frequencies\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	552 /* For each dmer group (group of positions with the same first d bytes):
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	553 * 1. For each position we set dmerAt[position] = dmerID. The dmerID is
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	554 * (groupBeginPtr - suffix). This allows us to go from position to
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	555 * dmerID so we can look up values in freq.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	556 * 2. We calculate how many samples the dmer occurs in and save it in
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	557 * freqs[dmerId].
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	558 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	559 COVER_groupBy(ctx->suffix, ctx->suffixSize, sizeof(U32), ctx, &COVER_cmp,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	560 &COVER_group);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	561 ctx->freqs = ctx->suffix;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	562 ctx->suffix = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	563 return 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	564 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	565
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	566 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	567 * Given the prepared context build the dictionary.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	568 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	569 static size_t COVER_buildDictionary(const COVER_ctx_t ctx, U32 freqs,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	570 COVER_map_t activeDmers, void dictBuffer,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	571 size_t dictBufferCapacity,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	572 COVER_params_t parameters) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	573 BYTE const dict = (BYTE )dictBuffer;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	574 size_t tail = dictBufferCapacity;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	575 /* Divide the data up into epochs of equal size.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	576 * We will select at least one segment from each epoch.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	577 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	578 const U32 epochs = (U32)(dictBufferCapacity / parameters.k);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	579 const U32 epochSize = (U32)(ctx->suffixSize / epochs);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	580 size_t epoch;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	581 DISPLAYLEVEL(2, "Breaking content into %u epochs of size %u\n", epochs,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	582 epochSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	583 /* Loop through the epochs until there are no more segments or the dictionary
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	584 * is full.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	585 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	586 for (epoch = 0; tail > 0; epoch = (epoch + 1) % epochs) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	587 const U32 epochBegin = (U32)(epoch * epochSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	588 const U32 epochEnd = epochBegin + epochSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	589 size_t segmentSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	590 /* Select a segment */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	591 COVER_segment_t segment = COVER_selectSegment(
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	592 ctx, freqs, activeDmers, epochBegin, epochEnd, parameters);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	593 /* Trim the segment if necessary and if it is empty then we are done */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	594 segmentSize = MIN(segment.end - segment.begin + parameters.d - 1, tail);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	595 if (segmentSize == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	596 break;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	597 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	598 /* We fill the dictionary from the back to allow the best segments to be
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	599 * referenced with the smallest offsets.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	600 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	601 tail -= segmentSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	602 memcpy(dict + tail, ctx->samples + segment.begin, segmentSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	603 DISPLAYUPDATE(
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	604 2, "\r%u%% ",
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	605 (U32)(((dictBufferCapacity - tail) * 100) / dictBufferCapacity));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	606 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	607 DISPLAYLEVEL(2, "\r%79s\r", "");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	608 return tail;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	609 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	610
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	611 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	612 * Translate from COVER_params_t to ZDICT_params_t required for finalizing the
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	613 * dictionary.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	614 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	615 static ZDICT_params_t COVER_translateParams(COVER_params_t parameters) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	616 ZDICT_params_t zdictParams;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	617 memset(&zdictParams, 0, sizeof(zdictParams));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	618 zdictParams.notificationLevel = 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	619 zdictParams.dictID = parameters.dictID;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	620 zdictParams.compressionLevel = parameters.compressionLevel;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	621 return zdictParams;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	622 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	623
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	624 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	625 * Constructs a dictionary using a heuristic based on the following paper:
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	626 *
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	627 * Liao, Petri, Moffat, Wirth
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	628 * Effective Construction of Relative Lempel-Ziv Dictionaries
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	629 * Published in WWW 2016.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	630 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	631 ZDICTLIB_API size_t COVER_trainFromBuffer(
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	632 void dictBuffer, size_t dictBufferCapacity, const void samplesBuffer,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	633 const size_t *samplesSizes, unsigned nbSamples, COVER_params_t parameters) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	634 BYTE const dict = (BYTE )dictBuffer;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	635 COVER_ctx_t ctx;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	636 COVER_map_t activeDmers;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	637 /* Checks */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	638 if (!COVER_checkParameters(parameters)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	639 DISPLAYLEVEL(1, "Cover parameters incorrect\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	640 return ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	641 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	642 if (nbSamples == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	643 DISPLAYLEVEL(1, "Cover must have at least one input file\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	644 return ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	645 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	646 if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	647 DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n",
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	648 ZDICT_DICTSIZE_MIN);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	649 return ERROR(dstSize_tooSmall);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	650 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	651 /* Initialize global data */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	652 g_displayLevel = parameters.notificationLevel;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	653 /* Initialize context and activeDmers */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	654 if (!COVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	655 parameters.d)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	656 return ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	657 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	658 if (!COVER_map_init(&activeDmers, parameters.k - parameters.d + 1)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	659 DISPLAYLEVEL(1, "Failed to allocate dmer map: out of memory\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	660 COVER_ctx_destroy(&ctx);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	661 return ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	662 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	663
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	664 DISPLAYLEVEL(2, "Building dictionary\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	665 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	666 const size_t tail =
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	667 COVER_buildDictionary(&ctx, ctx.freqs, &activeDmers, dictBuffer,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	668 dictBufferCapacity, parameters);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	669 ZDICT_params_t zdictParams = COVER_translateParams(parameters);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	670 const size_t dictionarySize = ZDICT_finalizeDictionary(
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	671 dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	672 samplesBuffer, samplesSizes, nbSamples, zdictParams);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	673 if (!ZSTD_isError(dictionarySize)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	674 DISPLAYLEVEL(2, "Constructed dictionary of size %u\n",
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	675 (U32)dictionarySize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	676 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	677 COVER_ctx_destroy(&ctx);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	678 COVER_map_destroy(&activeDmers);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	679 return dictionarySize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	680 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	681 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	682
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	683 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	684 * COVER_best_t is used for two purposes:
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	685 * 1. Synchronizing threads.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	686 * 2. Saving the best parameters and dictionary.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	687 *
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	688 * All of the methods except COVER_best_init() are thread safe if zstd is
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	689 * compiled with multithreaded support.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	690 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	691 typedef struct COVER_best_s {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	692 pthread_mutex_t mutex;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	693 pthread_cond_t cond;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	694 size_t liveJobs;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	695 void *dict;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	696 size_t dictSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	697 COVER_params_t parameters;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	698 size_t compressedSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	699 } COVER_best_t;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	700
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	701 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	702 * Initialize the `COVER_best_t`.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	703 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	704 static void COVER_best_init(COVER_best_t *best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	705 if (!best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	706 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	707 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	708 pthread_mutex_init(&best->mutex, NULL);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	709 pthread_cond_init(&best->cond, NULL);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	710 best->liveJobs = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	711 best->dict = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	712 best->dictSize = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	713 best->compressedSize = (size_t)-1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	714 memset(&best->parameters, 0, sizeof(best->parameters));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	715 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	716
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	717 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	718 * Wait until liveJobs == 0.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	719 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	720 static void COVER_best_wait(COVER_best_t *best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	721 if (!best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	722 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	723 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	724 pthread_mutex_lock(&best->mutex);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	725 while (best->liveJobs != 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	726 pthread_cond_wait(&best->cond, &best->mutex);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	727 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	728 pthread_mutex_unlock(&best->mutex);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	729 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	730
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	731 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	732 * Call COVER_best_wait() and then destroy the COVER_best_t.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	733 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	734 static void COVER_best_destroy(COVER_best_t *best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	735 if (!best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	736 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	737 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	738 COVER_best_wait(best);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	739 if (best->dict) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	740 free(best->dict);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	741 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	742 pthread_mutex_destroy(&best->mutex);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	743 pthread_cond_destroy(&best->cond);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	744 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	745
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	746 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	747 * Called when a thread is about to be launched.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	748 * Increments liveJobs.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	749 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	750 static void COVER_best_start(COVER_best_t *best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	751 if (!best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	752 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	753 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	754 pthread_mutex_lock(&best->mutex);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	755 ++best->liveJobs;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	756 pthread_mutex_unlock(&best->mutex);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	757 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	758
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	759 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	760 * Called when a thread finishes executing, both on error or success.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	761 * Decrements liveJobs and signals any waiting threads if liveJobs == 0.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	762 * If this dictionary is the best so far save it and its parameters.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	763 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	764 static void COVER_best_finish(COVER_best_t *best, size_t compressedSize,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	765 COVER_params_t parameters, void *dict,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	766 size_t dictSize) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	767 if (!best) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	768 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	769 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	770 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	771 size_t liveJobs;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	772 pthread_mutex_lock(&best->mutex);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	773 --best->liveJobs;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	774 liveJobs = best->liveJobs;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	775 /* If the new dictionary is better */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	776 if (compressedSize < best->compressedSize) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	777 /* Allocate space if necessary */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	778 if (!best->dict \|\| best->dictSize < dictSize) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	779 if (best->dict) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	780 free(best->dict);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	781 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	782 best->dict = malloc(dictSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	783 if (!best->dict) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	784 best->compressedSize = ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	785 best->dictSize = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	786 return;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	787 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	788 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	789 /* Save the dictionary, parameters, and size */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	790 memcpy(best->dict, dict, dictSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	791 best->dictSize = dictSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	792 best->parameters = parameters;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	793 best->compressedSize = compressedSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	794 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	795 pthread_mutex_unlock(&best->mutex);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	796 if (liveJobs == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	797 pthread_cond_broadcast(&best->cond);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	798 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	799 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	800 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	801
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	802 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	803 * Parameters for COVER_tryParameters().
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	804 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	805 typedef struct COVER_tryParameters_data_s {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	806 const COVER_ctx_t *ctx;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	807 COVER_best_t *best;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	808 size_t dictBufferCapacity;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	809 COVER_params_t parameters;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	810 } COVER_tryParameters_data_t;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	811
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	812 /**
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	813 * Tries a set of parameters and upates the COVER_best_t with the results.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	814 * This function is thread safe if zstd is compiled with multithreaded support.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	815 * It takes its parameters as an OWNING opaque pointer to support threading.
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	816 */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	817 static void COVER_tryParameters(void *opaque) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	818 /* Save parameters as local variables */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	819 COVER_tryParameters_data_t const data = (COVER_tryParameters_data_t )opaque;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	820 const COVER_ctx_t *const ctx = data->ctx;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	821 const COVER_params_t parameters = data->parameters;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	822 size_t dictBufferCapacity = data->dictBufferCapacity;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	823 size_t totalCompressedSize = ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	824 /* Allocate space for hash table, dict, and freqs */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	825 COVER_map_t activeDmers;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	826 BYTE const dict = (BYTE const)malloc(dictBufferCapacity);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	827 U32 freqs = (U32 )malloc(ctx->suffixSize * sizeof(U32));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	828 if (!COVER_map_init(&activeDmers, parameters.k - parameters.d + 1)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	829 DISPLAYLEVEL(1, "Failed to allocate dmer map: out of memory\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	830 goto _cleanup;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	831 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	832 if (!dict \|\| !freqs) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	833 DISPLAYLEVEL(1, "Failed to allocate buffers: out of memory\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	834 goto _cleanup;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	835 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	836 /* Copy the frequencies because we need to modify them */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	837 memcpy(freqs, ctx->freqs, ctx->suffixSize * sizeof(U32));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	838 /* Build the dictionary */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	839 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	840 const size_t tail = COVER_buildDictionary(ctx, freqs, &activeDmers, dict,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	841 dictBufferCapacity, parameters);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	842 const ZDICT_params_t zdictParams = COVER_translateParams(parameters);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	843 dictBufferCapacity = ZDICT_finalizeDictionary(
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	844 dict, dictBufferCapacity, dict + tail, dictBufferCapacity - tail,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	845 ctx->samples, ctx->samplesSizes, (unsigned)ctx->nbSamples, zdictParams);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	846 if (ZDICT_isError(dictBufferCapacity)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	847 DISPLAYLEVEL(1, "Failed to finalize dictionary\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	848 goto _cleanup;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	849 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	850 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	851 /* Check total compressed size */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	852 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	853 /* Pointers */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	854 ZSTD_CCtx *cctx;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	855 ZSTD_CDict *cdict;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	856 void *dst;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	857 /* Local variables */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	858 size_t dstCapacity;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	859 size_t i;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	860 /* Allocate dst with enough space to compress the maximum sized sample */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	861 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	862 size_t maxSampleSize = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	863 for (i = 0; i < ctx->nbSamples; ++i) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	864 maxSampleSize = MAX(ctx->samplesSizes[i], maxSampleSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	865 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	866 dstCapacity = ZSTD_compressBound(maxSampleSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	867 dst = malloc(dstCapacity);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	868 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	869 /* Create the cctx and cdict */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	870 cctx = ZSTD_createCCtx();
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	871 cdict =
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	872 ZSTD_createCDict(dict, dictBufferCapacity, parameters.compressionLevel);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	873 if (!dst \|\| !cctx \|\| !cdict) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	874 goto _compressCleanup;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	875 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	876 /* Compress each sample and sum their sizes (or error) */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	877 totalCompressedSize = 0;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	878 for (i = 0; i < ctx->nbSamples; ++i) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	879 const size_t size = ZSTD_compress_usingCDict(
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	880 cctx, dst, dstCapacity, ctx->samples + ctx->offsets[i],
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	881 ctx->samplesSizes[i], cdict);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	882 if (ZSTD_isError(size)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	883 totalCompressedSize = ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	884 goto _compressCleanup;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	885 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	886 totalCompressedSize += size;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	887 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	888 _compressCleanup:
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	889 ZSTD_freeCCtx(cctx);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	890 ZSTD_freeCDict(cdict);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	891 if (dst) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	892 free(dst);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	893 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	894 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	895
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	896 _cleanup:
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	897 COVER_best_finish(data->best, totalCompressedSize, parameters, dict,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	898 dictBufferCapacity);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	899 free(data);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	900 COVER_map_destroy(&activeDmers);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	901 if (dict) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	902 free(dict);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	903 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	904 if (freqs) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	905 free(freqs);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	906 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	907 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	908
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	909 ZDICTLIB_API size_t COVER_optimizeTrainFromBuffer(void *dictBuffer,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	910 size_t dictBufferCapacity,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	911 const void *samplesBuffer,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	912 const size_t *samplesSizes,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	913 unsigned nbSamples,
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	914 COVER_params_t *parameters) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	915 /* constants */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	916 const unsigned nbThreads = parameters->nbThreads;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	917 const unsigned kMinD = parameters->d == 0 ? 6 : parameters->d;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	918 const unsigned kMaxD = parameters->d == 0 ? 16 : parameters->d;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	919 const unsigned kMinK = parameters->k == 0 ? kMaxD : parameters->k;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	920 const unsigned kMaxK = parameters->k == 0 ? 2048 : parameters->k;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	921 const unsigned kSteps = parameters->steps == 0 ? 32 : parameters->steps;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	922 const unsigned kStepSize = MAX((kMaxK - kMinK) / kSteps, 1);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	923 const unsigned kIterations =
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	924 (1 + (kMaxD - kMinD) / 2) * (1 + (kMaxK - kMinK) / kStepSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	925 /* Local variables */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	926 const int displayLevel = parameters->notificationLevel;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	927 unsigned iteration = 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	928 unsigned d;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	929 unsigned k;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	930 COVER_best_t best;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	931 POOL_ctx *pool = NULL;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	932 /* Checks */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	933 if (kMinK < kMaxD \|\| kMaxK < kMinK) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	934 LOCALDISPLAYLEVEL(displayLevel, 1, "Incorrect parameters\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	935 return ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	936 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	937 if (nbSamples == 0) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	938 DISPLAYLEVEL(1, "Cover must have at least one input file\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	939 return ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	940 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	941 if (dictBufferCapacity < ZDICT_DICTSIZE_MIN) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	942 DISPLAYLEVEL(1, "dictBufferCapacity must be at least %u\n",
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	943 ZDICT_DICTSIZE_MIN);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	944 return ERROR(dstSize_tooSmall);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	945 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	946 if (nbThreads > 1) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	947 pool = POOL_create(nbThreads, 1);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	948 if (!pool) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	949 return ERROR(memory_allocation);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	950 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	951 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	952 /* Initialization */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	953 COVER_best_init(&best);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	954 /* Turn down global display level to clean up display at level 2 and below */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	955 g_displayLevel = parameters->notificationLevel - 1;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	956 /* Loop through d first because each new value needs a new context */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	957 LOCALDISPLAYLEVEL(displayLevel, 2, "Trying %u different sets of parameters\n",
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	958 kIterations);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	959 for (d = kMinD; d <= kMaxD; d += 2) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	960 /* Initialize the context for this value of d */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	961 COVER_ctx_t ctx;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	962 LOCALDISPLAYLEVEL(displayLevel, 3, "d=%u\n", d);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	963 if (!COVER_ctx_init(&ctx, samplesBuffer, samplesSizes, nbSamples, d)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	964 LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to initialize context\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	965 COVER_best_destroy(&best);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	966 return ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	967 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	968 /* Loop through k reusing the same context */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	969 for (k = kMinK; k <= kMaxK; k += kStepSize) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	970 /* Prepare the arguments */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	971 COVER_tryParameters_data_t data = (COVER_tryParameters_data_t )malloc(
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	972 sizeof(COVER_tryParameters_data_t));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	973 LOCALDISPLAYLEVEL(displayLevel, 3, "k=%u\n", k);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	974 if (!data) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	975 LOCALDISPLAYLEVEL(displayLevel, 1, "Failed to allocate parameters\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	976 COVER_best_destroy(&best);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	977 COVER_ctx_destroy(&ctx);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	978 return ERROR(GENERIC);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	979 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	980 data->ctx = &ctx;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	981 data->best = &best;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	982 data->dictBufferCapacity = dictBufferCapacity;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	983 data->parameters = *parameters;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	984 data->parameters.k = k;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	985 data->parameters.d = d;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	986 data->parameters.steps = kSteps;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	987 /* Check the parameters */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	988 if (!COVER_checkParameters(data->parameters)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	989 DISPLAYLEVEL(1, "Cover parameters incorrect\n");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	990 continue;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	991 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	992 /* Call the function and pass ownership of data to it */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	993 COVER_best_start(&best);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	994 if (pool) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	995 POOL_add(pool, &COVER_tryParameters, data);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	996 } else {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	997 COVER_tryParameters(data);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	998 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	999 /* Print status */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1000 LOCALDISPLAYUPDATE(displayLevel, 2, "\r%u%% ",
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1001 (U32)((iteration * 100) / kIterations));
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1002 ++iteration;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1003 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1004 COVER_best_wait(&best);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1005 COVER_ctx_destroy(&ctx);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1006 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1007 LOCALDISPLAYLEVEL(displayLevel, 2, "\r%79s\r", "");
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1008 /* Fill the output buffer and parameters with output of the best parameters */
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1009 {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1010 const size_t dictSize = best.dictSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1011 if (ZSTD_isError(best.compressedSize)) {
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1012 COVER_best_destroy(&best);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1013 return best.compressedSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1014 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1015 *parameters = best.parameters;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1016 memcpy(dictBuffer, best.dict, dictSize);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1017 COVER_best_destroy(&best);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1018 POOL_free(pool);
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1019 return dictSize;
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1020 }
c32454d69b85 zstd: vendor python-zstandard 0.7.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1021 }

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/dictBuilder/cover.c @ 35320:d901a88891fe