irc/TechBot/Compression/Checksums/Adler32.cs

   1 // Adler32.cs - Computes Adler32 data checksum of a data stream
   2 // Copyright (C) 2001 Mike Krueger
   3 //
   4 // This file was translated from java, it was part of the GNU Classpath
   5 // Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
   6 //
   7 // This program is free software; you can redistribute it and/or
   8 // modify it under the terms of the GNU General Public License
   9 // as published by the Free Software Foundation; either version 2
  10 // of the License, or (at your option) any later version.
  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 // GNU General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU General Public License
  18 // along with this program; if not, write to the Free Software
  19 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  20 //
  21 // Linking this library statically or dynamically with other modules is
  22 // making a combined work based on this library.  Thus, the terms and
  23 // conditions of the GNU General Public License cover the whole
  24 // combination.
  25 //
  26 // As a special exception, the copyright holders of this library give you
  27 // permission to link this library with independent modules to produce an
  28 // executable, regardless of the license terms of these independent
  29 // modules, and to copy and distribute the resulting executable under
  30 // terms of your choice, provided that you also meet, for each linked
  31 // independent module, the terms and conditions of the license of that
  32 // module.  An independent module is a module which is not derived from
  33 // or based on this library.  If you modify this library, you may extend
  34 // this exception to your version of the library, but you are not
  35 // obligated to do so.  If you do not wish to do so, delete this
  36 // exception statement from your version.
  37
  38 using System;
  39
  40 namespace ICSharpCode.SharpZipLib.Checksums
  41 {
  42
  43         /// <summary>
  44         /// Computes Adler32 checksum for a stream of data. An Adler32
  45         /// checksum is not as reliable as a CRC32 checksum, but a lot faster to
  46         /// compute.
  47         ///
  48         /// The specification for Adler32 may be found in RFC 1950.
  49         /// ZLIB Compressed Data Format Specification version 3.3)
  50         ///
  51         ///
  52         /// From that document:
  53         ///
  54         ///      "ADLER32 (Adler-32 checksum)
  55         ///       This contains a checksum value of the uncompressed data
  56         ///       (excluding any dictionary data) computed according to Adler-32
  57         ///       algorithm. This algorithm is a 32-bit extension and improvement
  58         ///       of the Fletcher algorithm, used in the ITU-T X.224 / ISO 8073
  59         ///       standard.
  60         ///
  61         ///       Adler-32 is composed of two sums accumulated per byte: s1 is
  62         ///       the sum of all bytes, s2 is the sum of all s1 values. Both sums
  63         ///       are done modulo 65521. s1 is initialized to 1, s2 to zero.  The
  64         ///       Adler-32 checksum is stored as s2*65536 + s1 in most-
  65         ///       significant-byte first (network) order."
  66         ///
  67         ///  "8.2. The Adler-32 algorithm
  68         ///
  69         ///    The Adler-32 algorithm is much faster than the CRC32 algorithm yet
  70         ///    still provides an extremely low probability of undetected errors.
  71         ///
  72         ///    The modulo on unsigned long accumulators can be delayed for 5552
  73         ///    bytes, so the modulo operation time is negligible.  If the bytes
  74         ///    are a, b, c, the second sum is 3a + 2b + c + 3, and so is position
  75         ///    and order sensitive, unlike the first sum, which is just a
  76         ///    checksum.  That 65521 is prime is important to avoid a possible
  77         ///    large class of two-byte errors that leave the check unchanged.
  78         ///    (The Fletcher checksum uses 255, which is not prime and which also
  79         ///    makes the Fletcher check insensitive to single byte changes 0 -
  80         ///    255.)
  81         ///
  82         ///    The sum s1 is initialized to 1 instead of zero to make the length
  83         ///    of the sequence part of s2, so that the length does not have to be
  84         ///    checked separately. (Any sequence of zeroes has a Fletcher
  85         ///    checksum of zero.)"
  86         /// </summary>
  87         /// <see cref="ICSharpCode.SharpZipLib.Zip.Compression.Streams.InflaterInputStream"/>
  88         /// <see cref="ICSharpCode.SharpZipLib.Zip.Compression.Streams.DeflaterOutputStream"/>
  89         public sealed class Adler32 : IChecksum
  90         {
  91                 /// <summary>
  92                 /// largest prime smaller than 65536
  93                 /// </summary>
  94                 readonly static uint BASE = 65521;
  95
  96                 uint checksum;
  97
  98                 /// <summary>
  99                 /// Returns the Adler32 data checksum computed so far.
 100                 /// </summary>
 101                 public long Value {
 102                         get {
 103                                 return checksum;
 104                         }
 105                 }
 106
 107                 /// <summary>
 108                 /// Creates a new instance of the <code>Adler32</code> class.
 109                 /// The checksum starts off with a value of 1.
 110                 /// </summary>
 111                 public Adler32()
 112                 {
 113                         Reset();
 114                 }
 115
 116                 /// <summary>
 117                 /// Resets the Adler32 checksum to the initial value.
 118                 /// </summary>
 119                 public void Reset()
 120                 {
 121                         checksum = 1; //Initialize to 1
 122                 }
 123
 124                 /// <summary>
 125                 /// Updates the checksum with the byte b.
 126                 /// </summary>
 127                 /// <param name="bval">
 128                 /// the data value to add. The high byte of the int is ignored.
 129                 /// </param>
 130                 public void Update(int bval)
 131                 {
 132                         //We could make a length 1 byte array and call update again, but I
 133                         //would rather not have that overhead
 134                         uint s1 = checksum & 0xFFFF;
 135                         uint s2 = checksum >> 16;
 136
 137                         s1 = (s1 + ((uint)bval & 0xFF)) % BASE;
 138                         s2 = (s1 + s2) % BASE;
 139
 140                         checksum = (s2 << 16) + s1;
 141                 }
 142
 143                 /// <summary>
 144                 /// Updates the checksum with the bytes taken from the array.
 145                 /// </summary>
 146                 /// <param name="buffer">
 147                 /// buffer an array of bytes
 148                 /// </param>
 149                 public void Update(byte[] buffer)
 150                 {
 151                         Update(buffer, 0, buffer.Length);
 152                 }
 153
 154                 /// <summary>
 155                 /// Updates the checksum with the bytes taken from the array.
 156                 /// </summary>
 157                 /// <param name="buf">
 158                 /// an array of bytes
 159                 /// </param>
 160                 /// <param name="off">
 161                 /// the start of the data used for this update
 162                 /// </param>
 163                 /// <param name="len">
 164                 /// the number of bytes to use for this update
 165                 /// </param>
 166                 public void Update(byte[] buf, int off, int len)
 167                 {
 168                         if (buf == null) {
 169                                 throw new ArgumentNullException("buf");
 170                         }
 171
 172                         if (off < 0 || len < 0 || off + len > buf.Length) {
 173                                 throw new ArgumentOutOfRangeException();
 174                         }
 175
 176                         //(By Per Bothner)
 177                         uint s1 = checksum & 0xFFFF;
 178                         uint s2 = checksum >> 16;
 179
 180                         while (len > 0) {
 181                                 // We can defer the modulo operation:
 182                                 // s1 maximally grows from 65521 to 65521 + 255 * 3800
 183                                 // s2 maximally grows by 3800 * median(s1) = 2090079800 < 2^31
 184                                 int n = 3800;
 185                                 if (n > len) {
 186                                         n = len;
 187                                 }
 188                                 len -= n;
 189                                 while (--n >= 0) {
 190                                         s1 = s1 + (uint)(buf[off++] & 0xFF);
 191                                         s2 = s2 + s1;
 192                                 }
 193                                 s1 %= BASE;
 194                                 s2 %= BASE;
 195                         }
 196
 197                         checksum = (s2 << 16) | s1;
 198                 }
 199         }
 200 }