/src/zopfli/src/zopfli/cache.c
Line | Count | Source (jump to first uncovered line) |
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 | 11.3k | void ZopfliInitCache(size_t blocksize, ZopfliLongestMatchCache* lmc) { |
29 | 11.3k | size_t i; |
30 | 11.3k | lmc->length = (unsigned short*)malloc(sizeof(unsigned short) * blocksize); |
31 | 11.3k | lmc->dist = (unsigned short*)malloc(sizeof(unsigned short) * blocksize); |
32 | | /* Rather large amount of memory. */ |
33 | 11.3k | lmc->sublen = (unsigned char*)malloc(ZOPFLI_CACHE_LENGTH * 3 * blocksize); |
34 | 11.3k | if(lmc->sublen == NULL) { |
35 | 0 | fprintf(stderr, |
36 | 0 | "Error: Out of memory. Tried allocating %lu bytes of memory.\n", |
37 | 0 | (unsigned long)ZOPFLI_CACHE_LENGTH * 3 * blocksize); |
38 | 0 | exit (EXIT_FAILURE); |
39 | 0 | } |
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 | 85.0M | for (i = 0; i < blocksize; i++) lmc->length[i] = 1; |
44 | 85.0M | for (i = 0; i < blocksize; i++) lmc->dist[i] = 0; |
45 | 2.04G | for (i = 0; i < ZOPFLI_CACHE_LENGTH * blocksize * 3; i++) lmc->sublen[i] = 0; |
46 | 11.3k | } |
47 | | |
48 | 11.3k | void ZopfliCleanCache(ZopfliLongestMatchCache* lmc) { |
49 | 11.3k | free(lmc->length); |
50 | 11.3k | free(lmc->dist); |
51 | 11.3k | free(lmc->sublen); |
52 | 11.3k | } |
53 | | |
54 | | void ZopfliSublenToCache(const unsigned short* sublen, |
55 | | size_t pos, size_t length, |
56 | 51.0M | ZopfliLongestMatchCache* lmc) { |
57 | 51.0M | size_t i; |
58 | 51.0M | size_t j = 0; |
59 | 51.0M | unsigned bestlength = 0; |
60 | 51.0M | unsigned char* cache; |
61 | | |
62 | | #if ZOPFLI_CACHE_LENGTH == 0 |
63 | | return; |
64 | | #endif |
65 | | |
66 | 51.0M | cache = &lmc->sublen[ZOPFLI_CACHE_LENGTH * pos * 3]; |
67 | 51.0M | if (length < 3) return; |
68 | 1.33G | for (i = 3; i <= length; i++) { |
69 | 1.32G | if (i == length || sublen[i] != sublen[i + 1]) { |
70 | 11.3M | cache[j * 3] = i - 3; |
71 | 11.3M | cache[j * 3 + 1] = sublen[i] % 256; |
72 | 11.3M | cache[j * 3 + 2] = (sublen[i] >> 8) % 256; |
73 | 11.3M | bestlength = i; |
74 | 11.3M | j++; |
75 | 11.3M | if (j >= ZOPFLI_CACHE_LENGTH) break; |
76 | 11.3M | } |
77 | 1.32G | } |
78 | 7.23M | if (j < ZOPFLI_CACHE_LENGTH) { |
79 | 7.16M | assert(bestlength == length); |
80 | 7.16M | cache[(ZOPFLI_CACHE_LENGTH - 1) * 3] = bestlength - 3; |
81 | 7.16M | } else { |
82 | 73.6k | assert(bestlength <= length); |
83 | 73.6k | } |
84 | 0 | assert(bestlength == ZopfliMaxCachedSublen(lmc, pos, length)); |
85 | 7.23M | } |
86 | | |
87 | | void ZopfliCacheToSublen(const ZopfliLongestMatchCache* lmc, |
88 | | size_t pos, size_t length, |
89 | 362M | unsigned short* sublen) { |
90 | 362M | size_t i, j; |
91 | 362M | unsigned maxlength = ZopfliMaxCachedSublen(lmc, pos, length); |
92 | 362M | unsigned prevlength = 0; |
93 | 362M | unsigned char* cache; |
94 | | #if ZOPFLI_CACHE_LENGTH == 0 |
95 | | return; |
96 | | #endif |
97 | 362M | if (length < 3) return; |
98 | 48.4M | cache = &lmc->sublen[ZOPFLI_CACHE_LENGTH * pos * 3]; |
99 | 73.5M | for (j = 0; j < ZOPFLI_CACHE_LENGTH; j++) { |
100 | 73.5M | unsigned length = cache[j * 3] + 3; |
101 | 73.5M | unsigned dist = cache[j * 3 + 1] + 256 * cache[j * 3 + 2]; |
102 | 8.56G | for (i = prevlength; i <= length; i++) { |
103 | 8.48G | sublen[i] = dist; |
104 | 8.48G | } |
105 | 73.5M | if (length == maxlength) break; |
106 | 25.0M | prevlength = length + 1; |
107 | 25.0M | } |
108 | 48.4M | } |
109 | | |
110 | | /* |
111 | | Returns the length up to which could be stored in the cache. |
112 | | */ |
113 | | unsigned ZopfliMaxCachedSublen(const ZopfliLongestMatchCache* lmc, |
114 | 731M | size_t pos, size_t length) { |
115 | 731M | unsigned char* cache; |
116 | | #if ZOPFLI_CACHE_LENGTH == 0 |
117 | | return 0; |
118 | | #endif |
119 | 731M | cache = &lmc->sublen[ZOPFLI_CACHE_LENGTH * pos * 3]; |
120 | 731M | (void)length; |
121 | 731M | if (cache[1] == 0 && cache[2] == 0) return 0; /* No sublen cached. */ |
122 | 104M | return cache[(ZOPFLI_CACHE_LENGTH - 1) * 3] + 3; |
123 | 731M | } |
124 | | |
125 | | #endif /* ZOPFLI_LONGEST_MATCH_CACHE */ |