Subversion Repositories lzrw1-compressor-core

/**************************************************************************************************************

*

*    L Z R W 1   E N C O D E R   C O R E

*

*  A high throughput loss less data compression core.

*

* Copyright 2012-2013   Lukas Schrittwieser (LS)

*

*    This program 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.

*

*    This program 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 this program; if not, write to the Free Software

*    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

*    Or see <http://www.gnu.org/licenses/>

*

***************************************************************************************************************

*

* Change Log:

*

* Version 1.0 - 2013/04/05 - LS

*   released

*

***************************************************************************************************************

*

* This is an example decoder (decompressor) for which can be used to decompress data encoded by the core.

*

***************************************************************************************************************/

package org.sump.analyzer;

import java.io.IOException;

class LZRW1Decoder

{

        final static boolean DEBUG = false;             // set this to true for detailed debug output to the console

        final static int HISTORY_LEN = 4096;    // buffer length in bytes 

        final static int LOOK_AHEAD_LEN = 16;   // look ahead buffer length in bytes

        final static int HASH_BIT_LEN = 11;     // number of bits for the index in the hash table

        /* configer the number of items (offset-length-tuples or literals) per frame */

        public final int ITEMS_PER_FRAME = 8;

        public LZRW1Decoder ()

        {

                // allocate the history buffer

                buffer = new int[HISTORY_LEN];

                validBufferLen = 0;

                histWrInd = 0;

                flags = 0;

                frameItemCnt = 0;

                offset = -1;

                copyCnt = 0;

                readIndex = 0;

                endOfData = false;

                if (DEBUG)

                        System.out.println("LZRW1Decoder constructed");

        }

        /**

        * Loads a block of compressed data into the module. Decoding will start at a given offset.

        * @param cd             The data to be decompressed

        * @param o              Index of the first byte of encoded data in cd

        */

        void loadCompressedData (byte [] cd, int o)

        {

                compressed = cd;

                // reset all internal states for a new stream

                validBufferLen = 0;

                histWrInd = 0;

                flags = 0;

                frameItemCnt = 0;

                offset = -1;

                copyCnt = 0;

                readIndex = o;

                endOfData = false;

                if (DEBUG)

                        System.out.println("compressed data loaded");

        }

        /**

        * Decompresses one byte of data stored in source block and returns it. If no source data is available an

        * exception will be created. If the end-of-data symbol is encountered -1 will be returned. If the compressed

        * data ends without an end-of-data symbol an exception will be created as well. Any data after an end-of-data

        * symbol will be ignored and can not be decoded. However the method may still be called, it will keep returning

        * -1 to indicated the end of the decoded data.

        * @return       The next byte in the stream of decoded data. -1 if end-of-data was reached

        * @throws IOException if an error is found in the encoded data

        */

        int decodeNextByte () throws IOException

        {

                int ch = 0;              // decoded char (to be returned)

                // make sure that we have data

                if (compressed == null)

                        throw new IOException("no compressed data loaded");

                if (endOfData)

                        return -1;

                // check wether we can copy data from the stream history (due to a offset/length pair found earlier)

                if (copyCnt > 0)

                {

                        ch = readFromHistory();

                        copyCnt--;

                        // the byte is decoded, it becomes part of the stream history

                        insertIntoHistBuf(ch);

                        return ch;

                }

                // get next byte from compressed data stream

                if (readIndex >= compressed.length)

                        throw new IOException("encountered end of compressed data without end-of-data symbol (data corrupt)");

                ch = compressed[readIndex++];

                // load a new header if necessary

                if (frameItemCnt==0)

                {

                        flags = ch&0xff;

                        if (DEBUG)

                                System.out.printf("   found header: %02x\n",flags);

                        frameItemCnt = 8;

                        // load the next byte

                        if (readIndex >= compressed.length)

                                throw new IOException("encountered end of compressed data without end-of-data symbol (data corrupt)");

                        ch = compressed[readIndex++];

                }

                // check whether we have a pair or not

                if ((flags&0x01) == 1)

                {

                        // this is a length-offset pair, load the second byte

                        if (readIndex >= compressed.length)

                                throw new IOException("encountered end of compressed data without end-of-data symbol (data corrupt)");

                        int lowByte = compressed[readIndex++];

                        int highByte = ch;

                        // decode the pair into offset and length

                        copyCnt = (highByte>>4) & 0x0f;

                        offset = ((highByte<<8)&0x0f00) + (lowByte&0xff);

                        // check for the end-of-data symbol

                        if ((offset==0) && (copyCnt==0))

                        {

                                if (DEBUG)

                                        System.out.println("   found end of data symbol");

                                endOfData = true;

                                // check that there is no data left in the encoded input

                                /*if (readIndex < compressed.length)

                                        throw new IOException("compressed data after end-of-data symbol (data corrupt) "+readIndex+"  "+compressed.length);*/

                                return -1;

                        }

                        copyCnt++;      // Note: the encoder saves the number of byte to be copied minus 1 to save some space (2 means copy 3 bytes, and so on)

                        if (DEBUG)

                                System.out.println("len:"+copyCnt+" off:"+offset);

                        // load the first copy byte from the history buffer

                        ch = readFromHistory();

                        copyCnt--;      // one byte copied

                        // this byte is decoded, it becomes part of the stream history

                        insertIntoHistBuf(ch);

                }

                else

                {

                        // convert the signed char (-128..127) to an unsigned value

                        //if (ch < 0)

                        //      ch += 256;

                        ch &= 0xff;

                        // this is a literal

                        if (DEBUG)

                                System.out.printf("lit: '%c'=%02x\n",ch,ch);

                        // save this byte in the history buffer

                        insertIntoHistBuf(ch);

                }

                // shift header for next byte

                frameItemCnt--;

                flags >>= 1;

                return ch;

        }

        /**

        * read one byte from the history buffer from the position defined by offset.

        */

        private int readFromHistory() throws IOException

        {

                if (offset >= validBufferLen)

                        throw new IOException("offset is pointing to a location before the beginning of the data (data corrupt)");

                // calculate index (move back offset bytes) from last one (-1 because histWrInd point to next free location)    

                int ind = histWrInd-offset-1;

                if (ind < 0)     // wrap around (ring buffer)

                        ind += HISTORY_LEN;

                if (ind < 0)

                        // index is still negative, this is an error in the encoded data

                        throw new IOException("Offset wraps more than once in history buffer (data corrupt)");

                // load the byte from the histroy buffer        

                return buffer[ind];

        }

        private void insertIntoHistBuf (int ch)

        {

                buffer[histWrInd++] = ch;

                if (histWrInd >= buffer.length)

                        histWrInd = 0;

                // count the number of valid bytes in the histroy buffer

                if (validBufferLen < HISTORY_LEN)

                        validBufferLen++;

        }

        int [] buffer;

        int validBufferLen;

        int histWrInd;

        int flags;

        int frameItemCnt;

        int offset;

        int copyCnt;

        byte [] compressed;     // holds the compressed data

        int readIndex;

        boolean endOfData;

}