1 /* slide_hash.c -- slide hash table C implementation
2  *
3  * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
4  * For conditions of distribution and use, see copyright notice in zlib.h
5  */
6 
7 #include "zbuild.h"
8 #include "deflate.h"
9 
10 /* ===========================================================================
11  * Slide the hash table when sliding the window down (could be avoided with 32
12  * bit values at the expense of memory usage). We slide even when level == 0 to
13  * keep the hash table consistent if we switch back to level > 0 later.
14  */
slide_hash_c_chain(Pos * table,uint32_t entries,uint16_t wsize)15 static inline void slide_hash_c_chain(Pos *table, uint32_t entries, uint16_t wsize) {
16 #ifdef NOT_TWEAK_COMPILER
17     table += entries;
18     do {
19         unsigned m;
20         m = *--table;
21         *table = (Pos)(m >= wsize ? m-wsize : 0);
22         /* If entries is not on any hash chain, prev[entries] is garbage but
23          * its value will never be used.
24          */
25     } while (--entries);
26 #else
27     {
28     /* As of I make this change, gcc (4.8.*) isn't able to vectorize
29      * this hot loop using saturated-subtraction on x86-64 architecture.
30      * To avoid this defect, we can change the loop such that
31      *    o. the pointer advance forward, and
32      *    o. demote the variable 'm' to be local to the loop, and
33      *       choose type "Pos" (instead of 'unsigned int') for the
34      *       variable to avoid unnecessary zero-extension.
35      */
36         unsigned int i;
37         Pos *q = table;
38         for (i = 0; i < entries; i++) {
39             Pos m = *q;
40             Pos t = (Pos)wsize;
41             *q++ = (Pos)(m >= t ? m-t: 0);
42         }
43     }
44 #endif /* NOT_TWEAK_COMPILER */
45 }
46 
slide_hash_c(deflate_state * s)47 Z_INTERNAL void slide_hash_c(deflate_state *s) {
48     unsigned int wsize = s->w_size;
49 
50     slide_hash_c_chain(s->head, HASH_SIZE, wsize);
51     slide_hash_c_chain(s->prev, wsize, wsize);
52 }
53