| // Copyright 2017 The Wuffs Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // ---------------- |
| |
| // This file contains a hand-written C implementation of |
| // release/c/wuffs-unsupported-snapshot.c's generated |
| // wuffs_deflate__decoder__decode_huffman_fast function. |
| // |
| // It is not intended to be used in production settings, on untrusted data. Its |
| // purpose is to give a rough upper bound on how fast Wuffs' generated C code |
| // can be, with a sufficiently smart Wuffs compiler. |
| // |
| // To repeat, substituting in this C implementation is NOT SAFE, and may result |
| // in buffer overflows. This code exists only to aid optimization of the (safe) |
| // std/deflate/*.wuffs code and the Wuffs compiler's code generation. |
| |
| // ---------------- |
| |
| // Having said that, to generate the benchmark numbers with this hand-written C |
| // implementation, edit release/c/wuffs-unsupported-snapshot.c and find the |
| // lines that say |
| // |
| // // ‼ WUFFS C HEADER ENDS HERE. |
| // #ifdef WUFFS_IMPLEMENTATION |
| // |
| // After that, add this line: |
| // |
| // #include "../../script/wuffs-deflate-decoder-decode-huffman.c" |
| // |
| // Then find the calls to wuffs_deflate__decoder__decode_huffman_fastxx. They |
| // should be inside the wuffs_deflate__decoder__decode_blocks function body, |
| // and the lines of code should look something like |
| // v_status = wuffs_deflate__decoder__decode_huffman_fast32(etc); |
| // and |
| // v_status = wuffs_deflate__decoder__decode_huffman_fast64(etc); |
| // |
| // Change the "wuffs_etc_fastxx" to "c_wuffs_etc_fast", i.e. add a "c_" prefix |
| // and drop the "32" or "64" suffix. The net result should look something like: |
| // |
| // clang-format off |
| /* |
| |
| $ git diff release/c/wuffs-unsupported-snapshot.c |
| diff --git a/release/c/wuffs-unsupported-snapshot.c b/release/c/wuffs-unsupported-snapshot.c |
| index d255a788..2a112728 100644 |
| --- a/release/c/wuffs-unsupported-snapshot.c |
| +++ b/release/c/wuffs-unsupported-snapshot.c |
| @@ -9758,6 +9758,8 @@ DecodeJson(DecodeJsonCallbacks& callbacks, |
| // ‼ WUFFS C HEADER ENDS HERE. |
| #ifdef WUFFS_IMPLEMENTATION |
| |
| +#include "../../script/wuffs-deflate-decoder-decode-huffman.c" |
| + |
| #ifdef __cplusplus |
| extern "C" { |
| #endif |
| @@ -25326,7 +25328,7 @@ wuffs_deflate__decoder__decode_blocks( |
| if (a_src) { |
| a_src->meta.ri = ((size_t)(iop_a_src - a_src->data.ptr)); |
| } |
| - v_status = wuffs_deflate__decoder__decode_huffman_fast32(self, a_dst, a_src); |
| + v_status = c_wuffs_deflate__decoder__decode_huffman_fast(self, a_dst, a_src); |
| if (a_src) { |
| iop_a_src = a_src->data.ptr + a_src->meta.ri; |
| } |
| @@ -25334,7 +25336,7 @@ wuffs_deflate__decoder__decode_blocks( |
| if (a_src) { |
| a_src->meta.ri = ((size_t)(iop_a_src - a_src->data.ptr)); |
| } |
| - v_status = wuffs_deflate__decoder__decode_huffman_fast64(self, a_dst, a_src); |
| + v_status = c_wuffs_deflate__decoder__decode_huffman_fast(self, a_dst, a_src); |
| if (a_src) { |
| iop_a_src = a_src->data.ptr + a_src->meta.ri; |
| } |
| |
| */ |
| // clang-format on |
| // |
| // That concludes the edits to release/c/wuffs-unsupported-snapshot.c. Run the |
| // tests and benchmarks with the "-skipgen" flag, otherwise the "wuffs" tool |
| // will re-generate the C code and override your edits: |
| // |
| // wuffs test -skipgen std/deflate |
| // wuffs bench -skipgen std/deflate |
| // |
| // You may also want to focus on one specific test, e.g.: |
| // |
| // wuffs test -skipgen -focus=wuffs_deflate_decode_midsummer std/deflate |
| // wuffs bench -skipgen -focus=wuffs_deflate_decode_100k_just std/deflate |
| |
| #include <stdbool.h> |
| #include <stddef.h> |
| #include <stdint.h> |
| #include <stdio.h> // For manual printf debugging. |
| #include <string.h> |
| |
| extern const char wuffs_deflate__error__internal_error_inconsistent_distance[]; |
| extern const char |
| wuffs_deflate__error__internal_error_inconsistent_huffman_decoder_state[]; |
| |
| // ---------------- |
| |
| // Define this macro to make this file compilable standalone, instead of |
| // hooking it into release/c/wuffs-unsupported-snapshot.c per the instructions |
| // above. Standalone means that you can run a "does it compile" check by |
| // |
| // gcc -c script/wuffs-deflate-decoder-decode-huffman.c -o /dev/null |
| // |
| // and also drop this file into disassembly tools like https://godbolt.org/ |
| |
| //#define MAKE_THIS_FILE_COMPILABLE_STANDALONE |
| |
| #ifdef MAKE_THIS_FILE_COMPILABLE_STANDALONE |
| |
| typedef struct { |
| const char* repr; |
| } wuffs_base__status; |
| |
| static inline wuffs_base__status // |
| wuffs_base__make_status(const char* repr) { |
| wuffs_base__status z; |
| z.repr = repr; |
| return z; |
| } |
| |
| typedef struct { |
| uint8_t* ptr; |
| size_t len; |
| } wuffs_base__slice_u8; |
| typedef struct { |
| size_t wi; |
| size_t ri; |
| uint64_t pos; |
| bool closed; |
| } wuffs_base__io_buffer_meta; |
| typedef struct { |
| wuffs_base__slice_u8 data; |
| wuffs_base__io_buffer_meta meta; |
| } wuffs_base__io_buffer; |
| typedef struct wuffs_deflate__decoder__struct { |
| struct { |
| uint32_t magic; |
| uint32_t f_bits; |
| uint32_t f_n_bits; |
| uint32_t f_history_index; |
| uint32_t f_n_huffs_bits[2]; |
| bool f_end_of_block; |
| } private_impl; |
| struct { |
| // 1024 is huffs_table_size in std/deflate/decode_deflate.wuffs. |
| uint32_t f_huffs[2][1024]; |
| uint8_t f_history[32768]; |
| uint8_t f_code_lengths[320]; |
| } private_data; |
| } wuffs_deflate__decoder; |
| |
| const char wuffs_base__error__bad_argument[] = "?base: bad argument"; |
| const char wuffs_deflate__error__bad_distance[] = "?deflate: bad distance"; |
| const char wuffs_deflate__error__internal_error_inconsistent_distance[] = |
| "?deflate: internal error: inconsistent distance"; |
| const char |
| wuffs_deflate__error__internal_error_inconsistent_huffman_decoder_state[] = |
| "?deflate: internal error: inconsistent Huffman decoder state"; |
| |
| static wuffs_base__status // |
| wuffs_deflate__decoder__decode_huffman_fast(wuffs_deflate__decoder* self, |
| wuffs_base__io_buffer* a_dst, |
| wuffs_base__io_buffer* a_src) { |
| return wuffs_base__make_status(NULL); |
| } |
| |
| #endif // MAKE_THIS_FILE_COMPILABLE_STANDALONE |
| |
| // ---------------- |
| |
| // Define this macro to further speed up this C implementation, using two |
| // techniques that are not used by the zlib-the-library C implementation (as of |
| // version 1.2.11, current as of November 2017). Doing so gives data for "how |
| // fast can Wuffs' zlib-the-format implementation be" instead of "is Wuffs' |
| // generated C code as fast as zlib-the-library's hand-written C code". |
| // |
| // Whether the same techniques could apply to zlib-the-library is discussed at |
| // https://github.com/madler/zlib/pull/292 |
| #ifdef __x86_64__ |
| //#define WUFFS_DEFLATE__HAVE_64_BIT_UNALIGNED_LITTLE_ENDIAN_LOADS |
| #endif |
| |
| // wuffs_base__width_to_mask_table is the width_to_mask_table from |
| // https://fgiesen.wordpress.com/2018/02/19/reading-bits-in-far-too-many-ways-part-1/ |
| // |
| // Look for "It may feel ridiculous" on that page for the rationale. |
| static const uint32_t wuffs_base__width_to_mask_table[33] = { |
| 0x00000000u, |
| |
| 0x00000001u, 0x00000003u, 0x00000007u, 0x0000000Fu, |
| 0x0000001Fu, 0x0000003Fu, 0x0000007Fu, 0x000000FFu, |
| |
| 0x000001FFu, 0x000003FFu, 0x000007FFu, 0x00000FFFu, |
| 0x00001FFFu, 0x00003FFFu, 0x00007FFFu, 0x0000FFFFu, |
| |
| 0x0001FFFFu, 0x0003FFFFu, 0x0007FFFFu, 0x000FFFFFu, |
| 0x001FFFFFu, 0x003FFFFFu, 0x007FFFFFu, 0x00FFFFFFu, |
| |
| 0x01FFFFFFu, 0x03FFFFFFu, 0x07FFFFFFu, 0x0FFFFFFFu, |
| 0x1FFFFFFFu, 0x3FFFFFFFu, 0x7FFFFFFFu, 0xFFFFFFFFu, |
| }; |
| |
| // Uncomment exactly one of these. Choosing between them lets us measure the |
| // effect of the table-based mask. |
| //#define MASK(n) ((((uint32_t)1) << (n)) - 1) |
| #define MASK(n) wuffs_base__width_to_mask_table[n] |
| |
| // ---------------- |
| |
| // These are the generated functions that we are explicitly overriding. Note |
| // that the function name is "wuffs_etc", not "c_wuffs_etc". |
| static wuffs_base__status // |
| wuffs_deflate__decoder__decode_huffman_fast32(wuffs_deflate__decoder* self, |
| wuffs_base__io_buffer* a_dst, |
| wuffs_base__io_buffer* a_src); |
| static wuffs_base__status // |
| wuffs_deflate__decoder__decode_huffman_fast64(wuffs_deflate__decoder* self, |
| wuffs_base__io_buffer* a_dst, |
| wuffs_base__io_buffer* a_src); |
| |
| // This is the overriding implementation. |
| wuffs_base__status // |
| c_wuffs_deflate__decoder__decode_huffman_fast(wuffs_deflate__decoder* self, |
| wuffs_base__io_buffer* a_dst, |
| wuffs_base__io_buffer* a_src) { |
| // Avoid the -Werror=unused-function warning for the now-unused |
| // overridden wuffs_deflate__decoder__decode_huffman_fastxx functions. |
| (void)(wuffs_deflate__decoder__decode_huffman_fast32); |
| (void)(wuffs_deflate__decoder__decode_huffman_fast64); |
| |
| if (!a_dst || !a_src) { |
| return wuffs_base__make_status(wuffs_base__error__bad_argument); |
| } |
| wuffs_base__status status = wuffs_base__make_status(NULL); |
| |
| // Load contextual state. Prepare to check that pdst and psrc remain within |
| // a_dst's and a_src's bounds. |
| |
| uint8_t* pdst = a_dst->data.ptr + a_dst->meta.wi; |
| uint8_t* qdst = a_dst->data.ptr + a_dst->data.len; |
| if ((qdst - pdst) < 258) { |
| return wuffs_base__make_status(NULL); |
| } else { |
| qdst -= 258; |
| } |
| |
| uint8_t* psrc = a_src->data.ptr + a_src->meta.ri; |
| uint8_t* qsrc = a_src->data.ptr + a_src->meta.wi; |
| if ((qsrc - psrc) < 12) { |
| return wuffs_base__make_status(NULL); |
| } else { |
| qsrc -= 12; |
| } |
| |
| #if defined(WUFFS_DEFLATE__HAVE_64_BIT_UNALIGNED_LITTLE_ENDIAN_LOADS) |
| uint64_t bits = self->private_impl.f_bits; |
| #else |
| uint32_t bits = self->private_impl.f_bits; |
| #endif |
| uint32_t n_bits = self->private_impl.f_n_bits; |
| |
| // Initialize other local variables. |
| uint8_t* pdst_mark = a_dst->data.ptr; |
| uint32_t lmask = MASK(self->private_impl.f_n_huffs_bits[0]); |
| uint32_t dmask = MASK(self->private_impl.f_n_huffs_bits[1]); |
| |
| outer_loop: |
| while ((pdst <= qdst) && (psrc <= qsrc)) { |
| #if defined(WUFFS_DEFLATE__HAVE_64_BIT_UNALIGNED_LITTLE_ENDIAN_LOADS) |
| // Ensure that we have at least 56 bits of input. |
| // |
| // This is "Variant 4" of |
| // https://fgiesen.wordpress.com/2018/02/20/reading-bits-in-far-too-many-ways-part-2/ |
| // |
| // 56, the number of bits in 7 bytes, is a property of that "Variant 4" |
| // bit-reading technique, and not related to the DEFLATE format per se. |
| // |
| // Specifically for DEFLATE, we need only up to 48 bits per outer_loop |
| // iteration. The maximum input bits used by a length/distance pair is 15 |
| // bits for the length code, 5 bits for the length extra, 15 bits for the |
| // distance code, and 13 bits for the distance extra. This totals 48 bits. |
| // |
| // The fact that the 48 we need is less than the 56 we get is a happy |
| // coincidence. It lets us eliminate any other loads in the loop body. |
| uint64_t src_u64; |
| memcpy(&src_u64, psrc, 8); |
| bits |= src_u64 << n_bits; |
| psrc += (63 - n_bits) >> 3; |
| n_bits |= 56; |
| #else |
| // Ensure that we have at least 15 bits of input. |
| if (n_bits < 15) { |
| bits |= ((uint32_t)(*psrc++)) << n_bits; |
| n_bits += 8; |
| bits |= ((uint32_t)(*psrc++)) << n_bits; |
| n_bits += 8; |
| } |
| #endif |
| |
| // Decode an lcode symbol from H-L. |
| uint32_t table_entry = self->private_data.f_huffs[0][bits & lmask]; |
| while (true) { |
| uint32_t n = table_entry & 0x0F; |
| bits >>= n; |
| n_bits -= n; |
| if ((table_entry >> 31) != 0) { |
| // Literal. |
| *pdst++ = (uint8_t)(table_entry >> 8); |
| goto outer_loop; |
| } |
| if ((table_entry >> 30) != 0) { |
| // Back-reference; length = base_number + extra_bits. |
| break; |
| } |
| if ((table_entry >> 29) != 0) { |
| // End of block. |
| self->private_impl.f_end_of_block = true; |
| goto end; |
| } |
| if ((table_entry >> 24) != 0x10) { |
| status = wuffs_base__make_status( |
| wuffs_deflate__error__internal_error_inconsistent_huffman_decoder_state); |
| goto end; |
| } |
| uint32_t top = (table_entry >> 8) & 0xFFFF; |
| uint32_t mask = MASK((table_entry >> 4) & 0x0F); |
| table_entry = self->private_data.f_huffs[0][top + (bits & mask)]; |
| } |
| |
| // length = base_number_minus_3 + 3 + extra_bits. |
| uint32_t length = ((table_entry >> 8) & 0xFF) + 3; |
| { |
| uint32_t n = (table_entry >> 4) & 0x0F; |
| if (n) { |
| #if !defined(WUFFS_DEFLATE__HAVE_64_BIT_UNALIGNED_LITTLE_ENDIAN_LOADS) |
| if (n_bits < n) { |
| bits |= ((uint32_t)(*psrc++)) << n_bits; |
| n_bits += 8; |
| } |
| #endif |
| length += bits & MASK(n); |
| bits >>= n; |
| n_bits -= n; |
| } |
| } |
| |
| #if !defined(WUFFS_DEFLATE__HAVE_64_BIT_UNALIGNED_LITTLE_ENDIAN_LOADS) |
| // Ensure that we have at least 15 bits of input. |
| if (n_bits < 15) { |
| bits |= ((uint32_t)(*psrc++)) << n_bits; |
| n_bits += 8; |
| bits |= ((uint32_t)(*psrc++)) << n_bits; |
| n_bits += 8; |
| } |
| #endif |
| |
| // Decode a dcode symbol from H-D. |
| table_entry = self->private_data.f_huffs[1][bits & dmask]; |
| while (true) { |
| uint32_t n = table_entry & 0x0F; |
| bits >>= n; |
| n_bits -= n; |
| if ((table_entry >> 30) != 0) { |
| // Back-reference; distance = base_number + extra_bits. |
| break; |
| } |
| if ((table_entry >> 24) != 0x10) { |
| status = wuffs_base__make_status( |
| wuffs_deflate__error__internal_error_inconsistent_huffman_decoder_state); |
| goto end; |
| } |
| uint32_t top = (table_entry >> 8) & 0xFFFF; |
| uint32_t mask = MASK((table_entry >> 4) & 0x0F); |
| table_entry = self->private_data.f_huffs[1][top + (bits & mask)]; |
| } |
| |
| // dist_minus_1 = base_number_minus_1 + extra_bits. |
| // distance = dist_minus_1 + 1. |
| uint32_t dist_minus_1 = (table_entry >> 8) & 0xFFFF; |
| { |
| uint32_t n = (table_entry >> 4) & 0x0F; |
| #if !defined(WUFFS_DEFLATE__HAVE_64_BIT_UNALIGNED_LITTLE_ENDIAN_LOADS) |
| // Ensure that we have at least n bits of input. |
| if (n_bits < n) { |
| bits |= ((uint32_t)(*psrc++)) << n_bits; |
| n_bits += 8; |
| bits |= ((uint32_t)(*psrc++)) << n_bits; |
| n_bits += 8; |
| } |
| #endif |
| dist_minus_1 += bits & MASK(n); |
| bits >>= n; |
| n_bits -= n; |
| } |
| |
| // Copy from the history buffer, if necessary. |
| if ((ptrdiff_t)(dist_minus_1 + 1) > (pdst - pdst_mark)) { |
| // Set (hlen, hdist) to be the length-distance pair to copy from |
| // this.history, and (length, distance) to be the remaining |
| // length-distance pair to copy from args.dst. |
| uint32_t hlen = 0; |
| uint32_t hdist = ((dist_minus_1 + 1) - (pdst - pdst_mark)); |
| if (length > hdist) { |
| length -= hdist; |
| hlen = hdist; |
| } else { |
| hlen = length; |
| length = 0; |
| } |
| if (self->private_impl.f_history_index < hdist) { |
| status = wuffs_base__make_status(wuffs_deflate__error__bad_distance); |
| goto end; |
| } |
| |
| // Copy up to the right edge of the f_history array. |
| uint32_t history_index = |
| (self->private_impl.f_history_index - hdist) & 0x7FFF; |
| uint32_t available = 0x8000 - history_index; |
| uint32_t n_copied = (hlen < available) ? hlen : available; |
| memmove(pdst, self->private_data.f_history + history_index, n_copied); |
| pdst += n_copied; |
| |
| // Copy from the left edge of the f_history array. |
| if (hlen > n_copied) { |
| hlen -= n_copied; |
| memmove(pdst, self->private_data.f_history, hlen); |
| pdst += hlen; |
| } |
| |
| if (length == 0) { |
| goto outer_loop; |
| } |
| |
| if ((ptrdiff_t)(dist_minus_1 + 1) > (pdst - pdst_mark)) { |
| status = wuffs_base__make_status( |
| wuffs_deflate__error__internal_error_inconsistent_distance); |
| goto end; |
| } |
| } |
| |
| uint8_t* pback = pdst - (dist_minus_1 + 1); |
| |
| #if defined(WUFFS_DEFLATE__HAVE_64_BIT_UNALIGNED_LITTLE_ENDIAN_LOADS) |
| // Back-copy fast path, copying 8 instead of 1 bytes at a time. |
| // |
| // This always copies 8*N bytes (where N is the smallest integer such that |
| // 8*N >= length, i.e. we round length up to a multiple of 8), instead of |
| // only length bytes, but that's OK, as subsequent iterations will fix up |
| // the overrun. |
| if (dist_minus_1 + 1 >= 8) { |
| while (1) { |
| memcpy(pdst, pback, 8); |
| if (length <= 8) { |
| pdst += length; |
| break; |
| } |
| pdst += 8; |
| pback += 8; |
| length -= 8; |
| } |
| continue; |
| } |
| #endif |
| |
| // Back-copy slow path. |
| for (; length >= 3; length -= 3) { |
| *pdst++ = *pback++; |
| *pdst++ = *pback++; |
| *pdst++ = *pback++; |
| } |
| for (; length; length--) { |
| *pdst++ = *pback++; |
| } |
| } |
| |
| end: |
| // Return unused input bytes. |
| for (; n_bits >= 8; n_bits -= 8) { |
| psrc--; |
| } |
| bits &= MASK(n_bits); |
| |
| // Save contextual state. |
| a_dst->meta.wi = pdst - a_dst->data.ptr; |
| a_src->meta.ri = psrc - a_src->data.ptr; |
| self->private_impl.f_bits = bits; |
| self->private_impl.f_n_bits = n_bits; |
| |
| return status; |
| } |