diff options
Diffstat (limited to 'neozip/tools')
| -rwxr-xr-x | neozip/tools/config.sub | 17 | ||||
| -rw-r--r-- | neozip/tools/makecrct.c | 242 | ||||
| -rw-r--r-- | neozip/tools/makefixed.c | 89 | ||||
| -rw-r--r-- | neozip/tools/maketrees.c | 155 |
4 files changed, 503 insertions, 0 deletions
diff --git a/neozip/tools/config.sub b/neozip/tools/config.sub new file mode 100755 index 0000000000..dba175ae31 --- /dev/null +++ b/neozip/tools/config.sub @@ -0,0 +1,17 @@ +#!/bin/sh +# Canonicalize CHOST. +# In particular, converts Debian multiarch tuples into GNU triplets. +# See also +# https://wiki.debian.org/Multiarch/Tuples +# https://wiki.gentoo.org/wiki/CHOST +# If you need an architecture not listed here, file a bug at github.com/zlib-ng/zlib-ng +# and work around the problem by dropping libtool's much more comprehensive config.sub +# on top of this file, see +# https://git.savannah.gnu.org/gitweb/?p=config.git;a=blob_plain;f=config.sub + +case "$1" in +*-*-linux-gnu*) echo $1;; +i686-linux-gnu*|x86_64-linux-gnu*) echo $1 | sed 's/-linux-gnu/-pc-linux-gnu/';; +*-linux-gnu*) echo $1 | sed 's/-linux-gnu/-unknown-linux-gnu/';; +*) echo $1;; +esac diff --git a/neozip/tools/makecrct.c b/neozip/tools/makecrct.c new file mode 100644 index 0000000000..812954ac0a --- /dev/null +++ b/neozip/tools/makecrct.c @@ -0,0 +1,242 @@ +/* makecrct.c -- output crc32 tables + * Copyright (C) 1995-2022 Mark Adler + * For conditions of distribution and use, see copyright notice in zlib.h +*/ + +#include <stdio.h> +#include <inttypes.h> +#include "zbuild.h" +#include "zutil.h" + +/* + The crc32 table header file contains tables for both 32-bit and 64-bit + z_word_t's, and so requires a 64-bit type be available. In that case, + z_word_t must be defined to be 64-bits. This code then also generates + and writes out the tables for the case that z_word_t is 32 bits. +*/ + +#define POLY 0xedb88320 /* p(x) reflected, with x^32 implied */ +#define BRAID_W 8 /* Need a 64-bit integer type in order to generate crc32 tables. */ +typedef uint64_t z_word_t; + +static uint32_t crc_table[256]; +static z_word_t crc_big_table[256]; +static uint32_t x2n_table[32]; + +#include "crc32_braid_comb_p.h" + +static void make_crc_table(void); +static void print_crc_table(void); + +static void braid(uint32_t ltl[][256], z_word_t big[][256], int n, int w); + +static void write_table(const uint32_t *table, int k); +static void write_table32hi(const z_word_t *table, int k); +static void write_table64(const z_word_t *table, int k); + +/* ========================================================================= */ +/* + Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: + x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1. + + Polynomials over GF(2) are represented in binary, one bit per coefficient, + with the lowest powers in the most significant bit. Then adding polynomials + is just exclusive-or, and multiplying a polynomial by x is a right shift by + one. If we call the above polynomial p, and represent a byte as the + polynomial q, also with the lowest power in the most significant bit (so the + byte 0xb1 is the polynomial x^7+x^3+x^2+1), then the CRC is (q*x^32) mod p, + where a mod b means the remainder after dividing a by b. + + This calculation is done using the shift-register method of multiplying and + taking the remainder. The register is initialized to zero, and for each + incoming bit, x^32 is added mod p to the register if the bit is a one (where + x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by x + (which is shifting right by one and adding x^32 mod p if the bit shifted out + is a one). We start with the highest power (least significant bit) of q and + repeat for all eight bits of q. + + The table is simply the CRC of all possible eight bit values. This is all the + information needed to generate CRCs on data a byte at a time for all + combinations of CRC register values and incoming bytes. +*/ +static void make_crc_table(void) { + unsigned i, j, n; + uint32_t p; + + /* initialize the CRC of bytes tables */ + for (i = 0; i < 256; i++) { + p = i; + for (j = 0; j < 8; j++) + p = p & 1 ? (p >> 1) ^ POLY : p >> 1; + crc_table[i] = p; + crc_big_table[i] = ZSWAP64(p); + } + + /* initialize the x^2^n mod p(x) table */ + p = (uint32_t)1 << 30; /* x^1 */ + x2n_table[0] = p; + for (n = 1; n < 32; n++) + x2n_table[n] = p = multmodp(p, p); +} + +/* + Generate the little and big-endian braid tables for the given n and z_word_t + size w. Each array must have room for w blocks of 256 elements. + */ +static void braid(uint32_t ltl[][256], z_word_t big[][256], int n, int w) { + int k; + uint32_t i, p, q; + for (k = 0; k < w; k++) { + p = x2nmodp(((z_off64_t)n * w + 3 - k) << 3, 0); + ltl[k][0] = 0; + big[w - 1 - k][0] = 0; + for (i = 1; i < 256; i++) { + ltl[k][i] = q = multmodp(i << 24, p); + big[w - 1 - k][i] = ZSWAP64(q); + } + } +} + +/* + Write the 32-bit values in table[0..k-1] to out, five per line in + hexadecimal separated by commas. + */ +static void write_table(const uint32_t *table, int k) { + int n; + + for (n = 0; n < k; n++) + printf("%s0x%08" PRIx32 "%s", n == 0 || n % 5 ? "" : " ", + (uint32_t)(table[n]), + n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", ")); +} + +/* + Write the high 32-bits of each value in table[0..k-1] to out, five per line + in hexadecimal separated by commas. + */ +static void write_table32hi(const z_word_t *table, int k) { + int n; + + for (n = 0; n < k; n++) + printf("%s0x%08" PRIx32 "%s", n == 0 || n % 5 ? "" : " ", + (uint32_t)(table[n] >> 32), + n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", ")); +} + +/* + Write the 64-bit values in table[0..k-1] to out, three per line in + hexadecimal separated by commas. This assumes that if there is a 64-bit + type, then there is also a long long integer type, and it is at least 64 + bits. If not, then the type cast and format string can be adjusted + accordingly. + */ +static void write_table64(const z_word_t *table, int k) { + int n; + + for (n = 0; n < k; n++) + printf("%s0x%016" PRIx64 "%s", n == 0 || n % 3 ? "" : " ", + (uint64_t)(table[n]), + n == k - 1 ? "" : (n % 3 == 2 ? ",\n" : ", ")); +} + +static void print_crc_table(void) { + int k, n; + uint32_t ltl[8][256]; + z_word_t big[8][256]; + + printf("#ifndef CRC32_BRAID_TBL_H_\n"); + printf("#define CRC32_BRAID_TBL_H_\n\n"); + printf("/* crc32_braid_tbl.h -- tables for braided CRC calculation\n"); + printf(" * Generated automatically by makecrct.c\n */\n\n"); + + /* print little-endian CRC table */ + printf("static const uint32_t crc_table[] = {\n"); + printf(" "); + write_table(crc_table, 256); + printf("};\n\n"); + + /* print big-endian CRC table for 64-bit z_word_t */ + printf("#ifdef BRAID_W\n"); + printf("# if BRAID_W == 8\n\n"); + printf("static const z_word_t crc_big_table[] = {\n"); + printf(" "); + write_table64(crc_big_table, 256); + printf("};\n\n"); + + /* print big-endian CRC table for 32-bit z_word_t */ + printf("# else /* BRAID_W == 4 */\n\n"); + printf("static const z_word_t crc_big_table[] = {\n"); + printf(" "); + write_table32hi(crc_big_table, 256); + printf("};\n\n"); + printf("# endif\n"); + printf("#endif /* BRAID_W */\n\n"); + + /* write out braid tables for each value of N */ + for (n = 1; n <= 6; n++) { + printf("#if BRAID_N == %d\n", n); + + /* compute braid tables for this N and 64-bit word_t */ + braid(ltl, big, n, 8); + + /* write out braid tables for 64-bit z_word_t */ + printf("# if BRAID_W == 8\n\n"); + printf("static const uint32_t crc_braid_table[][256] = {\n"); + for (k = 0; k < 8; k++) { + printf(" {"); + write_table(ltl[k], 256); + printf("}%s", k < 7 ? ",\n" : ""); + } + printf("};\n\n"); + printf("static const z_word_t crc_braid_big_table[][256] = {\n"); + for (k = 0; k < 8; k++) { + printf(" {"); + write_table64(big[k], 256); + printf("}%s", k < 7 ? ",\n" : ""); + } + printf("};\n"); + + /* compute braid tables for this N and 32-bit word_t */ + braid(ltl, big, n, 4); + + /* write out braid tables for 32-bit z_word_t */ + printf("\n"); + printf("# else /* BRAID_W == 4 */\n\n"); + printf("static const uint32_t crc_braid_table[][256] = {\n"); + for (k = 0; k < 4; k++) { + printf(" {"); + write_table(ltl[k], 256); + printf("}%s", k < 3 ? ",\n" : ""); + } + printf("};\n\n"); + printf("static const z_word_t crc_braid_big_table[][256] = {\n"); + for (k = 0; k < 4; k++) { + printf(" {"); + write_table32hi(big[k], 256); + printf("}%s", k < 3 ? ",\n" : ""); + } + printf("};\n\n"); + printf("# endif /* BRAID_W */\n"); + printf("#endif /* BRAID_N == %d */\n", n); + } + printf("\n"); + + /* write out zeros operator table */ + printf("static const uint32_t x2n_table[] = {\n"); + printf(" "); + write_table(x2n_table, 32); + printf("};\n"); + + printf("\n"); + printf("#endif /* CRC32_BRAID_TBL_H_ */\n"); +} + +// The output of this application can be piped out to recreate crc32 tables +int main(int argc, char *argv[]) { + Z_UNUSED(argc); + Z_UNUSED(argv); + + make_crc_table(); + print_crc_table(); + return 0; +} diff --git a/neozip/tools/makefixed.c b/neozip/tools/makefixed.c new file mode 100644 index 0000000000..13d4fa70d2 --- /dev/null +++ b/neozip/tools/makefixed.c @@ -0,0 +1,89 @@ +#include <stdio.h> +#include "zbuild.h" +#include "zutil.h" +#include "inftrees.h" +#include "inflate.h" + +// Build and return state with length and distance decoding tables and index sizes set to fixed code decoding. +void Z_INTERNAL buildfixedtables(struct inflate_state *state) { + static code *lenfix, *distfix; + static code fixed[544]; + + // build fixed huffman tables + unsigned sym, bits; + static code *next; + + // literal/length table + sym = 0; + while (sym < 144) state->lens[sym++] = 8; + while (sym < 256) state->lens[sym++] = 9; + while (sym < 280) state->lens[sym++] = 7; + while (sym < 288) state->lens[sym++] = 8; + next = fixed; + lenfix = next; + bits = 9; + zng_inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work); + + // distance table + sym = 0; + while (sym < 32) state->lens[sym++] = 5; + distfix = next; + bits = 5; + zng_inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work); + + state->lencode = lenfix; + state->lenbits = 9; + state->distcode = distfix; + state->distbits = 5; +} + + +// Create fixed tables on the fly and write out a inffixed_tbl.h file that is #include'd above. +// makefixed() writes those tables to stdout, which would be piped to inffixed_tbl.h. +void makefixed(void) { + unsigned low, size; + struct inflate_state state; + + memset(&state, 0, sizeof(state)); + buildfixedtables(&state); + puts("/* inffixed_tbl.h -- table for decoding fixed codes"); + puts(" * Generated automatically by makefixed()."); + puts(" */"); + puts(""); + puts("/* WARNING: this file should *not* be used by applications."); + puts(" * It is part of the implementation of this library and is"); + puts(" * subject to change. Applications should only use zlib.h."); + puts(" */"); + puts(""); + size = 1U << 9; + printf("static const code lenfix[%u] = {", size); + low = 0; + for (;;) { + if ((low % 7) == 0) + printf("\n "); + printf("{%u,%u,%d}", state.lencode[low].bits, (low & 127) == 99 ? 64 : state.lencode[low].op, + state.lencode[low].val); + if (++low == size) + break; + putchar(','); + } + puts("\n};"); + size = 1U << 5; + printf("\nstatic const code distfix[%u] = {", size); + low = 0; + for (;;) { + if ((low % 6) == 0) + printf("\n "); + printf("{%u,%u,%d}", state.distcode[low].bits, state.distcode[low].op, state.distcode[low].val); + if (++low == size) + break; + putchar(','); + } + puts("\n};"); +} + +// The output of this application can be piped out to recreate inffixed_tbl.h +int main(void) { + makefixed(); + return 0; +} diff --git a/neozip/tools/maketrees.c b/neozip/tools/maketrees.c new file mode 100644 index 0000000000..aa68c35603 --- /dev/null +++ b/neozip/tools/maketrees.c @@ -0,0 +1,155 @@ +/* maketrees.c -- output static huffman trees + * Copyright (C) 1995-2017 Jean-loup Gailly + * For conditions of distribution and use, see copyright notice in zlib.h + */ + +#include <stdio.h> +#include "zbuild.h" +#include "deflate.h" +#include "deflate_p.h" +#include "trees.h" + +static 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 zng_tr_init). + */ + +static ct_data static_dtree[D_CODES]; +/* The static distance tree. (Actually a trivial tree since all codes use 5 bits.) + */ + +static unsigned char 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. + */ + +static unsigned char length_code[STD_MAX_MATCH-STD_MIN_MATCH+1]; +/* length code for each normalized match length (0 == STD_MIN_MATCH) */ + +static int base_length[LENGTH_CODES]; +/* First normalized length for each code (0 = STD_MIN_MATCH) */ + +static int base_dist[D_CODES]; +/* First normalized distance for each code (0 = distance of 1) */ + + +static void tr_static_init(void) { + int n; /* iterates over tree elements */ + int bits; /* bit counter */ + int length; /* length value */ + int code; /* code value */ + int dist; /* distance index */ + uint16_t bl_count[MAX_BITS+1]; + /* number of codes at each bit length for an optimal tree */ + + /* 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++] = (unsigned char)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] = (unsigned char)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++] = (unsigned char)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++] = (unsigned char)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((uint16_t)n, 5); + } +} + +# define SEPARATOR(i, last, width) \ + ((i) == (last)? "\n};\n\n" : \ + ((i) % (width) == (width)-1 ? ",\n" : ", ")) + +static void gen_trees_header(void) { + int i; + + printf("#ifndef TREES_TBL_H_\n"); + printf("#define TREES_TBL_H_\n\n"); + + printf("/* header created automatically with maketrees.c */\n\n"); + + printf("Z_INTERNAL const ct_data static_ltree[L_CODES+2] = {\n"); + for (i = 0; i < L_CODES+2; i++) { + printf("{{%3u},{%u}}%s", static_ltree[i].Code, static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5)); + } + + printf("Z_INTERNAL const ct_data static_dtree[D_CODES] = {\n"); + for (i = 0; i < D_CODES; i++) { + printf("{{%2u},{%u}}%s", static_dtree[i].Code, static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5)); + } + + printf("const unsigned char Z_INTERNAL zng_dist_code[DIST_CODE_LEN] = {\n"); + for (i = 0; i < DIST_CODE_LEN; i++) { + printf("%2u%s", dist_code[i], SEPARATOR(i, DIST_CODE_LEN-1, 20)); + } + + printf("const unsigned char Z_INTERNAL zng_length_code[STD_MAX_MATCH-STD_MIN_MATCH+1] = {\n"); + for (i = 0; i < STD_MAX_MATCH-STD_MIN_MATCH+1; i++) { + printf("%2u%s", length_code[i], SEPARATOR(i, STD_MAX_MATCH-STD_MIN_MATCH, 20)); + } + + printf("/* Combined base + extra_bits tables for single-lookup optimization.\n"); + printf(" * Length table: bits 0-7 = base_length, bits 8-11 = extra_lbits\n"); + printf(" * Distance table: bits 0-15 = base_dist, bits 16-19 = extra_dbits\n"); + printf(" */\n"); + printf("#define LBASE_EXTRA(base, extra) ((extra) << 8 | (base))\n"); + printf("#define DBASE_EXTRA(base, extra) ((extra) << 16 | (base))\n\n"); + + printf("Z_INTERNAL const uint16_t lbase_extra[LENGTH_CODES] = {\n"); + for (i = 0; i < LENGTH_CODES; i++) { + printf("LBASE_EXTRA(%3d, %d)%s", base_length[i], extra_lbits[i], SEPARATOR(i, LENGTH_CODES-1, 4)); + } + + printf("Z_INTERNAL const uint32_t dbase_extra[D_CODES] = {\n"); + for (i = 0; i < D_CODES; i++) { + printf("DBASE_EXTRA(%5d, %2d)%s", base_dist[i], extra_dbits[i], SEPARATOR(i, D_CODES-1, 4)); + } + + printf("#endif /* TREES_TBL_H_ */\n"); +} + +// The output of this application can be piped out to recreate trees.h +int main(void) { + tr_static_init(); + gen_trees_header(); + return 0; +} |