openconnect-unknown/lzo.c

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 >= 65535) {
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     /* Should never happen */
90     if (cnt < 0) {
91 	c->error |= AV_LZO_ERROR;
92 	return;
93     }
94     if (cnt > c->in_end - src) {
95         cnt       = FFMAX(c->in_end - src, 0);
96         c->error |= AV_LZO_INPUT_DEPLETED;
97     }
98     if (cnt > c->out_end - dst) {
99         cnt       = FFMAX(c->out_end - dst, 0);
100         c->error |= AV_LZO_OUTPUT_FULL;
101     }
102 #if defined(INBUF_PADDED) && defined(OUTBUF_PADDED)
103     AV_COPY32U(dst, src);
104     src += 4;
105     dst += 4;
106     cnt -= 4;
107     if (cnt > 0)
108 #endif
109     memcpy(dst, src, cnt);
110     c->in  = src + cnt;
111     c->out = dst + cnt;
112 }
113 
114 /**
115  * @brief Copies previously decoded bytes to current position.
116  * @param back how many bytes back we start, must be > 0
117  * @param cnt number of bytes to copy, must be > 0
118  *
119  * cnt > back is valid, this will copy the bytes we just copied,
120  * thus creating a repeating pattern with a period length of back.
121  */
122 static inline void copy_backptr(LZOContext *c, int back, int cnt)
123 {
124     register uint8_t *dst       = c->out;
125     if (cnt <= 0) {
126         c->error |= AV_LZO_ERROR;
127 	return;
128     }
129     if (dst - c->out_start < back) {
130         c->error |= AV_LZO_INVALID_BACKPTR;
131         return;
132     }
133     if (cnt > c->out_end - dst) {
134         cnt       = FFMAX(c->out_end - dst, 0);
135         c->error |= AV_LZO_OUTPUT_FULL;
136     }
137     av_memcpy_backptr(dst, back, cnt);
138     c->out = dst + cnt;
139 }
140 
141 int av_lzo1x_decode(void *out, int *outlen, const void *in, int *inlen)
142 {
143     int state = 0;
144     int x;
145     LZOContext c;
146     if (*outlen <= 0 || *inlen <= 0) {
147         int res = 0;
148         if (*outlen <= 0)
149             res |= AV_LZO_OUTPUT_FULL;
150         if (*inlen <= 0)
151             res |= AV_LZO_INPUT_DEPLETED;
152         return res;
153     }
154     c.in      = in;
155     c.in_end  = (const uint8_t *)in + *inlen;
156     c.out     = c.out_start = out;
157     c.out_end = (uint8_t *)out + *outlen;
158     c.error   = 0;
159     x         = GETB(c);
160     if (x > 17) {
161         copy(&c, x - 17);
162         x = GETB(c);
163         if (x < 16)
164             c.error |= AV_LZO_ERROR;
165     }
166     if (c.in > c.in_end)
167         c.error |= AV_LZO_INPUT_DEPLETED;
168     while (!c.error) {
169         int cnt, back;
170         if (x > 15) {
171 	    if (x > 63) { /* cccbbbnn BBBBBBBB */
172                 cnt  = (x >> 5) - 1;
173                 back = (GETB(c) << 3) + ((x >> 2) & 7) + 1;
174             } else if (x > 31) { /* 001ccccc (cccccccc...) bbbbbbnn BBBBBBBB */
175                 cnt  = get_len(&c, x, 31);
176                 x    = GETB(c);
177                 back = (GETB(c) << 6) + (x >> 2) + 1;
178             } else { /* 0001bccc (cccccccc...) bbbbbbnn BBBBBBBB */
179                 cnt   = get_len(&c, x, 7);
180                 back  = (1 << 14) + ((x & 8) << 11);
181                 x     = GETB(c);
182                 back += (GETB(c) << 6) + (x >> 2);
183                 if (back == (1 << 14)) {
184                     if (cnt != 1)
185                         c.error |= AV_LZO_ERROR;
186                     break;
187                 }
188             }
189         } else if (!state) { /* 0000llll (llllllll...) { literal... } ( 0000bbnn BBBBBBBB ) */
190             cnt = get_len(&c, x, 15);
191             copy(&c, cnt + 3);
192             x = GETB(c);
193             if (x > 15)
194                 continue;
195             cnt  = 1;
196             back = (1 << 11) + (GETB(c) << 2) + (x >> 2) + 1;
197         } else { /* 0000bbnn BBBBBBBB ) */
198             cnt  = 0;
199             back = (GETB(c) << 2) + (x >> 2) + 1;
200         }
201         copy_backptr(&c, back, cnt + 2);
202         state =
203         cnt   = x & 3;
204         copy(&c, cnt);
205         x = GETB(c);
206     }
207     *inlen = c.in_end - c.in;
208     if (c.in > c.in_end)
209         *inlen = 0;
210     *outlen = c.out_end - c.out;
211     return c.error;
212 }
213 
214 #ifdef TEST
215 #include <stdio.h>
216 #include <lzo/lzo1x.h>
217 #include "log.h"
218 #define MAXSZ (10*1024*1024)
219 
220 /* Define one of these to 1 if you wish to benchmark liblzo
221  * instead of our native implementation. */
222 #define BENCHMARK_LIBLZO_SAFE   0
223 #define BENCHMARK_LIBLZO_UNSAFE 0
224 
225 int main(int argc, char *argv[]) {
226     FILE *in = fopen(argv[1], "rb");
227     int comp_level = argc > 2 ? atoi(argv[2]) : 0;
228     uint8_t *orig = av_malloc(MAXSZ + 16);
229     uint8_t *comp = av_malloc(2*MAXSZ + 16);
230     uint8_t *decomp = av_malloc(MAXSZ + 16);
231     size_t s = fread(orig, 1, MAXSZ, in);
232     lzo_uint clen = 0;
233     long tmp[LZO1X_MEM_COMPRESS];
234     int inlen, outlen;
235     int i;
236     av_log_set_level(AV_LOG_DEBUG);
237     if (comp_level == 0) {
238         lzo1x_1_compress(orig, s, comp, &clen, tmp);
239     } else if (comp_level == 11) {
240         lzo1x_1_11_compress(orig, s, comp, &clen, tmp);
241     } else if (comp_level == 12) {
242         lzo1x_1_12_compress(orig, s, comp, &clen, tmp);
243     } else if (comp_level == 15) {
244         lzo1x_1_15_compress(orig, s, comp, &clen, tmp);
245     } else
246         lzo1x_999_compress(orig, s, comp, &clen, tmp);
247     for (i = 0; i < 300; i++) {
248 START_TIMER
249         inlen = clen; outlen = MAXSZ;
250 #if BENCHMARK_LIBLZO_SAFE
251         if (lzo1x_decompress_safe(comp, inlen, decomp, &outlen, NULL))
252 #elif BENCHMARK_LIBLZO_UNSAFE
253         if (lzo1x_decompress(comp, inlen, decomp, &outlen, NULL))
254 #else
255         if (av_lzo1x_decode(decomp, &outlen, comp, &inlen))
256 #endif
257             av_log(NULL, AV_LOG_ERROR, "decompression error\n");
258 STOP_TIMER("lzod")
259     }
260     if (memcmp(orig, decomp, s))
261         av_log(NULL, AV_LOG_ERROR, "decompression incorrect\n");
262     else
263         av_log(NULL, AV_LOG_ERROR, "decompression OK\n");
264     fclose(in);
265     return 0;
266 }
267 #endif