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 libavcodec/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 */
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}LZWEncodeState;
62
63
64const 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 */
72static 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 */
87static 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 */
100static 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 */
110static 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 */
124static 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 */
146static 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 */
162static 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 */
185static 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 */
199void 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 */
220int 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 */
253int 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}
263