1 /* insert_string.h
2 *
3 * Copyright 2019 The Chromium Authors
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the Chromium source repository LICENSE file.
6 */
7
8 #ifndef INSERT_STRING_H
9 #define INSERT_STRING_H
10
11 #ifndef INLINE
12 #if defined(_MSC_VER) && !defined(__clang__)
13 #define INLINE __inline
14 #else
15 #define INLINE inline
16 #endif
17 #endif
18
19 #include "cpu_features.h"
20
21 // clang-format off
22 #if defined(CRC32_SIMD_SSE42_PCLMUL)
23 #include <smmintrin.h> /* Required to make MSVC bot build pass. */
24
25 #if defined(__clang__) || defined(__GNUC__)
26 #define TARGET_CPU_WITH_CRC __attribute__((target("sse4.2")))
27 #else
28 #define TARGET_CPU_WITH_CRC
29 #endif
30
31 /* CRC32C uint32_t */
32 #define _cpu_crc32c_hash_u32 _mm_crc32_u32
33
34 #elif defined(CRC32_ARMV8_CRC32)
35 #if defined(__clang__)
36 #define __crc32cw __builtin_arm_crc32cw
37 #elif defined(__GNUC__)
38 #define __crc32cw __builtin_aarch64_crc32cw
39 #endif
40
41 #if defined(__aarch64__) && defined(__clang__)
42 #define TARGET_CPU_WITH_CRC __attribute__((target("crc")))
43 #elif defined(__aarch64__) && defined(__GNUC__)
44 #define TARGET_CPU_WITH_CRC __attribute__((target("+crc")))
45 #elif defined(__clang__) // !defined(__aarch64__)
46 #define TARGET_CPU_WITH_CRC __attribute__((target("armv8-a,crc")))
47 #endif // defined(__aarch64__)
48
49 /* CRC32C uint32_t */
50 #define _cpu_crc32c_hash_u32 __crc32cw
51
52 #endif
53 // clang-format on
54
55 #if defined(TARGET_CPU_WITH_CRC)
56
57 TARGET_CPU_WITH_CRC
insert_string_simd(deflate_state * const s,const Pos str)58 local INLINE Pos insert_string_simd(deflate_state* const s, const Pos str) {
59 Pos ret;
60 unsigned val, h = 0;
61
62 zmemcpy(&val, &s->window[str], sizeof(val));
63
64 if (s->level >= 6)
65 val &= 0xFFFFFF;
66
67 /* Compute hash from the CRC32C of |val|. */
68 h = _cpu_crc32c_hash_u32(h, val);
69
70 ret = s->head[h & s->hash_mask];
71 s->head[h & s->hash_mask] = str;
72 s->prev[str & s->w_mask] = ret;
73 return ret;
74 }
75
76 #endif // TARGET_CPU_WITH_CRC
77
78 /**
79 * Some applications need to match zlib DEFLATE output exactly [3]. Use the
80 * canonical zlib Rabin-Karp rolling hash [1,2] in that case.
81 *
82 * [1] For a description of the Rabin and Karp algorithm, see "Algorithms"
83 * book by R. Sedgewick, Addison-Wesley, p252.
84 * [2] https://www.euccas.me/zlib/#zlib_rabin_karp and also "rolling hash"
85 * https://en.wikipedia.org/wiki/Rolling_hash
86 * [3] crbug.com/1316541 AOSP incremental client APK package OTA upgrades.
87 */
88 #ifdef CHROMIUM_ZLIB_NO_CASTAGNOLI
89 #define USE_ZLIB_RABIN_KARP_ROLLING_HASH
90 #endif
91
92 /* ===========================================================================
93 * Update a hash value with the given input byte (Rabin-Karp rolling hash).
94 * IN assertion: all calls to UPDATE_HASH are made with consecutive input
95 * characters, so that a running hash key can be computed from the previous
96 * key instead of complete recalculation each time.
97 */
98 #define UPDATE_HASH(s, h, c) (h = (((h) << s->hash_shift) ^ (c)) & s->hash_mask)
99
100 /* ===========================================================================
101 * Insert string str in the dictionary and set match_head to the previous head
102 * of the hash chain (the most recent string with same hash key). Return
103 * the previous length of the hash chain.
104 * If this file is compiled with -DFASTEST, the compression level is forced
105 * to 1, and no hash chains are maintained.
106 * IN assertion: all calls to INSERT_STRING are made with consecutive input
107 * characters and the first MIN_MATCH bytes of str are valid (except for
108 * the last MIN_MATCH-1 bytes of the input file).
109 */
insert_string_c(deflate_state * const s,const Pos str)110 local INLINE Pos insert_string_c(deflate_state* const s, const Pos str) {
111 Pos ret;
112
113 UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH - 1)]);
114 #ifdef FASTEST
115 ret = s->head[s->ins_h];
116 #else
117 ret = s->prev[str & s->w_mask] = s->head[s->ins_h];
118 #endif
119 s->head[s->ins_h] = str;
120
121 return ret;
122 }
123
insert_string(deflate_state * const s,const Pos str)124 local INLINE Pos insert_string(deflate_state* const s, const Pos str) {
125 /* insert_string_simd string dictionary insertion: SIMD crc32c symbol hasher
126 * significantly improves data compression speed.
127 *
128 * Note: the generated compressed output is a valid DEFLATE stream, but will
129 * differ from canonical zlib output.
130 */
131 #if defined(USE_ZLIB_RABIN_KARP_ROLLING_HASH)
132 /* So this build-time option can be used to disable the crc32c hash, and use
133 * the Rabin-Karp hash instead.
134 */ /* FALLTHROUGH Rabin-Karp */
135 #elif defined(TARGET_CPU_WITH_CRC) && defined(CRC32_SIMD_SSE42_PCLMUL)
136 if (x86_cpu_enable_simd)
137 return insert_string_simd(s, str);
138 #elif defined(TARGET_CPU_WITH_CRC) && defined(CRC32_ARMV8_CRC32)
139 if (arm_cpu_enable_crc32)
140 return insert_string_simd(s, str);
141 #endif
142 return insert_string_c(s, str); /* Rabin-Karp */
143 }
144
145 #endif /* INSERT_STRING_H */
146