BaseTools: Update Brotli Compress to the latest one 1.0.6

[mirror_edk2.git] / BaseTools / Source / C / BrotliCompress / enc / literal_cost.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
/* Literal cost model to allow backward reference replacement to be efficient.\r
*/\r
\r
#include "./literal_cost.h"\r
\r
#include "../common/platform.h"\r
#include <brotli/types.h>\r
#include "./fast_log.h"\r
#include "./utf8_util.h"\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
extern "C" {\r
#endif\r
\r
static size_t UTF8Position(size_t last, size_t c, size_t clamp) {\r
  if (c < 128) {\r
    return 0;  /* Next one is the 'Byte 1' again. */\r
  } else if (c >= 192) {  /* Next one is the 'Byte 2' of utf-8 encoding. */\r
    return BROTLI_MIN(size_t, 1, clamp);\r
  } else {\r
    /* Let's decide over the last byte if this ends the sequence. */\r
    if (last < 0xE0) {\r
      return 0;  /* Completed two or three byte coding. */\r
    } else {  /* Next one is the 'Byte 3' of utf-8 encoding. */\r
      return BROTLI_MIN(size_t, 2, clamp);\r
    }\r
  }\r
}\r
\r
static size_t DecideMultiByteStatsLevel(size_t pos, size_t len, size_t mask,\r
                                        const uint8_t* data) {\r
  size_t counts[3] = { 0 };\r
  size_t max_utf8 = 1;  /* should be 2, but 1 compresses better. */\r
  size_t last_c = 0;\r
  size_t i;\r
  for (i = 0; i < len; ++i) {\r
    size_t c = data[(pos + i) & mask];\r
    ++counts[UTF8Position(last_c, c, 2)];\r
    last_c = c;\r
  }\r
  if (counts[2] < 500) {\r
    max_utf8 = 1;\r
  }\r
  if (counts[1] + counts[2] < 25) {\r
    max_utf8 = 0;\r
  }\r
  return max_utf8;\r
}\r
\r
static void EstimateBitCostsForLiteralsUTF8(size_t pos, size_t len, size_t mask,\r
                                            const uint8_t* data, float* cost) {\r
  /* max_utf8 is 0 (normal ASCII single byte modeling),\r
     1 (for 2-byte UTF-8 modeling), or 2 (for 3-byte UTF-8 modeling). */\r
  const size_t max_utf8 = DecideMultiByteStatsLevel(pos, len, mask, data);\r
  size_t histogram[3][256] = { { 0 } };\r
  size_t window_half = 495;\r
  size_t in_window = BROTLI_MIN(size_t, window_half, len);\r
  size_t in_window_utf8[3] = { 0 };\r
\r
  size_t i;\r
  {  /* Bootstrap histograms. */\r
    size_t last_c = 0;\r
    size_t utf8_pos = 0;\r
    for (i = 0; i < in_window; ++i) {\r
      size_t c = data[(pos + i) & mask];\r
      ++histogram[utf8_pos][c];\r
      ++in_window_utf8[utf8_pos];\r
      utf8_pos = UTF8Position(last_c, c, max_utf8);\r
      last_c = c;\r
    }\r
  }\r
\r
  /* Compute bit costs with sliding window. */\r
  for (i = 0; i < len; ++i) {\r
    if (i >= window_half) {\r
      /* Remove a byte in the past. */\r
      size_t c =\r
          i < window_half + 1 ? 0 : data[(pos + i - window_half - 1) & mask];\r
      size_t last_c =\r
          i < window_half + 2 ? 0 : data[(pos + i - window_half - 2) & mask];\r
      size_t utf8_pos2 = UTF8Position(last_c, c, max_utf8);\r
      --histogram[utf8_pos2][data[(pos + i - window_half) & mask]];\r
      --in_window_utf8[utf8_pos2];\r
    }\r
    if (i + window_half < len) {\r
      /* Add a byte in the future. */\r
      size_t c = data[(pos + i + window_half - 1) & mask];\r
      size_t last_c = data[(pos + i + window_half - 2) & mask];\r
      size_t utf8_pos2 = UTF8Position(last_c, c, max_utf8);\r
      ++histogram[utf8_pos2][data[(pos + i + window_half) & mask]];\r
      ++in_window_utf8[utf8_pos2];\r
    }\r
    {\r
      size_t c = i < 1 ? 0 : data[(pos + i - 1) & mask];\r
      size_t last_c = i < 2 ? 0 : data[(pos + i - 2) & mask];\r
      size_t utf8_pos = UTF8Position(last_c, c, max_utf8);\r
      size_t masked_pos = (pos + i) & mask;\r
      size_t histo = histogram[utf8_pos][data[masked_pos]];\r
      double lit_cost;\r
      if (histo == 0) {\r
        histo = 1;\r
      }\r
      lit_cost = FastLog2(in_window_utf8[utf8_pos]) - FastLog2(histo);\r
      lit_cost += 0.02905;\r
      if (lit_cost < 1.0) {\r
        lit_cost *= 0.5;\r
        lit_cost += 0.5;\r
      }\r
      /* Make the first bytes more expensive -- seems to help, not sure why.\r
         Perhaps because the entropy source is changing its properties\r
         rapidly in the beginning of the file, perhaps because the beginning\r
         of the data is a statistical "anomaly". */\r
      if (i < 2000) {\r
        lit_cost += 0.7 - ((double)(2000 - i) / 2000.0 * 0.35);\r
      }\r
      cost[i] = (float)lit_cost;\r
    }\r
  }\r
}\r
\r
void BrotliEstimateBitCostsForLiterals(size_t pos, size_t len, size_t mask,\r
                                       const uint8_t* data, float* cost) {\r
  if (BrotliIsMostlyUTF8(data, pos, mask, len, kMinUTF8Ratio)) {\r
    EstimateBitCostsForLiteralsUTF8(pos, len, mask, data, cost);\r
    return;\r
  } else {\r
    size_t histogram[256] = { 0 };\r
    size_t window_half = 2000;\r
    size_t in_window = BROTLI_MIN(size_t, window_half, len);\r
\r
    /* Bootstrap histogram. */\r
    size_t i;\r
    for (i = 0; i < in_window; ++i) {\r
      ++histogram[data[(pos + i) & mask]];\r
    }\r
\r
    /* Compute bit costs with sliding window. */\r
    for (i = 0; i < len; ++i) {\r
      size_t histo;\r
      if (i >= window_half) {\r
        /* Remove a byte in the past. */\r
        --histogram[data[(pos + i - window_half) & mask]];\r
        --in_window;\r
      }\r
      if (i + window_half < len) {\r
        /* Add a byte in the future. */\r
        ++histogram[data[(pos + i + window_half) & mask]];\r
        ++in_window;\r
      }\r
      histo = histogram[data[(pos + i) & mask]];\r
      if (histo == 0) {\r
        histo = 1;\r
      }\r
      {\r
        double lit_cost = FastLog2(in_window) - FastLog2(histo);\r
        lit_cost += 0.029;\r
        if (lit_cost < 1.0) {\r
          lit_cost *= 0.5;\r
          lit_cost += 0.5;\r
        }\r
        cost[i] = (float)lit_cost;\r
      }\r
    }\r
  }\r
}\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
}  /* extern "C" */\r
#endif\r