From eb12ec04ebb0e9ebb95bb2f13d1edfb62d7ae51d Mon Sep 17 00:00:00 2001 From: Eugene Kliuchnikov Date: Wed, 20 Jun 2018 15:14:10 +0200 Subject: Update (#688) * add rolling-composite-hasher for large-window mode * make API methods explicitly public --- c/common/platform.h | 206 +------------------------------------- c/enc/backward_references.c | 15 +++ c/enc/hash.h | 56 ++++++++++- c/enc/hash_composite_inc.h | 133 +++++++++++++++++++++++++ c/enc/hash_rolling_inc.h | 215 ++++++++++++++++++++++++++++++++++++++++ c/enc/quality.h | 18 ++++ c/include/brotli/port.h | 237 +++++++++++++++++++++++++++++++++++++++++++- 7 files changed, 667 insertions(+), 213 deletions(-) create mode 100755 c/enc/hash_composite_inc.h create mode 100755 c/enc/hash_rolling_inc.h diff --git a/c/common/platform.h b/c/common/platform.h index 3fd0305..9f303bc 100755 --- a/c/common/platform.h +++ b/c/common/platform.h @@ -51,210 +51,6 @@ /* >>> >>> >>> hedley macros */ -#define BROTLI_MAKE_VERSION(major, minor, revision) \ - (((major) * 1000000) + ((minor) * 1000) + (revision)) - -#if defined(__GNUC__) && defined(__GNUC_PATCHLEVEL__) -#define BROTLI_GNUC_VERSION \ - BROTLI_MAKE_VERSION(__GNUC__, __GNUC_MINOR__, __GNUC_PATCHLEVEL__) -#elif defined(__GNUC__) -#define BROTLI_GNUC_VERSION BROTLI_MAKE_VERSION(__GNUC__, __GNUC_MINOR__, 0) -#endif - -#if defined(BROTLI_GNUC_VERSION) -#define BROTLI_GNUC_VERSION_CHECK(major, minor, patch) \ - (BROTLI_GNUC_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_GNUC_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(_MSC_FULL_VER) && (_MSC_FULL_VER >= 140000000) -#define BROTLI_MSVC_VERSION \ - BROTLI_MAKE_VERSION((_MSC_FULL_VER / 10000000), \ - (_MSC_FULL_VER % 10000000) / 100000, \ - (_MSC_FULL_VER % 100000) / 100) -#elif defined(_MSC_FULL_VER) -#define BROTLI_MSVC_VERSION \ - BROTLI_MAKE_VERSION((_MSC_FULL_VER / 1000000), \ - (_MSC_FULL_VER % 1000000) / 10000, \ - (_MSC_FULL_VER % 10000) / 10) -#elif defined(_MSC_VER) -#define BROTLI_MSVC_VERSION \ - BROTLI_MAKE_VERSION(_MSC_VER / 100, _MSC_VER % 100, 0) -#endif - -#if !defined(_MSC_VER) -#define BROTLI_MSVC_VERSION_CHECK(major, minor, patch) (0) -#elif defined(_MSC_VER) && (_MSC_VER >= 1400) -#define BROTLI_MSVC_VERSION_CHECK(major, minor, patch) \ - (_MSC_FULL_VER >= ((major * 10000000) + (minor * 100000) + (patch))) -#elif defined(_MSC_VER) && (_MSC_VER >= 1200) -#define BROTLI_MSVC_VERSION_CHECK(major, minor, patch) \ - (_MSC_FULL_VER >= ((major * 1000000) + (minor * 10000) + (patch))) -#else -#define BROTLI_MSVC_VERSION_CHECK(major, minor, patch) \ - (_MSC_VER >= ((major * 100) + (minor))) -#endif - -#if defined(__INTEL_COMPILER) && defined(__INTEL_COMPILER_UPDATE) -#define BROTLI_INTEL_VERSION \ - BROTLI_MAKE_VERSION(__INTEL_COMPILER / 100, \ - __INTEL_COMPILER % 100, \ - __INTEL_COMPILER_UPDATE) -#elif defined(__INTEL_COMPILER) -#define BROTLI_INTEL_VERSION \ - BROTLI_MAKE_VERSION(__INTEL_COMPILER / 100, __INTEL_COMPILER % 100, 0) -#endif - -#if defined(BROTLI_INTEL_VERSION) -#define BROTLI_INTEL_VERSION_CHECK(major, minor, patch) \ - (BROTLI_INTEL_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_INTEL_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(__PGI) && \ - defined(__PGIC__) && defined(__PGIC_MINOR__) && defined(__PGIC_PATCHLEVEL__) -#define BROTLI_PGI_VERSION \ - BROTLI_MAKE_VERSION(__PGIC__, __PGIC_MINOR__, __PGIC_PATCHLEVEL__) -#endif - -#if defined(BROTLI_PGI_VERSION) -#define BROTLI_PGI_VERSION_CHECK(major, minor, patch) \ - (BROTLI_PGI_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_PGI_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(__SUNPRO_C) && (__SUNPRO_C > 0x1000) -#define BROTLI_SUNPRO_VERSION \ - BROTLI_MAKE_VERSION( \ - (((__SUNPRO_C >> 16) & 0xf) * 10) + ((__SUNPRO_C >> 12) & 0xf), \ - (((__SUNPRO_C >> 8) & 0xf) * 10) + ((__SUNPRO_C >> 4) & 0xf), \ - (__SUNPRO_C & 0xf) * 10) -#elif defined(__SUNPRO_C) -#define BROTLI_SUNPRO_VERSION \ - BROTLI_MAKE_VERSION((__SUNPRO_C >> 8) & 0xf, \ - (__SUNPRO_C >> 4) & 0xf, \ - (__SUNPRO_C) & 0xf) -#elif defined(__SUNPRO_CC) && (__SUNPRO_CC > 0x1000) -#define BROTLI_SUNPRO_VERSION \ - BROTLI_MAKE_VERSION( \ - (((__SUNPRO_CC >> 16) & 0xf) * 10) + ((__SUNPRO_CC >> 12) & 0xf), \ - (((__SUNPRO_CC >> 8) & 0xf) * 10) + ((__SUNPRO_CC >> 4) & 0xf), \ - (__SUNPRO_CC & 0xf) * 10) -#elif defined(__SUNPRO_CC) -#define BROTLI_SUNPRO_VERSION \ - BROTLI_MAKE_VERSION((__SUNPRO_CC >> 8) & 0xf, \ - (__SUNPRO_CC >> 4) & 0xf, \ - (__SUNPRO_CC) & 0xf) -#endif - -#if defined(BROTLI_SUNPRO_VERSION) -#define BROTLI_SUNPRO_VERSION_CHECK(major, minor, patch) \ - (BROTLI_SUNPRO_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_SUNPRO_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(__CC_ARM) && defined(__ARMCOMPILER_VERSION) -#define BROTLI_ARM_VERSION \ - BROTLI_MAKE_VERSION((__ARMCOMPILER_VERSION / 1000000), \ - (__ARMCOMPILER_VERSION % 1000000) / 10000, \ - (__ARMCOMPILER_VERSION % 10000) / 100) -#elif defined(__CC_ARM) && defined(__ARMCC_VERSION) -#define BROTLI_ARM_VERSION \ - BROTLI_MAKE_VERSION((__ARMCC_VERSION / 1000000), \ - (__ARMCC_VERSION % 1000000) / 10000, \ - (__ARMCC_VERSION % 10000) / 100) -#endif - -#if defined(BROTLI_ARM_VERSION) -#define BROTLI_ARM_VERSION_CHECK(major, minor, patch) \ - (BROTLI_ARM_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_ARM_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(__ibmxl__) -#define BROTLI_IBM_VERSION \ - BROTLI_MAKE_VERSION(__ibmxl_version__, \ - __ibmxl_release__, \ - __ibmxl_modification__) -#elif defined(__xlC__) && defined(__xlC_ver__) -#define BROTLI_IBM_VERSION \ - BROTLI_MAKE_VERSION(__xlC__ >> 8, __xlC__ & 0xff, (__xlC_ver__ >> 8) & 0xff) -#elif defined(__xlC__) -#define BROTLI_IBM_VERSION BROTLI_MAKE_VERSION(__xlC__ >> 8, __xlC__ & 0xff, 0) -#endif - -#if defined(BROTLI_IBM_VERSION) -#define BROTLI_IBM_VERSION_CHECK(major, minor, patch) \ - (BROTLI_IBM_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_IBM_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(__TI_COMPILER_VERSION__) -#define BROTLI_TI_VERSION \ - BROTLI_MAKE_VERSION((__TI_COMPILER_VERSION__ / 1000000), \ - (__TI_COMPILER_VERSION__ % 1000000) / 1000, \ - (__TI_COMPILER_VERSION__ % 1000)) -#endif - -#if defined(BROTLI_TI_VERSION) -#define BROTLI_TI_VERSION_CHECK(major, minor, patch) \ - (BROTLI_TI_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_TI_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(__IAR_SYSTEMS_ICC__) -#if __VER__ > 1000 -#define BROTLI_IAR_VERSION \ - BROTLI_MAKE_VERSION((__VER__ / 1000000), \ - (__VER__ / 1000) % 1000, \ - (__VER__ % 1000)) -#else -#define BROTLI_IAR_VERSION BROTLI_MAKE_VERSION(VER / 100, __VER__ % 100, 0) -#endif -#endif - -#if defined(BROTLI_IAR_VERSION) -#define BROTLI_IAR_VERSION_CHECK(major, minor, patch) \ - (BROTLI_IAR_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_IAR_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(__TINYC__) -#define BROTLI_TINYC_VERSION \ - BROTLI_MAKE_VERSION(__TINYC__ / 1000, (__TINYC__ / 100) % 10, __TINYC__ % 100) -#endif - -#if defined(BROTLI_TINYC_VERSION) -#define BROTLI_TINYC_VERSION_CHECK(major, minor, patch) \ - (BROTLI_TINYC_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) -#else -#define BROTLI_TINYC_VERSION_CHECK(major, minor, patch) (0) -#endif - -#if defined(__has_attribute) -#define BROTLI_GNUC_HAS_ATTRIBUTE(attribute, major, minor, patch) \ - __has_attribute(attribute) -#else -#define BROTLI_GNUC_HAS_ATTRIBUTE(attribute, major, minor, patch) \ - BROTLI_GNUC_VERSION_CHECK(major, minor, patch) -#endif - -#if defined(__has_builtin) -#define BROTLI_GNUC_HAS_BUILTIN(builtin, major, minor, patch) \ - __has_builtin(builtin) -#else -#define BROTLI_GNUC_HAS_BUILTIN(builtin, major, minor, patch) \ - BROTLI_GNUC_VERSION_CHECK(major, minor, patch) -#endif - /* Define "BROTLI_PREDICT_TRUE" and "BROTLI_PREDICT_FALSE" macros for capable compilers. @@ -375,7 +171,7 @@ OR: #endif #endif -/* <<< <<< <<< end of headley macros. */ +/* <<< <<< <<< end of hedley macros. */ #if BROTLI_GNUC_HAS_ATTRIBUTE(unused, 2, 7, 0) || \ BROTLI_INTEL_VERSION_CHECK(16, 0, 0) diff --git a/c/enc/backward_references.c b/c/enc/backward_references.c index 3dd897b..cd023d9 100644 --- a/c/enc/backward_references.c +++ b/c/enc/backward_references.c @@ -97,6 +97,21 @@ static BROTLI_INLINE size_t ComputeDistanceCode(size_t distance, #include "./backward_references_inc.h" #undef HASHER +#define HASHER() H35 +/* NOLINTNEXTLINE(build/include) */ +#include "./backward_references_inc.h" +#undef HASHER + +#define HASHER() H55 +/* NOLINTNEXTLINE(build/include) */ +#include "./backward_references_inc.h" +#undef HASHER + +#define HASHER() H65 +/* NOLINTNEXTLINE(build/include) */ +#include "./backward_references_inc.h" +#undef HASHER + #undef PREFIX #undef EXPORT_FN diff --git a/c/enc/hash.h b/c/enc/hash.h index fc7356b..2602490 100644 --- a/c/enc/hash.h +++ b/c/enc/hash.h @@ -153,14 +153,14 @@ static BROTLI_INLINE BROTLI_BOOL TestStaticDictionaryItem( size_t max_length, size_t max_backward, size_t max_distance, HasherSearchResult* out) { size_t len; - size_t dist; + size_t word_idx; size_t offset; size_t matchlen; size_t backward; score_t score; len = item & 0x1F; - dist = item >> 5; - offset = dictionary->words->offsets_by_length[len] + len * dist; + word_idx = item >> 5; + offset = dictionary->words->offsets_by_length[len] + len * word_idx; if (len > max_length) { return BROTLI_FALSE; } @@ -174,7 +174,7 @@ static BROTLI_INLINE BROTLI_BOOL TestStaticDictionaryItem( size_t cut = len - matchlen; size_t transform_id = (cut << 2) + (size_t)((dictionary->cutoffTransforms >> (cut * 6)) & 0x3F); - backward = max_backward + dist + 1 + + backward = max_backward + 1 + word_idx + (transform_id << dictionary->words->size_bits_by_length[len]); } if (backward > max_distance) { @@ -343,11 +343,57 @@ static BROTLI_INLINE size_t BackwardMatchLengthCode(const BackwardMatch* self) { #undef BUCKET_BITS #undef HASHER +/* fast large window hashers */ + +#define HASHER() HROLLING_FAST +#define CHUNKLEN 32 +#define JUMP 4 +#define NUMBUCKETS 16777216 +#define MASK ((NUMBUCKETS * 64) - 1) +#include "./hash_rolling_inc.h" /* NOLINT(build/include) */ +#undef JUMP +#undef HASHER + + +#define HASHER() HROLLING +#define JUMP 1 +#include "./hash_rolling_inc.h" /* NOLINT(build/include) */ +#undef MASK +#undef NUMBUCKETS +#undef JUMP +#undef CHUNKLEN +#undef HASHER + +#define HASHER() H35 +#define HASHER_A H3 +#define HASHER_B HROLLING_FAST +#include "./hash_composite_inc.h" /* NOLINT(build/include) */ +#undef HASHER_A +#undef HASHER_B +#undef HASHER + +#define HASHER() H55 +#define HASHER_A H54 +#define HASHER_B HROLLING_FAST +#include "./hash_composite_inc.h" /* NOLINT(build/include) */ +#undef HASHER_A +#undef HASHER_B +#undef HASHER + +#define HASHER() H65 +#define HASHER_A H6 +#define HASHER_B HROLLING +#include "./hash_composite_inc.h" /* NOLINT(build/include) */ +#undef HASHER_A +#undef HASHER_B +#undef HASHER + #undef FN #undef CAT #undef EXPAND_CAT -#define FOR_GENERIC_HASHERS(H) H(2) H(3) H(4) H(5) H(6) H(40) H(41) H(42) H(54) +#define FOR_GENERIC_HASHERS(H) H(2) H(3) H(4) H(5) H(6) H(40) H(41) H(42) H(54)\ + H(35) H(55) H(65) #define FOR_ALL_HASHERS(H) FOR_GENERIC_HASHERS(H) H(10) static BROTLI_INLINE void DestroyHasher( diff --git a/c/enc/hash_composite_inc.h b/c/enc/hash_composite_inc.h new file mode 100755 index 0000000..f829a97 --- /dev/null +++ b/c/enc/hash_composite_inc.h @@ -0,0 +1,133 @@ +/* NOLINT(build/header_guard) */ +/* Copyright 2018 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* template parameters: FN, HASHER_A, HASHER_B */ + +/* Composite hasher: This hasher allows to combine two other hashers, HASHER_A + and HASHER_B. */ + +#define HashComposite HASHER() + +#define FN_A(X) EXPAND_CAT(X, HASHER_A) +#define FN_B(X) EXPAND_CAT(X, HASHER_B) + +static BROTLI_INLINE size_t FN(HashTypeLength)(void) { + size_t a = FN_A(HashTypeLength)(); + size_t b = FN_B(HashTypeLength)(); + return a > b ? a : b; +} + +static BROTLI_INLINE size_t FN(StoreLookahead)(void) { + size_t a = FN_A(StoreLookahead)(); + size_t b = FN_B(StoreLookahead)(); + return a > b ? a : b; +} + +typedef struct HashComposite { + HasherHandle ha; + HasherHandle hb; + const BrotliEncoderParams* params; +} HashComposite; + +static BROTLI_INLINE HashComposite* FN(Self)(HasherHandle handle) { + return (HashComposite*)&(GetHasherCommon(handle)[1]); +} + +static void FN(Initialize)( + HasherHandle handle, const BrotliEncoderParams* params) { + HashComposite* self = FN(Self)(handle); + self->ha = 0; + self->hb = 0; + self->params = params; + /* TODO: Initialize of the hashers is defered to Prepare (and params + remembered here) because we don't get the one_shot and input_size params + here that are needed to know the memory size of them. Instead provide + those params to all hashers FN(Initialize) */ +} + +static void FN(Prepare)(HasherHandle handle, BROTLI_BOOL one_shot, + size_t input_size, const uint8_t* data) { + HashComposite* self = FN(Self)(handle); + if (!self->ha) { + HasherCommon* common_a; + HasherCommon* common_b; + + self->ha = handle + sizeof(HasherCommon) + sizeof(HashComposite); + common_a = (HasherCommon*)self->ha; + common_a->params = self->params->hasher; + common_a->is_prepared_ = BROTLI_FALSE; + common_a->dict_num_lookups = 0; + common_a->dict_num_matches = 0; + FN_A(Initialize)(self->ha, self->params); + + self->hb = self->ha + sizeof(HasherCommon) + FN_A(HashMemAllocInBytes)( + self->params, one_shot, input_size); + common_b = (HasherCommon*)self->hb; + common_b->params = self->params->hasher; + common_b->is_prepared_ = BROTLI_FALSE; + common_b->dict_num_lookups = 0; + common_b->dict_num_matches = 0; + FN_B(Initialize)(self->hb, self->params); + } + FN_A(Prepare)(self->ha, one_shot, input_size, data); + FN_B(Prepare)(self->hb, one_shot, input_size, data); +} + +static BROTLI_INLINE size_t FN(HashMemAllocInBytes)( + const BrotliEncoderParams* params, BROTLI_BOOL one_shot, + size_t input_size) { + return sizeof(HashComposite) + 2 * sizeof(HasherCommon) + + FN_A(HashMemAllocInBytes)(params, one_shot, input_size) + + FN_B(HashMemAllocInBytes)(params, one_shot, input_size); +} + +static BROTLI_INLINE void FN(Store)(HasherHandle BROTLI_RESTRICT handle, + const uint8_t* BROTLI_RESTRICT data, const size_t mask, const size_t ix) { + HashComposite* self = FN(Self)(handle); + FN_A(Store)(self->ha, data, mask, ix); + FN_B(Store)(self->hb, data, mask, ix); +} + +static BROTLI_INLINE void FN(StoreRange)(HasherHandle handle, + const uint8_t* data, const size_t mask, const size_t ix_start, + const size_t ix_end) { + HashComposite* self = FN(Self)(handle); + FN_A(StoreRange)(self->ha, data, mask, ix_start, ix_end); + FN_B(StoreRange)(self->hb, data, mask, ix_start, ix_end); +} + +static BROTLI_INLINE void FN(StitchToPreviousBlock)(HasherHandle handle, + size_t num_bytes, size_t position, const uint8_t* ringbuffer, + size_t ring_buffer_mask) { + HashComposite* self = FN(Self)(handle); + FN_A(StitchToPreviousBlock)(self->ha, num_bytes, position, ringbuffer, + ring_buffer_mask); + FN_B(StitchToPreviousBlock)(self->hb, num_bytes, position, ringbuffer, + ring_buffer_mask); +} + +static BROTLI_INLINE void FN(PrepareDistanceCache)( + HasherHandle handle, int* BROTLI_RESTRICT distance_cache) { + HashComposite* self = FN(Self)(handle); + FN_A(PrepareDistanceCache)(self->ha, distance_cache); + FN_B(PrepareDistanceCache)(self->hb, distance_cache); +} + +static BROTLI_INLINE void FN(FindLongestMatch)(HasherHandle handle, + const BrotliEncoderDictionary* dictionary, + const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask, + const int* BROTLI_RESTRICT distance_cache, const size_t cur_ix, + const size_t max_length, const size_t max_backward, const size_t gap, + const size_t max_distance, HasherSearchResult* BROTLI_RESTRICT out) { + HashComposite* self = FN(Self)(handle); + FN_A(FindLongestMatch)(self->ha, dictionary, data, ring_buffer_mask, + distance_cache, cur_ix, max_length, max_backward, gap, max_distance, out); + FN_B(FindLongestMatch)(self->hb, dictionary, data, ring_buffer_mask, + distance_cache, cur_ix, max_length, max_backward, gap, max_distance, out); +} + +#undef HashComposite diff --git a/c/enc/hash_rolling_inc.h b/c/enc/hash_rolling_inc.h new file mode 100755 index 0000000..4d5d14a --- /dev/null +++ b/c/enc/hash_rolling_inc.h @@ -0,0 +1,215 @@ +/* NOLINT(build/header_guard) */ +/* Copyright 2018 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* template parameters: FN, JUMP, NUMBUCKETS, MASK, CHUNKLEN */ +/* NUMBUCKETS / (MASK + 1) = probability of storing and using hash code. */ +/* JUMP = skip bytes for speedup */ + +/* Rolling hash for long distance long string matches. Stores one position + per bucket, bucket key is computed over a long region. */ + +#define HashRolling HASHER() + +static const uint32_t FN(kRollingHashMul32) = 69069; +static const uint32_t FN(kInvalidPos) = 0xffffffff; + +/* This hasher uses a longer forward length, but returning a higher value here + will hurt compression by the main hasher when combined with a composite + hasher. The hasher tests for forward itself instead. */ +static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 4; } +static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return 4; } + +/* Computes a code from a single byte. A lookup table of 256 values could be + used, but simply adding 1 works about as good. */ +static uint32_t FN(HashByte)(uint8_t byte) { + return (uint32_t)byte + 1u; +} + +static uint32_t FN(HashRollingFunctionInitial)(uint32_t state, uint8_t add, + uint32_t factor) { + return (uint32_t)(factor * state + FN(HashByte)(add)); +} + +static uint32_t FN(HashRollingFunction)(uint32_t state, uint8_t add, + uint8_t rem, uint32_t factor, + uint32_t factor_remove) { + return (uint32_t)(factor * state + + FN(HashByte)(add) - factor_remove * FN(HashByte)(rem)); +} + +typedef struct HashRolling { + uint32_t state; + uint32_t* table; + size_t next_ix; + + uint32_t chunk_len; + uint32_t factor; + uint32_t factor_remove; +} HashRolling; + +static BROTLI_INLINE HashRolling* FN(Self)(HasherHandle handle) { + return (HashRolling*)&(GetHasherCommon(handle)[1]); +} + +static void FN(Initialize)( + HasherHandle handle, const BrotliEncoderParams* params) { + HashRolling* self = FN(Self)(handle); + size_t i; + self->state = 0; + self->next_ix = 0; + + self->factor = FN(kRollingHashMul32); + + /* Compute the factor of the oldest byte to remove: factor**steps modulo + 0xffffffff (the multiplications rely on 32-bit overflow) */ + self->factor_remove = 1; + for (i = 0; i < CHUNKLEN; i += JUMP) { + self->factor_remove *= self->factor; + } + + self->table = (uint32_t*)((HasherHandle)self + sizeof(HashRolling)); + for (i = 0; i < NUMBUCKETS; i++) { + self->table[i] = FN(kInvalidPos); + } + + BROTLI_UNUSED(params); +} + +static void FN(Prepare)(HasherHandle handle, BROTLI_BOOL one_shot, + size_t input_size, const uint8_t* data) { + HashRolling* self = FN(Self)(handle); + size_t i; + /* Too small size, cannot use this hasher. */ + if (input_size < CHUNKLEN) return; + self->state = 0; + for (i = 0; i < CHUNKLEN; i += JUMP) { + self->state = FN(HashRollingFunctionInitial)( + self->state, data[i], self->factor); + } + BROTLI_UNUSED(one_shot); +} + +static BROTLI_INLINE size_t FN(HashMemAllocInBytes)( + const BrotliEncoderParams* params, BROTLI_BOOL one_shot, + size_t input_size) { + return sizeof(HashRolling) + NUMBUCKETS * sizeof(uint32_t); + BROTLI_UNUSED(params); + BROTLI_UNUSED(one_shot); + BROTLI_UNUSED(input_size); +} + +static BROTLI_INLINE void FN(Store)(HasherHandle BROTLI_RESTRICT handle, + const uint8_t* BROTLI_RESTRICT data, const size_t mask, const size_t ix) { + BROTLI_UNUSED(handle); + BROTLI_UNUSED(data); + BROTLI_UNUSED(mask); + BROTLI_UNUSED(ix); +} + +static BROTLI_INLINE void FN(StoreRange)(HasherHandle handle, + const uint8_t* data, const size_t mask, const size_t ix_start, + const size_t ix_end) { + BROTLI_UNUSED(handle); + BROTLI_UNUSED(data); + BROTLI_UNUSED(mask); + BROTLI_UNUSED(ix_start); + BROTLI_UNUSED(ix_end); +} + +static BROTLI_INLINE void FN(StitchToPreviousBlock)(HasherHandle handle, + size_t num_bytes, size_t position, const uint8_t* ringbuffer, + size_t ring_buffer_mask) { + /* In this case we must re-initialize the hasher from scratch from the + current position. */ + HashRolling* self = FN(Self)(handle); + size_t position_masked; + size_t available = num_bytes; + if ((position & (JUMP - 1)) != 0) { + size_t diff = JUMP - (position & (JUMP - 1)); + available = (diff > available) ? 0 : (available - diff); + position += diff; + } + position_masked = position & ring_buffer_mask; + /* wrapping around ringbuffer not handled. */ + if (available > ring_buffer_mask - position_masked) { + available = ring_buffer_mask - position_masked; + } + + FN(Prepare)(handle, BROTLI_FALSE, available, + ringbuffer + (position & ring_buffer_mask)); + self->next_ix = position; + BROTLI_UNUSED(num_bytes); +} + +static BROTLI_INLINE void FN(PrepareDistanceCache)( + HasherHandle handle, int* BROTLI_RESTRICT distance_cache) { + BROTLI_UNUSED(handle); + BROTLI_UNUSED(distance_cache); +} + +static BROTLI_INLINE void FN(FindLongestMatch)(HasherHandle handle, + const BrotliEncoderDictionary* dictionary, + const uint8_t* BROTLI_RESTRICT data, const size_t ring_buffer_mask, + const int* BROTLI_RESTRICT distance_cache, const size_t cur_ix, + const size_t max_length, const size_t max_backward, const size_t gap, + const size_t max_distance, HasherSearchResult* BROTLI_RESTRICT out) { + HashRolling* self = FN(Self)(handle); + const size_t cur_ix_masked = cur_ix & ring_buffer_mask; + size_t pos = self->next_ix; + + if ((cur_ix & (JUMP - 1)) != 0) return; + + /* Not enough lookahead */ + if (max_length < CHUNKLEN) return; + + for (pos = self->next_ix; pos <= cur_ix; pos += JUMP) { + uint32_t code = self->state & MASK; + + uint8_t rem = data[pos & ring_buffer_mask]; + uint8_t add = data[(pos + CHUNKLEN) & ring_buffer_mask]; + size_t found_ix = FN(kInvalidPos); + + self->state = FN(HashRollingFunction)( + self->state, add, rem, self->factor, self->factor_remove); + + if (code < NUMBUCKETS) { + found_ix = self->table[code]; + self->table[code] = (uint32_t)pos; + if (pos == cur_ix && found_ix != FN(kInvalidPos)) { + /* The cast to 32-bit makes backward distances up to 4GB work even + if cur_ix is above 4GB, despite using 32-bit values in the table. */ + size_t backward = (uint32_t)(cur_ix - found_ix); + if (backward <= max_backward) { + const size_t found_ix_masked = found_ix & ring_buffer_mask; + const size_t len = FindMatchLengthWithLimit(&data[found_ix_masked], + &data[cur_ix_masked], + max_length); + if (len >= 4 && len > out->len) { + score_t score = BackwardReferenceScore(len, backward); + if (score > out->score) { + out->len = len; + out->distance = backward; + out->score = score; + out->len_code_delta = 0; + } + } + } + } + } + } + + self->next_ix = cur_ix + JUMP; + + /* NOTE: this hasher does not search in the dictionary. It is used as + backup-hasher, the main hasher already searches in it. */ + BROTLI_UNUSED(dictionary); + BROTLI_UNUSED(distance_cache); + BROTLI_UNUSED(gap); + BROTLI_UNUSED(max_distance); +} + +#undef HashRolling diff --git a/c/enc/quality.h b/c/enc/quality.h index aa7ba0d..5f4d034 100644 --- a/c/enc/quality.h +++ b/c/enc/quality.h @@ -142,6 +142,24 @@ static BROTLI_INLINE void ChooseHasher(const BrotliEncoderParams* params, hparams->num_last_distances_to_check = params->quality < 7 ? 4 : params->quality < 9 ? 10 : 16; } + + if (params->lgwin > 24) { + /* Different hashers for large window brotli: not for qualities <= 2, + these are too fast for large window. Not for qualities >= 10: their + hasher already works well with large window. So the changes are: + H3 --> H35: for quality 3. + H54 --> H55: for quality 4 with size hint > 1MB + H6 --> H65: for qualities 5, 6, 7, 8, 9. */ + if (hparams->type == 3) { + hparams->type = 35; + } + if (hparams->type == 54) { + hparams->type = 55; + } + if (hparams->type == 6) { + hparams->type = 65; + } + } } #endif /* BROTLI_ENC_QUALITY_H_ */ diff --git a/c/include/brotli/port.h b/c/include/brotli/port.h index e5ac4ba..20dc231 100644 --- a/c/include/brotli/port.h +++ b/c/include/brotli/port.h @@ -9,7 +9,230 @@ #ifndef BROTLI_COMMON_PORT_H_ #define BROTLI_COMMON_PORT_H_ -/* NB: borrowed from github.com.nemequ/hedley. */ +/* The following macros were borrowed from https://github.com/nemequ/hedley + * with permission of original author - Evan Nemerson */ + +/* >>> >>> >>> hedley macros */ + +#define BROTLI_MAKE_VERSION(major, minor, revision) \ + (((major) * 1000000) + ((minor) * 1000) + (revision)) + +#if defined(__GNUC__) && defined(__GNUC_PATCHLEVEL__) +#define BROTLI_GNUC_VERSION \ + BROTLI_MAKE_VERSION(__GNUC__, __GNUC_MINOR__, __GNUC_PATCHLEVEL__) +#elif defined(__GNUC__) +#define BROTLI_GNUC_VERSION BROTLI_MAKE_VERSION(__GNUC__, __GNUC_MINOR__, 0) +#endif + +#if defined(BROTLI_GNUC_VERSION) +#define BROTLI_GNUC_VERSION_CHECK(major, minor, patch) \ + (BROTLI_GNUC_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_GNUC_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(_MSC_FULL_VER) && (_MSC_FULL_VER >= 140000000) +#define BROTLI_MSVC_VERSION \ + BROTLI_MAKE_VERSION((_MSC_FULL_VER / 10000000), \ + (_MSC_FULL_VER % 10000000) / 100000, \ + (_MSC_FULL_VER % 100000) / 100) +#elif defined(_MSC_FULL_VER) +#define BROTLI_MSVC_VERSION \ + BROTLI_MAKE_VERSION((_MSC_FULL_VER / 1000000), \ + (_MSC_FULL_VER % 1000000) / 10000, \ + (_MSC_FULL_VER % 10000) / 10) +#elif defined(_MSC_VER) +#define BROTLI_MSVC_VERSION \ + BROTLI_MAKE_VERSION(_MSC_VER / 100, _MSC_VER % 100, 0) +#endif + +#if !defined(_MSC_VER) +#define BROTLI_MSVC_VERSION_CHECK(major, minor, patch) (0) +#elif defined(_MSC_VER) && (_MSC_VER >= 1400) +#define BROTLI_MSVC_VERSION_CHECK(major, minor, patch) \ + (_MSC_FULL_VER >= ((major * 10000000) + (minor * 100000) + (patch))) +#elif defined(_MSC_VER) && (_MSC_VER >= 1200) +#define BROTLI_MSVC_VERSION_CHECK(major, minor, patch) \ + (_MSC_FULL_VER >= ((major * 1000000) + (minor * 10000) + (patch))) +#else +#define BROTLI_MSVC_VERSION_CHECK(major, minor, patch) \ + (_MSC_VER >= ((major * 100) + (minor))) +#endif + +#if defined(__INTEL_COMPILER) && defined(__INTEL_COMPILER_UPDATE) +#define BROTLI_INTEL_VERSION \ + BROTLI_MAKE_VERSION(__INTEL_COMPILER / 100, \ + __INTEL_COMPILER % 100, \ + __INTEL_COMPILER_UPDATE) +#elif defined(__INTEL_COMPILER) +#define BROTLI_INTEL_VERSION \ + BROTLI_MAKE_VERSION(__INTEL_COMPILER / 100, __INTEL_COMPILER % 100, 0) +#endif + +#if defined(BROTLI_INTEL_VERSION) +#define BROTLI_INTEL_VERSION_CHECK(major, minor, patch) \ + (BROTLI_INTEL_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_INTEL_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(__PGI) && \ + defined(__PGIC__) && defined(__PGIC_MINOR__) && defined(__PGIC_PATCHLEVEL__) +#define BROTLI_PGI_VERSION \ + BROTLI_MAKE_VERSION(__PGIC__, __PGIC_MINOR__, __PGIC_PATCHLEVEL__) +#endif + +#if defined(BROTLI_PGI_VERSION) +#define BROTLI_PGI_VERSION_CHECK(major, minor, patch) \ + (BROTLI_PGI_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_PGI_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(__SUNPRO_C) && (__SUNPRO_C > 0x1000) +#define BROTLI_SUNPRO_VERSION \ + BROTLI_MAKE_VERSION( \ + (((__SUNPRO_C >> 16) & 0xf) * 10) + ((__SUNPRO_C >> 12) & 0xf), \ + (((__SUNPRO_C >> 8) & 0xf) * 10) + ((__SUNPRO_C >> 4) & 0xf), \ + (__SUNPRO_C & 0xf) * 10) +#elif defined(__SUNPRO_C) +#define BROTLI_SUNPRO_VERSION \ + BROTLI_MAKE_VERSION((__SUNPRO_C >> 8) & 0xf, \ + (__SUNPRO_C >> 4) & 0xf, \ + (__SUNPRO_C) & 0xf) +#elif defined(__SUNPRO_CC) && (__SUNPRO_CC > 0x1000) +#define BROTLI_SUNPRO_VERSION \ + BROTLI_MAKE_VERSION( \ + (((__SUNPRO_CC >> 16) & 0xf) * 10) + ((__SUNPRO_CC >> 12) & 0xf), \ + (((__SUNPRO_CC >> 8) & 0xf) * 10) + ((__SUNPRO_CC >> 4) & 0xf), \ + (__SUNPRO_CC & 0xf) * 10) +#elif defined(__SUNPRO_CC) +#define BROTLI_SUNPRO_VERSION \ + BROTLI_MAKE_VERSION((__SUNPRO_CC >> 8) & 0xf, \ + (__SUNPRO_CC >> 4) & 0xf, \ + (__SUNPRO_CC) & 0xf) +#endif + +#if defined(BROTLI_SUNPRO_VERSION) +#define BROTLI_SUNPRO_VERSION_CHECK(major, minor, patch) \ + (BROTLI_SUNPRO_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_SUNPRO_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(__CC_ARM) && defined(__ARMCOMPILER_VERSION) +#define BROTLI_ARM_VERSION \ + BROTLI_MAKE_VERSION((__ARMCOMPILER_VERSION / 1000000), \ + (__ARMCOMPILER_VERSION % 1000000) / 10000, \ + (__ARMCOMPILER_VERSION % 10000) / 100) +#elif defined(__CC_ARM) && defined(__ARMCC_VERSION) +#define BROTLI_ARM_VERSION \ + BROTLI_MAKE_VERSION((__ARMCC_VERSION / 1000000), \ + (__ARMCC_VERSION % 1000000) / 10000, \ + (__ARMCC_VERSION % 10000) / 100) +#endif + +#if defined(BROTLI_ARM_VERSION) +#define BROTLI_ARM_VERSION_CHECK(major, minor, patch) \ + (BROTLI_ARM_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_ARM_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(__ibmxl__) +#define BROTLI_IBM_VERSION \ + BROTLI_MAKE_VERSION(__ibmxl_version__, \ + __ibmxl_release__, \ + __ibmxl_modification__) +#elif defined(__xlC__) && defined(__xlC_ver__) +#define BROTLI_IBM_VERSION \ + BROTLI_MAKE_VERSION(__xlC__ >> 8, __xlC__ & 0xff, (__xlC_ver__ >> 8) & 0xff) +#elif defined(__xlC__) +#define BROTLI_IBM_VERSION BROTLI_MAKE_VERSION(__xlC__ >> 8, __xlC__ & 0xff, 0) +#endif + +#if defined(BROTLI_IBM_VERSION) +#define BROTLI_IBM_VERSION_CHECK(major, minor, patch) \ + (BROTLI_IBM_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_IBM_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(__TI_COMPILER_VERSION__) +#define BROTLI_TI_VERSION \ + BROTLI_MAKE_VERSION((__TI_COMPILER_VERSION__ / 1000000), \ + (__TI_COMPILER_VERSION__ % 1000000) / 1000, \ + (__TI_COMPILER_VERSION__ % 1000)) +#endif + +#if defined(BROTLI_TI_VERSION) +#define BROTLI_TI_VERSION_CHECK(major, minor, patch) \ + (BROTLI_TI_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_TI_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(__IAR_SYSTEMS_ICC__) +#if __VER__ > 1000 +#define BROTLI_IAR_VERSION \ + BROTLI_MAKE_VERSION((__VER__ / 1000000), \ + (__VER__ / 1000) % 1000, \ + (__VER__ % 1000)) +#else +#define BROTLI_IAR_VERSION BROTLI_MAKE_VERSION(VER / 100, __VER__ % 100, 0) +#endif +#endif + +#if defined(BROTLI_IAR_VERSION) +#define BROTLI_IAR_VERSION_CHECK(major, minor, patch) \ + (BROTLI_IAR_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_IAR_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(__TINYC__) +#define BROTLI_TINYC_VERSION \ + BROTLI_MAKE_VERSION(__TINYC__ / 1000, (__TINYC__ / 100) % 10, __TINYC__ % 100) +#endif + +#if defined(BROTLI_TINYC_VERSION) +#define BROTLI_TINYC_VERSION_CHECK(major, minor, patch) \ + (BROTLI_TINYC_VERSION >= BROTLI_MAKE_VERSION(major, minor, patch)) +#else +#define BROTLI_TINYC_VERSION_CHECK(major, minor, patch) (0) +#endif + +#if defined(__has_attribute) +#define BROTLI_GNUC_HAS_ATTRIBUTE(attribute, major, minor, patch) \ + __has_attribute(attribute) +#else +#define BROTLI_GNUC_HAS_ATTRIBUTE(attribute, major, minor, patch) \ + BROTLI_GNUC_VERSION_CHECK(major, minor, patch) +#endif + +#if defined(__has_builtin) +#define BROTLI_GNUC_HAS_BUILTIN(builtin, major, minor, patch) \ + __has_builtin(builtin) +#else +#define BROTLI_GNUC_HAS_BUILTIN(builtin, major, minor, patch) \ + BROTLI_GNUC_VERSION_CHECK(major, minor, patch) +#endif + +#if defined(_WIN32) || defined(__CYGWIN__) +#define BROTLI_PUBLIC +#elif BROTLI_GNUC_VERSION_CHECK(3, 3, 0) || \ + BROTLI_TI_VERSION_CHECK(8, 0, 0) || \ + BROTLI_INTEL_VERSION_CHECK(16, 0, 0) || \ + BROTLI_ARM_VERSION_CHECK(4, 1, 0) || \ + BROTLI_IBM_VERSION_CHECK(13, 1, 0) || \ + BROTLI_SUNPRO_VERSION_CHECK(5, 11, 0) || \ + (BROTLI_TI_VERSION_CHECK(7, 3, 0) && \ + defined(__TI_GNU_ATTRIBUTE_SUPPORT__) && defined(__TI_EABI__)) +#define BROTLI_PUBLIC __attribute__ ((visibility ("default"))) +#else +#define BROTLI_PUBLIC +#endif + #if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) && \ !defined(__STDC_NO_VLA__) && !defined(__cplusplus) && \ !defined(__PGI) && !defined(__PGIC__) && !defined(__TINYC__) @@ -18,7 +241,10 @@ #define BROTLI_ARRAY_PARAM(name) #endif -#if defined(BROTLI_SHARED_COMPILATION) && defined(_WIN32) +/* <<< <<< <<< end of hedley macros. */ + +#if defined(BROTLI_SHARED_COMPILATION) +#if defined(_WIN32) #if defined(BROTLICOMMON_SHARED_COMPILATION) #define BROTLI_COMMON_API __declspec(dllexport) #else @@ -34,7 +260,12 @@ #else #define BROTLI_ENC_API __declspec(dllimport) #endif /* BROTLIENC_SHARED_COMPILATION */ -#else /* BROTLI_SHARED_COMPILATION && _WIN32 */ +#else /* _WIN32 */ +#define BROTLI_COMMON_API BROTLI_PUBLIC +#define BROTLI_DEC_API BROTLI_PUBLIC +#define BROTLI_ENC_API BROTLI_PUBLIC +#endif /* _WIN32 */ +#else /* BROTLI_SHARED_COMPILATION */ #define BROTLI_COMMON_API #define BROTLI_DEC_API #define BROTLI_ENC_API -- cgit v1.1