1/* 2 * LZW encoder 3 * Copyright (c) 2007 Bartlomiej Wolowiec 4 * 5 * This file is part of FFmpeg. 6 * 7 * FFmpeg is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU Lesser General Public 9 * License as published by the Free Software Foundation; either 10 * version 2.1 of the License, or (at your option) any later version. 11 * 12 * FFmpeg is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 * Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public 18 * License along with FFmpeg; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 20 */ 21 22/** 23 * LZW encoder 24 * @file libavcodec/lzwenc.c 25 * @author Bartlomiej Wolowiec 26 */ 27 28#include "avcodec.h" 29#include "bitstream.h" 30#include "lzw.h" 31 32#define LZW_MAXBITS 12 33#define LZW_SIZTABLE (1<<LZW_MAXBITS) 34#define LZW_HASH_SIZE 16411 35#define LZW_HASH_SHIFT 6 36 37#define LZW_PREFIX_EMPTY -1 38#define LZW_PREFIX_FREE -2 39 40/** One code in hash table */ 41typedef struct Code{ 42 /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code 43 int hash_prefix; 44 int code; ///< LZW code 45 uint8_t suffix; ///< Last character in code block 46}Code; 47 48/** LZW encode state */ 49typedef struct LZWEncodeState { 50 int clear_code; ///< Value of clear code 51 int end_code; ///< Value of end code 52 Code tab[LZW_HASH_SIZE]; ///< Hash table 53 int tabsize; ///< Number of values in hash table 54 int bits; ///< Actual bits code 55 int bufsize; ///< Size of output buffer 56 PutBitContext pb; ///< Put bit context for output 57 int maxbits; ///< Max bits code 58 int maxcode; ///< Max value of code 59 int output_bytes; ///< Number of written bytes 60 int last_code; ///< Value of last output code or LZW_PREFIX_EMPTY 61}LZWEncodeState; 62 63 64const int ff_lzw_encode_state_size = sizeof(LZWEncodeState); 65 66/** 67 * Hash function adding character 68 * @param head LZW code for prefix 69 * @param add Character to add 70 * @return New hash value 71 */ 72static inline int hash(int head, const int add) 73{ 74 head ^= (add << LZW_HASH_SHIFT); 75 if (head >= LZW_HASH_SIZE) 76 head -= LZW_HASH_SIZE; 77 assert(head >= 0 && head < LZW_HASH_SIZE); 78 return head; 79} 80 81/** 82 * Hash function calculates next hash value 83 * @param head Actual hash code 84 * @param offset Offset calculated by hashOffset 85 * @return New hash value 86 */ 87static inline int hashNext(int head, const int offset) 88{ 89 head -= offset; 90 if(head < 0) 91 head += LZW_HASH_SIZE; 92 return head; 93} 94 95/** 96 * Hash function calculates hash offset 97 * @param head Actual hash code 98 * @return Hash offset 99 */ 100static inline int hashOffset(const int head) 101{ 102 return head ? LZW_HASH_SIZE - head : 1; 103} 104 105/** 106 * Write one code to stream 107 * @param s LZW state 108 * @param c code to write 109 */ 110static inline void writeCode(LZWEncodeState * s, int c) 111{ 112 assert(0 <= c && c < 1 << s->bits); 113 put_bits(&s->pb, s->bits, c); 114} 115 116 117/** 118 * Find LZW code for block 119 * @param s LZW state 120 * @param c Last character in block 121 * @param hash_prefix LZW code for prefix 122 * @return LZW code for block or -1 if not found in table 123 */ 124static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix) 125{ 126 int h = hash(FFMAX(hash_prefix, 0), c); 127 int hash_offset = hashOffset(h); 128 129 while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) { 130 if ((s->tab[h].suffix == c) 131 && (s->tab[h].hash_prefix == hash_prefix)) 132 return h; 133 h = hashNext(h, hash_offset); 134 } 135 136 return h; 137} 138 139/** 140 * Add block to LZW code table 141 * @param s LZW state 142 * @param c Last character in block 143 * @param hash_prefix LZW code for prefix 144 * @param hash_code LZW code for bytes block 145 */ 146static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code) 147{ 148 s->tab[hash_code].code = s->tabsize; 149 s->tab[hash_code].suffix = c; 150 s->tab[hash_code].hash_prefix = hash_prefix; 151 152 s->tabsize++; 153 154 if (s->tabsize >= 1 << s->bits) 155 s->bits++; 156} 157 158/** 159 * Clear LZW code table 160 * @param s LZW state 161 */ 162static void clearTable(LZWEncodeState * s) 163{ 164 int i, h; 165 166 writeCode(s, s->clear_code); 167 s->bits = 9; 168 for (i = 0; i < LZW_HASH_SIZE; i++) { 169 s->tab[i].hash_prefix = LZW_PREFIX_FREE; 170 } 171 for (i = 0; i < 256; i++) { 172 h = hash(0, i); 173 s->tab[h].code = i; 174 s->tab[h].suffix = i; 175 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY; 176 } 177 s->tabsize = 258; 178} 179 180/** 181 * Calculate number of bytes written 182 * @param s LZW encode state 183 * @return Number of bytes written 184 */ 185static int writtenBytes(LZWEncodeState *s){ 186 int ret = put_bits_count(&s->pb) >> 3; 187 ret -= s->output_bytes; 188 s->output_bytes += ret; 189 return ret; 190} 191 192/** 193 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run. 194 * @param s LZW state 195 * @param outbuf Output buffer 196 * @param outsize Size of output buffer 197 * @param maxbits Maximum length of code 198 */ 199void ff_lzw_encode_init(LZWEncodeState * s, uint8_t * outbuf, int outsize, int maxbits) 200{ 201 s->clear_code = 256; 202 s->end_code = 257; 203 s->maxbits = maxbits; 204 init_put_bits(&s->pb, outbuf, outsize); 205 s->bufsize = outsize; 206 assert(9 <= s->maxbits && s->maxbits <= s->maxbits); 207 s->maxcode = 1 << s->maxbits; 208 s->output_bytes = 0; 209 s->last_code = LZW_PREFIX_EMPTY; 210 s->bits = 9; 211} 212 213/** 214 * LZW main compress function 215 * @param s LZW state 216 * @param inbuf Input buffer 217 * @param insize Size of input buffer 218 * @return Number of bytes written or -1 on error 219 */ 220int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize) 221{ 222 int i; 223 224 if(insize * 3 > (s->bufsize - s->output_bytes) * 2){ 225 return -1; 226 } 227 228 if (s->last_code == LZW_PREFIX_EMPTY) 229 clearTable(s); 230 231 for (i = 0; i < insize; i++) { 232 uint8_t c = *inbuf++; 233 int code = findCode(s, c, s->last_code); 234 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) { 235 writeCode(s, s->last_code); 236 addCode(s, c, s->last_code, code); 237 code= hash(0, c); 238 } 239 s->last_code = s->tab[code].code; 240 if (s->tabsize >= s->maxcode - 1) { 241 clearTable(s); 242 } 243 } 244 245 return writtenBytes(s); 246} 247 248/** 249 * Write end code and flush bitstream 250 * @param s LZW state 251 * @return Number of bytes written or -1 on error 252 */ 253int ff_lzw_encode_flush(LZWEncodeState * s) 254{ 255 if (s->last_code != -1) 256 writeCode(s, s->last_code); 257 writeCode(s, s->end_code); 258 flush_put_bits(&s->pb); 259 s->last_code = -1; 260 261 return writtenBytes(s); 262} 263