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