Statistics
| Branch: | Revision:

ffmpeg / libavcodec / lzwenc.c @ 2912e87a

History | View | Annotate | Download (7.11 KB)

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

    
22
/**
23
 * LZW encoder
24
 * @file
25
 * @author Bartlomiej Wolowiec
26
 */
27

    
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

    
40
/** One code in hash table */
41
typedef struct Code{
42
    /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code
43
    int hash_prefix;
44
    int code;               ///< LZW code
45
    uint8_t suffix;         ///< Last character in code block
46
}Code;
47

    
48
/** LZW encode state */
49
typedef struct LZWEncodeState {
50
    int clear_code;          ///< Value of clear code
51
    int end_code;            ///< Value of end code
52
    Code tab[LZW_HASH_SIZE]; ///< Hash table
53
    int tabsize;             ///< Number of values in hash table
54
    int bits;                ///< Actual bits code
55
    int bufsize;             ///< Size of output buffer
56
    PutBitContext pb;        ///< Put bit context for output
57
    int maxbits;             ///< Max bits code
58
    int maxcode;             ///< Max value of code
59
    int output_bytes;        ///< Number of written bytes
60
    int last_code;           ///< Value of last output code or LZW_PREFIX_EMPTY
61
    enum FF_LZW_MODES mode;  ///< TIFF or GIF
62
    void (*put_bits)(PutBitContext *, int, unsigned); ///< GIF is LE while TIFF is BE
63
}LZWEncodeState;
64

    
65

    
66
const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);
67

    
68
/**
69
 * Hash function adding character
70
 * @param head LZW code for prefix
71
 * @param add Character to add
72
 * @return New hash value
73
 */
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

    
83
/**
84
 * Hash function calculates next hash value
85
 * @param head Actual hash code
86
 * @param offset Offset calculated by hashOffset
87
 * @return New hash value
88
 */
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

    
97
/**
98
 * Hash function calculates hash offset
99
 * @param head Actual hash code
100
 * @return Hash offset
101
 */
102
static inline int hashOffset(const int head)
103
{
104
    return head ? LZW_HASH_SIZE - head : 1;
105
}
106

    
107
/**
108
 * Write one code to stream
109
 * @param s LZW state
110
 * @param c code to write
111
 */
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

    
119
/**
120
 * Find LZW code for block
121
 * @param s LZW state
122
 * @param c Last character in block
123
 * @param hash_prefix LZW code for prefix
124
 * @return LZW code for block or -1 if not found in table
125
 */
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

    
141
/**
142
 * Add block to LZW code table
143
 * @param s LZW state
144
 * @param c Last character in block
145
 * @param hash_prefix LZW code for prefix
146
 * @param hash_code LZW code for bytes block
147
 */
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

    
160
/**
161
 * Clear LZW code table
162
 * @param s LZW state
163
 */
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

    
182
/**
183
 * Calculate number of bytes written
184
 * @param s LZW encode state
185
 * @return Number of bytes written
186
 */
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

    
194
/**
195
 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
196
 * @param s LZW state
197
 * @param outbuf Output buffer
198
 * @param outsize Size of output buffer
199
 * @param maxbits Maximum length of code
200
 */
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

    
219
/**
220
 * LZW main compress function
221
 * @param s LZW state
222
 * @param inbuf Input buffer
223
 * @param insize Size of input buffer
224
 * @return Number of bytes written or -1 on error
225
 */
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

    
254
/**
255
 * Write end code and flush bitstream
256
 * @param s LZW state
257
 * @return Number of bytes written or -1 on error
258
 */
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
}