LCOV - code coverage report
Current view: top level - libavcodec - lzwenc.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 86 88 97.7 %
Date: 2017-12-15 11:05:35 Functions: 11 11 100.0 %

          Line data    Source code
       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    35103170 : static inline int hash(int head, const int add)
      76             : {
      77    35103170 :     head ^= (add << LZW_HASH_SHIFT);
      78    35103170 :     if (head >= LZW_HASH_SIZE)
      79           0 :         head -= LZW_HASH_SIZE;
      80             :     av_assert2(head >= 0 && head < LZW_HASH_SIZE);
      81    35103170 :     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    18619128 : static inline int hashNext(int head, const int offset)
      91             : {
      92    18619128 :     head -= offset;
      93    18619128 :     if(head < 0)
      94    17017018 :         head += LZW_HASH_SIZE;
      95    18619128 :     return head;
      96             : }
      97             : 
      98             : /**
      99             :  * Hash function calculates hash offset
     100             :  * @param head Actual hash code
     101             :  * @return Hash offset
     102             :  */
     103    26800124 : static inline int hashOffset(const int head)
     104             : {
     105    26800124 :     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     7641407 : static inline void writeCode(LZWEncodeState * s, int c)
     114             : {
     115             :     av_assert2(0 <= c && c < 1 << s->bits);
     116     7641407 :     s->put_bits(&s->pb, s->bits, c);
     117     7641407 : }
     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    26800124 : static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
     128             : {
     129    26800124 :     int h = hash(FFMAX(hash_prefix, 0), c);
     130    26800124 :     int hash_offset = hashOffset(h);
     131             : 
     132    72219376 :     while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
     133    37782574 :         if ((s->tab[h].suffix == c)
     134    20942719 :             && (s->tab[h].hash_prefix == hash_prefix))
     135    19163446 :             return h;
     136    18619128 :         h = hashNext(h, hash_offset);
     137             :     }
     138             : 
     139     7636678 :     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     7636678 : static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
     150             : {
     151     7636678 :     s->tab[hash_code].code = s->tabsize;
     152     7636678 :     s->tab[hash_code].suffix = c;
     153     7636678 :     s->tab[hash_code].hash_prefix = hash_prefix;
     154             : 
     155     7636678 :     s->tabsize++;
     156             : 
     157     7636678 :     if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
     158        6643 :         s->bits++;
     159     7636678 : }
     160             : 
     161             : /**
     162             :  * Clear LZW code table
     163             :  * @param s LZW state
     164             :  */
     165        2603 : static void clearTable(LZWEncodeState * s)
     166             : {
     167             :     int i, h;
     168             : 
     169        2603 :     writeCode(s, s->clear_code);
     170        2603 :     s->bits = 9;
     171    42720436 :     for (i = 0; i < LZW_HASH_SIZE; i++) {
     172    42717833 :         s->tab[i].hash_prefix = LZW_PREFIX_FREE;
     173             :     }
     174      668971 :     for (i = 0; i < 256; i++) {
     175      666368 :         h = hash(0, i);
     176      666368 :         s->tab[h].code = i;
     177      666368 :         s->tab[h].suffix = i;
     178      666368 :         s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
     179             :     }
     180        2603 :     s->tabsize = 258;
     181        2603 : }
     182             : 
     183             : /**
     184             :  * Calculate number of bytes written
     185             :  * @param s LZW encode state
     186             :  * @return Number of bytes written
     187             :  */
     188      134677 : static int writtenBytes(LZWEncodeState *s){
     189      134677 :     int ret = put_bits_count(&s->pb) >> 3;
     190      134677 :     ret -= s->output_bytes;
     191      134677 :     s->output_bytes += ret;
     192      134677 :     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        1063 : 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        1063 :     s->clear_code = 256;
     207        1063 :     s->end_code = 257;
     208        1063 :     s->maxbits = maxbits;
     209        1063 :     init_put_bits(&s->pb, outbuf, outsize);
     210        1063 :     s->bufsize = outsize;
     211        1063 :     av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
     212        1063 :     s->maxcode = 1 << s->maxbits;
     213        1063 :     s->output_bytes = 0;
     214        1063 :     s->last_code = LZW_PREFIX_EMPTY;
     215        1063 :     s->bits = 9;
     216        1063 :     s->mode = mode;
     217        1063 :     s->put_bits = lzw_put_bits;
     218        1063 : }
     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      133614 : int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
     228             : {
     229             :     int i;
     230             : 
     231      133614 :     if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
     232           0 :         return -1;
     233             :     }
     234             : 
     235      133614 :     if (s->last_code == LZW_PREFIX_EMPTY)
     236        1063 :         clearTable(s);
     237             : 
     238    26933738 :     for (i = 0; i < insize; i++) {
     239    26800124 :         uint8_t c = *inbuf++;
     240    26800124 :         int code = findCode(s, c, s->last_code);
     241    26800124 :         if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
     242     7636678 :             writeCode(s, s->last_code);
     243     7636678 :             addCode(s, c, s->last_code, code);
     244     7636678 :             code= hash(0, c);
     245             :         }
     246    26800124 :         s->last_code = s->tab[code].code;
     247    26800124 :         if (s->tabsize >= s->maxcode - 1) {
     248        1540 :             clearTable(s);
     249             :         }
     250             :     }
     251             : 
     252      133614 :     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        1063 : int ff_lzw_encode_flush(LZWEncodeState *s,
     261             :                         void (*lzw_flush_put_bits)(PutBitContext *))
     262             : {
     263        1063 :     if (s->last_code != -1)
     264        1063 :         writeCode(s, s->last_code);
     265        1063 :     writeCode(s, s->end_code);
     266        1063 :     if (s->mode == FF_LZW_GIF)
     267        1063 :         s->put_bits(&s->pb, 1, 0);
     268             : 
     269        1063 :     lzw_flush_put_bits(&s->pb);
     270        1063 :     s->last_code = -1;
     271             : 
     272        1063 :     return writtenBytes(s);
     273             : }

Generated by: LCOV version 1.13