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 "put_bits.h"
30 #include "lzw.h"
31 
32 #define LZW_MAXBITS 12
33 #define LZW_SIZTABLE (1<<LZW_MAXBITS)
34 #define LZW_HASH_SIZE 16411
35 #define LZW_HASH_SHIFT 6
36 
37 #define LZW_PREFIX_EMPTY -1
38 #define LZW_PREFIX_FREE -2
39 
41 typedef struct Code{
44  int code;
45  uint8_t suffix;
46 }Code;
47 
49 typedef struct LZWEncodeState {
50  int clear_code;
51  int end_code;
53  int tabsize;
54  int bits;
55  int bufsize;
57  int maxbits;
58  int maxcode;
60  int last_code;
62  void (*put_bits)(PutBitContext *, int, unsigned);
64 
65 
67 
74 static inline int hash(int head, const int add)
75 {
76  head ^= (add << LZW_HASH_SHIFT);
77  if (head >= LZW_HASH_SIZE)
78  head -= LZW_HASH_SIZE;
79  assert(head >= 0 && head < LZW_HASH_SIZE);
80  return head;
81 }
82 
89 static inline int hashNext(int head, const int offset)
90 {
91  head -= offset;
92  if(head < 0)
93  head += LZW_HASH_SIZE;
94  return head;
95 }
96 
102 static inline int hashOffset(const int head)
103 {
104  return head ? LZW_HASH_SIZE - head : 1;
105 }
106 
112 static inline void writeCode(LZWEncodeState * s, int c)
113 {
114  assert(0 <= c && c < 1 << s->bits);
115  s->put_bits(&s->pb, s->bits, c);
116 }
117 
118 
126 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
127 {
128  int h = hash(FFMAX(hash_prefix, 0), c);
129  int hash_offset = hashOffset(h);
130 
131  while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
132  if ((s->tab[h].suffix == c)
133  && (s->tab[h].hash_prefix == hash_prefix))
134  return h;
135  h = hashNext(h, hash_offset);
136  }
137 
138  return h;
139 }
140 
148 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
149 {
150  s->tab[hash_code].code = s->tabsize;
151  s->tab[hash_code].suffix = c;
152  s->tab[hash_code].hash_prefix = hash_prefix;
153 
154  s->tabsize++;
155 
156  if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
157  s->bits++;
158 }
159 
164 static void clearTable(LZWEncodeState * s)
165 {
166  int i, h;
167 
168  writeCode(s, s->clear_code);
169  s->bits = 9;
170  for (i = 0; i < LZW_HASH_SIZE; i++) {
172  }
173  for (i = 0; i < 256; i++) {
174  h = hash(0, i);
175  s->tab[h].code = i;
176  s->tab[h].suffix = i;
178  }
179  s->tabsize = 258;
180 }
181 
188  int ret = put_bits_count(&s->pb) >> 3;
189  ret -= s->output_bytes;
190  s->output_bytes += ret;
191  return ret;
192 }
193 
201 void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,
202  int maxbits, enum FF_LZW_MODES mode,
203  void (*lzw_put_bits)(PutBitContext *, int, unsigned))
204 {
205  s->clear_code = 256;
206  s->end_code = 257;
207  s->maxbits = maxbits;
208  init_put_bits(&s->pb, outbuf, outsize);
209  s->bufsize = outsize;
210  assert(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
211  s->maxcode = 1 << s->maxbits;
212  s->output_bytes = 0;
214  s->bits = 9;
215  s->mode = mode;
216  s->put_bits = lzw_put_bits;
217 }
218 
226 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
227 {
228  int i;
229 
230  if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
231  return -1;
232  }
233 
234  if (s->last_code == LZW_PREFIX_EMPTY)
235  clearTable(s);
236 
237  for (i = 0; i < insize; i++) {
238  uint8_t c = *inbuf++;
239  int code = findCode(s, c, s->last_code);
240  if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
241  writeCode(s, s->last_code);
242  addCode(s, c, s->last_code, code);
243  code= hash(0, c);
244  }
245  s->last_code = s->tab[code].code;
246  if (s->tabsize >= s->maxcode - 1) {
247  clearTable(s);
248  }
249  }
250 
251  return writtenBytes(s);
252 }
253 
260  void (*lzw_flush_put_bits)(PutBitContext *))
261 {
262  if (s->last_code != -1)
263  writeCode(s, s->last_code);
264  writeCode(s, s->end_code);
265  lzw_flush_put_bits(&s->pb);
266  s->last_code = -1;
267 
268  return writtenBytes(s);
269 }