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 * @author modified for use in TIFF by Konstantin Shishkov 28 */ 29 30#include "libavutil/attributes.h" 31#include "bytestream.h" 32#include "lzw.h" 33#include "libavutil/mem.h" 34 35#define LZW_MAXBITS 12 36#define LZW_SIZTABLE (1<<LZW_MAXBITS) 37 38static const uint16_t mask[17] = 39{ 40 0x0000, 0x0001, 0x0003, 0x0007, 41 0x000F, 0x001F, 0x003F, 0x007F, 42 0x00FF, 0x01FF, 0x03FF, 0x07FF, 43 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF 44}; 45 46struct LZWState { 47 GetByteContext gb; 48 int bbits; 49 unsigned int bbuf; 50 51 int mode; ///< Decoder mode 52 int cursize; ///< The current code size 53 int curmask; 54 int codesize; 55 int clear_code; 56 int end_code; 57 int newcodes; ///< First available code 58 int top_slot; ///< Highest code for current size 59 int extra_slot; 60 int slot; ///< Last read code 61 int fc, oc; 62 uint8_t *sp; 63 uint8_t stack[LZW_SIZTABLE]; 64 uint8_t suffix[LZW_SIZTABLE]; 65 uint16_t prefix[LZW_SIZTABLE]; 66 int bs; ///< current buffer size for GIF 67}; 68 69/* get one code from stream */ 70static int lzw_get_code(struct LZWState * s) 71{ 72 int c; 73 74 if (s->bbits < s->cursize && bytestream2_get_bytes_left(&s->gb) <= 0) 75 return s->end_code; 76 77 if(s->mode == FF_LZW_GIF) { 78 while (s->bbits < s->cursize) { 79 if (!s->bs) { 80 s->bs = bytestream2_get_byte(&s->gb); 81 } 82 s->bbuf |= bytestream2_get_byte(&s->gb) << s->bbits; 83 s->bbits += 8; 84 s->bs--; 85 } 86 c = s->bbuf; 87 s->bbuf >>= s->cursize; 88 } else { // TIFF 89 while (s->bbits < s->cursize) { 90 s->bbuf = (s->bbuf << 8) | bytestream2_get_byte(&s->gb); 91 s->bbits += 8; 92 } 93 c = s->bbuf >> (s->bbits - s->cursize); 94 } 95 s->bbits -= s->cursize; 96 return c & s->curmask; 97} 98 99int 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->bs > 0 && bytestream2_get_bytes_left(&s->gb)) { 105 bytestream2_skip(&s->gb, s->bs); 106 s->bs = bytestream2_get_byte(&s->gb); 107 } 108 }else 109 bytestream2_skip(&s->gb, bytestream2_get_bytes_left(&s->gb)); 110 return bytestream2_tell(&s->gb); 111} 112 113av_cold void ff_lzw_decode_open(LZWState **p) 114{ 115 *p = av_mallocz(sizeof(struct LZWState)); 116} 117 118av_cold void ff_lzw_decode_close(LZWState **p) 119{ 120 av_freep(p); 121} 122 123/** 124 * Initialize LZW decoder 125 * @param p LZW context 126 * @param csize initial code size in bits 127 * @param buf input data 128 * @param buf_size input data size 129 * @param mode decoder working mode - either GIF or TIFF 130 */ 131int ff_lzw_decode_init(LZWState *p, int csize, const uint8_t *buf, int buf_size, int mode) 132{ 133 struct LZWState *s = (struct LZWState *)p; 134 135 if(csize < 1 || csize >= LZW_MAXBITS) 136 return -1; 137 /* read buffer */ 138 bytestream2_init(&s->gb, buf, 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 p 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