summaryrefslogtreecommitdiff
path: root/dviware/dvisvgm/libs/brotli/enc/encode.c
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2023-11-16 03:01:15 +0000
committerNorbert Preining <norbert@preining.info>2023-11-16 03:01:15 +0000
commite0db3f0709a737e7258fd40a7cbfe9a461ea0756 (patch)
treee81cfc35b6602ffceefa73b8971ce3b94312820a /dviware/dvisvgm/libs/brotli/enc/encode.c
parentf5460c92605f1b3b17448b27ce53375157c3e4b1 (diff)
CTAN sync 202311160301
Diffstat (limited to 'dviware/dvisvgm/libs/brotli/enc/encode.c')
-rw-r--r--dviware/dvisvgm/libs/brotli/enc/encode.c875
1 files changed, 472 insertions, 403 deletions
diff --git a/dviware/dvisvgm/libs/brotli/enc/encode.c b/dviware/dvisvgm/libs/brotli/enc/encode.c
index e77009e39a..95ff2eaf50 100644
--- a/dviware/dvisvgm/libs/brotli/enc/encode.c
+++ b/dviware/dvisvgm/libs/brotli/enc/encode.c
@@ -7,6 +7,8 @@
/* Implementation of Brotli compressor. */
#include <brotli/encode.h>
+#include <brotli/shared_dictionary.h>
+#include <brotli/types.h>
#include <stdlib.h> /* free, malloc */
#include <string.h> /* memcpy, memset */
@@ -15,24 +17,26 @@
#include "../common/context.h"
#include "../common/platform.h"
#include "../common/version.h"
-#include "./backward_references.h"
-#include "./backward_references_hq.h"
-#include "./bit_cost.h"
-#include "./brotli_bit_stream.h"
-#include "./compress_fragment.h"
-#include "./compress_fragment_two_pass.h"
-#include "./encoder_dict.h"
-#include "./entropy_encode.h"
-#include "./fast_log.h"
-#include "./hash.h"
-#include "./histogram.h"
-#include "./memory.h"
-#include "./metablock.h"
-#include "./prefix.h"
-#include "./quality.h"
-#include "./ringbuffer.h"
-#include "./utf8_util.h"
-#include "./write_bits.h"
+#include "backward_references.h"
+#include "backward_references_hq.h"
+#include "bit_cost.h"
+#include "brotli_bit_stream.h"
+#include "compress_fragment.h"
+#include "compress_fragment_two_pass.h"
+#include "dictionary_hash.h"
+#include "encoder_dict.h"
+#include "entropy_encode.h"
+#include "fast_log.h"
+#include "hash.h"
+#include "histogram.h"
+#include "memory.h"
+#include "metablock.h"
+#include "prefix.h"
+#include "state.h"
+#include "quality.h"
+#include "ringbuffer.h"
+#include "utf8_util.h"
+#include "write_bits.h"
#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
@@ -40,94 +44,6 @@ extern "C" {
#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 enum BrotliEncoderFlintState {
- BROTLI_FLINT_NEEDS_2_BYTES = 2,
- BROTLI_FLINT_NEEDS_1_BYTE = 1,
- BROTLI_FLINT_WAITING_FOR_PROCESSING = 0,
- BROTLI_FLINT_WAITING_FOR_FLUSHING = -1,
- BROTLI_FLINT_DONE = -2
-} BrotliEncoderFlintState;
-
-typedef struct BrotliEncoderStateStruct {
- BrotliEncoderParams params;
-
- MemoryManager memory_manager_;
-
- 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_[BROTLI_NUM_DISTANCE_SHORT_CODES];
- int saved_dist_cache_[4];
- uint16_t last_bytes_;
- uint8_t last_bytes_bits_;
- /* "Flint" is a tiny uncompressed block emitted before the continuation
- block to unwire literal context from previous data. Despite being int8_t,
- field is actually BrotliEncoderFlintState enum. */
- int8_t flint_;
- uint8_t prev_byte_;
- uint8_t prev_byte2_;
- size_t storage_size_;
- uint8_t* storage_;
-
- Hasher hasher_;
-
- /* 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 size_t InputBlockSize(BrotliEncoderState* s) {
return (size_t)1 << s->params.lgblock;
}
@@ -147,7 +63,7 @@ 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. */
+ /* TODO(eustas): Validate/clamp parameters here. */
switch (p) {
case BROTLI_PARAM_MODE:
state->params.mode = (BrotliEncoderMode)value;
@@ -283,11 +199,9 @@ static void EncodeWindowBits(int lgwin, BROTLI_BOOL large_window,
}
}
+/* TODO(eustas): move to compress_fragment.c? */
/* 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],
- size_t* cmd_code_numbits) {
+static void InitCommandPrefixCodes(BrotliOnePassArena* s) {
static const uint8_t kDefaultCommandDepths[128] = {
0, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8,
0, 0, 0, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7,
@@ -320,13 +234,13 @@ static void InitCommandPrefixCodes(uint8_t cmd_depths[128],
0x46, 0xe1, 0xb0, 0xd0, 0x4e, 0xb2, 0xf7, 0x04, 0x00,
};
static const size_t kDefaultCommandCodeNumBits = 448;
- COPY_ARRAY(cmd_depths, kDefaultCommandDepths);
- COPY_ARRAY(cmd_bits, kDefaultCommandBits);
+ COPY_ARRAY(s->cmd_depth, kDefaultCommandDepths);
+ COPY_ARRAY(s->cmd_bits, kDefaultCommandBits);
/* Initialize the pre-compressed form of the command and distance prefix
codes. */
- COPY_ARRAY(cmd_code, kDefaultCommandCode);
- *cmd_code_numbits = kDefaultCommandCodeNumBits;
+ COPY_ARRAY(s->cmd_code, kDefaultCommandCode);
+ s->cmd_code_numbits = kDefaultCommandCodeNumBits;
}
/* Decide about the context map based on the ability of the prediction
@@ -401,7 +315,8 @@ static void ChooseContextMap(int quality,
first 5 bits of literals. */
static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input,
size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint,
- size_t* num_literal_contexts, const uint32_t** literal_context_map) {
+ size_t* num_literal_contexts, const uint32_t** literal_context_map,
+ uint32_t* arena) {
static const uint32_t kStaticContextMapComplexUTF8[64] = {
11, 11, 12, 12, /* 0 special */
0, 0, 0, 0, /* 4 lf */
@@ -426,16 +341,17 @@ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input,
return BROTLI_FALSE;
} else {
const size_t end_pos = start_pos + length;
- /* To make entropy calculations faster and to fit on the stack, we collect
- histograms over the 5 most significant bits of literals. One histogram
+ /* To make entropy calculations faster, we collect histograms
+ over the 5 most significant bits of literals. One histogram
without context and 13 additional histograms for each context value. */
- uint32_t combined_histo[32] = { 0 };
- uint32_t context_histo[13][32] = { { 0 } };
+ uint32_t* BROTLI_RESTRICT const combined_histo = arena;
+ uint32_t* BROTLI_RESTRICT const context_histo = arena + 32;
uint32_t total = 0;
double entropy[3];
size_t dummy;
size_t i;
ContextLut utf8_lut = BROTLI_CONTEXT_LUT(CONTEXT_UTF8);
+ memset(arena, 0, sizeof(arena[0]) * 32 * 14);
for (; start_pos + 64 <= end_pos; start_pos += 4096) {
const size_t stride_end_pos = start_pos + 64;
uint8_t prev2 = input[start_pos & mask];
@@ -449,7 +365,7 @@ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input,
BROTLI_CONTEXT(prev1, prev2, utf8_lut)];
++total;
++combined_histo[literal >> 3];
- ++context_histo[context][literal >> 3];
+ ++context_histo[(context << 5) + (literal >> 3)];
prev2 = prev1;
prev1 = literal;
}
@@ -457,7 +373,7 @@ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input,
entropy[1] = ShannonEntropy(combined_histo, 32, &dummy);
entropy[2] = 0;
for (i = 0; i < 13; ++i) {
- entropy[2] += ShannonEntropy(&context_histo[i][0], 32, &dummy);
+ entropy[2] += ShannonEntropy(context_histo + (i << 5), 32, &dummy);
}
entropy[0] = 1.0 / (double)total;
entropy[1] *= entropy[0];
@@ -481,19 +397,21 @@ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input,
static void DecideOverLiteralContextModeling(const uint8_t* input,
size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint,
- size_t* num_literal_contexts, const uint32_t** literal_context_map) {
+ size_t* num_literal_contexts, const uint32_t** literal_context_map,
+ uint32_t* arena) {
if (quality < MIN_QUALITY_FOR_CONTEXT_MODELING || length < 64) {
return;
} else if (ShouldUseComplexStaticContextMap(
input, start_pos, length, mask, quality, size_hint,
- num_literal_contexts, literal_context_map)) {
+ num_literal_contexts, literal_context_map, arena)) {
/* Context map was already set, nothing else to do. */
} 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 };
+ uint32_t* BROTLI_RESTRICT const bigram_prefix_histo = arena;
+ memset(bigram_prefix_histo, 0, sizeof(arena[0]) * 9);
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;
@@ -513,7 +431,7 @@ static void DecideOverLiteralContextModeling(const uint8_t* input,
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) {
- /* TODO: find more precise minimal block overhead. */
+ /* TODO(eustas): find more precise minimal block overhead. */
if (bytes <= 2) return BROTLI_FALSE;
if (num_commands < (bytes >> 8) + 2) {
if ((double)num_literals > 0.99 * (double)bytes) {
@@ -613,10 +531,14 @@ static void WriteMetaBlockInternal(MemoryManager* m,
size_t num_literal_contexts = 1;
const uint32_t* literal_context_map = NULL;
if (!params->disable_literal_context_modeling) {
+ /* TODO(eustas): pull to higher level and reuse. */
+ uint32_t* arena = BROTLI_ALLOC(m, uint32_t, 14 * 32);
+ if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(arena)) return;
DecideOverLiteralContextModeling(
data, wrapped_last_flush_pos, bytes, mask, params->quality,
params->size_hint, &num_literal_contexts,
- &literal_context_map);
+ &literal_context_map, arena);
+ BROTLI_FREE(m, arena);
}
BrotliBuildMetaBlockGreedy(m, data, wrapped_last_flush_pos, mask,
prev_byte, prev_byte2, literal_context_lut, num_literal_contexts,
@@ -681,12 +603,13 @@ static void ChooseDistanceParams(BrotliEncoderParams* params) {
}
}
- BrotliInitDistanceParams(
- params, distance_postfix_bits, num_direct_distance_codes);
+ BrotliInitDistanceParams(&params->dist, distance_postfix_bits,
+ num_direct_distance_codes, params->large_window);
}
static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s) {
- if (BROTLI_IS_OOM(&s->memory_manager_)) return BROTLI_FALSE;
+ MemoryManager* m = &s->memory_manager_;
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
if (s->is_initialized_) return BROTLI_TRUE;
s->last_bytes_bits_ = 0;
@@ -728,8 +651,12 @@ static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s) {
}
if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) {
- InitCommandPrefixCodes(s->cmd_depths_, s->cmd_bits_,
- s->cmd_code_, &s->cmd_code_numbits_);
+ s->one_pass_arena_ = BROTLI_ALLOC(m, BrotliOnePassArena, 1);
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
+ InitCommandPrefixCodes(s->one_pass_arena_);
+ } else if (s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) {
+ s->two_pass_arena_ = BROTLI_ALLOC(m, BrotliTwoPassArena, 1);
+ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
}
s->is_initialized_ = BROTLI_TRUE;
@@ -745,7 +672,7 @@ static void BrotliEncoderInitParams(BrotliEncoderParams* params) {
params->stream_offset = 0;
params->size_hint = 0;
params->disable_literal_context_modeling = BROTLI_FALSE;
- BrotliInitEncoderDictionary(&params->dictionary);
+ BrotliInitSharedEncoderDictionary(&params->dictionary);
params->dist.distance_postfix_bits = 0;
params->dist.num_direct_distance_codes = 0;
params->dist.alphabet_size_max =
@@ -754,6 +681,11 @@ static void BrotliEncoderInitParams(BrotliEncoderParams* params) {
params->dist.max_distance = BROTLI_MAX_DISTANCE;
}
+static void BrotliEncoderCleanupParams(MemoryManager* m,
+ BrotliEncoderParams* params) {
+ BrotliCleanupSharedEncoderDictionary(m, &params->dictionary);
+}
+
static void BrotliEncoderInitState(BrotliEncoderState* s) {
BrotliEncoderInitParams(&s->params);
s->input_pos_ = 0;
@@ -769,9 +701,11 @@ static void BrotliEncoderInitState(BrotliEncoderState* s) {
HasherInit(&s->hasher_);
s->large_table_ = NULL;
s->large_table_size_ = 0;
- s->cmd_code_numbits_ = 0;
+ s->one_pass_arena_ = NULL;
+ s->two_pass_arena_ = NULL;
s->command_buf_ = NULL;
s->literal_buf_ = NULL;
+ s->total_in_ = 0;
s->next_out_ = NULL;
s->available_out_ = 0;
s->total_out_ = 0;
@@ -796,13 +730,9 @@ static void BrotliEncoderInitState(BrotliEncoderState* s) {
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) {
+ BrotliEncoderState* state = (BrotliEncoderState*)BrotliBootstrapAlloc(
+ sizeof(BrotliEncoderState), alloc_func, free_func, opaque);
+ if (state == NULL) {
/* BROTLI_DUMP(); */
return 0;
}
@@ -812,19 +742,36 @@ BrotliEncoderState* BrotliEncoderCreateInstance(
return state;
}
+#ifdef BROTLI_REPORTING
+/* When BROTLI_REPORTING is defined extra reporting module have to be linked. */
+void BrotliEncoderOnFinish(const BrotliEncoderState* s);
+#define BROTLI_ENCODER_ON_FINISH(s) BrotliEncoderOnFinish(s);
+#else
+#if !defined(BROTLI_ENCODER_ON_FINISH)
+#define BROTLI_ENCODER_ON_FINISH(s) (void)(s);
+#endif
+#endif
+
static void BrotliEncoderCleanupState(BrotliEncoderState* s) {
MemoryManager* m = &s->memory_manager_;
+
+ BROTLI_ENCODER_ON_FINISH(s);
+
if (BROTLI_IS_OOM(m)) {
BrotliWipeOutMemoryManager(m);
return;
}
+
BROTLI_FREE(m, s->storage_);
BROTLI_FREE(m, s->commands_);
RingBufferFree(m, &s->ringbuffer_);
DestroyHasher(m, &s->hasher_);
BROTLI_FREE(m, s->large_table_);
+ BROTLI_FREE(m, s->one_pass_arena_);
+ BROTLI_FREE(m, s->two_pass_arena_);
BROTLI_FREE(m, s->command_buf_);
BROTLI_FREE(m, s->literal_buf_);
+ BrotliEncoderCleanupParams(m, &s->params);
}
/* Deinitializes and frees BrotliEncoderState instance. */
@@ -832,11 +779,8 @@ 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);
+ BrotliBootstrapFree(state, &state->memory_manager_);
}
}
@@ -925,6 +869,8 @@ static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes,
uint64_t cmd_dist = (uint64_t)s->dist_cache_[0];
uint32_t distance_code = CommandRestoreDistanceCode(last_command,
&s->params.dist);
+ const CompoundDictionary* dict = &s->params.dictionary.compound;
+ size_t compound_dictionary_size = dict->total_size;
if (distance_code < BROTLI_NUM_DISTANCE_SHORT_CODES ||
distance_code - (BROTLI_NUM_DISTANCE_SHORT_CODES - 1) == cmd_dist) {
if (cmd_dist <= max_distance) {
@@ -935,6 +881,38 @@ static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes,
(*wrapped_last_processed_pos)++;
}
} else {
+ if ((cmd_dist - max_distance - 1) < compound_dictionary_size &&
+ last_copy_len < cmd_dist - max_distance) {
+ size_t address =
+ compound_dictionary_size - (size_t)(cmd_dist - max_distance) +
+ (size_t)last_copy_len;
+ size_t br_index = 0;
+ size_t br_offset;
+ const uint8_t* chunk;
+ size_t chunk_length;
+ while (address >= dict->chunk_offsets[br_index + 1]) br_index++;
+ br_offset = address - dict->chunk_offsets[br_index];
+ chunk = dict->chunk_source[br_index];
+ chunk_length =
+ dict->chunk_offsets[br_index + 1] - dict->chunk_offsets[br_index];
+ while (*bytes != 0 && data[*wrapped_last_processed_pos & mask] ==
+ chunk[br_offset]) {
+ last_command->copy_len_++;
+ (*bytes)--;
+ (*wrapped_last_processed_pos)++;
+ if (++br_offset == chunk_length) {
+ br_index++;
+ br_offset = 0;
+ if (br_index != dict->num_chunks) {
+ chunk = dict->chunk_source[br_index];
+ chunk_length = dict->chunk_offsets[br_index + 1] -
+ dict->chunk_offsets[br_index];
+ } else {
+ break;
+ }
+ }
+ }
+ }
}
/* The copy length is at most the metablock size, and thus expressible. */
GetLengthCode(last_command->insert_len_,
@@ -952,8 +930,8 @@ static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes,
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.
+ to 7 bits of the last byte of output. Byte-alignment could be enforced by
+ emitting an empty meta-data block.
Returns BROTLI_FALSE if the size of the input data is larger than
input_block_size().
*/
@@ -968,10 +946,39 @@ static BROTLI_BOOL EncodeData(
MemoryManager* m = &s->memory_manager_;
ContextType literal_context_mode;
ContextLut literal_context_lut;
+ BROTLI_BOOL fast_compress =
+ s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY ||
+ s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY;
data = s->ringbuffer_.buffer_;
mask = s->ringbuffer_.mask_;
+ if (delta == 0) { /* No new input; still might want to flush or finish. */
+ if (!data) { /* No input has been processed so far. */
+ if (is_last) { /* Emit complete finalized stream. */
+ BROTLI_DCHECK(s->last_bytes_bits_ <= 14);
+ s->last_bytes_ |= (uint16_t)(3u << s->last_bytes_bits_);
+ s->last_bytes_bits_ = (uint8_t)(s->last_bytes_bits_ + 2u);
+ s->tiny_buf_.u8[0] = (uint8_t)s->last_bytes_;
+ s->tiny_buf_.u8[1] = (uint8_t)(s->last_bytes_ >> 8);
+ *output = s->tiny_buf_.u8;
+ *out_size = (s->last_bytes_bits_ + 7u) >> 3u;
+ return BROTLI_TRUE;
+ } else { /* No data, not last -> no-op. */
+ *out_size = 0;
+ return BROTLI_TRUE;
+ }
+ } else {
+ /* Fast compress performs flush every block -> flush is no-op. */
+ if (!is_last && (!force_flush || fast_compress)) { /* Another no-op. */
+ *out_size = 0;
+ return BROTLI_TRUE;
+ }
+ }
+ }
+ BROTLI_DCHECK(data);
+
+ if (s->params.quality > s->params.dictionary.max_quality) return BROTLI_FALSE;
/* Adding more blocks after "last" block is forbidden. */
if (s->is_last_block_emitted_) return BROTLI_FALSE;
if (is_last) s->is_last_block_emitted_ = BROTLI_TRUE;
@@ -991,19 +998,12 @@ static BROTLI_BOOL EncodeData(
}
}
- if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY ||
- s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) {
+ if (fast_compress) {
uint8_t* storage;
size_t storage_ix = s->last_bytes_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. */
- *out_size = 0;
- return BROTLI_TRUE;
- }
storage = GetBrotliStorage(s, 2 * bytes + 503);
if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
storage[0] = (uint8_t)s->last_bytes_;
@@ -1012,16 +1012,14 @@ static BROTLI_BOOL EncodeData(
if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) {
BrotliCompressFragmentFast(
- m, &data[wrapped_last_processed_pos & mask],
+ s->one_pass_arena_, &data[wrapped_last_processed_pos & mask],
bytes, 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, &data[wrapped_last_processed_pos & mask],
+ s->two_pass_arena_, &data[wrapped_last_processed_pos & mask],
bytes, is_last,
s->command_buf_, s->literal_buf_,
table, table_size,
@@ -1099,7 +1097,7 @@ static BROTLI_BOOL EncodeData(
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? */
+ /* TODO(eustas): 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
@@ -1192,7 +1190,7 @@ static size_t WriteMetadataHeader(
if (block_size == 0) {
BrotliWriteBits(2, 0, &storage_ix, header);
} else {
- uint32_t nbits = (block_size == 1) ? 0 :
+ uint32_t nbits = (block_size == 1) ? 1 :
(Log2FloorNonZero((uint32_t)block_size - 1) + 1);
uint32_t nbytes = (nbits + 7) / 8;
BrotliWriteBits(2, nbytes, &storage_ix, header);
@@ -1201,228 +1199,6 @@ static size_t WriteMetadataHeader(
return (storage_ix + 7u) >> 3;
}
-static BROTLI_BOOL BrotliCompressBufferQuality10(
- int lgwin, size_t input_size, const uint8_t* input_buffer,
- size_t* encoded_size, uint8_t* encoded_buffer) {
- MemoryManager memory_manager;
- MemoryManager* m = &memory_manager;
-
- const size_t mask = BROTLI_SIZE_MAX >> 1;
- int dist_cache[4] = { 4, 11, 15, 16 };
- int saved_dist_cache[4] = { 4, 11, 15, 16 };
- BROTLI_BOOL ok = BROTLI_TRUE;
- const size_t max_out_size = *encoded_size;
- size_t total_out_size = 0;
- uint16_t last_bytes;
- uint8_t last_bytes_bits;
-
- const size_t hasher_eff_size = BROTLI_MIN(size_t,
- input_size, BROTLI_MAX_BACKWARD_LIMIT(lgwin) + BROTLI_WINDOW_GAP);
-
- BrotliEncoderParams params;
-
- 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;
-
- Hasher hasher;
- HasherInit(&hasher);
-
- BrotliEncoderInitParams(&params);
- params.quality = 10;
- params.lgwin = lgwin;
- if (lgwin > BROTLI_MAX_WINDOW_BITS) {
- params.large_window = BROTLI_TRUE;
- }
- SanitizeParams(&params);
- params.lgblock = ComputeLgBlock(&params);
- ChooseDistanceParams(&params);
- max_block_size = (size_t)1 << params.lgblock;
-
- BrotliInitMemoryManager(m, 0, 0, 0);
-
- BROTLI_DCHECK(input_size <= mask + 1);
- EncodeWindowBits(lgwin, params.large_window, &last_bytes, &last_bytes_bits);
- InitOrStitchToPreviousBlock(m, &hasher, input_buffer, mask, &params,
- 0, hasher_eff_size, BROTLI_TRUE);
- if (BROTLI_IS_OOM(m)) goto oom;
-
- while (ok && metablock_start < input_size) {
- const size_t metablock_end =
- 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;
- size_t num_commands = 0;
- size_t last_insert_len = 0;
- size_t num_literals = 0;
- size_t metablock_size = 0;
- size_t cmd_alloc_size = 0;
- BROTLI_BOOL is_last;
- uint8_t* storage;
- size_t storage_ix;
-
- ContextType literal_context_mode = ChooseContextMode(&params,
- input_buffer, metablock_start, mask, metablock_end - metablock_start);
- ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode);
-
- 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) || BROTLI_IS_NULL(nodes)) goto oom;
- BrotliInitZopfliNodes(nodes, block_size + 1);
- StitchToPreviousBlockH10(&hasher.privat._H10, block_size, block_start,
- input_buffer, mask);
- path_size = BrotliZopfliComputeShortestPath(m, block_size, block_start,
- input_buffer, mask, literal_context_lut, &params, 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) || BROTLI_IS_NULL(new_commands)) goto oom;
- cmd_alloc_size = new_cmd_alloc_size;
- if (commands) {
- memcpy(new_commands, commands, sizeof(Command) * num_commands);
- BROTLI_FREE(m, commands);
- }
- commands = new_commands;
- }
- BrotliZopfliCreateCommands(block_size, block_start, &nodes[0], dist_cache,
- &last_insert_len, &params, &commands[num_commands], &num_literals);
- num_commands += path_size;
- block_start += block_size;
- metablock_size += block_size;
- BROTLI_FREE(m, nodes);
- if (num_literals > max_literals_per_metablock ||
- num_commands > max_commands_per_metablock) {
- break;
- }
- }
-
- if (last_insert_len > 0) {
- InitInsertCommand(&commands[num_commands++], last_insert_len);
- num_literals += last_insert_len;
- }
-
- is_last = TO_BROTLI_BOOL(metablock_start + metablock_size == input_size);
- storage = NULL;
- storage_ix = last_bytes_bits;
-
- if (metablock_size == 0) {
- /* Write the ISLAST and ISEMPTY bits. */
- storage = BROTLI_ALLOC(m, uint8_t, 16);
- if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom;
- storage[0] = (uint8_t)last_bytes;
- storage[1] = (uint8_t)(last_bytes >> 8);
- 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. */
- memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0]));
- storage = BROTLI_ALLOC(m, uint8_t, metablock_size + 16);
- if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom;
- storage[0] = (uint8_t)last_bytes;
- storage[1] = (uint8_t)(last_bytes >> 8);
- BrotliStoreUncompressedMetaBlock(is_last, input_buffer,
- metablock_start, mask, metablock_size,
- &storage_ix, storage);
- } else {
- MetaBlockSplit mb;
- BrotliEncoderParams block_params = params;
- InitMetaBlockSplit(&mb);
- BrotliBuildMetaBlock(m, input_buffer, metablock_start, mask,
- &block_params,
- prev_byte, prev_byte2,
- commands, num_commands,
- literal_context_mode,
- &mb);
- if (BROTLI_IS_OOM(m)) goto oom;
- {
- /* The number of distance symbols effectively used for distance
- histograms. It might be less than distance alphabet size
- for "Large Window Brotli" (32-bit). */
- BrotliOptimizeHistograms(block_params.dist.alphabet_size_limit, &mb);
- }
- storage = BROTLI_ALLOC(m, uint8_t, 2 * metablock_size + 503);
- if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom;
- storage[0] = (uint8_t)last_bytes;
- storage[1] = (uint8_t)(last_bytes >> 8);
- BrotliStoreMetaBlock(m, input_buffer, metablock_start, metablock_size,
- mask, prev_byte, prev_byte2,
- is_last,
- &block_params,
- 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. */
- memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0]));
- storage[0] = (uint8_t)last_bytes;
- storage[1] = (uint8_t)(last_bytes >> 8);
- storage_ix = last_bytes_bits;
- BrotliStoreUncompressedMetaBlock(is_last, input_buffer,
- metablock_start, mask,
- metablock_size, &storage_ix, storage);
- }
- DestroyMetaBlockSplit(m, &mb);
- }
- last_bytes = (uint16_t)(storage[storage_ix >> 3]);
- last_bytes_bits = storage_ix & 7u;
- metablock_start += metablock_size;
- if (metablock_start < input_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. */
- 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 = BROTLI_FALSE;
- }
- }
- BROTLI_FREE(m, storage);
- BROTLI_FREE(m, commands);
- }
-
- *encoded_size = total_out_size;
- DestroyHasher(m, &hasher);
- return ok;
-
-oom:
- BrotliWipeOutMemoryManager(m);
- return BROTLI_FALSE;
-}
-
size_t BrotliEncoderMaxCompressedSize(size_t input_size) {
/* [window bits / empty metadata] + N * [uncompressed] + [last empty] */
size_t num_large_blocks = input_size >> 14;
@@ -1470,7 +1246,8 @@ static size_t MakeUncompressedStream(
BROTLI_BOOL BrotliEncoderCompress(
int quality, int lgwin, BrotliEncoderMode mode, size_t input_size,
- const uint8_t input_buffer[BROTLI_ARRAY_PARAM(input_size)], size_t* encoded_size,
+ const uint8_t input_buffer[BROTLI_ARRAY_PARAM(input_size)],
+ size_t* encoded_size,
uint8_t encoded_buffer[BROTLI_ARRAY_PARAM(*encoded_size)]) {
BrotliEncoderState* s;
size_t out_size = *encoded_size;
@@ -1487,17 +1264,6 @@ BROTLI_BOOL BrotliEncoderCompress(
*encoded_buffer = 6;
return BROTLI_TRUE;
}
- if (quality == 10) {
- /* TODO: Implement this direct path for all quality levels. */
- const int lg_win = BROTLI_MIN(int, BROTLI_LARGE_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;
- }
s = BrotliEncoderCreateInstance(0, 0, 0);
if (!s) {
@@ -1509,6 +1275,7 @@ BROTLI_BOOL BrotliEncoderCompress(
uint8_t* next_out = encoded_buffer;
size_t total_out = 0;
BROTLI_BOOL result = BROTLI_FALSE;
+ /* TODO(eustas): check that parameters are sane. */
BrotliEncoderSetParameter(s, BROTLI_PARAM_QUALITY, (uint32_t)quality);
BrotliEncoderSetParameter(s, BROTLI_PARAM_LGWIN, (uint32_t)lgwin);
BrotliEncoderSetParameter(s, BROTLI_PARAM_MODE, (uint32_t)mode);
@@ -1560,6 +1327,18 @@ static void InjectBytePaddingBlock(BrotliEncoderState* s) {
s->available_out_ += (seal_bits + 7) >> 3;
}
+/* Fills the |total_out|, if it is not NULL. */
+static void SetTotalOut(BrotliEncoderState* s, size_t* total_out) {
+ if (total_out) {
+ /* Saturating conversion uint64_t -> size_t */
+ size_t result = (size_t)-1;
+ if (s->total_out_ < result) {
+ result = (size_t)s->total_out_;
+ }
+ *total_out = result;
+ }
+}
+
/* Injects padding bits or pushes compressed data to output.
Returns false if nothing is done. */
static BROTLI_BOOL InjectFlushOrPushOutput(BrotliEncoderState* s,
@@ -1579,7 +1358,7 @@ static BROTLI_BOOL InjectFlushOrPushOutput(BrotliEncoderState* s,
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_;
+ SetTotalOut(s, total_out);
return BROTLI_TRUE;
}
@@ -1676,19 +1455,19 @@ static BROTLI_BOOL BrotliEncoderCompressStreamFast(
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);
+ BrotliCompressFragmentFast(s->one_pass_arena_, *next_in, block_size,
+ is_last, table, table_size, &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,
+ BrotliCompressFragmentTwoPass(s->two_pass_arena_, *next_in, block_size,
+ is_last, command_buf, literal_buf, table, table_size,
&storage_ix, storage);
if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
}
if (block_size != 0) {
*next_in += block_size;
*available_in -= block_size;
+ s->total_in_ += block_size;
}
if (inplace) {
size_t out_bytes = storage_ix >> 3;
@@ -1697,7 +1476,7 @@ static BROTLI_BOOL BrotliEncoderCompressStreamFast(
*next_out += out_bytes;
*available_out -= out_bytes;
s->total_out_ += out_bytes;
- if (total_out) *total_out = s->total_out_;
+ SetTotalOut(s, total_out);
} else {
size_t out_bytes = storage_ix >> 3;
s->next_out_ = storage;
@@ -1766,6 +1545,7 @@ static BROTLI_BOOL ProcessMetadata(
memcpy(*next_out, *next_in, copy);
*next_in += copy;
*available_in -= copy;
+ s->total_in_ += copy; /* not actually data input, though */
s->remaining_metadata_bytes_ -= copy;
*next_out += copy;
*available_out -= copy;
@@ -1776,6 +1556,7 @@ static BROTLI_BOOL ProcessMetadata(
memcpy(s->next_out_, *next_in, copy);
*next_in += copy;
*available_in -= copy;
+ s->total_in_ += copy; /* not actually data input, though */
s->remaining_metadata_bytes_ -= copy;
s->available_out_ = copy;
}
@@ -1803,7 +1584,7 @@ static void UpdateSizeHint(BrotliEncoderState* s, size_t available_in) {
BROTLI_BOOL BrotliEncoderCompressStream(
BrotliEncoderState* s, BrotliEncoderOperation op, size_t* available_in,
- const uint8_t** next_in, size_t* available_out,uint8_t** next_out,
+ const uint8_t** next_in, size_t* available_out, uint8_t** next_out,
size_t* total_out) {
if (!EnsureInitialized(s)) return BROTLI_FALSE;
@@ -1845,6 +1626,7 @@ BROTLI_BOOL BrotliEncoderCompressStream(
CopyInputToRingBuffer(s, copy_input_size, *next_in);
*next_in += copy_input_size;
*available_in -= copy_input_size;
+ s->total_in_ += copy_input_size;
if (s->flint_ > 0) s->flint_ = (int8_t)(s->flint_ - (int)copy_input_size);
continue;
}
@@ -1922,6 +1704,293 @@ uint32_t BrotliEncoderVersion(void) {
return BROTLI_VERSION;
}
+BrotliEncoderPreparedDictionary* BrotliEncoderPrepareDictionary(
+ BrotliSharedDictionaryType type, size_t size,
+ const uint8_t data[BROTLI_ARRAY_PARAM(size)], int quality,
+ brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {
+ ManagedDictionary* managed_dictionary = NULL;
+ BROTLI_BOOL type_is_known = BROTLI_FALSE;
+ type_is_known |= (type == BROTLI_SHARED_DICTIONARY_RAW);
+#if defined(BROTLI_EXPERIMENTAL)
+ type_is_known |= (type == BROTLI_SHARED_DICTIONARY_SERIALIZED);
+#endif /* BROTLI_EXPERIMENTAL */
+ if (!type_is_known) {
+ return NULL;
+ }
+ managed_dictionary =
+ BrotliCreateManagedDictionary(alloc_func, free_func, opaque);
+ if (managed_dictionary == NULL) {
+ return NULL;
+ }
+ if (type == BROTLI_SHARED_DICTIONARY_RAW) {
+ managed_dictionary->dictionary = (uint32_t*)CreatePreparedDictionary(
+ &managed_dictionary->memory_manager_, data, size);
+ }
+#if defined(BROTLI_EXPERIMENTAL)
+ if (type == BROTLI_SHARED_DICTIONARY_SERIALIZED) {
+ SharedEncoderDictionary* dict = (SharedEncoderDictionary*)BrotliAllocate(
+ &managed_dictionary->memory_manager_, sizeof(SharedEncoderDictionary));
+ managed_dictionary->dictionary = (uint32_t*)dict;
+ if (dict != NULL) {
+ BROTLI_BOOL ok = BrotliInitCustomSharedEncoderDictionary(
+ &managed_dictionary->memory_manager_, data, size, quality, dict);
+ if (!ok) {
+ BrotliFree(&managed_dictionary->memory_manager_, dict);
+ managed_dictionary->dictionary = NULL;
+ }
+ }
+ }
+#else /* BROTLI_EXPERIMENTAL */
+ (void)quality;
+#endif /* BROTLI_EXPERIMENTAL */
+ if (managed_dictionary->dictionary == NULL) {
+ BrotliDestroyManagedDictionary(managed_dictionary);
+ return NULL;
+ }
+ return (BrotliEncoderPreparedDictionary*)managed_dictionary;
+}
+
+void BrotliEncoderDestroyPreparedDictionary(
+ BrotliEncoderPreparedDictionary* dictionary) {
+ ManagedDictionary* dict = (ManagedDictionary*)dictionary;
+ if (!dictionary) return;
+ /* First field of dictionary structs. */
+ /* Only managed dictionaries are eligible for destruction by this method. */
+ if (dict->magic != kManagedDictionaryMagic) {
+ return;
+ }
+ if (dict->dictionary == NULL) {
+ /* This should never ever happen. */
+ } else if (*dict->dictionary == kLeanPreparedDictionaryMagic) {
+ DestroyPreparedDictionary(
+ &dict->memory_manager_, (PreparedDictionary*)dict->dictionary);
+ } else if (*dict->dictionary == kSharedDictionaryMagic) {
+ BrotliCleanupSharedEncoderDictionary(&dict->memory_manager_,
+ (SharedEncoderDictionary*)dict->dictionary);
+ BrotliFree(&dict->memory_manager_, dict->dictionary);
+ } else {
+ /* There is also kPreparedDictionaryMagic, but such instances should be
+ * constructed and destroyed by different means. */
+ }
+ dict->dictionary = NULL;
+ BrotliDestroyManagedDictionary(dict);
+}
+
+BROTLI_BOOL BrotliEncoderAttachPreparedDictionary(BrotliEncoderState* state,
+ const BrotliEncoderPreparedDictionary* dictionary) {
+ /* First field of dictionary structs */
+ const BrotliEncoderPreparedDictionary* dict = dictionary;
+ uint32_t magic = *((const uint32_t*)dict);
+ SharedEncoderDictionary* current = NULL;
+ if (magic == kManagedDictionaryMagic) {
+ /* Unwrap managed dictionary. */
+ ManagedDictionary* managed_dictionary = (ManagedDictionary*)dict;
+ magic = *managed_dictionary->dictionary;
+ dict = (BrotliEncoderPreparedDictionary*)managed_dictionary->dictionary;
+ }
+ current = &state->params.dictionary;
+ if (magic == kPreparedDictionaryMagic ||
+ magic == kLeanPreparedDictionaryMagic) {
+ const PreparedDictionary* prepared = (const PreparedDictionary*)dict;
+ if (!AttachPreparedDictionary(&current->compound, prepared)) {
+ return BROTLI_FALSE;
+ }
+ } else if (magic == kSharedDictionaryMagic) {
+ const SharedEncoderDictionary* attached =
+ (const SharedEncoderDictionary*)dict;
+ BROTLI_BOOL was_default = !current->contextual.context_based &&
+ current->contextual.num_dictionaries == 1 &&
+ current->contextual.dict[0]->hash_table_words ==
+ kStaticDictionaryHashWords &&
+ current->contextual.dict[0]->hash_table_lengths ==
+ kStaticDictionaryHashLengths;
+ BROTLI_BOOL new_default = !attached->contextual.context_based &&
+ attached->contextual.num_dictionaries == 1 &&
+ attached->contextual.dict[0]->hash_table_words ==
+ kStaticDictionaryHashWords &&
+ attached->contextual.dict[0]->hash_table_lengths ==
+ kStaticDictionaryHashLengths;
+ size_t i;
+ if (state->is_initialized_) return BROTLI_FALSE;
+ current->max_quality =
+ BROTLI_MIN(int, current->max_quality, attached->max_quality);
+ for (i = 0; i < attached->compound.num_chunks; i++) {
+ if (!AttachPreparedDictionary(&current->compound,
+ attached->compound.chunks[i])) {
+ return BROTLI_FALSE;
+ }
+ }
+ if (!new_default) {
+ if (!was_default) return BROTLI_FALSE;
+ /* Copy by value, but then set num_instances_ to 0 because their memory
+ is managed by attached, not by current */
+ current->contextual = attached->contextual;
+ current->contextual.num_instances_ = 0;
+ }
+ } else {
+ return BROTLI_FALSE;
+ }
+ return BROTLI_TRUE;
+}
+
+size_t BrotliEncoderEstimatePeakMemoryUsage(int quality, int lgwin,
+ size_t input_size) {
+ BrotliEncoderParams params;
+ size_t memory_manager_slots = BROTLI_ENCODER_MEMORY_MANAGER_SLOTS;
+ size_t memory_manager_size = memory_manager_slots * sizeof(void*);
+ BrotliEncoderInitParams(&params);
+ params.quality = quality;
+ params.lgwin = lgwin;
+ params.size_hint = input_size;
+ params.large_window = lgwin > BROTLI_MAX_WINDOW_BITS;
+ SanitizeParams(&params);
+ params.lgblock = ComputeLgBlock(&params);
+ ChooseHasher(&params, &params.hasher);
+ if (params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY ||
+ params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) {
+ size_t state_size = sizeof(BrotliEncoderState);
+ size_t block_size = BROTLI_MIN(size_t, input_size, (1ul << params.lgwin));
+ size_t hash_table_size =
+ HashTableSize(MaxHashTableSize(params.quality), block_size);
+ size_t hash_size =
+ (hash_table_size < (1u << 10)) ? 0 : sizeof(int) * hash_table_size;
+ size_t cmdbuf_size = params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY ?
+ 5 * BROTLI_MIN(size_t, block_size, 1ul << 17) : 0;
+ if (params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) {
+ state_size += sizeof(BrotliOnePassArena);
+ } else {
+ state_size += sizeof(BrotliTwoPassArena);
+ }
+ return hash_size + cmdbuf_size + state_size;
+ } else {
+ size_t short_ringbuffer_size = (size_t)1 << params.lgblock;
+ int ringbuffer_bits = ComputeRbBits(&params);
+ size_t ringbuffer_size = input_size < short_ringbuffer_size ?
+ input_size : (1u << ringbuffer_bits) + short_ringbuffer_size;
+ size_t hash_size[4] = {0};
+ size_t metablock_size =
+ BROTLI_MIN(size_t, input_size, MaxMetablockSize(&params));
+ size_t inputblock_size =
+ BROTLI_MIN(size_t, input_size, (size_t)1 << params.lgblock);
+ size_t cmdbuf_size = metablock_size * 2 + inputblock_size * 6;
+ size_t outbuf_size = metablock_size * 2 + 503;
+ size_t histogram_size = 0;
+ HasherSize(&params, BROTLI_TRUE, input_size, hash_size);
+ if (params.quality < MIN_QUALITY_FOR_BLOCK_SPLIT) {
+ cmdbuf_size = BROTLI_MIN(size_t, cmdbuf_size,
+ MAX_NUM_DELAYED_SYMBOLS * sizeof(Command) + inputblock_size * 12);
+ }
+ if (params.quality >= MIN_QUALITY_FOR_HQ_BLOCK_SPLITTING) {
+ /* Only a very rough estimation, based on enwik8. */
+ histogram_size = 200 << 20;
+ } else if (params.quality >= MIN_QUALITY_FOR_BLOCK_SPLIT) {
+ size_t literal_histograms =
+ BROTLI_MIN(size_t, metablock_size / 6144, 256);
+ size_t command_histograms =
+ BROTLI_MIN(size_t, metablock_size / 6144, 256);
+ size_t distance_histograms =
+ BROTLI_MIN(size_t, metablock_size / 6144, 256);
+ histogram_size = literal_histograms * sizeof(HistogramLiteral) +
+ command_histograms * sizeof(HistogramCommand) +
+ distance_histograms * sizeof(HistogramDistance);
+ }
+ return (memory_manager_size + ringbuffer_size +
+ hash_size[0] + hash_size[1] + hash_size[2] + hash_size[3] +
+ cmdbuf_size +
+ outbuf_size +
+ histogram_size);
+ }
+}
+size_t BrotliEncoderGetPreparedDictionarySize(
+ const BrotliEncoderPreparedDictionary* prepared_dictionary) {
+ /* First field of dictionary structs */
+ const BrotliEncoderPreparedDictionary* prepared = prepared_dictionary;
+ uint32_t magic = *((const uint32_t*)prepared);
+ size_t overhead = 0;
+ if (magic == kManagedDictionaryMagic) {
+ const ManagedDictionary* managed = (const ManagedDictionary*)prepared;
+ overhead = sizeof(ManagedDictionary);
+ magic = *managed->dictionary;
+ prepared = (const BrotliEncoderPreparedDictionary*)managed->dictionary;
+ }
+
+ if (magic == kPreparedDictionaryMagic) {
+ const PreparedDictionary* dictionary =
+ (const PreparedDictionary*)prepared;
+ /* Keep in sync with step 3 of CreatePreparedDictionary */
+ return sizeof(PreparedDictionary) + dictionary->source_size +
+ (sizeof(uint32_t) << dictionary->slot_bits) +
+ (sizeof(uint16_t) << dictionary->bucket_bits) +
+ (sizeof(uint32_t) * dictionary->num_items) + overhead;
+ } else if (magic == kLeanPreparedDictionaryMagic) {
+ const PreparedDictionary* dictionary =
+ (const PreparedDictionary*)prepared;
+ /* Keep in sync with step 3 of CreatePreparedDictionary */
+ return sizeof(PreparedDictionary) + sizeof(uint8_t*) +
+ (sizeof(uint32_t) << dictionary->slot_bits) +
+ (sizeof(uint16_t) << dictionary->bucket_bits) +
+ (sizeof(uint32_t) * dictionary->num_items) + overhead;
+ } else if (magic == kSharedDictionaryMagic) {
+ const SharedEncoderDictionary* dictionary =
+ (const SharedEncoderDictionary*)prepared;
+ const CompoundDictionary* compound = &dictionary->compound;
+ const ContextualEncoderDictionary* contextual = &dictionary->contextual;
+ size_t result = sizeof(*dictionary);
+ size_t i;
+ size_t num_instances;
+ const BrotliEncoderDictionary* instances;
+ for (i = 0; i < compound->num_prepared_instances_; i++) {
+ size_t size = BrotliEncoderGetPreparedDictionarySize(
+ (const BrotliEncoderPreparedDictionary*)
+ compound->prepared_instances_[i]);
+ if (!size) return 0; /* error */
+ result += size;
+ }
+ if (contextual->context_based) {
+ num_instances = contextual->num_instances_;
+ instances = contextual->instances_;
+ result += sizeof(*instances) * num_instances;
+ } else {
+ num_instances = 1;
+ instances = &contextual->instance_;
+ }
+ for (i = 0; i < num_instances; i++) {
+ const BrotliEncoderDictionary* dict = &instances[i];
+ result += dict->trie.pool_capacity * sizeof(BrotliTrieNode);
+ if (dict->hash_table_data_words_) {
+ result += sizeof(kStaticDictionaryHashWords);
+ }
+ if (dict->hash_table_data_lengths_) {
+ result += sizeof(kStaticDictionaryHashLengths);
+ }
+ if (dict->buckets_data_) {
+ result += sizeof(*dict->buckets_data_) * dict->buckets_alloc_size_;
+ }
+ if (dict->dict_words_data_) {
+ result += sizeof(*dict->dict_words) * dict->dict_words_alloc_size_;
+ }
+ if (dict->words_instance_) {
+ result += sizeof(*dict->words_instance_);
+ /* data_size not added here: it is never allocated by the
+ SharedEncoderDictionary, instead it always points to the file
+ already loaded in memory. So if the caller wants to include
+ this memory as well, add the size of the loaded dictionary
+ file to this. */
+ }
+ }
+ return result + overhead;
+ }
+ return 0; /* error */
+}
+
+#if defined(BROTLI_TEST)
+size_t MakeUncompressedStreamForTest(const uint8_t*, size_t, uint8_t*);
+size_t MakeUncompressedStreamForTest(
+ const uint8_t* input, size_t input_size, uint8_t* output) {
+ return MakeUncompressedStream(input, input_size, output);
+}
+#endif
+
#if defined(__cplusplus) || defined(c_plusplus)
} /* extern "C" */
#endif