FFmpeg
lzo.c
Go to the documentation of this file.
1 /*
2  * LZO 1x decompression
3  * Copyright (c) 2006 Reimar Doeffinger
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 #include <string.h>
23 
24 #include "avutil.h"
25 #include "avassert.h"
26 #include "common.h"
27 #include "intreadwrite.h"
28 #include "lzo.h"
29 
30 /// Define if we may write up to 12 bytes beyond the output buffer.
31 #define OUTBUF_PADDED 1
32 /// Define if we may read up to 8 bytes beyond the input buffer.
33 #define INBUF_PADDED 1
34 
35 typedef struct LZOContext {
36  const uint8_t *in, *in_end;
37  uint8_t *out_start, *out, *out_end;
38  int error;
39 } LZOContext;
40 
41 /**
42  * @brief Reads one byte from the input buffer, avoiding an overrun.
43  * @return byte read
44  */
45 static inline int get_byte(LZOContext *c)
46 {
47  if (c->in < c->in_end)
48  return *c->in++;
49  c->error |= AV_LZO_INPUT_DEPLETED;
50  return 1;
51 }
52 
53 #ifdef INBUF_PADDED
54 #define GETB(c) (*(c).in++)
55 #else
56 #define GETB(c) get_byte(&(c))
57 #endif
58 
59 /**
60  * @brief Decodes a length value in the coding used by lzo.
61  * @param x previous byte value
62  * @param mask bits used from x
63  * @return decoded length value
64  */
65 static inline int get_len(LZOContext *c, int x, int mask)
66 {
67  int cnt = x & mask;
68  if (!cnt) {
69  while (!(x = get_byte(c))) {
70  if (cnt >= INT_MAX - 1000) {
71  c->error |= AV_LZO_ERROR;
72  break;
73  }
74  cnt += 255;
75  }
76  cnt += mask + x;
77  }
78  return cnt;
79 }
80 
81 /**
82  * @brief Copies bytes from input to output buffer with checking.
83  * @param cnt number of bytes to copy, must be >= 0
84  */
85 static inline void copy(LZOContext *c, int cnt)
86 {
87  register const uint8_t *src = c->in;
88  register uint8_t *dst = c->out;
89  av_assert0(cnt >= 0);
90  if (cnt > c->in_end - src) {
91  cnt = FFMAX(c->in_end - src, 0);
92  c->error |= AV_LZO_INPUT_DEPLETED;
93  }
94  if (cnt > c->out_end - dst) {
95  cnt = FFMAX(c->out_end - dst, 0);
96  c->error |= AV_LZO_OUTPUT_FULL;
97  }
98 #if defined(INBUF_PADDED) && defined(OUTBUF_PADDED)
99  AV_COPY32U(dst, src);
100  src += 4;
101  dst += 4;
102  cnt -= 4;
103  if (cnt > 0)
104 #endif
105  memcpy(dst, src, cnt);
106  c->in = src + cnt;
107  c->out = dst + cnt;
108 }
109 
110 /**
111  * @brief Copies previously decoded bytes to current position.
112  * @param back how many bytes back we start, must be > 0
113  * @param cnt number of bytes to copy, must be > 0
114  *
115  * cnt > back is valid, this will copy the bytes we just copied,
116  * thus creating a repeating pattern with a period length of back.
117  */
118 static inline void copy_backptr(LZOContext *c, int back, int cnt)
119 {
120  register uint8_t *dst = c->out;
121  av_assert0(cnt > 0);
122  if (dst - c->out_start < back) {
123  c->error |= AV_LZO_INVALID_BACKPTR;
124  return;
125  }
126  if (cnt > c->out_end - dst) {
127  cnt = FFMAX(c->out_end - dst, 0);
128  c->error |= AV_LZO_OUTPUT_FULL;
129  }
130  av_memcpy_backptr(dst, back, cnt);
131  c->out = dst + cnt;
132 }
133 
134 int av_lzo1x_decode(void *out, int *outlen, const void *in, int *inlen)
135 {
136  int state = 0;
137  int x;
138  LZOContext c;
139  if (*outlen <= 0 || *inlen <= 0) {
140  int res = 0;
141  if (*outlen <= 0)
142  res |= AV_LZO_OUTPUT_FULL;
143  if (*inlen <= 0)
144  res |= AV_LZO_INPUT_DEPLETED;
145  return res;
146  }
147  c.in = in;
148  c.in_end = (const uint8_t *)in + *inlen;
149  c.out = c.out_start = out;
150  c.out_end = (uint8_t *)out + *outlen;
151  c.error = 0;
152  x = GETB(c);
153  if (x > 17) {
154  copy(&c, x - 17);
155  x = GETB(c);
156  if (x < 16)
157  c.error |= AV_LZO_ERROR;
158  }
159  if (c.in > c.in_end)
160  c.error |= AV_LZO_INPUT_DEPLETED;
161  while (!c.error) {
162  int cnt, back;
163  if (x > 15) {
164  if (x > 63) {
165  cnt = (x >> 5) - 1;
166  back = (GETB(c) << 3) + ((x >> 2) & 7) + 1;
167  } else if (x > 31) {
168  cnt = get_len(&c, x, 31);
169  x = GETB(c);
170  back = (GETB(c) << 6) + (x >> 2) + 1;
171  } else {
172  cnt = get_len(&c, x, 7);
173  back = (1 << 14) + ((x & 8) << 11);
174  x = GETB(c);
175  back += (GETB(c) << 6) + (x >> 2);
176  if (back == (1 << 14)) {
177  if (cnt != 1)
178  c.error |= AV_LZO_ERROR;
179  break;
180  }
181  }
182  } else if (!state) {
183  cnt = get_len(&c, x, 15);
184  copy(&c, cnt + 3);
185  x = GETB(c);
186  if (x > 15)
187  continue;
188  cnt = 1;
189  back = (1 << 11) + (GETB(c) << 2) + (x >> 2) + 1;
190  } else {
191  cnt = 0;
192  back = (GETB(c) << 2) + (x >> 2) + 1;
193  }
194  copy_backptr(&c, back, cnt + 2);
195  state =
196  cnt = x & 3;
197  copy(&c, cnt);
198  x = GETB(c);
199  }
200  *inlen = c.in_end - c.in;
201  if (c.in > c.in_end)
202  *inlen = 0;
203  *outlen = c.out_end - c.out;
204  return c.error;
205 }
out
FILE * out
Definition: movenc.c:54
copy
static void copy(LZOContext *c, int cnt)
Copies bytes from input to output buffer with checking.
Definition: lzo.c:85
FFMAX
#define FFMAX(a, b)
Definition: macros.h:47
LZOContext::out_end
uint8_t * out_end
Definition: lzo.c:37
AV_LZO_INPUT_DEPLETED
#define AV_LZO_INPUT_DEPLETED
end of the input buffer reached before decoding finished
Definition: lzo.h:37
LZOContext::in
const uint8_t * in
Definition: lzo.c:36
LZOContext::out
uint8_t * out
Definition: lzo.c:37
avassert.h
AV_COPY32U
#define AV_COPY32U(d, s)
Definition: intreadwrite.h:572
mask
static const uint16_t mask[17]
Definition: lzw.c:38
av_memcpy_backptr
void av_memcpy_backptr(uint8_t *dst, int back, int cnt)
Overlapping memcpy() implementation.
Definition: mem.c:454
intreadwrite.h
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
LZOContext::out_start
uint8_t * out_start
Definition: lzo.c:37
LZOContext
Definition: lzo.c:35
get_len
static int get_len(LZOContext *c, int x, int mask)
Decodes a length value in the coding used by lzo.
Definition: lzo.c:65
src
#define src
Definition: vp8dsp.c:255
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
av_lzo1x_decode
int av_lzo1x_decode(void *out, int *outlen, const void *in, int *inlen)
Decodes LZO 1x compressed data.
Definition: lzo.c:134
state
static struct @320 state
AV_LZO_INVALID_BACKPTR
#define AV_LZO_INVALID_BACKPTR
a reference to previously decoded data was wrong
Definition: lzo.h:41
AV_LZO_ERROR
#define AV_LZO_ERROR
a non-specific error in the compressed bitstream
Definition: lzo.h:43
get_byte
static int get_byte(LZOContext *c)
Reads one byte from the input buffer, avoiding an overrun.
Definition: lzo.c:45
LZOContext::error
int error
Definition: lzo.c:38
common.h
LZOContext::in_end
const uint8_t * in_end
Definition: lzo.c:36
GETB
#define GETB(c)
Definition: lzo.c:54
lzo.h
copy_backptr
static void copy_backptr(LZOContext *c, int back, int cnt)
Copies previously decoded bytes to current position.
Definition: lzo.c:118
AV_LZO_OUTPUT_FULL
#define AV_LZO_OUTPUT_FULL
decoded data did not fit into output buffer
Definition: lzo.h:39
avutil.h