diff options
Diffstat (limited to 'backends/platform/ds/arm9/source/compressor')
| -rw-r--r-- | backends/platform/ds/arm9/source/compressor/lz.cpp | 539 |
1 files changed, 0 insertions, 539 deletions
diff --git a/backends/platform/ds/arm9/source/compressor/lz.cpp b/backends/platform/ds/arm9/source/compressor/lz.cpp index 237b432ce8..1234bf7b3b 100644 --- a/backends/platform/ds/arm9/source/compressor/lz.cpp +++ b/backends/platform/ds/arm9/source/compressor/lz.cpp @@ -537,542 +537,3 @@ void LZ_Uncompress( unsigned char *in, unsigned char *out, } while( inpos < insize ); } -/************************************************************************* -* Name: lz.c -* Author: Marcus Geelnard -* Description: LZ77 coder/decoder implementation. -* Reentrant: Yes -* $Id$ -* -* The LZ77 compression scheme is a substitutional compression scheme -* proposed by Abraham Lempel and Jakob Ziv in 1977. It is very simple in -* its design, and uses no fancy bit level compression. -* -* This is my first attempt at an implementation of a LZ77 code/decoder. -* -* The principle of the LZ77 compression algorithm is to store repeated -* occurrences of strings as references to previous occurrences of the same -* string. The point is that the reference consumes less space than the -* string itself, provided that the string is long enough (in this -* implementation, the string has to be at least 4 bytes long, since the -* minimum coded reference is 3 bytes long). Also note that the term -* "string" refers to any kind of byte sequence (it does not have to be -* an ASCII string, for instance). -* -* The coder uses a brute force approach to finding string matches in the -* history buffer (or "sliding window", if you wish), which is very, very -* slow. I recon the complexity is somewhere between O(n^2) and O(n^3), -* depending on the input data. -* -* There is also a faster implementation that uses a large working buffer -* in which a "jump table" is stored, which is used to quickly find -* possible string matches (see the source code for LZ_CompressFast() for -* more information). The faster method is an order of magnitude faster, -* and also does a full string search in the entire input buffer (it does -* not use a sliding window). -* -* The upside is that decompression is very fast, and the compression ratio -* is often very good. -* -* The reference to a string is coded as a (length,offset) pair, where the -* length indicates the length of the string, and the offset gives the -* offset from the current data position. To distinguish between string -* references and literal strings (uncompressed bytes), a string reference -* is preceded by a marker byte, which is chosen as the least common byte -* symbol in the input data stream (this marker byte is stored in the -* output stream as the first byte). -* -* Occurrences of the marker byte in the stream are encoded as the marker -* byte followed by a zero byte, which means that occurrences of the marker -* byte have to be coded with two bytes. -* -* The lengths and offsets are coded in a variable length fashion, allowing -* values of any magnitude (up to 4294967295 in this implementation). -* -* With this compression scheme, the worst case compression result is -* (257/256)*insize + 1. -* -*------------------------------------------------------------------------- -* Copyright (c) 2003-2004 Marcus Geelnard -* -* 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. -* -* Marcus Geelnard -* marcus.geelnard at home.se -*************************************************************************/ - - -/************************************************************************* -* Constants used for LZ77 coding -*************************************************************************/ - -/* Maximum offset (can be any size < 2^32). Lower values gives faster - compression, while higher values gives better compression. - NOTE: LZ_CompressFast does not use this constant. */ -#define LZ_MAX_OFFSET 512 - - - -/************************************************************************* -* INTERNAL FUNCTIONS * -*************************************************************************/ - - -/************************************************************************* -* _LZ_StringCompare() - Return maximum length string match. -*************************************************************************/ - -inline static unsigned int _LZ_StringCompare( unsigned char * str1, - unsigned char * str2, unsigned int minlen, unsigned int maxlen ) -{ - unsigned int len; - - for( len = minlen; (len < maxlen) && (str1[len] == str2[len]); ++ len ); - - return len; -} - - -/************************************************************************* -* _LZ_WriteVarSize() - Write unsigned integer with variable number of -* bytes depending on value. -*************************************************************************/ - -inline static int _LZ_WriteVarSize( unsigned int x, unsigned char * buf ) -{ - unsigned int y; - int num_bytes, i, b; - - /* Determine number of bytes needed to store the number x */ - y = x >> 3; - for( num_bytes = 5; num_bytes >= 2; -- num_bytes ) - { - if( y & 0xfe000000 ) break; - y <<= 7; - } - - /* Write all bytes, seven bits in each, with 8:th bit set for all */ - /* but the last byte. */ - for( i = num_bytes-1; i >= 0; -- i ) - { - b = (x >> (i*7)) & 0x0000007f; - if( i > 0 ) - { - b |= 0x00000080; - } - *buf ++ = (unsigned char) b; - } - - /* Return number of bytes written */ - return num_bytes; -} - - -/************************************************************************* -* _LZ_ReadVarSize() - Read unsigned integer with variable number of -* bytes depending on value. -*************************************************************************/ - -inline static int _LZ_ReadVarSize( unsigned int * x, unsigned char * buf ) -{ - unsigned int y, b, num_bytes; - - /* Read complete value (stop when byte contains zero in 8:th bit) */ - y = 0; - num_bytes = 0; - do - { - b = (unsigned int) (*buf ++); - y = (y << 7) | (b & 0x0000007f); - ++ num_bytes; - } - while( b & 0x00000080 ); - - /* Store value in x */ - *x = y; - - /* Return number of bytes read */ - return num_bytes; -} - - - -/************************************************************************* -* PUBLIC FUNCTIONS * -*************************************************************************/ - - -/************************************************************************* -* LZ_Compress() - Compress a block of data using an LZ77 coder. -* in - Input (uncompressed) buffer. -* out - Output (compressed) buffer. This buffer must be 0.4% larger -* than the input buffer, plus one byte. -* insize - Number of input bytes. -* The function returns the size of the compressed data. -*************************************************************************/ - -int LZ_Compress( unsigned char *in, unsigned char *out, - unsigned int insize ) -{ - unsigned char marker, symbol; - unsigned int inpos, outpos, bytesleft, i; - unsigned int maxoffset, offset, bestoffset; - unsigned int maxlength, length, bestlength; - unsigned int histogram[ 256 ]; - unsigned char *ptr1, *ptr2; - - /* Do we have anything to compress? */ - if( insize < 1 ) - { - return 0; - } - - /* Create histogram */ - for( i = 0; i < 256; ++ i ) - { - histogram[ i ] = 0; - } - for( i = 0; i < insize; ++ i ) - { - ++ histogram[ in[ i ] ]; - } - - /* Find the least common byte, and use it as the code marker */ - marker = 0; - for( i = 1; i < 256; ++ i ) - { - if( histogram[ i ] < histogram[ marker ] ) - { - marker = i; - } - } - - /* Remember the repetition marker for the decoder */ - out[ 0 ] = marker; - - /* Start of compression */ - inpos = 0; - outpos = 1; - - /* Main compression loop */ - bytesleft = insize; - do - { - /* Determine most distant position */ - if( inpos > LZ_MAX_OFFSET ) maxoffset = LZ_MAX_OFFSET; - else maxoffset = inpos; - - /* Get pointer to current position */ - ptr1 = &in[ inpos ]; - - /* Search history window for maximum length string match */ - bestlength = 3; - bestoffset = 0; - for( offset = 3; offset <= maxoffset; ++ offset ) - { - /* Get pointer to candidate string */ - ptr2 = &ptr1[ -offset ]; - - /* Quickly determine if this is a candidate (for speed) */ - if( (ptr1[ 0 ] == ptr2[ 0 ]) && - (ptr1[ bestlength ] == ptr2[ bestlength ]) ) - { - /* Determine maximum length for this offset */ - maxlength = (bytesleft < offset ? bytesleft : offset); - - /* Count maximum length match at this offset */ - length = _LZ_StringCompare( ptr1, ptr2, 0, maxlength ); - - /* Better match than any previous match? */ - if( length > bestlength ) - { - bestlength = length; - bestoffset = offset; - } - } - } - - /* Was there a good enough match? */ - if( (bestlength >= 8) || - ((bestlength == 4) && (bestoffset <= 0x0000007f)) || - ((bestlength == 5) && (bestoffset <= 0x00003fff)) || - ((bestlength == 6) && (bestoffset <= 0x001fffff)) || - ((bestlength == 7) && (bestoffset <= 0x0fffffff)) ) - { - out[ outpos ++ ] = (unsigned char) marker; - outpos += _LZ_WriteVarSize( bestlength, &out[ outpos ] ); - outpos += _LZ_WriteVarSize( bestoffset, &out[ outpos ] ); - inpos += bestlength; - bytesleft -= bestlength; - } - else - { - /* Output single byte (or two bytes if marker byte) */ - symbol = in[ inpos ++ ]; - out[ outpos ++ ] = symbol; - if( symbol == marker ) - { - out[ outpos ++ ] = 0; - } - -- bytesleft; - } - } - while( bytesleft > 3 ); - - /* Dump remaining bytes, if any */ - while( inpos < insize ) - { - if( in[ inpos ] == marker ) - { - out[ outpos ++ ] = marker; - out[ outpos ++ ] = 0; - } - else - { - out[ outpos ++ ] = in[ inpos ]; - } - ++ inpos; - } - - return outpos; -} - - -/************************************************************************* -* LZ_CompressFast() - Compress a block of data using an LZ77 coder. -* in - Input (uncompressed) buffer. -* out - Output (compressed) buffer. This buffer must be 0.4% larger -* than the input buffer, plus one byte. -* insize - Number of input bytes. -* work - Pointer to a temporary buffer (internal working buffer), which -* must be able to hold (insize+65536) unsigned integers. -* The function returns the size of the compressed data. -*************************************************************************/ - -int LZ_CompressFast( unsigned char *in, unsigned char *out, - unsigned int insize, unsigned int *work ) -{ - unsigned char marker, symbol; - unsigned int inpos, outpos, bytesleft, i, index, symbols; - unsigned int offset, bestoffset; - unsigned int maxlength, length, bestlength; - unsigned int histogram[ 256 ], *lastindex, *jumptable; - unsigned char *ptr1, *ptr2; - - /* Do we have anything to compress? */ - if( insize < 1 ) - { - return 0; - } - - /* Assign arrays to the working area */ - lastindex = work; - jumptable = &work[ 65536 ]; - - /* Build a "jump table". Here is how the jump table works: - jumptable[i] points to the nearest previous occurrence of the same - symbol pair as in[i]:in[i+1], so in[i] == in[jumptable[i]] and - in[i+1] == in[jumptable[i]+1]. Following the jump table gives a - dramatic boost for the string search'n'match loop compared to doing - a brute force search. */ - for( i = 0; i < 65536; ++ i ) - { - lastindex[ i ] = 0xffffffff; - } - for( i = 0; i < insize-1; ++ i ) - { - symbols = (((unsigned int)in[i]) << 8) | ((unsigned int)in[i+1]); - index = lastindex[ symbols ]; - lastindex[ symbols ] = i; - jumptable[ i ] = index; - } - jumptable[ insize-1 ] = 0xffffffff; - - /* Create histogram */ - for( i = 0; i < 256; ++ i ) - { - histogram[ i ] = 0; - } - for( i = 0; i < insize; ++ i ) - { - ++ histogram[ in[ i ] ]; - } - - /* Find the least common byte, and use it as the code marker */ - marker = 0; - for( i = 1; i < 256; ++ i ) - { - if( histogram[ i ] < histogram[ marker ] ) - { - marker = i; - } - } - - /* Remember the repetition marker for the decoder */ - out[ 0 ] = marker; - - /* Start of compression */ - inpos = 0; - outpos = 1; - - /* Main compression loop */ - bytesleft = insize; - do - { - /* Get pointer to current position */ - ptr1 = &in[ inpos ]; - - /* Search history window for maximum length string match */ - bestlength = 3; - bestoffset = 0; - index = jumptable[ inpos ]; - while( index != 0xffffffff ) - { - /* Get pointer to candidate string */ - ptr2 = &in[ index ]; - - /* Quickly determine if this is a candidate (for speed) */ - if( ptr2[ bestlength ] == ptr1[ bestlength ] ) - { - /* Determine maximum length for this offset */ - offset = inpos - index; - maxlength = (bytesleft < offset ? bytesleft : offset); - - /* Count maximum length match at this offset */ - length = _LZ_StringCompare( ptr1, ptr2, 2, maxlength ); - - /* Better match than any previous match? */ - if( length > bestlength ) - { - bestlength = length; - bestoffset = offset; - } - } - - /* Get next possible index from jump table */ - index = jumptable[ index ]; - } - - /* Was there a good enough match? */ - if( (bestlength >= 8) || - ((bestlength == 4) && (bestoffset <= 0x0000007f)) || - ((bestlength == 5) && (bestoffset <= 0x00003fff)) || - ((bestlength == 6) && (bestoffset <= 0x001fffff)) || - ((bestlength == 7) && (bestoffset <= 0x0fffffff)) ) - { - out[ outpos ++ ] = (unsigned char) marker; - outpos += _LZ_WriteVarSize( bestlength, &out[ outpos ] ); - outpos += _LZ_WriteVarSize( bestoffset, &out[ outpos ] ); - inpos += bestlength; - bytesleft -= bestlength; - } - else - { - /* Output single byte (or two bytes if marker byte) */ - symbol = in[ inpos ++ ]; - out[ outpos ++ ] = symbol; - if( symbol == marker ) - { - out[ outpos ++ ] = 0; - } - -- bytesleft; - } - } - while( bytesleft > 3 ); - - /* Dump remaining bytes, if any */ - while( inpos < insize ) - { - if( in[ inpos ] == marker ) - { - out[ outpos ++ ] = marker; - out[ outpos ++ ] = 0; - } - else - { - out[ outpos ++ ] = in[ inpos ]; - } - ++ inpos; - } - - return outpos; -} - - -/************************************************************************* -* LZ_Uncompress() - Uncompress a block of data using an LZ77 decoder. -* in - Input (compressed) buffer. -* out - Output (uncompressed) buffer. This buffer must be large -* enough to hold the uncompressed data. -* insize - Number of input bytes. -*************************************************************************/ - -void LZ_Uncompress( unsigned char *in, unsigned char *out, - unsigned int insize ) -{ - unsigned char marker, symbol; - unsigned int i, inpos, outpos, length, offset; - - /* Do we have anything to compress? */ - if( insize < 1 ) - { - return; - } - - /* Get marker symbol from input stream */ - marker = in[ 0 ]; - inpos = 1; - - /* Main decompression loop */ - outpos = 0; - do - { - symbol = in[ inpos ++ ]; - if( symbol == marker ) - { - /* We had a marker byte */ - if( in[ inpos ] == 0 ) - { - /* It was a single occurrence of the marker byte */ - out[ outpos ++ ] = marker; - ++ inpos; - } - else - { - /* Extract true length and offset */ - inpos += _LZ_ReadVarSize( &length, &in[ inpos ] ); - inpos += _LZ_ReadVarSize( &offset, &in[ inpos ] ); - - /* Copy corresponding data from history window */ - for( i = 0; i < length; ++ i ) - { - out[ outpos ] = out[ outpos - offset ]; - ++ outpos; - } - } - } - else - { - /* No marker, plain copy */ - out[ outpos ++ ] = symbol; - } - } - while( inpos < insize ); -} |