Index: third_party/brotli/enc/encode.c |
diff --git a/third_party/brotli/enc/encode.cc b/third_party/brotli/enc/encode.c |
similarity index 19% |
rename from third_party/brotli/enc/encode.cc |
rename to third_party/brotli/enc/encode.c |
index b92768e9f7c61a1c96640a2e5f76e65401cb5d48..d846513a0297525867ba3f9ac84f127174a3e0b8 100644 |
--- a/third_party/brotli/enc/encode.cc |
+++ b/third_party/brotli/enc/encode.c |
@@ -4,55 +4,169 @@ |
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
*/ |
-// Implementation of Brotli compressor. |
+/* Implementation of Brotli compressor. */ |
-#include "./encode.h" |
+#include <brotli/encode.h> |
-#include <algorithm> |
-#include <cstdlib> /* free, malloc */ |
-#include <cstring> /* memset */ |
-#include <limits> |
+#include <stdlib.h> /* free, malloc */ |
+#include <string.h> /* memcpy, memset */ |
+#include "../common/version.h" |
#include "./backward_references.h" |
#include "./bit_cost.h" |
-#include "./block_splitter.h" |
#include "./brotli_bit_stream.h" |
-#include "./cluster.h" |
-#include "./context.h" |
-#include "./metablock.h" |
-#include "./transform.h" |
#include "./compress_fragment.h" |
#include "./compress_fragment_two_pass.h" |
+#include "./context.h" |
#include "./entropy_encode.h" |
#include "./fast_log.h" |
#include "./hash.h" |
#include "./histogram.h" |
+#include "./memory.h" |
+#include "./metablock.h" |
+#include "./port.h" |
#include "./prefix.h" |
+#include "./quality.h" |
+#include "./ringbuffer.h" |
#include "./utf8_util.h" |
#include "./write_bits.h" |
-namespace brotli { |
- |
-static const int kMinQualityForBlockSplit = 4; |
-static const int kMinQualityForContextModeling = 5; |
-static const int kMinQualityForOptimizeHistograms = 4; |
-// For quality 2 there is no block splitting, so we buffer at most this much |
-// literals and commands. |
-static const size_t kMaxNumDelayedSymbols = 0x2fff; |
+#if defined(__cplusplus) || defined(c_plusplus) |
+extern "C" { |
+#endif |
#define COPY_ARRAY(dst, src) memcpy(dst, src, sizeof(src)); |
+typedef enum BrotliEncoderStreamState { |
+ /* Default state. */ |
+ BROTLI_STREAM_PROCESSING = 0, |
+ /* Intermediate state; after next block is emitted, byte-padding should be |
+ performed before getting back to default state. */ |
+ BROTLI_STREAM_FLUSH_REQUESTED = 1, |
+ /* Last metablock was produced; no more input is acceptable. */ |
+ BROTLI_STREAM_FINISHED = 2, |
+ /* Flushing compressed block and writing meta-data block header. */ |
+ BROTLI_STREAM_METADATA_HEAD = 3, |
+ /* Writing metadata block body. */ |
+ BROTLI_STREAM_METADATA_BODY = 4 |
+} BrotliEncoderStreamState; |
+ |
+typedef struct BrotliEncoderStateStruct { |
+ BrotliEncoderParams params; |
+ |
+ MemoryManager memory_manager_; |
+ |
+ Hashers hashers_; |
+ uint64_t input_pos_; |
+ RingBuffer ringbuffer_; |
+ size_t cmd_alloc_size_; |
+ Command* commands_; |
+ size_t num_commands_; |
+ size_t num_literals_; |
+ size_t last_insert_len_; |
+ uint64_t last_flush_pos_; |
+ uint64_t last_processed_pos_; |
+ int dist_cache_[4]; |
+ int saved_dist_cache_[4]; |
+ uint8_t last_byte_; |
+ uint8_t last_byte_bits_; |
+ uint8_t prev_byte_; |
+ uint8_t prev_byte2_; |
+ size_t storage_size_; |
+ uint8_t* storage_; |
+ /* Hash table for FAST_ONE_PASS_COMPRESSION_QUALITY mode. */ |
+ int small_table_[1 << 10]; /* 4KiB */ |
+ int* large_table_; /* Allocated only when needed */ |
+ size_t large_table_size_; |
+ /* Command and distance prefix codes (each 64 symbols, stored back-to-back) |
+ used for the next block in FAST_ONE_PASS_COMPRESSION_QUALITY. The command |
+ prefix code is over a smaller alphabet with the following 64 symbols: |
+ 0 - 15: insert length code 0, copy length code 0 - 15, same distance |
+ 16 - 39: insert length code 0, copy length code 0 - 23 |
+ 40 - 63: insert length code 0 - 23, copy length code 0 |
+ Note that symbols 16 and 40 represent the same code in the full alphabet, |
+ but we do not use either of them in FAST_ONE_PASS_COMPRESSION_QUALITY. */ |
+ uint8_t cmd_depths_[128]; |
+ uint16_t cmd_bits_[128]; |
+ /* The compressed form of the command and distance prefix codes for the next |
+ block in FAST_ONE_PASS_COMPRESSION_QUALITY. */ |
+ uint8_t cmd_code_[512]; |
+ size_t cmd_code_numbits_; |
+ /* Command and literal buffers for FAST_TWO_PASS_COMPRESSION_QUALITY. */ |
+ uint32_t* command_buf_; |
+ uint8_t* literal_buf_; |
+ |
+ uint8_t* next_out_; |
+ size_t available_out_; |
+ size_t total_out_; |
+ /* Temporary buffer for padding flush bits or metadata block header / body. */ |
+ union { |
+ uint64_t u64[2]; |
+ uint8_t u8[16]; |
+ } tiny_buf_; |
+ uint32_t remaining_metadata_bytes_; |
+ BrotliEncoderStreamState stream_state_; |
+ |
+ BROTLI_BOOL is_last_block_emitted_; |
+ BROTLI_BOOL is_initialized_; |
+} BrotliEncoderStateStruct; |
+ |
+static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s); |
+ |
+static size_t InputBlockSize(BrotliEncoderState* s) { |
+ if (!EnsureInitialized(s)) return 0; |
+ return (size_t)1 << s->params.lgblock; |
+} |
+ |
+static uint64_t UnprocessedInputSize(BrotliEncoderState* s) { |
+ return s->input_pos_ - s->last_processed_pos_; |
+} |
+ |
+static size_t RemainingInputBlockSize(BrotliEncoderState* s) { |
+ const uint64_t delta = UnprocessedInputSize(s); |
+ size_t block_size = InputBlockSize(s); |
+ if (delta >= block_size) return 0; |
+ return block_size - (size_t)delta; |
+} |
+ |
+BROTLI_BOOL BrotliEncoderSetParameter( |
+ BrotliEncoderState* state, BrotliEncoderParameter p, uint32_t value) { |
+ /* Changing parameters on the fly is not implemented yet. */ |
+ if (state->is_initialized_) return BROTLI_FALSE; |
+ /* TODO: Validate/clamp parameters here. */ |
+ switch (p) { |
+ case BROTLI_PARAM_MODE: |
+ state->params.mode = (BrotliEncoderMode)value; |
+ return BROTLI_TRUE; |
+ |
+ case BROTLI_PARAM_QUALITY: |
+ state->params.quality = (int)value; |
+ return BROTLI_TRUE; |
+ |
+ case BROTLI_PARAM_LGWIN: |
+ state->params.lgwin = (int)value; |
+ return BROTLI_TRUE; |
+ |
+ case BROTLI_PARAM_LGBLOCK: |
+ state->params.lgblock = (int)value; |
+ return BROTLI_TRUE; |
+ |
+ default: return BROTLI_FALSE; |
+ } |
+} |
+ |
static void RecomputeDistancePrefixes(Command* cmds, |
size_t num_commands, |
uint32_t num_direct_distance_codes, |
uint32_t distance_postfix_bits) { |
+ size_t i; |
if (num_direct_distance_codes == 0 && distance_postfix_bits == 0) { |
return; |
} |
- for (size_t i = 0; i < num_commands; ++i) { |
+ for (i = 0; i < num_commands; ++i) { |
Command* cmd = &cmds[i]; |
- if (cmd->copy_len() && cmd->cmd_prefix_ >= 128) { |
- PrefixEncodeCopyDistance(cmd->DistanceCode(), |
+ if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) { |
+ PrefixEncodeCopyDistance(CommandRestoreDistanceCode(cmd), |
num_direct_distance_codes, |
distance_postfix_bits, |
&cmd->dist_prefix_, |
@@ -61,27 +175,27 @@ static void RecomputeDistancePrefixes(Command* cmds, |
} |
} |
-/* Wraps 64-bit input position to 32-bit ringbuffer position preserving |
+/* Wraps 64-bit input position to 32-bit ring-buffer position preserving |
"not-a-first-lap" feature. */ |
static uint32_t WrapPosition(uint64_t position) { |
- uint32_t result = static_cast<uint32_t>(position); |
- if (position > (1u << 30)) { |
- result = (result & ((1u << 30) - 1)) | (1u << 30); |
+ uint32_t result = (uint32_t)position; |
+ uint64_t gb = position >> 30; |
+ if (gb > 2) { |
+ /* Wrap every 2GiB; The first 3GB are continuous. */ |
+ result = (result & ((1u << 30) - 1)) | ((uint32_t)((gb - 1) & 1) + 1) << 30; |
} |
return result; |
} |
-uint8_t* BrotliCompressor::GetBrotliStorage(size_t size) { |
- if (storage_size_ < size) { |
- delete[] storage_; |
- storage_ = new uint8_t[size]; |
- storage_size_ = size; |
+static uint8_t* GetBrotliStorage(BrotliEncoderState* s, size_t size) { |
+ MemoryManager* m = &s->memory_manager_; |
+ if (s->storage_size_ < size) { |
+ BROTLI_FREE(m, s->storage_); |
+ s->storage_ = BROTLI_ALLOC(m, uint8_t, size); |
+ if (BROTLI_IS_OOM(m)) return NULL; |
+ s->storage_size_ = size; |
} |
- return storage_; |
-} |
- |
-static size_t MaxHashTableSize(int quality) { |
- return quality == 0 ? 1 << 15 : 1 << 17; |
+ return s->storage_; |
} |
static size_t HashTableSize(size_t max_table_size, size_t input_size) { |
@@ -92,25 +206,34 @@ static size_t HashTableSize(size_t max_table_size, size_t input_size) { |
return htsize; |
} |
-int* BrotliCompressor::GetHashTable(int quality, |
- size_t input_size, |
- size_t* table_size) { |
- // Use smaller hash table when input.size() is smaller, since we |
- // fill the table, incurring O(hash table size) overhead for |
- // compression, and if the input is short, we won't need that |
- // many hash table entries anyway. |
+static int* GetHashTable(BrotliEncoderState* s, int quality, |
+ size_t input_size, size_t* table_size) { |
+ /* Use smaller hash table when input.size() is smaller, since we |
+ fill the table, incurring O(hash table size) overhead for |
+ compression, and if the input is short, we won't need that |
+ many hash table entries anyway. */ |
+ MemoryManager* m = &s->memory_manager_; |
const size_t max_table_size = MaxHashTableSize(quality); |
- assert(max_table_size >= 256); |
size_t htsize = HashTableSize(max_table_size, input_size); |
- |
int* table; |
- if (htsize <= sizeof(small_table_) / sizeof(small_table_[0])) { |
- table = small_table_; |
+ assert(max_table_size >= 256); |
+ if (quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { |
+ /* Only odd shifts are supported by fast-one-pass. */ |
+ if ((htsize & 0xAAAAA) == 0) { |
+ htsize <<= 1; |
+ } |
+ } |
+ |
+ if (htsize <= sizeof(s->small_table_) / sizeof(s->small_table_[0])) { |
+ table = s->small_table_; |
} else { |
- if (large_table_ == NULL) { |
- large_table_ = new int[max_table_size]; |
+ if (htsize > s->large_table_size_) { |
+ s->large_table_size_ = htsize; |
+ BROTLI_FREE(m, s->large_table_); |
+ s->large_table_ = BROTLI_ALLOC(m, int, htsize); |
+ if (BROTLI_IS_OOM(m)) return 0; |
} |
- table = large_table_; |
+ table = s->large_table_; |
} |
*table_size = htsize; |
@@ -119,7 +242,7 @@ int* BrotliCompressor::GetHashTable(int quality, |
} |
static void EncodeWindowBits(int lgwin, uint8_t* last_byte, |
- uint8_t* last_byte_bits) { |
+ uint8_t* last_byte_bits) { |
if (lgwin == 16) { |
*last_byte = 0; |
*last_byte_bits = 1; |
@@ -127,15 +250,15 @@ static void EncodeWindowBits(int lgwin, uint8_t* last_byte, |
*last_byte = 1; |
*last_byte_bits = 7; |
} else if (lgwin > 17) { |
- *last_byte = static_cast<uint8_t>(((lgwin - 17) << 1) | 1); |
+ *last_byte = (uint8_t)(((lgwin - 17) << 1) | 1); |
*last_byte_bits = 4; |
} else { |
- *last_byte = static_cast<uint8_t>(((lgwin - 8) << 4) | 1); |
+ *last_byte = (uint8_t)(((lgwin - 8) << 4) | 1); |
*last_byte_bits = 7; |
} |
} |
-// Initializes the command and distance prefix codes for the first block. |
+/* Initializes the command and distance prefix codes for the first block. */ |
static void InitCommandPrefixCodes(uint8_t cmd_depths[128], |
uint16_t cmd_bits[128], |
uint8_t cmd_code[512], |
@@ -164,11 +287,6 @@ static void InitCommandPrefixCodes(uint8_t cmd_depths[128], |
2, 10, 6, 21, 13, 29, 3, 19, 11, 15, 47, 31, 95, 63, 127, 255, |
767, 2815, 1791, 3839, 511, 2559, 1535, 3583, 1023, 3071, 2047, 4095, |
}; |
- COPY_ARRAY(cmd_depths, kDefaultCommandDepths); |
- COPY_ARRAY(cmd_bits, kDefaultCommandBits); |
- |
- // Initialize the pre-compressed form of the command and distance prefix |
- // codes. |
static const uint8_t kDefaultCommandCode[] = { |
0xff, 0x77, 0xd5, 0xbf, 0xe7, 0xde, 0xea, 0x9e, 0x51, 0x5d, 0xde, 0xc6, |
0x70, 0x57, 0xbc, 0x58, 0x58, 0x58, 0xd8, 0xd8, 0x58, 0xd5, 0xcb, 0x8c, |
@@ -176,71 +294,79 @@ static void InitCommandPrefixCodes(uint8_t cmd_depths[128], |
0x06, 0x83, 0xc1, 0x60, 0x30, 0x18, 0xcc, 0xa1, 0xce, 0x88, 0x54, 0x94, |
0x46, 0xe1, 0xb0, 0xd0, 0x4e, 0xb2, 0xf7, 0x04, 0x00, |
}; |
- static const int kDefaultCommandCodeNumBits = 448; |
+ static const size_t kDefaultCommandCodeNumBits = 448; |
+ COPY_ARRAY(cmd_depths, kDefaultCommandDepths); |
+ COPY_ARRAY(cmd_bits, kDefaultCommandBits); |
+ |
+ /* Initialize the pre-compressed form of the command and distance prefix |
+ codes. */ |
COPY_ARRAY(cmd_code, kDefaultCommandCode); |
*cmd_code_numbits = kDefaultCommandCodeNumBits; |
} |
-// Decide about the context map based on the ability of the prediction |
-// ability of the previous byte UTF8-prefix on the next byte. The |
-// prediction ability is calculated as shannon entropy. Here we need |
-// shannon entropy instead of 'BitsEntropy' since the prefix will be |
-// encoded with the remaining 6 bits of the following byte, and |
-// BitsEntropy will assume that symbol to be stored alone using Huffman |
-// coding. |
+/* Decide about the context map based on the ability of the prediction |
+ ability of the previous byte UTF8-prefix on the next byte. The |
+ prediction ability is calculated as Shannon entropy. Here we need |
+ Shannon entropy instead of 'BitsEntropy' since the prefix will be |
+ encoded with the remaining 6 bits of the following byte, and |
+ BitsEntropy will assume that symbol to be stored alone using Huffman |
+ coding. */ |
static void ChooseContextMap(int quality, |
uint32_t* bigram_histo, |
size_t* num_literal_contexts, |
const uint32_t** literal_context_map) { |
+ static const uint32_t kStaticContextMapContinuation[64] = { |
+ 1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
+ }; |
+ static const uint32_t kStaticContextMapSimpleUTF8[64] = { |
+ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
+ }; |
+ |
uint32_t monogram_histo[3] = { 0 }; |
uint32_t two_prefix_histo[6] = { 0 }; |
size_t total = 0; |
- for (size_t i = 0; i < 9; ++i) { |
+ size_t i; |
+ size_t dummy; |
+ double entropy[4]; |
+ for (i = 0; i < 9; ++i) { |
+ size_t j = i; |
total += bigram_histo[i]; |
monogram_histo[i % 3] += bigram_histo[i]; |
- size_t j = i; |
if (j >= 6) { |
j -= 6; |
} |
two_prefix_histo[j] += bigram_histo[i]; |
} |
- size_t dummy; |
- double entropy1 = ShannonEntropy(monogram_histo, 3, &dummy); |
- double entropy2 = (ShannonEntropy(two_prefix_histo, 3, &dummy) + |
- ShannonEntropy(two_prefix_histo + 3, 3, &dummy)); |
- double entropy3 = 0; |
- for (size_t k = 0; k < 3; ++k) { |
- entropy3 += ShannonEntropy(bigram_histo + 3 * k, 3, &dummy); |
+ entropy[1] = ShannonEntropy(monogram_histo, 3, &dummy); |
+ entropy[2] = (ShannonEntropy(two_prefix_histo, 3, &dummy) + |
+ ShannonEntropy(two_prefix_histo + 3, 3, &dummy)); |
+ entropy[3] = 0; |
+ for (i = 0; i < 3; ++i) { |
+ entropy[3] += ShannonEntropy(bigram_histo + 3 * i, 3, &dummy); |
} |
assert(total != 0); |
- double scale = 1.0 / static_cast<double>(total); |
- entropy1 *= scale; |
- entropy2 *= scale; |
- entropy3 *= scale; |
- |
- static const uint32_t kStaticContextMapContinuation[64] = { |
- 1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
- }; |
- static const uint32_t kStaticContextMapSimpleUTF8[64] = { |
- 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
- }; |
- if (quality < 7) { |
- // 3 context models is a bit slower, don't use it at lower qualities. |
- entropy3 = entropy1 * 10; |
- } |
- // If expected savings by symbol are less than 0.2 bits, skip the |
- // context modeling -- in exchange for faster decoding speed. |
- if (entropy1 - entropy2 < 0.2 && |
- entropy1 - entropy3 < 0.2) { |
+ entropy[0] = 1.0 / (double)total; |
+ entropy[1] *= entropy[0]; |
+ entropy[2] *= entropy[0]; |
+ entropy[3] *= entropy[0]; |
+ |
+ if (quality < MIN_QUALITY_FOR_HQ_CONTEXT_MODELING) { |
+ /* 3 context models is a bit slower, don't use it at lower qualities. */ |
+ entropy[3] = entropy[1] * 10; |
+ } |
+ /* If expected savings by symbol are less than 0.2 bits, skip the |
+ context modeling -- in exchange for faster decoding speed. */ |
+ if (entropy[1] - entropy[2] < 0.2 && |
+ entropy[1] - entropy[3] < 0.2) { |
*num_literal_contexts = 1; |
- } else if (entropy2 - entropy3 < 0.02) { |
+ } else if (entropy[2] - entropy[3] < 0.02) { |
*num_literal_contexts = 2; |
*literal_context_map = kStaticContextMapSimpleUTF8; |
} else { |
@@ -249,72 +375,67 @@ static void ChooseContextMap(int quality, |
} |
} |
-static void DecideOverLiteralContextModeling( |
- const uint8_t* input, |
- size_t start_pos, |
- size_t length, |
- size_t mask, |
- int quality, |
- ContextType* literal_context_mode, |
- size_t* num_literal_contexts, |
+static void DecideOverLiteralContextModeling(const uint8_t* input, |
+ size_t start_pos, size_t length, size_t mask, int quality, |
+ ContextType* literal_context_mode, size_t* num_literal_contexts, |
const uint32_t** literal_context_map) { |
- if (quality < kMinQualityForContextModeling || length < 64) { |
+ if (quality < MIN_QUALITY_FOR_CONTEXT_MODELING || length < 64) { |
return; |
- } |
- // Gather bigram data of the UTF8 byte prefixes. To make the analysis of |
- // UTF8 data faster we only examine 64 byte long strides at every 4kB |
- // intervals. |
- const size_t end_pos = start_pos + length; |
- uint32_t bigram_prefix_histo[9] = { 0 }; |
- for (; start_pos + 64 <= end_pos; start_pos += 4096) { |
+ } else { |
+ /* Gather bi-gram data of the UTF8 byte prefixes. To make the analysis of |
+ UTF8 data faster we only examine 64 byte long strides at every 4kB |
+ intervals. */ |
+ const size_t end_pos = start_pos + length; |
+ uint32_t bigram_prefix_histo[9] = { 0 }; |
+ for (; start_pos + 64 <= end_pos; start_pos += 4096) { |
static const int lut[4] = { 0, 0, 1, 2 }; |
- const size_t stride_end_pos = start_pos + 64; |
- int prev = lut[input[start_pos & mask] >> 6] * 3; |
- for (size_t pos = start_pos + 1; pos < stride_end_pos; ++pos) { |
- const uint8_t literal = input[pos & mask]; |
- ++bigram_prefix_histo[prev + lut[literal >> 6]]; |
- prev = lut[literal >> 6] * 3; |
+ const size_t stride_end_pos = start_pos + 64; |
+ int prev = lut[input[start_pos & mask] >> 6] * 3; |
+ size_t pos; |
+ for (pos = start_pos + 1; pos < stride_end_pos; ++pos) { |
+ const uint8_t literal = input[pos & mask]; |
+ ++bigram_prefix_histo[prev + lut[literal >> 6]]; |
+ prev = lut[literal >> 6] * 3; |
+ } |
} |
+ *literal_context_mode = CONTEXT_UTF8; |
+ ChooseContextMap(quality, &bigram_prefix_histo[0], num_literal_contexts, |
+ literal_context_map); |
} |
- *literal_context_mode = CONTEXT_UTF8; |
- ChooseContextMap(quality, &bigram_prefix_histo[0], num_literal_contexts, |
- literal_context_map); |
} |
-static bool ShouldCompress(const uint8_t* data, |
- const size_t mask, |
- const uint64_t last_flush_pos, |
- const size_t bytes, |
- const size_t num_literals, |
- const size_t num_commands) { |
+static BROTLI_BOOL ShouldCompress( |
+ const uint8_t* data, const size_t mask, const uint64_t last_flush_pos, |
+ const size_t bytes, const size_t num_literals, const size_t num_commands) { |
if (num_commands < (bytes >> 8) + 2) { |
- if (num_literals > 0.99 * static_cast<double>(bytes)) { |
+ if (num_literals > 0.99 * (double)bytes) { |
uint32_t literal_histo[256] = { 0 }; |
static const uint32_t kSampleRate = 13; |
static const double kMinEntropy = 7.92; |
const double bit_cost_threshold = |
- static_cast<double>(bytes) * kMinEntropy / kSampleRate; |
+ (double)bytes * kMinEntropy / kSampleRate; |
size_t t = (bytes + kSampleRate - 1) / kSampleRate; |
- uint32_t pos = static_cast<uint32_t>(last_flush_pos); |
- for (size_t i = 0; i < t; i++) { |
+ uint32_t pos = (uint32_t)last_flush_pos; |
+ size_t i; |
+ for (i = 0; i < t; i++) { |
++literal_histo[data[pos & mask]]; |
pos += kSampleRate; |
} |
if (BitsEntropy(literal_histo, 256) > bit_cost_threshold) { |
- return false; |
+ return BROTLI_FALSE; |
} |
} |
} |
- return true; |
+ return BROTLI_TRUE; |
} |
-static void WriteMetaBlockInternal(const uint8_t* data, |
+static void WriteMetaBlockInternal(MemoryManager* m, |
+ const uint8_t* data, |
const size_t mask, |
const uint64_t last_flush_pos, |
const size_t bytes, |
- const bool is_last, |
- const int quality, |
- const bool font_mode, |
+ const BROTLI_BOOL is_last, |
+ const BrotliEncoderParams* params, |
const uint8_t prev_byte, |
const uint8_t prev_byte2, |
const size_t num_literals, |
@@ -324,29 +445,34 @@ static void WriteMetaBlockInternal(const uint8_t* data, |
int* dist_cache, |
size_t* storage_ix, |
uint8_t* storage) { |
+ const uint32_t wrapped_last_flush_pos = WrapPosition(last_flush_pos); |
+ uint8_t last_byte; |
+ uint8_t last_byte_bits; |
+ uint32_t num_direct_distance_codes = 0; |
+ uint32_t distance_postfix_bits = 0; |
+ |
if (bytes == 0) { |
- // Write the ISLAST and ISEMPTY bits. |
- WriteBits(2, 3, storage_ix, storage); |
+ /* Write the ISLAST and ISEMPTY bits. */ |
+ BrotliWriteBits(2, 3, storage_ix, storage); |
*storage_ix = (*storage_ix + 7u) & ~7u; |
return; |
} |
if (!ShouldCompress(data, mask, last_flush_pos, bytes, |
num_literals, num_commands)) { |
- // Restore the distance cache, as its last update by |
- // CreateBackwardReferences is now unused. |
+ /* Restore the distance cache, as its last update by |
+ CreateBackwardReferences is now unused. */ |
memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); |
- StoreUncompressedMetaBlock(is_last, data, |
- WrapPosition(last_flush_pos), mask, bytes, |
- storage_ix, storage); |
+ BrotliStoreUncompressedMetaBlock(is_last, data, |
+ wrapped_last_flush_pos, mask, bytes, |
+ storage_ix, storage); |
return; |
} |
- const uint8_t last_byte = storage[0]; |
- const uint8_t last_byte_bits = static_cast<uint8_t>(*storage_ix & 0xff); |
- uint32_t num_direct_distance_codes = 0; |
- uint32_t distance_postfix_bits = 0; |
- if (quality > 9 && font_mode) { |
+ last_byte = storage[0]; |
+ last_byte_bits = (uint8_t)(*storage_ix & 0xff); |
+ if (params->quality >= MIN_QUALITY_FOR_RECOMPUTE_DISTANCE_PREFIXES && |
+ params->mode == BROTLI_MODE_FONT) { |
num_direct_distance_codes = 12; |
distance_postfix_bits = 1; |
RecomputeDistancePrefixes(commands, |
@@ -354,463 +480,590 @@ static void WriteMetaBlockInternal(const uint8_t* data, |
num_direct_distance_codes, |
distance_postfix_bits); |
} |
- if (quality == 2) { |
- StoreMetaBlockFast(data, WrapPosition(last_flush_pos), |
- bytes, mask, is_last, |
- commands, num_commands, |
- storage_ix, storage); |
- } else if (quality < kMinQualityForBlockSplit) { |
- StoreMetaBlockTrivial(data, WrapPosition(last_flush_pos), |
- bytes, mask, is_last, |
- commands, num_commands, |
- storage_ix, storage); |
+ if (params->quality <= MAX_QUALITY_FOR_STATIC_ENRTOPY_CODES) { |
+ BrotliStoreMetaBlockFast(m, data, wrapped_last_flush_pos, |
+ bytes, mask, is_last, |
+ commands, num_commands, |
+ storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) return; |
+ } else if (params->quality < MIN_QUALITY_FOR_BLOCK_SPLIT) { |
+ BrotliStoreMetaBlockTrivial(m, data, wrapped_last_flush_pos, |
+ bytes, mask, is_last, |
+ commands, num_commands, |
+ storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) return; |
} else { |
- MetaBlockSplit mb; |
ContextType literal_context_mode = CONTEXT_UTF8; |
- if (quality <= 9) { |
+ MetaBlockSplit mb; |
+ InitMetaBlockSplit(&mb); |
+ if (params->quality < MIN_QUALITY_FOR_HQ_BLOCK_SPLITTING) { |
size_t num_literal_contexts = 1; |
const uint32_t* literal_context_map = NULL; |
- DecideOverLiteralContextModeling(data, WrapPosition(last_flush_pos), |
+ DecideOverLiteralContextModeling(data, wrapped_last_flush_pos, |
bytes, mask, |
- quality, |
+ params->quality, |
&literal_context_mode, |
&num_literal_contexts, |
&literal_context_map); |
if (literal_context_map == NULL) { |
- BuildMetaBlockGreedy(data, WrapPosition(last_flush_pos), mask, |
- commands, num_commands, &mb); |
+ BrotliBuildMetaBlockGreedy(m, data, wrapped_last_flush_pos, mask, |
+ commands, num_commands, &mb); |
+ if (BROTLI_IS_OOM(m)) return; |
} else { |
- BuildMetaBlockGreedyWithContexts(data, WrapPosition(last_flush_pos), |
- mask, |
- prev_byte, prev_byte2, |
- literal_context_mode, |
- num_literal_contexts, |
- literal_context_map, |
- commands, num_commands, |
- &mb); |
+ BrotliBuildMetaBlockGreedyWithContexts(m, data, |
+ wrapped_last_flush_pos, |
+ mask, |
+ prev_byte, prev_byte2, |
+ literal_context_mode, |
+ num_literal_contexts, |
+ literal_context_map, |
+ commands, num_commands, |
+ &mb); |
+ if (BROTLI_IS_OOM(m)) return; |
} |
} else { |
- if (!IsMostlyUTF8(data, WrapPosition(last_flush_pos), mask, bytes, |
- kMinUTF8Ratio)) { |
+ if (!BrotliIsMostlyUTF8(data, wrapped_last_flush_pos, mask, bytes, |
+ kMinUTF8Ratio)) { |
literal_context_mode = CONTEXT_SIGNED; |
} |
- BuildMetaBlock(data, WrapPosition(last_flush_pos), mask, |
- prev_byte, prev_byte2, |
- commands, num_commands, |
- literal_context_mode, |
- &mb); |
+ BrotliBuildMetaBlock(m, data, wrapped_last_flush_pos, mask, params, |
+ prev_byte, prev_byte2, |
+ commands, num_commands, |
+ literal_context_mode, |
+ &mb); |
+ if (BROTLI_IS_OOM(m)) return; |
} |
- if (quality >= kMinQualityForOptimizeHistograms) { |
- OptimizeHistograms(num_direct_distance_codes, |
- distance_postfix_bits, |
- &mb); |
+ if (params->quality >= MIN_QUALITY_FOR_OPTIMIZE_HISTOGRAMS) { |
+ BrotliOptimizeHistograms(num_direct_distance_codes, |
+ distance_postfix_bits, |
+ &mb); |
} |
- StoreMetaBlock(data, WrapPosition(last_flush_pos), bytes, mask, |
- prev_byte, prev_byte2, |
- is_last, |
- num_direct_distance_codes, |
- distance_postfix_bits, |
- literal_context_mode, |
- commands, num_commands, |
- mb, |
- storage_ix, storage); |
+ BrotliStoreMetaBlock(m, data, wrapped_last_flush_pos, bytes, mask, |
+ prev_byte, prev_byte2, |
+ is_last, |
+ num_direct_distance_codes, |
+ distance_postfix_bits, |
+ literal_context_mode, |
+ commands, num_commands, |
+ &mb, |
+ storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) return; |
+ DestroyMetaBlockSplit(m, &mb); |
} |
if (bytes + 4 < (*storage_ix >> 3)) { |
- // Restore the distance cache and last byte. |
+ /* Restore the distance cache and last byte. */ |
memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); |
storage[0] = last_byte; |
*storage_ix = last_byte_bits; |
- StoreUncompressedMetaBlock(is_last, data, |
- WrapPosition(last_flush_pos), mask, |
- bytes, storage_ix, storage); |
+ BrotliStoreUncompressedMetaBlock(is_last, data, |
+ wrapped_last_flush_pos, mask, |
+ bytes, storage_ix, storage); |
} |
} |
-BrotliCompressor::BrotliCompressor(BrotliParams params) |
- : params_(params), |
- hashers_(new Hashers()), |
- input_pos_(0), |
- num_commands_(0), |
- num_literals_(0), |
- last_insert_len_(0), |
- last_flush_pos_(0), |
- last_processed_pos_(0), |
- prev_byte_(0), |
- prev_byte2_(0), |
- storage_size_(0), |
- storage_(0), |
- large_table_(NULL), |
- cmd_code_numbits_(0), |
- command_buf_(NULL), |
- literal_buf_(NULL), |
- is_last_block_emitted_(0) { |
- // Sanitize params. |
- params_.quality = std::max(0, params_.quality); |
- if (params_.lgwin < kMinWindowBits) { |
- params_.lgwin = kMinWindowBits; |
- } else if (params_.lgwin > kMaxWindowBits) { |
- params_.lgwin = kMaxWindowBits; |
- } |
- if (params_.quality <= 1) { |
- params_.lgblock = params_.lgwin; |
- } else if (params_.quality < kMinQualityForBlockSplit) { |
- params_.lgblock = 14; |
- } else if (params_.lgblock == 0) { |
- params_.lgblock = 16; |
- if (params_.quality >= 9 && params_.lgwin > params_.lgblock) { |
- params_.lgblock = std::min(18, params_.lgwin); |
+static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s) { |
+ if (BROTLI_IS_OOM(&s->memory_manager_)) return BROTLI_FALSE; |
+ if (s->is_initialized_) return BROTLI_TRUE; |
+ |
+ SanitizeParams(&s->params); |
+ s->params.lgblock = ComputeLgBlock(&s->params); |
+ |
+ s->remaining_metadata_bytes_ = BROTLI_UINT32_MAX; |
+ |
+ RingBufferSetup(&s->params, &s->ringbuffer_); |
+ |
+ /* Initialize last byte with stream header. */ |
+ { |
+ int lgwin = s->params.lgwin; |
+ if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY || |
+ s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { |
+ lgwin = BROTLI_MAX(int, lgwin, 18); |
} |
- } else { |
- params_.lgblock = std::min(kMaxInputBlockBits, |
- std::max(kMinInputBlockBits, params_.lgblock)); |
- } |
- |
- // Initialize input and literal cost ring buffers. |
- // We allocate at least lgwin + 1 bits for the ring buffer so that the newly |
- // added block fits there completely and we still get lgwin bits and at least |
- // read_block_size_bits + 1 bits because the copy tail length needs to be |
- // smaller than ringbuffer size. |
- int ringbuffer_bits = std::max(params_.lgwin + 1, params_.lgblock + 1); |
- ringbuffer_ = new RingBuffer(ringbuffer_bits, params_.lgblock); |
- |
- commands_ = 0; |
- cmd_alloc_size_ = 0; |
- |
- // Initialize last byte with stream header. |
- EncodeWindowBits(params_.lgwin, &last_byte_, &last_byte_bits_); |
- |
- // Initialize distance cache. |
- dist_cache_[0] = 4; |
- dist_cache_[1] = 11; |
- dist_cache_[2] = 15; |
- dist_cache_[3] = 16; |
- // Save the state of the distance cache in case we need to restore it for |
- // emitting an uncompressed block. |
- memcpy(saved_dist_cache_, dist_cache_, sizeof(dist_cache_)); |
- |
- if (params_.quality == 0) { |
- InitCommandPrefixCodes(cmd_depths_, cmd_bits_, |
- cmd_code_, &cmd_code_numbits_); |
- } else if (params_.quality == 1) { |
- command_buf_ = new uint32_t[kCompressFragmentTwoPassBlockSize]; |
- literal_buf_ = new uint8_t[kCompressFragmentTwoPassBlockSize]; |
- } |
- |
- // Initialize hashers. |
- hash_type_ = std::min(10, params_.quality); |
- hashers_->Init(hash_type_); |
+ EncodeWindowBits(lgwin, &s->last_byte_, &s->last_byte_bits_); |
+ } |
+ |
+ if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { |
+ InitCommandPrefixCodes(s->cmd_depths_, s->cmd_bits_, |
+ s->cmd_code_, &s->cmd_code_numbits_); |
+ } |
+ |
+ /* Initialize hashers. */ |
+ HashersSetup(&s->memory_manager_, &s->hashers_, ChooseHasher(&s->params)); |
+ if (BROTLI_IS_OOM(&s->memory_manager_)) return BROTLI_FALSE; |
+ |
+ s->is_initialized_ = BROTLI_TRUE; |
+ return BROTLI_TRUE; |
+} |
+ |
+static void BrotliEncoderInitState(BrotliEncoderState* s) { |
+ s->params.mode = BROTLI_DEFAULT_MODE; |
+ s->params.quality = BROTLI_DEFAULT_QUALITY; |
+ s->params.lgwin = BROTLI_DEFAULT_WINDOW; |
+ s->params.lgblock = 0; |
+ |
+ s->input_pos_ = 0; |
+ s->num_commands_ = 0; |
+ s->num_literals_ = 0; |
+ s->last_insert_len_ = 0; |
+ s->last_flush_pos_ = 0; |
+ s->last_processed_pos_ = 0; |
+ s->prev_byte_ = 0; |
+ s->prev_byte2_ = 0; |
+ s->storage_size_ = 0; |
+ s->storage_ = 0; |
+ s->large_table_ = NULL; |
+ s->large_table_size_ = 0; |
+ s->cmd_code_numbits_ = 0; |
+ s->command_buf_ = NULL; |
+ s->literal_buf_ = NULL; |
+ s->next_out_ = NULL; |
+ s->available_out_ = 0; |
+ s->total_out_ = 0; |
+ s->stream_state_ = BROTLI_STREAM_PROCESSING; |
+ s->is_last_block_emitted_ = BROTLI_FALSE; |
+ s->is_initialized_ = BROTLI_FALSE; |
+ |
+ InitHashers(&s->hashers_); |
+ |
+ RingBufferInit(&s->ringbuffer_); |
+ |
+ s->commands_ = 0; |
+ s->cmd_alloc_size_ = 0; |
+ |
+ /* Initialize distance cache. */ |
+ s->dist_cache_[0] = 4; |
+ s->dist_cache_[1] = 11; |
+ s->dist_cache_[2] = 15; |
+ s->dist_cache_[3] = 16; |
+ /* Save the state of the distance cache in case we need to restore it for |
+ emitting an uncompressed block. */ |
+ memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->dist_cache_)); |
+} |
+ |
+BrotliEncoderState* BrotliEncoderCreateInstance(brotli_alloc_func alloc_func, |
+ brotli_free_func free_func, |
+ void* opaque) { |
+ BrotliEncoderState* state = 0; |
+ if (!alloc_func && !free_func) { |
+ state = (BrotliEncoderState*)malloc(sizeof(BrotliEncoderState)); |
+ } else if (alloc_func && free_func) { |
+ state = (BrotliEncoderState*)alloc_func(opaque, sizeof(BrotliEncoderState)); |
+ } |
+ if (state == 0) { |
+ /* BROTLI_DUMP(); */ |
+ return 0; |
+ } |
+ BrotliInitMemoryManager( |
+ &state->memory_manager_, alloc_func, free_func, opaque); |
+ BrotliEncoderInitState(state); |
+ return state; |
} |
-BrotliCompressor::~BrotliCompressor(void) { |
- delete[] storage_; |
- free(commands_); |
- delete ringbuffer_; |
- delete hashers_; |
- delete[] large_table_; |
- delete[] command_buf_; |
- delete[] literal_buf_; |
+static void BrotliEncoderCleanupState(BrotliEncoderState* s) { |
+ MemoryManager* m = &s->memory_manager_; |
+ if (BROTLI_IS_OOM(m)) { |
+ BrotliWipeOutMemoryManager(m); |
+ return; |
+ } |
+ BROTLI_FREE(m, s->storage_); |
+ BROTLI_FREE(m, s->commands_); |
+ RingBufferFree(m, &s->ringbuffer_); |
+ DestroyHashers(m, &s->hashers_); |
+ BROTLI_FREE(m, s->large_table_); |
+ BROTLI_FREE(m, s->command_buf_); |
+ BROTLI_FREE(m, s->literal_buf_); |
} |
-void BrotliCompressor::CopyInputToRingBuffer(const size_t input_size, |
- const uint8_t* input_buffer) { |
- ringbuffer_->Write(input_buffer, input_size); |
- input_pos_ += input_size; |
- |
- // TL;DR: If needed, initialize 7 more bytes in the ring buffer to make the |
- // hashing not depend on uninitialized data. This makes compression |
- // deterministic and it prevents uninitialized memory warnings in Valgrind. |
- // Even without erasing, the output would be valid (but nondeterministic). |
- // |
- // Background information: The compressor stores short (at most 8 bytes) |
- // substrings of the input already read in a hash table, and detects |
- // repetitions by looking up such substrings in the hash table. If it |
- // can find a substring, it checks whether the substring is really there |
- // in the ring buffer (or it's just a hash collision). Should the hash |
- // table become corrupt, this check makes sure that the output is |
- // still valid, albeit the compression ratio would be bad. |
- // |
- // The compressor populates the hash table from the ring buffer as it's |
- // reading new bytes from the input. However, at the last few indexes of |
- // the ring buffer, there are not enough bytes to build full-length |
- // substrings from. Since the hash table always contains full-length |
- // substrings, we erase with dummy 0s here to make sure that those |
- // substrings will contain 0s at the end instead of uninitialized |
- // data. |
- // |
- // Please note that erasing is not necessary (because the |
- // memory region is already initialized since he ring buffer |
- // has a `tail' that holds a copy of the beginning,) so we |
- // skip erasing if we have already gone around at least once in |
- // the ring buffer. |
- size_t pos = ringbuffer_->position(); |
- // Only clear during the first round of ringbuffer writes. On |
- // subsequent rounds data in the ringbuffer would be affected. |
- if (pos <= ringbuffer_->mask()) { |
- // This is the first time when the ring buffer is being written. |
- // We clear 7 bytes just after the bytes that have been copied from |
- // the input buffer. |
- // |
- // The ringbuffer has a "tail" that holds a copy of the beginning, |
- // but only once the ring buffer has been fully written once, i.e., |
- // pos <= mask. For the first time, we need to write values |
- // in this tail (where index may be larger than mask), so that |
- // we have exactly defined behavior and don't read un-initialized |
- // memory. Due to performance reasons, hashing reads data using a |
- // LOAD64, which can go 7 bytes beyond the bytes written in the |
- // ringbuffer. |
- memset(ringbuffer_->start() + pos, 0, 7); |
+/* Deinitializes and frees BrotliEncoderState instance. */ |
+void BrotliEncoderDestroyInstance(BrotliEncoderState* state) { |
+ if (!state) { |
+ return; |
+ } else { |
+ MemoryManager* m = &state->memory_manager_; |
+ brotli_free_func free_func = m->free_func; |
+ void* opaque = m->opaque; |
+ BrotliEncoderCleanupState(state); |
+ free_func(opaque, state); |
} |
} |
-void BrotliCompressor::BrotliSetCustomDictionary( |
- const size_t size, const uint8_t* dict) { |
- CopyInputToRingBuffer(size, dict); |
- last_flush_pos_ = size; |
- last_processed_pos_ = size; |
- if (size > 0) { |
- prev_byte_ = dict[size - 1]; |
+/* |
+ Copies the given input data to the internal ring buffer of the compressor. |
+ No processing of the data occurs at this time and this function can be |
+ called multiple times before calling WriteBrotliData() to process the |
+ accumulated input. At most input_block_size() bytes of input data can be |
+ copied to the ring buffer, otherwise the next WriteBrotliData() will fail. |
+ */ |
+static void CopyInputToRingBuffer(BrotliEncoderState* s, |
+ const size_t input_size, |
+ const uint8_t* input_buffer) { |
+ RingBuffer* ringbuffer_ = &s->ringbuffer_; |
+ MemoryManager* m = &s->memory_manager_; |
+ if (!EnsureInitialized(s)) return; |
+ RingBufferWrite(m, input_buffer, input_size, ringbuffer_); |
+ if (BROTLI_IS_OOM(m)) return; |
+ s->input_pos_ += input_size; |
+ |
+ /* TL;DR: If needed, initialize 7 more bytes in the ring buffer to make the |
+ hashing not depend on uninitialized data. This makes compression |
+ deterministic and it prevents uninitialized memory warnings in Valgrind. |
+ Even without erasing, the output would be valid (but nondeterministic). |
+ |
+ Background information: The compressor stores short (at most 8 bytes) |
+ substrings of the input already read in a hash table, and detects |
+ repetitions by looking up such substrings in the hash table. If it |
+ can find a substring, it checks whether the substring is really there |
+ in the ring buffer (or it's just a hash collision). Should the hash |
+ table become corrupt, this check makes sure that the output is |
+ still valid, albeit the compression ratio would be bad. |
+ |
+ The compressor populates the hash table from the ring buffer as it's |
+ reading new bytes from the input. However, at the last few indexes of |
+ the ring buffer, there are not enough bytes to build full-length |
+ substrings from. Since the hash table always contains full-length |
+ substrings, we erase with dummy zeros here to make sure that those |
+ substrings will contain zeros at the end instead of uninitialized |
+ data. |
+ |
+ Please note that erasing is not necessary (because the |
+ memory region is already initialized since he ring buffer |
+ has a `tail' that holds a copy of the beginning,) so we |
+ skip erasing if we have already gone around at least once in |
+ the ring buffer. |
+ |
+ Only clear during the first round of ring-buffer writes. On |
+ subsequent rounds data in the ring-buffer would be affected. */ |
+ if (ringbuffer_->pos_ <= ringbuffer_->mask_) { |
+ /* This is the first time when the ring buffer is being written. |
+ We clear 7 bytes just after the bytes that have been copied from |
+ the input buffer. |
+ |
+ The ring-buffer has a "tail" that holds a copy of the beginning, |
+ but only once the ring buffer has been fully written once, i.e., |
+ pos <= mask. For the first time, we need to write values |
+ in this tail (where index may be larger than mask), so that |
+ we have exactly defined behavior and don't read uninitialized |
+ memory. Due to performance reasons, hashing reads data using a |
+ LOAD64, which can go 7 bytes beyond the bytes written in the |
+ ring-buffer. */ |
+ memset(ringbuffer_->buffer_ + ringbuffer_->pos_, 0, 7); |
+ } |
+} |
+ |
+void BrotliEncoderSetCustomDictionary(BrotliEncoderState* s, size_t size, |
+ const uint8_t* dict) { |
+ size_t max_dict_size = MaxBackwardLimit(s->params.lgwin); |
+ size_t dict_size = size; |
+ MemoryManager* m = &s->memory_manager_; |
+ |
+ if (!EnsureInitialized(s)) return; |
+ |
+ if (dict_size == 0 || |
+ s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY || |
+ s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { |
+ return; |
+ } |
+ if (size > max_dict_size) { |
+ dict += size - max_dict_size; |
+ dict_size = max_dict_size; |
+ } |
+ CopyInputToRingBuffer(s, dict_size, dict); |
+ s->last_flush_pos_ = dict_size; |
+ s->last_processed_pos_ = dict_size; |
+ if (dict_size > 0) { |
+ s->prev_byte_ = dict[dict_size - 1]; |
} |
- if (size > 1) { |
- prev_byte2_ = dict[size - 2]; |
+ if (dict_size > 1) { |
+ s->prev_byte2_ = dict[dict_size - 2]; |
} |
- hashers_->PrependCustomDictionary(hash_type_, params_.lgwin, size, dict); |
+ HashersPrependCustomDictionary(m, &s->hashers_, &s->params, dict_size, dict); |
+ if (BROTLI_IS_OOM(m)) return; |
} |
-bool BrotliCompressor::WriteBrotliData(const bool is_last, |
- const bool force_flush, |
- size_t* out_size, |
- uint8_t** output) { |
- const uint64_t delta = input_pos_ - last_processed_pos_; |
- const uint8_t* data = ringbuffer_->start(); |
- const uint32_t mask = ringbuffer_->mask(); |
+/* Marks all input as processed. |
+ Returns true if position wrapping occurs. */ |
+static BROTLI_BOOL UpdateLastProcessedPos(BrotliEncoderState* s) { |
+ uint32_t wrapped_last_processed_pos = WrapPosition(s->last_processed_pos_); |
+ uint32_t wrapped_input_pos = WrapPosition(s->input_pos_); |
+ s->last_processed_pos_ = s->input_pos_; |
+ return TO_BROTLI_BOOL(wrapped_input_pos < wrapped_last_processed_pos); |
+} |
+ |
+/* |
+ Processes the accumulated input data and sets |*out_size| to the length of |
+ the new output meta-block, or to zero if no new output meta-block has been |
+ created (in this case the processed input data is buffered internally). |
+ If |*out_size| is positive, |*output| points to the start of the output |
+ data. If |is_last| or |force_flush| is BROTLI_TRUE, an output meta-block is |
+ always created. However, until |is_last| is BROTLI_TRUE encoder may retain up |
+ to 7 bits of the last byte of output. To force encoder to dump the remaining |
+ bits use WriteMetadata() to append an empty meta-data block. |
+ Returns BROTLI_FALSE if the size of the input data is larger than |
+ input_block_size(). |
+ */ |
+static BROTLI_BOOL EncodeData( |
+ BrotliEncoderState* s, const BROTLI_BOOL is_last, |
+ const BROTLI_BOOL force_flush, size_t* out_size, uint8_t** output) { |
+ const uint64_t delta = UnprocessedInputSize(s); |
+ const uint32_t bytes = (uint32_t)delta; |
+ const uint32_t wrapped_last_processed_pos = |
+ WrapPosition(s->last_processed_pos_); |
+ uint8_t* data; |
+ uint32_t mask; |
+ MemoryManager* m = &s->memory_manager_; |
+ |
+ if (!EnsureInitialized(s)) return BROTLI_FALSE; |
+ data = s->ringbuffer_.buffer_; |
+ mask = s->ringbuffer_.mask_; |
/* Adding more blocks after "last" block is forbidden. */ |
- if (is_last_block_emitted_) return false; |
- if (is_last) is_last_block_emitted_ = 1; |
+ if (s->is_last_block_emitted_) return BROTLI_FALSE; |
+ if (is_last) s->is_last_block_emitted_ = BROTLI_TRUE; |
- if (delta > input_block_size()) { |
- return false; |
+ if (delta > InputBlockSize(s)) { |
+ return BROTLI_FALSE; |
+ } |
+ if (s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY && |
+ !s->command_buf_) { |
+ s->command_buf_ = |
+ BROTLI_ALLOC(m, uint32_t, kCompressFragmentTwoPassBlockSize); |
+ s->literal_buf_ = |
+ BROTLI_ALLOC(m, uint8_t, kCompressFragmentTwoPassBlockSize); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
} |
- const uint32_t bytes = static_cast<uint32_t>(delta); |
- if (params_.quality <= 1) { |
+ if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY || |
+ s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { |
+ uint8_t* storage; |
+ size_t storage_ix = s->last_byte_bits_; |
+ size_t table_size; |
+ int* table; |
+ |
if (delta == 0 && !is_last) { |
- // We have no new input data and we don't have to finish the stream, so |
- // nothing to do. |
+ /* We have no new input data and we don't have to finish the stream, so |
+ nothing to do. */ |
*out_size = 0; |
- return true; |
+ return BROTLI_TRUE; |
} |
- const size_t max_out_size = 2 * bytes + 500; |
- uint8_t* storage = GetBrotliStorage(max_out_size); |
- storage[0] = last_byte_; |
- size_t storage_ix = last_byte_bits_; |
- size_t table_size; |
- int* table = GetHashTable(params_.quality, bytes, &table_size); |
- if (params_.quality == 0) { |
+ storage = GetBrotliStorage(s, 2 * bytes + 502); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ storage[0] = s->last_byte_; |
+ table = GetHashTable(s, s->params.quality, bytes, &table_size); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { |
BrotliCompressFragmentFast( |
- &data[WrapPosition(last_processed_pos_) & mask], |
+ m, &data[wrapped_last_processed_pos & mask], |
bytes, is_last, |
table, table_size, |
- cmd_depths_, cmd_bits_, |
- &cmd_code_numbits_, cmd_code_, |
+ s->cmd_depths_, s->cmd_bits_, |
+ &s->cmd_code_numbits_, s->cmd_code_, |
&storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
} else { |
BrotliCompressFragmentTwoPass( |
- &data[WrapPosition(last_processed_pos_) & mask], |
+ m, &data[wrapped_last_processed_pos & mask], |
bytes, is_last, |
- command_buf_, literal_buf_, |
+ s->command_buf_, s->literal_buf_, |
table, table_size, |
&storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
} |
- last_byte_ = storage[storage_ix >> 3]; |
- last_byte_bits_ = storage_ix & 7u; |
- last_processed_pos_ = input_pos_; |
+ s->last_byte_ = storage[storage_ix >> 3]; |
+ s->last_byte_bits_ = storage_ix & 7u; |
+ UpdateLastProcessedPos(s); |
*output = &storage[0]; |
*out_size = storage_ix >> 3; |
- return true; |
- } |
- |
- // Theoretical max number of commands is 1 per 2 bytes. |
- size_t newsize = num_commands_ + bytes / 2 + 1; |
- if (newsize > cmd_alloc_size_) { |
- // Reserve a bit more memory to allow merging with a next block |
- // without realloc: that would impact speed. |
- newsize += (bytes / 4) + 16; |
- cmd_alloc_size_ = newsize; |
- commands_ = |
- static_cast<Command*>(realloc(commands_, sizeof(Command) * newsize)); |
- } |
- |
- CreateBackwardReferences(bytes, WrapPosition(last_processed_pos_), |
- is_last, data, mask, |
- params_.quality, |
- params_.lgwin, |
- hashers_, |
- hash_type_, |
- dist_cache_, |
- &last_insert_len_, |
- &commands_[num_commands_], |
- &num_commands_, |
- &num_literals_); |
- |
- size_t max_length = std::min<size_t>(mask + 1, 1u << kMaxInputBlockBits); |
- const size_t max_literals = max_length / 8; |
- const size_t max_commands = max_length / 8; |
- if (!is_last && !force_flush && |
- (params_.quality >= kMinQualityForBlockSplit || |
- (num_literals_ + num_commands_ < kMaxNumDelayedSymbols)) && |
- num_literals_ < max_literals && |
- num_commands_ < max_commands && |
- input_pos_ + input_block_size() <= last_flush_pos_ + max_length) { |
- // Merge with next input block. Everything will happen later. |
- last_processed_pos_ = input_pos_; |
- *out_size = 0; |
- return true; |
+ return BROTLI_TRUE; |
} |
- // Create the last insert-only command. |
- if (last_insert_len_ > 0) { |
- brotli::Command cmd(last_insert_len_); |
- commands_[num_commands_++] = cmd; |
- num_literals_ += last_insert_len_; |
- last_insert_len_ = 0; |
+ { |
+ /* Theoretical max number of commands is 1 per 2 bytes. */ |
+ size_t newsize = s->num_commands_ + bytes / 2 + 1; |
+ if (newsize > s->cmd_alloc_size_) { |
+ Command* new_commands; |
+ /* Reserve a bit more memory to allow merging with a next block |
+ without reallocation: that would impact speed. */ |
+ newsize += (bytes / 4) + 16; |
+ s->cmd_alloc_size_ = newsize; |
+ new_commands = BROTLI_ALLOC(m, Command, newsize); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ if (s->commands_) { |
+ memcpy(new_commands, s->commands_, sizeof(Command) * s->num_commands_); |
+ BROTLI_FREE(m, s->commands_); |
+ } |
+ s->commands_ = new_commands; |
+ } |
} |
- if (!is_last && input_pos_ == last_flush_pos_) { |
- // We have no new input data and we don't have to finish the stream, so |
- // nothing to do. |
- *out_size = 0; |
- return true; |
- } |
- assert(input_pos_ >= last_flush_pos_); |
- assert(input_pos_ > last_flush_pos_ || is_last); |
- assert(input_pos_ - last_flush_pos_ <= 1u << 24); |
- const uint32_t metablock_size = |
- static_cast<uint32_t>(input_pos_ - last_flush_pos_); |
- const size_t max_out_size = 2 * metablock_size + 500; |
- uint8_t* storage = GetBrotliStorage(max_out_size); |
- storage[0] = last_byte_; |
- size_t storage_ix = last_byte_bits_; |
- bool font_mode = params_.mode == BrotliParams::MODE_FONT; |
- WriteMetaBlockInternal( |
- data, mask, last_flush_pos_, metablock_size, is_last, params_.quality, |
- font_mode, prev_byte_, prev_byte2_, num_literals_, num_commands_, |
- commands_, saved_dist_cache_, dist_cache_, &storage_ix, storage); |
- last_byte_ = storage[storage_ix >> 3]; |
- last_byte_bits_ = storage_ix & 7u; |
- last_flush_pos_ = input_pos_; |
- last_processed_pos_ = input_pos_; |
- if (last_flush_pos_ > 0) { |
- prev_byte_ = data[(static_cast<uint32_t>(last_flush_pos_) - 1) & mask]; |
- } |
- if (last_flush_pos_ > 1) { |
- prev_byte2_ = data[(static_cast<uint32_t>(last_flush_pos_) - 2) & mask]; |
- } |
- num_commands_ = 0; |
- num_literals_ = 0; |
- // Save the state of the distance cache in case we need to restore it for |
- // emitting an uncompressed block. |
- memcpy(saved_dist_cache_, dist_cache_, sizeof(dist_cache_)); |
- *output = &storage[0]; |
- *out_size = storage_ix >> 3; |
- return true; |
-} |
+ BrotliCreateBackwardReferences(m, bytes, wrapped_last_processed_pos, |
+ is_last, data, mask, |
+ &s->params, |
+ &s->hashers_, |
+ s->dist_cache_, |
+ &s->last_insert_len_, |
+ &s->commands_[s->num_commands_], |
+ &s->num_commands_, |
+ &s->num_literals_); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ |
+ { |
+ const size_t max_length = MaxMetablockSize(&s->params); |
+ const size_t max_literals = max_length / 8; |
+ const size_t max_commands = max_length / 8; |
+ const size_t processed_bytes = (size_t)(s->input_pos_ - s->last_flush_pos_); |
+ /* If maximal possible additional block doesn't fit metablock, flush now. */ |
+ /* TODO: Postpone decision until next block arrives? */ |
+ const BROTLI_BOOL next_input_fits_metablock = TO_BROTLI_BOOL( |
+ processed_bytes + InputBlockSize(s) <= max_length); |
+ /* If block splitting is not used, then flush as soon as there is some |
+ amount of commands / literals produced. */ |
+ const BROTLI_BOOL should_flush = TO_BROTLI_BOOL( |
+ s->params.quality < MIN_QUALITY_FOR_BLOCK_SPLIT && |
+ s->num_literals_ + s->num_commands_ >= MAX_NUM_DELAYED_SYMBOLS); |
+ if (!is_last && !force_flush && !should_flush && |
+ next_input_fits_metablock && |
+ s->num_literals_ < max_literals && |
+ s->num_commands_ < max_commands) { |
+ /* Merge with next input block. Everything will happen later. */ |
+ if (UpdateLastProcessedPos(s)) { |
+ HashersReset(&s->hashers_, ChooseHasher(&s->params)); |
+ } |
+ *out_size = 0; |
+ return BROTLI_TRUE; |
+ } |
+ } |
+ |
+ /* Create the last insert-only command. */ |
+ if (s->last_insert_len_ > 0) { |
+ InitInsertCommand(&s->commands_[s->num_commands_++], s->last_insert_len_); |
+ s->num_literals_ += s->last_insert_len_; |
+ s->last_insert_len_ = 0; |
+ } |
-bool BrotliCompressor::WriteMetaBlock(const size_t input_size, |
- const uint8_t* input_buffer, |
- const bool is_last, |
- size_t* encoded_size, |
- uint8_t* encoded_buffer) { |
- CopyInputToRingBuffer(input_size, input_buffer); |
- size_t out_size = 0; |
- uint8_t* output; |
- if (!WriteBrotliData(is_last, /* force_flush = */ true, &out_size, &output) || |
- out_size > *encoded_size) { |
- return false; |
- } |
- if (out_size > 0) { |
- memcpy(encoded_buffer, output, out_size); |
- } |
- *encoded_size = out_size; |
- return true; |
+ if (!is_last && s->input_pos_ == s->last_flush_pos_) { |
+ /* We have no new input data and we don't have to finish the stream, so |
+ nothing to do. */ |
+ *out_size = 0; |
+ return BROTLI_TRUE; |
+ } |
+ assert(s->input_pos_ >= s->last_flush_pos_); |
+ assert(s->input_pos_ > s->last_flush_pos_ || is_last); |
+ assert(s->input_pos_ - s->last_flush_pos_ <= 1u << 24); |
+ { |
+ const uint32_t metablock_size = |
+ (uint32_t)(s->input_pos_ - s->last_flush_pos_); |
+ uint8_t* storage = GetBrotliStorage(s, 2 * metablock_size + 502); |
+ size_t storage_ix = s->last_byte_bits_; |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ storage[0] = s->last_byte_; |
+ WriteMetaBlockInternal( |
+ m, data, mask, s->last_flush_pos_, metablock_size, is_last, |
+ &s->params, s->prev_byte_, s->prev_byte2_, |
+ s->num_literals_, s->num_commands_, s->commands_, s->saved_dist_cache_, |
+ s->dist_cache_, &storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ s->last_byte_ = storage[storage_ix >> 3]; |
+ s->last_byte_bits_ = storage_ix & 7u; |
+ s->last_flush_pos_ = s->input_pos_; |
+ if (UpdateLastProcessedPos(s)) { |
+ HashersReset(&s->hashers_, ChooseHasher(&s->params)); |
+ } |
+ if (s->last_flush_pos_ > 0) { |
+ s->prev_byte_ = data[((uint32_t)s->last_flush_pos_ - 1) & mask]; |
+ } |
+ if (s->last_flush_pos_ > 1) { |
+ s->prev_byte2_ = data[(uint32_t)(s->last_flush_pos_ - 2) & mask]; |
+ } |
+ s->num_commands_ = 0; |
+ s->num_literals_ = 0; |
+ /* Save the state of the distance cache in case we need to restore it for |
+ emitting an uncompressed block. */ |
+ memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->dist_cache_)); |
+ *output = &storage[0]; |
+ *out_size = storage_ix >> 3; |
+ return BROTLI_TRUE; |
+ } |
} |
-bool BrotliCompressor::WriteMetadata(const size_t input_size, |
- const uint8_t* input_buffer, |
- const bool is_last, |
- size_t* encoded_size, |
- uint8_t* encoded_buffer) { |
- if (input_size > (1 << 24) || input_size + 6 > *encoded_size) { |
- return false; |
- } |
- uint64_t hdr_buffer_data[2]; |
- uint8_t* hdr_buffer = reinterpret_cast<uint8_t*>(&hdr_buffer_data[0]); |
- size_t storage_ix = last_byte_bits_; |
- hdr_buffer[0] = last_byte_; |
- WriteBits(1, 0, &storage_ix, hdr_buffer); |
- WriteBits(2, 3, &storage_ix, hdr_buffer); |
- WriteBits(1, 0, &storage_ix, hdr_buffer); |
- if (input_size == 0) { |
- WriteBits(2, 0, &storage_ix, hdr_buffer); |
- *encoded_size = (storage_ix + 7u) >> 3; |
- memcpy(encoded_buffer, hdr_buffer, *encoded_size); |
+/* Dumps remaining output bits and metadata header to |header|. |
+ Returns number of produced bytes. |
+ REQUIRED: |header| should be 8-byte aligned and at least 16 bytes long. |
+ REQUIRED: |block_size| <= (1 << 24). */ |
+static size_t WriteMetadataHeader( |
+ BrotliEncoderState* s, const size_t block_size, uint8_t* header) { |
+ size_t storage_ix; |
+ storage_ix = s->last_byte_bits_; |
+ header[0] = s->last_byte_; |
+ s->last_byte_ = 0; |
+ s->last_byte_bits_ = 0; |
+ |
+ BrotliWriteBits(1, 0, &storage_ix, header); |
+ BrotliWriteBits(2, 3, &storage_ix, header); |
+ BrotliWriteBits(1, 0, &storage_ix, header); |
+ if (block_size == 0) { |
+ BrotliWriteBits(2, 0, &storage_ix, header); |
} else { |
- uint32_t nbits = (input_size == 1) ? 0 : (Log2FloorNonZero( |
- static_cast<uint32_t>(input_size) - 1) + 1); |
+ uint32_t nbits = (block_size == 1) ? 0 : |
+ (Log2FloorNonZero((uint32_t)block_size - 1) + 1); |
uint32_t nbytes = (nbits + 7) / 8; |
- WriteBits(2, nbytes, &storage_ix, hdr_buffer); |
- WriteBits(8 * nbytes, input_size - 1, &storage_ix, hdr_buffer); |
- size_t hdr_size = (storage_ix + 7u) >> 3; |
- memcpy(encoded_buffer, hdr_buffer, hdr_size); |
- memcpy(&encoded_buffer[hdr_size], input_buffer, input_size); |
- *encoded_size = hdr_size + input_size; |
- } |
- if (is_last) { |
- encoded_buffer[(*encoded_size)++] = 3; |
- } |
- last_byte_ = 0; |
- last_byte_bits_ = 0; |
- return true; |
+ BrotliWriteBits(2, nbytes, &storage_ix, header); |
+ BrotliWriteBits(8 * nbytes, block_size - 1, &storage_ix, header); |
+ } |
+ return (storage_ix + 7u) >> 3; |
} |
-bool BrotliCompressor::FinishStream( |
+static BROTLI_BOOL BrotliCompressBufferQuality10( |
+ int lgwin, size_t input_size, const uint8_t* input_buffer, |
size_t* encoded_size, uint8_t* encoded_buffer) { |
- return WriteMetaBlock(0, NULL, true, encoded_size, encoded_buffer); |
-} |
+ MemoryManager memory_manager; |
+ MemoryManager* m = &memory_manager; |
-static int BrotliCompressBufferQuality10(int lgwin, |
- size_t input_size, |
- const uint8_t* input_buffer, |
- size_t* encoded_size, |
- uint8_t* encoded_buffer) { |
- const size_t mask = std::numeric_limits<size_t>::max() >> 1; |
- assert(input_size <= mask + 1); |
- const size_t max_backward_limit = (1 << lgwin) - 16; |
+ const size_t mask = BROTLI_SIZE_MAX >> 1; |
+ const size_t max_backward_limit = MaxBackwardLimit(lgwin); |
int dist_cache[4] = { 4, 11, 15, 16 }; |
int saved_dist_cache[4] = { 4, 11, 15, 16 }; |
- int ok = 1; |
+ BROTLI_BOOL ok = BROTLI_TRUE; |
const size_t max_out_size = *encoded_size; |
size_t total_out_size = 0; |
uint8_t last_byte; |
uint8_t last_byte_bits; |
- EncodeWindowBits(lgwin, &last_byte, &last_byte_bits); |
+ H10* hasher; |
+ |
+ const size_t hasher_eff_size = |
+ BROTLI_MIN(size_t, input_size, max_backward_limit + BROTLI_WINDOW_GAP); |
- Hashers::H10* hasher = new Hashers::H10; |
- const size_t hasher_eff_size = std::min(input_size, max_backward_limit + 16); |
- hasher->Init(lgwin, 0, hasher_eff_size, true); |
+ BrotliEncoderParams params; |
- const int lgblock = std::min(18, lgwin); |
- const int lgmetablock = std::min(24, lgwin + 1); |
- const size_t max_block_size = static_cast<size_t>(1) << lgblock; |
- const size_t max_metablock_size = static_cast<size_t>(1) << lgmetablock; |
+ const int lgmetablock = BROTLI_MIN(int, 24, lgwin + 1); |
+ size_t max_block_size; |
+ const size_t max_metablock_size = (size_t)1 << lgmetablock; |
const size_t max_literals_per_metablock = max_metablock_size / 8; |
const size_t max_commands_per_metablock = max_metablock_size / 8; |
size_t metablock_start = 0; |
uint8_t prev_byte = 0; |
uint8_t prev_byte2 = 0; |
+ |
+ params.mode = BROTLI_DEFAULT_MODE; |
+ params.quality = 10; |
+ params.lgwin = lgwin; |
+ params.lgblock = 0; |
+ SanitizeParams(¶ms); |
+ params.lgblock = ComputeLgBlock(¶ms); |
+ max_block_size = (size_t)1 << params.lgblock; |
+ |
+ BrotliInitMemoryManager(m, 0, 0, 0); |
+ |
+ assert(input_size <= mask + 1); |
+ EncodeWindowBits(lgwin, &last_byte, &last_byte_bits); |
+ hasher = BROTLI_ALLOC(m, H10, 1); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
+ InitializeH10(hasher); |
+ InitH10(m, hasher, input_buffer, ¶ms, 0, hasher_eff_size, 1); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
+ |
while (ok && metablock_start < input_size) { |
const size_t metablock_end = |
- std::min(input_size, metablock_start + max_metablock_size); |
+ BROTLI_MIN(size_t, input_size, metablock_start + max_metablock_size); |
const size_t expected_num_commands = |
(metablock_end - metablock_start) / 12 + 16; |
Command* commands = 0; |
@@ -819,38 +1072,52 @@ static int BrotliCompressBufferQuality10(int lgwin, |
size_t num_literals = 0; |
size_t metablock_size = 0; |
size_t cmd_alloc_size = 0; |
- |
- for (size_t block_start = metablock_start; block_start < metablock_end; ) { |
- size_t block_size = std::min(metablock_end - block_start, max_block_size); |
- ZopfliNode* nodes = new ZopfliNode[block_size + 1]; |
- std::vector<uint32_t> path; |
- hasher->StitchToPreviousBlock(block_size, block_start, |
- input_buffer, mask); |
- ZopfliComputeShortestPath(block_size, block_start, input_buffer, mask, |
- max_backward_limit, dist_cache, |
- hasher, nodes, &path); |
- // We allocate a command buffer in the first iteration of this loop that |
- // will be likely big enough for the whole metablock, so that for most |
- // inputs we will not have to reallocate in later iterations. We do the |
- // allocation here and not before the loop, because if the input is small, |
- // this will be allocated after the zopfli cost model is freed, so this |
- // will not increase peak memory usage. |
- // TODO: If the first allocation is too small, increase command |
- // buffer size exponentially. |
- size_t new_cmd_alloc_size = std::max(expected_num_commands, |
- num_commands + path.size() + 1); |
+ BROTLI_BOOL is_last; |
+ uint8_t* storage; |
+ size_t storage_ix; |
+ |
+ size_t block_start; |
+ for (block_start = metablock_start; block_start < metablock_end; ) { |
+ size_t block_size = |
+ BROTLI_MIN(size_t, metablock_end - block_start, max_block_size); |
+ ZopfliNode* nodes = BROTLI_ALLOC(m, ZopfliNode, block_size + 1); |
+ size_t path_size; |
+ size_t new_cmd_alloc_size; |
+ if (BROTLI_IS_OOM(m)) goto oom; |
+ BrotliInitZopfliNodes(nodes, block_size + 1); |
+ StitchToPreviousBlockH10(hasher, block_size, block_start, |
+ input_buffer, mask); |
+ path_size = BrotliZopfliComputeShortestPath( |
+ m, block_size, block_start, input_buffer, mask, ¶ms, |
+ max_backward_limit, dist_cache, hasher, nodes); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
+ /* We allocate a command buffer in the first iteration of this loop that |
+ will be likely big enough for the whole metablock, so that for most |
+ inputs we will not have to reallocate in later iterations. We do the |
+ allocation here and not before the loop, because if the input is small, |
+ this will be allocated after the Zopfli cost model is freed, so this |
+ will not increase peak memory usage. |
+ TODO: If the first allocation is too small, increase command |
+ buffer size exponentially. */ |
+ new_cmd_alloc_size = BROTLI_MAX(size_t, expected_num_commands, |
+ num_commands + path_size + 1); |
if (cmd_alloc_size != new_cmd_alloc_size) { |
+ Command* new_commands = BROTLI_ALLOC(m, Command, new_cmd_alloc_size); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
cmd_alloc_size = new_cmd_alloc_size; |
- commands = static_cast<Command*>( |
- realloc(commands, cmd_alloc_size * sizeof(Command))); |
+ if (commands) { |
+ memcpy(new_commands, commands, sizeof(Command) * num_commands); |
+ BROTLI_FREE(m, commands); |
+ } |
+ commands = new_commands; |
} |
- ZopfliCreateCommands(block_size, block_start, max_backward_limit, path, |
- &nodes[0], dist_cache, &last_insert_len, |
- &commands[num_commands], &num_literals); |
- num_commands += path.size(); |
+ BrotliZopfliCreateCommands(block_size, block_start, max_backward_limit, |
+ &nodes[0], dist_cache, &last_insert_len, |
+ &commands[num_commands], &num_literals); |
+ num_commands += path_size; |
block_start += block_size; |
metablock_size += block_size; |
- delete[] nodes; |
+ BROTLI_FREE(m, nodes); |
if (num_literals > max_literals_per_metablock || |
num_commands > max_commands_per_metablock) { |
break; |
@@ -858,323 +1125,577 @@ static int BrotliCompressBufferQuality10(int lgwin, |
} |
if (last_insert_len > 0) { |
- Command cmd(last_insert_len); |
- commands[num_commands++] = cmd; |
+ InitInsertCommand(&commands[num_commands++], last_insert_len); |
num_literals += last_insert_len; |
} |
- const bool is_last = (metablock_start + metablock_size == input_size); |
- uint8_t* storage = NULL; |
- size_t storage_ix = last_byte_bits; |
+ is_last = TO_BROTLI_BOOL(metablock_start + metablock_size == input_size); |
+ storage = NULL; |
+ storage_ix = last_byte_bits; |
if (metablock_size == 0) { |
- // Write the ISLAST and ISEMPTY bits. |
- storage = new uint8_t[16]; |
+ /* Write the ISLAST and ISEMPTY bits. */ |
+ storage = BROTLI_ALLOC(m, uint8_t, 16); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
storage[0] = last_byte; |
- WriteBits(2, 3, &storage_ix, storage); |
+ BrotliWriteBits(2, 3, &storage_ix, storage); |
storage_ix = (storage_ix + 7u) & ~7u; |
} else if (!ShouldCompress(input_buffer, mask, metablock_start, |
metablock_size, num_literals, num_commands)) { |
- // Restore the distance cache, as its last update by |
- // CreateBackwardReferences is now unused. |
+ /* Restore the distance cache, as its last update by |
+ CreateBackwardReferences is now unused. */ |
memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); |
- storage = new uint8_t[metablock_size + 16]; |
+ storage = BROTLI_ALLOC(m, uint8_t, metablock_size + 16); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
storage[0] = last_byte; |
- StoreUncompressedMetaBlock(is_last, input_buffer, |
- metablock_start, mask, metablock_size, |
- &storage_ix, storage); |
+ BrotliStoreUncompressedMetaBlock(is_last, input_buffer, |
+ metablock_start, mask, metablock_size, |
+ &storage_ix, storage); |
} else { |
uint32_t num_direct_distance_codes = 0; |
uint32_t distance_postfix_bits = 0; |
- MetaBlockSplit mb; |
ContextType literal_context_mode = CONTEXT_UTF8; |
- if (!IsMostlyUTF8( |
- input_buffer, metablock_start, mask, metablock_size, |
- kMinUTF8Ratio)) { |
+ MetaBlockSplit mb; |
+ InitMetaBlockSplit(&mb); |
+ if (!BrotliIsMostlyUTF8(input_buffer, metablock_start, mask, |
+ metablock_size, kMinUTF8Ratio)) { |
literal_context_mode = CONTEXT_SIGNED; |
} |
- BuildMetaBlock(input_buffer, metablock_start, mask, |
- prev_byte, prev_byte2, |
- commands, num_commands, |
- literal_context_mode, |
- &mb); |
- OptimizeHistograms(num_direct_distance_codes, |
- distance_postfix_bits, |
- &mb); |
- const size_t max_out_metablock_size = 2 * metablock_size + 500; |
- storage = new uint8_t[max_out_metablock_size]; |
+ BrotliBuildMetaBlock(m, input_buffer, metablock_start, mask, ¶ms, |
+ prev_byte, prev_byte2, |
+ commands, num_commands, |
+ literal_context_mode, |
+ &mb); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
+ BrotliOptimizeHistograms(num_direct_distance_codes, |
+ distance_postfix_bits, |
+ &mb); |
+ storage = BROTLI_ALLOC(m, uint8_t, 2 * metablock_size + 502); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
storage[0] = last_byte; |
- StoreMetaBlock(input_buffer, metablock_start, metablock_size, mask, |
- prev_byte, prev_byte2, |
- is_last, |
- num_direct_distance_codes, |
- distance_postfix_bits, |
- literal_context_mode, |
- commands, num_commands, |
- mb, |
- &storage_ix, storage); |
+ BrotliStoreMetaBlock(m, input_buffer, metablock_start, metablock_size, |
+ mask, prev_byte, prev_byte2, |
+ is_last, |
+ num_direct_distance_codes, |
+ distance_postfix_bits, |
+ literal_context_mode, |
+ commands, num_commands, |
+ &mb, |
+ &storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) goto oom; |
if (metablock_size + 4 < (storage_ix >> 3)) { |
- // Restore the distance cache and last byte. |
+ /* Restore the distance cache and last byte. */ |
memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); |
storage[0] = last_byte; |
storage_ix = last_byte_bits; |
- StoreUncompressedMetaBlock(is_last, input_buffer, |
- metablock_start, mask, |
- metablock_size, &storage_ix, storage); |
+ BrotliStoreUncompressedMetaBlock(is_last, input_buffer, |
+ metablock_start, mask, |
+ metablock_size, &storage_ix, storage); |
} |
+ DestroyMetaBlockSplit(m, &mb); |
} |
last_byte = storage[storage_ix >> 3]; |
last_byte_bits = storage_ix & 7u; |
metablock_start += metablock_size; |
prev_byte = input_buffer[metablock_start - 1]; |
prev_byte2 = input_buffer[metablock_start - 2]; |
- // Save the state of the distance cache in case we need to restore it for |
- // emitting an uncompressed block. |
+ /* Save the state of the distance cache in case we need to restore it for |
+ emitting an uncompressed block. */ |
memcpy(saved_dist_cache, dist_cache, 4 * sizeof(dist_cache[0])); |
- const size_t out_size = storage_ix >> 3; |
- total_out_size += out_size; |
- if (total_out_size <= max_out_size) { |
- memcpy(encoded_buffer, storage, out_size); |
- encoded_buffer += out_size; |
- } else { |
- ok = 0; |
+ { |
+ const size_t out_size = storage_ix >> 3; |
+ total_out_size += out_size; |
+ if (total_out_size <= max_out_size) { |
+ memcpy(encoded_buffer, storage, out_size); |
+ encoded_buffer += out_size; |
+ } else { |
+ ok = BROTLI_FALSE; |
+ } |
} |
- delete[] storage; |
- free(commands); |
+ BROTLI_FREE(m, storage); |
+ BROTLI_FREE(m, commands); |
} |
*encoded_size = total_out_size; |
- delete hasher; |
+ CleanupH10(m, hasher); |
+ BROTLI_FREE(m, hasher); |
return ok; |
+ |
+oom: |
+ BrotliWipeOutMemoryManager(m); |
+ return BROTLI_FALSE; |
} |
-int BrotliCompressBuffer(BrotliParams params, |
- size_t input_size, |
- const uint8_t* input_buffer, |
- size_t* encoded_size, |
- uint8_t* encoded_buffer) { |
- if (*encoded_size == 0) { |
- // Output buffer needs at least one byte. |
- return 0; |
+size_t BrotliEncoderMaxCompressedSize(size_t input_size) { |
+ /* [window bits / empty metadata] + N * [uncompressed] + [last empty] */ |
+ size_t num_large_blocks = input_size >> 24; |
+ size_t tail = input_size - (num_large_blocks << 24); |
+ size_t tail_overhead = (tail > (1 << 20)) ? 4 : 3; |
+ size_t overhead = 2 + (4 * num_large_blocks) + tail_overhead + 1; |
+ size_t result = input_size + overhead; |
+ if (input_size == 0) return 1; |
+ return (result < input_size) ? 0 : result; |
+} |
+ |
+/* Wraps data to uncompressed brotli stream with minimal window size. |
+ |output| should point at region with at least BrotliEncoderMaxCompressedSize |
+ addressable bytes. |
+ Returns the length of stream. */ |
+static size_t MakeUncompressedStream( |
+ const uint8_t* input, size_t input_size, uint8_t* output) { |
+ size_t size = input_size; |
+ size_t result = 0; |
+ size_t offset = 0; |
+ if (input_size == 0) { |
+ output[0] = 6; |
+ return 1; |
+ } |
+ output[result++] = 0x21; /* window bits = 10, is_last = false */ |
+ output[result++] = 0x03; /* empty metadata, padding */ |
+ while (size > 0) { |
+ uint32_t nibbles = 0; |
+ uint32_t chunk_size; |
+ uint32_t bits; |
+ chunk_size = (size > (1u << 24)) ? (1u << 24) : (uint32_t)size; |
+ if (chunk_size > (1u << 16)) nibbles = (chunk_size > (1u << 20)) ? 2 : 1; |
+ bits = |
+ (nibbles << 1) | ((chunk_size - 1) << 3) | (1u << (19 + 4 * nibbles)); |
+ output[result++] = (uint8_t)bits; |
+ output[result++] = (uint8_t)(bits >> 8); |
+ output[result++] = (uint8_t)(bits >> 16); |
+ if (nibbles == 2) output[result++] = (uint8_t)(bits >> 24); |
+ memcpy(&output[result], &input[offset], chunk_size); |
+ result += chunk_size; |
+ offset += chunk_size; |
+ size -= chunk_size; |
+ } |
+ output[result++] = 3; |
+ return result; |
+} |
+ |
+BROTLI_BOOL BrotliEncoderCompress( |
+ int quality, int lgwin, BrotliEncoderMode mode, size_t input_size, |
+ const uint8_t* input_buffer, size_t* encoded_size, |
+ uint8_t* encoded_buffer) { |
+ BrotliEncoderState* s; |
+ size_t out_size = *encoded_size; |
+ const uint8_t* input_start = input_buffer; |
+ uint8_t* output_start = encoded_buffer; |
+ size_t max_out_size = BrotliEncoderMaxCompressedSize(input_size); |
+ if (out_size == 0) { |
+ /* Output buffer needs at least one byte. */ |
+ return BROTLI_FALSE; |
} |
if (input_size == 0) { |
- // Handle the special case of empty input. |
+ /* Handle the special case of empty input. */ |
*encoded_size = 1; |
*encoded_buffer = 6; |
- return 1; |
+ return BROTLI_TRUE; |
} |
- if (params.quality == 10) { |
- // TODO: Implement this direct path for all quality levels. |
- const int lgwin = std::min(24, std::max(16, params.lgwin)); |
- return BrotliCompressBufferQuality10(lgwin, input_size, input_buffer, |
- encoded_size, encoded_buffer); |
+ if (quality == 10) { |
+ /* TODO: Implement this direct path for all quality levels. */ |
+ const int lg_win = BROTLI_MIN(int, BROTLI_MAX_WINDOW_BITS, |
+ BROTLI_MAX(int, 16, lgwin)); |
+ int ok = BrotliCompressBufferQuality10(lg_win, input_size, input_buffer, |
+ encoded_size, encoded_buffer); |
+ if (!ok || (max_out_size && *encoded_size > max_out_size)) { |
+ goto fallback; |
+ } |
+ return BROTLI_TRUE; |
} |
- BrotliMemIn in(input_buffer, input_size); |
- BrotliMemOut out(encoded_buffer, *encoded_size); |
- if (!BrotliCompress(params, &in, &out)) { |
- return 0; |
+ |
+ s = BrotliEncoderCreateInstance(0, 0, 0); |
+ if (!s) { |
+ return BROTLI_FALSE; |
+ } else { |
+ size_t available_in = input_size; |
+ const uint8_t* next_in = input_buffer; |
+ size_t available_out = *encoded_size; |
+ uint8_t* next_out = encoded_buffer; |
+ size_t total_out = 0; |
+ BROTLI_BOOL result = BROTLI_FALSE; |
+ BrotliEncoderSetParameter(s, BROTLI_PARAM_QUALITY, (uint32_t)quality); |
+ BrotliEncoderSetParameter(s, BROTLI_PARAM_LGWIN, (uint32_t)lgwin); |
+ BrotliEncoderSetParameter(s, BROTLI_PARAM_MODE, (uint32_t)mode); |
+ result = BrotliEncoderCompressStream(s, BROTLI_OPERATION_FINISH, |
+ &available_in, &next_in, &available_out, &next_out, &total_out); |
+ if (!BrotliEncoderIsFinished(s)) result = 0; |
+ *encoded_size = total_out; |
+ BrotliEncoderDestroyInstance(s); |
+ if (!result || (max_out_size && *encoded_size > max_out_size)) { |
+ goto fallback; |
+ } |
+ return BROTLI_TRUE; |
+ } |
+fallback: |
+ *encoded_size = 0; |
+ if (!max_out_size) return BROTLI_FALSE; |
+ if (out_size >= max_out_size) { |
+ *encoded_size = |
+ MakeUncompressedStream(input_start, input_size, output_start); |
+ return BROTLI_TRUE; |
} |
- *encoded_size = out.position(); |
- return 1; |
+ return BROTLI_FALSE; |
} |
-static bool BrotliInIsFinished(BrotliIn* r) { |
- size_t read_bytes; |
- return r->Read(0, &read_bytes) == NULL; |
+static void InjectBytePaddingBlock(BrotliEncoderState* s) { |
+ uint32_t seal = s->last_byte_; |
+ size_t seal_bits = s->last_byte_bits_; |
+ uint8_t* destination; |
+ s->last_byte_ = 0; |
+ s->last_byte_bits_ = 0; |
+ /* is_last = 0, data_nibbles = 11, reserved = 0, meta_nibbles = 00 */ |
+ seal |= 0x6u << seal_bits; |
+ seal_bits += 6; |
+ /* If we have already created storage, then append to it. |
+ Storage is valid until next block is being compressed. */ |
+ if (s->next_out_) { |
+ destination = s->next_out_ + s->available_out_; |
+ } else { |
+ destination = s->tiny_buf_.u8; |
+ s->next_out_ = destination; |
+ } |
+ destination[0] = (uint8_t)seal; |
+ if (seal_bits > 8) destination[1] = (uint8_t)(seal >> 8); |
+ s->available_out_ += (seal_bits + 7) >> 3; |
} |
-static const uint8_t* BrotliInReadAndCheckEnd(const size_t block_size, |
- BrotliIn* r, |
- size_t* bytes_read, |
- bool* is_last) { |
- *bytes_read = 0; |
- const uint8_t* data = reinterpret_cast<const uint8_t*>( |
- r->Read(block_size, bytes_read)); |
- assert((data == NULL) == (*bytes_read == 0)); |
- *is_last = BrotliInIsFinished(r); |
- return data; |
-} |
+/* Injects padding bits or pushes compressed data to output. |
+ Returns false if nothing is done. */ |
+static BROTLI_BOOL InjectFlushOrPushOutput(BrotliEncoderState* s, |
+ size_t* available_out, uint8_t** next_out, size_t* total_out) { |
+ if (s->stream_state_ == BROTLI_STREAM_FLUSH_REQUESTED && |
+ s->last_byte_bits_ != 0) { |
+ InjectBytePaddingBlock(s); |
+ return BROTLI_TRUE; |
+ } |
-static bool CopyOneBlockToRingBuffer(BrotliIn* r, |
- BrotliCompressor* compressor, |
- size_t* bytes_read, |
- bool* is_last) { |
- const size_t block_size = compressor->input_block_size(); |
- const uint8_t* data = BrotliInReadAndCheckEnd(block_size, r, |
- bytes_read, is_last); |
- if (data == NULL) { |
- return *is_last; |
- } |
- compressor->CopyInputToRingBuffer(*bytes_read, data); |
- |
- // Read more bytes until block_size is filled or an EOF (data == NULL) is |
- // received. This is useful to get deterministic compressed output for the |
- // same input no matter how r->Read splits the input to chunks. |
- for (size_t remaining = block_size - *bytes_read; remaining > 0; ) { |
- size_t more_bytes_read = 0; |
- data = BrotliInReadAndCheckEnd(remaining, r, &more_bytes_read, is_last); |
- if (data == NULL) { |
- return *is_last; |
- } |
- compressor->CopyInputToRingBuffer(more_bytes_read, data); |
- *bytes_read += more_bytes_read; |
- remaining -= more_bytes_read; |
+ if (s->available_out_ != 0 && *available_out != 0) { |
+ size_t copy_output_size = |
+ BROTLI_MIN(size_t, s->available_out_, *available_out); |
+ memcpy(*next_out, s->next_out_, copy_output_size); |
+ *next_out += copy_output_size; |
+ *available_out -= copy_output_size; |
+ s->next_out_ += copy_output_size; |
+ s->available_out_ -= copy_output_size; |
+ s->total_out_ += copy_output_size; |
+ if (total_out) *total_out = s->total_out_; |
+ return BROTLI_TRUE; |
} |
- return true; |
-} |
+ return BROTLI_FALSE; |
+} |
-int BrotliCompress(BrotliParams params, BrotliIn* in, BrotliOut* out) { |
- return BrotliCompressWithCustomDictionary(0, 0, params, in, out); |
+static void CheckFlushComplete(BrotliEncoderState* s) { |
+ if (s->stream_state_ == BROTLI_STREAM_FLUSH_REQUESTED && |
+ s->available_out_ == 0) { |
+ s->stream_state_ = BROTLI_STREAM_PROCESSING; |
+ s->next_out_ = 0; |
+ } |
} |
-// Reads the provided input in 'block_size' blocks. Only the last read can be |
-// smaller than 'block_size'. |
-class BrotliBlockReader { |
- public: |
- explicit BrotliBlockReader(size_t block_size) |
- : block_size_(block_size), buf_(NULL) {} |
- ~BrotliBlockReader(void) { delete[] buf_; } |
- |
- const uint8_t* Read(BrotliIn* in, size_t* bytes_read, bool* is_last) { |
- *bytes_read = 0; |
- const uint8_t* data = BrotliInReadAndCheckEnd(block_size_, in, |
- bytes_read, is_last); |
- if (data == NULL || *bytes_read == block_size_ || *is_last) { |
- // If we could get the whole block in one read, or it is the last block, |
- // we just return the pointer to the data without copying. |
- return data; |
+static BROTLI_BOOL BrotliEncoderCompressStreamFast( |
+ BrotliEncoderState* s, BrotliEncoderOperation op, size_t* available_in, |
+ const uint8_t** next_in, size_t* available_out, uint8_t** next_out, |
+ size_t* total_out) { |
+ const size_t block_size_limit = (size_t)1 << s->params.lgwin; |
+ const size_t buf_size = BROTLI_MIN(size_t, kCompressFragmentTwoPassBlockSize, |
+ BROTLI_MIN(size_t, *available_in, block_size_limit)); |
+ uint32_t* tmp_command_buf = NULL; |
+ uint32_t* command_buf = NULL; |
+ uint8_t* tmp_literal_buf = NULL; |
+ uint8_t* literal_buf = NULL; |
+ MemoryManager* m = &s->memory_manager_; |
+ if (s->params.quality != FAST_ONE_PASS_COMPRESSION_QUALITY && |
+ s->params.quality != FAST_TWO_PASS_COMPRESSION_QUALITY) { |
+ return BROTLI_FALSE; |
+ } |
+ if (s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { |
+ if (!s->command_buf_ && buf_size == kCompressFragmentTwoPassBlockSize) { |
+ s->command_buf_ = |
+ BROTLI_ALLOC(m, uint32_t, kCompressFragmentTwoPassBlockSize); |
+ s->literal_buf_ = |
+ BROTLI_ALLOC(m, uint8_t, kCompressFragmentTwoPassBlockSize); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
} |
- // If the data comes in smaller chunks, we need to copy it into an internal |
- // buffer until we get a whole block or reach the last chunk. |
- if (buf_ == NULL) { |
- buf_ = new uint8_t[block_size_]; |
+ if (s->command_buf_) { |
+ command_buf = s->command_buf_; |
+ literal_buf = s->literal_buf_; |
+ } else { |
+ tmp_command_buf = BROTLI_ALLOC(m, uint32_t, buf_size); |
+ tmp_literal_buf = BROTLI_ALLOC(m, uint8_t, buf_size); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ command_buf = tmp_command_buf; |
+ literal_buf = tmp_literal_buf; |
} |
- memcpy(buf_, data, *bytes_read); |
- do { |
- size_t cur_bytes_read = 0; |
- data = BrotliInReadAndCheckEnd(block_size_ - *bytes_read, in, |
- &cur_bytes_read, is_last); |
- if (data == NULL) { |
- return *is_last ? buf_ : NULL; |
- } |
- memcpy(&buf_[*bytes_read], data, cur_bytes_read); |
- *bytes_read += cur_bytes_read; |
- } while (*bytes_read < block_size_ && !*is_last); |
- return buf_; |
- } |
- |
- private: |
- const size_t block_size_; |
- uint8_t* buf_; |
-}; |
- |
-int BrotliCompressWithCustomDictionary(size_t dictsize, const uint8_t* dict, |
- BrotliParams params, |
- BrotliIn* in, BrotliOut* out) { |
- if (params.quality <= 1) { |
- const int quality = std::max(0, params.quality); |
- const int lgwin = std::min(kMaxWindowBits, |
- std::max(kMinWindowBits, params.lgwin)); |
- uint8_t* storage = NULL; |
- int* table = NULL; |
- uint32_t* command_buf = NULL; |
- uint8_t* literal_buf = NULL; |
- uint8_t cmd_depths[128]; |
- uint16_t cmd_bits[128]; |
- uint8_t cmd_code[512]; |
- size_t cmd_code_numbits; |
- if (quality == 0) { |
- InitCommandPrefixCodes(cmd_depths, cmd_bits, cmd_code, &cmd_code_numbits); |
+ } |
+ |
+ while (BROTLI_TRUE) { |
+ if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) { |
+ continue; |
} |
- uint8_t last_byte; |
- uint8_t last_byte_bits; |
- EncodeWindowBits(lgwin, &last_byte, &last_byte_bits); |
- BrotliBlockReader r(1u << lgwin); |
- int ok = 1; |
- bool is_last = false; |
- while (ok && !is_last) { |
- // Read next block of input. |
- size_t bytes; |
- const uint8_t* data = r.Read(in, &bytes, &is_last); |
- if (data == NULL) { |
- if (!is_last) { |
- ok = 0; |
- break; |
- } |
- assert(bytes == 0); |
- } |
- // Set up output storage. |
- const size_t max_out_size = 2 * bytes + 500; |
- if (storage == NULL) { |
- storage = new uint8_t[max_out_size]; |
+ |
+ /* Compress block only when internal output buffer is empty, stream is not |
+ finished, there is no pending flush request, and there is either |
+ additional input or pending operation. */ |
+ if (s->available_out_ == 0 && |
+ s->stream_state_ == BROTLI_STREAM_PROCESSING && |
+ (*available_in != 0 || op != BROTLI_OPERATION_PROCESS)) { |
+ size_t block_size = BROTLI_MIN(size_t, block_size_limit, *available_in); |
+ BROTLI_BOOL is_last = |
+ (*available_in == block_size) && (op == BROTLI_OPERATION_FINISH); |
+ BROTLI_BOOL force_flush = |
+ (*available_in == block_size) && (op == BROTLI_OPERATION_FLUSH); |
+ size_t max_out_size = 2 * block_size + 502; |
+ BROTLI_BOOL inplace = BROTLI_TRUE; |
+ uint8_t* storage = NULL; |
+ size_t storage_ix = s->last_byte_bits_; |
+ size_t table_size; |
+ int* table; |
+ |
+ if (force_flush && block_size == 0) { |
+ s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED; |
+ continue; |
} |
- storage[0] = last_byte; |
- size_t storage_ix = last_byte_bits; |
- // Set up hash table. |
- size_t htsize = HashTableSize(MaxHashTableSize(quality), bytes); |
- if (table == NULL) { |
- table = new int[htsize]; |
+ if (max_out_size <= *available_out) { |
+ storage = *next_out; |
+ } else { |
+ inplace = BROTLI_FALSE; |
+ storage = GetBrotliStorage(s, max_out_size); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
} |
- memset(table, 0, htsize * sizeof(table[0])); |
- // Set up command and literal buffers for two pass mode. |
- if (quality == 1 && command_buf == NULL) { |
- size_t buf_size = std::min(bytes, kCompressFragmentTwoPassBlockSize); |
- command_buf = new uint32_t[buf_size]; |
- literal_buf = new uint8_t[buf_size]; |
+ storage[0] = s->last_byte_; |
+ table = GetHashTable(s, s->params.quality, block_size, &table_size); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ |
+ if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { |
+ BrotliCompressFragmentFast(m, *next_in, block_size, is_last, table, |
+ table_size, s->cmd_depths_, s->cmd_bits_, &s->cmd_code_numbits_, |
+ s->cmd_code_, &storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
+ } else { |
+ BrotliCompressFragmentTwoPass(m, *next_in, block_size, is_last, |
+ command_buf, literal_buf, table, table_size, |
+ &storage_ix, storage); |
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; |
} |
- // Do the actual compression. |
- if (quality == 0) { |
- BrotliCompressFragmentFast(data, bytes, is_last, table, htsize, |
- cmd_depths, cmd_bits, |
- &cmd_code_numbits, cmd_code, |
- &storage_ix, storage); |
+ *next_in += block_size; |
+ *available_in -= block_size; |
+ if (inplace) { |
+ size_t out_bytes = storage_ix >> 3; |
+ assert(out_bytes <= *available_out); |
+ assert((storage_ix & 7) == 0 || out_bytes < *available_out); |
+ *next_out += out_bytes; |
+ *available_out -= out_bytes; |
+ s->total_out_ += out_bytes; |
+ if (total_out) *total_out = s->total_out_; |
} else { |
- BrotliCompressFragmentTwoPass(data, bytes, is_last, |
- command_buf, literal_buf, |
- table, htsize, |
- &storage_ix, storage); |
+ size_t out_bytes = storage_ix >> 3; |
+ s->next_out_ = storage; |
+ s->available_out_ = out_bytes; |
} |
- // Save last bytes to stitch it together with the next output block. |
- last_byte = storage[storage_ix >> 3]; |
- last_byte_bits = storage_ix & 7u; |
- // Write output block. |
- size_t out_bytes = storage_ix >> 3; |
- if (out_bytes > 0 && !out->Write(storage, out_bytes)) { |
- ok = 0; |
+ s->last_byte_ = storage[storage_ix >> 3]; |
+ s->last_byte_bits_ = storage_ix & 7u; |
+ |
+ if (force_flush) s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED; |
+ if (is_last) s->stream_state_ = BROTLI_STREAM_FINISHED; |
+ continue; |
+ } |
+ break; |
+ } |
+ BROTLI_FREE(m, tmp_command_buf); |
+ BROTLI_FREE(m, tmp_literal_buf); |
+ CheckFlushComplete(s); |
+ return BROTLI_TRUE; |
+} |
+ |
+static BROTLI_BOOL ProcessMetadata( |
+ BrotliEncoderState* s, size_t* available_in, const uint8_t** next_in, |
+ size_t* available_out, uint8_t** next_out, size_t* total_out) { |
+ if (*available_in > (1u << 24)) return BROTLI_FALSE; |
+ /* Switch to metadata block workflow, if required. */ |
+ if (s->stream_state_ == BROTLI_STREAM_PROCESSING) { |
+ s->remaining_metadata_bytes_ = (uint32_t)*available_in; |
+ s->stream_state_ = BROTLI_STREAM_METADATA_HEAD; |
+ } |
+ if (s->stream_state_ != BROTLI_STREAM_METADATA_HEAD && |
+ s->stream_state_ != BROTLI_STREAM_METADATA_BODY) { |
+ return BROTLI_FALSE; |
+ } |
+ |
+ while (BROTLI_TRUE) { |
+ if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) { |
+ continue; |
+ } |
+ if (s->available_out_ != 0) break; |
+ |
+ if (s->input_pos_ != s->last_flush_pos_) { |
+ BROTLI_BOOL result = EncodeData(s, BROTLI_FALSE, BROTLI_TRUE, |
+ &s->available_out_, &s->next_out_); |
+ if (!result) return BROTLI_FALSE; |
+ continue; |
+ } |
+ |
+ if (s->stream_state_ == BROTLI_STREAM_METADATA_HEAD) { |
+ s->next_out_ = s->tiny_buf_.u8; |
+ s->available_out_ = |
+ WriteMetadataHeader(s, s->remaining_metadata_bytes_, s->next_out_); |
+ s->stream_state_ = BROTLI_STREAM_METADATA_BODY; |
+ continue; |
+ } else { |
+ /* Exit workflow only when there is no more input and no more output. |
+ Otherwise client may continue producing empty metadata blocks. */ |
+ if (s->remaining_metadata_bytes_ == 0) { |
+ s->remaining_metadata_bytes_ = BROTLI_UINT32_MAX; |
+ s->stream_state_ = BROTLI_STREAM_PROCESSING; |
break; |
} |
+ if (*available_out) { |
+ /* Directly copy input to output. */ |
+ uint32_t copy = (uint32_t)BROTLI_MIN( |
+ size_t, s->remaining_metadata_bytes_, *available_out); |
+ memcpy(*next_out, *next_in, copy); |
+ *next_in += copy; |
+ *available_in -= copy; |
+ s->remaining_metadata_bytes_ -= copy; |
+ *next_out += copy; |
+ *available_out -= copy; |
+ } else { |
+ /* This guarantees progress in "TakeOutput" workflow. */ |
+ uint32_t copy = BROTLI_MIN(uint32_t, s->remaining_metadata_bytes_, 16); |
+ s->next_out_ = s->tiny_buf_.u8; |
+ memcpy(s->next_out_, *next_in, copy); |
+ *next_in += copy; |
+ *available_in -= copy; |
+ s->remaining_metadata_bytes_ -= copy; |
+ s->available_out_ = copy; |
+ } |
+ continue; |
} |
- delete[] storage; |
- delete[] table; |
- delete[] command_buf; |
- delete[] literal_buf; |
- return ok; |
- } |
- |
- size_t in_bytes = 0; |
- size_t out_bytes = 0; |
- uint8_t* output = NULL; |
- bool final_block = false; |
- BrotliCompressor compressor(params); |
- if (dictsize != 0) compressor.BrotliSetCustomDictionary(dictsize, dict); |
- while (!final_block) { |
- if (!CopyOneBlockToRingBuffer(in, &compressor, &in_bytes, &final_block)) { |
- return false; |
+ } |
+ |
+ return BROTLI_TRUE; |
+} |
+ |
+BROTLI_BOOL BrotliEncoderCompressStream( |
+ BrotliEncoderState* s, BrotliEncoderOperation op, size_t* available_in, |
+ const uint8_t** next_in, size_t* available_out,uint8_t** next_out, |
+ size_t* total_out) { |
+ if (!EnsureInitialized(s)) return BROTLI_FALSE; |
+ |
+ /* Unfinished metadata block; check requirements. */ |
+ if (s->remaining_metadata_bytes_ != BROTLI_UINT32_MAX) { |
+ if (*available_in != s->remaining_metadata_bytes_) return BROTLI_FALSE; |
+ if (op != BROTLI_OPERATION_EMIT_METADATA) return BROTLI_FALSE; |
+ } |
+ |
+ if (op == BROTLI_OPERATION_EMIT_METADATA) { |
+ return ProcessMetadata( |
+ s, available_in, next_in, available_out, next_out, total_out); |
+ } |
+ |
+ if (s->stream_state_ == BROTLI_STREAM_METADATA_HEAD || |
+ s->stream_state_ == BROTLI_STREAM_METADATA_BODY) { |
+ return BROTLI_FALSE; |
+ } |
+ |
+ if (s->stream_state_ != BROTLI_STREAM_PROCESSING && *available_in != 0) { |
+ return BROTLI_FALSE; |
+ } |
+ if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY || |
+ s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { |
+ return BrotliEncoderCompressStreamFast(s, op, available_in, next_in, |
+ available_out, next_out, total_out); |
+ } |
+ while (BROTLI_TRUE) { |
+ size_t remaining_block_size = RemainingInputBlockSize(s); |
+ |
+ if (remaining_block_size != 0 && *available_in != 0) { |
+ size_t copy_input_size = |
+ BROTLI_MIN(size_t, remaining_block_size, *available_in); |
+ CopyInputToRingBuffer(s, copy_input_size, *next_in); |
+ *next_in += copy_input_size; |
+ *available_in -= copy_input_size; |
+ continue; |
} |
- out_bytes = 0; |
- if (!compressor.WriteBrotliData(final_block, |
- /* force_flush = */ false, |
- &out_bytes, &output)) { |
- return false; |
+ |
+ if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) { |
+ continue; |
} |
- if (out_bytes > 0 && !out->Write(output, out_bytes)) { |
- return false; |
+ |
+ /* Compress data only when internal output buffer is empty, stream is not |
+ finished and there is no pending flush request. */ |
+ if (s->available_out_ == 0 && |
+ s->stream_state_ == BROTLI_STREAM_PROCESSING) { |
+ if (remaining_block_size == 0 || op != BROTLI_OPERATION_PROCESS) { |
+ BROTLI_BOOL is_last = TO_BROTLI_BOOL( |
+ (*available_in == 0) && op == BROTLI_OPERATION_FINISH); |
+ BROTLI_BOOL force_flush = TO_BROTLI_BOOL( |
+ (*available_in == 0) && op == BROTLI_OPERATION_FLUSH); |
+ BROTLI_BOOL result = EncodeData(s, is_last, force_flush, |
+ &s->available_out_, &s->next_out_); |
+ if (!result) return BROTLI_FALSE; |
+ if (force_flush) s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED; |
+ if (is_last) s->stream_state_ = BROTLI_STREAM_FINISHED; |
+ continue; |
+ } |
} |
+ break; |
} |
- return true; |
+ CheckFlushComplete(s); |
+ return BROTLI_TRUE; |
+} |
+ |
+BROTLI_BOOL BrotliEncoderIsFinished(BrotliEncoderState* s) { |
+ return TO_BROTLI_BOOL(s->stream_state_ == BROTLI_STREAM_FINISHED && |
+ !BrotliEncoderHasMoreOutput(s)); |
} |
+BROTLI_BOOL BrotliEncoderHasMoreOutput(BrotliEncoderState* s) { |
+ return TO_BROTLI_BOOL(s->available_out_ != 0); |
+} |
+ |
+const uint8_t* BrotliEncoderTakeOutput(BrotliEncoderState* s, size_t* size) { |
+ size_t consumed_size = s->available_out_; |
+ uint8_t* result = s->next_out_; |
+ if (*size) { |
+ consumed_size = BROTLI_MIN(size_t, *size, s->available_out_); |
+ } |
+ if (consumed_size) { |
+ s->next_out_ += consumed_size; |
+ s->available_out_ -= consumed_size; |
+ s->total_out_ += consumed_size; |
+ CheckFlushComplete(s); |
+ *size = consumed_size; |
+ } else { |
+ *size = 0; |
+ result = 0; |
+ } |
+ return result; |
+} |
+ |
+uint32_t BrotliEncoderVersion(void) { |
+ return BROTLI_VERSION; |
+} |
+ |
+ |
+/* DEPRECATED >>> */ |
+size_t BrotliEncoderInputBlockSize(BrotliEncoderState* s) { |
+ return InputBlockSize(s); |
+} |
+void BrotliEncoderCopyInputToRingBuffer(BrotliEncoderState* s, |
+ const size_t input_size, |
+ const uint8_t* input_buffer) { |
+ CopyInputToRingBuffer(s, input_size, input_buffer); |
+} |
+BROTLI_BOOL BrotliEncoderWriteData( |
+ BrotliEncoderState* s, const BROTLI_BOOL is_last, |
+ const BROTLI_BOOL force_flush, size_t* out_size, uint8_t** output) { |
+ return EncodeData(s, is_last, force_flush, out_size, output); |
+} |
+/* <<< DEPRECATED */ |
-} // namespace brotli |
+#if defined(__cplusplus) || defined(c_plusplus) |
+} /* extern "C" */ |
+#endif |