1/** 2 * @file 3 * Common code for Vorbis I encoder and decoder 4 * @author Denes Balatoni ( dbalatoni programozo hu ) 5 * 6 * This file is part of FFmpeg. 7 * 8 * FFmpeg is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * FFmpeg is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with FFmpeg; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 */ 22 23/** 24 * @file 25 * Common code for Vorbis I encoder and decoder 26 * @author Denes Balatoni ( dbalatoni programozo hu ) 27 */ 28 29#include "libavutil/common.h" 30 31#include "avcodec.h" 32#include "vorbis.h" 33 34 35/* Helper functions */ 36 37// x^(1/n) 38unsigned int ff_vorbis_nth_root(unsigned int x, unsigned int n) 39{ 40 unsigned int ret = 0, i, j; 41 42 do { 43 ++ret; 44 for (i = 0, j = ret; i < n - 1; i++) 45 j *= ret; 46 } while (j <= x); 47 48 return ret - 1; 49} 50 51// Generate vlc codes from vorbis huffman code lengths 52 53// the two bits[p] > 32 checks should be redundant, all calling code should 54// already ensure that, but since it allows overwriting the stack it seems 55// reasonable to check redundantly. 56int ff_vorbis_len2vlc(uint8_t *bits, uint32_t *codes, unsigned num) 57{ 58 uint32_t exit_at_level[33] = { 404 }; 59 unsigned i, j, p, code; 60 61 for (p = 0; (p < num) && (bits[p] == 0); ++p) 62 ; 63 if (p == num) 64 return 0; 65 66 codes[p] = 0; 67 if (bits[p] > 32) 68 return AVERROR_INVALIDDATA; 69 for (i = 0; i < bits[p]; ++i) 70 exit_at_level[i+1] = 1u << i; 71 72 ++p; 73 74 for (i = p; (i < num) && (bits[i] == 0); ++i) 75 ; 76 if (i == num) 77 return 0; 78 79 for (; p < num; ++p) { 80 if (bits[p] > 32) 81 return AVERROR_INVALIDDATA; 82 if (bits[p] == 0) 83 continue; 84 // find corresponding exit(node which the tree can grow further from) 85 for (i = bits[p]; i > 0; --i) 86 if (exit_at_level[i]) 87 break; 88 if (!i) // overspecified tree 89 return AVERROR_INVALIDDATA; 90 code = exit_at_level[i]; 91 exit_at_level[i] = 0; 92 // construct code (append 0s to end) and introduce new exits 93 for (j = i + 1 ;j <= bits[p]; ++j) 94 exit_at_level[j] = code + (1u << (j - 1)); 95 codes[p] = code; 96 } 97 98 //no exits should be left (underspecified tree - ie. unused valid vlcs - not allowed by SPEC) 99 for (p = 1; p < 33; p++) 100 if (exit_at_level[p]) 101 return AVERROR_INVALIDDATA; 102 103 return 0; 104} 105 106int ff_vorbis_ready_floor1_list(AVCodecContext *avctx, 107 vorbis_floor1_entry *list, int values) 108{ 109 int i; 110 list[0].sort = 0; 111 list[1].sort = 1; 112 for (i = 2; i < values; i++) { 113 int j; 114 list[i].low = 0; 115 list[i].high = 1; 116 list[i].sort = i; 117 for (j = 2; j < i; j++) { 118 int tmp = list[j].x; 119 if (tmp < list[i].x) { 120 if (tmp > list[list[i].low].x) 121 list[i].low = j; 122 } else { 123 if (tmp < list[list[i].high].x) 124 list[i].high = j; 125 } 126 } 127 } 128 for (i = 0; i < values - 1; i++) { 129 int j; 130 for (j = i + 1; j < values; j++) { 131 if (list[i].x == list[j].x) { 132 av_log(avctx, AV_LOG_ERROR, 133 "Duplicate value found in floor 1 X coordinates\n"); 134 return AVERROR_INVALIDDATA; 135 } 136 if (list[list[i].sort].x > list[list[j].sort].x) { 137 int tmp = list[i].sort; 138 list[i].sort = list[j].sort; 139 list[j].sort = tmp; 140 } 141 } 142 } 143 return 0; 144} 145 146static inline void render_line_unrolled(intptr_t x, int y, int x1, 147 intptr_t sy, int ady, int adx, 148 float *buf) 149{ 150 int err = -adx; 151 x -= x1 - 1; 152 buf += x1 - 1; 153 while (++x < 0) { 154 err += ady; 155 if (err >= 0) { 156 err += ady - adx; 157 y += sy; 158 buf[x++] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y)]; 159 } 160 buf[x] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y)]; 161 } 162 if (x <= 0) { 163 if (err + ady >= 0) 164 y += sy; 165 buf[x] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y)]; 166 } 167} 168 169static void render_line(int x0, int y0, int x1, int y1, float *buf) 170{ 171 int dy = y1 - y0; 172 int adx = x1 - x0; 173 int ady = FFABS(dy); 174 int sy = dy < 0 ? -1 : 1; 175 buf[x0] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y0)]; 176 if (ady*2 <= adx) { // optimized common case 177 render_line_unrolled(x0, y0, x1, sy, ady, adx, buf); 178 } else { 179 int base = dy / adx; 180 int x = x0; 181 int y = y0; 182 int err = -adx; 183 ady -= FFABS(base) * adx; 184 while (++x < x1) { 185 y += base; 186 err += ady; 187 if (err >= 0) { 188 err -= adx; 189 y += sy; 190 } 191 buf[x] = ff_vorbis_floor1_inverse_db_table[av_clip_uint8(y)]; 192 } 193 } 194} 195 196void ff_vorbis_floor1_render_list(vorbis_floor1_entry * list, int values, 197 uint16_t *y_list, int *flag, 198 int multiplier, float *out, int samples) 199{ 200 int lx, ly, i; 201 lx = 0; 202 ly = y_list[0] * multiplier; 203 for (i = 1; i < values; i++) { 204 int pos = list[i].sort; 205 if (flag[pos]) { 206 int x1 = list[pos].x; 207 int y1 = y_list[pos] * multiplier; 208 if (lx < samples) 209 render_line(lx, ly, FFMIN(x1,samples), y1, out); 210 lx = x1; 211 ly = y1; 212 } 213 if (lx >= samples) 214 break; 215 } 216 if (lx < samples) 217 render_line(lx, ly, samples, ly, out); 218} 219