From 7c21a96e9afa3408ca0b459a392275aa0ae77608 Mon Sep 17 00:00:00 2001 From: Jens Arnold Date: Sun, 27 Nov 2005 23:41:55 +0000 Subject: Initial check-in of (stripped-down) UCL data compression library v 1.01 git-svn-id: svn://svn.rockbox.org/rockbox/trunk@8087 a1c6a512-1295-4272-9138-f99709370657 --- tools/ucl/src/n2_99.ch | 643 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 643 insertions(+) create mode 100755 tools/ucl/src/n2_99.ch (limited to 'tools/ucl/src/n2_99.ch') diff --git a/tools/ucl/src/n2_99.ch b/tools/ucl/src/n2_99.ch new file mode 100755 index 0000000000..5df69baaf4 --- /dev/null +++ b/tools/ucl/src/n2_99.ch @@ -0,0 +1,643 @@ +/* n2_99.ch -- implementation of the NRV2[BDE]-99 compression algorithms + + This file is part of the UCL data compression library. + + Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + The UCL library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The UCL library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the UCL library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + + Markus F.X.J. Oberhumer + + http://www.oberhumer.com/opensource/ucl/ + */ + + + +#include +#include +#include "ucl_conf.h" + +#if 0 +#undef UCL_DEBUG +#define UCL_DEBUG +#endif + +#include + +#if 0 && !defined(UCL_DEBUG) +#undef NDEBUG +#include +#endif + + +/*********************************************************************** +// +************************************************************************/ + +#if 0 +#define N (128*1024ul) /* size of ring buffer */ +#else +#define N (1024*1024ul) /* size of ring buffer */ +#define SWD_USE_MALLOC +#define SWD_HSIZE 65536ul +#endif +#define THRESHOLD 1 /* lower limit for match length */ +#define F 2048 /* upper limit for match length */ + +#if defined(NRV2B) +# define UCL_COMPRESS_T ucl_nrv2b_t +# define ucl_swd_t ucl_nrv2b_swd_t +# define ucl_nrv_99_compress ucl_nrv2b_99_compress +# define M2_MAX_OFFSET 0xd00 +#elif defined(NRV2D) +# define UCL_COMPRESS_T ucl_nrv2d_t +# define ucl_swd_t ucl_nrv2d_swd_t +# define ucl_nrv_99_compress ucl_nrv2d_99_compress +# define M2_MAX_OFFSET 0x500 +#elif defined(NRV2E) +# define UCL_COMPRESS_T ucl_nrv2e_t +# define ucl_swd_t ucl_nrv2e_swd_t +# define ucl_nrv_99_compress ucl_nrv2e_99_compress +# define M2_MAX_OFFSET 0x500 +#else +# error +#endif +#define ucl_swd_p ucl_swd_t * __UCL_MMODEL + +#if 0 +# define HEAD3(b,p) \ + ((((((ucl_uint32)b[p]<<3)^b[p+1])<<3)^b[p+2]) & (SWD_HSIZE-1)) +#endif +#if 0 && defined(UCL_UNALIGNED_OK_4) && (UCL_BYTE_ORDER == UCL_LITTLE_ENDIAN) +# define HEAD3(b,p) \ + (((* (ucl_uint32p) &b[p]) ^ ((* (ucl_uint32p) &b[p])>>10)) & (SWD_HSIZE-1)) +#endif + +#include "ucl_mchw.ch" + + +/*********************************************************************** +// +************************************************************************/ + +static void code_prefix_ss11(UCL_COMPRESS_T *c, ucl_uint32 i) +{ + if (i >= 2) + { + ucl_uint32 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); +} + + +#if defined(NRV2D) || defined(NRV2E) +static void code_prefix_ss12(UCL_COMPRESS_T *c, ucl_uint32 i) +{ + if (i >= 2) + { + ucl_uint32 t = 2; + do { + i -= t; + t <<= 2; + } while (i >= t); + do { + t >>= 1; + bbPutBit(c, (i & t) ? 1 : 0); + bbPutBit(c, 0); + t >>= 1; + bbPutBit(c, (i & t) ? 1 : 0); + } while (t > 2); + } + bbPutBit(c, (unsigned)i & 1); + bbPutBit(c, 1); +} +#endif + + +static void +code_match(UCL_COMPRESS_T *c, ucl_uint m_len, const ucl_uint m_off) +{ + unsigned m_low = 0; + + 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 defined(NRV2B) + 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); + } +#elif defined(NRV2D) + m_len = m_len - 1 - (m_off > M2_MAX_OFFSET); + assert(m_len > 0); + m_low = (m_len >= 4) ? 0u : (unsigned) m_len; + if (m_off == c->last_m_off) + { + bbPutBit(c, 0); + bbPutBit(c, 1); + bbPutBit(c, m_low > 1); + bbPutBit(c, m_low & 1); + } + else + { + code_prefix_ss12(c, 1 + ((m_off - 1) >> 7)); + bbPutByte(c, ((((unsigned)m_off - 1) & 0x7f) << 1) | ((m_low > 1) ? 0 : 1)); + bbPutBit(c, m_low & 1); + } + if (m_len >= 4) + code_prefix_ss11(c, m_len - 4); +#elif defined(NRV2E) + m_len = m_len - 1 - (m_off > M2_MAX_OFFSET); + assert(m_len > 0); + m_low = (m_len <= 2); + if (m_off == c->last_m_off) + { + bbPutBit(c, 0); + bbPutBit(c, 1); + bbPutBit(c, m_low); + } + else + { + code_prefix_ss12(c, 1 + ((m_off - 1) >> 7)); + bbPutByte(c, ((((unsigned)m_off - 1) & 0x7f) << 1) | (m_low ^ 1)); + } + if (m_low) + bbPutBit(c, (unsigned)m_len - 1); + else if (m_len <= 4) + { + bbPutBit(c, 1); + bbPutBit(c, (unsigned)m_len - 3); + } + else + { + bbPutBit(c, 0); + code_prefix_ss11(c, m_len - 5); + } +#else +# error +#endif + + c->last_m_off = m_off; + UCL_UNUSED(m_low); +} + + +static void +code_run(UCL_COMPRESS_T *c, const ucl_byte *ii, ucl_uint 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(UCL_COMPRESS_T *c, ucl_uint m_len, ucl_uint 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 + { +#if defined(NRV2B) + b = 1 + 10; + m_off = (m_off - 1) >> 8; + while (m_off > 0) + { + b += 2; + m_off >>= 1; + } +#elif defined(NRV2D) || defined(NRV2E) + b = 1 + 9; + m_off = (m_off - 1) >> 7; + while (m_off > 0) + { + b += 3; + m_off >>= 2; + } +#else +# error +#endif + } + +#if defined(NRV2B) || defined(NRV2D) + b += 2; + if (m_len < 3) + return b; + m_len -= 3; +#elif defined(NRV2E) + b += 2; + if (m_len < 2) + return b; + if (m_len < 4) + return b + 1; + m_len -= 4; +#else +# error +#endif + do { + b += 2; + m_len >>= 1; + } while (m_len > 0); + + return b; +} + + +/*********************************************************************** +// +************************************************************************/ + +#if !defined(NDEBUG) +static +void assert_match( const ucl_swd_p swd, ucl_uint m_len, ucl_uint m_off ) +{ + const UCL_COMPRESS_T *c = swd->c; + ucl_uint d_off; + + assert(m_len >= 2); + if (m_off <= (ucl_uint) (c->bp - c->in)) + { + assert(c->bp - m_off + m_len < c->ip); + assert(ucl_memcmp(c->bp, c->bp - m_off, m_len) == 0); + } + else + { + assert(swd->dict != NULL); + d_off = m_off - (ucl_uint) (c->bp - c->in); + assert(d_off <= swd->dict_len); + if (m_len > d_off) + { + assert(ucl_memcmp(c->bp, swd->dict_end - d_off, d_off) == 0); + assert(c->in + m_len - d_off < c->ip); + assert(ucl_memcmp(c->bp + d_off, c->in, m_len - d_off) == 0); + } + else + { + assert(ucl_memcmp(c->bp, swd->dict_end - d_off, m_len) == 0); + } + } +} +#else +# define assert_match(a,b,c) ((void)0) +#endif + + +#if defined(SWD_BEST_OFF) + +static void +better_match ( const ucl_swd_p swd, ucl_uint *m_len, ucl_uint *m_off ) +{ +} + +#endif + + +/*********************************************************************** +// +************************************************************************/ + +UCL_PUBLIC(int) +ucl_nrv_99_compress ( const ucl_bytep in, ucl_uint in_len, + ucl_bytep out, ucl_uintp out_len, + ucl_progress_callback_p cb, + int level, + const struct ucl_compress_config_p conf, + ucl_uintp result) +{ + const ucl_byte *ii; + ucl_uint lit; + ucl_uint m_len, m_off; + UCL_COMPRESS_T c_buffer; + UCL_COMPRESS_T * const c = &c_buffer; +#undef swd +#if 1 && defined(SWD_USE_MALLOC) + ucl_swd_t the_swd; +# define swd (&the_swd) +#else + ucl_swd_p swd; +#endif + ucl_uint result_buffer[16]; + int r; + + struct swd_config_t + { + unsigned try_lazy; + ucl_uint good_length; + ucl_uint max_lazy; + ucl_uint nice_length; + ucl_uint max_chain; + ucl_uint32 flags; + ucl_uint32 max_offset; + }; + const struct swd_config_t *sc; + static const struct swd_config_t swd_config[10] = { + /* faster compression */ + { 0, 0, 0, 8, 4, 0, 48*1024L }, + { 0, 0, 0, 16, 8, 0, 48*1024L }, + { 0, 0, 0, 32, 16, 0, 48*1024L }, + { 1, 4, 4, 16, 16, 0, 48*1024L }, + { 1, 8, 16, 32, 32, 0, 48*1024L }, + { 1, 8, 16, 128, 128, 0, 48*1024L }, + { 2, 8, 32, 128, 256, 0, 128*1024L }, + { 2, 32, 128, F, 2048, 1, 128*1024L }, + { 2, 32, 128, F, 2048, 1, 256*1024L }, + { 2, F, F, F, 4096, 1, N } + /* max. compression */ + }; + + if (level < 1 || level > 10) + return UCL_E_INVALID_ARGUMENT; + sc = &swd_config[level - 1]; + + memset(c, 0, sizeof(*c)); + c->ip = c->in = in; + c->in_end = in + in_len; + c->out = out; + if (cb && cb->callback) + c->cb = cb; + cb = NULL; + c->result = result ? result : (ucl_uintp) result_buffer; + memset(c->result, 0, 16*sizeof(*c->result)); + c->result[0] = c->result[2] = c->result[4] = UCL_UINT_MAX; + result = NULL; + memset(&c->conf, 0xff, sizeof(c->conf)); + if (conf) + memcpy(&c->conf, conf, sizeof(c->conf)); + conf = NULL; + r = bbConfig(c, 0, 8); + 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; + +#if !defined(swd) + swd = (ucl_swd_p) ucl_alloc(1, ucl_sizeof(*swd)); + if (!swd) + return UCL_E_OUT_OF_MEMORY; +#endif + swd->f = UCL_MIN(F, c->conf.max_match); + swd->n = UCL_MIN(N, sc->max_offset); + if (c->conf.max_offset != UCL_UINT_MAX) + swd->n = UCL_MIN(N, c->conf.max_offset); + 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) + { +#if !defined(swd) + ucl_free(swd); +#endif + 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; + + if (c->cb) + (*c->cb->callback)(0,0,-1,c->cb->user); + + c->last_m_off = 1; + r = find_match(c,swd,0,0); + if (r != UCL_E_OK) + return r; + while (c->look > 0) + { + ucl_uint ahead; + ucl_uint 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 */ +#if defined(SWD_BEST_OFF) + if (swd->use_best_off) + better_match(swd,&m_len,&m_off); +#endif + 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 = UCL_MIN(sc->try_lazy, 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; +#if defined(SWD_BEST_OFF) + if (swd->use_best_off) + better_match(swd,&c->m_len,&c->m_off); +#endif + l2 = len_of_coded_match(c,c->m_len,c->m_off); + if (l2 < 0) + continue; +#if 1 + if (l1 + (int)(ahead + c->m_len - m_len) * 5 > l2 + (int)(ahead) * 9) +#else + if (l1 > l2) +#endif + { + c->lazy++; + assert_match(swd,c->m_len,c->m_off); + +#if 0 + if (l3 > 0) + { + /* code previous run */ + code_run(c,ii,lit); + lit = 0; + /* code shortened match */ + code_match(c,ahead,m_off); + } + else +#endif + { + 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); +#if defined(NRV2B) + code_prefix_ss11(c, UCL_UINT32_C(0x1000000)); + bbPutByte(c, 0xff); +#elif defined(NRV2D) || defined(NRV2E) + code_prefix_ss12(c, UCL_UINT32_C(0x1000000)); + bbPutByte(c, 0xff); +#else +# error +#endif + bbFlushBits(c, 0); + + assert(c->textsize == in_len); + c->codesize = c->bb_op - out; + *out_len = c->bb_op - out; + if (c->cb) + (*c->cb->callback)(c->textsize,c->codesize,4,c->cb->user); + +#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); +#if !defined(swd) + ucl_free(swd); +#endif + return UCL_E_OK; +#undef swd +} + + +/* +vi:ts=4:et +*/ + -- cgit v1.2.3