00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00028 #include "avcodec.h"
00029 #include "bitstream.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 }LZWEncodeState;
00062
00063
00064 const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);
00065
00072 static inline int hash(int head, const int add)
00073 {
00074 head ^= (add << LZW_HASH_SHIFT);
00075 if (head >= LZW_HASH_SIZE)
00076 head -= LZW_HASH_SIZE;
00077 assert(head >= 0 && head < LZW_HASH_SIZE);
00078 return head;
00079 }
00080
00087 static inline int hashNext(int head, const int offset)
00088 {
00089 head -= offset;
00090 if(head < 0)
00091 head += LZW_HASH_SIZE;
00092 return head;
00093 }
00094
00100 static inline int hashOffset(const int head)
00101 {
00102 return head ? LZW_HASH_SIZE - head : 1;
00103 }
00104
00110 static inline void writeCode(LZWEncodeState * s, int c)
00111 {
00112 assert(0 <= c && c < 1 << s->bits);
00113 put_bits(&s->pb, s->bits, c);
00114 }
00115
00116
00124 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
00125 {
00126 int h = hash(FFMAX(hash_prefix, 0), c);
00127 int hash_offset = hashOffset(h);
00128
00129 while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
00130 if ((s->tab[h].suffix == c)
00131 && (s->tab[h].hash_prefix == hash_prefix))
00132 return h;
00133 h = hashNext(h, hash_offset);
00134 }
00135
00136 return h;
00137 }
00138
00146 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
00147 {
00148 s->tab[hash_code].code = s->tabsize;
00149 s->tab[hash_code].suffix = c;
00150 s->tab[hash_code].hash_prefix = hash_prefix;
00151
00152 s->tabsize++;
00153
00154 if (s->tabsize >= 1 << s->bits)
00155 s->bits++;
00156 }
00157
00162 static void clearTable(LZWEncodeState * s)
00163 {
00164 int i, h;
00165
00166 writeCode(s, s->clear_code);
00167 s->bits = 9;
00168 for (i = 0; i < LZW_HASH_SIZE; i++) {
00169 s->tab[i].hash_prefix = LZW_PREFIX_FREE;
00170 }
00171 for (i = 0; i < 256; i++) {
00172 h = hash(0, i);
00173 s->tab[h].code = i;
00174 s->tab[h].suffix = i;
00175 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
00176 }
00177 s->tabsize = 258;
00178 }
00179
00185 static int writtenBytes(LZWEncodeState *s){
00186 int ret = put_bits_count(&s->pb) >> 3;
00187 ret -= s->output_bytes;
00188 s->output_bytes += ret;
00189 return ret;
00190 }
00191
00199 void ff_lzw_encode_init(LZWEncodeState * s, uint8_t * outbuf, int outsize, int maxbits)
00200 {
00201 s->clear_code = 256;
00202 s->end_code = 257;
00203 s->maxbits = maxbits;
00204 init_put_bits(&s->pb, outbuf, outsize);
00205 s->bufsize = outsize;
00206 assert(9 <= s->maxbits && s->maxbits <= s->maxbits);
00207 s->maxcode = 1 << s->maxbits;
00208 s->output_bytes = 0;
00209 s->last_code = LZW_PREFIX_EMPTY;
00210 s->bits = 9;
00211 }
00212
00220 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
00221 {
00222 int i;
00223
00224 if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
00225 return -1;
00226 }
00227
00228 if (s->last_code == LZW_PREFIX_EMPTY)
00229 clearTable(s);
00230
00231 for (i = 0; i < insize; i++) {
00232 uint8_t c = *inbuf++;
00233 int code = findCode(s, c, s->last_code);
00234 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
00235 writeCode(s, s->last_code);
00236 addCode(s, c, s->last_code, code);
00237 code= hash(0, c);
00238 }
00239 s->last_code = s->tab[code].code;
00240 if (s->tabsize >= s->maxcode - 1) {
00241 clearTable(s);
00242 }
00243 }
00244
00245 return writtenBytes(s);
00246 }
00247
00253 int ff_lzw_encode_flush(LZWEncodeState * s)
00254 {
00255 if (s->last_code != -1)
00256 writeCode(s, s->last_code);
00257 writeCode(s, s->end_code);
00258 flush_put_bits(&s->pb);
00259 s->last_code = -1;
00260
00261 return writtenBytes(s);
00262 }