BrotliDictionary.cpp 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244
  1. /*
  2. * Copyright (c) 2022, Michiel Visser <opensource@webmichiel.nl>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/Types.h>
  7. #include <LibCompress/BrotliDictionary.h>
  8. // Include the 119.9 KiB of dictionary data from a binary file
  9. extern u8 const brotli_dictionary_data[];
  10. #if defined(__APPLE__)
  11. asm(".const_data\n"
  12. ".globl _brotli_dictionary_data\n"
  13. "_brotli_dictionary_data:\n");
  14. #else
  15. asm(".section .rodata\n"
  16. ".global brotli_dictionary_data\n"
  17. "brotli_dictionary_data:\n");
  18. #endif
  19. asm(".incbin \"LibCompress/BrotliDictionaryData.bin\"\n"
  20. ".previous\n");
  21. namespace Compress {
  22. static size_t const bits_by_length[25] {
  23. 0, 0, 0, 0, 10, 10, 11, 11, 10, 10, 10, 10, 10, 9, 9, 8, 7, 7, 8, 7, 7, 6, 6, 5, 5
  24. };
  25. static size_t const offset_by_length[25] {
  26. 0, 0, 0, 0, 0, 4096, 9216, 21504, 35840, 44032, 53248, 63488, 74752, 87040, 93696, 100864,
  27. 104704, 106752, 108928, 113536, 115968, 118528, 119872, 121280, 122016
  28. };
  29. static int ferment(Bytes word, size_t pos)
  30. {
  31. if (word[pos] < 192) {
  32. if (word[pos] >= 97 && word[pos] <= 122) {
  33. word[pos] = word[pos] ^ 32;
  34. }
  35. return 1;
  36. } else if (word[pos] < 224) {
  37. if (pos + 1 < word.size()) {
  38. word[pos + 1] = word[pos + 1] ^ 32;
  39. }
  40. return 2;
  41. } else {
  42. if (pos + 2 < word.size()) {
  43. word[pos + 2] = word[pos + 2] ^ 5;
  44. }
  45. return 3;
  46. }
  47. }
  48. static void ferment_first(Bytes word)
  49. {
  50. if (word.size() > 0) {
  51. ferment(word, 0);
  52. }
  53. }
  54. [[maybe_unused]] static void ferment_all(Bytes word)
  55. {
  56. size_t i = 0;
  57. while (i < word.size()) {
  58. i += ferment(word, i);
  59. }
  60. }
  61. using BrotliDictionary::TransformationOperation::FermentAll;
  62. using BrotliDictionary::TransformationOperation::FermentFirst;
  63. using BrotliDictionary::TransformationOperation::Identity;
  64. using BrotliDictionary::TransformationOperation::OmitFirst;
  65. using BrotliDictionary::TransformationOperation::OmitLast;
  66. constexpr static BrotliDictionary::Transformation transformations[121] {
  67. // ID Prefix Transform Suffix
  68. // -- ------ --------- ------
  69. { ""sv, Identity, 0, ""sv }, // 0 "" Identity ""
  70. { ""sv, Identity, 0, " "sv }, // 1 "" Identity " "
  71. { " "sv, Identity, 0, " "sv }, // 2 " " Identity " "
  72. { ""sv, OmitFirst, 1, ""sv }, // 3 "" OmitFirst1 ""
  73. { ""sv, FermentFirst, 0, " "sv }, // 4 "" FermentFirst " "
  74. { ""sv, Identity, 0, " the "sv }, // 5 "" Identity " the "
  75. { " "sv, Identity, 0, ""sv }, // 6 " " Identity ""
  76. { "s "sv, Identity, 0, " "sv }, // 7 "s " Identity " "
  77. { ""sv, Identity, 0, " of "sv }, // 8 "" Identity " of "
  78. { ""sv, FermentFirst, 0, ""sv }, // 9 "" FermentFirst ""
  79. { ""sv, Identity, 0, " and "sv }, // 10 "" Identity " and "
  80. { ""sv, OmitFirst, 2, ""sv }, // 11 "" OmitFirst2 ""
  81. { ""sv, OmitLast, 1, ""sv }, // 12 "" OmitLast1 ""
  82. { ", "sv, Identity, 0, " "sv }, // 13 ", " Identity " "
  83. { ""sv, Identity, 0, ", "sv }, // 14 "" Identity ", "
  84. { " "sv, FermentFirst, 0, " "sv }, // 15 " " FermentFirst " "
  85. { ""sv, Identity, 0, " in "sv }, // 16 "" Identity " in "
  86. { ""sv, Identity, 0, " to "sv }, // 17 "" Identity " to "
  87. { "e "sv, Identity, 0, " "sv }, // 18 "e " Identity " "
  88. { ""sv, Identity, 0, "\""sv }, // 19 "" Identity "\""
  89. { ""sv, Identity, 0, "."sv }, // 20 "" Identity "."
  90. { ""sv, Identity, 0, "\">"sv }, // 21 "" Identity "\">"
  91. { ""sv, Identity, 0, "\n"sv }, // 22 "" Identity "\n"
  92. { ""sv, OmitLast, 3, ""sv }, // 23 "" OmitLast3 ""
  93. { ""sv, Identity, 0, "]"sv }, // 24 "" Identity "]"
  94. { ""sv, Identity, 0, " for "sv }, // 25 "" Identity " for "
  95. { ""sv, OmitFirst, 3, ""sv }, // 26 "" OmitFirst3 ""
  96. { ""sv, OmitLast, 2, ""sv }, // 27 "" OmitLast2 ""
  97. { ""sv, Identity, 0, " a "sv }, // 28 "" Identity " a "
  98. { ""sv, Identity, 0, " that "sv }, // 29 "" Identity " that "
  99. { " "sv, FermentFirst, 0, ""sv }, // 30 " " FermentFirst ""
  100. { ""sv, Identity, 0, ". "sv }, // 31 "" Identity ". "
  101. { "."sv, Identity, 0, ""sv }, // 32 "." Identity ""
  102. { " "sv, Identity, 0, ", "sv }, // 33 " " Identity ", "
  103. { ""sv, OmitFirst, 4, ""sv }, // 34 "" OmitFirst4 ""
  104. { ""sv, Identity, 0, " with "sv }, // 35 "" Identity " with "
  105. { ""sv, Identity, 0, "'"sv }, // 36 "" Identity "'"
  106. { ""sv, Identity, 0, " from "sv }, // 37 "" Identity " from "
  107. { ""sv, Identity, 0, " by "sv }, // 38 "" Identity " by "
  108. { ""sv, OmitFirst, 5, ""sv }, // 39 "" OmitFirst5 ""
  109. { ""sv, OmitFirst, 6, ""sv }, // 40 "" OmitFirst6 ""
  110. { " the "sv, Identity, 0, ""sv }, // 41 " the " Identity ""
  111. { ""sv, OmitLast, 4, ""sv }, // 42 "" OmitLast4 ""
  112. { ""sv, Identity, 0, ". The "sv }, // 43 "" Identity ". The "
  113. { ""sv, FermentAll, 0, ""sv }, // 44 "" FermentAll ""
  114. { ""sv, Identity, 0, " on "sv }, // 45 "" Identity " on "
  115. { ""sv, Identity, 0, " as "sv }, // 46 "" Identity " as "
  116. { ""sv, Identity, 0, " is "sv }, // 47 "" Identity " is "
  117. { ""sv, OmitLast, 7, ""sv }, // 48 "" OmitLast7 ""
  118. { ""sv, OmitLast, 1, "ing "sv }, // 49 "" OmitLast1 "ing "
  119. { ""sv, Identity, 0, "\n\t"sv }, // 50 "" Identity "\n\t"
  120. { ""sv, Identity, 0, ":"sv }, // 51 "" Identity ":"
  121. { " "sv, Identity, 0, ". "sv }, // 52 " " Identity ". "
  122. { ""sv, Identity, 0, "ed "sv }, // 53 "" Identity "ed "
  123. { ""sv, OmitFirst, 9, ""sv }, // 54 "" OmitFirst9 ""
  124. { ""sv, OmitFirst, 7, ""sv }, // 55 "" OmitFirst7 ""
  125. { ""sv, OmitLast, 6, ""sv }, // 56 "" OmitLast6 ""
  126. { ""sv, Identity, 0, "("sv }, // 57 "" Identity "("
  127. { ""sv, FermentFirst, 0, ", "sv }, // 58 "" FermentFirst ", "
  128. { ""sv, OmitLast, 8, ""sv }, // 59 "" OmitLast8 ""
  129. { ""sv, Identity, 0, " at "sv }, // 60 "" Identity " at "
  130. { ""sv, Identity, 0, "ly "sv }, // 61 "" Identity "ly "
  131. { " the "sv, Identity, 0, " of "sv }, // 62 " the " Identity " of "
  132. { ""sv, OmitLast, 5, ""sv }, // 63 "" OmitLast5 ""
  133. { ""sv, OmitLast, 9, ""sv }, // 64 "" OmitLast9 ""
  134. { " "sv, FermentFirst, 0, ", "sv }, // 65 " " FermentFirst ", "
  135. { ""sv, FermentFirst, 0, "\""sv }, // 66 "" FermentFirst "\""
  136. { "."sv, Identity, 0, "("sv }, // 67 "." Identity "("
  137. { ""sv, FermentAll, 0, " "sv }, // 68 "" FermentAll " "
  138. { ""sv, FermentFirst, 0, "\">"sv }, // 69 "" FermentFirst "\">"
  139. { ""sv, Identity, 0, "=\""sv }, // 70 "" Identity "=\""
  140. { " "sv, Identity, 0, "."sv }, // 71 " " Identity "."
  141. { ".com/"sv, Identity, 0, ""sv }, // 72 ".com/" Identity ""
  142. { " the "sv, Identity, 0, " of the "sv }, // 73 " the " Identity " of the "
  143. { ""sv, FermentFirst, 0, "'"sv }, // 74 "" FermentFirst "'"
  144. { ""sv, Identity, 0, ". This "sv }, // 75 "" Identity ". This "
  145. { ""sv, Identity, 0, ","sv }, // 76 "" Identity ","
  146. { "."sv, Identity, 0, " "sv }, // 77 "." Identity " "
  147. { ""sv, FermentFirst, 0, "("sv }, // 78 "" FermentFirst "("
  148. { ""sv, FermentFirst, 0, "."sv }, // 79 "" FermentFirst "."
  149. { ""sv, Identity, 0, " not "sv }, // 80 "" Identity " not "
  150. { " "sv, Identity, 0, "=\""sv }, // 81 " " Identity "=\""
  151. { ""sv, Identity, 0, "er "sv }, // 82 "" Identity "er "
  152. { " "sv, FermentAll, 0, " "sv }, // 83 " " FermentAll " "
  153. { ""sv, Identity, 0, "al "sv }, // 84 "" Identity "al "
  154. { " "sv, FermentAll, 0, ""sv }, // 85 " " FermentAll ""
  155. { ""sv, Identity, 0, "='"sv }, // 86 "" Identity "='"
  156. { ""sv, FermentAll, 0, "\""sv }, // 87 "" FermentAll "\""
  157. { ""sv, FermentFirst, 0, ". "sv }, // 88 "" FermentFirst ". "
  158. { " "sv, Identity, 0, "("sv }, // 89 " " Identity "("
  159. { ""sv, Identity, 0, "ful "sv }, // 90 "" Identity "ful "
  160. { " "sv, FermentFirst, 0, ". "sv }, // 91 " " FermentFirst ". "
  161. { ""sv, Identity, 0, "ive "sv }, // 92 "" Identity "ive "
  162. { ""sv, Identity, 0, "less "sv }, // 93 "" Identity "less "
  163. { ""sv, FermentAll, 0, "'"sv }, // 94 "" FermentAll "'"
  164. { ""sv, Identity, 0, "est "sv }, // 95 "" Identity "est "
  165. { " "sv, FermentFirst, 0, "."sv }, // 96 " " FermentFirst "."
  166. { ""sv, FermentAll, 0, "\">"sv }, // 97 "" FermentAll "\">"
  167. { " "sv, Identity, 0, "='"sv }, // 98 " " Identity "='"
  168. { ""sv, FermentFirst, 0, ","sv }, // 99 "" FermentFirst ","
  169. { ""sv, Identity, 0, "ize "sv }, // 100 "" Identity "ize "
  170. { ""sv, FermentAll, 0, "."sv }, // 101 "" FermentAll "."
  171. { "\xc2\xa0"sv, Identity, 0, ""sv }, // 102 "\xc2\xa0" Identity ""
  172. { " "sv, Identity, 0, ","sv }, // 103 " " Identity ","
  173. { ""sv, FermentFirst, 0, "=\""sv }, // 104 "" FermentFirst "=\""
  174. { ""sv, FermentAll, 0, "=\""sv }, // 105 "" FermentAll "=\""
  175. { ""sv, Identity, 0, "ous "sv }, // 106 "" Identity "ous "
  176. { ""sv, FermentAll, 0, ", "sv }, // 107 "" FermentAll ", "
  177. { ""sv, FermentFirst, 0, "='"sv }, // 108 "" FermentFirst "='"
  178. { " "sv, FermentFirst, 0, ","sv }, // 109 " " FermentFirst ","
  179. { " "sv, FermentAll, 0, "=\""sv }, // 110 " " FermentAll "=\""
  180. { " "sv, FermentAll, 0, ", "sv }, // 111 " " FermentAll ", "
  181. { ""sv, FermentAll, 0, ","sv }, // 112 "" FermentAll ","
  182. { ""sv, FermentAll, 0, "("sv }, // 113 "" FermentAll "("
  183. { ""sv, FermentAll, 0, ". "sv }, // 114 "" FermentAll ". "
  184. { " "sv, FermentAll, 0, "."sv }, // 115 " " FermentAll "."
  185. { ""sv, FermentAll, 0, "='"sv }, // 116 "" FermentAll "='"
  186. { " "sv, FermentAll, 0, ". "sv }, // 117 " " FermentAll ". "
  187. { " "sv, FermentFirst, 0, "=\""sv }, // 118 " " FermentFirst "=\""
  188. { " "sv, FermentAll, 0, "='"sv }, // 119 " " FermentAll "='"
  189. { " "sv, FermentFirst, 0, "='"sv }, // 120 " " FermentFirst "='"
  190. };
  191. ErrorOr<ByteBuffer> BrotliDictionary::lookup_word(size_t index, size_t length)
  192. {
  193. if (length < 4 || length > 24)
  194. return Error::from_string_literal("invalid dictionary lookup length");
  195. size_t word_index = index % (1 << bits_by_length[length]);
  196. ReadonlyBytes base_word { brotli_dictionary_data + offset_by_length[length] + (word_index * length), length };
  197. size_t transform_id = index >> bits_by_length[length];
  198. if (transform_id >= 121)
  199. return Error::from_string_literal("invalid dictionary transformation");
  200. auto transformation = transformations[transform_id];
  201. ByteBuffer bb;
  202. bb.append(transformation.prefix.bytes());
  203. size_t prefix_length = bb.size();
  204. switch (transformation.operation) {
  205. case TransformationOperation::Identity:
  206. bb.append(base_word);
  207. break;
  208. case TransformationOperation::FermentFirst:
  209. bb.append(base_word);
  210. ferment_first(bb.bytes().slice(prefix_length));
  211. break;
  212. case TransformationOperation::FermentAll:
  213. bb.append(base_word);
  214. ferment_all(bb.bytes().slice(prefix_length));
  215. break;
  216. case TransformationOperation::OmitFirst:
  217. if (transformation.operation_data < base_word.size())
  218. bb.append(base_word.slice(transformation.operation_data));
  219. break;
  220. case TransformationOperation::OmitLast:
  221. if (transformation.operation_data < base_word.size())
  222. bb.append(base_word.slice(0, base_word.size() - transformation.operation_data));
  223. break;
  224. }
  225. bb.append(transformation.suffix.bytes());
  226. return bb;
  227. }
  228. }