vendor/adler32/src/lib.rs

   1 //! A minimal implementation of Adler32 for Rust.
   2 //!
   3 //! This provides the simple method adler32(), that exhausts a Read and
   4 //! computes the Adler32 hash, as well as the RollingAdler32 struct, that can
   5 //! build a hash byte-by-byte, allowing to 'forget' past bytes in a rolling
   6 //! fashion.
   7 //!
   8 //! The adler32 code has been translated (as accurately as I could manage) from
   9 //! the zlib implementation.
  10
  11 #![forbid(unsafe_code)]
  12 #![no_std]
  13
  14 #[cfg(feature = "std")]
  15 extern crate std;
  16
  17 #[cfg(test)]
  18 extern crate rand;
  19
  20 // adler32 algorithm and implementation taken from zlib; http://www.zlib.net/
  21 // It was translated into Rust as accurately as I could manage
  22 // The (slow) reference was taken from Wikipedia; https://en.wikipedia.org/
  23
  24 /* zlib.h -- interface of the 'zlib' general purpose compression library
  25   version 1.2.8, April 28th, 2013
  26
  27   Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
  28
  29   This software is provided 'as-is', without any express or implied
  30   warranty.  In no event will the authors be held liable for any damages
  31   arising from the use of this software.
  32
  33   Permission is granted to anyone to use this software for any purpose,
  34   including commercial applications, and to alter it and redistribute it
  35   freely, subject to the following restrictions:
  36
  37   1. The origin of this software must not be misrepresented; you must not
  38      claim that you wrote the original software. If you use this software
  39      in a product, an acknowledgment in the product documentation would be
  40      appreciated but is not required.
  41   2. Altered source versions must be plainly marked as such, and must not be
  42      misrepresented as being the original software.
  43   3. This notice may not be removed or altered from any source distribution.
  44
  45   Jean-loup Gailly        Mark Adler
  46   jloup@gzip.org          madler@alumni.caltech.edu
  47
  48 */
  49
  50 // largest prime smaller than 65536
  51 const BASE: u32 = 65521;
  52
  53 // NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1
  54 const NMAX: usize = 5552;
  55
  56 #[inline(always)]
  57 fn do1(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
  58     *adler += u32::from(buf[0]);
  59     *sum2 += *adler;
  60 }
  61
  62 #[inline(always)]
  63 fn do2(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
  64     do1(adler, sum2, &buf[0..1]);
  65     do1(adler, sum2, &buf[1..2]);
  66 }
  67
  68 #[inline(always)]
  69 fn do4(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
  70     do2(adler, sum2, &buf[0..2]);
  71     do2(adler, sum2, &buf[2..4]);
  72 }
  73
  74 #[inline(always)]
  75 fn do8(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
  76     do4(adler, sum2, &buf[0..4]);
  77     do4(adler, sum2, &buf[4..8]);
  78 }
  79
  80 #[inline(always)]
  81 fn do16(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
  82     do8(adler, sum2, &buf[0..8]);
  83     do8(adler, sum2, &buf[8..16]);
  84 }
  85
  86 /// A rolling version of the Adler32 hash, which can 'forget' past bytes.
  87 ///
  88 /// Calling remove() will update the hash to the value it would have if that
  89 /// past byte had never been fed to the algorithm. This allows you to get the
  90 /// hash of a rolling window very efficiently.
  91 #[derive(Clone)]
  92 pub struct RollingAdler32 {
  93     a: u32,
  94     b: u32,
  95 }
  96
  97 impl Default for RollingAdler32 {
  98     fn default() -> RollingAdler32 {
  99         RollingAdler32::new()
 100     }
 101 }
 102
 103 impl RollingAdler32 {
 104     /// Creates an empty Adler32 context (with hash 1).
 105     pub fn new() -> RollingAdler32 {
 106         Self::from_value(1)
 107     }
 108
 109     /// Creates an Adler32 context with the given initial value.
 110     pub fn from_value(adler32: u32) -> RollingAdler32 {
 111         let a = adler32 & 0xFFFF;
 112         let b = adler32 >> 16;
 113         RollingAdler32 { a, b }
 114     }
 115
 116     /// Convenience function initializing a context from the hash of a buffer.
 117     pub fn from_buffer(buffer: &[u8]) -> RollingAdler32 {
 118         let mut hash = RollingAdler32::new();
 119         hash.update_buffer(buffer);
 120         hash
 121     }
 122
 123     /// Returns the current hash.
 124     pub fn hash(&self) -> u32 {
 125         (self.b << 16) | self.a
 126     }
 127
 128     /// Removes the given `byte` that was fed to the algorithm `size` bytes ago.
 129     pub fn remove(&mut self, size: usize, byte: u8) {
 130         let byte = u32::from(byte);
 131         self.a = (self.a + BASE - byte) % BASE;
 132         self.b = ((self.b + BASE - 1)
 133             .wrapping_add(BASE.wrapping_sub(size as u32).wrapping_mul(byte)))
 134             % BASE;
 135     }
 136
 137     /// Feeds a new `byte` to the algorithm to update the hash.
 138     pub fn update(&mut self, byte: u8) {
 139         let byte = u32::from(byte);
 140         self.a = (self.a + byte) % BASE;
 141         self.b = (self.b + self.a) % BASE;
 142     }
 143
 144     /// Feeds a vector of bytes to the algorithm to update the hash.
 145     pub fn update_buffer(&mut self, buffer: &[u8]) {
 146         let len = buffer.len();
 147
 148         // in case user likes doing a byte at a time, keep it fast
 149         if len == 1 {
 150             self.update(buffer[0]);
 151             return;
 152         }
 153
 154         // in case short lengths are provided, keep it somewhat fast
 155         if len < 16 {
 156             for byte in buffer.iter().take(len) {
 157                 self.a += u32::from(*byte);
 158                 self.b += self.a;
 159             }
 160             if self.a >= BASE {
 161                 self.a -= BASE;
 162             }
 163             self.b %= BASE;
 164             return;
 165         }
 166
 167         let mut pos = 0;
 168
 169         // do length NMAX blocks -- requires just one modulo operation;
 170         while pos + NMAX <= len {
 171             let end = pos + NMAX;
 172             while pos < end {
 173                 // 16 sums unrolled
 174                 do16(&mut self.a, &mut self.b, &buffer[pos..pos + 16]);
 175                 pos += 16;
 176             }
 177             self.a %= BASE;
 178             self.b %= BASE;
 179         }
 180
 181         // do remaining bytes (less than NMAX, still just one modulo)
 182         if pos < len {
 183             // avoid modulos if none remaining
 184             while len - pos >= 16 {
 185                 do16(&mut self.a, &mut self.b, &buffer[pos..pos + 16]);
 186                 pos += 16;
 187             }
 188             while len - pos > 0 {
 189                 self.a += u32::from(buffer[pos]);
 190                 self.b += self.a;
 191                 pos += 1;
 192             }
 193             self.a %= BASE;
 194             self.b %= BASE;
 195         }
 196     }
 197 }
 198
 199 /// Consume a Read object and returns the Adler32 hash.
 200 #[cfg(feature = "std")]
 201 pub fn adler32<R: std::io::Read>(mut reader: R) -> std::io::Result<u32> {
 202     let mut hash = RollingAdler32::new();
 203     let mut buffer = [0u8; NMAX];
 204     let mut read = reader.read(&mut buffer)?;
 205     while read > 0 {
 206         hash.update_buffer(&buffer[..read]);
 207         read = reader.read(&mut buffer)?;
 208     }
 209     Ok(hash.hash())
 210 }
 211
 212 #[cfg(test)]
 213 mod test {
 214     use rand::Rng;
 215     use std::io;
 216     use std::prelude::v1::*;
 217     use std::vec;
 218
 219     use super::{adler32, RollingAdler32, BASE};
 220
 221     fn adler32_slow<R: io::Read>(reader: R) -> io::Result<u32> {
 222         let mut a: u32 = 1;
 223         let mut b: u32 = 0;
 224
 225         for byte in reader.bytes() {
 226             let byte = byte? as u32;
 227             a = (a + byte) % BASE;
 228             b = (b + a) % BASE;
 229         }
 230
 231         Ok((b << 16) | a)
 232     }
 233
 234     #[test]
 235     fn testvectors() {
 236         fn do_test(v: u32, bytes: &[u8]) {
 237             let mut hash = RollingAdler32::new();
 238             hash.update_buffer(&bytes);
 239             assert_eq!(hash.hash(), v);
 240
 241             let r = io::Cursor::new(bytes);
 242             assert_eq!(adler32(r).unwrap(), v);
 243         }
 244         do_test(0x00000001, b"");
 245         do_test(0x00620062, b"a");
 246         do_test(0x024d0127, b"abc");
 247         do_test(0x29750586, b"message digest");
 248         do_test(0x90860b20, b"abcdefghijklmnopqrstuvwxyz");
 249         do_test(
 250             0x8adb150c,
 251             b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
 252                               abcdefghijklmnopqrstuvwxyz\
 253                               0123456789",
 254         );
 255         do_test(
 256             0x97b61069,
 257             b"1234567890123456789012345678901234567890\
 258                               1234567890123456789012345678901234567890",
 259         );
 260         do_test(0xD6251498, &[255; 64000]);
 261     }
 262
 263     #[test]
 264     fn compare() {
 265         let mut rng = rand::thread_rng();
 266         let mut data = vec![0u8; 5589];
 267         for size in [
 268             0, 1, 3, 4, 5, 31, 32, 33, 67, 5550, 5552, 5553, 5568, 5584, 5589,
 269         ]
 270         .iter()
 271         .cloned()
 272         {
 273             rng.fill_bytes(&mut data[..size]);
 274             let r1 = io::Cursor::new(&data[..size]);
 275             let r2 = r1.clone();
 276             if adler32_slow(r1).unwrap() != adler32(r2).unwrap() {
 277                 panic!("Comparison failed, size={}", size);
 278             }
 279         }
 280     }
 281
 282     #[test]
 283     fn rolling() {
 284         assert_eq!(RollingAdler32::from_value(0x01020304).hash(), 0x01020304);
 285
 286         fn do_test(a: &[u8], b: &[u8]) {
 287             let mut total = Vec::with_capacity(a.len() + b.len());
 288             total.extend(a);
 289             total.extend(b);
 290             let mut h = RollingAdler32::from_buffer(&total[..(b.len())]);
 291             for i in 0..(a.len()) {
 292                 h.remove(b.len(), a[i]);
 293                 h.update(total[b.len() + i]);
 294             }
 295             assert_eq!(h.hash(), adler32(b).unwrap());
 296         }
 297         do_test(b"a", b"b");
 298         do_test(b"", b"this a test");
 299         do_test(b"th", b"is a test");
 300         do_test(b"this a ", b"test");
 301     }
 302
 303     #[test]
 304     fn long_window_remove() {
 305         let mut hash = RollingAdler32::new();
 306         let w = 65536;
 307         assert!(w as u32 > BASE);
 308
 309         let mut bytes = vec![0; w * 3];
 310         for (i, b) in bytes.iter_mut().enumerate() {
 311             *b = i as u8;
 312         }
 313
 314         for (i, b) in bytes.iter().enumerate() {
 315             if i >= w {
 316                 hash.remove(w, bytes[i - w]);
 317             }
 318             hash.update(*b);
 319             if i > 0 && i % w == 0 {
 320                 assert_eq!(hash.hash(), 0x433a8772);
 321             }
 322         }
 323         assert_eq!(hash.hash(), 0xbbba8772);
 324     }
 325 }