"Fossies" - the Fresh Open Source Software Archive 
Member "xdelta3-3.0.11/xdelta3-hash.h" (24 Mar 2015, 4735 Bytes) of package /linux/misc/xdelta3-3.0.11.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "xdelta3-hash.h" see the
Fossies "Dox" file reference documentation.
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 #ifndef _XDELTA3_HASH_H_
20 #define _XDELTA3_HASH_H_
21
22 #if XD3_DEBUG
23 #define SMALL_HASH_DEBUG1(s,inp) \
24 uint32_t debug_state; \
25 uint32_t debug_hval = xd3_checksum_hash (& (s)->small_hash, \
26 xd3_scksum (&debug_state, (inp), (s)->smatcher.small_look))
27 #define SMALL_HASH_DEBUG2(s,inp) \
28 XD3_ASSERT (debug_hval == xd3_checksum_hash (& (s)->small_hash, \
29 xd3_scksum (&debug_state, (inp), (s)->smatcher.small_look)))
30 #else
31 #define SMALL_HASH_DEBUG1(s,inp)
32 #define SMALL_HASH_DEBUG2(s,inp)
33 #endif /* XD3_DEBUG */
34
35 /* This is a good hash multiplier for 32-bit LCGs: see "linear
36 * congruential generators of different sizes and good lattice
37 * structure" */
38 static const uint32_t hash_multiplier = 1597334677U;
39
40 /***********************************************************************
41 Permute stuff
42 ***********************************************************************/
43
44 #if HASH_PERMUTE == 0
45 #define PERMUTE(x) (x)
46 #else
47 #define PERMUTE(x) (__single_hash[(uint32_t)x])
48
49 extern const uint16_t __single_hash[256];
50 #endif
51
52 /* Update the checksum state. */
53 #if ADLER_LARGE_CKSUM
54 inline uint32_t
55 xd3_large_cksum_update (uint32_t cksum,
56 const uint8_t *base,
57 usize_t look) {
58 uint32_t old_c = PERMUTE(base[0]);
59 uint32_t new_c = PERMUTE(base[look]);
60 uint32_t low = ((cksum & 0xffff) - old_c + new_c) & 0xffff;
61 uint32_t high = ((cksum >> 16) - (old_c * look) + low) & 0xffff;
62 return (high << 16) | low;
63 }
64 #else
65 /* TODO: revisit this topic */
66 #endif
67
68 #if UNALIGNED_OK
69 #define UNALIGNED_READ32(dest,src) (*(dest)) = (*(uint32_t*)(src))
70 #else
71 #define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4);
72 #endif
73
74 /* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */
75 static inline uint32_t
76 xd3_scksum (uint32_t *state,
77 const uint8_t *base,
78 const usize_t look)
79 {
80 UNALIGNED_READ32(state, base);
81 return (*state) * hash_multiplier;
82 }
83 static inline uint32_t
84 xd3_small_cksum_update (uint32_t *state,
85 const uint8_t *base,
86 usize_t look)
87 {
88 UNALIGNED_READ32(state, base+1);
89 return (*state) * hash_multiplier;
90 }
91
92 /***********************************************************************
93 Ctable stuff
94 ***********************************************************************/
95
96 static inline usize_t
97 xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum)
98 {
99 return (cksum >> cfg->shift) ^ (cksum & cfg->mask);
100 }
101
102 /***********************************************************************
103 Cksum function
104 ***********************************************************************/
105
106 #if ADLER_LARGE_CKSUM
107 static inline uint32_t
108 xd3_lcksum (const uint8_t *seg, const usize_t ln)
109 {
110 usize_t i = 0;
111 uint32_t low = 0;
112 uint32_t high = 0;
113
114 for (; i < ln; i += 1)
115 {
116 low += PERMUTE(*seg++);
117 high += low;
118 }
119
120 return ((high & 0xffff) << 16) | (low & 0xffff);
121 }
122 #else
123 static inline uint32_t
124 xd3_lcksum (const uint8_t *seg, const usize_t ln)
125 {
126 usize_t i, j;
127 uint32_t h = 0;
128 for (i = 0, j = ln - 1; i < ln; ++i, --j) {
129 h += PERMUTE(seg[i]) * hash_multiplier_powers[j];
130 }
131 return h;
132 }
133 #endif
134
135 #if XD3_ENCODER
136 static usize_t
137 xd3_size_log2 (usize_t slots)
138 {
139 int bits = 28; /* This should not be an unreasonable limit. */
140 int i;
141
142 for (i = 3; i <= bits; i += 1)
143 {
144 if (slots < (1U << i))
145 {
146 /* TODO: this is compaction=1 in checksum_test.cc and maybe should
147 * not be fixed at -1. */
148 bits = i - 1;
149 break;
150 }
151 }
152
153 return bits;
154 }
155
156 static void
157 xd3_size_hashtable (xd3_stream *stream,
158 usize_t slots,
159 xd3_hash_cfg *cfg)
160 {
161 int bits = xd3_size_log2 (slots);
162
163 /* TODO: there's a 32-bit assumption here */
164 cfg->size = (1 << bits);
165 cfg->mask = (cfg->size - 1);
166 cfg->shift = 32 - bits;
167 }
168 #endif
169
170 #endif