/* ĠCopyright Ġ( c ) Ġ 2 0 0 3 - 2 0 0 4 , ĠMark ĠBor ger ding ĊĠĠ ĠCopyright Ġ( c ) Ġ 2 0 0 7 - 2 0 0 8 ĠC SI RO ĊĠĠ ĠCopyright Ġ( c ) Ġ 2 0 0 7 - 2 0 1 1 ĠX iph . Org ĠFoundation ĊĠĠ ĠModified Ġfrom ĠK ISS - FFT Ġby ĠJean - Mar c ĠVal in ĊĠĠ ĠPort ed Ġto ĠJava Ġby ĠLog an ĠSt rom berg ĊĊĠĠ ĠRedistribution Ġand Ġuse Ġin Ġsource Ġand Ġbinary Ġforms , Ġwith Ġor Ġwithout ĊĠĠ Ġmodification , Ġare Ġpermitted Ġprovided Ġthat Ġthe Ġfollowing Ġconditions ĊĠĠ Ġare Ġmet : ĊĊĠĠ Ġ- ĠRedistributions Ġof Ġsource Ġcode Ġmust Ġretain Ġthe Ġabove Ġcopyright ĊĠĠ Ġnotice , Ġthis Ġlist Ġof Ġconditions Ġand Ġthe Ġfollowing Ġdisclaimer . ĊĊĠĠ Ġ- ĠRedistributions Ġin Ġbinary Ġform Ġmust Ġreproduce Ġthe Ġabove Ġcopyright ĊĠĠ Ġnotice , Ġthis Ġlist Ġof Ġconditions Ġand Ġthe Ġfollowing Ġdisclaimer Ġin Ġthe ĊĠĠ Ġdocumentation Ġand / or Ġother Ġmaterials Ġprovided Ġwith Ġthe Ġdistribution . ĊĊĠĠ Ġ- ĠNeither Ġthe Ġname Ġof ĠInternet ĠSociety , ĠI ET F Ġor ĠI ET F ĠTrust , Ġnor Ġthe ĊĠĠ Ġnames Ġof Ġspecific Ġcontributors , Ġmay Ġbe Ġused Ġto Ġendorse Ġor Ġpromote ĊĠĠ Ġproducts Ġderived Ġfrom Ġthis Ġsoftware Ġwithout Ġspecific Ġprior Ġwritten ĊĠĠ Ġpermission . ĊĊĠĠ ĠTHIS ĠSOFTWARE ĠIS ĠPROVIDED ĠBY ĠTHE ĠCOPYRIGHT ĠHOLDERS ĠAND ĠCONTRIBUTORS ĊĠĠ Ġ`` AS ĠIS '' ĠAND ĠANY ĠEXPRESS ĠOR ĠIMPLIED ĠWARRANTIES , ĠINCLUDING , ĠBUT ĠNOT ĊĠĠ ĠLIMITED ĠTO , ĠTHE ĠIMPLIED ĠWARRANTIES ĠOF ĠMERCHANTABILITY ĠAND ĠFITNESS ĠFOR ĊĠĠ ĠA ĠPARTICULAR ĠPURPOSE ĠARE ĠDISCLAIMED . ĠIN ĠNO ĠEVENT ĠSHALL ĠTHE ĠCOPYRIGHT ĠOWNER ĊĠĠ ĠOR ĠCONTRIBUTORS ĠBE ĠLIABLE ĠFOR ĠANY ĠDIRECT , ĠINDIRECT , ĠINCIDENTAL , ĠSPECIAL , ĊĠĠ ĠEXEMPLARY , ĠOR ĠCONSEQUENTIAL ĠDAMAGES Ġ( INCLUDING , ĠBUT ĠNOT ĠLIMITED ĠTO , ĊĠĠ ĠPROCUREMENT ĠOF ĠSUBSTITUTE ĠGOODS ĠOR ĠSERVICES ; ĠLOSS ĠOF ĠUSE , ĠDATA , ĠOR ĊĠĠ ĠPROFITS ; ĠOR ĠBUSINESS ĠINTERRUPTION ) ĠHOWEVER ĠCAUSED ĠAND ĠON ĠANY ĠTHEORY ĠOF ĊĠĠ ĠLIABILITY , ĠWHETHER ĠIN ĠCONTRACT , ĠSTRICT ĠLIABILITY , ĠOR ĠTORT Ġ( INCLUDING ĊĠĠ ĠNEGLIGENCE ĠOR ĠOTHERWISE ) ĠARISING ĠIN ĠANY ĠWAY ĠOUT ĠOF ĠTHE ĠUSE ĠOF ĠTHIS ĊĠĠ ĠSOFTWARE , ĠEVEN ĠIF ĠADVISED ĠOF ĠTHE ĠPOSSIBILITY ĠOF ĠSUCH ĠDAMAGE . Ċ Ġ*/ Ċ package Ġcom . so y wiz . kor au . format . org . con cent us Ċ Ċ internal Ġobject ĠMD CT Ġ{ ĊĊĠĠĠ Ġ/* ĠForward ĠMD CT Ġtr ashes Ġthe Ġinput Ġarray Ġ*/ ĊĠĠĠ Ġfun Ġcl t _ md ct _ forward ( ĊĠĠĠĠĠĠĠ Ġl : ĠMD CT Lookup , Ġinput : ĠInt Array , Ġinput _ ptr : ĠInt , Ġoutput : ĠInt Array , Ġoutput _ ptr : ĠInt , ĊĠĠĠĠĠĠĠ Ġwindow : ĠInt Array , Ġoverlap : ĠInt , Ġshift : ĠInt , Ġstride : ĠInt ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġi : ĠInt ĊĠĠĠĠĠĠĠ Ġvar ĠN : ĠInt ĊĠĠĠĠĠĠĠ Ġval ĠN 2 : ĠInt ĊĠĠĠĠĠĠĠ Ġval ĠN 4 : ĠInt ĊĠĠĠĠĠĠĠ Ġval Ġf : ĠInt Array ĊĠĠĠĠĠĠĠ Ġval Ġf 2 : ĠInt Array ĊĠĠĠĠĠĠĠ Ġval Ġst Ġ= Ġl . k fft [ shift ] ĊĠĠĠĠĠĠĠ Ġval Ġtrig : ĠShort Array ? ĊĠĠĠĠĠĠĠ Ġvar Ġtrig _ ptr Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġscale : ĠInt ĊĊĠĠĠĠĠĠĠ Ġval Ġscale _ shift Ġ= Ġst !!. scale _ shift Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġscale Ġ= Ġst . scale . toInt () ĊĊĠĠĠĠĠĠĠ ĠN Ġ= Ġl . n ĊĠĠĠĠĠĠĠ Ġtrig Ġ= Ġl . trig ĊĠĠĠĠĠĠĠ Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġshift ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠN Ġ= ĠN Ġshr Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtrig _ ptr Ġ+= ĠN ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠN 2 Ġ= ĠN Ġshr Ġ 1 ĊĠĠĠĠĠĠĠ ĠN 4 Ġ= ĠN Ġshr Ġ 2 ĊĊĠĠĠĠĠĠĠ Ġf Ġ= ĠInt Array ( N 2 ) ĊĠĠĠĠĠĠĠ Ġf 2 Ġ= ĠInt Array ( N 4 Ġ* Ġ 2 ) ĊĊĠĠĠĠĠĠĠ Ġ/* ĠConsider Ġthe Ġinput Ġto Ġbe Ġcomposed Ġof Ġfour Ġblocks : Ġ[ a , Ġb , Ġc , Ġd ] Ġ*/ ĊĠĠĠĠĠĠĠ Ġ/* ĠWindow , Ġshuffle , Ġfold Ġ*/ ĊĠĠĠĠĠĠĠ Ġrun Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠTemp Ġpointers Ġto Ġmake Ġit Ġreally Ġclear Ġto Ġthe Ġcompiler Ġwhat Ġwe 're Ġdoing Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġxp 1 Ġ= Ġinput _ ptr Ġ+ Ġ( overlap Ġshr Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġxp 2 Ġ= Ġinput _ ptr Ġ+ ĠN 2 Ġ- Ġ 1 Ġ+ Ġ( overlap Ġshr Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġy p Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġwp 1 Ġ= Ġoverlap Ġshr Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġwp 2 Ġ= Ġ( overlap Ġshr Ġ 1 ) Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġoverlap Ġ+ Ġ 3 Ġshr Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠReal Ġpart Ġarrange d Ġas Ġ- d - c R , ĠIm ag Ġpart Ġarrange d Ġas Ġ- b + a R */ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf [ yp ++] Ġ= ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 2 ], Ġinput [ xp 1 Ġ+ ĠN 2 ]) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 1 ], Ġinput [ xp 2 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf [ yp ++] Ġ= ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 1 ], Ġinput [ xp 1 ]) Ġ- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 2 ], Ġinput [ xp 2 Ġ- ĠN 2 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġxp 1 Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġxp 2 Ġ-= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwp 1 Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwp 2 Ġ-= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwp 1 Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwp 2 Ġ= Ġoverlap Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< ĠN 4 Ġ- Ġ( overlap Ġ+ Ġ 3 Ġshr Ġ 2 )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠReal Ġpart Ġarrange d Ġas Ġa - b R , ĠIm ag Ġpart Ġarrange d Ġas Ġ- c - d R Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf [ yp ++] Ġ= Ġinput [ xp 2 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf [ yp ++] Ġ= Ġinput [ xp 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġxp 1 Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġxp 2 Ġ-= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< ĠN 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠReal Ġpart Ġarrange d Ġas Ġa - b R , ĠIm ag Ġpart Ġarrange d Ġas Ġ- c - d R Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf [ yp ++] Ġ= ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 2 ], Ġinput [ xp 2 ]) Ġ- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 1 ], Ġinput [ xp 1 Ġ- ĠN 2 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf [ yp ++] Ġ= ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 2 ], Ġinput [ xp 1 ]) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 1 ], Ġinput [ xp 2 Ġ+ ĠN 2 ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġxp 1 Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġxp 2 Ġ-= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwp 1 Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwp 2 Ġ-= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ/* ĠPre - rotation Ġ*/ ĊĠĠĠĠĠĠĠ Ġrun Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġy p Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġtrig _ ptr ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< ĠN 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt 0 : ĠShort ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt 1 : ĠShort ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġre : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġim : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy r : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy i : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt 0 Ġ= Ġtrig ! ![ t Ġ+ Ġi ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt 1 Ġ= Ġtrig [ t Ġ+ ĠN 4 Ġ+ Ġi ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġre Ġ= Ġf [ yp ++] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġim Ġ= Ġf [ yp ++] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy r Ġ= ĠK iss FFT . S _ MUL ( re , Ġt 0 ) Ġ- ĠK iss FFT . S _ MUL ( im , Ġt 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy i Ġ= ĠK iss FFT . S _ MUL ( im , Ġt 0 ) Ġ+ ĠK iss FFT . S _ MUL ( re , Ġt 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf 2 [ 2 Ġ* Ġst . bit rev ! ![ i ]] Ġ= ĠIn lines . P SH R 3 2 ( In lines . MULT 1 6 _ 3 2 _ Q 1 6 ( scale , Ġy r ), Ġscale _ shift ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf 2 [ 2 Ġ* Ġst . bit rev ! ![ i ] Ġ+ Ġ 1 ] Ġ= ĠIn lines . P SH R 3 2 ( In lines . MULT 1 6 _ 3 2 _ Q 1 6 ( scale , Ġy i ), Ġscale _ shift ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/* ĠN / 4 Ġcomplex ĠFFT , Ġdoes Ġnot Ġdown scale Ġanymore Ġ*/ ĊĠĠĠĠĠĠĠ ĠK iss FFT . opus _ fft _ impl ( st , Ġf 2 , Ġ 0 ) ĊĊĠĠĠĠĠĠĠ Ġ/* ĠPost - rotate Ġ*/ ĊĠĠĠĠĠĠĠ Ġrun Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠTemp Ġpointers Ġto Ġmake Ġit Ġreally Ġclear Ġto Ġthe Ġcompiler Ġwhat Ġwe 're Ġdoing Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġfp Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġy p 1 Ġ= Ġoutput _ ptr ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġy p 2 Ġ= Ġoutput _ ptr Ġ+ Ġstride Ġ* Ġ( N 2 Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġtrig _ ptr ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< ĠN 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy r : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy i : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy r Ġ= ĠK iss FFT . S _ MUL ( f 2 [ fp Ġ+ Ġ 1 ], Ġtrig ! ![ t Ġ+ ĠN 4 Ġ+ Ġi ]) Ġ- ĠK iss FFT . S _ MUL ( f 2 [ fp ], Ġtrig ! ![ t Ġ+ Ġi ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy i Ġ= ĠK iss FFT . S _ MUL ( f 2 [ fp ], Ġtrig ! ![ t Ġ+ ĠN 4 Ġ+ Ġi ]) Ġ+ ĠK iss FFT . S _ MUL ( f 2 [ fp Ġ+ Ġ 1 ], Ġtrig ! ![ t Ġ+ Ġi ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ yp 1 ] Ġ= Ġy r ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ yp 2 ] Ġ= Ġy i ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfp Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy p 1 Ġ+= Ġ 2 Ġ* Ġstride ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy p 2 Ġ-= Ġ 2 Ġ* Ġstride ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcl t _ md ct _ backward ( ĊĠĠĠĠĠĠĠ Ġl : ĠMD CT Lookup , Ġinput : ĠInt Array , Ġinput _ ptr : ĠInt , Ġoutput : ĠInt Array , Ġoutput _ ptr : ĠInt , ĊĠĠĠĠĠĠĠ Ġwindow : ĠInt Array , Ġoverlap : ĠInt , Ġshift : ĠInt , Ġstride : ĠInt ĊĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġinput _ ptr Ġ= Ġinput _ ptr ĊĠĠĠĠĠĠĠ Ġvar Ġi : ĠInt ĊĠĠĠĠĠĠĠ Ġvar ĠN : ĠInt ĊĠĠĠĠĠĠĠ Ġval ĠN 2 : ĠInt ĊĠĠĠĠĠĠĠ Ġval ĠN 4 : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġtrig Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġxp 1 : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġxp 2 : ĠInt ĊĠĠĠĠĠĠĠ Ġval Ġy p : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġy p 0 : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġy p 1 : ĠInt ĊĊĠĠĠĠĠĠĠ ĠN Ġ= Ġl . n ĊĠĠĠĠĠĠĠ Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġshift ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠN Ġ= ĠN Ġshr Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtrig Ġ+= ĠN ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠN 2 Ġ= ĠN Ġshr Ġ 1 ĊĠĠĠĠĠĠĠ ĠN 4 Ġ= ĠN Ġshr Ġ 2 ĊĊĠĠĠĠĠĠĠ Ġ/* ĠPre - rotate Ġ*/ ĊĠĠĠĠĠĠĠ Ġ/* ĠTemp Ġpointers Ġto Ġmake Ġit Ġreally Ġclear Ġto Ġthe Ġcompiler Ġwhat Ġwe 're Ġdoing Ġ*/ ĊĠĠĠĠĠĠĠ Ġxp 2 Ġ= Ġinput _ ptr Ġ+ Ġstride Ġ* Ġ( N 2 Ġ- Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġy p Ġ= Ġoutput _ ptr Ġ+ Ġ( overlap Ġshr Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġval Ġbit rev Ġ= Ġl . k fft [ shift ] !!. bit rev ĊĠĠĠĠĠĠĠ Ġvar Ġbit rav _ ptr Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< ĠN 4 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrev Ġ= Ġbit rev ! ![ bitr av _ ptr ++ ]. toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy pr Ġ= Ġy p Ġ+ Ġ 2 Ġ* Ġrev ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠWe Ġswap Ġreal Ġand Ġimag Ġbecause Ġwe Ġuse Ġan ĠFFT Ġinstead Ġof Ġan ĠI FFT . Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ y pr Ġ+ Ġ 1 ] Ġ= ĠK iss FFT . S _ MUL ( input [ xp 2 ], Ġl . trig ! ![ trig Ġ+ Ġi ]) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠK iss FFT . S _ MUL ( input [ input _ ptr ], Ġl . trig ! ![ trig Ġ+ ĠN 4 Ġ+ Ġi ]) Ġ// yr ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ y pr ] Ġ= ĠK iss FFT . S _ MUL ( input [ input _ ptr ], Ġl . trig ! ![ trig Ġ+ Ġi ]) Ġ- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠK iss FFT . S _ MUL ( input [ xp 2 ], Ġl . trig ! ![ trig Ġ+ ĠN 4 Ġ+ Ġi ]) Ġ// yi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠSt oring Ġthe Ġpre - rotation Ġdirectly Ġin Ġthe Ġbit rev Ġorder . Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġinput _ ptr Ġ+= Ġ 2 Ġ* Ġstride ĊĠĠĠĠĠĠĠĠĠĠĠ Ġxp 2 Ġ-= Ġ 2 Ġ* Ġstride ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ ĠK iss FFT . opus _ fft _ impl ( l . k fft ! ![ shift ] !! , Ġoutput , Ġoutput _ ptr Ġ+ Ġ( overlap Ġshr Ġ 1 )) ĊĊĠĠĠĠĠĠĠ Ġ/* ĠPost - rotate Ġand Ġde - shuffle Ġfrom Ġboth Ġends Ġof Ġthe Ġbuffer Ġat Ġonce Ġto Ġmake ĊĠĠĠĠĠĠĠĠĠĠĠ Ġit Ġin - place . Ġ*/ ĊĠĠĠĠĠĠĠ Ġy p 0 Ġ= Ġoutput _ ptr Ġ+ Ġ( overlap Ġshr Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġy p 1 Ġ= Ġoutput _ ptr Ġ+ Ġ( overlap Ġshr Ġ 1 ) Ġ+ ĠN 2 Ġ- Ġ 2 ĊĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġtrig ĊĊĠĠĠĠĠĠĠ Ġ/* ĠLoop Ġto Ġ( N 4 + 1 )>> 1 Ġto Ġhandle Ġodd ĠN 4 . ĠWhen ĠN 4 Ġis Ġodd , Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmiddle Ġpair Ġwill Ġbe Ġcomputed Ġtwice . Ġ*/ ĊĠĠĠĠĠĠĠ Ġval Ġt N 4 m 1 Ġ= Ġt Ġ+ ĠN 4 Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġval Ġt N 2 m 1 Ġ= Ġt Ġ+ ĠN 2 Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< ĠN 4 Ġ+ Ġ 1 Ġshr Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġre : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġim : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġy r : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġy i : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġt 0 : ĠShort ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġt 1 : ĠShort ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠWe Ġswap Ġreal Ġand Ġimag Ġbecause Ġwe 're Ġusing Ġan ĠFFT Ġinstead Ġof Ġan ĠI FFT . Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġre Ġ= Ġoutput [ yp 0 Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġim Ġ= Ġoutput [ yp 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 0 Ġ= Ġl . trig ! ![ t Ġ+ Ġi ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 1 Ġ= Ġl . trig ! ![ t Ġ+ ĠN 4 Ġ+ Ġi ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠWe 'd Ġscale Ġup Ġby Ġ 2 Ġhere , Ġbut Ġinstead Ġit 's Ġdone Ġwhen Ġmixing Ġthe Ġwindows Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy r Ġ= ĠK iss FFT . S _ MUL ( re , Ġt 0 ) Ġ+ ĠK iss FFT . S _ MUL ( im , Ġt 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy i Ġ= ĠK iss FFT . S _ MUL ( re , Ġt 1 ) Ġ- ĠK iss FFT . S _ MUL ( im , Ġt 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠWe Ġswap Ġreal Ġand Ġimag Ġbecause Ġwe 're Ġusing Ġan ĠFFT Ġinstead Ġof Ġan ĠI FFT . Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġre Ġ= Ġoutput [ yp 1 Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġim Ġ= Ġoutput [ yp 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ yp 0 ] Ġ= Ġy r ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ yp 1 Ġ+ Ġ 1 ] Ġ= Ġy i ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 0 Ġ= Ġl . trig ! ![ t N 4 m 1 Ġ- Ġi ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 1 Ġ= Ġl . trig ! ![ t N 2 m 1 Ġ- Ġi ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ/* ĠWe 'd Ġscale Ġup Ġby Ġ 2 Ġhere , Ġbut Ġinstead Ġit 's Ġdone Ġwhen Ġmixing Ġthe Ġwindows Ġ*/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy r Ġ= ĠK iss FFT . S _ MUL ( re , Ġt 0 ) Ġ+ ĠK iss FFT . S _ MUL ( im , Ġt 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy i Ġ= ĠK iss FFT . S _ MUL ( re , Ġt 1 ) Ġ- ĠK iss FFT . S _ MUL ( im , Ġt 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ yp 1 ] Ġ= Ġy r ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ yp 0 Ġ+ Ġ 1 ] Ġ= Ġy i ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy p 0 Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy p 1 Ġ-= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/* ĠM irror Ġon Ġboth Ġsides Ġfor ĠT DAC Ġ*/ ĊĠĠĠĠĠĠĠ Ġxp 1 Ġ= Ġoutput _ ptr Ġ+ Ġoverlap Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġy p 1 Ġ= Ġoutput _ ptr ĊĠĠĠĠĠĠĠ Ġvar Ġwp 1 Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġwp 2 Ġ= Ġoverlap Ġ- Ġ 1 ĊĊĠĠĠĠĠĠĠ Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġoverlap Ġ/ Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx 1 Ġ= Ġoutput [ xp 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx 2 Ġ= Ġoutput [ yp 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ yp 1 ++] Ġ= ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 2 ], Ġx 2 ) Ġ- ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 1 ], Ġx 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoutput [ xp 1 -- ] Ġ= ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 1 ], Ġx 2 ) Ġ+ ĠIn lines . MULT 1 6 _ 3 2 _ Q 1 5 ( window [ wp 2 ], Ġx 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwp 1 ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwp 2 -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ