src/base/compression/lzss_compression.cc

/*
 * Copyright (c) 2003-2005 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Erik Hallnor
 */

/** @file
 * LZSSCompression definitions.
 */

#include <cassert>
#include <cstring>
#include "base/compression/lzss_compression.hh"

#include "base/misc.hh" //for fatal

void
LZSSCompression::findSubString(uint8_t *src, int back, int size, uint16_t &L,
                               uint16_t &P)
{
    int front = 0;
    int max_length = size - back;
    L = 0;
    P = back - 1;
    while (front < back) {
        while (src[front] != src[back] && front < back) ++front;
        if (front >= back) {
            return;
        }
        int i = 1;
        while (src[front+i] == src[back+i] && i < max_length) ++i;
        if (i >= L) {
            L = i;
            P = front;
        }
        if (src[front+i] != src[back+i-1]) {
            // can't find a longer substring until past this point.
            front += i;
        } else {
            ++front;
        }
    }
}

int
LZSSCompression::emitByte(uint8_t *dest, uint8_t byte)
{
    if ((byte >> 5 & 0x7) == 0 || (byte >> 5 & 0x7) == 7) {
        // If the top 3 bits are the same, emit 00<6bits>
        dest[0] = byte & 0x3f;
        return 1;
    } else {
        // emit 01XXXXXX <8 bits>
        dest[0] = 0x40;
        dest[1] = byte;
        return 2;
    }
}

void
LZSSCompression::emitString(uint8_t *dest, uint16_t P, uint16_t L)
{
    // Emit 1<7P> <5P><3L> <8L>
    dest[0] = 1<<7 | (P >> 5 & 0x7f);
    dest[1] = ((P & 0x1f) << 3) | (L>>8 & 0x3);
    dest[2] = L & 0xFF;
}

int
LZSSCompression::compress(uint8_t *dest, uint8_t *src, int size)
{
    if (size > 4096) {
        fatal("Compression can only handle block sizes of 4096 bytes or less");
    }

    // Encode the first byte.
    int dest_index = emitByte(dest, src[0]);
    int i = 1;
    // A 11 bit field
    uint16_t L;
    // A 12 bit field
    uint16_t P = 0;

    while (i < size && dest_index < size) {
        L = 0;

        if (dest_index+3 >= size) {
            dest_index = size;
            continue;
        }

        if (i == size - 1) {
            // Output the character
            dest_index += emitByte(&dest[dest_index], src[i]);
            ++i;
            continue;
        }
        findSubString(src, i, size, L, P);
        if (L > 1) {
            // Output the string reference
            emitString(&dest[dest_index], P, L);
            dest_index += 3;
            i = i+L;
        } else {
            // Output the character
            dest_index += emitByte(&dest[dest_index], src[i]);
            ++i;
        }
    }

    if (dest_index >= size) {
        // Have expansion instead of compression, just copy.
        std::memcpy(dest,src,size);
        return size;
    }
    return dest_index;
}

int
LZSSCompression::uncompress(uint8_t *dest, uint8_t *src, int size)
{
    int index = 0;
    int i = 0;
    while (i < size) {
        if (src[i] & 1<<7 ) {
            // We have a string
            // Extract P
            int start = (src[i] & 0x3f)<<5 | ((src[i+1] >> 3) & 0x1f);
            // Extract L
            int len = (src[i+1] & 0x07)<<8 | src[i+2];
            i += 3;
            for (int j = start; j < start+len; ++j) {
                dest[index++] = dest[j];
            }
        } else {
            // We have a character
            if (src[i] & 1<<6) {
                // Value is in the next byte
                dest[index++] = src[i+1];
                i += 2;
            } else {
                // just extend the lower 6 bits
                dest[index++] = (src[i] & 0x3f) | ((src[i] & 1<<5) ? 0xC0 : 0);
                ++i;
            }
        }
    }
    return index;
}