LCOV - code coverage report
Current view: top level - src/libavcodec/tests - mjpegenc_huffman.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 35 41 85.4 %
Date: 2017-06-23 19:00:59 Functions: 2 2 100.0 %

          Line data    Source code
       1             : /*
       2             :  * Copyright (c) 2016 William Ma, Sofia Kim, Dustin Woo
       3             :  *
       4             :  * This file is part of FFmpeg.
       5             :  *
       6             :  * FFmpeg is free software; you can redistribute it and/or
       7             :  * modify it under the terms of the GNU Lesser General Public
       8             :  * License as published by the Free Software Foundation; either
       9             :  * version 2.1 of the License, or (at your option) any later version.
      10             :  *
      11             :  * FFmpeg is distributed in the hope that it will be useful,
      12             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      14             :  * Lesser General Public License for more details.
      15             :  *
      16             :  * You should have received a copy of the GNU Lesser General Public
      17             :  * License along with FFmpeg; if not, write to the Free Software
      18             :  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
      19             :  */
      20             : 
      21             : /**
      22             :  * @file
      23             :  * Optimal Huffman Encoding tests.
      24             :  */
      25             : 
      26             : #include "libavcodec/avcodec.h"
      27             : #include <stdlib.h>
      28             : #include "libavcodec/mjpegenc.h"
      29             : #include "libavcodec/mjpegenc_huffman.h"
      30             : #include "libavcodec/mjpegenc_common.h"
      31             : #include "libavcodec/mpegvideo.h"
      32             : 
      33             : // Validate the computed lengths satisfy the JPEG restrictions and is optimal.
      34           3 : static int check_lengths(int L, int expected_length,
      35             :                          const int *probs, int nprobs)
      36             : {
      37             :     HuffTable lengths[256];
      38             :     PTable val_counts[256];
      39           3 :     int actual_length = 0, i, j, k, prob, length;
      40           3 :     int ret = 0;
      41           3 :     double cantor_measure = 0;
      42           3 :     av_assert0(nprobs <= 256);
      43             : 
      44         520 :     for (i = 0; i < nprobs; i++) {
      45         517 :         val_counts[i] = (PTable){.value = i, .prob = probs[i]};
      46             :     }
      47             : 
      48           3 :     ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
      49             : 
      50         520 :     for (i = 0; i < nprobs; i++) {
      51             :         // Find the value's prob and length
      52       65807 :         for (j = 0; j < nprobs; j++)
      53       65807 :             if (val_counts[j].value == i) break;
      54       65807 :         for (k = 0; k < nprobs; k++)
      55       65807 :             if (lengths[k].code == i) break;
      56         517 :         if (!(j < nprobs && k < nprobs)) return 1;
      57         517 :         prob = val_counts[j].prob;
      58         517 :         length = lengths[k].length;
      59             : 
      60         517 :         if (prob) {
      61         340 :             actual_length += prob * length;
      62         340 :             cantor_measure += 1. / (1 << length);
      63             :         }
      64             : 
      65         517 :         if (length > L || length < 1) return 1;
      66             :     }
      67             :     // Check that the codes can be prefix-free.
      68           3 :     if (cantor_measure > 1) ret = 1;
      69             :     // Check that the total length is optimal
      70           3 :     if (actual_length != expected_length) ret = 1;
      71             : 
      72           3 :     if (ret == 1) {
      73           0 :       fprintf(stderr,
      74             :               "Cantor measure: %f\n"
      75             :               "Actual length: %d\n"
      76             :               "Expected length: %d\n",
      77             :               cantor_measure, actual_length, expected_length);
      78             :     }
      79             : 
      80           3 :     return ret;
      81             : }
      82             : 
      83             : static const int probs_zeroes[] = {
      84             :     6, 6, 0, 0, 0
      85             : };
      86             : 
      87             : static const int probs_skewed[] = {
      88             :     2, 0, 0, 0, 0, 1, 0, 0, 20, 0, 2, 0, 10, 5, 1, 1, 9, 1, 1, 6, 0, 5, 0, 1, 0, 7, 6,
      89             :     1, 1, 5, 0, 0, 0, 0, 11, 0, 0, 0, 51, 1, 0, 20, 0, 1, 0, 0, 0, 0, 6, 106, 1, 0, 1,
      90             :     0, 2, 1, 16, 0, 0, 5, 0, 0, 0, 4, 3, 15, 4, 4, 0, 0, 0, 3, 0, 0, 1, 0, 3, 0, 3, 2,
      91             :     2, 0, 0, 4, 3, 40, 1, 2, 0, 22, 0, 0, 0, 9, 0, 0, 0, 0, 1, 1, 0, 1, 6, 11, 4, 10,
      92             :     28, 6, 1, 0, 0, 9, 9, 4, 0, 0, 0, 0, 8, 33844, 2, 0, 2, 1, 1, 5, 0, 0, 1, 9, 1, 0,
      93             :     4, 14, 4, 0, 0, 3, 8, 0, 51, 9, 6, 1, 1, 2, 2, 3, 1, 5, 5, 29, 0, 0, 0, 0, 14, 29,
      94             :     6, 4, 13, 12, 2, 3, 1, 0, 5, 4, 1, 1, 0, 0, 29, 1, 0, 0, 0, 0, 4, 0, 0, 1, 0, 1,
      95             :     7, 0, 42, 0, 0, 0, 0, 0, 2, 0, 3, 9, 0, 0, 0, 2, 1, 0, 0, 6, 5, 6, 1, 2, 3, 0, 0,
      96             :     0, 3, 0, 0, 28, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 23, 0, 0, 0, 0,
      97             :     0, 21, 1, 0, 3, 24, 2, 0, 0, 7, 0, 0, 1, 5, 1, 2, 0, 5
      98             : };
      99             : 
     100             : static const int probs_sat[] = {
     101             :     74, 8, 14, 7, 9345, 40, 0, 2014, 2, 1, 115, 0, 2, 1, 194, 388, 20, 0, 0, 2, 1, 121,
     102             :     1, 1583, 0, 16, 21, 2, 132, 2, 15, 9, 13, 1, 0, 2293, 2, 8, 5, 2, 30, 0, 0, 4, 54,
     103             :     783, 4, 1, 2, 4, 0, 22, 93, 1, 143, 19, 0, 36, 32, 4, 6, 33, 3, 45, 0, 8, 1, 0, 18,
     104             :     17, 1, 0, 1, 0, 0, 1, 1004, 38, 3, 8, 90, 23, 0, 2819, 3, 0, 970, 158, 9, 6, 4, 48,
     105             :     4, 0, 1, 0, 0, 60, 3, 62, 0, 2, 2, 2, 279, 66, 16, 1, 20, 0, 7, 9, 32, 1411, 6, 3,
     106             :     27, 1, 5, 49, 0, 0, 0, 0, 0, 2, 10, 1, 1, 2, 3, 801, 3, 25, 5, 1, 1, 0, 632, 0, 14,
     107             :     18, 5, 8, 200, 4, 4, 22, 12, 0, 4, 1, 0, 2, 4, 9, 3, 16, 7, 2, 2, 213, 0, 2, 620,
     108             :     39303, 0, 1, 0, 2, 1, 183781, 1, 0, 0, 0, 94, 7, 3, 4, 0, 4, 306, 43, 352, 76, 34,
     109             :     13, 11, 0, 51, 1, 13, 19, 0, 26, 0, 7276, 4, 207, 31, 1, 2, 4, 6, 19, 8, 17, 4, 6,
     110             :     0, 1085, 0, 0, 0, 3, 489, 36, 1, 0, 1, 9420, 294, 28, 0, 57, 5, 0, 9, 2, 0, 1, 2,
     111             :     2, 0, 0, 9, 2, 29, 2, 2, 7, 0, 5, 490, 0, 7, 5, 0, 1, 8, 0, 0, 23255, 0, 1
     112             : };
     113             : 
     114             : // Test the example given on @see
     115             : // http://guru.multimedia.cx/small-tasks-for-ffmpeg/
     116           1 : int main(int argc, char **argv)
     117             : {
     118           1 :     int i, ret = 0;
     119             :     // Probabilities of symbols 0..4
     120           1 :     PTable val_counts[] = {
     121             :         {.value = 0, .prob = 1},
     122             :         {.value = 1, .prob = 2},
     123             :         {.value = 2, .prob = 5},
     124             :         {.value = 3, .prob = 10},
     125             :         {.value = 4, .prob = 21},
     126             :     };
     127             :     // Expected code lengths for each symbol
     128             :     static const HuffTable expected[] = {
     129             :         {.code = 0, .length = 3},
     130             :         {.code = 1, .length = 3},
     131             :         {.code = 2, .length = 3},
     132             :         {.code = 3, .length = 3},
     133             :         {.code = 4, .length = 1},
     134             :     };
     135             :     // Actual code lengths
     136             :     HuffTable distincts[5];
     137             : 
     138             :     // Build optimal huffman tree using an internal function, to allow for
     139             :     // smaller-than-normal test cases. This mutates val_counts by sorting.
     140           1 :     ff_mjpegenc_huffman_compute_bits(val_counts, distincts,
     141             :                                      FF_ARRAY_ELEMS(distincts), 3);
     142             : 
     143           6 :     for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) {
     144          10 :         if (distincts[i].code != expected[i].code ||
     145           5 :             distincts[i].length != expected[i].length) {
     146           0 :             fprintf(stderr,
     147             :                     "Built huffman does not equal expectations. "
     148             :                     "Expected: code %d probability %d, "
     149             :                     "Actual: code %d probability %d\n",
     150             :                     expected[i].code, expected[i].length,
     151             :                     distincts[i].code, distincts[i].length);
     152           0 :             ret = 1;
     153             :         }
     154             :     }
     155             : 
     156             :     // Check handling of zero probabilities
     157           1 :     if (check_lengths(16, 18, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes)))
     158           0 :         ret = 1;
     159             :     // Check skewed distribution over 256 without saturated lengths
     160           1 :     if (check_lengths(16, 41282, probs_skewed, FF_ARRAY_ELEMS(probs_skewed)))
     161           0 :         ret = 1;
     162             :     // Check skewed distribution over 256 with saturated lengths
     163           1 :     if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat)))
     164           0 :         ret = 1;
     165             : 
     166           1 :     return ret;
     167             : }

Generated by: LCOV version 1.13