224 lines
7.2 KiB
C
224 lines
7.2 KiB
C
/* Copyright 2025 Google Inc. All Rights Reserved.
|
|
|
|
Distributed under MIT license.
|
|
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
|
|
*/
|
|
|
|
/* Lookup table for static dictionary and transforms. */
|
|
|
|
#include "static_dict_lut.h"
|
|
|
|
#include "../common/platform.h" /* IWYU pragma: keep */
|
|
#include "../common/static_init.h"
|
|
|
|
#if (BROTLI_STATIC_INIT != BROTLI_STATIC_INIT_NONE)
|
|
#include "../common/dictionary.h"
|
|
#include "../common/transform.h"
|
|
#include "hash_base.h"
|
|
#endif
|
|
|
|
#if defined(__cplusplus) || defined(c_plusplus)
|
|
extern "C" {
|
|
#endif
|
|
|
|
#if (BROTLI_STATIC_INIT != BROTLI_STATIC_INIT_NONE)
|
|
|
|
/* TODO(eustas): deal with largest bucket(s). Not it contains 163 items. */
|
|
static BROTLI_BOOL BROTLI_COLD DoBrotliEncoderInitStaticDictionaryLut(
|
|
const BrotliDictionary* dict, uint16_t* buckets, DictWord* words,
|
|
void* arena) {
|
|
DictWord* slots = (DictWord*)arena;
|
|
uint16_t* heads = (uint16_t*)(slots + BROTLI_ENC_STATIC_DICT_LUT_NUM_ITEMS);
|
|
uint16_t* counts = heads + BROTLI_ENC_STATIC_DICT_LUT_NUM_BUCKETS;
|
|
uint16_t* prev = counts + BROTLI_ENC_STATIC_DICT_LUT_NUM_BUCKETS;
|
|
size_t next_slot = 0;
|
|
uint8_t transformed_word[24];
|
|
uint8_t transformed_other_word[24];
|
|
size_t l;
|
|
size_t pos;
|
|
size_t i;
|
|
|
|
memset(counts, 0, BROTLI_ENC_STATIC_DICT_LUT_NUM_BUCKETS * sizeof(uint16_t));
|
|
memset(heads, 0, BROTLI_ENC_STATIC_DICT_LUT_NUM_BUCKETS * sizeof(uint16_t));
|
|
memset(prev, 0, BROTLI_ENC_STATIC_DICT_LUT_NUM_ITEMS * sizeof(uint16_t));
|
|
|
|
for (l = 4; l <= 24; ++l) {
|
|
size_t n = 1u << dict->size_bits_by_length[l];
|
|
const uint8_t* dict_words = dict->data + dict->offsets_by_length[l];
|
|
for (i = 0; i < n; ++i) {
|
|
const uint8_t* dict_word = dict_words + l * i;
|
|
uint32_t key = Hash15(dict_word);
|
|
slots[next_slot].len = (uint8_t)l;
|
|
slots[next_slot].transform = BROTLI_TRANSFORM_IDENTITY;
|
|
slots[next_slot].idx = (uint16_t)i;
|
|
prev[next_slot] = heads[key];
|
|
heads[key] = (uint16_t)next_slot;
|
|
counts[key]++;
|
|
++next_slot;
|
|
}
|
|
for (i = 0; i < n; ++i) {
|
|
uint32_t key;
|
|
uint32_t prefix;
|
|
BROTLI_BOOL found;
|
|
size_t curr;
|
|
const uint8_t* dict_word = dict_words + l * i;
|
|
if (dict_word[0] < 'a' || dict_word[0] > 'z') continue;
|
|
memcpy(transformed_word, dict_word, l);
|
|
transformed_word[0] = transformed_word[0] - 32;
|
|
key = Hash15(transformed_word);
|
|
prefix = BROTLI_UNALIGNED_LOAD32LE(transformed_word) & ~0x20202020u;
|
|
found = BROTLI_FALSE;
|
|
curr = heads[key];
|
|
while (curr != 0) {
|
|
const uint8_t* other_word;
|
|
uint32_t other_prefix;
|
|
if (slots[curr].len != l) break;
|
|
other_word = dict_words + l * slots[curr].idx;
|
|
other_prefix = BROTLI_UNALIGNED_LOAD32LE(other_word) & ~0x20202020u;
|
|
if (prefix == other_prefix) {
|
|
if (memcmp(transformed_word, other_word, l) == 0) {
|
|
found = BROTLI_TRUE;
|
|
break;
|
|
}
|
|
}
|
|
curr = prev[curr];
|
|
}
|
|
if (found) continue;
|
|
slots[next_slot].len = (uint8_t)l;
|
|
slots[next_slot].transform = BROTLI_TRANSFORM_UPPERCASE_FIRST;
|
|
slots[next_slot].idx = (uint16_t)i;
|
|
prev[next_slot] = heads[key];
|
|
heads[key] = (uint16_t)next_slot;
|
|
counts[key]++;
|
|
++next_slot;
|
|
}
|
|
for (i = 0; i < n; ++i) {
|
|
const uint8_t* dict_word = dict_words + l * i;
|
|
BROTLI_BOOL is_ascii = BROTLI_TRUE;
|
|
BROTLI_BOOL has_lower = BROTLI_FALSE;
|
|
size_t k;
|
|
uint32_t prefix;
|
|
uint32_t key;
|
|
size_t curr;
|
|
BROTLI_BOOL found;
|
|
for (k = 0; k < l; ++k) {
|
|
if (dict_word[k] >= 128) is_ascii = BROTLI_FALSE;
|
|
if (k > 0 && dict_word[k] >= 'a' && dict_word[k] <= 'z')
|
|
has_lower = BROTLI_TRUE;
|
|
}
|
|
if (!is_ascii || !has_lower) continue;
|
|
memcpy(transformed_word, dict_word, l);
|
|
prefix = BROTLI_UNALIGNED_LOAD32LE(transformed_word) & ~0x20202020u;
|
|
for (k = 0; k < l; ++k) {
|
|
if (transformed_word[k] >= 'a' && transformed_word[k] <= 'z') {
|
|
transformed_word[k] = transformed_word[k] - 32;
|
|
}
|
|
}
|
|
key = Hash15(transformed_word);
|
|
found = BROTLI_FALSE;
|
|
curr = heads[key];
|
|
while (curr != 0) {
|
|
const uint8_t* other_word;
|
|
uint32_t other_prefix;
|
|
if (slots[curr].len != l) break;
|
|
other_word = dict_words + l * slots[curr].idx;
|
|
other_prefix = BROTLI_UNALIGNED_LOAD32LE(other_word) & ~0x20202020u;
|
|
if (prefix == other_prefix) {
|
|
if (slots[curr].transform == BROTLI_TRANSFORM_IDENTITY) {
|
|
if (memcmp(transformed_word, other_word, l) == 0) {
|
|
found = BROTLI_TRUE;
|
|
break;
|
|
}
|
|
} else if (slots[curr].transform ==
|
|
BROTLI_TRANSFORM_UPPERCASE_FIRST) {
|
|
if ((transformed_word[0] == (other_word[0] - 32)) &&
|
|
memcmp(transformed_word + 1, other_word + 1, l - 1) == 0) {
|
|
found = BROTLI_TRUE;
|
|
break;
|
|
}
|
|
} else {
|
|
for (k = 0; k < l; ++k) {
|
|
if (other_word[k] >= 'a' && other_word[k] <= 'z') {
|
|
transformed_other_word[k] = other_word[k] - 32;
|
|
} else {
|
|
transformed_other_word[k] = other_word[k];
|
|
}
|
|
}
|
|
if (memcmp(transformed_word, transformed_other_word, l) == 0) {
|
|
found = BROTLI_TRUE;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
curr = prev[curr];
|
|
}
|
|
if (found) {
|
|
continue;
|
|
}
|
|
slots[next_slot].len = (uint8_t)l;
|
|
slots[next_slot].transform = BROTLI_TRANSFORM_UPPERCASE_ALL;
|
|
slots[next_slot].idx = (uint16_t)i;
|
|
prev[next_slot] = heads[key];
|
|
heads[key] = (uint16_t)next_slot;
|
|
counts[key]++;
|
|
++next_slot;
|
|
}
|
|
}
|
|
|
|
if (next_slot != 31704) return BROTLI_FALSE;
|
|
pos = 0;
|
|
/* Unused; makes offsets start from 1. */
|
|
words[pos].len = 0;
|
|
words[pos].transform = 0;
|
|
words[pos].idx = 0;
|
|
pos++;
|
|
for (i = 0; i < BROTLI_ENC_STATIC_DICT_LUT_NUM_BUCKETS; ++i) {
|
|
size_t num_words = counts[i];
|
|
size_t curr;
|
|
if (num_words == 0) {
|
|
buckets[i] = 0;
|
|
continue;
|
|
}
|
|
buckets[i] = (uint16_t)pos;
|
|
curr = heads[i];
|
|
pos += num_words;
|
|
for (size_t k = 0; k < num_words; ++k) {
|
|
words[pos - 1 - k] = slots[curr];
|
|
curr = prev[curr];
|
|
}
|
|
words[pos - 1].len |= 0x80;
|
|
}
|
|
return BROTLI_TRUE;
|
|
}
|
|
|
|
BROTLI_BOOL BrotliEncoderInitStaticDictionaryLut(
|
|
const BrotliDictionary* dict, uint16_t* buckets, DictWord* words) {
|
|
size_t arena_size =
|
|
BROTLI_ENC_STATIC_DICT_LUT_NUM_ITEMS *
|
|
(sizeof(uint16_t) + sizeof(DictWord)) +
|
|
BROTLI_ENC_STATIC_DICT_LUT_NUM_BUCKETS * 2 * sizeof(uint16_t);
|
|
void* arena = malloc(arena_size);
|
|
BROTLI_BOOL ok;
|
|
if (arena == NULL) {
|
|
return BROTLI_FALSE;
|
|
}
|
|
ok = DoBrotliEncoderInitStaticDictionaryLut(dict, buckets, words, arena);
|
|
free(arena);
|
|
return ok;
|
|
}
|
|
|
|
BROTLI_MODEL("small")
|
|
uint16_t kStaticDictionaryBuckets[BROTLI_ENC_STATIC_DICT_LUT_NUM_BUCKETS];
|
|
BROTLI_MODEL("small")
|
|
DictWord kStaticDictionaryWords[BROTLI_ENC_STATIC_DICT_LUT_NUM_ITEMS];
|
|
|
|
#else /* BROTLI_STATIC_INIT */
|
|
|
|
/* Embed kStaticDictionaryBuckets and kStaticDictionaryWords. */
|
|
#include "static_dict_lut_inc.h"
|
|
|
|
#endif /* BROTLI_STATIC_INIT */
|
|
|
|
#if defined(__cplusplus) || defined(c_plusplus)
|
|
} /* extern "C" */
|
|
#endif
|