Main Page
Related Pages
Modules
Data Structures
Files
Examples
File List
Globals
libavcodec
lzwenc.c
Go to the documentation of this file.
1
/*
2
* LZW encoder
3
* Copyright (c) 2007 Bartlomiej Wolowiec
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
28
#include "
avcodec.h
"
29
#include "
put_bits.h
"
30
#include "
lzw.h
"
31
32
#define LZW_MAXBITS 12
33
#define LZW_SIZTABLE (1<<LZW_MAXBITS)
34
#define LZW_HASH_SIZE 16411
35
#define LZW_HASH_SHIFT 6
36
37
#define LZW_PREFIX_EMPTY -1
38
#define LZW_PREFIX_FREE -2
39
41
typedef
struct
Code
{
43
int
hash_prefix
;
44
int
code
;
45
uint8_t
suffix
;
46
}
Code
;
47
49
typedef
struct
LZWEncodeState
{
50
int
clear_code
;
51
int
end_code
;
52
Code
tab
[
LZW_HASH_SIZE
];
53
int
tabsize
;
54
int
bits
;
55
int
bufsize
;
56
PutBitContext
pb
;
57
int
maxbits
;
58
int
maxcode
;
59
int
output_bytes
;
60
int
last_code
;
61
enum
FF_LZW_MODES
mode
;
62
void
(*
put_bits
)(
PutBitContext
*, int, unsigned);
63
}
LZWEncodeState
;
64
65
66
const
int
ff_lzw_encode_state_size
=
sizeof
(
LZWEncodeState
);
67
74
static
inline
int
hash
(
int
head,
const
int
add)
75
{
76
head ^= (add <<
LZW_HASH_SHIFT
);
77
if
(head >=
LZW_HASH_SIZE
)
78
head -=
LZW_HASH_SIZE
;
79
assert(head >= 0 && head <
LZW_HASH_SIZE
);
80
return
head;
81
}
82
89
static
inline
int
hashNext
(
int
head,
const
int
offset)
90
{
91
head -= offset;
92
if
(head < 0)
93
head +=
LZW_HASH_SIZE
;
94
return
head;
95
}
96
102
static
inline
int
hashOffset
(
const
int
head)
103
{
104
return
head ?
LZW_HASH_SIZE
- head : 1;
105
}
106
112
static
inline
void
writeCode
(
LZWEncodeState
* s,
int
c)
113
{
114
assert(0 <= c && c < 1 << s->
bits
);
115
s->
put_bits
(&s->
pb
, s->
bits
, c);
116
}
117
118
126
static
inline
int
findCode
(
LZWEncodeState
* s, uint8_t c,
int
hash_prefix)
127
{
128
int
h =
hash
(
FFMAX
(hash_prefix, 0), c);
129
int
hash_offset =
hashOffset
(h);
130
131
while
(s->
tab
[h].
hash_prefix
!=
LZW_PREFIX_FREE
) {
132
if
((s->
tab
[h].
suffix
== c)
133
&& (s->
tab
[h].
hash_prefix
== hash_prefix))
134
return
h;
135
h =
hashNext
(h, hash_offset);
136
}
137
138
return
h;
139
}
140
148
static
inline
void
addCode
(
LZWEncodeState
* s, uint8_t c,
int
hash_prefix,
int
hash_code)
149
{
150
s->
tab
[hash_code].
code
= s->
tabsize
;
151
s->
tab
[hash_code].
suffix
= c;
152
s->
tab
[hash_code].
hash_prefix
= hash_prefix;
153
154
s->
tabsize
++;
155
156
if
(s->
tabsize
>= (1 << s->
bits
) + (s->
mode
==
FF_LZW_GIF
))
157
s->
bits
++;
158
}
159
164
static
void
clearTable
(
LZWEncodeState
* s)
165
{
166
int
i, h;
167
168
writeCode
(s, s->
clear_code
);
169
s->
bits
= 9;
170
for
(i = 0; i <
LZW_HASH_SIZE
; i++) {
171
s->
tab
[i].
hash_prefix
=
LZW_PREFIX_FREE
;
172
}
173
for
(i = 0; i < 256; i++) {
174
h =
hash
(0, i);
175
s->
tab
[h].
code
= i;
176
s->
tab
[h].
suffix
= i;
177
s->
tab
[h].
hash_prefix
=
LZW_PREFIX_EMPTY
;
178
}
179
s->
tabsize
= 258;
180
}
181
187
static
int
writtenBytes
(
LZWEncodeState
*s){
188
int
ret =
put_bits_count
(&s->
pb
) >> 3;
189
ret -= s->
output_bytes
;
190
s->
output_bytes
+= ret;
191
return
ret;
192
}
193
201
void
ff_lzw_encode_init
(
LZWEncodeState
*s, uint8_t *outbuf,
int
outsize,
202
int
maxbits,
enum
FF_LZW_MODES
mode,
203
void
(*lzw_put_bits)(
PutBitContext
*,
int
,
unsigned
))
204
{
205
s->
clear_code
= 256;
206
s->
end_code
= 257;
207
s->
maxbits
= maxbits;
208
init_put_bits
(&s->
pb
, outbuf, outsize);
209
s->
bufsize
= outsize;
210
assert(s->
maxbits
>= 9 && s->
maxbits
<=
LZW_MAXBITS
);
211
s->
maxcode
= 1 << s->
maxbits
;
212
s->
output_bytes
= 0;
213
s->
last_code
=
LZW_PREFIX_EMPTY
;
214
s->
bits
= 9;
215
s->
mode
= mode;
216
s->
put_bits
= lzw_put_bits;
217
}
218
226
int
ff_lzw_encode
(
LZWEncodeState
* s,
const
uint8_t * inbuf,
int
insize)
227
{
228
int
i;
229
230
if
(insize * 3 > (s->
bufsize
- s->
output_bytes
) * 2){
231
return
-1;
232
}
233
234
if
(s->
last_code
==
LZW_PREFIX_EMPTY
)
235
clearTable
(s);
236
237
for
(i = 0; i < insize; i++) {
238
uint8_t c = *inbuf++;
239
int
code =
findCode
(s, c, s->
last_code
);
240
if
(s->
tab
[code].
hash_prefix
==
LZW_PREFIX_FREE
) {
241
writeCode
(s, s->
last_code
);
242
addCode
(s, c, s->
last_code
, code);
243
code=
hash
(0, c);
244
}
245
s->
last_code
= s->
tab
[code].
code
;
246
if
(s->
tabsize
>= s->
maxcode
- 1) {
247
clearTable
(s);
248
}
249
}
250
251
return
writtenBytes
(s);
252
}
253
259
int
ff_lzw_encode_flush
(
LZWEncodeState
*s,
260
void
(*lzw_flush_put_bits)(
PutBitContext
*))
261
{
262
if
(s->
last_code
!= -1)
263
writeCode
(s, s->
last_code
);
264
writeCode
(s, s->
end_code
);
265
lzw_flush_put_bits(&s->
pb
);
266
s->
last_code
= -1;
267
268
return
writtenBytes
(s);
269
}