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
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 */
41typedef 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 */
49typedef 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
66const 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 */
74static 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 */
89static 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 */
102static 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 */
112static 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 */
126static 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 */
148static 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 */
164static 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 */
187static 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 */
201void 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 */
226int 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 */
259int 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}
270