Subversion Repositories Kolibri OS

/*

 * LZW encoder

 * Copyright (c) 2007 Bartlomiej Wolowiec

 *

 * This file is part of FFmpeg.

 *

 * FFmpeg is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * FFmpeg 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

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with FFmpeg; if not, write to the Free Software

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

 */

/**

 * @file

 * LZW encoder

 * @author Bartlomiej Wolowiec

 */

#include "avcodec.h"

#include "put_bits.h"

#include "lzw.h"

#define LZW_MAXBITS 12

#define LZW_SIZTABLE (1<

#define LZW_HASH_SIZE 16411

#define LZW_HASH_SHIFT 6

#define LZW_PREFIX_EMPTY -1

#define LZW_PREFIX_FREE -2

/** One code in hash table */

typedef struct Code{

    /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code

    int hash_prefix;

    int code;               ///< LZW code

    uint8_t suffix;         ///< Last character in code block

}Code;

/** LZW encode state */

typedef struct LZWEncodeState {

    int clear_code;          ///< Value of clear code

    int end_code;            ///< Value of end code

    Code tab[LZW_HASH_SIZE]; ///< Hash table

    int tabsize;             ///< Number of values in hash table

    int bits;                ///< Actual bits code

    int bufsize;             ///< Size of output buffer

    PutBitContext pb;        ///< Put bit context for output

    int maxbits;             ///< Max bits code

    int maxcode;             ///< Max value of code

    int output_bytes;        ///< Number of written bytes

    int last_code;           ///< Value of last output code or LZW_PREFIX_EMPTY

    enum FF_LZW_MODES mode;  ///< TIFF or GIF

    void (*put_bits)(PutBitContext *, int, unsigned); ///< GIF is LE while TIFF is BE

}LZWEncodeState;

const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);

/**

 * Hash function adding character

 * @param head LZW code for prefix

 * @param add Character to add

 * @return New hash value

 */

static inline int hash(int head, const int add)

{

    head ^= (add << LZW_HASH_SHIFT);

    if (head >= LZW_HASH_SIZE)

        head -= LZW_HASH_SIZE;

    av_assert2(head >= 0 && head < LZW_HASH_SIZE);

    return head;

}

/**

 * Hash function calculates next hash value

 * @param head Actual hash code

 * @param offset Offset calculated by hashOffset

 * @return New hash value

 */

static inline int hashNext(int head, const int offset)

{

    head -= offset;

    if(head < 0)

        head += LZW_HASH_SIZE;

    return head;

}

/**

 * Hash function calculates hash offset

 * @param head Actual hash code

 * @return Hash offset

 */

static inline int hashOffset(const int head)

{

    return head ? LZW_HASH_SIZE - head : 1;

}

/**

 * Write one code to stream

 * @param s LZW state

 * @param c code to write

 */

static inline void writeCode(LZWEncodeState * s, int c)

{

    av_assert2(0 <= c && c < 1 << s->bits);

    s->put_bits(&s->pb, s->bits, c);

}

/**

 * Find LZW code for block

 * @param s LZW state

 * @param c Last character in block

 * @param hash_prefix LZW code for prefix

 * @return LZW code for block or -1 if not found in table

 */

static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)

{

    int h = hash(FFMAX(hash_prefix, 0), c);

    int hash_offset = hashOffset(h);

    while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {

        if ((s->tab[h].suffix == c)

            && (s->tab[h].hash_prefix == hash_prefix))

            return h;

        h = hashNext(h, hash_offset);

    }

    return h;

}

/**

 * Add block to LZW code table

 * @param s LZW state

 * @param c Last character in block

 * @param hash_prefix LZW code for prefix

 * @param hash_code LZW code for bytes block

 */

static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)

{

    s->tab[hash_code].code = s->tabsize;

    s->tab[hash_code].suffix = c;

    s->tab[hash_code].hash_prefix = hash_prefix;

    s->tabsize++;

    if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))

        s->bits++;

}

/**

 * Clear LZW code table

 * @param s LZW state

 */

static void clearTable(LZWEncodeState * s)

{

    int i, h;

    writeCode(s, s->clear_code);

    s->bits = 9;

    for (i = 0; i < LZW_HASH_SIZE; i++) {

        s->tab[i].hash_prefix = LZW_PREFIX_FREE;

    }

    for (i = 0; i < 256; i++) {

        h = hash(0, i);

        s->tab[h].code = i;

        s->tab[h].suffix = i;

        s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;

    }

    s->tabsize = 258;

}

/**

 * Calculate number of bytes written

 * @param s LZW encode state

 * @return Number of bytes written

 */

static int writtenBytes(LZWEncodeState *s){

    int ret = put_bits_count(&s->pb) >> 3;

    ret -= s->output_bytes;

    s->output_bytes += ret;

    return ret;

}

/**

 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.

 * @param s LZW state

 * @param outbuf Output buffer

 * @param outsize Size of output buffer

 * @param maxbits Maximum length of code

 */

void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,

                        int maxbits, enum FF_LZW_MODES mode,

                        void (*lzw_put_bits)(PutBitContext *, int, unsigned))

{

    s->clear_code = 256;

    s->end_code = 257;

    s->maxbits = maxbits;

    init_put_bits(&s->pb, outbuf, outsize);

    s->bufsize = outsize;

    av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);

    s->maxcode = 1 << s->maxbits;

    s->output_bytes = 0;

    s->last_code = LZW_PREFIX_EMPTY;

    s->bits = 9;

    s->mode = mode;

    s->put_bits = lzw_put_bits;

}

/**

 * LZW main compress function

 * @param s LZW state

 * @param inbuf Input buffer

 * @param insize Size of input buffer

 * @return Number of bytes written or -1 on error

 */

int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)

{

    int i;

    if(insize * 3 > (s->bufsize - s->output_bytes) * 2){

        return -1;

    }

    if (s->last_code == LZW_PREFIX_EMPTY)

        clearTable(s);

    for (i = 0; i < insize; i++) {

        uint8_t c = *inbuf++;

        int code = findCode(s, c, s->last_code);

        if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {

            writeCode(s, s->last_code);

            addCode(s, c, s->last_code, code);

            code= hash(0, c);

        }

        s->last_code = s->tab[code].code;

        if (s->tabsize >= s->maxcode - 1) {

            clearTable(s);

        }

    }

    return writtenBytes(s);

}

/**

 * Write end code and flush bitstream

 * @param s LZW state

 * @return Number of bytes written or -1 on error

 */

int ff_lzw_encode_flush(LZWEncodeState *s,

                        void (*lzw_flush_put_bits)(PutBitContext *))

{

    if (s->last_code != -1)

        writeCode(s, s->last_code);

    writeCode(s, s->end_code);

    if (s->mode == FF_LZW_GIF)

        s->put_bits(&s->pb, 1, 0);

    lzw_flush_put_bits(&s->pb);

    s->last_code = -1;

    return writtenBytes(s);

}