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