lzw.c 6 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44
 */

#include "avcodec.h"
#include "lzw.h"

#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 {
Michael Niedermayer's avatar
Michael Niedermayer committed
45
    const uint8_t *pbuf, *ebuf;
46 47 48 49 50 51 52 53 54 55 56
    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
57
    int extra_slot;
58 59 60 61 62 63 64 65 66 67 68 69
    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
70
    int c;
71 72 73 74

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

Michael Niedermayer's avatar
Michael Niedermayer committed
94
const uint8_t* ff_lzw_cur_ptr(LZWState *p)
95 96 97 98 99 100 101
{
    return ((struct LZWState*)p)->pbuf;
}

void ff_lzw_decode_tail(LZWState *p)
{
    struct LZWState *s = (struct LZWState *)p;
102 103

    if(s->mode == FF_LZW_GIF) {
104
        while (s->bs > 0) {
105
            if (s->bs >= s->ebuf - s->pbuf) {
106 107 108 109 110 111
                s->pbuf = s->ebuf;
                break;
            } else {
                s->pbuf += s->bs;
                s->bs = *s->pbuf++;
            }
112 113 114
        }
    }else
        s->pbuf= s->ebuf;
115 116
}

117
av_cold void ff_lzw_decode_open(LZWState **p)
118 119 120 121
{
    *p = av_mallocz(sizeof(struct LZWState));
}

122
av_cold void ff_lzw_decode_close(LZWState **p)
123 124 125 126 127 128
{
    av_freep(p);
}

/**
 * Initialize LZW decoder
129
 * @param p LZW context
130 131 132 133 134
 * @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
135
int ff_lzw_decode_init(LZWState *p, int csize, const uint8_t *buf, int buf_size, int mode)
136 137 138
{
    struct LZWState *s = (struct LZWState *)p;

139
    if(csize < 1 || csize >= LZW_MAXBITS)
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155
        return -1;
    /* read buffer */
    s->pbuf = buf;
    s->ebuf = s->pbuf + buf_size;
    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
156
    s->oc = s->fc = -1;
157 158 159
    s->sp = s->stack;

    s->mode = mode;
Michael Niedermayer's avatar
Michael Niedermayer committed
160
    s->extra_slot = s->mode == FF_LZW_TIFF;
161 162 163 164 165 166 167 168
    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.
 *
169
 * @param p LZW context
170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
 * @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
188 189 190 191 192
        while (sp > s->stack) {
            *buf++ = *(--sp);
            if ((--l) == 0)
                goto the_end;
        }
193 194 195 196 197 198 199 200
        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
201
            fc= oc= -1;
202 203
        } else {
            code = c;
204
            if (code == s->slot && fc>=0) {
205 206
                *sp++ = fc;
                code = oc;
207 208
            }else if(code >= s->slot)
                break;
209 210 211 212 213
            while (code >= s->newcodes) {
                *sp++ = s->suffix[code];
                code = s->prefix[code];
            }
            *sp++ = code;
Michael Niedermayer's avatar
Michael Niedermayer committed
214 215
            if (s->slot < s->top_slot && oc>=0) {
                s->suffix[s->slot] = code;
216 217
                s->prefix[s->slot++] = oc;
            }
Michael Niedermayer's avatar
Michael Niedermayer committed
218 219
            fc = code;
            oc = c;
Michael Niedermayer's avatar
Michael Niedermayer committed
220
            if (s->slot >= s->top_slot - s->extra_slot) {
221 222 223 224 225 226 227
                if (s->cursize < LZW_MAXBITS) {
                    s->top_slot <<= 1;
                    s->curmask = mask[++s->cursize];
                }
            }
        }
    }
228
    s->end_code = -1;
229 230 231 232 233 234
  the_end:
    s->sp = sp;
    s->oc = oc;
    s->fc = fc;
    return len - l;
}