Import 'adler2' crate
Request Document: go/android-rust-importing-crates
For CL Reviewers: go/android3p#cl-review
Bug: 399467838
Test: m libadler2
Change-Id: I86b8ad56d3223abb55565bf5d6dc98ae124b1300
diff --git a/crates/adler2/.android-checksum.json b/crates/adler2/.android-checksum.json
new file mode 100644
index 0000000..b736029
--- /dev/null
+++ b/crates/adler2/.android-checksum.json
@@ -0,0 +1 @@
+{"package":null,"files":{".cargo-checksum.json":"843b45346fc0f6e726da6623abf365b03746a52a09ecbb6f9c2cb8ad087013c4","Android.bp":"2a0e5c9e9a23a4bd3832b60742e9483026ee9abfbd678fc74aeee256e6832155","CHANGELOG.md":"496dd8df370a5fd523f8fc9859a5ca2c0737456ae28d07bec5cd30dee337efaa","Cargo.toml":"7d518650bdb99eb251da38a34069fa1c10dec6e12b153a50cdd88a82fe4880dc","LICENSE":"73e842a46e7a5996ac314beb59dfe0ab84424a632a6772406eda5175bcce7bdd","LICENSE-APACHE":"73e842a46e7a5996ac314beb59dfe0ab84424a632a6772406eda5175bcce7bdd","METADATA":"a79e81613495926d8859711e8ee0584a2056893461531e65052e350210c5dd28","MODULE_LICENSE_APACHE2":"0d6f8afa3940b7f06bebee651376d43bc8b0d5b437337be2696d30377451e93a","README.md":"24e6a9f65121a741e602f68b70d01834a6360c18bebec606c6ab35dd138d08ce","RELEASE_PROCESS.md":"ee0fca303b9a08c9686e64bb6bee1db48b89653465b7764790071444d6fda006","benches/bench.rs":"73a53253655aa3ce82e1513bcaf9e712d25a518daf78a2ebb34b3ac412658c25","cargo_embargo.json":"e81a8293a8210fc4535b44bb9c665156a37008436b7508658c4d39de97765637","src/algo.rs":"958407ea1bba5a074c48acaf9feead44005a5a6255e0d8dc2c6558d058874d20","src/lib.rs":"8904398f21d6fa9cbb7ea84d147fc125ad5e43c214145dd52559a6b14a743ede"}}
\ No newline at end of file
diff --git a/crates/adler2/.cargo-checksum.json b/crates/adler2/.cargo-checksum.json
new file mode 100644
index 0000000..14e102f
--- /dev/null
+++ b/crates/adler2/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"CHANGELOG.md":"52435caf085b428cdb6171a34f4980f52aaaf541a3dced226c92eb82f69a48a7","Cargo.toml":"56b9cca6450964cbe772b6519bc048c2f56cc80e9261de1126d789c5e1951136","LICENSE-0BSD":"861399f8c21c042b110517e76dc6b63a2b334276c8cf17412fc3c8908ca8dc17","LICENSE-APACHE":"8ada45cd9f843acf64e4722ae262c622a2b3b3007c7310ef36ac1061a30f6adb","LICENSE-MIT":"23f18e03dc49df91622fe2a76176497404e46ced8a715d9d2b67a7446571cca3","README.md":"cd955d5d6a49161e6f7a04df4a5963581b66ed43fd5096b2dedca8e295efe4f9","RELEASE_PROCESS.md":"a86cd10fc70f167f8d00e9e4ce0c6b4ebdfa1865058390dffd1e0ad4d3e68d9d","benches/bench.rs":"d67bef1c7f36ed300a8fbcf9d50b9dfdead1fd340bf87a4d47d99a0c1c042c04","src/algo.rs":"932c2bc591d13fe4470185125617b5aaa660a3898f23b553acc85df0bf49dded","src/lib.rs":"4acd41668fe30daffa37084e7e223f268957b816afc1864ffb3f5d6d7adf0890"},"package":"512761e0bb2578dd7380c6baaa0f4ce03e84f95e960231d1dec8bf4d7d6e2627"}
\ No newline at end of file
diff --git a/crates/adler2/Android.bp b/crates/adler2/Android.bp
new file mode 100644
index 0000000..0e60b7e
--- /dev/null
+++ b/crates/adler2/Android.bp
@@ -0,0 +1,34 @@
+// This file is generated by cargo_embargo.
+// Do not modify this file because the changes will be overridden on upgrade.
+
+package {
+ default_applicable_licenses: ["external_rust_crates_adler2_license"],
+ default_team: "trendy_team_android_rust",
+}
+
+license {
+ name: "external_rust_crates_adler2_license",
+ visibility: [":__subpackages__"],
+ license_kinds: ["SPDX-license-identifier-Apache-2.0"],
+ license_text: ["LICENSE"],
+}
+
+rust_library {
+ name: "libadler2",
+ host_supported: true,
+ crate_name: "adler2",
+ cargo_env_compat: true,
+ cargo_pkg_version: "2.0.0",
+ crate_root: "src/lib.rs",
+ edition: "2021",
+ features: [
+ "default",
+ "std",
+ ],
+ apex_available: [
+ "//apex_available:platform",
+ "//apex_available:anyapex",
+ ],
+ product_available: true,
+ vendor_available: true,
+}
diff --git a/crates/adler2/CHANGELOG.md b/crates/adler2/CHANGELOG.md
new file mode 100644
index 0000000..9ddf18b
--- /dev/null
+++ b/crates/adler2/CHANGELOG.md
@@ -0,0 +1,77 @@
+# Changelog
+
+All notable changes to this project will be documented in this file.
+
+---
+## [2.0.0](https://github.com/Frommi/miniz_oxide/compare/1.0.2..2.0.0) - 2024-08-04
+
+First release of adler2 - fork of adler crate as the original is unmaintained and archived
+
+##### Changes since last version of Adler:
+
+### Bug Fixes
+
+- **(core)** change to rust 2021 edition, update repository info and links, update author info - ([867b115](https://github.com/Frommi/miniz_oxide/commit/867b115bad79bf62098f2acccc81bf53ec5a125d)) - oyvindln
+- **(core)** simplify some code and fix benches - ([128fb9c](https://github.com/Frommi/miniz_oxide/commit/128fb9cb6cad5c3a54fb0b6c68549d80b79a1fe0)) - oyvindln
+
+### Changelog of original adler crate
+
+---
+
+## [1.0.2 - 2021-02-26](https://github.com/jonas-schievink/adler/releases/tag/v1.0.2)
+
+- Fix doctest on big-endian systems ([#9]).
+
+[#9]: https://github.com/jonas-schievink/adler/pull/9
+
+## [1.0.1 - 2020-11-08](https://github.com/jonas-schievink/adler/releases/tag/v1.0.1)
+
+### Fixes
+
+- Fix documentation on docs.rs.
+
+## [1.0.0 - 2020-11-08](https://github.com/jonas-schievink/adler/releases/tag/v1.0.0)
+
+### Fixes
+
+- Fix `cargo test --no-default-features` ([#5]).
+
+### Improvements
+
+- Extended and clarified documentation.
+- Added more rustdoc examples.
+- Extended CI to test the crate with `--no-default-features`.
+
+### Breaking Changes
+
+- `adler32_reader` now takes its generic argument by value instead of as a `&mut`.
+- Renamed `adler32_reader` to `adler32`.
+
+## [0.2.3 - 2020-07-11](https://github.com/jonas-schievink/adler/releases/tag/v0.2.3)
+
+- Process 4 Bytes at a time, improving performance by up to 50% ([#2]).
+
+## [0.2.2 - 2020-06-27](https://github.com/jonas-schievink/adler/releases/tag/v0.2.2)
+
+- Bump MSRV to 1.31.0.
+
+## [0.2.1 - 2020-06-27](https://github.com/jonas-schievink/adler/releases/tag/v0.2.1)
+
+- Add a few `#[inline]` annotations to small functions.
+- Fix CI badge.
+- Allow integration into libstd.
+
+## [0.2.0 - 2020-06-27](https://github.com/jonas-schievink/adler/releases/tag/v0.2.0)
+
+- Support `#![no_std]` when using `default-features = false`.
+- Improve performance by around 7x.
+- Support Rust 1.8.0.
+- Improve API naming.
+
+## [0.1.0 - 2020-06-26](https://github.com/jonas-schievink/adler/releases/tag/v0.1.0)
+
+Initial release.
+
+
+[#2]: https://github.com/jonas-schievink/adler/pull/2
+[#5]: https://github.com/jonas-schievink/adler/pull/5
diff --git a/crates/adler2/Cargo.toml b/crates/adler2/Cargo.toml
new file mode 100644
index 0000000..d8610a8
--- /dev/null
+++ b/crates/adler2/Cargo.toml
@@ -0,0 +1,97 @@
+# 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 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]
+edition = "2021"
+name = "adler2"
+version = "2.0.0"
+authors = [
+ "Jonas Schievink <[email protected]>",
+ "oyvindln <[email protected]>",
+]
+build = false
+autobins = false
+autoexamples = false
+autotests = false
+autobenches = false
+description = "A simple clean-room implementation of the Adler-32 checksum"
+documentation = "https://docs.rs/adler2/"
+readme = "README.md"
+keywords = [
+ "checksum",
+ "integrity",
+ "hash",
+ "adler32",
+ "zlib",
+]
+categories = ["algorithms"]
+license = "0BSD OR MIT OR Apache-2.0"
+repository = "https://github.com/oyvindln/adler2"
+
+[package.metadata.docs.rs]
+rustdoc-args = ["--cfg=docsrs"]
+
+[package.metadata.release]
+no-dev-version = true
+pre-release-commit-message = "Release {{version}}"
+tag-message = "{{version}}"
+
+[[package.metadata.release.pre-release-replacements]]
+file = "CHANGELOG.md"
+replace = """
+## Unreleased
+
+No changes.
+
+## [{{version}} - {{date}}](https://github.com/jonas-schievink/adler/releases/tag/v{{version}})
+"""
+search = """
+## Unreleased
+"""
+
+[[package.metadata.release.pre-release-replacements]]
+file = "README.md"
+replace = 'adler = "{{version}}"'
+search = 'adler = "[a-z0-9\\.-]+"'
+
+[[package.metadata.release.pre-release-replacements]]
+file = "src/lib.rs"
+replace = "https://docs.rs/adler/{{version}}"
+search = 'https://docs.rs/adler/[a-z0-9\.-]+'
+
+[lib]
+name = "adler2"
+path = "src/lib.rs"
+
+[[bench]]
+name = "bench"
+path = "benches/bench.rs"
+harness = false
+
+[dependencies.compiler_builtins]
+version = "0.1.2"
+optional = true
+
+[dependencies.core]
+version = "1.0.0"
+optional = true
+package = "rustc-std-workspace-core"
+
+[dev-dependencies.criterion]
+version = "0.3.2"
+
+[features]
+default = ["std"]
+rustc-dep-of-std = [
+ "core",
+ "compiler_builtins",
+]
+std = []
diff --git a/crates/adler2/LICENSE b/crates/adler2/LICENSE
new file mode 120000
index 0000000..6b579aa
--- /dev/null
+++ b/crates/adler2/LICENSE
@@ -0,0 +1 @@
+LICENSE-APACHE
\ No newline at end of file
diff --git a/crates/adler2/LICENSE-APACHE b/crates/adler2/LICENSE-APACHE
new file mode 100644
index 0000000..c98d27d
--- /dev/null
+++ b/crates/adler2/LICENSE-APACHE
@@ -0,0 +1,201 @@
+ Apache License
+ Version 2.0, January 2004
+ https://www.apache.org/licenses/LICENSE-2.0
+
+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
+
+ https://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/crates/adler2/METADATA b/crates/adler2/METADATA
new file mode 100644
index 0000000..334e968
--- /dev/null
+++ b/crates/adler2/METADATA
@@ -0,0 +1,17 @@
+name: "adler2"
+description: "A simple clean-room implementation of the Adler-32 checksum"
+third_party {
+ version: "2.0.0"
+ license_type: NOTICE
+ last_upgrade_date {
+ year: 2025
+ month: 3
+ day: 6
+ }
+ homepage: "https://crates.io/crates/adler2"
+ identifier {
+ type: "Archive"
+ value: "https://static.crates.io/crates/adler2/adler2-2.0.0.crate"
+ version: "2.0.0"
+ }
+}
diff --git a/crates/adler2/MODULE_LICENSE_APACHE2 b/crates/adler2/MODULE_LICENSE_APACHE2
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/crates/adler2/MODULE_LICENSE_APACHE2
diff --git a/crates/adler2/README.md b/crates/adler2/README.md
new file mode 100644
index 0000000..25e7571
--- /dev/null
+++ b/crates/adler2/README.md
@@ -0,0 +1,46 @@
+# Adler-32 checksums for Rust
+
+This is a fork of the adler crate as the [original](https://github.com/jonas-schievink/adler) has been archived and is no longer updated by it's author
+
+[](https://crates.io/crates/adler)
+[](https://docs.rs/adler/)
+
+
+This crate provides a simple implementation of the Adler-32 checksum, used in
+the zlib compression format.
+
+Please refer to the [changelog](CHANGELOG.md) to see what changed in the last
+releases.
+
+## Features
+
+- Permissively licensed (0BSD) clean-room implementation.
+- Zero dependencies.
+- Zero `unsafe`.
+- Decent performance (3-4 GB/s) (see note).
+- Supports `#![no_std]` (with `default-features = false`).
+
+## Usage
+
+Add an entry to your `Cargo.toml`:
+
+```toml
+[dependencies]
+adler2 = "2.0.0"
+```
+
+Check the [API Documentation](https://docs.rs/adler/) for how to use the
+crate's functionality.
+
+## Rust version support
+
+Currently, this crate supports all Rust versions starting at Rust 1.56.0.
+
+Bumping the Minimum Supported Rust Version (MSRV) is *not* considered a breaking
+change, but will not be done without good reasons. The latest 3 stable Rust
+versions will always be supported no matter what.
+
+## Performance
+
+Due to the way the algorithm works this crate and the fact that it's not possible to use explicit simd in safe rust currently, this crate benefits drastically from being compiled with newer cpu instructions enabled (using e.g ```RUSTFLAGS=-C target-feature'+sse4.1``` or ```-C target-cpu=x86-64-v2```/```-C target-cpu=x86-64-v3``` arguments depending on what cpu support is being targeted.)
+Judging by the crate benchmarks, on a Ryzen 5600, compiling with SSE 4.1 (enabled in x86-64-v2 feature level) enabled can give a ~50-150% speedup, enabling the LZCNT instruction (enabled in x86-64-v3 feature level) can give a further ~50% speedup,
diff --git a/crates/adler2/RELEASE_PROCESS.md b/crates/adler2/RELEASE_PROCESS.md
new file mode 100644
index 0000000..71a3673
--- /dev/null
+++ b/crates/adler2/RELEASE_PROCESS.md
@@ -0,0 +1,13 @@
+# What to do to publish a new release
+
+1. Ensure all notable changes are in the changelog under "Unreleased".
+
+2. Execute `cargo release <level>` to bump version(s), tag and publish
+ everything. External subcommand, must be installed with `cargo install
+ cargo-release`.
+
+ `<level>` can be one of `major|minor|patch`. If this is the first release
+ (`0.1.0`), use `minor`, since the version starts out as `0.0.0`.
+
+3. Go to the GitHub releases, edit the just-pushed tag. Copy the release notes
+ from the changelog.
diff --git a/crates/adler2/benches/bench.rs b/crates/adler2/benches/bench.rs
new file mode 100644
index 0000000..29d87c1
--- /dev/null
+++ b/crates/adler2/benches/bench.rs
@@ -0,0 +1,109 @@
+extern crate adler2;
+extern crate criterion;
+
+use adler2::{adler32_slice, Adler32};
+use criterion::{criterion_group, criterion_main, Criterion, Throughput};
+
+fn simple(c: &mut Criterion) {
+ {
+ const SIZE: usize = 100;
+
+ let mut group = c.benchmark_group("simple-100b");
+ group.throughput(Throughput::Bytes(SIZE as u64));
+ group.bench_function("zeroes-100", |bencher| {
+ bencher.iter(|| {
+ adler32_slice(&[0; SIZE]);
+ });
+ });
+ group.bench_function("ones-100", |bencher| {
+ bencher.iter(|| {
+ adler32_slice(&[0xff; SIZE]);
+ });
+ });
+ }
+
+ {
+ const SIZE: usize = 1024;
+
+ let mut group = c.benchmark_group("simple-1k");
+ group.throughput(Throughput::Bytes(SIZE as u64));
+
+ group.bench_function("zeroes-1k", |bencher| {
+ bencher.iter(|| {
+ adler32_slice(&[0; SIZE]);
+ });
+ });
+
+ group.bench_function("ones-1k", |bencher| {
+ bencher.iter(|| {
+ adler32_slice(&[0xff; SIZE]);
+ });
+ });
+ }
+
+ {
+ const SIZE: usize = 1024 * 1024;
+
+ let mut group = c.benchmark_group("simple-1m");
+ group.throughput(Throughput::Bytes(SIZE as u64));
+ group.bench_function("zeroes-1m", |bencher| {
+ bencher.iter(|| {
+ adler32_slice(&[0; SIZE]);
+ });
+ });
+
+ group.bench_function("ones-1m", |bencher| {
+ bencher.iter(|| {
+ adler32_slice(&[0xff; SIZE]);
+ });
+ });
+ }
+}
+
+fn chunked(c: &mut Criterion) {
+ const SIZE: usize = 16 * 1024 * 1024;
+
+ let data = vec![0xAB; SIZE];
+
+ let mut group = c.benchmark_group("chunked-16m");
+ group.throughput(Throughput::Bytes(SIZE as u64));
+ group.bench_function("5552", |bencher| {
+ bencher.iter(|| {
+ let mut h = Adler32::new();
+ for chunk in data.chunks(5552) {
+ h.write_slice(chunk);
+ }
+ h.checksum()
+ });
+ });
+ group.bench_function("8k", |bencher| {
+ bencher.iter(|| {
+ let mut h = Adler32::new();
+ for chunk in data.chunks(8 * 1024) {
+ h.write_slice(chunk);
+ }
+ h.checksum()
+ });
+ });
+ group.bench_function("64k", |bencher| {
+ bencher.iter(|| {
+ let mut h = Adler32::new();
+ for chunk in data.chunks(64 * 1024) {
+ h.write_slice(chunk);
+ }
+ h.checksum()
+ });
+ });
+ group.bench_function("1m", |bencher| {
+ bencher.iter(|| {
+ let mut h = Adler32::new();
+ for chunk in data.chunks(1024 * 1024) {
+ h.write_slice(chunk);
+ }
+ h.checksum()
+ });
+ });
+}
+
+criterion_group!(benches, simple, chunked);
+criterion_main!(benches);
diff --git a/crates/adler2/cargo_embargo.json b/crates/adler2/cargo_embargo.json
new file mode 100644
index 0000000..a15eb22
--- /dev/null
+++ b/crates/adler2/cargo_embargo.json
@@ -0,0 +1 @@
+{"run_cargo": false}
\ No newline at end of file
diff --git a/crates/adler2/src/algo.rs b/crates/adler2/src/algo.rs
new file mode 100644
index 0000000..14addd8
--- /dev/null
+++ b/crates/adler2/src/algo.rs
@@ -0,0 +1,155 @@
+use crate::Adler32;
+use std::ops::{AddAssign, MulAssign, RemAssign};
+
+impl Adler32 {
+ pub(crate) fn compute(&mut self, bytes: &[u8]) {
+ // The basic algorithm is, for every byte:
+ // a = (a + byte) % MOD
+ // b = (b + a) % MOD
+ // where MOD = 65521.
+ //
+ // For efficiency, we can defer the `% MOD` operations as long as neither a nor b overflows:
+ // - Between calls to `write`, we ensure that a and b are always in range 0..MOD.
+ // - We use 32-bit arithmetic in this function.
+ // - Therefore, a and b must not increase by more than 2^32-MOD without performing a `% MOD`
+ // operation.
+ //
+ // According to Wikipedia, b is calculated as follows for non-incremental checksumming:
+ // b = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n*1 (mod 65521)
+ // Where n is the number of bytes and Di is the i-th Byte. We need to change this to account
+ // for the previous values of a and b, as well as treat every input Byte as being 255:
+ // b_inc = n×255 + (n-1)×255 + ... + 255 + n*65520
+ // Or in other words:
+ // b_inc = n*65520 + n(n+1)/2*255
+ // The max chunk size is thus the largest value of n so that b_inc <= 2^32-65521.
+ // 2^32-65521 = n*65520 + n(n+1)/2*255
+ // Plugging this into an equation solver since I can't math gives n = 5552.18..., so 5552.
+ //
+ // On top of the optimization outlined above, the algorithm can also be parallelized with a
+ // bit more work:
+ //
+ // Note that b is a linear combination of a vector of input bytes (D1, ..., Dn).
+ //
+ // If we fix some value k<N and rewrite indices 1, ..., N as
+ //
+ // 1_1, 1_2, ..., 1_k, 2_1, ..., 2_k, ..., (N/k)_k,
+ //
+ // then we can express a and b in terms of sums of smaller sequences kb and ka:
+ //
+ // ka(j) := D1_j + D2_j + ... + D(N/k)_j where j <= k
+ // kb(j) := (N/k)*D1_j + (N/k-1)*D2_j + ... + D(N/k)_j where j <= k
+ //
+ // a = ka(1) + ka(2) + ... + ka(k) + 1
+ // b = k*(kb(1) + kb(2) + ... + kb(k)) - 1*ka(2) - ... - (k-1)*ka(k) + N
+ //
+ // We use this insight to unroll the main loop and process k=4 bytes at a time.
+ // The resulting code is highly amenable to SIMD acceleration, although the immediate speedups
+ // stem from increased pipeline parallelism rather than auto-vectorization.
+ //
+ // This technique is described in-depth (here:)[https://software.intel.com/content/www/us/\
+ // en/develop/articles/fast-computation-of-fletcher-checksums.html]
+
+ const MOD: u32 = 65521;
+ const CHUNK_SIZE: usize = 5552 * 4;
+
+ let mut a = u32::from(self.a);
+ let mut b = u32::from(self.b);
+ let mut a_vec = U32X4([0; 4]);
+ let mut b_vec = a_vec;
+
+ let (bytes, remainder) = bytes.split_at(bytes.len() - bytes.len() % 4);
+
+ // iterate over 4 bytes at a time
+ let chunk_iter = bytes.chunks_exact(CHUNK_SIZE);
+ let remainder_chunk = chunk_iter.remainder();
+ for chunk in chunk_iter {
+ for byte_vec in chunk.chunks_exact(4) {
+ let val = U32X4::from(byte_vec);
+ a_vec += val;
+ b_vec += a_vec;
+ }
+
+ b += CHUNK_SIZE as u32 * a;
+ a_vec %= MOD;
+ b_vec %= MOD;
+ b %= MOD;
+ }
+ // special-case the final chunk because it may be shorter than the rest
+ for byte_vec in remainder_chunk.chunks_exact(4) {
+ let val = U32X4::from(byte_vec);
+ a_vec += val;
+ b_vec += a_vec;
+ }
+ b += remainder_chunk.len() as u32 * a;
+ a_vec %= MOD;
+ b_vec %= MOD;
+ b %= MOD;
+
+ // combine the sub-sum results into the main sum
+ b_vec *= 4;
+ b_vec.0[1] += MOD - a_vec.0[1];
+ b_vec.0[2] += (MOD - a_vec.0[2]) * 2;
+ b_vec.0[3] += (MOD - a_vec.0[3]) * 3;
+ for &av in a_vec.0.iter() {
+ a += av;
+ }
+ for &bv in b_vec.0.iter() {
+ b += bv;
+ }
+
+ // iterate over the remaining few bytes in serial
+ for &byte in remainder.iter() {
+ a += u32::from(byte);
+ b += a;
+ }
+
+ self.a = (a % MOD) as u16;
+ self.b = (b % MOD) as u16;
+ }
+}
+
+#[derive(Copy, Clone)]
+struct U32X4([u32; 4]);
+
+impl U32X4 {
+ #[inline]
+ fn from(bytes: &[u8]) -> Self {
+ U32X4([
+ u32::from(bytes[0]),
+ u32::from(bytes[1]),
+ u32::from(bytes[2]),
+ u32::from(bytes[3]),
+ ])
+ }
+}
+
+impl AddAssign<Self> for U32X4 {
+ #[inline]
+ fn add_assign(&mut self, other: Self) {
+ // Implement this in a primitive manner to help out the compiler a bit.
+ self.0[0] += other.0[0];
+ self.0[1] += other.0[1];
+ self.0[2] += other.0[2];
+ self.0[3] += other.0[3];
+ }
+}
+
+impl RemAssign<u32> for U32X4 {
+ #[inline]
+ fn rem_assign(&mut self, quotient: u32) {
+ self.0[0] %= quotient;
+ self.0[1] %= quotient;
+ self.0[2] %= quotient;
+ self.0[3] %= quotient;
+ }
+}
+
+impl MulAssign<u32> for U32X4 {
+ #[inline]
+ fn mul_assign(&mut self, rhs: u32) {
+ self.0[0] *= rhs;
+ self.0[1] *= rhs;
+ self.0[2] *= rhs;
+ self.0[3] *= rhs;
+ }
+}
diff --git a/crates/adler2/src/lib.rs b/crates/adler2/src/lib.rs
new file mode 100644
index 0000000..559108a
--- /dev/null
+++ b/crates/adler2/src/lib.rs
@@ -0,0 +1,287 @@
+//! Adler-32 checksum implementation.
+//!
+//! This implementation features:
+//!
+//! - Permissively licensed (0BSD) clean-room implementation.
+//! - Zero dependencies.
+//! - Zero `unsafe`.
+//! - Decent performance (3-4 GB/s).
+//! - `#![no_std]` support (with `default-features = false`).
+
+#![doc(html_root_url = "https://docs.rs/adler2/2.0.0")]
+// Deny a few warnings in doctests, since rustdoc `allow`s many warnings by default
+#![doc(test(attr(deny(unused_imports, unused_must_use))))]
+#![cfg_attr(docsrs, feature(doc_cfg))]
+#![warn(missing_debug_implementations)]
+#![forbid(unsafe_code)]
+#![cfg_attr(not(feature = "std"), no_std)]
+
+#[cfg(not(feature = "std"))]
+extern crate core as std;
+
+mod algo;
+
+use std::hash::Hasher;
+
+#[cfg(feature = "std")]
+use std::io::{self, BufRead};
+
+/// Adler-32 checksum calculator.
+///
+/// An instance of this type is equivalent to an Adler-32 checksum: It can be created in the default
+/// state via [`new`] (or the provided `Default` impl), or from a precalculated checksum via
+/// [`from_checksum`], and the currently stored checksum can be fetched via [`checksum`].
+///
+/// This type also implements `Hasher`, which makes it easy to calculate Adler-32 checksums of any
+/// type that implements or derives `Hash`. This also allows using Adler-32 in a `HashMap`, although
+/// that is not recommended (while every checksum is a hash function, they are not necessarily a
+/// good one).
+///
+/// # Examples
+///
+/// Basic, piecewise checksum calculation:
+///
+/// ```
+/// use adler2::Adler32;
+///
+/// let mut adler = Adler32::new();
+///
+/// adler.write_slice(&[0, 1, 2]);
+/// adler.write_slice(&[3, 4, 5]);
+///
+/// assert_eq!(adler.checksum(), 0x00290010);
+/// ```
+///
+/// Using `Hash` to process structures:
+///
+/// ```
+/// use std::hash::Hash;
+/// use adler2::Adler32;
+///
+/// #[derive(Hash)]
+/// struct Data {
+/// byte: u8,
+/// word: u16,
+/// big: u64,
+/// }
+///
+/// let mut adler = Adler32::new();
+///
+/// let data = Data { byte: 0x1F, word: 0xABCD, big: !0 };
+/// data.hash(&mut adler);
+///
+/// // hash value depends on architecture endianness
+/// if cfg!(target_endian = "little") {
+/// assert_eq!(adler.checksum(), 0x33410990);
+/// }
+/// if cfg!(target_endian = "big") {
+/// assert_eq!(adler.checksum(), 0x331F0990);
+/// }
+///
+/// ```
+///
+/// [`new`]: #method.new
+/// [`from_checksum`]: #method.from_checksum
+/// [`checksum`]: #method.checksum
+#[derive(Debug, Copy, Clone)]
+pub struct Adler32 {
+ a: u16,
+ b: u16,
+}
+
+impl Adler32 {
+ /// Creates a new Adler-32 instance with default state.
+ #[inline]
+ pub fn new() -> Self {
+ Self::default()
+ }
+
+ /// Creates an `Adler32` instance from a precomputed Adler-32 checksum.
+ ///
+ /// This allows resuming checksum calculation without having to keep the `Adler32` instance
+ /// around.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// # use adler2::Adler32;
+ /// let parts = [
+ /// "rust",
+ /// "acean",
+ /// ];
+ /// let whole = adler2::adler32_slice(b"rustacean");
+ ///
+ /// let mut sum = Adler32::new();
+ /// sum.write_slice(parts[0].as_bytes());
+ /// let partial = sum.checksum();
+ ///
+ /// // ...later
+ ///
+ /// let mut sum = Adler32::from_checksum(partial);
+ /// sum.write_slice(parts[1].as_bytes());
+ /// assert_eq!(sum.checksum(), whole);
+ /// ```
+ #[inline]
+ pub const fn from_checksum(sum: u32) -> Self {
+ Adler32 {
+ a: sum as u16,
+ b: (sum >> 16) as u16,
+ }
+ }
+
+ /// Returns the calculated checksum at this point in time.
+ #[inline]
+ pub fn checksum(&self) -> u32 {
+ (u32::from(self.b) << 16) | u32::from(self.a)
+ }
+
+ /// Adds `bytes` to the checksum calculation.
+ ///
+ /// If efficiency matters, this should be called with Byte slices that contain at least a few
+ /// thousand Bytes.
+ pub fn write_slice(&mut self, bytes: &[u8]) {
+ self.compute(bytes);
+ }
+}
+
+impl Default for Adler32 {
+ #[inline]
+ fn default() -> Self {
+ Adler32 { a: 1, b: 0 }
+ }
+}
+
+impl Hasher for Adler32 {
+ #[inline]
+ fn finish(&self) -> u64 {
+ u64::from(self.checksum())
+ }
+
+ fn write(&mut self, bytes: &[u8]) {
+ self.write_slice(bytes);
+ }
+}
+
+/// Calculates the Adler-32 checksum of a byte slice.
+///
+/// This is a convenience function around the [`Adler32`] type.
+///
+/// [`Adler32`]: struct.Adler32.html
+pub fn adler32_slice(data: &[u8]) -> u32 {
+ let mut h = Adler32::new();
+ h.write_slice(data);
+ h.checksum()
+}
+
+/// Calculates the Adler-32 checksum of a `BufRead`'s contents.
+///
+/// The passed `BufRead` implementor will be read until it reaches EOF (or until it reports an
+/// error).
+///
+/// If you only have a `Read` implementor, you can wrap it in `std::io::BufReader` before calling
+/// this function.
+///
+/// # Errors
+///
+/// Any error returned by the reader are bubbled up by this function.
+///
+/// # Examples
+///
+/// ```no_run
+/// # fn run() -> Result<(), Box<dyn std::error::Error>> {
+/// use adler2::adler32;
+///
+/// use std::fs::File;
+/// use std::io::BufReader;
+///
+/// let file = File::open("input.txt")?;
+/// let mut file = BufReader::new(file);
+///
+/// adler32(&mut file)?;
+/// # Ok(()) }
+/// # fn main() { run().unwrap() }
+/// ```
+#[cfg(feature = "std")]
+#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
+pub fn adler32<R: BufRead>(mut reader: R) -> io::Result<u32> {
+ let mut h = Adler32::new();
+ loop {
+ let len = {
+ let buf = reader.fill_buf()?;
+ if buf.is_empty() {
+ return Ok(h.checksum());
+ }
+
+ h.write_slice(buf);
+ buf.len()
+ };
+ reader.consume(len);
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ #[test]
+ fn zeroes() {
+ assert_eq!(adler32_slice(&[]), 1);
+ assert_eq!(adler32_slice(&[0]), 1 | 1 << 16);
+ assert_eq!(adler32_slice(&[0, 0]), 1 | 2 << 16);
+ assert_eq!(adler32_slice(&[0; 100]), 0x00640001);
+ assert_eq!(adler32_slice(&[0; 1024]), 0x04000001);
+ assert_eq!(adler32_slice(&[0; 1024 * 1024]), 0x00f00001);
+ }
+
+ #[test]
+ fn ones() {
+ assert_eq!(adler32_slice(&[0xff; 1024]), 0x79a6fc2e);
+ assert_eq!(adler32_slice(&[0xff; 1024 * 1024]), 0x8e88ef11);
+ }
+
+ #[test]
+ fn mixed() {
+ assert_eq!(adler32_slice(&[1]), 2 | 2 << 16);
+ assert_eq!(adler32_slice(&[40]), 41 | 41 << 16);
+
+ assert_eq!(adler32_slice(&[0xA5; 1024 * 1024]), 0xd5009ab1);
+ }
+
+ /// Example calculation from https://en.wikipedia.org/wiki/Adler-32.
+ #[test]
+ fn wiki() {
+ assert_eq!(adler32_slice(b"Wikipedia"), 0x11E60398);
+ }
+
+ #[test]
+ fn resume() {
+ let mut adler = Adler32::new();
+ adler.write_slice(&[0xff; 1024]);
+ let partial = adler.checksum();
+ assert_eq!(partial, 0x79a6fc2e); // from above
+ adler.write_slice(&[0xff; 1024 * 1024 - 1024]);
+ assert_eq!(adler.checksum(), 0x8e88ef11); // from above
+
+ // Make sure that we can resume computing from the partial checksum via `from_checksum`.
+ let mut adler = Adler32::from_checksum(partial);
+ adler.write_slice(&[0xff; 1024 * 1024 - 1024]);
+ assert_eq!(adler.checksum(), 0x8e88ef11); // from above
+ }
+
+ #[cfg(feature = "std")]
+ #[test]
+ fn bufread() {
+ use std::io::BufReader;
+ fn test(data: &[u8], checksum: u32) {
+ // `BufReader` uses an 8 KB buffer, so this will test buffer refilling.
+ let mut buf = BufReader::new(data);
+ let real_sum = adler32(&mut buf).unwrap();
+ assert_eq!(checksum, real_sum);
+ }
+
+ test(&[], 1);
+ test(&[0; 1024], 0x04000001);
+ test(&[0; 1024 * 1024], 0x00f00001);
+ test(&[0xA5; 1024 * 1024], 0xd5009ab1);
+ }
+}
diff --git a/pseudo_crate/Cargo.lock b/pseudo_crate/Cargo.lock
index 3c8300e..29ed2b0 100644
--- a/pseudo_crate/Cargo.lock
+++ b/pseudo_crate/Cargo.lock
@@ -99,6 +99,7 @@
dependencies = [
"aarch64-paging",
"acpi",
+ "adler2",
"ahash 0.8.11",
"aho-corasick",
"android_bp",
diff --git a/pseudo_crate/Cargo.toml b/pseudo_crate/Cargo.toml
index 8ca6d32..ac71ed0 100644
--- a/pseudo_crate/Cargo.toml
+++ b/pseudo_crate/Cargo.toml
@@ -9,6 +9,7 @@
# go/keep-sorted start
aarch64-paging = "=0.7.0"
acpi = "=5.2.0"
+adler2 = "=2.0.0"
ahash = "=0.8.11"
aho-corasick = "=0.7.20"
android_bp = "=0.3.0"
diff --git a/pseudo_crate/crate-list.txt b/pseudo_crate/crate-list.txt
index 91c40e3..1ca037e 100644
--- a/pseudo_crate/crate-list.txt
+++ b/pseudo_crate/crate-list.txt
@@ -1,5 +1,6 @@
aarch64-paging
acpi
+adler2
ahash
aho-corasick
android_bp
