1/* 2 * LZW decoder 3 * Copyright (c) 2003 Fabrice Bellard 4 * Copyright (c) 2006 Konstantin Shishkov 5 * 6 * This file is part of FFmpeg. 7 * 8 * FFmpeg is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * FFmpeg is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with FFmpeg; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 */ 22 23/** 24 * @file 25 * @brief LZW decoding routines 26 * @author Fabrice Bellard 27 * Modified for use in TIFF by Konstantin Shishkov 28 */ 29 30#include "avcodec.h" 31#include "lzw.h" 32 33#define LZW_MAXBITS 12 34#define LZW_SIZTABLE (1<<LZW_MAXBITS) 35 36static const uint16_t mask[17] = 37{ 38 0x0000, 0x0001, 0x0003, 0x0007, 39 0x000F, 0x001F, 0x003F, 0x007F, 40 0x00FF, 0x01FF, 0x03FF, 0x07FF, 41 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF 42}; 43 44struct LZWState { 45 const uint8_t *pbuf, *ebuf; 46 int bbits; 47 unsigned int bbuf; 48 49 int mode; ///< Decoder mode 50 int cursize; ///< The current code size 51 int curmask; 52 int codesize; 53 int clear_code; 54 int end_code; 55 int newcodes; ///< First available code 56 int top_slot; ///< Highest code for current size 57 int extra_slot; 58 int slot; ///< Last read code 59 int fc, oc; 60 uint8_t *sp; 61 uint8_t stack[LZW_SIZTABLE]; 62 uint8_t suffix[LZW_SIZTABLE]; 63 uint16_t prefix[LZW_SIZTABLE]; 64 int bs; ///< current buffer size for GIF 65}; 66 67/* get one code from stream */ 68static int lzw_get_code(struct LZWState * s) 69{ 70 int c; 71 72 if(s->mode == FF_LZW_GIF) { 73 while (s->bbits < s->cursize) { 74 if (!s->bs) { 75 s->bs = *s->pbuf++; 76 } 77 s->bbuf |= (*s->pbuf++) << s->bbits; 78 s->bbits += 8; 79 s->bs--; 80 } 81 c = s->bbuf; 82 s->bbuf >>= s->cursize; 83 } else { // TIFF 84 while (s->bbits < s->cursize) { 85 s->bbuf = (s->bbuf << 8) | (*s->pbuf++); 86 s->bbits += 8; 87 } 88 c = s->bbuf >> (s->bbits - s->cursize); 89 } 90 s->bbits -= s->cursize; 91 return c & s->curmask; 92} 93 94const uint8_t* ff_lzw_cur_ptr(LZWState *p) 95{ 96 return ((struct LZWState*)p)->pbuf; 97} 98 99void ff_lzw_decode_tail(LZWState *p) 100{ 101 struct LZWState *s = (struct LZWState *)p; 102 103 if(s->mode == FF_LZW_GIF) { 104 while(s->pbuf < s->ebuf && s->bs>0){ 105 s->pbuf += s->bs; 106 s->bs = *s->pbuf++; 107 } 108 }else 109 s->pbuf= s->ebuf; 110} 111 112av_cold void ff_lzw_decode_open(LZWState **p) 113{ 114 *p = av_mallocz(sizeof(struct LZWState)); 115} 116 117av_cold void ff_lzw_decode_close(LZWState **p) 118{ 119 av_freep(p); 120} 121 122/** 123 * Initialize LZW decoder 124 * @param s LZW context 125 * @param csize initial code size in bits 126 * @param buf input data 127 * @param buf_size input data size 128 * @param mode decoder working mode - either GIF or TIFF 129 */ 130int ff_lzw_decode_init(LZWState *p, int csize, const uint8_t *buf, int buf_size, int mode) 131{ 132 struct LZWState *s = (struct LZWState *)p; 133 134 if(csize < 1 || csize >= LZW_MAXBITS) 135 return -1; 136 /* read buffer */ 137 s->pbuf = buf; 138 s->ebuf = s->pbuf + buf_size; 139 s->bbuf = 0; 140 s->bbits = 0; 141 s->bs = 0; 142 143 /* decoder */ 144 s->codesize = csize; 145 s->cursize = s->codesize + 1; 146 s->curmask = mask[s->cursize]; 147 s->top_slot = 1 << s->cursize; 148 s->clear_code = 1 << s->codesize; 149 s->end_code = s->clear_code + 1; 150 s->slot = s->newcodes = s->clear_code + 2; 151 s->oc = s->fc = -1; 152 s->sp = s->stack; 153 154 s->mode = mode; 155 s->extra_slot = s->mode == FF_LZW_TIFF; 156 return 0; 157} 158 159/** 160 * Decode given number of bytes 161 * NOTE: the algorithm here is inspired from the LZW GIF decoder 162 * written by Steven A. Bennett in 1987. 163 * 164 * @param s LZW context 165 * @param buf output buffer 166 * @param len number of bytes to decode 167 * @return number of bytes decoded 168 */ 169int ff_lzw_decode(LZWState *p, uint8_t *buf, int len){ 170 int l, c, code, oc, fc; 171 uint8_t *sp; 172 struct LZWState *s = (struct LZWState *)p; 173 174 if (s->end_code < 0) 175 return 0; 176 177 l = len; 178 sp = s->sp; 179 oc = s->oc; 180 fc = s->fc; 181 182 for (;;) { 183 while (sp > s->stack) { 184 *buf++ = *(--sp); 185 if ((--l) == 0) 186 goto the_end; 187 } 188 c = lzw_get_code(s); 189 if (c == s->end_code) { 190 break; 191 } else if (c == s->clear_code) { 192 s->cursize = s->codesize + 1; 193 s->curmask = mask[s->cursize]; 194 s->slot = s->newcodes; 195 s->top_slot = 1 << s->cursize; 196 fc= oc= -1; 197 } else { 198 code = c; 199 if (code == s->slot && fc>=0) { 200 *sp++ = fc; 201 code = oc; 202 }else if(code >= s->slot) 203 break; 204 while (code >= s->newcodes) { 205 *sp++ = s->suffix[code]; 206 code = s->prefix[code]; 207 } 208 *sp++ = code; 209 if (s->slot < s->top_slot && oc>=0) { 210 s->suffix[s->slot] = code; 211 s->prefix[s->slot++] = oc; 212 } 213 fc = code; 214 oc = c; 215 if (s->slot >= s->top_slot - s->extra_slot) { 216 if (s->cursize < LZW_MAXBITS) { 217 s->top_slot <<= 1; 218 s->curmask = mask[++s->cursize]; 219 } 220 } 221 } 222 } 223 s->end_code = -1; 224 the_end: 225 s->sp = sp; 226 s->oc = oc; 227 s->fc = fc; 228 return len - l; 229} 230