/src/zlib-ng/insert_string_tpl.h
Line | Count | Source |
1 | | /* insert_string_tpl.h -- Private insert_string functions shared with more than |
2 | | * one insert string implementation |
3 | | * |
4 | | * Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler |
5 | | * |
6 | | * Copyright (C) 2013 Intel Corporation. All rights reserved. |
7 | | * Authors: |
8 | | * Wajdi Feghali <wajdi.k.feghali@intel.com> |
9 | | * Jim Guilford <james.guilford@intel.com> |
10 | | * Vinodh Gopal <vinodh.gopal@intel.com> |
11 | | * Erdinc Ozturk <erdinc.ozturk@intel.com> |
12 | | * Jim Kukunas <james.t.kukunas@linux.intel.com> |
13 | | * |
14 | | * Portions are Copyright (C) 2016 12Sided Technology, LLC. |
15 | | * Author: |
16 | | * Phil Vachon <pvachon@12sidedtech.com> |
17 | | * |
18 | | * For conditions of distribution and use, see copyright notice in zlib.h |
19 | | * |
20 | | */ |
21 | | |
22 | | #ifndef HASH_CALC_READ |
23 | 6.21M | # define HASH_CALC_READ val = Z_U32_FROM_LE(zng_memread_4(strstart)); |
24 | | #endif |
25 | | |
26 | | /* =========================================================================== |
27 | | * Update a hash value with the given input byte |
28 | | * IN assertion: all calls to UPDATE_HASH are made with consecutive |
29 | | * input characters, so that a running hash key can be computed from the |
30 | | * previous key instead of complete recalculation each time. |
31 | | */ |
32 | 4.79M | Z_FORCEINLINE static uint32_t UPDATE_HASH(uint32_t h, uint32_t val) { |
33 | 4.79M | HASH_CALC(h, val); |
34 | 4.79M | return h & HASH_CALC_MASK; |
35 | 4.79M | } deflate.c:update_hash_roll Line | Count | Source | 32 | 10.6k | Z_FORCEINLINE static uint32_t UPDATE_HASH(uint32_t h, uint32_t val) { | 33 | 10.6k | HASH_CALC(h, val); | 34 | 10.6k | return h & HASH_CALC_MASK; | 35 | 10.6k | } |
Unexecuted instantiation: deflate.c:update_hash Unexecuted instantiation: deflate_fast.c:update_hash Unexecuted instantiation: deflate_fast.c:update_hash_roll Unexecuted instantiation: deflate_medium.c:update_hash Unexecuted instantiation: deflate_medium.c:update_hash_roll Unexecuted instantiation: deflate_quick.c:update_hash Unexecuted instantiation: deflate_quick.c:update_hash_roll Unexecuted instantiation: deflate_slow.c:update_hash Unexecuted instantiation: deflate_slow.c:update_hash_roll Unexecuted instantiation: insert_string.c:update_hash Unexecuted instantiation: insert_string.c:update_hash_roll Unexecuted instantiation: compare256_sse2.c:update_hash_roll Unexecuted instantiation: compare256_sse2.c:update_hash compare256_avx2.c:update_hash_roll Line | Count | Source | 32 | 4.78M | Z_FORCEINLINE static uint32_t UPDATE_HASH(uint32_t h, uint32_t val) { | 33 | 4.78M | HASH_CALC(h, val); | 34 | 4.78M | return h & HASH_CALC_MASK; | 35 | 4.78M | } |
Unexecuted instantiation: compare256_avx2.c:update_hash Unexecuted instantiation: compare256_avx512.c:update_hash_roll Unexecuted instantiation: compare256_avx512.c:update_hash |
36 | | |
37 | | /* =========================================================================== |
38 | | * Quick insert string str in the dictionary using a pre-read value and set match_head |
39 | | * to the previous head of the hash chain (the most recent string with same hash key). |
40 | | * Return the previous length of the hash chain. |
41 | | */ |
42 | 733k | Z_FORCEINLINE static uint32_t QUICK_INSERT_VALUE(deflate_state *const s, uint32_t str, uint32_t val) { |
43 | 733k | uint32_t hm, head; |
44 | | |
45 | 733k | HASH_CALC_VAR_INIT; |
46 | 733k | HASH_CALC(HASH_CALC_VAR, val); |
47 | 733k | HASH_CALC_VAR &= HASH_CALC_MASK; |
48 | 733k | hm = HASH_CALC_VAR; |
49 | | |
50 | 733k | head = s->head[hm]; |
51 | 733k | if (LIKELY(head != str)) { |
52 | 733k | s->prev[str & W_MASK(s)] = (Pos)head; |
53 | 733k | s->head[hm] = (Pos)str; |
54 | 733k | } |
55 | 733k | return head; |
56 | 733k | } Unexecuted instantiation: deflate.c:quick_insert_value Unexecuted instantiation: deflate.c:quick_insert_value_roll deflate_fast.c:quick_insert_value Line | Count | Source | 42 | 733k | Z_FORCEINLINE static uint32_t QUICK_INSERT_VALUE(deflate_state *const s, uint32_t str, uint32_t val) { | 43 | 733k | uint32_t hm, head; | 44 | | | 45 | 733k | HASH_CALC_VAR_INIT; | 46 | 733k | HASH_CALC(HASH_CALC_VAR, val); | 47 | 733k | HASH_CALC_VAR &= HASH_CALC_MASK; | 48 | 733k | hm = HASH_CALC_VAR; | 49 | | | 50 | 733k | head = s->head[hm]; | 51 | 733k | if (LIKELY(head != str)) { | 52 | 733k | s->prev[str & W_MASK(s)] = (Pos)head; | 53 | 733k | s->head[hm] = (Pos)str; | 54 | 733k | } | 55 | 733k | return head; | 56 | 733k | } |
Unexecuted instantiation: deflate_fast.c:quick_insert_value_roll Unexecuted instantiation: deflate_medium.c:quick_insert_value Unexecuted instantiation: deflate_medium.c:quick_insert_value_roll Unexecuted instantiation: deflate_quick.c:quick_insert_value Unexecuted instantiation: deflate_quick.c:quick_insert_value_roll Unexecuted instantiation: deflate_slow.c:quick_insert_value Unexecuted instantiation: deflate_slow.c:quick_insert_value_roll Unexecuted instantiation: insert_string.c:quick_insert_value Unexecuted instantiation: insert_string.c:quick_insert_value_roll Unexecuted instantiation: compare256_sse2.c:quick_insert_value Unexecuted instantiation: compare256_sse2.c:quick_insert_value_roll Unexecuted instantiation: compare256_avx2.c:quick_insert_value Unexecuted instantiation: compare256_avx2.c:quick_insert_value_roll Unexecuted instantiation: compare256_avx512.c:quick_insert_value Unexecuted instantiation: compare256_avx512.c:quick_insert_value_roll |
57 | | |
58 | | /* =========================================================================== |
59 | | * Quick insert string str in the dictionary and set match_head to the previous head |
60 | | * of the hash chain (the most recent string with same hash key). Return |
61 | | * the previous length of the hash chain. |
62 | | */ |
63 | 3.92M | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { |
64 | 3.92M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; |
65 | 3.92M | uint32_t val, hm, head; |
66 | | |
67 | 3.92M | HASH_CALC_VAR_INIT; |
68 | 3.92M | HASH_CALC_READ; |
69 | 3.92M | HASH_CALC(HASH_CALC_VAR, val); |
70 | 3.92M | HASH_CALC_VAR &= HASH_CALC_MASK; |
71 | 3.92M | hm = HASH_CALC_VAR; |
72 | | |
73 | 3.92M | head = s->head[hm]; |
74 | 3.92M | if (LIKELY(head != str)) { |
75 | 3.91M | s->prev[str & W_MASK(s)] = (Pos)head; |
76 | 3.91M | s->head[hm] = (Pos)str; |
77 | 3.91M | } |
78 | 3.92M | return head; |
79 | 3.92M | } deflate.c:quick_insert_string Line | Count | Source | 63 | 22.5k | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 22.5k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 22.5k | uint32_t val, hm, head; | 66 | | | 67 | 22.5k | HASH_CALC_VAR_INIT; | 68 | 22.5k | HASH_CALC_READ; | 69 | 22.5k | HASH_CALC(HASH_CALC_VAR, val); | 70 | 22.5k | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 22.5k | hm = HASH_CALC_VAR; | 72 | | | 73 | 22.5k | head = s->head[hm]; | 74 | 22.5k | if (LIKELY(head != str)) { | 75 | 14.5k | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 14.5k | s->head[hm] = (Pos)str; | 77 | 14.5k | } | 78 | 22.5k | return head; | 79 | 22.5k | } |
Unexecuted instantiation: deflate.c:quick_insert_string_roll deflate_fast.c:quick_insert_string Line | Count | Source | 63 | 81.9k | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 81.9k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 81.9k | uint32_t val, hm, head; | 66 | | | 67 | 81.9k | HASH_CALC_VAR_INIT; | 68 | 81.9k | HASH_CALC_READ; | 69 | 81.9k | HASH_CALC(HASH_CALC_VAR, val); | 70 | 81.9k | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 81.9k | hm = HASH_CALC_VAR; | 72 | | | 73 | 81.9k | head = s->head[hm]; | 74 | 81.9k | if (LIKELY(head != str)) { | 75 | 81.9k | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 81.9k | s->head[hm] = (Pos)str; | 77 | 81.9k | } | 78 | 81.9k | return head; | 79 | 81.9k | } |
Unexecuted instantiation: deflate_fast.c:quick_insert_string_roll deflate_medium.c:quick_insert_string Line | Count | Source | 63 | 1.71M | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 1.71M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 1.71M | uint32_t val, hm, head; | 66 | | | 67 | 1.71M | HASH_CALC_VAR_INIT; | 68 | 1.71M | HASH_CALC_READ; | 69 | 1.71M | HASH_CALC(HASH_CALC_VAR, val); | 70 | 1.71M | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 1.71M | hm = HASH_CALC_VAR; | 72 | | | 73 | 1.71M | head = s->head[hm]; | 74 | 1.71M | if (LIKELY(head != str)) { | 75 | 1.71M | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 1.71M | s->head[hm] = (Pos)str; | 77 | 1.71M | } | 78 | 1.71M | return head; | 79 | 1.71M | } |
Unexecuted instantiation: deflate_medium.c:quick_insert_string_roll Unexecuted instantiation: deflate_quick.c:quick_insert_string Unexecuted instantiation: deflate_quick.c:quick_insert_string_roll deflate_slow.c:quick_insert_string_roll Line | Count | Source | 63 | 1.94M | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 1.94M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 1.94M | uint32_t val, hm, head; | 66 | | | 67 | 1.94M | HASH_CALC_VAR_INIT; | 68 | 1.94M | HASH_CALC_READ; | 69 | 1.94M | HASH_CALC(HASH_CALC_VAR, val); | 70 | 1.94M | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 1.94M | hm = HASH_CALC_VAR; | 72 | | | 73 | 1.94M | head = s->head[hm]; | 74 | 1.94M | if (LIKELY(head != str)) { | 75 | 1.94M | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 1.94M | s->head[hm] = (Pos)str; | 77 | 1.94M | } | 78 | 1.94M | return head; | 79 | 1.94M | } |
deflate_slow.c:quick_insert_string Line | Count | Source | 63 | 160k | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 160k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 160k | uint32_t val, hm, head; | 66 | | | 67 | 160k | HASH_CALC_VAR_INIT; | 68 | 160k | HASH_CALC_READ; | 69 | 160k | HASH_CALC(HASH_CALC_VAR, val); | 70 | 160k | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 160k | hm = HASH_CALC_VAR; | 72 | | | 73 | 160k | head = s->head[hm]; | 74 | 160k | if (LIKELY(head != str)) { | 75 | 160k | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 160k | s->head[hm] = (Pos)str; | 77 | 160k | } | 78 | 160k | return head; | 79 | 160k | } |
Unexecuted instantiation: insert_string.c:quick_insert_string Unexecuted instantiation: insert_string.c:quick_insert_string_roll Unexecuted instantiation: compare256_sse2.c:quick_insert_string Unexecuted instantiation: compare256_sse2.c:quick_insert_string_roll Unexecuted instantiation: compare256_avx2.c:quick_insert_string Unexecuted instantiation: compare256_avx2.c:quick_insert_string_roll Unexecuted instantiation: compare256_avx512.c:quick_insert_string Unexecuted instantiation: compare256_avx512.c:quick_insert_string_roll |
80 | | |
81 | | /* =========================================================================== |
82 | | * Insert string str in the dictionary and set match_head to the previous head |
83 | | * of the hash chain (the most recent string with same hash key). Return |
84 | | * the previous length of the hash chain. |
85 | | * IN assertion: all calls to INSERT_STRING are made with consecutive |
86 | | * input characters and the first STD_MIN_MATCH bytes of str are valid |
87 | | * (except for the last STD_MIN_MATCH-1 bytes of the input file). |
88 | | */ |
89 | 420k | Z_FORCEINLINE static void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { |
90 | 420k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; |
91 | 420k | uint8_t *strend = strstart + count; |
92 | | |
93 | | /* Local pointers to avoid indirection */ |
94 | 420k | Pos *headp = s->head; |
95 | 420k | Pos *prevp = s->prev; |
96 | 420k | const unsigned int w_mask = W_MASK(s); |
97 | | |
98 | 8.69M | for (uint32_t idx = str; strstart < strend; idx++, strstart++) { |
99 | 8.27M | uint32_t val, hm, head; |
100 | | |
101 | 8.27M | HASH_CALC_VAR_INIT; |
102 | 8.27M | HASH_CALC_READ; |
103 | 8.27M | HASH_CALC(HASH_CALC_VAR, val); |
104 | 8.27M | HASH_CALC_VAR &= HASH_CALC_MASK; |
105 | 8.27M | hm = HASH_CALC_VAR; |
106 | | |
107 | 8.27M | head = headp[hm]; |
108 | 8.27M | if (LIKELY(head != idx)) { |
109 | 8.26M | prevp[idx & w_mask] = (Pos)head; |
110 | 8.26M | headp[hm] = (Pos)idx; |
111 | 8.26M | } |
112 | 8.27M | } |
113 | 420k | } Unexecuted instantiation: deflate.c:insert_string_static Unexecuted instantiation: deflate.c:insert_string_roll_static deflate_fast.c:insert_string_static Line | Count | Source | 89 | 38.7k | Z_FORCEINLINE static void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { | 90 | 38.7k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 91 | 38.7k | uint8_t *strend = strstart + count; | 92 | | | 93 | | /* Local pointers to avoid indirection */ | 94 | 38.7k | Pos *headp = s->head; | 95 | 38.7k | Pos *prevp = s->prev; | 96 | 38.7k | const unsigned int w_mask = W_MASK(s); | 97 | | | 98 | 155k | for (uint32_t idx = str; strstart < strend; idx++, strstart++) { | 99 | 116k | uint32_t val, hm, head; | 100 | | | 101 | 116k | HASH_CALC_VAR_INIT; | 102 | 116k | HASH_CALC_READ; | 103 | 116k | HASH_CALC(HASH_CALC_VAR, val); | 104 | 116k | HASH_CALC_VAR &= HASH_CALC_MASK; | 105 | 116k | hm = HASH_CALC_VAR; | 106 | | | 107 | 116k | head = headp[hm]; | 108 | 116k | if (LIKELY(head != idx)) { | 109 | 116k | prevp[idx & w_mask] = (Pos)head; | 110 | 116k | headp[hm] = (Pos)idx; | 111 | 116k | } | 112 | 116k | } | 113 | 38.7k | } |
Unexecuted instantiation: deflate_fast.c:insert_string_roll_static Unexecuted instantiation: deflate_medium.c:insert_string_static Unexecuted instantiation: deflate_medium.c:insert_string_roll_static Unexecuted instantiation: deflate_quick.c:insert_string_static Unexecuted instantiation: deflate_quick.c:insert_string_roll_static Unexecuted instantiation: deflate_slow.c:insert_string_static Unexecuted instantiation: deflate_slow.c:insert_string_roll_static insert_string.c:insert_string_static Line | Count | Source | 89 | 172k | Z_FORCEINLINE static void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { | 90 | 172k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 91 | 172k | uint8_t *strend = strstart + count; | 92 | | | 93 | | /* Local pointers to avoid indirection */ | 94 | 172k | Pos *headp = s->head; | 95 | 172k | Pos *prevp = s->prev; | 96 | 172k | const unsigned int w_mask = W_MASK(s); | 97 | | | 98 | 4.28M | for (uint32_t idx = str; strstart < strend; idx++, strstart++) { | 99 | 4.11M | uint32_t val, hm, head; | 100 | | | 101 | 4.11M | HASH_CALC_VAR_INIT; | 102 | 4.11M | HASH_CALC_READ; | 103 | 4.11M | HASH_CALC(HASH_CALC_VAR, val); | 104 | 4.11M | HASH_CALC_VAR &= HASH_CALC_MASK; | 105 | 4.11M | hm = HASH_CALC_VAR; | 106 | | | 107 | 4.11M | head = headp[hm]; | 108 | 4.11M | if (LIKELY(head != idx)) { | 109 | 4.10M | prevp[idx & w_mask] = (Pos)head; | 110 | 4.10M | headp[hm] = (Pos)idx; | 111 | 4.10M | } | 112 | 4.11M | } | 113 | 172k | } |
insert_string.c:insert_string_roll_static Line | Count | Source | 89 | 209k | Z_FORCEINLINE static void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { | 90 | 209k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 91 | 209k | uint8_t *strend = strstart + count; | 92 | | | 93 | | /* Local pointers to avoid indirection */ | 94 | 209k | Pos *headp = s->head; | 95 | 209k | Pos *prevp = s->prev; | 96 | 209k | const unsigned int w_mask = W_MASK(s); | 97 | | | 98 | 4.24M | for (uint32_t idx = str; strstart < strend; idx++, strstart++) { | 99 | 4.04M | uint32_t val, hm, head; | 100 | | | 101 | 4.04M | HASH_CALC_VAR_INIT; | 102 | 4.04M | HASH_CALC_READ; | 103 | 4.04M | HASH_CALC(HASH_CALC_VAR, val); | 104 | 4.04M | HASH_CALC_VAR &= HASH_CALC_MASK; | 105 | 4.04M | hm = HASH_CALC_VAR; | 106 | | | 107 | 4.04M | head = headp[hm]; | 108 | 4.04M | if (LIKELY(head != idx)) { | 109 | 4.03M | prevp[idx & w_mask] = (Pos)head; | 110 | 4.03M | headp[hm] = (Pos)idx; | 111 | 4.03M | } | 112 | 4.04M | } | 113 | 209k | } |
Unexecuted instantiation: compare256_sse2.c:insert_string_static Unexecuted instantiation: compare256_sse2.c:insert_string_roll_static Unexecuted instantiation: compare256_avx2.c:insert_string_static Unexecuted instantiation: compare256_avx2.c:insert_string_roll_static Unexecuted instantiation: compare256_avx512.c:insert_string_static Unexecuted instantiation: compare256_avx512.c:insert_string_roll_static |
114 | | |
115 | | // Cleanup |
116 | | #undef HASH_SLIDE |
117 | | #undef HASH_CALC |
118 | | #undef HASH_CALC_READ |
119 | | #undef HASH_CALC_MASK |
120 | | #undef HASH_CALC_OFFSET |
121 | | #undef HASH_CALC_VAR |
122 | | #undef HASH_CALC_VAR_INIT |
123 | | #undef UPDATE_HASH |
124 | | #undef INSERT_STRING |
125 | | #undef QUICK_INSERT_STRING |
126 | | #undef QUICK_INSERT_VALUE |