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 #include "hash.h"
21
22 #include <assert.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25
26 #define HASH_SHIFT 5
27 #define HASH_MASK 32767
28
ZopfliAllocHash(size_t window_size,ZopfliHash * h)29 void ZopfliAllocHash(size_t window_size, ZopfliHash* h) {
30 h->head = (int*)malloc(sizeof(*h->head) * 65536);
31 h->prev = (unsigned short*)malloc(sizeof(*h->prev) * window_size);
32 h->hashval = (int*)malloc(sizeof(*h->hashval) * window_size);
33
34 #ifdef ZOPFLI_HASH_SAME
35 h->same = (unsigned short*)malloc(sizeof(*h->same) * window_size);
36 #endif
37
38 #ifdef ZOPFLI_HASH_SAME_HASH
39 h->head2 = (int*)malloc(sizeof(*h->head2) * 65536);
40 h->prev2 = (unsigned short*)malloc(sizeof(*h->prev2) * window_size);
41 h->hashval2 = (int*)malloc(sizeof(*h->hashval2) * window_size);
42 #endif
43 }
44
ZopfliResetHash(size_t window_size,ZopfliHash * h)45 void ZopfliResetHash(size_t window_size, ZopfliHash* h) {
46 size_t i;
47
48 h->val = 0;
49 for (i = 0; i < 65536; i++) {
50 h->head[i] = -1; /* -1 indicates no head so far. */
51 }
52 for (i = 0; i < window_size; i++) {
53 h->prev[i] = i; /* If prev[j] == j, then prev[j] is uninitialized. */
54 h->hashval[i] = -1;
55 }
56
57 #ifdef ZOPFLI_HASH_SAME
58 for (i = 0; i < window_size; i++) {
59 h->same[i] = 0;
60 }
61 #endif
62
63 #ifdef ZOPFLI_HASH_SAME_HASH
64 h->val2 = 0;
65 for (i = 0; i < 65536; i++) {
66 h->head2[i] = -1;
67 }
68 for (i = 0; i < window_size; i++) {
69 h->prev2[i] = i;
70 h->hashval2[i] = -1;
71 }
72 #endif
73 }
74
ZopfliCleanHash(ZopfliHash * h)75 void ZopfliCleanHash(ZopfliHash* h) {
76 free(h->head);
77 free(h->prev);
78 free(h->hashval);
79
80 #ifdef ZOPFLI_HASH_SAME_HASH
81 free(h->head2);
82 free(h->prev2);
83 free(h->hashval2);
84 #endif
85
86 #ifdef ZOPFLI_HASH_SAME
87 free(h->same);
88 #endif
89 }
90
91 /*
92 Update the sliding hash value with the given byte. All calls to this function
93 must be made on consecutive input characters. Since the hash value exists out
94 of multiple input bytes, a few warmups with this function are needed initially.
95 */
UpdateHashValue(ZopfliHash * h,unsigned char c)96 static void UpdateHashValue(ZopfliHash* h, unsigned char c) {
97 h->val = (((h->val) << HASH_SHIFT) ^ (c)) & HASH_MASK;
98 }
99
ZopfliUpdateHash(const unsigned char * array,size_t pos,size_t end,ZopfliHash * h)100 void ZopfliUpdateHash(const unsigned char* array, size_t pos, size_t end,
101 ZopfliHash* h) {
102 unsigned short hpos = pos & ZOPFLI_WINDOW_MASK;
103 #ifdef ZOPFLI_HASH_SAME
104 size_t amount = 0;
105 #endif
106
107 UpdateHashValue(h, pos + ZOPFLI_MIN_MATCH <= end ?
108 array[pos + ZOPFLI_MIN_MATCH - 1] : 0);
109 h->hashval[hpos] = h->val;
110 if (h->head[h->val] != -1 && h->hashval[h->head[h->val]] == h->val) {
111 h->prev[hpos] = h->head[h->val];
112 }
113 else h->prev[hpos] = hpos;
114 h->head[h->val] = hpos;
115
116 #ifdef ZOPFLI_HASH_SAME
117 /* Update "same". */
118 if (h->same[(pos - 1) & ZOPFLI_WINDOW_MASK] > 1) {
119 amount = h->same[(pos - 1) & ZOPFLI_WINDOW_MASK] - 1;
120 }
121 while (pos + amount + 1 < end &&
122 array[pos] == array[pos + amount + 1] && amount < (unsigned short)(-1)) {
123 amount++;
124 }
125 h->same[hpos] = amount;
126 #endif
127
128 #ifdef ZOPFLI_HASH_SAME_HASH
129 h->val2 = ((h->same[hpos] - ZOPFLI_MIN_MATCH) & 255) ^ h->val;
130 h->hashval2[hpos] = h->val2;
131 if (h->head2[h->val2] != -1 && h->hashval2[h->head2[h->val2]] == h->val2) {
132 h->prev2[hpos] = h->head2[h->val2];
133 }
134 else h->prev2[hpos] = hpos;
135 h->head2[h->val2] = hpos;
136 #endif
137 }
138
ZopfliWarmupHash(const unsigned char * array,size_t pos,size_t end,ZopfliHash * h)139 void ZopfliWarmupHash(const unsigned char* array, size_t pos, size_t end,
140 ZopfliHash* h) {
141 UpdateHashValue(h, array[pos + 0]);
142 if (pos + 1 < end) UpdateHashValue(h, array[pos + 1]);
143 }
144