FFmpeg  4.3
mjpegenc_huffman.c
Go to the documentation of this file.
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 static int compare_by_prob(const void *a, const void *b)
39 {
40  PTable a_val = *(PTable *) a;
41  PTable b_val = *(PTable *) b;
42  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 static int compare_by_length(const void *a, const void *b)
53 {
54  HuffTable a_val = *(HuffTable *) a;
55  HuffTable b_val = *(HuffTable *) b;
56  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 void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)
81 {
82  PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;
83 
84  int times, i, j, k;
85 
86  int nbits[257] = {0};
87 
88  int min;
89 
90  av_assert0(max_length > 0);
91 
92  to->nitems = 0;
93  from->nitems = 0;
94  to->item_idx[0] = 0;
95  from->item_idx[0] = 0;
96  AV_QSORT(prob_table, size, PTable, compare_by_prob);
97 
98  for (times = 0; times <= max_length; times++) {
99  to->nitems = 0;
100  to->item_idx[0] = 0;
101 
102  j = 0;
103  k = 0;
104 
105  if (times < max_length) {
106  i = 0;
107  }
108  while (i < size || j + 1 < from->nitems) {
109  to->nitems++;
110  to->item_idx[to->nitems] = to->item_idx[to->nitems - 1];
111  if (i < size &&
112  (j + 1 >= from->nitems ||
113  prob_table[i].prob <
114  from->probability[j] + from->probability[j + 1])) {
115  to->items[to->item_idx[to->nitems]++] = prob_table[i].value;
116  to->probability[to->nitems - 1] = prob_table[i].prob;
117  i++;
118  } else {
119  for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) {
120  to->items[to->item_idx[to->nitems]++] = from->items[k];
121  }
122  to->probability[to->nitems - 1] =
123  from->probability[j] + from->probability[j + 1];
124  j += 2;
125  }
126  }
127  temp = to;
128  to = from;
129  from = temp;
130  }
131 
132  min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
133  for (i = 0; i < from->item_idx[min]; i++) {
134  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  j = 0;
139  for (i = 0; i < 256; i++) {
140  if (nbits[i] > 0) {
141  distincts[j].code = i;
142  distincts[j].length = nbits[i];
143  j++;
144  }
145  }
146 }
147 
149 {
150  memset(s->val_count, 0, sizeof(s->val_count));
151 }
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  */
162  uint8_t val[], int max_nval)
163 {
164  int i, j;
165  int nval = 0;
166  PTable val_counts[257];
167  HuffTable distincts[256];
168 
169  for (i = 0; i < 256; i++) {
170  if (s->val_count[i]) nval++;
171  }
172  av_assert0 (nval <= max_nval);
173 
174  j = 0;
175  for (i = 0; i < 256; i++) {
176  if (s->val_count[i]) {
177  val_counts[j].value = i;
178  val_counts[j].prob = s->val_count[i];
179  j++;
180  }
181  }
182  val_counts[j].value = 256;
183  val_counts[j].prob = 0;
184  ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);
185  AV_QSORT(distincts, nval, HuffTable, compare_by_length);
186 
187  memset(bits, 0, sizeof(bits[0]) * 17);
188  for (i = 0; i < nval; i++) {
189  val[i] = distincts[i].code;
190  bits[distincts[i].length]++;
191  }
192 }
ff_mjpeg_encode_huffman_close
void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17], uint8_t val[], int max_nval)
Produces a Huffman encoding with a given input.
Definition: mjpegenc_huffman.c:161
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
b
#define b
Definition: input.c:41
ff_mjpeg_encode_huffman_init
void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
Definition: mjpegenc_huffman.c:148
compare_by_prob
static int compare_by_prob(const void *a, const void *b)
Comparison function for two PTables by prob.
Definition: mjpegenc_huffman.c:38
val
static double val(void *priv, double ch)
Definition: aeval.c:76
to
FFmpeg Automated Testing Environment ************************************Introduction Using FATE from your FFmpeg source directory Submitting the results to the FFmpeg result aggregation server Uploading new samples to the fate suite FATE makefile targets and variables Makefile targets Makefile variables Examples Introduction **************FATE is an extended regression suite on the client side and a means for results aggregation and presentation on the server side The first part of this document explains how you can use FATE from your FFmpeg source directory to test your ffmpeg binary The second part describes how you can run FATE to submit the results to FFmpeg’s FATE server In any way you can have a look at the publicly viewable FATE results by visiting this as it can be seen if some test on some platform broke with their recent contribution This usually happens on the platforms the developers could not test on The second part of this document describes how you can run FATE to submit your results to FFmpeg’s FATE server If you want to submit your results be sure to check that your combination of OS and compiler is not already listed on the above mentioned website In the third part you can find a comprehensive listing of FATE makefile targets and variables Using FATE from your FFmpeg source directory **********************************************If you want to run FATE on your machine you need to have the samples in place You can get the samples via the build target fate rsync Use this command from the top level source this will cause FATE to fail NOTE To use a custom wrapper to run the pass ‘ target exec’ to ‘configure’ or set the TARGET_EXEC Make variable Submitting the results to the FFmpeg result aggregation server ****************************************************************To submit your results to the server you should run fate through the shell script ‘tests fate sh’ from the FFmpeg sources This script needs to be invoked with a configuration file as its first argument tests fate sh path to fate_config A configuration file template with comments describing the individual configuration variables can be found at ‘doc fate_config sh template’ Create a configuration that suits your based on the configuration template The ‘slot’ configuration variable can be any string that is not yet but it is suggested that you name it adhering to the following pattern ‘ARCH OS COMPILER COMPILER VERSION’ The configuration file itself will be sourced in a shell therefore all shell features may be used This enables you to setup the environment as you need it for your build For your first test runs the ‘fate_recv’ variable should be empty or commented out This will run everything as normal except that it will omit the submission of the results to the server The following files should be present in $workdir as specified in the configuration it may help to try out the ‘ssh’ command with one or more ‘ v’ options You should get detailed output concerning your SSH configuration and the authentication process The only thing left is to automate the execution of the fate sh script and the synchronisation of the samples directory Uploading new samples to the fate suite *****************************************If you need a sample uploaded send a mail to samples request This is for developers who have an account on the fate suite server If you upload new please make sure they are as small as space on each network bandwidth and so on benefit from smaller test cases Also keep in mind older checkouts use existing sample that means in practice generally do not remove or overwrite files as it likely would break older checkouts or releases Also all needed samples for a commit should be ideally before the push If you need an account for frequently uploading samples or you wish to help others by doing that send a mail to ffmpeg devel rsync vauL Duo ug o o X fate suite ffmpeg Duo ug o o X fate suite fate suite ffmpeg Duo ug o o X fate suite fate suite ffmpeg can be set to
Definition: fate.txt:178
avassert.h
s
#define s(width, name)
Definition: cbs_vp9.c:257
compare_by_length
static int compare_by_length(const void *a, const void *b)
Comparison function for two HuffTables by length.
Definition: mjpegenc_huffman.c:52
bits
uint8_t bits
Definition: vp3data.h:202
from
const char * from
Definition: jacosubdec.c:65
MJpegEncHuffmanContext
Definition: mjpegenc_huffman.h:32
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:50
PTable
Used to assign a occurrence count or "probability" to an input value.
Definition: magicyuvenc.c:48
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
error.h
for
for(j=16;j >0;--j)
Definition: h264pred_template.c:469
qsort.h
PackageMergerList
Used to store intermediate lists in the package merge algorithm.
Definition: magicyuvenc.c:289
HuffTable::length
int length
length of the encoding
Definition: mjpegenc_huffman.h:71
size
int size
Definition: twinvq_data.h:11134
mjpegenc_huffman.h
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
PTable::value
int value
input value
Definition: magicyuvenc.c:49
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:269
AV_QSORT
#define AV_QSORT(p, num, type, cmp)
Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input t...
Definition: qsort.h:33
common.h
uint8_t
uint8_t
Definition: audio_convert.c:194
temp
else temp
Definition: vf_mcdeint.c:256
min
float min
Definition: vorbis_enc_data.h:456