tizen 2.4 release
[external/xdelta3.git] / xdelta3-hash.h
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