tech_report/node3.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>Rolling checksum</TITLE>
  10 <META NAME="description" CONTENT="Rolling checksum">
  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="node4.html">
  17 <LINK REL="previous" HREF="node2.html">
  18 <LINK REL="up" HREF="tech_report.html">
  19 <LINK REL="next" HREF="node4.html">
  20 </HEAD>
  21 <BODY >
  22 <!--Navigation Panel-->
  23 <A NAME="tex2html42"
  24  HREF="node4.html">
  25 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
  26  SRC="/usr/local/src/latex2html/icons.gif/next_motif.gif"></A>
  27 <A NAME="tex2html40"
  28  HREF="tech_report.html">
  29 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
  30  SRC="/usr/local/src/latex2html/icons.gif/up_motif.gif"></A>
  31 <A NAME="tex2html34"
  32  HREF="node2.html">
  33 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
  34  SRC="/usr/local/src/latex2html/icons.gif/previous_motif.gif"></A>
  35 <BR>
  36 <B> Next:</B> <A NAME="tex2html43"
  37  HREF="node4.html">Checksum searching</A>
  38 <B> Up:</B> <A NAME="tex2html41"
  39  HREF="tech_report.html">The rsync algorithm</A>
  40 <B> Previous:</B> <A NAME="tex2html35"
  41  HREF="node2.html">The rsync algorithm</A>
  42 <BR>
  43 <BR>
  44 <!--End of Navigation Panel-->
  45
  46 <H1><A NAME="SECTION00030000000000000000">
  47 Rolling checksum</A>
  48 </H1>
  49
  50 <P>
  51 The weak rolling checksum used in the rsync algorithm needs to have
  52 the property that it is very cheap to calculate the checksum of a
  53 buffer
  54 <!-- MATH: $X_2 .. X_{n+1}$ -->
  55 <I>X</I><SUB>2</SUB> .. <I>X</I><SUB><I>n</I>+1</SUB> given the checksum of buffer
  56 <!-- MATH: $X_1 .. X_n$ -->
  57 <I>X</I><SUB>1</SUB> .. <I>X</I><SUB><I>n</I></SUB> and
  58 the values of the bytes <I>X</I><SUB>1</SUB> and <I>X</I><SUB><I>n</I>+1</SUB>.
  59
  60 <P>
  61 The weak checksum algorithm we used in our implementation was inspired
  62 by Mark Adler's adler-32 checksum.  Our checksum is defined by
  63 <BR><P></P>
  64 <DIV ALIGN="CENTER">
  65 <!-- MATH: \begin{displaymath}
  66 a(k,l) = (\sum_{i=k}^l X_i) \bmod M
  67 \end{displaymath} -->
  68
  69
  70 <IMG
  71  WIDTH="176" HEIGHT="56"
  72  SRC="img3.gif"
  73  ALT="\begin{displaymath}a(k,l) = (\sum_{i=k}^l X_i) \bmod M \end{displaymath}">
  74 </DIV>
  75 <BR CLEAR="ALL">
  76 <P></P>
  77 <BR><P></P>
  78 <DIV ALIGN="CENTER">
  79 <!-- MATH: \begin{displaymath}
  80 b(k,l) = (\sum_{i=k}^l (l-i+1)X_i) \bmod M
  81 \end{displaymath} -->
  82
  83
  84 <IMG
  85  WIDTH="240" HEIGHT="56"
  86  SRC="img4.gif"
  87  ALT="\begin{displaymath}b(k,l) = (\sum_{i=k}^l (l-i+1)X_i) \bmod M \end{displaymath}">
  88 </DIV>
  89 <BR CLEAR="ALL">
  90 <P></P>
  91 <BR><P></P>
  92 <DIV ALIGN="CENTER">
  93 <!-- MATH: \begin{displaymath}
  94 s(k,l) = a(k,l) + 2^{16} b(k,l)
  95 \end{displaymath} -->
  96
  97
  98 <I>s</I>(<I>k</I>,<I>l</I>) = <I>a</I>(<I>k</I>,<I>l</I>) + 2<SUP>16</SUP> <I>b</I>(<I>k</I>,<I>l</I>)
  99 </DIV>
 100 <BR CLEAR="ALL">
 101 <P></P>
 102 <P>
 103 where <I>s</I>(<I>k</I>,<I>l</I>) is the rolling checksum of the bytes
 104 <!-- MATH: $X_k \ldots X_l$ -->
 105 <IMG
 106  WIDTH="67" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
 107  SRC="img5.gif"
 108  ALT="$X_k \ldots X_l$">.
 109 For simplicity and speed, we use
 110 <!-- MATH: $M = 2^{16}$ -->
 111 <I>M</I> = 2<SUP>16</SUP>.
 112
 113 <P>
 114 The important property of this checksum is that successive values can
 115 be computed very efficiently using the recurrence relations
 116
 117 <P>
 118 <BR><P></P>
 119 <DIV ALIGN="CENTER">
 120 <!-- MATH: \begin{displaymath}
 121 a(k+1,l+1) = (a(k,l) - X_k + X_{l+1}) \bmod M
 122 \end{displaymath} -->
 123
 124
 125 <IMG
 126  WIDTH="322" HEIGHT="28"
 127  SRC="img6.gif"
 128  ALT="\begin{displaymath}a(k+1,l+1) = (a(k,l) - X_k + X_{l+1}) \bmod M \end{displaymath}">
 129 </DIV>
 130 <BR CLEAR="ALL">
 131 <P></P>
 132 <BR><P></P>
 133 <DIV ALIGN="CENTER">
 134 <!-- MATH: \begin{displaymath}
 135 b(k+1,l+1) = (b(k,l) - (l-k+1) X_k + a(k+1,l+1)) \bmod M
 136 \end{displaymath} -->
 137
 138
 139 <IMG
 140  WIDTH="454" HEIGHT="28"
 141  SRC="img7.gif"
 142  ALT="\begin{displaymath}b(k+1,l+1) = (b(k,l) - (l-k+1) X_k + a(k+1,l+1)) \bmod M \end{displaymath}">
 143 </DIV>
 144 <BR CLEAR="ALL">
 145 <P></P>
 146 <P>
 147 Thus the checksum can be calculated for blocks of length S at all
 148 possible offsets within a file in a ``rolling'' fashion, with very
 149 little computation at each point.
 150
 151 <P>
 152 Despite its simplicity, this checksum was found to be quite adequate as
 153 a first level check for a match of two file blocks.  We have found in
 154 practice that the probability of this checksum matching when the
 155 blocks are not equal is quite low.  This is important because the much
 156 more expensive strong checksum must be calculated for each block where
 157 the weak checksum matches.
 158
 159 <P>
 160 <HR>
 161 <!--Navigation Panel-->
 162 <A NAME="tex2html42"
 163  HREF="node4.html">
 164 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
 165  SRC="/usr/local/src/latex2html/icons.gif/next_motif.gif"></A>
 166 <A NAME="tex2html40"
 167  HREF="tech_report.html">
 168 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
 169  SRC="/usr/local/src/latex2html/icons.gif/up_motif.gif"></A>
 170 <A NAME="tex2html34"
 171  HREF="node2.html">
 172 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
 173  SRC="/usr/local/src/latex2html/icons.gif/previous_motif.gif"></A>
 174 <BR>
 175 <B> Next:</B> <A NAME="tex2html43"
 176  HREF="node4.html">Checksum searching</A>
 177 <B> Up:</B> <A NAME="tex2html41"
 178  HREF="tech_report.html">The rsync algorithm</A>
 179 <B> Previous:</B> <A NAME="tex2html35"
 180  HREF="node2.html">The rsync algorithm</A>
 181 <!--End of Navigation Panel-->
 182 <ADDRESS>
 183 <I>Andrew Tridgell</I>
 184 <BR><I>1998-11-09</I>
 185 </ADDRESS>
 186 </BODY>
 187 </HTML>