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  int little_endian; ///< 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  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  */
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  */
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  */
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 }
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:168
findCode
static int findCode(LZWEncodeState *s, uint8_t c, int hash_prefix)
Find LZW code for block.
Definition: lzwenc.c:130
ff_lzw_encode_flush
int ff_lzw_encode_flush(LZWEncodeState *s)
Write end code and flush bitstream.
Definition: lzwenc.c:262
init_put_bits
static void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
Initialize the PutBitContext s.
Definition: put_bits.h:66
put_bits
static void put_bits(Jpeg2000EncoderContext *s, int val, int n)
put n times val bit
Definition: j2kenc.c:218
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:229
put_bytes_count
static int put_bytes_count(const PutBitContext *s, int round_up)
Definition: put_bits.h:104
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:152
LZWEncodeState::maxcode
int maxcode
Max value of code.
Definition: lzwenc.c:59
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:205
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:51
LZWEncodeState::pb
PutBitContext pb
Put bit context for output.
Definition: lzwenc.c:57
mathops.h
flush_put_bits_le
static void flush_put_bits_le(PutBitContext *s)
Definition: put_bits.h:168
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
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:191
lzw.h
LZW decoding routines.
FFMAX
#define FFMAX(a, b)
Definition: common.h:103
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
i
int i
Definition: input.c:407
ff_lzw_encode_state_size
const int ff_lzw_encode_state_size
Definition: lzwenc.c:67
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: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
add
static float add(float src0, float src1)
Definition: dnn_backend_native_layer_mathbinary.c:36
flush_put_bits
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:147
LZWEncodeState::end_code
int end_code
Value of end code.
Definition: lzwenc.c:52
put_bits_le
static void put_bits_le(PutBitContext *s, int n, BitBuf value)
Definition: put_bits.h:262
h
h
Definition: vp9dsp_template.c:2038
put_bits.h
LZWEncodeState::little_endian
int little_endian
GIF is LE while TIFF is BE.
Definition: lzwenc.c:63