beatDetektor.js

    var BD_DETECTION_RANGES  = 128;
    var BD_DETECTION_RATE    = 10.0;
    var BD_DETECTION_FACTOR  = 0.98;
        
    var BD_QUALITY_DECAY     = 0.5;
    var BD_QUALITY_TOLERANCE = 0.9;
    var BD_QUALITY_REWARD    = 1.0;
    var BD_QUALITY_LOSS      = 0.2;
    var BD_QUALITY_STEP      = 0.5;
    var BD_QUALITY_MINIMUM   = 100.0;
    
    var BPM_MIN;
  	var BPM_MAX;

  	var current_bpm; 
  	var winning_bpm; 
  	var win_val;
  	var win_bpm_int;

  	var bpm_predict;

  	var is_erratic;
  	var bpm_offset;
  	var last_timer;
  	var last_update;

  	var bpm_timer;
  	var beat_counter;
  	var half_counter;

  	// current average (this sample) for range n
  	var a_freq_range = new Array(BD_DETECTION_RANGES);
  	// moving average of frequency range n
  	var ma_freq_range = new Array(BD_DETECTION_RANGES);
  	// moving average of moving average of frequency range n
  	var maa_freq_range = new Array(BD_DETECTION_RANGES);
  	// timestamp of last detection for frequecy range n
  	var last_detection = new Array(BD_DETECTION_RANGES);

  	// moving average of gap lengths
  	var ma_bpm_range = new Array(BD_DETECTION_RANGES);
  	// moving average of moving average of gap lengths
  	var maa_bpm_range = new Array(BD_DETECTION_RANGES);

  	// range n quality attribute, good match = quality+, bad match = quality-, min = 0
  	var detection_quality = new Array(BD_DETECTION_RANGES);

  	// current trigger state for range n
  	var detection = new Array(BD_DETECTION_RANGES); 

  	var bpm_contest = new Array();	

    /*
  	BeatDetektor(float BPM_MIN_in=100.0,float BPM_MAX_in=200.0) :

  	current_bpm(0.0),
  	winning_bpm(0.0), 
  	win_val(0.0),
  	win_bpm_int(0),

  	bpm_predict(0),

  	is_erratic(false),
  	bpm_offset(0.0),
  	last_timer(0.0),
  	last_update(0.0),

  	bpm_timer(0.0),
  	beat_counter(0),
  	half_counter(0)

  	{
  		for (int i = 0; i < BD_DETECTION_RANGES; i++) ma_bpm_range[i] = maa_bpm_range[i] = 60.0/140.0;			
  		BPM_MIN = BPM_MIN_in;
  		BPM_MAX = BPM_MAX_in;
  	}


  	void process(float timer_seconds, std::vector<float> &fft_data);

  	*/
       
    
    function BeatDetector(timer_seconds, fft_data)
    {
    	if (!last_timer) { last_timer = timer_seconds; return; }	// ignore 0 start time

    	var timestamp = timer_seconds;

    	last_update = timer_seconds - last_timer;
    	last_timer = timer_seconds;

    	var range_step = (fft_data.size()/BD_DETECTION_RANGES);
    	var range = 0;
    	var i,x;
    	var v;

    	var bpm_floor = 60.0/BPM_MAX;
    	var bpm_ceil = 60.0/BPM_MIN;

    	for (x=0; x<fft_data.size(); x+=range_step)
    	{
    		a_freq_range[range] = 0;

    		// accumulate frequency values for this range
    		for (i = x; i<x+range_step; i++)
    		{
    			v = fabs(fft_data[i]);
    			a_freq_range[range] += v;
    		}

    		// average for range
    		a_freq_range[range] /= range_step;

    		// two sets of averages chase this one at a 

    		// moving average, increment closer to a_freq_range at a rate of 1.0 / BD_DETECTION_RATE seconds
    		ma_freq_range[range] -= (ma_freq_range[range]-a_freq_range[range])*last_update*BD_DETECTION_RATE;
    		// moving average of moving average, increment closer to ma_freq_range at a rate of 1.0 / BD_DETECTION_RATE seconds
    		maa_freq_range[range] -= (maa_freq_range[range]-ma_freq_range[range])*last_update*BD_DETECTION_RATE;

    		// if closest moving average peaks above trailing (with a tolerance of BD_DETECTION_FACTOR) then trigger a detection for this range 
    		var det = (ma_freq_range[range]*BD_DETECTION_FACTOR >= maa_freq_range[range]); // bool

    		// compute bpm clamps for comparison to gap lengths

    		// clamp detection averages to input ranges
    		if (ma_bpm_range[range] > bpm_ceil) ma_bpm_range[range] = bpm_ceil;
    		if (ma_bpm_range[range] < bpm_floor) ma_bpm_range[range] = bpm_floor;
    		if (maa_bpm_range[range] > bpm_ceil) maa_bpm_range[range] = bpm_ceil;
    		if (maa_bpm_range[range] < bpm_floor) maa_bpm_range[range] = bpm_floor;

    		// new detection since last, test it's quality
    		if (!detection[range] && det)
    		{
    			// calculate length of gap (since start of last trigger)
    			var trigger_gap = timestamp-last_detection[range];

          var REWARD_VALS = 6;
    			var reward_tolerances = [ 0.01, 0.04, 0.08, 0.1, 0.15, 0.2 ];  // 1%,  2%,  4%
    			var reward_multipliers = [ 6.0, 4.0, 2.0, 1.0/2.0, 1.0/4.0, 1.0/8.0 ];
    			var rewarded = false;
    			var quality_multiplier = 1.0;

    			// trigger falls within acceptable range, 
    			if (trigger_gap < bpm_ceil && trigger_gap > (bpm_floor))
    			{		
    				rewarded = false;
    				// compute gap and award quality

    				for (i = 0; i < REWARD_VALS; i++)
    				{
    					if (fabs(ma_bpm_range[range]-trigger_gap) < ma_bpm_range[range]*reward_tolerances[i])
    					{
    						detection_quality[range] += BD_QUALITY_REWARD * reward_multipliers[i]; 
    						quality_multiplier = 4.0 / i;
    						rewarded = true;
    					}
    				}


    				if (rewarded) 
    				{
    					last_detection[range] = timestamp;
    				}
    				else
    				{
    					quality_multiplier = 0.2;
    				}
    			}
    			else if (trigger_gap >= bpm_ceil) // low quality, gap exceeds maximum time
    			{
    				// start a new gap test, next gap is guaranteed to be longer

    				rewarded = false;				

    				// test for 1/2 beat
    				trigger_gap /= 2.0;
    				// && fabs((60.0/trigger_gap)-(60.0/ma_bpm_range[range])) < 50.0
    				if (trigger_gap < bpm_ceil && trigger_gap > (bpm_floor)) for (i = 0; i < REWARD_VALS; i++)
    				{
    					if (fabs(ma_bpm_range[range]-trigger_gap) < ma_bpm_range[range]*reward_tolerances[i])
    					{
    						detection_quality[range] += BD_QUALITY_REWARD * reward_multipliers[i]; 
    						quality_multiplier = 4.0 / i;
    						rewarded = true;
    					}
    				}

    				// decrement quality if no 1/2 beat reward
    				if (!rewarded) 
    				{
    					last_detection[range] = timestamp;	
    					quality_multiplier = 0.2;
    				}
    			}
    			else
    			{
    				quality_multiplier = 0.5;
    			}

    			if (rewarded)
    			{
    				ma_bpm_range[range] -= (ma_bpm_range[range]-trigger_gap) * BD_QUALITY_STEP * quality_multiplier;
    				maa_bpm_range[range] -= (maa_bpm_range[range]-ma_bpm_range[range]) * BD_QUALITY_STEP * quality_multiplier;
    			}
    			else
    			{
    				detection_quality[range]-=BD_QUALITY_LOSS*quality_multiplier;
    			}

    		}

    		if (!det && detection[range]) detection_quality[range] *= BD_QUALITY_DECAY;
    		if (!det && timestamp-last_detection[range] > bpm_ceil) detection_quality[range] -= detection_quality[range]*BD_QUALITY_DECAY*last_update;

    		// quality bottomed out, set to 0
    		if (detection_quality[range] < 0) detection_quality[range]=0;


    		detection[range] = det;		

    		range++;
    	}


    	// total contribution weight
    	var quality_total = 0.0;

    	// total of bpm values
    	var bpm_total = 0.0;
    	// number of bpm ranges that contributed to this test
    	var bpm_contributions = 0;


    	// accumulate quality weight total
    	for (x=0; x<BD_DETECTION_RANGES; x++)
    	{
    		quality_total += detection_quality[x];
    	}

    	// determine the average weight of each quality range
    	var quality_avg = quality_total / BD_DETECTION_RANGES;

    	var avg_bpm_offset = 0.0;
    	var offset_test_bpm = current_bpm;
    	var draft = new Array(); 

    	// if the current weight of quality exceeds the minimum then run the test
    	if (quality_total >= BD_QUALITY_MINIMUM) for (x=0; x<BD_DETECTION_RANGES; x++)
    	{
    		// if this detection range weight*tolerance is higher than the average weight then add it's moving average contribution 
    		if (detection_quality[x]*BD_QUALITY_TOLERANCE >= quality_avg)
    		{
    			if (ma_bpm_range[x] < bpm_ceil && ma_bpm_range[x] > bpm_floor)
    			{
    				bpm_total += maa_bpm_range[x];
    				draft[(60.0/maa_bpm_range[x])]++;
    				bpm_contributions++;
    				if (offset_test_bpm == 0.0) offset_test_bpm = ma_bpm_range[x];
    				else 
    				{
    					avg_bpm_offset += fabs(offset_test_bpm-ma_bpm_range[x]);
    				}
    			}
    		}
    	}


    	// if we have one or more contributions that pass criteria then attempt to display a guess
    	var has_prediction = (bpm_contributions>=4)?true:false;


    	if (has_prediction) 
    	{
    		std::map<int,float>::iterator draft_i; ??

    		var draft_winner=0;
    		var win_val = 0;

    		for (draft_i = draft.begin(); draft_i != draft.end(); draft_i++)
    		{
    			if (draft_i.second > win_val)
    			{
    				win_val = draft_i.second;
    				draft_winner = draft_i.first;
    			}
    		}

    		bpm_predict = 60.0/draft_winner;

    		avg_bpm_offset /= bpm_contributions;
    		bpm_offset = avg_bpm_offset;

    		if (!current_bpm)  
    		{
    			current_bpm = bpm_predict; 
    		}
    	}

    	if (current_bpm && bpm_predict) current_bpm -= (current_bpm-bpm_predict)*BD_DETECTION_RATE*last_update;	


    	// hold a contest for bpm to find the current mode
    	//std::map<int,float>::iterator contest_i; ??

    	var contest_max=0;

    	for (contest_i = bpm_contest.begin(); contest_i != bpm_contest.end(); contest_i++)
    	{
    		if (contest_max < contest_i.second) contest_max = contest_i.second; 
    	}


    	// normalize to a finish line of 20
    	if (contest_max > 20.0) 
    	{
    		for (contest_i = bpm_contest.begin(); contest_i != bpm_contest.end(); contest_i++)
    		{
    			contest_i.second=(contest_i.second/contest_max)*20.0;
    		}
    	}

    	// decay contest values from last loop
    	for (contest_i = bpm_contest.begin(); contest_i != bpm_contest.end(); contest_i++)
    	{
    		contest_i.second-=contest_i.second*(last_update/BD_DETECTION_RATE);
    	}


    	bpm_timer+=last_update;

    	win_val = 0;

    	// attempt to display the beat at the beat interval ;)
    	if (bpm_timer > winning_bpm/2.0 && current_bpm)
    	{		
    		if (winning_bpm) while (bpm_timer > winning_bpm/2.0) bpm_timer -= winning_bpm/2;

    		// increment beat counter
    		half_counter++;
    		if (half_counter % 2) beat_counter++;

    		// award the winner of this iteration
    		bpm_contest[(int)(60.0/current_bpm)]+=BD_QUALITY_REWARD;

    	  var winner = 0;

    		// find the overall winner so far
    		for (contest_i = bpm_contest.begin(); contest_i != bpm_contest.end(); contest_i++)
    		{
    			if (win_val < contest_i.second)
    			{
    				winner = contest_i.first;
    				win_val = contest_i.second;
    			}
    		}

    		if (winner)
    		{
    			win_bpm_int = winner;
    			winning_bpm = 60.0/ winner;
    		}

    		//		if (winner > 100 && winner < 200)
    		//		{
    		//			BPM_MIN = winner-60; 
    		//			BPM_MAX = winner+60; 
    		//		}
    		//		
    		//		if (BPM_MIN < 80.0) BPM_MIN = 80.0;
    		//		if (BPM_MAX > 220.0) BPM_MAX = 220.0;

    		console.log("quality: " + quality_total + ", current bpm estimate: " + winner + " @ " + win_val + " / " + bpm_offset + "\n");
    	}
    }