Libav
|
00001 /* 00002 * LZW encoder 00003 * Copyright (c) 2007 Bartlomiej Wolowiec 00004 * 00005 * This file is part of FFmpeg. 00006 * 00007 * FFmpeg is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU Lesser General Public 00009 * License as published by the Free Software Foundation; either 00010 * version 2.1 of the License, or (at your option) any later version. 00011 * 00012 * FFmpeg is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 * Lesser General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU Lesser General Public 00018 * License along with FFmpeg; if not, write to the Free Software 00019 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00020 */ 00021 00028 #include "avcodec.h" 00029 #include "put_bits.h" 00030 #include "lzw.h" 00031 00032 #define LZW_MAXBITS 12 00033 #define LZW_SIZTABLE (1<<LZW_MAXBITS) 00034 #define LZW_HASH_SIZE 16411 00035 #define LZW_HASH_SHIFT 6 00036 00037 #define LZW_PREFIX_EMPTY -1 00038 #define LZW_PREFIX_FREE -2 00039 00041 typedef struct Code{ 00043 int hash_prefix; 00044 int code; 00045 uint8_t suffix; 00046 }Code; 00047 00049 typedef struct LZWEncodeState { 00050 int clear_code; 00051 int end_code; 00052 Code tab[LZW_HASH_SIZE]; 00053 int tabsize; 00054 int bits; 00055 int bufsize; 00056 PutBitContext pb; 00057 int maxbits; 00058 int maxcode; 00059 int output_bytes; 00060 int last_code; 00061 enum FF_LZW_MODES mode; 00062 void (*put_bits)(PutBitContext *, int, unsigned); 00063 }LZWEncodeState; 00064 00065 00066 const int ff_lzw_encode_state_size = sizeof(LZWEncodeState); 00067 00074 static inline int hash(int head, const int add) 00075 { 00076 head ^= (add << LZW_HASH_SHIFT); 00077 if (head >= LZW_HASH_SIZE) 00078 head -= LZW_HASH_SIZE; 00079 assert(head >= 0 && head < LZW_HASH_SIZE); 00080 return head; 00081 } 00082 00089 static inline int hashNext(int head, const int offset) 00090 { 00091 head -= offset; 00092 if(head < 0) 00093 head += LZW_HASH_SIZE; 00094 return head; 00095 } 00096 00102 static inline int hashOffset(const int head) 00103 { 00104 return head ? LZW_HASH_SIZE - head : 1; 00105 } 00106 00112 static inline void writeCode(LZWEncodeState * s, int c) 00113 { 00114 assert(0 <= c && c < 1 << s->bits); 00115 s->put_bits(&s->pb, s->bits, c); 00116 } 00117 00118 00126 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix) 00127 { 00128 int h = hash(FFMAX(hash_prefix, 0), c); 00129 int hash_offset = hashOffset(h); 00130 00131 while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) { 00132 if ((s->tab[h].suffix == c) 00133 && (s->tab[h].hash_prefix == hash_prefix)) 00134 return h; 00135 h = hashNext(h, hash_offset); 00136 } 00137 00138 return h; 00139 } 00140 00148 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code) 00149 { 00150 s->tab[hash_code].code = s->tabsize; 00151 s->tab[hash_code].suffix = c; 00152 s->tab[hash_code].hash_prefix = hash_prefix; 00153 00154 s->tabsize++; 00155 00156 if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF)) 00157 s->bits++; 00158 } 00159 00164 static void clearTable(LZWEncodeState * s) 00165 { 00166 int i, h; 00167 00168 writeCode(s, s->clear_code); 00169 s->bits = 9; 00170 for (i = 0; i < LZW_HASH_SIZE; i++) { 00171 s->tab[i].hash_prefix = LZW_PREFIX_FREE; 00172 } 00173 for (i = 0; i < 256; i++) { 00174 h = hash(0, i); 00175 s->tab[h].code = i; 00176 s->tab[h].suffix = i; 00177 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY; 00178 } 00179 s->tabsize = 258; 00180 } 00181 00187 static int writtenBytes(LZWEncodeState *s){ 00188 int ret = put_bits_count(&s->pb) >> 3; 00189 ret -= s->output_bytes; 00190 s->output_bytes += ret; 00191 return ret; 00192 } 00193 00201 void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize, 00202 int maxbits, enum FF_LZW_MODES mode, 00203 void (*lzw_put_bits)(PutBitContext *, int, unsigned)) 00204 { 00205 s->clear_code = 256; 00206 s->end_code = 257; 00207 s->maxbits = maxbits; 00208 init_put_bits(&s->pb, outbuf, outsize); 00209 s->bufsize = outsize; 00210 assert(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS); 00211 s->maxcode = 1 << s->maxbits; 00212 s->output_bytes = 0; 00213 s->last_code = LZW_PREFIX_EMPTY; 00214 s->bits = 9; 00215 s->mode = mode; 00216 s->put_bits = lzw_put_bits; 00217 } 00218 00226 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize) 00227 { 00228 int i; 00229 00230 if(insize * 3 > (s->bufsize - s->output_bytes) * 2){ 00231 return -1; 00232 } 00233 00234 if (s->last_code == LZW_PREFIX_EMPTY) 00235 clearTable(s); 00236 00237 for (i = 0; i < insize; i++) { 00238 uint8_t c = *inbuf++; 00239 int code = findCode(s, c, s->last_code); 00240 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) { 00241 writeCode(s, s->last_code); 00242 addCode(s, c, s->last_code, code); 00243 code= hash(0, c); 00244 } 00245 s->last_code = s->tab[code].code; 00246 if (s->tabsize >= s->maxcode - 1) { 00247 clearTable(s); 00248 } 00249 } 00250 00251 return writtenBytes(s); 00252 } 00253 00259 int ff_lzw_encode_flush(LZWEncodeState *s, 00260 void (*lzw_flush_put_bits)(PutBitContext *)) 00261 { 00262 if (s->last_code != -1) 00263 writeCode(s, s->last_code); 00264 writeCode(s, s->end_code); 00265 lzw_flush_put_bits(&s->pb); 00266 s->last_code = -1; 00267 00268 return writtenBytes(s); 00269 }