git.sesse.net Git - ffmpeg/blob - libavcodec/tests/mjpegenc_huffman.c

   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 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     int actual_length = 0, i, j, k, prob, length;
  40     int ret = 0;
  41     double cantor_measure = 0;
  42     av_assert0(nprobs <= 256);
  43
  44     for (i = 0; i < nprobs; i++) {
  45         val_counts[i] = (PTable){.value = i, .prob = probs[i]};
  46     }
  47
  48     ff_mjpegenc_huffman_compute_bits(val_counts, lengths, nprobs, L);
  49
  50     for (i = 0; i < nprobs; i++) {
  51         // Find the value's prob and length
  52         for (j = 0; j < nprobs; j++)
  53             if (val_counts[j].value == i) break;
  54         for (k = 0; k < nprobs; k++)
  55             if (lengths[k].code == i) break;
  56         if (!(j < nprobs && k < nprobs)) return 1;
  57         prob = val_counts[j].prob;
  58         length = lengths[k].length;
  59
  60         if (prob) {
  61             actual_length += prob * length;
  62             cantor_measure += 1. / (1 << length);
  63         }
  64
  65         if (length > L || length < 1) return 1;
  66     }
  67     // Check that the codes can be prefix-free.
  68     if (cantor_measure > 1) ret = 1;
  69     // Check that the total length is optimal
  70     if (actual_length != expected_length) ret = 1;
  71
  72     if (ret == 1) {
  73       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     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 int main(int argc, char **argv)
 117 {
 118     int i, ret = 0;
 119     // Probabilities of symbols 0..4
 120     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     ff_mjpegenc_huffman_compute_bits(val_counts, distincts,
 141                                      FF_ARRAY_ELEMS(distincts), 3);
 142
 143     for (i = 0; i < FF_ARRAY_ELEMS(distincts); i++) {
 144         if (distincts[i].code != expected[i].code ||
 145             distincts[i].length != expected[i].length) {
 146             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             ret = 1;
 153         }
 154     }
 155
 156     // Check handling of zero probabilities
 157     if (check_lengths(16, 18, probs_zeroes, FF_ARRAY_ELEMS(probs_zeroes)))
 158         ret = 1;
 159     // Check skewed distribution over 256 without saturated lengths
 160     if (check_lengths(16, 41282, probs_skewed, FF_ARRAY_ELEMS(probs_skewed)))
 161         ret = 1;
 162     // Check skewed distribution over 256 with saturated lengths
 163     if (check_lengths(16, 669904, probs_sat, FF_ARRAY_ELEMS(probs_sat)))
 164         ret = 1;
 165
 166     return ret;
 167 }