FFmpeg
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 "libavutil/avassert.h"
25 #include "libavutil/qsort.h"
26 #include "mjpegenc_huffman.h"
27 
28 /**
29  * Comparison function for two PTables by prob
30  *
31  * @param a First PTable to compare
32  * @param b Second PTable to compare
33  * @return < 0 for less than, 0 for equals, > 0 for greater than
34  */
35 static int compare_by_prob(const void *a, const void *b)
36 {
37  PTable a_val = *(PTable *) a;
38  PTable b_val = *(PTable *) b;
39  return a_val.prob - b_val.prob;
40 }
41 
42 /**
43  * Comparison function for two HuffTables by length
44  *
45  * @param a First HuffTable to compare
46  * @param b Second HuffTable to compare
47  * @return < 0 for less than, 0 for equals, > 0 for greater than
48  */
49 static int compare_by_length(const void *a, const void *b)
50 {
51  HuffTable a_val = *(HuffTable *) a;
52  HuffTable b_val = *(HuffTable *) b;
53  return a_val.length - b_val.length;
54 }
55 
56 /**
57  * Computes the length of the Huffman encoding for each distinct input value.
58  * Uses package merge algorithm as follows:
59  * 1. start with an empty list, lets call it list(0), set i = 0
60  * 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
61  * 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
62  * 4. if there is more than 1 symbol left in the current list(i), then goto 3
63  * 5. i++
64  * 6. if i < 16 goto 2
65  * 7. select the n-1 elements in the last list with the lowest score (n = the number of symbols)
66  * 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
67  * Go to guru.multimedia.cx/small-tasks-for-ffmpeg/ for more details
68  *
69  * All probabilities should be positive integers. The output is sorted by code,
70  * not by length.
71  *
72  * @param prob_table input array of a PTable for each distinct input value
73  * @param distincts output array of a HuffTable that will be populated by this function
74  * @param size size of the prob_table array
75  * @param max_length max length of an encoding
76  */
77 void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)
78 {
79  PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;
80 
81  int times, i, j, k;
82 
83  int nbits[257] = {0};
84 
85  int min;
86 
87  av_assert0(max_length > 0);
88 
89  to->nitems = 0;
90  from->nitems = 0;
91  to->item_idx[0] = 0;
92  from->item_idx[0] = 0;
93  AV_QSORT(prob_table, size, PTable, compare_by_prob);
94 
95  for (times = 0; times <= max_length; times++) {
96  to->nitems = 0;
97  to->item_idx[0] = 0;
98 
99  j = 0;
100  k = 0;
101 
102  if (times < max_length) {
103  i = 0;
104  }
105  while (i < size || j + 1 < from->nitems) {
106  to->nitems++;
107  to->item_idx[to->nitems] = to->item_idx[to->nitems - 1];
108  if (i < size &&
109  (j + 1 >= from->nitems ||
110  prob_table[i].prob <
111  from->probability[j] + from->probability[j + 1])) {
112  to->items[to->item_idx[to->nitems]++] = prob_table[i].value;
113  to->probability[to->nitems - 1] = prob_table[i].prob;
114  i++;
115  } else {
116  for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) {
117  to->items[to->item_idx[to->nitems]++] = from->items[k];
118  }
119  to->probability[to->nitems - 1] =
120  from->probability[j] + from->probability[j + 1];
121  j += 2;
122  }
123  }
124  temp = to;
125  to = from;
126  from = temp;
127  }
128 
129  min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
130  for (i = 0; i < from->item_idx[min]; i++) {
131  nbits[from->items[i]]++;
132  }
133  // we don't want to return the 256 bit count (it was just in here to prevent
134  // all 1s encoding)
135  j = 0;
136  for (i = 0; i < 256; i++) {
137  if (nbits[i] > 0) {
138  distincts[j].code = i;
139  distincts[j].length = nbits[i];
140  j++;
141  }
142  }
143 }
144 
146 {
147  memset(s->val_count, 0, sizeof(s->val_count));
148 }
149 
150 /**
151  * Produces a Huffman encoding with a given input
152  *
153  * @param s input to encode
154  * @param bits output array where the ith character represents how many input values have i length encoding
155  * @param val output array of input values sorted by their encoded length
156  * @param max_nval maximum number of distinct input values
157  */
159  uint8_t val[], int max_nval)
160 {
161  int i, j;
162  int nval = 0;
163  PTable val_counts[257];
164  HuffTable distincts[256];
165 
166  for (i = 0; i < 256; i++) {
167  if (s->val_count[i]) nval++;
168  }
169  av_assert0 (nval <= max_nval);
170 
171  j = 0;
172  for (i = 0; i < 256; i++) {
173  if (s->val_count[i]) {
174  val_counts[j].value = i;
175  val_counts[j].prob = s->val_count[i];
176  j++;
177  }
178  }
179  val_counts[j].value = 256;
180  val_counts[j].prob = 0;
181  ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);
182  AV_QSORT(distincts, nval, HuffTable, compare_by_length);
183 
184  memset(bits, 0, sizeof(bits[0]) * 17);
185  for (i = 0; i < nval; i++) {
186  val[i] = distincts[i].code;
187  bits[distincts[i].length]++;
188  }
189 }
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:158
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:77
b
#define b
Definition: input.c:41
ff_mjpeg_encode_huffman_init
void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
Definition: mjpegenc_huffman.c:145
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:35
val
static double val(void *priv, double ch)
Definition: aeval.c:78
avassert.h
s
#define s(width, name)
Definition: cbs_vp9.c:198
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:49
bits
uint8_t bits
Definition: vp3data.h:128
from
const char * from
Definition: jacosubdec.c:66
to
const char * to
Definition: webvttdec.c:35
MJpegEncHuffmanContext
Definition: mjpegenc_huffman.h:32
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:40
PTable::prob
int64_t prob
number of occurences of this value in input
Definition: magicyuvenc.c:53
PTable
Used to assign a occurrence count or "probability" to an input value.
Definition: magicyuvenc.c:51
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
qsort.h
PackageMergerList
Used to store intermediate lists in the package merge algorithm.
Definition: magicyuvenc.c:296
for
for(k=2;k<=8;++k)
Definition: h264pred_template.c:425
HuffTable::length
int length
length of the encoding
Definition: mjpegenc_huffman.h:71
size
int size
Definition: twinvq_data.h:10344
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:52
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:255
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
temp
else temp
Definition: vf_mcdeint.c:263
min
float min
Definition: vorbis_enc_data.h:429