Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1636)

Unified Diff: third_party/brotli/enc/encode.c

Issue 2537133002: Update brotli to v1.0.0-snapshot. (Closed)
Patch Set: Fixed typo Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « third_party/brotli/enc/encode.h ('k') | third_party/brotli/enc/encode.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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(&params);
+ params.lgblock = ComputeLgBlock(&params);
+ 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, &params, 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, &params,
+ 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, &params,
+ 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
« no previous file with comments | « third_party/brotli/enc/encode.h ('k') | third_party/brotli/enc/encode.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698