cannam@127: /*
cannam@127:  * Copyright (c) 2003, 2007-14 Matteo Frigo
cannam@127:  * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
cannam@127:  *
cannam@127:  * This program is free software; you can redistribute it and/or modify
cannam@127:  * it under the terms of the GNU General Public License as published by
cannam@127:  * the Free Software Foundation; either version 2 of the License, or
cannam@127:  * (at your option) any later version.
cannam@127:  *
cannam@127:  * This program is distributed in the hope that it will be useful,
cannam@127:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
cannam@127:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
cannam@127:  * GNU General Public License for more details.
cannam@127:  *
cannam@127:  * You should have received a copy of the GNU General Public License
cannam@127:  * along with this program; if not, write to the Free Software
cannam@127:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
cannam@127:  *
cannam@127:  */
cannam@127: 
cannam@127: 
cannam@127: /* Twiddle manipulation */
cannam@127: 
cannam@127: #include "ifftw.h"
cannam@127: #include <math.h>
cannam@127: 
cannam@127: #define HASHSZ 109
cannam@127: 
cannam@127: /* hash table of known twiddle factors */
cannam@127: static twid *twlist[HASHSZ];
cannam@127: 
cannam@127: static INT hash(INT n, INT r)
cannam@127: {
cannam@127:      INT h = n * 17 + r;
cannam@127: 
cannam@127:      if (h < 0) h = -h;
cannam@127: 
cannam@127:      return (h % HASHSZ);
cannam@127: }
cannam@127: 
cannam@127: static int equal_instr(const tw_instr *p, const tw_instr *q)
cannam@127: {
cannam@127:      if (p == q)
cannam@127:           return 1;
cannam@127: 
cannam@127:      for (;; ++p, ++q) {
cannam@127:           if (p->op != q->op)
cannam@127: 	       return 0;
cannam@127: 
cannam@127: 	  switch (p->op) {
cannam@127: 	      case TW_NEXT:
cannam@127: 		   return (p->v == q->v); /* p->i is ignored */
cannam@127: 
cannam@127: 	      case TW_FULL:
cannam@127: 	      case TW_HALF:
cannam@127: 		   if (p->v != q->v) return 0; /* p->i is ignored */
cannam@127: 		   break;
cannam@127: 
cannam@127: 	      default:
cannam@127: 		   if (p->v != q->v || p->i != q->i) return 0;
cannam@127: 		   break;
cannam@127: 	  }
cannam@127:      }
cannam@127:      A(0 /* can't happen */);
cannam@127: }
cannam@127: 
cannam@127: static int ok_twid(const twid *t, 
cannam@127: 		   enum wakefulness wakefulness,
cannam@127: 		   const tw_instr *q, INT n, INT r, INT m)
cannam@127: {
cannam@127:      return (wakefulness == t->wakefulness &&
cannam@127: 	     n == t->n &&
cannam@127: 	     r == t->r && 
cannam@127: 	     m <= t->m && 
cannam@127: 	     equal_instr(t->instr, q));
cannam@127: }
cannam@127: 
cannam@127: static twid *lookup(enum wakefulness wakefulness,
cannam@127: 		    const tw_instr *q, INT n, INT r, INT m)
cannam@127: {
cannam@127:      twid *p;
cannam@127: 
cannam@127:      for (p = twlist[hash(n,r)]; 
cannam@127: 	  p && !ok_twid(p, wakefulness, q, n, r, m); 
cannam@127: 	  p = p->cdr)
cannam@127:           ;
cannam@127:      return p;
cannam@127: }
cannam@127: 
cannam@127: static INT twlen0(INT r, const tw_instr *p, INT *vl)
cannam@127: {
cannam@127:      INT ntwiddle = 0;
cannam@127: 
cannam@127:      /* compute length of bytecode program */
cannam@127:      A(r > 0);
cannam@127:      for ( ; p->op != TW_NEXT; ++p) {
cannam@127: 	  switch (p->op) {
cannam@127: 	      case TW_FULL:
cannam@127: 		   ntwiddle += (r - 1) * 2;
cannam@127: 		   break;
cannam@127: 	      case TW_HALF:
cannam@127: 		   ntwiddle += (r - 1);
cannam@127: 		   break;
cannam@127: 	      case TW_CEXP:
cannam@127: 		   ntwiddle += 2;
cannam@127: 		   break;
cannam@127: 	      case TW_COS:
cannam@127: 	      case TW_SIN:
cannam@127: 		   ntwiddle += 1;
cannam@127: 		   break;
cannam@127: 	  }
cannam@127:      }
cannam@127: 
cannam@127:      *vl = (INT)p->v;
cannam@127:      return ntwiddle;
cannam@127: }
cannam@127: 
cannam@127: INT X(twiddle_length)(INT r, const tw_instr *p)
cannam@127: {
cannam@127:      INT vl;
cannam@127:      return twlen0(r, p, &vl);
cannam@127: }
cannam@127: 
cannam@127: static R *compute(enum wakefulness wakefulness,
cannam@127: 		  const tw_instr *instr, INT n, INT r, INT m)
cannam@127: {
cannam@127:      INT ntwiddle, j, vl;
cannam@127:      R *W, *W0;
cannam@127:      const tw_instr *p;
cannam@127:      triggen *t = X(mktriggen)(wakefulness, n);
cannam@127: 
cannam@127:      p = instr;
cannam@127:      ntwiddle = twlen0(r, p, &vl);
cannam@127: 
cannam@127:      A(m % vl == 0);
cannam@127: 
cannam@127:      W0 = W = (R *)MALLOC((ntwiddle * (m / vl)) * sizeof(R), TWIDDLES);
cannam@127: 
cannam@127:      for (j = 0; j < m; j += vl) {
cannam@127:           for (p = instr; p->op != TW_NEXT; ++p) {
cannam@127: 	       switch (p->op) {
cannam@127: 		   case TW_FULL: {
cannam@127: 			INT i;
cannam@127: 			for (i = 1; i < r; ++i) {
cannam@127: 			     A((j + (INT)p->v) * i < n);
cannam@127: 			     A((j + (INT)p->v) * i > -n);
cannam@127: 			     t->cexp(t, (j + (INT)p->v) * i, W);
cannam@127: 			     W += 2;
cannam@127: 			}
cannam@127: 			break;
cannam@127: 		   }
cannam@127: 
cannam@127: 		   case TW_HALF: {
cannam@127: 			INT i;
cannam@127: 			A((r % 2) == 1);
cannam@127: 			for (i = 1; i + i < r; ++i) {
cannam@127: 			     t->cexp(t, MULMOD(i, (j + (INT)p->v), n), W);
cannam@127: 			     W += 2;
cannam@127: 			}
cannam@127: 			break;
cannam@127: 		   }
cannam@127: 
cannam@127: 		   case TW_COS: {
cannam@127: 			R d[2];
cannam@127: 
cannam@127: 			A((j + (INT)p->v) * p->i < n);
cannam@127: 			A((j + (INT)p->v) * p->i > -n);
cannam@127: 			t->cexp(t, (j + (INT)p->v) * (INT)p->i, d);
cannam@127: 			*W++ = d[0];
cannam@127: 			break;
cannam@127: 		   }
cannam@127: 
cannam@127: 		   case TW_SIN: {
cannam@127: 			R d[2];
cannam@127: 
cannam@127: 			A((j + (INT)p->v) * p->i < n);
cannam@127: 			A((j + (INT)p->v) * p->i > -n);
cannam@127: 			t->cexp(t, (j + (INT)p->v) * (INT)p->i, d);
cannam@127: 			*W++ = d[1];
cannam@127: 			break;
cannam@127: 		   }
cannam@127: 
cannam@127: 		   case TW_CEXP:
cannam@127: 			A((j + (INT)p->v) * p->i < n);
cannam@127: 			A((j + (INT)p->v) * p->i > -n);
cannam@127: 			t->cexp(t, (j + (INT)p->v) * (INT)p->i, W);
cannam@127: 			W += 2;
cannam@127: 			break;
cannam@127: 	       }
cannam@127: 	  }
cannam@127:      }
cannam@127: 
cannam@127:      X(triggen_destroy)(t);
cannam@127:      return W0;
cannam@127: }
cannam@127: 
cannam@127: static void mktwiddle(enum wakefulness wakefulness,
cannam@127: 		      twid **pp, const tw_instr *instr, INT n, INT r, INT m)
cannam@127: {
cannam@127:      twid *p;
cannam@127:      INT h;
cannam@127: 
cannam@127:      if ((p = lookup(wakefulness, instr, n, r, m))) {
cannam@127:           ++p->refcnt;
cannam@127:      } else {
cannam@127: 	  p = (twid *) MALLOC(sizeof(twid), TWIDDLES);
cannam@127: 	  p->n = n;
cannam@127: 	  p->r = r;
cannam@127: 	  p->m = m;
cannam@127: 	  p->instr = instr;
cannam@127: 	  p->refcnt = 1;
cannam@127: 	  p->wakefulness = wakefulness;
cannam@127: 	  p->W = compute(wakefulness, instr, n, r, m);
cannam@127: 
cannam@127: 	  /* cons! onto twlist */
cannam@127: 	  h = hash(n, r);
cannam@127: 	  p->cdr = twlist[h];
cannam@127: 	  twlist[h] = p;
cannam@127:      }
cannam@127: 
cannam@127:      *pp = p;
cannam@127: }
cannam@127: 
cannam@127: static void twiddle_destroy(twid **pp)
cannam@127: {
cannam@127:      twid *p = *pp;
cannam@127:      twid **q;
cannam@127: 
cannam@127:      if ((--p->refcnt) == 0) {
cannam@127: 	  /* remove p from twiddle list */
cannam@127: 	  for (q = &twlist[hash(p->n, p->r)]; *q; q = &((*q)->cdr)) {
cannam@127: 	       if (*q == p) {
cannam@127: 		    *q = p->cdr;
cannam@127: 		    X(ifree)(p->W);
cannam@127: 		    X(ifree)(p);
cannam@127: 		    *pp = 0;
cannam@127: 		    return;
cannam@127: 	       }
cannam@127: 	  }
cannam@127: 	  A(0 /* can't happen */ );
cannam@127:      }
cannam@127: }
cannam@127: 
cannam@127: 
cannam@127: void X(twiddle_awake)(enum wakefulness wakefulness, twid **pp, 
cannam@127: 		      const tw_instr *instr, INT n, INT r, INT m)
cannam@127: {
cannam@127:      switch (wakefulness) {
cannam@127: 	 case SLEEPY: 
cannam@127: 	      twiddle_destroy(pp);
cannam@127: 	      break;
cannam@127: 	 default:
cannam@127: 	      mktwiddle(wakefulness, pp, instr, n, r, m);
cannam@127: 	      break;
cannam@127:      }
cannam@127: }