GCC Code Coverage Report
Directory: ../../../ffmpeg/ Exec Total Coverage
File: src/libavcodec/mjpegenc_huffman.c Lines: 75 75 100.0 %
Date: 2019-11-20 04:07:19 Branches: 123 126 97.6 %

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
}