libavcodec/lzwenc.c

   1 /*
   2  * LZW encoder
   3  * Copyright (c) 2007 Bartlomiej Wolowiec
   4  *
   5  * This file is part of FFmpeg.
   6  *
   7  * FFmpeg is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * FFmpeg is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with FFmpeg; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 /**
  23  * @file
  24  * LZW encoder
  25  * @author Bartlomiej Wolowiec
  26  */
  27
  28 #include "avcodec.h"
  29 #include "put_bits.h"
  30 #include "lzw.h"
  31
  32 #define LZW_MAXBITS 12
  33 #define LZW_SIZTABLE (1<<LZW_MAXBITS)
  34 #define LZW_HASH_SIZE 16411
  35 #define LZW_HASH_SHIFT 6
  36
  37 #define LZW_PREFIX_EMPTY -1
  38 #define LZW_PREFIX_FREE -2
  39
  40 /** One code in hash table */
  41 typedef struct Code{
  42     /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code
  43     int hash_prefix;
  44     int code;               ///< LZW code
  45     uint8_t suffix;         ///< Last character in code block
  46 }Code;
  47
  48 /** LZW encode state */
  49 typedef struct LZWEncodeState {
  50     int clear_code;          ///< Value of clear code
  51     int end_code;            ///< Value of end code
  52     Code tab[LZW_HASH_SIZE]; ///< Hash table
  53     int tabsize;             ///< Number of values in hash table
  54     int bits;                ///< Actual bits code
  55     int bufsize;             ///< Size of output buffer
  56     PutBitContext pb;        ///< Put bit context for output
  57     int maxbits;             ///< Max bits code
  58     int maxcode;             ///< Max value of code
  59     int output_bytes;        ///< Number of written bytes
  60     int last_code;           ///< Value of last output code or LZW_PREFIX_EMPTY
  61     enum FF_LZW_MODES mode;  ///< TIFF or GIF
  62     void (*put_bits)(PutBitContext *, int, unsigned); ///< GIF is LE while TIFF is BE
  63 }LZWEncodeState;
  64
  65
  66 const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);
  67
  68 /**
  69  * Hash function adding character
  70  * @param head LZW code for prefix
  71  * @param add Character to add
  72  * @return New hash value
  73  */
  74 static inline int hash(int head, const int add)
  75 {
  76     head ^= (add << LZW_HASH_SHIFT);
  77     if (head >= LZW_HASH_SIZE)
  78         head -= LZW_HASH_SIZE;
  79     assert(head >= 0 && head < LZW_HASH_SIZE);
  80     return head;
  81 }
  82
  83 /**
  84  * Hash function calculates next hash value
  85  * @param head Actual hash code
  86  * @param offset Offset calculated by hashOffset
  87  * @return New hash value
  88  */
  89 static inline int hashNext(int head, const int offset)
  90 {
  91     head -= offset;
  92     if(head < 0)
  93         head += LZW_HASH_SIZE;
  94     return head;
  95 }
  96
  97 /**
  98  * Hash function calculates hash offset
  99  * @param head Actual hash code
 100  * @return Hash offset
 101  */
 102 static inline int hashOffset(const int head)
 103 {
 104     return head ? LZW_HASH_SIZE - head : 1;
 105 }
 106
 107 /**
 108  * Write one code to stream
 109  * @param s LZW state
 110  * @param c code to write
 111  */
 112 static inline void writeCode(LZWEncodeState * s, int c)
 113 {
 114     assert(0 <= c && c < 1 << s->bits);
 115     s->put_bits(&s->pb, s->bits, c);
 116 }
 117
 118
 119 /**
 120  * Find LZW code for block
 121  * @param s LZW state
 122  * @param c Last character in block
 123  * @param hash_prefix LZW code for prefix
 124  * @return LZW code for block or -1 if not found in table
 125  */
 126 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
 127 {
 128     int h = hash(FFMAX(hash_prefix, 0), c);
 129     int hash_offset = hashOffset(h);
 130
 131     while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
 132         if ((s->tab[h].suffix == c)
 133             && (s->tab[h].hash_prefix == hash_prefix))
 134             return h;
 135         h = hashNext(h, hash_offset);
 136     }
 137
 138     return h;
 139 }
 140
 141 /**
 142  * Add block to LZW code table
 143  * @param s LZW state
 144  * @param c Last character in block
 145  * @param hash_prefix LZW code for prefix
 146  * @param hash_code LZW code for bytes block
 147  */
 148 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
 149 {
 150     s->tab[hash_code].code = s->tabsize;
 151     s->tab[hash_code].suffix = c;
 152     s->tab[hash_code].hash_prefix = hash_prefix;
 153
 154     s->tabsize++;
 155
 156     if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
 157         s->bits++;
 158 }
 159
 160 /**
 161  * Clear LZW code table
 162  * @param s LZW state
 163  */
 164 static void clearTable(LZWEncodeState * s)
 165 {
 166     int i, h;
 167
 168     writeCode(s, s->clear_code);
 169     s->bits = 9;
 170     for (i = 0; i < LZW_HASH_SIZE; i++) {
 171         s->tab[i].hash_prefix = LZW_PREFIX_FREE;
 172     }
 173     for (i = 0; i < 256; i++) {
 174         h = hash(0, i);
 175         s->tab[h].code = i;
 176         s->tab[h].suffix = i;
 177         s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
 178     }
 179     s->tabsize = 258;
 180 }
 181
 182 /**
 183  * Calculate number of bytes written
 184  * @param s LZW encode state
 185  * @return Number of bytes written
 186  */
 187 static int writtenBytes(LZWEncodeState *s){
 188     int ret = put_bits_count(&s->pb) >> 3;
 189     ret -= s->output_bytes;
 190     s->output_bytes += ret;
 191     return ret;
 192 }
 193
 194 /**
 195  * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
 196  * @param s LZW state
 197  * @param outbuf Output buffer
 198  * @param outsize Size of output buffer
 199  * @param maxbits Maximum length of code
 200  */
 201 void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,
 202                         int maxbits, enum FF_LZW_MODES mode,
 203                         void (*lzw_put_bits)(PutBitContext *, int, unsigned))
 204 {
 205     s->clear_code = 256;
 206     s->end_code = 257;
 207     s->maxbits = maxbits;
 208     init_put_bits(&s->pb, outbuf, outsize);
 209     s->bufsize = outsize;
 210     assert(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
 211     s->maxcode = 1 << s->maxbits;
 212     s->output_bytes = 0;
 213     s->last_code = LZW_PREFIX_EMPTY;
 214     s->bits = 9;
 215     s->mode = mode;
 216     s->put_bits = lzw_put_bits;
 217 }
 218
 219 /**
 220  * LZW main compress function
 221  * @param s LZW state
 222  * @param inbuf Input buffer
 223  * @param insize Size of input buffer
 224  * @return Number of bytes written or -1 on error
 225  */
 226 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
 227 {
 228     int i;
 229
 230     if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
 231         return -1;
 232     }
 233
 234     if (s->last_code == LZW_PREFIX_EMPTY)
 235         clearTable(s);
 236
 237     for (i = 0; i < insize; i++) {
 238         uint8_t c = *inbuf++;
 239         int code = findCode(s, c, s->last_code);
 240         if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
 241             writeCode(s, s->last_code);
 242             addCode(s, c, s->last_code, code);
 243             code= hash(0, c);
 244         }
 245         s->last_code = s->tab[code].code;
 246         if (s->tabsize >= s->maxcode - 1) {
 247             clearTable(s);
 248         }
 249     }
 250
 251     return writtenBytes(s);
 252 }
 253
 254 /**
 255  * Write end code and flush bitstream
 256  * @param s LZW state
 257  * @return Number of bytes written or -1 on error
 258  */
 259 int ff_lzw_encode_flush(LZWEncodeState *s,
 260                         void (*lzw_flush_put_bits)(PutBitContext *))
 261 {
 262     if (s->last_code != -1)
 263         writeCode(s, s->last_code);
 264     writeCode(s, s->end_code);
 265     lzw_flush_put_bits(&s->pb);
 266     s->last_code = -1;
 267
 268     return writtenBytes(s);
 269 }