Head

GCC Code Coverage Report

Directory:	../../../ffmpeg/		Exec	Total	Coverage
File:	src/libavcodec/mjpegenc_huffman.c	Lines:	75	75	100.0 %
Date:	2020-01-28 04:56:05	Branches:	123	126	97.6 %


/*
 * MJPEG encoder
 * Copyright (c) 2016 William Ma, Ted Ying, Jerry Jiang
 *
 * 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
 */

#include <string.h>
#include <stdint.h>
#include <stdlib.h>
#include "libavutil/avassert.h"
#include "libavutil/common.h"
#include "libavutil/error.h"
#include "libavutil/qsort.h"
#include "mjpegenc_huffman.h"

/**
 * Comparison function for two PTables by prob
 *
 * @param a First PTable to compare
 * @param b Second PTable to compare
 * @return < 0 for less than, 0 for equals, > 0 for greater than
 */
static int compare_by_prob(const void *a, const void *b)
{
    PTable a_val = *(PTable *) a;
    PTable b_val = *(PTable *) b;
    return a_val.prob - b_val.prob;
}

/**
 * Comparison function for two HuffTables by length
 *
 * @param a First HuffTable to compare
 * @param b Second HuffTable to compare
 * @return < 0 for less than, 0 for equals, > 0 for greater than
 */
static int compare_by_length(const void *a, const void *b)
{
    HuffTable a_val = *(HuffTable *) a;
    HuffTable b_val = *(HuffTable *) b;
    return a_val.length - b_val.length;
}

/**
 * Computes the length of the Huffman encoding for each distinct input value.
 * Uses package merge algorithm as follows:
 * 1. start with an empty list, lets call it list(0), set i = 0
 * 2. add 1 entry to list(i) for each symbol we have and give each a score equal to the probability of the respective symbol
 * 3. merge the 2 symbols of least score and put them in list(i+1), and remove them from list(i). The new score will be the sum of the 2 scores
 * 4. if there is more than 1 symbol left in the current list(i), then goto 3
 * 5. i++
 * 6. if i < 16 goto 2
 * 7. select the n-1 elements in the last list with the lowest score (n = the number of symbols)
 * 8. the length of the huffman code for symbol s will be equal to the number of times the symbol occurs in the select elements
 * Go to guru.multimedia.cx/small-tasks-for-ffmpeg/ for more details
 *
 * All probabilities should be positive integers. The output is sorted by code,
 * not by length.
 *
 * @param prob_table input array of a PTable for each distinct input value
 * @param distincts  output array of a HuffTable that will be populated by this function
 * @param size       size of the prob_table array
 * @param max_length max length of an encoding
 */
void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)
{
    PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;

    int times, i, j, k;

    int nbits[257] = {0};

    int min;

    av_assert0(max_length > 0);

    to->nitems = 0;
    from->nitems = 0;
    to->item_idx[0] = 0;
    from->item_idx[0] = 0;
    AV_QSORT(prob_table, size, PTable, compare_by_prob);

    for (times = 0; times <= max_length; times++) {
        to->nitems = 0;
        to->item_idx[0] = 0;

        j = 0;
        k = 0;

        if (times < max_length) {
            i = 0;
        }
        while (i < size || j + 1 < from->nitems) {
            to->nitems++;
            to->item_idx[to->nitems] = to->item_idx[to->nitems - 1];
            if (i < size &&
                (j + 1 >= from->nitems ||
                 prob_table[i].prob <
                     from->probability[j] + from->probability[j + 1])) {
                to->items[to->item_idx[to->nitems]++] = prob_table[i].value;
                to->probability[to->nitems - 1] = prob_table[i].prob;
                i++;
            } else {
                for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) {
                    to->items[to->item_idx[to->nitems]++] = from->items[k];
                }
                to->probability[to->nitems - 1] =
                    from->probability[j] + from->probability[j + 1];
                j += 2;
            }
        }
        temp = to;
        to = from;
        from = temp;
    }

    min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
    for (i = 0; i < from->item_idx[min]; i++) {
        nbits[from->items[i]]++;
    }
    // we don't want to return the 256 bit count (it was just in here to prevent
    // all 1s encoding)
    j = 0;
    for (i = 0; i < 256; i++) {
        if (nbits[i] > 0) {
            distincts[j].code = i;
            distincts[j].length = nbits[i];
            j++;
        }
    }
}

void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
{
    memset(s->val_count, 0, sizeof(s->val_count));
}

/**
 * Produces a Huffman encoding with a given input
 *
 * @param s         input to encode
 * @param bits      output array where the ith character represents how many input values have i length encoding
 * @param val       output array of input values sorted by their encoded length
 * @param max_nval  maximum number of distinct input values
 */
void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
                                   uint8_t val[], int max_nval)
{
    int i, j;
    int nval = 0;
    PTable val_counts[257];
    HuffTable distincts[256];

    for (i = 0; i < 256; i++) {
        if (s->val_count[i]) nval++;
    }
    av_assert0 (nval <= max_nval);

    j = 0;
    for (i = 0; i < 256; i++) {
        if (s->val_count[i]) {
            val_counts[j].value = i;
            val_counts[j].prob = s->val_count[i];
            j++;
        }
    }
    val_counts[j].value = 256;
    val_counts[j].prob = 0;
    ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);
    AV_QSORT(distincts, nval, HuffTable, compare_by_length);

    memset(bits, 0, sizeof(bits[0]) * 17);
    for (i = 0; i < nval; i++) {
        val[i] = distincts[i].code;
        bits[distincts[i].length]++;
    }
}


Generated by: GCOVR (Version 4.1)

Line	Branch	Exec	Source
1			/*
2			* MJPEG encoder
3			* Copyright (c) 2016 William Ma, Ted Ying, Jerry Jiang
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			#include <string.h>
23			#include <stdint.h>
24			#include <stdlib.h>
25			#include "libavutil/avassert.h"
26			#include "libavutil/common.h"
27			#include "libavutil/error.h"
28			#include "libavutil/qsort.h"
29			#include "mjpegenc_huffman.h"
30
31			/**
32			* Comparison function for two PTables by prob
33			*
34			* @param a First PTable to compare
35			* @param b Second PTable to compare
36			* @return < 0 for less than, 0 for equals, > 0 for greater than
37			*/
38		480909	static int compare_by_prob(const void a, const void b)
39			{
40		480909	PTable a_val = (PTable ) a;
41		480909	PTable b_val = (PTable ) b;
42		480909	return a_val.prob - b_val.prob;
43			}
44
45			/**
46			* Comparison function for two HuffTables by length
47			*
48			* @param a First HuffTable to compare
49			* @param b Second HuffTable to compare
50			* @return < 0 for less than, 0 for equals, > 0 for greater than
51			*/
52		436310	static int compare_by_length(const void a, const void b)
53			{
54		436310	HuffTable a_val = (HuffTable ) a;
55		436310	HuffTable b_val = (HuffTable ) b;
56		436310	return a_val.length - b_val.length;
57			}
58
59			/**
60			* Computes the length of the Huffman encoding for each distinct input value.
61			* Uses package merge algorithm as follows:
62			* 1. start with an empty list, lets call it list(0), set i = 0
63			* 2. add 1 entry to list(i) for each symbol we have and give each a score equal to the probability of the respective symbol
64			* 3. merge the 2 symbols of least score and put them in list(i+1), and remove them from list(i). The new score will be the sum of the 2 scores
65			* 4. if there is more than 1 symbol left in the current list(i), then goto 3
66			* 5. i++
67			* 6. if i < 16 goto 2
68			* 7. select the n-1 elements in the last list with the lowest score (n = the number of symbols)
69			* 8. the length of the huffman code for symbol s will be equal to the number of times the symbol occurs in the select elements
70			* Go to guru.multimedia.cx/small-tasks-for-ffmpeg/ for more details
71			*
72			* All probabilities should be positive integers. The output is sorted by code,
73			* not by length.
74			*
75			* @param prob_table input array of a PTable for each distinct input value
76			* @param distincts output array of a HuffTable that will be populated by this function
77			* @param size size of the prob_table array
78			* @param max_length max length of an encoding
79			*/
80		4956	void ff_mjpegenc_huffman_compute_bits(PTable prob_table, HuffTable distincts, int size, int max_length)
81			{
82		4956	PackageMergerList list_a, list_b, to = &list_a, from = &list_b, *temp;
83
84			int times, i, j, k;
85
86		4956	int nbits[257] = {0};
87
88			int min;
89
90	✗✓	4956	av_assert0(max_length > 0);
91
92		4956	to->nitems = 0;
93		4956	from->nitems = 0;
94		4956	to->item_idx[0] = 0;
95		4956	from->item_idx[0] = 0;
96	✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓	354120	AV_QSORT(prob_table, size, PTable, compare_by_prob);
97
98	✓✓	89195	for (times = 0; times <= max_length; times++) {
99		84239	to->nitems = 0;
100		84239	to->item_idx[0] = 0;
101
102		84239	j = 0;
103		84239	k = 0;
104
105	✓✓	84239	if (times < max_length) {
106		79283	i = 0;
107			}
108	✓✓✓✓	3589304	while (i < size \|\| j + 1 < from->nitems) {
109		3505065	to->nitems++;
110		3505065	to->item_idx[to->nitems] = to->item_idx[to->nitems - 1];
111	✓✓	3505065	if (i < size &&
112	✓✓	3147874	(j + 1 >= from->nitems \|\|
113		3032076	prob_table[i].prob <
114	✓✓	3032076	from->probability[j] + from->probability[j + 1])) {
115		1840847	to->items[to->item_idx[to->nitems]++] = prob_table[i].value;
116		1840847	to->probability[to->nitems - 1] = prob_table[i].prob;
117		1840847	i++;
118			} else {
119	✓✓	11837013	for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) {
120		10172795	to->items[to->item_idx[to->nitems]++] = from->items[k];
121			}
122		1664218	to->probability[to->nitems - 1] =
123		1664218	from->probability[j] + from->probability[j + 1];
124		1664218	j += 2;
125			}
126			}
127		84239	temp = to;
128		84239	to = from;
129		84239	from = temp;
130			}
131
132	✗✓	4956	min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
133	✓✓	863605	for (i = 0; i < from->item_idx[min]; i++) {
134		858649	nbits[from->items[i]]++;
135			}
136			// we don't want to return the 256 bit count (it was just in here to prevent
137			// all 1s encoding)
138		4956	j = 0;
139	✓✓	1273692	for (i = 0; i < 256; i++) {
140	✓✓	1268736	if (nbits[i] > 0) {
141		110105	distincts[j].code = i;
142		110105	distincts[j].length = nbits[i];
143		110105	j++;
144			}
145			}
146		4956	}
147
148		4952	void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
149			{
150		4952	memset(s->val_count, 0, sizeof(s->val_count));
151		4952	}
152
153			/**
154			* Produces a Huffman encoding with a given input
155			*
156			* @param s input to encode
157			* @param bits output array where the ith character represents how many input values have i length encoding
158			* @param val output array of input values sorted by their encoded length
159			* @param max_nval maximum number of distinct input values
160			*/
161		4952	void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],
162			uint8_t val[], int max_nval)
163			{
164			int i, j;
165		4952	int nval = 0;
166			PTable val_counts[257];
167			HuffTable distincts[256];
168
169	✓✓	1272664	for (i = 0; i < 256; i++) {
170	✓✓	1267712	if (s->val_count[i]) nval++;
171			}
172	✗✓	4952	av_assert0 (nval <= max_nval);
173
174		4952	j = 0;
175	✓✓	1272664	for (i = 0; i < 256; i++) {
176	✓✓	1267712	if (s->val_count[i]) {
177		109583	val_counts[j].value = i;
178		109583	val_counts[j].prob = s->val_count[i];
179		109583	j++;
180			}
181			}
182		4952	val_counts[j].value = 256;
183		4952	val_counts[j].prob = 0;
184		4952	ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);
185	✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓ ✓✓✓✓	314848	AV_QSORT(distincts, nval, HuffTable, compare_by_length);
186
187		4952	memset(bits, 0, sizeof(bits[0]) * 17);
188	✓✓	114535	for (i = 0; i < nval; i++) {
189		109583	val[i] = distincts[i].code;
190		109583	bits[distincts[i].length]++;
191			}
192		4952	}