"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/xdelta3-hash.h" (26 Sep 2015, 4509 Bytes) of package /linux/misc/xdelta3-3.1.0.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 and the latest Fossies "Diffs" side-by-side code changes report: 3.0.11_vs_3.1.0.

    1 /* xdelta 3 - delta compression tools and library
    2  * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, 2011, 2012, 2014.
    3  * Joshua P. MacDonald
    4  *
    5  *  This program is free software; you can redistribute it and/or modify
    6  *  it under the terms of the GNU General Public License as published by
    7  *  the Free Software Foundation; either version 2 of the License, or
    8  *  (at your option) any later version.
    9  *
   10  *  This program is distributed in the hope that it will be useful,
   11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   13  *  GNU General Public License for more details.
   14  *
   15  *  You should have received a copy of the GNU General Public License
   16  *  along with this program; if not, write to the Free Software
   17  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   18  */
   19 
   20 #ifndef _XDELTA3_HASH_H_
   21 #define _XDELTA3_HASH_H_
   22 
   23 #include "xdelta3-internal.h"
   24 
   25 #if XD3_DEBUG
   26 #define SMALL_HASH_DEBUG1(s,inp)                                  \
   27   uint32_t debug_state;                                           \
   28   uint32_t debug_hval = xd3_checksum_hash (& (s)->small_hash,     \
   29               xd3_scksum (&debug_state, (inp), (s)->smatcher.small_look))
   30 #define SMALL_HASH_DEBUG2(s,inp)                                  \
   31   XD3_ASSERT (debug_hval == xd3_checksum_hash (& (s)->small_hash, \
   32               xd3_scksum (&debug_state, (inp), (s)->smatcher.small_look)))
   33 #else
   34 #define SMALL_HASH_DEBUG1(s,inp)
   35 #define SMALL_HASH_DEBUG2(s,inp)
   36 #endif /* XD3_DEBUG */
   37 
   38 #if UNALIGNED_OK
   39 #define UNALIGNED_READ32(dest,src) (*(dest)) = (*(uint32_t*)(src))
   40 #else
   41 #define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4);
   42 #endif
   43 
   44 /* These are good hash multipliers for 32-bit and 64-bit LCGs: see
   45  * "linear congruential generators of different sizes and good lattice
   46  * structure" */
   47 #define xd3_hash_multiplier32 1597334677U
   48 #define xd3_hash_multiplier64 1181783497276652981ULL
   49 
   50 /* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */
   51 static inline uint32_t
   52 xd3_scksum (uint32_t *state,
   53             const uint8_t *base,
   54             const usize_t look)
   55 {
   56   UNALIGNED_READ32(state, base);
   57   return (*state) * xd3_hash_multiplier32;
   58 }
   59 static inline uint32_t
   60 xd3_small_cksum_update (uint32_t *state,
   61             const uint8_t *base,
   62             usize_t look)
   63 {
   64   UNALIGNED_READ32(state, base+1);
   65   return (*state) * xd3_hash_multiplier32;
   66 }
   67 
   68 #if XD3_ENCODER
   69 inline usize_t
   70 xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum)
   71 {
   72   return (cksum >> cfg->shift) ^ (cksum & cfg->mask);
   73 }
   74 
   75 #if SIZEOF_USIZE_T == 4
   76 inline uint32_t
   77 xd3_large32_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look)
   78 {
   79   uint32_t h = 0;
   80   for (usize_t i = 0; i < look; i++) {
   81     h += base[i] * cfg->powers[i];
   82   }
   83   return h;
   84 }
   85 
   86 inline uint32_t
   87 xd3_large32_cksum_update (xd3_hash_cfg *cfg, const uint32_t cksum,
   88               const uint8_t *base, const usize_t look)
   89 {
   90   return xd3_hash_multiplier32 * cksum - cfg->multiplier * base[0] + base[look];
   91 }
   92 #endif
   93 
   94 #if SIZEOF_USIZE_T == 8
   95 inline uint64_t
   96 xd3_large64_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look)
   97 {
   98   uint64_t h = 0;
   99   for (usize_t i = 0; i < look; i++) {
  100     h += base[i] * cfg->powers[i];
  101   }
  102   return h;
  103 }
  104 
  105 inline uint64_t
  106 xd3_large64_cksum_update (xd3_hash_cfg *cfg, const uint64_t cksum,
  107               const uint8_t *base, const usize_t look)
  108 {
  109   return xd3_hash_multiplier64 * cksum - cfg->multiplier * base[0] + base[look];
  110 }
  111 #endif
  112 
  113 static usize_t
  114 xd3_size_hashtable_bits (usize_t slots)
  115 {
  116   usize_t bits = (SIZEOF_USIZE_T * 8) - 1;
  117   usize_t i;
  118 
  119   for (i = 3; i <= bits; i += 1)
  120     {
  121       if (slots < (1U << i))
  122     {
  123       /* Note: this is the compaction=1 setting measured in
  124        * checksum_test */
  125       bits = i - 1;
  126       break;
  127     }
  128     }
  129 
  130   return bits;
  131 }
  132 
  133 int
  134 xd3_size_hashtable (xd3_stream   *stream,
  135             usize_t       slots,
  136             usize_t       look,
  137             xd3_hash_cfg *cfg)
  138 {
  139   usize_t bits = xd3_size_hashtable_bits (slots);
  140 
  141   cfg->size  = (1U << bits);
  142   cfg->mask  = (cfg->size - 1);
  143   cfg->shift = (SIZEOF_USIZE_T * 8) - bits;
  144   cfg->look  = look;
  145 
  146   if ((cfg->powers = 
  147        (usize_t*) xd3_alloc0 (stream, look, sizeof (usize_t))) == NULL)
  148     {
  149       return ENOMEM;
  150     }
  151 
  152   cfg->powers[look-1] = 1;
  153   for (int i = look-2; i >= 0; i--)
  154     {
  155       cfg->powers[i] = cfg->powers[i+1] * xd3_hash_multiplier;
  156     }
  157   cfg->multiplier = cfg->powers[0] * xd3_hash_multiplier;
  158 
  159   return 0;
  160 }
  161 
  162 #endif /* XD3_ENCODER */
  163 #endif /* _XDELTA3_HASH_H_ */