aboutsummaryrefslogtreecommitdiff
path: root/src/zopfli/blocksplitter.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/zopfli/blocksplitter.c')
-rw-r--r--src/zopfli/blocksplitter.c78
1 files changed, 34 insertions, 44 deletions
diff --git a/src/zopfli/blocksplitter.c b/src/zopfli/blocksplitter.c
index 68f5ff3..161783d 100644
--- a/src/zopfli/blocksplitter.c
+++ b/src/zopfli/blocksplitter.c
@@ -24,7 +24,6 @@ Author: jyrki.alakuijala@gmail.com (Jyrki Alakuijala)
#include <stdlib.h>
#include "deflate.h"
-#include "lz77.h"
#include "squeeze.h"
#include "tree.h"
#include "util.h"
@@ -39,9 +38,10 @@ typedef double FindMinimumFun(size_t i, void* context);
/*
Finds minimum of function f(i) where is is of type size_t, f(i) is of type
double, i is in range start-end (excluding end).
+Outputs the minimum value in *smallest and returns the index of this value.
*/
static size_t FindMinimum(FindMinimumFun f, void* context,
- size_t start, size_t end) {
+ size_t start, size_t end, double* smallest) {
if (end - start < 1024) {
double best = ZOPFLI_LARGE_FLOAT;
size_t result = start;
@@ -53,6 +53,7 @@ static size_t FindMinimum(FindMinimumFun f, void* context,
result = i;
}
}
+ *smallest = best;
return result;
} else {
/* Try to find minimum faster by recursively checking multiple points. */
@@ -88,6 +89,7 @@ static size_t FindMinimum(FindMinimumFun f, void* context,
pos = p[besti];
lastbest = best;
}
+ *smallest = lastbest;
return pos;
#undef NUM
}
@@ -103,16 +105,13 @@ dists: ll77 distances
lstart: start of block
lend: end of block (not inclusive)
*/
-static double EstimateCost(const unsigned short* litlens,
- const unsigned short* dists,
+static double EstimateCost(const ZopfliLZ77Store* lz77,
size_t lstart, size_t lend) {
- return ZopfliCalculateBlockSize(litlens, dists, lstart, lend, 2);
+ return ZopfliCalculateBlockSizeAutoType(lz77, lstart, lend);
}
typedef struct SplitCostContext {
- const unsigned short* litlens;
- const unsigned short* dists;
- size_t llsize;
+ const ZopfliLZ77Store* lz77;
size_t start;
size_t end;
} SplitCostContext;
@@ -125,8 +124,7 @@ type: FindMinimumFun
*/
static double SplitCost(size_t i, void* context) {
SplitCostContext* c = (SplitCostContext*)context;
- return EstimateCost(c->litlens, c->dists, c->start, i) +
- EstimateCost(c->litlens, c->dists, i, c->end);
+ return EstimateCost(c->lz77, c->start, i) + EstimateCost(c->lz77, i, c->end);
}
static void AddSorted(size_t value, size_t** out, size_t* outsize) {
@@ -147,9 +145,8 @@ static void AddSorted(size_t value, size_t** out, size_t* outsize) {
/*
Prints the block split points as decimal and hex values in the terminal.
*/
-static void PrintBlockSplitPoints(const unsigned short* litlens,
- const unsigned short* dists,
- size_t llsize, const size_t* lz77splitpoints,
+static void PrintBlockSplitPoints(const ZopfliLZ77Store* lz77,
+ const size_t* lz77splitpoints,
size_t nlz77points) {
size_t* splitpoints = 0;
size_t npoints = 0;
@@ -158,8 +155,8 @@ static void PrintBlockSplitPoints(const unsigned short* litlens,
index values. */
size_t pos = 0;
if (nlz77points > 0) {
- for (i = 0; i < llsize; i++) {
- size_t length = dists[i] == 0 ? 1 : litlens[i];
+ for (i = 0; i < lz77->size; i++) {
+ size_t length = lz77->dists[i] == 0 ? 1 : lz77->litlens[i];
if (lz77splitpoints[npoints] == i) {
ZOPFLI_APPEND_DATA(pos, &splitpoints, &npoints);
if (npoints == nlz77points) break;
@@ -186,7 +183,7 @@ static void PrintBlockSplitPoints(const unsigned short* litlens,
Finds next block to try to split, the largest of the available ones.
The largest is chosen to make sure that if only a limited amount of blocks is
requested, their sizes are spread evenly.
-llsize: the size of the LL77 data, which is the size of the done array here.
+lz77size: the size of the LL77 data, which is the size of the done array here.
done: array indicating which blocks starting at that position are no longer
splittable (splitting them increases rather than decreases cost).
splitpoints: the splitpoints found so far.
@@ -196,7 +193,7 @@ lend: output variable, giving end of block.
returns 1 if a block was found, 0 if no block found (all are done).
*/
static int FindLargestSplittableBlock(
- size_t llsize, const unsigned char* done,
+ size_t lz77size, const unsigned char* done,
const size_t* splitpoints, size_t npoints,
size_t* lstart, size_t* lend) {
size_t longest = 0;
@@ -204,7 +201,7 @@ static int FindLargestSplittableBlock(
size_t i;
for (i = 0; i <= npoints; i++) {
size_t start = i == 0 ? 0 : splitpoints[i - 1];
- size_t end = i == npoints ? llsize - 1 : splitpoints[i];
+ size_t end = i == npoints ? lz77size - 1 : splitpoints[i];
if (!done[start] && end - start > longest) {
*lstart = start;
*lend = end;
@@ -216,9 +213,7 @@ static int FindLargestSplittableBlock(
}
void ZopfliBlockSplitLZ77(const ZopfliOptions* options,
- const unsigned short* litlens,
- const unsigned short* dists,
- size_t llsize, size_t maxblocks,
+ const ZopfliLZ77Store* lz77, size_t maxblocks,
size_t** splitpoints, size_t* npoints) {
size_t lstart, lend;
size_t i;
@@ -227,14 +222,14 @@ void ZopfliBlockSplitLZ77(const ZopfliOptions* options,
unsigned char* done;
double splitcost, origcost;
- if (llsize < 10) return; /* This code fails on tiny files. */
+ if (lz77->size < 10) return; /* This code fails on tiny files. */
- done = (unsigned char*)malloc(llsize);
+ done = (unsigned char*)malloc(lz77->size);
if (!done) exit(-1); /* Allocation failed. */
- for (i = 0; i < llsize; i++) done[i] = 0;
+ for (i = 0; i < lz77->size; i++) done[i] = 0;
lstart = 0;
- lend = llsize;
+ lend = lz77->size;
for (;;) {
SplitCostContext c;
@@ -242,20 +237,16 @@ void ZopfliBlockSplitLZ77(const ZopfliOptions* options,
break;
}
- c.litlens = litlens;
- c.dists = dists;
- c.llsize = llsize;
+ c.lz77 = lz77;
c.start = lstart;
c.end = lend;
assert(lstart < lend);
- llpos = FindMinimum(SplitCost, &c, lstart + 1, lend);
+ llpos = FindMinimum(SplitCost, &c, lstart + 1, lend, &splitcost);
assert(llpos > lstart);
assert(llpos < lend);
- splitcost = EstimateCost(litlens, dists, lstart, llpos) +
- EstimateCost(litlens, dists, llpos, lend);
- origcost = EstimateCost(litlens, dists, lstart, lend);
+ origcost = EstimateCost(lz77, lstart, lend);
if (splitcost > origcost || llpos == lstart + 1 || llpos == lend) {
done[lstart] = 1;
@@ -265,7 +256,7 @@ void ZopfliBlockSplitLZ77(const ZopfliOptions* options,
}
if (!FindLargestSplittableBlock(
- llsize, done, *splitpoints, *npoints, &lstart, &lend)) {
+ lz77->size, done, *splitpoints, *npoints, &lstart, &lend)) {
break; /* No further split will probably reduce compression. */
}
@@ -275,7 +266,7 @@ void ZopfliBlockSplitLZ77(const ZopfliOptions* options,
}
if (options->verbose) {
- PrintBlockSplitPoints(litlens, dists, llsize, *splitpoints, *npoints);
+ PrintBlockSplitPoints(lz77, *splitpoints, *npoints);
}
free(done);
@@ -290,25 +281,22 @@ void ZopfliBlockSplit(const ZopfliOptions* options,
size_t* lz77splitpoints = 0;
size_t nlz77points = 0;
ZopfliLZ77Store store;
+ ZopfliHash hash;
+ ZopfliHash* h = &hash;
- ZopfliInitLZ77Store(&store);
-
- s.options = options;
- s.blockstart = instart;
- s.blockend = inend;
-#ifdef ZOPFLI_LONGEST_MATCH_CACHE
- s.lmc = 0;
-#endif
+ ZopfliInitLZ77Store(in, &store);
+ ZopfliInitBlockState(options, instart, inend, 0, &s);
+ ZopfliAllocHash(ZOPFLI_WINDOW_SIZE, h);
*npoints = 0;
*splitpoints = 0;
/* Unintuitively, Using a simple LZ77 method here instead of ZopfliLZ77Optimal
results in better blocks. */
- ZopfliLZ77Greedy(&s, in, instart, inend, &store);
+ ZopfliLZ77Greedy(&s, in, instart, inend, &store, h);
ZopfliBlockSplitLZ77(options,
- store.litlens, store.dists, store.size, maxblocks,
+ &store, maxblocks,
&lz77splitpoints, &nlz77points);
/* Convert LZ77 positions to positions in the uncompressed input. */
@@ -326,7 +314,9 @@ void ZopfliBlockSplit(const ZopfliOptions* options,
assert(*npoints == nlz77points);
free(lz77splitpoints);
+ ZopfliCleanBlockState(&s);
ZopfliCleanLZ77Store(&store);
+ ZopfliCleanHash(h);
}
void ZopfliBlockSplitSimple(const unsigned char* in,
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-01 22:01:10 +0000