git.sesse.net Git - ffmpeg/blob - 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 "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     int little_endian;       ///< 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     av_assert2(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     av_assert2(0 <= c && c < 1 << s->bits);
 116     if (s->little_endian)
 117         put_bits_le(&s->pb, s->bits, c);
 118     else
 119         put_bits(&s->pb, s->bits, c);
 120 }
 121
 122
 123 /**
 124  * Find LZW code for block
 125  * @param s LZW state
 126  * @param c Last character in block
 127  * @param hash_prefix LZW code for prefix
 128  * @return LZW code for block or -1 if not found in table
 129  */
 130 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
 131 {
 132     int h = hash(FFMAX(hash_prefix, 0), c);
 133     int hash_offset = hashOffset(h);
 134
 135     while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
 136         if ((s->tab[h].suffix == c)
 137             && (s->tab[h].hash_prefix == hash_prefix))
 138             return h;
 139         h = hashNext(h, hash_offset);
 140     }
 141
 142     return h;
 143 }
 144
 145 /**
 146  * Add block to LZW code table
 147  * @param s LZW state
 148  * @param c Last character in block
 149  * @param hash_prefix LZW code for prefix
 150  * @param hash_code LZW code for bytes block
 151  */
 152 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
 153 {
 154     s->tab[hash_code].code = s->tabsize;
 155     s->tab[hash_code].suffix = c;
 156     s->tab[hash_code].hash_prefix = hash_prefix;
 157
 158     s->tabsize++;
 159
 160     if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
 161         s->bits++;
 162 }
 163
 164 /**
 165  * Clear LZW code table
 166  * @param s LZW state
 167  */
 168 static void clearTable(LZWEncodeState * s)
 169 {
 170     int i, h;
 171
 172     writeCode(s, s->clear_code);
 173     s->bits = 9;
 174     for (i = 0; i < LZW_HASH_SIZE; i++) {
 175         s->tab[i].hash_prefix = LZW_PREFIX_FREE;
 176     }
 177     for (i = 0; i < 256; i++) {
 178         h = hash(0, i);
 179         s->tab[h].code = i;
 180         s->tab[h].suffix = i;
 181         s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
 182     }
 183     s->tabsize = 258;
 184 }
 185
 186 /**
 187  * Calculate number of bytes written
 188  * @param s LZW encode state
 189  * @return Number of bytes written
 190  */
 191 static int writtenBytes(LZWEncodeState *s){
 192     int ret = put_bytes_count(&s->pb, 0);
 193     ret -= s->output_bytes;
 194     s->output_bytes += ret;
 195     return ret;
 196 }
 197
 198 /**
 199  * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
 200  * @param s LZW state
 201  * @param outbuf Output buffer
 202  * @param outsize Size of output buffer
 203  * @param maxbits Maximum length of code
 204  */
 205 void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,
 206                         int maxbits, enum FF_LZW_MODES mode, int little_endian)
 207 {
 208     s->clear_code = 256;
 209     s->end_code = 257;
 210     s->maxbits = maxbits;
 211     init_put_bits(&s->pb, outbuf, outsize);
 212     s->bufsize = outsize;
 213     av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
 214     s->maxcode = 1 << s->maxbits;
 215     s->output_bytes = 0;
 216     s->last_code = LZW_PREFIX_EMPTY;
 217     s->bits = 9;
 218     s->mode = mode;
 219     s->little_endian = little_endian;
 220 }
 221
 222 /**
 223  * LZW main compress function
 224  * @param s LZW state
 225  * @param inbuf Input buffer
 226  * @param insize Size of input buffer
 227  * @return Number of bytes written or -1 on error
 228  */
 229 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
 230 {
 231     int i;
 232
 233     if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
 234         return -1;
 235     }
 236
 237     if (s->last_code == LZW_PREFIX_EMPTY)
 238         clearTable(s);
 239
 240     for (i = 0; i < insize; i++) {
 241         uint8_t c = *inbuf++;
 242         int code = findCode(s, c, s->last_code);
 243         if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
 244             writeCode(s, s->last_code);
 245             addCode(s, c, s->last_code, code);
 246             code= hash(0, c);
 247         }
 248         s->last_code = s->tab[code].code;
 249         if (s->tabsize >= s->maxcode - 1) {
 250             clearTable(s);
 251         }
 252     }
 253
 254     return writtenBytes(s);
 255 }
 256
 257 /**
 258  * Write end code and flush bitstream
 259  * @param s LZW state
 260  * @return Number of bytes written or -1 on error
 261  */
 262 int ff_lzw_encode_flush(LZWEncodeState *s)
 263 {
 264     if (s->last_code != -1)
 265         writeCode(s, s->last_code);
 266     writeCode(s, s->end_code);
 267     if (s->little_endian) {
 268         if (s->mode == FF_LZW_GIF)
 269             put_bits_le(&s->pb, 1, 0);
 270
 271         flush_put_bits_le(&s->pb);
 272     } else {
 273         if (s->mode == FF_LZW_GIF)
 274             put_bits(&s->pb, 1, 0);
 275
 276         flush_put_bits(&s->pb);
 277     }
 278     s->last_code = -1;
 279
 280     return writtenBytes(s);
 281 }