Implement Snappy decompression
[libav.git] / libavcodec / snappy.c
1 /*
2 * Snappy decompression algorithm
3 * Copyright (c) 2015 Luca Barbato
4 *
5 * This file is part of Libav.
6 *
7 * Libav 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 * Libav 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 Libav; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22 #include "libavutil/mem.h"
23
24 #include "bytestream.h"
25 #include "snappy.h"
26
27 enum {
28 SNAPPY_LITERAL,
29 SNAPPY_COPY_1,
30 SNAPPY_COPY_2,
31 SNAPPY_COPY_4,
32 };
33
34 static int64_t bytestream2_get_levarint(GetByteContext *gb)
35 {
36 uint64_t val = 0;
37 int shift = 0;
38 int tmp;
39
40 do {
41 tmp = bytestream2_get_byte(gb);
42 val |= (tmp & 127) << shift;
43 shift += 7;
44 } while (tmp & 128);
45
46 return val;
47 }
48
49 static int snappy_literal(GetByteContext *gb, uint8_t *p, int size, int val)
50 {
51 unsigned int len = 1;
52
53 switch (val) {
54 case 63:
55 len += bytestream2_get_le32(gb);
56 break;
57 case 62:
58 len += bytestream2_get_le24(gb);
59 break;
60 case 61:
61 len += bytestream2_get_le16(gb);
62 break;
63 case 60:
64 len += bytestream2_get_byte(gb);
65 break;
66 default: // val < 60
67 len += val;
68 }
69
70 if (size < len)
71 return AVERROR_INVALIDDATA;
72
73 bytestream2_get_buffer(gb, p, len);
74
75 return len;
76 }
77
78 static int snappy_copy(uint8_t *start, uint8_t *p, int size,
79 unsigned int off, int len)
80 {
81 uint8_t *q;
82 int i;
83 if (off > p - start || size < len)
84 return AVERROR_INVALIDDATA;
85
86 q = p - off;
87
88 for (i = 0; i < len; i++)
89 p[i] = q[i];
90
91 return len;
92 }
93
94 static int snappy_copy1(GetByteContext *gb, uint8_t *start, uint8_t *p,
95 int size, int val)
96 {
97 int len = 4 + (val & 0x7);
98 unsigned int off = bytestream2_get_byte(gb) | (val & 0x38) << 5;
99
100 return snappy_copy(start, p, size, off, len);
101 }
102
103 static int snappy_copy2(GetByteContext *gb, uint8_t *start, uint8_t *p,
104 int size, int val)
105 {
106 int len = 1 + val;
107 unsigned int off = bytestream2_get_le16(gb);
108
109 return snappy_copy(start, p, size, off, len);
110 }
111
112 static int snappy_copy4(GetByteContext *gb, uint8_t *start, uint8_t *p,
113 int size, int val)
114 {
115 int len = 1 + val;
116 unsigned int off = bytestream2_get_le32(gb);
117
118 return snappy_copy(start, p, size, off, len);
119 }
120
121 static int64_t decode_len(GetByteContext *gb)
122 {
123 int64_t len = bytestream2_get_levarint(gb);
124
125 if (len < 0 || len > UINT_MAX)
126 return AVERROR_INVALIDDATA;
127
128 return len;
129 }
130
131 int ff_snappy_uncompress(GetByteContext *gb, uint8_t **buf, int64_t *size)
132 {
133 int64_t len = decode_len(gb);
134 int ret = 0;
135 uint8_t *p;
136
137 if (len < 0)
138 return len;
139
140 if ((ret = av_reallocp(buf, len)) < 0)
141 return AVERROR(ENOMEM);
142
143 *size = len;
144 p = *buf;
145
146 while (bytestream2_get_bytes_left(gb) > 0) {
147 uint8_t s = bytestream2_get_byte(gb);
148 int val = s >> 2;
149
150 switch (s & 0x03) {
151 case SNAPPY_LITERAL:
152 ret = snappy_literal(gb, p, len, val);
153 break;
154 case SNAPPY_COPY_1:
155 ret = snappy_copy1(gb, *buf, p, len, val);
156 break;
157 case SNAPPY_COPY_2:
158 ret = snappy_copy2(gb, *buf, p, len, val);
159 break;
160 case SNAPPY_COPY_4:
161 ret = snappy_copy4(gb, *buf, p, len, val);
162 break;
163 }
164
165 if (ret < 0)
166 return ret;
167
168 p += ret;
169 len -= ret;
170 }
171
172 return 0;
173 }