/* * Copyright (c) 2022, Michiel Visser * * SPDX-License-Identifier: BSD-2-Clause */ #include #include // Include the 119.9 KiB of dictionary data from a binary file extern u8 const brotli_dictionary_data[]; #if defined(AK_OS_MACOS) || defined(AK_OS_IOS) asm(".const_data\n" ".globl _brotli_dictionary_data\n" "_brotli_dictionary_data:\n"); #elif defined(AK_OS_EMSCRIPTEN) asm(".section .data, \"\",@\n" ".global brotli_dictionary_data\n" "brotli_dictionary_data:\n"); #else asm(".section .rodata\n" ".global brotli_dictionary_data\n" "brotli_dictionary_data:\n"); #endif asm(".incbin \"" __FILE__ ".dict.bin\"\n" #if (!defined(AK_OS_WINDOWS) && !defined(AK_OS_EMSCRIPTEN)) ".previous\n"); #else ); #endif namespace Compress { static size_t const bits_by_length[25] { 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 }; static size_t const offset_by_length[25] { 0, 0, 0, 0, 0, 4096, 9216, 21504, 35840, 44032, 53248, 63488, 74752, 87040, 93696, 100864, 104704, 106752, 108928, 113536, 115968, 118528, 119872, 121280, 122016 }; static int ferment(Bytes word, size_t pos) { if (word[pos] < 192) { if (word[pos] >= 97 && word[pos] <= 122) { word[pos] = word[pos] ^ 32; } return 1; } else if (word[pos] < 224) { if (pos + 1 < word.size()) { word[pos + 1] = word[pos + 1] ^ 32; } return 2; } else { if (pos + 2 < word.size()) { word[pos + 2] = word[pos + 2] ^ 5; } return 3; } } static void ferment_first(Bytes word) { if (word.size() > 0) { ferment(word, 0); } } [[maybe_unused]] static void ferment_all(Bytes word) { size_t i = 0; while (i < word.size()) { i += ferment(word, i); } } using BrotliDictionary::TransformationOperation::FermentAll; using BrotliDictionary::TransformationOperation::FermentFirst; using BrotliDictionary::TransformationOperation::Identity; using BrotliDictionary::TransformationOperation::OmitFirst; using BrotliDictionary::TransformationOperation::OmitLast; constexpr static BrotliDictionary::Transformation transformations[121] { // ID Prefix Transform Suffix // -- ------ --------- ------ { ""sv, Identity, 0, ""sv }, // 0 "" Identity "" { ""sv, Identity, 0, " "sv }, // 1 "" Identity " " { " "sv, Identity, 0, " "sv }, // 2 " " Identity " " { ""sv, OmitFirst, 1, ""sv }, // 3 "" OmitFirst1 "" { ""sv, FermentFirst, 0, " "sv }, // 4 "" FermentFirst " " { ""sv, Identity, 0, " the "sv }, // 5 "" Identity " the " { " "sv, Identity, 0, ""sv }, // 6 " " Identity "" { "s "sv, Identity, 0, " "sv }, // 7 "s " Identity " " { ""sv, Identity, 0, " of "sv }, // 8 "" Identity " of " { ""sv, FermentFirst, 0, ""sv }, // 9 "" FermentFirst "" { ""sv, Identity, 0, " and "sv }, // 10 "" Identity " and " { ""sv, OmitFirst, 2, ""sv }, // 11 "" OmitFirst2 "" { ""sv, OmitLast, 1, ""sv }, // 12 "" OmitLast1 "" { ", "sv, Identity, 0, " "sv }, // 13 ", " Identity " " { ""sv, Identity, 0, ", "sv }, // 14 "" Identity ", " { " "sv, FermentFirst, 0, " "sv }, // 15 " " FermentFirst " " { ""sv, Identity, 0, " in "sv }, // 16 "" Identity " in " { ""sv, Identity, 0, " to "sv }, // 17 "" Identity " to " { "e "sv, Identity, 0, " "sv }, // 18 "e " Identity " " { ""sv, Identity, 0, "\""sv }, // 19 "" Identity "\"" { ""sv, Identity, 0, "."sv }, // 20 "" Identity "." { ""sv, Identity, 0, "\">"sv }, // 21 "" Identity "\">" { ""sv, Identity, 0, "\n"sv }, // 22 "" Identity "\n" { ""sv, OmitLast, 3, ""sv }, // 23 "" OmitLast3 "" { ""sv, Identity, 0, "]"sv }, // 24 "" Identity "]" { ""sv, Identity, 0, " for "sv }, // 25 "" Identity " for " { ""sv, OmitFirst, 3, ""sv }, // 26 "" OmitFirst3 "" { ""sv, OmitLast, 2, ""sv }, // 27 "" OmitLast2 "" { ""sv, Identity, 0, " a "sv }, // 28 "" Identity " a " { ""sv, Identity, 0, " that "sv }, // 29 "" Identity " that " { " "sv, FermentFirst, 0, ""sv }, // 30 " " FermentFirst "" { ""sv, Identity, 0, ". "sv }, // 31 "" Identity ". " { "."sv, Identity, 0, ""sv }, // 32 "." Identity "" { " "sv, Identity, 0, ", "sv }, // 33 " " Identity ", " { ""sv, OmitFirst, 4, ""sv }, // 34 "" OmitFirst4 "" { ""sv, Identity, 0, " with "sv }, // 35 "" Identity " with " { ""sv, Identity, 0, "'"sv }, // 36 "" Identity "'" { ""sv, Identity, 0, " from "sv }, // 37 "" Identity " from " { ""sv, Identity, 0, " by "sv }, // 38 "" Identity " by " { ""sv, OmitFirst, 5, ""sv }, // 39 "" OmitFirst5 "" { ""sv, OmitFirst, 6, ""sv }, // 40 "" OmitFirst6 "" { " the "sv, Identity, 0, ""sv }, // 41 " the " Identity "" { ""sv, OmitLast, 4, ""sv }, // 42 "" OmitLast4 "" { ""sv, Identity, 0, ". The "sv }, // 43 "" Identity ". The " { ""sv, FermentAll, 0, ""sv }, // 44 "" FermentAll "" { ""sv, Identity, 0, " on "sv }, // 45 "" Identity " on " { ""sv, Identity, 0, " as "sv }, // 46 "" Identity " as " { ""sv, Identity, 0, " is "sv }, // 47 "" Identity " is " { ""sv, OmitLast, 7, ""sv }, // 48 "" OmitLast7 "" { ""sv, OmitLast, 1, "ing "sv }, // 49 "" OmitLast1 "ing " { ""sv, Identity, 0, "\n\t"sv }, // 50 "" Identity "\n\t" { ""sv, Identity, 0, ":"sv }, // 51 "" Identity ":" { " "sv, Identity, 0, ". "sv }, // 52 " " Identity ". " { ""sv, Identity, 0, "ed "sv }, // 53 "" Identity "ed " { ""sv, OmitFirst, 9, ""sv }, // 54 "" OmitFirst9 "" { ""sv, OmitFirst, 7, ""sv }, // 55 "" OmitFirst7 "" { ""sv, OmitLast, 6, ""sv }, // 56 "" OmitLast6 "" { ""sv, Identity, 0, "("sv }, // 57 "" Identity "(" { ""sv, FermentFirst, 0, ", "sv }, // 58 "" FermentFirst ", " { ""sv, OmitLast, 8, ""sv }, // 59 "" OmitLast8 "" { ""sv, Identity, 0, " at "sv }, // 60 "" Identity " at " { ""sv, Identity, 0, "ly "sv }, // 61 "" Identity "ly " { " the "sv, Identity, 0, " of "sv }, // 62 " the " Identity " of " { ""sv, OmitLast, 5, ""sv }, // 63 "" OmitLast5 "" { ""sv, OmitLast, 9, ""sv }, // 64 "" OmitLast9 "" { " "sv, FermentFirst, 0, ", "sv }, // 65 " " FermentFirst ", " { ""sv, FermentFirst, 0, "\""sv }, // 66 "" FermentFirst "\"" { "."sv, Identity, 0, "("sv }, // 67 "." Identity "(" { ""sv, FermentAll, 0, " "sv }, // 68 "" FermentAll " " { ""sv, FermentFirst, 0, "\">"sv }, // 69 "" FermentFirst "\">" { ""sv, Identity, 0, "=\""sv }, // 70 "" Identity "=\"" { " "sv, Identity, 0, "."sv }, // 71 " " Identity "." { ".com/"sv, Identity, 0, ""sv }, // 72 ".com/" Identity "" { " the "sv, Identity, 0, " of the "sv }, // 73 " the " Identity " of the " { ""sv, FermentFirst, 0, "'"sv }, // 74 "" FermentFirst "'" { ""sv, Identity, 0, ". This "sv }, // 75 "" Identity ". This " { ""sv, Identity, 0, ","sv }, // 76 "" Identity "," { "."sv, Identity, 0, " "sv }, // 77 "." Identity " " { ""sv, FermentFirst, 0, "("sv }, // 78 "" FermentFirst "(" { ""sv, FermentFirst, 0, "."sv }, // 79 "" FermentFirst "." { ""sv, Identity, 0, " not "sv }, // 80 "" Identity " not " { " "sv, Identity, 0, "=\""sv }, // 81 " " Identity "=\"" { ""sv, Identity, 0, "er "sv }, // 82 "" Identity "er " { " "sv, FermentAll, 0, " "sv }, // 83 " " FermentAll " " { ""sv, Identity, 0, "al "sv }, // 84 "" Identity "al " { " "sv, FermentAll, 0, ""sv }, // 85 " " FermentAll "" { ""sv, Identity, 0, "='"sv }, // 86 "" Identity "='" { ""sv, FermentAll, 0, "\""sv }, // 87 "" FermentAll "\"" { ""sv, FermentFirst, 0, ". "sv }, // 88 "" FermentFirst ". " { " "sv, Identity, 0, "("sv }, // 89 " " Identity "(" { ""sv, Identity, 0, "ful "sv }, // 90 "" Identity "ful " { " "sv, FermentFirst, 0, ". "sv }, // 91 " " FermentFirst ". " { ""sv, Identity, 0, "ive "sv }, // 92 "" Identity "ive " { ""sv, Identity, 0, "less "sv }, // 93 "" Identity "less " { ""sv, FermentAll, 0, "'"sv }, // 94 "" FermentAll "'" { ""sv, Identity, 0, "est "sv }, // 95 "" Identity "est " { " "sv, FermentFirst, 0, "."sv }, // 96 " " FermentFirst "." { ""sv, FermentAll, 0, "\">"sv }, // 97 "" FermentAll "\">" { " "sv, Identity, 0, "='"sv }, // 98 " " Identity "='" { ""sv, FermentFirst, 0, ","sv }, // 99 "" FermentFirst "," { ""sv, Identity, 0, "ize "sv }, // 100 "" Identity "ize " { ""sv, FermentAll, 0, "."sv }, // 101 "" FermentAll "." { "\xc2\xa0"sv, Identity, 0, ""sv }, // 102 "\xc2\xa0" Identity "" { " "sv, Identity, 0, ","sv }, // 103 " " Identity "," { ""sv, FermentFirst, 0, "=\""sv }, // 104 "" FermentFirst "=\"" { ""sv, FermentAll, 0, "=\""sv }, // 105 "" FermentAll "=\"" { ""sv, Identity, 0, "ous "sv }, // 106 "" Identity "ous " { ""sv, FermentAll, 0, ", "sv }, // 107 "" FermentAll ", " { ""sv, FermentFirst, 0, "='"sv }, // 108 "" FermentFirst "='" { " "sv, FermentFirst, 0, ","sv }, // 109 " " FermentFirst "," { " "sv, FermentAll, 0, "=\""sv }, // 110 " " FermentAll "=\"" { " "sv, FermentAll, 0, ", "sv }, // 111 " " FermentAll ", " { ""sv, FermentAll, 0, ","sv }, // 112 "" FermentAll "," { ""sv, FermentAll, 0, "("sv }, // 113 "" FermentAll "(" { ""sv, FermentAll, 0, ". "sv }, // 114 "" FermentAll ". " { " "sv, FermentAll, 0, "."sv }, // 115 " " FermentAll "." { ""sv, FermentAll, 0, "='"sv }, // 116 "" FermentAll "='" { " "sv, FermentAll, 0, ". "sv }, // 117 " " FermentAll ". " { " "sv, FermentFirst, 0, "=\""sv }, // 118 " " FermentFirst "=\"" { " "sv, FermentAll, 0, "='"sv }, // 119 " " FermentAll "='" { " "sv, FermentFirst, 0, "='"sv }, // 120 " " FermentFirst "='" }; ErrorOr BrotliDictionary::lookup_word(size_t index, size_t length) { if (length < 4 || length > 24) return Error::from_string_literal("invalid dictionary lookup length"); size_t word_index = index % (1 << bits_by_length[length]); ReadonlyBytes base_word { brotli_dictionary_data + offset_by_length[length] + (word_index * length), length }; size_t transform_id = index >> bits_by_length[length]; if (transform_id >= 121) return Error::from_string_literal("invalid dictionary transformation"); auto transformation = transformations[transform_id]; ByteBuffer bb; bb.append(transformation.prefix.bytes()); size_t prefix_length = bb.size(); switch (transformation.operation) { case TransformationOperation::Identity: bb.append(base_word); break; case TransformationOperation::FermentFirst: bb.append(base_word); ferment_first(bb.bytes().slice(prefix_length)); break; case TransformationOperation::FermentAll: bb.append(base_word); ferment_all(bb.bytes().slice(prefix_length)); break; case TransformationOperation::OmitFirst: if (transformation.operation_data < base_word.size()) bb.append(base_word.slice(transformation.operation_data)); break; case TransformationOperation::OmitLast: if (transformation.operation_data < base_word.size()) bb.append(base_word.slice(0, base_word.size() - transformation.operation_data)); break; } bb.append(transformation.suffix.bytes()); return bb; } }