• 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 "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 }

Generated on Sat Feb 16 2013 09:23:12 for ffmpeg by  doxygen 1.7.1