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