[tremor] Re: [PATCH] new mdct code, redundant tables eliminated
Nicolas Pitre
nico at cam.org
Mon Sep 16 10:28:34 PDT 2002
On Fri, 13 Sep 2002, Nicolas Pitre wrote:
> On Fri, 13 Sep 2002, Monty wrote:
>
> > Patch is on mainline.
> >
> > It is not bit-identical decode to the original, but upon review, the
> > negation shuffling would cause that. This appears to be simple
> > integer rounding behavior.
>
> Right, usually the difference is only on the least significant bit in the
> final sample.
>
> However the table reduction is a compromise since it won't give perfect
> results for all cases. The problematic cases are when n==4096 and n==8192
> in the first loop of the "rotate + window" section of the code.
[...]
> Of course the simple solution would involve quadrupling the lookup table,
> but a table too sparse would also have negative impact on small cache
> systems due to bad locality for the cases where n is small. The text size
> reduction achievement would also be compromised.
>
> My preferred alternative would involve linear interpolation within the
> current table. This should give pretty good accuracy and not require many
> more cycles (only some additions and shifts). However to do it efficiently
> separate loops for n=4096 and n=8192 might be best.
OK, so I did it. Attached is a patch that implements the needed
interpolation for the problematic cases, and the results suggest that the
final output should be pretty accurate for all cases now with no negative
impact on the whole.
Monty, could you apply this patch to CVS please?
<p>Nicolas
-------------- next part --------------
Index: mdct.c
===================================================================
RCS file: /usr/local/cvsroot/Tremor/mdct.c,v
retrieving revision 1.4
diff -u -r1.4 mdct.c
--- mdct.c 13 Sep 2002 16:37:56 -0000 1.4
+++ mdct.c 16 Sep 2002 16:04:11 -0000
@@ -405,39 +405,116 @@
DATA_TYPE *oX1=out+n2+n4;
DATA_TYPE *oX2=out+n2+n4;
DATA_TYPE *iX =out;
- T =sin_lookup-(step>>1);
- V =sin_lookup+2048+(step>>1);
-
- do{
- oX1-=4;
-
- T += step;
- V -= step;
- oX1[3] = MULT31 (iX[0] , *T) - MULT31(iX[1] , *V);
- oX2[0] =-(MULT31 (iX[0] , *V) + MULT31(iX[1] , *T));
-
- T += step;
- V -= step;
- oX1[2] = MULT31 (iX[2] , *T) - MULT31(iX[3] , *V);
- oX2[1] =-(MULT31 (iX[2] , *V) + MULT31(iX[3] , *T));
-
- if(!step) T++,V--;
-
- T += step;
- V -= step;
- oX1[1] = MULT31 (iX[4] , *T) - MULT31(iX[5] , *V);
- oX2[2] =-(MULT31 (iX[4] , *V) + MULT31(iX[5] , *T));
-
- T += step;
- V -= step;
- oX1[0] = MULT31 (iX[6] , *T) - MULT31(iX[7] , *V);
- oX2[3] =-(MULT31 (iX[6] , *V) + MULT31(iX[7] , *T));
-
- if(!step) T++,V--;
-
- oX2+=4;
- iX += 8;
- }while(iX<oX1);
+
+ switch(step) {
+ default: {
+ T = sin_lookup-(step>>1);
+ V = sin_lookup+2048+(step>>1);
+ do{
+ oX1-=4;
+
+ T += step;
+ V -= step;
+ oX1[3] = MULT31 (iX[0] , *T) - MULT31(iX[1] , *V);
+ oX2[0] =-(MULT31 (iX[0] , *V) + MULT31(iX[1] , *T));
+
+ T += step;
+ V -= step;
+ oX1[2] = MULT31 (iX[2] , *T) - MULT31(iX[3] , *V);
+ oX2[1] =-(MULT31 (iX[2] , *V) + MULT31(iX[3] , *T));
+
+ T += step;
+ V -= step;
+ oX1[1] = MULT31 (iX[4] , *T) - MULT31(iX[5] , *V);
+ oX2[2] =-(MULT31 (iX[4] , *V) + MULT31(iX[5] , *T));
+
+ T += step;
+ V -= step;
+ oX1[0] = MULT31 (iX[6] , *T) - MULT31(iX[7] , *V);
+ oX2[3] =-(MULT31 (iX[6] , *V) + MULT31(iX[7] , *T));
+
+ oX2+=4;
+ iX+=8;
+ }while(iX<oX1);
+ break;
+ }
+
+ case 1: {
+ /* linear interpolation between table values: offset=0.5, step=1 */
+ REG_TYPE t0,t1,v0,v1;
+ T = sin_lookup;
+ V = sin_lookup+2048;
+ t0 = (*T++)>>1;
+ v0 = (*V--)>>1;
+ do{
+ oX1-=4;
+
+ t0 += (t1 = (*T++)>>1);
+ v0 += (v1 = (*V--)>>1);
+ oX1[3] = MULT31 (iX[0] , t0) - MULT31(iX[1] , v0);
+ oX2[0] =-(MULT31 (iX[0] , v0) + MULT31(iX[1] , t0));
+
+ t1 += (t0 = (*T++)>>1);
+ v1 += (v0 = (*V--)>>1);
+ oX1[2] = MULT31 (iX[2] , t1) - MULT31(iX[3] , v1);
+ oX2[1] =-(MULT31 (iX[2] , v1) + MULT31(iX[3] , t1));
+
+ t0 += (t1 = (*T++)>>1);
+ v0 += (v1 = (*V--)>>1);
+ oX1[1] = MULT31 (iX[4] , t0) - MULT31(iX[5] , v0);
+ oX2[2] =-(MULT31 (iX[4] , v0) + MULT31(iX[5] , t0));
+
+ t1 += (t0 = (*T++)>>1);
+ v1 += (v0 = (*V--)>>1);
+ oX1[0] = MULT31 (iX[6] , t1) - MULT31(iX[7] , v1);
+ oX2[3] =-(MULT31 (iX[6] , v1) + MULT31(iX[7] , t1));
+
+ oX2+=4;
+ iX+=8;
+ }while(iX<oX1);
+ break;
+ }
+
+ case 0: {
+ /* linear interpolation between table values: offset=0.25, step=0.5 */
+ REG_TYPE t0,t1,v0,v1,dt,dv;
+ T = sin_lookup;
+ V = sin_lookup+2048;
+ t0 = *T++;
+ v0 = *V--;
+ do{
+ oX1-=4;
+
+ t1 = *T++;
+ v1 = *V--;
+ t0 += (dt = (t1-t0)>>2);
+ v0 += (dv = (v1-v0)>>2);
+ oX1[3] = MULT31 (iX[0] , t0) - MULT31(iX[1] , v0);
+ oX2[0] =-(MULT31 (iX[0] , v0) + MULT31(iX[1] , t0));
+
+ t0 = t1-dt;
+ v0 = v1-dv;
+ oX1[2] = MULT31 (iX[2] , t0) - MULT31(iX[3] , v0);
+ oX2[1] =-(MULT31 (iX[2] , v0) + MULT31(iX[3] , t0));
+
+ t0 = *T++;
+ v0 = *V--;
+ t1 += (dt = (t0-t1)>>2);
+ v1 += (dv = (v0-v1)>>2);
+ oX1[1] = MULT31 (iX[4] , t1) - MULT31(iX[5] , v1);
+ oX2[2] =-(MULT31 (iX[4] , v1) + MULT31(iX[5] , t1));
+
+ t1 = t0-dt;
+ v1 = v0-dv;
+ oX1[0] = MULT31 (iX[6] , t1) - MULT31(iX[7] , v1);
+ oX2[3] =-(MULT31 (iX[6] , v1) + MULT31(iX[7] , t1));
+
+ oX2+=4;
+ iX+=8;
+ }while(iX<oX1);
+ break;
+ }
+ }
iX=out+n2+n4;
oX1=out+n4;
More information about the Tremor
mailing list