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++) {
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;
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;
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 }
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:208
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:149
#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:165
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 ff_lzw_encode_flush(LZWEncodeState *s, void(*lzw_flush_put_bits)(PutBitContext *))
Write end code and flush bitstream.
Definition: lzwenc.c:260
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:188
#define LZW_MAXBITS
Definition: lzwenc.c:33
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
#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:85
int ff_lzw_encode(LZWEncodeState *s, const uint8_t *inbuf, int insize)
LZW main compress function.
Definition: lzwenc.c:227
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:127
Definition: lzw.h:38
typedef void(APIENTRY *FF_PFNGLACTIVETEXTUREPROC)(GLenum texture)
#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
void(* put_bits)(PutBitContext *, int, unsigned)
GIF is LE while TIFF is BE.
Definition: lzwenc.c:63
int
static void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
Initialize the PutBitContext s.
Definition: put_bits.h:48
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
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
#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
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
Code tab[LZW_HASH_SIZE]
Hash table.
Definition: lzwenc.c:53
bitstream writer API