← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/xvidcap/jaunty-proposed

« back to all changes in this revision

Viewing changes to ffmpeg/libavcodec/lzwenc.c

  • Committer: Bazaar Package Importer
  • Author(s): Lionel Le Folgoc, Andrew Starr-Bochicchio, Lionel Le Folgoc
  • Date: 2008-12-26 00:10:06 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20081226001006-2040ls9680bd1blt
Tags: 1.1.7-0.2ubuntu1
https://launchpad.net/bugs/298547
https://launchpad.net/bugs/311412
[ Andrew Starr-Bochicchio ]
* Merge from debian-multimedia (LP: #298547), Ubuntu Changes:
 - For ffmpeg-related build-deps, fix versionized dependencies
   as the ubuntu versioning is different than debian-multimedia's.

[ Lionel Le Folgoc ]
* LP: #311412 is fixed since the 1.1.7~rc1-0.1 revision.
* debian/patches/03_ffmpeg.diff: updated to fix FTBFS due to libswscale API
  change (cherry-pick from Gentoo #234383).

Show diffs side-by-side

added added

removed removed

Lines of Context:
ffmpeg/libavcodec/lzwenc.c
 
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
 * LZW encoder
 
24
 * @file lzwenc.c
 
25
 * @author Bartlomiej Wolowiec
 
26
 */
 
27
 
 
28
#include "avcodec.h"
 
29
#include "bitstream.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
}LZWEncodeState;
 
62
 
 
63
 
 
64
const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);
 
65
 
 
66
/**
 
67
 * Hash function adding character
 
68
 * @param head LZW code for prefix
 
69
 * @param add Character to add
 
70
 * @return New hash value
 
71
 */
 
72
static inline int hash(int head, const int add)
 
73
{
 
74
    head ^= (add << LZW_HASH_SHIFT);
 
75
    if (head >= LZW_HASH_SIZE)
 
76
        head -= LZW_HASH_SIZE;
 
77
    assert(head >= 0 && head < LZW_HASH_SIZE);
 
78
    return head;
 
79
}
 
80
 
 
81
/**
 
82
 * Hash function calculates next hash value
 
83
 * @param head Actual hash code
 
84
 * @param offset Offset calculated by hashOffset
 
85
 * @return New hash value
 
86
 */
 
87
static inline int hashNext(int head, const int offset)
 
88
{
 
89
    head -= offset;
 
90
    if(head < 0)
 
91
        head += LZW_HASH_SIZE;
 
92
    return head;
 
93
}
 
94
 
 
95
/**
 
96
 * Hash function calculates hash offset
 
97
 * @param head Actual hash code
 
98
 * @return Hash offset
 
99
 */
 
100
static inline int hashOffset(const int head)
 
101
{
 
102
    return head ? LZW_HASH_SIZE - head : 1;
 
103
}
 
104
 
 
105
/**
 
106
 * Write one code to stream
 
107
 * @param s LZW state
 
108
 * @param c code to write
 
109
 */
 
110
static inline void writeCode(LZWEncodeState * s, int c)
 
111
{
 
112
    assert(0 <= c && c < 1 << s->bits);
 
113
    put_bits(&s->pb, s->bits, c);
 
114
}
 
115
 
 
116
 
 
117
/**
 
118
 * Find LZW code for block
 
119
 * @param s LZW state
 
120
 * @param c Last character in block
 
121
 * @param hash_prefix LZW code for prefix
 
122
 * @return LZW code for block or -1 if not found in table
 
123
 */
 
124
static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
 
125
{
 
126
    int h = hash(FFMAX(hash_prefix, 0), c);
 
127
    int hash_offset = hashOffset(h);
 
128
 
 
129
    while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
 
130
        if ((s->tab[h].suffix == c)
 
131
            && (s->tab[h].hash_prefix == hash_prefix))
 
132
            return h;
 
133
        h = hashNext(h, hash_offset);
 
134
    }
 
135
 
 
136
    return h;
 
137
}
 
138
 
 
139
/**
 
140
 * Add block to LZW code table
 
141
 * @param s LZW state
 
142
 * @param c Last character in block
 
143
 * @param hash_prefix LZW code for prefix
 
144
 * @param hash_code LZW code for bytes block
 
145
 */
 
146
static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
 
147
{
 
148
    s->tab[hash_code].code = s->tabsize;
 
149
    s->tab[hash_code].suffix = c;
 
150
    s->tab[hash_code].hash_prefix = hash_prefix;
 
151
 
 
152
    s->tabsize++;
 
153
 
 
154
    if (s->tabsize >= 1 << s->bits)
 
155
        s->bits++;
 
156
}
 
157
 
 
158
/**
 
159
 * Clear LZW code table
 
160
 * @param s LZW state
 
161
 */
 
162
static void clearTable(LZWEncodeState * s)
 
163
{
 
164
    int i, h;
 
165
 
 
166
    writeCode(s, s->clear_code);
 
167
    s->bits = 9;
 
168
    for (i = 0; i < LZW_HASH_SIZE; i++) {
 
169
        s->tab[i].hash_prefix = LZW_PREFIX_FREE;
 
170
    }
 
171
    for (i = 0; i < 256; i++) {
 
172
        h = hash(0, i);
 
173
        s->tab[h].code = i;
 
174
        s->tab[h].suffix = i;
 
175
        s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
 
176
    }
 
177
    s->tabsize = 258;
 
178
}
 
179
 
 
180
/**
 
181
 * Calculate number of bytes written
 
182
 * @param s LZW encode state
 
183
 * @return Number of bytes written
 
184
 */
 
185
static int writtenBytes(LZWEncodeState *s){
 
186
    int ret = put_bits_count(&s->pb) >> 3;
 
187
    ret -= s->output_bytes;
 
188
    s->output_bytes += ret;
 
189
    return ret;
 
190
}
 
191
 
 
192
/**
 
193
 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
 
194
 * @param s LZW state
 
195
 * @param outbuf Output buffer
 
196
 * @param outsize Size of output buffer
 
197
 * @param maxbits Maximum length of code
 
198
 */
 
199
void ff_lzw_encode_init(LZWEncodeState * s, uint8_t * outbuf, int outsize, int maxbits)
 
200
{
 
201
    s->clear_code = 256;
 
202
    s->end_code = 257;
 
203
    s->maxbits = maxbits;
 
204
    init_put_bits(&s->pb, outbuf, outsize);
 
205
    s->bufsize = outsize;
 
206
    assert(9 <= s->maxbits && s->maxbits <= s->maxbits);
 
207
    s->maxcode = 1 << s->maxbits;
 
208
    s->output_bytes = 0;
 
209
    s->last_code = LZW_PREFIX_EMPTY;
 
210
    s->bits = 9;
 
211
}
 
212
 
 
213
/**
 
214
 * LZW main compress function
 
215
 * @param s LZW state
 
216
 * @param inbuf Input buffer
 
217
 * @param insize Size of input buffer
 
218
 * @return Number of bytes written or -1 on error
 
219
 */
 
220
int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
 
221
{
 
222
    int i;
 
223
 
 
224
    if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
 
225
        return -1;
 
226
    }
 
227
 
 
228
    if (s->last_code == LZW_PREFIX_EMPTY)
 
229
        clearTable(s);
 
230
 
 
231
    for (i = 0; i < insize; i++) {
 
232
        uint8_t c = *inbuf++;
 
233
        int code = findCode(s, c, s->last_code);
 
234
        if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
 
235
            writeCode(s, s->last_code);
 
236
            addCode(s, c, s->last_code, code);
 
237
            code= hash(0, c);
 
238
        }
 
239
        s->last_code = s->tab[code].code;
 
240
        if (s->tabsize >= s->maxcode - 1) {
 
241
            clearTable(s);
 
242
        }
 
243
    }
 
244
 
 
245
    return writtenBytes(s);
 
246
}
 
247
 
 
248
/**
 
249
 * Write end code and flush bitstream
 
250
 * @param s LZW state
 
251
 * @return Number of bytes written or -1 on error
 
252
 */
 
253
int ff_lzw_encode_flush(LZWEncodeState * s)
 
254
{
 
255
    if (s->last_code != -1)
 
256
        writeCode(s, s->last_code);
 
257
    writeCode(s, s->end_code);
 
258
    flush_put_bits(&s->pb);
 
259
    s->last_code = -1;
 
260
 
 
261
    return writtenBytes(s);
 
262
}