FFmpeg
lzw.c
Go to the documentation of this file.
1 /*
2  * LZW decoder
3  * Copyright (c) 2003 Fabrice Bellard
4  * Copyright (c) 2006 Konstantin Shishkov
5  *
6  * This file is part of FFmpeg.
7  *
8  * FFmpeg is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  *
13  * FFmpeg is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with FFmpeg; if not, write to the Free Software
20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21  */
22 
23 /**
24  * @file
25  * @brief LZW decoding routines
26  * @author Fabrice Bellard
27  * @author modified for use in TIFF by Konstantin Shishkov
28  */
29 
30 #include "avcodec.h"
31 #include "bytestream.h"
32 #include "lzw.h"
33 #include "libavutil/mem.h"
34 
35 #define LZW_MAXBITS 12
36 #define LZW_SIZTABLE (1<<LZW_MAXBITS)
37 
38 static const uint16_t mask[17] =
39 {
40  0x0000, 0x0001, 0x0003, 0x0007,
41  0x000F, 0x001F, 0x003F, 0x007F,
42  0x00FF, 0x01FF, 0x03FF, 0x07FF,
43  0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF
44 };
45 
46 struct LZWState {
48  int bbits;
49  unsigned int bbuf;
50 
51  int mode; ///< Decoder mode
52  int cursize; ///< The current code size
53  int curmask;
54  int codesize;
56  int end_code;
57  int newcodes; ///< First available code
58  int top_slot; ///< Highest code for current size
60  int slot; ///< Last read code
61  int fc, oc;
65  uint16_t prefix[LZW_SIZTABLE];
66  int bs; ///< current buffer size for GIF
67 };
68 
69 /* get one code from stream */
70 static int lzw_get_code(struct LZWState * s)
71 {
72  int c;
73 
74  if (s->bbits < s->cursize && bytestream2_get_bytes_left(&s->gb) <= 0)
75  return s->end_code;
76 
77  if(s->mode == FF_LZW_GIF) {
78  while (s->bbits < s->cursize) {
79  if (!s->bs) {
80  s->bs = bytestream2_get_byte(&s->gb);
81  }
82  s->bbuf |= bytestream2_get_byte(&s->gb) << s->bbits;
83  s->bbits += 8;
84  s->bs--;
85  }
86  c = s->bbuf;
87  s->bbuf >>= s->cursize;
88  } else { // TIFF
89  while (s->bbits < s->cursize) {
90  s->bbuf = (s->bbuf << 8) | bytestream2_get_byte(&s->gb);
91  s->bbits += 8;
92  }
93  c = s->bbuf >> (s->bbits - s->cursize);
94  }
95  s->bbits -= s->cursize;
96  return c & s->curmask;
97 }
98 
100 {
101  struct LZWState *s = (struct LZWState *)p;
102 
103  if(s->mode == FF_LZW_GIF) {
104  while (s->bs > 0 && bytestream2_get_bytes_left(&s->gb)) {
105  bytestream2_skip(&s->gb, s->bs);
106  s->bs = bytestream2_get_byte(&s->gb);
107  }
108  }else
110  return bytestream2_tell(&s->gb);
111 }
112 
114 {
115  *p = av_mallocz(sizeof(struct LZWState));
116 }
117 
119 {
120  av_freep(p);
121 }
122 
123 /**
124  * Initialize LZW decoder
125  * @param p LZW context
126  * @param csize initial code size in bits
127  * @param buf input data
128  * @param buf_size input data size
129  * @param mode decoder working mode - either GIF or TIFF
130  */
131 int ff_lzw_decode_init(LZWState *p, int csize, const uint8_t *buf, int buf_size, int mode)
132 {
133  struct LZWState *s = (struct LZWState *)p;
134 
135  if(csize < 1 || csize >= LZW_MAXBITS)
136  return -1;
137  /* read buffer */
138  bytestream2_init(&s->gb, buf, buf_size);
139  s->bbuf = 0;
140  s->bbits = 0;
141  s->bs = 0;
142 
143  /* decoder */
144  s->codesize = csize;
145  s->cursize = s->codesize + 1;
146  s->curmask = mask[s->cursize];
147  s->top_slot = 1 << s->cursize;
148  s->clear_code = 1 << s->codesize;
149  s->end_code = s->clear_code + 1;
150  s->slot = s->newcodes = s->clear_code + 2;
151  s->oc = s->fc = -1;
152  s->sp = s->stack;
153 
154  s->mode = mode;
155  s->extra_slot = s->mode == FF_LZW_TIFF;
156  return 0;
157 }
158 
159 /**
160  * Decode given number of bytes
161  * NOTE: the algorithm here is inspired from the LZW GIF decoder
162  * written by Steven A. Bennett in 1987.
163  *
164  * @param p LZW context
165  * @param buf output buffer
166  * @param len number of bytes to decode
167  * @return number of bytes decoded
168  */
170  int l, c, code, oc, fc;
171  uint8_t *sp;
172  struct LZWState *s = (struct LZWState *)p;
173 
174  if (s->end_code < 0)
175  return 0;
176 
177  l = len;
178  sp = s->sp;
179  oc = s->oc;
180  fc = s->fc;
181 
182  for (;;) {
183  while (sp > s->stack) {
184  *buf++ = *(--sp);
185  if ((--l) == 0)
186  goto the_end;
187  }
188  c = lzw_get_code(s);
189  if (c == s->end_code) {
190  break;
191  } else if (c == s->clear_code) {
192  s->cursize = s->codesize + 1;
193  s->curmask = mask[s->cursize];
194  s->slot = s->newcodes;
195  s->top_slot = 1 << s->cursize;
196  fc= oc= -1;
197  } else {
198  code = c;
199  if (code == s->slot && fc>=0) {
200  *sp++ = fc;
201  code = oc;
202  }else if(code >= s->slot)
203  break;
204  while (code >= s->newcodes) {
205  *sp++ = s->suffix[code];
206  code = s->prefix[code];
207  }
208  *sp++ = code;
209  if (s->slot < s->top_slot && oc>=0) {
210  s->suffix[s->slot] = code;
211  s->prefix[s->slot++] = oc;
212  }
213  fc = code;
214  oc = c;
215  if (s->slot >= s->top_slot - s->extra_slot) {
216  if (s->cursize < LZW_MAXBITS) {
217  s->top_slot <<= 1;
218  s->curmask = mask[++s->cursize];
219  }
220  }
221  }
222  }
223  s->end_code = -1;
224  the_end:
225  s->sp = sp;
226  s->oc = oc;
227  s->fc = fc;
228  return len - l;
229 }
int ff_lzw_decode(LZWState *p, uint8_t *buf, int len)
Decode given number of bytes NOTE: the algorithm here is inspired from the LZW GIF decoder written by...
Definition: lzw.c:169
int cursize
The current code size.
Definition: lzw.c:52
Memory handling functions.
uint16_t prefix[LZW_SIZTABLE]
Definition: lzw.c:65
av_cold void ff_lzw_decode_close(LZWState **p)
Definition: lzw.c:118
av_cold void ff_lzw_decode_open(LZWState **p)
Definition: lzw.c:113
static av_always_inline void bytestream2_init(GetByteContext *g, const uint8_t *buf, int buf_size)
Definition: bytestream.h:133
int clear_code
Definition: lzw.c:55
void * av_mallocz(size_t size)
Allocate a memory block with alignment suitable for all memory accesses (including vectors if availab...
Definition: mem.c:236
uint8_t suffix[LZW_SIZTABLE]
Definition: lzw.c:64
int top_slot
Highest code for current size.
Definition: lzw.c:58
int ff_lzw_decode_tail(LZWState *p)
Definition: lzw.c:99
uint8_t
#define av_cold
Definition: attributes.h:82
int bbits
Definition: lzw.c:48
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
uint8_t stack[LZW_SIZTABLE]
Definition: lzw.c:63
int newcodes
First available code.
Definition: lzw.c:57
int end_code
Definition: lzw.c:56
Definition: lzw.c:46
#define LZW_SIZTABLE
Definition: lzw.c:36
static const uint16_t mask[17]
Definition: lzw.c:38
static av_always_inline void bytestream2_skip(GetByteContext *g, unsigned int size)
Definition: bytestream.h:164
int extra_slot
Definition: lzw.c:59
uint8_t * sp
Definition: lzw.c:62
static av_always_inline unsigned int bytestream2_get_bytes_left(GetByteContext *g)
Definition: bytestream.h:154
unsigned int bbuf
Definition: lzw.c:49
Definition: lzw.h:38
int fc
Definition: lzw.c:61
int codesize
Definition: lzw.c:54
#define s(width, name)
Definition: cbs_vp9.c:257
int bs
current buffer size for GIF
Definition: lzw.c:66
static int lzw_get_code(struct LZWState *s)
Definition: lzw.c:70
static av_always_inline int bytestream2_tell(GetByteContext *g)
Definition: bytestream.h:188
Libavcodec external API header.
GetByteContext gb
Definition: lzw.c:47
void * buf
Definition: avisynth_c.h:766
int slot
Last read code.
Definition: lzw.c:60
int oc
Definition: lzw.c:61
int curmask
Definition: lzw.c:53
and forward the test the status of outputs and forward it to the corresponding return FFERROR_NOT_READY If the filters stores internally one or a few frame for some it can consider them to be part of the FIFO and delay acknowledging a status change accordingly Example code
LZW decoding routines.
#define LZW_MAXBITS
Definition: lzw.c:35
int mode
Decoder mode.
Definition: lzw.c:51
int ff_lzw_decode_init(LZWState *p, int csize, const uint8_t *buf, int buf_size, int mode)
Initialize LZW decoder.
Definition: lzw.c:131
int len
#define av_freep(p)
mode
Use these values in ebur128_init (or&#39;ed).
Definition: ebur128.h:83