BaseTools: Copy Brotli algorithm 3rd party source code for tool

[mirror_edk2.git] / BaseTools / Source / C / BrotliCompress / enc / block_splitter.c

/* Copyright 2013 Google Inc. All Rights Reserved.\r
\r
   Distributed under MIT license.\r
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
*/\r
\r
/* Block split point selection utilities. */\r
\r
#include "./block_splitter.h"\r
\r
#include <assert.h>\r
#include <string.h>  /* memcpy, memset */\r
\r
#include "./bit_cost.h"\r
#include "./cluster.h"\r
#include "./command.h"\r
#include "./fast_log.h"\r
#include "./histogram.h"\r
#include "./memory.h"\r
#include "./port.h"\r
#include "./quality.h"\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
extern "C" {\r
#endif\r
\r
static const size_t kMaxLiteralHistograms = 100;\r
static const size_t kMaxCommandHistograms = 50;\r
static const double kLiteralBlockSwitchCost = 28.1;\r
static const double kCommandBlockSwitchCost = 13.5;\r
static const double kDistanceBlockSwitchCost = 14.6;\r
static const size_t kLiteralStrideLength = 70;\r
static const size_t kCommandStrideLength = 40;\r
static const size_t kSymbolsPerLiteralHistogram = 544;\r
static const size_t kSymbolsPerCommandHistogram = 530;\r
static const size_t kSymbolsPerDistanceHistogram = 544;\r
static const size_t kMinLengthForBlockSplitting = 128;\r
static const size_t kIterMulForRefining = 2;\r
static const size_t kMinItersForRefining = 100;\r
\r
static size_t CountLiterals(const Command* cmds, const size_t num_commands) {\r
  /* Count how many we have. */\r
  size_t total_length = 0;\r
  size_t i;\r
  for (i = 0; i < num_commands; ++i) {\r
    total_length += cmds[i].insert_len_;\r
  }\r
  return total_length;\r
}\r
\r
static void CopyLiteralsToByteArray(const Command* cmds,\r
                                    const size_t num_commands,\r
                                    const uint8_t* data,\r
                                    const size_t offset,\r
                                    const size_t mask,\r
                                    uint8_t* literals) {\r
  size_t pos = 0;\r
  size_t from_pos = offset & mask;\r
  size_t i;\r
  for (i = 0; i < num_commands; ++i) {\r
    size_t insert_len = cmds[i].insert_len_;\r
    if (from_pos + insert_len > mask) {\r
      size_t head_size = mask + 1 - from_pos;\r
      memcpy(literals + pos, data + from_pos, head_size);\r
      from_pos = 0;\r
      pos += head_size;\r
      insert_len -= head_size;\r
    }\r
    if (insert_len > 0) {\r
      memcpy(literals + pos, data + from_pos, insert_len);\r
      pos += insert_len;\r
    }\r
    from_pos = (from_pos + insert_len + CommandCopyLen(&cmds[i])) & mask;\r
  }\r
}\r
\r
static BROTLI_INLINE unsigned int MyRand(unsigned int* seed) {\r
  *seed *= 16807U;\r
  if (*seed == 0) {\r
    *seed = 1;\r
  }\r
  return *seed;\r
}\r
\r
static BROTLI_INLINE double BitCost(size_t count) {\r
  return count == 0 ? -2.0 : FastLog2(count);\r
}\r
\r
#define HISTOGRAMS_PER_BATCH 64\r
#define CLUSTERS_PER_BATCH 16\r
\r
#define FN(X) X ## Literal\r
#define DataType uint8_t\r
/* NOLINTNEXTLINE(build/include) */\r
#include "./block_splitter_inc.h"\r
#undef DataType\r
#undef FN\r
\r
#define FN(X) X ## Command\r
#define DataType uint16_t\r
/* NOLINTNEXTLINE(build/include) */\r
#include "./block_splitter_inc.h"\r
#undef FN\r
\r
#define FN(X) X ## Distance\r
/* NOLINTNEXTLINE(build/include) */\r
#include "./block_splitter_inc.h"\r
#undef DataType\r
#undef FN\r
\r
void BrotliInitBlockSplit(BlockSplit* self) {\r
  self->num_types = 0;\r
  self->num_blocks = 0;\r
  self->types = 0;\r
  self->lengths = 0;\r
  self->types_alloc_size = 0;\r
  self->lengths_alloc_size = 0;\r
}\r
\r
void BrotliDestroyBlockSplit(MemoryManager* m, BlockSplit* self) {\r
  BROTLI_FREE(m, self->types);\r
  BROTLI_FREE(m, self->lengths);\r
}\r
\r
void BrotliSplitBlock(MemoryManager* m,\r
                      const Command* cmds,\r
                      const size_t num_commands,\r
                      const uint8_t* data,\r
                      const size_t pos,\r
                      const size_t mask,\r
                      const BrotliEncoderParams* params,\r
                      BlockSplit* literal_split,\r
                      BlockSplit* insert_and_copy_split,\r
                      BlockSplit* dist_split) {\r
  {\r
    size_t literals_count = CountLiterals(cmds, num_commands);\r
    uint8_t* literals = BROTLI_ALLOC(m, uint8_t, literals_count);\r
    if (BROTLI_IS_OOM(m)) return;\r
    /* Create a continuous array of literals. */\r
    CopyLiteralsToByteArray(cmds, num_commands, data, pos, mask, literals);\r
    /* Create the block split on the array of literals.\r
       Literal histograms have alphabet size 256. */\r
    SplitByteVectorLiteral(\r
        m, literals, literals_count,\r
        kSymbolsPerLiteralHistogram, kMaxLiteralHistograms,\r
        kLiteralStrideLength, kLiteralBlockSwitchCost, params,\r
        literal_split);\r
    if (BROTLI_IS_OOM(m)) return;\r
    BROTLI_FREE(m, literals);\r
  }\r
\r
  {\r
    /* Compute prefix codes for commands. */\r
    uint16_t* insert_and_copy_codes = BROTLI_ALLOC(m, uint16_t, num_commands);\r
    size_t i;\r
    if (BROTLI_IS_OOM(m)) return;\r
    for (i = 0; i < num_commands; ++i) {\r
      insert_and_copy_codes[i] = cmds[i].cmd_prefix_;\r
    }\r
    /* Create the block split on the array of command prefixes. */\r
    SplitByteVectorCommand(\r
        m, insert_and_copy_codes, num_commands,\r
        kSymbolsPerCommandHistogram, kMaxCommandHistograms,\r
        kCommandStrideLength, kCommandBlockSwitchCost, params,\r
        insert_and_copy_split);\r
    if (BROTLI_IS_OOM(m)) return;\r
    /* TODO: reuse for distances? */\r
    BROTLI_FREE(m, insert_and_copy_codes);\r
  }\r
\r
  {\r
    /* Create a continuous array of distance prefixes. */\r
    uint16_t* distance_prefixes = BROTLI_ALLOC(m, uint16_t, num_commands);\r
    size_t j = 0;\r
    size_t i;\r
    if (BROTLI_IS_OOM(m)) return;\r
    for (i = 0; i < num_commands; ++i) {\r
      const Command* cmd = &cmds[i];\r
      if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {\r
        distance_prefixes[j++] = cmd->dist_prefix_;\r
      }\r
    }\r
    /* Create the block split on the array of distance prefixes. */\r
    SplitByteVectorDistance(\r
        m, distance_prefixes, j,\r
        kSymbolsPerDistanceHistogram, kMaxCommandHistograms,\r
        kCommandStrideLength, kDistanceBlockSwitchCost, params,\r
        dist_split);\r
    if (BROTLI_IS_OOM(m)) return;\r
    BROTLI_FREE(m, distance_prefixes);\r
  }\r
}\r
\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
}  /* extern "C" */\r
#endif\r