FFmpeg coverage

GCC Code Coverage Report

Directory:	../../../ffmpeg/		Exec	Total	Coverage
File:	src/libavcodec/lzwenc.c	Lines:	88	94	93.6 %
Date:	2020-09-25 23:16:12	Branches:	32	42	76.2 %


/*
 * LZW encoder
 * Copyright (c) 2007 Bartlomiej Wolowiec
 *
 * This file is part of FFmpeg.
 *
 * FFmpeg is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * FFmpeg is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with FFmpeg; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

/**
 * @file
 * LZW encoder
 * @author Bartlomiej Wolowiec
 */

#include "avcodec.h"
#include "lzw.h"
#include "mathops.h"
#include "put_bits.h"

#define LZW_MAXBITS 12
#define LZW_SIZTABLE (1<<LZW_MAXBITS)
#define LZW_HASH_SIZE 16411
#define LZW_HASH_SHIFT 6

#define LZW_PREFIX_EMPTY -1
#define LZW_PREFIX_FREE -2

/** One code in hash table */
typedef struct Code{
    /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code
    int hash_prefix;
    int code;               ///< LZW code
    uint8_t suffix;         ///< Last character in code block
}Code;

/** LZW encode state */
typedef struct LZWEncodeState {
    int clear_code;          ///< Value of clear code
    int end_code;            ///< Value of end code
    Code tab[LZW_HASH_SIZE]; ///< Hash table
    int tabsize;             ///< Number of values in hash table
    int bits;                ///< Actual bits code
    int bufsize;             ///< Size of output buffer
    PutBitContext pb;        ///< Put bit context for output
    int maxbits;             ///< Max bits code
    int maxcode;             ///< Max value of code
    int output_bytes;        ///< Number of written bytes
    int last_code;           ///< Value of last output code or LZW_PREFIX_EMPTY
    enum FF_LZW_MODES mode;  ///< TIFF or GIF
    int little_endian;       ///< GIF is LE while TIFF is BE
}LZWEncodeState;


const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);

/**
 * Hash function adding character
 * @param head LZW code for prefix
 * @param add Character to add
 * @return New hash value
 */
static inline int hash(int head, const int add)
{
    head ^= (add << LZW_HASH_SHIFT);
    if (head >= LZW_HASH_SIZE)
        head -= LZW_HASH_SIZE;
    av_assert2(head >= 0 && head < LZW_HASH_SIZE);
    return head;
}

/**
 * Hash function calculates next hash value
 * @param head Actual hash code
 * @param offset Offset calculated by hashOffset
 * @return New hash value
 */
static inline int hashNext(int head, const int offset)
{
    head -= offset;
    if(head < 0)
        head += LZW_HASH_SIZE;
    return head;
}

/**
 * Hash function calculates hash offset
 * @param head Actual hash code
 * @return Hash offset
 */
static inline int hashOffset(const int head)
{
    return head ? LZW_HASH_SIZE - head : 1;
}

/**
 * Write one code to stream
 * @param s LZW state
 * @param c code to write
 */
static inline void writeCode(LZWEncodeState * s, int c)
{
    av_assert2(0 <= c && c < 1 << s->bits);
    if (s->little_endian)
        put_bits_le(&s->pb, s->bits, c);
    else
        put_bits(&s->pb, s->bits, c);
}


/**
 * Find LZW code for block
 * @param s LZW state
 * @param c Last character in block
 * @param hash_prefix LZW code for prefix
 * @return LZW code for block or -1 if not found in table
 */
static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
{
    int h = hash(FFMAX(hash_prefix, 0), c);
    int hash_offset = hashOffset(h);

    while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
        if ((s->tab[h].suffix == c)
            && (s->tab[h].hash_prefix == hash_prefix))
            return h;
        h = hashNext(h, hash_offset);
    }

    return h;
}

/**
 * Add block to LZW code table
 * @param s LZW state
 * @param c Last character in block
 * @param hash_prefix LZW code for prefix
 * @param hash_code LZW code for bytes block
 */
static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
{
    s->tab[hash_code].code = s->tabsize;
    s->tab[hash_code].suffix = c;
    s->tab[hash_code].hash_prefix = hash_prefix;

    s->tabsize++;

    if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
        s->bits++;
}

/**
 * Clear LZW code table
 * @param s LZW state
 */
static void clearTable(LZWEncodeState * s)
{
    int i, h;

    writeCode(s, s->clear_code);
    s->bits = 9;
    for (i = 0; i < LZW_HASH_SIZE; i++) {
        s->tab[i].hash_prefix = LZW_PREFIX_FREE;
    }
    for (i = 0; i < 256; i++) {
        h = hash(0, i);
        s->tab[h].code = i;
        s->tab[h].suffix = i;
        s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
    }
    s->tabsize = 258;
}

/**
 * Calculate number of bytes written
 * @param s LZW encode state
 * @return Number of bytes written
 */
static int writtenBytes(LZWEncodeState *s){
    int ret = put_bits_count(&s->pb) >> 3;
    ret -= s->output_bytes;
    s->output_bytes += ret;
    return ret;
}

/**
 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
 * @param s LZW state
 * @param outbuf Output buffer
 * @param outsize Size of output buffer
 * @param maxbits Maximum length of code
 */
void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,
                        int maxbits, enum FF_LZW_MODES mode, int little_endian)
{
    s->clear_code = 256;
    s->end_code = 257;
    s->maxbits = maxbits;
    init_put_bits(&s->pb, outbuf, outsize);
    s->bufsize = outsize;
    av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
    s->maxcode = 1 << s->maxbits;
    s->output_bytes = 0;
    s->last_code = LZW_PREFIX_EMPTY;
    s->bits = 9;
    s->mode = mode;
    s->little_endian = little_endian;
}

/**
 * LZW main compress function
 * @param s LZW state
 * @param inbuf Input buffer
 * @param insize Size of input buffer
 * @return Number of bytes written or -1 on error
 */
int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
{
    int i;

    if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
        return -1;
    }

    if (s->last_code == LZW_PREFIX_EMPTY)
        clearTable(s);

    for (i = 0; i < insize; i++) {
        uint8_t c = *inbuf++;
        int code = findCode(s, c, s->last_code);
        if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
            writeCode(s, s->last_code);
            addCode(s, c, s->last_code, code);
            code= hash(0, c);
        }
        s->last_code = s->tab[code].code;
        if (s->tabsize >= s->maxcode - 1) {
            clearTable(s);
        }
    }

    return writtenBytes(s);
}

/**
 * Write end code and flush bitstream
 * @param s LZW state
 * @return Number of bytes written or -1 on error
 */
int ff_lzw_encode_flush(LZWEncodeState *s)
{
    if (s->last_code != -1)
        writeCode(s, s->last_code);
    writeCode(s, s->end_code);
    if (s->little_endian) {
        if (s->mode == FF_LZW_GIF)
            put_bits_le(&s->pb, 1, 0);

        flush_put_bits_le(&s->pb);
    } else {
        if (s->mode == FF_LZW_GIF)
            put_bits(&s->pb, 1, 0);

        flush_put_bits(&s->pb);
    }
    s->last_code = -1;

    return writtenBytes(s);
}


Generated by: GCOVR (Version 4.2)

Line	Branch	Exec	Source
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			int little_endian; ///< 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		5529886	static inline int hash(int head, const int add)
76			{
77		5529886	head ^= (add << LZW_HASH_SHIFT);
78	✗✓	5529886	if (head >= LZW_HASH_SIZE)
79			head -= LZW_HASH_SIZE;
80			av_assert2(head >= 0 && head < LZW_HASH_SIZE);
81		5529886	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		1409932	static inline int hashNext(int head, const int offset)
91			{
92		1409932	head -= offset;
93	✓✓	1409932	if(head < 0)
94		1118268	head += LZW_HASH_SIZE;
95		1409932	return head;
96			}
97
98			/**
99			* Hash function calculates hash offset
100			* @param head Actual hash code
101			* @return Hash offset
102			*/
103		3541685	static inline int hashOffset(const int head)
104			{
105	✓✓	3541685	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		1630012	static inline void writeCode(LZWEncodeState * s, int c)
114			{
115			av_assert2(0 <= c && c < 1 << s->bits);
116	✓✗	1630012	if (s->little_endian)
117		1630012	put_bits_le(&s->pb, s->bits, c);
118			else
119			put_bits(&s->pb, s->bits, c);
120		1630012	}
121
122
123			/**
124			* Find LZW code for block
125			* @param s LZW state
126			* @param c Last character in block
127			* @param hash_prefix LZW code for prefix
128			* @return LZW code for block or -1 if not found in table
129			*/
130		3541685	static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
131			{
132		3541685	int h = hash(FFMAX(hash_prefix, 0), c);
133		3541685	int hash_offset = hashOffset(h);
134
135	✓✓	4951617	while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
136	✓✓	3325144	if ((s->tab[h].suffix == c)
137	✓✓	1965850	&& (s->tab[h].hash_prefix == hash_prefix))
138		1915212	return h;
139		1409932	h = hashNext(h, hash_offset);
140			}
141
142		1626473	return h;
143			}
144
145			/**
146			* Add block to LZW code table
147			* @param s LZW state
148			* @param c Last character in block
149			* @param hash_prefix LZW code for prefix
150			* @param hash_code LZW code for bytes block
151			*/
152		1626473	static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
153			{
154		1626473	s->tab[hash_code].code = s->tabsize;
155		1626473	s->tab[hash_code].suffix = c;
156		1626473	s->tab[hash_code].hash_prefix = hash_prefix;
157
158		1626473	s->tabsize++;
159
160	✓✓	1626473	if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
161		1324	s->bits++;
162		1626473	}
163
164			/**
165			* Clear LZW code table
166			* @param s LZW state
167			*/
168		1413	static void clearTable(LZWEncodeState * s)
169			{
170			int i, h;
171
172		1413	writeCode(s, s->clear_code);
173		1413	s->bits = 9;
174	✓✓	23190156	for (i = 0; i < LZW_HASH_SIZE; i++) {
175		23188743	s->tab[i].hash_prefix = LZW_PREFIX_FREE;
176			}
177	✓✓	363141	for (i = 0; i < 256; i++) {
178		361728	h = hash(0, i);
179		361728	s->tab[h].code = i;
180		361728	s->tab[h].suffix = i;
181		361728	s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
182			}
183		1413	s->tabsize = 258;
184		1413	}
185
186			/**
187			* Calculate number of bytes written
188			* @param s LZW encode state
189			* @return Number of bytes written
190			*/
191		35140	static int writtenBytes(LZWEncodeState *s){
192		35140	int ret = put_bits_count(&s->pb) >> 3;
193		35140	ret -= s->output_bytes;
194		35140	s->output_bytes += ret;
195		35140	return ret;
196			}
197
198			/**
199			* Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
200			* @param s LZW state
201			* @param outbuf Output buffer
202			* @param outsize Size of output buffer
203			* @param maxbits Maximum length of code
204			*/
205		1063	void ff_lzw_encode_init(LZWEncodeState s, uint8_t outbuf, int outsize,
206			int maxbits, enum FF_LZW_MODES mode, int little_endian)
207			{
208		1063	s->clear_code = 256;
209		1063	s->end_code = 257;
210		1063	s->maxbits = maxbits;
211		1063	init_put_bits(&s->pb, outbuf, outsize);
212		1063	s->bufsize = outsize;
213	✓✗✗✓	1063	av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
214		1063	s->maxcode = 1 << s->maxbits;
215		1063	s->output_bytes = 0;
216		1063	s->last_code = LZW_PREFIX_EMPTY;
217		1063	s->bits = 9;
218		1063	s->mode = mode;
219		1063	s->little_endian = little_endian;
220		1063	}
221
222			/**
223			* LZW main compress function
224			* @param s LZW state
225			* @param inbuf Input buffer
226			* @param insize Size of input buffer
227			* @return Number of bytes written or -1 on error
228			*/
229		34077	int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
230			{
231			int i;
232
233	✗✓	34077	if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
234			return -1;
235			}
236
237	✓✓	34077	if (s->last_code == LZW_PREFIX_EMPTY)
238		1063	clearTable(s);
239
240	✓✓	3575762	for (i = 0; i < insize; i++) {
241		3541685	uint8_t c = *inbuf++;
242		3541685	int code = findCode(s, c, s->last_code);
243	✓✓	3541685	if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
244		1626473	writeCode(s, s->last_code);
245		1626473	addCode(s, c, s->last_code, code);
246		1626473	code= hash(0, c);
247			}
248		3541685	s->last_code = s->tab[code].code;
249	✓✓	3541685	if (s->tabsize >= s->maxcode - 1) {
250		350	clearTable(s);
251			}
252			}
253
254		34077	return writtenBytes(s);
255			}
256
257			/**
258			* Write end code and flush bitstream
259			* @param s LZW state
260			* @return Number of bytes written or -1 on error
261			*/
262		1063	int ff_lzw_encode_flush(LZWEncodeState *s)
263			{
264	✓✗	1063	if (s->last_code != -1)
265		1063	writeCode(s, s->last_code);
266		1063	writeCode(s, s->end_code);
267	✓✗	1063	if (s->little_endian) {
268	✓✗	1063	if (s->mode == FF_LZW_GIF)
269		1063	put_bits_le(&s->pb, 1, 0);
270
271		1063	flush_put_bits_le(&s->pb);
272			} else {
273			if (s->mode == FF_LZW_GIF)
274			put_bits(&s->pb, 1, 0);
275
276			flush_put_bits(&s->pb);
277			}
278		1063	s->last_code = -1;
279
280		1063	return writtenBytes(s);
281			}