diff options
Diffstat (limited to 'gpxe/src/util/nrv2b.c')
| -rw-r--r-- | gpxe/src/util/nrv2b.c | 1501 |
1 files changed, 0 insertions, 1501 deletions
diff --git a/gpxe/src/util/nrv2b.c b/gpxe/src/util/nrv2b.c deleted file mode 100644 index 6bac4cdd..00000000 --- a/gpxe/src/util/nrv2b.c +++ /dev/null @@ -1,1501 +0,0 @@ -/************************************************************** - Form adapted from lzhuf.c - written by Haruyasu Yoshizaki 11/20/1988 - some minor changes 4/6/1989 - comments translated by Haruhiko Okumura 4/7/1989 - - minor beautifications and adjustments for compiling under Linux - by Markus Gutschke <gutschk@math.uni-muenster.de> - 1997-01-27 - - Modifications to allow use as a filter by Ken Yap - <ken_yap@users.sourceforge.net>. - - 1997-07-01 - - Small mod to cope with running on big-endian machines - by Jim Hague <jim.hague@acm.org) - 1998-02-06 - - Make compression statistics report shorter - by Ken Yap <ken_yap@users.sourceforge.net>. - 2001-04-25 - - Replaced algorithm with nrv2b from ucl the compression - library from upx. That code is: - Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer - And is distributed under the terms of the GPL. - The conversion was performed - by Eric Biederman <ebiederman@lnxi.com>. - 20 August 2002 - -**************************************************************/ -#define UCLPACK_COMPAT 0 -#define NDEBUG 1 -#include <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <ctype.h> -#include <errno.h> -#ifdef __FreeBSD__ -#include <inttypes.h> -#else -#include <stdint.h> -#endif -#include <limits.h> -#include <assert.h> -#if UCLPACK_COMPAT -#include <netinet/in.h> -#endif - -#ifndef VERBOSE -#define Fprintf(x) -#define wterr 0 -#else -#define Fprintf(x) fprintf x -#endif - -#ifndef MAIN -extern -#endif -FILE *infile, *outfile; - -#if defined(ENCODE) || defined(DECODE) - -#ifndef ENDIAN -#define ENDIAN 0 -#endif -#ifndef BITSIZE -#define BITSIZE 32 -#endif - -static __inline__ void Error(char *message) -{ - Fprintf((stderr, "\n%s\n", message)); - exit(EXIT_FAILURE); -} - -/* These will be a complete waste of time on a lo-endian */ -/* system, but it only gets done once so WTF. */ -static unsigned long i86ul_to_host(unsigned long ul) -{ - unsigned long res = 0; - int i; - union - { - unsigned char c[4]; - unsigned long ul; - } u; - - u.ul = ul; - for (i = 3; i >= 0; i--) - res = (res << 8) + u.c[i]; - return res; -} - -static unsigned long host_to_i86ul(unsigned long ul) -{ - int i; - union - { - unsigned char c[4]; - unsigned long ul; - } u; - - for (i = 0; i < 4; i++) - { - u.c[i] = ul & 0xff; - ul >>= 8; - } - return u.ul; -} -#endif - - - -#if UCLPACK_COMPAT -/* magic file header for compressed files */ -static const unsigned char magic[8] = -{ 0x00, 0xe9, 0x55, 0x43, 0x4c, 0xff, 0x01, 0x1a }; - -#endif - -#ifdef ENCODE -/********** NRV2B_99 compression **********/ - -/* Note by limiting the ring buffer I have limited the maximum - * offset to 64K. Since etherboot rarely gets that big it - * is not a problem and it gives me a firm guarantee - * that I will never get a 3 byte string match that is encodes - * to more than 9/8 it's original size. - * That guaranteee is important to for the inplace decompressor. - * There are better ways to do this if a larger offset and buffer - * would give better compression. - */ -#define N (65536ul) /* size of ring buffer */ -#define THRESHOLD 1 /* lower limit for match length */ -#define F 2048 /* upper limit for match length */ -#define M2_MAX_OFFSET 0xd00 - -/* note: to use default values pass -1, i.e. initialize - * this struct by a memset(x,0xff,sizeof(x)) */ -struct ucl_compress_config -{ - int bb_endian; - int bb_size; - unsigned int max_offset; - unsigned int max_match; - int s_level; - int h_level; - int p_level; - int c_flags; - unsigned int m_size; -}; - -struct ucl_compress -{ - int init; - - unsigned int look; /* bytes in lookahead buffer */ - - unsigned int m_len; - unsigned int m_off; - - unsigned int last_m_len; - unsigned int last_m_off; - - const unsigned char *bp; - const unsigned char *ip; - const unsigned char *in; - const unsigned char *in_end; - unsigned char *out; - - uint64_t bb_b; - unsigned bb_k; - unsigned bb_c_endian; - unsigned bb_c_s; - unsigned bb_c_s8; - unsigned char *bb_p; - unsigned char *bb_op; - - struct ucl_compress_config conf; - unsigned int *result; - - unsigned int textsize; /* text size counter */ - unsigned int codesize; /* code size counter */ - unsigned int printcount; /* counter for reporting progress every 1K - bytes */ - - - /* some stats */ - unsigned long lit_bytes; - unsigned long match_bytes; - unsigned long rep_bytes; - unsigned long lazy; -}; - - - -#define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1)) - -#define UCL_E_OK 0 -#define UCL_E_INVALID_ARGUMENT 1 -#define UCL_E_OUT_OF_MEMORY 2 -#define UCL_E_ERROR 3 - -/*********************************************************************** -// -************************************************************************/ - -#define SWD_HSIZE 16384 -#define SWD_MAX_CHAIN 2048 -#define SWD_BEST_OFF 1 - -#define HEAD3(b,p) \ - (((0x9f5f*(((((uint32_t)b[p]<<5)^b[p+1])<<5)^b[p+2]))>>5) & (SWD_HSIZE-1)) - -#define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8)) -#define NIL2 UINT_MAX - -struct ucl_swd -{ -/* public - "built-in" */ - unsigned int n; - unsigned int f; - unsigned int threshold; - -/* public - configuration */ - unsigned int max_chain; - unsigned int nice_length; - int use_best_off; - unsigned int lazy_insert; - -/* public - output */ - unsigned int m_len; - unsigned int m_off; - unsigned int look; - int b_char; -#if defined(SWD_BEST_OFF) - unsigned int best_off[ SWD_BEST_OFF ]; -#endif - -/* semi public */ - struct ucl_compress *c; - unsigned int m_pos; -#if defined(SWD_BEST_OFF) - unsigned int best_pos[ SWD_BEST_OFF ]; -#endif - -/* private */ - const uint8_t *dict; - const uint8_t *dict_end; - unsigned int dict_len; - -/* private */ - unsigned int ip; /* input pointer (lookahead) */ - unsigned int bp; /* buffer pointer */ - unsigned int rp; /* remove pointer */ - unsigned int b_size; - - unsigned char *b_wrap; - - unsigned int node_count; - unsigned int first_rp; - - unsigned char b [ N + F + F ]; - unsigned int head3 [ SWD_HSIZE ]; - unsigned int succ3 [ N + F ]; - unsigned int best3 [ N + F ]; - unsigned int llen3 [ SWD_HSIZE ]; - unsigned int head2 [ 65536U ]; -}; - -#define s_head3(s,key) s->head3[key] - - -#if !defined( NDEBUG) -static void assert_match(const struct ucl_swd * swd, unsigned int m_len, - unsigned int m_off ) - -{ - const struct ucl_compress *c = swd->c; - unsigned int d_off; - - assert(m_len >= 2); - if (m_off <= (unsigned int) (c->bp - c->in)) - { - assert(c->bp - m_off + m_len < c->ip); - assert(memcmp(c->bp, c->bp - m_off, m_len) == 0); - } - else - { - assert(swd->dict != NULL); - d_off = m_off - (unsigned int) (c->bp - c->in); - assert(d_off <= swd->dict_len); - if (m_len > d_off) - { - assert(memcmp(c->bp, swd->dict_end - d_off, d_off) == - 0); - - assert(c->in + m_len - d_off < c->ip); - assert(memcmp(c->bp + d_off, c->in, m_len - d_off) == - 0); - - } - else - { - assert(memcmp(c->bp, swd->dict_end - d_off, m_len) == - 0); - - } - } -} -#else -# define assert_match(a,b,c) ((void)0) -#endif - -/*********************************************************************** -// -************************************************************************/ - - -static -void swd_initdict(struct ucl_swd *s, const uint8_t *dict, unsigned int dict_len) - -{ - s->dict = s->dict_end = NULL; - s->dict_len = 0; - - if (!dict || dict_len <= 0) - return; - if (dict_len > s->n) - { - dict += dict_len - s->n; - dict_len = s->n; - } - - s->dict = dict; - s->dict_len = dict_len; - s->dict_end = dict + dict_len; - memcpy(s->b,dict,dict_len); - s->ip = dict_len; -} - - -static -void swd_insertdict(struct ucl_swd *s, unsigned int node, unsigned int len) -{ - unsigned int key; - - s->node_count = s->n - len; - s->first_rp = node; - - while (len-- > 0) - { - key = HEAD3(s->b,node); - s->succ3[node] = s_head3(s,key); - s->head3[key] = (unsigned int)(node); - s->best3[node] = (unsigned int)(s->f + 1); - s->llen3[key]++; - assert(s->llen3[key] <= s->n); - - key = HEAD2(s->b,node); - s->head2[key] = (unsigned int)(node); - - node++; - } -} - -/*********************************************************************** -// -************************************************************************/ - - -static -int swd_init(struct ucl_swd *s, const uint8_t *dict, unsigned int dict_len) -{ - unsigned int i = 0; - int c = 0; - - if (s->n == 0) - s->n = N; - if (s->f == 0) - s->f = F; - s->threshold = THRESHOLD; - if (s->n > N || s->f > F) - return UCL_E_INVALID_ARGUMENT; - - /* defaults */ - s->max_chain = SWD_MAX_CHAIN; - s->nice_length = s->f; - s->use_best_off = 0; - s->lazy_insert = 0; - - s->b_size = s->n + s->f; - if (s->b_size + s->f >= UINT_MAX) - return UCL_E_ERROR; - s->b_wrap = s->b + s->b_size; - s->node_count = s->n; - - memset(s->llen3, 0, sizeof(s->llen3[0]) * SWD_HSIZE); - for (i = 0; i < 65536U; i++) - s->head2[i] = NIL2; - - s->ip = 0; - swd_initdict(s,dict,dict_len); - s->bp = s->ip; - s->first_rp = s->ip; - - assert(s->ip + s->f <= s->b_size); - - s->look = (unsigned int) (s->c->in_end - s->c->ip); - if (s->look > 0) - { - if (s->look > s->f) - s->look = s->f; - memcpy(&s->b[s->ip],s->c->ip,s->look); - s->c->ip += s->look; - s->ip += s->look; - } - if (s->ip == s->b_size) - s->ip = 0; - - if (s->look >= 2 && s->dict_len > 0) - swd_insertdict(s,0,s->dict_len); - - s->rp = s->first_rp; - if (s->rp >= s->node_count) - s->rp -= s->node_count; - else - s->rp += s->b_size - s->node_count; - - /* unused i */ - /* unused c */ - return UCL_E_OK; -} - - -static -void swd_exit(struct ucl_swd *s) -{ - /* unused s */ - -} - -#define swd_pos2off(s,pos) \ - (s->bp > (pos) ? s->bp - (pos) : s->b_size - ((pos) - s->bp)) - -/*********************************************************************** -// -************************************************************************/ - -static __inline__ -void swd_getbyte(struct ucl_swd *s) -{ - int c; - - if ((c = getbyte(*(s->c))) < 0) - { - if (s->look > 0) - --s->look; - } - else - { - s->b[s->ip] = (uint8_t)(c); - if (s->ip < s->f) - s->b_wrap[s->ip] = (uint8_t)(c); - } - if (++s->ip == s->b_size) - s->ip = 0; - if (++s->bp == s->b_size) - s->bp = 0; - if (++s->rp == s->b_size) - s->rp = 0; -} -/*********************************************************************** -// remove node from lists -************************************************************************/ - -static __inline__ -void swd_remove_node(struct ucl_swd *s, unsigned int node) -{ - if (s->node_count == 0) - { - unsigned int key; - -#ifdef UCL_DEBUG - if (s->first_rp != UINT_MAX) - { - if (node != s->first_rp) - printf("Remove %5d: %5d %5d %5d %5d %6d %6d\n", - - node, s->rp, s->ip, s->bp, s->first_rp, - s->ip - node, s->ip - s->bp); - assert(node == s->first_rp); - s->first_rp = UINT_MAX; - } -#endif - - key = HEAD3(s->b,node); - assert(s->llen3[key] > 0); - --s->llen3[key]; - - key = HEAD2(s->b,node); - assert(s->head2[key] != NIL2); - if ((unsigned int) s->head2[key] == node) - s->head2[key] = NIL2; - } - else - --s->node_count; -} - - -/*********************************************************************** -// -************************************************************************/ - - -static -void swd_accept(struct ucl_swd *s, unsigned int n) -{ - assert(n <= s->look); - - if (n > 0) do - { - unsigned int key; - - swd_remove_node(s,s->rp); - - /* add bp into HEAD3 */ - key = HEAD3(s->b,s->bp); - s->succ3[s->bp] = s_head3(s,key); - s->head3[key] = (unsigned int)(s->bp); - s->best3[s->bp] = (unsigned int)(s->f + 1); - s->llen3[key]++; - assert(s->llen3[key] <= s->n); - - /* add bp into HEAD2 */ - key = HEAD2(s->b,s->bp); - s->head2[key] = (unsigned int)(s->bp); - - swd_getbyte(s); - } while (--n > 0); -} - -/*********************************************************************** -// -************************************************************************/ - -static -void swd_search(struct ucl_swd *s, unsigned int node, unsigned int cnt) -{ - const unsigned char *p1; - const unsigned char *p2; - const unsigned char *px; - - unsigned int m_len = s->m_len; - const unsigned char * b = s->b; - const unsigned char * bp = s->b + s->bp; - const unsigned char * bx = s->b + s->bp + s->look; - unsigned char scan_end1; - - assert(s->m_len > 0); - - scan_end1 = bp[m_len - 1]; - for ( ; cnt-- > 0; node = s->succ3[node]) - { - p1 = bp; - p2 = b + node; - px = bx; - - assert(m_len < s->look); - - if ( - p2[m_len - 1] == scan_end1 && - p2[m_len] == p1[m_len] && - p2[0] == p1[0] && - p2[1] == p1[1]) - { - unsigned int i; - assert(memcmp(bp,&b[node],3) == 0); - - p1 += 2; p2 += 2; - do {} while (++p1 < px && *p1 == *++p2); - i = p1 - bp; - -#ifdef UCL_DEBUG - if (memcmp(bp,&b[node],i) != 0) - printf("%5ld %5ld %02x%02x %02x%02x\n", - (long)s->bp, (long) node, - bp[0], bp[1], b[node], b[node+1]); -#endif - assert(memcmp(bp,&b[node],i) == 0); - -#if defined(SWD_BEST_OFF) - if (i < SWD_BEST_OFF) - { - if (s->best_pos[i] == 0) - s->best_pos[i] = node + 1; - } -#endif - if (i > m_len) - { - s->m_len = m_len = i; - s->m_pos = node; - if (m_len == s->look) - return; - if (m_len >= s->nice_length) - return; - if (m_len > (unsigned int) s->best3[node]) - return; - scan_end1 = bp[m_len - 1]; - } - } - } -} - -static int swd_search2(struct ucl_swd *s) -{ - unsigned int key; - - assert(s->look >= 2); - assert(s->m_len > 0); - - key = s->head2[ HEAD2(s->b,s->bp) ]; - if (key == NIL2) - return 0; -#ifdef UCL_DEBUG - if (memcmp(&s->b[s->bp],&s->b[key],2) != 0) - printf("%5ld %5ld %02x%02x %02x%02x\n", (long)s->bp, (long)key, - s->b[s->bp], s->b[s->bp+1], s->b[key], s->b[key+1]); -#endif - assert(memcmp(&s->b[s->bp],&s->b[key],2) == 0); -#if defined(SWD_BEST_OFF) - if (s->best_pos[2] == 0) - s->best_pos[2] = key + 1; -#endif - - if (s->m_len < 2) - { - s->m_len = 2; - s->m_pos = key; - } - return 1; -} - -/*********************************************************************** -// -************************************************************************/ - -static -void swd_findbest(struct ucl_swd *s) -{ - unsigned int key; - unsigned int cnt, node; - unsigned int len; - - assert(s->m_len > 0); - - /* get current head, add bp into HEAD3 */ - key = HEAD3(s->b,s->bp); - node = s->succ3[s->bp] = s_head3(s,key); - cnt = s->llen3[key]++; - assert(s->llen3[key] <= s->n + s->f); - if (cnt > s->max_chain && s->max_chain > 0) - cnt = s->max_chain; - s->head3[key] = (unsigned int)(s->bp); - - s->b_char = s->b[s->bp]; - len = s->m_len; - if (s->m_len >= s->look) - { - if (s->look == 0) - s->b_char = -1; - s->m_off = 0; - s->best3[s->bp] = (unsigned int)(s->f + 1); - } - else - { - if (swd_search2(s)) - if (s->look >= 3) - swd_search(s,node,cnt); - if (s->m_len > len) - s->m_off = swd_pos2off(s,s->m_pos); - s->best3[s->bp] = (unsigned int)(s->m_len); - -#if defined(SWD_BEST_OFF) - if (s->use_best_off) - { - int i; - for (i = 2; i < SWD_BEST_OFF; i++) - if (s->best_pos[i] > 0) - s->best_off[i] = - swd_pos2off(s,s->best_pos[i]-1); - - else - s->best_off[i] = 0; - } -#endif - } - - swd_remove_node(s,s->rp); - - /* add bp into HEAD2 */ - key = HEAD2(s->b,s->bp); - s->head2[key] = (unsigned int)(s->bp); -} - - -/*********************************************************************** -// -************************************************************************/ - -static int -init_match ( struct ucl_compress *c, struct ucl_swd *s, - const uint8_t *dict, unsigned int dict_len, - uint32_t flags ) -{ - int r; - - assert(!c->init); - c->init = 1; - - s->c = c; - - c->last_m_len = c->last_m_off = 0; - - c->textsize = c->codesize = c->printcount = 0; - c->lit_bytes = c->match_bytes = c->rep_bytes = 0; - c->lazy = 0; - - r = swd_init(s,dict,dict_len); - if (r != UCL_E_OK) - { - swd_exit(s); - return r; - } - - s->use_best_off = (flags & 1) ? 1 : 0; - return UCL_E_OK; -} - -static int -find_match ( struct ucl_compress *c, struct ucl_swd *s, - unsigned int this_len, unsigned int skip ) -{ - assert(c->init); - - if (skip > 0) - { - assert(this_len >= skip); - swd_accept(s, this_len - skip); - c->textsize += this_len - skip + 1; - } - else - { - assert(this_len <= 1); - c->textsize += this_len - skip; - } - - s->m_len = THRESHOLD; -#ifdef SWD_BEST_OFF - if (s->use_best_off) - memset(s->best_pos,0,sizeof(s->best_pos)); -#endif - swd_findbest(s); - c->m_len = s->m_len; - c->m_off = s->m_off; - - swd_getbyte(s); - - if (s->b_char < 0) - { - c->look = 0; - c->m_len = 0; - swd_exit(s); - } - else - { - c->look = s->look + 1; - } - c->bp = c->ip - c->look; - -#if 0 - /* brute force match search */ - if (c->m_len > THRESHOLD && c->m_len + 1 <= c->look) - { - const uint8_t *ip = c->bp; - const uint8_t *m = c->bp - c->m_off; - const uint8_t *in = c->in; - - if (ip - in > N) - in = ip - N; - for (;;) - { - while (*in != *ip) - in++; - if (in == ip) - break; - if (in != m) - if (memcmp(in,ip,c->m_len+1) == 0) - printf("%p %p %p %5d\n",in,ip,m,c->m_len); - - in++; - } - } -#endif - - return UCL_E_OK; -} - - -static int bbConfig(struct ucl_compress *c, int endian, int bitsize) -{ - if (endian != -1) - { - if (endian != 0) - return UCL_E_ERROR; - c->bb_c_endian = endian; - } - if (bitsize != -1) - { - if (bitsize != 8 && bitsize != 16 && bitsize != 32 && bitsize != 64) - return UCL_E_ERROR; - c->bb_c_s = bitsize; - c->bb_c_s8 = bitsize / 8; - } - c->bb_b = 0; c->bb_k = 0; - c->bb_p = NULL; - c->bb_op = NULL; - return UCL_E_OK; -} - -static void bbWriteBits(struct ucl_compress *c) -{ - uint8_t *p = c->bb_p; - uint64_t b = c->bb_b; - - p[0] = (uint8_t)(b >> 0); - if (c->bb_c_s >= 16) - { - p[1] = (uint8_t)(b >> 8); - if (c->bb_c_s >= 32) - { - p[2] = (uint8_t)(b >> 16); - p[3] = (uint8_t)(b >> 24); - if (c->bb_c_s == 64) - { - p[4] = (uint8_t)(b >> 32); - p[5] = (uint8_t)(b >> 40); - p[6] = (uint8_t)(b >> 48); - p[7] = (uint8_t)(b >> 56); - } - } - } -} - - -static void bbPutBit(struct ucl_compress *c, unsigned bit) -{ - assert(bit == 0 || bit == 1); - assert(c->bb_k <= c->bb_c_s); - - if (c->bb_k < c->bb_c_s) - { - if (c->bb_k == 0) - { - assert(c->bb_p == NULL); - c->bb_p = c->bb_op; - c->bb_op += c->bb_c_s8; - } - assert(c->bb_p != NULL); - assert(c->bb_p + c->bb_c_s8 <= c->bb_op); - - c->bb_b = (c->bb_b << 1) + bit; - c->bb_k++; - } - else - { - assert(c->bb_p != NULL); - assert(c->bb_p + c->bb_c_s8 <= c->bb_op); - - bbWriteBits(c); - c->bb_p = c->bb_op; - c->bb_op += c->bb_c_s8; - c->bb_b = bit; - c->bb_k = 1; - } -} - - -static void bbPutByte(struct ucl_compress *c, unsigned b) -{ - /**printf("putbyte %p %p %x (%d)\n", op, bb_p, x, bb_k);*/ - assert(c->bb_p == NULL || c->bb_p + c->bb_c_s8 <= c->bb_op); - *c->bb_op++ = (uint8_t)(b); -} - -static void bbFlushBits(struct ucl_compress *c, unsigned filler_bit) -{ - if (c->bb_k > 0) - { - assert(c->bb_k <= c->bb_c_s); - while (c->bb_k != c->bb_c_s) - bbPutBit(c, filler_bit); - bbWriteBits(c); - c->bb_k = 0; - } - c->bb_p = NULL; -} - - - -/*********************************************************************** -// -************************************************************************/ - - -static void code_prefix_ss11(struct ucl_compress *c, uint32_t i) -{ - if (i >= 2) - { - uint32_t t = 4; - i += 2; - do { - t <<= 1; - } while (i >= t); - t >>= 1; - do { - t >>= 1; - bbPutBit(c, (i & t) ? 1 : 0); - bbPutBit(c, 0); - } while (t > 2); - } - bbPutBit(c, (unsigned)i & 1); - bbPutBit(c, 1); -} - -static void -code_match(struct ucl_compress *c, unsigned int m_len, const unsigned int m_off) - -{ - while (m_len > c->conf.max_match) - { - code_match(c, c->conf.max_match - 3, m_off); - m_len -= c->conf.max_match - 3; - } - - c->match_bytes += m_len; - if (m_len > c->result[3]) - c->result[3] = m_len; - if (m_off > c->result[1]) - c->result[1] = m_off; - - bbPutBit(c, 0); - - if (m_off == c->last_m_off) - { - bbPutBit(c, 0); - bbPutBit(c, 1); - } - else - { - code_prefix_ss11(c, 1 + ((m_off - 1) >> 8)); - bbPutByte(c, (unsigned)m_off - 1); - } - m_len = m_len - 1 - (m_off > M2_MAX_OFFSET); - if (m_len >= 4) - { - bbPutBit(c,0); - bbPutBit(c,0); - code_prefix_ss11(c, m_len - 4); - } - else - { - bbPutBit(c, m_len > 1); - bbPutBit(c, (unsigned)m_len & 1); - } - - c->last_m_off = m_off; -} - -static void -code_run(struct ucl_compress *c, const uint8_t *ii, unsigned int lit) -{ - if (lit == 0) - return; - c->lit_bytes += lit; - if (lit > c->result[5]) - c->result[5] = lit; - do { - bbPutBit(c, 1); - bbPutByte(c, *ii++); - } while (--lit > 0); -} - -/*********************************************************************** -// -************************************************************************/ - -static int -len_of_coded_match(struct ucl_compress *c, unsigned int m_len, unsigned int - m_off) - -{ - int b; - if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET)) - || m_off > c->conf.max_offset) - return -1; - assert(m_off > 0); - - m_len = m_len - 2 - (m_off > M2_MAX_OFFSET); - - if (m_off == c->last_m_off) - b = 1 + 2; - else - { - b = 1 + 10; - m_off = (m_off - 1) >> 8; - while (m_off > 0) - { - b += 2; - m_off >>= 1; - } - } - - b += 2; - if (m_len < 3) - return b; - m_len -= 3; - - do { - b += 2; - m_len >>= 1; - } while (m_len > 0); - - return b; -} - -int ucl_nrv2b_99_compress( - const uint8_t *in, unsigned long in_len, - uint8_t *out, unsigned long *out_len, - unsigned int *result) -{ - const uint8_t *ii; - unsigned int lit; - unsigned int m_len, m_off; - struct ucl_compress c_buffer; - struct ucl_compress * const c = &c_buffer; - struct ucl_swd *swd; - unsigned int result_buffer[16]; - int r; - -/* max compression */ -#define SC_TRY_LAZY 2 -#define SC_GOOD_LENGTH F -#define SC_MAX_LAZY F -#define SC_NICE_LENGTH F -#define SC_MAX_CHAIN 4096 -#define SC_FLAGS 1 -#define SC_MAX_OFFSET N - - memset(c, 0, sizeof(*c)); - c->ip = c->in = in; - c->in_end = in + in_len; - c->out = out; - c->result = result ? result : result_buffer; - memset(c->result, 0, 16*sizeof(*c->result)); - c->result[0] = c->result[2] = c->result[4] = UINT_MAX; - result = NULL; - memset(&c->conf, 0xff, sizeof(c->conf)); - r = bbConfig(c, ENDIAN, BITSIZE); - if (r == 0) - r = bbConfig(c, c->conf.bb_endian, c->conf.bb_size); - if (r != 0) - return UCL_E_INVALID_ARGUMENT; - c->bb_op = out; - - ii = c->ip; /* point to start of literal run */ - lit = 0; - - - swd = (struct ucl_swd *) malloc(sizeof(*swd)); - if (!swd) - return UCL_E_OUT_OF_MEMORY; - - swd->f = F; - swd->n = N; - if (in_len >= 256 && in_len < swd->n) - swd->n = in_len; - if (swd->f < 8 || swd->n < 256) - return UCL_E_INVALID_ARGUMENT; - - r = init_match(c,swd,NULL,0, SC_FLAGS); - if (r != UCL_E_OK) - { - free(swd); - return r; - } - if (SC_MAX_CHAIN > 0) - swd->max_chain = SC_MAX_CHAIN; - if (SC_NICE_LENGTH > 0) - swd->nice_length = SC_NICE_LENGTH; - if (c->conf.max_match < swd->nice_length) - swd->nice_length = c->conf.max_match; - - c->last_m_off = 1; - r = find_match(c,swd,0,0); - if (r != UCL_E_OK) - return r; - while (c->look > 0) - { - unsigned int ahead; - unsigned int max_ahead; - int l1, l2; - - c->codesize = c->bb_op - out; - - m_len = c->m_len; - m_off = c->m_off; - - assert(c->bp == c->ip - c->look); - assert(c->bp >= in); - if (lit == 0) - ii = c->bp; - assert(ii + lit == c->bp); - assert(swd->b_char == *(c->bp)); - - if (m_len < 2 || (m_len == 2 && (m_off > M2_MAX_OFFSET)) - || m_off > c->conf.max_offset) - { - /* a literal */ - lit++; - swd->max_chain = SC_MAX_CHAIN; - r = find_match(c,swd,1,0); - assert(r == 0); - continue; - } - - /* a match */ - assert_match(swd,m_len,m_off); - - /* shall we try a lazy match ? */ - ahead = 0; - if (SC_TRY_LAZY <= 0 || m_len >= SC_MAX_LAZY || m_off == - c->last_m_off) - - { - /* no */ - l1 = 0; - max_ahead = 0; - } - else - { - /* yes, try a lazy match */ - l1 = len_of_coded_match(c,m_len,m_off); - assert(l1 > 0); - max_ahead = SC_TRY_LAZY; - if ((m_len - 1) < max_ahead) { - max_ahead = m_len -1; - } - } - - while (ahead < max_ahead && c->look > m_len) - { - if (m_len >= SC_GOOD_LENGTH) - swd->max_chain = SC_MAX_CHAIN >> 2; - else - swd->max_chain = SC_MAX_CHAIN; - r = find_match(c,swd,1,0); - ahead++; - - assert(r == 0); - assert(c->look > 0); - assert(ii + lit + ahead == c->bp); - - if (c->m_len < 2) - continue; - l2 = len_of_coded_match(c,c->m_len,c->m_off); - if (l2 < 0) - continue; - if (l1 + (int)(ahead + c->m_len - m_len) * 5 > l2 + - (int)(ahead) * 9) - { - c->lazy++; - assert_match(swd,c->m_len,c->m_off); - lit += ahead; - assert(ii + lit == c->bp); - goto lazy_match_done; - } - } - - assert(ii + lit + ahead == c->bp); - - /* 1 - code run */ - code_run(c,ii,lit); - lit = 0; - - /* 2 - code match */ - code_match(c,m_len,m_off); - swd->max_chain = SC_MAX_CHAIN; - r = find_match(c,swd,m_len,1+ahead); - assert(r == 0); - - lazy_match_done: ; - } - - /* store final run */ - code_run(c,ii,lit); - - /* EOF */ - bbPutBit(c, 0); - code_prefix_ss11(c, 0x1000000U); - bbPutByte(c, 0xff); - - bbFlushBits(c, 0); - - assert(c->textsize == in_len); - c->codesize = c->bb_op - out; - *out_len = c->bb_op - out; - -#if 0 - printf("%7ld %7ld -> %7ld %7ld %7ld %ld (max: %d %d %d)\n", - (long) c->textsize, (long) in_len, (long) c->codesize, - c->match_bytes, c->lit_bytes, c->lazy, - c->result[1], c->result[3], c->result[5]); -#endif - assert(c->lit_bytes + c->match_bytes == in_len); - - swd_exit(swd); - free(swd); - - return UCL_E_OK; -} - - -void Encode(void) /* compression */ -{ - uint8_t *in, *out; - unsigned long in_len, out_len; - uint32_t tw; - int r; - fseek(infile, 0, SEEK_END); - in_len = ftell(infile); -#ifdef VERBOSE - if ((signed long)in_len < 0) - Fprintf((stderr, "Errno: %d", errno)); -#endif -#if UCLPACK_COMPAT - { - uint8_t byte; - if (fwrite(magic, sizeof(magic), 1, outfile) != 1) - Error("Can't write."); - tw = htonl(0); /* flags */ - if (fwrite(&tw, sizeof(tw), 1, outfile) != 1) - Error("Can't write."); - byte = 0x2b; /* method */ - if (fwrite(&byte, sizeof(byte), 1, outfile) != 1) - Error("Can't write."); - byte = 10; /* level */ - if (fwrite(&byte, sizeof(byte), 1, outfile) != 1) - Error("Can't write."); - tw = htonl(256*1024); /* block_size */ - if (fwrite(&tw, sizeof(tw), 1, outfile) != 1) - Error("Can't write."); - tw = htonl(in_len); - if (fwrite(&tw, sizeof(tw), 1, outfile) != 1) - Error("Can't write."); /* output size of text */ - } -#else - tw = host_to_i86ul(in_len); - if (fwrite(&tw, sizeof(tw), 1, outfile) != 1) - Error("Can't write."); /* output size of text */ -#endif - if (in_len == 0) - return; - rewind(infile); - - in = malloc(in_len); - out_len = in_len + (in_len/8) + 256; - out = malloc(out_len); - if (!in || !out) { - Error("Can't malloc"); - } - if (fread(in, in_len, 1, infile) != 1) { - Error("Can't read"); - } - r = ucl_nrv2b_99_compress(in, in_len, out, &out_len, 0 ); - if (r != UCL_E_OK) - Error("Compression failure\n"); -#if UCLPACK_COMPAT - tw = htonl(out_len); - if (fwrite(&tw, sizeof(tw), 1, outfile) != 1) - Error("Can't write."); /* file size of text */ - -#endif - if (fwrite(out, out_len, 1, outfile) != 1) { - Error("Write error\n"); - } -#if UCLPACK_COMPAT - tw = htonl(0); /* EOF marker */ - if (fwrite(&tw, sizeof(tw), 1, outfile) != 1) - Error("Can't write."); - -#endif - -#ifdef LONG_REPORT - Fprintf((stdout, "input size %ld bytes\n", in_len)); - Fprintf((stdout, "output size %ld bytes\n", out_len)); - Fprintf((stdout, "input/output %.3f\n", (double)in_len / out_len)); -#else - Fprintf((stdout, "input/output = %ld/%ld = %.3f\n", in_len, out_len, - (double)in_len / out_len)); -#endif - -} - -#endif - -#ifdef DECODE - -#define GETBIT_8(bb, src, ilen) \ - (((bb = bb & 0x7f ? bb*2 : ((unsigned)src[ilen++]*2+1)) >> 8) & 1) - -#define GETBIT_LE16(bb, src, ilen) \ - (bb*=2,bb&0xffff ? (bb>>16)&1 : (ilen+=2,((bb=(src[ilen-2]+src[ilen-1]*256u)*2+1)>>16)&1)) - -#define GETBIT_LE32(bb, src, ilen) \ - (bc > 0 ? ((bb>>--bc)&1) : (bc=31,\ - bb=*(const uint32_t *)((src)+ilen),ilen+=4,(bb>>31)&1)) - -#define GETBIT_LE64(bb, src, ilen) \ - (bc > 0 ? ((bb>>--bc)&1) : (bc=63, \ - bb=*(const uint64_t *)((src)+ilen),ilen+=8,(bb>>63)&1)) - -#if ENDIAN == 0 && BITSIZE == 8 -#define GETBIT(bb, src, ilen) GETBIT_8(bb, src, ilen) -#endif -#if ENDIAN == 0 && BITSIZE == 16 -#define GETBIT(bb, src, ilen) GETBIT_LE16(bb, src, ilen) -#endif -#if ENDIAN == 0 && BITSIZE == 32 -#define GETBIT(bb, src, ilen) GETBIT_LE32(bb, src, ilen) -#endif -#if ENDIAN == 0 && BITSIZE == 64 -#define GETBIT(bb, src, ilen) GETBIT_LE64(bb, src, ilen) -#endif -#ifndef GETBIT -#error "Bad Combination of ENDIAN and BITSIZE values specified" -#endif - -#undef SAFE - -#ifdef SAFE -#define FAIL(x,r) if (x) { Error(r); } -#else -#define FAIL(x,r) -#endif - -void Decode(void) /* recover */ -{ - uint32_t tw; - uint8_t *src, *dst; - unsigned long max_src_len, src_len, dst_len; - unsigned long ilen = 0, olen = 0, last_m_off = 1; -#if BITSIZE <= 32 - uint32_t bb = 0; -#elif BITSIZE == 64 - uint64_t bb = 0; -#endif - unsigned bc = 0; -#if UCLPACK_COMPAT - if (fseek(infile, sizeof(magic) + sizeof(tw) + 1 + 1 + sizeof(tw), - SEEK_SET) != 0) - - Error("Seek Error"); - if (fread(&tw, sizeof(tw), 1, infile) < 1) - Error("Can't read"); /* read size of text */ - dst_len = ntohl(tw); - if (fread(&tw, sizeof(tw), 1, infile) < 1) - Error("Can't read"); /* read size of file */ - max_src_len = ntohl(tw); -#else - if (fread(&tw, sizeof(tw), 1, infile) < 1) - Error("Can't read"); /* read size of text */ - dst_len = i86ul_to_host(tw); - max_src_len = dst_len + (dst_len/8) + 256; -#endif - if (dst_len == 0) - return; - dst = malloc(dst_len); - if (!dst) - Error("Can't malloc"); - src = malloc(max_src_len); - if (!src) - Error("Can't malloc"); - src_len = fread(src, 1, max_src_len, infile); - if (src_len <= 0) - Error("Can't read"); - - for(;;) { - unsigned int m_off, m_len; - while(GETBIT(bb, src, ilen)) { - FAIL(ilen >= src_len, "input overrun"); - FAIL(olen >= dst_len, "output overrun"); - dst[olen++] = src[ilen++]; - } - m_off = 1; - do { - m_off = m_off*2 + GETBIT(bb, src, ilen); - FAIL(ilen >= src_len, "input overrun"); - FAIL(m_off > 0xffffffU +3, "lookbehind overrun"); - } while (!GETBIT(bb, src, ilen)); - if (m_off == 2) - { - m_off = last_m_off; - } - else - { - FAIL(ilen >= src_len, "input overrun"); - m_off = (m_off - 3)*256 + src[ilen++]; - if (m_off == 0xffffffffU) - break; - last_m_off = ++m_off; - } - m_len = GETBIT(bb, src, ilen); - m_len = m_len*2 + GETBIT(bb, src, ilen); - if (m_len == 0) - { - m_len++; - do { - m_len = m_len*2 + GETBIT(bb, src, ilen); - FAIL(ilen >= src_len, "input overrun"); - FAIL(m_len >= dst_len, "output overrun"); - } while(!GETBIT(bb, src, ilen)); - m_len += 2; - } - m_len += (m_off > 0xd00); - FAIL(olen + m_len > dst_len, "output overrun"); - FAIL(m_off > olen, "lookbeind overrun"); - { - const uint8_t *m_pos; - m_pos = dst + olen - m_off; - dst[olen++] = *m_pos++; - do { - dst[olen++] = *m_pos++; - } while(--m_len > 0); - } - } - FAIL(ilen < src_len, "input not consumed"); - FAIL(ilen > src_len, "input overrun"); - assert(ilen == src_len); - Fprintf((stderr, "%12ld\n", olen)); - if (dst_len != olen) { - fprintf(stderr, "length != expected length\n"); - } - if (fwrite(dst, olen, 1, outfile) != 1) - Error("Write error\n"); - free(src); - free(dst); -} -#endif - -#ifdef MAIN -int main(int argc, char *argv[]) -{ - char *s; - FILE *f; - int c; - - if (argc == 2) { - outfile = stdout; - if ((f = tmpfile()) == NULL) { - perror("tmpfile"); - return EXIT_FAILURE; - } - while ((c = getchar()) != EOF) - fputc(c, f); - rewind(infile = f); - } - else if (argc != 4) { - Fprintf((stderr, "'nrv2b e file1 file2' encodes file1 into file2.\n" - "'nrv2b d file2 file1' decodes file2 into file1.\n")); - return EXIT_FAILURE; - } - if (argc == 4) { - if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL) - || (s = argv[2], (infile = fopen(s, "rb")) == NULL) - || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) { - Fprintf((stderr, "??? %s\n", s)); - return EXIT_FAILURE; - } - } - if (toupper(*argv[1]) == 'E') - Encode(); - else - Decode(); - fclose(infile); - fclose(outfile); - return EXIT_SUCCESS; -} -#endif |