The Tor Browser / file comparison

comparison: media/libvorbis/lib/vorbis_floor1.c

media/libvorbis/lib/vorbis_floor1.c

branch
TOR_BUG_9701
changeset 8
97036ab72558
equal deleted inserted replaced
-1:000000000000 0:219ca94df041
1 /********************************************************************
2 * *
3 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS *
5 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. *
7 * *
8 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009 *
9 * by the Xiph.Org Foundation http://www.xiph.org/ *
10 * *
11 ********************************************************************
12
13 function: floor backend 1 implementation
14 last mod: $Id: floor1.c 19031 2013-12-03 19:20:50Z tterribe $
15
16 ********************************************************************/
17
18 #include <stdlib.h>
19 #include <string.h>
20 #include <math.h>
21 #include <ogg/ogg.h>
22 #include "vorbis/codec.h"
23 #include "codec_internal.h"
24 #include "registry.h"
25 #include "codebook.h"
26 #include "misc.h"
27 #include "scales.h"
28
29 #include <stdio.h>
30
31 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
32
33 typedef struct lsfit_acc{
34 int x0;
35 int x1;
36
37 int xa;
38 int ya;
39 int x2a;
40 int y2a;
41 int xya;
42 int an;
43
44 int xb;
45 int yb;
46 int x2b;
47 int y2b;
48 int xyb;
49 int bn;
50 } lsfit_acc;
51
52 /***********************************************/
53
54 static void floor1_free_info(vorbis_info_floor *i){
55 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
56 if(info){
57 memset(info,0,sizeof(*info));
58 _ogg_free(info);
59 }
60 }
61
62 static void floor1_free_look(vorbis_look_floor *i){
63 vorbis_look_floor1 *look=(vorbis_look_floor1 *)i;
64 if(look){
65 /*fprintf(stderr,"floor 1 bit usage %f:%f (%f total)\n",
66 (float)look->phrasebits/look->frames,
67 (float)look->postbits/look->frames,
68 (float)(look->postbits+look->phrasebits)/look->frames);*/
69
70 memset(look,0,sizeof(*look));
71 _ogg_free(look);
72 }
73 }
74
75 static int ilog(unsigned int v){
76 int ret=0;
77 while(v){
78 ret++;
79 v>>=1;
80 }
81 return(ret);
82 }
83
84 static int ilog2(unsigned int v){
85 int ret=0;
86 if(v)--v;
87 while(v){
88 ret++;
89 v>>=1;
90 }
91 return(ret);
92 }
93
94 static void floor1_pack (vorbis_info_floor *i,oggpack_buffer *opb){
95 vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
96 int j,k;
97 int count=0;
98 int rangebits;
99 int maxposit=info->postlist[1];
100 int maxclass=-1;
101
102 /* save out partitions */
103 oggpack_write(opb,info->partitions,5); /* only 0 to 31 legal */
104 for(j=0;j<info->partitions;j++){
105 oggpack_write(opb,info->partitionclass[j],4); /* only 0 to 15 legal */
106 if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
107 }
108
109 /* save out partition classes */
110 for(j=0;j<maxclass+1;j++){
111 oggpack_write(opb,info->class_dim[j]-1,3); /* 1 to 8 */
112 oggpack_write(opb,info->class_subs[j],2); /* 0 to 3 */
113 if(info->class_subs[j])oggpack_write(opb,info->class_book[j],8);
114 for(k=0;k<(1<<info->class_subs[j]);k++)
115 oggpack_write(opb,info->class_subbook[j][k]+1,8);
116 }
117
118 /* save out the post list */
119 oggpack_write(opb,info->mult-1,2); /* only 1,2,3,4 legal now */
120 oggpack_write(opb,ilog2(maxposit),4);
121 rangebits=ilog2(maxposit);
122
123 for(j=0,k=0;j<info->partitions;j++){
124 count+=info->class_dim[info->partitionclass[j]];
125 for(;k<count;k++)
126 oggpack_write(opb,info->postlist[k+2],rangebits);
127 }
128 }
129
130 static int icomp(const void *a,const void *b){
131 return(**(int **)a-**(int **)b);
132 }
133
134 static vorbis_info_floor *floor1_unpack (vorbis_info *vi,oggpack_buffer *opb){
135 codec_setup_info *ci=vi->codec_setup;
136 int j,k,count=0,maxclass=-1,rangebits;
137
138 vorbis_info_floor1 *info=_ogg_calloc(1,sizeof(*info));
139 /* read partitions */
140 info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */
141 for(j=0;j<info->partitions;j++){
142 info->partitionclass[j]=oggpack_read(opb,4); /* only 0 to 15 legal */
143 if(info->partitionclass[j]<0)goto err_out;
144 if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
145 }
146
147 /* read partition classes */
148 for(j=0;j<maxclass+1;j++){
149 info->class_dim[j]=oggpack_read(opb,3)+1; /* 1 to 8 */
150 info->class_subs[j]=oggpack_read(opb,2); /* 0,1,2,3 bits */
151 if(info->class_subs[j]<0)
152 goto err_out;
153 if(info->class_subs[j])info->class_book[j]=oggpack_read(opb,8);
154 if(info->class_book[j]<0 || info->class_book[j]>=ci->books)
155 goto err_out;
156 for(k=0;k<(1<<info->class_subs[j]);k++){
157 info->class_subbook[j][k]=oggpack_read(opb,8)-1;
158 if(info->class_subbook[j][k]<-1 || info->class_subbook[j][k]>=ci->books)
159 goto err_out;
160 }
161 }
162
163 /* read the post list */
164 info->mult=oggpack_read(opb,2)+1; /* only 1,2,3,4 legal now */
165 rangebits=oggpack_read(opb,4);
166 if(rangebits<0)goto err_out;
167
168 for(j=0,k=0;j<info->partitions;j++){
169 count+=info->class_dim[info->partitionclass[j]];
170 if(count>VIF_POSIT) goto err_out;
171 for(;k<count;k++){
172 int t=info->postlist[k+2]=oggpack_read(opb,rangebits);
173 if(t<0 || t>=(1<<rangebits))
174 goto err_out;
175 }
176 }
177 info->postlist[0]=0;
178 info->postlist[1]=1<<rangebits;
179
180 /* don't allow repeated values in post list as they'd result in
181 zero-length segments */
182 {
183 int *sortpointer[VIF_POSIT+2];
184 for(j=0;j<count+2;j++)sortpointer[j]=info->postlist+j;
185 qsort(sortpointer,count+2,sizeof(*sortpointer),icomp);
186
187 for(j=1;j<count+2;j++)
188 if(*sortpointer[j-1]==*sortpointer[j])goto err_out;
189 }
190
191 return(info);
192
193 err_out:
194 floor1_free_info(info);
195 return(NULL);
196 }
197
198 static vorbis_look_floor *floor1_look(vorbis_dsp_state *vd,
199 vorbis_info_floor *in){
200
201 int *sortpointer[VIF_POSIT+2];
202 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
203 vorbis_look_floor1 *look=_ogg_calloc(1,sizeof(*look));
204 int i,j,n=0;
205
206 (void)vd;
207
208 look->vi=info;
209 look->n=info->postlist[1];
210
211 /* we drop each position value in-between already decoded values,
212 and use linear interpolation to predict each new value past the
213 edges. The positions are read in the order of the position
214 list... we precompute the bounding positions in the lookup. Of
215 course, the neighbors can change (if a position is declined), but
216 this is an initial mapping */
217
218 for(i=0;i<info->partitions;i++)n+=info->class_dim[info->partitionclass[i]];
219 n+=2;
220 look->posts=n;
221
222 /* also store a sorted position index */
223 for(i=0;i<n;i++)sortpointer[i]=info->postlist+i;
224 qsort(sortpointer,n,sizeof(*sortpointer),icomp);
225
226 /* points from sort order back to range number */
227 for(i=0;i<n;i++)look->forward_index[i]=sortpointer[i]-info->postlist;
228 /* points from range order to sorted position */
229 for(i=0;i<n;i++)look->reverse_index[look->forward_index[i]]=i;
230 /* we actually need the post values too */
231 for(i=0;i<n;i++)look->sorted_index[i]=info->postlist[look->forward_index[i]];
232
233 /* quantize values to multiplier spec */
234 switch(info->mult){
235 case 1: /* 1024 -> 256 */
236 look->quant_q=256;
237 break;
238 case 2: /* 1024 -> 128 */
239 look->quant_q=128;
240 break;
241 case 3: /* 1024 -> 86 */
242 look->quant_q=86;
243 break;
244 case 4: /* 1024 -> 64 */
245 look->quant_q=64;
246 break;
247 }
248
249 /* discover our neighbors for decode where we don't use fit flags
250 (that would push the neighbors outward) */
251 for(i=0;i<n-2;i++){
252 int lo=0;
253 int hi=1;
254 int lx=0;
255 int hx=look->n;
256 int currentx=info->postlist[i+2];
257 for(j=0;j<i+2;j++){
258 int x=info->postlist[j];
259 if(x>lx && x<currentx){
260 lo=j;
261 lx=x;
262 }
263 if(x<hx && x>currentx){
264 hi=j;
265 hx=x;
266 }
267 }
268 look->loneighbor[i]=lo;
269 look->hineighbor[i]=hi;
270 }
271
272 return(look);
273 }
274
275 static int render_point(int x0,int x1,int y0,int y1,int x){
276 y0&=0x7fff; /* mask off flag */
277 y1&=0x7fff;
278
279 {
280 int dy=y1-y0;
281 int adx=x1-x0;
282 int ady=abs(dy);
283 int err=ady*(x-x0);
284
285 int off=err/adx;
286 if(dy<0)return(y0-off);
287 return(y0+off);
288 }
289 }
290
291 static int vorbis_dBquant(const float *x){
292 int i= *x*7.3142857f+1023.5f;
293 if(i>1023)return(1023);
294 if(i<0)return(0);
295 return i;
296 }
297
298 static const float FLOOR1_fromdB_LOOKUP[256]={
299 1.0649863e-07F, 1.1341951e-07F, 1.2079015e-07F, 1.2863978e-07F,
300 1.3699951e-07F, 1.4590251e-07F, 1.5538408e-07F, 1.6548181e-07F,
301 1.7623575e-07F, 1.8768855e-07F, 1.9988561e-07F, 2.128753e-07F,
302 2.2670913e-07F, 2.4144197e-07F, 2.5713223e-07F, 2.7384213e-07F,
303 2.9163793e-07F, 3.1059021e-07F, 3.3077411e-07F, 3.5226968e-07F,
304 3.7516214e-07F, 3.9954229e-07F, 4.2550680e-07F, 4.5315863e-07F,
305 4.8260743e-07F, 5.1396998e-07F, 5.4737065e-07F, 5.8294187e-07F,
306 6.2082472e-07F, 6.6116941e-07F, 7.0413592e-07F, 7.4989464e-07F,
307 7.9862701e-07F, 8.5052630e-07F, 9.0579828e-07F, 9.6466216e-07F,
308 1.0273513e-06F, 1.0941144e-06F, 1.1652161e-06F, 1.2409384e-06F,
309 1.3215816e-06F, 1.4074654e-06F, 1.4989305e-06F, 1.5963394e-06F,
310 1.7000785e-06F, 1.8105592e-06F, 1.9282195e-06F, 2.0535261e-06F,
311 2.1869758e-06F, 2.3290978e-06F, 2.4804557e-06F, 2.6416497e-06F,
312 2.8133190e-06F, 2.9961443e-06F, 3.1908506e-06F, 3.3982101e-06F,
313 3.6190449e-06F, 3.8542308e-06F, 4.1047004e-06F, 4.3714470e-06F,
314 4.6555282e-06F, 4.9580707e-06F, 5.2802740e-06F, 5.6234160e-06F,
315 5.9888572e-06F, 6.3780469e-06F, 6.7925283e-06F, 7.2339451e-06F,
316 7.7040476e-06F, 8.2047000e-06F, 8.7378876e-06F, 9.3057248e-06F,
317 9.9104632e-06F, 1.0554501e-05F, 1.1240392e-05F, 1.1970856e-05F,
318 1.2748789e-05F, 1.3577278e-05F, 1.4459606e-05F, 1.5399272e-05F,
319 1.6400004e-05F, 1.7465768e-05F, 1.8600792e-05F, 1.9809576e-05F,
320 2.1096914e-05F, 2.2467911e-05F, 2.3928002e-05F, 2.5482978e-05F,
321 2.7139006e-05F, 2.8902651e-05F, 3.0780908e-05F, 3.2781225e-05F,
322 3.4911534e-05F, 3.7180282e-05F, 3.9596466e-05F, 4.2169667e-05F,
323 4.4910090e-05F, 4.7828601e-05F, 5.0936773e-05F, 5.4246931e-05F,
324 5.7772202e-05F, 6.1526565e-05F, 6.5524908e-05F, 6.9783085e-05F,
325 7.4317983e-05F, 7.9147585e-05F, 8.4291040e-05F, 8.9768747e-05F,
326 9.5602426e-05F, 0.00010181521F, 0.00010843174F, 0.00011547824F,
327 0.00012298267F, 0.00013097477F, 0.00013948625F, 0.00014855085F,
328 0.00015820453F, 0.00016848555F, 0.00017943469F, 0.00019109536F,
329 0.00020351382F, 0.00021673929F, 0.00023082423F, 0.00024582449F,
330 0.00026179955F, 0.00027881276F, 0.00029693158F, 0.00031622787F,
331 0.00033677814F, 0.00035866388F, 0.00038197188F, 0.00040679456F,
332 0.00043323036F, 0.00046138411F, 0.00049136745F, 0.00052329927F,
333 0.00055730621F, 0.00059352311F, 0.00063209358F, 0.00067317058F,
334 0.00071691700F, 0.00076350630F, 0.00081312324F, 0.00086596457F,
335 0.00092223983F, 0.00098217216F, 0.0010459992F, 0.0011139742F,
336 0.0011863665F, 0.0012634633F, 0.0013455702F, 0.0014330129F,
337 0.0015261382F, 0.0016253153F, 0.0017309374F, 0.0018434235F,
338 0.0019632195F, 0.0020908006F, 0.0022266726F, 0.0023713743F,
339 0.0025254795F, 0.0026895994F, 0.0028643847F, 0.0030505286F,
340 0.0032487691F, 0.0034598925F, 0.0036847358F, 0.0039241906F,
341 0.0041792066F, 0.0044507950F, 0.0047400328F, 0.0050480668F,
342 0.0053761186F, 0.0057254891F, 0.0060975636F, 0.0064938176F,
343 0.0069158225F, 0.0073652516F, 0.0078438871F, 0.0083536271F,
344 0.0088964928F, 0.009474637F, 0.010090352F, 0.010746080F,
345 0.011444421F, 0.012188144F, 0.012980198F, 0.013823725F,
346 0.014722068F, 0.015678791F, 0.016697687F, 0.017782797F,
347 0.018938423F, 0.020169149F, 0.021479854F, 0.022875735F,
348 0.024362330F, 0.025945531F, 0.027631618F, 0.029427276F,
349 0.031339626F, 0.033376252F, 0.035545228F, 0.037855157F,
350 0.040315199F, 0.042935108F, 0.045725273F, 0.048696758F,
351 0.051861348F, 0.055231591F, 0.058820850F, 0.062643361F,
352 0.066714279F, 0.071049749F, 0.075666962F, 0.080584227F,
353 0.085821044F, 0.091398179F, 0.097337747F, 0.10366330F,
354 0.11039993F, 0.11757434F, 0.12521498F, 0.13335215F,
355 0.14201813F, 0.15124727F, 0.16107617F, 0.17154380F,
356 0.18269168F, 0.19456402F, 0.20720788F, 0.22067342F,
357 0.23501402F, 0.25028656F, 0.26655159F, 0.28387361F,
358 0.30232132F, 0.32196786F, 0.34289114F, 0.36517414F,
359 0.38890521F, 0.41417847F, 0.44109412F, 0.46975890F,
360 0.50028648F, 0.53279791F, 0.56742212F, 0.60429640F,
361 0.64356699F, 0.68538959F, 0.72993007F, 0.77736504F,
362 0.82788260F, 0.88168307F, 0.9389798F, 1.F,
363 };
364
365 static void render_line(int n, int x0,int x1,int y0,int y1,float *d){
366 int dy=y1-y0;
367 int adx=x1-x0;
368 int ady=abs(dy);
369 int base=dy/adx;
370 int sy=(dy<0?base-1:base+1);
371 int x=x0;
372 int y=y0;
373 int err=0;
374
375 ady-=abs(base*adx);
376
377 if(n>x1)n=x1;
378
379 if(x<n)
380 d[x]*=FLOOR1_fromdB_LOOKUP[y];
381
382 while(++x<n){
383 err=err+ady;
384 if(err>=adx){
385 err-=adx;
386 y+=sy;
387 }else{
388 y+=base;
389 }
390 d[x]*=FLOOR1_fromdB_LOOKUP[y];
391 }
392 }
393
394 static void render_line0(int n, int x0,int x1,int y0,int y1,int *d){
395 int dy=y1-y0;
396 int adx=x1-x0;
397 int ady=abs(dy);
398 int base=dy/adx;
399 int sy=(dy<0?base-1:base+1);
400 int x=x0;
401 int y=y0;
402 int err=0;
403
404 ady-=abs(base*adx);
405
406 if(n>x1)n=x1;
407
408 if(x<n)
409 d[x]=y;
410
411 while(++x<n){
412 err=err+ady;
413 if(err>=adx){
414 err-=adx;
415 y+=sy;
416 }else{
417 y+=base;
418 }
419 d[x]=y;
420 }
421 }
422
423 /* the floor has already been filtered to only include relevant sections */
424 static int accumulate_fit(const float *flr,const float *mdct,
425 int x0, int x1,lsfit_acc *a,
426 int n,vorbis_info_floor1 *info){
427 long i;
428
429 int xa=0,ya=0,x2a=0,y2a=0,xya=0,na=0, xb=0,yb=0,x2b=0,y2b=0,xyb=0,nb=0;
430
431 memset(a,0,sizeof(*a));
432 a->x0=x0;
433 a->x1=x1;
434 if(x1>=n)x1=n-1;
435
436 for(i=x0;i<=x1;i++){
437 int quantized=vorbis_dBquant(flr+i);
438 if(quantized){
439 if(mdct[i]+info->twofitatten>=flr[i]){
440 xa += i;
441 ya += quantized;
442 x2a += i*i;
443 y2a += quantized*quantized;
444 xya += i*quantized;
445 na++;
446 }else{
447 xb += i;
448 yb += quantized;
449 x2b += i*i;
450 y2b += quantized*quantized;
451 xyb += i*quantized;
452 nb++;
453 }
454 }
455 }
456
457 a->xa=xa;
458 a->ya=ya;
459 a->x2a=x2a;
460 a->y2a=y2a;
461 a->xya=xya;
462 a->an=na;
463
464 a->xb=xb;
465 a->yb=yb;
466 a->x2b=x2b;
467 a->y2b=y2b;
468 a->xyb=xyb;
469 a->bn=nb;
470
471 return(na);
472 }
473
474 static int fit_line(lsfit_acc *a,int fits,int *y0,int *y1,
475 vorbis_info_floor1 *info){
476 double xb=0,yb=0,x2b=0,y2b=0,xyb=0,bn=0;
477 int i;
478 int x0=a[0].x0;
479 int x1=a[fits-1].x1;
480
481 for(i=0;i<fits;i++){
482 double weight = (a[i].bn+a[i].an)*info->twofitweight/(a[i].an+1)+1.;
483
484 xb+=a[i].xb + a[i].xa * weight;
485 yb+=a[i].yb + a[i].ya * weight;
486 x2b+=a[i].x2b + a[i].x2a * weight;
487 y2b+=a[i].y2b + a[i].y2a * weight;
488 xyb+=a[i].xyb + a[i].xya * weight;
489 bn+=a[i].bn + a[i].an * weight;
490 }
491
492 if(*y0>=0){
493 xb+= x0;
494 yb+= *y0;
495 x2b+= x0 * x0;
496 y2b+= *y0 * *y0;
497 xyb+= *y0 * x0;
498 bn++;
499 }
500
501 if(*y1>=0){
502 xb+= x1;
503 yb+= *y1;
504 x2b+= x1 * x1;
505 y2b+= *y1 * *y1;
506 xyb+= *y1 * x1;
507 bn++;
508 }
509
510 {
511 double denom=(bn*x2b-xb*xb);
512
513 if(denom>0.){
514 double a=(yb*x2b-xyb*xb)/denom;
515 double b=(bn*xyb-xb*yb)/denom;
516 *y0=rint(a+b*x0);
517 *y1=rint(a+b*x1);
518
519 /* limit to our range! */
520 if(*y0>1023)*y0=1023;
521 if(*y1>1023)*y1=1023;
522 if(*y0<0)*y0=0;
523 if(*y1<0)*y1=0;
524
525 return 0;
526 }else{
527 *y0=0;
528 *y1=0;
529 return 1;
530 }
531 }
532 }
533
534 static int inspect_error(int x0,int x1,int y0,int y1,const float *mask,
535 const float *mdct,
536 vorbis_info_floor1 *info){
537 int dy=y1-y0;
538 int adx=x1-x0;
539 int ady=abs(dy);
540 int base=dy/adx;
541 int sy=(dy<0?base-1:base+1);
542 int x=x0;
543 int y=y0;
544 int err=0;
545 int val=vorbis_dBquant(mask+x);
546 int mse=0;
547 int n=0;
548
549 ady-=abs(base*adx);
550
551 mse=(y-val);
552 mse*=mse;
553 n++;
554 if(mdct[x]+info->twofitatten>=mask[x]){
555 if(y+info->maxover<val)return(1);
556 if(y-info->maxunder>val)return(1);
557 }
558
559 while(++x<x1){
560 err=err+ady;
561 if(err>=adx){
562 err-=adx;
563 y+=sy;
564 }else{
565 y+=base;
566 }
567
568 val=vorbis_dBquant(mask+x);
569 mse+=((y-val)*(y-val));
570 n++;
571 if(mdct[x]+info->twofitatten>=mask[x]){
572 if(val){
573 if(y+info->maxover<val)return(1);
574 if(y-info->maxunder>val)return(1);
575 }
576 }
577 }
578
579 if(info->maxover*info->maxover/n>info->maxerr)return(0);
580 if(info->maxunder*info->maxunder/n>info->maxerr)return(0);
581 if(mse/n>info->maxerr)return(1);
582 return(0);
583 }
584
585 static int post_Y(int *A,int *B,int pos){
586 if(A[pos]<0)
587 return B[pos];
588 if(B[pos]<0)
589 return A[pos];
590
591 return (A[pos]+B[pos])>>1;
592 }
593
594 int *floor1_fit(vorbis_block *vb,vorbis_look_floor1 *look,
595 const float *logmdct, /* in */
596 const float *logmask){
597 long i,j;
598 vorbis_info_floor1 *info=look->vi;
599 long n=look->n;
600 long posts=look->posts;
601 long nonzero=0;
602 lsfit_acc fits[VIF_POSIT+1];
603 int fit_valueA[VIF_POSIT+2]; /* index by range list position */
604 int fit_valueB[VIF_POSIT+2]; /* index by range list position */
605
606 int loneighbor[VIF_POSIT+2]; /* sorted index of range list position (+2) */
607 int hineighbor[VIF_POSIT+2];
608 int *output=NULL;
609 int memo[VIF_POSIT+2];
610
611 for(i=0;i<posts;i++)fit_valueA[i]=-200; /* mark all unused */
612 for(i=0;i<posts;i++)fit_valueB[i]=-200; /* mark all unused */
613 for(i=0;i<posts;i++)loneighbor[i]=0; /* 0 for the implicit 0 post */
614 for(i=0;i<posts;i++)hineighbor[i]=1; /* 1 for the implicit post at n */
615 for(i=0;i<posts;i++)memo[i]=-1; /* no neighbor yet */
616
617 /* quantize the relevant floor points and collect them into line fit
618 structures (one per minimal division) at the same time */
619 if(posts==0){
620 nonzero+=accumulate_fit(logmask,logmdct,0,n,fits,n,info);
621 }else{
622 for(i=0;i<posts-1;i++)
623 nonzero+=accumulate_fit(logmask,logmdct,look->sorted_index[i],
624 look->sorted_index[i+1],fits+i,
625 n,info);
626 }
627
628 if(nonzero){
629 /* start by fitting the implicit base case.... */
630 int y0=-200;
631 int y1=-200;
632 fit_line(fits,posts-1,&y0,&y1,info);
633
634 fit_valueA[0]=y0;
635 fit_valueB[0]=y0;
636 fit_valueB[1]=y1;
637 fit_valueA[1]=y1;
638
639 /* Non degenerate case */
640 /* start progressive splitting. This is a greedy, non-optimal
641 algorithm, but simple and close enough to the best
642 answer. */
643 for(i=2;i<posts;i++){
644 int sortpos=look->reverse_index[i];
645 int ln=loneighbor[sortpos];
646 int hn=hineighbor[sortpos];
647
648 /* eliminate repeat searches of a particular range with a memo */
649 if(memo[ln]!=hn){
650 /* haven't performed this error search yet */
651 int lsortpos=look->reverse_index[ln];
652 int hsortpos=look->reverse_index[hn];
653 memo[ln]=hn;
654
655 {
656 /* A note: we want to bound/minimize *local*, not global, error */
657 int lx=info->postlist[ln];
658 int hx=info->postlist[hn];
659 int ly=post_Y(fit_valueA,fit_valueB,ln);
660 int hy=post_Y(fit_valueA,fit_valueB,hn);
661
662 if(ly==-1 || hy==-1){
663 exit(1);
664 }
665
666 if(inspect_error(lx,hx,ly,hy,logmask,logmdct,info)){
667 /* outside error bounds/begin search area. Split it. */
668 int ly0=-200;
669 int ly1=-200;
670 int hy0=-200;
671 int hy1=-200;
672 int ret0=fit_line(fits+lsortpos,sortpos-lsortpos,&ly0,&ly1,info);
673 int ret1=fit_line(fits+sortpos,hsortpos-sortpos,&hy0,&hy1,info);
674
675 if(ret0){
676 ly0=ly;
677 ly1=hy0;
678 }
679 if(ret1){
680 hy0=ly1;
681 hy1=hy;
682 }
683
684 if(ret0 && ret1){
685 fit_valueA[i]=-200;
686 fit_valueB[i]=-200;
687 }else{
688 /* store new edge values */
689 fit_valueB[ln]=ly0;
690 if(ln==0)fit_valueA[ln]=ly0;
691 fit_valueA[i]=ly1;
692 fit_valueB[i]=hy0;
693 fit_valueA[hn]=hy1;
694 if(hn==1)fit_valueB[hn]=hy1;
695
696 if(ly1>=0 || hy0>=0){
697 /* store new neighbor values */
698 for(j=sortpos-1;j>=0;j--)
699 if(hineighbor[j]==hn)
700 hineighbor[j]=i;
701 else
702 break;
703 for(j=sortpos+1;j<posts;j++)
704 if(loneighbor[j]==ln)
705 loneighbor[j]=i;
706 else
707 break;
708 }
709 }
710 }else{
711 fit_valueA[i]=-200;
712 fit_valueB[i]=-200;
713 }
714 }
715 }
716 }
717
718 output=_vorbis_block_alloc(vb,sizeof(*output)*posts);
719
720 output[0]=post_Y(fit_valueA,fit_valueB,0);
721 output[1]=post_Y(fit_valueA,fit_valueB,1);
722
723 /* fill in posts marked as not using a fit; we will zero
724 back out to 'unused' when encoding them so long as curve
725 interpolation doesn't force them into use */
726 for(i=2;i<posts;i++){
727 int ln=look->loneighbor[i-2];
728 int hn=look->hineighbor[i-2];
729 int x0=info->postlist[ln];
730 int x1=info->postlist[hn];
731 int y0=output[ln];
732 int y1=output[hn];
733
734 int predicted=render_point(x0,x1,y0,y1,info->postlist[i]);
735 int vx=post_Y(fit_valueA,fit_valueB,i);
736
737 if(vx>=0 && predicted!=vx){
738 output[i]=vx;
739 }else{
740 output[i]= predicted|0x8000;
741 }
742 }
743 }
744
745 return(output);
746
747 }
748
749 int *floor1_interpolate_fit(vorbis_block *vb,vorbis_look_floor1 *look,
750 int *A,int *B,
751 int del){
752
753 long i;
754 long posts=look->posts;
755 int *output=NULL;
756
757 if(A && B){
758 output=_vorbis_block_alloc(vb,sizeof(*output)*posts);
759
760 /* overly simpleminded--- look again post 1.2 */
761 for(i=0;i<posts;i++){
762 output[i]=((65536-del)*(A[i]&0x7fff)+del*(B[i]&0x7fff)+32768)>>16;
763 if(A[i]&0x8000 && B[i]&0x8000)output[i]|=0x8000;
764 }
765 }
766
767 return(output);
768 }
769
770
771 int floor1_encode(oggpack_buffer *opb,vorbis_block *vb,
772 vorbis_look_floor1 *look,
773 int *post,int *ilogmask){
774
775 long i,j;
776 vorbis_info_floor1 *info=look->vi;
777 long posts=look->posts;
778 codec_setup_info *ci=vb->vd->vi->codec_setup;
779 int out[VIF_POSIT+2];
780 static_codebook **sbooks=ci->book_param;
781 codebook *books=ci->fullbooks;
782
783 /* quantize values to multiplier spec */
784 if(post){
785 for(i=0;i<posts;i++){
786 int val=post[i]&0x7fff;
787 switch(info->mult){
788 case 1: /* 1024 -> 256 */
789 val>>=2;
790 break;
791 case 2: /* 1024 -> 128 */
792 val>>=3;
793 break;
794 case 3: /* 1024 -> 86 */
795 val/=12;
796 break;
797 case 4: /* 1024 -> 64 */
798 val>>=4;
799 break;
800 }
801 post[i]=val | (post[i]&0x8000);
802 }
803
804 out[0]=post[0];
805 out[1]=post[1];
806
807 /* find prediction values for each post and subtract them */
808 for(i=2;i<posts;i++){
809 int ln=look->loneighbor[i-2];
810 int hn=look->hineighbor[i-2];
811 int x0=info->postlist[ln];
812 int x1=info->postlist[hn];
813 int y0=post[ln];
814 int y1=post[hn];
815
816 int predicted=render_point(x0,x1,y0,y1,info->postlist[i]);
817
818 if((post[i]&0x8000) || (predicted==post[i])){
819 post[i]=predicted|0x8000; /* in case there was roundoff jitter
820 in interpolation */
821 out[i]=0;
822 }else{
823 int headroom=(look->quant_q-predicted<predicted?
824 look->quant_q-predicted:predicted);
825
826 int val=post[i]-predicted;
827
828 /* at this point the 'deviation' value is in the range +/- max
829 range, but the real, unique range can always be mapped to
830 only [0-maxrange). So we want to wrap the deviation into
831 this limited range, but do it in the way that least screws
832 an essentially gaussian probability distribution. */
833
834 if(val<0)
835 if(val<-headroom)
836 val=headroom-val-1;
837 else
838 val=-1-(val<<1);
839 else
840 if(val>=headroom)
841 val= val+headroom;
842 else
843 val<<=1;
844
845 out[i]=val;
846 post[ln]&=0x7fff;
847 post[hn]&=0x7fff;
848 }
849 }
850
851 /* we have everything we need. pack it out */
852 /* mark nontrivial floor */
853 oggpack_write(opb,1,1);
854
855 /* beginning/end post */
856 look->frames++;
857 look->postbits+=ilog(look->quant_q-1)*2;
858 oggpack_write(opb,out[0],ilog(look->quant_q-1));
859 oggpack_write(opb,out[1],ilog(look->quant_q-1));
860
861
862 /* partition by partition */
863 for(i=0,j=2;i<info->partitions;i++){
864 int class=info->partitionclass[i];
865 int cdim=info->class_dim[class];
866 int csubbits=info->class_subs[class];
867 int csub=1<<csubbits;
868 int bookas[8]={0,0,0,0,0,0,0,0};
869 int cval=0;
870 int cshift=0;
871 int k,l;
872
873 /* generate the partition's first stage cascade value */
874 if(csubbits){
875 int maxval[8];
876 for(k=0;k<csub;k++){
877 int booknum=info->class_subbook[class][k];
878 if(booknum<0){
879 maxval[k]=1;
880 }else{
881 maxval[k]=sbooks[info->class_subbook[class][k]]->entries;
882 }
883 }
884 for(k=0;k<cdim;k++){
885 for(l=0;l<csub;l++){
886 int val=out[j+k];
887 if(val<maxval[l]){
888 bookas[k]=l;
889 break;
890 }
891 }
892 cval|= bookas[k]<<cshift;
893 cshift+=csubbits;
894 }
895 /* write it */
896 look->phrasebits+=
897 vorbis_book_encode(books+info->class_book[class],cval,opb);
898
899 #ifdef TRAIN_FLOOR1
900 {
901 FILE *of;
902 char buffer[80];
903 sprintf(buffer,"line_%dx%ld_class%d.vqd",
904 vb->pcmend/2,posts-2,class);
905 of=fopen(buffer,"a");
906 fprintf(of,"%d\n",cval);
907 fclose(of);
908 }
909 #endif
910 }
911
912 /* write post values */
913 for(k=0;k<cdim;k++){
914 int book=info->class_subbook[class][bookas[k]];
915 if(book>=0){
916 /* hack to allow training with 'bad' books */
917 if(out[j+k]<(books+book)->entries)
918 look->postbits+=vorbis_book_encode(books+book,
919 out[j+k],opb);
920 /*else
921 fprintf(stderr,"+!");*/
922
923 #ifdef TRAIN_FLOOR1
924 {
925 FILE *of;
926 char buffer[80];
927 sprintf(buffer,"line_%dx%ld_%dsub%d.vqd",
928 vb->pcmend/2,posts-2,class,bookas[k]);
929 of=fopen(buffer,"a");
930 fprintf(of,"%d\n",out[j+k]);
931 fclose(of);
932 }
933 #endif
934 }
935 }
936 j+=cdim;
937 }
938
939 {
940 /* generate quantized floor equivalent to what we'd unpack in decode */
941 /* render the lines */
942 int hx=0;
943 int lx=0;
944 int ly=post[0]*info->mult;
945 int n=ci->blocksizes[vb->W]/2;
946
947 for(j=1;j<look->posts;j++){
948 int current=look->forward_index[j];
949 int hy=post[current]&0x7fff;
950 if(hy==post[current]){
951
952 hy*=info->mult;
953 hx=info->postlist[current];
954
955 render_line0(n,lx,hx,ly,hy,ilogmask);
956
957 lx=hx;
958 ly=hy;
959 }
960 }
961 for(j=hx;j<vb->pcmend/2;j++)ilogmask[j]=ly; /* be certain */
962 return(1);
963 }
964 }else{
965 oggpack_write(opb,0,1);
966 memset(ilogmask,0,vb->pcmend/2*sizeof(*ilogmask));
967 return(0);
968 }
969 }
970
971 static void *floor1_inverse1(vorbis_block *vb,vorbis_look_floor *in){
972 vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
973 vorbis_info_floor1 *info=look->vi;
974 codec_setup_info *ci=vb->vd->vi->codec_setup;
975
976 int i,j,k;
977 codebook *books=ci->fullbooks;
978
979 /* unpack wrapped/predicted values from stream */
980 if(oggpack_read(&vb->opb,1)==1){
981 int *fit_value=_vorbis_block_alloc(vb,(look->posts)*sizeof(*fit_value));
982
983 fit_value[0]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
984 fit_value[1]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
985
986 /* partition by partition */
987 for(i=0,j=2;i<info->partitions;i++){
988 int class=info->partitionclass[i];
989 int cdim=info->class_dim[class];
990 int csubbits=info->class_subs[class];
991 int csub=1<<csubbits;
992 int cval=0;
993
994 /* decode the partition's first stage cascade value */
995 if(csubbits){
996 cval=vorbis_book_decode(books+info->class_book[class],&vb->opb);
997
998 if(cval==-1)goto eop;
999 }
1000
1001 for(k=0;k<cdim;k++){
1002 int book=info->class_subbook[class][cval&(csub-1)];
1003 cval>>=csubbits;
1004 if(book>=0){
1005 if((fit_value[j+k]=vorbis_book_decode(books+book,&vb->opb))==-1)
1006 goto eop;
1007 }else{
1008 fit_value[j+k]=0;
1009 }
1010 }
1011 j+=cdim;
1012 }
1013
1014 /* unwrap positive values and reconsitute via linear interpolation */
1015 for(i=2;i<look->posts;i++){
1016 int predicted=render_point(info->postlist[look->loneighbor[i-2]],
1017 info->postlist[look->hineighbor[i-2]],
1018 fit_value[look->loneighbor[i-2]],
1019 fit_value[look->hineighbor[i-2]],
1020 info->postlist[i]);
1021 int hiroom=look->quant_q-predicted;
1022 int loroom=predicted;
1023 int room=(hiroom<loroom?hiroom:loroom)<<1;
1024 int val=fit_value[i];
1025
1026 if(val){
1027 if(val>=room){
1028 if(hiroom>loroom){
1029 val = val-loroom;
1030 }else{
1031 val = -1-(val-hiroom);
1032 }
1033 }else{
1034 if(val&1){
1035 val= -((val+1)>>1);
1036 }else{
1037 val>>=1;
1038 }
1039 }
1040
1041 fit_value[i]=(val+predicted)&0x7fff;
1042 fit_value[look->loneighbor[i-2]]&=0x7fff;
1043 fit_value[look->hineighbor[i-2]]&=0x7fff;
1044
1045 }else{
1046 fit_value[i]=predicted|0x8000;
1047 }
1048
1049 }
1050
1051 return(fit_value);
1052 }
1053 eop:
1054 return(NULL);
1055 }
1056
1057 static int floor1_inverse2(vorbis_block *vb,vorbis_look_floor *in,void *memo,
1058 float *out){
1059 vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
1060 vorbis_info_floor1 *info=look->vi;
1061
1062 codec_setup_info *ci=vb->vd->vi->codec_setup;
1063 int n=ci->blocksizes[vb->W]/2;
1064 int j;
1065
1066 if(memo){
1067 /* render the lines */
1068 int *fit_value=(int *)memo;
1069 int hx=0;
1070 int lx=0;
1071 int ly=fit_value[0]*info->mult;
1072 /* guard lookup against out-of-range values */
1073 ly=(ly<0?0:ly>255?255:ly);
1074
1075 for(j=1;j<look->posts;j++){
1076 int current=look->forward_index[j];
1077 int hy=fit_value[current]&0x7fff;
1078 if(hy==fit_value[current]){
1079
1080 hx=info->postlist[current];
1081 hy*=info->mult;
1082 /* guard lookup against out-of-range values */
1083 hy=(hy<0?0:hy>255?255:hy);
1084
1085 render_line(n,lx,hx,ly,hy,out);
1086
1087 lx=hx;
1088 ly=hy;
1089 }
1090 }
1091 for(j=hx;j<n;j++)out[j]*=FLOOR1_fromdB_LOOKUP[ly]; /* be certain */
1092 return(1);
1093 }
1094 memset(out,0,sizeof(*out)*n);
1095 return(0);
1096 }
1097
1098 /* export hooks */
1099 const vorbis_func_floor floor1_exportbundle={
1100 &floor1_pack,&floor1_unpack,&floor1_look,&floor1_free_info,
1101 &floor1_free_look,&floor1_inverse1,&floor1_inverse2
1102 };

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial