media/libvorbis/lib/vorbis_floor1.c@97036ab72558
media/libvorbis/lib/vorbis_floor1.c
Tue, 06 Jan 2015 21:39:09 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Tue, 06 Jan 2015 21:39:09 +0100
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
- permissions
- -rw-r--r--
Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.
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 ********************************************************************
13 function: floor backend 1 implementation
14 last mod: $Id: floor1.c 19031 2013-12-03 19:20:50Z tterribe $
16 ********************************************************************/
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"
29 #include <stdio.h>
31 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
33 typedef struct lsfit_acc{
34 int x0;
35 int x1;
37 int xa;
38 int ya;
39 int x2a;
40 int y2a;
41 int xya;
42 int an;
44 int xb;
45 int yb;
46 int x2b;
47 int y2b;
48 int xyb;
49 int bn;
50 } lsfit_acc;
52 /***********************************************/
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 }
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);*/
70 memset(look,0,sizeof(*look));
71 _ogg_free(look);
72 }
73 }
75 static int ilog(unsigned int v){
76 int ret=0;
77 while(v){
78 ret++;
79 v>>=1;
80 }
81 return(ret);
82 }
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 }
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;
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 }
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 }
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);
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 }
130 static int icomp(const void *a,const void *b){
131 return(**(int **)a-**(int **)b);
132 }
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;
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 }
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 }
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;
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;
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);
187 for(j=1;j<count+2;j++)
188 if(*sortpointer[j-1]==*sortpointer[j])goto err_out;
189 }
191 return(info);
193 err_out:
194 floor1_free_info(info);
195 return(NULL);
196 }
198 static vorbis_look_floor *floor1_look(vorbis_dsp_state *vd,
199 vorbis_info_floor *in){
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;
206 (void)vd;
208 look->vi=info;
209 look->n=info->postlist[1];
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 */
218 for(i=0;i<info->partitions;i++)n+=info->class_dim[info->partitionclass[i]];
219 n+=2;
220 look->posts=n;
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);
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]];
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 }
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 }
272 return(look);
273 }
275 static int render_point(int x0,int x1,int y0,int y1,int x){
276 y0&=0x7fff; /* mask off flag */
277 y1&=0x7fff;
279 {
280 int dy=y1-y0;
281 int adx=x1-x0;
282 int ady=abs(dy);
283 int err=ady*(x-x0);
285 int off=err/adx;
286 if(dy<0)return(y0-off);
287 return(y0+off);
288 }
289 }
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 }
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 };
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;
375 ady-=abs(base*adx);
377 if(n>x1)n=x1;
379 if(x<n)
380 d[x]*=FLOOR1_fromdB_LOOKUP[y];
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 }
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;
404 ady-=abs(base*adx);
406 if(n>x1)n=x1;
408 if(x<n)
409 d[x]=y;
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 }
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;
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;
431 memset(a,0,sizeof(*a));
432 a->x0=x0;
433 a->x1=x1;
434 if(x1>=n)x1=n-1;
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 }
457 a->xa=xa;
458 a->ya=ya;
459 a->x2a=x2a;
460 a->y2a=y2a;
461 a->xya=xya;
462 a->an=na;
464 a->xb=xb;
465 a->yb=yb;
466 a->x2b=x2b;
467 a->y2b=y2b;
468 a->xyb=xyb;
469 a->bn=nb;
471 return(na);
472 }
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;
481 for(i=0;i<fits;i++){
482 double weight = (a[i].bn+a[i].an)*info->twofitweight/(a[i].an+1)+1.;
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 }
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 }
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 }
510 {
511 double denom=(bn*x2b-xb*xb);
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);
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;
525 return 0;
526 }else{
527 *y0=0;
528 *y1=0;
529 return 1;
530 }
531 }
532 }
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;
549 ady-=abs(base*adx);
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 }
559 while(++x<x1){
560 err=err+ady;
561 if(err>=adx){
562 err-=adx;
563 y+=sy;
564 }else{
565 y+=base;
566 }
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 }
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 }
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];
591 return (A[pos]+B[pos])>>1;
592 }
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 */
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];
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 */
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 }
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);
634 fit_valueA[0]=y0;
635 fit_valueB[0]=y0;
636 fit_valueB[1]=y1;
637 fit_valueA[1]=y1;
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];
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;
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);
662 if(ly==-1 || hy==-1){
663 exit(1);
664 }
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);
675 if(ret0){
676 ly0=ly;
677 ly1=hy0;
678 }
679 if(ret1){
680 hy0=ly1;
681 hy1=hy;
682 }
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;
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 }
718 output=_vorbis_block_alloc(vb,sizeof(*output)*posts);
720 output[0]=post_Y(fit_valueA,fit_valueB,0);
721 output[1]=post_Y(fit_valueA,fit_valueB,1);
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];
734 int predicted=render_point(x0,x1,y0,y1,info->postlist[i]);
735 int vx=post_Y(fit_valueA,fit_valueB,i);
737 if(vx>=0 && predicted!=vx){
738 output[i]=vx;
739 }else{
740 output[i]= predicted|0x8000;
741 }
742 }
743 }
745 return(output);
747 }
749 int *floor1_interpolate_fit(vorbis_block *vb,vorbis_look_floor1 *look,
750 int *A,int *B,
751 int del){
753 long i;
754 long posts=look->posts;
755 int *output=NULL;
757 if(A && B){
758 output=_vorbis_block_alloc(vb,sizeof(*output)*posts);
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 }
767 return(output);
768 }
771 int floor1_encode(oggpack_buffer *opb,vorbis_block *vb,
772 vorbis_look_floor1 *look,
773 int *post,int *ilogmask){
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;
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 }
804 out[0]=post[0];
805 out[1]=post[1];
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];
816 int predicted=render_point(x0,x1,y0,y1,info->postlist[i]);
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);
826 int val=post[i]-predicted;
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. */
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;
845 out[i]=val;
846 post[ln]&=0x7fff;
847 post[hn]&=0x7fff;
848 }
849 }
851 /* we have everything we need. pack it out */
852 /* mark nontrivial floor */
853 oggpack_write(opb,1,1);
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));
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;
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);
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 }
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,"+!");*/
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 }
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;
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]){
952 hy*=info->mult;
953 hx=info->postlist[current];
955 render_line0(n,lx,hx,ly,hy,ilogmask);
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 }
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;
976 int i,j,k;
977 codebook *books=ci->fullbooks;
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));
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));
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;
994 /* decode the partition's first stage cascade value */
995 if(csubbits){
996 cval=vorbis_book_decode(books+info->class_book[class],&vb->opb);
998 if(cval==-1)goto eop;
999 }
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 }
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];
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 }
1041 fit_value[i]=(val+predicted)&0x7fff;
1042 fit_value[look->loneighbor[i-2]]&=0x7fff;
1043 fit_value[look->hineighbor[i-2]]&=0x7fff;
1045 }else{
1046 fit_value[i]=predicted|0x8000;
1047 }
1049 }
1051 return(fit_value);
1052 }
1053 eop:
1054 return(NULL);
1055 }
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;
1062 codec_setup_info *ci=vb->vd->vi->codec_setup;
1063 int n=ci->blocksizes[vb->W]/2;
1064 int j;
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);
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]){
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);
1085 render_line(n,lx,hx,ly,hy,out);
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 }
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 };
