1 /*
2 Copyright 2011 Google Inc. All Rights Reserved.
3 
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7 
8     http://www.apache.org/licenses/LICENSE-2.0
9 
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 
16 Author: lode.vandevenne@gmail.com (Lode Vandevenne)
17 Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala)
18 */
19 
20 /*
21 The hash for ZopfliFindLongestMatch of lz77.c.
22 */
23 
24 #ifndef ZOPFLI_HASH_H_
25 #define ZOPFLI_HASH_H_
26 
27 #include "util.h"
28 
29 typedef struct ZopfliHash {
30   int* head;  /* Hash value to index of its most recent occurrence. */
31   unsigned short* prev;  /* Index to index of prev. occurrence of same hash. */
32   int* hashval;  /* Index to hash value at this index. */
33   int val;  /* Current hash value. */
34 
35 #ifdef ZOPFLI_HASH_SAME_HASH
36   /* Fields with similar purpose as the above hash, but for the second hash with
37   a value that is calculated differently.  */
38   int* head2;  /* Hash value to index of its most recent occurrence. */
39   unsigned short* prev2;  /* Index to index of prev. occurrence of same hash. */
40   int* hashval2;  /* Index to hash value at this index. */
41   int val2;  /* Current hash value. */
42 #endif
43 
44 #ifdef ZOPFLI_HASH_SAME
45   unsigned short* same;  /* Amount of repetitions of same byte after this .*/
46 #endif
47 } ZopfliHash;
48 
49 /* Allocates ZopfliHash memory. */
50 void ZopfliAllocHash(size_t window_size, ZopfliHash* h);
51 
52 /* Resets all fields of ZopfliHash. */
53 void ZopfliResetHash(size_t window_size, ZopfliHash* h);
54 
55 /* Frees ZopfliHash memory. */
56 void ZopfliCleanHash(ZopfliHash* h);
57 
58 /*
59 Updates the hash values based on the current position in the array. All calls
60 to this must be made for consecutive bytes.
61 */
62 void ZopfliUpdateHash(const unsigned char* array, size_t pos, size_t end,
63                       ZopfliHash* h);
64 
65 /*
66 Prepopulates hash:
67 Fills in the initial values in the hash, before ZopfliUpdateHash can be used
68 correctly.
69 */
70 void ZopfliWarmupHash(const unsigned char* array, size_t pos, size_t end,
71                       ZopfliHash* h);
72 
73 #endif  /* ZOPFLI_HASH_H_ */
74