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++) {
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;
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_bits_count(&s->pb) >> 3;
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;
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 }
int hash_prefix
Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code.
Definition: lzwenc.c:44
static void put_bits(Jpeg2000EncoderContext *s, int val, int n)
put n times val bit
Definition: j2kenc.c:218
int bufsize
Size of output buffer.
Definition: lzwenc.c:56
static int hash(int head, const int add)
Hash function adding character.
Definition: lzwenc.c:75
static void addCode(LZWEncodeState *s, uint8_t c, int hash_prefix, int hash_code)
Add block to LZW code table.
Definition: lzwenc.c:152
#define LZW_HASH_SHIFT
Definition: lzwenc.c:36
int end_code
Value of end code.
Definition: lzwenc.c:52
int maxbits
Max bits code.
Definition: lzwenc.c:58
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
static void clearTable(LZWEncodeState *s)
Clear LZW code table.
Definition: lzwenc.c:168
uint8_t
#define av_assert2(cond)
assert() equivalent, that does lie in speed critical code.
Definition: avassert.h:64
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
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
int little_endian
GIF is LE while TIFF is BE.
Definition: lzwenc.c:63
PutBitContext pb
Put bit context for output.
Definition: lzwenc.c:57
int tabsize
Number of values in hash table.
Definition: lzwenc.c:54
LZW encode state.
Definition: lzwenc.c:50
int clear_code
Value of clear code.
Definition: lzwenc.c:51
static int writtenBytes(LZWEncodeState *s)
Calculate number of bytes written.
Definition: lzwenc.c:191
#define LZW_MAXBITS
Definition: lzwenc.c:33
#define FFMAX(a, b)
Definition: common.h:94
int last_code
Value of last output code or LZW_PREFIX_EMPTY.
Definition: lzwenc.c:61
static int put_bits_count(PutBitContext *s)
Definition: put_bits.h:83
static void flush_put_bits_le(PutBitContext *s)
Definition: put_bits.h:138
int ff_lzw_encode(LZWEncodeState *s, const uint8_t *inbuf, int insize)
LZW main compress function.
Definition: lzwenc.c:229
static void put_bits_le(PutBitContext *s, int n, BitBuf value)
Definition: put_bits.h:232
static void writeCode(LZWEncodeState *s, int c)
Write one code to stream.
Definition: lzwenc.c:113
static int findCode(LZWEncodeState *s, uint8_t c, int hash_prefix)
Find LZW code for block.
Definition: lzwenc.c:130
Definition: lzw.h:38
int ff_lzw_encode_flush(LZWEncodeState *s)
Write end code and flush bitstream.
Definition: lzwenc.c:262
#define s(width, name)
Definition: cbs_vp9.c:257
uint8_t suffix
Last character in code block.
Definition: lzwenc.c:46
int maxcode
Max value of code.
Definition: lzwenc.c:59
Libavcodec external API header.
enum FF_LZW_MODES mode
TIFF or GIF.
Definition: lzwenc.c:62
int code
LZW code.
Definition: lzwenc.c:45
int bits
Actual bits code.
Definition: lzwenc.c:55
LZW decoding routines.
#define LZW_PREFIX_FREE
Definition: lzwenc.c:39
static void flush_put_bits(PutBitContext *s)
Pad the end of the output stream with zeros.
Definition: put_bits.h:117
static void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
Initialize the PutBitContext s.
Definition: put_bits.h:64
int output_bytes
Number of written bytes.
Definition: lzwenc.c:60
One code in hash table.
Definition: lzwenc.c:42
#define LZW_PREFIX_EMPTY
Definition: lzwenc.c:38
static const struct twinvq_data tab
static float add(float src0, float src1)
FF_LZW_MODES
Definition: lzw.h:37
static int hashNext(int head, const int offset)
Hash function calculates next hash value.
Definition: lzwenc.c:90
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
#define LZW_HASH_SIZE
Definition: lzwenc.c:35
const int ff_lzw_encode_state_size
Definition: lzwenc.c:67
mode
Use these values in ebur128_init (or&#39;ed).
Definition: ebur128.h:83
static int hashOffset(const int head)
Hash function calculates hash offset.
Definition: lzwenc.c:103
Code tab[LZW_HASH_SIZE]
Hash table.
Definition: lzwenc.c:53
int i
Definition: input.c:407
bitstream writer API