Line  Branch  Exec  Source 

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 021101301 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  481404  static int compare_by_prob(const void *a, const void *b)  
36  {  
37  481404  PTable a_val = *(PTable *) a;  
38  481404  PTable b_val = *(PTable *) b;  
39  481404  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  436737  static int compare_by_length(const void *a, const void *b)  
50  {  
51  436737  HuffTable a_val = *(HuffTable *) a;  
52  436737  HuffTable b_val = *(HuffTable *) b;  
53  436737  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 n1 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/smalltasksforffmpeg/ 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  4960  void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)  
78  {  
79  4960  PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;  
80  
81  int times, i, j, k;  
82  
83  4960  int nbits[257] = {0};  
84  
85  int min;  
86  
87 
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4960 times.

4960  av_assert0(max_length > 0); 
88  
89  4960  to>nitems = 0;  
90  4960  from>nitems = 0;  
91  4960  to>item_idx[0] = 0;  
92  4960  from>item_idx[0] = 0;  
93 
44/44✓ Branch 0 taken 43396 times.
✓ Branch 1 taken 15212 times.
✓ Branch 3 taken 18471 times.
✓ Branch 4 taken 24925 times.
✓ Branch 6 taken 4088 times.
✓ Branch 7 taken 14383 times.
✓ Branch 9 taken 5333 times.
✓ Branch 10 taken 19592 times.
✓ Branch 12 taken 19663 times.
✓ Branch 13 taken 23733 times.
✓ Branch 14 taken 8520 times.
✓ Branch 15 taken 34876 times.
✓ Branch 16 taken 160552 times.
✓ Branch 17 taken 9670 times.
✓ Branch 19 taken 81722 times.
✓ Branch 20 taken 78830 times.
✓ Branch 21 taken 156007 times.
✓ Branch 22 taken 25458 times.
✓ Branch 24 taken 92965 times.
✓ Branch 25 taken 63042 times.
✓ Branch 26 taken 63042 times.
✓ Branch 27 taken 25458 times.
✓ Branch 28 taken 88500 times.
✓ Branch 29 taken 34876 times.
✓ Branch 30 taken 8844 times.
✓ Branch 31 taken 26032 times.
✓ Branch 32 taken 6081 times.
✓ Branch 33 taken 2763 times.
✓ Branch 34 taken 2706 times.
✓ Branch 35 taken 3375 times.
✓ Branch 36 taken 19445 times.
✓ Branch 37 taken 2342 times.
✓ Branch 39 taken 16318 times.
✓ Branch 40 taken 3127 times.
✓ Branch 41 taken 2342 times.
✓ Branch 42 taken 3127 times.
✓ Branch 43 taken 13973 times.
✓ Branch 44 taken 18561 times.
✓ Branch 46 taken 5893 times.
✓ Branch 47 taken 9319 times.
✓ Branch 48 taken 58608 times.
✓ Branch 49 taken 11420 times.
✓ Branch 50 taken 37494 times.
✓ Branch 51 taken 4960 times.

389369  AV_QSORT(prob_table, size, PTable, compare_by_prob); 
94  
95 
2/2✓ Branch 0 taken 84307 times.
✓ Branch 1 taken 4960 times.

89267  for (times = 0; times <= max_length; times++) { 
96  84307  to>nitems = 0;  
97  84307  to>item_idx[0] = 0;  
98  
99  84307  j = 0;  
100  84307  k = 0;  
101  
102 
2/2✓ Branch 0 taken 79347 times.
✓ Branch 1 taken 4960 times.

84307  if (times < max_length) { 
103  79347  i = 0;  
104  }  
105 
4/4✓ Branch 0 taken 3150837 times.
✓ Branch 1 taken 441834 times.
✓ Branch 2 taken 357527 times.
✓ Branch 3 taken 84307 times.

3592671  while (i < size  j + 1 < from>nitems) { 
106  3508364  to>nitems++;  
107  3508364  to>item_idx[to>nitems] = to>item_idx[to>nitems  1];  
108 
2/2✓ Branch 0 taken 3150837 times.
✓ Branch 1 taken 357527 times.

3508364  if (i < size && 
109 
2/2✓ Branch 0 taken 3034930 times.
✓ Branch 1 taken 115907 times.

3150837  (j + 1 >= from>nitems  
110  3034930  prob_table[i].prob <  
111 
2/2✓ Branch 0 taken 1726668 times.
✓ Branch 1 taken 1308262 times.

3034930  from>probability[j] + from>probability[j + 1])) { 
112  1842575  to>items[to>item_idx[to>nitems]++] = prob_table[i].value;  
113  1842575  to>probability[to>nitems  1] = prob_table[i].prob;  
114  1842575  i++;  
115  } else {  
116 
2/2✓ Branch 0 taken 10182849 times.
✓ Branch 1 taken 1665789 times.

11848638  for (k = from>item_idx[j]; k < from>item_idx[j + 2]; k++) { 
117  10182849  to>items[to>item_idx[to>nitems]++] = from>items[k];  
118  }  
119  1665789  to>probability[to>nitems  1] =  
120  1665789  from>probability[j] + from>probability[j + 1];  
121  1665789  j += 2;  
122  }  
123  }  
124  84307  temp = to;  
125  84307  to = from;  
126  84307  from = temp;  
127  }  
128  
129 
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4960 times.

4960  min = (size  1 < from>nitems) ? size  1 : from>nitems; 
130 
2/2✓ Branch 0 taken 859509 times.
✓ Branch 1 taken 4960 times.

864469  for (i = 0; i < from>item_idx[min]; i++) { 
131  859509  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  4960  j = 0;  
136 
2/2✓ Branch 0 taken 1269760 times.
✓ Branch 1 taken 4960 times.

1274720  for (i = 0; i < 256; i++) { 
137 
2/2✓ Branch 0 taken 110209 times.
✓ Branch 1 taken 1159551 times.

1269760  if (nbits[i] > 0) { 
138  110209  distincts[j].code = i;  
139  110209  distincts[j].length = nbits[i];  
140  110209  j++;  
141  }  
142  }  
143  4960  }  
144  
145  4956  void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)  
146  {  
147  4956  memset(s>val_count, 0, sizeof(s>val_count));  
148  4956  }  
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  */  
158  4956  void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],  
159  uint8_t val[], int max_nval)  
160  {  
161  int i, j;  
162  4956  int nval = 0;  
163  PTable val_counts[257];  
164  HuffTable distincts[256];  
165  
166 
2/2✓ Branch 0 taken 1268736 times.
✓ Branch 1 taken 4956 times.

1273692  for (i = 0; i < 256; i++) { 
167 
2/2✓ Branch 0 taken 109687 times.
✓ Branch 1 taken 1159049 times.

1268736  if (s>val_count[i]) nval++; 
168  }  
169 
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4956 times.

4956  av_assert0 (nval <= max_nval); 
170  
171  4956  j = 0;  
172 
2/2✓ Branch 0 taken 1268736 times.
✓ Branch 1 taken 4956 times.

1273692  for (i = 0; i < 256; i++) { 
173 
2/2✓ Branch 0 taken 109687 times.
✓ Branch 1 taken 1159049 times.

1268736  if (s>val_count[i]) { 
174  109687  val_counts[j].value = i;  
175  109687  val_counts[j].prob = s>val_count[i];  
176  109687  j++;  
177  }  
178  }  
179  4956  val_counts[j].value = 256;  
180  4956  val_counts[j].prob = 0;  
181  4956  ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);  
182 
44/44✓ Branch 0 taken 40969 times.
✓ Branch 1 taken 10918 times.
✓ Branch 3 taken 10499 times.
✓ Branch 4 taken 30470 times.
✓ Branch 6 taken 1546 times.
✓ Branch 7 taken 8953 times.
✓ Branch 9 taken 6754 times.
✓ Branch 10 taken 23716 times.
✓ Branch 12 taken 9624 times.
✓ Branch 13 taken 31345 times.
✓ Branch 14 taken 9435 times.
✓ Branch 15 taken 31534 times.
✓ Branch 16 taken 152734 times.
✓ Branch 17 taken 7469 times.
✓ Branch 19 taken 86516 times.
✓ Branch 20 taken 66218 times.
✓ Branch 21 taken 127624 times.
✓ Branch 22 taken 15975 times.
✓ Branch 24 taken 69912 times.
✓ Branch 25 taken 57712 times.
✓ Branch 26 taken 57712 times.
✓ Branch 27 taken 15975 times.
✓ Branch 28 taken 73687 times.
✓ Branch 29 taken 31534 times.
✓ Branch 30 taken 13020 times.
✓ Branch 31 taken 18514 times.
✓ Branch 32 taken 9122 times.
✓ Branch 33 taken 3898 times.
✓ Branch 34 taken 3613 times.
✓ Branch 35 taken 5509 times.
✓ Branch 36 taken 22554 times.
✓ Branch 37 taken 2997 times.
✓ Branch 39 taken 18040 times.
✓ Branch 40 taken 4514 times.
✓ Branch 41 taken 2997 times.
✓ Branch 42 taken 4514 times.
✓ Branch 43 taken 15271 times.
✓ Branch 44 taken 13266 times.
✓ Branch 46 taken 3015 times.
✓ Branch 47 taken 7903 times.
✓ Branch 48 taken 51887 times.
✓ Branch 49 taken 10143 times.
✓ Branch 50 taken 33493 times.
✓ Branch 51 taken 4956 times.

346675  AV_QSORT(distincts, nval, HuffTable, compare_by_length); 
183  
184  4956  memset(bits, 0, sizeof(bits[0]) * 17);  
185 
2/2✓ Branch 0 taken 109687 times.
✓ Branch 1 taken 4956 times.

114643  for (i = 0; i < nval; i++) { 
186  109687  val[i] = distincts[i].code;  
187  109687  bits[distincts[i].length]++;  
188  }  
189  4956  }  
190 