"Fossies" - the Fresh Open Source Software Archive

Member "pigz-2.8/zopfli/src/zopfli/hash.c" (28 Dec 2017, 3958 Bytes) of package /linux/privat/pigz-2.8.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hash.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 2.4_vs_2.5.

    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 
   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 
   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 
   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 */
   96 static void UpdateHashValue(ZopfliHash* h, unsigned char c) {
   97   h->val = (((h->val) << HASH_SHIFT) ^ (c)) & HASH_MASK;
   98 }
   99 
  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 
  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 }