#include "kis_lzf_compression.h"
#include "kis_debug.h"

Macros
#define	HASH_LOG 12

#define	HASH_MASK (HASH_SIZE-1)

#define	HASH_SIZE (1<< HASH_LOG)

#define	MAX_COPY 32

#define	MAX_DISTANCE 8192

#define	MAX_LEN 264 /* 256 + 8 */

#define	UPDATE_HASH(v, p) { v = ((quint16)p); v ^= ((quint16)(p+1))^(v>>(16-HASH_LOG)); }

Functions
int	lzff_compress (const void input, int length, void output, int)

int	lzff_decompress (const void input, int length, void output, int maxout)

Macro Definition Documentation

◆ HASH_LOG

#define HASH_LOG 12

Definition at line 12 of file kis_lzf_compression.cpp.

◆ HASH_MASK

#define HASH_MASK (HASH_SIZE-1)

Definition at line 14 of file kis_lzf_compression.cpp.

◆ HASH_SIZE

#define HASH_SIZE (1<< HASH_LOG)

Definition at line 13 of file kis_lzf_compression.cpp.

◆ MAX_COPY

#define MAX_COPY 32

Definition at line 21 of file kis_lzf_compression.cpp.

◆ MAX_DISTANCE

#define MAX_DISTANCE 8192

Definition at line 23 of file kis_lzf_compression.cpp.

◆ MAX_LEN

#define MAX_LEN 264 /* 256 + 8 */

Definition at line 22 of file kis_lzf_compression.cpp.

◆ UPDATE_HASH

#define UPDATE_HASH	(		v,
			p ) { v = ((quint16)p); v ^= ((quint16)(p+1))^(v>>(16-HASH_LOG)); }

Definition at line 19 of file kis_lzf_compression.cpp.

Function Documentation

◆ lzff_compress()

int lzff_compress	(	const void *	input,
		int	length,
		void *	output,
		int	)

Definition at line 28 of file kis_lzf_compression.cpp.

{
    const quint8* ip = (const quint8*) input;
    const quint8* ip_limit = ip + length - MAX_COPY - 4;
    quint8* op = (quint8*) output;
 
    const quint8* htab[HASH_SIZE];
    const quint8** hslot;
    quint32 hval;
 
    quint8* ref;
    qint32 copy;
    qint32 len;
    qint32 distance;
    quint8* anchor;
 
    /* initializes hash table */
    for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
        *hslot = ip;
 
    /* we start with literal copy */
    copy = 0;
    *op++ = MAX_COPY - 1;
 
    /* main loop */
    while (ip < ip_limit) {
        /* find potential match */
        UPDATE_HASH(hval, ip);
        hslot = htab + (hval & HASH_MASK);
        ref = (quint8*) * hslot;
 
        /* update hash table */
        *hslot = ip;
 
        /* find itself? then it's no match */
        if (ip == ref)
            goto literal;
 
        /* is this a match? check the first 2 bytes */
        if (*((quint16*)ref) != *((quint16*)ip))
            goto literal;
 
        /* now check the 3rd byte */
        if (ref[2] != ip[2])
            goto literal;
 
        /* calculate distance to the match */
        distance = ip - ref;
 
        /* skip if too far away */
        if (distance >= MAX_DISTANCE)
            goto literal;
 
        /* here we have 3-byte matches */
        anchor = (quint8*)ip;
        len = 3;
        ref += 3;
        ip += 3;
 
        /* now we have to check how long the match is */
        if (ip < ip_limit - MAX_LEN) {
            while (len < MAX_LEN - 8) {
                /* unroll 8 times */
                if (*ref++ != *ip++) break;
                if (*ref++ != *ip++) break;
                if (*ref++ != *ip++) break;
                if (*ref++ != *ip++) break;
                if (*ref++ != *ip++) break;
                if (*ref++ != *ip++) break;
                if (*ref++ != *ip++) break;
                if (*ref++ != *ip++) break;
                len += 8;
            }
            ip--;
        }
        len = ip - anchor;
 
        /* just before the last non-matching byte */
        ip = anchor + len;
 
        /* if we have copied something, adjust the copy count */
        if (copy) {
            /* copy is biased, '0' means 1 byte copy */
            anchor = anchor - copy - 1;
            *(op - copy - 1) = copy - 1;
            copy = 0;
        } else
            /* back, to overwrite the copy count */
            op--;
 
        /* length is biased, '1' means a match of 3 bytes */
        len -= 2;
 
        /* distance is also biased */
        distance--;
 
        /* encode the match */
        if (len < 7)
            *op++ = (len << 5) + (distance >> 8);
        else {
            *op++ = (7 << 5) + (distance >> 8);
            *op++ = len - 7;
        }
        *op++ = (distance & 255);
 
        /* assuming next will be literal copy */
        *op++ = MAX_COPY - 1;
 
        /* update the hash at match boundary */
        --ip;
        UPDATE_HASH(hval, ip);
        htab[hval & HASH_MASK] = ip;
        ip++;
 
        continue;
 
    literal:
        *op++ = *ip++;
        copy++;
        if (copy >= MAX_COPY) {
            copy = 0;
            *op++ = MAX_COPY - 1;
        }
    }
 
    /* left-over as literal copy */
    ip_limit = (const quint8*)input + length;
    while (ip < ip_limit) {
        *op++ = *ip++;
        copy++;
        if (copy == MAX_COPY) {
            copy = 0;
            *op++ = MAX_COPY - 1;
        }
    }
 
    /* if we have copied something, adjust the copy length */
    if (copy)
        *(op - copy - 1) = copy - 1;
    else
        op--;
 
    return op - (quint8*)output;
}

References distance(), HASH_MASK, HASH_SIZE, length(), MAX_COPY, MAX_DISTANCE, MAX_LEN, and UPDATE_HASH.

◆ lzff_decompress()

int lzff_decompress	(	const void *	input,
		int	length,
		void *	output,
		int	maxout )

Definition at line 173 of file kis_lzf_compression.cpp.

{
    const quint8* ip = (const quint8*) input;
    const quint8* ip_limit  = ip + length - 1;
    quint8* op = (quint8*) output;
    quint8* op_limit = op + maxout;
    quint8* ref;
 
    while (ip < ip_limit) {
        quint32 ctrl = (*ip) + 1;
        quint32 ofs = ((*ip) & 31) << 8;
        quint32 len = (*ip++) >> 5;
 
        if (ctrl < 33) {
            /* literal copy */
            if (op + ctrl > op_limit)
                return 0;
 
            /* crazy unrolling */
            if (ctrl) {
                *op++ = *ip++;
                ctrl--;
 
                if (ctrl) {
                    *op++ = *ip++;
                    ctrl--;
 
                    if (ctrl) {
                        *op++ = *ip++;
                        ctrl--;
 
                        for (; ctrl; ctrl--)
                            *op++ = *ip++;
                    }
                }
            }
        } else {
            /* back reference */
            len--;
            ref = op - ofs;
            ref--;
 
            if (len == 7 - 1)
                len += *ip++;
 
            ref -= *ip++;
 
            if (op + len + 3 > op_limit)
                return 0;
 
            if (ref < (quint8 *)output)
                return 0;
 
            *op++ = *ref++;
            *op++ = *ref++;
            *op++ = *ref++;
            if (len)
                for (; len; --len)
                    *op++ = *ref++;
        }
    }
 
    return op - (quint8*)output;
}

References length().

Macros

Functions