Adding upstream version 124.0.1.upstream/124.0.1

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

5 files changed, 503 insertions, 0 deletions

diff --git a/third_party/rust/fxhash/.cargo-checksum.json b/third_party/rust/fxhash/.cargo-checksum.json
new file mode 100644
index 0000000000..95747d6f48
--- /dev/null
+++ b/third_party/rust/fxhash/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"83bb4c3e7fbfb7380c175923ba7dfe150e4e09bd4ebfb45e65e5f8a494d36ab9","README.md":"7b9227f966b312e221bd372fef79438b2446a21241eb7542520eac29bfbc10d0","bench.rs":"b4dc3ef9eeb043ffb470b37a0c2a36306a024af808eac8517924359298d3e183","lib.rs":"885b72a1c977dc1c3ff4e0652719e62b6d8c3e713403e571afd581283f72df7b"},"package":"c31b6d751ae2c7f11320402d34e41349dd1016f8d5d45e48c4312bc8625af50c"}
\ No newline at end of file
diff --git a/third_party/rust/fxhash/Cargo.toml b/third_party/rust/fxhash/Cargo.toml
new file mode 100644
index 0000000000..ae86c78c46
--- /dev/null
+++ b/third_party/rust/fxhash/Cargo.toml
@@ -0,0 +1,38 @@
+# 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 = "fxhash"
+version = "0.2.1"
+authors = ["cbreeden <github@u.breeden.cc>"]
+description = "A fast, non-secure, hashing algorithm derived from an internal hasher used in FireFox and Rustc."
+documentation = "https://docs.rs/fxhash"
+readme = "README.md"
+keywords = ["hash"]
+categories = ["algorithms"]
+license = "Apache-2.0/MIT"
+repository = "https://github.com/cbreeden/fxhash"
+
+[lib]
+name = "fxhash"
+path = "lib.rs"
+
+[[bench]]
+name = "fxhash"
+path = "bench.rs"
+[dependencies.byteorder]
+version = "1.0.0"
+[dev-dependencies.seahash]
+version = "3.0.5"
+
+[dev-dependencies.fnv]
+version = "1.0.5"
diff --git a/third_party/rust/fxhash/README.md b/third_party/rust/fxhash/README.md
new file mode 100644
index 0000000000..672568ab12
--- /dev/null
+++ b/third_party/rust/fxhash/README.md
@@ -0,0 +1,62 @@
+# Fx Hash
+
+This hashing algorithm was extracted from the Rustc compiler.  This is the same hashing algoirthm used for some internal operations in FireFox.  The strength of this algorithm is in hashing 8 bytes at a time on 64-bit platforms, where the FNV algorithm works on one byte at a time.
+
+## Disclaimer
+
+It is **not a cryptographically secure** hash, so it is strongly recommended that you do not use this hash for cryptographic purproses.  Furthermore, this hashing algorithm was not designed to prevent any attacks for determining collisions which could be used to potentially cause quadratic behavior in `HashMap`s.  So it is not recommended to expose this hash in places where collissions or DDOS attacks may be a concern.
+
+## Examples
+
+Building an Fx backed hashmap.
+
+```rust
+extern crate fxhash;
+use fxhash::FxHashMap;
+
+let mut hashmap = FxHashMap::new();
+
+hashmap.insert("black", 0);
+hashmap.insert("white", 255);
+```
+
+Building an Fx backed hashset.
+
+```rust
+extern crate fxhash;
+use fxhash::FxHashSet;
+
+let mut hashmap = FxHashSet::new();
+
+hashmap.insert("black");
+hashmap.insert("white");
+```
+
+## Benchmarks
+
+Generally `fxhash` is than `fnv` on `u32`, `u64`, or any byte sequence with length >= 5.  However, keep in mind that hashing speed is not the only characteristic worth considering.  That being said, Rustc had an observable increase in speed when switching from `fnv` backed hashmaps to `fx` based hashmaps.
+
+    bench_fnv_003     ... bench:      3 ns/iter (+/- 0)
+    bench_fnv_004     ... bench:      2 ns/iter (+/- 0)
+    bench_fnv_011     ... bench:      6 ns/iter (+/- 1)
+    bench_fnv_012     ... bench:      5 ns/iter (+/- 1)
+    bench_fnv_023     ... bench:     14 ns/iter (+/- 3)
+    bench_fnv_024     ... bench:     14 ns/iter (+/- 4)
+    bench_fnv_068     ... bench:     57 ns/iter (+/- 11)
+    bench_fnv_132     ... bench:    145 ns/iter (+/- 30)
+    bench_fx_003      ... bench:      4 ns/iter (+/- 0)
+    bench_fx_004      ... bench:      3 ns/iter (+/- 1)
+    bench_fx_011      ... bench:      5 ns/iter (+/- 2)
+    bench_fx_012      ... bench:      4 ns/iter (+/- 1)
+    bench_fx_023      ... bench:      7 ns/iter (+/- 3)
+    bench_fx_024      ... bench:      4 ns/iter (+/- 1)
+    bench_fx_068      ... bench:     10 ns/iter (+/- 3)
+    bench_fx_132      ... bench:     19 ns/iter (+/- 5)
+    bench_seahash_003 ... bench:     30 ns/iter (+/- 12)
+    bench_seahash_004 ... bench:     32 ns/iter (+/- 22)
+    bench_seahash_011 ... bench:     30 ns/iter (+/- 4)
+    bench_seahash_012 ... bench:     31 ns/iter (+/- 1)
+    bench_seahash_023 ... bench:     32 ns/iter (+/- 6)
+    bench_seahash_024 ... bench:     31 ns/iter (+/- 5)
+    bench_seahash_068 ... bench:     40 ns/iter (+/- 9)
+    bench_seahash_132 ... bench:     50 ns/iter (+/- 12)
\ No newline at end of file
diff --git a/third_party/rust/fxhash/bench.rs b/third_party/rust/fxhash/bench.rs
new file mode 100644
index 0000000000..b54395497c
--- /dev/null
+++ b/third_party/rust/fxhash/bench.rs
@@ -0,0 +1,78 @@
+#![feature(test)]
+extern crate test;
+extern crate fnv;
+extern crate fxhash;
+extern crate seahash;
+
+use std::hash::{Hash, Hasher};
+use test::{Bencher, black_box};
+
+
+fn fnvhash<H: Hash>(b: H) -> u64 {
+    let mut hasher = fnv::FnvHasher::default();
+    b.hash(&mut hasher);
+    hasher.finish()
+}
+
+fn seahash<H: Hash>(b: H) -> u64 {
+    let mut hasher = seahash::SeaHasher::default();
+    b.hash(&mut hasher);
+    hasher.finish()
+}
+
+macro_rules! generate_benches {
+    ($($fx:ident, $fx32:ident, $fx64:ident, $fnv:ident, $sea:ident, $s:expr),* $(,)*) => (
+        $(
+            #[bench]
+            fn $fx(b: &mut Bencher) {
+                let s = black_box($s);
+                b.iter(|| {
+                    fxhash::hash(&s)
+                })
+            }
+
+            #[bench]
+            fn $fx32(b: &mut Bencher) {
+                let s = black_box($s);
+                b.iter(|| {
+                    fxhash::hash32(&s)
+                })
+            }
+
+            #[bench]
+            fn $fx64(b: &mut Bencher) {
+                let s = black_box($s);
+                b.iter(|| {
+                    fxhash::hash64(&s)
+                })
+            }
+
+            #[bench]
+            fn $fnv(b: &mut Bencher) {
+                let s = black_box($s);
+                b.iter(|| {
+                    fnvhash(&s)
+                })
+            }
+
+            #[bench]
+            fn $sea(b: &mut Bencher) {
+                let s = black_box($s);
+                b.iter(|| {
+                    seahash(&s)
+                })
+            }
+        )*
+    )
+}
+
+generate_benches!(
+    bench_fx_003, bench_fx32_003, bench_fx64_003, bench_fnv_003, bench_seahash_003, "123",
+    bench_fx_004, bench_fx32_004, bench_fx64_004, bench_fnv_004, bench_seahash_004, "1234",
+    bench_fx_011, bench_fx32_011, bench_fx64_011, bench_fnv_011, bench_seahash_011, "12345678901",
+    bench_fx_012, bench_fx32_012, bench_fx64_012, bench_fnv_012, bench_seahash_012, "123456789012",
+    bench_fx_023, bench_fx32_023, bench_fx64_023, bench_fnv_023, bench_seahash_023, "12345678901234567890123",
+    bench_fx_024, bench_fx32_024, bench_fx64_024, bench_fnv_024, bench_seahash_024, "123456789012345678901234",
+    bench_fx_068, bench_fx32_068, bench_fx64_068, bench_fnv_068, bench_seahash_068, "11234567890123456789012345678901234567890123456789012345678901234567",
+    bench_fx_132, bench_fx32_132, bench_fx64_132, bench_fnv_132, bench_seahash_132, "112345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901",
+);
\ No newline at end of file
diff --git a/third_party/rust/fxhash/lib.rs b/third_party/rust/fxhash/lib.rs
new file mode 100644
index 0000000000..22eb88c8d2
--- /dev/null
+++ b/third_party/rust/fxhash/lib.rs
@@ -0,0 +1,324 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![deny(missing_docs)]
+
+//! # Fx Hash
+//!
+//! This hashing algorithm was extracted from the Rustc compiler.  This is the same hashing
+//! algoirthm used for some internal operations in FireFox.  The strength of this algorithm
+//! is in hashing 8 bytes at a time on 64-bit platforms, where the FNV algorithm works on one
+//! byte at a time.
+//!
+//! ## Disclaimer
+//!
+//! It is **not a cryptographically secure** hash, so it is strongly recommended that you do
+//! not use this hash for cryptographic purproses.  Furthermore, this hashing algorithm was
+//! not designed to prevent any attacks for determining collisions which could be used to
+//! potentially cause quadratic behavior in `HashMap`s.  So it is not recommended to expose
+//! this hash in places where collissions or DDOS attacks may be a concern.
+
+use std::collections::{HashMap, HashSet};
+use std::default::Default;
+use std::hash::{Hasher, Hash, BuildHasherDefault};
+use std::ops::BitXor;
+
+extern crate byteorder;
+use byteorder::{ByteOrder, NativeEndian};
+
+/// A builder for default Fx hashers.
+pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
+
+/// A `HashMap` using a default Fx hasher.
+pub type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;
+
+/// A `HashSet` using a default Fx hasher.
+pub type FxHashSet<V> = HashSet<V, FxBuildHasher>;
+
+const ROTATE: u32 = 5;
+const SEED64: u64 = 0x517cc1b727220a95;
+const SEED32: u32 = (SEED64 & 0xFFFF_FFFF) as u32;
+
+#[cfg(target_pointer_width = "32")]
+const SEED: usize = SEED32 as usize;
+#[cfg(target_pointer_width = "64")]
+const SEED: usize = SEED64 as usize;
+
+trait HashWord {
+    fn hash_word(&mut self, Self);
+}
+
+macro_rules! impl_hash_word {
+    ($($ty:ty = $key:ident),* $(,)*) => (
+        $(
+            impl HashWord for $ty {
+                #[inline]
+                fn hash_word(&mut self, word: Self) {
+                    *self = self.rotate_left(ROTATE).bitxor(word).wrapping_mul($key);
+                }
+            }
+        )*
+    )
+}
+
+impl_hash_word!(usize = SEED, u32 = SEED32, u64 = SEED64);
+
+#[inline]
+fn write32(mut hash: u32, mut bytes: &[u8]) -> u32 {
+    while bytes.len() >= 4 {
+        let n = NativeEndian::read_u32(bytes);
+        hash.hash_word(n);
+        bytes = bytes.split_at(4).1;
+    }
+
+    for byte in bytes {
+        hash.hash_word(*byte as u32);
+    }
+    hash
+}
+
+#[inline]
+fn write64(mut hash: u64, mut bytes: &[u8]) -> u64 {
+    while bytes.len() >= 8 {
+        let n = NativeEndian::read_u64(bytes);
+        hash.hash_word(n);
+        bytes = bytes.split_at(8).1;
+    }
+
+    if bytes.len() >= 4 {
+        let n = NativeEndian::read_u32(bytes);
+        hash.hash_word(n as u64);
+        bytes = bytes.split_at(4).1;
+    }
+
+    for byte in bytes {
+        hash.hash_word(*byte as u64);
+    }
+    hash
+}
+
+#[inline]
+#[cfg(target_pointer_width = "32")]
+fn write(hash: usize, bytes: &[u8]) -> usize {
+    write32(hash as u32, bytes) as usize
+}
+
+#[inline]
+#[cfg(target_pointer_width = "64")]
+fn write(hash: usize, bytes: &[u8]) -> usize {
+    write64(hash as u64, bytes) as usize
+}
+
+/// This hashing algorithm was extracted from the Rustc compiler.
+/// This is the same hashing algoirthm used for some internal operations in FireFox.
+/// The strength of this algorithm is in hashing 8 bytes at a time on 64-bit platforms,
+/// where the FNV algorithm works on one byte at a time.
+///
+/// This hashing algorithm should not be used for cryptographic, or in scenarios where
+/// DOS attacks are a concern.
+#[derive(Debug, Clone)]
+pub struct FxHasher {
+    hash: usize,
+}
+
+impl Default for FxHasher {
+    #[inline]
+    fn default() -> FxHasher {
+        FxHasher { hash: 0 }
+    }
+}
+
+impl Hasher for FxHasher {
+    #[inline]
+    fn write(&mut self, bytes: &[u8]) {
+        self.hash = write(self.hash, bytes);
+    }
+
+    #[inline]
+    fn write_u8(&mut self, i: u8) {
+        self.hash.hash_word(i as usize);
+    }
+
+    #[inline]
+    fn write_u16(&mut self, i: u16) {
+        self.hash.hash_word(i as usize);
+    }
+
+    #[inline]
+    fn write_u32(&mut self, i: u32) {
+        self.hash.hash_word(i as usize);
+    }
+
+    #[inline]
+    #[cfg(target_pointer_width = "32")]
+    fn write_u64(&mut self, i: u64) {
+        self.hash.hash_word(i as usize);
+        self.hash.hash_word((i >> 32) as usize);
+    }
+
+    #[inline]
+    #[cfg(target_pointer_width = "64")]
+    fn write_u64(&mut self, i: u64) {
+        self.hash.hash_word(i as usize);
+    }
+
+    #[inline]
+    fn write_usize(&mut self, i: usize) {
+        self.hash.hash_word(i);
+    }
+
+    #[inline]
+    fn finish(&self) -> u64 {
+        self.hash as u64
+    }
+}
+
+/// This hashing algorithm was extracted from the Rustc compiler.
+/// This is the same hashing algoirthm used for some internal operations in FireFox.
+/// The strength of this algorithm is in hashing 8 bytes at a time on any platform,
+/// where the FNV algorithm works on one byte at a time.
+///
+/// This hashing algorithm should not be used for cryptographic, or in scenarios where
+/// DOS attacks are a concern.
+#[derive(Debug, Clone)]
+pub struct FxHasher64 {
+    hash: u64,
+}
+
+impl Default for FxHasher64 {
+    #[inline]
+    fn default() -> FxHasher64 {
+        FxHasher64 { hash: 0 }
+    }
+}
+
+impl Hasher for FxHasher64 {
+    #[inline]
+    fn write(&mut self, bytes: &[u8]) {
+        self.hash = write64(self.hash, bytes);
+    }
+
+    #[inline]
+    fn write_u8(&mut self, i: u8) {
+        self.hash.hash_word(i as u64);
+    }
+
+    #[inline]
+    fn write_u16(&mut self, i: u16) {
+        self.hash.hash_word(i as u64);
+    }
+
+    #[inline]
+    fn write_u32(&mut self, i: u32) {
+        self.hash.hash_word(i as u64);
+    }
+
+    fn write_u64(&mut self, i: u64) {
+        self.hash.hash_word(i);
+    }
+
+    #[inline]
+    fn write_usize(&mut self, i: usize) {
+        self.hash.hash_word(i as u64);
+    }
+
+    #[inline]
+    fn finish(&self) -> u64 {
+        self.hash
+    }
+}
+
+/// This hashing algorithm was extracted from the Rustc compiler.
+/// This is the same hashing algoirthm used for some internal operations in FireFox.
+/// The strength of this algorithm is in hashing 4 bytes at a time on any platform,
+/// where the FNV algorithm works on one byte at a time.
+///
+/// This hashing algorithm should not be used for cryptographic, or in scenarios where
+/// DOS attacks are a concern.
+#[derive(Debug, Clone)]
+pub struct FxHasher32 {
+    hash: u32,
+}
+
+impl Default for FxHasher32 {
+    #[inline]
+    fn default() -> FxHasher32 {
+        FxHasher32 { hash: 0 }
+    }
+}
+
+impl Hasher for FxHasher32 {
+    #[inline]
+    fn write(&mut self, bytes: &[u8]) {
+        self.hash = write32(self.hash, bytes);
+    }
+
+    #[inline]
+    fn write_u8(&mut self, i: u8) {
+        self.hash.hash_word(i as u32);
+    }
+
+    #[inline]
+    fn write_u16(&mut self, i: u16) {
+        self.hash.hash_word(i as u32);
+    }
+
+    #[inline]
+    fn write_u32(&mut self, i: u32) {
+        self.hash.hash_word(i);
+    }
+
+    #[inline]
+    fn write_u64(&mut self, i: u64) {
+        self.hash.hash_word(i as u32);
+        self.hash.hash_word((i >> 32) as u32);
+    }
+
+    #[inline]
+    #[cfg(target_pointer_width = "32")]
+    fn write_usize(&mut self, i: usize) {
+        self.write_u32(i as u32);
+    }
+
+    #[inline]
+    #[cfg(target_pointer_width = "64")]
+    fn write_usize(&mut self, i: usize) {
+        self.write_u64(i as u64);
+    }
+
+    #[inline]
+    fn finish(&self) -> u64 {
+        self.hash as u64
+    }
+}
+
+/// A convenience function for when you need a quick 64-bit hash.
+#[inline]
+pub fn hash64<T: Hash + ?Sized>(v: &T) -> u64 {
+    let mut state = FxHasher64::default();
+    v.hash(&mut state);
+    state.finish()
+}
+
+/// A convenience function for when you need a quick 32-bit hash.
+#[inline]
+pub fn hash32<T: Hash + ?Sized>(v: &T) -> u32 {
+    let mut state = FxHasher32::default();
+    v.hash(&mut state);
+    state.finish() as u32
+}
+
+/// A convenience function for when you need a quick usize hash.
+#[inline]
+pub fn hash<T: Hash + ?Sized>(v: &T) -> usize {
+    let mut state = FxHasher::default();
+    v.hash(&mut state);
+    state.finish() as usize
+}
\ No newline at end of file