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

[mirror_edk2.git] / BaseTools / Source / C / BrotliCompress / enc / static_dict.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
#include "./static_dict.h"\r
\r
#include "../common/dictionary.h"\r
#include "./find_match_length.h"\r
#include "./port.h"\r
#include "./static_dict_lut.h"\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
extern "C" {\r
#endif\r
\r
static const uint8_t kUppercaseFirst = 10;\r
static const uint8_t kOmitLastNTransforms[10] = {\r
  0, 12, 27, 23, 42, 63, 56, 48, 59, 64,\r
};\r
\r
static BROTLI_INLINE uint32_t Hash(const uint8_t *data) {\r
  uint32_t h = BROTLI_UNALIGNED_LOAD32(data) * kDictHashMul32;\r
  /* The higher bits contain more mixture from the multiplication,\r
     so we take our results from there. */\r
  return h >> (32 - kDictNumBits);\r
}\r
\r
static BROTLI_INLINE void AddMatch(size_t distance, size_t len, size_t len_code,\r
                                   uint32_t* matches) {\r
  uint32_t match = (uint32_t)((distance << 5) + len_code);\r
  matches[len] = BROTLI_MIN(uint32_t, matches[len], match);\r
}\r
\r
static BROTLI_INLINE size_t DictMatchLength(const uint8_t* data,\r
                                            size_t id,\r
                                            size_t len,\r
                                            size_t maxlen) {\r
  const size_t offset = kBrotliDictionaryOffsetsByLength[len] + len * id;\r
  return FindMatchLengthWithLimit(&kBrotliDictionary[offset], data,\r
                                  BROTLI_MIN(size_t, len, maxlen));\r
}\r
\r
static BROTLI_INLINE BROTLI_BOOL IsMatch(\r
    DictWord w, const uint8_t* data, size_t max_length) {\r
  if (w.len > max_length) {\r
    return BROTLI_FALSE;\r
  } else {\r
    const size_t offset = kBrotliDictionaryOffsetsByLength[w.len] +\r
        (size_t)w.len * (size_t)w.idx;\r
    const uint8_t* dict = &kBrotliDictionary[offset];\r
    if (w.transform == 0) {\r
      /* Match against base dictionary word. */\r
      return\r
          TO_BROTLI_BOOL(FindMatchLengthWithLimit(dict, data, w.len) == w.len);\r
    } else if (w.transform == 10) {\r
      /* Match against uppercase first transform.\r
         Note that there are only ASCII uppercase words in the lookup table. */\r
      return TO_BROTLI_BOOL(dict[0] >= 'a' && dict[0] <= 'z' &&\r
              (dict[0] ^ 32) == data[0] &&\r
              FindMatchLengthWithLimit(&dict[1], &data[1], w.len - 1u) ==\r
              w.len - 1u);\r
    } else {\r
      /* Match against uppercase all transform.\r
         Note that there are only ASCII uppercase words in the lookup table. */\r
      size_t i;\r
      for (i = 0; i < w.len; ++i) {\r
        if (dict[i] >= 'a' && dict[i] <= 'z') {\r
          if ((dict[i] ^ 32) != data[i]) return BROTLI_FALSE;\r
        } else {\r
          if (dict[i] != data[i]) return BROTLI_FALSE;\r
        }\r
      }\r
      return BROTLI_TRUE;\r
    }\r
  }\r
}\r
\r
BROTLI_BOOL BrotliFindAllStaticDictionaryMatches(\r
    const uint8_t* data, size_t min_length, size_t max_length,\r
    uint32_t* matches) {\r
  BROTLI_BOOL has_found_match = BROTLI_FALSE;\r
  {\r
    size_t offset = kStaticDictionaryBuckets[Hash(data)];\r
    BROTLI_BOOL end = !offset;\r
    while (!end) {\r
      DictWord w = kStaticDictionaryWords[offset++];\r
      const size_t l = w.len & 0x7F;\r
      const size_t n = (size_t)1 << kBrotliDictionarySizeBitsByLength[l];\r
      const size_t id = w.idx;\r
      end = !!(w.len & 0x80);\r
      w.len = (uint8_t)l;\r
      if (w.transform == 0) {\r
        const size_t matchlen = DictMatchLength(data, id, l, max_length);\r
        const uint8_t* s;\r
        size_t minlen;\r
        size_t maxlen;\r
        size_t len;\r
        /* Transform "" + kIdentity + "" */\r
        if (matchlen == l) {\r
          AddMatch(id, l, l, matches);\r
          has_found_match = BROTLI_TRUE;\r
        }\r
        /* Transforms "" + kOmitLast1 + "" and "" + kOmitLast1 + "ing " */\r
        if (matchlen >= l - 1) {\r
          AddMatch(id + 12 * n, l - 1, l, matches);\r
          if (l + 2 < max_length &&\r
              data[l - 1] == 'i' && data[l] == 'n' && data[l + 1] == 'g' &&\r
              data[l + 2] == ' ') {\r
            AddMatch(id + 49 * n, l + 3, l, matches);\r
          }\r
          has_found_match = BROTLI_TRUE;\r
        }\r
        /* Transform "" + kOmitLastN + "" (N = 2 .. 9) */\r
        minlen = min_length;\r
        if (l > 9) minlen = BROTLI_MAX(size_t, minlen, l - 9);\r
        maxlen = BROTLI_MIN(size_t, matchlen, l - 2);\r
        for (len = minlen; len <= maxlen; ++len) {\r
          AddMatch(id + kOmitLastNTransforms[l - len] * n, len, l, matches);\r
          has_found_match = BROTLI_TRUE;\r
        }\r
        if (matchlen < l || l + 6 >= max_length) {\r
          continue;\r
        }\r
        s = &data[l];\r
        /* Transforms "" + kIdentity + <suffix> */\r
        if (s[0] == ' ') {\r
          AddMatch(id + n, l + 1, l, matches);\r
          if (s[1] == 'a') {\r
            if (s[2] == ' ') {\r
              AddMatch(id + 28 * n, l + 3, l, matches);\r
            } else if (s[2] == 's') {\r
              if (s[3] == ' ') AddMatch(id + 46 * n, l + 4, l, matches);\r
            } else if (s[2] == 't') {\r
              if (s[3] == ' ') AddMatch(id + 60 * n, l + 4, l, matches);\r
            } else if (s[2] == 'n') {\r
              if (s[3] == 'd' && s[4] == ' ') {\r
                AddMatch(id + 10 * n, l + 5, l, matches);\r
              }\r
            }\r
          } else if (s[1] == 'b') {\r
            if (s[2] == 'y' && s[3] == ' ') {\r
              AddMatch(id + 38 * n, l + 4, l, matches);\r
            }\r
          } else if (s[1] == 'i') {\r
            if (s[2] == 'n') {\r
              if (s[3] == ' ') AddMatch(id + 16 * n, l + 4, l, matches);\r
            } else if (s[2] == 's') {\r
              if (s[3] == ' ') AddMatch(id + 47 * n, l + 4, l, matches);\r
            }\r
          } else if (s[1] == 'f') {\r
            if (s[2] == 'o') {\r
              if (s[3] == 'r' && s[4] == ' ') {\r
                AddMatch(id + 25 * n, l + 5, l, matches);\r
              }\r
            } else if (s[2] == 'r') {\r
              if (s[3] == 'o' && s[4] == 'm' && s[5] == ' ') {\r
                AddMatch(id + 37 * n, l + 6, l, matches);\r
              }\r
            }\r
          } else if (s[1] == 'o') {\r
            if (s[2] == 'f') {\r
              if (s[3] == ' ') AddMatch(id + 8 * n, l + 4, l, matches);\r
            } else if (s[2] == 'n') {\r
              if (s[3] == ' ') AddMatch(id + 45 * n, l + 4, l, matches);\r
            }\r
          } else if (s[1] == 'n') {\r
            if (s[2] == 'o' && s[3] == 't' && s[4] == ' ') {\r
              AddMatch(id + 80 * n, l + 5, l, matches);\r
            }\r
          } else if (s[1] == 't') {\r
            if (s[2] == 'h') {\r
              if (s[3] == 'e') {\r
                if (s[4] == ' ') AddMatch(id + 5 * n, l + 5, l, matches);\r
              } else if (s[3] == 'a') {\r
                if (s[4] == 't' && s[5] == ' ') {\r
                  AddMatch(id + 29 * n, l + 6, l, matches);\r
                }\r
              }\r
            } else if (s[2] == 'o') {\r
              if (s[3] == ' ') AddMatch(id + 17 * n, l + 4, l, matches);\r
            }\r
          } else if (s[1] == 'w') {\r
            if (s[2] == 'i' && s[3] == 't' && s[4] == 'h' && s[5] == ' ') {\r
              AddMatch(id + 35 * n, l + 6, l, matches);\r
            }\r
          }\r
        } else if (s[0] == '"') {\r
          AddMatch(id + 19 * n, l + 1, l, matches);\r
          if (s[1] == '>') {\r
            AddMatch(id + 21 * n, l + 2, l, matches);\r
          }\r
        } else if (s[0] == '.') {\r
          AddMatch(id + 20 * n, l + 1, l, matches);\r
          if (s[1] == ' ') {\r
            AddMatch(id + 31 * n, l + 2, l, matches);\r
            if (s[2] == 'T' && s[3] == 'h') {\r
              if (s[4] == 'e') {\r
                if (s[5] == ' ') AddMatch(id + 43 * n, l + 6, l, matches);\r
              } else if (s[4] == 'i') {\r
                if (s[5] == 's' && s[6] == ' ') {\r
                  AddMatch(id + 75 * n, l + 7, l, matches);\r
                }\r
              }\r
            }\r
          }\r
        } else if (s[0] == ',') {\r
          AddMatch(id + 76 * n, l + 1, l, matches);\r
          if (s[1] == ' ') {\r
            AddMatch(id + 14 * n, l + 2, l, matches);\r
          }\r
        } else if (s[0] == '\n') {\r
          AddMatch(id + 22 * n, l + 1, l, matches);\r
          if (s[1] == '\t') {\r
            AddMatch(id + 50 * n, l + 2, l, matches);\r
          }\r
        } else if (s[0] == ']') {\r
          AddMatch(id + 24 * n, l + 1, l, matches);\r
        } else if (s[0] == '\'') {\r
          AddMatch(id + 36 * n, l + 1, l, matches);\r
        } else if (s[0] == ':') {\r
          AddMatch(id + 51 * n, l + 1, l, matches);\r
        } else if (s[0] == '(') {\r
          AddMatch(id + 57 * n, l + 1, l, matches);\r
        } else if (s[0] == '=') {\r
          if (s[1] == '"') {\r
            AddMatch(id + 70 * n, l + 2, l, matches);\r
          } else if (s[1] == '\'') {\r
            AddMatch(id + 86 * n, l + 2, l, matches);\r
          }\r
        } else if (s[0] == 'a') {\r
          if (s[1] == 'l' && s[2] == ' ') {\r
            AddMatch(id + 84 * n, l + 3, l, matches);\r
          }\r
        } else if (s[0] == 'e') {\r
          if (s[1] == 'd') {\r
            if (s[2] == ' ') AddMatch(id + 53 * n, l + 3, l, matches);\r
          } else if (s[1] == 'r') {\r
            if (s[2] == ' ') AddMatch(id + 82 * n, l + 3, l, matches);\r
          } else if (s[1] == 's') {\r
            if (s[2] == 't' && s[3] == ' ') {\r
              AddMatch(id + 95 * n, l + 4, l, matches);\r
            }\r
          }\r
        } else if (s[0] == 'f') {\r
          if (s[1] == 'u' && s[2] == 'l' && s[3] == ' ') {\r
            AddMatch(id + 90 * n, l + 4, l, matches);\r
          }\r
        } else if (s[0] == 'i') {\r
          if (s[1] == 'v') {\r
            if (s[2] == 'e' && s[3] == ' ') {\r
              AddMatch(id + 92 * n, l + 4, l, matches);\r
            }\r
          } else if (s[1] == 'z') {\r
            if (s[2] == 'e' && s[3] == ' ') {\r
              AddMatch(id + 100 * n, l + 4, l, matches);\r
            }\r
          }\r
        } else if (s[0] == 'l') {\r
          if (s[1] == 'e') {\r
            if (s[2] == 's' && s[3] == 's' && s[4] == ' ') {\r
              AddMatch(id + 93 * n, l + 5, l, matches);\r
            }\r
          } else if (s[1] == 'y') {\r
            if (s[2] == ' ') AddMatch(id + 61 * n, l + 3, l, matches);\r
          }\r
        } else if (s[0] == 'o') {\r
          if (s[1] == 'u' && s[2] == 's' && s[3] == ' ') {\r
            AddMatch(id + 106 * n, l + 4, l, matches);\r
          }\r
        }\r
      } else {\r
        /* Set is_all_caps=0 for kUppercaseFirst and\r
               is_all_caps=1 otherwise (kUppercaseAll) transform. */\r
        const BROTLI_BOOL is_all_caps =\r
            TO_BROTLI_BOOL(w.transform != kUppercaseFirst);\r
        const uint8_t* s;\r
        if (!IsMatch(w, data, max_length)) {\r
          continue;\r
        }\r
        /* Transform "" + kUppercase{First,All} + "" */\r
        AddMatch(id + (is_all_caps ? 44 : 9) * n, l, l, matches);\r
        has_found_match = BROTLI_TRUE;\r
        if (l + 1 >= max_length) {\r
          continue;\r
        }\r
        /* Transforms "" + kUppercase{First,All} + <suffix> */\r
        s = &data[l];\r
        if (s[0] == ' ') {\r
          AddMatch(id + (is_all_caps ? 68 : 4) * n, l + 1, l, matches);\r
        } else if (s[0] == '"') {\r
          AddMatch(id + (is_all_caps ? 87 : 66) * n, l + 1, l, matches);\r
          if (s[1] == '>') {\r
            AddMatch(id + (is_all_caps ? 97 : 69) * n, l + 2, l, matches);\r
          }\r
        } else if (s[0] == '.') {\r
          AddMatch(id + (is_all_caps ? 101 : 79) * n, l + 1, l, matches);\r
          if (s[1] == ' ') {\r
            AddMatch(id + (is_all_caps ? 114 : 88) * n, l + 2, l, matches);\r
          }\r
        } else if (s[0] == ',') {\r
          AddMatch(id + (is_all_caps ? 112 : 99) * n, l + 1, l, matches);\r
          if (s[1] == ' ') {\r
            AddMatch(id + (is_all_caps ? 107 : 58) * n, l + 2, l, matches);\r
          }\r
        } else if (s[0] == '\'') {\r
          AddMatch(id + (is_all_caps ? 94 : 74) * n, l + 1, l, matches);\r
        } else if (s[0] == '(') {\r
          AddMatch(id + (is_all_caps ? 113 : 78) * n, l + 1, l, matches);\r
        } else if (s[0] == '=') {\r
          if (s[1] == '"') {\r
            AddMatch(id + (is_all_caps ? 105 : 104) * n, l + 2, l, matches);\r
          } else if (s[1] == '\'') {\r
            AddMatch(id + (is_all_caps ? 116 : 108) * n, l + 2, l, matches);\r
          }\r
        }\r
      }\r
    }\r
  }\r
  /* Transforms with prefixes " " and "." */\r
  if (max_length >= 5 && (data[0] == ' ' || data[0] == '.')) {\r
    BROTLI_BOOL is_space = TO_BROTLI_BOOL(data[0] == ' ');\r
    size_t offset = kStaticDictionaryBuckets[Hash(&data[1])];\r
    BROTLI_BOOL end = !offset;\r
    while (!end) {\r
      DictWord w = kStaticDictionaryWords[offset++];\r
      const size_t l = w.len & 0x7F;\r
      const size_t n = (size_t)1 << kBrotliDictionarySizeBitsByLength[l];\r
      const size_t id = w.idx;\r
      end = !!(w.len & 0x80);\r
      w.len = (uint8_t)l;\r
      if (w.transform == 0) {\r
        const uint8_t* s;\r
        if (!IsMatch(w, &data[1], max_length - 1)) {\r
          continue;\r
        }\r
        /* Transforms " " + kIdentity + "" and "." + kIdentity + "" */\r
        AddMatch(id + (is_space ? 6 : 32) * n, l + 1, l, matches);\r
        has_found_match = BROTLI_TRUE;\r
        if (l + 2 >= max_length) {\r
          continue;\r
        }\r
        /* Transforms " " + kIdentity + <suffix> and "." + kIdentity + <suffix>\r
        */\r
        s = &data[l + 1];\r
        if (s[0] == ' ') {\r
          AddMatch(id + (is_space ? 2 : 77) * n, l + 2, l, matches);\r
        } else if (s[0] == '(') {\r
          AddMatch(id + (is_space ? 89 : 67) * n, l + 2, l, matches);\r
        } else if (is_space) {\r
          if (s[0] == ',') {\r
            AddMatch(id + 103 * n, l + 2, l, matches);\r
            if (s[1] == ' ') {\r
              AddMatch(id + 33 * n, l + 3, l, matches);\r
            }\r
          } else if (s[0] == '.') {\r
            AddMatch(id + 71 * n, l + 2, l, matches);\r
            if (s[1] == ' ') {\r
              AddMatch(id + 52 * n, l + 3, l, matches);\r
            }\r
          } else if (s[0] == '=') {\r
            if (s[1] == '"') {\r
              AddMatch(id + 81 * n, l + 3, l, matches);\r
            } else if (s[1] == '\'') {\r
              AddMatch(id + 98 * n, l + 3, l, matches);\r
            }\r
          }\r
        }\r
      } else if (is_space) {\r
        /* Set is_all_caps=0 for kUppercaseFirst and\r
               is_all_caps=1 otherwise (kUppercaseAll) transform. */\r
        const BROTLI_BOOL is_all_caps =\r
            TO_BROTLI_BOOL(w.transform != kUppercaseFirst);\r
        const uint8_t* s;\r
        if (!IsMatch(w, &data[1], max_length - 1)) {\r
          continue;\r
        }\r
        /* Transforms " " + kUppercase{First,All} + "" */\r
        AddMatch(id + (is_all_caps ? 85 : 30) * n, l + 1, l, matches);\r
        has_found_match = BROTLI_TRUE;\r
        if (l + 2 >= max_length) {\r
          continue;\r
        }\r
        /* Transforms " " + kUppercase{First,All} + <suffix> */\r
        s = &data[l + 1];\r
        if (s[0] == ' ') {\r
          AddMatch(id + (is_all_caps ? 83 : 15) * n, l + 2, l, matches);\r
        } else if (s[0] == ',') {\r
          if (!is_all_caps) {\r
            AddMatch(id + 109 * n, l + 2, l, matches);\r
          }\r
          if (s[1] == ' ') {\r
            AddMatch(id + (is_all_caps ? 111 : 65) * n, l + 3, l, matches);\r
          }\r
        } else if (s[0] == '.') {\r
          AddMatch(id + (is_all_caps ? 115 : 96) * n, l + 2, l, matches);\r
          if (s[1] == ' ') {\r
            AddMatch(id + (is_all_caps ? 117 : 91) * n, l + 3, l, matches);\r
          }\r
        } else if (s[0] == '=') {\r
          if (s[1] == '"') {\r
            AddMatch(id + (is_all_caps ? 110 : 118) * n, l + 3, l, matches);\r
          } else if (s[1] == '\'') {\r
            AddMatch(id + (is_all_caps ? 119 : 120) * n, l + 3, l, matches);\r
          }\r
        }\r
      }\r
    }\r
  }\r
  if (max_length >= 6) {\r
    /* Transforms with prefixes "e ", "s ", ", " and "\xc2\xa0" */\r
    if ((data[1] == ' ' &&\r
         (data[0] == 'e' || data[0] == 's' || data[0] == ',')) ||\r
        (data[0] == 0xc2 && data[1] == 0xa0)) {\r
      size_t offset = kStaticDictionaryBuckets[Hash(&data[2])];\r
      BROTLI_BOOL end = !offset;\r
      while (!end) {\r
        DictWord w = kStaticDictionaryWords[offset++];\r
        const size_t l = w.len & 0x7F;\r
        const size_t n = (size_t)1 << kBrotliDictionarySizeBitsByLength[l];\r
        const size_t id = w.idx;\r
        end = !!(w.len & 0x80);\r
        w.len = (uint8_t)l;\r
        if (w.transform == 0 && IsMatch(w, &data[2], max_length - 2)) {\r
          if (data[0] == 0xc2) {\r
            AddMatch(id + 102 * n, l + 2, l, matches);\r
            has_found_match = BROTLI_TRUE;\r
          } else if (l + 2 < max_length && data[l + 2] == ' ') {\r
            size_t t = data[0] == 'e' ? 18 : (data[0] == 's' ? 7 : 13);\r
            AddMatch(id + t * n, l + 3, l, matches);\r
            has_found_match = BROTLI_TRUE;\r
          }\r
        }\r
      }\r
    }\r
  }\r
  if (max_length >= 9) {\r
    /* Transforms with prefixes " the " and ".com/" */\r
    if ((data[0] == ' ' && data[1] == 't' && data[2] == 'h' &&\r
         data[3] == 'e' && data[4] == ' ') ||\r
        (data[0] == '.' && data[1] == 'c' && data[2] == 'o' &&\r
         data[3] == 'm' && data[4] == '/')) {\r
      size_t offset = kStaticDictionaryBuckets[Hash(&data[5])];\r
      BROTLI_BOOL end = !offset;\r
      while (!end) {\r
        DictWord w = kStaticDictionaryWords[offset++];\r
        const size_t l = w.len & 0x7F;\r
        const size_t n = (size_t)1 << kBrotliDictionarySizeBitsByLength[l];\r
        const size_t id = w.idx;\r
        end = !!(w.len & 0x80);\r
        w.len = (uint8_t)l;\r
        if (w.transform == 0 && IsMatch(w, &data[5], max_length - 5)) {\r
          AddMatch(id + (data[0] == ' ' ? 41 : 72) * n, l + 5, l, matches);\r
          has_found_match = BROTLI_TRUE;\r
          if (l + 5 < max_length) {\r
            const uint8_t* s = &data[l + 5];\r
            if (data[0] == ' ') {\r
              if (l + 8 < max_length &&\r
                  s[0] == ' ' && s[1] == 'o' && s[2] == 'f' && s[3] == ' ') {\r
                AddMatch(id + 62 * n, l + 9, l, matches);\r
                if (l + 12 < max_length &&\r
                    s[4] == 't' && s[5] == 'h' && s[6] == 'e' && s[7] == ' ') {\r
                  AddMatch(id + 73 * n, l + 13, l, matches);\r
                }\r
              }\r
            }\r
          }\r
        }\r
      }\r
    }\r
  }\r
  return has_found_match;\r
}\r
\r
#if defined(__cplusplus) || defined(c_plusplus)\r
}  /* extern "C" */\r
#endif\r