• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • File List
  • Globals

libavcodec/lzwenc.c

Go to the documentation of this file.
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 }

Generated on Fri Sep 16 2011 17:17:39 for FFmpeg by  doxygen 1.7.1