blob: df1141b7e75da08c5bfe50dee396e03532cdd906
| 1 | /* |
| 2 | * Copyright (c) 2006 Konstantin Shishkov |
| 3 | * Copyright (c) 2007 Loren Merritt |
| 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 | /** |
| 23 | * @file |
| 24 | * huffman tree builder and VLC generator |
| 25 | */ |
| 26 | |
| 27 | #include <stdint.h> |
| 28 | |
| 29 | #include "libavutil/qsort.h" |
| 30 | #include "libavutil/common.h" |
| 31 | |
| 32 | #include "avcodec.h" |
| 33 | #include "huffman.h" |
| 34 | #include "vlc.h" |
| 35 | |
| 36 | /* symbol for Huffman tree node */ |
| 37 | #define HNODE -1 |
| 38 | |
| 39 | typedef struct HeapElem { |
| 40 | uint64_t val; |
| 41 | int name; |
| 42 | } HeapElem; |
| 43 | |
| 44 | static void heap_sift(HeapElem *h, int root, int size) |
| 45 | { |
| 46 | while (root * 2 + 1 < size) { |
| 47 | int child = root * 2 + 1; |
| 48 | if (child < size - 1 && h[child].val > h[child+1].val) |
| 49 | child++; |
| 50 | if (h[root].val > h[child].val) { |
| 51 | FFSWAP(HeapElem, h[root], h[child]); |
| 52 | root = child; |
| 53 | } else |
| 54 | break; |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | int ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats, int stats_size, int skip0) |
| 59 | { |
| 60 | HeapElem *h = av_malloc_array(sizeof(*h), stats_size); |
| 61 | int *up = av_malloc_array(sizeof(*up) * 2, stats_size); |
| 62 | uint8_t *len = av_malloc_array(sizeof(*len) * 2, stats_size); |
| 63 | uint16_t *map= av_malloc_array(sizeof(*map), stats_size); |
| 64 | int offset, i, next; |
| 65 | int size = 0; |
| 66 | int ret = 0; |
| 67 | |
| 68 | if (!h || !up || !len || !map) { |
| 69 | ret = AVERROR(ENOMEM); |
| 70 | goto end; |
| 71 | } |
| 72 | |
| 73 | for (i = 0; i<stats_size; i++) { |
| 74 | dst[i] = 255; |
| 75 | if (stats[i] || !skip0) |
| 76 | map[size++] = i; |
| 77 | } |
| 78 | |
| 79 | for (offset = 1; ; offset <<= 1) { |
| 80 | for (i=0; i < size; i++) { |
| 81 | h[i].name = i; |
| 82 | h[i].val = (stats[map[i]] << 14) + offset; |
| 83 | } |
| 84 | for (i = size / 2 - 1; i >= 0; i--) |
| 85 | heap_sift(h, i, size); |
| 86 | |
| 87 | for (next = size; next < size * 2 - 1; next++) { |
| 88 | // merge the two smallest entries, and put it back in the heap |
| 89 | uint64_t min1v = h[0].val; |
| 90 | up[h[0].name] = next; |
| 91 | h[0].val = INT64_MAX; |
| 92 | heap_sift(h, 0, size); |
| 93 | up[h[0].name] = next; |
| 94 | h[0].name = next; |
| 95 | h[0].val += min1v; |
| 96 | heap_sift(h, 0, size); |
| 97 | } |
| 98 | |
| 99 | len[2 * size - 2] = 0; |
| 100 | for (i = 2 * size - 3; i >= size; i--) |
| 101 | len[i] = len[up[i]] + 1; |
| 102 | for (i = 0; i < size; i++) { |
| 103 | dst[map[i]] = len[up[i]] + 1; |
| 104 | if (dst[map[i]] >= 32) break; |
| 105 | } |
| 106 | if (i==size) break; |
| 107 | } |
| 108 | end: |
| 109 | av_free(h); |
| 110 | av_free(up); |
| 111 | av_free(len); |
| 112 | av_free(map); |
| 113 | return ret; |
| 114 | } |
| 115 | |
| 116 | static void get_tree_codes(uint32_t *bits, int16_t *lens, uint8_t *xlat, |
| 117 | Node *nodes, int node, |
| 118 | uint32_t pfx, int pl, int *pos, int no_zero_count) |
| 119 | { |
| 120 | int s; |
| 121 | |
| 122 | s = nodes[node].sym; |
| 123 | if (s != HNODE || (no_zero_count && !nodes[node].count)) { |
| 124 | bits[*pos] = pfx; |
| 125 | lens[*pos] = pl; |
| 126 | xlat[*pos] = s; |
| 127 | (*pos)++; |
| 128 | } else { |
| 129 | pfx <<= 1; |
| 130 | pl++; |
| 131 | get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0, pfx, pl, |
| 132 | pos, no_zero_count); |
| 133 | pfx |= 1; |
| 134 | get_tree_codes(bits, lens, xlat, nodes, nodes[node].n0 + 1, pfx, pl, |
| 135 | pos, no_zero_count); |
| 136 | } |
| 137 | } |
| 138 | |
| 139 | static int build_huff_tree(VLC *vlc, Node *nodes, int head, int flags, int nb_bits) |
| 140 | { |
| 141 | int no_zero_count = !(flags & FF_HUFFMAN_FLAG_ZERO_COUNT); |
| 142 | uint32_t bits[256]; |
| 143 | int16_t lens[256]; |
| 144 | uint8_t xlat[256]; |
| 145 | int pos = 0; |
| 146 | |
| 147 | get_tree_codes(bits, lens, xlat, nodes, head, 0, 0, |
| 148 | &pos, no_zero_count); |
| 149 | return ff_init_vlc_sparse(vlc, nb_bits, pos, lens, 2, 2, bits, 4, 4, xlat, 1, 1, 0); |
| 150 | } |
| 151 | |
| 152 | |
| 153 | /** |
| 154 | * nodes size must be 2*nb_codes |
| 155 | * first nb_codes nodes.count must be set |
| 156 | */ |
| 157 | int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, int nb_bits, |
| 158 | Node *nodes, HuffCmp cmp, int flags) |
| 159 | { |
| 160 | int i, j; |
| 161 | int cur_node; |
| 162 | int64_t sum = 0; |
| 163 | |
| 164 | for (i = 0; i < nb_codes; i++) { |
| 165 | nodes[i].sym = i; |
| 166 | nodes[i].n0 = -2; |
| 167 | sum += nodes[i].count; |
| 168 | } |
| 169 | |
| 170 | if (sum >> 31) { |
| 171 | av_log(avctx, AV_LOG_ERROR, |
| 172 | "Too high symbol frequencies. " |
| 173 | "Tree construction is not possible\n"); |
| 174 | return -1; |
| 175 | } |
| 176 | AV_QSORT(nodes, nb_codes, Node, cmp); |
| 177 | cur_node = nb_codes; |
| 178 | nodes[nb_codes*2-1].count = 0; |
| 179 | for (i = 0; i < nb_codes * 2 - 1; i += 2) { |
| 180 | uint32_t cur_count = nodes[i].count + nodes[i+1].count; |
| 181 | // find correct place to insert new node, and |
| 182 | // make space for the new node while at it |
| 183 | for(j = cur_node; j > i + 2; j--){ |
| 184 | if(cur_count > nodes[j-1].count || |
| 185 | (cur_count == nodes[j-1].count && |
| 186 | !(flags & FF_HUFFMAN_FLAG_HNODE_FIRST))) |
| 187 | break; |
| 188 | nodes[j] = nodes[j - 1]; |
| 189 | } |
| 190 | nodes[j].sym = HNODE; |
| 191 | nodes[j].count = cur_count; |
| 192 | nodes[j].n0 = i; |
| 193 | cur_node++; |
| 194 | } |
| 195 | if (build_huff_tree(vlc, nodes, nb_codes * 2 - 2, flags, nb_bits) < 0) { |
| 196 | av_log(avctx, AV_LOG_ERROR, "Error building tree\n"); |
| 197 | return -1; |
| 198 | } |
| 199 | return 0; |
| 200 | } |
| 201 |