Pillow

1
/*
2
 * The Python Imaging Library.
3
 * $Id$
4
 *
5
 * encoder for uncompressed GIF data
6
 *
7
 * history:
8
 * 97-01-05 fl created (writes uncompressed data)
9
 * 97-08-27 fl fixed off-by-one error in buffer size test
10
 * 98-07-09 fl added interlace write support
11
 * 99-02-07 fl rewritten, now uses a run-length encoding strategy
12
 * 99-02-08 fl improved run-length encoding for long runs
13
 * 2020-12-12 rdg Reworked for LZW compression.
14
 *
15
 * Copyright (c) Secret Labs AB 1997-99.
16
 * Copyright (c) Fredrik Lundh 1997.
17
 *
18
 * See the README file for information on usage and redistribution.
19
 */
20

21
#include "Imaging.h"
22

23
#include "Gif.h"
24

25
enum { INIT, ENCODE, FINISH };
26

27
/* GIF LZW encoder by Raymond Gardner. */
28
/* Released here under PIL license. */
29

30
/* This LZW encoder conforms to the GIF LZW format specified in the original
31
 * Compuserve GIF 87a and GIF 89a specifications (see e.g.
32
 * https://www.w3.org/Graphics/GIF/spec-gif87.txt Appendix C and
33
 * https://www.w3.org/Graphics/GIF/spec-gif89a.txt Appendix F).
34
 */
35

36
/* Return values */
37
#define GLZW_OK 0
38
#define GLZW_NO_INPUT_AVAIL 1
39
#define GLZW_NO_OUTPUT_AVAIL 2
40
#define GLZW_INTERNAL_ERROR 3
41

42
#define CODE_LIMIT 4096
43

44
/* Values of entry_state */
45
enum {
46
    LZW_INITIAL,
47
    LZW_TRY_IN1,
48
    LZW_TRY_IN2,
49
    LZW_TRY_OUT1,
50
    LZW_TRY_OUT2,
51
    LZW_FINISHED
52
};
53

54
/* Values of control_state */
55
enum { PUT_HEAD, PUT_INIT_CLEAR, PUT_CLEAR, PUT_LAST_HEAD, PUT_END };
56

57
static void
58
glzwe_reset(GIFENCODERSTATE *st) {
59
    st->next_code = st->end_code + 1;
60
    st->max_code = 2 * st->clear_code - 1;
61
    st->code_width = st->bits + 1;
62
    memset(st->codes, 0, sizeof(st->codes));
63
}
64

65
static void
66
glzwe_init(GIFENCODERSTATE *st) {
67
    st->clear_code = 1 << st->bits;
68
    st->end_code = st->clear_code + 1;
69
    glzwe_reset(st);
70
    st->entry_state = LZW_INITIAL;
71
    st->buf_bits_left = 8;
72
    st->code_buffer = 0;
73
}
74

75
static int
76
glzwe(
77
    GIFENCODERSTATE *st,
78
    const UINT8 *in_ptr,
79
    UINT8 *out_ptr,
80
    UINT32 *in_avail,
81
    UINT32 *out_avail,
82
    UINT32 end_of_data
83
) {
84
    switch (st->entry_state) {
85
        case LZW_TRY_IN1:
86
get_first_byte:
87
            if (!*in_avail) {
88
                if (end_of_data) {
89
                    goto end_of_data;
90
                }
91
                st->entry_state = LZW_TRY_IN1;
92
                return GLZW_NO_INPUT_AVAIL;
93
            }
94
            st->head = *in_ptr++;
95
            (*in_avail)--;
96

97
        case LZW_TRY_IN2:
98
encode_loop:
99
            if (!*in_avail) {
100
                if (end_of_data) {
101
                    st->code = st->head;
102
                    st->put_state = PUT_LAST_HEAD;
103
                    goto put_code;
104
                }
105
                st->entry_state = LZW_TRY_IN2;
106
                return GLZW_NO_INPUT_AVAIL;
107
            }
108
            st->tail = *in_ptr++;
109
            (*in_avail)--;
110

111
            /* Knuth TAOCP vol 3 sec. 6.4 algorithm D. */
112
            /* Hash found experimentally to be pretty good. */
113
            /* This works ONLY with TABLE_SIZE a power of 2. */
114
            st->probe = ((st->head ^ (st->tail << 6)) * 31) & (TABLE_SIZE - 1);
115
            while (st->codes[st->probe]) {
116
                if ((st->codes[st->probe] & 0xFFFFF) == ((st->head << 8) | st->tail)) {
117
                    st->head = st->codes[st->probe] >> 20;
118
                    goto encode_loop;
119
                } else {
120
                    // Reprobe decrement must be non-zero and relatively prime to table
121
                    // size. So, any odd positive number for power-of-2 size.
122
                    if ((st->probe -= ((st->tail << 2) | 1)) < 0) {
123
                        st->probe += TABLE_SIZE;
124
                    }
125
                }
126
            }
127
            /* Key not found, probe is at empty slot. */
128
            st->code = st->head;
129
            st->put_state = PUT_HEAD;
130
            goto put_code;
131
insert_code_or_clear: /* jump here after put_code */
132
            if (st->next_code < CODE_LIMIT) {
133
                st->codes[st->probe] =
134
                    (st->next_code << 20) | (st->head << 8) | st->tail;
135
                if (st->next_code > st->max_code) {
136
                    st->max_code = st->max_code * 2 + 1;
137
                    st->code_width++;
138
                }
139
                st->next_code++;
140
            } else {
141
                st->code = st->clear_code;
142
                st->put_state = PUT_CLEAR;
143
                goto put_code;
144
reset_after_clear: /* jump here after put_code */
145
                glzwe_reset(st);
146
            }
147
            st->head = st->tail;
148
            goto encode_loop;
149

150
        case LZW_INITIAL:
151
            glzwe_reset(st);
152
            st->code = st->clear_code;
153
            st->put_state = PUT_INIT_CLEAR;
154
put_code:
155
            st->code_bits_left = st->code_width;
156
check_buf_bits:
157
            if (!st->buf_bits_left) { /* out buffer full */
158

159
                case LZW_TRY_OUT1:
160
                    if (!*out_avail) {
161
                        st->entry_state = LZW_TRY_OUT1;
162
                        return GLZW_NO_OUTPUT_AVAIL;
163
                    }
164
                    *out_ptr++ = st->code_buffer;
165
                    (*out_avail)--;
166
                    st->code_buffer = 0;
167
                    st->buf_bits_left = 8;
168
            }
169
            /* code bits to pack */
170
            UINT32 n = st->buf_bits_left < st->code_bits_left ? st->buf_bits_left
171
                                                              : st->code_bits_left;
172
            st->code_buffer |= (st->code & ((1 << n) - 1)) << (8 - st->buf_bits_left);
173
            st->code >>= n;
174
            st->buf_bits_left -= n;
175
            st->code_bits_left -= n;
176
            if (st->code_bits_left) {
177
                goto check_buf_bits;
178
            }
179
            switch (st->put_state) {
180
                case PUT_INIT_CLEAR:
181
                    goto get_first_byte;
182
                case PUT_HEAD:
183
                    goto insert_code_or_clear;
184
                case PUT_CLEAR:
185
                    goto reset_after_clear;
186
                case PUT_LAST_HEAD:
187
                    goto end_of_data;
188
                case PUT_END:
189
                    goto flush_code_buffer;
190
                default:
191
                    return GLZW_INTERNAL_ERROR;
192
            }
193

194
end_of_data:
195
            st->code = st->end_code;
196
            st->put_state = PUT_END;
197
            goto put_code;
198
flush_code_buffer: /* jump here after put_code */
199
            if (st->buf_bits_left < 8) {
200
                case LZW_TRY_OUT2:
201
                    if (!*out_avail) {
202
                        st->entry_state = LZW_TRY_OUT2;
203
                        return GLZW_NO_OUTPUT_AVAIL;
204
                    }
205
                    *out_ptr++ = st->code_buffer;
206
                    (*out_avail)--;
207
            }
208
            st->entry_state = LZW_FINISHED;
209
            return GLZW_OK;
210

211
        case LZW_FINISHED:
212
            return GLZW_OK;
213

214
        default:
215
            return GLZW_INTERNAL_ERROR;
216
    }
217
}
218
/* -END- GIF LZW encoder. */
219

220
int
221
ImagingGifEncode(Imaging im, ImagingCodecState state, UINT8 *buf, int bytes) {
222
    UINT8 *ptr;
223
    UINT8 *sub_block_ptr;
224
    UINT8 *sub_block_limit;
225
    UINT8 *buf_limit;
226
    GIFENCODERSTATE *context = (GIFENCODERSTATE *)state->context;
227
    int r;
228

229
    UINT32 in_avail, in_used;
230
    UINT32 out_avail, out_used;
231

232
    if (state->state == INIT) {
233
        state->state = ENCODE;
234
        glzwe_init(context);
235

236
        if (context->interlace) {
237
            context->interlace = 1;
238
            context->step = 8;
239
        } else {
240
            context->step = 1;
241
        }
242

243
        /* Need at least 2 bytes for data sub-block; 5 for empty image */
244
        if (bytes < 5) {
245
            state->errcode = IMAGING_CODEC_CONFIG;
246
            return 0;
247
        }
248
        /* sanity check */
249
        if (state->xsize <= 0 || state->ysize <= 0) {
250
            /* Is this better than an error return? */
251
            /* This will handle any legal "LZW Minimum Code Size" */
252
            memset(buf, 0, 5);
253
            in_avail = 0;
254
            out_avail = 5;
255
            r = glzwe(context, (const UINT8 *)"", buf + 1, &in_avail, &out_avail, 1);
256
            if (r == GLZW_OK) {
257
                r = 5 - out_avail;
258
                if (r < 1 || r > 3) {
259
                    state->errcode = IMAGING_CODEC_BROKEN;
260
                    return 0;
261
                }
262
                buf[0] = r;
263
                state->errcode = IMAGING_CODEC_END;
264
                return r + 2;
265
            } else {
266
                /* Should not be possible unless something external to this
267
                 * routine messes with our state data */
268
                state->errcode = IMAGING_CODEC_BROKEN;
269
                return 0;
270
            }
271
        }
272
        /* Init state->x to make if() below true the first time through. */
273
        state->x = state->xsize;
274
    }
275

276
    buf_limit = buf + bytes;
277
    sub_block_limit = sub_block_ptr = ptr = buf;
278

279
    /* On entry, buf is output buffer, bytes is space available in buf.
280
     * Loop here getting input until buf is full or image is all encoded. */
281
    for (;;) {
282
        /* Set up sub-block ptr and limit. sub_block_ptr stays at beginning
283
         * of sub-block until it is full. ptr will advance when any data is
284
         * placed in buf.
285
         */
286
        if (ptr >= sub_block_limit) {
287
            if (buf_limit - ptr < 2) { /* Need at least 2 for data sub-block */
288
                return ptr - buf;
289
            }
290
            sub_block_ptr = ptr;
291
            sub_block_limit =
292
                sub_block_ptr +
293
                (256 < buf_limit - sub_block_ptr ? 256 : buf_limit - sub_block_ptr);
294
            *ptr++ = 0;
295
        }
296

297
        /* Get next row of pixels. */
298
        /* This if() originally tested state->x==0 for the first time through.
299
         * This no longer works, as the loop will not advance state->x if
300
         * glzwe() does not consume any input; this would advance the row
301
         * spuriously.  Now pre-init state->x above for first time, and avoid
302
         * entering if() when state->state is FINISH, or it will loop
303
         * infinitely.
304
         */
305
        if (state->x >= state->xsize && state->state == ENCODE) {
306
            if (!context->interlace && state->y >= state->ysize) {
307
                state->state = FINISH;
308
                continue;
309
            }
310

311
            /* get another line of data */
312
            state->shuffle(
313
                state->buffer,
314
                (UINT8 *)im->image[state->y + state->yoff] +
315
                    state->xoff * im->pixelsize,
316
                state->xsize
317
            );
318
            state->x = 0;
319

320
            /* step forward, according to the interlace settings */
321
            state->y += context->step;
322
            while (context->interlace && state->y >= state->ysize) {
323
                switch (context->interlace) {
324
                    case 1:
325
                        state->y = 4;
326
                        context->interlace = 2;
327
                        break;
328
                    case 2:
329
                        context->step = 4;
330
                        state->y = 2;
331
                        context->interlace = 3;
332
                        break;
333
                    case 3:
334
                        context->step = 2;
335
                        state->y = 1;
336
                        context->interlace = 0;
337
                        break;
338
                    default:
339
                        /* just make sure we don't loop forever */
340
                        context->interlace = 0;
341
                }
342
            }
343
        }
344

345
        in_avail = state->xsize - state->x; /* bytes left in line */
346
        out_avail = sub_block_limit - ptr;  /* bytes left in sub-block */
347
        r = glzwe(
348
            context,
349
            &state->buffer[state->x],
350
            ptr,
351
            &in_avail,
352
            &out_avail,
353
            state->state == FINISH
354
        );
355
        out_used = sub_block_limit - ptr - out_avail;
356
        *sub_block_ptr += out_used;
357
        ptr += out_used;
358
        in_used = state->xsize - state->x - in_avail;
359
        state->x += in_used;
360

361
        if (r == GLZW_OK) {
362
            /* Should not be possible when end-of-data flag is false. */
363
            state->errcode = IMAGING_CODEC_END;
364
            return ptr - buf;
365
        } else if (r == GLZW_NO_INPUT_AVAIL) {
366
            /* Used all the input line; get another line */
367
            continue;
368
        } else if (r == GLZW_NO_OUTPUT_AVAIL) {
369
            /* subblock is full */
370
            continue;
371
        } else {
372
            /* Should not be possible unless something external to this
373
             * routine messes with our state data */
374
            state->errcode = IMAGING_CODEC_BROKEN;
375
            return 0;
376
        }
377
    }
378
}
379