LZSSCompress Class Reference

#include <lzsscomprs.h>

Inheritance diagram for LZSSCompress:

Collaboration diagram for LZSSCompress:

Classes
class	Private

Public Member Functions
virtual void	decode (void)
virtual void	encode (void)
virtual unsigned long	getChars (char *buf, unsigned long len)
virtual char *	getCompressedBuf (unsigned long *len=0)
virtual int	getLevel ()
virtual char *	getUncompressedBuf (unsigned long *len=0)
	LZSSCompress ()
virtual unsigned long	sendChars (char *buf, unsigned long len)
virtual void	setCompressedBuf (unsigned long *len, char *buf=0)
virtual void	setLevel (int l)
virtual void	setUncompressedBuf (const char *buf=0, unsigned long *len=0)
virtual	~LZSSCompress ()

Protected Attributes
char *	buf
char	direct
int	level
unsigned long	pos
unsigned long	slen
char *	zbuf
unsigned long	zlen
unsigned long	zpos

Private Attributes
Private *	p

Detailed Description

Definition at line 33 of file lzsscomprs.h.

Constructor & Destructor Documentation

LZSSCompress::LZSSCompress

(

)

Definition at line 132 of file lzsscomprs.cpp.

                           : SWCompress() {
    p = new Private();
}

LZSSCompress::~LZSSCompress ( )

virtual

Definition at line 141 of file lzsscomprs.cpp.

                            {
    delete p;
}

Member Function Documentation

void LZSSCompress::decode ( void  )

virtual

Reimplemented from SWCompress.

Definition at line 611 of file lzsscomprs.cpp.

{
    int k;
    int r;                            // node number
    unsigned char c[F];              // an array of chars
    unsigned char flags;                // 8 bits of flags
    int flag_count;                  // which flag we're on
    short int pos;                    // position in the ring buffer
    short int len;                    // number of chars in ring buffer
    unsigned long totalLen = 0;

    direct = 1; // set direction needed by parent [Get|Send]Chars()

    // Initialize the ring buffer with a common string.
    //
    // Note that the last F bytes of the ring buffer are not filled.

    memset(p->m_ring_buffer, ' ', N - F);
    
    r = N - F;

    flags = (char) 0;
    flag_count = 0;

    for ( ; ; ) {

        // If there are more bits of interest in this flag, then
        // shift that next interesting bit into the 1's position.
        //
        // If this flag has been exhausted, the next byte must 
        // be a flag.

        if (flag_count > 0) {
            flags = (unsigned char) (flags >> 1);
            flag_count--;
        }
        else {
            // Next byte must be a flag.

            if (getChars((char *) &flags, 1) != 1)
                break;

            // Set the flag counter.  While at first it might appear
            // that this should be an 8 since there are 8 bits in the
            // flag, it should really be a 7 because the shift must
            // be performed 7 times in order to see all 8 bits.

            flag_count = 7;
        }

        // If the low order bit of the flag is now set, then we know
        // that the next byte is a single, unencoded character.

        if (flags & 1) {
            if (getChars((char *) c, 1) != 1)
                break;

            if (sendChars((char *) c, 1) != 1) {
                break;
            }
            totalLen++;

            // Add to buffer, and increment to next spot. Wrap at end.

            p->m_ring_buffer[r] = c[0];
            r = (short int) ( (r + 1) & (N - 1) );
        }

        // Otherwise, we know that the next two bytes are a
        // <position,length> pair.  The position is in 12 bits and
        // the length is in 4 bits.

        else {
            // Original code:
            //  if ((i = getc(infile)) == EOF)
            //    break;
            //  if ((j = getc(infile)) == EOF)
            //    break;
            //  i |= ((j & 0xf0) << 4); 
            //  j = (j & 0x0f) + THRESHOLD;
            //
            // I've modified this to only make one input call, and
            // have changed the variable names to something more
            // obvious.

            if (getChars((char *) c, 2) != 2)
                break;

            // Convert these two characters into the position and
            // length.  Note that the length is always at least
            // THRESHOLD, which is why we're able to get a length
            // of 18 out of only 4 bits.

            pos = (short int) ( c[0] | ((c[1] & 0xf0) << 4) );

            len = (short int) ( (c[1] & 0x0f) + THRESHOLD );

            // There are now "len" characters at position "pos" in
            // the ring buffer that can be pulled out.  Note that
            // len is never more than F.

            for (k = 0; k < len; k++) {
                c[k] = p->m_ring_buffer[(pos + k) & (N - 1)];

                // Add to buffer, and increment to next spot. Wrap at end.

                p->m_ring_buffer[r] = c[k];
                r = (short int) ( (r + 1) & (N - 1) );
            }

            // Add the "len" :characters to the output stream.

            if (sendChars((char *) c, len) != (unsigned int)len) {
                break;
            }
            totalLen += len;
        }
    }
    slen = totalLen;
}

void LZSSCompress::encode ( void  )

virtual

Reimplemented from SWCompress.

Definition at line 367 of file lzsscomprs.cpp.

{
    short int i;                        // an iterator
    short int r;                        // node number in the binary tree
    short int s;                        // position in the ring buffer
    unsigned short int len;          // len of initial string
    short int last_match_length;        // length of last match
    short int code_buf_pos;          // position in the output buffer
    unsigned char code_buf[17];      // the output buffer
    unsigned char mask;              // bit mask for byte 0 of out buf
    unsigned char c;                    // character read from string

    // Start with a clean tree.

    p->InitTree();
    direct = 0; // set direction needed by parent [Get|Send]Chars()

    // code_buf[0] works as eight flags.  A "1" represents that the
    // unit is an unencoded letter (1 byte), and a "0" represents
    // that the next unit is a <position,length> pair (2 bytes).
    //
    // code_buf[1..16] stores eight units of code.  Since the best
    // we can do is store eight <position,length> pairs, at most 16 
    // bytes are needed to store this.
    //
    // This is why the maximum size of the code buffer is 17 bytes.

    code_buf[0] = 0;
    code_buf_pos = 1;

    // Mask iterates over the 8 bits in the code buffer.  The first
    // character ends up being stored in the low bit.
    //
    //  bit   8   7   6   5   4   3   2   1
    //      |                          |
    //      |            first sequence in code buffer
    //      |
    //    last sequence in code buffer      

    mask = 1;

    s = 0;
    r = (short int) N - (short int) F;

    // Initialize the ring buffer with spaces...

    // Note that the last F bytes of the ring buffer are not filled.
    // This is because those F bytes will be filled in immediately
    // with bytes from the input stream.

    memset(p->m_ring_buffer, ' ', N - F);
    
    // Read F bytes into the last F bytes of the ring buffer.
    //
    // This function loads the buffer with X characters and returns
    // the actual amount loaded.

    len = getChars((char *) &(p->m_ring_buffer[r]), F);

    // Make sure there is something to be compressed.

    if (len == 0)
        return;

    // Insert the F strings, each of which begins with one or more
    // 'space' characters.  Note the order in which these strings
    // are inserted.  This way, degenerate trees will be less likely
    // to occur.

    for (i = 1; i <= F; i++) {
        p->InsertNode((short int) (r - i));
    }

    // Finally, insert the whole string just read.  The
    // member variables match_length and match_position are set.

    p->InsertNode(r);

    // Now that we're preloaded, continue till done.

    do {

        // m_match_length may be spuriously long near the end of
        // text.

        if (p->m_match_length > len) {
            p->m_match_length = len;
        }

        // Is it cheaper to store this as a single character?  If so,
        // make it so.

        if (p->m_match_length < THRESHOLD) {
            // Send one character.  Remember that code_buf[0] is the
            // set of flags for the next eight items.

            p->m_match_length = 1;   
            code_buf[0] |= mask;  
            code_buf[code_buf_pos++] = p->m_ring_buffer[r];
        }

        // Otherwise, we do indeed have a string that can be stored
        // compressed to save space.

        else {
            // The next 16 bits need to contain the position (12 bits)
            // and the length (4 bits).

            code_buf[code_buf_pos++] = (unsigned char) p->m_match_position;
            code_buf[code_buf_pos++] = (unsigned char) (
                ((p->m_match_position >> 4) & 0xf0) | 
                (p->m_match_length - THRESHOLD) );
        }

        // Shift the mask one bit to the left so that it will be ready
        // to store the new bit.

        mask = (unsigned char) (mask << 1);

        // If the mask is now 0, then we know that we have a full set
        // of flags and items in the code buffer.  These need to be
        // output.

        if (!mask) {
            // code_buf is the buffer of characters to be output.
            // code_buf_pos is the number of characters it contains.

            sendChars((char *) code_buf, code_buf_pos);

            // Reset for next buffer...

            code_buf[0] = 0;
            code_buf_pos = 1;
            mask = 1;
        }

        last_match_length = p->m_match_length;

        // Delete old strings and read new bytes...

        for (i = 0; i < last_match_length; i++) {
            // Get next character...

            if (getChars((char *) &c, 1) != 1)
                break;

            // Delete "old strings"

            p->DeleteNode(s);

            // Put this character into the ring buffer.
            //        
            // The original comment here says "If the position is near
            // the end of the buffer, extend the buffer to make
            // string comparison easier."
            //
            // That's a little misleading, because the "end" of the 
            // buffer is really what we consider to be the "beginning"
            // of the buffer, that is, positions 0 through F.
            //
            // The idea is that the front end of the buffer is duplicated
            // into the back end so that when you're looking at characters
            // at the back end of the buffer, you can index ahead (beyond
            // the normal end of the buffer) and see the characters
            // that are at the front end of the buffer wihtout having
            // to adjust the index.
            //
            // That is...
            //
            //    1234xxxxxxxxxxxxxxxxxxxxxxxxxxxxx1234
            //    |                            |  |
            //    position 0          end of buffer  |
            //                                       |
            //                duplicate of front of buffer

            p->m_ring_buffer[s] = c;

            if (s < F - 1) {
                p->m_ring_buffer[s + N] = c;
            }

            // Increment the position, and wrap around when we're at
            // the end.  Note that this relies on N being a power of 2.

            s = (short int) ( (s + 1) & (N - 1) );
            r = (short int) ( (r + 1) & (N - 1) );

            // Register the string that is found in 
            // m_ring_buffer[r..r+F-1].

            p->InsertNode(r);
        }

        // If we didn't quit because we hit the last_match_length,
        // then we must have quit because we ran out of characters
        // to process.

        while (i++ < last_match_length) {                             
            p->DeleteNode(s);

            s = (short int) ( (s + 1) & (N - 1) );
            r = (short int) ( (r + 1) & (N - 1) );

            // Note that len hitting 0 is the key that causes the
            // do...while() to terminate.  This is the only place
            // within the loop that len is modified.
            //
            // Its original value is F (or a number less than F for
            // short strings).

            if (--len) {
                p->InsertNode(r);      /* buffer may not be empty. */
            }
        }

        // End of do...while() loop.  Continue processing until there
        // are no more characters to be compressed.  The variable
        // "len" is used to signal this condition.
    } while (len > 0);

    // There could still be something in the output buffer.  Send it
    // now.

    if (code_buf_pos > 1) {
        // code_buf is the encoded string to send.
        // code_buf_ptr is the number of characters.

        sendChars((char *) code_buf, code_buf_pos);
    }


    // must set zlen for parent class to know length of compressed buffer
    zlen = zpos;
}

unsigned long SWCompress::getChars ( char *  buf, unsigned long  len  )

virtualinherited

Definition at line 121 of file swcomprs.cpp.

                                                                {
    if (direct) {
        len = (((zlen - zpos) > (unsigned)len) ? len : zlen - zpos);
        if (len > 0) {
            memmove(ibuf, &zbuf[zpos], len);
            zpos += len;
        }
    }
    else {
//      slen = strlen(buf);
        len = (((slen - pos) > (unsigned)len) ? len : slen - pos);
        if (len > 0) {
            memmove(ibuf, &buf[pos], len);
            pos += len;
        }
    }
    return len;
}

char * SWCompress::getCompressedBuf ( unsigned long *  len = 0 )

virtualinherited

Definition at line 111 of file swcomprs.cpp.

                                                     {
    if (!zbuf) {
        direct = 0;
        encode();
    }
    if (len) *len = zlen;
    return zbuf;
}

virtual int SWCompress::getLevel ( )

inlinevirtualinherited

Definition at line 54 of file swcomprs.h.

{return level;};

char * SWCompress::getUncompressedBuf ( unsigned long *  len = 0 )

virtualinherited

Definition at line 90 of file swcomprs.cpp.

                                                       {
    if (!buf) {
        buf = (char *)calloc(1,1); // be sure we at least allocate an empty buf for return;
        direct = 1;
        decode();
    }
    if (len) *len = slen;
    return buf;
}

unsigned long SWCompress::sendChars ( char *  buf, unsigned long  len  )

virtualinherited

Definition at line 141 of file swcomprs.cpp.

                                                                 {
    if (direct) {
        if (buf) {
//          slen = strlen(buf);
            if ((pos + len) > (unsigned)slen) {
                buf = (char *) realloc(buf, pos + len + 1024);
                memset(&buf[pos], 0, len + 1024);
            }
        }
        else    buf = (char *)calloc(1, len + 1024);
        memmove(&buf[pos], ibuf, len);
        pos += len;
    }
    else {
        if (zbuf) {
            if ((zpos + len) > zlen) {
                zbuf = (char *) realloc(zbuf, zpos + len + 1024);
                zlen = zpos + len + 1024;
            }
        }
        else {
            zbuf = (char *)calloc(1, len + 1024);
            zlen = len + 1024;
        }
        memmove(&zbuf[zpos], ibuf, len);
        zpos += len;
    }
    return len;
}

void SWCompress::setCompressedBuf ( unsigned long *  len, char *  buf = 0  )

virtualinherited

Definition at line 101 of file swcomprs.cpp.

                                                                {
    if (ibuf) {
        init();
        zbuf = (char *) malloc(*len);
        memcpy(zbuf, ibuf, *len);
        zlen = *len;
    }
    *len = zlen;
}

virtual void SWCompress::setLevel ( int  l )

inlinevirtualinherited

Reimplemented in XzCompress.

Definition at line 53 of file swcomprs.h.

{level = l;};

void SWCompress::setUncompressedBuf ( const char *  buf = 0, unsigned long *  len = 0  )

virtualinherited

Definition at line 75 of file swcomprs.cpp.

                                                                        {
    if (ibuf) {
        init();
        slen = (len) ? *len : strlen(ibuf);
        buf = (char *) calloc(slen + 1, 1);
        memcpy(buf, ibuf, slen);
    }
    if (!buf) {
        buf = (char *)calloc(1,1); // be sure we at least allocate an empty buf for return;
        direct = 1;
        decode();
        if (len) *len = slen;
    }
}

Member Data Documentation

char* SWCompress::buf

mutableprotectedinherited

Definition at line 38 of file swcomprs.h.

char SWCompress::direct

mutableprotectedinherited

Definition at line 38 of file swcomprs.h.

int SWCompress::level

protectedinherited

Definition at line 40 of file swcomprs.h.

Private* LZSSCompress::p

private

Definition at line 35 of file lzsscomprs.h.

unsigned long SWCompress::pos

protectedinherited

Definition at line 39 of file swcomprs.h.

unsigned long SWCompress::slen

protectedinherited

Definition at line 39 of file swcomprs.h.

char * SWCompress::zbuf

mutableprotectedinherited

Definition at line 38 of file swcomprs.h.

unsigned long SWCompress::zlen

protectedinherited

Definition at line 39 of file swcomprs.h.

unsigned long SWCompress::zpos

protectedinherited

Definition at line 39 of file swcomprs.h.

---

The documentation for this class was generated from the following files:

• include/lzsscomprs.h
• src/modules/common/lzsscomprs.cpp