LCOV - code coverage report
Current view: top level - libavcodec - mjpegenc_huffman.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 75 75 100.0 %
Date: 2017-12-16 13:57:32 Functions: 5 5 100.0 %

          Line data    Source code
       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      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 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        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        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        4956 :     AV_QSORT(prob_table, size, PTable, compare_by_prob);
      97             : 
      98       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       84239 :         if (times < max_length) {
     106       79283 :             i = 0;
     107             :         }
     108     3673543 :         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     6652939 :             if (i < size &&
     112     6179950 :                 (j + 1 >= from->nitems ||
     113     3032076 :                  prob_table[i].prob <
     114     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    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     3328436 :                 to->probability[to->nitems - 1] =
     123     3328436 :                     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        4956 :     min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
     133      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     1273692 :     for (i = 0; i < 256; i++) {
     140     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     1272664 :     for (i = 0; i < 256; i++) {
     170     1267712 :         if (s->val_count[i]) nval++;
     171             :     }
     172        4952 :     av_assert0 (nval <= max_nval);
     173             : 
     174        4952 :     j = 0;
     175     1272664 :     for (i = 0; i < 256; i++) {
     176     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        4952 :     AV_QSORT(distincts, nval, HuffTable, compare_by_length);
     186             : 
     187        4952 :     memset(bits, 0, sizeof(bits[0]) * 17);
     188      114535 :     for (i = 0; i < nval; i++) {
     189      109583 :         val[i] = distincts[i].code;
     190      109583 :         bits[distincts[i].length]++;
     191             :     }
     192        4952 : }

Generated by: LCOV version 1.13