/* * 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 */ /** * LZW encoder * @file lzwenc.c * @author Bartlomiej Wolowiec */ #include "avcodec.h" #include "bitstream.h" #include "lzw.h" #define LZW_MAXBITS 12 #define LZW_SIZTABLE (1<<LZW_MAXBITS) #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 }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; assert(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) { assert(0 <= c && c < 1 << s->bits); 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->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) { s->clear_code = 256; s->end_code = 257; s->maxbits = maxbits; init_put_bits(&s->pb, outbuf, outsize); s->bufsize = outsize; assert(9 <= s->maxbits && s->maxbits <= s->maxbits); s->maxcode = 1 << s->maxbits; s->output_bytes = 0; s->last_code = LZW_PREFIX_EMPTY; s->bits = 9; } /** * 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) { if (s->last_code != -1) writeCode(s, s->last_code); writeCode(s, s->end_code); flush_put_bits(&s->pb); s->last_code = -1; return writtenBytes(s); }