1 /* insert_string.h
2 *
3 * Copyright 2019 The Chromium Authors. All rights reserved.
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 #if defined(_MSC_VER)
9 #define INLINE __inline
10 #else
11 #define INLINE inline
12 #endif
13
14 #include "cpu_features.h"
15
16 // clang-format off
17 #if defined(CRC32_SIMD_SSE42_PCLMUL)
18 #include <smmintrin.h> /* Required to make MSVC bot build pass. */
19
20 #if defined(__clang__) || defined(__GNUC__)
21 #define TARGET_CPU_WITH_CRC __attribute__((target("sse4.2")))
22 #else
23 #define TARGET_CPU_WITH_CRC
24 #endif
25
26 #define _cpu_crc32_u32 _mm_crc32_u32
27
28 #elif defined(CRC32_ARMV8_CRC32)
29 #if defined(__clang__)
30 #define __crc32cw __builtin_arm_crc32cw
31 #elif defined(__GNUC__)
32 #define __crc32cw __builtin_aarch64_crc32cw
33 #endif
34
35 #if defined(__aarch64__) && defined(__clang__)
36 #define TARGET_CPU_WITH_CRC __attribute__((target("crc")))
37 #elif defined(__aarch64__) && defined(__GNUC__)
38 #define TARGET_CPU_WITH_CRC __attribute__((target("+crc")))
39 #elif defined(__clang__) // !defined(__aarch64__)
40 #define TARGET_CPU_WITH_CRC __attribute__((target("armv8-a,crc")))
41 #endif // defined(__aarch64__)
42
43 #define _cpu_crc32_u32 __crc32cw
44
45 #endif
46 // clang-format on
47
48 #if defined(TARGET_CPU_WITH_CRC)
49
50 TARGET_CPU_WITH_CRC
insert_string_simd(deflate_state * const s,const Pos str)51 local INLINE Pos insert_string_simd(deflate_state* const s, const Pos str) {
52 Pos ret;
53 unsigned *ip, val, h = 0;
54
55 ip = (unsigned*)&s->window[str];
56 val = *ip;
57
58 if (s->level >= 6)
59 val &= 0xFFFFFF;
60
61 /* Unlike the case of data integrity checks for GZIP format where the
62 * polynomial used is defined (https://tools.ietf.org/html/rfc1952#page-11),
63 * here it is just a hash function for the hash table used while
64 * performing compression.
65 */
66 h = _cpu_crc32_u32(h, val);
67
68 ret = s->head[h & s->hash_mask];
69 s->head[h & s->hash_mask] = str;
70 s->prev[str & s->w_mask] = ret;
71 return ret;
72 }
73
74 #endif // TARGET_CPU_WITH_CRC
75
76 /* ===========================================================================
77 * Update a hash value with the given input byte
78 * IN assertion: all calls to UPDATE_HASH are made with consecutive input
79 * characters, so that a running hash key can be computed from the previous
80 * key instead of complete recalculation each time.
81 */
82 #define UPDATE_HASH(s, h, c) (h = (((h) << s->hash_shift) ^ (c)) & s->hash_mask)
83
84 /* ===========================================================================
85 * Insert string str in the dictionary and set match_head to the previous head
86 * of the hash chain (the most recent string with same hash key). Return
87 * the previous length of the hash chain.
88 * If this file is compiled with -DFASTEST, the compression level is forced
89 * to 1, and no hash chains are maintained.
90 * IN assertion: all calls to INSERT_STRING are made with consecutive input
91 * characters and the first MIN_MATCH bytes of str are valid (except for
92 * the last MIN_MATCH-1 bytes of the input file).
93 */
insert_string_c(deflate_state * const s,const Pos str)94 local INLINE Pos insert_string_c(deflate_state* const s, const Pos str) {
95 Pos ret;
96
97 UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH - 1)]);
98 #ifdef FASTEST
99 ret = s->head[s->ins_h];
100 #else
101 ret = s->prev[str & s->w_mask] = s->head[s->ins_h];
102 #endif
103 s->head[s->ins_h] = str;
104
105 return ret;
106 }
107
insert_string(deflate_state * const s,const Pos str)108 local INLINE Pos insert_string(deflate_state* const s, const Pos str) {
109 /* insert_string_simd string dictionary insertion: this SIMD symbol hashing
110 * significantly improves data compression speed.
111 *
112 * Note: the generated compressed output is a valid DEFLATE stream but will
113 * differ from vanilla zlib output ...
114 */
115 #if defined(CHROMIUM_ZLIB_NO_CASTAGNOLI)
116 /* ... so this build-time option can used to disable the SIMD symbol hasher
117 * if matching vanilla zlib DEFLATE output is required.
118 */ (;) /* FALLTHOUGH */
119 #elif defined(TARGET_CPU_WITH_CRC) && defined(CRC32_SIMD_SSE42_PCLMUL)
120 if (x86_cpu_enable_simd)
121 return insert_string_simd(s, str);
122 #elif defined(TARGET_CPU_WITH_CRC) && defined(CRC32_ARMV8_CRC32)
123 if (arm_cpu_enable_crc32)
124 return insert_string_simd(s, str);
125 #endif
126 return insert_string_c(s, str);
127 }
128