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 <stdint.h>
20
21 /**
22 * Some applications need to match zlib DEFLATE output exactly [3]. Use the
23 * canonical zlib Rabin-Karp rolling hash [1,2] in that case.
24 *
25 * [1] For a description of the Rabin and Karp algorithm, see "Algorithms"
26 * book by R. Sedgewick, Addison-Wesley, p252.
27 * [2] https://www.euccas.me/zlib/#zlib_rabin_karp and also "rolling hash"
28 * https://en.wikipedia.org/wiki/Rolling_hash
29 * [3] crbug.com/1316541 AOSP incremental client APK package OTA upgrades.
30 */
31 #ifdef CHROMIUM_ZLIB_NO_CASTAGNOLI
32 #define USE_ZLIB_RABIN_KARP_ROLLING_HASH
33 #endif
34
35 /* ===========================================================================
36 * Update a hash value with the given input byte (Rabin-Karp rolling hash).
37 * IN assertion: all calls to UPDATE_HASH are made with consecutive input
38 * characters, so that a running hash key can be computed from the previous
39 * key instead of complete recalculation each time.
40 */
41 #define UPDATE_HASH(s, h, c) (h = (((h) << s->hash_shift) ^ (c)) & s->hash_mask)
42
43 /* ===========================================================================
44 * Insert string str in the dictionary and set match_head to the previous head
45 * of the hash chain (the most recent string with same hash key). Return
46 * the previous length of the hash chain.
47 * If this file is compiled with -DFASTEST, the compression level is forced
48 * to 1, and no hash chains are maintained.
49 * IN assertion: all calls to INSERT_STRING are made with consecutive input
50 * characters and the first MIN_MATCH bytes of str are valid (except for
51 * the last MIN_MATCH-1 bytes of the input file).
52 */
insert_string(deflate_state * const s,const Pos str)53 local INLINE Pos insert_string(deflate_state* const s, const Pos str) {
54 Pos ret;
55 /* insert_string dictionary insertion: ANZAC++ hasher
56 * significantly improves data compression speed.
57 *
58 * Note: the generated compressed output is a valid DEFLATE stream, but will
59 * differ from canonical zlib output.
60 */
61 #if defined(USE_ZLIB_RABIN_KARP_ROLLING_HASH)
62 UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH - 1)]);
63 #else
64 uint32_t value;
65 // Validated for little endian archs (i.e. x86, Arm). YMMV for big endian.
66 zmemcpy(&value, &s->window[str], sizeof(value));
67 s->ins_h = ((value * 66521 + 66521) >> 16) & s->hash_mask;
68 #endif
69
70 #ifdef FASTEST
71 ret = s->head[s->ins_h];
72 #else
73 ret = s->prev[str & s->w_mask] = s->head[s->ins_h];
74 #endif
75 s->head[s->ins_h] = str;
76
77 return ret;
78 }
79
80 #endif /* INSERT_STRING_H */
81