cannam@86: /******************************************************************** cannam@86: * * cannam@86: * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. * cannam@86: * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS * cannam@86: * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE * cannam@86: * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING. * cannam@86: * * cannam@86: * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009 * cannam@86: * by the Xiph.Org Foundation http://www.xiph.org/ * cannam@86: * * cannam@86: ******************************************************************** cannam@86: cannam@86: function: normalized modified discrete cosine transform cannam@86: power of two length transform only [64 <= n ] cannam@86: last mod: $Id: mdct.c 16227 2009-07-08 06:58:46Z xiphmont $ cannam@86: cannam@86: Original algorithm adapted long ago from _The use of multirate filter cannam@86: banks for coding of high quality digital audio_, by T. Sporer, cannam@86: K. Brandenburg and B. Edler, collection of the European Signal cannam@86: Processing Conference (EUSIPCO), Amsterdam, June 1992, Vol.1, pp cannam@86: 211-214 cannam@86: cannam@86: The below code implements an algorithm that no longer looks much like cannam@86: that presented in the paper, but the basic structure remains if you cannam@86: dig deep enough to see it. cannam@86: cannam@86: This module DOES NOT INCLUDE code to generate/apply the window cannam@86: function. Everybody has their own weird favorite including me... I cannam@86: happen to like the properties of y=sin(.5PI*sin^2(x)), but others may cannam@86: vehemently disagree. cannam@86: cannam@86: ********************************************************************/ cannam@86: cannam@86: /* this can also be run as an integer transform by uncommenting a cannam@86: define in mdct.h; the integerization is a first pass and although cannam@86: it's likely stable for Vorbis, the dynamic range is constrained and cannam@86: roundoff isn't done (so it's noisy). Consider it functional, but cannam@86: only a starting point. There's no point on a machine with an FPU */ cannam@86: cannam@86: #include cannam@86: #include cannam@86: #include cannam@86: #include cannam@86: #include "vorbis/codec.h" cannam@86: #include "mdct.h" cannam@86: #include "os.h" cannam@86: #include "misc.h" cannam@86: cannam@86: /* build lookups for trig functions; also pre-figure scaling and cannam@86: some window function algebra. */ cannam@86: cannam@86: void mdct_init(mdct_lookup *lookup,int n){ cannam@86: int *bitrev=_ogg_malloc(sizeof(*bitrev)*(n/4)); cannam@86: DATA_TYPE *T=_ogg_malloc(sizeof(*T)*(n+n/4)); cannam@86: cannam@86: int i; cannam@86: int n2=n>>1; cannam@86: int log2n=lookup->log2n=rint(log((float)n)/log(2.f)); cannam@86: lookup->n=n; cannam@86: lookup->trig=T; cannam@86: lookup->bitrev=bitrev; cannam@86: cannam@86: /* trig lookups... */ cannam@86: cannam@86: for(i=0;i>j;j++) cannam@86: if((msb>>j)&i)acc|=1<scale=FLOAT_CONV(4.f/n); cannam@86: } cannam@86: cannam@86: /* 8 point butterfly (in place, 4 register) */ cannam@86: STIN void mdct_butterfly_8(DATA_TYPE *x){ cannam@86: REG_TYPE r0 = x[6] + x[2]; cannam@86: REG_TYPE r1 = x[6] - x[2]; cannam@86: REG_TYPE r2 = x[4] + x[0]; cannam@86: REG_TYPE r3 = x[4] - x[0]; cannam@86: cannam@86: x[6] = r0 + r2; cannam@86: x[4] = r0 - r2; cannam@86: cannam@86: r0 = x[5] - x[1]; cannam@86: r2 = x[7] - x[3]; cannam@86: x[0] = r1 + r0; cannam@86: x[2] = r1 - r0; cannam@86: cannam@86: r0 = x[5] + x[1]; cannam@86: r1 = x[7] + x[3]; cannam@86: x[3] = r2 + r3; cannam@86: x[1] = r2 - r3; cannam@86: x[7] = r1 + r0; cannam@86: x[5] = r1 - r0; cannam@86: cannam@86: } cannam@86: cannam@86: /* 16 point butterfly (in place, 4 register) */ cannam@86: STIN void mdct_butterfly_16(DATA_TYPE *x){ cannam@86: REG_TYPE r0 = x[1] - x[9]; cannam@86: REG_TYPE r1 = x[0] - x[8]; cannam@86: cannam@86: x[8] += x[0]; cannam@86: x[9] += x[1]; cannam@86: x[0] = MULT_NORM((r0 + r1) * cPI2_8); cannam@86: x[1] = MULT_NORM((r0 - r1) * cPI2_8); cannam@86: cannam@86: r0 = x[3] - x[11]; cannam@86: r1 = x[10] - x[2]; cannam@86: x[10] += x[2]; cannam@86: x[11] += x[3]; cannam@86: x[2] = r0; cannam@86: x[3] = r1; cannam@86: cannam@86: r0 = x[12] - x[4]; cannam@86: r1 = x[13] - x[5]; cannam@86: x[12] += x[4]; cannam@86: x[13] += x[5]; cannam@86: x[4] = MULT_NORM((r0 - r1) * cPI2_8); cannam@86: x[5] = MULT_NORM((r0 + r1) * cPI2_8); cannam@86: cannam@86: r0 = x[14] - x[6]; cannam@86: r1 = x[15] - x[7]; cannam@86: x[14] += x[6]; cannam@86: x[15] += x[7]; cannam@86: x[6] = r0; cannam@86: x[7] = r1; cannam@86: cannam@86: mdct_butterfly_8(x); cannam@86: mdct_butterfly_8(x+8); cannam@86: } cannam@86: cannam@86: /* 32 point butterfly (in place, 4 register) */ cannam@86: STIN void mdct_butterfly_32(DATA_TYPE *x){ cannam@86: REG_TYPE r0 = x[30] - x[14]; cannam@86: REG_TYPE r1 = x[31] - x[15]; cannam@86: cannam@86: x[30] += x[14]; cannam@86: x[31] += x[15]; cannam@86: x[14] = r0; cannam@86: x[15] = r1; cannam@86: cannam@86: r0 = x[28] - x[12]; cannam@86: r1 = x[29] - x[13]; cannam@86: x[28] += x[12]; cannam@86: x[29] += x[13]; cannam@86: x[12] = MULT_NORM( r0 * cPI1_8 - r1 * cPI3_8 ); cannam@86: x[13] = MULT_NORM( r0 * cPI3_8 + r1 * cPI1_8 ); cannam@86: cannam@86: r0 = x[26] - x[10]; cannam@86: r1 = x[27] - x[11]; cannam@86: x[26] += x[10]; cannam@86: x[27] += x[11]; cannam@86: x[10] = MULT_NORM(( r0 - r1 ) * cPI2_8); cannam@86: x[11] = MULT_NORM(( r0 + r1 ) * cPI2_8); cannam@86: cannam@86: r0 = x[24] - x[8]; cannam@86: r1 = x[25] - x[9]; cannam@86: x[24] += x[8]; cannam@86: x[25] += x[9]; cannam@86: x[8] = MULT_NORM( r0 * cPI3_8 - r1 * cPI1_8 ); cannam@86: x[9] = MULT_NORM( r1 * cPI3_8 + r0 * cPI1_8 ); cannam@86: cannam@86: r0 = x[22] - x[6]; cannam@86: r1 = x[7] - x[23]; cannam@86: x[22] += x[6]; cannam@86: x[23] += x[7]; cannam@86: x[6] = r1; cannam@86: x[7] = r0; cannam@86: cannam@86: r0 = x[4] - x[20]; cannam@86: r1 = x[5] - x[21]; cannam@86: x[20] += x[4]; cannam@86: x[21] += x[5]; cannam@86: x[4] = MULT_NORM( r1 * cPI1_8 + r0 * cPI3_8 ); cannam@86: x[5] = MULT_NORM( r1 * cPI3_8 - r0 * cPI1_8 ); cannam@86: cannam@86: r0 = x[2] - x[18]; cannam@86: r1 = x[3] - x[19]; cannam@86: x[18] += x[2]; cannam@86: x[19] += x[3]; cannam@86: x[2] = MULT_NORM(( r1 + r0 ) * cPI2_8); cannam@86: x[3] = MULT_NORM(( r1 - r0 ) * cPI2_8); cannam@86: cannam@86: r0 = x[0] - x[16]; cannam@86: r1 = x[1] - x[17]; cannam@86: x[16] += x[0]; cannam@86: x[17] += x[1]; cannam@86: x[0] = MULT_NORM( r1 * cPI3_8 + r0 * cPI1_8 ); cannam@86: x[1] = MULT_NORM( r1 * cPI1_8 - r0 * cPI3_8 ); cannam@86: cannam@86: mdct_butterfly_16(x); cannam@86: mdct_butterfly_16(x+16); cannam@86: cannam@86: } cannam@86: cannam@86: /* N point first stage butterfly (in place, 2 register) */ cannam@86: STIN void mdct_butterfly_first(DATA_TYPE *T, cannam@86: DATA_TYPE *x, cannam@86: int points){ cannam@86: cannam@86: DATA_TYPE *x1 = x + points - 8; cannam@86: DATA_TYPE *x2 = x + (points>>1) - 8; cannam@86: REG_TYPE r0; cannam@86: REG_TYPE r1; cannam@86: cannam@86: do{ cannam@86: cannam@86: r0 = x1[6] - x2[6]; cannam@86: r1 = x1[7] - x2[7]; cannam@86: x1[6] += x2[6]; cannam@86: x1[7] += x2[7]; cannam@86: x2[6] = MULT_NORM(r1 * T[1] + r0 * T[0]); cannam@86: x2[7] = MULT_NORM(r1 * T[0] - r0 * T[1]); cannam@86: cannam@86: r0 = x1[4] - x2[4]; cannam@86: r1 = x1[5] - x2[5]; cannam@86: x1[4] += x2[4]; cannam@86: x1[5] += x2[5]; cannam@86: x2[4] = MULT_NORM(r1 * T[5] + r0 * T[4]); cannam@86: x2[5] = MULT_NORM(r1 * T[4] - r0 * T[5]); cannam@86: cannam@86: r0 = x1[2] - x2[2]; cannam@86: r1 = x1[3] - x2[3]; cannam@86: x1[2] += x2[2]; cannam@86: x1[3] += x2[3]; cannam@86: x2[2] = MULT_NORM(r1 * T[9] + r0 * T[8]); cannam@86: x2[3] = MULT_NORM(r1 * T[8] - r0 * T[9]); cannam@86: cannam@86: r0 = x1[0] - x2[0]; cannam@86: r1 = x1[1] - x2[1]; cannam@86: x1[0] += x2[0]; cannam@86: x1[1] += x2[1]; cannam@86: x2[0] = MULT_NORM(r1 * T[13] + r0 * T[12]); cannam@86: x2[1] = MULT_NORM(r1 * T[12] - r0 * T[13]); cannam@86: cannam@86: x1-=8; cannam@86: x2-=8; cannam@86: T+=16; cannam@86: cannam@86: }while(x2>=x); cannam@86: } cannam@86: cannam@86: /* N/stage point generic N stage butterfly (in place, 2 register) */ cannam@86: STIN void mdct_butterfly_generic(DATA_TYPE *T, cannam@86: DATA_TYPE *x, cannam@86: int points, cannam@86: int trigint){ cannam@86: cannam@86: DATA_TYPE *x1 = x + points - 8; cannam@86: DATA_TYPE *x2 = x + (points>>1) - 8; cannam@86: REG_TYPE r0; cannam@86: REG_TYPE r1; cannam@86: cannam@86: do{ cannam@86: cannam@86: r0 = x1[6] - x2[6]; cannam@86: r1 = x1[7] - x2[7]; cannam@86: x1[6] += x2[6]; cannam@86: x1[7] += x2[7]; cannam@86: x2[6] = MULT_NORM(r1 * T[1] + r0 * T[0]); cannam@86: x2[7] = MULT_NORM(r1 * T[0] - r0 * T[1]); cannam@86: cannam@86: T+=trigint; cannam@86: cannam@86: r0 = x1[4] - x2[4]; cannam@86: r1 = x1[5] - x2[5]; cannam@86: x1[4] += x2[4]; cannam@86: x1[5] += x2[5]; cannam@86: x2[4] = MULT_NORM(r1 * T[1] + r0 * T[0]); cannam@86: x2[5] = MULT_NORM(r1 * T[0] - r0 * T[1]); cannam@86: cannam@86: T+=trigint; cannam@86: cannam@86: r0 = x1[2] - x2[2]; cannam@86: r1 = x1[3] - x2[3]; cannam@86: x1[2] += x2[2]; cannam@86: x1[3] += x2[3]; cannam@86: x2[2] = MULT_NORM(r1 * T[1] + r0 * T[0]); cannam@86: x2[3] = MULT_NORM(r1 * T[0] - r0 * T[1]); cannam@86: cannam@86: T+=trigint; cannam@86: cannam@86: r0 = x1[0] - x2[0]; cannam@86: r1 = x1[1] - x2[1]; cannam@86: x1[0] += x2[0]; cannam@86: x1[1] += x2[1]; cannam@86: x2[0] = MULT_NORM(r1 * T[1] + r0 * T[0]); cannam@86: x2[1] = MULT_NORM(r1 * T[0] - r0 * T[1]); cannam@86: cannam@86: T+=trigint; cannam@86: x1-=8; cannam@86: x2-=8; cannam@86: cannam@86: }while(x2>=x); cannam@86: } cannam@86: cannam@86: STIN void mdct_butterflies(mdct_lookup *init, cannam@86: DATA_TYPE *x, cannam@86: int points){ cannam@86: cannam@86: DATA_TYPE *T=init->trig; cannam@86: int stages=init->log2n-5; cannam@86: int i,j; cannam@86: cannam@86: if(--stages>0){ cannam@86: mdct_butterfly_first(T,x,points); cannam@86: } cannam@86: cannam@86: for(i=1;--stages>0;i++){ cannam@86: for(j=0;j<(1<>i)*j,points>>i,4<trig)_ogg_free(l->trig); cannam@86: if(l->bitrev)_ogg_free(l->bitrev); cannam@86: memset(l,0,sizeof(*l)); cannam@86: } cannam@86: } cannam@86: cannam@86: STIN void mdct_bitreverse(mdct_lookup *init, cannam@86: DATA_TYPE *x){ cannam@86: int n = init->n; cannam@86: int *bit = init->bitrev; cannam@86: DATA_TYPE *w0 = x; cannam@86: DATA_TYPE *w1 = x = w0+(n>>1); cannam@86: DATA_TYPE *T = init->trig+n; cannam@86: cannam@86: do{ cannam@86: DATA_TYPE *x0 = x+bit[0]; cannam@86: DATA_TYPE *x1 = x+bit[1]; cannam@86: cannam@86: REG_TYPE r0 = x0[1] - x1[1]; cannam@86: REG_TYPE r1 = x0[0] + x1[0]; cannam@86: REG_TYPE r2 = MULT_NORM(r1 * T[0] + r0 * T[1]); cannam@86: REG_TYPE r3 = MULT_NORM(r1 * T[1] - r0 * T[0]); cannam@86: cannam@86: w1 -= 4; cannam@86: cannam@86: r0 = HALVE(x0[1] + x1[1]); cannam@86: r1 = HALVE(x0[0] - x1[0]); cannam@86: cannam@86: w0[0] = r0 + r2; cannam@86: w1[2] = r0 - r2; cannam@86: w0[1] = r1 + r3; cannam@86: w1[3] = r3 - r1; cannam@86: cannam@86: x0 = x+bit[2]; cannam@86: x1 = x+bit[3]; cannam@86: cannam@86: r0 = x0[1] - x1[1]; cannam@86: r1 = x0[0] + x1[0]; cannam@86: r2 = MULT_NORM(r1 * T[2] + r0 * T[3]); cannam@86: r3 = MULT_NORM(r1 * T[3] - r0 * T[2]); cannam@86: cannam@86: r0 = HALVE(x0[1] + x1[1]); cannam@86: r1 = HALVE(x0[0] - x1[0]); cannam@86: cannam@86: w0[2] = r0 + r2; cannam@86: w1[0] = r0 - r2; cannam@86: w0[3] = r1 + r3; cannam@86: w1[1] = r3 - r1; cannam@86: cannam@86: T += 4; cannam@86: bit += 4; cannam@86: w0 += 4; cannam@86: cannam@86: }while(w0n; cannam@86: int n2=n>>1; cannam@86: int n4=n>>2; cannam@86: cannam@86: /* rotate */ cannam@86: cannam@86: DATA_TYPE *iX = in+n2-7; cannam@86: DATA_TYPE *oX = out+n2+n4; cannam@86: DATA_TYPE *T = init->trig+n4; cannam@86: cannam@86: do{ cannam@86: oX -= 4; cannam@86: oX[0] = MULT_NORM(-iX[2] * T[3] - iX[0] * T[2]); cannam@86: oX[1] = MULT_NORM (iX[0] * T[3] - iX[2] * T[2]); cannam@86: oX[2] = MULT_NORM(-iX[6] * T[1] - iX[4] * T[0]); cannam@86: oX[3] = MULT_NORM (iX[4] * T[1] - iX[6] * T[0]); cannam@86: iX -= 8; cannam@86: T += 4; cannam@86: }while(iX>=in); cannam@86: cannam@86: iX = in+n2-8; cannam@86: oX = out+n2+n4; cannam@86: T = init->trig+n4; cannam@86: cannam@86: do{ cannam@86: T -= 4; cannam@86: oX[0] = MULT_NORM (iX[4] * T[3] + iX[6] * T[2]); cannam@86: oX[1] = MULT_NORM (iX[4] * T[2] - iX[6] * T[3]); cannam@86: oX[2] = MULT_NORM (iX[0] * T[1] + iX[2] * T[0]); cannam@86: oX[3] = MULT_NORM (iX[0] * T[0] - iX[2] * T[1]); cannam@86: iX -= 8; cannam@86: oX += 4; cannam@86: }while(iX>=in); cannam@86: cannam@86: mdct_butterflies(init,out+n2,n2); cannam@86: mdct_bitreverse(init,out); cannam@86: cannam@86: /* roatate + window */ cannam@86: cannam@86: { cannam@86: DATA_TYPE *oX1=out+n2+n4; cannam@86: DATA_TYPE *oX2=out+n2+n4; cannam@86: DATA_TYPE *iX =out; cannam@86: T =init->trig+n2; cannam@86: cannam@86: do{ cannam@86: oX1-=4; cannam@86: cannam@86: oX1[3] = MULT_NORM (iX[0] * T[1] - iX[1] * T[0]); cannam@86: oX2[0] = -MULT_NORM (iX[0] * T[0] + iX[1] * T[1]); cannam@86: cannam@86: oX1[2] = MULT_NORM (iX[2] * T[3] - iX[3] * T[2]); cannam@86: oX2[1] = -MULT_NORM (iX[2] * T[2] + iX[3] * T[3]); cannam@86: cannam@86: oX1[1] = MULT_NORM (iX[4] * T[5] - iX[5] * T[4]); cannam@86: oX2[2] = -MULT_NORM (iX[4] * T[4] + iX[5] * T[5]); cannam@86: cannam@86: oX1[0] = MULT_NORM (iX[6] * T[7] - iX[7] * T[6]); cannam@86: oX2[3] = -MULT_NORM (iX[6] * T[6] + iX[7] * T[7]); cannam@86: cannam@86: oX2+=4; cannam@86: iX += 8; cannam@86: T += 8; cannam@86: }while(iXoX2); cannam@86: } cannam@86: } cannam@86: cannam@86: void mdct_forward(mdct_lookup *init, DATA_TYPE *in, DATA_TYPE *out){ cannam@86: int n=init->n; cannam@86: int n2=n>>1; cannam@86: int n4=n>>2; cannam@86: int n8=n>>3; cannam@86: DATA_TYPE *w=alloca(n*sizeof(*w)); /* forward needs working space */ cannam@86: DATA_TYPE *w2=w+n2; cannam@86: cannam@86: /* rotate */ cannam@86: cannam@86: /* window + rotate + step 1 */ cannam@86: cannam@86: REG_TYPE r0; cannam@86: REG_TYPE r1; cannam@86: DATA_TYPE *x0=in+n2+n4; cannam@86: DATA_TYPE *x1=x0+1; cannam@86: DATA_TYPE *T=init->trig+n2; cannam@86: cannam@86: int i=0; cannam@86: cannam@86: for(i=0;itrig+n2; cannam@86: x0=out+n2; cannam@86: cannam@86: for(i=0;iscale); cannam@86: x0[0] =MULT_NORM((w[0]*T[1]-w[1]*T[0])*init->scale); cannam@86: w+=2; cannam@86: T+=2; cannam@86: } cannam@86: }