tech_report/node4.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
   2 <!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
   3 originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
   4 * revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
   5 * with significant contributions from:
   6   Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
   7 <HTML>
   8 <HEAD>
   9 <TITLE>Checksum searching</TITLE>
  10 <META NAME="description" CONTENT="Checksum searching">
  11 <META NAME="keywords" CONTENT="tech_report">
  12 <META NAME="resource-type" CONTENT="document">
  13 <META NAME="distribution" CONTENT="global">
  14 <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
  15 <LINK REL="STYLESHEET" HREF="tech_report.css">
  16 <LINK REL="next" HREF="node5.html">
  17 <LINK REL="previous" HREF="node3.html">
  18 <LINK REL="up" HREF="tech_report.html">
  19 <LINK REL="next" HREF="node5.html">
  20 </HEAD>
  21 <BODY >
  22 <!--Navigation Panel-->
  23 <A NAME="tex2html52"
  24  HREF="node5.html">
  25 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
  26  SRC="next.gif"></A>
  27 <A NAME="tex2html50"
  28  HREF="tech_report.html">
  29 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
  30  SRC="up.gif"></A>
  31 <A NAME="tex2html44"
  32  HREF="node3.html">
  33 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
  34  SRC="previous.gif"></A>
  35 <BR>
  36 <B> Next:</B> <A NAME="tex2html53"
  37  HREF="node5.html">Pipelining</A>
  38 <B> Up:</B> <A NAME="tex2html51"
  39  HREF="tech_report.html">The rsync algorithm</A>
  40 <B> Previous:</B> <A NAME="tex2html45"
  41  HREF="node3.html">Rolling checksum</A>
  42 <BR>
  43 <BR>
  44 <!--End of Navigation Panel-->
  45
  46 <H1><A NAME="SECTION00040000000000000000">
  47 Checksum searching</A>
  48 </H1>
  49
  50 <P>
  51 Once <IMG
  52  WIDTH="15" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
  53  SRC="img1.gif"
  54  ALT="$\alpha$">
  55 has received the list of checksums of the blocks of <I>B</I>,
  56 it must search <I>A</I> for any blocks at any offset that match the
  57 checksum of some block of <I>B</I>.  The basic strategy is to compute the
  58 32-bit rolling checksum for a block of length <I>S</I> starting at each
  59 byte of <I>A</I> in turn, and for each checksum, search the list for a
  60 match.  To do this our implementation uses a
  61 simple 3 level searching scheme.
  62
  63 <P>
  64 The first level uses a 16-bit hash of the 32-bit rolling checksum and
  65 a 2<SUP>16</SUP> entry hash table.  The list of checksum values (i.e., the
  66 checksums from the blocks of <I>B</I>) is sorted according to the 16-bit
  67 hash of the 32-bit rolling checksum.  Each entry in the hash table
  68 points to the first element of the list for that hash value, or
  69 contains a null value if no element of the list has that hash value.
  70
  71 <P>
  72 At each offset in the file the 32-bit rolling checksum and its 16-bit
  73 hash are calculated.  If the hash table entry for that hash value is
  74 not a null value, the second level check is invoked.
  75
  76 <P>
  77 The second level check involves scanning the sorted checksum list
  78 starting with the entry pointed to by the hash table entry, looking
  79 for an entry whose 32-bit rolling checksum matches the current value.
  80 The scan terminates when it reaches an entry whose 16-bit hash
  81 differs.  If this search finds a match, the third level check is
  82 invoked.
  83
  84 <P>
  85 The third level check involves calculating the strong checksum for the
  86 current offset in the file and comparing it with the strong checksum
  87 value in the current list entry.  If the two strong checksums match,
  88 we assume that we have found a block of <I>A</I> which matches a block of
  89 <I>B</I>.  In fact the blocks could be different, but the probability of
  90 this is microscopic, and in practice this is a reasonable assumption.
  91
  92 <P>
  93 When a match is found, <IMG
  94  WIDTH="15" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
  95  SRC="img1.gif"
  96  ALT="$\alpha$">
  97 sends <IMG
  98  WIDTH="14" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
  99  SRC="img2.gif"
 100  ALT="$\beta$">
 101 the data in <I>A</I> between
 102 the current file offset and the end of the previous match, followed by
 103 the index of the block in <I>B</I> that matched.  This data is sent
 104 immediately a match is found, which allows us to overlap the
 105 communication with further computation.
 106
 107 <P>
 108 If no match is found at a given offset in the file, the rolling
 109 checksum is updated to the next offset and the search proceeds.  If a
 110 match is found, the search is restarted at the end of the matched
 111 block.  This strategy saves a considerable amount of computation for
 112 the common case where the two files are nearly identical.  In
 113 addition, it would be a simple matter to encode the block indexes as
 114 runs, for the common case where a portion of <I>A</I> matches a series of
 115 blocks of <I>B</I> in order.
 116
 117 <P>
 118 <HR>
 119 <!--Navigation Panel-->
 120 <A NAME="tex2html52"
 121  HREF="node5.html">
 122 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
 123  SRC="next.gif"></A>
 124 <A NAME="tex2html50"
 125  HREF="tech_report.html">
 126 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
 127  SRC="up.gif"></A>
 128 <A NAME="tex2html44"
 129  HREF="node3.html">
 130 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
 131  SRC="previous.gif"></A>
 132 <BR>
 133 <B> Next:</B> <A NAME="tex2html53"
 134  HREF="node5.html">Pipelining</A>
 135 <B> Up:</B> <A NAME="tex2html51"
 136  HREF="tech_report.html">The rsync algorithm</A>
 137 <B> Previous:</B> <A NAME="tex2html45"
 138  HREF="node3.html">Rolling checksum</A>
 139 <!--End of Navigation Panel-->
 140 <ADDRESS>
 141 <I>Andrew Tridgell</I>
 142 <BR><I>1998-11-09</I>
 143 </ADDRESS>
 144 </BODY>
 145 </HTML>