1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#ifndef INSERT_STRING_H_
#define INSERT_STRING_H_
/* insert_string_tpl.h -- Private insert_string functions shared with more than
* one insert string implementation
*
* Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler
*
* Copyright (C) 2013 Intel Corporation. All rights reserved.
* Authors:
* Wajdi Feghali <wajdi.k.feghali@intel.com>
* Jim Guilford <james.guilford@intel.com>
* Vinodh Gopal <vinodh.gopal@intel.com>
* Erdinc Ozturk <erdinc.ozturk@intel.com>
* Jim Kukunas <james.t.kukunas@linux.intel.com>
*
* Portions are Copyright (C) 2016 12Sided Technology, LLC.
* Author:
* Phil Vachon <pvachon@12sidedtech.com>
*
* For conditions of distribution and use, see copyright notice in zlib.h
*
*/
#include "zmemory.h"
#ifndef HASH_CALC_OFFSET
# define HASH_CALC_OFFSET 0
#endif
#ifndef HASH_CALC_MASK
# define HASH_CALC_MASK HASH_MASK
#endif
#ifndef HASH_CALC_READ
# if BYTE_ORDER == LITTLE_ENDIAN
# define HASH_CALC_READ \
val = zng_memread_4(strstart);
# else
# define HASH_CALC_READ \
val = ZSWAP32(zng_memread_4(strstart));
# endif
#endif
/* ===========================================================================
* Update a hash value with the given input byte
* IN assertion: all calls to UPDATE_HASH are made with consecutive
* input characters, so that a running hash key can be computed from the
* previous key instead of complete recalculation each time.
*/
Z_INTERNAL uint32_t UPDATE_HASH(uint32_t h, uint32_t val) {
HASH_CALC(h, val);
return h & HASH_CALC_MASK;
}
/* ===========================================================================
* Quick insert string str in the dictionary and set match_head to the previous head
* of the hash chain (the most recent string with same hash key). Return
* the previous length of the hash chain.
*/
Z_INTERNAL Pos QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) {
Pos head;
uint8_t *strstart = s->window + str + HASH_CALC_OFFSET;
uint32_t val, hm;
HASH_CALC_VAR_INIT;
HASH_CALC_READ;
HASH_CALC(HASH_CALC_VAR, val);
HASH_CALC_VAR &= HASH_CALC_MASK;
hm = HASH_CALC_VAR;
head = s->head[hm];
if (LIKELY(head != str)) {
s->prev[str & s->w_mask] = head;
s->head[hm] = (Pos)str;
}
return head;
}
/* ===========================================================================
* Insert string str in the dictionary and set match_head to the previous head
* of the hash chain (the most recent string with same hash key). Return
* the previous length of the hash chain.
* IN assertion: all calls to INSERT_STRING are made with consecutive
* input characters and the first STD_MIN_MATCH bytes of str are valid
* (except for the last STD_MIN_MATCH-1 bytes of the input file).
*/
Z_INTERNAL void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) {
uint8_t *strstart = s->window + str + HASH_CALC_OFFSET;
uint8_t *strend = strstart + count;
for (Pos idx = (Pos)str; strstart < strend; idx++, strstart++) {
uint32_t val, hm;
HASH_CALC_VAR_INIT;
HASH_CALC_READ;
HASH_CALC(HASH_CALC_VAR, val);
HASH_CALC_VAR &= HASH_CALC_MASK;
hm = HASH_CALC_VAR;
Pos head = s->head[hm];
if (LIKELY(head != idx)) {
s->prev[idx & s->w_mask] = head;
s->head[hm] = idx;
}
}
}
#endif
|
