diff options
Diffstat (limited to 'third_party/rust/itoa')
| -rw-r--r-- | third_party/rust/itoa/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | third_party/rust/itoa/Cargo.toml | 30 | ||||
| -rw-r--r-- | third_party/rust/itoa/LICENSE-APACHE | 201 | ||||
| -rw-r--r-- | third_party/rust/itoa/LICENSE-MIT | 23 | ||||
| -rw-r--r-- | third_party/rust/itoa/README.md | 95 | ||||
| -rw-r--r-- | third_party/rust/itoa/benches/bench.rs | 83 | ||||
| -rw-r--r-- | third_party/rust/itoa/src/lib.rs | 342 | ||||
| -rw-r--r-- | third_party/rust/itoa/src/udiv128.rs | 61 | ||||
| -rw-r--r-- | third_party/rust/itoa/tests/test.rs | 50 |
9 files changed, 886 insertions, 0 deletions
diff --git a/third_party/rust/itoa/.cargo-checksum.json b/third_party/rust/itoa/.cargo-checksum.json new file mode 100644 index 0000000000..0c5f193e42 --- /dev/null +++ b/third_party/rust/itoa/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"f744809613f4bebac2bce3256ffde0044d9f0cda6adcb2fd0cc462d2afb8ad98","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"23f18e03dc49df91622fe2a76176497404e46ced8a715d9d2b67a7446571cca3","README.md":"398a1f9022fdf54c13326688a2ba060dfb4b247b45cfc731aad00eba39442f2d","benches/bench.rs":"65020d3ef575c4f9aa9f09ab28dc4164d98207515301d7d16b57c3e48d84049d","src/lib.rs":"c818bec8a1e3522f2b34dd7f8c8f36ca26a368e028c96e3c5771cf57a18158fc","src/udiv128.rs":"16c27cc61f69ca79eca3ac624d6baceaccdbf27cfa43c85c7e065c1ff1481748","tests/test.rs":"428d30ab57b412211a6a0faa7ac36b359e37572b259cd05ac56f4dff6078e896"},"package":"501266b7edd0174f8530248f87f99c88fbe60ca4ef3dd486835b8d8d53136f7f"}
\ No newline at end of file diff --git a/third_party/rust/itoa/Cargo.toml b/third_party/rust/itoa/Cargo.toml new file mode 100644 index 0000000000..0563bc1af4 --- /dev/null +++ b/third_party/rust/itoa/Cargo.toml @@ -0,0 +1,30 @@ +# 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 = "itoa" +version = "0.4.4" +authors = ["David Tolnay <dtolnay@gmail.com>"] +exclude = ["performance.png"] +description = "Fast functions for printing integer primitives to an io::Write" +documentation = "https://github.com/dtolnay/itoa" +readme = "README.md" +categories = ["value-formatting"] +license = "MIT/Apache-2.0" +repository = "https://github.com/dtolnay/itoa" + +[features] +default = ["std"] +i128 = [] +std = [] +[badges.travis-ci] +repository = "dtolnay/itoa" diff --git a/third_party/rust/itoa/LICENSE-APACHE b/third_party/rust/itoa/LICENSE-APACHE new file mode 100644 index 0000000000..16fe87b06e --- /dev/null +++ b/third_party/rust/itoa/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/third_party/rust/itoa/LICENSE-MIT b/third_party/rust/itoa/LICENSE-MIT new file mode 100644 index 0000000000..31aa79387f --- /dev/null +++ b/third_party/rust/itoa/LICENSE-MIT @@ -0,0 +1,23 @@ +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/third_party/rust/itoa/README.md b/third_party/rust/itoa/README.md new file mode 100644 index 0000000000..d36f4fd51c --- /dev/null +++ b/third_party/rust/itoa/README.md @@ -0,0 +1,95 @@ +itoa +==== + +[](https://travis-ci.org/dtolnay/itoa) +[](https://crates.io/crates/itoa) +[](https://docs.rs/itoa) + +This crate provides fast functions for printing integer primitives to an +[`io::Write`] or a [`fmt::Write`]. The implementation comes straight from +[libcore] but avoids the performance penalty of going through +[`fmt::Formatter`]. + +See also [`dtoa`] for printing floating point primitives. + +*Version requirement: rustc 1.0+* + +[`io::Write`]: https://doc.rust-lang.org/std/io/trait.Write.html +[`fmt::Write`]: https://doc.rust-lang.org/core/fmt/trait.Write.html +[libcore]: https://github.com/rust-lang/rust/blob/b8214dc6c6fc20d0a660fb5700dca9ebf51ebe89/src/libcore/fmt/num.rs#L201-L254 +[`fmt::Formatter`]: https://doc.rust-lang.org/std/fmt/struct.Formatter.html +[`dtoa`]: https://github.com/dtolnay/dtoa + +```toml +[dependencies] +itoa = "0.4" +``` + +<br> + +## Performance (lower is better) + + + +<br> + +## Examples + +```rust +use std::{fmt, io}; + +fn demo_itoa_write() -> io::Result<()> { + // Write to a vector or other io::Write. + let mut buf = Vec::new(); + itoa::write(&mut buf, 128u64)?; + println!("{:?}", buf); + + // Write to a stack buffer. + let mut bytes = [0u8; 20]; + let n = itoa::write(&mut bytes[..], 128u64)?; + println!("{:?}", &bytes[..n]); + + Ok(()) +} + +fn demo_itoa_fmt() -> fmt::Result { + // Write to a string. + let mut s = String::new(); + itoa::fmt(&mut s, 128u64)?; + println!("{}", s); + + Ok(()) +} +``` + +The function signatures are: + +```rust +fn write<W: io::Write, V: itoa::Integer>(writer: W, value: V) -> io::Result<usize>; + +fn fmt<W: fmt::Write, V: itoa::Integer>(writer: W, value: V) -> fmt::Result; +``` + +where `itoa::Integer` is implemented for i8, u8, i16, u16, i32, u32, i64, u64, +i128, u128, isize and usize. 128-bit integer support requires rustc 1.26+ and +the `i128` feature of this crate enabled. + +The `write` function is only available when the `std` feature is enabled +(default is enabled). The return value gives the number of bytes written. + +<br> + +#### License + +<sup> +Licensed under either of <a href="LICENSE-APACHE">Apache License, Version +2.0</a> or <a href="LICENSE-MIT">MIT license</a> at your option. +</sup> + +<br> + +<sub> +Unless you explicitly state otherwise, any contribution intentionally submitted +for inclusion in this crate by you, as defined in the Apache-2.0 license, shall +be dual licensed as above, without any additional terms or conditions. +</sub> diff --git a/third_party/rust/itoa/benches/bench.rs b/third_party/rust/itoa/benches/bench.rs new file mode 100644 index 0000000000..c3b55000b9 --- /dev/null +++ b/third_party/rust/itoa/benches/bench.rs @@ -0,0 +1,83 @@ +#![cfg_attr(feature = "cargo-clippy", allow(cast_lossless))] +#![feature(test)] +#![allow(non_snake_case)] + +extern crate itoa; +extern crate test; + +macro_rules! benches { + ( + $( + $(#[$attr:meta])* + $name:ident($value:expr) + ),* + ) => { + mod bench_itoa_write { + use test::{Bencher, black_box}; + $( + $(#[$attr])* + #[bench] + fn $name(b: &mut Bencher) { + use itoa; + + let mut buf = Vec::with_capacity(40); + + b.iter(|| { + buf.clear(); + itoa::write(&mut buf, black_box($value)).unwrap() + }); + } + )* + } + + mod bench_itoa_fmt { + use test::{Bencher, black_box}; + $( + $(#[$attr])* + #[bench] + fn $name(b: &mut Bencher) { + use itoa; + + let mut buf = String::with_capacity(40); + + b.iter(|| { + buf.clear(); + itoa::fmt(&mut buf, black_box($value)).unwrap() + }); + } + )* + } + + mod bench_std_fmt { + use test::{Bencher, black_box}; + $( + $(#[$attr])* + #[bench] + fn $name(b: &mut Bencher) { + use std::io::Write; + + let mut buf = Vec::with_capacity(40); + + b.iter(|| { + buf.clear(); + write!(&mut buf, "{}", black_box($value)).unwrap() + }); + } + )* + } + } +} + +benches!{ + bench_u64_0(0u64), + bench_u64_half(<u32>::max_value() as u64), + bench_u64_max(<u64>::max_value()), + + bench_i16_0(0i16), + bench_i16_min(<i16>::min_value()), + + #[cfg(feature = "i128")] + bench_u128_0(0u128), + #[cfg(feature = "i128")] + bench_u128_max(<u128>::max_value()) +} diff --git a/third_party/rust/itoa/src/lib.rs b/third_party/rust/itoa/src/lib.rs new file mode 100644 index 0000000000..323bb6e2fe --- /dev/null +++ b/third_party/rust/itoa/src/lib.rs @@ -0,0 +1,342 @@ +//! This crate provides fast functions for printing integer primitives to an +//! [`io::Write`] or a [`fmt::Write`]. The implementation comes straight from +//! [libcore] but avoids the performance penalty of going through +//! [`fmt::Formatter`]. +//! +//! See also [`dtoa`] for printing floating point primitives. +//! +//! [`io::Write`]: https://doc.rust-lang.org/std/io/trait.Write.html +//! [`fmt::Write`]: https://doc.rust-lang.org/core/fmt/trait.Write.html +//! [libcore]: https://github.com/rust-lang/rust/blob/b8214dc6c6fc20d0a660fb5700dca9ebf51ebe89/src/libcore/fmt/num.rs#L201-L254 +//! [`fmt::Formatter`]: https://doc.rust-lang.org/std/fmt/struct.Formatter.html +//! [`dtoa`]: https://github.com/dtolnay/dtoa +//! +//! <br> +//! +//! # Performance (lower is better) +//! +//!  +//! +//! <br> +//! +//! # Examples +//! +//! ```edition2018 +//! use std::{fmt, io}; +//! +//! fn demo_itoa_write() -> io::Result<()> { +//! // Write to a vector or other io::Write. +//! let mut buf = Vec::new(); +//! itoa::write(&mut buf, 128u64)?; +//! println!("{:?}", buf); +//! +//! // Write to a stack buffer. +//! let mut bytes = [0u8; 20]; +//! let n = itoa::write(&mut bytes[..], 128u64)?; +//! println!("{:?}", &bytes[..n]); +//! +//! Ok(()) +//! } +//! +//! fn demo_itoa_fmt() -> fmt::Result { +//! // Write to a string. +//! let mut s = String::new(); +//! itoa::fmt(&mut s, 128u64)?; +//! println!("{}", s); +//! +//! Ok(()) +//! } +//! ``` + +#![doc(html_root_url = "https://docs.rs/itoa/0.4.4")] +#![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), +)] + +#[cfg(feature = "i128")] +mod udiv128; + +#[cfg(feature = "std")] +use std::{fmt, io, mem, ptr, slice, str}; + +#[cfg(not(feature = "std"))] +use core::{fmt, mem, ptr, slice, str}; + +/// Write integer to an `io::Write`. +#[cfg(feature = "std")] +#[inline] +pub fn write<W: io::Write, V: Integer>(mut wr: W, value: V) -> io::Result<usize> { + let mut buf = Buffer::new(); + let s = buf.format(value); + try!(wr.write_all(s.as_bytes())); + Ok(s.len()) +} + +/// Write integer to an `fmt::Write`. +#[inline] +pub fn fmt<W: fmt::Write, V: Integer>(mut wr: W, value: V) -> fmt::Result { + let mut buf = Buffer::new(); + wr.write_str(buf.format(value)) +} + +/// A safe API for formatting integers to text. +/// +/// # Example +/// +/// ``` +/// let mut buffer = itoa::Buffer::new(); +/// let printed = buffer.format(1234); +/// assert_eq!(printed, "1234"); +/// ``` +#[derive(Copy)] +pub struct Buffer { + bytes: [u8; I128_MAX_LEN], +} + +impl Default for Buffer { + #[inline] + fn default() -> Buffer { + Buffer::new() + } +} + +impl Clone for Buffer { + #[inline] + fn clone(&self) -> Self { + Buffer::new() + } +} + +impl Buffer { + /// This is a cheap operation; you don't need to worry about reusing buffers + /// for efficiency. + #[inline] + pub fn new() -> Buffer { + Buffer { + bytes: unsafe { mem::uninitialized() }, + } + } + + /// Print an integer into this buffer and return a reference to its string representation + /// within the buffer. + pub fn format<I: Integer>(&mut self, i: I) -> &str { + i.write(self) + } +} + +// Seal to prevent downstream implementations of the Integer trait. +mod private { + pub trait Sealed {} +} + +/// An integer that can be formatted by `itoa::write` and `itoa::fmt`. +/// +/// This trait is sealed and cannot be implemented for types outside of itoa. +pub trait Integer: private::Sealed { + // Not public API. + #[doc(hidden)] + fn write(self, buf: &mut Buffer) -> &str; +} + +trait IntegerPrivate<B> { + fn write_to(self, buf: &mut B) -> &[u8]; +} + +const DEC_DIGITS_LUT: &'static [u8] = b"\ + 0001020304050607080910111213141516171819\ + 2021222324252627282930313233343536373839\ + 4041424344454647484950515253545556575859\ + 6061626364656667686970717273747576777879\ + 8081828384858687888990919293949596979899"; + +// Adaptation of the original implementation at +// https://github.com/rust-lang/rust/blob/b8214dc6c6fc20d0a660fb5700dca9ebf51ebe89/src/libcore/fmt/num.rs#L188-L266 +macro_rules! impl_IntegerCommon { + ($max_len:expr, $t:ident) => { + impl Integer for $t { + #[inline] + fn write(self, buf: &mut Buffer) -> &str { + unsafe { + debug_assert!($max_len <= I128_MAX_LEN); + let buf = mem::transmute::<&mut [u8; I128_MAX_LEN], &mut [u8; $max_len]>( + &mut buf.bytes, + ); + let bytes = self.write_to(buf); + str::from_utf8_unchecked(bytes) + } + } + } + + impl private::Sealed for $t {} + }; +} + +macro_rules! impl_Integer { + ($($max_len:expr => $t:ident),* as $conv_fn:ident) => {$( + impl_IntegerCommon!($max_len, $t); + + impl IntegerPrivate<[u8; $max_len]> for $t { + #[allow(unused_comparisons)] + #[inline] + fn write_to(self, buf: &mut [u8; $max_len]) -> &[u8] { + let is_nonnegative = self >= 0; + let mut n = if is_nonnegative { + self as $conv_fn + } else { + // convert the negative num to positive by summing 1 to it's 2 complement + (!(self as $conv_fn)).wrapping_add(1) + }; + let mut curr = buf.len() as isize; + let buf_ptr = buf.as_mut_ptr(); + let lut_ptr = DEC_DIGITS_LUT.as_ptr(); + + unsafe { + // need at least 16 bits for the 4-characters-at-a-time to work. + if mem::size_of::<$t>() >= 2 { + // eagerly decode 4 characters at a time + while n >= 10000 { + let rem = (n % 10000) as isize; + n /= 10000; + + let d1 = (rem / 100) << 1; + let d2 = (rem % 100) << 1; + curr -= 4; + ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2); + ptr::copy_nonoverlapping(lut_ptr.offset(d2), buf_ptr.offset(curr + 2), 2); + } + } + + // if we reach here numbers are <= 9999, so at most 4 chars long + let mut n = n as isize; // possibly reduce 64bit math + + // decode 2 more chars, if > 2 chars + if n >= 100 { + let d1 = (n % 100) << 1; + n /= 100; + curr -= 2; + ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2); + } + + // decode last 1 or 2 chars + if n < 10 { + curr -= 1; + *buf_ptr.offset(curr) = (n as u8) + b'0'; + } else { + let d1 = n << 1; + curr -= 2; + ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2); + } + + if !is_nonnegative { + curr -= 1; + *buf_ptr.offset(curr) = b'-'; + } + } + + let len = buf.len() - curr as usize; + unsafe { slice::from_raw_parts(buf_ptr.offset(curr), len) } + } + } + )*}; +} + +const I8_MAX_LEN: usize = 4; +const U8_MAX_LEN: usize = 3; +const I16_MAX_LEN: usize = 6; +const U16_MAX_LEN: usize = 5; +const I32_MAX_LEN: usize = 11; +const U32_MAX_LEN: usize = 10; +const I64_MAX_LEN: usize = 20; +const U64_MAX_LEN: usize = 20; + +impl_Integer!( + I8_MAX_LEN => i8, + U8_MAX_LEN => u8, + I16_MAX_LEN => i16, + U16_MAX_LEN => u16, + I32_MAX_LEN => i32, + U32_MAX_LEN => u32 + as u32); + +impl_Integer!(I64_MAX_LEN => i64, U64_MAX_LEN => u64 as u64); + +#[cfg(target_pointer_width = "16")] +impl_Integer!(I16_MAX_LEN => isize, U16_MAX_LEN => usize as u16); + +#[cfg(target_pointer_width = "32")] +impl_Integer!(I32_MAX_LEN => isize, U32_MAX_LEN => usize as u32); + +#[cfg(target_pointer_width = "64")] +impl_Integer!(I64_MAX_LEN => isize, U64_MAX_LEN => usize as u64); + +#[cfg(all(feature = "i128"))] +macro_rules! impl_Integer128 { + ($($max_len:expr => $t:ident),*) => {$( + impl_IntegerCommon!($max_len, $t); + + impl IntegerPrivate<[u8; $max_len]> for $t { + #[allow(unused_comparisons)] + #[inline] + fn write_to(self, buf: &mut [u8; $max_len]) -> &[u8] { + let is_nonnegative = self >= 0; + let n = if is_nonnegative { + self as u128 + } else { + // convert the negative num to positive by summing 1 to it's 2 complement + (!(self as u128)).wrapping_add(1) + }; + let mut curr = buf.len() as isize; + let buf_ptr = buf.as_mut_ptr(); + + unsafe { + // Divide by 10^19 which is the highest power less than 2^64. + let (n, rem) = udiv128::udivmod_1e19(n); + let buf1 = buf_ptr.offset(curr - U64_MAX_LEN as isize) as *mut [u8; U64_MAX_LEN]; + curr -= rem.write_to(&mut *buf1).len() as isize; + + if n != 0 { + // Memset the base10 leading zeros of rem. + let target = buf.len() as isize - 19; + ptr::write_bytes(buf_ptr.offset(target), b'0', (curr - target) as usize); + curr = target; + + // Divide by 10^19 again. + let (n, rem) = udiv128::udivmod_1e19(n); + let buf2 = buf_ptr.offset(curr - U64_MAX_LEN as isize) as *mut [u8; U64_MAX_LEN]; + curr -= rem.write_to(&mut *buf2).len() as isize; + + if n != 0 { + // Memset the leading zeros. + let target = buf.len() as isize - 38; + ptr::write_bytes(buf_ptr.offset(target), b'0', (curr - target) as usize); + curr = target; + + // There is at most one digit left + // because u128::max / 10^19 / 10^19 is 3. + curr -= 1; + *buf_ptr.offset(curr) = (n as u8) + b'0'; + } + } + + if !is_nonnegative { + curr -= 1; + *buf_ptr.offset(curr) = b'-'; + } + + let len = buf.len() - curr as usize; + slice::from_raw_parts(buf_ptr.offset(curr), len) + } + } + } + )*}; +} + +#[cfg(all(feature = "i128"))] +const U128_MAX_LEN: usize = 39; +const I128_MAX_LEN: usize = 40; + +#[cfg(all(feature = "i128"))] +impl_Integer128!(I128_MAX_LEN => i128, U128_MAX_LEN => u128); diff --git a/third_party/rust/itoa/src/udiv128.rs b/third_party/rust/itoa/src/udiv128.rs new file mode 100644 index 0000000000..adbdce2272 --- /dev/null +++ b/third_party/rust/itoa/src/udiv128.rs @@ -0,0 +1,61 @@ +// 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. + +#[inline] +pub fn udivmod_1e19(n: u128) -> (u128, u64) { + let d = 10_000_000_000_000_000_000_u64; // 10^19 + + let high = (n >> 64) as u64; + if high == 0 { + let low = n as u64; + return ((low / d) as u128, low % d); + } + + let sr = 65 - high.leading_zeros(); + + // 2 <= sr <= 65 + let mut q: u128 = n << (128 - sr); + let mut r: u128 = n >> sr; + let mut carry: u64 = 0; + + // 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; + + // r:q = ((r:q) << 1) | carry + r = (r << 1) | (q >> 127); + q = (q << 1) | carry as u128; + + // 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; + } + + ((q << 1) | carry as u128, r as u64) +} diff --git a/third_party/rust/itoa/tests/test.rs b/third_party/rust/itoa/tests/test.rs new file mode 100644 index 0000000000..dd8d4948a4 --- /dev/null +++ b/third_party/rust/itoa/tests/test.rs @@ -0,0 +1,50 @@ +#![cfg_attr( + feature = "cargo-clippy", + allow(cast_lossless, string_lit_as_bytes) +)] +#![allow(non_snake_case)] + +extern crate itoa; + +macro_rules! test { + ( + $( + $(#[$attr:meta])* + $name:ident($value:expr, $expected:expr) + ),* + ) => { + $( + $(#[$attr])* + #[test] + fn $name() { + #[cfg(feature = "std")] + { + let mut buf = [b'\0'; 40]; + let len = itoa::write(&mut buf[..], $value).unwrap(); + assert_eq!(&buf[0..len], $expected.as_bytes()); + } + + let mut s = String::new(); + itoa::fmt(&mut s, $value).unwrap(); + assert_eq!(s, $expected); + } + )* + } +} + +test!{ + test_u64_0(0u64, "0"), + test_u64_half(<u32>::max_value() as u64, "4294967295"), + test_u64_max(<u64>::max_value(), "18446744073709551615"), + test_i64_min(<i64>::min_value(), "-9223372036854775808"), + + test_i16_0(0i16, "0"), + test_i16_min(<i16>::min_value(), "-32768"), + + #[cfg(feature = "i128")] + test_u128_0(0u128, "0"), + #[cfg(feature = "i128")] + test_u128_max(<u128>::max_value(), "340282366920938463463374607431768211455"), + #[cfg(feature = "i128")] + test_i128_min(<i128>::min_value(), "-170141183460469231731687303715884105728") +} |