libavcodec/lzwenc.c

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