1b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 2b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneCopyright 2011 Google Inc. All Rights Reserved. 3b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 4b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneLicensed under the Apache License, Version 2.0 (the "License"); 5b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneyou may not use this file except in compliance with the License. 6b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneYou may obtain a copy of the License at 7b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 8b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne http://www.apache.org/licenses/LICENSE-2.0 9b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 10b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneUnless required by applicable law or agreed to in writing, software 11b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennedistributed under the License is distributed on an "AS IS" BASIS, 12b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneWITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneSee the License for the specific language governing permissions and 14b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennelimitations under the License. 15b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 16b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneAuthor: lode.vandevenne@gmail.com (Lode Vandevenne) 17b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneAuthor: jyrki.alakuijala@gmail.com (Jyrki Alakuijala) 18b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 19b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 20b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include "hash.h" 21b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 22b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <assert.h> 23b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <stdio.h> 24b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#include <stdlib.h> 25b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 26b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#define HASH_SHIFT 5 27b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#define HASH_MASK 32767 28b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 29981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliInitHash(size_t window_size, ZopfliHash* h) { 30b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t i; 31b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 32b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->val = 0; 33b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->head = (int*)malloc(sizeof(*h->head) * 65536); 34b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->prev = (unsigned short*)malloc(sizeof(*h->prev) * window_size); 35b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->hashval = (int*)malloc(sizeof(*h->hashval) * window_size); 36b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < 65536; i++) { 37b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->head[i] = -1; /* -1 indicates no head so far. */ 38b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 39b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < window_size; i++) { 40b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->prev[i] = i; /* If prev[j] == j, then prev[j] is uninitialized. */ 41b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->hashval[i] = -1; 42b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 43b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 44981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME 45b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->same = (unsigned short*)malloc(sizeof(*h->same) * window_size); 46b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < window_size; i++) { 47b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->same[i] = 0; 48b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 49b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 50b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 51981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME_HASH 52b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->val2 = 0; 53b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->head2 = (int*)malloc(sizeof(*h->head2) * 65536); 54b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->prev2 = (unsigned short*)malloc(sizeof(*h->prev2) * window_size); 55b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->hashval2 = (int*)malloc(sizeof(*h->hashval2) * window_size); 56b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < 65536; i++) { 57b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->head2[i] = -1; 58b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 59b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne for (i = 0; i < window_size; i++) { 60b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->prev2[i] = i; 61b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->hashval2[i] = -1; 62b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 63b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 64b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 65b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 66981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliCleanHash(ZopfliHash* h) { 67b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(h->head); 68b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(h->prev); 69b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(h->hashval); 70b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 71981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME_HASH 72b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(h->head2); 73b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(h->prev2); 74b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(h->hashval2); 75b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 76b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 77981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME 78b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne free(h->same); 79b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 80b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 81b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 82b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne/* 83b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode VandevenneUpdate the sliding hash value with the given byte. All calls to this function 84b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevennemust be made on consecutive input characters. Since the hash value exists out 85b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenneof multiple input bytes, a few warmups with this function are needed initially. 86b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne*/ 87981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennestatic void UpdateHashValue(ZopfliHash* h, unsigned char c) { 88b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->val = (((h->val) << HASH_SHIFT) ^ (c)) & HASH_MASK; 89b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 90b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 91981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliUpdateHash(const unsigned char* array, size_t pos, size_t end, 92981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliHash* h) { 93981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne unsigned short hpos = pos & ZOPFLI_WINDOW_MASK; 94981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME 95b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne size_t amount = 0; 96b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 97b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 98981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne UpdateHashValue(h, pos + ZOPFLI_MIN_MATCH <= end ? 99981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne array[pos + ZOPFLI_MIN_MATCH - 1] : 0); 100b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->hashval[hpos] = h->val; 101b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (h->head[h->val] != -1 && h->hashval[h->head[h->val]] == h->val) { 102b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->prev[hpos] = h->head[h->val]; 103b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 104b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne else h->prev[hpos] = hpos; 105b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->head[h->val] = hpos; 106b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 107981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME 108b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne /* Update "same". */ 109981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne if (h->same[(pos - 1) & ZOPFLI_WINDOW_MASK] > 1) { 110981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne amount = h->same[(pos - 1) & ZOPFLI_WINDOW_MASK] - 1; 111b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 112b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne while (pos + amount + 1 < end && 113b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne array[pos] == array[pos + amount + 1] && amount < (unsigned short)(-1)) { 114b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne amount++; 115b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 116b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->same[hpos] = amount; 117b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 118b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 119981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne#ifdef ZOPFLI_HASH_SAME_HASH 120981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne h->val2 = ((h->same[hpos] - ZOPFLI_MIN_MATCH) & 255) ^ h->val; 121b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->hashval2[hpos] = h->val2; 122b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne if (h->head2[h->val2] != -1 && h->hashval2[h->head2[h->val2]] == h->val2) { 123b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->prev2[hpos] = h->head2[h->val2]; 124b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne } 125b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne else h->prev2[hpos] = hpos; 126b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne h->head2[h->val2] = hpos; 127b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne#endif 128b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 129b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne 130981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevennevoid ZopfliWarmupHash(const unsigned char* array, size_t pos, size_t end, 131981df0fe897c94382b9b963eb72bc36cbc2e729cLode Vandevenne ZopfliHash* h) { 132b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne (void)end; 133b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne UpdateHashValue(h, array[pos + 0]); 134b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne UpdateHashValue(h, array[pos + 1]); 135b50b7ef8f8150616d3e9a227ce2d722a8355b1dLode Vandevenne} 136