GCC Code Coverage Report
Directory: ../../../ffmpeg/ Exec Total Coverage
File: src/libavcodec/lzwenc.c Lines: 86 88 97.7 %
Date: 2019-11-20 04:07:19 Branches: 30 36 83.3 %

Line Branch Exec Source
1
/*
2
 * LZW encoder
3
 * Copyright (c) 2007 Bartlomiej Wolowiec
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
/**
23
 * @file
24
 * LZW encoder
25
 * @author Bartlomiej Wolowiec
26
 */
27
28
#include "avcodec.h"
29
#include "lzw.h"
30
#include "mathops.h"
31
#include "put_bits.h"
32
33
#define LZW_MAXBITS 12
34
#define LZW_SIZTABLE (1<<LZW_MAXBITS)
35
#define LZW_HASH_SIZE 16411
36
#define LZW_HASH_SHIFT 6
37
38
#define LZW_PREFIX_EMPTY -1
39
#define LZW_PREFIX_FREE -2
40
41
/** One code in hash table */
42
typedef struct Code{
43
    /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code
44
    int hash_prefix;
45
    int code;               ///< LZW code
46
    uint8_t suffix;         ///< Last character in code block
47
}Code;
48
49
/** LZW encode state */
50
typedef struct LZWEncodeState {
51
    int clear_code;          ///< Value of clear code
52
    int end_code;            ///< Value of end code
53
    Code tab[LZW_HASH_SIZE]; ///< Hash table
54
    int tabsize;             ///< Number of values in hash table
55
    int bits;                ///< Actual bits code
56
    int bufsize;             ///< Size of output buffer
57
    PutBitContext pb;        ///< Put bit context for output
58
    int maxbits;             ///< Max bits code
59
    int maxcode;             ///< Max value of code
60
    int output_bytes;        ///< Number of written bytes
61
    int last_code;           ///< Value of last output code or LZW_PREFIX_EMPTY
62
    enum FF_LZW_MODES mode;  ///< TIFF or GIF
63
    void (*put_bits)(PutBitContext *, int, unsigned); ///< GIF is LE while TIFF is BE
64
}LZWEncodeState;
65
66
67
const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);
68
69
/**
70
 * Hash function adding character
71
 * @param head LZW code for prefix
72
 * @param add Character to add
73
 * @return New hash value
74
 */
75
5529886
static inline int hash(int head, const int add)
76
{
77
5529886
    head ^= (add << LZW_HASH_SHIFT);
78
5529886
    if (head >= LZW_HASH_SIZE)
79
        head -= LZW_HASH_SIZE;
80
    av_assert2(head >= 0 && head < LZW_HASH_SIZE);
81
5529886
    return head;
82
}
83
84
/**
85
 * Hash function calculates next hash value
86
 * @param head Actual hash code
87
 * @param offset Offset calculated by hashOffset
88
 * @return New hash value
89
 */
90
1409932
static inline int hashNext(int head, const int offset)
91
{
92
1409932
    head -= offset;
93
1409932
    if(head < 0)
94
1118268
        head += LZW_HASH_SIZE;
95
1409932
    return head;
96
}
97
98
/**
99
 * Hash function calculates hash offset
100
 * @param head Actual hash code
101
 * @return Hash offset
102
 */
103
3541685
static inline int hashOffset(const int head)
104
{
105
3541685
    return head ? LZW_HASH_SIZE - head : 1;
106
}
107
108
/**
109
 * Write one code to stream
110
 * @param s LZW state
111
 * @param c code to write
112
 */
113
1630012
static inline void writeCode(LZWEncodeState * s, int c)
114
{
115
    av_assert2(0 <= c && c < 1 << s->bits);
116
1630012
    s->put_bits(&s->pb, s->bits, c);
117
1630012
}
118
119
120
/**
121
 * Find LZW code for block
122
 * @param s LZW state
123
 * @param c Last character in block
124
 * @param hash_prefix LZW code for prefix
125
 * @return LZW code for block or -1 if not found in table
126
 */
127
3541685
static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
128
{
129
3541685
    int h = hash(FFMAX(hash_prefix, 0), c);
130
3541685
    int hash_offset = hashOffset(h);
131
132
4951617
    while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
133
3325144
        if ((s->tab[h].suffix == c)
134
1965850
            && (s->tab[h].hash_prefix == hash_prefix))
135
1915212
            return h;
136
1409932
        h = hashNext(h, hash_offset);
137
    }
138
139
1626473
    return h;
140
}
141
142
/**
143
 * Add block to LZW code table
144
 * @param s LZW state
145
 * @param c Last character in block
146
 * @param hash_prefix LZW code for prefix
147
 * @param hash_code LZW code for bytes block
148
 */
149
1626473
static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
150
{
151
1626473
    s->tab[hash_code].code = s->tabsize;
152
1626473
    s->tab[hash_code].suffix = c;
153
1626473
    s->tab[hash_code].hash_prefix = hash_prefix;
154
155
1626473
    s->tabsize++;
156
157
1626473
    if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
158
1324
        s->bits++;
159
1626473
}
160
161
/**
162
 * Clear LZW code table
163
 * @param s LZW state
164
 */
165
1413
static void clearTable(LZWEncodeState * s)
166
{
167
    int i, h;
168
169
1413
    writeCode(s, s->clear_code);
170
1413
    s->bits = 9;
171
23190156
    for (i = 0; i < LZW_HASH_SIZE; i++) {
172
23188743
        s->tab[i].hash_prefix = LZW_PREFIX_FREE;
173
    }
174
363141
    for (i = 0; i < 256; i++) {
175
361728
        h = hash(0, i);
176
361728
        s->tab[h].code = i;
177
361728
        s->tab[h].suffix = i;
178
361728
        s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
179
    }
180
1413
    s->tabsize = 258;
181
1413
}
182
183
/**
184
 * Calculate number of bytes written
185
 * @param s LZW encode state
186
 * @return Number of bytes written
187
 */
188
35140
static int writtenBytes(LZWEncodeState *s){
189
35140
    int ret = put_bits_count(&s->pb) >> 3;
190
35140
    ret -= s->output_bytes;
191
35140
    s->output_bytes += ret;
192
35140
    return ret;
193
}
194
195
/**
196
 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
197
 * @param s LZW state
198
 * @param outbuf Output buffer
199
 * @param outsize Size of output buffer
200
 * @param maxbits Maximum length of code
201
 */
202
1063
void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,
203
                        int maxbits, enum FF_LZW_MODES mode,
204
                        void (*lzw_put_bits)(PutBitContext *, int, unsigned))
205
{
206
1063
    s->clear_code = 256;
207
1063
    s->end_code = 257;
208
1063
    s->maxbits = maxbits;
209
1063
    init_put_bits(&s->pb, outbuf, outsize);
210
1063
    s->bufsize = outsize;
211

1063
    av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
212
1063
    s->maxcode = 1 << s->maxbits;
213
1063
    s->output_bytes = 0;
214
1063
    s->last_code = LZW_PREFIX_EMPTY;
215
1063
    s->bits = 9;
216
1063
    s->mode = mode;
217
1063
    s->put_bits = lzw_put_bits;
218
1063
}
219
220
/**
221
 * LZW main compress function
222
 * @param s LZW state
223
 * @param inbuf Input buffer
224
 * @param insize Size of input buffer
225
 * @return Number of bytes written or -1 on error
226
 */
227
34077
int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
228
{
229
    int i;
230
231
34077
    if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
232
        return -1;
233
    }
234
235
34077
    if (s->last_code == LZW_PREFIX_EMPTY)
236
1063
        clearTable(s);
237
238
3575762
    for (i = 0; i < insize; i++) {
239
3541685
        uint8_t c = *inbuf++;
240
3541685
        int code = findCode(s, c, s->last_code);
241
3541685
        if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
242
1626473
            writeCode(s, s->last_code);
243
1626473
            addCode(s, c, s->last_code, code);
244
1626473
            code= hash(0, c);
245
        }
246
3541685
        s->last_code = s->tab[code].code;
247
3541685
        if (s->tabsize >= s->maxcode - 1) {
248
350
            clearTable(s);
249
        }
250
    }
251
252
34077
    return writtenBytes(s);
253
}
254
255
/**
256
 * Write end code and flush bitstream
257
 * @param s LZW state
258
 * @return Number of bytes written or -1 on error
259
 */
260
1063
int ff_lzw_encode_flush(LZWEncodeState *s,
261
                        void (*lzw_flush_put_bits)(PutBitContext *))
262
{
263
1063
    if (s->last_code != -1)
264
1063
        writeCode(s, s->last_code);
265
1063
    writeCode(s, s->end_code);
266
1063
    if (s->mode == FF_LZW_GIF)
267
1063
        s->put_bits(&s->pb, 1, 0);
268
269
1063
    lzw_flush_put_bits(&s->pb);
270
1063
    s->last_code = -1;
271
272
1063
    return writtenBytes(s);
273
}