1/*
2Copyright 2011 Google Inc. All Rights Reserved.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8    http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15
16Author: lode.vandevenne@gmail.com (Lode Vandevenne)
17Author: 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
29void ZopfliInitHash(size_t window_size, ZopfliHash* h) {
30  size_t i;
31
32  h->val = 0;
33  h->head = (int*)malloc(sizeof(*h->head) * 65536);
34  h->prev = (unsigned short*)malloc(sizeof(*h->prev) * window_size);
35  h->hashval = (int*)malloc(sizeof(*h->hashval) * window_size);
36  for (i = 0; i < 65536; i++) {
37    h->head[i] = -1;  /* -1 indicates no head so far. */
38  }
39  for (i = 0; i < window_size; i++) {
40    h->prev[i] = i;  /* If prev[j] == j, then prev[j] is uninitialized. */
41    h->hashval[i] = -1;
42  }
43
44#ifdef ZOPFLI_HASH_SAME
45  h->same = (unsigned short*)malloc(sizeof(*h->same) * window_size);
46  for (i = 0; i < window_size; i++) {
47    h->same[i] = 0;
48  }
49#endif
50
51#ifdef ZOPFLI_HASH_SAME_HASH
52  h->val2 = 0;
53  h->head2 = (int*)malloc(sizeof(*h->head2) * 65536);
54  h->prev2 = (unsigned short*)malloc(sizeof(*h->prev2) * window_size);
55  h->hashval2 = (int*)malloc(sizeof(*h->hashval2) * window_size);
56  for (i = 0; i < 65536; i++) {
57    h->head2[i] = -1;
58  }
59  for (i = 0; i < window_size; i++) {
60    h->prev2[i] = i;
61    h->hashval2[i] = -1;
62  }
63#endif
64}
65
66void ZopfliCleanHash(ZopfliHash* h) {
67  free(h->head);
68  free(h->prev);
69  free(h->hashval);
70
71#ifdef ZOPFLI_HASH_SAME_HASH
72  free(h->head2);
73  free(h->prev2);
74  free(h->hashval2);
75#endif
76
77#ifdef ZOPFLI_HASH_SAME
78  free(h->same);
79#endif
80}
81
82/*
83Update the sliding hash value with the given byte. All calls to this function
84must be made on consecutive input characters. Since the hash value exists out
85of multiple input bytes, a few warmups with this function are needed initially.
86*/
87static void UpdateHashValue(ZopfliHash* h, unsigned char c) {
88  h->val = (((h->val) << HASH_SHIFT) ^ (c)) & HASH_MASK;
89}
90
91void ZopfliUpdateHash(const unsigned char* array, size_t pos, size_t end,
92                ZopfliHash* h) {
93  unsigned short hpos = pos & ZOPFLI_WINDOW_MASK;
94#ifdef ZOPFLI_HASH_SAME
95  size_t amount = 0;
96#endif
97
98  UpdateHashValue(h, pos + ZOPFLI_MIN_MATCH <= end ?
99      array[pos + ZOPFLI_MIN_MATCH - 1] : 0);
100  h->hashval[hpos] = h->val;
101  if (h->head[h->val] != -1 && h->hashval[h->head[h->val]] == h->val) {
102    h->prev[hpos] = h->head[h->val];
103  }
104  else h->prev[hpos] = hpos;
105  h->head[h->val] = hpos;
106
107#ifdef ZOPFLI_HASH_SAME
108  /* Update "same". */
109  if (h->same[(pos - 1) & ZOPFLI_WINDOW_MASK] > 1) {
110    amount = h->same[(pos - 1) & ZOPFLI_WINDOW_MASK] - 1;
111  }
112  while (pos + amount + 1 < end &&
113      array[pos] == array[pos + amount + 1] && amount < (unsigned short)(-1)) {
114    amount++;
115  }
116  h->same[hpos] = amount;
117#endif
118
119#ifdef ZOPFLI_HASH_SAME_HASH
120  h->val2 = ((h->same[hpos] - ZOPFLI_MIN_MATCH) & 255) ^ h->val;
121  h->hashval2[hpos] = h->val2;
122  if (h->head2[h->val2] != -1 && h->hashval2[h->head2[h->val2]] == h->val2) {
123    h->prev2[hpos] = h->head2[h->val2];
124  }
125  else h->prev2[hpos] = hpos;
126  h->head2[h->val2] = hpos;
127#endif
128}
129
130void ZopfliWarmupHash(const unsigned char* array, size_t pos, size_t end,
131                ZopfliHash* h) {
132  (void)end;
133  UpdateHashValue(h, array[pos + 0]);
134  UpdateHashValue(h, array[pos + 1]);
135}
136