beenull/ladybird
1
0
Fork 0
mirror of https://github.com/LadybirdBrowser/ladybird.git synced 2024-11-21 23:20:20 +00:00
Code Issues Projects Releases Packages Wiki Activity Actions 6
ladybird/Libraries/LibCompress/BrotliDictionary.cpp

253 lines
16 KiB
C++
Raw Permalink Normal View History

LibCompress: Implement Brotli decompressor This implements the BrotliDecompressionStream, which is a Core::Stream that can decompress another Core::Stream.
2022-03-31 19:07:45 +00:00
/*
* Copyright (c) 2022, Michiel Visser <opensource@webmichiel.nl>
*
* SPDX-License-Identifier: BSD-2-Clause
*/
#include <AK/Types.h>
#include <LibCompress/BrotliDictionary.h>
// Include the 119.9 KiB of dictionary data from a binary file
extern u8 const brotli_dictionary_data[];
AK+Lagom: Make it possible to build for iOS This commit makes it possible to build AK and most of Lagom for iOS, based on the work for the Ladybird build demoed on discord: https://discord.com/channels/830522505605283862/830525031720943627/1211987732646068314
2024-02-27 13:32:29 +00:00
#if defined(AK_OS_MACOS) || defined(AK_OS_IOS)
LibCompress: Implement Brotli decompressor This implements the BrotliDecompressionStream, which is a Core::Stream that can decompress another Core::Stream.
2022-03-31 19:07:45 +00:00
asm(".const_data\n"
".globl _brotli_dictionary_data\n"
"_brotli_dictionary_data:\n");
Everywhere: Add support for compilation under emscripten Co-Authored-By: Andrew Kaster <akaster@serenityos.org>
2022-11-20 03:23:14 +00:00
#elif defined(AK_OS_EMSCRIPTEN)
asm(".section .data, \"\",@\n"
".global brotli_dictionary_data\n"
"brotli_dictionary_data:\n");
LibCompress: Implement Brotli decompressor This implements the BrotliDecompressionStream, which is a Core::Stream that can decompress another Core::Stream.
2022-03-31 19:07:45 +00:00
#else
asm(".section .rodata\n"
".global brotli_dictionary_data\n"
"brotli_dictionary_data:\n");
#endif
LibCompress: Use a __FILE__-relative path for the brotli dictionary file This makes it so the generated assembly doesn't depend on compile-specific search paths, also making it possible to build with LTO.
2024-01-09 16:50:15 +00:00
asm(".incbin \"" __FILE__ ".dict.bin\"\n"
Everywhere: Add support for compilation under emscripten Co-Authored-By: Andrew Kaster <akaster@serenityos.org>
2022-11-20 03:23:14 +00:00
#if (!defined(AK_OS_WINDOWS) && !defined(AK_OS_EMSCRIPTEN))
LibCompress: Implement Brotli decompressor This implements the BrotliDecompressionStream, which is a Core::Stream that can decompress another Core::Stream.
2022-03-31 19:07:45 +00:00
".previous\n");
Everywhere: Add support for compilation under emscripten Co-Authored-By: Andrew Kaster <akaster@serenityos.org>
2022-11-20 03:23:14 +00:00
#else
);
#endif
LibCompress: Implement Brotli decompressor This implements the BrotliDecompressionStream, which is a Core::Stream that can decompress another Core::Stream.
2022-03-31 19:07:45 +00:00
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<ByteBuffer> 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;
}
}
Reference in a new issue Copy permalink