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