Snap for 8358640 from a3c757545f3449a212d1f23b39a87b8e04d88360 to mainline-go-media-releaseaml_go_med_330913000android13-mainline-go-media-release

Change-Id: I9299e4b8456b904e1ca2888bb62d0e1d901de593

11 files changed, 147 insertions, 70 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 14919dc..8da2e20 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
 {
   "git": {
-    "sha1": "08c79b5e2348a4b44cac8860612c9ee1f5518544"
+    "sha1": "de247d6ac25d2e62d4cbd195f064ed4af35fd4eb"
   }
 }
diff --git a/.clippy.toml b/.clippy.toml
new file mode 100644
index 0000000..8e17d80
--- /dev/null
+++ b/.clippy.toml
@@ -0,0 +1 @@
+msrv = "1.0.0"
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
index ec51099..e0f8585 100644
--- a/.github/workflows/ci.yml
+++ b/.github/workflows/ci.yml
@@ -43,3 +43,11 @@ jobs:
       - uses: actions/checkout@v2
       - uses: dtolnay/rust-toolchain@1.0.0
       - run: cargo build
+
+  clippy:
+    name: Clippy
+    runs-on: ubuntu-latest
+    steps:
+      - uses: actions/checkout@v2
+      - uses: dtolnay/rust-toolchain@clippy
+      - run: cargo clippy -- -Dclippy::all -Dclippy::pedantic
diff --git a/Android.bp b/Android.bp
index f49b03d..6027693 100644
--- a/Android.bp
+++ b/Android.bp
@@ -38,10 +38,34 @@ license {
     ],
 }
 
+rust_test {
+    name: "itoa_test_tests_test",
+    host_supported: true,
+    crate_name: "test",
+    cargo_env_compat: true,
+    cargo_pkg_version: "0.4.8",
+    srcs: ["tests/test.rs"],
+    test_suites: ["general-tests"],
+    auto_gen_config: true,
+    test_options: {
+        unit_test: true,
+    },
+    edition: "2015",
+    features: [
+        "default",
+        "std",
+    ],
+    rustlibs: [
+        "libitoa",
+    ],
+}
+
 rust_library {
     name: "libitoa",
     host_supported: true,
     crate_name: "itoa",
+    cargo_env_compat: true,
+    cargo_pkg_version: "0.4.8",
     srcs: ["src/lib.rs"],
     edition: "2015",
     features: [
diff --git a/Cargo.toml b/Cargo.toml
index 8900cdc..02b4382 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,16 +3,15 @@
 # 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
+# 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)
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
 
 [package]
 name = "itoa"
-version = "0.4.7"
+version = "0.4.8"
 authors = ["David Tolnay <dtolnay@gmail.com>"]
 exclude = ["performance.png"]
 description = "Fast functions for printing integer primitives to an io::Write"
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 0192401..2781d7c 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
 [package]
 name = "itoa"
-version = "0.4.7" # remember to update html_root_url
+version = "0.4.8" # remember to update html_root_url
 authors = ["David Tolnay <dtolnay@gmail.com>"]
 license = "MIT OR Apache-2.0"
 description = "Fast functions for printing integer primitives to an io::Write"
diff --git a/METADATA b/METADATA
index 8ced762..e9cdb68 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/itoa/itoa-0.4.7.crate"
+    value: "https://static.crates.io/crates/itoa/itoa-0.4.8.crate"
   }
-  version: "0.4.7"
+  version: "0.4.8"
   license_type: NOTICE
   last_upgrade_date {
-    year: 2020
-    month: 12
-    day: 29
+    year: 2021
+    month: 9
+    day: 22
   }
 }
diff --git a/TEST_MAPPING b/TEST_MAPPING
index b4e52d2..9095ded 100644
--- a/TEST_MAPPING
+++ b/TEST_MAPPING
@@ -1,8 +1,63 @@
-// Generated by cargo2android.py for tests that depend on this crate.
+// Generated by update_crate_tests.py for tests that depend on this crate.
 {
+  "imports": [
+    {
+      "path": "external/rust/crates/base64"
+    },
+    {
+      "path": "external/rust/crates/bitflags"
+    },
+    {
+      "path": "external/rust/crates/either"
+    },
+    {
+      "path": "external/rust/crates/rand_chacha"
+    },
+    {
+      "path": "external/rust/crates/tinytemplate"
+    },
+    {
+      "path": "external/rust/crates/tinyvec"
+    },
+    {
+      "path": "external/rust/crates/unicode-xid"
+    },
+    {
+      "path": "external/rust/crates/url"
+    }
+  ],
   "presubmit": [
     {
-      "name": "url_device_test_src_lib"
+      "name": "ZipFuseTest"
+    },
+    {
+      "name": "authfs_device_test_src_lib"
+    },
+    {
+      "name": "itoa_test_tests_test"
+    },
+    {
+      "name": "microdroid_manager_test"
+    },
+    {
+      "name": "virtualizationservice_device_test"
+    }
+  ],
+  "presubmit-rust": [
+    {
+      "name": "ZipFuseTest"
+    },
+    {
+      "name": "authfs_device_test_src_lib"
+    },
+    {
+      "name": "itoa_test_tests_test"
+    },
+    {
+      "name": "microdroid_manager_test"
+    },
+    {
+      "name": "virtualizationservice_device_test"
     }
   ]
 }
diff --git a/cargo2android.json b/cargo2android.json
index 42b7833..ac56e26 100644
--- a/cargo2android.json
+++ b/cargo2android.json
@@ -5,5 +5,6 @@
   ],
   "dependencies": true,
   "device": true,
-  "run": true
+  "run": true,
+  "tests": true
 }
\ No newline at end of file
diff --git a/src/lib.rs b/src/lib.rs
index d7bc81c..8d4582e 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -56,12 +56,17 @@
 //! }
 //! ```
 
-#![doc(html_root_url = "https://docs.rs/itoa/0.4.7")]
+#![doc(html_root_url = "https://docs.rs/itoa/0.4.8")]
 #![cfg_attr(not(feature = "std"), no_std)]
 #![cfg_attr(feature = "cargo-clippy", allow(renamed_and_removed_lints))]
 #![cfg_attr(
     feature = "cargo-clippy",
-    allow(const_static_lifetime, transmute_ptr_to_ptr)
+    allow(
+        expl_impl_clone_on_copy,
+        missing_errors_doc,
+        must_use_candidate,
+        transmute_ptr_to_ptr
+    )
 )]
 
 #[cfg(feature = "i128")]
diff --git a/src/udiv128.rs b/src/udiv128.rs
index adbdce2..617c1c1 100644
--- a/src/udiv128.rs
+++ b/src/udiv128.rs
@@ -1,61 +1,45 @@
-// The code in this file is based on Rust's compiler-builtins crate. The Rust
-// compiler automatically links programs against this crate for target-specific
-// runtime support. We have copied the implementation of `__udivmodti4()` which
-// is an intrinsic implementing division with remainder for architectures
-// without 128-bit integers. This implementation works around some poor codegen
-// by LLVM (https://github.com/rust-lang/rust/issues/44545) and allows for
-// inlining which does not happen with the intrinsic.
-//
-// The compiler-builtins crate carries the following license, which is available
-// in full at:
-// https://github.com/rust-lang-nursery/compiler-builtins/blob/master/LICENSE.TXT
-//
-// ---
-//
-// Copyright 2009-2016 compiler-builtins Developers
-//
-// The compiler-builtins crate is dual licensed under both the University of
-// Illinois "BSD-Like" license and the MIT license. As a user of this code you
-// may choose to use it under either license. As a contributor, you agree to
-// allow your code to be used under both.
-
+/// Multiply unsigned 128 bit integers, return upper 128 bits of the result
 #[inline]
-pub fn udivmod_1e19(n: u128) -> (u128, u64) {
-    let d = 10_000_000_000_000_000_000_u64; // 10^19
+fn u128_mulhi(x: u128, y: u128) -> u128 {
+    let x_lo = x as u64;
+    let x_hi = (x >> 64) as u64;
+    let y_lo = y as u64;
+    let y_hi = (y >> 64) as u64;
 
-    let high = (n >> 64) as u64;
-    if high == 0 {
-        let low = n as u64;
-        return ((low / d) as u128, low % d);
-    }
+    // handle possibility of overflow
+    let carry = (x_lo as u128 * y_lo as u128) >> 64;
+    let m = x_lo as u128 * y_hi as u128 + carry;
+    let high1 = m >> 64;
 
-    let sr = 65 - high.leading_zeros();
+    let m_lo = m as u64;
+    let high2 = x_hi as u128 * y_lo as u128 + m_lo as u128 >> 64;
 
-    // 2 <= sr <= 65
-    let mut q: u128 = n << (128 - sr);
-    let mut r: u128 = n >> sr;
-    let mut carry: u64 = 0;
+    x_hi as u128 * y_hi as u128 + high1 + high2
+}
 
-    // Don't use a range because they may generate references to memcpy in unoptimized code
-    //
-    // Loop invariants:  r < d; carry is 0 or 1
-    let mut i = 0;
-    while i < sr {
-        i += 1;
+/// Divide `n` by 1e19 and return quotient and remainder
+///
+/// Integer division algorithm is based on the following paper:
+///
+///   T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication”
+///   in Proc. of the SIGPLAN94 Conference on Programming Language Design and
+///   Implementation, 1994, pp. 61–72
+///
+#[inline]
+pub fn udivmod_1e19(n: u128) -> (u128, u64) {
+    let d = 10_000_000_000_000_000_000_u64; // 10^19
 
-        // r:q = ((r:q) << 1) | carry
-        r = (r << 1) | (q >> 127);
-        q = (q << 1) | carry as u128;
+    let quot = if n < 1 << 83 {
+        ((n >> 19) as u64 / (d >> 19)) as u128
+    } else {
+        let factor =
+            (8507059173023461586_u64 as u128) << 64 | 10779635027931437427 as u128;
+        u128_mulhi(n, factor) >> 62
+    };
 
-        // carry = 0
-        // if r >= d {
-        //     r -= d;
-        //     carry = 1;
-        // }
-        let s = (d as u128).wrapping_sub(r).wrapping_sub(1) as i128 >> 127;
-        carry = (s & 1) as u64;
-        r -= (d as u128) & s as u128;
-    }
+    let rem = (n - quot * d as u128) as u64;
+    debug_assert_eq!(quot, n / d as u128);
+    debug_assert_eq!(rem as u128, n % d as u128);
 
-    ((q << 1) | carry as u128, r as u64)
+    (quot, rem)
 }