GCC Code Coverage Report
Directory: ../../../ffmpeg/ Exec Total Coverage
File: src/libavcodec/tests/mjpegenc_huffman.c Lines: 35 41 85.4 %
Date: 2020-10-23 17:01:47 Branches: 27 42 64.3 %

Line Branch Exec Source
1
/*
2
 * Copyright (c) 2016 William Ma, Sofia Kim, Dustin Woo
3
 *
4
 * This file is part of FFmpeg.
5
 *
6
 * FFmpeg is free software; you can redistribute it and/or
7
 * modify it under the terms of the GNU Lesser General Public
8
 * License as published by the Free Software Foundation; either
9
 * version 2.1 of the License, or (at your option) any later version.
10
 *
11
 * FFmpeg is distributed in the hope that it will be useful,
12
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14
 * Lesser General Public License for more details.
15
 *
16
 * You should have received a copy of the GNU Lesser General Public
17
 * License along with FFmpeg; if not, write to the Free Software
18
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19
 */
20
21
/**
22
 * @file
23
 * Optimal Huffman Encoding tests.
24
 */
25
26
#include "libavcodec/avcodec.h"
27
#include <stdlib.h>
28
#include "libavcodec/mjpegenc.h"
29
#include "libavcodec/mjpegenc_huffman.h"
30
#include "libavcodec/mjpegenc_common.h"
31
#include "libavcodec/mpegvideo.h"
32
33
// Validate the computed lengths satisfy the JPEG restrictions and is optimal.
34
3
static int check_lengths(int L, int expected_length,
35
                         const int *probs, int nprobs)
36
{
37
    HuffTable lengths[256];
38
    PTable val_counts[256];
39
3
    int actual_length = 0, i, j, k, prob, length;
40
3
    int ret = 0;
41
3
    double cantor_measure = 0;
42
3
    av_assert0(nprobs <= 256);
43
44
520
    for (i = 0; i < nprobs; i++) {
45
517
        val_counts[i] = (PTable){.value = i, .prob = probs[i]};
46
    }
47
48
3
    ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
49
50
520
    for (i = 0; i < nprobs; i++) {
51
        // Find the value's prob and length
52
65807
        for (j = 0; j < nprobs; j++)
53
65807
            if (val_counts[j].value == i) break;
54
65807
        for (k = 0; k < nprobs; k++)
55
65807
            if (lengths[k].code == i) break;
56

517
        if (!(j < nprobs && k < nprobs)) return 1;
57
517
        prob = val_counts[j].prob;
58
517
        length = lengths[k].length;
59
60
517
        if (prob) {
61
340
            actual_length += prob * length;
62
340
            cantor_measure += 1. / (1 << length);
63
        }
64
65

517
        if (length > L || length < 1) return 1;
66
    }
67
    // Check that the codes can be prefix-free.
68
3
    if (cantor_measure > 1) ret = 1;
69
    // Check that the total length is optimal
70
3
    if (actual_length != expected_length) ret = 1;
71
72
3
    if (ret == 1) {
73
      fprintf(stderr,
74
              "Cantor measure: %f\n"
75
              "Actual length: %d\n"
76
              "Expected length: %d\n",
77
              cantor_measure, actual_length, expected_length);
78
    }
79
80
3
    return ret;
81
}
82
83
static const int probs_zeroes[] = {
84
    6, 6, 0, 0, 0
85
};
86
87
static const int probs_skewed[] = {
88
    2, 0, 0, 0, 0, 1, 0, 0, 20, 0, 2, 0, 10, 5, 1, 1, 9, 1, 1, 6, 0, 5, 0, 1, 0, 7, 6,
89
    1, 1, 5, 0, 0, 0, 0, 11, 0, 0, 0, 51, 1, 0, 20, 0, 1, 0, 0, 0, 0, 6, 106, 1, 0, 1,
90
    0, 2, 1, 16, 0, 0, 5, 0, 0, 0, 4, 3, 15, 4, 4, 0, 0, 0, 3, 0, 0, 1, 0, 3, 0, 3, 2,
91
    2, 0, 0, 4, 3, 40, 1, 2, 0, 22, 0, 0, 0, 9, 0, 0, 0, 0, 1, 1, 0, 1, 6, 11, 4, 10,
92
    28, 6, 1, 0, 0, 9, 9, 4, 0, 0, 0, 0, 8, 33844, 2, 0, 2, 1, 1, 5, 0, 0, 1, 9, 1, 0,
93
    4, 14, 4, 0, 0, 3, 8, 0, 51, 9, 6, 1, 1, 2, 2, 3, 1, 5, 5, 29, 0, 0, 0, 0, 14, 29,
94
    6, 4, 13, 12, 2, 3, 1, 0, 5, 4, 1, 1, 0, 0, 29, 1, 0, 0, 0, 0, 4, 0, 0, 1, 0, 1,
95
    7, 0, 42, 0, 0, 0, 0, 0, 2, 0, 3, 9, 0, 0, 0, 2, 1, 0, 0, 6, 5, 6, 1, 2, 3, 0, 0,
96
    0, 3, 0, 0, 28, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 23, 0, 0, 0, 0,
97
    0, 21, 1, 0, 3, 24, 2, 0, 0, 7, 0, 0, 1, 5, 1, 2, 0, 5
98
};
99
100
static const int probs_sat[] = {
101
    74, 8, 14, 7, 9345, 40, 0, 2014, 2, 1, 115, 0, 2, 1, 194, 388, 20, 0, 0, 2, 1, 121,
102
    1, 1583, 0, 16, 21, 2, 132, 2, 15, 9, 13, 1, 0, 2293, 2, 8, 5, 2, 30, 0, 0, 4, 54,
103
    783, 4, 1, 2, 4, 0, 22, 93, 1, 143, 19, 0, 36, 32, 4, 6, 33, 3, 45, 0, 8, 1, 0, 18,
104
    17, 1, 0, 1, 0, 0, 1, 1004, 38, 3, 8, 90, 23, 0, 2819, 3, 0, 970, 158, 9, 6, 4, 48,
105
    4, 0, 1, 0, 0, 60, 3, 62, 0, 2, 2, 2, 279, 66, 16, 1, 20, 0, 7, 9, 32, 1411, 6, 3,
106
    27, 1, 5, 49, 0, 0, 0, 0, 0, 2, 10, 1, 1, 2, 3, 801, 3, 25, 5, 1, 1, 0, 632, 0, 14,
107
    18, 5, 8, 200, 4, 4, 22, 12, 0, 4, 1, 0, 2, 4, 9, 3, 16, 7, 2, 2, 213, 0, 2, 620,
108
    39303, 0, 1, 0, 2, 1, 183781, 1, 0, 0, 0, 94, 7, 3, 4, 0, 4, 306, 43, 352, 76, 34,
109
    13, 11, 0, 51, 1, 13, 19, 0, 26, 0, 7276, 4, 207, 31, 1, 2, 4, 6, 19, 8, 17, 4, 6,
110
    0, 1085, 0, 0, 0, 3, 489, 36, 1, 0, 1, 9420, 294, 28, 0, 57, 5, 0, 9, 2, 0, 1, 2,
111
    2, 0, 0, 9, 2, 29, 2, 2, 7, 0, 5, 490, 0, 7, 5, 0, 1, 8, 0, 0, 23255, 0, 1
112
};
113
114
// Test the example given on @see
115
// http://guru.multimedia.cx/small-tasks-for-ffmpeg/
116
1
int main(int argc, char **argv)
117
{
118
1
    int i, ret = 0;
119
    // Probabilities of symbols 0..4
120
1
    PTable val_counts[] = {
121
        {.value = 0, .prob = 1},
122
        {.value = 1, .prob = 2},
123
        {.value = 2, .prob = 5},
124
        {.value = 3, .prob = 10},
125
        {.value = 4, .prob = 21},
126
    };
127
    // Expected code lengths for each symbol
128
    static const HuffTable expected[] = {
129
        {.code = 0, .length = 3},
130
        {.code = 1, .length = 3},
131
        {.code = 2, .length = 3},
132
        {.code = 3, .length = 3},
133
        {.code = 4, .length = 1},
134
    };
135
    // Actual code lengths
136
    HuffTable distincts[5];
137
138
    // Build optimal huffman tree using an internal function, to allow for
139
    // smaller-than-normal test cases. This mutates val_counts by sorting.
140
1
    ff_mjpegenc_huffman_compute_bits(val_counts, distincts,
141
                                     FF_ARRAY_ELEMS(distincts), 3);
142
143
6
    for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) {
144
5
        if (distincts[i].code != expected[i].code ||
145
5
            distincts[i].length != expected[i].length) {
146
            fprintf(stderr,
147
                    "Built huffman does not equal expectations. "
148
                    "Expected: code %d probability %d, "
149
                    "Actual: code %d probability %d\n",
150
                    expected[i].code, expected[i].length,
151
                    distincts[i].code, distincts[i].length);
152
            ret = 1;
153
        }
154
    }
155
156
    // Check handling of zero probabilities
157
1
    if (check_lengths(16, 18, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes)))
158
        ret = 1;
159
    // Check skewed distribution over 256 without saturated lengths
160
1
    if (check_lengths(16, 41282, probs_skewed, FF_ARRAY_ELEMS(probs_skewed)))
161
        ret = 1;
162
    // Check skewed distribution over 256 with saturated lengths
163
1
    if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat)))
164
        ret = 1;
165
166
1
    return ret;
167
}