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