You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by mt...@apache.org on 2010/09/15 14:17:17 UTC
svn commit: r997302 [14/18] - in /labs/axmake/trunk: ./ src/ src/libuc++/
src/libuc++/port/ src/libuc++/srclib/ src/libuc++/srclib/bzip2/
src/libuc++/srclib/expat/ src/libuc++/srclib/regex/
src/libuc++/srclib/zlib/ src/libuc++/srclib/zlib/unix/ src/lib...
Added: labs/axmake/trunk/src/libuc++/srclib/zlib/trees.c
URL: http://svn.apache.org/viewvc/labs/axmake/trunk/src/libuc%2B%2B/srclib/zlib/trees.c?rev=997302&view=auto
==============================================================================
--- labs/axmake/trunk/src/libuc++/srclib/zlib/trees.c (added)
+++ labs/axmake/trunk/src/libuc++/srclib/zlib/trees.c Wed Sep 15 12:17:15 2010
@@ -0,0 +1,1244 @@
+/* trees.c -- output deflated data using Huffman coding
+ * Copyright (C) 1995-2010 Jean-loup Gailly
+ * detect_data_type() function provided freely by Cosmin Truta, 2006
+ * For conditions of distribution and use, see copyright notice in zlib.h
+ */
+
+/*
+ * ALGORITHM
+ *
+ * The "deflation" process uses several Huffman trees. The more
+ * common source values are represented by shorter bit sequences.
+ *
+ * Each code tree is stored in a compressed form which is itself
+ * a Huffman encoding of the lengths of all the code strings (in
+ * ascending order by source values). The actual code strings are
+ * reconstructed from the lengths in the inflate process, as described
+ * in the deflate specification.
+ *
+ * REFERENCES
+ *
+ * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
+ * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
+ *
+ * Storer, James A.
+ * Data Compression: Methods and Theory, pp. 49-50.
+ * Computer Science Press, 1988. ISBN 0-7167-8156-5.
+ *
+ * Sedgewick, R.
+ * Algorithms, p290.
+ * Addison-Wesley, 1983. ISBN 0-201-06672-6.
+ */
+
+/* @(#) $Id$ */
+
+/* #define GEN_TREES_H */
+
+#include "deflate.h"
+
+#ifdef DEBUG
+# include <ctype.h>
+#endif
+
+/* ===========================================================================
+ * Constants
+ */
+
+#define MAX_BL_BITS 7
+/* Bit length codes must not exceed MAX_BL_BITS bits */
+
+#define END_BLOCK 256
+/* end of block literal code */
+
+#define REP_3_6 16
+/* repeat previous bit length 3-6 times (2 bits of repeat count) */
+
+#define REPZ_3_10 17
+/* repeat a zero length 3-10 times (3 bits of repeat count) */
+
+#define REPZ_11_138 18
+/* repeat a zero length 11-138 times (7 bits of repeat count) */
+
+local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
+ = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
+
+local const int extra_dbits[D_CODES] /* extra bits for each distance code */
+ = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
+
+local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
+ = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
+
+local const uch bl_order[BL_CODES]
+ = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
+/* The lengths of the bit length codes are sent in order of decreasing
+ * probability, to avoid transmitting the lengths for unused bit length codes.
+ */
+
+#define Buf_size (8 * 2*sizeof(char))
+/* Number of bits used within bi_buf. (bi_buf might be implemented on
+ * more than 16 bits on some systems.)
+ */
+
+/* ===========================================================================
+ * Local data. These are initialized only once.
+ */
+
+#define DIST_CODE_LEN 512 /* see definition of array dist_code below */
+
+#if defined(GEN_TREES_H) || !defined(STDC)
+/* non ANSI compilers may not accept trees.h */
+
+local ct_data static_ltree[L_CODES+2];
+/* The static literal tree. Since the bit lengths are imposed, there is no
+ * need for the L_CODES extra codes used during heap construction. However
+ * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
+ * below).
+ */
+
+local ct_data static_dtree[D_CODES];
+/* The static distance tree. (Actually a trivial tree since all codes use
+ * 5 bits.)
+ */
+
+uch _dist_code[DIST_CODE_LEN];
+/* Distance codes. The first 256 values correspond to the distances
+ * 3 .. 258, the last 256 values correspond to the top 8 bits of
+ * the 15 bit distances.
+ */
+
+uch _length_code[MAX_MATCH-MIN_MATCH+1];
+/* length code for each normalized match length (0 == MIN_MATCH) */
+
+local int base_length[LENGTH_CODES];
+/* First normalized length for each code (0 = MIN_MATCH) */
+
+local int base_dist[D_CODES];
+/* First normalized distance for each code (0 = distance of 1) */
+
+#else
+# include "trees.h"
+#endif /* GEN_TREES_H */
+
+struct static_tree_desc_s {
+ const ct_data *static_tree; /* static tree or NULL */
+ const intf *extra_bits; /* extra bits for each code or NULL */
+ int extra_base; /* base index for extra_bits */
+ int elems; /* max number of elements in the tree */
+ int max_length; /* max bit length for the codes */
+};
+
+local static_tree_desc static_l_desc =
+{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
+
+local static_tree_desc static_d_desc =
+{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
+
+local static_tree_desc static_bl_desc =
+{(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
+
+/* ===========================================================================
+ * Local (static) routines in this file.
+ */
+
+local void tr_static_init OF((void));
+local void init_block OF((deflate_state *s));
+local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
+local void gen_bitlen OF((deflate_state *s, tree_desc *desc));
+local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
+local void build_tree OF((deflate_state *s, tree_desc *desc));
+local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
+local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
+local int build_bl_tree OF((deflate_state *s));
+local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
+ int blcodes));
+local void compress_block OF((deflate_state *s, ct_data *ltree,
+ ct_data *dtree));
+local int detect_data_type OF((deflate_state *s));
+local unsigned bi_reverse OF((unsigned value, int length));
+local void bi_windup OF((deflate_state *s));
+local void bi_flush OF((deflate_state *s));
+local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
+ int header));
+
+#ifdef GEN_TREES_H
+local void gen_trees_header OF((void));
+#endif
+
+#ifndef DEBUG
+# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
+ /* Send a code of the given tree. c and tree must not have side effects */
+
+#else /* DEBUG */
+# define send_code(s, c, tree) \
+ { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
+ send_bits(s, tree[c].Code, tree[c].Len); }
+#endif
+
+/* ===========================================================================
+ * Output a short LSB first on the stream.
+ * IN assertion: there is enough room in pendingBuf.
+ */
+#define put_short(s, w) { \
+ put_byte(s, (uch)((w) & 0xff)); \
+ put_byte(s, (uch)((ush)(w) >> 8)); \
+}
+
+/* ===========================================================================
+ * Send a value on a given number of bits.
+ * IN assertion: length <= 16 and value fits in length bits.
+ */
+#ifdef DEBUG
+local void send_bits OF((deflate_state *s, int value, int length));
+
+local void send_bits(s, value, length)
+ deflate_state *s;
+ int value; /* value to send */
+ int length; /* number of bits */
+{
+ Tracevv((stderr," l %2d v %4x ", length, value));
+ Assert(length > 0 && length <= 15, "invalid length");
+ s->bits_sent += (ulg)length;
+
+ /* If not enough room in bi_buf, use (valid) bits from bi_buf and
+ * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
+ * unused bits in value.
+ */
+ if (s->bi_valid > (int)Buf_size - length) {
+ s->bi_buf |= (ush)value << s->bi_valid;
+ put_short(s, s->bi_buf);
+ s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
+ s->bi_valid += length - Buf_size;
+ } else {
+ s->bi_buf |= (ush)value << s->bi_valid;
+ s->bi_valid += length;
+ }
+}
+#else /* !DEBUG */
+
+#define send_bits(s, value, length) \
+{ int len = length;\
+ if (s->bi_valid > (int)Buf_size - len) {\
+ int val = value;\
+ s->bi_buf |= (ush)val << s->bi_valid;\
+ put_short(s, s->bi_buf);\
+ s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
+ s->bi_valid += len - Buf_size;\
+ } else {\
+ s->bi_buf |= (ush)(value) << s->bi_valid;\
+ s->bi_valid += len;\
+ }\
+}
+#endif /* DEBUG */
+
+
+/* the arguments must not have side effects */
+
+/* ===========================================================================
+ * Initialize the various 'constant' tables.
+ */
+local void tr_static_init()
+{
+#if defined(GEN_TREES_H) || !defined(STDC)
+ static int static_init_done = 0;
+ int n; /* iterates over tree elements */
+ int bits; /* bit counter */
+ int length; /* length value */
+ int code; /* code value */
+ int dist; /* distance index */
+ ush bl_count[MAX_BITS+1];
+ /* number of codes at each bit length for an optimal tree */
+
+ if (static_init_done) return;
+
+ /* For some embedded targets, global variables are not initialized: */
+#ifdef NO_INIT_GLOBAL_POINTERS
+ static_l_desc.static_tree = static_ltree;
+ static_l_desc.extra_bits = extra_lbits;
+ static_d_desc.static_tree = static_dtree;
+ static_d_desc.extra_bits = extra_dbits;
+ static_bl_desc.extra_bits = extra_blbits;
+#endif
+
+ /* Initialize the mapping length (0..255) -> length code (0..28) */
+ length = 0;
+ for (code = 0; code < LENGTH_CODES-1; code++) {
+ base_length[code] = length;
+ for (n = 0; n < (1<<extra_lbits[code]); n++) {
+ _length_code[length++] = (uch)code;
+ }
+ }
+ Assert (length == 256, "tr_static_init: length != 256");
+ /* Note that the length 255 (match length 258) can be represented
+ * in two different ways: code 284 + 5 bits or code 285, so we
+ * overwrite length_code[255] to use the best encoding:
+ */
+ _length_code[length-1] = (uch)code;
+
+ /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
+ dist = 0;
+ for (code = 0 ; code < 16; code++) {
+ base_dist[code] = dist;
+ for (n = 0; n < (1<<extra_dbits[code]); n++) {
+ _dist_code[dist++] = (uch)code;
+ }
+ }
+ Assert (dist == 256, "tr_static_init: dist != 256");
+ dist >>= 7; /* from now on, all distances are divided by 128 */
+ for ( ; code < D_CODES; code++) {
+ base_dist[code] = dist << 7;
+ for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
+ _dist_code[256 + dist++] = (uch)code;
+ }
+ }
+ Assert (dist == 256, "tr_static_init: 256+dist != 512");
+
+ /* Construct the codes of the static literal tree */
+ for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
+ n = 0;
+ while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
+ while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
+ while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
+ while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
+ /* Codes 286 and 287 do not exist, but we must include them in the
+ * tree construction to get a canonical Huffman tree (longest code
+ * all ones)
+ */
+ gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
+
+ /* The static distance tree is trivial: */
+ for (n = 0; n < D_CODES; n++) {
+ static_dtree[n].Len = 5;
+ static_dtree[n].Code = bi_reverse((unsigned)n, 5);
+ }
+ static_init_done = 1;
+
+# ifdef GEN_TREES_H
+ gen_trees_header();
+# endif
+#endif /* defined(GEN_TREES_H) || !defined(STDC) */
+}
+
+/* ===========================================================================
+ * Genererate the file trees.h describing the static trees.
+ */
+#ifdef GEN_TREES_H
+# ifndef DEBUG
+# include <stdio.h>
+# endif
+
+# define SEPARATOR(i, last, width) \
+ ((i) == (last)? "\n};\n\n" : \
+ ((i) % (width) == (width)-1 ? ",\n" : ", "))
+
+void gen_trees_header()
+{
+ FILE *header = fopen("trees.h", "w");
+ int i;
+
+ Assert (header != NULL, "Can't open trees.h");
+ fprintf(header,
+ "/* header created automatically with -DGEN_TREES_H */\n\n");
+
+ fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
+ for (i = 0; i < L_CODES+2; i++) {
+ fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
+ static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
+ }
+
+ fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
+ for (i = 0; i < D_CODES; i++) {
+ fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
+ static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
+ }
+
+ fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
+ for (i = 0; i < DIST_CODE_LEN; i++) {
+ fprintf(header, "%2u%s", _dist_code[i],
+ SEPARATOR(i, DIST_CODE_LEN-1, 20));
+ }
+
+ fprintf(header,
+ "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
+ for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
+ fprintf(header, "%2u%s", _length_code[i],
+ SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
+ }
+
+ fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
+ for (i = 0; i < LENGTH_CODES; i++) {
+ fprintf(header, "%1u%s", base_length[i],
+ SEPARATOR(i, LENGTH_CODES-1, 20));
+ }
+
+ fprintf(header, "local const int base_dist[D_CODES] = {\n");
+ for (i = 0; i < D_CODES; i++) {
+ fprintf(header, "%5u%s", base_dist[i],
+ SEPARATOR(i, D_CODES-1, 10));
+ }
+
+ fclose(header);
+}
+#endif /* GEN_TREES_H */
+
+/* ===========================================================================
+ * Initialize the tree data structures for a new zlib stream.
+ */
+void ZLIB_INTERNAL _tr_init(s)
+ deflate_state *s;
+{
+ tr_static_init();
+
+ s->l_desc.dyn_tree = s->dyn_ltree;
+ s->l_desc.stat_desc = &static_l_desc;
+
+ s->d_desc.dyn_tree = s->dyn_dtree;
+ s->d_desc.stat_desc = &static_d_desc;
+
+ s->bl_desc.dyn_tree = s->bl_tree;
+ s->bl_desc.stat_desc = &static_bl_desc;
+
+ s->bi_buf = 0;
+ s->bi_valid = 0;
+ s->last_eob_len = 8; /* enough lookahead for inflate */
+#ifdef DEBUG
+ s->compressed_len = 0L;
+ s->bits_sent = 0L;
+#endif
+
+ /* Initialize the first block of the first file: */
+ init_block(s);
+}
+
+/* ===========================================================================
+ * Initialize a new block.
+ */
+local void init_block(s)
+ deflate_state *s;
+{
+ int n; /* iterates over tree elements */
+
+ /* Initialize the trees. */
+ for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
+ for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
+ for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
+
+ s->dyn_ltree[END_BLOCK].Freq = 1;
+ s->opt_len = s->static_len = 0L;
+ s->last_lit = s->matches = 0;
+}
+
+#define SMALLEST 1
+/* Index within the heap array of least frequent node in the Huffman tree */
+
+
+/* ===========================================================================
+ * Remove the smallest element from the heap and recreate the heap with
+ * one less element. Updates heap and heap_len.
+ */
+#define pqremove(s, tree, top) \
+{\
+ top = s->heap[SMALLEST]; \
+ s->heap[SMALLEST] = s->heap[s->heap_len--]; \
+ pqdownheap(s, tree, SMALLEST); \
+}
+
+/* ===========================================================================
+ * Compares to subtrees, using the tree depth as tie breaker when
+ * the subtrees have equal frequency. This minimizes the worst case length.
+ */
+#define smaller(tree, n, m, depth) \
+ (tree[n].Freq < tree[m].Freq || \
+ (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
+
+/* ===========================================================================
+ * Restore the heap property by moving down the tree starting at node k,
+ * exchanging a node with the smallest of its two sons if necessary, stopping
+ * when the heap property is re-established (each father smaller than its
+ * two sons).
+ */
+local void pqdownheap(s, tree, k)
+ deflate_state *s;
+ ct_data *tree; /* the tree to restore */
+ int k; /* node to move down */
+{
+ int v = s->heap[k];
+ int j = k << 1; /* left son of k */
+ while (j <= s->heap_len) {
+ /* Set j to the smallest of the two sons: */
+ if (j < s->heap_len &&
+ smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
+ j++;
+ }
+ /* Exit if v is smaller than both sons */
+ if (smaller(tree, v, s->heap[j], s->depth)) break;
+
+ /* Exchange v with the smallest son */
+ s->heap[k] = s->heap[j]; k = j;
+
+ /* And continue down the tree, setting j to the left son of k */
+ j <<= 1;
+ }
+ s->heap[k] = v;
+}
+
+/* ===========================================================================
+ * Compute the optimal bit lengths for a tree and update the total bit length
+ * for the current block.
+ * IN assertion: the fields freq and dad are set, heap[heap_max] and
+ * above are the tree nodes sorted by increasing frequency.
+ * OUT assertions: the field len is set to the optimal bit length, the
+ * array bl_count contains the frequencies for each bit length.
+ * The length opt_len is updated; static_len is also updated if stree is
+ * not null.
+ */
+local void gen_bitlen(s, desc)
+ deflate_state *s;
+ tree_desc *desc; /* the tree descriptor */
+{
+ ct_data *tree = desc->dyn_tree;
+ int max_code = desc->max_code;
+ const ct_data *stree = desc->stat_desc->static_tree;
+ const intf *extra = desc->stat_desc->extra_bits;
+ int base = desc->stat_desc->extra_base;
+ int max_length = desc->stat_desc->max_length;
+ int h; /* heap index */
+ int n, m; /* iterate over the tree elements */
+ int bits; /* bit length */
+ int xbits; /* extra bits */
+ ush f; /* frequency */
+ int overflow = 0; /* number of elements with bit length too large */
+
+ for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
+
+ /* In a first pass, compute the optimal bit lengths (which may
+ * overflow in the case of the bit length tree).
+ */
+ tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
+
+ for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
+ n = s->heap[h];
+ bits = tree[tree[n].Dad].Len + 1;
+ if (bits > max_length) bits = max_length, overflow++;
+ tree[n].Len = (ush)bits;
+ /* We overwrite tree[n].Dad which is no longer needed */
+
+ if (n > max_code) continue; /* not a leaf node */
+
+ s->bl_count[bits]++;
+ xbits = 0;
+ if (n >= base) xbits = extra[n-base];
+ f = tree[n].Freq;
+ s->opt_len += (ulg)f * (bits + xbits);
+ if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
+ }
+ if (overflow == 0) return;
+
+ Trace((stderr,"\nbit length overflow\n"));
+ /* This happens for example on obj2 and pic of the Calgary corpus */
+
+ /* Find the first bit length which could increase: */
+ do {
+ bits = max_length-1;
+ while (s->bl_count[bits] == 0) bits--;
+ s->bl_count[bits]--; /* move one leaf down the tree */
+ s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
+ s->bl_count[max_length]--;
+ /* The brother of the overflow item also moves one step up,
+ * but this does not affect bl_count[max_length]
+ */
+ overflow -= 2;
+ } while (overflow > 0);
+
+ /* Now recompute all bit lengths, scanning in increasing frequency.
+ * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
+ * lengths instead of fixing only the wrong ones. This idea is taken
+ * from 'ar' written by Haruhiko Okumura.)
+ */
+ for (bits = max_length; bits != 0; bits--) {
+ n = s->bl_count[bits];
+ while (n != 0) {
+ m = s->heap[--h];
+ if (m > max_code) continue;
+ if ((unsigned) tree[m].Len != (unsigned) bits) {
+ Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
+ s->opt_len += ((long)bits - (long)tree[m].Len)
+ *(long)tree[m].Freq;
+ tree[m].Len = (ush)bits;
+ }
+ n--;
+ }
+ }
+}
+
+/* ===========================================================================
+ * Generate the codes for a given tree and bit counts (which need not be
+ * optimal).
+ * IN assertion: the array bl_count contains the bit length statistics for
+ * the given tree and the field len is set for all tree elements.
+ * OUT assertion: the field code is set for all tree elements of non
+ * zero code length.
+ */
+local void gen_codes (tree, max_code, bl_count)
+ ct_data *tree; /* the tree to decorate */
+ int max_code; /* largest code with non zero frequency */
+ ushf *bl_count; /* number of codes at each bit length */
+{
+ ush next_code[MAX_BITS+1]; /* next code value for each bit length */
+ ush code = 0; /* running code value */
+ int bits; /* bit index */
+ int n; /* code index */
+
+ /* The distribution counts are first used to generate the code values
+ * without bit reversal.
+ */
+ for (bits = 1; bits <= MAX_BITS; bits++) {
+ next_code[bits] = code = (code + bl_count[bits-1]) << 1;
+ }
+ /* Check that the bit counts in bl_count are consistent. The last code
+ * must be all ones.
+ */
+ Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
+ "inconsistent bit counts");
+ Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
+
+ for (n = 0; n <= max_code; n++) {
+ int len = tree[n].Len;
+ if (len == 0) continue;
+ /* Now reverse the bits */
+ tree[n].Code = bi_reverse(next_code[len]++, len);
+
+ Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
+ n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
+ }
+}
+
+/* ===========================================================================
+ * Construct one Huffman tree and assigns the code bit strings and lengths.
+ * Update the total bit length for the current block.
+ * IN assertion: the field freq is set for all tree elements.
+ * OUT assertions: the fields len and code are set to the optimal bit length
+ * and corresponding code. The length opt_len is updated; static_len is
+ * also updated if stree is not null. The field max_code is set.
+ */
+local void build_tree(s, desc)
+ deflate_state *s;
+ tree_desc *desc; /* the tree descriptor */
+{
+ ct_data *tree = desc->dyn_tree;
+ const ct_data *stree = desc->stat_desc->static_tree;
+ int elems = desc->stat_desc->elems;
+ int n, m; /* iterate over heap elements */
+ int max_code = -1; /* largest code with non zero frequency */
+ int node; /* new node being created */
+
+ /* Construct the initial heap, with least frequent element in
+ * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
+ * heap[0] is not used.
+ */
+ s->heap_len = 0, s->heap_max = HEAP_SIZE;
+
+ for (n = 0; n < elems; n++) {
+ if (tree[n].Freq != 0) {
+ s->heap[++(s->heap_len)] = max_code = n;
+ s->depth[n] = 0;
+ } else {
+ tree[n].Len = 0;
+ }
+ }
+
+ /* The pkzip format requires that at least one distance code exists,
+ * and that at least one bit should be sent even if there is only one
+ * possible code. So to avoid special checks later on we force at least
+ * two codes of non zero frequency.
+ */
+ while (s->heap_len < 2) {
+ node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
+ tree[node].Freq = 1;
+ s->depth[node] = 0;
+ s->opt_len--; if (stree) s->static_len -= stree[node].Len;
+ /* node is 0 or 1 so it does not have extra bits */
+ }
+ desc->max_code = max_code;
+
+ /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
+ * establish sub-heaps of increasing lengths:
+ */
+ for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
+
+ /* Construct the Huffman tree by repeatedly combining the least two
+ * frequent nodes.
+ */
+ node = elems; /* next internal node of the tree */
+ do {
+ pqremove(s, tree, n); /* n = node of least frequency */
+ m = s->heap[SMALLEST]; /* m = node of next least frequency */
+
+ s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
+ s->heap[--(s->heap_max)] = m;
+
+ /* Create a new node father of n and m */
+ tree[node].Freq = tree[n].Freq + tree[m].Freq;
+ s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
+ s->depth[n] : s->depth[m]) + 1);
+ tree[n].Dad = tree[m].Dad = (ush)node;
+#ifdef DUMP_BL_TREE
+ if (tree == s->bl_tree) {
+ fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
+ node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
+ }
+#endif
+ /* and insert the new node in the heap */
+ s->heap[SMALLEST] = node++;
+ pqdownheap(s, tree, SMALLEST);
+
+ } while (s->heap_len >= 2);
+
+ s->heap[--(s->heap_max)] = s->heap[SMALLEST];
+
+ /* At this point, the fields freq and dad are set. We can now
+ * generate the bit lengths.
+ */
+ gen_bitlen(s, (tree_desc *)desc);
+
+ /* The field len is now set, we can generate the bit codes */
+ gen_codes ((ct_data *)tree, max_code, s->bl_count);
+}
+
+/* ===========================================================================
+ * Scan a literal or distance tree to determine the frequencies of the codes
+ * in the bit length tree.
+ */
+local void scan_tree (s, tree, max_code)
+ deflate_state *s;
+ ct_data *tree; /* the tree to be scanned */
+ int max_code; /* and its largest code of non zero frequency */
+{
+ int n; /* iterates over all tree elements */
+ int prevlen = -1; /* last emitted length */
+ int curlen; /* length of current code */
+ int nextlen = tree[0].Len; /* length of next code */
+ int count = 0; /* repeat count of the current code */
+ int max_count = 7; /* max repeat count */
+ int min_count = 4; /* min repeat count */
+
+ if (nextlen == 0) max_count = 138, min_count = 3;
+ tree[max_code+1].Len = (ush)0xffff; /* guard */
+
+ for (n = 0; n <= max_code; n++) {
+ curlen = nextlen; nextlen = tree[n+1].Len;
+ if (++count < max_count && curlen == nextlen) {
+ continue;
+ } else if (count < min_count) {
+ s->bl_tree[curlen].Freq += count;
+ } else if (curlen != 0) {
+ if (curlen != prevlen) s->bl_tree[curlen].Freq++;
+ s->bl_tree[REP_3_6].Freq++;
+ } else if (count <= 10) {
+ s->bl_tree[REPZ_3_10].Freq++;
+ } else {
+ s->bl_tree[REPZ_11_138].Freq++;
+ }
+ count = 0; prevlen = curlen;
+ if (nextlen == 0) {
+ max_count = 138, min_count = 3;
+ } else if (curlen == nextlen) {
+ max_count = 6, min_count = 3;
+ } else {
+ max_count = 7, min_count = 4;
+ }
+ }
+}
+
+/* ===========================================================================
+ * Send a literal or distance tree in compressed form, using the codes in
+ * bl_tree.
+ */
+local void send_tree (s, tree, max_code)
+ deflate_state *s;
+ ct_data *tree; /* the tree to be scanned */
+ int max_code; /* and its largest code of non zero frequency */
+{
+ int n; /* iterates over all tree elements */
+ int prevlen = -1; /* last emitted length */
+ int curlen; /* length of current code */
+ int nextlen = tree[0].Len; /* length of next code */
+ int count = 0; /* repeat count of the current code */
+ int max_count = 7; /* max repeat count */
+ int min_count = 4; /* min repeat count */
+
+ /* tree[max_code+1].Len = -1; */ /* guard already set */
+ if (nextlen == 0) max_count = 138, min_count = 3;
+
+ for (n = 0; n <= max_code; n++) {
+ curlen = nextlen; nextlen = tree[n+1].Len;
+ if (++count < max_count && curlen == nextlen) {
+ continue;
+ } else if (count < min_count) {
+ do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
+
+ } else if (curlen != 0) {
+ if (curlen != prevlen) {
+ send_code(s, curlen, s->bl_tree); count--;
+ }
+ Assert(count >= 3 && count <= 6, " 3_6?");
+ send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
+
+ } else if (count <= 10) {
+ send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
+
+ } else {
+ send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
+ }
+ count = 0; prevlen = curlen;
+ if (nextlen == 0) {
+ max_count = 138, min_count = 3;
+ } else if (curlen == nextlen) {
+ max_count = 6, min_count = 3;
+ } else {
+ max_count = 7, min_count = 4;
+ }
+ }
+}
+
+/* ===========================================================================
+ * Construct the Huffman tree for the bit lengths and return the index in
+ * bl_order of the last bit length code to send.
+ */
+local int build_bl_tree(s)
+ deflate_state *s;
+{
+ int max_blindex; /* index of last bit length code of non zero freq */
+
+ /* Determine the bit length frequencies for literal and distance trees */
+ scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
+ scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
+
+ /* Build the bit length tree: */
+ build_tree(s, (tree_desc *)(&(s->bl_desc)));
+ /* opt_len now includes the length of the tree representations, except
+ * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
+ */
+
+ /* Determine the number of bit length codes to send. The pkzip format
+ * requires that at least 4 bit length codes be sent. (appnote.txt says
+ * 3 but the actual value used is 4.)
+ */
+ for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
+ if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
+ }
+ /* Update opt_len to include the bit length tree and counts */
+ s->opt_len += 3*(max_blindex+1) + 5+5+4;
+ Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
+ s->opt_len, s->static_len));
+
+ return max_blindex;
+}
+
+/* ===========================================================================
+ * Send the header for a block using dynamic Huffman trees: the counts, the
+ * lengths of the bit length codes, the literal tree and the distance tree.
+ * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
+ */
+local void send_all_trees(s, lcodes, dcodes, blcodes)
+ deflate_state *s;
+ int lcodes, dcodes, blcodes; /* number of codes for each tree */
+{
+ int rank; /* index in bl_order */
+
+ Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
+ Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
+ "too many codes");
+ Tracev((stderr, "\nbl counts: "));
+ send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
+ send_bits(s, dcodes-1, 5);
+ send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
+ for (rank = 0; rank < blcodes; rank++) {
+ Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
+ send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
+ }
+ Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
+
+ send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
+ Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
+
+ send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
+ Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
+}
+
+/* ===========================================================================
+ * Send a stored block
+ */
+void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last)
+ deflate_state *s;
+ charf *buf; /* input block */
+ ulg stored_len; /* length of input block */
+ int last; /* one if this is the last block for a file */
+{
+ send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */
+#ifdef DEBUG
+ s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
+ s->compressed_len += (stored_len + 4) << 3;
+#endif
+ copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
+}
+
+/* ===========================================================================
+ * Send one empty static block to give enough lookahead for inflate.
+ * This takes 10 bits, of which 7 may remain in the bit buffer.
+ * The current inflate code requires 9 bits of lookahead. If the
+ * last two codes for the previous block (real code plus EOB) were coded
+ * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
+ * the last real code. In this case we send two empty static blocks instead
+ * of one. (There are no problems if the previous block is stored or fixed.)
+ * To simplify the code, we assume the worst case of last real code encoded
+ * on one bit only.
+ */
+void ZLIB_INTERNAL _tr_align(s)
+ deflate_state *s;
+{
+ send_bits(s, STATIC_TREES<<1, 3);
+ send_code(s, END_BLOCK, static_ltree);
+#ifdef DEBUG
+ s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
+#endif
+ bi_flush(s);
+ /* Of the 10 bits for the empty block, we have already sent
+ * (10 - bi_valid) bits. The lookahead for the last real code (before
+ * the EOB of the previous block) was thus at least one plus the length
+ * of the EOB plus what we have just sent of the empty static block.
+ */
+ if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
+ send_bits(s, STATIC_TREES<<1, 3);
+ send_code(s, END_BLOCK, static_ltree);
+#ifdef DEBUG
+ s->compressed_len += 10L;
+#endif
+ bi_flush(s);
+ }
+ s->last_eob_len = 7;
+}
+
+/* ===========================================================================
+ * Determine the best encoding for the current block: dynamic trees, static
+ * trees or store, and output the encoded block to the zip file.
+ */
+void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last)
+ deflate_state *s;
+ charf *buf; /* input block, or NULL if too old */
+ ulg stored_len; /* length of input block */
+ int last; /* one if this is the last block for a file */
+{
+ ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
+ int max_blindex = 0; /* index of last bit length code of non zero freq */
+
+ /* Build the Huffman trees unless a stored block is forced */
+ if (s->level > 0) {
+
+ /* Check if the file is binary or text */
+ if (s->strm->data_type == Z_UNKNOWN)
+ s->strm->data_type = detect_data_type(s);
+
+ /* Construct the literal and distance trees */
+ build_tree(s, (tree_desc *)(&(s->l_desc)));
+ Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
+ s->static_len));
+
+ build_tree(s, (tree_desc *)(&(s->d_desc)));
+ Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
+ s->static_len));
+ /* At this point, opt_len and static_len are the total bit lengths of
+ * the compressed block data, excluding the tree representations.
+ */
+
+ /* Build the bit length tree for the above two trees, and get the index
+ * in bl_order of the last bit length code to send.
+ */
+ max_blindex = build_bl_tree(s);
+
+ /* Determine the best encoding. Compute the block lengths in bytes. */
+ opt_lenb = (s->opt_len+3+7)>>3;
+ static_lenb = (s->static_len+3+7)>>3;
+
+ Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
+ opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
+ s->last_lit));
+
+ if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
+
+ } else {
+ Assert(buf != (char*)0, "lost buf");
+ opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
+ }
+
+#ifdef FORCE_STORED
+ if (buf != (char*)0) { /* force stored block */
+#else
+ if (stored_len+4 <= opt_lenb && buf != (char*)0) {
+ /* 4: two words for the lengths */
+#endif
+ /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
+ * Otherwise we can't have processed more than WSIZE input bytes since
+ * the last block flush, because compression would have been
+ * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
+ * transform a block into a stored block.
+ */
+ _tr_stored_block(s, buf, stored_len, last);
+
+#ifdef FORCE_STATIC
+ } else if (static_lenb >= 0) { /* force static trees */
+#else
+ } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
+#endif
+ send_bits(s, (STATIC_TREES<<1)+last, 3);
+ compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
+#ifdef DEBUG
+ s->compressed_len += 3 + s->static_len;
+#endif
+ } else {
+ send_bits(s, (DYN_TREES<<1)+last, 3);
+ send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
+ max_blindex+1);
+ compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
+#ifdef DEBUG
+ s->compressed_len += 3 + s->opt_len;
+#endif
+ }
+ Assert (s->compressed_len == s->bits_sent, "bad compressed size");
+ /* The above check is made mod 2^32, for files larger than 512 MB
+ * and uLong implemented on 32 bits.
+ */
+ init_block(s);
+
+ if (last) {
+ bi_windup(s);
+#ifdef DEBUG
+ s->compressed_len += 7; /* align on byte boundary */
+#endif
+ }
+ Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
+ s->compressed_len-7*last));
+}
+
+/* ===========================================================================
+ * Save the match info and tally the frequency counts. Return true if
+ * the current block must be flushed.
+ */
+int ZLIB_INTERNAL _tr_tally (s, dist, lc)
+ deflate_state *s;
+ unsigned dist; /* distance of matched string */
+ unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
+{
+ s->d_buf[s->last_lit] = (ush)dist;
+ s->l_buf[s->last_lit++] = (uch)lc;
+ if (dist == 0) {
+ /* lc is the unmatched char */
+ s->dyn_ltree[lc].Freq++;
+ } else {
+ s->matches++;
+ /* Here, lc is the match length - MIN_MATCH */
+ dist--; /* dist = match distance - 1 */
+ Assert((ush)dist < (ush)MAX_DIST(s) &&
+ (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
+ (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
+
+ s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
+ s->dyn_dtree[d_code(dist)].Freq++;
+ }
+
+#ifdef TRUNCATE_BLOCK
+ /* Try to guess if it is profitable to stop the current block here */
+ if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
+ /* Compute an upper bound for the compressed length */
+ ulg out_length = (ulg)s->last_lit*8L;
+ ulg in_length = (ulg)((long)s->strstart - s->block_start);
+ int dcode;
+ for (dcode = 0; dcode < D_CODES; dcode++) {
+ out_length += (ulg)s->dyn_dtree[dcode].Freq *
+ (5L+extra_dbits[dcode]);
+ }
+ out_length >>= 3;
+ Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
+ s->last_lit, in_length, out_length,
+ 100L - out_length*100L/in_length));
+ if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
+ }
+#endif
+ return (s->last_lit == s->lit_bufsize-1);
+ /* We avoid equality with lit_bufsize because of wraparound at 64K
+ * on 16 bit machines and because stored blocks are restricted to
+ * 64K-1 bytes.
+ */
+}
+
+/* ===========================================================================
+ * Send the block data compressed using the given Huffman trees
+ */
+local void compress_block(s, ltree, dtree)
+ deflate_state *s;
+ ct_data *ltree; /* literal tree */
+ ct_data *dtree; /* distance tree */
+{
+ unsigned dist; /* distance of matched string */
+ int lc; /* match length or unmatched char (if dist == 0) */
+ unsigned lx = 0; /* running index in l_buf */
+ unsigned code; /* the code to send */
+ int extra; /* number of extra bits to send */
+
+ if (s->last_lit != 0) do {
+ dist = s->d_buf[lx];
+ lc = s->l_buf[lx++];
+ if (dist == 0) {
+ send_code(s, lc, ltree); /* send a literal byte */
+ Tracecv(isgraph(lc), (stderr," '%c' ", lc));
+ } else {
+ /* Here, lc is the match length - MIN_MATCH */
+ code = _length_code[lc];
+ send_code(s, code+LITERALS+1, ltree); /* send the length code */
+ extra = extra_lbits[code];
+ if (extra != 0) {
+ lc -= base_length[code];
+ send_bits(s, lc, extra); /* send the extra length bits */
+ }
+ dist--; /* dist is now the match distance - 1 */
+ code = d_code(dist);
+ Assert (code < D_CODES, "bad d_code");
+
+ send_code(s, code, dtree); /* send the distance code */
+ extra = extra_dbits[code];
+ if (extra != 0) {
+ dist -= base_dist[code];
+ send_bits(s, dist, extra); /* send the extra distance bits */
+ }
+ } /* literal or match pair ? */
+
+ /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
+ Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
+ "pendingBuf overflow");
+
+ } while (lx < s->last_lit);
+
+ send_code(s, END_BLOCK, ltree);
+ s->last_eob_len = ltree[END_BLOCK].Len;
+}
+
+/* ===========================================================================
+ * Check if the data type is TEXT or BINARY, using the following algorithm:
+ * - TEXT if the two conditions below are satisfied:
+ * a) There are no non-portable control characters belonging to the
+ * "black list" (0..6, 14..25, 28..31).
+ * b) There is at least one printable character belonging to the
+ * "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
+ * - BINARY otherwise.
+ * - The following partially-portable control characters form a
+ * "gray list" that is ignored in this detection algorithm:
+ * (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
+ * IN assertion: the fields Freq of dyn_ltree are set.
+ */
+local int detect_data_type(s)
+ deflate_state *s;
+{
+ /* black_mask is the bit mask of black-listed bytes
+ * set bits 0..6, 14..25, and 28..31
+ * 0xf3ffc07f = binary 11110011111111111100000001111111
+ */
+ unsigned long black_mask = 0xf3ffc07fUL;
+ int n;
+
+ /* Check for non-textual ("black-listed") bytes. */
+ for (n = 0; n <= 31; n++, black_mask >>= 1)
+ if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
+ return Z_BINARY;
+
+ /* Check for textual ("white-listed") bytes. */
+ if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
+ || s->dyn_ltree[13].Freq != 0)
+ return Z_TEXT;
+ for (n = 32; n < LITERALS; n++)
+ if (s->dyn_ltree[n].Freq != 0)
+ return Z_TEXT;
+
+ /* There are no "black-listed" or "white-listed" bytes:
+ * this stream either is empty or has tolerated ("gray-listed") bytes only.
+ */
+ return Z_BINARY;
+}
+
+/* ===========================================================================
+ * Reverse the first len bits of a code, using straightforward code (a faster
+ * method would use a table)
+ * IN assertion: 1 <= len <= 15
+ */
+local unsigned bi_reverse(code, len)
+ unsigned code; /* the value to invert */
+ int len; /* its bit length */
+{
+ register unsigned res = 0;
+ do {
+ res |= code & 1;
+ code >>= 1, res <<= 1;
+ } while (--len > 0);
+ return res >> 1;
+}
+
+/* ===========================================================================
+ * Flush the bit buffer, keeping at most 7 bits in it.
+ */
+local void bi_flush(s)
+ deflate_state *s;
+{
+ if (s->bi_valid == 16) {
+ put_short(s, s->bi_buf);
+ s->bi_buf = 0;
+ s->bi_valid = 0;
+ } else if (s->bi_valid >= 8) {
+ put_byte(s, (Byte)s->bi_buf);
+ s->bi_buf >>= 8;
+ s->bi_valid -= 8;
+ }
+}
+
+/* ===========================================================================
+ * Flush the bit buffer and align the output on a byte boundary
+ */
+local void bi_windup(s)
+ deflate_state *s;
+{
+ if (s->bi_valid > 8) {
+ put_short(s, s->bi_buf);
+ } else if (s->bi_valid > 0) {
+ put_byte(s, (Byte)s->bi_buf);
+ }
+ s->bi_buf = 0;
+ s->bi_valid = 0;
+#ifdef DEBUG
+ s->bits_sent = (s->bits_sent+7) & ~7;
+#endif
+}
+
+/* ===========================================================================
+ * Copy a stored block, storing first the length and its
+ * one's complement if requested.
+ */
+local void copy_block(s, buf, len, header)
+ deflate_state *s;
+ charf *buf; /* the input data */
+ unsigned len; /* its length */
+ int header; /* true if block header must be written */
+{
+ bi_windup(s); /* align on byte boundary */
+ s->last_eob_len = 8; /* enough lookahead for inflate */
+
+ if (header) {
+ put_short(s, (ush)len);
+ put_short(s, (ush)~len);
+#ifdef DEBUG
+ s->bits_sent += 2*16;
+#endif
+ }
+#ifdef DEBUG
+ s->bits_sent += (ulg)len<<3;
+#endif
+ while (len--) {
+ put_byte(s, *buf++);
+ }
+}
Propchange: labs/axmake/trunk/src/libuc++/srclib/zlib/trees.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: labs/axmake/trunk/src/libuc++/srclib/zlib/trees.h
URL: http://svn.apache.org/viewvc/labs/axmake/trunk/src/libuc%2B%2B/srclib/zlib/trees.h?rev=997302&view=auto
==============================================================================
--- labs/axmake/trunk/src/libuc++/srclib/zlib/trees.h (added)
+++ labs/axmake/trunk/src/libuc++/srclib/zlib/trees.h Wed Sep 15 12:17:15 2010
@@ -0,0 +1,128 @@
+/* header created automatically with -DGEN_TREES_H */
+
+local const ct_data static_ltree[L_CODES+2] = {
+{{ 12},{ 8}}, {{140},{ 8}}, {{ 76},{ 8}}, {{204},{ 8}}, {{ 44},{ 8}},
+{{172},{ 8}}, {{108},{ 8}}, {{236},{ 8}}, {{ 28},{ 8}}, {{156},{ 8}},
+{{ 92},{ 8}}, {{220},{ 8}}, {{ 60},{ 8}}, {{188},{ 8}}, {{124},{ 8}},
+{{252},{ 8}}, {{ 2},{ 8}}, {{130},{ 8}}, {{ 66},{ 8}}, {{194},{ 8}},
+{{ 34},{ 8}}, {{162},{ 8}}, {{ 98},{ 8}}, {{226},{ 8}}, {{ 18},{ 8}},
+{{146},{ 8}}, {{ 82},{ 8}}, {{210},{ 8}}, {{ 50},{ 8}}, {{178},{ 8}},
+{{114},{ 8}}, {{242},{ 8}}, {{ 10},{ 8}}, {{138},{ 8}}, {{ 74},{ 8}},
+{{202},{ 8}}, {{ 42},{ 8}}, {{170},{ 8}}, {{106},{ 8}}, {{234},{ 8}},
+{{ 26},{ 8}}, {{154},{ 8}}, {{ 90},{ 8}}, {{218},{ 8}}, {{ 58},{ 8}},
+{{186},{ 8}}, {{122},{ 8}}, {{250},{ 8}}, {{ 6},{ 8}}, {{134},{ 8}},
+{{ 70},{ 8}}, {{198},{ 8}}, {{ 38},{ 8}}, {{166},{ 8}}, {{102},{ 8}},
+{{230},{ 8}}, {{ 22},{ 8}}, {{150},{ 8}}, {{ 86},{ 8}}, {{214},{ 8}},
+{{ 54},{ 8}}, {{182},{ 8}}, {{118},{ 8}}, {{246},{ 8}}, {{ 14},{ 8}},
+{{142},{ 8}}, {{ 78},{ 8}}, {{206},{ 8}}, {{ 46},{ 8}}, {{174},{ 8}},
+{{110},{ 8}}, {{238},{ 8}}, {{ 30},{ 8}}, {{158},{ 8}}, {{ 94},{ 8}},
+{{222},{ 8}}, {{ 62},{ 8}}, {{190},{ 8}}, {{126},{ 8}}, {{254},{ 8}},
+{{ 1},{ 8}}, {{129},{ 8}}, {{ 65},{ 8}}, {{193},{ 8}}, {{ 33},{ 8}},
+{{161},{ 8}}, {{ 97},{ 8}}, {{225},{ 8}}, {{ 17},{ 8}}, {{145},{ 8}},
+{{ 81},{ 8}}, {{209},{ 8}}, {{ 49},{ 8}}, {{177},{ 8}}, {{113},{ 8}},
+{{241},{ 8}}, {{ 9},{ 8}}, {{137},{ 8}}, {{ 73},{ 8}}, {{201},{ 8}},
+{{ 41},{ 8}}, {{169},{ 8}}, {{105},{ 8}}, {{233},{ 8}}, {{ 25},{ 8}},
+{{153},{ 8}}, {{ 89},{ 8}}, {{217},{ 8}}, {{ 57},{ 8}}, {{185},{ 8}},
+{{121},{ 8}}, {{249},{ 8}}, {{ 5},{ 8}}, {{133},{ 8}}, {{ 69},{ 8}},
+{{197},{ 8}}, {{ 37},{ 8}}, {{165},{ 8}}, {{101},{ 8}}, {{229},{ 8}},
+{{ 21},{ 8}}, {{149},{ 8}}, {{ 85},{ 8}}, {{213},{ 8}}, {{ 53},{ 8}},
+{{181},{ 8}}, {{117},{ 8}}, {{245},{ 8}}, {{ 13},{ 8}}, {{141},{ 8}},
+{{ 77},{ 8}}, {{205},{ 8}}, {{ 45},{ 8}}, {{173},{ 8}}, {{109},{ 8}},
+{{237},{ 8}}, {{ 29},{ 8}}, {{157},{ 8}}, {{ 93},{ 8}}, {{221},{ 8}},
+{{ 61},{ 8}}, {{189},{ 8}}, {{125},{ 8}}, {{253},{ 8}}, {{ 19},{ 9}},
+{{275},{ 9}}, {{147},{ 9}}, {{403},{ 9}}, {{ 83},{ 9}}, {{339},{ 9}},
+{{211},{ 9}}, {{467},{ 9}}, {{ 51},{ 9}}, {{307},{ 9}}, {{179},{ 9}},
+{{435},{ 9}}, {{115},{ 9}}, {{371},{ 9}}, {{243},{ 9}}, {{499},{ 9}},
+{{ 11},{ 9}}, {{267},{ 9}}, {{139},{ 9}}, {{395},{ 9}}, {{ 75},{ 9}},
+{{331},{ 9}}, {{203},{ 9}}, {{459},{ 9}}, {{ 43},{ 9}}, {{299},{ 9}},
+{{171},{ 9}}, {{427},{ 9}}, {{107},{ 9}}, {{363},{ 9}}, {{235},{ 9}},
+{{491},{ 9}}, {{ 27},{ 9}}, {{283},{ 9}}, {{155},{ 9}}, {{411},{ 9}},
+{{ 91},{ 9}}, {{347},{ 9}}, {{219},{ 9}}, {{475},{ 9}}, {{ 59},{ 9}},
+{{315},{ 9}}, {{187},{ 9}}, {{443},{ 9}}, {{123},{ 9}}, {{379},{ 9}},
+{{251},{ 9}}, {{507},{ 9}}, {{ 7},{ 9}}, {{263},{ 9}}, {{135},{ 9}},
+{{391},{ 9}}, {{ 71},{ 9}}, {{327},{ 9}}, {{199},{ 9}}, {{455},{ 9}},
+{{ 39},{ 9}}, {{295},{ 9}}, {{167},{ 9}}, {{423},{ 9}}, {{103},{ 9}},
+{{359},{ 9}}, {{231},{ 9}}, {{487},{ 9}}, {{ 23},{ 9}}, {{279},{ 9}},
+{{151},{ 9}}, {{407},{ 9}}, {{ 87},{ 9}}, {{343},{ 9}}, {{215},{ 9}},
+{{471},{ 9}}, {{ 55},{ 9}}, {{311},{ 9}}, {{183},{ 9}}, {{439},{ 9}},
+{{119},{ 9}}, {{375},{ 9}}, {{247},{ 9}}, {{503},{ 9}}, {{ 15},{ 9}},
+{{271},{ 9}}, {{143},{ 9}}, {{399},{ 9}}, {{ 79},{ 9}}, {{335},{ 9}},
+{{207},{ 9}}, {{463},{ 9}}, {{ 47},{ 9}}, {{303},{ 9}}, {{175},{ 9}},
+{{431},{ 9}}, {{111},{ 9}}, {{367},{ 9}}, {{239},{ 9}}, {{495},{ 9}},
+{{ 31},{ 9}}, {{287},{ 9}}, {{159},{ 9}}, {{415},{ 9}}, {{ 95},{ 9}},
+{{351},{ 9}}, {{223},{ 9}}, {{479},{ 9}}, {{ 63},{ 9}}, {{319},{ 9}},
+{{191},{ 9}}, {{447},{ 9}}, {{127},{ 9}}, {{383},{ 9}}, {{255},{ 9}},
+{{511},{ 9}}, {{ 0},{ 7}}, {{ 64},{ 7}}, {{ 32},{ 7}}, {{ 96},{ 7}},
+{{ 16},{ 7}}, {{ 80},{ 7}}, {{ 48},{ 7}}, {{112},{ 7}}, {{ 8},{ 7}},
+{{ 72},{ 7}}, {{ 40},{ 7}}, {{104},{ 7}}, {{ 24},{ 7}}, {{ 88},{ 7}},
+{{ 56},{ 7}}, {{120},{ 7}}, {{ 4},{ 7}}, {{ 68},{ 7}}, {{ 36},{ 7}},
+{{100},{ 7}}, {{ 20},{ 7}}, {{ 84},{ 7}}, {{ 52},{ 7}}, {{116},{ 7}},
+{{ 3},{ 8}}, {{131},{ 8}}, {{ 67},{ 8}}, {{195},{ 8}}, {{ 35},{ 8}},
+{{163},{ 8}}, {{ 99},{ 8}}, {{227},{ 8}}
+};
+
+local const ct_data static_dtree[D_CODES] = {
+{{ 0},{ 5}}, {{16},{ 5}}, {{ 8},{ 5}}, {{24},{ 5}}, {{ 4},{ 5}},
+{{20},{ 5}}, {{12},{ 5}}, {{28},{ 5}}, {{ 2},{ 5}}, {{18},{ 5}},
+{{10},{ 5}}, {{26},{ 5}}, {{ 6},{ 5}}, {{22},{ 5}}, {{14},{ 5}},
+{{30},{ 5}}, {{ 1},{ 5}}, {{17},{ 5}}, {{ 9},{ 5}}, {{25},{ 5}},
+{{ 5},{ 5}}, {{21},{ 5}}, {{13},{ 5}}, {{29},{ 5}}, {{ 3},{ 5}},
+{{19},{ 5}}, {{11},{ 5}}, {{27},{ 5}}, {{ 7},{ 5}}, {{23},{ 5}}
+};
+
+const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {
+ 0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8,
+ 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10,
+10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
+11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
+12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13,
+13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
+13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
+14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15,
+15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
+15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17,
+18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22,
+23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
+26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
+27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
+27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
+28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
+28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
+28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
+29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
+29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
+29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
+};
+
+const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
+13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
+17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
+19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
+21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
+22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
+23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
+25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
+25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
+26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
+26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
+27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28
+};
+
+local const int base_length[LENGTH_CODES] = {
+0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
+64, 80, 96, 112, 128, 160, 192, 224, 0
+};
+
+local const int base_dist[D_CODES] = {
+ 0, 1, 2, 3, 4, 6, 8, 12, 16, 24,
+ 32, 48, 64, 96, 128, 192, 256, 384, 512, 768,
+ 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576
+};
+
Propchange: labs/axmake/trunk/src/libuc++/srclib/zlib/trees.h
------------------------------------------------------------------------------
svn:eol-style = native
Added: labs/axmake/trunk/src/libuc++/srclib/zlib/uncompr.c
URL: http://svn.apache.org/viewvc/labs/axmake/trunk/src/libuc%2B%2B/srclib/zlib/uncompr.c?rev=997302&view=auto
==============================================================================
--- labs/axmake/trunk/src/libuc++/srclib/zlib/uncompr.c (added)
+++ labs/axmake/trunk/src/libuc++/srclib/zlib/uncompr.c Wed Sep 15 12:17:15 2010
@@ -0,0 +1,59 @@
+/* uncompr.c -- decompress a memory buffer
+ * Copyright (C) 1995-2003, 2010 Jean-loup Gailly.
+ * For conditions of distribution and use, see copyright notice in zlib.h
+ */
+
+/* @(#) $Id$ */
+
+#define ZLIB_INTERNAL
+#include "zlib.h"
+
+/* ===========================================================================
+ Decompresses the source buffer into the destination buffer. sourceLen is
+ the byte length of the source buffer. Upon entry, destLen is the total
+ size of the destination buffer, which must be large enough to hold the
+ entire uncompressed data. (The size of the uncompressed data must have
+ been saved previously by the compressor and transmitted to the decompressor
+ by some mechanism outside the scope of this compression library.)
+ Upon exit, destLen is the actual size of the compressed buffer.
+
+ uncompress returns Z_OK if success, Z_MEM_ERROR if there was not
+ enough memory, Z_BUF_ERROR if there was not enough room in the output
+ buffer, or Z_DATA_ERROR if the input data was corrupted.
+*/
+int ZEXPORT uncompress (dest, destLen, source, sourceLen)
+ Bytef *dest;
+ uLongf *destLen;
+ const Bytef *source;
+ uLong sourceLen;
+{
+ z_stream stream;
+ int err;
+
+ stream.next_in = (Bytef*)source;
+ stream.avail_in = (uInt)sourceLen;
+ /* Check for source > 64K on 16-bit machine: */
+ if ((uLong)stream.avail_in != sourceLen) return Z_BUF_ERROR;
+
+ stream.next_out = dest;
+ stream.avail_out = (uInt)*destLen;
+ if ((uLong)stream.avail_out != *destLen) return Z_BUF_ERROR;
+
+ stream.zalloc = (alloc_func)0;
+ stream.zfree = (free_func)0;
+
+ err = inflateInit(&stream);
+ if (err != Z_OK) return err;
+
+ err = inflate(&stream, Z_FINISH);
+ if (err != Z_STREAM_END) {
+ inflateEnd(&stream);
+ if (err == Z_NEED_DICT || (err == Z_BUF_ERROR && stream.avail_in == 0))
+ return Z_DATA_ERROR;
+ return err;
+ }
+ *destLen = stream.total_out;
+
+ err = inflateEnd(&stream);
+ return err;
+}
Propchange: labs/axmake/trunk/src/libuc++/srclib/zlib/uncompr.c
------------------------------------------------------------------------------
svn:eol-style = native
Added: labs/axmake/trunk/src/libuc++/srclib/zlib/unix/amd64-match.S
URL: http://svn.apache.org/viewvc/labs/axmake/trunk/src/libuc%2B%2B/srclib/zlib/unix/amd64-match.S?rev=997302&view=auto
==============================================================================
--- labs/axmake/trunk/src/libuc++/srclib/zlib/unix/amd64-match.S (added)
+++ labs/axmake/trunk/src/libuc++/srclib/zlib/unix/amd64-match.S Wed Sep 15 12:17:15 2010
@@ -0,0 +1,452 @@
+/*
+ * match.S -- optimized version of longest_match()
+ * based on the similar work by Gilles Vollant, and Brian Raiter, written 1998
+ *
+ * This is free software; you can redistribute it and/or modify it
+ * under the terms of the BSD License. Use by owners of Che Guevarra
+ * parafernalia is prohibited, where possible, and highly discouraged
+ * elsewhere.
+ */
+
+#ifndef NO_UNDERLINE
+# define match_init _match_init
+# define longest_match _longest_match
+#endif
+
+#define scanend ebx
+#define scanendw bx
+#define chainlenwmask edx /* high word: current chain len low word: s->wmask */
+#define curmatch rsi
+#define curmatchd esi
+#define windowbestlen r8
+#define scanalign r9
+#define scanalignd r9d
+#define window r10
+#define bestlen r11
+#define bestlend r11d
+#define scanstart r12d
+#define scanstartw r12w
+#define scan r13
+#define nicematch r14d
+#define limit r15
+#define limitd r15d
+#define prev rcx
+
+/*
+ * The 258 is a "magic number, not a parameter -- changing it
+ * breaks the hell loose
+ */
+#define MAX_MATCH (258)
+#define MIN_MATCH (3)
+#define MIN_LOOKAHEAD (MAX_MATCH + MIN_MATCH + 1)
+#define MAX_MATCH_8 ((MAX_MATCH + 7) & ~7)
+
+/* stack frame offsets */
+#define LocalVarsSize (112)
+#define _chainlenwmask ( 8-LocalVarsSize)(%rsp)
+#define _windowbestlen (16-LocalVarsSize)(%rsp)
+#define save_r14 (24-LocalVarsSize)(%rsp)
+#define save_rsi (32-LocalVarsSize)(%rsp)
+#define save_rbx (40-LocalVarsSize)(%rsp)
+#define save_r12 (56-LocalVarsSize)(%rsp)
+#define save_r13 (64-LocalVarsSize)(%rsp)
+#define save_r15 (80-LocalVarsSize)(%rsp)
+
+
+.globl match_init, longest_match
+
+/*
+ * On AMD64 the first argument of a function (in our case -- the pointer to
+ * deflate_state structure) is passed in %rdi, hence our offsets below are
+ * all off of that.
+ */
+
+/* you can check the structure offset by running
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "deflate.h"
+
+void print_depl()
+{
+deflate_state ds;
+deflate_state *s=&ds;
+printf("size pointer=%u\n",(int)sizeof(void*));
+
+printf("#define dsWSize (%3u)(%%rdi)\n",(int)(((char*)&(s->w_size))-((char*)s)));
+printf("#define dsWMask (%3u)(%%rdi)\n",(int)(((char*)&(s->w_mask))-((char*)s)));
+printf("#define dsWindow (%3u)(%%rdi)\n",(int)(((char*)&(s->window))-((char*)s)));
+printf("#define dsPrev (%3u)(%%rdi)\n",(int)(((char*)&(s->prev))-((char*)s)));
+printf("#define dsMatchLen (%3u)(%%rdi)\n",(int)(((char*)&(s->match_length))-((char*)s)));
+printf("#define dsPrevMatch (%3u)(%%rdi)\n",(int)(((char*)&(s->prev_match))-((char*)s)));
+printf("#define dsStrStart (%3u)(%%rdi)\n",(int)(((char*)&(s->strstart))-((char*)s)));
+printf("#define dsMatchStart (%3u)(%%rdi)\n",(int)(((char*)&(s->match_start))-((char*)s)));
+printf("#define dsLookahead (%3u)(%%rdi)\n",(int)(((char*)&(s->lookahead))-((char*)s)));
+printf("#define dsPrevLen (%3u)(%%rdi)\n",(int)(((char*)&(s->prev_length))-((char*)s)));
+printf("#define dsMaxChainLen (%3u)(%%rdi)\n",(int)(((char*)&(s->max_chain_length))-((char*)s)));
+printf("#define dsGoodMatch (%3u)(%%rdi)\n",(int)(((char*)&(s->good_match))-((char*)s)));
+printf("#define dsNiceMatch (%3u)(%%rdi)\n",(int)(((char*)&(s->nice_match))-((char*)s)));
+}
+
+*/
+
+
+/*
+ to compile for XCode 3.2 on MacOSX x86_64
+ - run "gcc -g -c -DXCODE_MAC_X64_STRUCTURE amd64-match.S"
+ */
+
+
+#ifndef CURRENT_LINX_XCODE_MAC_X64_STRUCTURE
+#define dsWSize ( 68)(%rdi)
+#define dsWMask ( 76)(%rdi)
+#define dsWindow ( 80)(%rdi)
+#define dsPrev ( 96)(%rdi)
+#define dsMatchLen (144)(%rdi)
+#define dsPrevMatch (148)(%rdi)
+#define dsStrStart (156)(%rdi)
+#define dsMatchStart (160)(%rdi)
+#define dsLookahead (164)(%rdi)
+#define dsPrevLen (168)(%rdi)
+#define dsMaxChainLen (172)(%rdi)
+#define dsGoodMatch (188)(%rdi)
+#define dsNiceMatch (192)(%rdi)
+
+#else
+
+#ifndef STRUCT_OFFSET
+# define STRUCT_OFFSET (0)
+#endif
+
+
+#define dsWSize ( 56 + STRUCT_OFFSET)(%rdi)
+#define dsWMask ( 64 + STRUCT_OFFSET)(%rdi)
+#define dsWindow ( 72 + STRUCT_OFFSET)(%rdi)
+#define dsPrev ( 88 + STRUCT_OFFSET)(%rdi)
+#define dsMatchLen (136 + STRUCT_OFFSET)(%rdi)
+#define dsPrevMatch (140 + STRUCT_OFFSET)(%rdi)
+#define dsStrStart (148 + STRUCT_OFFSET)(%rdi)
+#define dsMatchStart (152 + STRUCT_OFFSET)(%rdi)
+#define dsLookahead (156 + STRUCT_OFFSET)(%rdi)
+#define dsPrevLen (160 + STRUCT_OFFSET)(%rdi)
+#define dsMaxChainLen (164 + STRUCT_OFFSET)(%rdi)
+#define dsGoodMatch (180 + STRUCT_OFFSET)(%rdi)
+#define dsNiceMatch (184 + STRUCT_OFFSET)(%rdi)
+
+#endif
+
+
+
+
+.text
+
+/* uInt longest_match(deflate_state *deflatestate, IPos curmatch) */
+
+longest_match:
+/*
+ * Retrieve the function arguments. %curmatch will hold cur_match
+ * throughout the entire function (passed via rsi on amd64).
+ * rdi will hold the pointer to the deflate_state (first arg on amd64)
+ */
+ mov %rsi, save_rsi
+ mov %rbx, save_rbx
+ mov %r12, save_r12
+ mov %r13, save_r13
+ mov %r14, save_r14
+ mov %r15, save_r15
+
+/* uInt wmask = s->w_mask; */
+/* unsigned chain_length = s->max_chain_length; */
+/* if (s->prev_length >= s->good_match) { */
+/* chain_length >>= 2; */
+/* } */
+
+ movl dsPrevLen, %eax
+ movl dsGoodMatch, %ebx
+ cmpl %ebx, %eax
+ movl dsWMask, %eax
+ movl dsMaxChainLen, %chainlenwmask
+ jl LastMatchGood
+ shrl $2, %chainlenwmask
+LastMatchGood:
+
+/* chainlen is decremented once beforehand so that the function can */
+/* use the sign flag instead of the zero flag for the exit test. */
+/* It is then shifted into the high word, to make room for the wmask */
+/* value, which it will always accompany. */
+
+ decl %chainlenwmask
+ shll $16, %chainlenwmask
+ orl %eax, %chainlenwmask
+
+/* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; */
+
+ movl dsNiceMatch, %eax
+ movl dsLookahead, %ebx
+ cmpl %eax, %ebx
+ jl LookaheadLess
+ movl %eax, %ebx
+LookaheadLess: movl %ebx, %nicematch
+
+/* register Bytef *scan = s->window + s->strstart; */
+
+ mov dsWindow, %window
+ movl dsStrStart, %limitd
+ lea (%limit, %window), %scan
+
+/* Determine how many bytes the scan ptr is off from being */
+/* dword-aligned. */
+
+ mov %scan, %scanalign
+ negl %scanalignd
+ andl $3, %scanalignd
+
+/* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */
+/* s->strstart - (IPos)MAX_DIST(s) : NIL; */
+
+ movl dsWSize, %eax
+ subl $MIN_LOOKAHEAD, %eax
+ xorl %ecx, %ecx
+ subl %eax, %limitd
+ cmovng %ecx, %limitd
+
+/* int best_len = s->prev_length; */
+
+ movl dsPrevLen, %bestlend
+
+/* Store the sum of s->window + best_len in %windowbestlen locally, and in memory. */
+
+ lea (%window, %bestlen), %windowbestlen
+ mov %windowbestlen, _windowbestlen
+
+/* register ush scan_start = *(ushf*)scan; */
+/* register ush scan_end = *(ushf*)(scan+best_len-1); */
+/* Posf *prev = s->prev; */
+
+ movzwl (%scan), %scanstart
+ movzwl -1(%scan, %bestlen), %scanend
+ mov dsPrev, %prev
+
+/* Jump into the main loop. */
+
+ movl %chainlenwmask, _chainlenwmask
+ jmp LoopEntry
+
+.balign 16
+
+/* do {
+ * match = s->window + cur_match;
+ * if (*(ushf*)(match+best_len-1) != scan_end ||
+ * *(ushf*)match != scan_start) continue;
+ * [...]
+ * } while ((cur_match = prev[cur_match & wmask]) > limit
+ * && --chain_length != 0);
+ *
+ * Here is the inner loop of the function. The function will spend the
+ * majority of its time in this loop, and majority of that time will
+ * be spent in the first ten instructions.
+ */
+LookupLoop:
+ andl %chainlenwmask, %curmatchd
+ movzwl (%prev, %curmatch, 2), %curmatchd
+ cmpl %limitd, %curmatchd
+ jbe LeaveNow
+ subl $0x00010000, %chainlenwmask
+ js LeaveNow
+LoopEntry: cmpw -1(%windowbestlen, %curmatch), %scanendw
+ jne LookupLoop
+ cmpw %scanstartw, (%window, %curmatch)
+ jne LookupLoop
+
+/* Store the current value of chainlen. */
+ movl %chainlenwmask, _chainlenwmask
+
+/* %scan is the string under scrutiny, and %prev to the string we */
+/* are hoping to match it up with. In actuality, %esi and %edi are */
+/* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is */
+/* initialized to -(MAX_MATCH_8 - scanalign). */
+
+ mov $(-MAX_MATCH_8), %rdx
+ lea (%curmatch, %window), %windowbestlen
+ lea MAX_MATCH_8(%windowbestlen, %scanalign), %windowbestlen
+ lea MAX_MATCH_8(%scan, %scanalign), %prev
+
+/* the prefetching below makes very little difference... */
+ prefetcht1 (%windowbestlen, %rdx)
+ prefetcht1 (%prev, %rdx)
+
+/*
+ * Test the strings for equality, 8 bytes at a time. At the end,
+ * adjust %rdx so that it is offset to the exact byte that mismatched.
+ *
+ * It should be confessed that this loop usually does not represent
+ * much of the total running time. Replacing it with a more
+ * straightforward "rep cmpsb" would not drastically degrade
+ * performance -- unrolling it, for example, makes no difference.
+ */
+
+#undef USE_SSE /* works, but is 6-7% slower, than non-SSE... */
+
+LoopCmps:
+#ifdef USE_SSE
+ /* Preload the SSE registers */
+ movdqu (%windowbestlen, %rdx), %xmm1
+ movdqu (%prev, %rdx), %xmm2
+ pcmpeqb %xmm2, %xmm1
+ movdqu 16(%windowbestlen, %rdx), %xmm3
+ movdqu 16(%prev, %rdx), %xmm4
+ pcmpeqb %xmm4, %xmm3
+ movdqu 32(%windowbestlen, %rdx), %xmm5
+ movdqu 32(%prev, %rdx), %xmm6
+ pcmpeqb %xmm6, %xmm5
+ movdqu 48(%windowbestlen, %rdx), %xmm7
+ movdqu 48(%prev, %rdx), %xmm8
+ pcmpeqb %xmm8, %xmm7
+
+ /* Check the comparisions' results */
+ pmovmskb %xmm1, %rax
+ notw %ax
+ bsfw %ax, %ax
+ jnz LeaveLoopCmps
+
+ /* this is the only iteration of the loop with a possibility of having
+ incremented rdx by 0x108 (each loop iteration add 16*4 = 0x40
+ and (0x40*4)+8=0x108 */
+ add $8, %rdx
+ jz LenMaximum
+ add $8, %rdx
+
+
+ pmovmskb %xmm3, %rax
+ notw %ax
+ bsfw %ax, %ax
+ jnz LeaveLoopCmps
+
+
+ add $16, %rdx
+
+
+ pmovmskb %xmm5, %rax
+ notw %ax
+ bsfw %ax, %ax
+ jnz LeaveLoopCmps
+
+ add $16, %rdx
+
+
+ pmovmskb %xmm7, %rax
+ notw %ax
+ bsfw %ax, %ax
+ jnz LeaveLoopCmps
+
+ add $16, %rdx
+
+ jmp LoopCmps
+LeaveLoopCmps: add %rax, %rdx
+#else
+ mov (%windowbestlen, %rdx), %rax
+ xor (%prev, %rdx), %rax
+ jnz LeaveLoopCmps
+
+ mov 8(%windowbestlen, %rdx), %rax
+ xor 8(%prev, %rdx), %rax
+ jnz LeaveLoopCmps8
+
+ mov 16(%windowbestlen, %rdx), %rax
+ xor 16(%prev, %rdx), %rax
+ jnz LeaveLoopCmps16
+
+ add $24, %rdx
+ jnz LoopCmps
+ jmp LenMaximum
+# if 0
+/*
+ * This three-liner is tantalizingly simple, but bsf is a slow instruction,
+ * and the complicated alternative down below is quite a bit faster. Sad...
+ */
+
+LeaveLoopCmps: bsf %rax, %rax /* find the first non-zero bit */
+ shrl $3, %eax /* divide by 8 to get the byte */
+ add %rax, %rdx
+# else
+LeaveLoopCmps16:
+ add $8, %rdx
+LeaveLoopCmps8:
+ add $8, %rdx
+LeaveLoopCmps: testl $0xFFFFFFFF, %eax /* Check the first 4 bytes */
+ jnz Check16
+ add $4, %rdx
+ shr $32, %rax
+Check16: testw $0xFFFF, %ax
+ jnz LenLower
+ add $2, %rdx
+ shrl $16, %eax
+LenLower: subb $1, %al
+ adc $0, %rdx
+# endif
+#endif
+
+/* Calculate the length of the match. If it is longer than MAX_MATCH, */
+/* then automatically accept it as the best possible match and leave. */
+
+ lea (%prev, %rdx), %rax
+ sub %scan, %rax
+ cmpl $MAX_MATCH, %eax
+ jge LenMaximum
+
+/* If the length of the match is not longer than the best match we */
+/* have so far, then forget it and return to the lookup loop. */
+
+ cmpl %bestlend, %eax
+ jg LongerMatch
+ mov _windowbestlen, %windowbestlen
+ mov dsPrev, %prev
+ movl _chainlenwmask, %edx
+ jmp LookupLoop
+
+/* s->match_start = cur_match; */
+/* best_len = len; */
+/* if (len >= nice_match) break; */
+/* scan_end = *(ushf*)(scan+best_len-1); */
+
+LongerMatch:
+ movl %eax, %bestlend
+ movl %curmatchd, dsMatchStart
+ cmpl %nicematch, %eax
+ jge LeaveNow
+
+ lea (%window, %bestlen), %windowbestlen
+ mov %windowbestlen, _windowbestlen
+
+ movzwl -1(%scan, %rax), %scanend
+ mov dsPrev, %prev
+ movl _chainlenwmask, %chainlenwmask
+ jmp LookupLoop
+
+/* Accept the current string, with the maximum possible length. */
+
+LenMaximum:
+ movl $MAX_MATCH, %bestlend
+ movl %curmatchd, dsMatchStart
+
+/* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */
+/* return s->lookahead; */
+
+LeaveNow:
+ movl dsLookahead, %eax
+ cmpl %eax, %bestlend
+ cmovngl %bestlend, %eax
+LookaheadRet:
+
+/* Restore the registers and return from whence we came. */
+
+ mov save_rsi, %rsi
+ mov save_rbx, %rbx
+ mov save_r12, %r12
+ mov save_r13, %r13
+ mov save_r14, %r14
+ mov save_r15, %r15
+
+ ret
+
+match_init: ret
Added: labs/axmake/trunk/src/libuc++/srclib/zlib/unix/gvmat64.S
URL: http://svn.apache.org/viewvc/labs/axmake/trunk/src/libuc%2B%2B/srclib/zlib/unix/gvmat64.S?rev=997302&view=auto
==============================================================================
--- labs/axmake/trunk/src/libuc++/srclib/zlib/unix/gvmat64.S (added)
+++ labs/axmake/trunk/src/libuc++/srclib/zlib/unix/gvmat64.S Wed Sep 15 12:17:15 2010
@@ -0,0 +1,574 @@
+/*
+;uInt longest_match_x64(
+; deflate_state *s,
+; IPos cur_match); // current match
+
+; gvmat64.S -- Asm portion of the optimized longest_match for 32 bits x86_64
+; (AMD64 on Athlon 64, Opteron, Phenom
+; and Intel EM64T on Pentium 4 with EM64T, Pentium D, Core 2 Duo, Core I5/I7)
+; this file is translation from gvmat64.asm to GCC 4.x (for Linux, Mac XCode)
+; Copyright (C) 1995-2010 Jean-loup Gailly, Brian Raiter and Gilles Vollant.
+;
+; File written by Gilles Vollant, by converting to assembly the longest_match
+; from Jean-loup Gailly in deflate.c of zLib and infoZip zip.
+; and by taking inspiration on asm686 with masm, optimised assembly code
+; from Brian Raiter, written 1998
+;
+; This software is provided 'as-is', without any express or implied
+; warranty. In no event will the authors be held liable for any damages
+; arising from the use of this software.
+;
+; Permission is granted to anyone to use this software for any purpose,
+; including commercial applications, and to alter it and redistribute it
+; freely, subject to the following restrictions:
+;
+; 1. The origin of this software must not be misrepresented; you must not
+; claim that you wrote the original software. If you use this software
+; in a product, an acknowledgment in the product documentation would be
+; appreciated but is not required.
+; 2. Altered source versions must be plainly marked as such, and must not be
+; misrepresented as being the original software
+; 3. This notice may not be removed or altered from any source distribution.
+;
+; http://www.zlib.net
+; http://www.winimage.com/zLibDll
+; http://www.muppetlabs.com/~breadbox/software/assembly.html
+;
+; to compile this file for zLib, I use option:
+; gcc -c -arch x86_64 gvmat64.S
+
+
+;uInt longest_match(s, cur_match)
+; deflate_state *s;
+; IPos cur_match; // current match /
+;
+; with XCode for Mac, I had strange error with some jump on intel syntax
+; this is why BEFORE_JMP and AFTER_JMP are used
+ */
+
+
+#define BEFORE_JMP .att_syntax
+#define AFTER_JMP .intel_syntax noprefix
+
+#ifndef NO_UNDERLINE
+# define match_init _match_init
+# define longest_match _longest_match
+#endif
+
+.intel_syntax noprefix
+
+.globl match_init, longest_match
+.text
+longest_match:
+
+
+
+#define LocalVarsSize 96
+/*
+; register used : rax,rbx,rcx,rdx,rsi,rdi,r8,r9,r10,r11,r12
+; free register : r14,r15
+; register can be saved : rsp
+*/
+
+#define chainlenwmask (rsp + 8 - LocalVarsSize)
+#define nicematch (rsp + 16 - LocalVarsSize)
+
+#define save_rdi (rsp + 24 - LocalVarsSize)
+#define save_rsi (rsp + 32 - LocalVarsSize)
+#define save_rbx (rsp + 40 - LocalVarsSize)
+#define save_rbp (rsp + 48 - LocalVarsSize)
+#define save_r12 (rsp + 56 - LocalVarsSize)
+#define save_r13 (rsp + 64 - LocalVarsSize)
+#define save_r14 (rsp + 72 - LocalVarsSize)
+#define save_r15 (rsp + 80 - LocalVarsSize)
+
+
+/*
+; all the +4 offsets are due to the addition of pending_buf_size (in zlib
+; in the deflate_state structure since the asm code was first written
+; (if you compile with zlib 1.0.4 or older, remove the +4).
+; Note : these value are good with a 8 bytes boundary pack structure
+*/
+
+#define MAX_MATCH 258
+#define MIN_MATCH 3
+#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
+
+/*
+;;; Offsets for fields in the deflate_state structure. These numbers
+;;; are calculated from the definition of deflate_state, with the
+;;; assumption that the compiler will dword-align the fields. (Thus,
+;;; changing the definition of deflate_state could easily cause this
+;;; program to crash horribly, without so much as a warning at
+;;; compile time. Sigh.)
+
+; all the +zlib1222add offsets are due to the addition of fields
+; in zlib in the deflate_state structure since the asm code was first written
+; (if you compile with zlib 1.0.4 or older, use "zlib1222add equ (-4)").
+; (if you compile with zlib between 1.0.5 and 1.2.2.1, use "zlib1222add equ 0").
+; if you compile with zlib 1.2.2.2 or later , use "zlib1222add equ 8").
+*/
+
+
+
+/* you can check the structure offset by running
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "deflate.h"
+
+void print_depl()
+{
+deflate_state ds;
+deflate_state *s=&ds;
+printf("size pointer=%u\n",(int)sizeof(void*));
+
+printf("#define dsWSize %u\n",(int)(((char*)&(s->w_size))-((char*)s)));
+printf("#define dsWMask %u\n",(int)(((char*)&(s->w_mask))-((char*)s)));
+printf("#define dsWindow %u\n",(int)(((char*)&(s->window))-((char*)s)));
+printf("#define dsPrev %u\n",(int)(((char*)&(s->prev))-((char*)s)));
+printf("#define dsMatchLen %u\n",(int)(((char*)&(s->match_length))-((char*)s)));
+printf("#define dsPrevMatch %u\n",(int)(((char*)&(s->prev_match))-((char*)s)));
+printf("#define dsStrStart %u\n",(int)(((char*)&(s->strstart))-((char*)s)));
+printf("#define dsMatchStart %u\n",(int)(((char*)&(s->match_start))-((char*)s)));
+printf("#define dsLookahead %u\n",(int)(((char*)&(s->lookahead))-((char*)s)));
+printf("#define dsPrevLen %u\n",(int)(((char*)&(s->prev_length))-((char*)s)));
+printf("#define dsMaxChainLen %u\n",(int)(((char*)&(s->max_chain_length))-((char*)s)));
+printf("#define dsGoodMatch %u\n",(int)(((char*)&(s->good_match))-((char*)s)));
+printf("#define dsNiceMatch %u\n",(int)(((char*)&(s->nice_match))-((char*)s)));
+}
+*/
+
+#define dsWSize 68
+#define dsWMask 76
+#define dsWindow 80
+#define dsPrev 96
+#define dsMatchLen 144
+#define dsPrevMatch 148
+#define dsStrStart 156
+#define dsMatchStart 160
+#define dsLookahead 164
+#define dsPrevLen 168
+#define dsMaxChainLen 172
+#define dsGoodMatch 188
+#define dsNiceMatch 192
+
+#define window_size [ rcx + dsWSize]
+#define WMask [ rcx + dsWMask]
+#define window_ad [ rcx + dsWindow]
+#define prev_ad [ rcx + dsPrev]
+#define strstart [ rcx + dsStrStart]
+#define match_start [ rcx + dsMatchStart]
+#define Lookahead [ rcx + dsLookahead] //; 0ffffffffh on infozip
+#define prev_length [ rcx + dsPrevLen]
+#define max_chain_length [ rcx + dsMaxChainLen]
+#define good_match [ rcx + dsGoodMatch]
+#define nice_match [ rcx + dsNiceMatch]
+
+/*
+; windows:
+; parameter 1 in rcx(deflate state s), param 2 in rdx (cur match)
+
+; see http://weblogs.asp.net/oldnewthing/archive/2004/01/14/58579.aspx and
+; http://msdn.microsoft.com/library/en-us/kmarch/hh/kmarch/64bitAMD_8e951dd2-ee77-4728-8702-55ce4b5dd24a.xml.asp
+;
+; All registers must be preserved across the call, except for
+; rax, rcx, rdx, r8, r9, r10, and r11, which are scratch.
+
+;
+; gcc on macosx-linux:
+; see http://www.x86-64.org/documentation/abi-0.99.pdf
+; param 1 in rdi, param 2 in rsi
+; rbx, rsp, rbp, r12 to r15 must be preserved
+
+;;; Save registers that the compiler may be using, and adjust esp to
+;;; make room for our stack frame.
+
+
+;;; Retrieve the function arguments. r8d will hold cur_match
+;;; throughout the entire function. edx will hold the pointer to the
+;;; deflate_state structure during the function's setup (before
+;;; entering the main loop.
+
+; ms: parameter 1 in rcx (deflate_state* s), param 2 in edx -> r8 (cur match)
+; mac: param 1 in rdi, param 2 rsi
+; this clear high 32 bits of r8, which can be garbage in both r8 and rdx
+*/
+ mov [save_rbx],rbx
+ mov [save_rbp],rbp
+
+
+ mov rcx,rdi
+
+ mov r8d,esi
+
+
+ mov [save_r12],r12
+ mov [save_r13],r13
+ mov [save_r14],r14
+ mov [save_r15],r15
+
+
+//;;; uInt wmask = s->w_mask;
+//;;; unsigned chain_length = s->max_chain_length;
+//;;; if (s->prev_length >= s->good_match) {
+//;;; chain_length >>= 2;
+//;;; }
+
+
+ mov edi, prev_length
+ mov esi, good_match
+ mov eax, WMask
+ mov ebx, max_chain_length
+ cmp edi, esi
+ jl LastMatchGood
+ shr ebx, 2
+LastMatchGood:
+
+//;;; chainlen is decremented once beforehand so that the function can
+//;;; use the sign flag instead of the zero flag for the exit test.
+//;;; It is then shifted into the high word, to make room for the wmask
+//;;; value, which it will always accompany.
+
+ dec ebx
+ shl ebx, 16
+ or ebx, eax
+
+//;;; on zlib only
+//;;; if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
+
+
+
+ mov eax, nice_match
+ mov [chainlenwmask], ebx
+ mov r10d, Lookahead
+ cmp r10d, eax
+ cmovnl r10d, eax
+ mov [nicematch],r10d
+
+
+
+//;;; register Bytef *scan = s->window + s->strstart;
+ mov r10, window_ad
+ mov ebp, strstart
+ lea r13, [r10 + rbp]
+
+//;;; Determine how many bytes the scan ptr is off from being
+//;;; dword-aligned.
+
+ mov r9,r13
+ neg r13
+ and r13,3
+
+//;;; IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
+//;;; s->strstart - (IPos)MAX_DIST(s) : NIL;
+
+
+ mov eax, window_size
+ sub eax, MIN_LOOKAHEAD
+
+
+ xor edi,edi
+ sub ebp, eax
+
+ mov r11d, prev_length
+
+ cmovng ebp,edi
+
+//;;; int best_len = s->prev_length;
+
+
+//;;; Store the sum of s->window + best_len in esi locally, and in esi.
+
+ lea rsi,[r10+r11]
+
+//;;; register ush scan_start = *(ushf*)scan;
+//;;; register ush scan_end = *(ushf*)(scan+best_len-1);
+//;;; Posf *prev = s->prev;
+
+ movzx r12d,word ptr [r9]
+ movzx ebx, word ptr [r9 + r11 - 1]
+
+ mov rdi, prev_ad
+
+//;;; Jump into the main loop.
+
+ mov edx, [chainlenwmask]
+
+ cmp bx,word ptr [rsi + r8 - 1]
+ jz LookupLoopIsZero
+
+
+
+LookupLoop1:
+ and r8d, edx
+
+ movzx r8d, word ptr [rdi + r8*2]
+ cmp r8d, ebp
+ jbe LeaveNow
+
+
+
+ sub edx, 0x00010000
+ BEFORE_JMP
+ js LeaveNow
+ AFTER_JMP
+
+LoopEntry1:
+ cmp bx,word ptr [rsi + r8 - 1]
+ BEFORE_JMP
+ jz LookupLoopIsZero
+ AFTER_JMP
+
+LookupLoop2:
+ and r8d, edx
+
+ movzx r8d, word ptr [rdi + r8*2]
+ cmp r8d, ebp
+ BEFORE_JMP
+ jbe LeaveNow
+ AFTER_JMP
+ sub edx, 0x00010000
+ BEFORE_JMP
+ js LeaveNow
+ AFTER_JMP
+
+LoopEntry2:
+ cmp bx,word ptr [rsi + r8 - 1]
+ BEFORE_JMP
+ jz LookupLoopIsZero
+ AFTER_JMP
+
+LookupLoop4:
+ and r8d, edx
+
+ movzx r8d, word ptr [rdi + r8*2]
+ cmp r8d, ebp
+ BEFORE_JMP
+ jbe LeaveNow
+ AFTER_JMP
+ sub edx, 0x00010000
+ BEFORE_JMP
+ js LeaveNow
+ AFTER_JMP
+
+LoopEntry4:
+
+ cmp bx,word ptr [rsi + r8 - 1]
+ BEFORE_JMP
+ jnz LookupLoop1
+ jmp LookupLoopIsZero
+ AFTER_JMP
+/*
+;;; do {
+;;; match = s->window + cur_match;
+;;; if (*(ushf*)(match+best_len-1) != scan_end ||
+;;; *(ushf*)match != scan_start) continue;
+;;; [...]
+;;; } while ((cur_match = prev[cur_match & wmask]) > limit
+;;; && --chain_length != 0);
+;;;
+;;; Here is the inner loop of the function. The function will spend the
+;;; majority of its time in this loop, and majority of that time will
+;;; be spent in the first ten instructions.
+;;;
+;;; Within this loop:
+;;; ebx = scanend
+;;; r8d = curmatch
+;;; edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)
+;;; esi = windowbestlen - i.e., (window + bestlen)
+;;; edi = prev
+;;; ebp = limit
+*/
+.balign 16
+LookupLoop:
+ and r8d, edx
+
+ movzx r8d, word ptr [rdi + r8*2]
+ cmp r8d, ebp
+ BEFORE_JMP
+ jbe LeaveNow
+ AFTER_JMP
+ sub edx, 0x00010000
+ BEFORE_JMP
+ js LeaveNow
+ AFTER_JMP
+
+LoopEntry:
+
+ cmp bx,word ptr [rsi + r8 - 1]
+ BEFORE_JMP
+ jnz LookupLoop1
+ AFTER_JMP
+LookupLoopIsZero:
+ cmp r12w, word ptr [r10 + r8]
+ BEFORE_JMP
+ jnz LookupLoop1
+ AFTER_JMP
+
+
+//;;; Store the current value of chainlen.
+ mov [chainlenwmask], edx
+/*
+;;; Point edi to the string under scrutiny, and esi to the string we
+;;; are hoping to match it up with. In actuality, esi and edi are
+;;; both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and edx is
+;;; initialized to -(MAX_MATCH_8 - scanalign).
+*/
+ lea rsi,[r8+r10]
+ mov rdx, 0xfffffffffffffef8 //; -(MAX_MATCH_8)
+ lea rsi, [rsi + r13 + 0x0108] //;MAX_MATCH_8]
+ lea rdi, [r9 + r13 + 0x0108] //;MAX_MATCH_8]
+
+ prefetcht1 [rsi+rdx]
+ prefetcht1 [rdi+rdx]
+
+/*
+;;; Test the strings for equality, 8 bytes at a time. At the end,
+;;; adjust rdx so that it is offset to the exact byte that mismatched.
+;;;
+;;; We already know at this point that the first three bytes of the
+;;; strings match each other, and they can be safely passed over before
+;;; starting the compare loop. So what this code does is skip over 0-3
+;;; bytes, as much as necessary in order to dword-align the edi
+;;; pointer. (rsi will still be misaligned three times out of four.)
+;;;
+;;; It should be confessed that this loop usually does not represent
+;;; much of the total running time. Replacing it with a more
+;;; straightforward "rep cmpsb" would not drastically degrade
+;;; performance.
+*/
+
+LoopCmps:
+ mov rax, [rsi + rdx]
+ xor rax, [rdi + rdx]
+ jnz LeaveLoopCmps
+
+ mov rax, [rsi + rdx + 8]
+ xor rax, [rdi + rdx + 8]
+ jnz LeaveLoopCmps8
+
+
+ mov rax, [rsi + rdx + 8+8]
+ xor rax, [rdi + rdx + 8+8]
+ jnz LeaveLoopCmps16
+
+ add rdx,8+8+8
+
+ BEFORE_JMP
+ jnz LoopCmps
+ jmp LenMaximum
+ AFTER_JMP
+
+LeaveLoopCmps16: add rdx,8
+LeaveLoopCmps8: add rdx,8
+LeaveLoopCmps:
+
+ test eax, 0x0000FFFF
+ jnz LenLower
+
+ test eax,0xffffffff
+
+ jnz LenLower32
+
+ add rdx,4
+ shr rax,32
+ or ax,ax
+ BEFORE_JMP
+ jnz LenLower
+ AFTER_JMP
+
+LenLower32:
+ shr eax,16
+ add rdx,2
+
+LenLower:
+ sub al, 1
+ adc rdx, 0
+//;;; Calculate the length of the match. If it is longer than MAX_MATCH,
+//;;; then automatically accept it as the best possible match and leave.
+
+ lea rax, [rdi + rdx]
+ sub rax, r9
+ cmp eax, MAX_MATCH
+ BEFORE_JMP
+ jge LenMaximum
+ AFTER_JMP
+/*
+;;; If the length of the match is not longer than the best match we
+;;; have so far, then forget it and return to the lookup loop.
+;///////////////////////////////////
+*/
+ cmp eax, r11d
+ jg LongerMatch
+
+ lea rsi,[r10+r11]
+
+ mov rdi, prev_ad
+ mov edx, [chainlenwmask]
+ BEFORE_JMP
+ jmp LookupLoop
+ AFTER_JMP
+/*
+;;; s->match_start = cur_match;
+;;; best_len = len;
+;;; if (len >= nice_match) break;
+;;; scan_end = *(ushf*)(scan+best_len-1);
+*/
+LongerMatch:
+ mov r11d, eax
+ mov match_start, r8d
+ cmp eax, [nicematch]
+ BEFORE_JMP
+ jge LeaveNow
+ AFTER_JMP
+
+ lea rsi,[r10+rax]
+
+ movzx ebx, word ptr [r9 + rax - 1]
+ mov rdi, prev_ad
+ mov edx, [chainlenwmask]
+ BEFORE_JMP
+ jmp LookupLoop
+ AFTER_JMP
+
+//;;; Accept the current string, with the maximum possible length.
+
+LenMaximum:
+ mov r11d,MAX_MATCH
+ mov match_start, r8d
+
+//;;; if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
+//;;; return s->lookahead;
+
+LeaveNow:
+ mov eax, Lookahead
+ cmp r11d, eax
+ cmovng eax, r11d
+
+
+
+//;;; Restore the stack and return from whence we came.
+
+
+// mov rsi,[save_rsi]
+// mov rdi,[save_rdi]
+ mov rbx,[save_rbx]
+ mov rbp,[save_rbp]
+ mov r12,[save_r12]
+ mov r13,[save_r13]
+ mov r14,[save_r14]
+ mov r15,[save_r15]
+
+
+ ret 0
+//; please don't remove this string !
+//; Your can freely use gvmat64 in any free or commercial app
+//; but it is far better don't remove the string in the binary!
+ // db 0dh,0ah,"asm686 with masm, optimised assembly code from Brian Raiter, written 1998, converted to amd 64 by Gilles Vollant 2005",0dh,0ah,0
+
+
+match_init:
+ ret 0
+
+
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org