FFmpeg
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 }
mjpegenc_common.h
ff_mjpegenc_huffman_compute_bits
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.
Definition: mjpegenc_huffman.c:80
mpegvideo.h
main
int main(int argc, char **argv)
Definition: mjpegenc_huffman.c:116
FF_ARRAY_ELEMS
#define FF_ARRAY_ELEMS(a)
Definition: sinewin_tablegen.c:29
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
PTable::prob
int64_t prob
number of occurences of this value in input
Definition: magicyuvenc.c:49
PTable
Used to assign a occurrence count or "probability" to an input value.
Definition: magicyuvenc.c:47
HuffTable
Used to store optimal huffman encoding results.
Definition: mjpegenc_huffman.h:69
HuffTable::code
int code
code is the input value
Definition: mjpegenc_huffman.h:70
HuffTable::length
int length
length of the encoding
Definition: mjpegenc_huffman.h:71
mjpegenc_huffman.h
PTable::value
int value
input value
Definition: magicyuvenc.c:48
i
int i
Definition: input.c:407
code
and forward the test the status of outputs and forward it to the corresponding return FFERROR_NOT_READY If the filters stores internally one or a few frame for some it can consider them to be part of the FIFO and delay acknowledging a status change accordingly Example code
Definition: filter_design.txt:178
check_lengths
static int check_lengths(int L, int expected_length, const int *probs, int nprobs)
Definition: mjpegenc_huffman.c:34
value
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf default value
Definition: writing_filters.txt:86
probs_zeroes
static const int probs_zeroes[]
Definition: mjpegenc_huffman.c:83
avcodec.h
ret
ret
Definition: filter_design.txt:187
prob
#define prob(name, subs,...)
Definition: cbs_vp9.c:373
L
#define L(x)
Definition: vp56_arith.h:36
probs_sat
static const int probs_sat[]
Definition: mjpegenc_huffman.c:100
mjpegenc.h
probs_skewed
static const int probs_skewed[]
Definition: mjpegenc_huffman.c:87