yading@10: /*
yading@10:  * LZW encoder
yading@10:  * Copyright (c) 2007 Bartlomiej Wolowiec
yading@10:  *
yading@10:  * This file is part of FFmpeg.
yading@10:  *
yading@10:  * FFmpeg is free software; you can redistribute it and/or
yading@10:  * modify it under the terms of the GNU Lesser General Public
yading@10:  * License as published by the Free Software Foundation; either
yading@10:  * version 2.1 of the License, or (at your option) any later version.
yading@10:  *
yading@10:  * FFmpeg is distributed in the hope that it will be useful,
yading@10:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
yading@10:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
yading@10:  * Lesser General Public License for more details.
yading@10:  *
yading@10:  * You should have received a copy of the GNU Lesser General Public
yading@10:  * License along with FFmpeg; if not, write to the Free Software
yading@10:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
yading@10:  */
yading@10: 
yading@10: /**
yading@10:  * @file
yading@10:  * LZW encoder
yading@10:  * @author Bartlomiej Wolowiec
yading@10:  */
yading@10: 
yading@10: #include "avcodec.h"
yading@10: #include "put_bits.h"
yading@10: #include "lzw.h"
yading@10: 
yading@10: #define LZW_MAXBITS 12
yading@10: #define LZW_SIZTABLE (1<<LZW_MAXBITS)
yading@10: #define LZW_HASH_SIZE 16411
yading@10: #define LZW_HASH_SHIFT 6
yading@10: 
yading@10: #define LZW_PREFIX_EMPTY -1
yading@10: #define LZW_PREFIX_FREE -2
yading@10: 
yading@10: /** One code in hash table */
yading@10: typedef struct Code{
yading@10:     /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code
yading@10:     int hash_prefix;
yading@10:     int code;               ///< LZW code
yading@10:     uint8_t suffix;         ///< Last character in code block
yading@10: }Code;
yading@10: 
yading@10: /** LZW encode state */
yading@10: typedef struct LZWEncodeState {
yading@10:     int clear_code;          ///< Value of clear code
yading@10:     int end_code;            ///< Value of end code
yading@10:     Code tab[LZW_HASH_SIZE]; ///< Hash table
yading@10:     int tabsize;             ///< Number of values in hash table
yading@10:     int bits;                ///< Actual bits code
yading@10:     int bufsize;             ///< Size of output buffer
yading@10:     PutBitContext pb;        ///< Put bit context for output
yading@10:     int maxbits;             ///< Max bits code
yading@10:     int maxcode;             ///< Max value of code
yading@10:     int output_bytes;        ///< Number of written bytes
yading@10:     int last_code;           ///< Value of last output code or LZW_PREFIX_EMPTY
yading@10:     enum FF_LZW_MODES mode;  ///< TIFF or GIF
yading@10:     void (*put_bits)(PutBitContext *, int, unsigned); ///< GIF is LE while TIFF is BE
yading@10: }LZWEncodeState;
yading@10: 
yading@10: 
yading@10: const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);
yading@10: 
yading@10: /**
yading@10:  * Hash function adding character
yading@10:  * @param head LZW code for prefix
yading@10:  * @param add Character to add
yading@10:  * @return New hash value
yading@10:  */
yading@10: static inline int hash(int head, const int add)
yading@10: {
yading@10:     head ^= (add << LZW_HASH_SHIFT);
yading@10:     if (head >= LZW_HASH_SIZE)
yading@10:         head -= LZW_HASH_SIZE;
yading@10:     av_assert2(head >= 0 && head < LZW_HASH_SIZE);
yading@10:     return head;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Hash function calculates next hash value
yading@10:  * @param head Actual hash code
yading@10:  * @param offset Offset calculated by hashOffset
yading@10:  * @return New hash value
yading@10:  */
yading@10: static inline int hashNext(int head, const int offset)
yading@10: {
yading@10:     head -= offset;
yading@10:     if(head < 0)
yading@10:         head += LZW_HASH_SIZE;
yading@10:     return head;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Hash function calculates hash offset
yading@10:  * @param head Actual hash code
yading@10:  * @return Hash offset
yading@10:  */
yading@10: static inline int hashOffset(const int head)
yading@10: {
yading@10:     return head ? LZW_HASH_SIZE - head : 1;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Write one code to stream
yading@10:  * @param s LZW state
yading@10:  * @param c code to write
yading@10:  */
yading@10: static inline void writeCode(LZWEncodeState * s, int c)
yading@10: {
yading@10:     assert(0 <= c && c < 1 << s->bits);
yading@10:     s->put_bits(&s->pb, s->bits, c);
yading@10: }
yading@10: 
yading@10: 
yading@10: /**
yading@10:  * Find LZW code for block
yading@10:  * @param s LZW state
yading@10:  * @param c Last character in block
yading@10:  * @param hash_prefix LZW code for prefix
yading@10:  * @return LZW code for block or -1 if not found in table
yading@10:  */
yading@10: static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
yading@10: {
yading@10:     int h = hash(FFMAX(hash_prefix, 0), c);
yading@10:     int hash_offset = hashOffset(h);
yading@10: 
yading@10:     while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
yading@10:         if ((s->tab[h].suffix == c)
yading@10:             && (s->tab[h].hash_prefix == hash_prefix))
yading@10:             return h;
yading@10:         h = hashNext(h, hash_offset);
yading@10:     }
yading@10: 
yading@10:     return h;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Add block to LZW code table
yading@10:  * @param s LZW state
yading@10:  * @param c Last character in block
yading@10:  * @param hash_prefix LZW code for prefix
yading@10:  * @param hash_code LZW code for bytes block
yading@10:  */
yading@10: static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
yading@10: {
yading@10:     s->tab[hash_code].code = s->tabsize;
yading@10:     s->tab[hash_code].suffix = c;
yading@10:     s->tab[hash_code].hash_prefix = hash_prefix;
yading@10: 
yading@10:     s->tabsize++;
yading@10: 
yading@10:     if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
yading@10:         s->bits++;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Clear LZW code table
yading@10:  * @param s LZW state
yading@10:  */
yading@10: static void clearTable(LZWEncodeState * s)
yading@10: {
yading@10:     int i, h;
yading@10: 
yading@10:     writeCode(s, s->clear_code);
yading@10:     s->bits = 9;
yading@10:     for (i = 0; i < LZW_HASH_SIZE; i++) {
yading@10:         s->tab[i].hash_prefix = LZW_PREFIX_FREE;
yading@10:     }
yading@10:     for (i = 0; i < 256; i++) {
yading@10:         h = hash(0, i);
yading@10:         s->tab[h].code = i;
yading@10:         s->tab[h].suffix = i;
yading@10:         s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
yading@10:     }
yading@10:     s->tabsize = 258;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Calculate number of bytes written
yading@10:  * @param s LZW encode state
yading@10:  * @return Number of bytes written
yading@10:  */
yading@10: static int writtenBytes(LZWEncodeState *s){
yading@10:     int ret = put_bits_count(&s->pb) >> 3;
yading@10:     ret -= s->output_bytes;
yading@10:     s->output_bytes += ret;
yading@10:     return ret;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
yading@10:  * @param s LZW state
yading@10:  * @param outbuf Output buffer
yading@10:  * @param outsize Size of output buffer
yading@10:  * @param maxbits Maximum length of code
yading@10:  */
yading@10: void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,
yading@10:                         int maxbits, enum FF_LZW_MODES mode,
yading@10:                         void (*lzw_put_bits)(PutBitContext *, int, unsigned))
yading@10: {
yading@10:     s->clear_code = 256;
yading@10:     s->end_code = 257;
yading@10:     s->maxbits = maxbits;
yading@10:     init_put_bits(&s->pb, outbuf, outsize);
yading@10:     s->bufsize = outsize;
yading@10:     assert(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
yading@10:     s->maxcode = 1 << s->maxbits;
yading@10:     s->output_bytes = 0;
yading@10:     s->last_code = LZW_PREFIX_EMPTY;
yading@10:     s->bits = 9;
yading@10:     s->mode = mode;
yading@10:     s->put_bits = lzw_put_bits;
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * LZW main compress function
yading@10:  * @param s LZW state
yading@10:  * @param inbuf Input buffer
yading@10:  * @param insize Size of input buffer
yading@10:  * @return Number of bytes written or -1 on error
yading@10:  */
yading@10: int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
yading@10: {
yading@10:     int i;
yading@10: 
yading@10:     if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
yading@10:         return -1;
yading@10:     }
yading@10: 
yading@10:     if (s->last_code == LZW_PREFIX_EMPTY)
yading@10:         clearTable(s);
yading@10: 
yading@10:     for (i = 0; i < insize; i++) {
yading@10:         uint8_t c = *inbuf++;
yading@10:         int code = findCode(s, c, s->last_code);
yading@10:         if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
yading@10:             writeCode(s, s->last_code);
yading@10:             addCode(s, c, s->last_code, code);
yading@10:             code= hash(0, c);
yading@10:         }
yading@10:         s->last_code = s->tab[code].code;
yading@10:         if (s->tabsize >= s->maxcode - 1) {
yading@10:             clearTable(s);
yading@10:         }
yading@10:     }
yading@10: 
yading@10:     return writtenBytes(s);
yading@10: }
yading@10: 
yading@10: /**
yading@10:  * Write end code and flush bitstream
yading@10:  * @param s LZW state
yading@10:  * @return Number of bytes written or -1 on error
yading@10:  */
yading@10: int ff_lzw_encode_flush(LZWEncodeState *s,
yading@10:                         void (*lzw_flush_put_bits)(PutBitContext *))
yading@10: {
yading@10:     if (s->last_code != -1)
yading@10:         writeCode(s, s->last_code);
yading@10:     writeCode(s, s->end_code);
yading@10:     lzw_flush_put_bits(&s->pb);
yading@10:     s->last_code = -1;
yading@10: 
yading@10:     return writtenBytes(s);
yading@10: }