diff options
author | josh.macdonald <jmacd@users.noreply.github.com> | 2007-11-11 07:59:13 +0000 |
---|---|---|
committer | josh.macdonald <jmacd@users.noreply.github.com> | 2007-11-11 07:59:13 +0000 |
commit | a4b5480a34e217e93e147f460b47e27741d809c1 (patch) | |
tree | ea759058caece01d1d09697c392f3a6d20c28bc5 /xdelta3/xdelta3-hash.h | |
parent | 9c137e5d088878e6867b5de40ddefa30a7afa59c (diff) |
Compile with g++ 3.4.4 and add C++ checksum_test.cc
Diffstat (limited to 'xdelta3/xdelta3-hash.h')
-rw-r--r-- | xdelta3/xdelta3-hash.h | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/xdelta3/xdelta3-hash.h b/xdelta3/xdelta3-hash.h new file mode 100644 index 0000000..a1cc9d8 --- /dev/null +++ b/xdelta3/xdelta3-hash.h | |||
@@ -0,0 +1,237 @@ | |||
1 | /* xdelta 3 - delta compression tools and library | ||
2 | * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007. Joshua P. MacDonald | ||
3 | * | ||
4 | * This program is free software; you can redistribute it and/or modify | ||
5 | * it under the terms of the GNU General Public License as published by | ||
6 | * the Free Software Foundation; either version 2 of the License, or | ||
7 | * (at your option) any later version. | ||
8 | * | ||
9 | * This program is distributed in the hope that it will be useful, | ||
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
12 | * GNU General Public License for more details. | ||
13 | * | ||
14 | * You should have received a copy of the GNU General Public License | ||
15 | * along with this program; if not, write to the Free Software | ||
16 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
17 | */ | ||
18 | |||
19 | /* To know more about Xdelta, start by reading xdelta3.c. If you are | ||
20 | * ready to use the API, continue reading here. There are two | ||
21 | * interfaces -- xd3_encode_input and xd3_decode_input -- plus a dozen | ||
22 | * or so related calls. This interface is styled after Zlib. */ | ||
23 | |||
24 | #ifndef _XDELTA3_HASH_H_ | ||
25 | #define _XDELTA3_HASH_H_ | ||
26 | |||
27 | #if XD3_DEBUG | ||
28 | #define SMALL_HASH_DEBUG1(s,inp) \ | ||
29 | usize_t debug_hval = xd3_checksum_hash (& (s)->small_hash, \ | ||
30 | xd3_scksum ((inp), (s)->smatcher.small_look)) | ||
31 | #define SMALL_HASH_DEBUG2(s,inp) \ | ||
32 | XD3_ASSERT (debug_hval == xd3_checksum_hash (& (s)->small_hash, \ | ||
33 | xd3_scksum ((inp), (s)->smatcher.small_look))) | ||
34 | #else | ||
35 | #define SMALL_HASH_DEBUG1(s,inp) | ||
36 | #define SMALL_HASH_DEBUG2(s,inp) | ||
37 | #endif /* XD3_DEBUG */ | ||
38 | |||
39 | /* Update the run-length state */ | ||
40 | #define NEXTRUN(c) do { if ((c) == run_c) { run_l += 1; } \ | ||
41 | else { run_c = (c); run_l = 1; } } while (0) | ||
42 | |||
43 | /* Update the checksum state. */ | ||
44 | #define OLD_LARGE_CKSUM 1 | ||
45 | #if OLD_LARGE_CKSUM | ||
46 | #define LARGE_CKSUM_UPDATE(cksum,base,look) \ | ||
47 | do { \ | ||
48 | uint32_t old_c = PERMUTE((base)[0]); \ | ||
49 | uint32_t new_c = PERMUTE((base)[(look)]); \ | ||
50 | uint32_t low = (((cksum) & 0xffff) - old_c + new_c) & 0xffff; \ | ||
51 | uint32_t high = (((cksum) >> 16) - (old_c * (look)) + low) & 0xffff; \ | ||
52 | (cksum) = (high << 16) | low; \ | ||
53 | } while (0) | ||
54 | #else | ||
55 | #define LARGE_CKSUM_UPDATE(cksum,base,look) \ | ||
56 | do { \ | ||
57 | // linear congruential generators of different | ||
58 | // sizes and good lattice structure | ||
59 | } while (1) | ||
60 | #endif | ||
61 | |||
62 | /* Multiply and add hash function */ | ||
63 | #if ARITH_SMALL_CKSUM | ||
64 | #define SMALL_CKSUM_UPDATE(cksum,base,look) (cksum) = ((*(unsigned long*)(base+1)) * 71143) | ||
65 | #else | ||
66 | #define SMALL_CKSUM_UPDATE LARGE_CKSUM_UPDATE | ||
67 | #endif | ||
68 | |||
69 | /*********************************************************************** | ||
70 | Permute stuff | ||
71 | ***********************************************************************/ | ||
72 | |||
73 | #if HASH_PERMUTE == 0 | ||
74 | #define PERMUTE(x) (x) | ||
75 | #else | ||
76 | #define PERMUTE(x) (__single_hash[(uint)x]) | ||
77 | |||
78 | static const uint16_t __single_hash[256] = | ||
79 | { | ||
80 | /* Random numbers generated using SLIB's pseudo-random number generator. This hashes | ||
81 | * the input alphabet. */ | ||
82 | 0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46, | ||
83 | 0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602, | ||
84 | 0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6, | ||
85 | 0xb645, 0xcb4d, 0xc44b, 0xe5dc, 0x9fe6, 0x5b5c, 0x35f5, 0x701a, | ||
86 | 0x220f, 0x6c38, 0x1a56, 0x4ca3, 0xffc6, 0xb152, 0x8d61, 0x7a58, | ||
87 | 0x9025, 0x8b3d, 0xbf0f, 0x95a3, 0xe5f4, 0xc127, 0x3bed, 0x320b, | ||
88 | 0xb7f3, 0x6054, 0x333c, 0xd383, 0x8154, 0x5242, 0x4e0d, 0x0a94, | ||
89 | 0x7028, 0x8689, 0x3a22, 0x0980, 0x1847, 0xb0f1, 0x9b5c, 0x4176, | ||
90 | 0xb858, 0xd542, 0x1f6c, 0x2497, 0x6a5a, 0x9fa9, 0x8c5a, 0x7743, | ||
91 | 0xa8a9, 0x9a02, 0x4918, 0x438c, 0xc388, 0x9e2b, 0x4cad, 0x01b6, | ||
92 | 0xab19, 0xf777, 0x365f, 0x1eb2, 0x091e, 0x7bf8, 0x7a8e, 0x5227, | ||
93 | 0xeab1, 0x2074, 0x4523, 0xe781, 0x01a3, 0x163d, 0x3b2e, 0x287d, | ||
94 | 0x5e7f, 0xa063, 0xb134, 0x8fae, 0x5e8e, 0xb7b7, 0x4548, 0x1f5a, | ||
95 | 0xfa56, 0x7a24, 0x900f, 0x42dc, 0xcc69, 0x02a0, 0x0b22, 0xdb31, | ||
96 | 0x71fe, 0x0c7d, 0x1732, 0x1159, 0xcb09, 0xe1d2, 0x1351, 0x52e9, | ||
97 | 0xf536, 0x5a4f, 0xc316, 0x6bf9, 0x8994, 0xb774, 0x5f3e, 0xf6d6, | ||
98 | 0x3a61, 0xf82c, 0xcc22, 0x9d06, 0x299c, 0x09e5, 0x1eec, 0x514f, | ||
99 | 0x8d53, 0xa650, 0x5c6e, 0xc577, 0x7958, 0x71ac, 0x8916, 0x9b4f, | ||
100 | 0x2c09, 0x5211, 0xf6d8, 0xcaaa, 0xf7ef, 0x287f, 0x7a94, 0xab49, | ||
101 | 0xfa2c, 0x7222, 0xe457, 0xd71a, 0x00c3, 0x1a76, 0xe98c, 0xc037, | ||
102 | 0x8208, 0x5c2d, 0xdfda, 0xe5f5, 0x0b45, 0x15ce, 0x8a7e, 0xfcad, | ||
103 | 0xaa2d, 0x4b5c, 0xd42e, 0xb251, 0x907e, 0x9a47, 0xc9a6, 0xd93f, | ||
104 | 0x085e, 0x35ce, 0xa153, 0x7e7b, 0x9f0b, 0x25aa, 0x5d9f, 0xc04d, | ||
105 | 0x8a0e, 0x2875, 0x4a1c, 0x295f, 0x1393, 0xf760, 0x9178, 0x0f5b, | ||
106 | 0xfa7d, 0x83b4, 0x2082, 0x721d, 0x6462, 0x0368, 0x67e2, 0x8624, | ||
107 | 0x194d, 0x22f6, 0x78fb, 0x6791, 0xb238, 0xb332, 0x7276, 0xf272, | ||
108 | 0x47ec, 0x4504, 0xa961, 0x9fc8, 0x3fdc, 0xb413, 0x007a, 0x0806, | ||
109 | 0x7458, 0x95c6, 0xccaa, 0x18d6, 0xe2ae, 0x1b06, 0xf3f6, 0x5050, | ||
110 | 0xc8e8, 0xf4ac, 0xc04c, 0xf41c, 0x992f, 0xae44, 0x5f1b, 0x1113, | ||
111 | 0x1738, 0xd9a8, 0x19ea, 0x2d33, 0x9698, 0x2fe9, 0x323f, 0xcde2, | ||
112 | 0x6d71, 0xe37d, 0xb697, 0x2c4f, 0x4373, 0x9102, 0x075d, 0x8e25, | ||
113 | 0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5 | ||
114 | }; | ||
115 | #endif | ||
116 | |||
117 | /*********************************************************************** | ||
118 | Ctable stuff | ||
119 | ***********************************************************************/ | ||
120 | |||
121 | #if HASH_PRIME | ||
122 | static const usize_t __primes[] = | ||
123 | { | ||
124 | 11, 19, 37, 73, 109, | ||
125 | 163, 251, 367, 557, 823, | ||
126 | 1237, 1861, 2777, 4177, 6247, | ||
127 | 9371, 14057, 21089, 31627, 47431, | ||
128 | 71143, 106721, 160073, 240101, 360163, | ||
129 | 540217, 810343, 1215497, 1823231, 2734867, | ||
130 | 4102283, 6153409, 9230113, 13845163, 20767711, | ||
131 | 31151543, 46727321, 70090921, 105136301, 157704401, | ||
132 | 236556601, 354834919, 532252367, 798378509, 1197567719, | ||
133 | 1796351503 | ||
134 | }; | ||
135 | |||
136 | static const usize_t __nprimes = SIZEOF_ARRAY (__primes); | ||
137 | #endif | ||
138 | |||
139 | static inline usize_t | ||
140 | xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum) | ||
141 | { | ||
142 | #if HASH_PRIME | ||
143 | /* If the table is prime compute the modulus. */ | ||
144 | return (cksum % cfg->size); | ||
145 | #else | ||
146 | /* If the table is power-of-two compute the mask.*/ | ||
147 | return (cksum ^ (cksum >> cfg->shift)) & cfg->mask; | ||
148 | #endif | ||
149 | } | ||
150 | |||
151 | /*********************************************************************** | ||
152 | Cksum function | ||
153 | ***********************************************************************/ | ||
154 | |||
155 | static inline uint32_t | ||
156 | xd3_lcksum (const uint8_t *seg, const int ln) | ||
157 | { | ||
158 | int i = 0; | ||
159 | uint32_t low = 0; | ||
160 | uint32_t high = 0; | ||
161 | |||
162 | for (; i < ln; i += 1) | ||
163 | { | ||
164 | low += PERMUTE(*seg++); | ||
165 | high += low; | ||
166 | } | ||
167 | |||
168 | return ((high & 0xffff) << 16) | (low & 0xffff); | ||
169 | } | ||
170 | |||
171 | #if ARITH_SMALL_CKSUM | ||
172 | static inline usize_t | ||
173 | xd3_scksum (const uint8_t *seg, const int ln) | ||
174 | { | ||
175 | usize_t c; | ||
176 | /* The -1 is because UPDATE operates on seg[1..ln] */ | ||
177 | SMALL_CKSUM_UPDATE (c,(seg-1),ln); | ||
178 | return c; | ||
179 | } | ||
180 | #else | ||
181 | #define xd3_scksum(seg,ln) xd3_lcksum(seg,ln) | ||
182 | #endif | ||
183 | |||
184 | #if XD3_ENCODER | ||
185 | #if !HASH_PRIME | ||
186 | static usize_t | ||
187 | xd3_size_log2 (usize_t slots) | ||
188 | { | ||
189 | int bits = 28; /* This should not be an unreasonable limit. */ | ||
190 | int i; | ||
191 | |||
192 | for (i = 3; i <= bits; i += 1) | ||
193 | { | ||
194 | if (slots < (1U << i)) | ||
195 | { | ||
196 | bits = i-1; | ||
197 | break; | ||
198 | } | ||
199 | } | ||
200 | |||
201 | return bits; | ||
202 | } | ||
203 | #endif | ||
204 | #endif | ||
205 | |||
206 | static void | ||
207 | xd3_size_hashtable (xd3_stream *stream, | ||
208 | usize_t slots, | ||
209 | xd3_hash_cfg *cfg) | ||
210 | { | ||
211 | /* initialize ctable: the number of hash buckets is computed from the table of primes or | ||
212 | * the nearest power-of-two, in both cases rounding down in favor of using less | ||
213 | * memory. */ | ||
214 | |||
215 | #if HASH_PRIME | ||
216 | usize_t i; | ||
217 | |||
218 | cfg->size = __primes[__nprimes-1]; | ||
219 | |||
220 | for (i = 1; i < __nprimes; i += 1) | ||
221 | { | ||
222 | if (slots < __primes[i]) | ||
223 | { | ||
224 | cfg->size = __primes[i-1]; | ||
225 | break; | ||
226 | } | ||
227 | } | ||
228 | #else | ||
229 | int bits = xd3_size_log2 (slots); | ||
230 | |||
231 | cfg->size = (1 << bits); | ||
232 | cfg->mask = (cfg->size - 1); | ||
233 | cfg->shift = min (32 - bits, 16); | ||
234 | #endif | ||
235 | } | ||
236 | |||
237 | #endif | ||