blob: 0e63f8066b55f981e00475b47153872d753195cb
| 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 | } |
| 193 |