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

   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 static int compare_by_prob(const void *a, const void *b)
  39 {
  40     PTable a_val = *(PTable *) a;
  41     PTable b_val = *(PTable *) b;
  42     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 static int compare_by_length(const void *a, const void *b)
  53 {
  54     HuffTable a_val = *(HuffTable *) a;
  55     HuffTable b_val = *(HuffTable *) b;
  56     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 void ff_mjpegenc_huffman_compute_bits(PTable *prob_table, HuffTable *distincts, int size, int max_length)
  81 {
  82     PackageMergerList list_a, list_b, *to = &list_a, *from = &list_b, *temp;
  83
  84     int times, i, j, k;
  85
  86     int nbits[257] = {0};
  87
  88     int min;
  89
  90     av_assert0(max_length > 0);
  91
  92     to->nitems = 0;
  93     from->nitems = 0;
  94     to->item_idx[0] = 0;
  95     from->item_idx[0] = 0;
  96     AV_QSORT(prob_table, size, PTable, compare_by_prob);
  97
  98     for (times = 0; times <= max_length; times++) {
  99         to->nitems = 0;
 100         to->item_idx[0] = 0;
 101
 102         j = 0;
 103         k = 0;
 104
 105         if (times < max_length) {
 106             i = 0;
 107         }
 108         while (i < size || j + 1 < from->nitems) {
 109             to->nitems++;
 110             to->item_idx[to->nitems] = to->item_idx[to->nitems - 1];
 111             if (i < size &&
 112                 (j + 1 >= from->nitems ||
 113                  prob_table[i].prob <
 114                      from->probability[j] + from->probability[j + 1])) {
 115                 to->items[to->item_idx[to->nitems]++] = prob_table[i].value;
 116                 to->probability[to->nitems - 1] = prob_table[i].prob;
 117                 i++;
 118             } else {
 119                 for (k = from->item_idx[j]; k < from->item_idx[j + 2]; k++) {
 120                     to->items[to->item_idx[to->nitems]++] = from->items[k];
 121                 }
 122                 to->probability[to->nitems - 1] =
 123                     from->probability[j] + from->probability[j + 1];
 124                 j += 2;
 125             }
 126         }
 127         temp = to;
 128         to = from;
 129         from = temp;
 130     }
 131
 132     min = (size - 1 < from->nitems) ? size - 1 : from->nitems;
 133     for (i = 0; i < from->item_idx[min]; i++) {
 134         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     j = 0;
 139     for (i = 0; i < 256; i++) {
 140         if (nbits[i] > 0) {
 141             distincts[j].code = i;
 142             distincts[j].length = nbits[i];
 143             j++;
 144         }
 145     }
 146 }
 147
 148 void ff_mjpeg_encode_huffman_init(MJpegEncHuffmanContext *s)
 149 {
 150     memset(s->val_count, 0, sizeof(s->val_count));
 151 }
 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 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     int nval = 0;
 166     PTable val_counts[257];
 167     HuffTable distincts[256];
 168
 169     for (i = 0; i < 256; i++) {
 170         if (s->val_count[i]) nval++;
 171     }
 172     av_assert0 (nval <= max_nval);
 173
 174     j = 0;
 175     for (i = 0; i < 256; i++) {
 176         if (s->val_count[i]) {
 177             val_counts[j].value = i;
 178             val_counts[j].prob = s->val_count[i];
 179             j++;
 180         }
 181     }
 182     val_counts[j].value = 256;
 183     val_counts[j].prob = 0;
 184     ff_mjpegenc_huffman_compute_bits(val_counts, distincts, nval + 1, 16);
 185     AV_QSORT(distincts, nval, HuffTable, compare_by_length);
 186
 187     memset(bits, 0, sizeof(bits[0]) * 17);
 188     for (i = 0; i < nval; i++) {
 189         val[i] = distincts[i].code;
 190         bits[distincts[i].length]++;
 191     }
 192 }