1 /* xdelta3 - delta compression tools and library
2 Copyright 2016 Joshua MacDonald
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16 #ifndef _XDELTA3_HASH_H_
17 #define _XDELTA3_HASH_H_
18
19 #include "xdelta3-internal.h"
20
21 #if XD3_DEBUG
22 #define SMALL_HASH_DEBUG1(s,inp) \
23 uint32_t debug_state; \
24 uint32_t debug_hval = xd3_checksum_hash (& (s)->small_hash, \
25 xd3_scksum (&debug_state, (inp), (s)->smatcher.small_look))
26 #define SMALL_HASH_DEBUG2(s,inp) \
27 XD3_ASSERT (debug_hval == xd3_checksum_hash (& (s)->small_hash, \
28 xd3_scksum (&debug_state, (inp), (s)->smatcher.small_look)))
29 #else
30 #define SMALL_HASH_DEBUG1(s,inp)
31 #define SMALL_HASH_DEBUG2(s,inp)
32 #endif /* XD3_DEBUG */
33
34 #if UNALIGNED_OK
35 #define UNALIGNED_READ32(dest,src) (*(dest)) = (*(uint32_t*)(src))
36 #else
37 #define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4);
38 #endif
39
40 /* These are good hash multipliers for 32-bit and 64-bit LCGs: see
41 * "linear congruential generators of different sizes and good lattice
42 * structure" */
43 #define xd3_hash_multiplier32 1597334677U
44 #define xd3_hash_multiplier64 1181783497276652981ULL
45
46 /* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */
47 static inline uint32_t
xd3_scksum(uint32_t * state,const uint8_t * base,const usize_t look)48 xd3_scksum (uint32_t *state,
49 const uint8_t *base,
50 const usize_t look)
51 {
52 UNALIGNED_READ32(state, base);
53 return (*state) * xd3_hash_multiplier32;
54 }
55 static inline uint32_t
xd3_small_cksum_update(uint32_t * state,const uint8_t * base,usize_t look)56 xd3_small_cksum_update (uint32_t *state,
57 const uint8_t *base,
58 usize_t look)
59 {
60 UNALIGNED_READ32(state, base+1);
61 return (*state) * xd3_hash_multiplier32;
62 }
63
64 #if XD3_ENCODER
65 inline usize_t
xd3_checksum_hash(const xd3_hash_cfg * cfg,const usize_t cksum)66 xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum)
67 {
68 return (cksum >> cfg->shift) ^ (cksum & cfg->mask);
69 }
70
71 #if SIZEOF_USIZE_T == 4
72 inline uint32_t
xd3_large32_cksum(xd3_hash_cfg * cfg,const uint8_t * base,const usize_t look)73 xd3_large32_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look)
74 {
75 uint32_t h = 0;
76 for (usize_t i = 0; i < look; i++) {
77 h += base[i] * cfg->powers[i];
78 }
79 return h;
80 }
81
82 inline uint32_t
xd3_large32_cksum_update(xd3_hash_cfg * cfg,const uint32_t cksum,const uint8_t * base,const usize_t look)83 xd3_large32_cksum_update (xd3_hash_cfg *cfg, const uint32_t cksum,
84 const uint8_t *base, const usize_t look)
85 {
86 return xd3_hash_multiplier32 * cksum - cfg->multiplier * base[0] + base[look];
87 }
88 #endif
89
90 #if SIZEOF_USIZE_T == 8
91 inline uint64_t
xd3_large64_cksum(xd3_hash_cfg * cfg,const uint8_t * base,const usize_t look)92 xd3_large64_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look)
93 {
94 uint64_t h = 0;
95 for (usize_t i = 0; i < look; i++) {
96 h += base[i] * cfg->powers[i];
97 }
98 return h;
99 }
100
101 inline uint64_t
xd3_large64_cksum_update(xd3_hash_cfg * cfg,const uint64_t cksum,const uint8_t * base,const usize_t look)102 xd3_large64_cksum_update (xd3_hash_cfg *cfg, const uint64_t cksum,
103 const uint8_t *base, const usize_t look)
104 {
105 return xd3_hash_multiplier64 * cksum - cfg->multiplier * base[0] + base[look];
106 }
107 #endif
108
109 static usize_t
xd3_size_hashtable_bits(usize_t slots)110 xd3_size_hashtable_bits (usize_t slots)
111 {
112 usize_t bits = (SIZEOF_USIZE_T * 8) - 1;
113 usize_t i;
114
115 for (i = 3; i <= bits; i += 1)
116 {
117 if (slots < (1U << i))
118 {
119 /* Note: this is the compaction=1 setting measured in
120 * checksum_test */
121 bits = i - 1;
122 break;
123 }
124 }
125
126 return bits;
127 }
128
129 int
xd3_size_hashtable(xd3_stream * stream,usize_t slots,usize_t look,xd3_hash_cfg * cfg)130 xd3_size_hashtable (xd3_stream *stream,
131 usize_t slots,
132 usize_t look,
133 xd3_hash_cfg *cfg)
134 {
135 usize_t bits = xd3_size_hashtable_bits (slots);
136
137 cfg->size = (1U << bits);
138 cfg->mask = (cfg->size - 1);
139 cfg->shift = (SIZEOF_USIZE_T * 8) - bits;
140 cfg->look = look;
141
142 if ((cfg->powers =
143 (usize_t*) xd3_alloc0 (stream, look, sizeof (usize_t))) == NULL)
144 {
145 return ENOMEM;
146 }
147
148 cfg->powers[look-1] = 1;
149 for (int i = look-2; i >= 0; i--)
150 {
151 cfg->powers[i] = cfg->powers[i+1] * xd3_hash_multiplier;
152 }
153 cfg->multiplier = cfg->powers[0] * xd3_hash_multiplier;
154
155 return 0;
156 }
157
158 #endif /* XD3_ENCODER */
159 #endif /* _XDELTA3_HASH_H_ */
160