Go Down

Topic: optimizing code: help avoiding modulus.. (Read 1 time) previous topic - next topic

tommyrosa

Hi
i have came up with an arduino program that outputs a waveform at a chosen frequency.
But...the interrupt vector that takes care of the output of the waveform's step's values includes a modulus (a % b):
Code: [Select]
if (conta % pitch==0){ 
    PORTD=out[n++];

The modulus really slows the whole interrupt quite a lot, according to some timing test's i've done,
(more info also on these links
-http://www.engblaze.com/faster-code-fridays-understand-division-and-speed-of-operations/
-http://bleaklow.com/2012/06/20/sensor_smoothing_and_optimised_maths_on_the_arduino.html )
             
right now the program still works fairly well, but in the future i was hoping to build it into a polyphonic synth, and for that reason i'm looking to make the interrupt routine much faster, hopefully by changing the modulus part of the code..
well, i have tried different options (creating a macro that calculated the remainder in a small loop, utilizing bitshifting and multiplications to avoid any divisions, since every other arithmetic operation is handled by the hardware).

even by google i was not able to find any code which would calculate the reminder of two numbers in a speedier way.

any suggestions?

the whole code i'm using right now:
Code: [Select]
#include <math.h>
#include <TimerOne.h>
#include <avr/interrupt.h>
#include <stdlib.h>

#define max_steps 200
#define interrupt_freq 40000 //25 microseconds = 40 Khz... minimum time for the interrupt vector to execute..
                             //the "conta % pitch" takes A LOT of cycles...


volatile char out[max_steps+20]; //just in case
volatile int n=0;
volatile unsigned int conta=0;
volatile unsigned int pitch=0;
volatile unsigned int steps=0;

double freq=0;
int tr=0;


void setup(){

  DDRD  = B11111111;    //port C set all as output for dac

  freq = 261.63;  //middle DO note freq
 
  set_freq(freq);
  fill_table(steps);

  Timer1.initialize(1000000/interrupt_freq); //converts HZ to micros..
  Timer1.attachInterrupt( DAC_out );
}


//outputs the values using a R2R DAC...

void DAC_out(){
  conta++;  //overflow should not be too much of a problem..in case change to unsigned long..

  if (conta % pitch==0){  //TODO: change modulus to something without any divisions for speed
    PORTD=out[n++];
    if (n > steps) n=0;
  }
}



//determine the number of steps the waveform must have and the
//pitch prescaler to meet the desired frequency

void set_freq(double freq){
  pitch=round(interrupt_freq/(freq*(max_steps-1))+0.5); //rounds always up, by adding 0.5
  steps=interrupt_freq/(freq*pitch);
}

//fills the output array with the value of each waveform step...

void fill_table(int wavesteps){
  for (int x=0; x<wavesteps ; x++){
    out[x]=triangle(x,wavesteps)+127;
  }
}



void loop(){
}

/////////////_____-----_____----- WaveShape functions -----_____-----_____\\\\\\\\\\\\\

int sinewave(int x,int num_steps){  //---ok
  double c=map(x,0,num_steps,0,PI);
  double d=map(tr,0,1023,0,60);
  return (((128-d)*sin(c)))+((d)*sin((10)*c));
}

int square(int x,int num_steps){ //---ok
  int y;
  if (tr==0)  y=-1;
  else y=map(tr,0,1023,5,num_steps);
  if (x<=y) return 128;   
  else return -128;
}

int triangle(int x,int num_steps){  //---ok
  double c=map(tr,0,1023,1,num_steps);
  if (x<=tr) return (256/c)*x-128;   
  else return (256 / (c-num_steps))*(x-num_steps)-128;
}

int noise(int x,int num_steps){   //---ok
  double c=map(x,0,num_steps,0,PI);
  if (random(1023)+5<tr) return random(256)-128;
  else return 128*sin(c);
}



Coding Badly


Several things...

conta does not need to be volatile.  That change should shave off a few machine instructions.

• This eliminates the modulus, is much faster, and (assuming I did not make a mistake) is functionally equivalent...

Code: [Select]
void DAC_out(){
  conta++;  //overflow should not be too much of a problem..in case change to unsigned long..

  if (conta >= pitch){
    PORTD=out[n++];
    if (n > steps) n=0;
    conta = 0;
  }
}


pitch is shared with the interrupt service routine and is multi-byte so access needs to be protected (disable/enable interrupts).

pitch does not need to be volatile but I would leave it volatile to indicate it is shared with an interrupt service routine.  I believe the generated code will be identical however it is declared.

steps is shared with the interrupt service routine and is multi-byte so access needs to be protected (disable/enable interrupts).

steps does not need to be volatile but I would leave it volatile to indicate it is shared with an interrupt service routine.  I believe the generated code will be identical however it is declared.

tommyrosa

thanks for the suggestions, i changed conta to not be volatile anymore...

the basic idea behind the modulus is to create polyphony, as explained in this link --> http://little-scale.blogspot.co.nz/2008/02/simple-polyphonic-synth-with-just.html.
right now my program has a single monophonic output, but i was hoping to implement polyphony once i figured out how to speed up the interrupt routine...
so, yes, your solution would work right now, but it's not the kind of solution i was after (unless there is a way to implement polyphony with your solution that i'm missing)..






Coding Badly


The problem is that Mr. Tomczak used mod for two very different purposes which is generally a very bad idea.  Instead, if you create a second variable to serve the second purpose, it becomes trivial to eliminate the modulus...

Code: [Select]
uint16_t accumulator[4];
...
uint16_t limit;
limit = analogRead(j) >> 2 & B11111110;
++accumulator[j];
if ( accumulator[j] >= limit )
{
  accumulator[j] = 0;
}
uint16_t value = accumulator[j] / (limit / 2);
state = state + value;

marco_c

Depending on the relative sizes of the numbers, subtracting pitch from conta until it is less than conta gives you the remainder if it was divided (modulus). This can be done in a very tight loop and if the numbers are close only a few subtractions are necessary.
Arduino libraries http://arduinocode.codeplex.com
Parola hardware & library http://parola.codeplex.com

Go Up