Libav
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 Libav.
6  *
7  * Libav 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  * Libav 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 Libav; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 
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 
42 typedef struct Code{
45  int code;
47 }Code;
48 
50 typedef struct LZWEncodeState {
51  int clear_code;
52  int end_code;
54  int tabsize;
55  int bits;
56  int bufsize;
58  int maxbits;
59  int maxcode;
61  int last_code;
63  void (*put_bits)(PutBitContext *, int, unsigned);
65 
66 
68 
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  assert(head >= 0 && head < LZW_HASH_SIZE);
81  return head;
82 }
83 
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 
103 static inline int hashOffset(const int head)
104 {
105  return head ? LZW_HASH_SIZE - head : 1;
106 }
107 
113 static inline void writeCode(LZWEncodeState * s, int c)
114 {
115  assert(0 <= c && c < 1 << s->bits);
116  s->put_bits(&s->pb, s->bits, c);
117 }
118 
119 
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 
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 
165 static void clearTable(LZWEncodeState * s)
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 
189  int ret = put_bits_count(&s->pb) >> 3;
190  ret -= s->output_bytes;
191  s->output_bytes += ret;
192  return ret;
193 }
194 
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  assert(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 
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 
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  lzw_flush_put_bits(&s->pb);
267  s->last_code = -1;
268 
269  return writtenBytes(s);
270 }
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 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
static void clearTable(LZWEncodeState *s)
Clear LZW code table.
Definition: lzwenc.c:165
uint8_t
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 FFMAX(a, b)
Definition: common.h:55
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:67
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
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.
static void(WINAPI *cond_broadcast)(pthread_cond_t *cond)
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
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
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
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