encode.c | Explore in Territory

/* Copyright 2013 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* Implementation of Brotli compressor. */

#include <brotli/encode.h>

#include <stdlib.h>  /* free, malloc */
#include <string.h>  /* memcpy, memset */

#include "../common/constants.h"
#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 "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 "quality.h"
#include "ringbuffer.h"
#include "utf8_util.h"
#include "write_bits.h"

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

#define COPY_ARRAY(dst, src) …

BrotliEncoderStreamState;

BrotliEncoderFlintState;

BrotliEncoderStateStruct;

static size_t InputBlockSize(BrotliEncoderState* s) { … }

static uint64_t UnprocessedInputSize(BrotliEncoderState* s) { … }

static size_t RemainingInputBlockSize(BrotliEncoderState* s) { … }

BROTLI_BOOL BrotliEncoderSetParameter(
    BrotliEncoderState* state, BrotliEncoderParameter p, uint32_t value) { … }

/* Wraps 64-bit input position to 32-bit ring-buffer position preserving
   "not-a-first-lap" feature. */
static uint32_t WrapPosition(uint64_t position) { … }

static uint8_t* GetBrotliStorage(BrotliEncoderState* s, size_t size) { … }

static size_t HashTableSize(size_t max_table_size, size_t input_size) { … }

static int* GetHashTable(BrotliEncoderState* s, int quality,
                         size_t input_size, size_t* table_size) { … }

static void EncodeWindowBits(int lgwin, BROTLI_BOOL large_window,
    uint16_t* last_bytes, uint8_t* last_bytes_bits) { … }

/* TODO(eustas): move to compress_fragment.c? */
/* Initializes the command and distance prefix codes for the first block. */
static void InitCommandPrefixCodes(BrotliOnePassArena* s) { … }

/* 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) { … }

/* Decide if we want to use a more complex static context map containing 13
   context values, based on the entropy reduction of histograms over the
   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,
    uint32_t* arena) { … }

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,
    uint32_t* arena) { … }

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) { … }

/* Chooses the literal context mode for a metablock */
static ContextType ChooseContextMode(const BrotliEncoderParams* params,
    const uint8_t* data, const size_t pos, const size_t mask,
    const size_t length) { … }

static void WriteMetaBlockInternal(MemoryManager* m,
                                   const uint8_t* data,
                                   const size_t mask,
                                   const uint64_t last_flush_pos,
                                   const size_t bytes,
                                   const BROTLI_BOOL is_last,
                                   ContextType literal_context_mode,
                                   const BrotliEncoderParams* params,
                                   const uint8_t prev_byte,
                                   const uint8_t prev_byte2,
                                   const size_t num_literals,
                                   const size_t num_commands,
                                   Command* commands,
                                   const int* saved_dist_cache,
                                   int* dist_cache,
                                   size_t* storage_ix,
                                   uint8_t* storage) { … }

static void ChooseDistanceParams(BrotliEncoderParams* params) { … }

static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s) { … }

static void BrotliEncoderInitParams(BrotliEncoderParams* params) { … }

static void BrotliEncoderCleanupParams(MemoryManager* m,
    BrotliEncoderParams* params) { … }

static void BrotliEncoderInitState(BrotliEncoderState* s) { … }

BrotliEncoderState* BrotliEncoderCreateInstance(
    brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { … }

static void BrotliEncoderCleanupState(BrotliEncoderState* s) { … }

/* Deinitializes and frees BrotliEncoderState instance. */
void BrotliEncoderDestroyInstance(BrotliEncoderState* state) { … }

/*
   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) { … }

/* Marks all input as processed.
   Returns true if position wrapping occurs. */
static BROTLI_BOOL UpdateLastProcessedPos(BrotliEncoderState* s) { … }

static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes,
                              uint32_t* 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) { … }

/* 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) { … }

static BROTLI_NOINLINE BROTLI_BOOL BrotliCompressBufferQuality10(
    int lgwin, size_t input_size, const uint8_t* input_buffer,
    size_t* encoded_size, uint8_t* encoded_buffer) { … }

size_t BrotliEncoderMaxCompressedSize(size_t input_size) { … }

/* 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) { … }

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,
    uint8_t encoded_buffer[BROTLI_ARRAY_PARAM(*encoded_size)]) { … }

static void InjectBytePaddingBlock(BrotliEncoderState* s) { … }

/* 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) { … }

static void CheckFlushComplete(BrotliEncoderState* s) { … }

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) { … }

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) { … }

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,
    size_t* total_out) { … }

BROTLI_BOOL BrotliEncoderIsFinished(BrotliEncoderState* s) { … }

BROTLI_BOOL BrotliEncoderHasMoreOutput(BrotliEncoderState* s) { … }

const uint8_t* BrotliEncoderTakeOutput(BrotliEncoderState* s, size_t* size) { … }

uint32_t BrotliEncoderVersion(void) { … }

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) { … }

void BrotliEncoderDestroyPreparedDictionary(
    BrotliEncoderPreparedDictionary* dictionary) { … }

BROTLI_BOOL BrotliEncoderAttachPreparedDictionary(BrotliEncoderState* state,
    const BrotliEncoderPreparedDictionary* dictionary) { … }

size_t BrotliEncoderEstimatePeakMemoryUsage(int quality, int lgwin,
                                            size_t input_size) { … }
size_t BrotliEncoderGetPreparedDictionarySize(
    const BrotliEncoderPreparedDictionary* prepared_dictionary) { … }

#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
chromium/third_party/brotli/enc/encode.c
