1 /********************************************************************
2  *                                                                  *
3  * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
4  *                                                                  *
5  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
6  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
7  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
8  *                                                                  *
9  * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
10  * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
11  *                                                                  *
12  ********************************************************************
13 
14  function: floor backend 1 implementation
15 
16  ********************************************************************/
17 
18 #include <stdlib.h>
19 #include <string.h>
20 #include <math.h>
21 #include "ogg.h"
22 #include "ivorbiscodec.h"
23 #include "codec_internal.h"
24 #include "registry.h"
25 #include "codebook.h"
26 #include "misc.h"
27 #include "block.h"
28 
29 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
30 
31 typedef struct {
32   int forward_index[VIF_POSIT+2];
33 
34   int hineighbor[VIF_POSIT];
35   int loneighbor[VIF_POSIT];
36   int posts;
37 
38   int n;
39   int quant_q;
40   vorbis_info_floor1 *vi;
41 
42 } vorbis_look_floor1;
43 
44 /***********************************************/
45 
floor1_free_info(vorbis_info_floor * i)46 static void floor1_free_info(vorbis_info_floor *i){
47   vorbis_info_floor1 *info=(vorbis_info_floor1 *)i;
48   if(info){
49     memset(info,0,sizeof(*info));
50     _ogg_free(info);
51   }
52 }
53 
floor1_free_look(vorbis_look_floor * i)54 static void floor1_free_look(vorbis_look_floor *i){
55   vorbis_look_floor1 *look=(vorbis_look_floor1 *)i;
56   if(look){
57     memset(look,0,sizeof(*look));
58     _ogg_free(look);
59   }
60 }
61 
ilog(unsigned int v)62 static int ilog(unsigned int v){
63   int ret=0;
64   while(v){
65     ret++;
66     v>>=1;
67   }
68   return(ret);
69 }
70 
icomp(const void * a,const void * b)71 static int icomp(const void *a,const void *b){
72   return(**(int **)a-**(int **)b);
73 }
74 
floor1_unpack(vorbis_info * vi,oggpack_buffer * opb)75 static vorbis_info_floor *floor1_unpack (vorbis_info *vi,oggpack_buffer *opb){
76   codec_setup_info     *ci=(codec_setup_info *)vi->codec_setup;
77   int j,k,count=0,maxclass=-1,rangebits;
78 
79   vorbis_info_floor1 *info=(vorbis_info_floor1 *)_ogg_calloc(1,sizeof(*info));
80   /* read partitions */
81   info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */
82   for(j=0;j<info->partitions;j++){
83     info->partitionclass[j]=oggpack_read(opb,4); /* only 0 to 15 legal */
84     if(info->partitionclass[j]<0)goto err_out;
85     if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
86   }
87 
88   /* read partition classes */
89   for(j=0;j<maxclass+1;j++){
90     info->class_dim[j]=oggpack_read(opb,3)+1; /* 1 to 8 */
91     info->class_subs[j]=oggpack_read(opb,2); /* 0,1,2,3 bits */
92     if(info->class_subs[j]<0)
93       goto err_out;
94     if(info->class_subs[j])info->class_book[j]=oggpack_read(opb,8);
95     if(info->class_book[j]<0 || info->class_book[j]>=ci->books)
96       goto err_out;
97     for(k=0;k<(1<<info->class_subs[j]);k++){
98       info->class_subbook[j][k]=oggpack_read(opb,8)-1;
99       if(info->class_subbook[j][k]<-1 || info->class_subbook[j][k]>=ci->books)
100 	goto err_out;
101     }
102   }
103 
104   /* read the post list */
105   info->mult=oggpack_read(opb,2)+1;     /* only 1,2,3,4 legal now */
106   rangebits=oggpack_read(opb,4);
107   if(rangebits<0)goto err_out;
108 
109   for(j=0,k=0;j<info->partitions;j++){
110     count+=info->class_dim[info->partitionclass[j]];
111     if(count>VIF_POSIT)goto err_out;
112     for(;k<count;k++){
113       int t=info->postlist[k+2]=oggpack_read(opb,rangebits);
114       if(t<0 || t>=(1<<rangebits))
115 	goto err_out;
116     }
117   }
118   info->postlist[0]=0;
119   info->postlist[1]=1<<rangebits;
120 
121   /* don't allow repeated values in post list as they'd result in
122      zero-length segments */
123   {
124     int *sortpointer[VIF_POSIT+2];
125     for(j=0;j<count+2;j++)sortpointer[j]=info->postlist+j;
126     qsort(sortpointer,count+2,sizeof(*sortpointer),icomp);
127 
128     for(j=1;j<count+2;j++)
129       if(*sortpointer[j-1]==*sortpointer[j])goto err_out;
130   }
131 
132   return(info);
133 
134  err_out:
135   floor1_free_info(info);
136   return(NULL);
137 }
138 
floor1_look(vorbis_dsp_state * vd,vorbis_info_mode * mi,vorbis_info_floor * in)139 static vorbis_look_floor *floor1_look(vorbis_dsp_state *vd,vorbis_info_mode *mi,
140                               vorbis_info_floor *in){
141 
142   int *sortpointer[VIF_POSIT+2];
143   vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
144   vorbis_look_floor1 *look=(vorbis_look_floor1 *)_ogg_calloc(1,sizeof(*look));
145   int i,j,n=0;
146 
147   look->vi=info;
148   look->n=info->postlist[1];
149 
150   /* we drop each position value in-between already decoded values,
151      and use linear interpolation to predict each new value past the
152      edges.  The positions are read in the order of the position
153      list... we precompute the bounding positions in the lookup.  Of
154      course, the neighbors can change (if a position is declined), but
155      this is an initial mapping */
156 
157   for(i=0;i<info->partitions;i++)n+=info->class_dim[info->partitionclass[i]];
158   n+=2;
159   look->posts=n;
160 
161   /* also store a sorted position index */
162   for(i=0;i<n;i++)sortpointer[i]=info->postlist+i;
163   qsort(sortpointer,n,sizeof(*sortpointer),icomp);
164 
165   /* points from sort order back to range number */
166   for(i=0;i<n;i++)look->forward_index[i]=sortpointer[i]-info->postlist;
167 
168   /* quantize values to multiplier spec */
169   switch(info->mult){
170   case 1: /* 1024 -> 256 */
171     look->quant_q=256;
172     break;
173   case 2: /* 1024 -> 128 */
174     look->quant_q=128;
175     break;
176   case 3: /* 1024 -> 86 */
177     look->quant_q=86;
178     break;
179   case 4: /* 1024 -> 64 */
180     look->quant_q=64;
181     break;
182   }
183 
184   /* discover our neighbors for decode where we don't use fit flags
185      (that would push the neighbors outward) */
186   for(i=0;i<n-2;i++){
187     int lo=0;
188     int hi=1;
189     int lx=0;
190     int hx=look->n;
191     int currentx=info->postlist[i+2];
192     for(j=0;j<i+2;j++){
193       int x=info->postlist[j];
194       if(x>lx && x<currentx){
195 	lo=j;
196 	lx=x;
197       }
198       if(x<hx && x>currentx){
199 	hi=j;
200 	hx=x;
201       }
202     }
203     look->loneighbor[i]=lo;
204     look->hineighbor[i]=hi;
205   }
206 
207   return(look);
208 }
209 
render_point(int x0,int x1,int y0,int y1,int x)210 static int render_point(int x0,int x1,int y0,int y1,int x){
211   y0&=0x7fff; /* mask off flag */
212   y1&=0x7fff;
213 
214   {
215     int dy=y1-y0;
216     int adx=x1-x0;
217     int ady=abs(dy);
218     int err=ady*(x-x0);
219 
220     int off=err/adx;
221     if(dy<0)return(y0-off);
222     return(y0+off);
223   }
224 }
225 
226 #ifdef _LOW_ACCURACY_
227 #  define XdB(n) ((((n)>>8)+1)>>1)
228 #else
229 #  define XdB(n) (n)
230 #endif
231 
232 static const ogg_int32_t FLOOR_fromdB_LOOKUP[256]={
233   XdB(0x000000e5), XdB(0x000000f4), XdB(0x00000103), XdB(0x00000114),
234   XdB(0x00000126), XdB(0x00000139), XdB(0x0000014e), XdB(0x00000163),
235   XdB(0x0000017a), XdB(0x00000193), XdB(0x000001ad), XdB(0x000001c9),
236   XdB(0x000001e7), XdB(0x00000206), XdB(0x00000228), XdB(0x0000024c),
237   XdB(0x00000272), XdB(0x0000029b), XdB(0x000002c6), XdB(0x000002f4),
238   XdB(0x00000326), XdB(0x0000035a), XdB(0x00000392), XdB(0x000003cd),
239   XdB(0x0000040c), XdB(0x00000450), XdB(0x00000497), XdB(0x000004e4),
240   XdB(0x00000535), XdB(0x0000058c), XdB(0x000005e8), XdB(0x0000064a),
241   XdB(0x000006b3), XdB(0x00000722), XdB(0x00000799), XdB(0x00000818),
242   XdB(0x0000089e), XdB(0x0000092e), XdB(0x000009c6), XdB(0x00000a69),
243   XdB(0x00000b16), XdB(0x00000bcf), XdB(0x00000c93), XdB(0x00000d64),
244   XdB(0x00000e43), XdB(0x00000f30), XdB(0x0000102d), XdB(0x0000113a),
245   XdB(0x00001258), XdB(0x0000138a), XdB(0x000014cf), XdB(0x00001629),
246   XdB(0x0000179a), XdB(0x00001922), XdB(0x00001ac4), XdB(0x00001c82),
247   XdB(0x00001e5c), XdB(0x00002055), XdB(0x0000226f), XdB(0x000024ac),
248   XdB(0x0000270e), XdB(0x00002997), XdB(0x00002c4b), XdB(0x00002f2c),
249   XdB(0x0000323d), XdB(0x00003581), XdB(0x000038fb), XdB(0x00003caf),
250   XdB(0x000040a0), XdB(0x000044d3), XdB(0x0000494c), XdB(0x00004e10),
251   XdB(0x00005323), XdB(0x0000588a), XdB(0x00005e4b), XdB(0x0000646b),
252   XdB(0x00006af2), XdB(0x000071e5), XdB(0x0000794c), XdB(0x0000812e),
253   XdB(0x00008993), XdB(0x00009283), XdB(0x00009c09), XdB(0x0000a62d),
254   XdB(0x0000b0f9), XdB(0x0000bc79), XdB(0x0000c8b9), XdB(0x0000d5c4),
255   XdB(0x0000e3a9), XdB(0x0000f274), XdB(0x00010235), XdB(0x000112fd),
256   XdB(0x000124dc), XdB(0x000137e4), XdB(0x00014c29), XdB(0x000161bf),
257   XdB(0x000178bc), XdB(0x00019137), XdB(0x0001ab4a), XdB(0x0001c70e),
258   XdB(0x0001e4a1), XdB(0x0002041f), XdB(0x000225aa), XdB(0x00024962),
259   XdB(0x00026f6d), XdB(0x000297f0), XdB(0x0002c316), XdB(0x0002f109),
260   XdB(0x000321f9), XdB(0x00035616), XdB(0x00038d97), XdB(0x0003c8b4),
261   XdB(0x000407a7), XdB(0x00044ab2), XdB(0x00049218), XdB(0x0004de23),
262   XdB(0x00052f1e), XdB(0x0005855c), XdB(0x0005e135), XdB(0x00064306),
263   XdB(0x0006ab33), XdB(0x00071a24), XdB(0x0007904b), XdB(0x00080e20),
264   XdB(0x00089422), XdB(0x000922da), XdB(0x0009bad8), XdB(0x000a5cb6),
265   XdB(0x000b091a), XdB(0x000bc0b1), XdB(0x000c8436), XdB(0x000d5471),
266   XdB(0x000e3233), XdB(0x000f1e5f), XdB(0x001019e4), XdB(0x001125c1),
267   XdB(0x00124306), XdB(0x001372d5), XdB(0x0014b663), XdB(0x00160ef7),
268   XdB(0x00177df0), XdB(0x001904c1), XdB(0x001aa4f9), XdB(0x001c603d),
269   XdB(0x001e384f), XdB(0x00202f0f), XdB(0x0022467a), XdB(0x002480b1),
270   XdB(0x0026dff7), XdB(0x002966b3), XdB(0x002c1776), XdB(0x002ef4fc),
271   XdB(0x0032022d), XdB(0x00354222), XdB(0x0038b828), XdB(0x003c67c2),
272   XdB(0x004054ae), XdB(0x004482e8), XdB(0x0048f6af), XdB(0x004db488),
273   XdB(0x0052c142), XdB(0x005821ff), XdB(0x005ddc33), XdB(0x0063f5b0),
274   XdB(0x006a74a7), XdB(0x00715faf), XdB(0x0078bdce), XdB(0x0080967f),
275   XdB(0x0088f1ba), XdB(0x0091d7f9), XdB(0x009b5247), XdB(0x00a56a41),
276   XdB(0x00b02a27), XdB(0x00bb9ce2), XdB(0x00c7ce12), XdB(0x00d4ca17),
277   XdB(0x00e29e20), XdB(0x00f15835), XdB(0x0101074b), XdB(0x0111bb4e),
278   XdB(0x01238531), XdB(0x01367704), XdB(0x014aa402), XdB(0x016020a7),
279   XdB(0x017702c3), XdB(0x018f6190), XdB(0x01a955cb), XdB(0x01c4f9cf),
280   XdB(0x01e269a8), XdB(0x0201c33b), XdB(0x0223265a), XdB(0x0246b4ea),
281   XdB(0x026c9302), XdB(0x0294e716), XdB(0x02bfda13), XdB(0x02ed9793),
282   XdB(0x031e4e09), XdB(0x03522ee4), XdB(0x03896ed0), XdB(0x03c445e2),
283   XdB(0x0402efd6), XdB(0x0445ac4b), XdB(0x048cbefc), XdB(0x04d87013),
284   XdB(0x05290c67), XdB(0x057ee5ca), XdB(0x05da5364), XdB(0x063bb204),
285   XdB(0x06a36485), XdB(0x0711d42b), XdB(0x0787710e), XdB(0x0804b299),
286   XdB(0x088a17ef), XdB(0x0918287e), XdB(0x09af747c), XdB(0x0a50957e),
287   XdB(0x0afc2f19), XdB(0x0bb2ef7f), XdB(0x0c759034), XdB(0x0d44d6ca),
288   XdB(0x0e2195bc), XdB(0x0f0cad0d), XdB(0x10070b62), XdB(0x1111aeea),
289   XdB(0x122da66c), XdB(0x135c120f), XdB(0x149e24d9), XdB(0x15f525b1),
290   XdB(0x176270e3), XdB(0x18e7794b), XdB(0x1a85c9ae), XdB(0x1c3f06d1),
291   XdB(0x1e14f07d), XdB(0x200963d7), XdB(0x221e5ccd), XdB(0x2455f870),
292   XdB(0x26b2770b), XdB(0x29363e2b), XdB(0x2be3db5c), XdB(0x2ebe06b6),
293   XdB(0x31c7a55b), XdB(0x3503ccd4), XdB(0x3875c5aa), XdB(0x3c210f44),
294   XdB(0x4009632b), XdB(0x4432b8cf), XdB(0x48a149bc), XdB(0x4d59959e),
295   XdB(0x52606733), XdB(0x57bad899), XdB(0x5d6e593a), XdB(0x6380b298),
296   XdB(0x69f80e9a), XdB(0x70dafda8), XdB(0x78307d76), XdB(0x7fffffff),
297 };
298 
render_line(int n,int x0,int x1,int y0,int y1,ogg_int32_t * d)299 static void render_line(int n, int x0,int x1,int y0,int y1,ogg_int32_t *d){
300   int dy=y1-y0;
301   int adx=x1-x0;
302   int ady=abs(dy);
303   int base=dy/adx;
304   int sy=(dy<0?base-1:base+1);
305   int x=x0;
306   int y=y0;
307   int err=0;
308 
309   if(n>x1)n=x1;
310   ady-=abs(base*adx);
311 
312   if(x<n)
313     d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
314 
315   while(++x<n){
316     err=err+ady;
317     if(err>=adx){
318       err-=adx;
319       y+=sy;
320     }else{
321       y+=base;
322     }
323     d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
324   }
325 }
326 
floor1_inverse1(vorbis_block * vb,vorbis_look_floor * in)327 static void *floor1_inverse1(vorbis_block *vb,vorbis_look_floor *in){
328   vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
329   vorbis_info_floor1 *info=look->vi;
330   codec_setup_info   *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
331 
332   int i,j,k;
333   codebook *books=ci->fullbooks;
334 
335   /* unpack wrapped/predicted values from stream */
336   if(oggpack_read(&vb->opb,1)==1){
337     int *fit_value=(int *)_vorbis_block_alloc(vb,(look->posts)*sizeof(*fit_value));
338 
339     fit_value[0]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
340     fit_value[1]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
341 
342     /* partition by partition */
343     /* partition by partition */
344     for(i=0,j=2;i<info->partitions;i++){
345       int classv=info->partitionclass[i];
346       int cdim=info->class_dim[classv];
347       int csubbits=info->class_subs[classv];
348       int csub=1<<csubbits;
349       int cval=0;
350 
351       /* decode the partition's first stage cascade value */
352       if(csubbits){
353 	cval=vorbis_book_decode(books+info->class_book[classv],&vb->opb);
354 
355 	if(cval==-1)goto eop;
356       }
357 
358       for(k=0;k<cdim;k++){
359 	int book=info->class_subbook[classv][cval&(csub-1)];
360 	cval>>=csubbits;
361 	if(book>=0){
362 	  if((fit_value[j+k]=vorbis_book_decode(books+book,&vb->opb))==-1)
363 	    goto eop;
364 	}else{
365 	  fit_value[j+k]=0;
366 	}
367       }
368       j+=cdim;
369     }
370 
371     /* unwrap positive values and reconsitute via linear interpolation */
372     for(i=2;i<look->posts;i++){
373       int predicted=render_point(info->postlist[look->loneighbor[i-2]],
374 				 info->postlist[look->hineighbor[i-2]],
375 				 fit_value[look->loneighbor[i-2]],
376 				 fit_value[look->hineighbor[i-2]],
377 				 info->postlist[i]);
378       int hiroom=look->quant_q-predicted;
379       int loroom=predicted;
380       int room=(hiroom<loroom?hiroom:loroom)<<1;
381       int val=fit_value[i];
382 
383       if(val){
384 	if(val>=room){
385 	  if(hiroom>loroom){
386 	    val = val-loroom;
387 	  }else{
388 	  val = -1-(val-hiroom);
389 	  }
390 	}else{
391 	  if(val&1){
392 	    val= -((val+1)>>1);
393 	  }else{
394 	    val>>=1;
395 	  }
396 	}
397 
398 	fit_value[i]=(val+predicted)&0x7fff;;
399 	fit_value[look->loneighbor[i-2]]&=0x7fff;
400 	fit_value[look->hineighbor[i-2]]&=0x7fff;
401 
402       }else{
403 	fit_value[i]=predicted|0x8000;
404       }
405 
406     }
407 
408     return(fit_value);
409   }
410  eop:
411   return(NULL);
412 }
413 
floor1_inverse2(vorbis_block * vb,vorbis_look_floor * in,void * memo,ogg_int32_t * out)414 static int floor1_inverse2(vorbis_block *vb,vorbis_look_floor *in,void *memo,
415 			  ogg_int32_t *out){
416   vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
417   vorbis_info_floor1 *info=look->vi;
418 
419   codec_setup_info   *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
420   int                  n=ci->blocksizes[vb->W]/2;
421   int j;
422 
423   if(memo){
424     /* render the lines */
425     int *fit_value=(int *)memo;
426     int hx=0;
427     int lx=0;
428     int ly=fit_value[0]*info->mult;
429     /* guard lookup against out-of-range values */
430     ly=(ly<0?0:ly>255?255:ly);
431 
432     for(j=1;j<look->posts;j++){
433       int current=look->forward_index[j];
434       int hy=fit_value[current]&0x7fff;
435       if(hy==fit_value[current]){
436 
437 	hx=info->postlist[current];
438 	hy*=info->mult;
439         /* guard lookup against out-of-range values */
440         hy=(hy<0?0:hy>255?255:hy);
441 
442 	render_line(n,lx,hx,ly,hy,out);
443 
444 	lx=hx;
445 	ly=hy;
446       }
447     }
448     for(j=hx;j<n;j++)out[j]*=ly; /* be certain */
449     return(1);
450   }
451   memset(out,0,sizeof(*out)*n);
452   return(0);
453 }
454 
455 /* export hooks */
456 vorbis_func_floor floor1_exportbundle={
457   &floor1_unpack,&floor1_look,&floor1_free_info,
458   &floor1_free_look,&floor1_inverse1,&floor1_inverse2
459 };
460 
461