"Fossies" - the Fresh Open Source Software Archive

Member "zsync-0.6.2/librcksum/internal.h" (16 Sep 2010, 4130 Bytes) of package /linux/privat/old/zsync-0.6.2.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 "internal.h" see the Fossies "Dox" file reference documentation.

    1 
    2 /*
    3  *   rcksum/lib - library for using the rsync algorithm to determine
    4  *               which parts of a file you have and which you need.
    5  *   Copyright (C) 2004,2005,2009 Colin Phipps <cph@moria.org.uk>
    6  *
    7  *   This program is free software; you can redistribute it and/or modify
    8  *   it under the terms of the Artistic License v2 (see the accompanying 
    9  *   file COPYING for the full license terms), or, at your option, any later 
   10  *   version of the same license.
   11  *
   12  *   This program is distributed in the hope that it will be useful,
   13  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
   14  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   15  *   COPYING file for details.
   16  */
   17 
   18 /* Internal data structures to the library. Not to be included by code outside librcksum. */
   19 
   20 /* Two types of checksum -
   21  * rsum: rolling Adler-style checksum
   22  * checksum: hopefully-collision-resistant MD4 checksum of the block
   23  */
   24 
   25 struct hash_entry {
   26     struct hash_entry *next;    /* next entry with the same rsum */
   27     struct rsum r;
   28     unsigned char checksum[CHECKSUM_SIZE];
   29 };
   30 
   31 /* An rcksum_state contains the set of checksums of the blocks of a target
   32  * file, and is used to apply the rsync algorithm to detect data in common with
   33  * a local file. It essentially contains as rsum and a checksum per block of
   34  * the target file, plus various hash tables to speed up lookups when looping
   35  * over data looking for matching blocks. */
   36 
   37 struct rcksum_state {
   38     struct rsum r[2];           /* Current rsums */
   39 
   40     zs_blockid blocks;          /* Number of blocks in the target file */
   41     size_t blocksize;           /* And how many bytes per block */
   42     int blockshift;             /* log2(blocksize) */
   43     unsigned short rsum_a_mask; /* The mask to apply to rsum values before looking up */
   44     int checksum_bytes;         /* How many bytes of the MD4 checksum are available */
   45     int seq_matches;
   46 
   47     unsigned int context;       /* precalculated blocksize * seq_matches */
   48 
   49     /* These are used by the library. Note, not thread safe. */
   50     const struct hash_entry *rover;
   51     int skip;                   /* skip forward on next submit_source_data */
   52 
   53     /* Internal; hint to rcksum_submit_source_data that it should try matching
   54      * the following block of input data against the block ->next_match.
   55      * next_known is a cached lookup of the id of the next block after that
   56      * that we already have data for. */
   57     const struct hash_entry *next_match;
   58     zs_blockid next_known;
   59 
   60     /* Hash table for rsync algorithm */
   61     unsigned int hashmask;
   62     struct hash_entry *blockhashes;
   63     struct hash_entry **rsum_hash;
   64 
   65     /* And a 1-bit per rsum value table to allow fast negative lookups for hash
   66      * values that don't occur in the target file. */
   67     unsigned int bithashmask;
   68     unsigned char *bithash;
   69 
   70     /* Current state and stats for data collected by algorithm */
   71     int numranges;
   72     zs_blockid *ranges;
   73     int gotblocks;
   74     struct {
   75         int hashhit, weakhit, stronghit, checksummed;
   76     } stats;
   77 
   78     /* Temp file for output */
   79     char *filename;
   80     int fd;
   81 };
   82 
   83 #define BITHASHBITS 3
   84 
   85 /* rcksum_state methods */
   86 
   87 /* From a hash entry, return the corresponding blockid */
   88 static inline zs_blockid get_HE_blockid(const struct rcksum_state *z,
   89                                         const struct hash_entry *e) {
   90     return e - z->blockhashes;
   91 }
   92 
   93 void add_to_ranges(struct rcksum_state *z, zs_blockid n);
   94 int already_got_block(struct rcksum_state *z, zs_blockid n);
   95 zs_blockid next_known_block(struct rcksum_state *rs, zs_blockid x);
   96 
   97 struct hash_entry *calc_hash_entry(void *data, size_t len);
   98 
   99 /* Hash the checksum values for the given hash entry and return the hash value */
  100 static inline unsigned calc_rhash(const struct rcksum_state *const z,
  101                                   const struct hash_entry *const e) {
  102     unsigned h = e[0].r.b;
  103 
  104     h ^= ((z->seq_matches > 1) ? e[1].r.b
  105         : e[0].r.a & z->rsum_a_mask) << BITHASHBITS;
  106 
  107     return h;
  108 }
  109 
  110 int build_hash(struct rcksum_state *z);
  111 void remove_block_from_hash(struct rcksum_state *z, zs_blockid id);