Adding upstream version 86.0.1.upstream/86.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

6 files changed, 400 insertions, 0 deletions

diff --git a/third_party/rust/adler32/.cargo-checksum.json b/third_party/rust/adler32/.cargo-checksum.json
new file mode 100644
index 0000000000..2a14a2cb31
--- /dev/null
+++ b/third_party/rust/adler32/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"3dfd0367a0af86dd57c4faf9f8a5b1ce8179c38e28d470d3c46ce2d2b45ef20f","LICENSE":"9efeecf73f68ed91830f71c69a53de1328d1f8c6968a68ca6e6b2d6f3a92a088","README.md":"77c9e2080e5ae700403343c27fe08bb616f1df92a8b42b0e7808a7b7d32eb7a2","appveyor.yml":"4873092bae0713890497e5ceae761af359d680e6cce5ce003bf38bc5c45cde44","src/lib.rs":"596ac0c2bbdfa759fb79eb7b7d9e18d6c51be0849f22204a85c4906fe2ae8bde"},"package":"5d2e7343e7fc9de883d1b0341e0b13970f764c14101234857d2ddafa1cb1cac2"}
\ No newline at end of file
diff --git a/third_party/rust/adler32/Cargo.toml b/third_party/rust/adler32/Cargo.toml
new file mode 100644
index 0000000000..39b77ce372
--- /dev/null
+++ b/third_party/rust/adler32/Cargo.toml
@@ -0,0 +1,24 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies
+#
+# If you believe there's an error in this file please file an
+# issue against the rust-lang/cargo repository. If you're
+# editing this file be aware that the upstream Cargo.toml
+# will likely look very different (and much more reasonable)
+
+[package]
+name = "adler32"
+version = "1.0.4"
+authors = ["Remi Rampin <remirampin@gmail.com>"]
+description = "Minimal Adler32 implementation for Rust."
+documentation = "https://remram44.github.io/adler32-rs/index.html"
+readme = "README.md"
+keywords = ["adler32", "hash", "rolling"]
+license = "Zlib"
+repository = "https://github.com/remram44/adler32-rs"
+[dev-dependencies.rand]
+version = "0.4"
diff --git a/third_party/rust/adler32/LICENSE b/third_party/rust/adler32/LICENSE
new file mode 100644
index 0000000000..218a84beb9
--- /dev/null
+++ b/third_party/rust/adler32/LICENSE
@@ -0,0 +1,43 @@
+Copyright notice for the Rust port:
+
+ (C) 2016 Remi Rampin
+
+  This software is provided 'as-is', without any express or implied
+  warranty.  In no event will the authors be held liable for any damages
+  arising from the use of this software.
+
+  Permission is granted to anyone to use this software for any purpose,
+  including commercial applications, and to alter it and redistribute it
+  freely, subject to the following restrictions:
+
+  1. The origin of this software must not be misrepresented; you must not
+     claim that you wrote the original software. If you use this software
+     in a product, an acknowledgment in the product documentation would be
+     appreciated but is not required.
+  2. Altered source versions must be plainly marked as such, and must not be
+     misrepresented as being the original software.
+  3. This notice may not be removed or altered from any source distribution.
+
+
+Copyright notice for the original C code from the zlib project:
+
+ (C) 1995-2017 Jean-loup Gailly and Mark Adler
+
+  This software is provided 'as-is', without any express or implied
+  warranty.  In no event will the authors be held liable for any damages
+  arising from the use of this software.
+
+  Permission is granted to anyone to use this software for any purpose,
+  including commercial applications, and to alter it and redistribute it
+  freely, subject to the following restrictions:
+
+  1. The origin of this software must not be misrepresented; you must not
+     claim that you wrote the original software. If you use this software
+     in a product, an acknowledgment in the product documentation would be
+     appreciated but is not required.
+  2. Altered source versions must be plainly marked as such, and must not be
+     misrepresented as being the original software.
+  3. This notice may not be removed or altered from any source distribution.
+
+  Jean-loup Gailly        Mark Adler
+  jloup@gzip.org          madler@alumni.caltech.edu
diff --git a/third_party/rust/adler32/README.md b/third_party/rust/adler32/README.md
new file mode 100644
index 0000000000..3f96e74a54
--- /dev/null
+++ b/third_party/rust/adler32/README.md
@@ -0,0 +1,13 @@
+[![Build Status](https://travis-ci.org/remram44/adler32-rs.svg?branch=master)](https://travis-ci.org/remram44/adler32-rs/builds)
+[![Win Build](https://ci.appveyor.com/api/projects/status/ekyg20rd6rwrus64/branch/master?svg=true)](https://ci.appveyor.com/project/remram44/adler32-rs)
+[![Crates.io](https://img.shields.io/crates/v/adler32.svg)](https://crates.io/crates/adler32)
+[![Say Thanks!](https://img.shields.io/badge/Say%20Thanks-!-1EAEDB.svg)](https://saythanks.io/to/remram44)
+
+What is this?
+=============
+
+It is an implementation of the [Adler32 rolling hash algorithm](https://en.wikipedia.org/wiki/Adler-32) in the [Rust programming language](https://www.rust-lang.org/).
+
+It is adapted from Jean-Loup Gailly's and Mark Adler's [original implementation in zlib](https://github.com/madler/zlib/blob/2fa463bacfff79181df1a5270fb67cc679a53e71/adler32.c). A copy of the zlib copyright and license can be found in LICENSE-ZLIB.
+
+[Generated documentation](https://remram44.github.io/adler32-rs/index.html)
diff --git a/third_party/rust/adler32/appveyor.yml b/third_party/rust/adler32/appveyor.yml
new file mode 100644
index 0000000000..03f815aa4b
--- /dev/null
+++ b/third_party/rust/adler32/appveyor.yml
@@ -0,0 +1,12 @@
+install:
+  - ps: Start-FileDownload 'https://static.rust-lang.org/dist/rust-nightly-i686-pc-windows-gnu.exe'
+  - rust-nightly-i686-pc-windows-gnu.exe /VERYSILENT /NORESTART /DIR="C:\Program Files (x86)\Rust"
+  - set PATH=%PATH%;C:\Program Files (x86)\Rust\bin
+  - rustc -V
+  - cargo -V
+
+build: false
+
+test_script:
+  - cargo build --verbose
+  - cargo test --verbose
diff --git a/third_party/rust/adler32/src/lib.rs b/third_party/rust/adler32/src/lib.rs
new file mode 100644
index 0000000000..a894857dde
--- /dev/null
+++ b/third_party/rust/adler32/src/lib.rs
@@ -0,0 +1,307 @@
+//! A minimal implementation of Adler32 for Rust.
+//!
+//! This provides the simple method adler32(), that exhausts a Read and
+//! computes the Adler32 hash, as well as the RollingAdler32 struct, that can
+//! build a hash byte-by-byte, allowing to 'forget' past bytes in a rolling
+//! fashion.
+//!
+//! The adler32 code has been translated (as accurately as I could manage) from
+//! the zlib implementation.
+
+#[cfg(test)]
+extern crate rand;
+
+use std::io;
+
+// adler32 algorithm and implementation taken from zlib; http://www.zlib.net/
+// It was translated into Rust as accurately as I could manage
+// The (slow) reference was taken from Wikipedia; https://en.wikipedia.org/
+
+/* zlib.h -- interface of the 'zlib' general purpose compression library
+  version 1.2.8, April 28th, 2013
+
+  Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
+
+  This software is provided 'as-is', without any express or implied
+  warranty.  In no event will the authors be held liable for any damages
+  arising from the use of this software.
+
+  Permission is granted to anyone to use this software for any purpose,
+  including commercial applications, and to alter it and redistribute it
+  freely, subject to the following restrictions:
+
+  1. The origin of this software must not be misrepresented; you must not
+     claim that you wrote the original software. If you use this software
+     in a product, an acknowledgment in the product documentation would be
+     appreciated but is not required.
+  2. Altered source versions must be plainly marked as such, and must not be
+     misrepresented as being the original software.
+  3. This notice may not be removed or altered from any source distribution.
+
+  Jean-loup Gailly        Mark Adler
+  jloup@gzip.org          madler@alumni.caltech.edu
+
+*/
+
+// largest prime smaller than 65536
+const BASE: u32 = 65521;
+
+// NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1
+const NMAX: usize = 5552;
+
+#[inline(always)]
+fn do1(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
+    *adler += u32::from(buf[0]);
+    *sum2 += *adler;
+}
+
+#[inline(always)]
+fn do2(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
+    do1(adler, sum2, &buf[0..1]);
+    do1(adler, sum2, &buf[1..2]);
+}
+
+#[inline(always)]
+fn do4(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
+    do2(adler, sum2, &buf[0..2]);
+    do2(adler, sum2, &buf[2..4]);
+}
+
+#[inline(always)]
+fn do8(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
+    do4(adler, sum2, &buf[0..4]);
+    do4(adler, sum2, &buf[4..8]);
+}
+
+#[inline(always)]
+fn do16(adler: &mut u32, sum2: &mut u32, buf: &[u8]) {
+    do8(adler, sum2, &buf[0..8]);
+    do8(adler, sum2, &buf[8..16]);
+}
+
+/// A rolling version of the Adler32 hash, which can 'forget' past bytes.
+///
+/// Calling remove() will update the hash to the value it would have if that
+/// past byte had never been fed to the algorithm. This allows you to get the
+/// hash of a rolling window very efficiently.
+pub struct RollingAdler32 {
+    a: u32,
+    b: u32,
+}
+
+impl Default for RollingAdler32 {
+    fn default() -> RollingAdler32 {
+        RollingAdler32::new()
+    }
+}
+
+impl RollingAdler32 {
+    /// Creates an empty Adler32 context (with hash 1).
+    pub fn new() -> RollingAdler32 {
+        Self::from_value(1)
+    }
+
+    /// Creates an Adler32 context with the given initial value.
+    pub fn from_value(adler32: u32) -> RollingAdler32 {
+        let a = adler32 & 0xFFFF;
+        let b = adler32 >> 16;
+        RollingAdler32 { a, b }
+    }
+
+    /// Convenience function initializing a context from the hash of a buffer.
+    pub fn from_buffer(buffer: &[u8]) -> RollingAdler32 {
+        let mut hash = RollingAdler32::new();
+        hash.update_buffer(buffer);
+        hash
+    }
+
+    /// Returns the current hash.
+    pub fn hash(&self) -> u32 {
+        (self.b << 16) | self.a
+    }
+
+    /// Removes the given `byte` that was fed to the algorithm `size` bytes ago.
+    pub fn remove(&mut self, size: usize, byte: u8) {
+        let byte = u32::from(byte);
+        self.a = (self.a + BASE - byte) % BASE;
+        self.b = ((self.b + BASE - 1)
+                      .wrapping_add(BASE.wrapping_sub(size as u32)
+                                        .wrapping_mul(byte))) % BASE;
+    }
+
+    /// Feeds a new `byte` to the algorithm to update the hash.
+    pub fn update(&mut self, byte: u8) {
+        let byte = u32::from(byte);
+        self.a = (self.a + byte) % BASE;
+        self.b = (self.b + self.a) % BASE;
+    }
+
+    /// Feeds a vector of bytes to the algorithm to update the hash.
+    pub fn update_buffer(&mut self, buffer: &[u8]) {
+        let len = buffer.len();
+
+        // in case user likes doing a byte at a time, keep it fast
+        if len == 1 {
+            self.update(buffer[0]);
+            return;
+        }
+
+        // in case short lengths are provided, keep it somewhat fast
+        if len < 16 {
+            for byte in buffer.iter().take(len) {
+                self.a += u32::from(*byte);
+                self.b += self.a;
+            }
+            if self.a >= BASE {
+                self.a -= BASE;
+            }
+            self.b %= BASE;
+            return;
+        }
+
+        let mut pos = 0;
+
+        // do length NMAX blocks -- requires just one modulo operation;
+        while pos + NMAX <= len {
+            let end = pos + NMAX;
+            while pos < end {
+                // 16 sums unrolled
+                do16(&mut self.a, &mut self.b, &buffer[pos..pos + 16]);
+                pos += 16;
+            }
+            self.a %= BASE;
+            self.b %= BASE;
+        }
+
+        // do remaining bytes (less than NMAX, still just one modulo)
+        if pos < len { // avoid modulos if none remaining
+            while len - pos >= 16 {
+                do16(&mut self.a, &mut self.b, &buffer[pos..pos + 16]);
+                pos += 16;
+            }
+            while len - pos > 0 {
+                self.a += u32::from(buffer[pos]);
+                self.b += self.a;
+                pos += 1;
+            }
+            self.a %= BASE;
+            self.b %= BASE;
+        }
+    }
+}
+
+/// Consume a Read object and returns the Adler32 hash.
+pub fn adler32<R: io::Read>(mut reader: R) -> io::Result<u32> {
+    let mut hash = RollingAdler32::new();
+    let mut buffer = [0u8; NMAX];
+    let mut read = try!(reader.read(&mut buffer));
+    while read > 0 {
+        hash.update_buffer(&buffer[..read]);
+        read = try!(reader.read(&mut buffer));
+    }
+    Ok(hash.hash())
+}
+
+#[cfg(test)]
+mod test {
+    use rand;
+    use rand::Rng;
+    use std::io;
+
+    use super::{BASE, adler32, RollingAdler32};
+
+    fn adler32_slow<R: io::Read>(reader: R) -> io::Result<u32> {
+        let mut a: u32 = 1;
+        let mut b: u32 = 0;
+
+        for byte in reader.bytes() {
+            let byte = try!(byte) as u32;
+            a = (a + byte) % BASE;
+            b = (b + a) % BASE;
+        }
+
+        Ok((b << 16) | a)
+    }
+
+    #[test]
+    fn testvectors() {
+        fn do_test(v: u32, bytes: &[u8]) {
+            let mut hash = RollingAdler32::new();
+            hash.update_buffer(&bytes);
+            assert_eq!(hash.hash(), v);
+
+            let r = io::Cursor::new(bytes);
+            assert_eq!(adler32(r).unwrap(), v);
+        }
+        do_test(0x00000001, b"");
+        do_test(0x00620062, b"a");
+        do_test(0x024d0127, b"abc");
+        do_test(0x29750586, b"message digest");
+        do_test(0x90860b20, b"abcdefghijklmnopqrstuvwxyz");
+        do_test(0x8adb150c, b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
+                              abcdefghijklmnopqrstuvwxyz\
+                              0123456789");
+        do_test(0x97b61069, b"1234567890123456789012345678901234567890\
+                              1234567890123456789012345678901234567890");
+        do_test(0xD6251498, &[255; 64000]);
+    }
+
+    #[test]
+    fn compare() {
+        let mut rng = rand::thread_rng();
+        let mut data = vec![0u8; 5589];
+        for size in [0, 1, 3, 4, 5, 31, 32, 33, 67,
+                     5550, 5552, 5553, 5568, 5584, 5589].iter().cloned() {
+            rng.fill_bytes(&mut data[..size]);
+            let r1 = io::Cursor::new(&data[..size]);
+            let r2 = r1.clone();
+            if adler32_slow(r1).unwrap() != adler32(r2).unwrap() {
+                panic!("Comparison failed, size={}", size);
+            }
+        }
+    }
+
+    #[test]
+    fn rolling() {
+        assert_eq!(RollingAdler32::from_value(0x01020304).hash(), 0x01020304);
+
+        fn do_test(a: &[u8], b: &[u8]) {
+            let mut total = Vec::with_capacity(a.len() + b.len());
+            total.extend(a);
+            total.extend(b);
+            let mut h = RollingAdler32::from_buffer(&total[..(b.len())]);
+            for i in 0..(a.len()) {
+                h.remove(b.len(), a[i]);
+                h.update(total[b.len() + i]);
+            }
+            assert_eq!(h.hash(), adler32(b).unwrap());
+        }
+        do_test(b"a", b"b");
+        do_test(b"", b"this a test");
+        do_test(b"th", b"is a test");
+        do_test(b"this a ", b"test");
+    }
+
+    #[test]
+    fn long_window_remove() {
+        let mut hash = RollingAdler32::new();
+        let w = 65536;
+        assert!(w as u32 > BASE);
+
+        let mut bytes = vec![0; w*3];
+        for (i, b) in bytes.iter_mut().enumerate() {
+            *b = i as u8;
+        }
+
+        for (i, b) in bytes.iter().enumerate() {
+            if i >= w {
+                hash.remove(w, bytes[i - w]);
+            }
+            hash.update(*b);
+            if i > 0 && i % w == 0 {
+                assert_eq!(hash.hash(), 0x433a8772);
+            }
+        }
+        assert_eq!(hash.hash(), 0xbbba8772);
+    }
+}