diff options
author | Zoltan Szabadka <szabadka@google.com> | 2013-10-11 10:26:07 +0200 |
---|---|---|
committer | Zoltan Szabadka <szabadka@google.com> | 2013-10-11 10:26:07 +0200 |
commit | 8f30907d0f2ef354c2b31bdee340c2b11dda0fb0 (patch) | |
tree | de7a7814cb21629378206ae6784c1f15d1af0fa6 | |
download | brotli-8f30907d0f2ef354c2b31bdee340c2b11dda0fb0.zip brotli-8f30907d0f2ef354c2b31bdee340c2b11dda0fb0.tar.gz brotli-8f30907d0f2ef354c2b31bdee340c2b11dda0fb0.tar.bz2 |
Add brotli decompressor
This commit is for the decoder for brotli compression format.
Brotli is a generic byte-level compression algorithm.
-rw-r--r-- | LICENSE | 202 | ||||
-rw-r--r-- | dec/README | 3 | ||||
-rw-r--r-- | dec/bit_reader.c | 122 | ||||
-rw-r--r-- | dec/bit_reader.h | 67 | ||||
-rw-r--r-- | dec/context.h | 124 | ||||
-rw-r--r-- | dec/decode.c | 788 | ||||
-rw-r--r-- | dec/decode.h | 46 | ||||
-rw-r--r-- | dec/huffman.c | 299 | ||||
-rw-r--r-- | dec/huffman.h | 91 | ||||
-rw-r--r-- | dec/prefix.h | 68 | ||||
-rw-r--r-- | dec/safe_malloc.c | 41 | ||||
-rw-r--r-- | dec/safe_malloc.h | 43 | ||||
-rw-r--r-- | dec/types.h | 41 |
13 files changed, 1935 insertions, 0 deletions
@@ -0,0 +1,202 @@ + + 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/dec/README b/dec/README new file mode 100644 index 0000000..933bdfd --- /dev/null +++ b/dec/README @@ -0,0 +1,3 @@ +This directory holds the decoder for brotli compression format. + +Brotli is proposed to be used at the byte-compression level in WOFF 2.0 format. diff --git a/dec/bit_reader.c b/dec/bit_reader.c new file mode 100644 index 0000000..858afcb --- /dev/null +++ b/dec/bit_reader.c @@ -0,0 +1,122 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Bit reading helpers + +#include <assert.h> + +#include "./bit_reader.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +#define MAX_NUM_BIT_READ 25 + +#define LBITS 64 // Number of bits prefetched. +#define WBITS 32 // Minimum number of bytes needed after + // BrotliFillBitWindow. +#define LOG8_WBITS 4 // Number of bytes needed to store WBITS bits. + +static const uint32_t kBitMask[MAX_NUM_BIT_READ] = { + 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, + 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215 +}; + +void BrotliInitBitReader(BrotliBitReader* const br, + const uint8_t* const start, + size_t length) { + size_t i; + assert(br != NULL); + assert(start != NULL); + assert(length < 0xfffffff8u); // can't happen with a RIFF chunk. + + br->buf_ = start; + br->len_ = length; + br->val_ = 0; + br->pos_ = 0; + br->bit_pos_ = 0; + br->eos_ = 0; + br->error_ = 0; + for (i = 0; i < sizeof(br->val_) && i < br->len_; ++i) { + br->val_ |= ((uint64_t)br->buf_[br->pos_]) << (8 * i); + ++br->pos_; + } +} + +void BrotliBitReaderSetBuffer(BrotliBitReader* const br, + const uint8_t* const buf, size_t len) { + assert(br != NULL); + assert(buf != NULL); + assert(len < 0xfffffff8u); // can't happen with a RIFF chunk. + br->eos_ = (br->pos_ >= len); + br->buf_ = buf; + br->len_ = len; +} + +// If not at EOS, reload up to LBITS byte-by-byte +static void ShiftBytes(BrotliBitReader* const br) { + while (br->bit_pos_ >= 8 && br->pos_ < br->len_) { + br->val_ >>= 8; + br->val_ |= ((uint64_t)br->buf_[br->pos_]) << (LBITS - 8); + ++br->pos_; + br->bit_pos_ -= 8; + } +} + +void BrotliFillBitWindow(BrotliBitReader* const br) { + if (br->bit_pos_ >= WBITS) { +#if (defined(__x86_64__) || defined(_M_X64)) + if (br->pos_ + sizeof(br->val_) < br->len_) { + br->val_ >>= WBITS; + br->bit_pos_ -= WBITS; + // The expression below needs a little-endian arch to work correctly. + // This gives a large speedup for decoding speed. + br->val_ |= *(const uint64_t*)(br->buf_ + br->pos_) << (LBITS - WBITS); + br->pos_ += LOG8_WBITS; + return; + } +#endif + ShiftBytes(br); // Slow path. + if (br->pos_ == br->len_ && br->bit_pos_ == LBITS) { + br->eos_ = 1; + } + } +} + +uint32_t BrotliReadBits(BrotliBitReader* const br, int n_bits) { + assert(n_bits >= 0); + // Flag an error if end_of_stream or n_bits is more than allowed limit. + if (n_bits == 0 || (!br->eos_ && n_bits < MAX_NUM_BIT_READ)) { + const uint32_t val = + (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits]; + const int new_bits = br->bit_pos_ + n_bits; + br->bit_pos_ = new_bits; + // If this read is going to cross the read buffer, set the eos flag. + if (br->pos_ == br->len_) { + if (new_bits >= LBITS) { + br->eos_ = 1; + } + } + ShiftBytes(br); + return val; + } else { + br->error_ = 1; + return 0; + } +} + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif diff --git a/dec/bit_reader.h b/dec/bit_reader.h new file mode 100644 index 0000000..8ee16e5 --- /dev/null +++ b/dec/bit_reader.h @@ -0,0 +1,67 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Bit reading helpers + +#ifndef BROTLI_DEC_BIT_READER_H_ +#define BROTLI_DEC_BIT_READER_H_ + +#include "./types.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +typedef struct { + uint64_t val_; // pre-fetched bits + const uint8_t* buf_; // input byte buffer + size_t len_; // buffer length + size_t pos_; // byte position in buf_ + int bit_pos_; // current bit-reading position in val_ + int eos_; // bitstream is finished + int error_; // an error occurred (buffer overflow attempt...) +} BrotliBitReader; + +void BrotliInitBitReader(BrotliBitReader* const br, + const uint8_t* const start, + size_t length); + +// Sets a new data buffer. +void BrotliBitReaderSetBuffer(BrotliBitReader* const br, + const uint8_t* const buffer, size_t length); + +// Reads the specified number of bits from Read Buffer. +// Flags an error in case end_of_stream or n_bits is more than allowed limit. +// Flags eos if this read attempt is going to cross the read buffer. +uint32_t BrotliReadBits(BrotliBitReader* const br, int n_bits); + +// Return the prefetched bits, so they can be looked up. +static BROTLI_INLINE uint32_t BrotliPrefetchBits(BrotliBitReader* const br) { + return (uint32_t)(br->val_ >> br->bit_pos_); +} + +// For jumping over a number of bits in the bit stream when accessed with +// BrotliPrefetchBits and BrotliFillBitWindow. +static BROTLI_INLINE void BrotliSetBitPos(BrotliBitReader* const br, int val) { + br->bit_pos_ = val; +} + +// Advances the Read buffer by 4 bytes to make room for reading next 32 bits. +void BrotliFillBitWindow(BrotliBitReader* const br); + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif + +#endif // BROTLI_DEC_BIT_READER_H_ diff --git a/dec/context.h b/dec/context.h new file mode 100644 index 0000000..0b1abd1 --- /dev/null +++ b/dec/context.h @@ -0,0 +1,124 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Lookup tables to map the previous one to three bytes to a context id. + +#ifndef BROTLI_DEC_CONTEXT_H_ +#define BROTLI_DEC_CONTEXT_H_ + + +#include "./types.h" + +static const int kSigned2BitContextLookup[] = { + 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, +}; + +static const int kSigned3BitContextLookup[] = { + 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, + 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, + 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, + 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, + 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, + 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, + 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, + 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, +}; + +static const int kSigned4BitContextLookup[] = { + 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, + 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, + 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, + 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 15, +}; + +enum ContextType { + CONTEXT_FULL = 0, + CONTEXT_MSB7 = 1, + CONTEXT_MSB6 = 2, + CONTEXT_MSB5 = 3, + CONTEXT_MSB4 = 4, + CONTEXT_MSB3 = 5, + CONTEXT_MSB2 = 6, + CONTEXT_MSB1 = 7, + CONTEXT_IS_ZERO = 8, + CONTEXT_SIGNED_2BIT = 9, + CONTEXT_SIGNED_3BIT = 10, + CONTEXT_SIGNED_4BIT = 11, + CONTEXT_SIGNED_MIXED_3BYTE = 12, +}; + +static const int kContextSize[] = { + 256, 128, 64, 32, 16, 8, 4, 2, 2, 4, 8, 16, 64, +}; + +static BROTLI_INLINE int NumContexts(int mode) { + return kContextSize[mode]; +} + +static BROTLI_INLINE uint8_t Context(uint8_t prev_byte, uint8_t prev_byte2, + uint8_t prev_byte3, int mode) { + switch (mode) { + case CONTEXT_IS_ZERO: + return prev_byte == 0 ? 0 : 1; + case CONTEXT_SIGNED_2BIT: + return kSigned2BitContextLookup[prev_byte]; + case CONTEXT_SIGNED_3BIT: + return kSigned3BitContextLookup[prev_byte]; + case CONTEXT_SIGNED_4BIT: + return kSigned4BitContextLookup[prev_byte]; + case CONTEXT_SIGNED_MIXED_3BYTE: + return ((kSigned3BitContextLookup[prev_byte] << 3) + + (kSigned2BitContextLookup[prev_byte2] << 1) + + (prev_byte3 == 0 ? 0 : 1)); + default: + return prev_byte >> mode; + } +} + +#endif // BROTLI_DEC_CONTEXT_H_ diff --git a/dec/decode.c b/dec/decode.c new file mode 100644 index 0000000..85f906a --- /dev/null +++ b/dec/decode.c @@ -0,0 +1,788 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include "./bit_reader.h" +#include "./context.h" +#include "./decode.h" +#include "./huffman.h" +#include "./prefix.h" +#include "./safe_malloc.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +#ifdef BROTLI_DECODE_DEBUG +#define BROTLI_LOG_UINT(name) \ + printf("[%s] %s = %zd\n", __func__, #name, (size_t)name) +#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \ + printf("[%s] %s[%zd] = %zd\n", __func__, #array_name, \ + (size_t)idx, (size_t)array_name[idx]) +#else +#define BROTLI_LOG_UINT(name) +#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) +#endif + +static const int kDefaultCodeLength = 8; +static const int kCodeLengthLiterals = 16; +static const int kCodeLengthRepeatCode = 16; +static const int kCodeLengthExtraBits[3] = { 2, 3, 7 }; +static const int kCodeLengthRepeatOffsets[3] = { 3, 3, 11 }; + +static const int kNumLiteralCodes = 256; +static const int kNumInsertAndCopyCodes = 704; +static const int kNumBlockLengthCodes = 26; + +#define CODE_LENGTH_CODES 19 +static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = { + 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 +}; + +#define NUM_DISTANCE_SHORT_CODES 16 +static const int kDistanceShortCodeIndexOffset[NUM_DISTANCE_SHORT_CODES] = { + 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 +}; + +static const int kDistanceShortCodeValueOffset[NUM_DISTANCE_SHORT_CODES] = { + 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 +}; + +static int DecodeSize(BrotliBitReader* br, size_t* len) { + int size_bytes = BrotliReadBits(br, 3); + *len = 0; + int i = 0; + for (; i < size_bytes; ++i) { + *len |= BrotliReadBits(br, 8) << (i * 8); + } + return !br->error_; +} + +static int DecodeMetaBlockLength(int input_size_bits, + size_t remaining_length, + BrotliBitReader* br, + size_t* meta_block_length) { + if (BrotliReadBits(br, 1)) { + *meta_block_length = remaining_length; + return 1; + } + *meta_block_length = 0; + int shift = 0; + while (input_size_bits > 0) { + *meta_block_length |= BrotliReadBits(br, 8) << shift; + input_size_bits -= 8; + shift += 8; + } + if (input_size_bits > 0) { + *meta_block_length |= BrotliReadBits(br, input_size_bits) << shift; + } + ++(*meta_block_length); + return !br->error_; +} + +// Decodes the next Huffman code from bit-stream. +// FillBitWindow(br) needs to be called at minimum every second call +// to ReadSymbol, in order to pre-fetch enough bits. +static BROTLI_INLINE int ReadSymbol(const HuffmanTree* tree, + BrotliBitReader* br) { + if (tree->fixed_bit_length_ > 0) { + return BrotliReadBits(br, tree->fixed_bit_length_); + } + const HuffmanTreeNode* node = tree->root_; + uint32_t bits = BrotliPrefetchBits(br); + int bitpos = br->bit_pos_; + // Check if we find the bit combination from the Huffman lookup table. + const int lut_ix = bits & (HUFF_LUT - 1); + const int lut_bits = tree->lut_bits_[lut_ix]; + if (lut_bits <= HUFF_LUT_BITS) { + BrotliSetBitPos(br, bitpos + lut_bits); + return tree->lut_symbol_[lut_ix]; + } + node += tree->lut_jump_[lut_ix]; + bitpos += HUFF_LUT_BITS; + bits >>= HUFF_LUT_BITS; + + // Decode the value from a binary tree. + assert(node != NULL); + do { + node = HuffmanTreeNextNode(node, bits & 1); + bits >>= 1; + ++bitpos; + } while (HuffmanTreeNodeIsNotLeaf(node)); + BrotliSetBitPos(br, bitpos); + return node->symbol_; +} + +static void PrintIntVector(const int* v, int len) { + while (len-- > 0) printf(" %d", *v++); + printf("\n"); +} + +static int ReadHuffmanCodeLengths( + const int* code_length_code_lengths, + int num_symbols, int* code_lengths, + BrotliBitReader* br) { + int ok = 0; + int symbol; + int max_symbol; + int prev_code_len = kDefaultCodeLength; + HuffmanTree tree; + + if (!HuffmanTreeBuildImplicit(&tree, code_length_code_lengths, + CODE_LENGTH_CODES)) { + printf("[ReadHuffmanCodeLengths] Building code length tree failed: "); + PrintIntVector(code_length_code_lengths, CODE_LENGTH_CODES); + return 0; + } + + int use_length = BrotliReadBits(br, 1); + BROTLI_LOG_UINT(use_length); + if (use_length) { + const int length_nbits = 2 + 2 * BrotliReadBits(br, 3); + max_symbol = 2 + BrotliReadBits(br, length_nbits); + BROTLI_LOG_UINT(length_nbits); + if (max_symbol > num_symbols) { + printf("[ReadHuffmanCodeLengths] max_symbol > num_symbols (%d vs %d)\n", + max_symbol, num_symbols); + goto End; + } + } else { + max_symbol = num_symbols; + } + BROTLI_LOG_UINT(max_symbol); + + symbol = 0; + while (symbol < num_symbols) { + int code_len; + if (max_symbol-- == 0) break; + BrotliFillBitWindow(br); + code_len = ReadSymbol(&tree, br); + BROTLI_LOG_UINT(symbol); + BROTLI_LOG_UINT(code_len); + if (code_len < kCodeLengthLiterals) { + code_lengths[symbol++] = code_len; + if (code_len != 0) prev_code_len = code_len; + } else { + const int use_prev = (code_len == kCodeLengthRepeatCode); + const int slot = code_len - kCodeLengthLiterals; + const int extra_bits = kCodeLengthExtraBits[slot]; + const int repeat_offset = kCodeLengthRepeatOffsets[slot]; + const int length = use_prev ? prev_code_len : 0; + int repeat = BrotliReadBits(br, extra_bits) + repeat_offset; + BROTLI_LOG_UINT(repeat); + BROTLI_LOG_UINT(length); + if (symbol + repeat > num_symbols) { + printf("[ReadHuffmanCodeLengths] symbol + repeat > num_symbols " + "(%d + %d vs %d)\n", symbol, repeat, num_symbols); + goto End; + } else { + while (repeat-- > 0) { + code_lengths[symbol++] = length; + } + } + } + } + while (symbol < num_symbols) code_lengths[symbol++] = 0; + ok = 1; + + End: + HuffmanTreeRelease(&tree); + return ok; +} + +static const int64_t kUnitInterval = 1LL<<30; + +static int RepairHuffmanCodeLengths(int num_symbols, int* code_lengths) { + int i; + int64_t space = kUnitInterval; + int max_length = 0; + for(i = 0; i < num_symbols; i++) + if (code_lengths[i] != 0) { + if (code_lengths[i] > max_length) + max_length = code_lengths[i]; + space -= kUnitInterval >> code_lengths[i]; + } + // The code which contains one symbol of length one cannot be made optimal. + if (max_length == 1) + return 1; + if (space < 0) { + int count_longest = 0; + for(i = 0; i < num_symbols; i++) { + if (code_lengths[i] == max_length) + count_longest++; + } + // Substitute all longest codes with sufficiently longer ones, so that all + // code words fit into the unit interval. Leftover space will be + // redistributed later. + space += count_longest * (kUnitInterval >> max_length); + if (space < 0) + return 0; + int new_length = max_length; + while (space < count_longest * (kUnitInterval >> new_length)) + new_length++; + space -= count_longest * (kUnitInterval >> new_length); + for(i = 0; i < num_symbols; i++) { + if (code_lengths[i] == max_length) + code_lengths[i] = new_length; + } + } + + while (space > 0) { + // Redistribute leftover space in an approximation of a uniform fashion. + for(i = 0; i < num_symbols; i++) { + if (code_lengths[i] > 1 && space >= (kUnitInterval >> code_lengths[i])) { + space -= kUnitInterval >> code_lengths[i]; + code_lengths[i]--; + } + if (space == 0) + break; + } + } + return 1; +} + +static int ReadHuffmanCode(int alphabet_size, + HuffmanTree* tree, + BrotliBitReader* br) { + int ok = 0; + const int simple_code = BrotliReadBits(br, 1); + BROTLI_LOG_UINT(simple_code); + + if (simple_code) { // Read symbols, codes & code lengths directly. + int symbols[2] = { 0 }; + int codes[2]; + int code_lengths[2]; + const int num_symbols = BrotliReadBits(br, 1) + 1; + const int first_symbol_len_code = BrotliReadBits(br, 1); + // The first code is either 1 bit or 8 bit code. + symbols[0] = BrotliReadBits(br, (first_symbol_len_code == 0) ? 1 : 8); + codes[0] = 0; + code_lengths[0] = num_symbols - 1; + // The second code (if present), is always 8 bit long. + if (num_symbols == 2) { + symbols[1] = BrotliReadBits(br, 8); + codes[1] = 1; + code_lengths[1] = num_symbols - 1; + } + BROTLI_LOG_UINT(num_symbols); + BROTLI_LOG_UINT(first_symbol_len_code); + BROTLI_LOG_UINT(symbols[0]); + BROTLI_LOG_UINT(symbols[1]); + ok = HuffmanTreeBuildExplicit(tree, code_lengths, codes, symbols, + alphabet_size, num_symbols); + if (!ok) { + printf("[ReadHuffmanCode] HuffmanTreeBuildExplicit failed: "); + PrintIntVector(code_lengths, num_symbols); + } + } else { // Decode Huffman-coded code lengths. + int* code_lengths = NULL; + int i; + int code_length_code_lengths[CODE_LENGTH_CODES] = { 0 }; + const int num_codes = BrotliReadBits(br, 4) + 4; + BROTLI_LOG_UINT(num_codes); + if (num_codes > CODE_LENGTH_CODES) { + return 0; + } + + code_lengths = + (int*)BrotliSafeMalloc((uint64_t)alphabet_size, sizeof(*code_lengths)); + if (code_lengths == NULL) { + return 0; + } + + for (i = 0; i < num_codes; ++i) { + int code_len_idx = kCodeLengthCodeOrder[i]; + code_length_code_lengths[code_len_idx] = BrotliReadBits(br, 3); + BROTLI_LOG_ARRAY_INDEX(code_length_code_lengths, code_len_idx); + } + ok = ReadHuffmanCodeLengths(code_length_code_lengths, alphabet_size, + code_lengths, br) && + RepairHuffmanCodeLengths(alphabet_size, code_lengths); + if (ok) { + ok = HuffmanTreeBuildImplicit(tree, code_lengths, alphabet_size); + if (!ok) { + printf("[ReadHuffmanCode] HuffmanTreeBuildImplicit failed: "); + PrintIntVector(code_lengths, alphabet_size); + } + } + free(code_lengths); + } + ok = ok && !br->error_; + if (!ok) { + return 0; + } + return 1; +} + +static int ReadCopyDistance(const HuffmanTree* tree, + int num_direct_codes, + int postfix_bits, + uint32_t postfix_mask, + BrotliBitReader* br) { + BrotliFillBitWindow(br); + int code = ReadSymbol(tree, br); + if (code < num_direct_codes) { + return code; + } + code -= num_direct_codes; + int postfix = code & postfix_mask; + code >>= postfix_bits; + int nbits = (code >> 1) + 1; + int offset = ((2 + (code & 1)) << nbits) - 4; + return (num_direct_codes + + ((offset + BrotliReadBits(br, nbits)) << postfix_bits) + + postfix); +} + +static int ReadBlockLength(const HuffmanTree* tree, BrotliBitReader* br) { + BrotliFillBitWindow(br); + int code = ReadSymbol(tree, br); + int nbits = kBlockLengthPrefixCode[code].nbits; + return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits); +} + +static void ReadInsertAndCopy(const HuffmanTree* tree, + int* insert_len, + int* copy_len, + int* copy_dist, + BrotliBitReader* br) { + BrotliFillBitWindow(br); + int code = ReadSymbol(tree, br); + int range_idx = code >> 6; + if (range_idx >= 2) { + range_idx -= 2; + *copy_dist = -1; + } else { + *copy_dist = 0; + } + int insert_code = (kInsertRangeLut[range_idx] << 3) + ((code >> 3) & 7); + int copy_code = (kCopyRangeLut[range_idx] << 3) + (code & 7); + *insert_len = + kInsertLengthPrefixCode[insert_code].offset + + BrotliReadBits(br, kInsertLengthPrefixCode[insert_code].nbits); + *copy_len = + kCopyLengthPrefixCode[copy_code].offset + + BrotliReadBits(br, kCopyLengthPrefixCode[copy_code].nbits); +} + +static int TranslateShortCodes(int code, int* ringbuffer, size_t* index) { + int val; + if (code < NUM_DISTANCE_SHORT_CODES) { + val = code; + int index_offset = kDistanceShortCodeIndexOffset[val]; + int value_offset = kDistanceShortCodeValueOffset[val]; + val = ringbuffer[(*index + index_offset) & 3] + value_offset; + } else { + val = code - NUM_DISTANCE_SHORT_CODES + 1; + } + if (code > 0) { + ringbuffer[*index & 3] = val; + ++(*index); + } + return val; +} + +static void MoveToFront(uint8_t* v, uint8_t index) { + uint8_t value = v[index]; + uint8_t i = index; + for (; i; --i) v[i] = v[i - 1]; + v[0] = value; +} + +static void InverseMoveToFrontTransform(uint8_t* v, int v_len) { + uint8_t mtf[256]; + int i; + for (i = 0; i < 256; ++i) { + mtf[i] = i; + } + for (i = 0; i < v_len; ++i) { + uint8_t index = v[i]; + v[i] = mtf[index]; + if (index) MoveToFront(mtf, index); + } +} + +// Contains a collection of huffman trees with the same alphabet size. +typedef struct { + int alphabet_size; + int num_htrees; + HuffmanTree* htrees; +} HuffmanTreeGroup; + +void HuffmanTreeGroupInit(HuffmanTreeGroup* group, int alphabet_size, + int ntrees) { + group->alphabet_size = alphabet_size; + group->num_htrees = ntrees; + group->htrees = (HuffmanTree*)malloc(sizeof(HuffmanTree) * ntrees); +} + +void HuffmanTreeGroupRelease(HuffmanTreeGroup* group) { + int i; + for (i = 0; i < group->num_htrees; ++i) { + HuffmanTreeRelease(&group->htrees[i]); + } + free(group->htrees); +} + +int HuffmanTreeGroupDecode(HuffmanTreeGroup* group, BrotliBitReader* br) { + int i; + for (i = 0; i < group->num_htrees; ++i) { + ReadHuffmanCode(group->alphabet_size, &group->htrees[i], br); + } + return 1; +} + +int DecodeContextMap(int num_block_types, + int stream_type, + int* context_mode, + int* contexts_per_block, + int* num_htrees, + uint8_t** context_map, + BrotliBitReader* br) { + int use_context = BrotliReadBits(br, 1); + if (!use_context) { + *context_mode = 0; + *contexts_per_block = 1; + *context_map = NULL; + *num_htrees = num_block_types; + return 1; + } + switch (stream_type) { + case 0: + *context_mode = BrotliReadBits(br, 4); + *contexts_per_block = NumContexts(*context_mode); + break; + case 2: + *context_mode = 1; + *contexts_per_block = 4; + break; + } + int context_map_size = *contexts_per_block * num_block_types; + *num_htrees = BrotliReadBits(br, 8) + 1; + + BROTLI_LOG_UINT(*context_mode); + BROTLI_LOG_UINT(context_map_size); + BROTLI_LOG_UINT(*num_htrees); + + *context_map = (uint8_t*)malloc(context_map_size); + if (*num_htrees <= 1) { + memset(*context_map, 0, context_map_size); + return 1; + } + + int i; + if (*num_htrees == context_map_size) { + for (i = 0; i < context_map_size; ++i) { + (*context_map)[i] = i; + } + return 1; + } + int use_rle_for_zeros = BrotliReadBits(br, 1); + int max_run_length_prefix = 0; + if (use_rle_for_zeros) { + max_run_length_prefix = BrotliReadBits(br, 4) + 1; + } + HuffmanTree tree_index_htree; + ReadHuffmanCode(*num_htrees + max_run_length_prefix, + &tree_index_htree, br); + if (use_rle_for_zeros) { + for (i = 0; i < context_map_size;) { + BrotliFillBitWindow(br); + int code = ReadSymbol(&tree_index_htree, br); + if (code == 0) { + (*context_map)[i] = 0; + ++i; + } else if (code <= max_run_length_prefix) { + int reps = 1 + (1 << code) + BrotliReadBits(br, code); + while (--reps) { + (*context_map)[i] = 0; + ++i; + } + } else { + (*context_map)[i] = code - max_run_length_prefix; + ++i; + } + } + } else { + for (i = 0; i < context_map_size; ++i) { + BrotliFillBitWindow(br); + (*context_map)[i] = ReadSymbol(&tree_index_htree, br); + } + } + HuffmanTreeRelease(&tree_index_htree); + if (BrotliReadBits(br, 1)) { + InverseMoveToFrontTransform(*context_map, context_map_size); + } + return 1; +} + +static BROTLI_INLINE void DecodeBlockType(const HuffmanTree* trees, + int tree_type, + int* block_types, + int* ringbuffers, + size_t* indexes, + BrotliBitReader* br) { + int* ringbuffer = ringbuffers + tree_type * 2; + size_t* index = indexes + tree_type; + int type_code = ReadSymbol(trees + tree_type, br); + int block_type; + if (type_code == 0) { + block_type = ringbuffer[*index & 1]; + } else if (type_code == 1) { + block_type = ringbuffer[(*index - 1) & 1] + 1; + } else { + block_type = type_code - 2; + } + block_types[tree_type] = block_type; + ringbuffer[(*index) & 1] = block_type; + ++(*index); +} + +int BrotliDecompressedSize(size_t encoded_size, + const uint8_t* encoded_buffer, + size_t* decoded_size) { + BrotliBitReader br; + BrotliInitBitReader(&br, encoded_buffer, encoded_size); + return DecodeSize(&br, decoded_size); +} + +int BrotliDecompressBuffer(size_t encoded_size, + const uint8_t* encoded_buffer, + size_t* decoded_size, + uint8_t* decoded_buffer) { + BrotliBitReader br; + BrotliInitBitReader(&br, encoded_buffer, encoded_size); + + int ok = DecodeSize(&br, decoded_size); + if (!ok) return 0; + + if (*decoded_size == 0) { + return 1; + } + size_t n = *decoded_size; + int input_size_bits = (n == (n &~ (n - 1))) ? -1 : 0; + while (n) { + ++input_size_bits; + n >>= 1; + } + + BROTLI_LOG_UINT(*decoded_size); + BROTLI_LOG_UINT(input_size_bits); + + int i; + size_t pos = 0; + const size_t end = *decoded_size; + uint8_t* data = decoded_buffer; + // This ring buffer holds a few past copy distances that will be used by + // some special distance codes. + int dist_rb[4] = { 4, 11, 15, 16 }; + size_t dist_rb_idx = 0; + HuffmanTreeGroup hgroup[3]; + + while (pos < end && ok) { + BROTLI_LOG_UINT(pos); + size_t meta_block_len = 0; + if (!DecodeMetaBlockLength(input_size_bits, end - pos, + &br, &meta_block_len)) { + printf("Could not decode meta-block length.\n"); + ok = 0; + goto End; + } + BROTLI_LOG_UINT(meta_block_len); + size_t meta_block_end = pos + meta_block_len; + size_t block_length[3] = { 0 }; + int block_type[3] = { 0 }; + int num_block_types[3] = { 0 }; + int block_type_rb[6] = { 0, 1, 0, 1, 0, 1 }; + size_t block_type_rb_index[3] = { 0 }; + HuffmanTree block_type_trees[3]; + HuffmanTree block_len_trees[3]; + for (i = 0; i < 3; ++i) { + block_type_trees[i].root_ = NULL; + block_len_trees[i].root_ = NULL; + if (BrotliReadBits(&br, 1)) { + num_block_types[i] = BrotliReadBits(&br, 8) + 1; + ReadHuffmanCode(num_block_types[i] + 2, &block_type_trees[i], &br); + ReadHuffmanCode(kNumBlockLengthCodes, &block_len_trees[i], &br); + block_length[i] = ReadBlockLength(&block_len_trees[i], &br); + block_type_rb_index[i] = 1; + } else { + num_block_types[i] = 1; + block_length[i] = meta_block_len; + } + } + + BROTLI_LOG_UINT(num_block_types[0]); + BROTLI_LOG_UINT(num_block_types[1]); + BROTLI_LOG_UINT(num_block_types[2]); + BROTLI_LOG_UINT(block_length[0]); + BROTLI_LOG_UINT(block_length[1]); + BROTLI_LOG_UINT(block_length[2]); + + int distance_postfix_bits = BrotliReadBits(&br, 2); + int num_direct_distance_codes = + NUM_DISTANCE_SHORT_CODES + + (BrotliReadBits(&br, 4) << distance_postfix_bits); + uint32_t distance_postfix_mask = (1 << distance_postfix_bits) - 1; + int num_distance_codes = (num_direct_distance_codes + + (48 << distance_postfix_bits)); + BROTLI_LOG_UINT(num_direct_distance_codes); + BROTLI_LOG_UINT(distance_postfix_bits); + + uint8_t* context_map; + int context_mode; + int contexts_per_block; + int num_literal_htrees; + DecodeContextMap(num_block_types[0], 0, &context_mode, &contexts_per_block, + &num_literal_htrees, &context_map, &br); + + uint8_t* dist_context_map; + int dist_context_mode; + int dist_contexts_per_block; + int num_dist_htrees; + DecodeContextMap(num_block_types[2], 2, &dist_context_mode, + &dist_contexts_per_block, + &num_dist_htrees, &dist_context_map, &br); + + HuffmanTreeGroupInit(&hgroup[0], kNumLiteralCodes, num_literal_htrees); + HuffmanTreeGroupInit(&hgroup[1], kNumInsertAndCopyCodes, + num_block_types[1]); + HuffmanTreeGroupInit(&hgroup[2], num_distance_codes, num_dist_htrees); + + for (i = 0; i < 3; ++i) { + HuffmanTreeGroupDecode(&hgroup[i], &br); + } + + HuffmanTree* literal_htrees = hgroup[0].htrees; + int context_offset = 0; + uint8_t* context_map_slice = context_map; + uint8_t literal_htree_index = 0; + int dist_context_offset = 0; + uint8_t* dist_context_map_slice = dist_context_map; + uint8_t dist_htree_index = 0; + + while (pos < meta_block_end) { + if (block_length[1] == 0) { + DecodeBlockType(block_type_trees, 1, block_type, block_type_rb, + block_type_rb_index, &br); + block_length[1] = ReadBlockLength(&block_len_trees[1], &br); + } + --block_length[1]; + int insert_length; + int copy_length; + int distance_code; + ReadInsertAndCopy(&hgroup[1].htrees[block_type[1]], + &insert_length, ©_length, &distance_code, &br); + BROTLI_LOG_UINT(insert_length); + BROTLI_LOG_UINT(copy_length); + BROTLI_LOG_UINT(distance_code); + int j; + for (j = 0; j < insert_length; ++j) { + if (block_length[0] == 0) { + DecodeBlockType(block_type_trees, 0, block_type, block_type_rb, + block_type_rb_index, &br); + block_length[0] = ReadBlockLength(&block_len_trees[0], &br); + literal_htree_index = block_type[0]; + context_offset = block_type[0] * contexts_per_block; + context_map_slice = context_map + context_offset; + } + --block_length[0]; + BrotliFillBitWindow(&br); + // Figure out htree + if (contexts_per_block > 1) { + uint8_t prev_byte = pos > 0 ? data[pos - 1] : 0; + uint8_t prev_byte2 = pos > 1 ? data[pos - 2] : 0; + uint8_t prev_byte3 = pos > 2 ? data[pos - 3] : 0; + uint8_t context = Context(prev_byte, prev_byte2, prev_byte3, + context_mode); + BROTLI_LOG_UINT(context); + literal_htree_index = context_map_slice[context]; + } + data[pos] = ReadSymbol(&literal_htrees[literal_htree_index], &br); + BROTLI_LOG_UINT(literal_htree_index); + BROTLI_LOG_ARRAY_INDEX(data, pos); + ++pos; + } + if (br.error_) { + printf("Read error after decoding literal sequence.\n"); + ok = 0; + goto End; + } + + if (pos == meta_block_end) break; + + if (distance_code < 0) { + if (block_length[2] == 0) { + DecodeBlockType(block_type_trees, 2, block_type, block_type_rb, + block_type_rb_index, &br); + block_length[2] = ReadBlockLength(&block_len_trees[2], &br); + dist_htree_index = block_type[2]; + dist_context_offset = block_type[2] * dist_contexts_per_block; + dist_context_map_slice = dist_context_map + dist_context_offset; + } + --block_length[2]; + if (dist_contexts_per_block > 1) { + uint8_t context = copy_length > 4 ? 3 : copy_length - 2; + dist_htree_index = dist_context_map_slice[context]; + } + distance_code = ReadCopyDistance(&hgroup[2].htrees[dist_htree_index], + num_direct_distance_codes, + distance_postfix_bits, + distance_postfix_mask, + &br); + if (br.error_) { + printf("Could not read copy distance.\n"); + ok = 0; + goto End; + } + } + + // Convert the distance code to the actual distance by possibly looking + // up past distnaces from the ringbuffer. + int dist = TranslateShortCodes(distance_code, dist_rb, &dist_rb_idx); + BROTLI_LOG_UINT(dist); + + // Do the actual copy if it is valid. + if (pos >= dist && pos + copy_length <= end) { + int j; + for (j = 0; j < copy_length; ++j) { + data[pos + j] = data[pos + j - dist]; + } + pos += copy_length; + } else { + printf("Invalid backward reference. pos: %zd dist: %d " + "len: %d end:%zd\n", + pos, dist, copy_length, end); + ok = 0; + goto End; + } + } + End: + free(context_map); + free(dist_context_map); + for (i = 0; i < 3; ++i) { + HuffmanTreeGroupRelease(&hgroup[i]); + HuffmanTreeRelease(&block_type_trees[i]); + HuffmanTreeRelease(&block_len_trees[i]); + } + } + + return ok; +} + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif diff --git a/dec/decode.h b/dec/decode.h new file mode 100644 index 0000000..6d63e3a --- /dev/null +++ b/dec/decode.h @@ -0,0 +1,46 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// API for Brotli decompression + +#ifndef BROTLI_DEC_DECODE_H_ +#define BROTLI_DEC_DECODE_H_ + +#include "./types.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +// Sets *decoded_size to the decompressed size of the given encoded stream. +// Returns 1 on success, 0 on failure. +int BrotliDecompressedSize(size_t encoded_size, + const uint8_t* encoded_buffer, + size_t* decoded_size); + +// Decompresses the data in encoded_buffer into decoded_buffer, and sets +// *decoded_size to the decompressed length. +// Returns 0 if there was either a bit stream error or memory allocation error, +// and 1 otherwise. +// If decoded size is zero, returns 1 and keeps decoded_buffer unchanged. +int BrotliDecompressBuffer(size_t encoded_size, + const uint8_t* encoded_buffer, + size_t* decoded_size, + uint8_t* decoded_buffer); + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif + +#endif // BROTLI_DEC_DECODE_H_ diff --git a/dec/huffman.c b/dec/huffman.c new file mode 100644 index 0000000..5f37df4 --- /dev/null +++ b/dec/huffman.c @@ -0,0 +1,299 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Utilities for building and looking up Huffman trees. + +#include <assert.h> +#include <stdlib.h> +#include <string.h> +#include "./huffman.h" +#include "./safe_malloc.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +// Uncomment the following to use look-up table for ReverseBits() +// (might be faster on some platform) +// #define USE_LUT_REVERSE_BITS + +#define NON_EXISTENT_SYMBOL (-1) +#define MAX_ALLOWED_CODE_LENGTH 15 + +static void TreeNodeInit(HuffmanTreeNode* const node) { + node->children_ = -1; // means: 'unassigned so far' +} + +static int NodeIsEmpty(const HuffmanTreeNode* const node) { + return (node->children_ < 0); +} + +static int IsFull(const HuffmanTree* const tree) { + return (tree->num_nodes_ == tree->max_nodes_); +} + +static void AssignChildren(HuffmanTree* const tree, + HuffmanTreeNode* const node) { + HuffmanTreeNode* const children = tree->root_ + tree->num_nodes_; + node->children_ = (int)(children - node); + assert(children - node == (int)(children - node)); + tree->num_nodes_ += 2; + TreeNodeInit(children + 0); + TreeNodeInit(children + 1); +} + +static int TreeInit(HuffmanTree* const tree, int num_leaves) { + assert(tree != NULL); + tree->fixed_bit_length_ = 0; + if (num_leaves == 0) return 0; + // We allocate maximum possible nodes in the tree at once. + // Note that a Huffman tree is a full binary tree; and in a full binary tree + // with L leaves, the total number of nodes N = 2 * L - 1. + tree->max_nodes_ = 2 * num_leaves - 1; + assert(tree->max_nodes_ < (1 << 16)); // limit for the lut_jump_ table + tree->root_ = (HuffmanTreeNode*)BrotliSafeMalloc((uint64_t)tree->max_nodes_, + sizeof(*tree->root_)); + if (tree->root_ == NULL) return 0; + TreeNodeInit(tree->root_); // Initialize root. + tree->num_nodes_ = 1; + memset(tree->lut_bits_, 255, sizeof(tree->lut_bits_)); + memset(tree->lut_jump_, 0, sizeof(tree->lut_jump_)); + return 1; +} + +void HuffmanTreeRelease(HuffmanTree* const tree) { + if (tree != NULL) { + free(tree->root_); + tree->root_ = NULL; + tree->max_nodes_ = 0; + tree->num_nodes_ = 0; + } +} + +int HuffmanCodeLengthsToCodes(const int* const code_lengths, + int code_lengths_size, int* const huff_codes) { + int symbol; + int code_len; + int code_length_hist[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; + int curr_code; + int next_codes[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; + int max_code_length = 0; + + assert(code_lengths != NULL); + assert(code_lengths_size > 0); + assert(huff_codes != NULL); + + // Calculate max code length. + for (symbol = 0; symbol < code_lengths_size; ++symbol) { + if (code_lengths[symbol] > max_code_length) { + max_code_length = code_lengths[symbol]; + } + } + if (max_code_length > MAX_ALLOWED_CODE_LENGTH) return 0; + + // Calculate code length histogram. + for (symbol = 0; symbol < code_lengths_size; ++symbol) { + ++code_length_hist[code_lengths[symbol]]; + } + code_length_hist[0] = 0; + + // Calculate the initial values of 'next_codes' for each code length. + // next_codes[code_len] denotes the code to be assigned to the next symbol + // of code length 'code_len'. + curr_code = 0; + next_codes[0] = -1; // Unused, as code length = 0 implies code doesn't exist. + for (code_len = 1; code_len <= max_code_length; ++code_len) { + curr_code = (curr_code + code_length_hist[code_len - 1]) << 1; + next_codes[code_len] = curr_code; + } + + // Get symbols. + for (symbol = 0; symbol < code_lengths_size; ++symbol) { + if (code_lengths[symbol] > 0) { + huff_codes[symbol] = next_codes[code_lengths[symbol]]++; + } else { + huff_codes[symbol] = NON_EXISTENT_SYMBOL; + } + } + return 1; +} + +#ifndef USE_LUT_REVERSE_BITS + +static int ReverseBitsShort(int bits, int num_bits) { + int retval = 0; + int i; + assert(num_bits <= 8); // Not a hard requirement, just for coherency. + for (i = 0; i < num_bits; ++i) { + retval <<= 1; + retval |= bits & 1; + bits >>= 1; + } + return retval; +} + +#else + +static const uint8_t kReversedBits[16] = { // Pre-reversed 4-bit values. + 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, + 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf +}; + +static int ReverseBitsShort(int bits, int num_bits) { + const uint8_t v = (kReversedBits[bits & 0xf] << 4) | kReversedBits[bits >> 4]; + assert(num_bits <= 8); + return v >> (8 - num_bits); +} + +#endif + +static int TreeAddSymbol(HuffmanTree* const tree, + int symbol, int code, int code_length) { + int step = HUFF_LUT_BITS; + int base_code; + HuffmanTreeNode* node = tree->root_; + const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_; + assert(symbol == (int16_t)symbol); + if (code_length <= HUFF_LUT_BITS) { + int i; + base_code = ReverseBitsShort(code, code_length); + for (i = 0; i < (1 << (HUFF_LUT_BITS - code_length)); ++i) { + const int idx = base_code | (i << code_length); + tree->lut_symbol_[idx] = (int16_t)symbol; + tree->lut_bits_[idx] = code_length; + } + } else { + base_code = ReverseBitsShort((code >> (code_length - HUFF_LUT_BITS)), + HUFF_LUT_BITS); + } + while (code_length-- > 0) { + if (node >= max_node) { + return 0; + } + if (NodeIsEmpty(node)) { + if (IsFull(tree)) return 0; // error: too many symbols. + AssignChildren(tree, node); + } else if (!HuffmanTreeNodeIsNotLeaf(node)) { + return 0; // leaf is already occupied. + } + node += node->children_ + ((code >> code_length) & 1); + if (--step == 0) { + tree->lut_jump_[base_code] = (int16_t)(node - tree->root_); + } + } + if (NodeIsEmpty(node)) { + node->children_ = 0; // turn newly created node into a leaf. + } else if (HuffmanTreeNodeIsNotLeaf(node)) { + return 0; // trying to assign a symbol to already used code. + } + node->symbol_ = symbol; // Add symbol in this node. + return 1; +} + +int HuffmanTreeBuildImplicit(HuffmanTree* const tree, + const int* const code_lengths, + int code_lengths_size) { + int symbol; + int num_symbols = 0; + int root_symbol = 0; + + assert(tree != NULL); + assert(code_lengths != NULL); + + // Find out number of symbols and the root symbol. + for (symbol = 0; symbol < code_lengths_size; ++symbol) { + if (code_lengths[symbol] > 0) { + // Note: code length = 0 indicates non-existent symbol. + ++num_symbols; + root_symbol = symbol; + } + } + + // Initialize the tree. Will fail for num_symbols = 0 + if (!TreeInit(tree, num_symbols)) return 0; + + // Build tree. + if (num_symbols == 1) { // Trivial case. + const int max_symbol = code_lengths_size; + if (root_symbol < 0 || root_symbol >= max_symbol) { + HuffmanTreeRelease(tree); + return 0; + } + return TreeAddSymbol(tree, root_symbol, 0, 0); + } else { // Normal case. + int ok = 0; + + // Get Huffman codes from the code lengths. + int* const codes = + (int*)BrotliSafeMalloc((uint64_t)code_lengths_size, sizeof(*codes)); + if (codes == NULL) goto End; + + if (!HuffmanCodeLengthsToCodes(code_lengths, code_lengths_size, codes)) { + goto End; + } + + // Add symbols one-by-one. + for (symbol = 0; symbol < code_lengths_size; ++symbol) { + if (code_lengths[symbol] > 0) { + if (!TreeAddSymbol(tree, symbol, codes[symbol], code_lengths[symbol])) { + goto End; + } + } + } + ok = 1; + End: + free(codes); + ok = ok && IsFull(tree); + if (!ok) HuffmanTreeRelease(tree); + return ok; + } +} + +int HuffmanTreeBuildExplicit(HuffmanTree* const tree, + const int* const code_lengths, + const int* const codes, + const int* const symbols, int max_symbol, + int num_symbols) { + int ok = 0; + int i; + + assert(tree != NULL); + assert(code_lengths != NULL); + assert(codes != NULL); + assert(symbols != NULL); + + // Initialize the tree. Will fail if num_symbols = 0. + if (!TreeInit(tree, num_symbols)) return 0; + + // Add symbols one-by-one. + for (i = 0; i < num_symbols; ++i) { + if (codes[i] != NON_EXISTENT_SYMBOL) { + if (symbols[i] < 0 || symbols[i] >= max_symbol) { + goto End; + } + if (!TreeAddSymbol(tree, symbols[i], codes[i], code_lengths[i])) { + goto End; + } + } + } + ok = 1; + End: + ok = ok && IsFull(tree); + if (!ok) HuffmanTreeRelease(tree); + return ok; +} + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif diff --git a/dec/huffman.h b/dec/huffman.h new file mode 100644 index 0000000..2c21fdd --- /dev/null +++ b/dec/huffman.h @@ -0,0 +1,91 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Utilities for building and looking up Huffman trees. + +#ifndef BROTLI_DEC_HUFFMAN_H_ +#define BROTLI_DEC_HUFFMAN_H_ + +#include <assert.h> +#include "./types.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +// A node of a Huffman tree. +typedef struct { + int symbol_; + int children_; // delta offset to both children (contiguous) or 0 if leaf. +} HuffmanTreeNode; + +// Huffman Tree. +#define HUFF_LUT_BITS 7 +#define HUFF_LUT (1U << HUFF_LUT_BITS) +typedef struct HuffmanTree HuffmanTree; +struct HuffmanTree { + // Fast lookup for short bit lengths. + uint8_t lut_bits_[HUFF_LUT]; + int16_t lut_symbol_[HUFF_LUT]; + int16_t lut_jump_[HUFF_LUT]; + // Complete tree for lookups. + HuffmanTreeNode* root_; // all the nodes, starting at root. + int max_nodes_; // max number of nodes + int num_nodes_; // number of currently occupied nodes + int fixed_bit_length_; // If non-zero, uses fixed length coding +}; + +// Returns true if the given node is not a leaf of the Huffman tree. +static BROTLI_INLINE int HuffmanTreeNodeIsNotLeaf( + const HuffmanTreeNode* const node) { + return node->children_; +} + +// Go down one level. Most critical function. 'right_child' must be 0 or 1. +static BROTLI_INLINE const HuffmanTreeNode* HuffmanTreeNextNode( + const HuffmanTreeNode* node, int right_child) { + return node + node->children_ + right_child; +} + +// Releases the nodes of the Huffman tree. +// Note: It does NOT free 'tree' itself. +void HuffmanTreeRelease(HuffmanTree* const tree); + +// Builds Huffman tree assuming code lengths are implicitly in symbol order. +// Returns false in case of error (invalid tree or memory error). +int HuffmanTreeBuildImplicit(HuffmanTree* const tree, + const int* const code_lengths, + int code_lengths_size); + +// Build a Huffman tree with explicitly given lists of code lengths, codes +// and symbols. Verifies that all symbols added are smaller than max_symbol. +// Returns false in case of an invalid symbol, invalid tree or memory error. +int HuffmanTreeBuildExplicit(HuffmanTree* const tree, + const int* const code_lengths, + const int* const codes, + const int* const symbols, int max_symbol, + int num_symbols); + +// Utility: converts Huffman code lengths to corresponding Huffman codes. +// 'huff_codes' should be pre-allocated. +// Returns false in case of error (memory allocation, invalid codes). +int HuffmanCodeLengthsToCodes(const int* const code_lengths, + int code_lengths_size, int* const huff_codes); + + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif + +#endif // BROTLI_DEC_HUFFMAN_H_ diff --git a/dec/prefix.h b/dec/prefix.h new file mode 100644 index 0000000..dda01b1 --- /dev/null +++ b/dec/prefix.h @@ -0,0 +1,68 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Lookup tables to map prefix codes to value ranges. This is used during +// decoding of the block lengths, literal insertion lengths and copy lengths. + +#ifndef BROTLI_DEC_PREFIX_H_ +#define BROTLI_DEC_PREFIX_H_ + +// Represents the range of values belonging to a prefix code: +// [offset, offset + 2^nbits) +struct PrefixCodeRange { + int offset; + int nbits; +}; + +static const struct PrefixCodeRange kBlockLengthPrefixCode[] = { + { 1, 2}, { 5, 2}, { 9, 2}, { 13, 2}, + { 17, 3}, { 25, 3}, { 33, 3}, { 41, 3}, + { 49, 4}, { 65, 4}, { 81, 4}, { 97, 4}, + { 113, 5}, { 145, 5}, { 177, 5}, { 209, 5}, + { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8}, + { 753, 9}, { 1265, 10}, {2289, 11}, {4337, 12}, + {8433, 13}, {16625, 24} +}; + +static const struct PrefixCodeRange kInsertLengthPrefixCode[] = { + { 0, 0}, { 1, 0}, { 2, 0}, { 3, 0}, + { 4, 0}, { 5, 0}, { 6, 1}, { 8, 1}, + { 10, 2}, { 14, 2}, { 18, 3}, { 26, 3}, + { 34, 4}, { 50, 4}, { 66, 5}, { 98, 5}, + { 130, 6}, { 194, 7}, { 322, 8}, { 578, 9}, + {1090, 10}, {2114, 12}, {6210, 14}, {22594, 24}, +}; + +static const struct PrefixCodeRange kCopyLengthPrefixCode[] = { + { 2, 0}, { 3, 0}, { 4, 0}, { 5, 0}, + { 6, 0}, { 7, 0}, { 8, 0}, { 9, 0}, + { 10, 1}, { 12, 1}, { 14, 2}, { 18, 2}, + { 22, 3}, { 30, 3}, { 38, 4}, { 54, 4}, + { 70, 5}, { 102, 5}, { 134, 6}, { 198, 7}, + {326, 8}, { 582, 9}, {1094, 10}, {2118, 24}, +}; + +static const int kInsertAndCopyRangeLut[9] = { + 0, 1, 4, 2, 3, 6, 5, 7, 8, +}; + +static const int kInsertRangeLut[9] = { + 0, 0, 1, 1, 0, 2, 1, 2, 2, +}; + +static const int kCopyRangeLut[9] = { + 0, 1, 0, 1, 2, 0, 2, 1, 2, +}; + +#endif // BROTLI_DEC_PREFIX_H_ diff --git a/dec/safe_malloc.c b/dec/safe_malloc.c new file mode 100644 index 0000000..41fa480 --- /dev/null +++ b/dec/safe_malloc.c @@ -0,0 +1,41 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Size-checked memory allocation. + +#include <stdlib.h> +#include "./safe_malloc.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +// Returns 0 in case of overflow of nmemb * size. +static int CheckSizeArgumentsOverflow(uint64_t nmemb, size_t size) { + const uint64_t total_size = nmemb * size; + if (nmemb == 0) return 1; + if ((uint64_t)size > BROTLI_MAX_ALLOCABLE_MEMORY / nmemb) return 0; + if (total_size != (size_t)total_size) return 0; + return 1; +} + +void* BrotliSafeMalloc(uint64_t nmemb, size_t size) { + if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL; + assert(nmemb * size > 0); + return malloc((size_t)(nmemb * size)); +} + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif diff --git a/dec/safe_malloc.h b/dec/safe_malloc.h new file mode 100644 index 0000000..5a334fc --- /dev/null +++ b/dec/safe_malloc.h @@ -0,0 +1,43 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Size-checked memory allocation. + +#ifndef BROTLI_UTILS_UTILS_H_ +#define BROTLI_UTILS_UTILS_H_ + +#include <assert.h> + +#include "./types.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +// This is the maximum memory amount that we will ever try to allocate. +#define BROTLI_MAX_ALLOCABLE_MEMORY (1ULL << 40) + +// size-checking safe malloc/calloc: verify that the requested size is not too +// large, or return NULL. You don't need to call these for constructs like +// malloc(sizeof(foo)), but only if there's font-dependent size involved +// somewhere (like: malloc(decoded_size * sizeof(*something))). That's why this +// safe malloc() borrows the signature from calloc(), pointing at the dangerous +// underlying multiply involved. +void* BrotliSafeMalloc(uint64_t nmemb, size_t size); + +#if defined(__cplusplus) || defined(c_plusplus) +} // extern "C" +#endif + +#endif /* BROTLI_UTILS_UTILS_H_ */ diff --git a/dec/types.h b/dec/types.h new file mode 100644 index 0000000..41696e4 --- /dev/null +++ b/dec/types.h @@ -0,0 +1,41 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// 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. +// +// Common types + +#ifndef BROTLI_DEC_TYPES_H_ +#define BROTLI_DEC_TYPES_H_ + +#include <stddef.h> // for size_t + +#ifndef _MSC_VER +#include <inttypes.h> +#ifdef __STRICT_ANSI__ +#define BROTLI_INLINE +#else /* __STRICT_ANSI__ */ +#define BROTLI_INLINE inline +#endif +#else +typedef signed char int8_t; +typedef unsigned char uint8_t; +typedef signed short int16_t; +typedef unsigned short uint16_t; +typedef signed int int32_t; +typedef unsigned int uint32_t; +typedef unsigned long long int uint64_t; +typedef long long int int64_t; +#define BROTLI_INLINE __forceinline +#endif /* _MSC_VER */ + +#endif // BROTLI_DEC_TYPES_H_ |