sync with ffmpeg
[mplayer/glamo.git] / tremor / floor1.c
blob963656d6312a88c13957ae7ccc2386cf11cb8283
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 ********************************************************************
14 function: floor backend 1 implementation
16 ********************************************************************/
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"
29 #define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
31 typedef struct {
32 int forward_index[VIF_POSIT+2];
34 int hineighbor[VIF_POSIT];
35 int loneighbor[VIF_POSIT];
36 int posts;
38 int n;
39 int quant_q;
40 vorbis_info_floor1 *vi;
42 } vorbis_look_floor1;
44 /***********************************************/
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);
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);
62 static int ilog(unsigned int v){
63 int ret=0;
64 while(v){
65 ret++;
66 v>>=1;
68 return(ret);
71 static vorbis_info_floor *floor1_unpack (vorbis_info *vi,oggpack_buffer *opb){
72 codec_setup_info *ci=(codec_setup_info *)vi->codec_setup;
73 int j,k,count=0,maxclass=-1,rangebits;
75 vorbis_info_floor1 *info=(vorbis_info_floor1 *)_ogg_calloc(1,sizeof(*info));
76 /* read partitions */
77 info->partitions=oggpack_read(opb,5); /* only 0 to 31 legal */
78 for(j=0;j<info->partitions;j++){
79 info->partitionclass[j]=oggpack_read(opb,4); /* only 0 to 15 legal */
80 if(maxclass<info->partitionclass[j])maxclass=info->partitionclass[j];
83 /* read partition classes */
84 for(j=0;j<maxclass+1;j++){
85 info->class_dim[j]=oggpack_read(opb,3)+1; /* 1 to 8 */
86 info->class_subs[j]=oggpack_read(opb,2); /* 0,1,2,3 bits */
87 if(info->class_subs[j]<0)
88 goto err_out;
89 if(info->class_subs[j])info->class_book[j]=oggpack_read(opb,8);
90 if(info->class_book[j]<0 || info->class_book[j]>=ci->books)
91 goto err_out;
92 for(k=0;k<(1<<info->class_subs[j]);k++){
93 info->class_subbook[j][k]=oggpack_read(opb,8)-1;
94 if(info->class_subbook[j][k]<-1 || info->class_subbook[j][k]>=ci->books)
95 goto err_out;
99 /* read the post list */
100 info->mult=oggpack_read(opb,2)+1; /* only 1,2,3,4 legal now */
101 rangebits=oggpack_read(opb,4);
103 for(j=0,k=0;j<info->partitions;j++){
104 count+=info->class_dim[info->partitionclass[j]];
105 for(;k<count;k++){
106 int t=info->postlist[k+2]=oggpack_read(opb,rangebits);
107 if(t<0 || t>=(1<<rangebits))
108 goto err_out;
111 info->postlist[0]=0;
112 info->postlist[1]=1<<rangebits;
114 return(info);
116 err_out:
117 floor1_free_info(info);
118 return(NULL);
121 static int icomp(const void *a,const void *b){
122 return(**(int **)a-**(int **)b);
125 static vorbis_look_floor *floor1_look(vorbis_dsp_state *vd,vorbis_info_mode *mi,
126 vorbis_info_floor *in){
128 int *sortpointer[VIF_POSIT+2];
129 vorbis_info_floor1 *info=(vorbis_info_floor1 *)in;
130 vorbis_look_floor1 *look=(vorbis_look_floor1 *)_ogg_calloc(1,sizeof(*look));
131 int i,j,n=0;
133 look->vi=info;
134 look->n=info->postlist[1];
136 /* we drop each position value in-between already decoded values,
137 and use linear interpolation to predict each new value past the
138 edges. The positions are read in the order of the position
139 list... we precompute the bounding positions in the lookup. Of
140 course, the neighbors can change (if a position is declined), but
141 this is an initial mapping */
143 for(i=0;i<info->partitions;i++)n+=info->class_dim[info->partitionclass[i]];
144 n+=2;
145 look->posts=n;
147 /* also store a sorted position index */
148 for(i=0;i<n;i++)sortpointer[i]=info->postlist+i;
149 qsort(sortpointer,n,sizeof(*sortpointer),icomp);
151 /* points from sort order back to range number */
152 for(i=0;i<n;i++)look->forward_index[i]=sortpointer[i]-info->postlist;
154 /* quantize values to multiplier spec */
155 switch(info->mult){
156 case 1: /* 1024 -> 256 */
157 look->quant_q=256;
158 break;
159 case 2: /* 1024 -> 128 */
160 look->quant_q=128;
161 break;
162 case 3: /* 1024 -> 86 */
163 look->quant_q=86;
164 break;
165 case 4: /* 1024 -> 64 */
166 look->quant_q=64;
167 break;
170 /* discover our neighbors for decode where we don't use fit flags
171 (that would push the neighbors outward) */
172 for(i=0;i<n-2;i++){
173 int lo=0;
174 int hi=1;
175 int lx=0;
176 int hx=look->n;
177 int currentx=info->postlist[i+2];
178 for(j=0;j<i+2;j++){
179 int x=info->postlist[j];
180 if(x>lx && x<currentx){
181 lo=j;
182 lx=x;
184 if(x<hx && x>currentx){
185 hi=j;
186 hx=x;
189 look->loneighbor[i]=lo;
190 look->hineighbor[i]=hi;
193 return(look);
196 static int render_point(int x0,int x1,int y0,int y1,int x){
197 y0&=0x7fff; /* mask off flag */
198 y1&=0x7fff;
201 int dy=y1-y0;
202 int adx=x1-x0;
203 int ady=abs(dy);
204 int err=ady*(x-x0);
206 int off=err/adx;
207 if(dy<0)return(y0-off);
208 return(y0+off);
212 #ifdef _LOW_ACCURACY_
213 # define XdB(n) ((((n)>>8)+1)>>1)
214 #else
215 # define XdB(n) (n)
216 #endif
218 static const ogg_int32_t FLOOR_fromdB_LOOKUP[256]={
219 XdB(0x000000e5), XdB(0x000000f4), XdB(0x00000103), XdB(0x00000114),
220 XdB(0x00000126), XdB(0x00000139), XdB(0x0000014e), XdB(0x00000163),
221 XdB(0x0000017a), XdB(0x00000193), XdB(0x000001ad), XdB(0x000001c9),
222 XdB(0x000001e7), XdB(0x00000206), XdB(0x00000228), XdB(0x0000024c),
223 XdB(0x00000272), XdB(0x0000029b), XdB(0x000002c6), XdB(0x000002f4),
224 XdB(0x00000326), XdB(0x0000035a), XdB(0x00000392), XdB(0x000003cd),
225 XdB(0x0000040c), XdB(0x00000450), XdB(0x00000497), XdB(0x000004e4),
226 XdB(0x00000535), XdB(0x0000058c), XdB(0x000005e8), XdB(0x0000064a),
227 XdB(0x000006b3), XdB(0x00000722), XdB(0x00000799), XdB(0x00000818),
228 XdB(0x0000089e), XdB(0x0000092e), XdB(0x000009c6), XdB(0x00000a69),
229 XdB(0x00000b16), XdB(0x00000bcf), XdB(0x00000c93), XdB(0x00000d64),
230 XdB(0x00000e43), XdB(0x00000f30), XdB(0x0000102d), XdB(0x0000113a),
231 XdB(0x00001258), XdB(0x0000138a), XdB(0x000014cf), XdB(0x00001629),
232 XdB(0x0000179a), XdB(0x00001922), XdB(0x00001ac4), XdB(0x00001c82),
233 XdB(0x00001e5c), XdB(0x00002055), XdB(0x0000226f), XdB(0x000024ac),
234 XdB(0x0000270e), XdB(0x00002997), XdB(0x00002c4b), XdB(0x00002f2c),
235 XdB(0x0000323d), XdB(0x00003581), XdB(0x000038fb), XdB(0x00003caf),
236 XdB(0x000040a0), XdB(0x000044d3), XdB(0x0000494c), XdB(0x00004e10),
237 XdB(0x00005323), XdB(0x0000588a), XdB(0x00005e4b), XdB(0x0000646b),
238 XdB(0x00006af2), XdB(0x000071e5), XdB(0x0000794c), XdB(0x0000812e),
239 XdB(0x00008993), XdB(0x00009283), XdB(0x00009c09), XdB(0x0000a62d),
240 XdB(0x0000b0f9), XdB(0x0000bc79), XdB(0x0000c8b9), XdB(0x0000d5c4),
241 XdB(0x0000e3a9), XdB(0x0000f274), XdB(0x00010235), XdB(0x000112fd),
242 XdB(0x000124dc), XdB(0x000137e4), XdB(0x00014c29), XdB(0x000161bf),
243 XdB(0x000178bc), XdB(0x00019137), XdB(0x0001ab4a), XdB(0x0001c70e),
244 XdB(0x0001e4a1), XdB(0x0002041f), XdB(0x000225aa), XdB(0x00024962),
245 XdB(0x00026f6d), XdB(0x000297f0), XdB(0x0002c316), XdB(0x0002f109),
246 XdB(0x000321f9), XdB(0x00035616), XdB(0x00038d97), XdB(0x0003c8b4),
247 XdB(0x000407a7), XdB(0x00044ab2), XdB(0x00049218), XdB(0x0004de23),
248 XdB(0x00052f1e), XdB(0x0005855c), XdB(0x0005e135), XdB(0x00064306),
249 XdB(0x0006ab33), XdB(0x00071a24), XdB(0x0007904b), XdB(0x00080e20),
250 XdB(0x00089422), XdB(0x000922da), XdB(0x0009bad8), XdB(0x000a5cb6),
251 XdB(0x000b091a), XdB(0x000bc0b1), XdB(0x000c8436), XdB(0x000d5471),
252 XdB(0x000e3233), XdB(0x000f1e5f), XdB(0x001019e4), XdB(0x001125c1),
253 XdB(0x00124306), XdB(0x001372d5), XdB(0x0014b663), XdB(0x00160ef7),
254 XdB(0x00177df0), XdB(0x001904c1), XdB(0x001aa4f9), XdB(0x001c603d),
255 XdB(0x001e384f), XdB(0x00202f0f), XdB(0x0022467a), XdB(0x002480b1),
256 XdB(0x0026dff7), XdB(0x002966b3), XdB(0x002c1776), XdB(0x002ef4fc),
257 XdB(0x0032022d), XdB(0x00354222), XdB(0x0038b828), XdB(0x003c67c2),
258 XdB(0x004054ae), XdB(0x004482e8), XdB(0x0048f6af), XdB(0x004db488),
259 XdB(0x0052c142), XdB(0x005821ff), XdB(0x005ddc33), XdB(0x0063f5b0),
260 XdB(0x006a74a7), XdB(0x00715faf), XdB(0x0078bdce), XdB(0x0080967f),
261 XdB(0x0088f1ba), XdB(0x0091d7f9), XdB(0x009b5247), XdB(0x00a56a41),
262 XdB(0x00b02a27), XdB(0x00bb9ce2), XdB(0x00c7ce12), XdB(0x00d4ca17),
263 XdB(0x00e29e20), XdB(0x00f15835), XdB(0x0101074b), XdB(0x0111bb4e),
264 XdB(0x01238531), XdB(0x01367704), XdB(0x014aa402), XdB(0x016020a7),
265 XdB(0x017702c3), XdB(0x018f6190), XdB(0x01a955cb), XdB(0x01c4f9cf),
266 XdB(0x01e269a8), XdB(0x0201c33b), XdB(0x0223265a), XdB(0x0246b4ea),
267 XdB(0x026c9302), XdB(0x0294e716), XdB(0x02bfda13), XdB(0x02ed9793),
268 XdB(0x031e4e09), XdB(0x03522ee4), XdB(0x03896ed0), XdB(0x03c445e2),
269 XdB(0x0402efd6), XdB(0x0445ac4b), XdB(0x048cbefc), XdB(0x04d87013),
270 XdB(0x05290c67), XdB(0x057ee5ca), XdB(0x05da5364), XdB(0x063bb204),
271 XdB(0x06a36485), XdB(0x0711d42b), XdB(0x0787710e), XdB(0x0804b299),
272 XdB(0x088a17ef), XdB(0x0918287e), XdB(0x09af747c), XdB(0x0a50957e),
273 XdB(0x0afc2f19), XdB(0x0bb2ef7f), XdB(0x0c759034), XdB(0x0d44d6ca),
274 XdB(0x0e2195bc), XdB(0x0f0cad0d), XdB(0x10070b62), XdB(0x1111aeea),
275 XdB(0x122da66c), XdB(0x135c120f), XdB(0x149e24d9), XdB(0x15f525b1),
276 XdB(0x176270e3), XdB(0x18e7794b), XdB(0x1a85c9ae), XdB(0x1c3f06d1),
277 XdB(0x1e14f07d), XdB(0x200963d7), XdB(0x221e5ccd), XdB(0x2455f870),
278 XdB(0x26b2770b), XdB(0x29363e2b), XdB(0x2be3db5c), XdB(0x2ebe06b6),
279 XdB(0x31c7a55b), XdB(0x3503ccd4), XdB(0x3875c5aa), XdB(0x3c210f44),
280 XdB(0x4009632b), XdB(0x4432b8cf), XdB(0x48a149bc), XdB(0x4d59959e),
281 XdB(0x52606733), XdB(0x57bad899), XdB(0x5d6e593a), XdB(0x6380b298),
282 XdB(0x69f80e9a), XdB(0x70dafda8), XdB(0x78307d76), XdB(0x7fffffff),
285 static void render_line(int x0,int x1,int y0,int y1,ogg_int32_t *d){
286 int dy=y1-y0;
287 int adx=x1-x0;
288 int ady=abs(dy);
289 int base=dy/adx;
290 int sy=(dy<0?base-1:base+1);
291 int x=x0;
292 int y=y0;
293 int err=0;
295 ady-=abs(base*adx);
297 d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
299 while(++x<x1){
300 err=err+ady;
301 if(err>=adx){
302 err-=adx;
303 y+=sy;
304 }else{
305 y+=base;
307 d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
311 static void *floor1_inverse1(vorbis_block *vb,vorbis_look_floor *in){
312 vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
313 vorbis_info_floor1 *info=look->vi;
314 codec_setup_info *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
316 int i,j,k;
317 codebook *books=ci->fullbooks;
319 /* unpack wrapped/predicted values from stream */
320 if(oggpack_read(&vb->opb,1)==1){
321 int *fit_value=(int *)_vorbis_block_alloc(vb,(look->posts)*sizeof(*fit_value));
323 fit_value[0]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
324 fit_value[1]=oggpack_read(&vb->opb,ilog(look->quant_q-1));
326 /* partition by partition */
327 /* partition by partition */
328 for(i=0,j=2;i<info->partitions;i++){
329 int classv=info->partitionclass[i];
330 int cdim=info->class_dim[classv];
331 int csubbits=info->class_subs[classv];
332 int csub=1<<csubbits;
333 int cval=0;
335 /* decode the partition's first stage cascade value */
336 if(csubbits){
337 cval=vorbis_book_decode(books+info->class_book[classv],&vb->opb);
339 if(cval==-1)goto eop;
342 for(k=0;k<cdim;k++){
343 int book=info->class_subbook[classv][cval&(csub-1)];
344 cval>>=csubbits;
345 if(book>=0){
346 if((fit_value[j+k]=vorbis_book_decode(books+book,&vb->opb))==-1)
347 goto eop;
348 }else{
349 fit_value[j+k]=0;
352 j+=cdim;
355 /* unwrap positive values and reconsitute via linear interpolation */
356 for(i=2;i<look->posts;i++){
357 int predicted=render_point(info->postlist[look->loneighbor[i-2]],
358 info->postlist[look->hineighbor[i-2]],
359 fit_value[look->loneighbor[i-2]],
360 fit_value[look->hineighbor[i-2]],
361 info->postlist[i]);
362 int hiroom=look->quant_q-predicted;
363 int loroom=predicted;
364 int room=(hiroom<loroom?hiroom:loroom)<<1;
365 int val=fit_value[i];
367 if(val){
368 if(val>=room){
369 if(hiroom>loroom){
370 val = val-loroom;
371 }else{
372 val = -1-(val-hiroom);
374 }else{
375 if(val&1){
376 val= -((val+1)>>1);
377 }else{
378 val>>=1;
382 fit_value[i]=val+predicted;
383 fit_value[look->loneighbor[i-2]]&=0x7fff;
384 fit_value[look->hineighbor[i-2]]&=0x7fff;
386 }else{
387 fit_value[i]=predicted|0x8000;
392 return(fit_value);
394 eop:
395 return(NULL);
398 static int floor1_inverse2(vorbis_block *vb,vorbis_look_floor *in,void *memo,
399 ogg_int32_t *out){
400 vorbis_look_floor1 *look=(vorbis_look_floor1 *)in;
401 vorbis_info_floor1 *info=look->vi;
403 codec_setup_info *ci=(codec_setup_info *)vb->vd->vi->codec_setup;
404 int n=ci->blocksizes[vb->W]/2;
405 int j;
407 if(memo){
408 /* render the lines */
409 int *fit_value=(int *)memo;
410 int hx=0;
411 int lx=0;
412 int ly=fit_value[0]*info->mult;
413 for(j=1;j<look->posts;j++){
414 int current=look->forward_index[j];
415 int hy=fit_value[current]&0x7fff;
416 if(hy==fit_value[current]){
418 hy*=info->mult;
419 hx=info->postlist[current];
421 render_line(lx,hx,ly,hy,out);
423 lx=hx;
424 ly=hy;
427 for(j=hx;j<n;j++)out[j]*=ly; /* be certain */
428 return(1);
430 memset(out,0,sizeof(*out)*n);
431 return(0);
434 /* export hooks */
435 vorbis_func_floor floor1_exportbundle={
436 &floor1_unpack,&floor1_look,&floor1_free_info,
437 &floor1_free_look,&floor1_inverse1,&floor1_inverse2