/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 | 94.2M | # 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 | 33.7M | Z_FORCEINLINE static uint32_t UPDATE_HASH(uint32_t h, uint32_t val) { |
33 | 33.7M | HASH_CALC(h, val); |
34 | 33.7M | return h & HASH_CALC_MASK; |
35 | 33.7M | } deflate.c:update_hash_roll Line | Count | Source | 32 | 4.33k | Z_FORCEINLINE static uint32_t UPDATE_HASH(uint32_t h, uint32_t val) { | 33 | 4.33k | HASH_CALC(h, val); | 34 | 4.33k | return h & HASH_CALC_MASK; | 35 | 4.33k | } |
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 | 33.6M | Z_FORCEINLINE static uint32_t UPDATE_HASH(uint32_t h, uint32_t val) { | 33 | 33.6M | HASH_CALC(h, val); | 34 | 33.6M | return h & HASH_CALC_MASK; | 35 | 33.6M | } |
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 | 98.7M | Z_FORCEINLINE static uint32_t QUICK_INSERT_VALUE(deflate_state *const s, uint32_t str, uint32_t val) { |
43 | 98.7M | uint32_t hm, head; |
44 | | |
45 | 98.7M | HASH_CALC_VAR_INIT; |
46 | 98.7M | HASH_CALC(HASH_CALC_VAR, val); |
47 | 98.7M | HASH_CALC_VAR &= HASH_CALC_MASK; |
48 | 98.7M | hm = HASH_CALC_VAR; |
49 | | |
50 | 98.7M | head = s->head[hm]; |
51 | 98.7M | if (LIKELY(head != str)) { |
52 | 98.7M | s->prev[str & W_MASK(s)] = (Pos)head; |
53 | 98.7M | s->head[hm] = (Pos)str; |
54 | 98.7M | } |
55 | 98.7M | return head; |
56 | 98.7M | } 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 | 23.4M | Z_FORCEINLINE static uint32_t QUICK_INSERT_VALUE(deflate_state *const s, uint32_t str, uint32_t val) { | 43 | 23.4M | uint32_t hm, head; | 44 | | | 45 | 23.4M | HASH_CALC_VAR_INIT; | 46 | 23.4M | HASH_CALC(HASH_CALC_VAR, val); | 47 | 23.4M | HASH_CALC_VAR &= HASH_CALC_MASK; | 48 | 23.4M | hm = HASH_CALC_VAR; | 49 | | | 50 | 23.4M | head = s->head[hm]; | 51 | 23.4M | if (LIKELY(head != str)) { | 52 | 23.4M | s->prev[str & W_MASK(s)] = (Pos)head; | 53 | 23.4M | s->head[hm] = (Pos)str; | 54 | 23.4M | } | 55 | 23.4M | return head; | 56 | 23.4M | } |
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 deflate_quick.c:quick_insert_value Line | Count | Source | 42 | 75.2M | Z_FORCEINLINE static uint32_t QUICK_INSERT_VALUE(deflate_state *const s, uint32_t str, uint32_t val) { | 43 | 75.2M | uint32_t hm, head; | 44 | | | 45 | 75.2M | HASH_CALC_VAR_INIT; | 46 | 75.2M | HASH_CALC(HASH_CALC_VAR, val); | 47 | 75.2M | HASH_CALC_VAR &= HASH_CALC_MASK; | 48 | 75.2M | hm = HASH_CALC_VAR; | 49 | | | 50 | 75.2M | head = s->head[hm]; | 51 | 75.2M | if (LIKELY(head != str)) { | 52 | 75.2M | s->prev[str & W_MASK(s)] = (Pos)head; | 53 | 75.2M | s->head[hm] = (Pos)str; | 54 | 75.2M | } | 55 | 75.2M | return head; | 56 | 75.2M | } |
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 | 97.5M | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { |
64 | 97.5M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; |
65 | 97.5M | uint32_t val, hm, head; |
66 | | |
67 | 97.5M | HASH_CALC_VAR_INIT; |
68 | 97.5M | HASH_CALC_READ; |
69 | 97.5M | HASH_CALC(HASH_CALC_VAR, val); |
70 | 97.5M | HASH_CALC_VAR &= HASH_CALC_MASK; |
71 | 97.5M | hm = HASH_CALC_VAR; |
72 | | |
73 | 97.5M | head = s->head[hm]; |
74 | 97.5M | if (LIKELY(head != str)) { |
75 | 97.5M | s->prev[str & W_MASK(s)] = (Pos)head; |
76 | 97.5M | s->head[hm] = (Pos)str; |
77 | 97.5M | } |
78 | 97.5M | return head; |
79 | 97.5M | } deflate.c:quick_insert_string Line | Count | Source | 63 | 8.93k | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 8.93k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 8.93k | uint32_t val, hm, head; | 66 | | | 67 | 8.93k | HASH_CALC_VAR_INIT; | 68 | 8.93k | HASH_CALC_READ; | 69 | 8.93k | HASH_CALC(HASH_CALC_VAR, val); | 70 | 8.93k | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 8.93k | hm = HASH_CALC_VAR; | 72 | | | 73 | 8.93k | head = s->head[hm]; | 74 | 8.93k | if (LIKELY(head != str)) { | 75 | 3.84k | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 3.84k | s->head[hm] = (Pos)str; | 77 | 3.84k | } | 78 | 8.93k | return head; | 79 | 8.93k | } |
Unexecuted instantiation: deflate.c:quick_insert_string_roll deflate_fast.c:quick_insert_string Line | Count | Source | 63 | 543k | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 543k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 543k | uint32_t val, hm, head; | 66 | | | 67 | 543k | HASH_CALC_VAR_INIT; | 68 | 543k | HASH_CALC_READ; | 69 | 543k | HASH_CALC(HASH_CALC_VAR, val); | 70 | 543k | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 543k | hm = HASH_CALC_VAR; | 72 | | | 73 | 543k | head = s->head[hm]; | 74 | 543k | if (LIKELY(head != str)) { | 75 | 543k | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 543k | s->head[hm] = (Pos)str; | 77 | 543k | } | 78 | 543k | return head; | 79 | 543k | } |
Unexecuted instantiation: deflate_fast.c:quick_insert_string_roll deflate_medium.c:quick_insert_string Line | Count | Source | 63 | 42.0M | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 42.0M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 42.0M | uint32_t val, hm, head; | 66 | | | 67 | 42.0M | HASH_CALC_VAR_INIT; | 68 | 42.0M | HASH_CALC_READ; | 69 | 42.0M | HASH_CALC(HASH_CALC_VAR, val); | 70 | 42.0M | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 42.0M | hm = HASH_CALC_VAR; | 72 | | | 73 | 42.0M | head = s->head[hm]; | 74 | 42.0M | if (LIKELY(head != str)) { | 75 | 42.0M | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 42.0M | s->head[hm] = (Pos)str; | 77 | 42.0M | } | 78 | 42.0M | return head; | 79 | 42.0M | } |
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 | 38.6M | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 38.6M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 38.6M | uint32_t val, hm, head; | 66 | | | 67 | 38.6M | HASH_CALC_VAR_INIT; | 68 | 38.6M | HASH_CALC_READ; | 69 | 38.6M | HASH_CALC(HASH_CALC_VAR, val); | 70 | 38.6M | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 38.6M | hm = HASH_CALC_VAR; | 72 | | | 73 | 38.6M | head = s->head[hm]; | 74 | 38.6M | if (LIKELY(head != str)) { | 75 | 38.6M | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 38.6M | s->head[hm] = (Pos)str; | 77 | 38.6M | } | 78 | 38.6M | return head; | 79 | 38.6M | } |
deflate_slow.c:quick_insert_string Line | Count | Source | 63 | 16.2M | Z_FORCEINLINE static uint32_t QUICK_INSERT_STRING(deflate_state *const s, uint32_t str) { | 64 | 16.2M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 65 | 16.2M | uint32_t val, hm, head; | 66 | | | 67 | 16.2M | HASH_CALC_VAR_INIT; | 68 | 16.2M | HASH_CALC_READ; | 69 | 16.2M | HASH_CALC(HASH_CALC_VAR, val); | 70 | 16.2M | HASH_CALC_VAR &= HASH_CALC_MASK; | 71 | 16.2M | hm = HASH_CALC_VAR; | 72 | | | 73 | 16.2M | head = s->head[hm]; | 74 | 16.2M | if (LIKELY(head != str)) { | 75 | 16.2M | s->prev[str & W_MASK(s)] = (Pos)head; | 76 | 16.2M | s->head[hm] = (Pos)str; | 77 | 16.2M | } | 78 | 16.2M | return head; | 79 | 16.2M | } |
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 | 8.32M | Z_FORCEINLINE static void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { |
90 | 8.32M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; |
91 | 8.32M | uint8_t *strend = strstart + count; |
92 | | |
93 | | /* Local pointers to avoid indirection */ |
94 | 8.32M | Pos *headp = s->head; |
95 | 8.32M | Pos *prevp = s->prev; |
96 | 8.32M | const unsigned int w_mask = W_MASK(s); |
97 | | |
98 | 72.2M | for (uint32_t idx = str; strstart < strend; idx++, strstart++) { |
99 | 63.9M | uint32_t val, hm, head; |
100 | | |
101 | 63.9M | HASH_CALC_VAR_INIT; |
102 | 63.9M | HASH_CALC_READ; |
103 | 63.9M | HASH_CALC(HASH_CALC_VAR, val); |
104 | 63.9M | HASH_CALC_VAR &= HASH_CALC_MASK; |
105 | 63.9M | hm = HASH_CALC_VAR; |
106 | | |
107 | 63.9M | head = headp[hm]; |
108 | 63.9M | if (LIKELY(head != idx)) { |
109 | 63.9M | prevp[idx & w_mask] = (Pos)head; |
110 | 63.9M | headp[hm] = (Pos)idx; |
111 | 63.9M | } |
112 | 63.9M | } |
113 | 8.32M | } 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 | 495k | Z_FORCEINLINE static void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { | 90 | 495k | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 91 | 495k | uint8_t *strend = strstart + count; | 92 | | | 93 | | /* Local pointers to avoid indirection */ | 94 | 495k | Pos *headp = s->head; | 95 | 495k | Pos *prevp = s->prev; | 96 | 495k | const unsigned int w_mask = W_MASK(s); | 97 | | | 98 | 1.98M | for (uint32_t idx = str; strstart < strend; idx++, strstart++) { | 99 | 1.48M | uint32_t val, hm, head; | 100 | | | 101 | 1.48M | HASH_CALC_VAR_INIT; | 102 | 1.48M | HASH_CALC_READ; | 103 | 1.48M | HASH_CALC(HASH_CALC_VAR, val); | 104 | 1.48M | HASH_CALC_VAR &= HASH_CALC_MASK; | 105 | 1.48M | hm = HASH_CALC_VAR; | 106 | | | 107 | 1.48M | head = headp[hm]; | 108 | 1.48M | if (LIKELY(head != idx)) { | 109 | 1.48M | prevp[idx & w_mask] = (Pos)head; | 110 | 1.48M | headp[hm] = (Pos)idx; | 111 | 1.48M | } | 112 | 1.48M | } | 113 | 495k | } |
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 | 3.01M | Z_FORCEINLINE static void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { | 90 | 3.01M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 91 | 3.01M | uint8_t *strend = strstart + count; | 92 | | | 93 | | /* Local pointers to avoid indirection */ | 94 | 3.01M | Pos *headp = s->head; | 95 | 3.01M | Pos *prevp = s->prev; | 96 | 3.01M | const unsigned int w_mask = W_MASK(s); | 97 | | | 98 | 36.8M | for (uint32_t idx = str; strstart < strend; idx++, strstart++) { | 99 | 33.8M | uint32_t val, hm, head; | 100 | | | 101 | 33.8M | HASH_CALC_VAR_INIT; | 102 | 33.8M | HASH_CALC_READ; | 103 | 33.8M | HASH_CALC(HASH_CALC_VAR, val); | 104 | 33.8M | HASH_CALC_VAR &= HASH_CALC_MASK; | 105 | 33.8M | hm = HASH_CALC_VAR; | 106 | | | 107 | 33.8M | head = headp[hm]; | 108 | 33.8M | if (LIKELY(head != idx)) { | 109 | 33.8M | prevp[idx & w_mask] = (Pos)head; | 110 | 33.8M | headp[hm] = (Pos)idx; | 111 | 33.8M | } | 112 | 33.8M | } | 113 | 3.01M | } |
insert_string.c:insert_string_roll_static Line | Count | Source | 89 | 4.81M | Z_FORCEINLINE static void INSERT_STRING(deflate_state *const s, uint32_t str, uint32_t count) { | 90 | 4.81M | uint8_t *strstart = s->window + str + HASH_CALC_OFFSET; | 91 | 4.81M | uint8_t *strend = strstart + count; | 92 | | | 93 | | /* Local pointers to avoid indirection */ | 94 | 4.81M | Pos *headp = s->head; | 95 | 4.81M | Pos *prevp = s->prev; | 96 | 4.81M | const unsigned int w_mask = W_MASK(s); | 97 | | | 98 | 33.3M | for (uint32_t idx = str; strstart < strend; idx++, strstart++) { | 99 | 28.5M | uint32_t val, hm, head; | 100 | | | 101 | 28.5M | HASH_CALC_VAR_INIT; | 102 | 28.5M | HASH_CALC_READ; | 103 | 28.5M | HASH_CALC(HASH_CALC_VAR, val); | 104 | 28.5M | HASH_CALC_VAR &= HASH_CALC_MASK; | 105 | 28.5M | hm = HASH_CALC_VAR; | 106 | | | 107 | 28.5M | head = headp[hm]; | 108 | 28.5M | if (LIKELY(head != idx)) { | 109 | 28.5M | prevp[idx & w_mask] = (Pos)head; | 110 | 28.5M | headp[hm] = (Pos)idx; | 111 | 28.5M | } | 112 | 28.5M | } | 113 | 4.81M | } |
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 |