Directory:  ../../../ffmpeg/ 

File:  src/libavcodec/mjpegenc_huffman.c 
Date:  20220121 12:56:39 
Exec  Total  Coverage  

Lines:  75  75  100.0% 
Branches:  123  126  97.6% 
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 <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  480909  static int compare_by_prob(const void *a, const void *b)  
39  {  
40  480909  PTable a_val = *(PTable *) a;  
41  480909  PTable b_val = *(PTable *) b;  
42  480909  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  436310  static int compare_by_length(const void *a, const void *b)  
53  {  
54  436310  HuffTable a_val = *(HuffTable *) a;  
55  436310  HuffTable b_val = *(HuffTable *) b;  
56  436310  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 n1 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/smalltasksforffmpeg/ 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  4956  void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)  
81  {  
82  4956  PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;  
83  
84  int times, i, j, k;  
85  
86  4956  int nbits[257] = {0};  
87  
88  int min;  
89  
90 
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4956 times.

4956  av_assert0(max_length > 0); 
91  
92  4956  to>nitems = 0;  
93  4956  from>nitems = 0;  
94  4956  to>item_idx[0] = 0;  
95  4956  from>item_idx[0] = 0;  
96 
44/44✓ Branch 0 taken 43354 times.
✓ Branch 1 taken 15199 times.
✓ Branch 3 taken 18450 times.
✓ Branch 4 taken 24904 times.
✓ Branch 6 taken 4082 times.
✓ Branch 7 taken 14368 times.
✓ Branch 9 taken 5325 times.
✓ Branch 10 taken 19579 times.
✓ Branch 12 taken 19645 times.
✓ Branch 13 taken 23709 times.
✓ Branch 14 taken 8512 times.
✓ Branch 15 taken 34842 times.
✓ Branch 16 taken 160384 times.
✓ Branch 17 taken 9661 times.
✓ Branch 19 taken 81631 times.
✓ Branch 20 taken 78753 times.
✓ Branch 21 taken 155829 times.
✓ Branch 22 taken 25434 times.
✓ Branch 24 taken 92849 times.
✓ Branch 25 taken 62980 times.
✓ Branch 26 taken 62980 times.
✓ Branch 27 taken 25434 times.
✓ Branch 28 taken 88414 times.
✓ Branch 29 taken 34842 times.
✓ Branch 30 taken 8836 times.
✓ Branch 31 taken 26006 times.
✓ Branch 32 taken 6074 times.
✓ Branch 33 taken 2762 times.
✓ Branch 34 taken 2704 times.
✓ Branch 35 taken 3370 times.
✓ Branch 36 taken 19435 times.
✓ Branch 37 taken 2339 times.
✓ Branch 39 taken 16308 times.
✓ Branch 40 taken 3127 times.
✓ Branch 41 taken 2339 times.
✓ Branch 42 taken 3127 times.
✓ Branch 43 taken 13956 times.
✓ Branch 44 taken 18547 times.
✓ Branch 46 taken 5890 times.
✓ Branch 47 taken 9309 times.
✓ Branch 48 taken 58553 times.
✓ Branch 49 taken 11409 times.
✓ Branch 50 taken 37459 times.
✓ Branch 51 taken 4956 times.

354120  AV_QSORT(prob_table, size, PTable, compare_by_prob); 
97  
98 
2/2✓ Branch 0 taken 84239 times.
✓ Branch 1 taken 4956 times.

89195  for (times = 0; times <= max_length; times++) { 
99  84239  to>nitems = 0;  
100  84239  to>item_idx[0] = 0;  
101  
102  84239  j = 0;  
103  84239  k = 0;  
104  
105 
2/2✓ Branch 0 taken 79283 times.
✓ Branch 1 taken 4956 times.

84239  if (times < max_length) { 
106  79283  i = 0;  
107  }  
108 
4/4✓ Branch 0 taken 3147874 times.
✓ Branch 1 taken 441430 times.
✓ Branch 2 taken 357191 times.
✓ Branch 3 taken 84239 times.

3589304  while (i < size  j + 1 < from>nitems) { 
109  3505065  to>nitems++;  
110  3505065  to>item_idx[to>nitems] = to>item_idx[to>nitems  1];  
111 
2/2✓ Branch 0 taken 3147874 times.
✓ Branch 1 taken 357191 times.

3505065  if (i < size && 
112 
2/2✓ Branch 0 taken 3032076 times.
✓ Branch 1 taken 115798 times.

3147874  (j + 1 >= from>nitems  
113  3032076  prob_table[i].prob <  
114 
2/2✓ Branch 0 taken 1725049 times.
✓ Branch 1 taken 1307027 times.

3032076  from>probability[j] + from>probability[j + 1])) { 
115  1840847  to>items[to>item_idx[to>nitems]++] = prob_table[i].value;  
116  1840847  to>probability[to>nitems  1] = prob_table[i].prob;  
117  1840847  i++;  
118  } else {  
119 
2/2✓ Branch 0 taken 10172795 times.
✓ Branch 1 taken 1664218 times.

11837013  for (k = from>item_idx[j]; k < from>item_idx[j + 2]; k++) { 
120  10172795  to>items[to>item_idx[to>nitems]++] = from>items[k];  
121  }  
122  1664218  to>probability[to>nitems  1] =  
123  1664218  from>probability[j] + from>probability[j + 1];  
124  1664218  j += 2;  
125  }  
126  }  
127  84239  temp = to;  
128  84239  to = from;  
129  84239  from = temp;  
130  }  
131  
132 
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4956 times.

4956  min = (size  1 < from>nitems) ? size  1 : from>nitems; 
133 
2/2✓ Branch 0 taken 858649 times.
✓ Branch 1 taken 4956 times.

863605  for (i = 0; i < from>item_idx[min]; i++) { 
134  858649  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  4956  j = 0;  
139 
2/2✓ Branch 0 taken 1268736 times.
✓ Branch 1 taken 4956 times.

1273692  for (i = 0; i < 256; i++) { 
140 
2/2✓ Branch 0 taken 110105 times.
✓ Branch 1 taken 1158631 times.

1268736  if (nbits[i] > 0) { 
141  110105  distincts[j].code = i;  
142  110105  distincts[j].length = nbits[i];  
143  110105  j++;  
144  }  
145  }  
146  4956  }  
147  
148  4952  void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)  
149  {  
150  4952  memset(s>val_count, 0, sizeof(s>val_count));  
151  4952  }  
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  */  
161  4952  void ff_mjpeg_encode_huffman_close(MJpegEncHuffmanContext *s, uint8_t bits[17],  
162  uint8_t val[], int max_nval)  
163  {  
164  int i, j;  
165  4952  int nval = 0;  
166  PTable val_counts[257];  
167  HuffTable distincts[256];  
168  
169 
2/2✓ Branch 0 taken 1267712 times.
✓ Branch 1 taken 4952 times.

1272664  for (i = 0; i < 256; i++) { 
170 
2/2✓ Branch 0 taken 109583 times.
✓ Branch 1 taken 1158129 times.

1267712  if (s>val_count[i]) nval++; 
171  }  
172 
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4952 times.

4952  av_assert0 (nval <= max_nval); 
173  
174  4952  j = 0;  
175 
2/2✓ Branch 0 taken 1267712 times.
✓ Branch 1 taken 4952 times.

1272664  for (i = 0; i < 256; i++) { 
176 
2/2✓ Branch 0 taken 109583 times.
✓ Branch 1 taken 1158129 times.

1267712  if (s>val_count[i]) { 
177  109583  val_counts[j].value = i;  
178  109583  val_counts[j].prob = s>val_count[i];  
179  109583  j++;  
180  }  
181  }  
182  4952  val_counts[j].value = 256;  
183  4952  val_counts[j].prob = 0;  
184  4952  ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);  
185 
44/44✓ Branch 0 taken 40930 times.
✓ Branch 1 taken 10908 times.
✓ Branch 3 taken 10492 times.
✓ Branch 4 taken 30438 times.
✓ Branch 6 taken 1544 times.
✓ Branch 7 taken 8948 times.
✓ Branch 9 taken 6747 times.
✓ Branch 10 taken 23691 times.
✓ Branch 12 taken 9615 times.
✓ Branch 13 taken 31315 times.
✓ Branch 14 taken 9425 times.
✓ Branch 15 taken 31505 times.
✓ Branch 16 taken 152588 times.
✓ Branch 17 taken 7465 times.
✓ Branch 19 taken 86443 times.
✓ Branch 20 taken 66145 times.
✓ Branch 21 taken 127497 times.
✓ Branch 22 taken 15962 times.
✓ Branch 24 taken 69849 times.
✓ Branch 25 taken 57648 times.
✓ Branch 26 taken 57648 times.
✓ Branch 27 taken 15962 times.
✓ Branch 28 taken 73610 times.
✓ Branch 29 taken 31505 times.
✓ Branch 30 taken 13005 times.
✓ Branch 31 taken 18500 times.
✓ Branch 32 taken 9114 times.
✓ Branch 33 taken 3891 times.
✓ Branch 34 taken 3609 times.
✓ Branch 35 taken 5505 times.
✓ Branch 36 taken 22527 times.
✓ Branch 37 taken 2995 times.
✓ Branch 39 taken 18022 times.
✓ Branch 40 taken 4505 times.
✓ Branch 41 taken 2995 times.
✓ Branch 42 taken 4505 times.
✓ Branch 43 taken 15255 times.
✓ Branch 44 taken 13255 times.
✓ Branch 46 taken 3014 times.
✓ Branch 47 taken 7894 times.
✓ Branch 48 taken 51838 times.
✓ Branch 49 taken 10134 times.
✓ Branch 50 taken 33462 times.
✓ Branch 51 taken 4952 times.

314848  AV_QSORT(distincts, nval, HuffTable, compare_by_length); 
186  
187  4952  memset(bits, 0, sizeof(bits[0]) * 17);  
188 
2/2✓ Branch 0 taken 109583 times.
✓ Branch 1 taken 4952 times.

114535  for (i = 0; i < nval; i++) { 
189  109583  val[i] = distincts[i].code;  
190  109583  bits[distincts[i].length]++;  
191  }  
192  4952  }  
193 