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