"Fossies" - the Fresh Open Source Software Archive

Member "pigz-2.6/zopfli/src/zopfli/cache.c" (6 Feb 2021, 3913 Bytes) of package /linux/privat/pigz-2.6.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 "cache.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 2.5_vs_2.6.

    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 "cache.h"
   21 
   22 #include <assert.h>
   23 #include <stdio.h>
   24 #include <stdlib.h>
   25 
   26 #ifdef ZOPFLI_LONGEST_MATCH_CACHE
   27 
   28 void ZopfliInitCache(size_t blocksize, ZopfliLongestMatchCache* lmc) {
   29   size_t i;
   30   lmc->length = (unsigned short*)malloc(sizeof(unsigned short) * blocksize);
   31   lmc->dist = (unsigned short*)malloc(sizeof(unsigned short) * blocksize);
   32   /* Rather large amount of memory. */
   33   lmc->sublen = (unsigned char*)malloc(ZOPFLI_CACHE_LENGTH * 3 * blocksize);
   34   if(lmc->sublen == NULL) {
   35     fprintf(stderr,
   36         "Error: Out of memory. Tried allocating %zu bytes of memory.\n",
   37         ZOPFLI_CACHE_LENGTH * 3 * blocksize);
   38     exit (EXIT_FAILURE);
   39   }
   40 
   41   /* length > 0 and dist 0 is invalid combination, which indicates on purpose
   42   that this cache value is not filled in yet. */
   43   for (i = 0; i < blocksize; i++) lmc->length[i] = 1;
   44   for (i = 0; i < blocksize; i++) lmc->dist[i] = 0;
   45   for (i = 0; i < ZOPFLI_CACHE_LENGTH * blocksize * 3; i++) lmc->sublen[i] = 0;
   46 }
   47 
   48 void ZopfliCleanCache(ZopfliLongestMatchCache* lmc) {
   49   free(lmc->length);
   50   free(lmc->dist);
   51   free(lmc->sublen);
   52 }
   53 
   54 void ZopfliSublenToCache(const unsigned short* sublen,
   55                          size_t pos, size_t length,
   56                          ZopfliLongestMatchCache* lmc) {
   57   size_t i;
   58   size_t j = 0;
   59   unsigned bestlength = 0;
   60   unsigned char* cache;
   61 
   62 #if ZOPFLI_CACHE_LENGTH == 0
   63   return;
   64 #endif
   65 
   66   cache = &lmc->sublen[ZOPFLI_CACHE_LENGTH * pos * 3];
   67   if (length < 3) return;
   68   for (i = 3; i <= length; i++) {
   69     if (i == length || sublen[i] != sublen[i + 1]) {
   70       cache[j * 3] = i - 3;
   71       cache[j * 3 + 1] = sublen[i] % 256;
   72       cache[j * 3 + 2] = (sublen[i] >> 8) % 256;
   73       bestlength = i;
   74       j++;
   75       if (j >= ZOPFLI_CACHE_LENGTH) break;
   76     }
   77   }
   78   if (j < ZOPFLI_CACHE_LENGTH) {
   79     assert(bestlength == length);
   80     cache[(ZOPFLI_CACHE_LENGTH - 1) * 3] = bestlength - 3;
   81   } else {
   82     assert(bestlength <= length);
   83   }
   84   assert(bestlength == ZopfliMaxCachedSublen(lmc, pos, length));
   85 }
   86 
   87 void ZopfliCacheToSublen(const ZopfliLongestMatchCache* lmc,
   88                          size_t pos, size_t length,
   89                          unsigned short* sublen) {
   90   size_t i, j;
   91   unsigned maxlength = ZopfliMaxCachedSublen(lmc, pos, length);
   92   unsigned prevlength = 0;
   93   unsigned char* cache;
   94 #if ZOPFLI_CACHE_LENGTH == 0
   95   return;
   96 #endif
   97   if (length < 3) return;
   98   cache = &lmc->sublen[ZOPFLI_CACHE_LENGTH * pos * 3];
   99   for (j = 0; j < ZOPFLI_CACHE_LENGTH; j++) {
  100     unsigned length = cache[j * 3] + 3;
  101     unsigned dist = cache[j * 3 + 1] + 256 * cache[j * 3 + 2];
  102     for (i = prevlength; i <= length; i++) {
  103       sublen[i] = dist;
  104     }
  105     if (length == maxlength) break;
  106     prevlength = length + 1;
  107   }
  108 }
  109 
  110 /*
  111 Returns the length up to which could be stored in the cache.
  112 */
  113 unsigned ZopfliMaxCachedSublen(const ZopfliLongestMatchCache* lmc,
  114                                size_t pos, size_t length) {
  115   unsigned char* cache;
  116 #if ZOPFLI_CACHE_LENGTH == 0
  117   return 0;
  118 #endif
  119   cache = &lmc->sublen[ZOPFLI_CACHE_LENGTH * pos * 3];
  120   (void)length;
  121   if (cache[1] == 0 && cache[2] == 0) return 0;  /* No sublen cached. */
  122   return cache[(ZOPFLI_CACHE_LENGTH - 1) * 3] + 3;
  123 }
  124 
  125 #endif  /* ZOPFLI_LONGEST_MATCH_CACHE */