diff options
Diffstat (limited to 'contrib/optimizations/insert_string.h')
| -rw-r--r-- | contrib/optimizations/insert_string.h | 62 |
1 files changed, 40 insertions, 22 deletions
diff --git a/contrib/optimizations/insert_string.h b/contrib/optimizations/insert_string.h index 9f634ae..c6a296a 100644 --- a/contrib/optimizations/insert_string.h +++ b/contrib/optimizations/insert_string.h @@ -1,15 +1,20 @@ /* insert_string.h * - * Copyright 2019 The Chromium Authors. All rights reserved. + * Copyright 2019 The Chromium Authors * Use of this source code is governed by a BSD-style license that can be * found in the Chromium source repository LICENSE file. */ -#if defined(_MSC_VER) +#ifndef INSERT_STRING_H +#define INSERT_STRING_H + +#ifndef INLINE +#if defined(_MSC_VER) && !defined(__clang__) #define INLINE __inline #else #define INLINE inline #endif +#endif #include "cpu_features.h" @@ -23,7 +28,8 @@ #define TARGET_CPU_WITH_CRC #endif - #define _cpu_crc32_u32 _mm_crc32_u32 + /* CRC32C uint32_t */ + #define _cpu_crc32c_hash_u32 _mm_crc32_u32 #elif defined(CRC32_ARMV8_CRC32) #if defined(__clang__) @@ -40,7 +46,8 @@ #define TARGET_CPU_WITH_CRC __attribute__((target("armv8-a,crc"))) #endif // defined(__aarch64__) - #define _cpu_crc32_u32 __crc32cw + /* CRC32C uint32_t */ + #define _cpu_crc32c_hash_u32 __crc32cw #endif // clang-format on @@ -50,20 +57,15 @@ TARGET_CPU_WITH_CRC local INLINE Pos insert_string_simd(deflate_state* const s, const Pos str) { Pos ret; - unsigned *ip, val, h = 0; + unsigned val, h = 0; - ip = (unsigned*)&s->window[str]; - val = *ip; + zmemcpy(&val, &s->window[str], sizeof(val)); if (s->level >= 6) val &= 0xFFFFFF; - /* Unlike the case of data integrity checks for GZIP format where the - * polynomial used is defined (https://tools.ietf.org/html/rfc1952#page-11), - * here it is just a hash function for the hash table used while - * performing compression. - */ - h = _cpu_crc32_u32(h, val); + /* Compute hash from the CRC32C of |val|. */ + h = _cpu_crc32c_hash_u32(h, val); ret = s->head[h & s->hash_mask]; s->head[h & s->hash_mask] = str; @@ -73,8 +75,22 @@ local INLINE Pos insert_string_simd(deflate_state* const s, const Pos str) { #endif // TARGET_CPU_WITH_CRC +/** + * Some applications need to match zlib DEFLATE output exactly [3]. Use the + * canonical zlib Rabin-Karp rolling hash [1,2] in that case. + * + * [1] For a description of the Rabin and Karp algorithm, see "Algorithms" + * book by R. Sedgewick, Addison-Wesley, p252. + * [2] https://www.euccas.me/zlib/#zlib_rabin_karp and also "rolling hash" + * https://en.wikipedia.org/wiki/Rolling_hash + * [3] crbug.com/1316541 AOSP incremental client APK package OTA upgrades. + */ +#ifdef CHROMIUM_ZLIB_NO_CASTAGNOLI +#define USE_ZLIB_RABIN_KARP_ROLLING_HASH +#endif + /* =========================================================================== - * Update a hash value with the given input byte + * Update a hash value with the given input byte (Rabin-Karp rolling hash). * IN assertion: all calls to UPDATE_HASH are made with consecutive input * characters, so that a running hash key can be computed from the previous * key instead of complete recalculation each time. @@ -106,16 +122,16 @@ local INLINE Pos insert_string_c(deflate_state* const s, const Pos str) { } local INLINE Pos insert_string(deflate_state* const s, const Pos str) { -/* insert_string_simd string dictionary insertion: this SIMD symbol hashing +/* insert_string_simd string dictionary insertion: SIMD crc32c symbol hasher * significantly improves data compression speed. * - * Note: the generated compressed output is a valid DEFLATE stream but will - * differ from vanilla zlib output ... + * Note: the generated compressed output is a valid DEFLATE stream, but will + * differ from canonical zlib output. */ -#if defined(CHROMIUM_ZLIB_NO_CASTAGNOLI) -/* ... so this build-time option can used to disable the SIMD symbol hasher - * if matching vanilla zlib DEFLATE output is required. - */ (;) /* FALLTHOUGH */ +#if defined(USE_ZLIB_RABIN_KARP_ROLLING_HASH) +/* So this build-time option can be used to disable the crc32c hash, and use + * the Rabin-Karp hash instead. + */ /* FALLTHROUGH Rabin-Karp */ #elif defined(TARGET_CPU_WITH_CRC) && defined(CRC32_SIMD_SSE42_PCLMUL) if (x86_cpu_enable_simd) return insert_string_simd(s, str); @@ -123,5 +139,7 @@ local INLINE Pos insert_string(deflate_state* const s, const Pos str) { if (arm_cpu_enable_crc32) return insert_string_simd(s, str); #endif - return insert_string_c(s, str); + return insert_string_c(s, str); /* Rabin-Karp */ } + +#endif /* INSERT_STRING_H */ |