lzw_encode.c

   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 #ifdef COMPRESSED_CONFIG_FILE
  23
  24 #include "cms_lzw.h"
  25
  26
  27 #ifdef DESKTOP_LINUX
  28
  29 /*
  30  * We are on Intel.  Intel is LE.
  31  */
  32 #define be2me_16(x) ntohs(x)
  33 #define be2me_32(x) ntohl(x)
  34
  35 #else
  36
  37 /*
  38  * We are on the MIPS.  MIPS is in BE mode.
  39  */
  40 #define be2me_16(x) (x)
  41 #define be2me_32(x) (x)
  42
  43 #define UNALIGNED_STORES_ARE_BAD
  44 #endif
  45
  46
  47 #define FFMAX(a,b) ((a) > (b) ? (a) : (b))
  48 #define FFMIN(a,b) ((a) > (b) ? (b) : (a))
  49
  50
  51 /**
  52  * Hash function adding character
  53  * @param head LZW code for prefix
  54  * @param add Character to add
  55  * @return New hash value
  56  */
  57 static inline int hash(int head, const int add)
  58 {
  59     head ^= (add << LZW_HASH_SHIFT);
  60     if (head >= LZW_HASH_SIZE)
  61         head -= LZW_HASH_SIZE;
  62     cmsAst_assert(head >= 0 && head < LZW_HASH_SIZE);
  63     return head;
  64 }
  65
  66 /**
  67  * Hash function calculates next hash value
  68  * @param head Actual hash code
  69  * @param offset Offset calculated by hashOffset
  70  * @return New hash value
  71  */
  72 static inline int hashNext(int head, const int offset)
  73 {
  74     head -= offset;
  75     if(head < 0)
  76         head += LZW_HASH_SIZE;
  77     return head;
  78 }
  79
  80 /**
  81  * Hash function calculates hash offset
  82  * @param head Actual hash code
  83  * @return Hash offset
  84  */
  85 static inline int hashOffset(const int head)
  86 {
  87     return head ? LZW_HASH_SIZE - head : 1;
  88 }
  89
  90
  91 static void init_put_bits(PutBitContext *s, uint8_t *buffer, int buffer_size)
  92 {
  93     if(buffer_size < 0) {
  94         buffer_size = 0;
  95         buffer = NULL;
  96     }
  97
  98     s->buf = buffer;
  99     s->buf_end = s->buf + buffer_size;
 100
 101     s->buf_ptr = s->buf;
 102     s->bit_left=32;
 103     s->bit_buf=0;
 104 }
 105
 106
 107 void put_bits(PutBitContext *s, int n, unsigned int value)
 108 {
 109     unsigned int bit_buf;
 110     int bit_left;
 111
 112     //    printf("put_bits=%d %c (0x%x)\n", n, value, value);
 113     cmsAst_assert(n == 32 || value < (1U << n));
 114
 115     bit_buf = s->bit_buf;
 116     bit_left = s->bit_left;
 117
 118     //    printf("n=%d value=%x cnt=%d buf=%x\n", n, value, bit_cnt, bit_buf);
 119     /* XXX: optimize */
 120     if (n < bit_left) {
 121         bit_buf = (bit_buf<<n) | value;
 122         bit_left-=n;
 123     } else {
 124         bit_buf<<=bit_left;
 125         bit_buf |= value >> (n - bit_left);
 126 #ifdef UNALIGNED_STORES_ARE_BAD
 127         if (3 & (intptr_t) s->buf_ptr) {
 128             s->buf_ptr[0] = bit_buf >> 24;
 129             s->buf_ptr[1] = bit_buf >> 16;
 130             s->buf_ptr[2] = bit_buf >>  8;
 131             s->buf_ptr[3] = bit_buf      ;
 132         } else
 133 #endif
 134         *(uint32_t *)s->buf_ptr = be2me_32(bit_buf);
 135         //        printf("STORING: buf=%p be bitbuf = %08x me=%08x (bit_left=%d)\n",
 136         //               s->buf_ptr, bit_buf, *(uint32_t *)s->buf_ptr, bit_left);
 137         s->buf_ptr+=4;
 138         bit_left+=32 - n;
 139         bit_buf = value;
 140     }
 141
 142     s->bit_buf = bit_buf;
 143     s->bit_left = bit_left;
 144 }
 145
 146 /* pad the end of the output stream with zeros */
 147 static inline void flush_put_bits(PutBitContext *s)
 148 {
 149     s->bit_buf<<= s->bit_left;
 150     while (s->bit_left < 32) {
 151         /* XXX: should test end of buffer */
 152         *s->buf_ptr++=s->bit_buf >> 24;
 153         s->bit_buf<<=8;
 154         s->bit_left+=8;
 155     }
 156     s->bit_left=32;
 157     s->bit_buf=0;
 158 }
 159
 160
 161 /* return the number of bits output */
 162 static inline int put_bits_count(PutBitContext *s)
 163 {
 164     return (s->buf_ptr - s->buf) * 8 + 32 - s->bit_left;
 165 }
 166
 167
 168
 169 /**
 170  * Write one code to stream
 171  * @param s LZW state
 172  * @param c code to write
 173  */
 174 static inline void writeCode(LZWEncoderState * s, int c)
 175 {
 176     cmsAst_assert(0 <= c && c < 1 << s->bits);
 177     put_bits(&s->pb, s->bits, c);
 178 }
 179
 180
 181 /**
 182  * Find LZW code for block
 183  * @param s LZW state
 184  * @param c Last character in block
 185  * @param hash_prefix LZW code for prefix
 186  * @return LZW code for block or -1 if not found in table
 187  */
 188 static inline int findCode(LZWEncoderState * s, uint8_t c, int hash_prefix)
 189 {
 190     int h = hash(FFMAX(hash_prefix, 0), c);
 191     int hash_offset = hashOffset(h);
 192
 193     while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
 194         if ((s->tab[h].suffix == c)
 195             && (s->tab[h].hash_prefix == hash_prefix))
 196             return h;
 197         h = hashNext(h, hash_offset);
 198     }
 199
 200     return h;
 201 }
 202
 203 /**
 204  * Add block to LZW code table
 205  * @param s LZW state
 206  * @param c Last character in block
 207  * @param hash_prefix LZW code for prefix
 208  * @param hash_code LZW code for bytes block
 209  */
 210 static inline void addCode(LZWEncoderState * s, uint8_t c, int hash_prefix, int hash_code)
 211 {
 212     s->tab[hash_code].code = s->tabsize;
 213     s->tab[hash_code].suffix = c;
 214     s->tab[hash_code].hash_prefix = hash_prefix;
 215
 216     s->tabsize++;
 217
 218     if (s->tabsize >= 1 << s->bits)
 219         s->bits++;
 220 }
 221
 222 /**
 223  * Clear LZW code table
 224  * @param s LZW state
 225  */
 226 static void clearTable(LZWEncoderState * s)
 227 {
 228     int i, h;
 229     //    printf("clearTable called\n");
 230     writeCode(s, s->clear_code);
 231     s->bits = 9;
 232     for (i = 0; i < LZW_HASH_SIZE; i++) {
 233         s->tab[i].hash_prefix = LZW_PREFIX_FREE;
 234     }
 235     for (i = 0; i < 256; i++) {
 236         h = hash(0, i);
 237         s->tab[h].code = i;
 238         s->tab[h].suffix = i;
 239         s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
 240     }
 241     s->tabsize = 258;
 242 }
 243
 244 /**
 245  * Calculate number of bytes written
 246  * @param s LZW encode state
 247  * @return Number of bytes written
 248  */
 249 static SINT32 writtenBytes(LZWEncoderState *s){
 250     int ret = put_bits_count(&s->pb) >> 3;
 251     ret -= s->output_bytes;
 252     s->output_bytes += ret;
 253     return ret;
 254 }
 255
 256
 257 CmsRet cmsLzw_initEncoder(LZWEncoderState **p, UINT8 *outbuf, UINT32 outsize)
 258 {
 259    LZWEncoderState *s;
 260
 261     *p = (LZWEncoderState *) cmsMem_alloc(sizeof(LZWEncoderState), ALLOC_ZEROIZE);
 262     if (*p == NULL)
 263     {
 264        cmsLog_error("could not allocate %d bytes for encoder state", sizeof(LZWEncoderState));
 265        return CMSRET_RESOURCE_EXCEEDED;
 266     }
 267     else
 268     {
 269        cmsLog_debug("%d bytes allocated for encoder state", sizeof(LZWEncoderState));
 270     }
 271
 272     s = *p;
 273
 274     s->clear_code = 256;
 275     s->end_code = 257;
 276     s->maxbits = LZW_MAXBITS;
 277     init_put_bits(&s->pb, outbuf, outsize);
 278     s->bufsize = outsize;
 279     cmsAst_assert(9 <= s->maxbits && s->maxbits <= s->maxbits);
 280     s->maxcode = 1 << s->maxbits;
 281     s->output_bytes = 0;
 282     s->last_code = LZW_PREFIX_EMPTY;
 283     s->bits = 9;
 284
 285     return CMSRET_SUCCESS;
 286 }
 287
 288
 289 int cmsLzw_encode(LZWEncoderState *s, const UINT8 *inbuf, UINT32 insize)
 290 {
 291     UINT32 i;
 292     UINT32 round_error=5;
 293
 294     //    printf("size check, insize*3=%d outbuf*2=%d\n", insize * 3, s->bufsize * 2);
 295     if(insize * 3 > (UINT32) (s->bufsize - s->output_bytes) * 2 + round_error){
 296         cmsLog_error("size check failed, insize=%d (*3) outsize=%d (*2)", insize, (s->bufsize - s->output_bytes));
 297         return -1;
 298     }
 299
 300     if (s->last_code == LZW_PREFIX_EMPTY)
 301         clearTable(s);
 302
 303     for (i = 0; i < insize; i++) {
 304         uint8_t c = *inbuf++;
 305         int code = findCode(s, c, s->last_code);
 306
 307         //        printf("\n\n[%d] c=%c code=%d\n", i, c, code);
 308         if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
 309             writeCode(s, s->last_code);
 310             addCode(s, c, s->last_code, code);
 311             code= hash(0, c);
 312         }
 313         s->last_code = s->tab[code].code;
 314         if (s->tabsize >= s->maxcode - 1) {
 315             clearTable(s);
 316         }
 317     }
 318
 319     return writtenBytes(s);
 320 }
 321
 322
 323 SINT32 cmsLzw_flushEncoder(LZWEncoderState * s)
 324 {
 325     if (s->last_code != -1)
 326         writeCode(s, s->last_code);
 327
 328     writeCode(s, s->end_code);
 329     flush_put_bits(&s->pb);
 330     s->last_code = -1;
 331
 332     return writtenBytes(s);
 333 }
 334
 335
 336 void cmsLzw_cleanupEncoder(LZWEncoderState **s)
 337 {
 338    cmsMem_free(*s);
 339    *s = NULL;
 340 }
 341
 342
 343 #endif /* COMPRESSED_CONFIG_FILE */
 344