FFmpeg: libavcodec/lzw.c Source File

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 "libavutil/attributes.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 {
47   GetByteContext gb;
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;
55   int clear_code;
56   int end_code;
57   int newcodes; ///< First available code
58   int top_slot; ///< Highest code for current size
59   int extra_slot;
60   int slot; ///< Last read code
61   int fc, oc;
62   uint8_t *sp;
63   uint8_t stack[LZW_SIZTABLE];
64   uint8_t suffix[LZW_SIZTABLE];
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 
99  int ff_lzw_decode_tail(LZWState *p)
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
109  bytestream2_skip(&s->gb, bytestream2_get_bytes_left(&s->gb));
110  return bytestream2_tell(&s->gb);
111 }
112 
113  av_cold void ff_lzw_decode_open(LZWState **p)
114 {
115  *p = av_mallocz(sizeof(struct LZWState));
116 }
117 
118  av_cold void ff_lzw_decode_close(LZWState **p)
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  */
169  int ff_lzw_decode(LZWState *p, uint8_t *buf, int len){
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 }
LZWState::prefix
uint16_t prefix[LZW_SIZTABLE]
Definition: lzw.c:65
GetByteContext
Definition: bytestream.h:33
fc
#define fc(width, name, range_min, range_max)
Definition: cbs_av1.c:551
ff_lzw_decode
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
ff_lzw_decode_close
av_cold void ff_lzw_decode_close(LZWState **p)
Definition: lzw.c:118
LZWState::suffix
uint8_t suffix[LZW_SIZTABLE]
Definition: lzw.c:64
bytestream2_skip
static av_always_inline void bytestream2_skip(GetByteContext *g, unsigned int size)
Definition: bytestream.h:168
LZWState::bs
int bs
current buffer size for GIF
Definition: lzw.c:66
LZWState::bbits
int bbits
Definition: lzw.c:48
FF_LZW_TIFF
@ FF_LZW_TIFF
Definition: lzw.h:39
LZW_SIZTABLE
#define LZW_SIZTABLE
Definition: lzw.c:36
av_cold
#define av_cold
Definition: attributes.h:90
LZWState::stack
uint8_t stack[LZW_SIZTABLE]
Definition: lzw.c:63
LZWState::newcodes
int newcodes
First available code.
Definition: lzw.c:57
mask
static const uint16_t mask[17]
Definition: lzw.c:38
LZWState::gb
GetByteContext gb
Definition: lzw.c:47
LZWState::clear_code
int clear_code
Definition: lzw.c:55
s
#define s(width, name)
Definition: cbs_vp9.c:257
LZWState::oc
int oc
Definition: lzw.c:61
ff_lzw_decode_open
av_cold void ff_lzw_decode_open(LZWState **p)
Definition: lzw.c:113
LZWState
Definition: lzw.c:46
LZWState::extra_slot
int extra_slot
Definition: lzw.c:59
FF_LZW_GIF
@ FF_LZW_GIF
Definition: lzw.h:38
c
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
bytestream2_get_bytes_left
static av_always_inline int bytestream2_get_bytes_left(GetByteContext *g)
Definition: bytestream.h:158
bytestream2_tell
static av_always_inline int bytestream2_tell(GetByteContext *g)
Definition: bytestream.h:192
lzw.h
LZW decoding routines.
sp
#define sp
Definition: regdef.h:63
LZWState::codesize
int codesize
Definition: lzw.c:54
LZWState::bbuf
unsigned int bbuf
Definition: lzw.c:49
attributes.h
lzw_get_code
static int lzw_get_code(struct LZWState *s)
Definition: lzw.c:70
LZWState::sp
uint8_t * sp
Definition: lzw.c:62
code
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
Definition: filter_design.txt:178
ff_lzw_decode_init
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
av_mallocz
void * av_mallocz(size_t size)
Allocate a memory block with alignment suitable for all memory accesses (including vectors if availab...
Definition: mem.c:263
len
int len
Definition: vorbis_enc_data.h:426
LZWState::end_code
int end_code
Definition: lzw.c:56
LZWState::fc
int fc
Definition: lzw.c:61
LZWState::curmask
int curmask
Definition: lzw.c:53
LZWState::top_slot
int top_slot
Highest code for current size.
Definition: lzw.c:58
mode
mode
Definition: ebur128.h:83
mem.h
LZWState::mode
int mode
Decoder mode.
Definition: lzw.c:51
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
bytestream.h
LZWState::slot
int slot
Last read code.
Definition: lzw.c:60
bytestream2_init
static av_always_inline void bytestream2_init(GetByteContext *g, const uint8_t *buf, int buf_size)
Definition: bytestream.h:137
ff_lzw_decode_tail
int ff_lzw_decode_tail(LZWState *p)
Definition: lzw.c:99
LZW_MAXBITS
#define LZW_MAXBITS
Definition: lzw.c:35
LZWState::cursize
int cursize
The current code size.
Definition: lzw.c:52
Generated on Wed Aug 24 2022 21:37:41 for FFmpeg by   doxygen 1.8.17

AltStyle によって変換されたページ (->オリジナル) /