FFmpeg  4.0
mjpegenc_huffman.c
Go to the documentation of this file.
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"
31 #include "libavcodec/mpegvideo.h"
32 
33 // Validate the computed lengths satisfy the JPEG restrictions and is optimal.
34 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  int actual_length = 0, i, j, k, prob, length;
40  int ret = 0;
41  double cantor_measure = 0;
42  av_assert0(nprobs <= 256);
43 
44  for (i = 0; i < nprobs; i++) {
45  val_counts[i] = (PTable){.value = i, .prob = probs[i]};
46  }
47 
48  ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
49 
50  for (i = 0; i < nprobs; i++) {
51  // Find the value's prob and length
52  for (j = 0; j < nprobs; j++)
53  if (val_counts[j].value == i) break;
54  for (k = 0; k < nprobs; k++)
55  if (lengths[k].code == i) break;
56  if (!(j < nprobs && k < nprobs)) return 1;
57  prob = val_counts[j].prob;
58  length = lengths[k].length;
59 
60  if (prob) {
61  actual_length += prob * length;
62  cantor_measure += 1. / (1 << length);
63  }
64 
65  if (length > L || length < 1) return 1;
66  }
67  // Check that the codes can be prefix-free.
68  if (cantor_measure > 1) ret = 1;
69  // Check that the total length is optimal
70  if (actual_length != expected_length) ret = 1;
71 
72  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  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 int main(int argc, char **argv)
117 {
118  int i, ret = 0;
119  // Probabilities of symbols 0..4
120  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  ff_mjpegenc_huffman_compute_bits(val_counts, distincts,
141  FF_ARRAY_ELEMS(distincts), 3);
142 
143  for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) {
144  if (distincts[i].code != expected[i].code ||
145  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
158  ret = 1;
159  // Check skewed distribution over 256 without saturated lengths
161  ret = 1;
162  // Check skewed distribution over 256 with saturated lengths
163  if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat)))
164  ret = 1;
165 
166  return ret;
167 }
static const int probs_sat[]
MJPEG encoder.
mpegvideo header.
int value
input value
Definition: magicyuvenc.c:49
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
int64_t prob
number of occurences of this value in input
Definition: magicyuvenc.c:50
int main(int argc, char **argv)
int length
length of the encoding
#define L(x)
Definition: vp56_arith.h:36
int code
code is the input value
#define FF_ARRAY_ELEMS(a)
void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)
Computes the length of the Huffman encoding for each distinct input value.
Used to store optimal huffman encoding results.
Libavcodec external API header.
Used to assign a occurrence count or "probability" to an input value.
Definition: magicyuvenc.c:48
double value
Definition: eval.c:98
static const int probs_zeroes[]
Huffman table generation for MJPEG encoder.
static int check_lengths(int L, int expected_length, const int *probs, int nprobs)
const char int length
Definition: avisynth_c.h:768
static const int probs_skewed[]