/src/zlib-ng/insert_string_p.h

Source
/* insert_string_p.h -- static single and batch hash insert functions
 *
 * Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */
#ifndef INSERT_STRING_P_H_
#define INSERT_STRING_P_H_

#define KNUTH_SHIFT (32 - HASH_BITS)
#define UPDATE_HASH_KNUTH(h,val) h = (((val) * 2654435761U) >> KNUTH_SHIFT)

#if (HASH_SIZE) > 65536u
#  define ROLL_HASH_SIZE 65536
#else
#  define ROLL_HASH_SIZE HASH_SIZE
#endif
#define ROLL_MASK ((HASH_SIZE / 2) - 1u))
#define UPDATE_HASH_ROLL(h,val) h = (((h << 5) ^ ((uint8_t)(val))) & ROLL_MASK

/* ===========================================================================
 * Update a hash value with the given input byte
 * IN  assertion: all calls to UPDATE_HASH are made with consecutive
 *    input characters, so that a running hash key can be computed from the
 *    previous key instead of complete recalculation each time.
 */
Z_FORCEINLINE static uint32_t update_hash_roll(uint32_t h, uint32_t val) {
    UPDATE_HASH_ROLL(h, val);
    return h;
}

/* ===========================================================================
 * Insert string str in the dictionary using a pre-read value and set match_head
 * to the previous head of the hash chain (the most recent string with same hash key).
 * Return the previous length of the hash chain.
 */
Z_FORCEINLINE static uint32_t insert_knuth_val(deflate_state *const s, uint32_t str, uint32_t val) {
    uint32_t h, head;

    UPDATE_HASH_KNUTH(h, val);

    head = s->head[h];
    if (LIKELY(head != str)) {
        s->prev[str & W_MASK(s)] = (Pos)head;
        s->head[h] = (Pos)str;
    }
    return head;
}

/* ===========================================================================
 * Insert string str using a pre-read value, returning the previous head of the
 * hash chain. The prev link is left untouched since deflate_quick only inspects
 * the chain head and never walks the chain.
 */
Z_FORCEINLINE static uint32_t insert_knuth_val_head(deflate_state *const s, uint32_t str, uint32_t val) {
    uint32_t h, head;

    UPDATE_HASH_KNUTH(h, val);

    head = s->head[h];
    s->head[h] = (Pos)str;
    return head;
}

/* ===========================================================================
 * Insert string str in the dictionary and set match_head to the previous head
 * of the hash chain (the most recent string with same hash key). Return
 * the previous length of the hash chain.
 */
Z_FORCEINLINE static uint32_t insert_knuth(deflate_state *const s, unsigned char *window, uint32_t str) {
    uint8_t *strstart = window + str;
    uint32_t val, h, head;

    val = Z_U32_FROM_LE(zng_memread_4(strstart));
    UPDATE_HASH_KNUTH(h, val);

    head = s->head[h];
    if (LIKELY(head != str)) {
        s->prev[str & W_MASK(s)] = (Pos)head;
        s->head[h] = (Pos)str;
    }
    return head;
}

/* ===========================================================================
 * Insert string str read from the window, returning the previous head of the
 * hash chain. Like insert_knuth but leaves the prev link untouched for
 * deflate_quick, which only inspects the chain head.
 */
Z_FORCEINLINE static uint32_t insert_knuth_head(deflate_state *const s, unsigned char *window, uint32_t str) {
    uint8_t *strstart = window + str;
    uint32_t val, h, head;

    val = Z_U32_FROM_LE(zng_memread_4(strstart));
    UPDATE_HASH_KNUTH(h, val);

    head = s->head[h];
    s->head[h] = (Pos)str;
    return head;
}

Z_FORCEINLINE static uint32_t insert_roll(deflate_state *const s, unsigned char *window, uint32_t str) {
    uint8_t *strstart = window + str + (STD_MIN_MATCH-1);
    uint32_t h, head;

    h = s->ins_h;
    UPDATE_HASH_ROLL(h, strstart[0]);
    s->ins_h = h;

    head = s->head[h];
    if (LIKELY(head != str)) {
        s->prev[str & W_MASK(s)] = (Pos)head;
        s->head[h] = (Pos)str;
    }
    return head;
}

/* ===========================================================================
 * Insert string str in the dictionary and set match_head to the previous head
 * of the hash chain (the most recent string with same hash key). Return
 * the previous length of the hash chain.
 * IN  assertion: all calls to insert_knuth_batch are made with consecutive
 *    input characters and the first STD_MIN_MATCH bytes of str are valid
 *    (except for the last STD_MIN_MATCH-1 bytes of the input file).
 */
Z_FORCEINLINE static void insert_knuth_batch_static(deflate_state *const s, unsigned char *window, uint32_t str, uint32_t count) {
    uint8_t *strstart = window + str;
    uint8_t *strend = strstart + count;

    /* Local pointers to avoid indirection */
    Pos *headp = s->head;
    Pos *prevp = s->prev;
    const unsigned int w_mask = W_MASK(s);

    for (uint32_t idx = str; strstart < strend; idx++, strstart++) {
        uint32_t val, h, head;

        val = Z_U32_FROM_LE(zng_memread_4(strstart));
        UPDATE_HASH_KNUTH(h, val);

        head = headp[h];
        if (LIKELY(head != idx)) {
            prevp[idx & w_mask] = (Pos)head;
            headp[h] = (Pos)idx;
        }
    }
}

/* ===========================================================================
 * Insert count strings read from the window, leaving the prev links untouched.
 * Used by fill_window during deflate_quick, which only inspects the chain head.
 */
Z_FORCEINLINE static void insert_knuth_batch_head_static(deflate_state *const s, unsigned char *window, uint32_t str, uint32_t count) {
    uint8_t *strstart = window + str;
    uint8_t *strend = strstart + count;
    Pos *headp = s->head;

    for (uint32_t idx = str; strstart < strend; idx++, strstart++) {
        uint32_t val, h;

        val = Z_U32_FROM_LE(zng_memread_4(strstart));
        UPDATE_HASH_KNUTH(h, val);

        headp[h] = (Pos)idx;
    }
}

Z_FORCEINLINE static void insert_roll_batch_static(deflate_state *const s, unsigned char *window, uint32_t str, uint32_t count) {
    uint8_t *strstart = window + str + (STD_MIN_MATCH-1);
    uint8_t *strend = strstart + count;

    /* Local pointers to avoid indirection */
    Pos *headp = s->head;
    Pos *prevp = s->prev;
    uint32_t h = s->ins_h;
    const unsigned int w_mask = W_MASK(s);

    for (uint32_t idx = str; strstart < strend; idx++, strstart++) {
        uint32_t head;

        UPDATE_HASH_ROLL(h, strstart[0]);

        head = headp[h];
        if (LIKELY(head != idx)) {
            prevp[idx & w_mask] = (Pos)head;
            headp[h] = (Pos)idx;
        }
    }
    s->ins_h = h;
}

#endif

Line	Count	Source
1		/* insert_string_p.h -- static single and batch hash insert functions
2		*
3		* Copyright (C) 1995-2024 Jean-loup Gailly and Mark Adler
4		* For conditions of distribution and use, see copyright notice in zlib.h
5		*/
6		#ifndef INSERT_STRING_P_H_
7		#define INSERT_STRING_P_H_
8
9		#define KNUTH_SHIFT (32 - HASH_BITS)
10		#define UPDATE_HASH_KNUTH(h,val) h = (((val) * 2654435761U) >> KNUTH_SHIFT)
11
12		#if (HASH_SIZE) > 65536u
13		# define ROLL_HASH_SIZE 65536
14		#else
15		# define ROLL_HASH_SIZE HASH_SIZE
16		#endif
17	0	#define ROLL_MASK ((HASH_SIZE / 2) - 1u))
18	0	#define UPDATE_HASH_ROLL(h,val) h = (((h << 5) ^ ((uint8_t)(val))) & ROLL_MASK
19
20		/* ===========================================================================
21		* Update a hash value with the given input byte
22		* IN assertion: all calls to UPDATE_HASH are made with consecutive
23		* input characters, so that a running hash key can be computed from the
24		* previous key instead of complete recalculation each time.
25		*/
26	0	Z_FORCEINLINE static uint32_t update_hash_roll(uint32_t h, uint32_t val) {
27	0	UPDATE_HASH_ROLL(h, val);
28	0	return h;
29	0	} Unexecuted instantiation: compare256_sse2.c:update_hash_roll Unexecuted instantiation: compare256_avx2.c:update_hash_roll Unexecuted instantiation: compare256_avx512.c:update_hash_roll
30
31		/* ===========================================================================
32		* Insert string str in the dictionary using a pre-read value and set match_head
33		* to the previous head of the hash chain (the most recent string with same hash key).
34		* Return the previous length of the hash chain.
35		*/
36	0	Z_FORCEINLINE static uint32_t insert_knuth_val(deflate_state *const s, uint32_t str, uint32_t val) {
37	0	uint32_t h, head;
38	0
39	0	UPDATE_HASH_KNUTH(h, val);
40	0
41	0	head = s->head[h];
42	0	if (LIKELY(head != str)) {
43	0	s->prev[str & W_MASK(s)] = (Pos)head;
44	0	s->head[h] = (Pos)str;
45	0	}
46	0	return head;
47	0	} Unexecuted instantiation: compare256_sse2.c:insert_knuth_val Unexecuted instantiation: compare256_avx2.c:insert_knuth_val Unexecuted instantiation: compare256_avx512.c:insert_knuth_val
48
49		/* ===========================================================================
50		* Insert string str using a pre-read value, returning the previous head of the
51		* hash chain. The prev link is left untouched since deflate_quick only inspects
52		* the chain head and never walks the chain.
53		*/
54	0	Z_FORCEINLINE static uint32_t insert_knuth_val_head(deflate_state *const s, uint32_t str, uint32_t val) {
55	0	uint32_t h, head;
56	0
57	0	UPDATE_HASH_KNUTH(h, val);
58	0
59	0	head = s->head[h];
60	0	s->head[h] = (Pos)str;
61	0	return head;
62	0	} Unexecuted instantiation: compare256_sse2.c:insert_knuth_val_head Unexecuted instantiation: compare256_avx2.c:insert_knuth_val_head Unexecuted instantiation: compare256_avx512.c:insert_knuth_val_head
63
64		/* ===========================================================================
65		* Insert string str in the dictionary and set match_head to the previous head
66		* of the hash chain (the most recent string with same hash key). Return
67		* the previous length of the hash chain.
68		*/
69	0	Z_FORCEINLINE static uint32_t insert_knuth(deflate_state const s, unsigned char window, uint32_t str) {
70	0	uint8_t *strstart = window + str;
71	0	uint32_t val, h, head;
72	0
73	0	val = Z_U32_FROM_LE(zng_memread_4(strstart));
74	0	UPDATE_HASH_KNUTH(h, val);
75	0
76	0	head = s->head[h];
77	0	if (LIKELY(head != str)) {
78	0	s->prev[str & W_MASK(s)] = (Pos)head;
79	0	s->head[h] = (Pos)str;
80	0	}
81	0	return head;
82	0	} Unexecuted instantiation: compare256_sse2.c:insert_knuth Unexecuted instantiation: compare256_avx2.c:insert_knuth Unexecuted instantiation: compare256_avx512.c:insert_knuth
83
84		/* ===========================================================================
85		* Insert string str read from the window, returning the previous head of the
86		* hash chain. Like insert_knuth but leaves the prev link untouched for
87		* deflate_quick, which only inspects the chain head.
88		*/
89	0	Z_FORCEINLINE static uint32_t insert_knuth_head(deflate_state const s, unsigned char window, uint32_t str) {
90	0	uint8_t *strstart = window + str;
91	0	uint32_t val, h, head;
92	0
93	0	val = Z_U32_FROM_LE(zng_memread_4(strstart));
94	0	UPDATE_HASH_KNUTH(h, val);
95	0
96	0	head = s->head[h];
97	0	s->head[h] = (Pos)str;
98	0	return head;
99	0	} Unexecuted instantiation: compare256_sse2.c:insert_knuth_head Unexecuted instantiation: compare256_avx2.c:insert_knuth_head Unexecuted instantiation: compare256_avx512.c:insert_knuth_head
100
101	0	Z_FORCEINLINE static uint32_t insert_roll(deflate_state const s, unsigned char window, uint32_t str) {
102	0	uint8_t *strstart = window + str + (STD_MIN_MATCH-1);
103	0	uint32_t h, head;
104	0
105	0	h = s->ins_h;
106	0	UPDATE_HASH_ROLL(h, strstart[0]);
107	0	s->ins_h = h;
108	0
109	0	head = s->head[h];
110	0	if (LIKELY(head != str)) {
111	0	s->prev[str & W_MASK(s)] = (Pos)head;
112	0	s->head[h] = (Pos)str;
113	0	}
114	0	return head;
115	0	} Unexecuted instantiation: compare256_sse2.c:insert_roll Unexecuted instantiation: compare256_avx2.c:insert_roll Unexecuted instantiation: compare256_avx512.c:insert_roll
116
117		/* ===========================================================================
118		* Insert string str in the dictionary and set match_head to the previous head
119		* of the hash chain (the most recent string with same hash key). Return
120		* the previous length of the hash chain.
121		* IN assertion: all calls to insert_knuth_batch are made with consecutive
122		* input characters and the first STD_MIN_MATCH bytes of str are valid
123		* (except for the last STD_MIN_MATCH-1 bytes of the input file).
124		*/
125	0	Z_FORCEINLINE static void insert_knuth_batch_static(deflate_state const s, unsigned char window, uint32_t str, uint32_t count) {
126	0	uint8_t *strstart = window + str;
127	0	uint8_t *strend = strstart + count;
128	0
129	0	/* Local pointers to avoid indirection */
130	0	Pos *headp = s->head;
131	0	Pos *prevp = s->prev;
132	0	const unsigned int w_mask = W_MASK(s);
133	0
134	0	for (uint32_t idx = str; strstart < strend; idx++, strstart++) {
135	0	uint32_t val, h, head;
136	0
137	0	val = Z_U32_FROM_LE(zng_memread_4(strstart));
138	0	UPDATE_HASH_KNUTH(h, val);
139	0
140	0	head = headp[h];
141	0	if (LIKELY(head != idx)) {
142	0	prevp[idx & w_mask] = (Pos)head;
143	0	headp[h] = (Pos)idx;
144	0	}
145	0	}
146	0	} Unexecuted instantiation: compare256_sse2.c:insert_knuth_batch_static Unexecuted instantiation: compare256_avx2.c:insert_knuth_batch_static Unexecuted instantiation: compare256_avx512.c:insert_knuth_batch_static
147
148		/* ===========================================================================
149		* Insert count strings read from the window, leaving the prev links untouched.
150		* Used by fill_window during deflate_quick, which only inspects the chain head.
151		*/
152	0	Z_FORCEINLINE static void insert_knuth_batch_head_static(deflate_state const s, unsigned char window, uint32_t str, uint32_t count) {
153	0	uint8_t *strstart = window + str;
154	0	uint8_t *strend = strstart + count;
155	0	Pos *headp = s->head;
156	0
157	0	for (uint32_t idx = str; strstart < strend; idx++, strstart++) {
158	0	uint32_t val, h;
159	0
160	0	val = Z_U32_FROM_LE(zng_memread_4(strstart));
161	0	UPDATE_HASH_KNUTH(h, val);
162	0
163	0	headp[h] = (Pos)idx;
164	0	}
165	0	} Unexecuted instantiation: compare256_sse2.c:insert_knuth_batch_head_static Unexecuted instantiation: compare256_avx2.c:insert_knuth_batch_head_static Unexecuted instantiation: compare256_avx512.c:insert_knuth_batch_head_static
166
167	0	Z_FORCEINLINE static void insert_roll_batch_static(deflate_state const s, unsigned char window, uint32_t str, uint32_t count) {
168	0	uint8_t *strstart = window + str + (STD_MIN_MATCH-1);
169	0	uint8_t *strend = strstart + count;
170	0
171	0	/* Local pointers to avoid indirection */
172	0	Pos *headp = s->head;
173	0	Pos *prevp = s->prev;
174	0	uint32_t h = s->ins_h;
175	0	const unsigned int w_mask = W_MASK(s);
176	0
177	0	for (uint32_t idx = str; strstart < strend; idx++, strstart++) {
178	0	uint32_t head;
179	0
180	0	UPDATE_HASH_ROLL(h, strstart[0]);
181	0
182	0	head = headp[h];
183	0	if (LIKELY(head != idx)) {
184	0	prevp[idx & w_mask] = (Pos)head;
185	0	headp[h] = (Pos)idx;
186	0	}
187	0	}
188	0	s->ins_h = h;
189	0	} Unexecuted instantiation: compare256_sse2.c:insert_roll_batch_static Unexecuted instantiation: compare256_avx2.c:insert_roll_batch_static Unexecuted instantiation: compare256_avx512.c:insert_roll_batch_static
190
191		#endif

Coverage Report

Created: 2026-07-25 06:58