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 25 * @author Bartlomiej Wolowiec 26 */ 27 28#include "avcodec.h" 29#include "put_bits.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 enum FF_LZW_MODES mode; ///< TIFF or GIF 62 void (*put_bits)(PutBitContext *, int, unsigned); ///< GIF is LE while TIFF is BE 63}LZWEncodeState; 64 65 66const int ff_lzw_encode_state_size = sizeof(LZWEncodeState); 67 68/** 69 * Hash function adding character 70 * @param head LZW code for prefix 71 * @param add Character to add 72 * @return New hash value 73 */ 74static inline int hash(int head, const int add) 75{ 76 head ^= (add << LZW_HASH_SHIFT); 77 if (head >= LZW_HASH_SIZE) 78 head -= LZW_HASH_SIZE; 79 assert(head >= 0 && head < LZW_HASH_SIZE); 80 return head; 81} 82 83/** 84 * Hash function calculates next hash value 85 * @param head Actual hash code 86 * @param offset Offset calculated by hashOffset 87 * @return New hash value 88 */ 89static inline int hashNext(int head, const int offset) 90{ 91 head -= offset; 92 if(head < 0) 93 head += LZW_HASH_SIZE; 94 return head; 95} 96 97/** 98 * Hash function calculates hash offset 99 * @param head Actual hash code 100 * @return Hash offset 101 */ 102static inline int hashOffset(const int head) 103{ 104 return head ? LZW_HASH_SIZE - head : 1; 105} 106 107/** 108 * Write one code to stream 109 * @param s LZW state 110 * @param c code to write 111 */ 112static inline void writeCode(LZWEncodeState * s, int c) 113{ 114 assert(0 <= c && c < 1 << s->bits); 115 s->put_bits(&s->pb, s->bits, c); 116} 117 118 119/** 120 * Find LZW code for block 121 * @param s LZW state 122 * @param c Last character in block 123 * @param hash_prefix LZW code for prefix 124 * @return LZW code for block or -1 if not found in table 125 */ 126static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix) 127{ 128 int h = hash(FFMAX(hash_prefix, 0), c); 129 int hash_offset = hashOffset(h); 130 131 while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) { 132 if ((s->tab[h].suffix == c) 133 && (s->tab[h].hash_prefix == hash_prefix)) 134 return h; 135 h = hashNext(h, hash_offset); 136 } 137 138 return h; 139} 140 141/** 142 * Add block to LZW code table 143 * @param s LZW state 144 * @param c Last character in block 145 * @param hash_prefix LZW code for prefix 146 * @param hash_code LZW code for bytes block 147 */ 148static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code) 149{ 150 s->tab[hash_code].code = s->tabsize; 151 s->tab[hash_code].suffix = c; 152 s->tab[hash_code].hash_prefix = hash_prefix; 153 154 s->tabsize++; 155 156 if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF)) 157 s->bits++; 158} 159 160/** 161 * Clear LZW code table 162 * @param s LZW state 163 */ 164static void clearTable(LZWEncodeState * s) 165{ 166 int i, h; 167 168 writeCode(s, s->clear_code); 169 s->bits = 9; 170 for (i = 0; i < LZW_HASH_SIZE; i++) { 171 s->tab[i].hash_prefix = LZW_PREFIX_FREE; 172 } 173 for (i = 0; i < 256; i++) { 174 h = hash(0, i); 175 s->tab[h].code = i; 176 s->tab[h].suffix = i; 177 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY; 178 } 179 s->tabsize = 258; 180} 181 182/** 183 * Calculate number of bytes written 184 * @param s LZW encode state 185 * @return Number of bytes written 186 */ 187static int writtenBytes(LZWEncodeState *s){ 188 int ret = put_bits_count(&s->pb) >> 3; 189 ret -= s->output_bytes; 190 s->output_bytes += ret; 191 return ret; 192} 193 194/** 195 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run. 196 * @param s LZW state 197 * @param outbuf Output buffer 198 * @param outsize Size of output buffer 199 * @param maxbits Maximum length of code 200 */ 201void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize, 202 int maxbits, enum FF_LZW_MODES mode, 203 void (*lzw_put_bits)(PutBitContext *, int, unsigned)) 204{ 205 s->clear_code = 256; 206 s->end_code = 257; 207 s->maxbits = maxbits; 208 init_put_bits(&s->pb, outbuf, outsize); 209 s->bufsize = outsize; 210 assert(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS); 211 s->maxcode = 1 << s->maxbits; 212 s->output_bytes = 0; 213 s->last_code = LZW_PREFIX_EMPTY; 214 s->bits = 9; 215 s->mode = mode; 216 s->put_bits = lzw_put_bits; 217} 218 219/** 220 * LZW main compress function 221 * @param s LZW state 222 * @param inbuf Input buffer 223 * @param insize Size of input buffer 224 * @return Number of bytes written or -1 on error 225 */ 226int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize) 227{ 228 int i; 229 230 if(insize * 3 > (s->bufsize - s->output_bytes) * 2){ 231 return -1; 232 } 233 234 if (s->last_code == LZW_PREFIX_EMPTY) 235 clearTable(s); 236 237 for (i = 0; i < insize; i++) { 238 uint8_t c = *inbuf++; 239 int code = findCode(s, c, s->last_code); 240 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) { 241 writeCode(s, s->last_code); 242 addCode(s, c, s->last_code, code); 243 code= hash(0, c); 244 } 245 s->last_code = s->tab[code].code; 246 if (s->tabsize >= s->maxcode - 1) { 247 clearTable(s); 248 } 249 } 250 251 return writtenBytes(s); 252} 253 254/** 255 * Write end code and flush bitstream 256 * @param s LZW state 257 * @return Number of bytes written or -1 on error 258 */ 259int ff_lzw_encode_flush(LZWEncodeState *s, 260 void (*lzw_flush_put_bits)(PutBitContext *)) 261{ 262 if (s->last_code != -1) 263 writeCode(s, s->last_code); 264 writeCode(s, s->end_code); 265 lzw_flush_put_bits(&s->pb); 266 s->last_code = -1; 267 268 return writtenBytes(s); 269} 270