From a74f046110cd5393c8a618c30b79e22d06dfe081 Mon Sep 17 00:00:00 2001 From: DongHun Kwak Date: Thu, 6 Apr 2023 09:10:44 +0900 Subject: [PATCH] Import qoi 0.4.1 --- .cargo_vcs_info.json | 6 + .github/workflows/ci.yml | 37 +++ .gitignore | 7 + .gitmodules | 3 + Cargo.toml | 66 +++++ Cargo.toml.orig | 45 ++++ LICENSE-APACHE | 201 ++++++++++++++ LICENSE-MIT | 25 ++ README.md | 66 +++++ doc/qoi-specification.pdf | Bin 0 -> 39373 bytes ext/qoi/.gitignore | 5 + ext/qoi/README.md | 92 +++++++ ext/qoi/qoi.h | 671 ++++++++++++++++++++++++++++++++++++++++++++++ ext/qoi/qoibench.c | 650 ++++++++++++++++++++++++++++++++++++++++++++ ext/qoi/qoiconv.c | 106 ++++++++ ext/qoi/qoifuzz.c | 51 ++++ rustfmt.toml | 7 + src/consts.rs | 17 ++ src/decode.rs | 396 +++++++++++++++++++++++++++ src/encode.rs | 210 +++++++++++++++ src/error.rs | 82 ++++++ src/header.rs | 120 +++++++++ src/lib.rs | 95 +++++++ src/pixel.rs | 183 +++++++++++++ src/types.rs | 113 ++++++++ src/utils.rs | 107 ++++++++ tests/common.rs | 12 + tests/test_chunks.rs | 211 +++++++++++++++ tests/test_gen.rs | 313 +++++++++++++++++++++ tests/test_misc.rs | 6 + tests/test_ref.rs | 114 ++++++++ 31 files changed, 4017 insertions(+) create mode 100644 .cargo_vcs_info.json create mode 100644 .github/workflows/ci.yml create mode 100644 .gitignore create mode 100644 .gitmodules create mode 100644 Cargo.toml create mode 100644 Cargo.toml.orig create mode 100644 LICENSE-APACHE create mode 100644 LICENSE-MIT create mode 100644 README.md create mode 100644 doc/qoi-specification.pdf create mode 100644 ext/qoi/.gitignore create mode 100644 ext/qoi/README.md create mode 100644 ext/qoi/qoi.h create mode 100644 ext/qoi/qoibench.c create mode 100644 ext/qoi/qoiconv.c create mode 100644 ext/qoi/qoifuzz.c create mode 100644 rustfmt.toml create mode 100644 src/consts.rs create mode 100644 src/decode.rs create mode 100644 src/encode.rs create mode 100644 src/error.rs create mode 100644 src/header.rs create mode 100644 src/lib.rs create mode 100644 src/pixel.rs create mode 100644 src/types.rs create mode 100644 src/utils.rs create mode 100644 tests/common.rs create mode 100644 tests/test_chunks.rs create mode 100644 tests/test_gen.rs create mode 100644 tests/test_misc.rs create mode 100644 tests/test_ref.rs diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json new file mode 100644 index 0000000..fdb88a6 --- /dev/null +++ b/.cargo_vcs_info.json @@ -0,0 +1,6 @@ +{ + "git": { + "sha1": "e97077e527618a07413f7895a3792a6859afac59" + }, + "path_in_vcs": "" +} \ No newline at end of file diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml new file mode 100644 index 0000000..8f9f42a --- /dev/null +++ b/.github/workflows/ci.yml @@ -0,0 +1,37 @@ +on: + push: + branches: [master] + pull_request: + branches: [master] +name: CI +env: + CARGO_TERM_COLOR: always + HOST: x86_64-unknown-linux-gnu + RUSTFLAGS: "-D warnings" +jobs: + tests: + runs-on: ubuntu-latest + strategy: + matrix: + rust: [stable, beta, nightly, 1.61.0] # MSRV=1.61 + steps: + - uses: actions/checkout@v2 + with: {submodules: true} + - uses: actions-rs/toolchain@v1 + with: {profile: minimal, toolchain: '${{ matrix.rust }}', override: true} + - run: cargo test + reference: + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + with: {submodules: true} + - uses: actions-rs/toolchain@v1 + with: {profile: minimal, toolchain: stable, override: true} + - run: cargo test --features=reference + clippy: + runs-on: ubuntu-latest + steps: + - uses: actions/checkout@v2 + - uses: actions-rs/toolchain@v1 + with: {profile: minimal, toolchain: beta, override: true, components: clippy} + - run: cargo clippy diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..082c762 --- /dev/null +++ b/.gitignore @@ -0,0 +1,7 @@ +**/target/ +**/Cargo.lock +/.idea +.DS_Store +/suite/ +/tmp/ +/fuzz/coverage/ diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..0bafc7c --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "ext/qoi"] + path = ext/qoi + url = https://github.com/phoboslab/qoi.git diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..93c69d6 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,66 @@ +# 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" +rust-version = "1.61.0" +name = "qoi" +version = "0.4.1" +authors = ["Ivan Smirnov "] +exclude = ["assets/*"] +description = "VERY fast encoder/decoder for QOI (Quite Okay Image) format" +homepage = "https://github.com/aldanor/qoi-rust" +documentation = "https://docs.rs/qoi" +readme = "README.md" +keywords = [ + "qoi", + "graphics", + "image", + "encoding", +] +categories = [ + "multimedia::images", + "multimedia::encoding", +] +license = "MIT/Apache-2.0" +repository = "https://github.com/aldanor/qoi-rust" + +[profile.test] +opt-level = 3 + +[lib] +name = "qoi" +path = "src/lib.rs" +doctest = false + +[dependencies.bytemuck] +version = "1.12" + +[dev-dependencies.anyhow] +version = "1.0" + +[dev-dependencies.cfg-if] +version = "1.0" + +[dev-dependencies.png] +version = "0.17" + +[dev-dependencies.rand] +version = "0.8" + +[dev-dependencies.walkdir] +version = "2.3" + +[features] +alloc = [] +default = ["std"] +reference = [] +std = [] diff --git a/Cargo.toml.orig b/Cargo.toml.orig new file mode 100644 index 0000000..8417cc7 --- /dev/null +++ b/Cargo.toml.orig @@ -0,0 +1,45 @@ +[package] +name = "qoi" +version = "0.4.1" +description = "VERY fast encoder/decoder for QOI (Quite Okay Image) format" +authors = ["Ivan Smirnov "] +edition = "2021" +readme = "README.md" +license = "MIT/Apache-2.0" +repository = "https://github.com/aldanor/qoi-rust" +homepage = "https://github.com/aldanor/qoi-rust" +documentation = "https://docs.rs/qoi" +categories = ["multimedia::images", "multimedia::encoding"] +keywords = ["qoi", "graphics", "image", "encoding"] +exclude = [ + "assets/*", +] +rust-version = "1.61.0" + +[features] +default = ["std"] +alloc = [] # provides access to `Vec` without enabling `std` mode +std = [] # std mode (enabled by default) - provides access to `std::io`, `Error` and `Vec` +reference = [] # follows reference encoder implementation precisely, but may be slightly slower + +[dependencies] +bytemuck = "1.12" + +[workspace] +members = ["libqoi", "bench"] + +[dev-dependencies] +anyhow = "1.0" +png = "0.17" +walkdir = "2.3" +cfg-if = "1.0" +rand = "0.8" +libqoi = { path = "libqoi"} + +[lib] +name = "qoi" +path = "src/lib.rs" +doctest = false + +[profile.test] +opt-level = 3 diff --git a/LICENSE-APACHE b/LICENSE-APACHE new file mode 100644 index 0000000..11069ed --- /dev/null +++ b/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/LICENSE-MIT b/LICENSE-MIT new file mode 100644 index 0000000..7b24776 --- /dev/null +++ b/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2022 Ivan Smirnov + +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/README.md b/README.md new file mode 100644 index 0000000..315d006 --- /dev/null +++ b/README.md @@ -0,0 +1,66 @@ +# [qoi](https://crates.io/crates/qoi) + +[![Build](https://github.com/aldanor/qoi-rust/workflows/CI/badge.svg)](https://github.com/aldanor/qoi-rust/actions?query=branch%3Amaster) +[![Latest Version](https://img.shields.io/crates/v/qoi.svg)](https://crates.io/crates/qoi) +[![Documentation](https://img.shields.io/docsrs/qoi)](https://docs.rs/qoi) +[![Apache 2.0](https://img.shields.io/badge/License-Apache%202.0-blue.svg)](https://opensource.org/licenses/Apache-2.0) +[![MIT](https://img.shields.io/badge/License-MIT-blue.svg)](https://opensource.org/licenses/MIT) +[![unsafe forbidden](https://img.shields.io/badge/unsafe-forbidden-success.svg)](https://github.com/rust-secure-code/safety-dance) + +Fast encoder/decoder for [QOI image format](https://qoiformat.org/), implemented in pure and safe Rust. + +- One of the [fastest](#benchmarks) QOI encoders/decoders out there. +- Compliant with the [latest](https://qoiformat.org/qoi-specification.pdf) QOI format specification. +- Zero unsafe code. +- Supports decoding from / encoding to `std::io` streams directly. +- `no_std` support. +- Roundtrip-tested vs the reference C implementation; fuzz-tested. + +### Examples + +```rust +use qoi::{encode_to_vec, decode_to_vec}; + +let encoded = encode_to_vec(&pixels, width, height)?; +let (header, decoded) = decode_to_vec(&encoded)?; + +assert_eq!(header.width, width); +assert_eq!(header.height, height); +assert_eq!(decoded, pixels); +``` + +### Benchmarks + +``` + decode:Mp/s encode:Mp/s decode:MB/s encode:MB/s +qoi.h 282.9 225.3 978.3 778.9 +qoi-rust 427.4 290.0 1477.7 1002.9 +``` + +- Reference C implementation: + [phoboslab/qoi@00e34217](https://github.com/phoboslab/qoi/commit/00e34217). +- Benchmark timings were collected on an Apple M1 laptop. +- 2846 images from the suite provided upstream + ([tarball](https://phoboslab.org/files/qoibench/qoi_benchmark_suite.tar)): + all pngs except two with broken checksums. +- 1.32 GPixels in total with 4.46 GB of raw pixel data. + +Benchmarks have also been run for all of the other Rust implementations +of QOI for comparison purposes and, at the time of writing this document, +this library proved to be the fastest one by a noticeable margin. + +### Rust version + +The minimum required Rust version for the latest crate version is 1.61.0. + +### `no_std` + +This crate supports `no_std` mode. By default, std is enabled via the `std` +feature. You can deactivate the `default-features` to target core instead. +In that case anything related to `std::io`, `std::error::Error` and heap +allocations is disabled. There is an additional `alloc` feature that can +be activated to bring back the support for heap allocations. + +### License + +This project is dual-licensed under MIT and Apache 2.0. diff --git a/doc/qoi-specification.pdf b/doc/qoi-specification.pdf new file mode 100644 index 0000000000000000000000000000000000000000..b94ff691ba18e087f7e643001db735648d8e51a5 GIT binary patch literal 39373 zcmd42bx>SO*M}Pj?(Q;pa0VG1g1dWgcXx;2?hxD|xVr`m1ot38gS$Iik|Xaq^;y-e z`^ROdnd#NCyI1c$vwqKBLm@9LN)KdUgQI9Ts(gTB1uy|@4J_bzcmRyj#x|x-W&pNV zlOh}d0ALg~w{kLeczw0fcQO_>HncS|hU4Rdb98br*0+Xp%h=NLj9KD{e_74`sJ>=* zoZd*vC#*1J?T0|=IQZjuWX#&-#Lo$3u<>wiAckm2R?ehm^~pyi(Rv~I$2r*-`XY4K zbY=~@xwgT)LYT8EsEGs~9?*{*4iC}!E=GR@!yh~GJ#fveT!tc&@^f5Z_y>j_Q+)tX#q>Qg+G)BOtn~Yv37Vd% z4|UUc^65oU?+XT}>fy@4jJ0u`1N~8O`bX8#uH$Ror*A_J&=^6rlIJDw6tP6N(iAbC zy^{@<^xG2Tc_S`QKpc?UrxpZz3T-F@@qvOB1oa%gC~QWW>Nq1ww;o6-0pW%&A*b*` z;wPlB;AIo6ow5MVxgj+8M?}i-lB9P~R>sRDI%$9zSfz9m(porcb*o4d`&m5Z_f8H1 zW(K5c;BbC~-9)@>1vNqlc4@7rtvUh;*;=~j)a6~)Sv0*!l=CU*cf2#UGXhQq|e>hDNv^?UmINGxcH zq`?K~hY<5yQ14@^k>cN>^iHCQBb}Cj1FSVx8WTMM$K0_C90nW0X*0Zy?P#?C*)U>!czv)_5*D$3sRbVZh}HP=+~EF`F5$^18SF5q zWjcoqZ+72Ha+3!8y|I)cC@#?hkvnBX2CuJ@TrB&Mw}aPx0IQG)MpZQr1(QdhlMH5p z25mqOXXz_6IAs_#DRV6<0q+@l}8ym?PdX~a$)fh<3h78G!DtL zpr84fAqSE}yvtjU%YBYVed|U>c%#b?$Sh?S(y#?jN4g2|pQH_>>O6wX6b>ztlkNeB z(O)2eRv7$p|Ne*-B^V?dwu}nKO81!aj+Q>-ZDhLhi0qU{59TQOlu>+6Dd9T#dyZ}7 zH)wL}(t~_8+7fx)mi)O1dWzy7DXscIPyw=U6<1Pt*DE@`m;C8Gn($!5zT_%Xo(Y=A zLvVCux@1Lp=raapdvou%A9Qw%_sI==#f1^SNVTUHZAyFj=3Be!EQ`-)7QvtGgjmI{ zw);M0`xIP~z3?Ik-JKt;Hg-Eh?~!JY+nnBBY3k9kJ%v88cjFGmOMO1QvbB6Cq$OBu zMWo-7wO*y6U;qaO@4RWMmfpV%he^W(R!i5Psi^wM(>3|SiAN#a`F=knk{0>mBrjmTcv{Pg+=#ZEUY+sBJc^o|@o;I4dRScH0;EDp}x!*BHk z;rxf`9uuuizZqZZ2ytERt}oW!VcjSC;wOYmxX9+c3D&->Znwc+r#LiO54)}mZ@RNF zy%`k7bq@q=Ar_ubMg3pPVQ}Q~=o60K;Cc_D$F;`#p$d!=k@#lq5c7;}oCptbse8Zr%dYdtMV&gI|@;2qpDt9&{$ZaGf;sG0>{9|lg z&Y5G}c%RU-6o|TC`(|n0mHn&!57WC_pECpGWZxB{PjBfyY+416r5Bo?d7iDloE=p# zJ&%?lzR7e$Tnu5(9*H<7Av9v7c}D`3f)j;l;Gf`??4P{%bDht+ulVe%P`qEFETyG1 ztsb{t>x-Lx7S>+DOf8= z1hvEvBLvEi7E%}?mVk$^1&e7ih>yZD0AfQ*e4}6Cl`rGhrQ22l>`__BEAZ1-EeJ6P zw}`{XTSkHfXi^snBN)8bl2=o}5e}Sd`*2tJaI?_@W8449_vX&^o`5XRx7?I7v;Wfv zk%#HZyCqEXp+qX`eS13?Zk*ZBQ+cDc!P?733ckVw3Y-TE${cS1I8I6mO6*=QdBCVg z`?v{RV-iC$vJn`xdsW=a4~65=Ey>`RxHv^DG_~*tl#u4;FO3}s9>eFhNh%!K4j2dI z(mg+hELuqb73B5m7kbasw6*$x=bzZJ^(C-IANZ;WqC{`=sC5?O49+1@38ZQ=YAyq) zoTn04J`pfU_>gljBC~Ql{JR(L$XAV^e z-Oa}Lril#E$RlFu%=!h#BcCGhqbKZV_O2EgbDlN&x>}98`9@PiNQvR;S}oZyfKX4Q zw0L%0Is;Y2qrM<>|F)~WTqcq_5$KzxlFK}WT6@OToE}pmi9P@Mm@9kKH8cshI%wE* zQ&rK5vxO|bjPu4eeuJUzIFs#UyzwYZNEHQD?xv_@_(c0=zWmb-3L5>nQ~XOB;)#v; zy+y_fTB>9)2@_Ya@ggQ6R!BTT4{H$4#@1{)B7z7DzGo}*-i9+*b5%juT~IR%Bl2k^ zYRTFWc(1&L!Ewk|5ABx?K1N!$H_8YWSQ8=csY<6bgZ3)x_^fU1Ars*HR^7y^TzmaB zwI6LwmgEoWKcBW?x)+YH1)U8S6zdqTGeF;@viAiTgB5DRpuNX)@btrK=ivA1c*EmP zci#Weyklz7LBVJ*@zARc1ueJ=jsTJQogu!VxNtwQ&*O9mJHOY>y)Prods4|!4!MO) zi_Kh)@Y7@11#Xc&my|ioIvQF3D7Hm3T-wbgJ`d0!8fM}^i#M_m30}Z+b0FbkIJkOAg{x z1i@5Fw5uXkb~VON#zypHyh2XPFQ@S>f+r|iqXVD1x$&|`VgX1Oa_*^QL!{qjFNKNT z8xGRTQbG&2;z?6xp##(l&LX|`%V1kz6;e}@%RM(;33V?0gGDbsYM*v>iNd=mf}QAvQk8O|&fRdj;j>iDq01=LQ)I5G){ zp~dCZi-ju>7lh}gkaWKXQ-1GK?y8bFOVa3PID zFo*Zxr$+XL?Y&5NhLF#_sMqb_75E``XXPlR*n$6%k3+0xMpj;<2V1Vz1z33QYlMa~ zUvOOi-u)WfTq$~P=i2nM$Xb23A7Vz~(cNGxo8eJ#4HHNw6ZFBMR3*YpEZpT#HKP1v zcdf8gJF~T>41u?>zAQ86s@auQKJ#{pCvF9Ak#nwzUfRbw+Le_NA0t{m3@^F!{toNW z9lKMvDSZ#6LyLdK&u{L`?9Rt`CfD5E&jQEJ4UZ@<2HCuAR~?3Stuqky)Kn1G3qqgE zda?!v9KoV%H{dOj+_cHyfR5+%x9kj(`nD?BblFCMsT-Zl537w#>AIN}(8WM)&=Y^s zo*)3sW-2CNIvO5sS1wiblG?}S%VipWq1;AQzmqHYwDxdV%;l1a$N4$jm%=1_J=E~8 zi0S_6@&$}fa&FTFrYd5LsAUA{y-nMpUtMoDCR*E4f(DMA7&0d$78kwmomPu=#n0l> zlEGo$nr74is|heK_EsvTK%CC2KU$3*Za2t@ANJv78;8D3l?@GL9qUwgJY2i?7Ck8C1{LMu`+}q>xV$KxJ*>XqH(*0y zH~d`CT2iqMP1ag!Ir6jFLRwVcRxQPE$kj+meqW}}>-&wN(j{jJZLYpi!+J!lEJ#-m zejklk$^MfCowPi@AxiLQnrVyFk-C%PN17N2PO4(_z3i172=-f4`?Rdy?~ij^L)FJjw`0Z~ zRSZ^hP)p-Q%N?xPwy+d4f@H6DGC^-E4KtKKim9?4?%CoO|G+8a;!;EeekS-#519bI!Pn&FE8 z9Sjx5JY-*fKz_3Y<)k7)#k|0&OYTyyo~p_Wvv)d9NPETka;Z$)TPRE}0d48k`mBe_ zj6I-y*@eFN=$x;)WuRl1o2EXt>y-g2*p2j#i>fow7M>VaV(_z}h>5FLUj2eI6%~Fz zxtZ3qg3kN*$u?QiPsMi#IcZcxc3|$~kOE#g z6SF+2)!A^qT}1Ytbb^V-LpMP2=Zgg<;sSWzV#|!t*f8{4Qq80(_JqP#nB@Ds*$=5z znBFv-Ix2*YKcI@6t?Tj=|C(gcI2X zuz2|0zp{mMb}tZ^AGy`)pMiPEiTq5c*Ya|^r2t$2)u$YqA}V(^c>lKIpRmWQG62mD0;Jszwgo2_bivWnsW5=ePS}IWx$R2DTs&PWzOksMrWj< zYj{MHFG%18^-{%2;Colt46>o`;x)2jIoyashR|75XjP5MMB0AmfY!nL;F{^<4c?rN z+SW3o*mT~UUSrRYYrjLamAAEv#OIqwI+PwmpxE3cvq`?&52UTFXg_bR01o;af*qF3 zjWYbY1N_!CqEquiZss7&4{cJ;JC@mbjEG@oj)u@4+QDj4)^_nuHoi?UV7mGG0H05e%!=Brg;y0-vDEjC*e#nYPy53zd@JSb`v%y=&7j2wY>3Fq zQGw?X3)_$P*qq(pn|e|@J4PQ~3~$pe&Z1;cz7m8G^)_vVeK8SxfoXi&XXsflz@XG| zsT9!5*P3`^j=cmQ=u`LLgR|&4_~;2yopun0IUEBo}BjAL46Gbin5@z@L4wLL;OoUx73 zpOokI-7h}$3kv;ueZ@koZ0x{a4Sp3_{>DeYfsu%tlbDjzD=Y%=@cc5o{xRw^y%qqB zLIMCFfYI<3W&mCh(rd*Z&y1qBHctO&Z9>mP&jbMdg`j>7@XG`Qu>acxd~L zsJVlq6M*&4_y0Q|;~njQ>tVuxTKJ&mI;ker0& zbm-}tC`qkvk#(Xi1X3wl9>(a|cX|6+9MABKduKiH+_bnd&hdFxG|Yck9e?OJSbFpJ z4Vg07N7rNRI;mCMnk}g}!yn$5&n-WkT=g(&xxYar24hlC@0)fc^SgV3yfDGmBt_nN^POE@cMN>L+G>`*_?p^+ioW?^1$rA_hEe{3ror^l zVsd%mO_{mPPdAHI`}sp?$*nC(+=eElB~6d<_Nlm5xjkSlq#xrOSV`dut)8ZYdM+Fk zrr}k;bHwQjNr~XgWER4Ce~(v;A|_feYI^Zt)rp4N`VCllAf!-M=X15dD+yPfCHv+M zjbDmZ8bKY?oQ#LA?#+OZ-@z=)k@nHNzM&We1xGE=Io1@N=agbBiR*4aaXJu;B?r zwN~ua&sF~ zwA!Qzas3m$)Jn=$u8IyyBX)%NhEvWn@9e!o8ML!)a168{BEFNF$2lrwJrf}^ziGSjV>P9wrp*KcKv72)m_xKwUc z-#hS$>d=zjMoKFX7qP}(1Lr{bM}dY~2tDI?QOTTOYe~w5c$vhs$*%Hqm}>ro31xL4 zpTr)~5L&{6@r}7FY{HT-dv7CXKv<5CMaOeK<#Tv`UK+hV*#gXUH}M@k={r6QUrYf| z7NVZLmDdjb#t+)~K9}kRE2Je78*Jx1DW1x`+Vn@3fJbx*B0SvC7bINEsPY9=R&)k} zqM^W8d)ZM&cf!=b=3*?SH?;ADW4qkj&lVMzO z{R!b2Kp5-dGQQG!b?Q>Gk$yiA-=cP=ArnjnF+mY1L!YHcjfXVMC|K8*suOJQ(O{{3 zlBG?E3ziUk1ulfTo;jVRfrpbBCic;3NMv<}Hd+dA&e42w+>LOLl?TOg>mJ4n$*NpK z*P3+?5u?Ck)@HVvuQceH`C<@vk8obJ!O1AzlKHxQBEpqEkwAegH34IYGOE_f3Rs3h zOPNH><>aF2%vOcoRkc^C%j-Tp$1fqmb_itvgNVDAKm;r~^ zED+YKPRO38fE^IvR?4iNLbh{CK%tqU---J6T%AZByw%Sg32O-c*6W9Xj)e~f@m35i zTPxlL<#L|YlAIOa2X}CrWmWl~n-lCy8FbLTt z3I<|O@aoKNe%Pm^I=xK}6bRi3RnuviPXuL-3Un0R<=yZ5Z9>D|^cOm&m1*lB46uDI z<*F9hy^{2oAyz;k&L?JKP^fcJ!;bsNYjvt{)WI=BN{f;jryQ%CR?kq9^^I2IgyM=E z7baEz*x4sLri;wPlo41Q>3tQ4jTCa+Qe|Sgo7Eq4gb;L|p3Kt>ug2K%a&dtt^Wst` zI<5Glu~_#`+qFTf-t#%5u;aD@z$Z>d7`Ya*{obMcD~5G-kK?4|pv6VyB|#`M1(daA z{wPWma4~gVpu_O+z2fFfYP2-HpE#mHBLnyiaKjqkK67Bn)wG#;88-{THkgr&gr9Q_ zuK8`2ANv|SIYu+wGGrFGt$!6D7tq4$9#podeN=L-`k+c)E>$VlnRa-by~tnUD;U={ zsPvQmJgHTRw{S&KH>vHL(pJTJKSq4!Ai2I^Yu45^y5eXL%q6E?o~ zUG`i(rY?6CL(3a>X^-uaJn!ip!mO*CGDTI1{)}@+PbHf@pXOYn>p1HWodz{NE+;b~ z2M4uVEA*zJxZ-^{I1xQFJp-ne1(a|O)^0W?tjq0m%(frgAdw@B z+&X#|7OR427g7b4j9J;n_DFA$fHJ6gWYPHc`E335e3hXTCMHg9uSo52R(kSu3#y^~ zx;ne1=qP-b!|&DhV)CJ53sFi%Gcw-pwkuhMzPtPPy;HpI0(thoSj`&DSg&$m@qFPB6t1=#~4Cc0^RAB>io?=D4%J&1qs)5DM9hGwfhfl2Ny%01> zwr0x>_TGk@_hlmt47yLsTKXWblZ~MSY<@2L$0-wgL8nl;-PrN`y5%pyLb~l6!ts+( zxL_d$dAqFo4Qys+bGVq24Fd~ou0i8O-^9i;rqE(LAmcR2_L>dX$u~TK*iq=b=)qP# zlo)vSdLln3+?Fky8imMws|AGh z@{>J{)@-WsI^8JBNiUYQMK>VNRNMJ&7;!IX1i3Ynps)iVRK-FM0_GYHQ9x~0F4Lov zPBc=RT6i?ze0Pzm*+(lCIQZeF5hiDtN!tsDn{yG^nkCog{Q8)T@m@8t#GwI6R!LUc<{HKb z3qR#q<9@u!`~kj6XbAmT`zZA(6my=TEIYxjD3pV(lEy|`%bUP-mBq?;4p+38kp+%X zc17`Ys>YBJ(<=2bfiURDhIR5lqGr?3LR3i!wrqB1Y}#UMqVP`}V;2x9YUk)eZ;Qql z|MuZ1e@0!CZ+apo=juc}^R-Y&Z;Z(i#H`(vEH{~%u8~P>;n3v)(jyLPN!L*Btg&fdz_gJ zhC1n9++)#F_V&1k)d!?ishFtJ?ex780yBgm&SjFWF`;9CEAdJm*>;^!J@}*=(;@G% zoQKH5gWgX>UdYmRYWp3973^MR5}dWOd5u;d-dem?LAsD7@hoc|?~SCAL_V5XQLDOw zL~)!IWF@6Ug93KOoJ``hIbTJNrs#*abUjw;;&PbP_}B08<^&NdFy_>Twsa>(M$e%O z91%UG@4;m^am4-6?wA)oz-NB&d*TWjeh0+aP)R3$3EU{^PQ+b7XYn?Fy`MK-w%;xz zKVhV?fp~q1F%r9ZJ3>jc8tCJla47e<_7#d>9G|&FFSx11^YBxr%2%wY+)i_rT?I=8 z_Ny2|bfRgH^@h)Vy8O(~%(m_}QSAf{gD5UrVZ6YW_pK}(w!1x({4qFJoNkx;2wl!& z90e~o!%b~AHDj#x{#bVtUx}RNe^6)%qi+m1aTlwbKBJcjqY6s>gy+p%MuPr{^e%x2 zQr^bj!Qv$Od<}+D(55*PnW~U`t)Mb#r40si8O->cl7re8#+U;YNxm&@AFKu9TYba* z9C5yT3IuK*VW;;M#(IsP1#g@=kIMb&w(V3UP+7uc+=e0QG|ps13wgYTb-^tc$KYrK)ta2tflkL@P2w)%9N zipgKmU*^+ZyDjP?vbOc%u>gyk>ugi@F}+)g>@YP2J@6mVnz6@YSOERh?kd@#T?mhF%u-O-O4eIJy`x#u#X+xWZ=4( zx8dEr;K;C6SZ?xbVEDnR_wM3)b}s@%7|p)AB&)tCH)=xzlC zvl~SIjBr+Hw;#KI^xw8);=A6t8v>6lsxP#Ctg1I1$uAu)VskqO=oT2Z~!RKc&&Yhv{wUe|inzQFI3}oK>EXTyaYCY`A zcdD-C3)v%;r?4ME4j-(w@qk4Evp^s!lfpz*Atny2B$z-MUau(A{jQl3h1=Gu7w93c;~q+cnp! zyl$oZ;jQ!UddzR({o#|>y(|)8GN`K6*R=c{A;yUOMKaxrap56X80?a}Q&}RtOsK|~ zHpcS|?#7wVK>kfrV@=Tmd$Jh=%6#-t#awpZ`o#G}^!#CcY3$DBl=(E)V@Eb2i-ISLp1t=%Xw8f#A0BQ@1ji9QS|~4%oNg7mzD<9hs|Z-3MYK zrw2zI76m~uaF@bs;_%TZpQ!BIDg%&D`j!cjcDR_Rmiio(M?mXL>?Rsa7hLG$7;c%c zEK@Q(y&v}|3DQi~gjA$i)?%fl2@iKl`Z+lI$Dkj8{m}vOPhJyIpANtJ`=Ar!ygpIF zN@ILN@#mYGHWjl4dT>q3&@@L(8h>%C)obr=mL*`qGb}-+Wh%nSA5xqI&o@(4rsIO- zf)ItPpN4nw2Tjd_@Mev16e3mqu^cg)U|6S@w%@VBvX+{md@i291b0SK4p%4=NJUu_ z-WL&|t8$=5ObrLbLTa3ae^uXq34(uag1k*hIp7CFc_>`}Z@AFEh#!#UZ!q+W&HcsA z{=#H`!@2)6WlURf*d~AprTu~S`V$c;k%TlENdZlV-L6pK)0=ASaOFtjLI19kN_NRY zBE7F|EWH-e4kg)^?3JC(E0ZywXdqXh`hq=xJpe z4op>&W4$KqGk}UdUgwA7NjT9Lud)gF@$Smkgri^V_rjK zziwR@0|fTSe9!zcw%llz2*c_(_ojeDm$lAAt<$j&_h}D!kcJ35$>3l6ZrsOLwS;nZ zHw(Xxa2`#rKXskfnW}jCfGMbCtNu4z^~?Q#B0Lsm*1vb^7a#p=r~V+EzhJAdv7@1b zxt)`(!ygRu)g-HL{fa;3Rpey_GzO2fX{E3h=9r`j1L0 zeN#sO3-jMC1qE&00Ga@LAQLkafSwh^3;?oovH*b0EX)Ay->oE^^sUSd1#C>Mi~&r) zEdq{)#;**RlbPdp@z?x*mFbyT*nS&?^zFor%}vdmeh>58q~v65tqS1yqyMjh_+N!z zD|}5`G=4qsFM_G~590gJ6Zb#v_+vb01E=2zSlPkZ_*dO;tDwH4@ozl+Ke^@?3KlZc zclgT#()xdvfk5`(BmCRn0N~%mno-2&HJj4h#uUJ)W^N;3<7obu;dehZb0a4+$5%(P z0NEKh*nv!(zZUcV)q{&aS!NdyU z_~j4~kd1+vh4qgk{Buwi76x_>PNvtBh?)J>4J^z|EWe=ruLmbPD+7@Ew_ia2X$ArU z890C-RwfYOALB3qSYPcx7G{p$3ufVDW?&%XW&cUUnL$iU|03eE%9c*bvzRNcot`G~(k2e3pCANbq$Bfr z(7@5rAU+Zrpuog{ho#j=AsXS320_7`o8d|H`w27EbOVrqB9auJBSXna5-q?gqRb;m z>XkLaKT1lWR(wR*lf8jxYgL`McyYPP@I2;S_3?VB8EYv(RbZV(8GNVNIU<8h5koRX zl+f?re}PSp+u#L;3NihB2d@U1mVDer@{n1}$B@nb)%L)VE?u0MgriLhqS2Hd^W!k& zs!pfb!nfVkDXcH}5MuP@@6yTI%|EikM{Bd1ZW(m+v)mV=USP%4dC_P-v5~6C zQo`BEBY)MRi{nWfBRmd)toiI1F4k<%rb{2I4$TEL+Q&gHB|TJk^& zO@GbEuW3O`Nf8-BB!{c!m=6aD=u zErXoIIR?xatRwr&6ZnMq3&!U(FJmr|@G8{y2|Y@5N{kJfT6K?-*r2FnWIZCF6e3)r zY4%_kNYKTucz($4O!!l_zEf~ow=MQq6jF(gkSfcWEuxvWifb?7GHV-wn{+j6tCt-* z4s8r>-8J7W8mgB%h;Loo!>bU;HE+l$lva9w?yJ+6i2wvtLf;u zIwY>9-El!vkvtew|8?2GMMIH7vcS-@VRO;=g3_Wu)(c+hv{JRKcz^sLq2yT=T3+(1 zr-OIH5Xr2p;Ciq;ygFTVx9|hH_LLO8W6*<90cn`~Agd+~+=PM#?MUzpt87`n#}I3t zOc9b)XBNqGk6uY~X&6nc2)vP+2;-!Hq*&~JP)U={g_*MqkL&(U;kJi${vMt)ASPJ; zeHUp5CALEB=LG{*E@`~NmZ;bvmVV;%Q5uJrJPr!pqt%?H>SiHU79-6qo4vhMjRLBY zjaWRCk5n`To{HlyR9knK^(8D3%eh^0BM;%u2Ig6VaN$Py0;E`XeeF8h2#Qe-X(K9CJSt!+u8T^Ne)Oy!B=q zYg~7YWHIn5!qYCMDyg){$O;^DjaR1H%p}h+cnm(X9H_z}6lnj!C*Lt@MjWc^afY=S z^&!N=@Qp0x8pI~Y=1$~1ZWYjHfMej6dh=a=lzpH7Tm#YUH#2h^CHlziUW(Ed#8I~U zbv537yRa(g5bygkA_9YUv_64>;YgItH=7jvI`x}DPefNAi67E4EV`g&WDgSxZi3Eu zHmM>zB8j%@wWkoyy;rl0TWw zzSJW#>_zXLg&IKbRiHASlj*+yT4B)vAEQ|#3vuwMPMi7RK%nAn3~-KTU)~ZYhU@gL zD54=-@BD?hbAv~qf_Bu&gMtc9RVmLcks+pGAt9|n4G$DDOLC9`?!XjNa$wCTg)g@Z zhWc=wz3OX&D)4ZpDEaMp7myG*7dSqmxP}adW9o^)XL@v!IIBip0Sa0e`Qg3q!oR$Q z4ciA}JT_gXiaQw=(dU6<6~esiwZb;px>2aZVX3&~G8}Lc8r73#XNm%Up(DBt4f8ZPs$lpMS0d&y?tod}O{q<=fR z>eJ6aG{iN;agA~*Y3sqswEjHFU}UPH(&$e|D~c#wgt!u?x@8<$Zy+435>-vo8@|3b zY0>O|X;$D4wE8TDcwxAUQjE9%1%(P~bx$FHYE2gT_*8wC(Ee22o|`PmUXwtvU<`w5 z*#`m6Fei~|BE|?GN*o%RDZXbnJ3<&NEYip4GD-Hzm^@TTkaPo=L6kUH2_XX^WM+Rb zNFj=Y{}4gb>SHa?pq~o_rYaigZzh`fNd!p8@abtnq+}R2G(`N%IW}7&HDMZT zmrFkA@I`;(h0FhiEB*z{muH~rzlOrUzmWe7g@GKPzw;EB|9Q9nuP^Wa+}!`ae(0hd zJ8sd-gfMX814pslr5k}S)=+EX8MxzYRbA<-_-E@SM5qtt2ErPSp zZ{GV>3n8(7S%2W-`Oup-MQB=pU^?r(HZkmIOWBc*E1-5e!<`z^o(b`wQ2I+y2uTS4^3kvAKUC6xM8$vap4Sda z?vAgLM#9F#_Saayl4lf+P0e5Pab6{uz-!u#@o(|gw$Vh^ViJ&r*;3b{~^!*uLb`ld;pApt$|+r_f-E7f=2qUg6`FWztqrgk1PJ6 zBmWbr|Gu{WDfC_i$$yR1|4u3TZxO{mBXuA%2OH>Lq577Gr%zBJVe z^ z!9(hXY&=(E)cB*?oF~{Mf*zpFy6643cTA(b4>6~Fv|OG7PrQ~MJTW)G!}0swWw9cZ z$!M95NVk&=-oj2*oPja)sihEP?*?ZjOR=bh1>_U5K$v-03WXJN;r<^SnuHQzI6>&b zTwoqGX>jB-E=3)THCg8T(^)6gch&-3qr{lvR(w)XPpRyCBlBIA2@bHa28WjEZpq?C zF61zY3hf5Bu)-*i5*R@M)ZAbR@VBH>%9HtZI)n>(#O$>qxGXgrh@|m@ey~Rp{oWG0 z4$U0CKbzq)RlL+pXQ{-!Tm>nGN1DL}G37tKgNc`ypb1!0L&k$7{CSRj>+}r%QwN=| zBQ7N2OM}e*eL}Uex?l!*Qe-$pBtwEDnLS&YmBLiFw48h1Ih1P3wgb8$aUJ(8{Z^5N z;n7hI$ayxUsi}N(%cs~T|MIh1MI6G^Ob^+__G#42V9xD+zl)8Gj&v#!OGRWD9^yIR)e&z8nn?a73#q(QRLh(33i~GpRQFgZb zEq2cugQC1TPY&Hk#zK|V-NHCH7(nE$R5)~^(PEuz#j5jQ#Qk*W`FFYsa%Ny$7HW#Z zBzrtPnziya{Ky-dxOZH2SJD!in&kzEg;Og;1CTGE)m*q9-Oy}5r#Pe#F+&WK3#qjr z06(L0zp75Fuq)HI8*>_&QUxeS1t_R^VQ|zC4ClDd#sOtxWNk;@pO!uy2y{eJ)K4wO zA@AS+IHM5Kf~_Erl`wM>^?r&>y}HWO1l&a+iEpcMb*`y>-)7hG*h5UZWvK4fd&YW! zi)qrUrt#G>g!$?c`zT&J(rrZ!=yyi?oQ{#ZfeV+(;iI1U{xgKBUw8;~DUpSiKqF1$ zQYls7ZGRgP&J#)(44CcoNM_q^%a~TH?O9}TvNHpA>9wltL#&yHE5X;y2$Ry-^3cp# z_2u}-8olt8o4pukw1c)`|KKJt*n*xbZK zL27#ALctPsnxuWnt3rnoMGG7m(Oz+`_$Um~eX(z3Nt3}2AI81~G1o}bOeY--Z#fhO z&sF2)N|wi$IDEj?tSGCN@+!d8C+zhte7H&`&?V=J)Uaf5}m z{BT=8lu#^_&C}xe(qLPu+vf6=Zh2XCmh8D(jsFP0V!sI`n7b*u!>@-}zCC=4_ROIR zRkrB@jEljBGIxm+g(KU`GFlkS!{Xdu)GLwtk=9P}!!U7~T7RQ)r^pfu4XF&RwS4GZ zbo39Ck00P*7E@=6WM?u9GEgf~*6c`Ml$<6Z}Q+!%nGV71e=$N9|O@)DP*jTn!u5YmS@dH0{yj z?E;gSwsR~4#NeD!-OrMw`2LHlj0||%Bn;y_MPFU3(%fD?Vxp{J!{5wg@C*yM+j@*f z>W-$J%hG>mP;|VjS3uYG{K8q~xHW}p+~wYJq`vBTOiSRFFLq6p*16USO;T0ynemBi zkG!9bOG9$zFmnH31YZwK3N17}*xII-@E*-#eukokDe2(sj)HYd7STYW)FCh{bJ1ga zc?li=F52cv-*(D=weciX5fSn;wRx=W5IroSqH|6VF~*d=j)su~Isd{2v$z0f|Gp%9 zC?7vrunIFxoMqCXI*PO$=v(-wEf;yJGl~EM)PT|effqE@j?#V2qf%QDHBTriYq=gx zO?yF_{<}Q*J1!i!+KU`{Ll=P;0l)DACp*bjgg|MnsMwXuBicF;B5tku9PKKIK5Rw1 z!%E}o$K*i5xE9aN@?(PY(wMf_y|DY{UP_i-^W2G#?=UhO?@B~FBAk>2^S-?#^8ncK zI~HqJka`1vrhgq2Pg=qxGW+wIJJa{MLVYO4Wd5jKB?}Ao3+h9uJ5|@4g>K4D9)|PH zny95F_UF@7{eE|MrZ*XDA2+f(ZfElZLT-+Em3ibdzpB?4&wgG?{h2Br{naK8l2Ae} z$%(;m<}0YcMxt>)bTob&_Y?E?JmPnVjR^IS<)%zibi@k=?|fnMWzw;%2No;ZH=967 z>ACUoU0SqzFqS%q4Sd9;B79${?#Z*qif@Ma`b}Y41drtv2hk;w3WKJEa7k?0%Tw^A ztP8Id#Y*aCl0LwuWl{>|EV-OC?_#^gUFP^MhE_OsjUa`1dQFlMj6I)QooB4~S}vsA zAozwfIosqA)6o-m71S|4=?&eU7iM|~l|uF&6Xy@WwhK068|wjh2fgEnsD}oeIJrZH zCY`>Da>MoY$kFvJ6YM+~|I4#AGk&{n=Ri}8V z@Uu9*K}mqzr=c26XD_Km`uMWuo9*=3Vfi_P$d~S<#Js}yaWky6hzDj$U#5!K!)7UW z{*LyM*jG;Gtx~oQJhAON&o>@me&BB@qpfG`P_Iv`78vSbGhc7^sZ0sBhSN<*kwOM* zd?flZvl#AMTA5!y;o7DQb+3=y*ZG_VAAivo6-E_HH7!q!Wk4VR6vf9n`xutWbi)J* z%d)#KqQ}OJgK01aA3tQqs%comLUHuY9P|53*>SV7cmXc+Z7MM|oLP<(@`dw6EO=0x z>jl4SBTPCsa&6J~5m_JbV1eMqXp~AaIn5A81LHEi+|LyO`>-(kG>0GP2z1|)O7Uyv z#BSNIA5>B7T*=9XdfFi}W$PN4kU(DmQjJ8*??uqaBFKYax#Y?7)MvwV%#`}ExeJ4R zeemHw!=_@5)@OPGP^Y~5)p{JRLB1av65O?WnW8x&_`VUwQJ0|l$p`1kFX1-imldDq z5<`67kEn@`*jTVNwR~=bwe~`->__=3mmicn9Ob#pH5@zx`B~|@dfV|r@Rr$}Z&6GRSN9C(TUJhKXVZh9T zwIF6qtVmpLxBv;3M6qd}bZEa730A^npc-WzYaNSA|UKnEIE53x<1Sf+?lkM| z$ZPG;=0GU{@*tdYt~r=F(F<_g#!yh5NM?&pTqpO%@Mna%=<59-CKw0v4(xmQHbRsq zbmh~IN1hk7a!*Fzs~vrk^_1BZ1KNdiDdflPJE=Rot~54crK=~c0$G20QMUKgJ)sit z$p&Y19A4bm3Zo>)CAOTWhbAyc#JnCK(;VHiGbbOF)W!IZ>1;!7K8UKVTCFH?9w9`x zV0&bxw+%tEb3f^*!p{!7E#`)ad^lIu1(!F(h`pxDig;Vn4f}${qJ&P?7R#2$5p>wLpC>5ua#QGKvueOlDyRru7UaIb=7(#@2hfQwhm*(j5 zdEVSrJ+EjU=%oVdR?4TCDBPrisX0c>8Q*PoznA^RU`DKpwtJ$N|A)G_49+CS)^*El zm)R~eGcz+YGcz+Ym6@5j%v@$DGcz+YGc#QG%;`PdGd+8DoY--1+#lZ;N@;~MQ<*7g zDc@(M=NtPwTj86BsosHy<@T7dyUT$bk_}ylT0nIKdL^<*t4n_w#;8+OqLtWyDpR>o zg$u5=OHe$V!lm+kX6N#S?xh@(_6s8szjE=p@FrHK2%*tMg1PtCoO}8YEh0}R3VkIb z`2hN*D0;e>1NP7ALZ0+G2u4?zMMH%e62%wei<~jRDJi?g3sv?QPb!3_P+3pK zCE+24bFJY_kTHdX1#_SamOzUCKs;#&f3A<S8*L%IjdcP3&<85tgiuU} z0;0Z7xFk^-PU|~-C8avr_bO&*f~qzUnA=SZEhN~SI+I_wSIK8Rek5*+QZ^mYQLekSF6$4_vd+` zplQ1%YP}o6`H@)ssujxpL$VAAL^K2{8kkGChEPO3ZptInOIlbM`=^%DpHp$SiR&0A~_mZ~G$Q&~Hs>$eLK<>U6HQ%vH&|=l| zYl4U8!4M-sMKW9aYID{sgaRpsfU)XE9V!N!4l-KomM#~iiwLf09i2k1%_O(H(#<@% zga2~lRgviU)erj_3>vK3c;PI z*Eq*iv@i*m@^mHOK69uR|1?kq>&cSNUTI^Q0-Uj|aw&rU~28>gh_Cqzx8?te~gKFEV!{2Q~?jN4r`Z*C|v{6by7cF}l?I zU}Eq>QqU=1zQ)Q1s4K&9B#J_8dXZYc9LAn2@`fM1kq#hJ@yHKO5cqF<&?|m(yvjtA zP4Tme_v=tMFLJRc9R*b`V&kbpYY|SB6cq z_bbA7Tl^1I*OnU)<_lr$(Va;1j^IbWuF5&JQhcwrF2%;FTp6aOI4ZwG141_?ay6u? za`Ad9@Is=ZLoHe|1wY=-;=pr<^_lBv_}CnAChPiQ9AISmK*muPfs%rQ3}-_P%;2M}p8*E!#NXVmA6 z_-1~EPyA@zzOxtwL42`ugzrj_1QwEY&>yoGDBa=*q(Z#2B*Y8m8Phq?h=q+TK5@w# zoe>l3r8%5dICg62n+G*%3!RTgSIDFWQm_=QAtTn868vtZZr4)L!rr-J8yR)pOkl@0 znd3FQA`lL2qwp^PqJ&R2_SIfWOc4#ZMl+J+Rt>dlfbCj%!4KJPK-?e$LX`+*#-Jx>I} z`s4cF>B3J=L9p3GGcsBT1EMJGofNQ)*)Dps2*VtUs6*6ky&A1Kj=xE7V!=iW&THk!5WJNUurXiN0s%{7Zw7)3P?>@}LucF-N@JT#pzYKF*2 zzU5E#Hf5GI7xi@TS)J@|fUBHi#?NRdsP~=ddF3MG%<9MU_V$ZX;SSCn6Oyam3euJ0 zp@YJQauro2$vfk`r~&bS{i=3~p~#q@PW9#l1@zE~@1Z_LAwY_lz|2=6gfOqjSN>Uj zQlf;HyRlmjAD)p!dcCsUl80xd0%;wr%grYR3uHQV!ECA3WJ^)$XOaU)3BGqR##h`j zD5A*1sHoF%ImUv*E;C?IA;fA85=D_GBQc|=DNQF0s~;CY)Q|YGnsv3a05K;Dyls#&&y_9YP;cv71`D+if z*oZ0aD5*A!4w2Ae{n_Dhgw}K|>G5zGiXfuDM!NW=cQ1_3L}JO;B#W(+g%^VSi5BX~ zyLTnvLBHUD4{ZB_Z;NN|lOKD}Z9Z4Tys07{Sc}D>oy!Ig(g_;M@kOQ0WE@P1J9KiF z#JZ!m=bsgeL!C9~CzW7=N~g;d>?lnB7Do<&z2m}_{=>cDBi<4O-x-p~z4Uvrw0M!U zfRv)WoZQ=$4;;)5>|-|V*7Fybo2yBba$W!SRzUWqOzphvYut>B-p2qag7|>3Zfz-* z3c;WOK`aJ&-$8dFdSY@K^KV63gr!2hu8D^VtepeiT_Zn)7Doo0i&3y_zr1J$ds0k$ z7s;WDA)gJ>7^BRh1Gs|_mo^yU3uh|hNF18#Z|M{>;vwb<&0$m;P-$-CbnCD;ehwxZ zArM7$^m029jlEWBUPW=3)6o&px6*gFm&6zfr}oim+Ap76U-;PVeJYZq^ig{1adiwQ z-Y2wwgg_V`BldL`heeZj<|AL=rY`LT+UfNkojc^9`HBl>0E;8WrMn`cEAP=}`Bh}$ zCzrG3*>aw&x~8%+r>!H}N1*OR+Y?&rLqDQL6pqeKF9xk^=OI`aSQHwCBB!0A*Bx|K z1U9Sf?V)d~huqB8DziPf*SFHr?P%PopI*s-1p~fcYJhV_+{}FNL2_ za-pfQ58HcQr0Z1!$5crtp^54N#5>&zQHFAShV)zv?fMDyz>@WINptWUdk$c+#^N&Q zPRS#-vrTic1JLoX5avhRb2|KMnkXkcfq*E%EPj3*qu8B{dQjqq48{e*?xc`u>#{Ig zOlru$%%unO=*%j;0)8eRa6M2tChm$5#OfnCHK&LiD?CxTuU#6*WUU@8?mks=WhfE#hgA0Dchj2eDWxxr zCx>63)6SXp^3U`2$3by+Yv3sSJW)Hvm(*1OWNL&Pq_y#Ed^1nc-eh*yF3DF4HfTOD zrE7Yg^X$K-RW}DK+DX2cB}bK`((3y4WPdH4qLVBD+Q~WIoXAPLc+_A(nQ$J@iv*8- z;W(HXV;R}O)KxDS5d|()#-|TK%1#-wp9a~{{W_Zm`3C>S)V4WtzxM+AeE-7G(mcCi z8EcFRskGS6ICb86zpZih@eXSn0a=BW6^!M|ND`&9a|P4tf99U=cs7Q&Y{EPwR7Qp8 zB?^p^8j(bqr}Pq%9v}vQCh5M-;S~zTbAvz-5Q07dO~@rmb`+^1v^8Y%QJO&8GcA-3ZJS$8 zA@}v;toeiIMd872^NXc0VQy$15H@c7Ac8ZthJ8$2?CqgU1RU;#fy8Ttm|<+pXq15l z&+YcyVt?%H{PB4fFo8A;gs?NjgvF5cJ-0?hy{8z)(Muit4U*p!tnm2m7dG+x7^_`Y zGdvZ%5Sa}>+*=|J+<-RkP@AAlN>W+LQaW?=@Y*#Y=Xf1G>>3P0dL7&lXdApVFH!d1 z+CvfNtpl|Plmp-I;gZQwqS9JlRG5=jad*0+vTfozrqP*0xnLjS5T_ZNGuw$2%?1!& zg~2iflPAx1<77cz28&XV&b!sDNgV8yoUgel5QJk-1R?Wf!^xHgzV?k>0UcD3;DnhR z>DCBl5{>7^LW@A+n!@57I*S>DA0-)N*{WBx612bV@i<*wGaT*JHcW1MF;T_RA+@^@ zKYBbouUAZz-qgp`AS?J^h^nZl1;&s|o5IhitIBTR0|O<$YwZ-Qw+SaHJ*ul;pl2Q4 z{Vd&jwA2LAE_HcC&E8GVo$+FJtD{oC2R3+dnebB4tk3LE(|+?093rB=9Ab zr<*2>hzD|AkDd)t%xvnniQiegC(cU7m6GICSRp1k*NC~tkBszzz29_0&k_*5xpK#r zN1VpZ|0Svt1B1&%KqZuxeW>77M7mBwDO0D{Ascd#D2gO%5sSQCo9cQ`fF(XEmFWO9 zef+4-D1Q+06a8$Tap`+P7$cOK)^8^4 z)hx-Oi|AoW!9nZ@h^UgN30%GmJpKY)?k%r**Cet7DnYxAr4V=|t{zWeG&mhbtTREr zG=Fz{d2!OblwDI@J-q(F17>ty1HLy$haf6;V8BJoNKDlPVTL3^)Ipc?gh>FQfyOls zxLDVfLL;u8#xfwIASTHhYjY*3JO`e(W;)7+7c0sJ9%GD^=p*Niwx2J>G=nJXLZ{Q+ z!SJz78dC+DbmXB>A^xyJ??*_f(J9j)KP)b04h24>w5{_gDu;VSo1OpL0kreuokwra zz~ae6m4Mzoj?}4c%3EttJ!AC(3~TR#aWxQ3!$z0(p5+DwvE2sreOTz3ms@;Oa&22h z_lO5^2#t+CO(ooYYXa4IYUjORKyuBJ^|&{>af{|@-@ZpL3Y*83=)#d`@?@(+@uDZ} z3R}XND<0)}N}o1(?E%}%5Ol*E=nI|6%IWDZT#M_fBDNQJ6AiYNZnYi7vc;wZuKFc1 z?mgpl7PY>y&v0PF%+e!pEI~{0!VP+Fbap@{CkskpC(+e+6ah{$zJW?gC3HxQwO(br280(4G-HY+j$R}t%U}Lf7Wxtvi#t1u2&Z;pDOCL^$iZsSxuEY;0!UcKz&`*(Wvi|Q>2V|P_-wb7vttm$v21*|Wq>23V3j>58@ zb#Ywi@Wy(oQ7jD6)o8Ilal^M=a+xgIvkDig%vh)EpqS@|%~?GHYR$(BDUFmeq=Zks z2FawiPw`07QH>GZSNb5VmA8yx5n3K`O?G-tgEJDN8AA4yna4Z(qwK;B(icdJW;ak)ButK`2;&{%I_}`ryA$qK+ zT@WxL#0F}+Ay+3y-m&vTtnb}1hPxprxd5wQ{Vd84;TkJHfLDcglO4nwa#vLy7fs6C zgRiYsg_G%urG!+A-_rvi8Ig1dOV!(dKni)s8x5ZD0vSy|{?3)E_s;#zpFyL1{+lVBm62yicw_j=%pMYRb-k zsb|y}I=lg6G^}Etwl;-Aa75m?pThx!L64;n%9v4A&;XP{HN|h@jy~do4$V`IQyN=_|)OB(K7x+w)aP=(eJXoe?S!fQMRWzV!iSS8{JU2O2YaY z+LIA~*Zm<%&3)_J{PsmH7ZaeGaPqp#M`v6*29RqJQ?9mWDOP!IWb2MrCcVOYzksK3 zENX^x*HO#*m&|>__>86VIE+Gvm*$a=&yli1;`Yv4bHRunHp)yx!?TjLcB5w_tWNM= zLOZI3)g1vWnas@+_p2M5{fVo_!h@sOjj=`T#tL4f(78sV_XYKkvihql>hPOc3r|vw zPsGLplUmUNhx&0cp4P%onP2G>Lv>DVjc2UqQfa{-=S;CgMb$nhHD&?|#ZFqtGt7K; zYLXb4+cn=#L%CQdb~%BfdkJjur9oQMKMPJ=!barphwL_8?KxRvGr*;P7|V{4m~#Wf z&wQT&ul{l0yNq~$R4bPaboB)@l;Cyiuy$T+&T>7t5e7XA=?0wH7X zaHgw>WW)brsZylFx1P`9h;Os&iZZx1;0f|Nx;!#XNhA{{<-naQ`9=C6)n5e0mmPq; z+Y)5ytJhag(0lC3mdi}|R)+2jp==Znh{L`sH#V=r+lx7#H`YgZcQ{wu+lx(|#k?N_ zyxy|hY(`yhUXqag5Dp(~MQ>CG^tsP=lS{pd(hkqB-sK}<$4~)w=(> zvj4$p{mJA{8~?(-(f^(2{fE@~v-kNIMeW~MyuV9_|7slm?Xmp(h)st}&-96Ee%AJ1 zAC4GPvanPfK;m}jU~4%!ICn>>W!9aqULf?=Rb4?v6h)bvwUaD{W?YOEgDxNIU+m&c z;MGJ?z~%H4z&TEm$L@Ff4hNi`6eE>^Pp)3VV_uK^Oq;K#AvOK<;7}{&+9hx87bg^{tqGxA^ON(so{gQDAHt4PHeH-)a@YfcKMoeJ}4fQi-ED{XB_)uwN&3;G8Sc= zt=6le2Cqn}3*^imnz6W+ePw#FQC2o;>)TA+W=g)|Cp|s`pnapuWAE;X%gnSFIC>^u z`biE}$-b1@!mioOwqwv(ME=dthaV_DB7G<=zw&m+WK zy?Z*IopizM*?*YKBDsAE37dzIGTW<_$1vnOtDeX+R@OnwPNSL9UAVsze^W+`)ZSXs zQN>s{8HX>H1^+=VJx4h5C=eI_s3AWx+!wOqqG6ZN!jI}tTyXmCxu9YPEKytKm(L%# zYtaiPROmQK%D|2zEF@v${umFLl$2O|=_W6c(oPs!L~=Eh2HZ$uAx___z#h#=DNT># z-77{<$$5oV@>S^vbtynIJ_ViIh5|)#qWe`Su0#HwsDo^ovP2hme5$5`%M2FC>MLew_} zkX{chkXcXml3}5{cG{6Ss>D)rQ!Zh%0z(eLo?8wfbJZo&bmDfQg(H}?A0D3J(bF-v zjgQ<`a_aMjNmSN1%aHjsV+lV{6q9Z{awZ~Z)$KI7Bvh=h`ssF>ttHmm=y$TF%x}>L z4x_9U4vuJ;D|=T2225)e6NU1Mlh!W3_m_hdvB`J2DPDE%Qn_&)f^N_!$yO#77}^2X z*9oRP-HN=#P$?v?xLk3iwnYv~+%CYLGS9~(%N@J)MeusDBAc7vf3y>Il;845c8r`y z%NbC9Mt9_4&rJb^Nh8?gMm@kjTu){9>?>G$&m`ZBd4_QEKc~M`;)C zqh^Ir>(|eU+wt6x;v>-OGw4*TJB6q6l1u*tRRFV7@E8h<5!SJz`AU;^CfXi=(WnrP z9l5i%)A-b2P;W~mO9U~!(lVx2b1=}~G6v@9G5ql;K4&Ctr=q!nIL?O<8o%xeBAF(S@9Ujd>%UP^gb2#lnBVF1g z_kvemh%G`kE^u!xoU1tf)UfR+LOQ4$T7lYfr_kF@c&*sI(m2i`1|q1HsjhRq_f}}F zR6rVyqk9#^4WmNQKe)UWPkSiV2wuZN&wtjha`~Nmuie>yZ<)`f$Y-(QFG9^EaAjkJ z=M~%+>|P}8>8E8Ulo!EX)&fso)YWebb@DQ0xQhFXbKSOTzAZ%4jwL9ehTLeF$A)1+ z8orR?iWg#&s@g^#snSwK4o#6><7V_tDw5iISU3-IgRy%1iMBH2^Dimgl=e!qEjT+o zcirCvu~=dg!%J29WXs5__-^xrn{upo!Oyink|>jBPG<)F$nk1pZ$Ph*1oVxiQGTUd5r>-DZGj=@mV(px@h+yIX8mc_S$8c zC(49=!8-IYvA`M?SW}PitF3|u$~&5c#!IY`Mq&^ui`fw;v&tc;EcB8$6xiDlhwYT| z)Cu#`XbEWc!$-&YJ2rOFKtPin2sLG@hE+D zrq;R3V$OTQ7^Hv|BtsWKYCbJKR)+MYrC`Zw`t(>ldNemt83%iJ?CA_qq>i4faTpTJ zc%Cj!t!4M8$M$s{Oc(D8*}yVN7+9Ps#>uV=DoOZ{TJMQ zn2o`Gy=zu3c)-K=aRMKcb+9pqgcOYA{g~JHOnH_$e%%unFNVgu3;P9h>|Z`El^alX zCxzWI&bEp8qw|={zx}9#Npgbhtb-PJz&!klpY= z!5$kiGd}4ku8u(|`DF2UHOL*uPqQ`pZDzORs=~?# z{{yt`KQz_L|{?A+g?QU4xA;@`FGU%_+#p-KPY0slve z?r#_OUnsi2bv}Q(2Yz3Z`_0w=KWlFce|HRio7?}VIX@je{XbE3Ywm8IibD4`N|`Np zXVNxD(k>0-(~kTBF~oShfN8`vAaHP)YKDk_farYiOM-rqiwF@=F>r=KQ1l_O@St>{ zQ{UkXaU$SQCi#MzzQv!-AR(-Fz3vr(OuWC?Lx__PSzwpxhZM&e>3Mc9Z%oy^9X;*URo5xM=zE5h zkxaiN^(}*ik88#{Q3=D&iz8H%zE>RKzJ^t$up&D-u>4Snl9A$FQ(VO)@jALCc*E(M zMeTtjAsSVxiuzB?n+F_r&4#dz6-~C~u0%HcrQ}`7;d9C6Rgqeb0@rvVwioWSL^4*a zILksuVh;jV2Now2lzVNZ*TI~lXe`fLD5faV(`7{k1&8m>O*YnhKb~mzH+;$s_5&aK z&%6o;7J%!O>`z*0zw9v~pj^o_!2$WuEmCk5in|0Bl}64WQV_*18itdQSa)SI*g zpqsY)4JahP`bIN|f{y8;#o!r+pvebiR=@v>AwSMe?4TE{RCVkAHZK_7$eFxNy{8?5N2S4piB zTg5k$tw62JTJ>`o!mjn)cVg>BH;F70T*%#{-WPjBwE0M+*s9Pfqf$gA_758*R)bdT zY?v31nX;!jA7><@1vcLi7YPzGq|ap~nl-Aam9{?|s~kRovAbY#k``Hf#32hm2)?=LA((puEvjJu@L#kZ-K z?KNVtup@!f`wlp-D#?vFes^l1l%HDu zwM9JE><)!TJ2NLwBCpx6m^@-LW`K8-FzOu~w&(8RF#5Rg`2x7=B}9dwcSbcb`t^WN zwDMw@yw7DdOYWr}4iZ%!rU>c&&ER5b#|jfLhGJooxn3rv~%c6i!HH zewM6;Hb)gLW{+9)aM!|b@tf}ifF1I;|A=Cla;|J6V=Kk>wB&cA1wtPIn{R{fo>V+_ zfj^!T2F+16B7nnCOgn*oF;t2R(QnK$HyxUN=GVop-CMMO1;|cREtyLaMKH@9lYz5P z?x5lYy!E!|WKMx9^sn%@x}T~88gJbdbgRigPZs(WAhfoRY+12ZU)GZ)#Fc#p<-opr zb5uPa-`&Jei%i%EVP^?H%mBS7MqCLjzvdjy7bE6bPRJo;6e^3;LbFVcm@eeTi*D-C zNl!ce#w$rvc_;pHRv7$j)5vu@c&SCWKfnHyz;DezBna-n`C{F(z(b;t*b|2SC(q;n z&7)AqZt`2$#-_?!e`_(PN)`tVI}I@nGYvHj_k;peAAhwfCDKTrcy*2{6?2kEV$1N_ z-qar5UiF^c-qjv94MHe)mFaQ)k?sPh#{nUyc>|f7cn8r;gW&`As+ELvhhK(@j#OF< zi!Q$A@k&{2wpC^yvNw;xx=ID)VmD5qg^1p2)45w4)2Z3(*&JQAa2C{R-Y_BY)NaFI z{ybIkQoK0gLvM2ZlqIfTbD(K0d8#|{*SMQ@kI8T7jJ0(~v}UI52(y;_4AL4=TwwLv zu)Qycuc7aRKK4u{g>&WV70lKVrOrw%WqD-=qj`5FGiOB-&M4_D8nxTsfR$L%Dr77M zxrBakCd_TT9H{JbSKmW7Tc|X$gzNA)-)t-#Z7UhvbJLqWTuuW$6cW~y7Zu86cwcAM z0aQS;phS83?3{aDg&#PcD<-G08;b6iPPWo?yQzGBaq^u5bk$g{nwP42%1gYW6cze# zhp24r)#0{L^Jx9Y7`dNLEkim%X}U28*%JD@l_kR3;6OyG+xBWGI`sQ?_GA0?{P975 z<+5i&Bt_9fj`zV;yB}BiM!WBz@+?V_5K~jNKlG0JYVy$Q+pB1l%d|||)S&^ER z_~%@E4DapMpcwrMsbtwQwq{zqFNe+Hj<_fJ`NkfyDw!8XJVpGdzYMqHP)3reRpnid z(gD(gqbl2d#-{Hr!qKU4`WH7%`z?=c!FZU!Q9e<>Dz z9rJSC9j4XEI}iHdBR3hg0-7OTphs3xC)%qYgEuoPcdz>9TxJc+#-=xy6D@XXSzAcx zW)&OSYfNM&+QczbK@e;cYZrK{w;bOwV&S^8pI%3E=5w=8N#|d=-*>n?uPdV09wxLV z6n78M*aZb#tY}=ua;88QFWLd_Z+Lpfi)no94NX-AA|;bv`eBX7fBLgThKjPH?4-%4 z|D>{ddEUFc;kvI;$3_c3Vujwin+*%+WeVAIQHOB|yf;Oh;9gzK>~_7FzA6drIES2g z+8ST}0yQIJbVd5R&M(6@_n`}c`V#?3{(26M)j-Rxg^Oqb*O=@aZgS2hYu&EWDIYJB zhj}{-kKH;8krsI{Ypn~j5AWzz8Xiu&pDSKzm<6OFJP{@GLl-~~!YL_Bhc|?--+HE)|I z6-HbGT4<5X7&Q$f=s?Ol3ri5^LK-nW1z-q}It*nfED}F;JN}(9de0G@XA2rj2h`ry zxrn*gpo!jmA?12Z$fD4@F8KpB!~XaRZGc2&ZdCKBH~3;Yq!xA|93$H0MEiO+U`X3# zAbQ>WnV#z{-Y;upU&@D>jyk`?Os_@vSi$XkLQt!65?LSibdikyfDF&h&}l2rV- zfcuGO18Gw_mAMu{#0J7^Yc8lK`})QJ8){U$e7MZ3ZwkkiSYiS9{hn!r#PcD%xD6Hi z5EMYwUeV?*^~>xL$2W}pe0KO4+3GsOtLwdRiKK=sn~&>!f(>ofur4tztdU8-c!lh2 zQW9pJ9XzqBAN6($1CN%p^)UkGUwA$fLfDuPFO|jS)zo zhJwx7xaq%a6H>V6>9)C^VY~{Cu3UhiNKUe>uc0F-XoPhdbHjip2o{z{gue8_Tzp)< zzf-pi-Ld)B506+6;*JInU&;rvilM~!4JwyZ6kS;`8J9e4RI^j^u{b>CS}E2S5Mjwg zQBrvBhiLAX2y~-3yU_v<>-@)+`5#*%5GYs@!B?D`y*(im;o?Jwys1;TpKk#GBTeYw zNCd;}f>fFMQ*_1g$QUCFLd@jTPL-C^?Nv?aM22H)6V3~@#eH)ctFw>vjGFXP>;lXX z(gEWG$hH-G1b1pJf3j-0jbGN$t>p^W0*iJEBhCWXV_A@_51b>mlzGj;A1g8oWt5K_ zKbcwDP3#VQ0)#!RVq|L+tm2s-YevjDqbkwg5OH!-_^RW6 z@g`vowJir}&P|Z^4_BI(o4Oq7b!ssp8mHYo?zEEjQ zT~AFemqfR{Os@8+Bx+;4+ddBtj`5F=!(d@!E_Y-vVAguS@2_dwcsbt(!1rOLes*$x zJT?;31IvC*OF1i7zPvxT=}A*$N2o^&phMt6=zt_0#X{hTn|OE7I0LUs%xjyrSut=YVqYm za|Qh+Y{RGIBTki<`AZj-&q3D$sP&^(g^s{LuEEU$URfpK3q=)n*=RK~2*zS}Vj>7? zEg466+Y}qzG>(s+XxwnZo_ZgR?&1hoqnWQ`E85iF`Llu>A|;6}g;a)VDKs$-`8*ST zRMTdY4yqF3s7H2zmHGufE6RpO!+&AQ{;nz3*dy<6Dr+dlfFcP^ub6jtlN19=`_RNy zt)~F-w&qkw!4E10Pe)!IW4{XgLzwux80}zOO$xO^*uEC7m;g1QZ?cqiF4L=x%F$Lo ziAE*&6sfxgi0h6phkEycSq5jk4zh5LPF<|4y$x=xYdN!oB@rtHG?J{*&El$Zd|=aA zYT@{~B-x4s2j&#MJg~99^aN^p?xB9oZW{$jvX=es*)DWtl|7sAFS|GQs=Mc!X@SIf zqLb1j$`bWP!lWtv<`n9jKGcHIts*z2jc5KQX-HG3kF<`llg9-{^?1ZHi`g?Kc*7HM zNJVxEN+oN*T(Q)9%SP&D8Mj?6uMH|N%9gd8p_7V=1xB~U!0ZQM$VW|W$?PHt0sW&C zo`@UjtyYXs8n}`g@ft;Va-vvgfN05PRLMh%Ndu#x1wi_@SankjX#&`uwpZLSi1Q-0 z*B^_D4i0=$kyW(cfTX9diLqqh33+0832*_g5PV(fh7<9HI%VU`jRw)Xb&R#rOdHn=n##p!RimVM2$>Ikg81{s zv#9#R?+&1kLk0oeWLR%nXY9`)C$-9ji{Cuz$k_4wGW3tkDXNebMFfk{pNUe3jF+Q~ zEnpOCEhCmVZc}4c^`467gkYnNd%(_$fK0RB9Ir>YUI$ivffgdo;6OoDdJyrb7Yq!! ziay*TUau<$2B|vG30B@w=xTON*Yd%Ja$LKj-qZx_Vns3OjEqH6<&Az8(GV2Dhu&2$ zMS6Xr%D*_MyMOY#X|oFb@<0L;o}Y6nCg*hD+KvtVoIaR|iJ6&+4au7tK714z^-b!1 z>p_#mZHC(EkCyTAE0Kg4`^m@SWL{`Cz}FDjGQpa;Z~{6&!Pb=6K#Hd5{9sbp#kNw8*~I zP|i-E68cbjhRQ42^%Ks$HWba^x+GK6w!_PZBw)dY@r5S%*KtY~;z>W%d!i{d-JW{-M<`H~EjL?#rEV-= z@?K^9>Vw=LBQpjgPo}9XrPOG+&&kh(bY^5eSFK_oJDLn47(0Mf!71D^;rVzy{WKO> zoZvmR5#){&)9j=)<0P5Xyo}M5o9fnszH~W+CL6(eYb{;fmN$Yjac`6tA=?ZRu zXJLwU4U=^;rsT+T8ZJWlFeT@ulJE1to_`@7g%)+?gZwhFTrc5&%d&x;swm{6iV*ga zTyDxmS+XY(dSS+`(nOZ=`vf`l!Awmtu29vL(*6rKoKfny4)YWi`AYAOro~Cgr@b zb>QWAi*Qk$X$)E&LmeHcwdEqG*bzIsVvb?2l$it)DJ#Qq$BGVt(#N7(dP;m)s3|CU zEKxrY6M0eZtQ^gbzWd! zpQ`Xf-Zos~d(o2SUkhjD(ah!XjO9gE$%}Tg)pS@r!bwi|^cq5YZJXb3yq)>&TV;N% z>TINZte%|qJ5<_aKCJ5KEUZ^O$4v6C7>Bi2-Cy&9?1MCVkmhR=IQsK2vayyBQ z9#yrpl2NwAw?U3ls?`KLMRhwX*fdgDoDI(w z!!_!%=(lv)4&yurARD=`r<|TyPMr51lD3VRTWZxbUY?swT%A*GOv8?|%)m0HPw$)k zz(y5Kf91!V8iniC}1TMqJl^HL?e71<)fAFRo{C(ibmjHin#z-Ciwg!03G7k&#~4 zg}OvRBB)Xdk*Iv<CQ)If8kKFIc~gw0zp07)num7<^6tvrQw8qs=dvT@7GEkw=W}t+L59JbUFcf zLBMqHm|f!f*OK8Ub#+BT0FgS9zGL5A;9xvF=r;ucxG}PC>Gi8>>-=DQABpv)vMF~X z(b+%B)h9Yyo)-tArJi+P_pvzUe`=^Sd+%+--^Cxas@SH5jo{+lZKiejBv0>uI!j?l zG>TSP8jJ?oD-9Qf#93|@>xGjU2-q}?*Z95P_o(DWK)UIp0`nB0%IjrxT1_uEv-fpg zludAjd|A;TV)2CbM??=f=(q~#Yay_VFs{lP8Bn?GM@D~9cq7-%fuqa;j($UN7%`(1 zIwyxU2(&Eaj2}x>YE0mt$zQMIMHj}&izlL*3zM7%q+NBBAj{!7?+|LL(Xnh!CBp2O zl4kX0fHbPjv%G80^n^RKxhxTugf;3b#^V1~dyl0aOmP$F83&sZi%LeE-tS3JH~|O) zL_i~ioGKb%Ef0EB_&n8==0Dbmc=+MQ>yZZ z7Pg66#ZwogrQC_9t=UbyKf7w#%E5PD^tsdcN5WA@RaXCbh67Lh>CEp-bVT?gaBpdC z&HULLK0P1Lj3Q#Si-znCu@4=?FD&yRXV!Hy^Ud|zd^&sdcy3U=d0+$xxW+Z#S91l9 z@*J7>U43+MswNN>5Z*$6g=)md*{n^!C;KYS;5lNhXXCWvgg!W&uYR22^l@_+ogBJ9 zldP8ZtbjFP%O-Bt8+u!6(W*`n`{q8!JZL058rj3@%vWyXw!qAgCV_ z_$bPOAT=#UZ}%=E^7`>E^KPReFM6Em@KM>WAQE+45cIQmhwyC}p@FwH^HMojZC8%d zd}3}Y&k@ZFY=R{o_Z%g5L^0664l-+Qr=^F^m{oju$o*~1{xN7Yz-36xJ|&~8*2WZO zv*nghEZ3yE-iYT8@J@9l`o&Eaw#N*R3O~L0-q#iTo-LA6*VRy%N$)Ra-j^>=_XS8w`u=1qE7>SKxX~u**IK(4cw^{D!2^ z7#uxxP4$DBVOA41#UMRA_+YzWBA#>_*+@_0iRXcv4)ZGGSZW)_>OLB zcqG_T;v+VBZx0{6&`!3h={l9z7G3~6!qn=F=V_(ZblO>i zQz_GDAouu7NOeE(;sQ2Vo>HW`HM)S^Q^%qRLIM&QCn4~t%p7#U=M$*8B0Ribv30WwjhT;)_+NxzcaFc zBD={!Czwcrt9u4;8AajF`LaV2&09ycjhUR)7x4jp8f9&~EUQ zplcg24sbRW<+U6QkFW#^xgOo?AcBP_eM>6MDZE8@{Gi%S*jtYX*|5{!kSF)k)RP5t zFJdWd56lsE(6@TggpwO$0c!+NbuzsVB~Jocx2yRx4q*JfPvCR8iwW^9PIR7(!DmoK z#)OcbV(7N?s&FKQgQ&T@K5V;LF>>(DcGZs!-l&7v=k=&@@JqY1)zS+pQFh+3XSd#{ zi{}t7Pe#Adfiws$Bv}G>d0zUdWrjl;GErS#qc_dzZ1_6|z7CjYq(Yq>UwBMbFeoKI zOl$k5Scs1$XrA%llZD~l6U?6%NS{-BJZ%bpi@xqT3bO4vcv~i1O)=k3qyg^33y9jJ z)5q@7x2J=CD-Ni=@;mak>OcXBwTk{us;w4o+bjMY*J?oOZ{3ZU?N98=uR%Qv)t5-Y z`vY5?!9M3f4m!f&2iBd*Q??C&?_FDvFxlC5Vc8C>I{`CDmrF&`R}3)OKWW3V*|*}K zF72op^$N&Pr0rOrV#%|1FJr$(Vsh`=>i?4Bga`A9_S?aXQtF(N&vs4dfrkk`=)r>l zWAp6X>TCwD_U-Y8d0}mx(4%Q+TmbNpl>Jz@uFmT5xQIgDSb@Gkg1k7t550&AasleL z#%b-*QvsPxe1O~7mkkeI#<)aosE_YS53I_Adp8a`b6)J(p@ZY39gK7*C|SXn;Xobiy9ov z_DapH{;EaH*{eqyjE9Mx0qf5OW#7pQ13T$>1pou&Eb!4VS=mW-e*y^du+j&}a(lLi z{9=FTU(X#liDA*^B0$4(+Y8Cn()sqpeC5rtsxtrx;2*QmgTKFm+Ytp{eg~e?hmCwF zC-R_A6=Q+`WDGt#rC+|63ZqP(sCUXW$-vnmqEhnBw_;ePh<}#)a4-sc{cM{&lB?7<)%5YOH2!kCpw-=@bugxnz z<^20Cd!f_Hx;f&C2)~Ea>erk#u9QXFCa~<*0WdR470I2+Bmwf^Z;+3<*FriprUn2s z!G_^NlKU|UDb&Pc!M%>6hp^bEOFej50+`3lQ390X;+BlPwjukQ`DloI8Id21;SHbb^n-RKyG&?t%jeLo$RxV5YKz!%ETH3$q3Ck9LgR)7LjbGGm9M zm}FO1t?_Gk`8W`Hw}HI$c?>7{03uG$&;ASj)9)13r*4CliRr)Mc{BVG=J;LV@eiot zuM{4C(wix?M19g#r*}w{G<|&Z*(AKQaGK~SZn)Ciyr2H*cU1(_UzZ!fwGK^R$Sk9h zYFm2n8ojx^*r;xP9^<%SO_-_7wDx9LpKwKsK_Ai6%<+}6M!&oyzeX>3mmSA>davF) za#78w|3538yQ+TL+1vBvU%f1jY5%e^$m{C;VxP)5y;m>4zn;19bM5VaOR}TNu7(_6 z+?A>Ibl<%YLjP|U>jt-F*1Rsh`f_8y>}5Kv=0|)Fx^e4yAMBCtl<(kwp#CZN;9C6%bN1i@ z1@(r<>IYLbcc|ty+HPc@zn7`%=ZOlIG}(TugOid4`Fq-%bRUO3y7GA8ap|NNg-86h zd|h+7`S8BDUzgbV<@YF;J=h%Xu>OD*W9c7N)QdmXFU{zs5J5{QiJFi~GVgsVcs+YgOH3563je9FI}ox#xI8HP09O1NFXh zrL35Xo1aX2|K#4w*^T*YC&x+c%lu^eW7aRzFVU~ITv+*XVOx9K4UT1O%)D*)q;~4R zDtsjU{>mdi*=oy+$L?%;FmeC>G@J4>Pmjy=exGxir2Fyh zqQCxONmQ^+QouxIVhLZvXo9>`0I|La=c2k0PwyxXZ?r{qlx~|cH8lrrn=%J(n=&*9 zZkqybXMmg;PSM>{Kx2sBHf4-{c@QkH$k;Z8CxmeCm@`Yv$QN++USAY`L2aBwD`z>AJm2#OGd!rfA{CwcS(l zmO5`xWb2x!!uR+4+KGDRGT%Q6uxN8$^;cb?bj{?!_w$PmvZt0LF#Nc>k4bKVz>bGA z*PL5h%(8KtZ|}j~*R8Vpb3(3J2RJ@o_3P=fWt=l}kPdOz^)xuZQhW>Vv(6ARXGrS87xru~#z;H2*S zgUdHY=Y*whh~Qj>&~VPfnguKNxrC#2;s|!c97pN@vPk zkuCkaQhiy~!A8MrEsVPh*#9t|O_4i>8Jfi^a}0FcT? A^Z)<= literal 0 HcmV?d00001 diff --git a/ext/qoi/.gitignore b/ext/qoi/.gitignore new file mode 100644 index 0000000..9234e61 --- /dev/null +++ b/ext/qoi/.gitignore @@ -0,0 +1,5 @@ +images/ +stb_image.h +stb_image_write.h +qoibench +qoiconv diff --git a/ext/qoi/README.md b/ext/qoi/README.md new file mode 100644 index 0000000..702c342 --- /dev/null +++ b/ext/qoi/README.md @@ -0,0 +1,92 @@ +![QOI Logo](https://qoiformat.org/qoi-logo.svg) + +# QOI - The “Quite OK Image Format” for fast, lossless image compression + +Single-file MIT licensed library for C/C++ + +See [qoi.h](https://github.com/phoboslab/qoi/blob/master/qoi.h) for +the documentation and format specification. + +More info at https://qoiformat.org + + +## Why? + +Compared to stb_image and stb_image_write QOI offers 20x-50x faster encoding, +3x-4x faster decoding and 20% better compression. It's also stupidly simple and +fits in about 300 lines of C. + + +## Example Usage + +- [qoiconv.c](https://github.com/phoboslab/qoi/blob/master/qoiconv.c) +converts between png <> qoi + - [qoibench.c](https://github.com/phoboslab/qoi/blob/master/qoibench.c) +a simple wrapper to benchmark stbi, libpng and qoi + + +## Limitations + +The QOI file format allows for huge images with up to 18 exa-pixels. A streaming +en-/decoder can handle these with minimal RAM requirements, assuming there is +enough storage space. + +This particular implementation of QOI however is limited to images with a +maximum size of 400 million pixels. It will safely refuse to en-/decode anything +larger than that. This is not a streaming en-/decoder. It loads the whole image +file into RAM before doing any work and is not extensively optimized for +performance (but it's still very fast). + +If this is a limitation for your use case, please look into any of the other +implementations listed below. + + +## Tools + +- https://github.com/floooh/qoiview - native QOI viewer +- https://github.com/pfusik/qoi-ci/releases/tag/qoi-ci-1.1.0 - QOI Plugin installer for GIMP, Imagine, Paint.NET and XnView MP +- https://github.com/iOrange/QoiFileTypeNet/releases/tag/v0.2 - QOI Plugin for Paint.NET +- https://github.com/iOrange/QOIThumbnailProvider - Add thumbnails for QOI images in Windows Explorer +- https://github.com/Tom94/tev - another native QOI viewer (allows pixel peeping and comparison with other image formats) + + +## Implementations & Bindings of QOI + +- https://github.com/pfusik/qoi-ci (Ć, transpiled to C, C++, C#, Java, JavaScript, Python and Swift) +- https://github.com/kodonnell/qoi (Python) +- https://github.com/Cr4xy/lua-qoi (Lua) +- https://github.com/superzazu/SDL_QOI (C, SDL2 bindings) +- https://github.com/saharNooby/qoi-java (Java) +- https://github.com/MasterQ32/zig-qoi (Zig) +- https://github.com/rbino/qoix (Elixir) +- https://github.com/NUlliiON/QoiSharp (C#) +- https://github.com/zakarumych/rapid-qoi (Rust) +- https://github.com/takeyourhatoff/qoi (Go) +- https://github.com/DosWorld/pasqoi (Pascal) +- https://github.com/elihwyma/Swift-QOI (Swift) +- https://github.com/xfmoulet/qoi (Go) +- https://erratique.ch/software/qoic (OCaml) + + +## QOI Support in Other Software + +- [SerenityOS](https://github.com/SerenityOS/serenity) supports decoding QOI system wide through a custom [cpp implementation in LibGfx](https://github.com/SerenityOS/serenity/blob/master/Userland/Libraries/LibGfx/QOILoader.h) +- [Raylib](https://github.com/raysan5/raylib) supports decoding and encoding QOI textures through its [rtextures module](https://github.com/raysan5/raylib/blob/master/src/rtextures.c) +- [Rebol3](https://github.com/Oldes/Rebol3/issues/39) supports decoding and encoding QOI using a native codec +- [c-ray](https://github.com/vkoskiv/c-ray) supports QOI natively + + +## Packages + +[AUR](https://aur.archlinux.org/pkgbase/qoi-git/) - system-wide qoi.h, qoiconv and qoibench install as split packages. + + +## Implementations not yet conforming to the final specification + +These implementations are based on the pre-release version of QOI. Resulting files are not compatible with the current version. + +- https://github.com/steven-joruk/qoi (Rust) +- https://github.com/ChevyRay/qoi_rs (Rust) +- https://github.com/panzi/jsqoi (TypeScript) +- https://github.com/0xd34df00d/hsqoi (Haskell) + diff --git a/ext/qoi/qoi.h b/ext/qoi/qoi.h new file mode 100644 index 0000000..7addd70 --- /dev/null +++ b/ext/qoi/qoi.h @@ -0,0 +1,671 @@ +/* + +QOI - The "Quite OK Image" format for fast, lossless image compression + +Dominic Szablewski - https://phoboslab.org + + +-- LICENSE: The MIT License(MIT) + +Copyright(c) 2021 Dominic Szablewski + +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. + + +-- About + +QOI encodes and decodes images in a lossless format. Compared to stb_image and +stb_image_write QOI offers 20x-50x faster encoding, 3x-4x faster decoding and +20% better compression. + + +-- Synopsis + +// Define `QOI_IMPLEMENTATION` in *one* C/C++ file before including this +// library to create the implementation. + +#define QOI_IMPLEMENTATION +#include "qoi.h" + +// Encode and store an RGBA buffer to the file system. The qoi_desc describes +// the input pixel data. +qoi_write("image_new.qoi", rgba_pixels, &(qoi_desc){ + .width = 1920, + .height = 1080, + .channels = 4, + .colorspace = QOI_SRGB +}); + +// Load and decode a QOI image from the file system into a 32bbp RGBA buffer. +// The qoi_desc struct will be filled with the width, height, number of channels +// and colorspace read from the file header. +qoi_desc desc; +void *rgba_pixels = qoi_read("image.qoi", &desc, 4); + + + +-- Documentation + +This library provides the following functions; +- qoi_read -- read and decode a QOI file +- qoi_decode -- decode the raw bytes of a QOI image from memory +- qoi_write -- encode and write a QOI file +- qoi_encode -- encode an rgba buffer into a QOI image in memory + +See the function declaration below for the signature and more information. + +If you don't want/need the qoi_read and qoi_write functions, you can define +QOI_NO_STDIO before including this library. + +This library uses malloc() and free(). To supply your own malloc implementation +you can define QOI_MALLOC and QOI_FREE before including this library. + +This library uses memset() to zero-initialize the index. To supply your own +implementation you can define QOI_ZEROARR before including this library. + + +-- Data Format + +A QOI file has a 14 byte header, followed by any number of data "chunks" and an +8-byte end marker. + +struct qoi_header_t { + char magic[4]; // magic bytes "qoif" + uint32_t width; // image width in pixels (BE) + uint32_t height; // image height in pixels (BE) + uint8_t channels; // 3 = RGB, 4 = RGBA + uint8_t colorspace; // 0 = sRGB with linear alpha, 1 = all channels linear +}; + +Images are encoded row by row, left to right, top to bottom. The decoder and +encoder start with {r: 0, g: 0, b: 0, a: 255} as the previous pixel value. An +image is complete when all pixels specified by width * height have been covered. + +Pixels are encoded as + - a run of the previous pixel + - an index into an array of previously seen pixels + - a difference to the previous pixel value in r,g,b + - full r,g,b or r,g,b,a values + +The color channels are assumed to not be premultiplied with the alpha channel +("un-premultiplied alpha"). + +A running array[64] (zero-initialized) of previously seen pixel values is +maintained by the encoder and decoder. Each pixel that is seen by the encoder +and decoder is put into this array at the position formed by a hash function of +the color value. In the encoder, if the pixel value at the index matches the +current pixel, this index position is written to the stream as QOI_OP_INDEX. +The hash function for the index is: + + index_position = (r * 3 + g * 5 + b * 7 + a * 11) % 64 + +Each chunk starts with a 2- or 8-bit tag, followed by a number of data bits. The +bit length of chunks is divisible by 8 - i.e. all chunks are byte aligned. All +values encoded in these data bits have the most significant bit on the left. + +The 8-bit tags have precedence over the 2-bit tags. A decoder must check for the +presence of an 8-bit tag first. + +The byte stream's end is marked with 7 0x00 bytes followed a single 0x01 byte. + + +The possible chunks are: + + +.- QOI_OP_INDEX ----------. +| Byte[0] | +| 7 6 5 4 3 2 1 0 | +|-------+-----------------| +| 0 0 | index | +`-------------------------` +2-bit tag b00 +6-bit index into the color index array: 0..63 + +A valid encoder must not issue 7 or more consecutive QOI_OP_INDEX chunks to the +index 0, to avoid confusion with the 8 byte end marker. + + +.- QOI_OP_DIFF -----------. +| Byte[0] | +| 7 6 5 4 3 2 1 0 | +|-------+-----+-----+-----| +| 0 1 | dr | dg | db | +`-------------------------` +2-bit tag b01 +2-bit red channel difference from the previous pixel between -2..1 +2-bit green channel difference from the previous pixel between -2..1 +2-bit blue channel difference from the previous pixel between -2..1 + +The difference to the current channel values are using a wraparound operation, +so "1 - 2" will result in 255, while "255 + 1" will result in 0. + +Values are stored as unsigned integers with a bias of 2. E.g. -2 is stored as +0 (b00). 1 is stored as 3 (b11). + +The alpha value remains unchanged from the previous pixel. + + +.- QOI_OP_LUMA -------------------------------------. +| Byte[0] | Byte[1] | +| 7 6 5 4 3 2 1 0 | 7 6 5 4 3 2 1 0 | +|-------+-----------------+-------------+-----------| +| 1 0 | green diff | dr - dg | db - dg | +`---------------------------------------------------` +2-bit tag b10 +6-bit green channel difference from the previous pixel -32..31 +4-bit red channel difference minus green channel difference -8..7 +4-bit blue channel difference minus green channel difference -8..7 + +The green channel is used to indicate the general direction of change and is +encoded in 6 bits. The red and blue channels (dr and db) base their diffs off +of the green channel difference and are encoded in 4 bits. I.e.: + dr_dg = (last_px.r - cur_px.r) - (last_px.g - cur_px.g) + db_dg = (last_px.b - cur_px.b) - (last_px.g - cur_px.g) + +The difference to the current channel values are using a wraparound operation, +so "10 - 13" will result in 253, while "250 + 7" will result in 1. + +Values are stored as unsigned integers with a bias of 32 for the green channel +and a bias of 8 for the red and blue channel. + +The alpha value remains unchanged from the previous pixel. + + +.- QOI_OP_RUN ------------. +| Byte[0] | +| 7 6 5 4 3 2 1 0 | +|-------+-----------------| +| 1 1 | run | +`-------------------------` +2-bit tag b11 +6-bit run-length repeating the previous pixel: 1..62 + +The run-length is stored with a bias of -1. Note that the run-lengths 63 and 64 +(b111110 and b111111) are illegal as they are occupied by the QOI_OP_RGB and +QOI_OP_RGBA tags. + + +.- QOI_OP_RGB ------------------------------------------. +| Byte[0] | Byte[1] | Byte[2] | Byte[3] | +| 7 6 5 4 3 2 1 0 | 7 .. 0 | 7 .. 0 | 7 .. 0 | +|-------------------------+---------+---------+---------| +| 1 1 1 1 1 1 1 0 | red | green | blue | +`-------------------------------------------------------` +8-bit tag b11111110 +8-bit red channel value +8-bit green channel value +8-bit blue channel value + +The alpha value remains unchanged from the previous pixel. + + +.- QOI_OP_RGBA ---------------------------------------------------. +| Byte[0] | Byte[1] | Byte[2] | Byte[3] | Byte[4] | +| 7 6 5 4 3 2 1 0 | 7 .. 0 | 7 .. 0 | 7 .. 0 | 7 .. 0 | +|-------------------------+---------+---------+---------+---------| +| 1 1 1 1 1 1 1 1 | red | green | blue | alpha | +`-----------------------------------------------------------------` +8-bit tag b11111111 +8-bit red channel value +8-bit green channel value +8-bit blue channel value +8-bit alpha channel value + +*/ + + +/* ----------------------------------------------------------------------------- +Header - Public functions */ + +#ifndef QOI_H +#define QOI_H + +#ifdef __cplusplus +extern "C" { +#endif + +/* A pointer to a qoi_desc struct has to be supplied to all of qoi's functions. +It describes either the input format (for qoi_write and qoi_encode), or is +filled with the description read from the file header (for qoi_read and +qoi_decode). + +The colorspace in this qoi_desc is an enum where + 0 = sRGB, i.e. gamma scaled RGB channels and a linear alpha channel + 1 = all channels are linear +You may use the constants QOI_SRGB or QOI_LINEAR. The colorspace is purely +informative. It will be saved to the file header, but does not affect +en-/decoding in any way. */ + +#define QOI_SRGB 0 +#define QOI_LINEAR 1 + +typedef struct { + unsigned int width; + unsigned int height; + unsigned char channels; + unsigned char colorspace; +} qoi_desc; + +#ifndef QOI_NO_STDIO + +/* Encode raw RGB or RGBA pixels into a QOI image and write it to the file +system. The qoi_desc struct must be filled with the image width, height, +number of channels (3 = RGB, 4 = RGBA) and the colorspace. + +The function returns 0 on failure (invalid parameters, or fopen or malloc +failed) or the number of bytes written on success. */ + +int qoi_write(const char *filename, const void *data, const qoi_desc *desc); + + +/* Read and decode a QOI image from the file system. If channels is 0, the +number of channels from the file header is used. If channels is 3 or 4 the +output format will be forced into this number of channels. + +The function either returns NULL on failure (invalid data, or malloc or fopen +failed) or a pointer to the decoded pixels. On success, the qoi_desc struct +will be filled with the description from the file header. + +The returned pixel data should be free()d after use. */ + +void *qoi_read(const char *filename, qoi_desc *desc, int channels); + +#endif /* QOI_NO_STDIO */ + + +/* Encode raw RGB or RGBA pixels into a QOI image in memory. + +The function either returns NULL on failure (invalid parameters or malloc +failed) or a pointer to the encoded data on success. On success the out_len +is set to the size in bytes of the encoded data. + +The returned qoi data should be free()d after use. */ + +void *qoi_encode(const void *data, const qoi_desc *desc, int *out_len); + + +/* Decode a QOI image from memory. + +The function either returns NULL on failure (invalid parameters or malloc +failed) or a pointer to the decoded pixels. On success, the qoi_desc struct +is filled with the description from the file header. + +The returned pixel data should be free()d after use. */ + +void *qoi_decode(const void *data, int size, qoi_desc *desc, int channels); + + +#ifdef __cplusplus +} +#endif +#endif /* QOI_H */ + + +/* ----------------------------------------------------------------------------- +Implementation */ + +#ifdef QOI_IMPLEMENTATION +#include +#include + +#ifndef QOI_MALLOC + #define QOI_MALLOC(sz) malloc(sz) + #define QOI_FREE(p) free(p) +#endif +#ifndef QOI_ZEROARR + #define QOI_ZEROARR(a) memset((a),0,sizeof(a)) +#endif + +#define QOI_OP_INDEX 0x00 /* 00xxxxxx */ +#define QOI_OP_DIFF 0x40 /* 01xxxxxx */ +#define QOI_OP_LUMA 0x80 /* 10xxxxxx */ +#define QOI_OP_RUN 0xc0 /* 11xxxxxx */ +#define QOI_OP_RGB 0xfe /* 11111110 */ +#define QOI_OP_RGBA 0xff /* 11111111 */ + +#define QOI_MASK_2 0xc0 /* 11000000 */ + +#define QOI_COLOR_HASH(C) (C.rgba.r*3 + C.rgba.g*5 + C.rgba.b*7 + C.rgba.a*11) +#define QOI_MAGIC \ + (((unsigned int)'q') << 24 | ((unsigned int)'o') << 16 | \ + ((unsigned int)'i') << 8 | ((unsigned int)'f')) +#define QOI_HEADER_SIZE 14 + +/* 2GB is the max file size that this implementation can safely handle. We guard +against anything larger than that, assuming the worst case with 5 bytes per +pixel, rounded down to a nice clean value. 400 million pixels ought to be +enough for anybody. */ +#define QOI_PIXELS_MAX ((unsigned int)400000000) + +typedef union { + struct { unsigned char r, g, b, a; } rgba; + unsigned int v; +} qoi_rgba_t; + +static const unsigned char qoi_padding[8] = {0,0,0,0,0,0,0,1}; + +static void qoi_write_32(unsigned char *bytes, int *p, unsigned int v) { + bytes[(*p)++] = (0xff000000 & v) >> 24; + bytes[(*p)++] = (0x00ff0000 & v) >> 16; + bytes[(*p)++] = (0x0000ff00 & v) >> 8; + bytes[(*p)++] = (0x000000ff & v); +} + +static unsigned int qoi_read_32(const unsigned char *bytes, int *p) { + unsigned int a = bytes[(*p)++]; + unsigned int b = bytes[(*p)++]; + unsigned int c = bytes[(*p)++]; + unsigned int d = bytes[(*p)++]; + return a << 24 | b << 16 | c << 8 | d; +} + +void *qoi_encode(const void *data, const qoi_desc *desc, int *out_len) { + int i, max_size, p, run; + int px_len, px_end, px_pos, channels; + unsigned char *bytes; + const unsigned char *pixels; + qoi_rgba_t index[64]; + qoi_rgba_t px, px_prev; + + if ( + data == NULL || out_len == NULL || desc == NULL || + desc->width == 0 || desc->height == 0 || + desc->channels < 3 || desc->channels > 4 || + desc->colorspace > 1 || + desc->height >= QOI_PIXELS_MAX / desc->width + ) { + return NULL; + } + + max_size = + desc->width * desc->height * (desc->channels + 1) + + QOI_HEADER_SIZE + sizeof(qoi_padding); + + p = 0; + bytes = (unsigned char *) QOI_MALLOC(max_size); + if (!bytes) { + return NULL; + } + + qoi_write_32(bytes, &p, QOI_MAGIC); + qoi_write_32(bytes, &p, desc->width); + qoi_write_32(bytes, &p, desc->height); + bytes[p++] = desc->channels; + bytes[p++] = desc->colorspace; + + + pixels = (const unsigned char *)data; + + QOI_ZEROARR(index); + + run = 0; + px_prev.rgba.r = 0; + px_prev.rgba.g = 0; + px_prev.rgba.b = 0; + px_prev.rgba.a = 255; + px = px_prev; + + px_len = desc->width * desc->height * desc->channels; + px_end = px_len - desc->channels; + channels = desc->channels; + + for (px_pos = 0; px_pos < px_len; px_pos += channels) { + if (channels == 4) { + px = *(qoi_rgba_t *)(pixels + px_pos); + } + else { + px.rgba.r = pixels[px_pos + 0]; + px.rgba.g = pixels[px_pos + 1]; + px.rgba.b = pixels[px_pos + 2]; + } + + if (px.v == px_prev.v) { + run++; + if (run == 62 || px_pos == px_end) { + bytes[p++] = QOI_OP_RUN | (run - 1); + run = 0; + } + } + else { + int index_pos; + + if (run > 0) { + bytes[p++] = QOI_OP_RUN | (run - 1); + run = 0; + } + + index_pos = QOI_COLOR_HASH(px) % 64; + + if (index[index_pos].v == px.v) { + bytes[p++] = QOI_OP_INDEX | index_pos; + } + else { + index[index_pos] = px; + + if (px.rgba.a == px_prev.rgba.a) { + signed char vr = px.rgba.r - px_prev.rgba.r; + signed char vg = px.rgba.g - px_prev.rgba.g; + signed char vb = px.rgba.b - px_prev.rgba.b; + + signed char vg_r = vr - vg; + signed char vg_b = vb - vg; + + if ( + vr > -3 && vr < 2 && + vg > -3 && vg < 2 && + vb > -3 && vb < 2 + ) { + bytes[p++] = QOI_OP_DIFF | (vr + 2) << 4 | (vg + 2) << 2 | (vb + 2); + } + else if ( + vg_r > -9 && vg_r < 8 && + vg > -33 && vg < 32 && + vg_b > -9 && vg_b < 8 + ) { + bytes[p++] = QOI_OP_LUMA | (vg + 32); + bytes[p++] = (vg_r + 8) << 4 | (vg_b + 8); + } + else { + bytes[p++] = QOI_OP_RGB; + bytes[p++] = px.rgba.r; + bytes[p++] = px.rgba.g; + bytes[p++] = px.rgba.b; + } + } + else { + bytes[p++] = QOI_OP_RGBA; + bytes[p++] = px.rgba.r; + bytes[p++] = px.rgba.g; + bytes[p++] = px.rgba.b; + bytes[p++] = px.rgba.a; + } + } + } + px_prev = px; + } + + for (i = 0; i < (int)sizeof(qoi_padding); i++) { + bytes[p++] = qoi_padding[i]; + } + + *out_len = p; + return bytes; +} + +void *qoi_decode(const void *data, int size, qoi_desc *desc, int channels) { + const unsigned char *bytes; + unsigned int header_magic; + unsigned char *pixels; + qoi_rgba_t index[64]; + qoi_rgba_t px; + int px_len, chunks_len, px_pos; + int p = 0, run = 0; + + if ( + data == NULL || desc == NULL || + (channels != 0 && channels != 3 && channels != 4) || + size < QOI_HEADER_SIZE + (int)sizeof(qoi_padding) + ) { + return NULL; + } + + bytes = (const unsigned char *)data; + + header_magic = qoi_read_32(bytes, &p); + desc->width = qoi_read_32(bytes, &p); + desc->height = qoi_read_32(bytes, &p); + desc->channels = bytes[p++]; + desc->colorspace = bytes[p++]; + + if ( + desc->width == 0 || desc->height == 0 || + desc->channels < 3 || desc->channels > 4 || + desc->colorspace > 1 || + header_magic != QOI_MAGIC || + desc->height >= QOI_PIXELS_MAX / desc->width + ) { + return NULL; + } + + if (channels == 0) { + channels = desc->channels; + } + + px_len = desc->width * desc->height * channels; + pixels = (unsigned char *) QOI_MALLOC(px_len); + if (!pixels) { + return NULL; + } + + QOI_ZEROARR(index); + px.rgba.r = 0; + px.rgba.g = 0; + px.rgba.b = 0; + px.rgba.a = 255; + + chunks_len = size - (int)sizeof(qoi_padding); + for (px_pos = 0; px_pos < px_len; px_pos += channels) { + if (run > 0) { + run--; + } + else if (p < chunks_len) { + int b1 = bytes[p++]; + + if (b1 == QOI_OP_RGB) { + px.rgba.r = bytes[p++]; + px.rgba.g = bytes[p++]; + px.rgba.b = bytes[p++]; + } + else if (b1 == QOI_OP_RGBA) { + px.rgba.r = bytes[p++]; + px.rgba.g = bytes[p++]; + px.rgba.b = bytes[p++]; + px.rgba.a = bytes[p++]; + } + else if ((b1 & QOI_MASK_2) == QOI_OP_INDEX) { + px = index[b1]; + } + else if ((b1 & QOI_MASK_2) == QOI_OP_DIFF) { + px.rgba.r += ((b1 >> 4) & 0x03) - 2; + px.rgba.g += ((b1 >> 2) & 0x03) - 2; + px.rgba.b += ( b1 & 0x03) - 2; + } + else if ((b1 & QOI_MASK_2) == QOI_OP_LUMA) { + int b2 = bytes[p++]; + int vg = (b1 & 0x3f) - 32; + px.rgba.r += vg - 8 + ((b2 >> 4) & 0x0f); + px.rgba.g += vg; + px.rgba.b += vg - 8 + (b2 & 0x0f); + } + else if ((b1 & QOI_MASK_2) == QOI_OP_RUN) { + run = (b1 & 0x3f); + } + + index[QOI_COLOR_HASH(px) % 64] = px; + } + + if (channels == 4) { + *(qoi_rgba_t*)(pixels + px_pos) = px; + } + else { + pixels[px_pos + 0] = px.rgba.r; + pixels[px_pos + 1] = px.rgba.g; + pixels[px_pos + 2] = px.rgba.b; + } + } + + return pixels; +} + +#ifndef QOI_NO_STDIO +#include + +int qoi_write(const char *filename, const void *data, const qoi_desc *desc) { + FILE *f = fopen(filename, "wb"); + int size; + void *encoded; + + if (!f) { + return 0; + } + + encoded = qoi_encode(data, desc, &size); + if (!encoded) { + fclose(f); + return 0; + } + + fwrite(encoded, 1, size, f); + fclose(f); + + QOI_FREE(encoded); + return size; +} + +void *qoi_read(const char *filename, qoi_desc *desc, int channels) { + FILE *f = fopen(filename, "rb"); + int size, bytes_read; + void *pixels, *data; + + if (!f) { + return NULL; + } + + fseek(f, 0, SEEK_END); + size = ftell(f); + if (size <= 0) { + fclose(f); + return NULL; + } + fseek(f, 0, SEEK_SET); + + data = QOI_MALLOC(size); + if (!data) { + fclose(f); + return NULL; + } + + bytes_read = fread(data, 1, size, f); + fclose(f); + + pixels = qoi_decode(data, bytes_read, desc, channels); + QOI_FREE(data); + return pixels; +} + +#endif /* QOI_NO_STDIO */ +#endif /* QOI_IMPLEMENTATION */ diff --git a/ext/qoi/qoibench.c b/ext/qoi/qoibench.c new file mode 100644 index 0000000..2c3df68 --- /dev/null +++ b/ext/qoi/qoibench.c @@ -0,0 +1,650 @@ +/* + +Simple benchmark suite for png, stbi and qoi + +Requires libpng, "stb_image.h" and "stb_image_write.h" +Compile with: + gcc qoibench.c -std=gnu99 -lpng -O3 -o qoibench + +Dominic Szablewski - https://phoboslab.org + + +-- LICENSE: The MIT License(MIT) + +Copyright(c) 2021 Dominic Szablewski + +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. + +*/ + +#include +#include +#include + +#define STB_IMAGE_IMPLEMENTATION +#define STBI_ONLY_PNG +#define STBI_NO_LINEAR +#include "stb_image.h" + +#define STB_IMAGE_WRITE_IMPLEMENTATION +#include "stb_image_write.h" + +#define QOI_IMPLEMENTATION +#include "qoi.h" + + + + +// ----------------------------------------------------------------------------- +// Cross platform high resolution timer +// From https://gist.github.com/ForeverZer0/0a4f80fc02b96e19380ebb7a3debbee5 + +#include +#if defined(__linux) + #define HAVE_POSIX_TIMER + #include + #ifdef CLOCK_MONOTONIC + #define CLOCKID CLOCK_MONOTONIC + #else + #define CLOCKID CLOCK_REALTIME + #endif +#elif defined(__APPLE__) + #define HAVE_MACH_TIMER + #include +#elif defined(_WIN32) + #define WIN32_LEAN_AND_MEAN + #include +#endif + +static uint64_t ns() { + static uint64_t is_init = 0; +#if defined(__APPLE__) + static mach_timebase_info_data_t info; + if (0 == is_init) { + mach_timebase_info(&info); + is_init = 1; + } + uint64_t now; + now = mach_absolute_time(); + now *= info.numer; + now /= info.denom; + return now; +#elif defined(__linux) + static struct timespec linux_rate; + if (0 == is_init) { + clock_getres(CLOCKID, &linux_rate); + is_init = 1; + } + uint64_t now; + struct timespec spec; + clock_gettime(CLOCKID, &spec); + now = spec.tv_sec * 1.0e9 + spec.tv_nsec; + return now; +#elif defined(_WIN32) + static LARGE_INTEGER win_frequency; + if (0 == is_init) { + QueryPerformanceFrequency(&win_frequency); + is_init = 1; + } + LARGE_INTEGER now; + QueryPerformanceCounter(&now); + return (uint64_t) ((1e9 * now.QuadPart) / win_frequency.QuadPart); +#endif +} + +#define STRINGIFY(x) #x +#define TOSTRING(x) STRINGIFY(x) +#define ERROR(...) printf("abort at line " TOSTRING(__LINE__) ": " __VA_ARGS__); printf("\n"); exit(1) + + +// ----------------------------------------------------------------------------- +// libpng encode/decode wrappers +// Seriously, who thought this was a good abstraction for an API to read/write +// images? + +typedef struct { + int size; + int capacity; + unsigned char *data; +} libpng_write_t; + +void libpng_encode_callback(png_structp png_ptr, png_bytep data, png_size_t length) { + libpng_write_t *write_data = (libpng_write_t*)png_get_io_ptr(png_ptr); + if (write_data->size + length >= write_data->capacity) { + ERROR("PNG write"); + } + memcpy(write_data->data + write_data->size, data, length); + write_data->size += length; +} + +void *libpng_encode(void *pixels, int w, int h, int channels, int *out_len) { + png_structp png = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL); + if (!png) { + ERROR("png_create_write_struct"); + } + + png_infop info = png_create_info_struct(png); + if (!info) { + ERROR("png_create_info_struct"); + } + + if (setjmp(png_jmpbuf(png))) { + ERROR("png_jmpbuf"); + } + + // Output is 8bit depth, RGBA format. + png_set_IHDR( + png, + info, + w, h, + 8, + channels == 3 ? PNG_COLOR_TYPE_RGB : PNG_COLOR_TYPE_RGBA, + PNG_INTERLACE_NONE, + PNG_COMPRESSION_TYPE_DEFAULT, + PNG_FILTER_TYPE_DEFAULT + ); + + png_bytep row_pointers[h]; + for(int y = 0; y < h; y++){ + row_pointers[y] = ((unsigned char *)pixels + y * w * channels); + } + + libpng_write_t write_data = { + .size = 0, + .capacity = w * h * channels, + .data = malloc(w * h * channels) + }; + + png_set_rows(png, info, row_pointers); + png_set_write_fn(png, &write_data, libpng_encode_callback, NULL); + png_write_png(png, info, PNG_TRANSFORM_IDENTITY, NULL); + + png_destroy_write_struct(&png, &info); + + *out_len = write_data.size; + return write_data.data; +} + + +typedef struct { + int pos; + int size; + unsigned char *data; +} libpng_read_t; + +void png_decode_callback(png_structp png, png_bytep data, png_size_t length) { + libpng_read_t *read_data = (libpng_read_t*)png_get_io_ptr(png); + if (read_data->pos + length > read_data->size) { + ERROR("PNG read %d bytes at pos %d (size: %d)", length, read_data->pos, read_data->size); + } + memcpy(data, read_data->data + read_data->pos, length); + read_data->pos += length; +} + +void png_warning_callback(png_structp png_ptr, png_const_charp warning_msg) { + // Ignore warnings about sRGB profiles and such. +} + +void *libpng_decode(void *data, int size, int *out_w, int *out_h) { + png_structp png = png_create_read_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, png_warning_callback); + if (!png) { + ERROR("png_create_read_struct"); + } + + png_infop info = png_create_info_struct(png); + if (!info) { + ERROR("png_create_info_struct"); + } + + libpng_read_t read_data = { + .pos = 0, + .size = size, + .data = data + }; + + png_set_read_fn(png, &read_data, png_decode_callback); + png_set_sig_bytes(png, 0); + png_read_info(png, info); + + png_uint_32 w, h; + int bitDepth, colorType, interlaceType; + png_get_IHDR(png, info, &w, &h, &bitDepth, &colorType, &interlaceType, NULL, NULL); + + // 16 bit -> 8 bit + png_set_strip_16(png); + + // 1, 2, 4 bit -> 8 bit + if (bitDepth < 8) { + png_set_packing(png); + } + + if (colorType & PNG_COLOR_MASK_PALETTE) { + png_set_expand(png); + } + + if (!(colorType & PNG_COLOR_MASK_COLOR)) { + png_set_gray_to_rgb(png); + } + + // set paletted or RGB images with transparency to full alpha so we get RGBA + if (png_get_valid(png, info, PNG_INFO_tRNS)) { + png_set_tRNS_to_alpha(png); + } + + // make sure every pixel has an alpha value + if (!(colorType & PNG_COLOR_MASK_ALPHA)) { + png_set_filler(png, 255, PNG_FILLER_AFTER); + } + + png_read_update_info(png, info); + + unsigned char* out = malloc(w * h * 4); + *out_w = w; + *out_h = h; + + // png_uint_32 rowBytes = png_get_rowbytes(png, info); + png_bytep row_pointers[h]; + for (png_uint_32 row = 0; row < h; row++ ) { + row_pointers[row] = (png_bytep)(out + (row * w * 4)); + } + + png_read_image(png, row_pointers); + png_read_end(png, info); + png_destroy_read_struct( &png, &info, NULL); + + return out; +} + + +// ----------------------------------------------------------------------------- +// stb_image encode callback + +void stbi_write_callback(void *context, void *data, int size) { + int *encoded_size = (int *)context; + *encoded_size += size; + // In theory we'd need to do another malloc(), memcpy() and free() here to + // be fair to the other decode functions... +} + + +// ----------------------------------------------------------------------------- +// function to load a whole file into memory + +void *fload(const char *path, int *out_size) { + FILE *fh = fopen(path, "rb"); + if (!fh) { + ERROR("Can't open file"); + } + + fseek(fh, 0, SEEK_END); + int size = ftell(fh); + fseek(fh, 0, SEEK_SET); + + void *buffer = malloc(size); + if (!buffer) { + ERROR("Malloc for %d bytes failed", size); + } + + if (!fread(buffer, size, 1, fh)) { + ERROR("Can't read file %s", path); + } + fclose(fh); + + *out_size = size; + return buffer; +} + + +// ----------------------------------------------------------------------------- +// benchmark runner + + +int opt_runs = 1; +int opt_nopng = 0; +int opt_nowarmup = 0; +int opt_noverify = 0; +int opt_nodecode = 0; +int opt_noencode = 0; +int opt_norecurse = 0; +int opt_onlytotals = 0; + + +typedef struct { + uint64_t size; + uint64_t encode_time; + uint64_t decode_time; +} benchmark_lib_result_t; + +typedef struct { + int count; + uint64_t raw_size; + uint64_t px; + int w; + int h; + benchmark_lib_result_t libpng; + benchmark_lib_result_t stbi; + benchmark_lib_result_t qoi; +} benchmark_result_t; + + +void benchmark_print_result(benchmark_result_t res) { + res.px /= res.count; + res.raw_size /= res.count; + res.libpng.encode_time /= res.count; + res.libpng.decode_time /= res.count; + res.libpng.size /= res.count; + res.stbi.encode_time /= res.count; + res.stbi.decode_time /= res.count; + res.stbi.size /= res.count; + res.qoi.encode_time /= res.count; + res.qoi.decode_time /= res.count; + res.qoi.size /= res.count; + + double px = res.px; + printf(" decode ms encode ms decode mpps encode mpps size kb rate\n"); + if (!opt_nopng) { + printf( + "libpng: %8.1f %8.1f %8.2f %8.2f %8d %4.1f%%\n", + (double)res.libpng.decode_time/1000000.0, + (double)res.libpng.encode_time/1000000.0, + (res.libpng.decode_time > 0 ? px / ((double)res.libpng.decode_time/1000.0) : 0), + (res.libpng.encode_time > 0 ? px / ((double)res.libpng.encode_time/1000.0) : 0), + res.libpng.size/1024, + ((double)res.libpng.size/(double)res.raw_size) * 100.0 + ); + printf( + "stbi: %8.1f %8.1f %8.2f %8.2f %8d %4.1f%%\n", + (double)res.stbi.decode_time/1000000.0, + (double)res.stbi.encode_time/1000000.0, + (res.stbi.decode_time > 0 ? px / ((double)res.stbi.decode_time/1000.0) : 0), + (res.stbi.encode_time > 0 ? px / ((double)res.stbi.encode_time/1000.0) : 0), + res.stbi.size/1024, + ((double)res.stbi.size/(double)res.raw_size) * 100.0 + ); + } + printf( + "qoi: %8.1f %8.1f %8.2f %8.2f %8d %4.1f%%\n", + (double)res.qoi.decode_time/1000000.0, + (double)res.qoi.encode_time/1000000.0, + (res.qoi.decode_time > 0 ? px / ((double)res.qoi.decode_time/1000.0) : 0), + (res.qoi.encode_time > 0 ? px / ((double)res.qoi.encode_time/1000.0) : 0), + res.qoi.size/1024, + ((double)res.qoi.size/(double)res.raw_size) * 100.0 + ); + printf("\n"); +} + +// Run __VA_ARGS__ a number of times and measure the time taken. The first +// run is ignored. +#define BENCHMARK_FN(NOWARMUP, RUNS, AVG_TIME, ...) \ + do { \ + uint64_t time = 0; \ + for (int i = NOWARMUP; i <= RUNS; i++) { \ + uint64_t time_start = ns(); \ + __VA_ARGS__ \ + uint64_t time_end = ns(); \ + if (i > 0) { \ + time += time_end - time_start; \ + } \ + } \ + AVG_TIME = time / RUNS; \ + } while (0) + + +benchmark_result_t benchmark_image(const char *path) { + int encoded_png_size; + int encoded_qoi_size; + int w; + int h; + int channels; + + // Load the encoded PNG, encoded QOI and raw pixels into memory + if(!stbi_info(path, &w, &h, &channels)) { + ERROR("Error decoding header %s", path); + } + + if (channels != 3) { + channels = 4; + } + + void *pixels = (void *)stbi_load(path, &w, &h, NULL, channels); + void *encoded_png = fload(path, &encoded_png_size); + void *encoded_qoi = qoi_encode(pixels, &(qoi_desc){ + .width = w, + .height = h, + .channels = channels, + .colorspace = QOI_SRGB + }, &encoded_qoi_size); + + if (!pixels || !encoded_qoi || !encoded_png) { + ERROR("Error decoding %s", path); + } + + // Verify QOI Output + + if (!opt_noverify) { + qoi_desc dc; + void *pixels_qoi = qoi_decode(encoded_qoi, encoded_qoi_size, &dc, channels); + if (memcmp(pixels, pixels_qoi, w * h * channels) != 0) { + ERROR("QOI roundtrip pixel mismatch for %s", path); + } + free(pixels_qoi); + } + + + + benchmark_result_t res = {0}; + res.count = 1; + res.raw_size = w * h * channels; + res.px = w * h; + res.w = w; + res.h = h; + + + // Decoding + + if (!opt_nodecode) { + if (!opt_nopng) { + BENCHMARK_FN(opt_nowarmup, opt_runs, res.libpng.decode_time, { + int dec_w, dec_h; + void *dec_p = libpng_decode(encoded_png, encoded_png_size, &dec_w, &dec_h); + free(dec_p); + }); + + BENCHMARK_FN(opt_nowarmup, opt_runs, res.stbi.decode_time, { + int dec_w, dec_h, dec_channels; + void *dec_p = stbi_load_from_memory(encoded_png, encoded_png_size, &dec_w, &dec_h, &dec_channels, 4); + free(dec_p); + }); + } + + BENCHMARK_FN(opt_nowarmup, opt_runs, res.qoi.decode_time, { + qoi_desc desc; + void *dec_p = qoi_decode(encoded_qoi, encoded_qoi_size, &desc, 4); + free(dec_p); + }); + } + + + // Encoding + if (!opt_noencode) { + if (!opt_nopng) { + BENCHMARK_FN(opt_nowarmup, opt_runs, res.libpng.encode_time, { + int enc_size; + void *enc_p = libpng_encode(pixels, w, h, channels, &enc_size); + res.libpng.size = enc_size; + free(enc_p); + }); + + BENCHMARK_FN(opt_nowarmup, opt_runs, res.stbi.encode_time, { + int enc_size = 0; + stbi_write_png_to_func(stbi_write_callback, &enc_size, w, h, channels, pixels, 0); + res.stbi.size = enc_size; + }); + } + + BENCHMARK_FN(opt_nowarmup, opt_runs, res.qoi.encode_time, { + int enc_size; + void *enc_p = qoi_encode(pixels, &(qoi_desc){ + .width = w, + .height = h, + .channels = channels, + .colorspace = QOI_SRGB + }, &enc_size); + res.qoi.size = enc_size; + free(enc_p); + }); + } + + free(pixels); + free(encoded_png); + free(encoded_qoi); + + return res; +} + +void benchmark_directory(const char *path, benchmark_result_t *grand_total) { + DIR *dir = opendir(path); + if (!dir) { + ERROR("Couldn't open directory %s", path); + } + + struct dirent *file; + + if (!opt_norecurse) { + for (int i = 0; (file = readdir(dir)) != NULL; i++) { + if ( + file->d_type & DT_DIR && + strcmp(file->d_name, ".") != 0 && + strcmp(file->d_name, "..") != 0 + ) { + char subpath[1024]; + snprintf(subpath, 1024, "%s/%s", path, file->d_name); + benchmark_directory(subpath, grand_total); + } + } + rewinddir(dir); + } + + float total_percentage = 0; + int total_size = 0; + + benchmark_result_t dir_total = {0}; + + int has_shown_head = 0; + for (int i = 0; (file = readdir(dir)) != NULL; i++) { + if (strcmp(file->d_name + strlen(file->d_name) - 4, ".png") != 0) { + continue; + } + + if (!has_shown_head) { + has_shown_head = 1; + printf("## Benchmarking %s/*.png -- %d runs\n\n", path, opt_runs); + } + + char *file_path = malloc(strlen(file->d_name) + strlen(path)+8); + sprintf(file_path, "%s/%s", path, file->d_name); + + benchmark_result_t res = benchmark_image(file_path); + + if (!opt_onlytotals) { + printf("## %s size: %dx%d\n", file_path, res.w, res.h); + benchmark_print_result(res); + } + + free(file_path); + + dir_total.count++; + dir_total.raw_size += res.raw_size; + dir_total.px += res.px; + dir_total.libpng.encode_time += res.libpng.encode_time; + dir_total.libpng.decode_time += res.libpng.decode_time; + dir_total.libpng.size += res.libpng.size; + dir_total.stbi.encode_time += res.stbi.encode_time; + dir_total.stbi.decode_time += res.stbi.decode_time; + dir_total.stbi.size += res.stbi.size; + dir_total.qoi.encode_time += res.qoi.encode_time; + dir_total.qoi.decode_time += res.qoi.decode_time; + dir_total.qoi.size += res.qoi.size; + + grand_total->count++; + grand_total->raw_size += res.raw_size; + grand_total->px += res.px; + grand_total->libpng.encode_time += res.libpng.encode_time; + grand_total->libpng.decode_time += res.libpng.decode_time; + grand_total->libpng.size += res.libpng.size; + grand_total->stbi.encode_time += res.stbi.encode_time; + grand_total->stbi.decode_time += res.stbi.decode_time; + grand_total->stbi.size += res.stbi.size; + grand_total->qoi.encode_time += res.qoi.encode_time; + grand_total->qoi.decode_time += res.qoi.decode_time; + grand_total->qoi.size += res.qoi.size; + } + closedir(dir); + + if (dir_total.count > 0) { + printf("## Total for %s\n", path); + benchmark_print_result(dir_total); + } +} + +int main(int argc, char **argv) { + if (argc < 3) { + printf("Usage: qoibench [options]\n"); + printf("Options:\n"); + printf(" --nowarmup ... don't perform a warmup run\n"); + printf(" --nopng ...... don't run png encode/decode\n"); + printf(" --noverify ... don't verify qoi roundtrip\n"); + printf(" --noencode ... don't run encoders\n"); + printf(" --nodecode ... don't run decoders\n"); + printf(" --norecurse .. don't descend into directories\n"); + printf(" --onlytotals . don't print individual image results\n"); + printf("Examples\n"); + printf(" qoibench 10 images/textures/\n"); + printf(" qoibench 1 images/textures/ --nopng --nowarmup\n"); + exit(1); + } + + for (int i = 3; i < argc; i++) { + if (strcmp(argv[i], "--nowarmup") == 0) { opt_nowarmup = 1; } + else if (strcmp(argv[i], "--nopng") == 0) { opt_nopng = 1; } + else if (strcmp(argv[i], "--noverify") == 0) { opt_noverify = 1; } + else if (strcmp(argv[i], "--noencode") == 0) { opt_noencode = 1; } + else if (strcmp(argv[i], "--nodecode") == 0) { opt_nodecode = 1; } + else if (strcmp(argv[i], "--norecurse") == 0) { opt_norecurse = 1; } + else if (strcmp(argv[i], "--onlytotals") == 0) { opt_onlytotals = 1; } + else { ERROR("Unknown option %s", argv[i]); } + } + + opt_runs = atoi(argv[1]); + if (opt_runs <=0) { + ERROR("Invalid number of runs %d", opt_runs); + } + + benchmark_result_t grand_total = {0}; + benchmark_directory(argv[2], &grand_total); + + if (grand_total.count > 0) { + printf("# Grand total for %s\n", argv[2]); + benchmark_print_result(grand_total); + } + else { + printf("No images found in %s\n", argv[2]); + } + + return 0; +} diff --git a/ext/qoi/qoiconv.c b/ext/qoi/qoiconv.c new file mode 100644 index 0000000..79aa75c --- /dev/null +++ b/ext/qoi/qoiconv.c @@ -0,0 +1,106 @@ +/* + +Command line tool to convert between png <> qoi format + +Requires "stb_image.h" and "stb_image_write.h" +Compile with: + gcc qoiconv.c -std=c99 -O3 -o qoiconv + +Dominic Szablewski - https://phoboslab.org + + +-- LICENSE: The MIT License(MIT) + +Copyright(c) 2021 Dominic Szablewski + +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. + +*/ + + +#define STB_IMAGE_IMPLEMENTATION +#define STBI_ONLY_PNG +#define STBI_NO_LINEAR +#include "stb_image.h" + +#define STB_IMAGE_WRITE_IMPLEMENTATION +#include "stb_image_write.h" + +#define QOI_IMPLEMENTATION +#include "qoi.h" + + +#define STR_ENDS_WITH(S, E) (strcmp(S + strlen(S) - (sizeof(E)-1), E) == 0) + +int main(int argc, char **argv) { + if (argc < 3) { + puts("Usage: qoiconv "); + puts("Examples:"); + puts(" qoiconv input.png output.qoi"); + puts(" qoiconv input.qoi output.png"); + exit(1); + } + + void *pixels = NULL; + int w, h, channels; + if (STR_ENDS_WITH(argv[1], ".png")) { + if(!stbi_info(argv[1], &w, &h, &channels)) { + printf("Couldn't read header %s\n", argv[1]); + exit(1); + } + + // Force all odd encodings to be RGBA + if(channels != 3) { + channels = 4; + } + + pixels = (void *)stbi_load(argv[1], &w, &h, NULL, channels); + } + else if (STR_ENDS_WITH(argv[1], ".qoi")) { + qoi_desc desc; + pixels = qoi_read(argv[1], &desc, 0); + channels = desc.channels; + w = desc.width; + h = desc.height; + } + + if (pixels == NULL) { + printf("Couldn't load/decode %s\n", argv[1]); + exit(1); + } + + int encoded = 0; + if (STR_ENDS_WITH(argv[2], ".png")) { + encoded = stbi_write_png(argv[2], w, h, channels, pixels, 0); + } + else if (STR_ENDS_WITH(argv[2], ".qoi")) { + encoded = qoi_write(argv[2], pixels, &(qoi_desc){ + .width = w, + .height = h, + .channels = channels, + .colorspace = QOI_SRGB + }); + } + + if (!encoded) { + printf("Couldn't write/encode %s\n", argv[2]); + exit(1); + } + + free(pixels); + return 0; +} diff --git a/ext/qoi/qoifuzz.c b/ext/qoi/qoifuzz.c new file mode 100644 index 0000000..1b5c792 --- /dev/null +++ b/ext/qoi/qoifuzz.c @@ -0,0 +1,51 @@ +/* + +clang fuzzing harness for qoi_decode + +Compile and run with: + clang -fsanitize=address,fuzzer -g -O0 qoifuzz.c && ./a.out + +Dominic Szablewski - https://phoboslab.org + + +-- LICENSE: The MIT License(MIT) + +Copyright(c) 2021 Dominic Szablewski + +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. + +*/ + + +#define QOI_IMPLEMENTATION +#include "qoi.h" +#include +#include + +int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + int w, h; + if (size < 4) { + return 0; + } + + qoi_desc desc; + void* decoded = qoi_decode((void*)(data + 4), (int)(size - 4), &desc, *((int *)data)); + if (decoded != NULL) { + free(decoded); + } + return 0; +} diff --git a/rustfmt.toml b/rustfmt.toml new file mode 100644 index 0000000..0160865 --- /dev/null +++ b/rustfmt.toml @@ -0,0 +1,7 @@ +use_small_heuristics = "Max" +use_field_init_shorthand = true +use_try_shorthand = true +empty_item_single_line = true +edition = "2018" +unstable_features = true +fn_args_layout = "Compressed" diff --git a/src/consts.rs b/src/consts.rs new file mode 100644 index 0000000..2281c24 --- /dev/null +++ b/src/consts.rs @@ -0,0 +1,17 @@ +pub const QOI_OP_INDEX: u8 = 0x00; // 00xxxxxx +pub const QOI_OP_DIFF: u8 = 0x40; // 01xxxxxx +pub const QOI_OP_LUMA: u8 = 0x80; // 10xxxxxx +pub const QOI_OP_RUN: u8 = 0xc0; // 11xxxxxx +pub const QOI_OP_RGB: u8 = 0xfe; // 11111110 +pub const QOI_OP_RGBA: u8 = 0xff; // 11111111 + +pub const QOI_MASK_2: u8 = 0xc0; // (11)000000 + +pub const QOI_HEADER_SIZE: usize = 14; + +pub const QOI_PADDING: [u8; 8] = [0, 0, 0, 0, 0, 0, 0, 0x01]; // 7 zeros and one 0x01 marker +pub const QOI_PADDING_SIZE: usize = 8; + +pub const QOI_MAGIC: u32 = u32::from_be_bytes(*b"qoif"); + +pub const QOI_PIXELS_MAX: usize = 400_000_000; diff --git a/src/decode.rs b/src/decode.rs new file mode 100644 index 0000000..019dac2 --- /dev/null +++ b/src/decode.rs @@ -0,0 +1,396 @@ +#[cfg(any(feature = "std", feature = "alloc"))] +use alloc::{vec, vec::Vec}; +#[cfg(feature = "std")] +use std::io::Read; + +// TODO: can be removed once https://github.com/rust-lang/rust/issues/74985 is stable +use bytemuck::{cast_slice_mut, Pod}; + +use crate::consts::{ + QOI_HEADER_SIZE, QOI_OP_DIFF, QOI_OP_INDEX, QOI_OP_LUMA, QOI_OP_RGB, QOI_OP_RGBA, QOI_OP_RUN, + QOI_PADDING, QOI_PADDING_SIZE, +}; +use crate::error::{Error, Result}; +use crate::header::Header; +use crate::pixel::{Pixel, SupportedChannels}; +use crate::types::Channels; +use crate::utils::{cold, unlikely}; + +const QOI_OP_INDEX_END: u8 = QOI_OP_INDEX | 0x3f; +const QOI_OP_RUN_END: u8 = QOI_OP_RUN | 0x3d; // <- note, 0x3d (not 0x3f) +const QOI_OP_DIFF_END: u8 = QOI_OP_DIFF | 0x3f; +const QOI_OP_LUMA_END: u8 = QOI_OP_LUMA | 0x3f; + +#[inline] +fn decode_impl_slice(data: &[u8], out: &mut [u8]) -> Result +where + Pixel: SupportedChannels, + [u8; N]: Pod, +{ + let mut pixels = cast_slice_mut::<_, [u8; N]>(out); + let data_len = data.len(); + let mut data = data; + + let mut index = [Pixel::<4>::new(); 256]; + let mut px = Pixel::::new().with_a(0xff); + let mut px_rgba: Pixel<4>; + + while let [px_out, ptail @ ..] = pixels { + pixels = ptail; + match data { + [b1 @ QOI_OP_INDEX..=QOI_OP_INDEX_END, dtail @ ..] => { + px_rgba = index[*b1 as usize]; + px.update(px_rgba); + *px_out = px.into(); + data = dtail; + continue; + } + [QOI_OP_RGB, r, g, b, dtail @ ..] => { + px.update_rgb(*r, *g, *b); + data = dtail; + } + [QOI_OP_RGBA, r, g, b, a, dtail @ ..] if RGBA => { + px.update_rgba(*r, *g, *b, *a); + data = dtail; + } + [b1 @ QOI_OP_RUN..=QOI_OP_RUN_END, dtail @ ..] => { + *px_out = px.into(); + let run = ((b1 & 0x3f) as usize).min(pixels.len()); + let (phead, ptail) = pixels.split_at_mut(run); // can't panic + phead.fill(px.into()); + pixels = ptail; + data = dtail; + continue; + } + [b1 @ QOI_OP_DIFF..=QOI_OP_DIFF_END, dtail @ ..] => { + px.update_diff(*b1); + data = dtail; + } + [b1 @ QOI_OP_LUMA..=QOI_OP_LUMA_END, b2, dtail @ ..] => { + px.update_luma(*b1, *b2); + data = dtail; + } + _ => { + cold(); + if unlikely(data.len() < QOI_PADDING_SIZE) { + return Err(Error::UnexpectedBufferEnd); + } + } + } + + px_rgba = px.as_rgba(0xff); + index[px_rgba.hash_index() as usize] = px_rgba; + *px_out = px.into(); + } + + if unlikely(data.len() < QOI_PADDING_SIZE) { + return Err(Error::UnexpectedBufferEnd); + } else if unlikely(data[..QOI_PADDING_SIZE] != QOI_PADDING) { + return Err(Error::InvalidPadding); + } + + Ok(data_len.saturating_sub(data.len()).saturating_sub(QOI_PADDING_SIZE)) +} + +#[inline] +fn decode_impl_slice_all( + data: &[u8], out: &mut [u8], channels: u8, src_channels: u8, +) -> Result { + match (channels, src_channels) { + (3, 3) => decode_impl_slice::<3, false>(data, out), + (3, 4) => decode_impl_slice::<3, true>(data, out), + (4, 3) => decode_impl_slice::<4, false>(data, out), + (4, 4) => decode_impl_slice::<4, true>(data, out), + _ => { + cold(); + Err(Error::InvalidChannels { channels }) + } + } +} + +/// Decode the image into a pre-allocated buffer. +/// +/// Note: the resulting number of channels will match the header. In order to change +/// the number of channels, use [`Decoder::with_channels`]. +#[inline] +pub fn decode_to_buf(buf: impl AsMut<[u8]>, data: impl AsRef<[u8]>) -> Result
{ + let mut decoder = Decoder::new(&data)?; + decoder.decode_to_buf(buf)?; + Ok(*decoder.header()) +} + +/// Decode the image into a newly allocated vector. +/// +/// Note: the resulting number of channels will match the header. In order to change +/// the number of channels, use [`Decoder::with_channels`]. +#[cfg(any(feature = "std", feature = "alloc"))] +#[inline] +pub fn decode_to_vec(data: impl AsRef<[u8]>) -> Result<(Header, Vec)> { + let mut decoder = Decoder::new(&data)?; + let out = decoder.decode_to_vec()?; + Ok((*decoder.header(), out)) +} + +/// Decode the image header from a slice of bytes. +#[inline] +pub fn decode_header(data: impl AsRef<[u8]>) -> Result
{ + Header::decode(data) +} + +#[cfg(any(feature = "std"))] +#[inline] +fn decode_impl_stream( + data: &mut R, out: &mut [u8], +) -> Result<()> +where + Pixel: SupportedChannels, + [u8; N]: Pod, +{ + let mut pixels = cast_slice_mut::<_, [u8; N]>(out); + + let mut index = [Pixel::::new(); 256]; + let mut px = Pixel::::new().with_a(0xff); + + while let [px_out, ptail @ ..] = pixels { + pixels = ptail; + let mut p = [0]; + data.read_exact(&mut p)?; + let [b1] = p; + match b1 { + QOI_OP_INDEX..=QOI_OP_INDEX_END => { + px = index[b1 as usize]; + *px_out = px.into(); + continue; + } + QOI_OP_RGB => { + let mut p = [0; 3]; + data.read_exact(&mut p)?; + px.update_rgb(p[0], p[1], p[2]); + } + QOI_OP_RGBA if RGBA => { + let mut p = [0; 4]; + data.read_exact(&mut p)?; + px.update_rgba(p[0], p[1], p[2], p[3]); + } + QOI_OP_RUN..=QOI_OP_RUN_END => { + *px_out = px.into(); + let run = ((b1 & 0x3f) as usize).min(pixels.len()); + let (phead, ptail) = pixels.split_at_mut(run); // can't panic + phead.fill(px.into()); + pixels = ptail; + continue; + } + QOI_OP_DIFF..=QOI_OP_DIFF_END => { + px.update_diff(b1); + } + QOI_OP_LUMA..=QOI_OP_LUMA_END => { + let mut p = [0]; + data.read_exact(&mut p)?; + let [b2] = p; + px.update_luma(b1, b2); + } + _ => { + cold(); + } + } + + index[px.hash_index() as usize] = px; + *px_out = px.into(); + } + + let mut p = [0_u8; QOI_PADDING_SIZE]; + data.read_exact(&mut p)?; + if unlikely(p != QOI_PADDING) { + return Err(Error::InvalidPadding); + } + + Ok(()) +} + +#[cfg(feature = "std")] +#[inline] +fn decode_impl_stream_all( + data: &mut R, out: &mut [u8], channels: u8, src_channels: u8, +) -> Result<()> { + match (channels, src_channels) { + (3, 3) => decode_impl_stream::<_, 3, false>(data, out), + (3, 4) => decode_impl_stream::<_, 3, true>(data, out), + (4, 3) => decode_impl_stream::<_, 4, false>(data, out), + (4, 4) => decode_impl_stream::<_, 4, true>(data, out), + _ => { + cold(); + Err(Error::InvalidChannels { channels }) + } + } +} + +#[doc(hidden)] +pub trait Reader: Sized { + fn decode_header(&mut self) -> Result
; + fn decode_image(&mut self, out: &mut [u8], channels: u8, src_channels: u8) -> Result<()>; +} + +pub struct Bytes<'a>(&'a [u8]); + +impl<'a> Bytes<'a> { + #[inline] + pub const fn new(buf: &'a [u8]) -> Self { + Self(buf) + } + + #[inline] + pub const fn as_slice(&self) -> &[u8] { + self.0 + } +} + +impl<'a> Reader for Bytes<'a> { + #[inline] + fn decode_header(&mut self) -> Result
{ + let header = Header::decode(self.0)?; + self.0 = &self.0[QOI_HEADER_SIZE..]; // can't panic + Ok(header) + } + + #[inline] + fn decode_image(&mut self, out: &mut [u8], channels: u8, src_channels: u8) -> Result<()> { + let n_read = decode_impl_slice_all(self.0, out, channels, src_channels)?; + self.0 = &self.0[n_read..]; + Ok(()) + } +} + +#[cfg(feature = "std")] +impl Reader for R { + #[inline] + fn decode_header(&mut self) -> Result
{ + let mut b = [0; QOI_HEADER_SIZE]; + self.read_exact(&mut b)?; + Header::decode(b) + } + + #[inline] + fn decode_image(&mut self, out: &mut [u8], channels: u8, src_channels: u8) -> Result<()> { + decode_impl_stream_all(self, out, channels, src_channels) + } +} + +/// Decode QOI images from slices or from streams. +#[derive(Clone)] +pub struct Decoder { + reader: R, + header: Header, + channels: Channels, +} + +impl<'a> Decoder> { + /// Creates a new decoder from a slice of bytes. + /// + /// The header will be decoded immediately upon construction. + /// + /// Note: this provides the most efficient decoding, but requires the source data to + /// be loaded in memory in order to decode it. In order to decode from a generic + /// stream, use [`Decoder::from_stream`] instead. + #[inline] + pub fn new(data: &'a (impl AsRef<[u8]> + ?Sized)) -> Result { + Self::new_impl(Bytes::new(data.as_ref())) + } + + /// Returns the undecoded tail of the input slice of bytes. + #[inline] + pub const fn data(&self) -> &[u8] { + self.reader.as_slice() + } +} + +#[cfg(feature = "std")] +impl Decoder { + /// Creates a new decoder from a generic reader that implements [`Read`](std::io::Read). + /// + /// The header will be decoded immediately upon construction. + /// + /// Note: while it's possible to pass a `&[u8]` slice here since it implements `Read`, it + /// would be more efficient to use a specialized constructor instead: [`Decoder::new`]. + #[inline] + pub fn from_stream(reader: R) -> Result { + Self::new_impl(reader) + } + + /// Returns an immutable reference to the underlying reader. + #[inline] + pub const fn reader(&self) -> &R { + &self.reader + } + + /// Consumes the decoder and returns the underlying reader back. + #[inline] + #[allow(clippy::missing_const_for_fn)] + pub fn into_reader(self) -> R { + self.reader + } +} + +impl Decoder { + #[inline] + fn new_impl(mut reader: R) -> Result { + let header = reader.decode_header()?; + Ok(Self { reader, header, channels: header.channels }) + } + + /// Returns a new decoder with modified number of channels. + /// + /// By default, the number of channels in the decoded image will be equal + /// to whatever is specified in the header. However, it is also possible + /// to decode RGB into RGBA (in which case the alpha channel will be set + /// to 255), and vice versa (in which case the alpha channel will be ignored). + #[inline] + pub const fn with_channels(mut self, channels: Channels) -> Self { + self.channels = channels; + self + } + + /// Returns the number of channels in the decoded image. + /// + /// Note: this may differ from the number of channels specified in the header. + #[inline] + pub const fn channels(&self) -> Channels { + self.channels + } + + /// Returns the decoded image header. + #[inline] + pub const fn header(&self) -> &Header { + &self.header + } + + /// The number of bytes the decoded image will take. + /// + /// Can be used to pre-allocate the buffer to decode the image into. + #[inline] + pub const fn required_buf_len(&self) -> usize { + self.header.n_pixels().saturating_mul(self.channels.as_u8() as usize) + } + + /// Decodes the image to a pre-allocated buffer and returns the number of bytes written. + /// + /// The minimum size of the buffer can be found via [`Decoder::required_buf_len`]. + #[inline] + pub fn decode_to_buf(&mut self, mut buf: impl AsMut<[u8]>) -> Result { + let buf = buf.as_mut(); + let size = self.required_buf_len(); + if unlikely(buf.len() < size) { + return Err(Error::OutputBufferTooSmall { size: buf.len(), required: size }); + } + self.reader.decode_image(buf, self.channels.as_u8(), self.header.channels.as_u8())?; + Ok(size) + } + + /// Decodes the image into a newly allocated vector of bytes and returns it. + #[cfg(any(feature = "std", feature = "alloc"))] + #[inline] + pub fn decode_to_vec(&mut self) -> Result> { + let mut out = vec![0; self.header.n_pixels() * self.channels.as_u8() as usize]; + let _ = self.decode_to_buf(&mut out)?; + Ok(out) + } +} diff --git a/src/encode.rs b/src/encode.rs new file mode 100644 index 0000000..0ed8476 --- /dev/null +++ b/src/encode.rs @@ -0,0 +1,210 @@ +#[cfg(any(feature = "std", feature = "alloc"))] +use alloc::{vec, vec::Vec}; +use core::convert::TryFrom; +#[cfg(feature = "std")] +use std::io::Write; + +use bytemuck::Pod; + +use crate::consts::{QOI_HEADER_SIZE, QOI_OP_INDEX, QOI_OP_RUN, QOI_PADDING, QOI_PADDING_SIZE}; +use crate::error::{Error, Result}; +use crate::header::Header; +use crate::pixel::{Pixel, SupportedChannels}; +use crate::types::{Channels, ColorSpace}; +#[cfg(feature = "std")] +use crate::utils::GenericWriter; +use crate::utils::{unlikely, BytesMut, Writer}; + +#[allow(clippy::cast_possible_truncation, unused_assignments, unused_variables)] +fn encode_impl(mut buf: W, data: &[u8]) -> Result +where + Pixel: SupportedChannels, + [u8; N]: Pod, +{ + let cap = buf.capacity(); + + let mut index = [Pixel::new(); 256]; + let mut px_prev = Pixel::new().with_a(0xff); + let mut hash_prev = px_prev.hash_index(); + let mut run = 0_u8; + let mut px = Pixel::::new().with_a(0xff); + let mut index_allowed = false; + + let n_pixels = data.len() / N; + + for (i, chunk) in data.chunks_exact(N).enumerate() { + px.read(chunk); + if px == px_prev { + run += 1; + if run == 62 || unlikely(i == n_pixels - 1) { + buf = buf.write_one(QOI_OP_RUN | (run - 1))?; + run = 0; + } + } else { + if run != 0 { + #[cfg(not(feature = "reference"))] + { + // credits for the original idea: @zakarumych (had to be fixed though) + buf = buf.write_one(if run == 1 && index_allowed { + QOI_OP_INDEX | hash_prev + } else { + QOI_OP_RUN | (run - 1) + })?; + } + #[cfg(feature = "reference")] + { + buf = buf.write_one(QOI_OP_RUN | (run - 1))?; + } + run = 0; + } + index_allowed = true; + let px_rgba = px.as_rgba(0xff); + hash_prev = px_rgba.hash_index(); + let index_px = &mut index[hash_prev as usize]; + if *index_px == px_rgba { + buf = buf.write_one(QOI_OP_INDEX | hash_prev)?; + } else { + *index_px = px_rgba; + buf = px.encode_into(px_prev, buf)?; + } + px_prev = px; + } + } + + buf = buf.write_many(&QOI_PADDING)?; + Ok(cap.saturating_sub(buf.capacity())) +} + +#[inline] +fn encode_impl_all(out: W, data: &[u8], channels: Channels) -> Result { + match channels { + Channels::Rgb => encode_impl::<_, 3>(out, data), + Channels::Rgba => encode_impl::<_, 4>(out, data), + } +} + +/// The maximum number of bytes the encoded image will take. +/// +/// Can be used to pre-allocate the buffer to encode the image into. +#[inline] +pub fn encode_max_len(width: u32, height: u32, channels: impl Into) -> usize { + let (width, height) = (width as usize, height as usize); + let n_pixels = width.saturating_mul(height); + QOI_HEADER_SIZE + + n_pixels.saturating_mul(channels.into() as usize) + + n_pixels + + QOI_PADDING_SIZE +} + +/// Encode the image into a pre-allocated buffer. +/// +/// Returns the total number of bytes written. +#[inline] +pub fn encode_to_buf( + buf: impl AsMut<[u8]>, data: impl AsRef<[u8]>, width: u32, height: u32, +) -> Result { + Encoder::new(&data, width, height)?.encode_to_buf(buf) +} + +/// Encode the image into a newly allocated vector. +#[cfg(any(feature = "alloc", feature = "std"))] +#[inline] +pub fn encode_to_vec(data: impl AsRef<[u8]>, width: u32, height: u32) -> Result> { + Encoder::new(&data, width, height)?.encode_to_vec() +} + +/// Encode QOI images into buffers or into streams. +pub struct Encoder<'a> { + data: &'a [u8], + header: Header, +} + +impl<'a> Encoder<'a> { + /// Creates a new encoder from a given array of pixel data and image dimensions. + /// + /// The number of channels will be inferred automatically (the valid values + /// are 3 or 4). The color space will be set to sRGB by default. + #[inline] + #[allow(clippy::cast_possible_truncation)] + pub fn new(data: &'a (impl AsRef<[u8]> + ?Sized), width: u32, height: u32) -> Result { + let data = data.as_ref(); + let mut header = + Header::try_new(width, height, Channels::default(), ColorSpace::default())?; + let size = data.len(); + let n_channels = size / header.n_pixels(); + if header.n_pixels() * n_channels != size { + return Err(Error::InvalidImageLength { size, width, height }); + } + header.channels = Channels::try_from(n_channels.min(0xff) as u8)?; + Ok(Self { data, header }) + } + + /// Returns a new encoder with modified color space. + /// + /// Note: the color space doesn't affect encoding or decoding in any way, it's + /// a purely informative field that's stored in the image header. + #[inline] + pub const fn with_colorspace(mut self, colorspace: ColorSpace) -> Self { + self.header = self.header.with_colorspace(colorspace); + self + } + + /// Returns the inferred number of channels. + #[inline] + pub const fn channels(&self) -> Channels { + self.header.channels + } + + /// Returns the header that will be stored in the encoded image. + #[inline] + pub const fn header(&self) -> &Header { + &self.header + } + + /// The maximum number of bytes the encoded image will take. + /// + /// Can be used to pre-allocate the buffer to encode the image into. + #[inline] + pub fn required_buf_len(&self) -> usize { + self.header.encode_max_len() + } + + /// Encodes the image to a pre-allocated buffer and returns the number of bytes written. + /// + /// The minimum size of the buffer can be found via [`Encoder::required_buf_len`]. + #[inline] + pub fn encode_to_buf(&self, mut buf: impl AsMut<[u8]>) -> Result { + let buf = buf.as_mut(); + let size_required = self.required_buf_len(); + if unlikely(buf.len() < size_required) { + return Err(Error::OutputBufferTooSmall { size: buf.len(), required: size_required }); + } + let (head, tail) = buf.split_at_mut(QOI_HEADER_SIZE); // can't panic + head.copy_from_slice(&self.header.encode()); + let n_written = encode_impl_all(BytesMut::new(tail), self.data, self.header.channels)?; + Ok(QOI_HEADER_SIZE + n_written) + } + + /// Encodes the image into a newly allocated vector of bytes and returns it. + #[cfg(any(feature = "alloc", feature = "std"))] + #[inline] + pub fn encode_to_vec(&self) -> Result> { + let mut out = vec![0_u8; self.required_buf_len()]; + let size = self.encode_to_buf(&mut out)?; + out.truncate(size); + Ok(out) + } + + /// Encodes the image directly to a generic writer that implements [`Write`](std::io::Write). + /// + /// Note: while it's possible to pass a `&mut [u8]` slice here since it implements `Write`, + /// it would more effficient to use a specialized method instead: [`Encoder::encode_to_buf`]. + #[cfg(feature = "std")] + #[inline] + pub fn encode_to_stream(&self, writer: &mut W) -> Result { + writer.write_all(&self.header.encode())?; + let n_written = + encode_impl_all(GenericWriter::new(writer), self.data, self.header.channels)?; + Ok(n_written + QOI_HEADER_SIZE) + } +} diff --git a/src/error.rs b/src/error.rs new file mode 100644 index 0000000..2b90636 --- /dev/null +++ b/src/error.rs @@ -0,0 +1,82 @@ +use core::convert::Infallible; +use core::fmt::{self, Display}; + +use crate::consts::QOI_MAGIC; + +/// Errors that can occur during encoding or decoding. +#[derive(Debug)] +pub enum Error { + /// Leading 4 magic bytes don't match when decoding + InvalidMagic { magic: u32 }, + /// Invalid number of channels: expected 3 or 4 + InvalidChannels { channels: u8 }, + /// Invalid color space: expected 0 or 1 + InvalidColorSpace { colorspace: u8 }, + /// Invalid image dimensions: can't be empty or larger than 400Mp + InvalidImageDimensions { width: u32, height: u32 }, + /// Image dimensions are inconsistent with image buffer length + InvalidImageLength { size: usize, width: u32, height: u32 }, + /// Output buffer is too small to fit encoded/decoded image + OutputBufferTooSmall { size: usize, required: usize }, + /// Input buffer ended unexpectedly before decoding was finished + UnexpectedBufferEnd, + /// Invalid stream end marker encountered when decoding + InvalidPadding, + #[cfg(feature = "std")] + /// Generic I/O error from the wrapped reader/writer + IoError(std::io::Error), +} + +/// Alias for [`Result`](std::result::Result) with the error type of [`Error`]. +pub type Result = core::result::Result; + +impl Display for Error { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self { + Self::InvalidMagic { magic } => { + write!(f, "invalid magic: expected {:?}, got {:?}", QOI_MAGIC, magic.to_be_bytes()) + } + Self::InvalidChannels { channels } => { + write!(f, "invalid number of channels: {}", channels) + } + Self::InvalidColorSpace { colorspace } => { + write!(f, "invalid color space: {} (expected 0 or 1)", colorspace) + } + Self::InvalidImageDimensions { width, height } => { + write!(f, "invalid image dimensions: {}x{}", width, height) + } + Self::InvalidImageLength { size, width, height } => { + write!(f, "invalid image length: {} bytes for {}x{}", size, width, height) + } + Self::OutputBufferTooSmall { size, required } => { + write!(f, "output buffer size too small: {} (required: {})", size, required) + } + Self::UnexpectedBufferEnd => { + write!(f, "unexpected input buffer end while decoding") + } + Self::InvalidPadding => { + write!(f, "invalid padding (stream end marker mismatch)") + } + #[cfg(feature = "std")] + Self::IoError(ref err) => { + write!(f, "i/o error: {}", err) + } + } + } +} + +#[cfg(feature = "std")] +impl std::error::Error for Error {} + +impl From for Error { + fn from(_: Infallible) -> Self { + unreachable!() + } +} + +#[cfg(feature = "std")] +impl From for Error { + fn from(err: std::io::Error) -> Self { + Self::IoError(err) + } +} diff --git a/src/header.rs b/src/header.rs new file mode 100644 index 0000000..ccdb1cc --- /dev/null +++ b/src/header.rs @@ -0,0 +1,120 @@ +use core::convert::TryInto; + +use bytemuck::cast_slice; + +use crate::consts::{QOI_HEADER_SIZE, QOI_MAGIC, QOI_PIXELS_MAX}; +use crate::encode_max_len; +use crate::error::{Error, Result}; +use crate::types::{Channels, ColorSpace}; +use crate::utils::unlikely; + +/// Image header: dimensions, channels, color space. +/// +/// ### Notes +/// A valid image header must satisfy the following conditions: +/// * Both width and height must be non-zero. +/// * Maximum number of pixels is 400Mp (=4e8 pixels). +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +pub struct Header { + /// Image width in pixels + pub width: u32, + /// Image height in pixels + pub height: u32, + /// Number of 8-bit channels per pixel + pub channels: Channels, + /// Color space (informative field, doesn't affect encoding) + pub colorspace: ColorSpace, +} + +impl Default for Header { + #[inline] + fn default() -> Self { + Self { + width: 1, + height: 1, + channels: Channels::default(), + colorspace: ColorSpace::default(), + } + } +} + +impl Header { + /// Creates a new header and validates image dimensions. + #[inline] + pub const fn try_new( + width: u32, height: u32, channels: Channels, colorspace: ColorSpace, + ) -> Result { + let n_pixels = (width as usize).saturating_mul(height as usize); + if unlikely(n_pixels == 0 || n_pixels > QOI_PIXELS_MAX) { + return Err(Error::InvalidImageDimensions { width, height }); + } + Ok(Self { width, height, channels, colorspace }) + } + + /// Creates a new header with modified channels. + #[inline] + pub const fn with_channels(mut self, channels: Channels) -> Self { + self.channels = channels; + self + } + + /// Creates a new header with modified color space. + #[inline] + pub const fn with_colorspace(mut self, colorspace: ColorSpace) -> Self { + self.colorspace = colorspace; + self + } + + /// Serializes the header into a bytes array. + #[inline] + pub(crate) fn encode(&self) -> [u8; QOI_HEADER_SIZE] { + let mut out = [0; QOI_HEADER_SIZE]; + out[..4].copy_from_slice(&QOI_MAGIC.to_be_bytes()); + out[4..8].copy_from_slice(&self.width.to_be_bytes()); + out[8..12].copy_from_slice(&self.height.to_be_bytes()); + out[12] = self.channels.into(); + out[13] = self.colorspace.into(); + out + } + + /// Deserializes the header from a byte array. + #[inline] + pub(crate) fn decode(data: impl AsRef<[u8]>) -> Result { + let data = data.as_ref(); + if unlikely(data.len() < QOI_HEADER_SIZE) { + return Err(Error::UnexpectedBufferEnd); + } + let v = cast_slice::<_, [u8; 4]>(&data[..12]); + let magic = u32::from_be_bytes(v[0]); + let width = u32::from_be_bytes(v[1]); + let height = u32::from_be_bytes(v[2]); + let channels = data[12].try_into()?; + let colorspace = data[13].try_into()?; + if unlikely(magic != QOI_MAGIC) { + return Err(Error::InvalidMagic { magic }); + } + Self::try_new(width, height, channels, colorspace) + } + + /// Returns a number of pixels in the image. + #[inline] + pub const fn n_pixels(&self) -> usize { + (self.width as usize).saturating_mul(self.height as usize) + } + + /// Returns the total number of bytes in the raw pixel array. + /// + /// This may come useful when pre-allocating a buffer to decode the image into. + #[inline] + pub const fn n_bytes(&self) -> usize { + self.n_pixels() * self.channels.as_u8() as usize + } + + /// The maximum number of bytes the encoded image will take. + /// + /// Can be used to pre-allocate the buffer to encode the image into. + #[inline] + pub fn encode_max_len(&self) -> usize { + encode_max_len(self.width, self.height, self.channels) + } +} diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..f77506b --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,95 @@ +//! Fast encoder/decoder for [QOI image format](https://qoiformat.org/), implemented in pure and safe Rust. +//! +//! - One of the [fastest](#benchmarks) QOI encoders/decoders out there. +//! - Compliant with the [latest](https://qoiformat.org/qoi-specification.pdf) QOI format specification. +//! - Zero unsafe code. +//! - Supports decoding from / encoding to `std::io` streams directly. +//! - `no_std` support. +//! - Roundtrip-tested vs the reference C implementation; fuzz-tested. +//! +//! ### Examples +//! +//! ```rust +//! use qoi::{encode_to_vec, decode_to_vec}; +//! +//! let encoded = encode_to_vec(&pixels, width, height)?; +//! let (header, decoded) = decode_to_vec(&encoded)?; +//! +//! assert_eq!(header.width, width); +//! assert_eq!(header.height, height); +//! assert_eq!(decoded, pixels); +//! ``` +//! +//! ### Benchmarks +//! +//! ``` +//! decode:Mp/s encode:Mp/s decode:MB/s encode:MB/s +//! qoi.h 282.9 225.3 978.3 778.9 +//! qoi-rust 427.4 290.0 1477.7 1002.9 +//! ``` +//! +//! - Reference C implementation: +//! [phoboslab/qoi@00e34217](https://github.com/phoboslab/qoi/commit/00e34217). +//! - Benchmark timings were collected on an Apple M1 laptop. +//! - 2846 images from the suite provided upstream +//! ([tarball](https://phoboslab.org/files/qoibench/qoi_benchmark_suite.tar)): +//! all pngs except two with broken checksums. +//! - 1.32 GPixels in total with 4.46 GB of raw pixel data. +//! +//! Benchmarks have also been run for all of the other Rust implementations +//! of QOI for comparison purposes and, at the time of writing this document, +//! this library proved to be the fastest one by a noticeable margin. +//! +//! ### Rust version +//! +//! The minimum supported Rust version is 1.51.0 (any changes to this would be +//! considered to be a breaking change). +//! +//! ### `no_std` +//! +//! This crate supports `no_std` mode. By default, std is enabled via the `std` +//! feature. You can deactivate the `default-features` to target core instead. +//! In that case anything related to `std::io`, `std::error::Error` and heap +//! allocations is disabled. There is an additional `alloc` feature that can +//! be activated to bring back the support for heap allocations. + +#![forbid(unsafe_code)] +#![warn(clippy::all, clippy::pedantic, clippy::nursery, clippy::cargo)] +#![allow( + clippy::inline_always, + clippy::similar_names, + clippy::missing_errors_doc, + clippy::must_use_candidate, + clippy::module_name_repetitions, + clippy::cargo_common_metadata, + clippy::doc_markdown, + clippy::return_self_not_must_use, +)] +#![cfg_attr(not(any(feature = "std", test)), no_std)] +#[cfg(all(feature = "alloc", not(any(feature = "std", test))))] +extern crate alloc; +#[cfg(any(feature = "std", test))] +extern crate std as alloc; + +mod decode; +mod encode; +mod error; +mod header; +mod pixel; +mod types; +mod utils; + +#[doc(hidden)] +pub mod consts; + +#[cfg(any(feature = "alloc", feature = "std"))] +pub use crate::decode::decode_to_vec; +pub use crate::decode::{decode_header, decode_to_buf, Decoder}; + +#[cfg(any(feature = "alloc", feature = "std"))] +pub use crate::encode::encode_to_vec; +pub use crate::encode::{encode_max_len, encode_to_buf, Encoder}; + +pub use crate::error::{Error, Result}; +pub use crate::header::Header; +pub use crate::types::{Channels, ColorSpace}; diff --git a/src/pixel.rs b/src/pixel.rs new file mode 100644 index 0000000..d103494 --- /dev/null +++ b/src/pixel.rs @@ -0,0 +1,183 @@ +use crate::consts::{QOI_OP_DIFF, QOI_OP_LUMA, QOI_OP_RGB, QOI_OP_RGBA}; +use crate::error::Result; +use crate::utils::Writer; +use bytemuck::{cast, Pod}; + +#[derive(Copy, Clone, PartialEq, Eq, Debug)] +#[repr(transparent)] +pub struct Pixel([u8; N]); + +impl Pixel { + #[inline] + pub const fn new() -> Self { + Self([0; N]) + } + + #[inline] + pub fn read(&mut self, s: &[u8]) { + if s.len() == N { + let mut i = 0; + while i < N { + self.0[i] = s[i]; + i += 1; + } + } else { + unreachable!(); + } + } + + #[inline] + pub fn update(&mut self, px: Pixel) { + let mut i = 0; + while i < M && i < N { + self.0[i] = px.0[i]; + i += 1; + } + } + + #[inline] + pub fn update_rgb(&mut self, r: u8, g: u8, b: u8) { + self.0[0] = r; + self.0[1] = g; + self.0[2] = b; + } + + #[inline] + pub fn update_rgba(&mut self, r: u8, g: u8, b: u8, a: u8) { + self.0[0] = r; + self.0[1] = g; + self.0[2] = b; + if N >= 4 { + self.0[3] = a; + } + } + + #[inline] + pub fn update_diff(&mut self, b1: u8) { + self.0[0] = self.0[0].wrapping_add((b1 >> 4) & 0x03).wrapping_sub(2); + self.0[1] = self.0[1].wrapping_add((b1 >> 2) & 0x03).wrapping_sub(2); + self.0[2] = self.0[2].wrapping_add(b1 & 0x03).wrapping_sub(2); + } + + #[inline] + pub fn update_luma(&mut self, b1: u8, b2: u8) { + let vg = (b1 & 0x3f).wrapping_sub(32); + let vg_8 = vg.wrapping_sub(8); + let vr = vg_8.wrapping_add((b2 >> 4) & 0x0f); + let vb = vg_8.wrapping_add(b2 & 0x0f); + self.0[0] = self.0[0].wrapping_add(vr); + self.0[1] = self.0[1].wrapping_add(vg); + self.0[2] = self.0[2].wrapping_add(vb); + } + + #[inline] + pub const fn as_rgba(self, with_a: u8) -> Pixel<4> { + let mut i = 0; + let mut out = Pixel::new(); + while i < N { + out.0[i] = self.0[i]; + i += 1; + } + if N < 4 { + out.0[3] = with_a; + } + out + } + + #[inline] + pub const fn r(self) -> u8 { + self.0[0] + } + + #[inline] + pub const fn g(self) -> u8 { + self.0[1] + } + + #[inline] + pub const fn b(self) -> u8 { + self.0[2] + } + + #[inline] + pub const fn with_a(mut self, value: u8) -> Self { + if N >= 4 { + self.0[3] = value; + } + self + } + + #[inline] + pub const fn a_or(self, value: u8) -> u8 { + if N < 4 { + value + } else { + self.0[3] + } + } + + #[inline] + #[allow(clippy::cast_lossless, clippy::cast_possible_truncation)] + pub fn hash_index(self) -> u8 + where + [u8; N]: Pod, + { + // credits for the initial idea: @zakarumych + let v = if N == 4 { + u32::from_ne_bytes(cast(self.0)) + } else { + u32::from_ne_bytes([self.0[0], self.0[1], self.0[2], 0xff]) + } as u64; + let s = ((v & 0xff00_ff00) << 32) | (v & 0x00ff_00ff); + s.wrapping_mul(0x0300_0700_0005_000b_u64).to_le().swap_bytes() as u8 & 63 + } + + #[inline] + pub fn rgb_add(&mut self, r: u8, g: u8, b: u8) { + self.0[0] = self.0[0].wrapping_add(r); + self.0[1] = self.0[1].wrapping_add(g); + self.0[2] = self.0[2].wrapping_add(b); + } + + #[inline] + pub fn encode_into(&self, px_prev: Self, buf: W) -> Result { + if N == 3 || self.a_or(0) == px_prev.a_or(0) { + let vg = self.g().wrapping_sub(px_prev.g()); + let vg_32 = vg.wrapping_add(32); + if vg_32 | 63 == 63 { + let vr = self.r().wrapping_sub(px_prev.r()); + let vb = self.b().wrapping_sub(px_prev.b()); + let vg_r = vr.wrapping_sub(vg); + let vg_b = vb.wrapping_sub(vg); + let (vr_2, vg_2, vb_2) = + (vr.wrapping_add(2), vg.wrapping_add(2), vb.wrapping_add(2)); + if vr_2 | vg_2 | vb_2 | 3 == 3 { + buf.write_one(QOI_OP_DIFF | vr_2 << 4 | vg_2 << 2 | vb_2) + } else { + let (vg_r_8, vg_b_8) = (vg_r.wrapping_add(8), vg_b.wrapping_add(8)); + if vg_r_8 | vg_b_8 | 15 == 15 { + buf.write_many(&[QOI_OP_LUMA | vg_32, vg_r_8 << 4 | vg_b_8]) + } else { + buf.write_many(&[QOI_OP_RGB, self.r(), self.g(), self.b()]) + } + } + } else { + buf.write_many(&[QOI_OP_RGB, self.r(), self.g(), self.b()]) + } + } else { + buf.write_many(&[QOI_OP_RGBA, self.r(), self.g(), self.b(), self.a_or(0xff)]) + } + } +} + +impl From> for [u8; N] { + #[inline(always)] + fn from(px: Pixel) -> Self { + px.0 + } +} + +pub trait SupportedChannels {} + +impl SupportedChannels for Pixel<3> {} +impl SupportedChannels for Pixel<4> {} diff --git a/src/types.rs b/src/types.rs new file mode 100644 index 0000000..81229d4 --- /dev/null +++ b/src/types.rs @@ -0,0 +1,113 @@ +use core::convert::TryFrom; + +use crate::error::{Error, Result}; +use crate::utils::unlikely; + +/// Image color space. +/// +/// Note: the color space is purely informative. Although it is saved to the +/// file header, it does not affect encoding/decoding in any way. +#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)] +#[repr(u8)] +pub enum ColorSpace { + /// sRGB with linear alpha + Srgb = 0, + /// All channels are linear + Linear = 1, +} + +impl ColorSpace { + /// Returns true if the color space is sRGB with linear alpha. + pub const fn is_srgb(self) -> bool { + matches!(self, Self::Srgb) + } + + /// Returns true is all channels are linear. + pub const fn is_linear(self) -> bool { + matches!(self, Self::Linear) + } + + /// Converts to an integer (0 if sRGB, 1 if all linear). + pub const fn as_u8(self) -> u8 { + self as u8 + } +} + +impl Default for ColorSpace { + fn default() -> Self { + Self::Srgb + } +} + +impl From for u8 { + #[inline] + fn from(colorspace: ColorSpace) -> Self { + colorspace as Self + } +} + +impl TryFrom for ColorSpace { + type Error = Error; + + #[inline] + fn try_from(colorspace: u8) -> Result { + if unlikely(colorspace | 1 != 1) { + Err(Error::InvalidColorSpace { colorspace }) + } else { + Ok(if colorspace == 0 { Self::Srgb } else { Self::Linear }) + } + } +} + +/// Number of 8-bit channels in a pixel. +#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)] +#[repr(u8)] +pub enum Channels { + /// Three 8-bit channels (RGB) + Rgb = 3, + /// Four 8-bit channels (RGBA) + Rgba = 4, +} + +impl Channels { + /// Returns true if there are 3 channels (RGB). + pub const fn is_rgb(self) -> bool { + matches!(self, Self::Rgb) + } + + /// Returns true if there are 4 channels (RGBA). + pub const fn is_rgba(self) -> bool { + matches!(self, Self::Rgba) + } + + /// Converts to an integer (3 if RGB, 4 if RGBA). + pub const fn as_u8(self) -> u8 { + self as u8 + } +} + +impl Default for Channels { + fn default() -> Self { + Self::Rgb + } +} + +impl From for u8 { + #[inline] + fn from(channels: Channels) -> Self { + channels as Self + } +} + +impl TryFrom for Channels { + type Error = Error; + + #[inline] + fn try_from(channels: u8) -> Result { + if unlikely(channels != 3 && channels != 4) { + Err(Error::InvalidChannels { channels }) + } else { + Ok(if channels == 3 { Self::Rgb } else { Self::Rgba }) + } + } +} diff --git a/src/utils.rs b/src/utils.rs new file mode 100644 index 0000000..d0c37a6 --- /dev/null +++ b/src/utils.rs @@ -0,0 +1,107 @@ +#[cfg(feature = "std")] +use std::io::Write; + +use crate::error::Result; + +#[inline(always)] +#[cold] +pub const fn cold() {} + +#[inline(always)] +#[allow(unused)] +pub const fn likely(b: bool) -> bool { + if !b { + cold(); + } + b +} + +#[inline(always)] +pub const fn unlikely(b: bool) -> bool { + if b { + cold(); + } + b +} + +pub trait Writer: Sized { + fn write_one(self, v: u8) -> Result; + fn write_many(self, v: &[u8]) -> Result; + fn capacity(&self) -> usize; +} + +pub struct BytesMut<'a>(&'a mut [u8]); + +impl<'a> BytesMut<'a> { + pub fn new(buf: &'a mut [u8]) -> Self { + Self(buf) + } + + #[inline] + pub fn write_one(self, v: u8) -> Self { + if let Some((first, tail)) = self.0.split_first_mut() { + *first = v; + Self(tail) + } else { + unreachable!() + } + } + + #[inline] + pub fn write_many(self, v: &[u8]) -> Self { + if v.len() <= self.0.len() { + let (head, tail) = self.0.split_at_mut(v.len()); + head.copy_from_slice(v); + Self(tail) + } else { + unreachable!() + } + } +} + +impl<'a> Writer for BytesMut<'a> { + #[inline] + fn write_one(self, v: u8) -> Result { + Ok(BytesMut::write_one(self, v)) + } + + #[inline] + fn write_many(self, v: &[u8]) -> Result { + Ok(BytesMut::write_many(self, v)) + } + + #[inline] + fn capacity(&self) -> usize { + self.0.len() + } +} + +#[cfg(feature = "std")] +pub struct GenericWriter { + writer: W, + n_written: usize, +} + +#[cfg(feature = "std")] +impl GenericWriter { + pub const fn new(writer: W) -> Self { + Self { writer, n_written: 0 } + } +} + +#[cfg(feature = "std")] +impl Writer for GenericWriter { + fn write_one(mut self, v: u8) -> Result { + self.n_written += 1; + self.writer.write_all(&[v]).map(|_| self).map_err(Into::into) + } + + fn write_many(mut self, v: &[u8]) -> Result { + self.n_written += v.len(); + self.writer.write_all(v).map(|_| self).map_err(Into::into) + } + + fn capacity(&self) -> usize { + usize::MAX - self.n_written + } +} diff --git a/tests/common.rs b/tests/common.rs new file mode 100644 index 0000000..cc1eff1 --- /dev/null +++ b/tests/common.rs @@ -0,0 +1,12 @@ +#[allow(unused)] +pub fn hash(px: [u8; N]) -> u8 { + let r = px[0]; + let g = px[1]; + let b = px[2]; + let a = if N >= 4 { px[3] } else { 0xff }; + let rm = r.wrapping_mul(3); + let gm = g.wrapping_mul(5); + let bm = b.wrapping_mul(7); + let am = a.wrapping_mul(11); + rm.wrapping_add(gm).wrapping_add(bm).wrapping_add(am) % 64 +} diff --git a/tests/test_chunks.rs b/tests/test_chunks.rs new file mode 100644 index 0000000..d465140 --- /dev/null +++ b/tests/test_chunks.rs @@ -0,0 +1,211 @@ +mod common; + +use bytemuck::{cast_slice, Pod}; + +use qoi::consts::{ + QOI_HEADER_SIZE, QOI_OP_DIFF, QOI_OP_INDEX, QOI_OP_LUMA, QOI_OP_RGB, QOI_OP_RGBA, QOI_OP_RUN, + QOI_PADDING_SIZE, +}; +use qoi::{decode_to_vec, encode_to_vec}; + +use self::common::hash; + +fn test_chunk(pixels: P, expected: E) +where + P: AsRef<[[u8; N]]>, + E: AsRef<[u8]>, + [u8; N]: Pod, +{ + let pixels = pixels.as_ref(); + let expected = expected.as_ref(); + let pixels_raw = cast_slice::<_, u8>(pixels); + let encoded = encode_to_vec(pixels_raw, pixels.len() as _, 1).unwrap(); + let decoded = decode_to_vec(&encoded).unwrap().1; + assert_eq!(pixels_raw, decoded.as_slice(), "roundtrip failed (encoded={:?}))", encoded); + assert!(encoded.len() >= expected.len() + QOI_HEADER_SIZE + QOI_PADDING_SIZE); + assert_eq!(&encoded[QOI_HEADER_SIZE..][..expected.len()], expected); +} + +#[test] +fn test_encode_rgb_3ch() { + test_chunk([[11, 121, 231]], [QOI_OP_RGB, 11, 121, 231]); +} + +#[test] +fn test_encode_rgb_4ch() { + test_chunk([[11, 121, 231, 0xff]], [QOI_OP_RGB, 11, 121, 231]); +} + +#[test] +fn test_encode_rgba() { + test_chunk([[11, 121, 231, 55]], [QOI_OP_RGBA, 11, 121, 231, 55]); +} + +#[test] +fn test_encode_run_start_len1to62_3ch() { + for n in 1..=62 { + let mut v = vec![[0, 0, 0]; n]; + v.push([11, 22, 33]); + test_chunk(v, [QOI_OP_RUN | (n as u8 - 1), QOI_OP_RGB]); + } +} + +#[test] +fn test_encode_run_start_len1to62_4ch() { + for n in 1..=62 { + let mut v = vec![[0, 0, 0, 0xff]; n]; + v.push([11, 22, 33, 44]); + test_chunk(v, [QOI_OP_RUN | (n as u8 - 1), QOI_OP_RGBA]); + } +} + +#[test] +fn test_encode_run_start_63to124_3ch() { + for n in 63..=124 { + let mut v = vec![[0, 0, 0]; n]; + v.push([11, 22, 33]); + test_chunk(v, [QOI_OP_RUN | 61, QOI_OP_RUN | (n as u8 - 63), QOI_OP_RGB]); + } +} + +#[test] +fn test_encode_run_start_len63to124_4ch() { + for n in 63..=124 { + let mut v = vec![[0, 0, 0, 0xff]; n]; + v.push([11, 22, 33, 44]); + test_chunk(v, [QOI_OP_RUN | 61, QOI_OP_RUN | (n as u8 - 63), QOI_OP_RGBA]); + } +} + +#[test] +fn test_encode_run_end_3ch() { + let px = [11, 33, 55]; + test_chunk( + [[1, 99, 2], px, px, px], + [QOI_OP_RGB, 1, 99, 2, QOI_OP_RGB, px[0], px[1], px[2], QOI_OP_RUN | 1], + ); +} + +#[test] +fn test_encode_run_end_4ch() { + let px = [11, 33, 55, 77]; + test_chunk( + [[1, 99, 2, 3], px, px, px], + [QOI_OP_RGBA, 1, 99, 2, 3, QOI_OP_RGBA, px[0], px[1], px[2], px[3], QOI_OP_RUN | 1], + ); +} + +#[test] +fn test_encode_run_mid_3ch() { + let px = [11, 33, 55]; + test_chunk( + [[1, 99, 2], px, px, px, [1, 2, 3]], + [QOI_OP_RGB, 1, 99, 2, QOI_OP_RGB, px[0], px[1], px[2], QOI_OP_RUN | 1], + ); +} + +#[test] +fn test_encode_run_mid_4ch() { + let px = [11, 33, 55, 77]; + test_chunk( + [[1, 99, 2, 3], px, px, px, [1, 2, 3, 4]], + [QOI_OP_RGBA, 1, 99, 2, 3, QOI_OP_RGBA, px[0], px[1], px[2], px[3], QOI_OP_RUN | 1], + ); +} + +#[test] +fn test_encode_index_3ch() { + let px = [101, 102, 103]; + test_chunk( + [px, [1, 2, 3], px], + [QOI_OP_RGB, 101, 102, 103, QOI_OP_RGB, 1, 2, 3, QOI_OP_INDEX | hash(px)], + ); +} + +#[test] +fn test_encode_index_4ch() { + let px = [101, 102, 103, 104]; + test_chunk( + [px, [1, 2, 3, 4], px], + [QOI_OP_RGBA, 101, 102, 103, 104, QOI_OP_RGBA, 1, 2, 3, 4, QOI_OP_INDEX | hash(px)], + ); +} + +#[test] +fn test_encode_index_zero_3ch() { + let px = [0, 0, 0]; + test_chunk([[101, 102, 103], px], [QOI_OP_RGB, 101, 102, 103, QOI_OP_RGB, 0, 0, 0]); +} + +#[test] +fn test_encode_index_zero_0x00_4ch() { + let px = [0, 0, 0, 0]; + test_chunk( + [[101, 102, 103, 104], px], + [QOI_OP_RGBA, 101, 102, 103, 104, QOI_OP_INDEX | hash(px)], + ); +} + +#[test] +fn test_encode_index_zero_0xff_4ch() { + let px = [0, 0, 0, 0xff]; + test_chunk( + [[101, 102, 103, 104], px], + [QOI_OP_RGBA, 101, 102, 103, 104, QOI_OP_RGBA, 0, 0, 0, 0xff], + ); +} + +#[test] +fn test_encode_diff() { + for x in 0..8_u8 { + let x = [x.wrapping_sub(5), x.wrapping_sub(4), x.wrapping_sub(3)]; + for dr in 0..3 { + for dg in 0..3 { + for db in 0..3 { + if dr != 2 || dg != 2 || db != 2 { + let r = x[0].wrapping_add(dr).wrapping_sub(2); + let g = x[1].wrapping_add(dg).wrapping_sub(2); + let b = x[2].wrapping_add(db).wrapping_sub(2); + let d = QOI_OP_DIFF | dr << 4 | dg << 2 | db; + test_chunk( + [[1, 99, 2], x, [r, g, b]], + [QOI_OP_RGB, 1, 99, 2, QOI_OP_RGB, x[0], x[1], x[2], d], + ); + test_chunk( + [[1, 99, 2, 0xff], [x[0], x[1], x[2], 9], [r, g, b, 9]], + [QOI_OP_RGB, 1, 99, 2, QOI_OP_RGBA, x[0], x[1], x[2], 9, d], + ); + } + } + } + } + } +} + +#[test] +fn test_encode_luma() { + for x in (0..200_u8).step_by(4) { + let x = [x.wrapping_mul(3), x.wrapping_sub(5), x.wrapping_sub(7)]; + for dr_g in (0..16).step_by(4) { + for dg in (0..64).step_by(8) { + for db_g in (0..16).step_by(4) { + if dr_g != 8 || dg != 32 || db_g != 8 { + let r = x[0].wrapping_add(dr_g).wrapping_add(dg).wrapping_sub(40); + let g = x[1].wrapping_add(dg).wrapping_sub(32); + let b = x[2].wrapping_add(db_g).wrapping_add(dg).wrapping_sub(40); + let d1 = QOI_OP_LUMA | dg; + let d2 = (dr_g << 4) | db_g; + test_chunk( + [[1, 99, 2], x, [r, g, b]], + [QOI_OP_RGB, 1, 99, 2, QOI_OP_RGB, x[0], x[1], x[2], d1, d2], + ); + test_chunk( + [[1, 99, 2, 0xff], [x[0], x[1], x[2], 9], [r, g, b, 9]], + [QOI_OP_RGB, 1, 99, 2, QOI_OP_RGBA, x[0], x[1], x[2], 9, d1, d2], + ); + } + } + } + } + } +} diff --git a/tests/test_gen.rs b/tests/test_gen.rs new file mode 100644 index 0000000..08767d4 --- /dev/null +++ b/tests/test_gen.rs @@ -0,0 +1,313 @@ +mod common; + +use bytemuck::cast_slice; +use std::borrow::Cow; +use std::fmt::Debug; + +use cfg_if::cfg_if; +use rand::{ + distributions::{Distribution, Standard}, + rngs::StdRng, + Rng, SeedableRng, +}; + +use libqoi::{qoi_decode, qoi_encode}; +use qoi::consts::{ + QOI_HEADER_SIZE, QOI_MASK_2, QOI_OP_DIFF, QOI_OP_INDEX, QOI_OP_LUMA, QOI_OP_RGB, QOI_OP_RGBA, + QOI_OP_RUN, QOI_PADDING_SIZE, +}; +use qoi::{decode_header, decode_to_vec, encode_to_vec}; + +use self::common::hash; + +struct GenState { + index: [[u8; N]; 64], + pixels: Vec, + prev: [u8; N], + len: usize, +} + +impl GenState { + pub fn with_capacity(capacity: usize) -> Self { + Self { + index: [[0; N]; 64], + pixels: Vec::with_capacity(capacity * N), + prev: Self::zero(), + len: 0, + } + } + pub fn write(&mut self, px: [u8; N]) { + self.index[hash(px) as usize] = px; + for i in 0..N { + self.pixels.push(px[i]); + } + self.prev = px; + self.len += 1; + } + + pub fn pick_from_index(&self, rng: &mut impl Rng) -> [u8; N] { + self.index[rng.gen_range(0_usize..64)] + } + + pub fn zero() -> [u8; N] { + let mut px = [0; N]; + if N >= 4 { + px[3] = 0xff; + } + px + } +} + +struct ImageGen { + p_new: f64, + p_index: f64, + p_repeat: f64, + p_diff: f64, + p_luma: f64, +} + +impl ImageGen { + pub fn new_random(rng: &mut impl Rng) -> Self { + let p: [f64; 6] = rng.gen(); + let t = p.iter().sum::(); + Self { + p_new: p[0] / t, + p_index: p[1] / t, + p_repeat: p[2] / t, + p_diff: p[3] / t, + p_luma: p[4] / t, + } + } + + pub fn generate(&self, rng: &mut impl Rng, channels: usize, min_len: usize) -> Vec { + match channels { + 3 => self.generate_const::<_, 3>(rng, min_len), + 4 => self.generate_const::<_, 4>(rng, min_len), + _ => panic!(), + } + } + + fn generate_const(&self, rng: &mut R, min_len: usize) -> Vec + where + Standard: Distribution<[u8; N]>, + { + let mut s = GenState::::with_capacity(min_len); + let zero = GenState::::zero(); + + while s.len < min_len { + let mut p = rng.gen_range(0.0..1.0); + + if p < self.p_new { + s.write(rng.gen()); + continue; + } + p -= self.p_new; + + if p < self.p_index { + let px = s.pick_from_index(rng); + s.write(px); + continue; + } + p -= self.p_index; + + if p < self.p_repeat { + let px = s.prev; + let n_repeat = rng.gen_range(1_usize..=70); + for _ in 0..n_repeat { + s.write(px); + } + continue; + } + p -= self.p_repeat; + + if p < self.p_diff { + let mut px = s.prev; + px[0] = px[0].wrapping_add(rng.gen_range(0_u8..4).wrapping_sub(2)); + px[1] = px[1].wrapping_add(rng.gen_range(0_u8..4).wrapping_sub(2)); + px[2] = px[2].wrapping_add(rng.gen_range(0_u8..4).wrapping_sub(2)); + s.write(px); + continue; + } + p -= self.p_diff; + + if p < self.p_luma { + let mut px = s.prev; + let vg = rng.gen_range(0_u8..64).wrapping_sub(32); + let vr = rng.gen_range(0_u8..16).wrapping_sub(8).wrapping_add(vg); + let vb = rng.gen_range(0_u8..16).wrapping_sub(8).wrapping_add(vg); + px[0] = px[0].wrapping_add(vr); + px[1] = px[1].wrapping_add(vg); + px[2] = px[2].wrapping_add(vb); + s.write(px); + continue; + } + + s.write(zero); + } + + s.pixels + } +} + +fn format_encoded(encoded: &[u8]) -> String { + let header = decode_header(encoded).unwrap(); + let mut data = &encoded[QOI_HEADER_SIZE..encoded.len() - QOI_PADDING_SIZE]; + let mut s = format!("{}x{}:{} = [", header.width, header.height, header.channels.as_u8()); + while !data.is_empty() { + let b1 = data[0]; + data = &data[1..]; + match b1 { + QOI_OP_RGB => { + s.push_str(&format!("rgb({},{},{})", data[0], data[1], data[2])); + data = &data[3..]; + } + QOI_OP_RGBA => { + s.push_str(&format!("rgba({},{},{},{})", data[0], data[1], data[2], data[3])); + data = &data[4..]; + } + _ => match b1 & QOI_MASK_2 { + QOI_OP_INDEX => s.push_str(&format!("index({})", b1 & 0x3f)), + QOI_OP_RUN => s.push_str(&format!("run({})", b1 & 0x3f)), + QOI_OP_DIFF => s.push_str(&format!( + "diff({},{},{})", + (b1 >> 4) & 0x03, + (b1 >> 2) & 0x03, + b1 & 0x03 + )), + QOI_OP_LUMA => { + let b2 = data[0]; + data = &data[1..]; + s.push_str(&format!("luma({},{},{})", (b2 >> 4) & 0x0f, b1 & 0x3f, b2 & 0x0f)) + } + _ => {} + }, + } + s.push_str(", "); + } + s.pop().unwrap(); + s.pop().unwrap(); + s.push(']'); + s +} + +fn check_roundtrip( + msg: &str, mut data: &[u8], channels: usize, encode: E, decode: D, +) where + E: Fn(&[u8], u32) -> Result, + D: Fn(&[u8]) -> Result, + VE: AsRef<[u8]>, + VD: AsRef<[u8]>, + EE: Debug, + ED: Debug, +{ + macro_rules! rt { + ($data:expr, $n:expr) => { + decode(encode($data, $n as _).unwrap().as_ref()).unwrap() + }; + } + macro_rules! fail { + ($msg:expr, $data:expr, $decoded:expr, $encoded:expr, $channels:expr) => { + assert!( + false, + "{} roundtrip failed\n\n image: {:?}\ndecoded: {:?}\nencoded: {}", + $msg, + cast_slice::<_, [u8; $channels]>($data.as_ref()), + cast_slice::<_, [u8; $channels]>($decoded.as_ref()), + format_encoded($encoded.as_ref()), + ); + }; + } + + let mut n_pixels = data.len() / channels; + assert_eq!(n_pixels * channels, data.len()); + + // if all ok, return + // ... but if roundtrip check fails, try to reduce the example to the smallest we can find + if rt!(data, n_pixels).as_ref() == data { + return; + } + + // try removing pixels from the beginning + while n_pixels > 1 { + let slice = &data[..data.len() - channels]; + if rt!(slice, n_pixels - 1).as_ref() != slice { + data = slice; + n_pixels -= 1; + } else { + break; + } + } + + // try removing pixels from the end + while n_pixels > 1 { + let slice = &data[channels..]; + if rt!(slice, n_pixels - 1).as_ref() != slice { + data = slice; + n_pixels -= 1; + } else { + break; + } + } + + // try removing pixels from the middle + let mut data = Cow::from(data); + let mut pos = 1; + while n_pixels > 1 && pos < n_pixels - 1 { + let mut vec = data.to_vec(); + for _ in 0..channels { + vec.remove(pos * channels); + } + if rt!(vec.as_slice(), n_pixels - 1).as_ref() != vec.as_slice() { + data = Cow::from(vec); + n_pixels -= 1; + } else { + pos += 1; + } + } + + let encoded = encode(data.as_ref(), n_pixels as _).unwrap(); + let decoded = decode(encoded.as_ref()).unwrap(); + assert_ne!(decoded.as_ref(), data.as_ref()); + if channels == 3 { + fail!(msg, data, decoded, encoded, 3); + } else { + fail!(msg, data, decoded, encoded, 4); + } +} + +#[test] +fn test_generated() { + let mut rng = StdRng::seed_from_u64(0); + + let mut n_pixels = 0; + while n_pixels < 20_000_000 { + let min_len = rng.gen_range(1..=5000); + let channels = rng.gen_range(3..=4); + let gen = ImageGen::new_random(&mut rng); + let img = gen.generate(&mut rng, channels, min_len); + + let encode = |data: &[u8], size| encode_to_vec(data, size, 1); + let decode = |data: &[u8]| decode_to_vec(data).map(|r| r.1); + let encode_c = |data: &[u8], size| qoi_encode(data, size, 1, channels as _); + let decode_c = |data: &[u8]| qoi_decode(data, channels as _).map(|r| r.1); + + check_roundtrip("qoi-rust -> qoi-rust", &img, channels as _, encode, decode); + check_roundtrip("qoi-rust -> qoi.h", &img, channels as _, encode, decode_c); + check_roundtrip("qoi.h -> qoi-rust", &img, channels as _, encode_c, decode); + + let size = (img.len() / channels) as u32; + let encoded = encode(&img, size).unwrap(); + let encoded_c = encode_c(&img, size).unwrap(); + cfg_if! { + if #[cfg(feature = "reference")] { + let eq = encoded.as_slice() == encoded_c.as_ref(); + assert!(eq, "qoi-rust [reference mode] doesn't match qoi.h"); + } else { + let eq = encoded.len() == encoded_c.len(); + assert!(eq, "qoi-rust [non-reference mode] length doesn't match qoi.h"); + } + } + + n_pixels += size; + } +} diff --git a/tests/test_misc.rs b/tests/test_misc.rs new file mode 100644 index 0000000..720adf4 --- /dev/null +++ b/tests/test_misc.rs @@ -0,0 +1,6 @@ +#[test] +fn test_new_encoder() { + // this used to fail due to `Bytes` not being `pub` + let arr = [0u8]; + let _ = qoi::Decoder::new(&arr[..]); +} \ No newline at end of file diff --git a/tests/test_ref.rs b/tests/test_ref.rs new file mode 100644 index 0000000..59a7315 --- /dev/null +++ b/tests/test_ref.rs @@ -0,0 +1,114 @@ +use std::fs::{self, File}; +use std::path::{Path, PathBuf}; + +use anyhow::{bail, Result}; +use cfg_if::cfg_if; +use walkdir::{DirEntry, WalkDir}; + +use qoi::{decode_to_vec, encode_to_vec}; + +fn find_qoi_png_pairs(root: impl AsRef) -> Vec<(PathBuf, PathBuf)> { + let root = root.as_ref(); + + let get_ext = + |path: &Path| path.extension().unwrap_or_default().to_string_lossy().to_ascii_lowercase(); + let check_qoi_png_pair = |path: &Path| { + let (qoi, png) = (path.to_path_buf(), path.with_extension("png")); + if qoi.is_file() && get_ext(&qoi) == "qoi" && png.is_file() { + Some((qoi, png)) + } else { + None + } + }; + + let mut out = vec![]; + if let Some(pair) = check_qoi_png_pair(root) { + out.push(pair); + } else if root.is_dir() { + out.extend( + WalkDir::new(root) + .follow_links(true) + .into_iter() + .filter_map(Result::ok) + .map(DirEntry::into_path) + .filter_map(|p| check_qoi_png_pair(&p)), + ) + } + out +} + +struct Image { + pub width: u32, + pub height: u32, + pub channels: u8, + pub data: Vec, +} + +impl Image { + fn from_png(filename: &Path) -> Result { + let decoder = png::Decoder::new(File::open(filename)?); + let mut reader = decoder.read_info()?; + let mut buf = vec![0; reader.output_buffer_size()]; + let info = reader.next_frame(&mut buf)?; + let bytes = &buf[..info.buffer_size()]; + Ok(Self { + width: info.width, + height: info.height, + channels: info.color_type.samples() as u8, + data: bytes.to_vec(), + }) + } +} + +fn compare_slices(name: &str, desc: &str, result: &[u8], expected: &[u8]) -> Result<()> { + if result == expected { + Ok(()) + } else { + if let Some(i) = + (0..result.len().min(expected.len())).position(|i| result[i] != expected[i]) + { + bail!( + "{}: {} mismatch at byte {}: expected {:?}, got {:?}", + name, + desc, + i, + &expected[i..(i + 4).min(expected.len())], + &result[i..(i + 4).min(result.len())], + ); + } else { + bail!( + "{}: {} length mismatch: expected {}, got {}", + name, + desc, + expected.len(), + result.len() + ); + } + } +} + +#[test] +fn test_reference_images() -> Result<()> { + let pairs = find_qoi_png_pairs("assets"); + assert!(!pairs.is_empty()); + + for (qoi_path, png_path) in &pairs { + let png_name = png_path.file_name().unwrap_or_default().to_string_lossy(); + let img = Image::from_png(png_path)?; + println!("{} {} {} {}", png_name, img.width, img.height, img.channels); + let encoded = encode_to_vec(&img.data, img.width, img.height)?; + let expected = fs::read(qoi_path)?; + assert_eq!(encoded.len(), expected.len()); // this should match regardless + cfg_if! { + if #[cfg(feature = "reference")] { + compare_slices(&png_name, "encoding", &encoded, &expected)?; + } + } + let (_header1, decoded1) = decode_to_vec(&encoded)?; + let (_header2, decoded2) = decode_to_vec(&expected)?; + compare_slices(&png_name, "decoding [1]", &decoded1, &img.data)?; + compare_slices(&png_name, "decoding [2]", &decoded2, &img.data)?; + } + + Ok(()) +} -- 2.7.4