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