--- /dev/null
+/* 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
projects / mirror_edk2.git / blobdiff