lzw.c 5.96 KB
Newer Older
1 2
/*
 * LZW decoder
3 4
 * Copyright (c) 2003 Fabrice Bellard
 * Copyright (c) 2006 Konstantin Shishkov
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
 *
 * This file is part of FFmpeg.
 *
 * FFmpeg is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * FFmpeg is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with FFmpeg; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

/**
24
 * @file
25 26
 * @brief LZW decoding routines
 * @author Fabrice Bellard
27
 * @author modified for use in TIFF by Konstantin Shishkov
28 29 30
 */

#include "avcodec.h"
31
#include "bytestream.h"
32
#include "lzw.h"
33
#include "libavutil/mem.h"
34 35 36 37 38 39 40 41 42 43 44 45 46

#define LZW_MAXBITS                 12
#define LZW_SIZTABLE                (1<<LZW_MAXBITS)

static const uint16_t mask[17] =
{
    0x0000, 0x0001, 0x0003, 0x0007,
    0x000F, 0x001F, 0x003F, 0x007F,
    0x00FF, 0x01FF, 0x03FF, 0x07FF,
    0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF
};

struct LZWState {
47
    GetByteContext gb;
48 49 50 51 52 53 54 55 56 57 58
    int bbits;
    unsigned int bbuf;

    int mode;                   ///< Decoder mode
    int cursize;                ///< The current code size
    int curmask;
    int codesize;
    int clear_code;
    int end_code;
    int newcodes;               ///< First available code
    int top_slot;               ///< Highest code for current size
Michael Niedermayer's avatar
Michael Niedermayer committed
59
    int extra_slot;
60 61 62 63 64 65 66 67 68 69 70 71
    int slot;                   ///< Last read code
    int fc, oc;
    uint8_t *sp;
    uint8_t stack[LZW_SIZTABLE];
    uint8_t suffix[LZW_SIZTABLE];
    uint16_t prefix[LZW_SIZTABLE];
    int bs;                     ///< current buffer size for GIF
};

/* get one code from stream */
static int lzw_get_code(struct LZWState * s)
{
Michael Niedermayer's avatar
Michael Niedermayer committed
72
    int c;
73 74 75 76

    if(s->mode == FF_LZW_GIF) {
        while (s->bbits < s->cursize) {
            if (!s->bs) {
77
                s->bs = bytestream2_get_byte(&s->gb);
78
            }
79
            s->bbuf |= bytestream2_get_byte(&s->gb) << s->bbits;
80 81 82
            s->bbits += 8;
            s->bs--;
        }
Michael Niedermayer's avatar
Michael Niedermayer committed
83
        c = s->bbuf;
Baptiste Coudurier's avatar
Baptiste Coudurier committed
84
        s->bbuf >>= s->cursize;
85 86
    } else { // TIFF
        while (s->bbits < s->cursize) {
87
            s->bbuf = (s->bbuf << 8) | bytestream2_get_byte(&s->gb);
88 89
            s->bbits += 8;
        }
Michael Niedermayer's avatar
Michael Niedermayer committed
90
        c = s->bbuf >> (s->bbits - s->cursize);
91 92
    }
    s->bbits -= s->cursize;
Michael Niedermayer's avatar
Michael Niedermayer committed
93
    return c & s->curmask;
94 95 96 97 98
}

void ff_lzw_decode_tail(LZWState *p)
{
    struct LZWState *s = (struct LZWState *)p;
99 100

    if(s->mode == FF_LZW_GIF) {
101 102 103
        while (s->bs > 0 && bytestream2_get_bytes_left(&s->gb)) {
            bytestream2_skip(&s->gb, s->bs);
            s->bs = bytestream2_get_byte(&s->gb);
104 105
        }
    }else
106
        bytestream2_skip(&s->gb, bytestream2_get_bytes_left(&s->gb));
107 108
}

109
av_cold void ff_lzw_decode_open(LZWState **p)
110 111 112 113
{
    *p = av_mallocz(sizeof(struct LZWState));
}

114
av_cold void ff_lzw_decode_close(LZWState **p)
115 116 117 118 119 120
{
    av_freep(p);
}

/**
 * Initialize LZW decoder
121
 * @param p LZW context
122 123 124 125 126
 * @param csize initial code size in bits
 * @param buf input data
 * @param buf_size input data size
 * @param mode decoder working mode - either GIF or TIFF
 */
Michael Niedermayer's avatar
Michael Niedermayer committed
127
int ff_lzw_decode_init(LZWState *p, int csize, const uint8_t *buf, int buf_size, int mode)
128 129 130
{
    struct LZWState *s = (struct LZWState *)p;

131
    if(csize < 1 || csize >= LZW_MAXBITS)
132 133
        return -1;
    /* read buffer */
134
    bytestream2_init(&s->gb, buf, buf_size);
135 136 137 138 139 140 141 142 143 144 145 146
    s->bbuf = 0;
    s->bbits = 0;
    s->bs = 0;

    /* decoder */
    s->codesize = csize;
    s->cursize = s->codesize + 1;
    s->curmask = mask[s->cursize];
    s->top_slot = 1 << s->cursize;
    s->clear_code = 1 << s->codesize;
    s->end_code = s->clear_code + 1;
    s->slot = s->newcodes = s->clear_code + 2;
Michael Niedermayer's avatar
Michael Niedermayer committed
147
    s->oc = s->fc = -1;
148 149 150
    s->sp = s->stack;

    s->mode = mode;
Michael Niedermayer's avatar
Michael Niedermayer committed
151
    s->extra_slot = s->mode == FF_LZW_TIFF;
152 153 154 155 156 157 158 159
    return 0;
}

/**
 * Decode given number of bytes
 * NOTE: the algorithm here is inspired from the LZW GIF decoder
 *  written by Steven A. Bennett in 1987.
 *
160
 * @param p LZW context
161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
 * @param buf output buffer
 * @param len number of bytes to decode
 * @return number of bytes decoded
 */
int ff_lzw_decode(LZWState *p, uint8_t *buf, int len){
    int l, c, code, oc, fc;
    uint8_t *sp;
    struct LZWState *s = (struct LZWState *)p;

    if (s->end_code < 0)
        return 0;

    l = len;
    sp = s->sp;
    oc = s->oc;
    fc = s->fc;

    for (;;) {
Michael Niedermayer's avatar
Michael Niedermayer committed
179 180 181 182 183
        while (sp > s->stack) {
            *buf++ = *(--sp);
            if ((--l) == 0)
                goto the_end;
        }
184 185 186 187 188 189 190 191
        c = lzw_get_code(s);
        if (c == s->end_code) {
            break;
        } else if (c == s->clear_code) {
            s->cursize = s->codesize + 1;
            s->curmask = mask[s->cursize];
            s->slot = s->newcodes;
            s->top_slot = 1 << s->cursize;
Michael Niedermayer's avatar
Michael Niedermayer committed
192
            fc= oc= -1;
193 194
        } else {
            code = c;
195
            if (code == s->slot && fc>=0) {
196 197
                *sp++ = fc;
                code = oc;
198 199
            }else if(code >= s->slot)
                break;
200 201 202 203 204
            while (code >= s->newcodes) {
                *sp++ = s->suffix[code];
                code = s->prefix[code];
            }
            *sp++ = code;
Michael Niedermayer's avatar
Michael Niedermayer committed
205 206
            if (s->slot < s->top_slot && oc>=0) {
                s->suffix[s->slot] = code;
207 208
                s->prefix[s->slot++] = oc;
            }
Michael Niedermayer's avatar
Michael Niedermayer committed
209 210
            fc = code;
            oc = c;
Michael Niedermayer's avatar
Michael Niedermayer committed
211
            if (s->slot >= s->top_slot - s->extra_slot) {
212 213 214 215 216 217 218
                if (s->cursize < LZW_MAXBITS) {
                    s->top_slot <<= 1;
                    s->curmask = mask[++s->cursize];
                }
            }
        }
    }
219
    s->end_code = -1;
220 221 222 223 224 225
  the_end:
    s->sp = sp;
    s->oc = oc;
    s->fc = fc;
    return len - l;
}