[Zlib-devel] [PATCH 13/13] deflate: add new deflate_medium strategy
Jim Kukunas
james.t.kukunas at linux.intel.com
Mon Nov 25 17:21:49 EST 2013
From: Arjan van de Ven <arjan at linux.intel.com>
As the name suggests, the deflate_medium deflate strategy is designed
to provide an intermediate strategy between deflate_fast and deflate_slow.
After finding two adjacent matches, deflate_medium scans left from
the second match in order to determine whether a better match can be
formed.
---
configure | 8 +-
deflate.c | 13 ++
deflate_medium.c | 364 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 381 insertions(+), 4 deletions(-)
create mode 100644 deflate_medium.c
diff --git a/configure b/configure
index e9f2886..a90d0b8 100755
--- a/configure
+++ b/configure
@@ -818,8 +818,8 @@ case "${ARCH}" in
CRC_FOLDING_lo=""
fi
- CFLAGS="${CFLAGS} -DUSE_QUICK"
- SFLAGS="${SFLAGS} -DUSE_QUICK"
+ CFLAGS="${CFLAGS} -DUSE_QUICK -DUSE_MEDIUM"
+ SFLAGS="${SFLAGS} -DUSE_QUICK -DUSE_MEDIUM"
;;
i386 | i486 | i586 | i686)
OBJC="${OBJC} x86.o"
@@ -858,8 +858,8 @@ case "${ARCH}" in
CRC_FOLDING_lo=""
fi
- CFLAGS="${CFLAGS} -DUSE_QUICK"
- SFLAGS="${SFLAGS} -DUSE_QUICK"
+ CFLAGS="${CFLAGS} -DUSE_QUICK -DUSE_MEDIUM"
+ SFLAGS="${SFLAGS} -DUSE_QUICK -DUSE_MEDIUM"
;;
esac
diff --git a/deflate.c b/deflate.c
index 1a099d3..c0925ef 100644
--- a/deflate.c
+++ b/deflate.c
@@ -82,6 +82,8 @@ local void fill_window OF((deflate_state *s));
local block_state deflate_stored OF((deflate_state *s, int flush));
local block_state deflate_fast OF((deflate_state *s, int flush));
local block_state deflate_quick OF((deflate_state *s, int flush));
+local block_state deflate_medium OF((deflate_state *s, int flush));
+
#ifndef FASTEST
local block_state deflate_slow OF((deflate_state *s, int flush));
#endif
@@ -147,9 +149,16 @@ local const config configuration_table[10] = {
/* 3 */ {4, 6, 32, 32, deflate_fast},
#endif
+#ifdef USE_MEDIUM
+/* 4 */ {4, 4, 16, 16, deflate_medium}, /* lazy matches */
+/* 5 */ {8, 16, 32, 32, deflate_medium},
+/* 6 */ {8, 16, 128, 128, deflate_medium},
+#else
/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
/* 5 */ {8, 16, 32, 32, deflate_slow},
/* 6 */ {8, 16, 128, 128, deflate_slow},
+#endif
+
/* 7 */ {8, 32, 128, 256, deflate_slow},
/* 8 */ {32, 128, 258, 1024, deflate_slow},
/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
@@ -1617,6 +1626,10 @@ local block_state deflate_fast(s, flush)
#include "deflate_quick.c"
#endif
+#ifdef USE_MEDIUM
+#include "deflate_medium.c"
+#endif
+
#ifndef FASTEST
/* ===========================================================================
* Same as above, but achieves better compression. We use a lazy
diff --git a/deflate_medium.c b/deflate_medium.c
new file mode 100644
index 0000000..5892843
--- /dev/null
+++ b/deflate_medium.c
@@ -0,0 +1,364 @@
+/*
+ * The deflate_medium deflate strategy
+ *
+ * Copyright (C) 2013 Intel Corporation. All rights reserved.
+ * Authors:
+ * Arjan van de Ven <arjan at linux.intel.com>
+ *
+ * For conditions of distribution and use, see copyright notice in zlib.h
+ */
+#undef PRINT
+#undef PRINT_EMIT
+
+
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+struct match {
+ uInt match_start;
+ uInt match_length;
+ uInt strstart;
+ uInt orgstart;
+};
+
+
+#define MAX_DIST2 ((1 << MAX_WBITS) - MIN_LOOKAHEAD)
+static int tr_tally_dist(deflate_state *s, int distance, int length)
+{
+ return _tr_tally(s, distance, length);
+}
+
+static int tr_tally_lit(deflate_state *s, int c)
+{
+ return _tr_tally(s, 0, c);
+}
+
+static void insert_check(int i)
+{
+#ifdef PRINT
+ static int prev = - 1;
+
+ if (prev + 1 != i)
+ printf("INSERT BUMP BY %i\n", i - prev - 1);
+ prev = i;
+#endif
+}
+
+
+static int emit_match(deflate_state *s, struct match match, IPos hash_head)
+{
+ int flush = 0;
+
+#ifdef PRINT_EMIT
+ printf("Emitting match for pos %i, length %i ", match.strstart, match.match_length);
+ if (match.match_length > 1)
+ printf("from %i", match.match_start);
+ printf("\n");
+#endif
+
+ /* matches that are not long enough we need to emit as litterals */
+ if (match.match_length < MIN_MATCH) {
+ while (match.match_length) {
+ flush += tr_tally_lit (s, s->window[match.strstart]);
+ s->lookahead--;
+ match.strstart++;
+ match.match_length--;
+ }
+ return flush;
+ }
+
+
+
+ check_match(s, match.strstart, match.match_start, match.match_length);
+
+ flush += tr_tally_dist(s, match.strstart - match.match_start,
+ match.match_length - MIN_MATCH);
+
+ s->lookahead -= match.match_length;
+
+ return flush;
+}
+
+static void insert_match(deflate_state *s, struct match match)
+{
+ /* matches that are not long enough we need to emit as litterals */
+ if (match.match_length < MIN_MATCH) {
+ while (match.match_length) {
+ match.strstart++;
+ match.match_length--;
+
+ if (match.match_length) {
+ if (match.strstart >= match.orgstart) {
+#ifdef PRINT
+ printf("A\t\t\t\tInsert %i\n", match.strstart);
+#endif
+ insert_string(s, match.strstart);
+ insert_check(match.strstart);
+ }
+ }
+ }
+ return;
+ }
+
+
+
+
+ /* Insert new strings in the hash table only if the match length
+ * is not too large. This saves time but degrades compression.
+ */
+ if (match.match_length <= 16* s->max_insert_length &&
+ s->lookahead >= MIN_MATCH) {
+ match.match_length--; /* string at strstart already in table */
+ do {
+ match.strstart++;
+ if (likely(match.strstart >= match.orgstart)) {
+#ifdef PRINT
+ printf("B\t\t\t\tInsert %i\n", match.strstart);
+#endif
+ insert_string(s, match.strstart);
+ insert_check(match.strstart);
+ }
+ /* strstart never exceeds WSIZE-MAX_MATCH, so there are
+ * always MIN_MATCH bytes ahead.
+ */
+ } while (--match.match_length != 0);
+
+ match.strstart++;
+ } else {
+ match.strstart += match.match_length;
+ match.match_length = 0;
+ s->ins_h = s->window[match.strstart];
+ if (match.strstart >= 1)
+ UPDATE_HASH(s, s->ins_h, match.strstart+2-MIN_MATCH);
+#if MIN_MATCH != 3
+#warning Call UPDATE_HASH() MIN_MATCH-3 more times
+#endif
+ /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
+ * matter since it will be recomputed at next deflate call.
+ */
+ }
+}
+
+
+static void fizzle_matches(deflate_state *s, struct match *current, struct match *next)
+{
+ IPos limit;
+ unsigned char *match, *orig;
+ int changed = 0;
+ struct match c,n;
+ /* step zero: sanity checks */
+
+ if (current->match_length <= 1)
+ return;
+
+ match = s->window - current->match_length + 1 + next->match_start ;
+ orig = s->window - current->match_length + 1 + next->strstart ;
+
+ /* quick exit check.. if this fails then don't bother with anything else */
+ if (likely(*match != *orig))
+ return;
+
+
+ /*
+ * check the overlap case and just give up. We can do better in theory,
+ * but unlikely to be worth it
+ */
+ if (next->match_start + next->match_length >= current->strstart)
+ return;
+
+
+ c = *current;
+ n = *next;
+
+ /* step one: try to move the "next" match to the left as much as possible */
+ limit = next->strstart > MAX_DIST2 ? next->strstart - MAX_DIST2 : 0;
+
+ match = s->window + n.match_start - 1;
+ orig = s->window + n.strstart - 1;
+
+ while (*match == *orig && n.strstart > limit && n.match_length < 256 && c.match_length >= 1) {
+ n.strstart--;
+ n.match_start--;
+ n.match_length++;
+ c.match_length--;
+ match--;
+ orig--;
+ changed ++;
+ }
+ if (!changed)
+ return;
+
+
+
+
+ if ( (c.match_length <= 1) && n.match_length != 2) {
+ n.orgstart++;
+ *current = c;
+ *next = n;
+ } else return;
+
+
+#ifdef PRINT
+ printf("Changed matches: (%i)\n", changed);
+ printf("match1: %5i ---> %5i for %i bytes\n", current->strstart, current->match_start, current->match_length);
+ printf("match2:(%4i) %5i ---> %5i for %i bytes\n", next->orgstart, next->strstart, next->match_start, next->match_length);
+ printf("\n");
+#endif
+
+}
+
+block_state deflate_medium(deflate_state *s, int flush)
+{
+
+ struct match current_match, next_match;
+
+ memset(¤t_match, 0, sizeof(struct match));
+ memset(&next_match, 0, sizeof(struct match));
+
+// printf("Deflate medium\n");
+
+ for (;;) {
+ IPos hash_head; /* head of the hash chain */
+
+ int bflush; /* set if current block must be flushed */
+
+
+ /* Make sure that we always have enough lookahead, except
+ * at the end of the input file. We need MAX_MATCH bytes
+ * for the next match, plus MIN_MATCH bytes to insert the
+ * string following the next current_match.
+ */
+ if (s->lookahead < MIN_LOOKAHEAD) {
+ fill_window(s);
+ if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
+ return need_more;
+ }
+ if (s->lookahead == 0) break; /* flush the current block */
+ next_match.match_length = 0;
+ }
+ s->prev_length = 2;
+
+
+ /* Insert the string window[strstart .. strstart+2] in the
+ * dictionary, and set hash_head to the head of the hash chain:
+ */
+
+ /* If we already have a future match from a previous round, just use that */
+ if (next_match.match_length > 0) {
+ current_match = next_match;
+ next_match.match_length = 0;
+
+ } else {
+ hash_head = 0;
+ if (s->lookahead >= MIN_MATCH) {
+ hash_head = insert_string(s, s->strstart);
+ insert_check(s->strstart);
+#ifdef PRINT
+ printf("C\t\t\t\tInsert %i\n", s->strstart);
+#endif
+ }
+
+ /* set up the initial match to be a 1 byte literal */
+ current_match.match_start = 0;
+ current_match.match_length = 1;
+ current_match.strstart = s->strstart;
+ current_match.orgstart = current_match.strstart;
+#ifdef PRINT
+ printf("\t\t\t\tHash head is %i\n", hash_head);
+#endif
+
+ /* Find the longest match, discarding those <= prev_length.
+ * At this point we have always match_length < MIN_MATCH
+ */
+
+ if (hash_head != 0 && s->strstart - hash_head <= MAX_DIST2) {
+ /* To simplify the code, we prevent matches with the string
+ * of window index 0 (in particular we have to avoid a match
+ * of the string with itself at the start of the input file).
+ */
+ current_match.match_length = longest_match (s, hash_head);
+ current_match.match_start = s->match_start;
+#ifdef PRINT
+ printf(" Offset %8i: Match from %i (%i) \n", current_match.strstart, current_match.match_start, current_match.match_length);
+#endif
+ if (current_match.match_length < MIN_MATCH)
+ current_match.match_length = 1;
+ if (current_match.match_start >= current_match.strstart) { /* this can happen due to some restarts */
+// printf("Got a match length %i at %i for %i\n", current_match.match_length, current_match.match_start, current_match.strstart);
+ current_match.match_length = 1;
+ }
+ }
+ }
+
+ insert_match(s, current_match);
+#if 1
+ /* now, look ahead one */
+ if (s->lookahead > MIN_LOOKAHEAD) {
+ s->strstart = current_match.strstart + current_match.match_length;
+
+ hash_head = insert_string(s, s->strstart);
+ insert_check(s->strstart);
+#ifdef PRINT
+ printf("D\t\t\t\tInsert %i\n", s->strstart);
+#endif
+
+ /* set up the initial match to be a 1 byte literal */
+ next_match.match_start = 0;
+ next_match.match_length = 1;
+ next_match.strstart = s->strstart;
+ next_match.orgstart = next_match.strstart;
+
+#ifdef PRINT
+ printf("\t\t\t\tHash head is %i\n", hash_head);
+#endif
+
+ /* Find the longest match, discarding those <= prev_length.
+ * At this point we have always match_length < MIN_MATCH
+ */
+ if (hash_head != 0 && s->strstart - hash_head <= MAX_DIST2) {
+ /* To simplify the code, we prevent matches with the string
+ * of window index 0 (in particular we have to avoid a match
+ * of the string with itself at the start of the input file).
+ */
+ next_match.match_length = longest_match (s, hash_head);
+ next_match.match_start = s->match_start;
+#ifdef PRINT
+ printf(" Next Offset %8i: Match from %i (%i) \n", next_match.strstart, next_match.match_start, next_match.match_length);
+#endif
+ if (next_match.match_start >= next_match.strstart) /* this can happen due to some restarts */
+ next_match.match_length = 1;
+ if (next_match.match_length < MIN_MATCH)
+ next_match.match_length = 1;
+ else
+ fizzle_matches(s, ¤t_match, &next_match);
+ }
+
+ /* short matches with a very long distance are rarely a good idea encoding wise */
+ if (next_match.match_length == 3 && (next_match.strstart - next_match.match_start) > 12000)
+ next_match.match_length = 1;
+ s->strstart = current_match.strstart;
+
+ } else {
+ next_match.match_length = 0;
+ }
+
+#endif
+ /* now emit the current match */
+ bflush = emit_match(s, current_match, hash_head);
+
+ /* move the "cursor" forward */
+ s->strstart += current_match.match_length;
+
+ if (bflush)
+ FLUSH_BLOCK(s, 0);
+ }
+ s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
+ if (flush == Z_FINISH) {
+ FLUSH_BLOCK(s, 1);
+ return finish_done;
+ }
+ if (s->last_lit)
+ FLUSH_BLOCK(s, 0);
+ return block_done;
+}
+
--
1.7.1
More information about the Zlib-devel
mailing list