FFmpeg
lzwenc.c
Go to the documentation of this file.
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
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
65 
66 
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  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  */
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  */
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  av_assert0(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  */
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  if (s->mode == FF_LZW_GIF)
267  s->put_bits(&s->pb, 1, 0);
268 
269  lzw_flush_put_bits(&s->pb);
270  s->last_code = -1;
271 
272  return writtenBytes(s);
273 }
LZWEncodeState::clear_code
int clear_code
Value of clear code.
Definition: lzwenc.c:51
clearTable
static void clearTable(LZWEncodeState *s)
Clear LZW code table.
Definition: lzwenc.c:165
findCode
static int findCode(LZWEncodeState *s, uint8_t c, int hash_prefix)
Find LZW code for block.
Definition: lzwenc.c:127
init_put_bits
static void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
Initialize the PutBitContext s.
Definition: put_bits.h:48
LZWEncodeState
LZW encode state.
Definition: lzwenc.c:50
ff_lzw_encode
int ff_lzw_encode(LZWEncodeState *s, const uint8_t *inbuf, int insize)
LZW main compress function.
Definition: lzwenc.c:227
ff_lzw_encode_init
void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize, int maxbits, enum FF_LZW_MODES mode, void(*lzw_put_bits)(PutBitContext *, int, unsigned))
Initialize LZW encoder.
Definition: lzwenc.c:202
FF_LZW_MODES
FF_LZW_MODES
Definition: lzw.h:37
LZWEncodeState::maxbits
int maxbits
Max bits code.
Definition: lzwenc.c:58
Code::hash_prefix
int hash_prefix
Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code.
Definition: lzwenc.c:44
hashNext
static int hashNext(int head, const int offset)
Hash function calculates next hash value.
Definition: lzwenc.c:90
LZWEncodeState::tabsize
int tabsize
Number of values in hash table.
Definition: lzwenc.c:54
addCode
static void addCode(LZWEncodeState *s, uint8_t c, int hash_prefix, int hash_code)
Add block to LZW code table.
Definition: lzwenc.c:149
LZWEncodeState::maxcode
int maxcode
Max value of code.
Definition: lzwenc.c:59
LZWEncodeState::last_code
int last_code
Value of last output code or LZW_PREFIX_EMPTY.
Definition: lzwenc.c:61
hashOffset
static int hashOffset(const int head)
Hash function calculates hash offset.
Definition: lzwenc.c:103
LZW_PREFIX_EMPTY
#define LZW_PREFIX_EMPTY
Definition: lzwenc.c:38
s
#define s(width, name)
Definition: cbs_vp9.c:257
LZWEncodeState::bufsize
int bufsize
Size of output buffer.
Definition: lzwenc.c:56
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
LZW_HASH_SIZE
#define LZW_HASH_SIZE
Definition: lzwenc.c:35
PutBitContext
Definition: put_bits.h:35
LZWEncodeState::pb
PutBitContext pb
Put bit context for output.
Definition: lzwenc.c:57
mathops.h
LZWEncodeState::put_bits
void(* put_bits)(PutBitContext *, int, unsigned)
GIF is LE while TIFF is BE.
Definition: lzwenc.c:63
FF_LZW_GIF
@ FF_LZW_GIF
Definition: lzw.h:38
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
LZW_PREFIX_FREE
#define LZW_PREFIX_FREE
Definition: lzwenc.c:39
ff_lzw_encode_flush
int ff_lzw_encode_flush(LZWEncodeState *s, void(*lzw_flush_put_bits)(PutBitContext *))
Write end code and flush bitstream.
Definition: lzwenc.c:260
LZWEncodeState::output_bytes
int output_bytes
Number of written bytes.
Definition: lzwenc.c:60
writtenBytes
static int writtenBytes(LZWEncodeState *s)
Calculate number of bytes written.
Definition: lzwenc.c:188
lzw.h
LZW decoding routines.
FFMAX
#define FFMAX(a, b)
Definition: common.h:94
LZWEncodeState::tab
Code tab[LZW_HASH_SIZE]
Hash table.
Definition: lzwenc.c:53
offset
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf offset
Definition: writing_filters.txt:86
Code::suffix
uint8_t suffix
Last character in code block.
Definition: lzwenc.c:46
av_assert2
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:64
ff_lzw_encode_state_size
const int ff_lzw_encode_state_size
Definition: lzwenc.c:67
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
code
and forward the test the status of outputs and forward it to the corresponding return FFERROR_NOT_READY If the filters stores internally one or a few frame for some it can consider them to be part of the FIFO and delay acknowledging a status change accordingly Example code
Definition: filter_design.txt:178
put_bits_count
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:85
LZWEncodeState::bits
int bits
Actual bits code.
Definition: lzwenc.c:55
Code
One code in hash table.
Definition: lzwenc.c:42
uint8_t
uint8_t
Definition: audio_convert.c:194
hash
static int hash(int head, const int add)
Hash function adding character.
Definition: lzwenc.c:75
avcodec.h
LZW_HASH_SHIFT
#define LZW_HASH_SHIFT
Definition: lzwenc.c:36
ret
ret
Definition: filter_design.txt:187
Code::code
int code
LZW code.
Definition: lzwenc.c:45
LZW_MAXBITS
#define LZW_MAXBITS
Definition: lzwenc.c:33
mode
mode
Definition: ebur128.h:83
writeCode
static void writeCode(LZWEncodeState *s, int c)
Write one code to stream.
Definition: lzwenc.c:113
LZWEncodeState::mode
enum FF_LZW_MODES mode
TIFF or GIF.
Definition: lzwenc.c:62
LZWEncodeState::end_code
int end_code
Value of end code.
Definition: lzwenc.c:52
h
h
Definition: vp9dsp_template.c:2038
int
int
Definition: ffmpeg_filter.c:191
put_bits.h