/branches/library_refactor/projects/libdragonfly/lights.c - Diff - Colony - Robotics Club

Revision 1107

Added by Martin Herrmann about 15 years ago

Implemented triple buffering
Optimized sorting

     /*
       TODO:
     	- test the timing
     	- Determine sorting time, possibly improve sorting algorithm (111 us sorted,
 us reverse sorted)
     	- stop sorting when finished (no change made) (and measure performance gain)
     	- Find out the interrupt time
     	- Optimize the OC interrupt
         - enable_orb_pwm use everywhere, add methods to switch on/off, add init
     	  function
     	- test old code: continuously setting the orbs
     	- n-buffering
     	- fix sync/volatile
      */
-...
         uint8_t mask;
     };
     sutrct pwm_t
     struct pwm_t
+    {
     	uint8_t init_mask;
     	pwm_channels_t channel[num_pwm_channels];
+    }
     	struct pwm_channel_t channel[num_pwm_channels];
     };
     // ***************
-...
     struct pwm_t pwm_buffer[3];
     // TODO using pointers might be faster (or might be slower because pointers are
     // 16 bit long).
     uint8_t read_buffer=0; // The buffer the ISR reads from
     uint8_t next_buffer=0; // The buffer the ISR will switch to on the next overflow
     uint8_t
     uint8_t inactive_buffer=2;
     struct pwm_t *pwm_read_buffer =&pwm_buffer[0]; // The front buffer the ISR reads from. Other thread may not touch this pointer or the buffer it points to.
     struct pwm_t *pwm_write_buffer=&pwm_buffer[1]; // The back buffer we can write to. The ISR may not touch this pointer or the buffer it points to.
     struct pwm_t *pwm_free_buffer =&pwm_buffer[2]; // The back buffer to flip with.
     bool pwm_page_flip=false; // Whether to do a page flip on the next overflow
     // The orb value array. Orb values are written here to be sorted into
     // pwm_channels.
     uint8_t orb_values[NUM_ORBS][NUM_COLORS];
-...
     SIGNAL (SIG_OVERFLOW0)
+    {
     PORTF|=4;
     	if (pwm_page_flip)
+    	{
     		// Flip the read buffer with the free buffer
     		// We are in an ISR, so we don't have to synchronize explicitly.
     		struct pwm_t *temp = pwm_read_buffer;
     		pwm_read_buffer    = pwm_free_buffer;
     		pwm_free_buffer    = temp;
     		pwm_page_flip=false;
+    	}
     	// Turn all appropriate PWM channels on
     	ORBPORT&=pwm_init_mask;
     	ORBPORT&=pwm_read_buffer->init_mask;
     	// Start at the first channel
     	// Start at the first channel (TODO faster w/ pointers?)
     	current_pwm_channel=0;
     	// Load the first OCR
     	OCR0=pwm_channels[current_pwm_channel].time;
     	OCR0=pwm_read_buffer->channel[current_pwm_channel].time;
     PORTF&=~4;
+    }
-...
     	// TODO improve (check overflow; maybe use return after last, maybe use
     	// pointers instead of indicies)
     	while (TCNT0==pwm_channels[current_pwm_channel].time+1)
     	while (TCNT0==pwm_read_buffer->channel[current_pwm_channel].time+1)
+    	{
     		// Turn the current channel off
     		ORBPORT|=pwm_channels[current_pwm_channel].mask;
     		ORBPORT|=pwm_read_buffer->channel[current_pwm_channel].mask;
     		// Increment the channel
     		current_pwm_channel++;
     		// If there is a next channel, load its OCR value
     		if (current_pwm_channel<=(num_pwm_channels-1))
     			if (pwm_channels[current_pwm_channel].time<255)
     				OCR0=pwm_channels[current_pwm_channel].time;
     			if (pwm_read_buffer->channel[current_pwm_channel].time<255)
     				OCR0=pwm_read_buffer->channel[current_pwm_channel].time;
+    	}
     PORTF&=~4;
+    }
-...
     		// Sort the orb values.
     PORTF|=2;
     SYNC
+    {
     		pwm_init_mask=~0;
     		pwm_write_buffer->init_mask=~0;
     		// 1. Write the orb values and corresponding masks to the pwm channels
     		// array unsorted
     		for (uint8_t orb=0; orb<2; ++orb)
+    		{
     			for (uint8_t color=0; color<3; ++color)
-...
     				uint8_t time=orb_values[orb][color];
     				uint8_t mask=orb_mask[orb][color];
     				pwm_channels[index].time=time-1;
     				pwm_channels[index].mask=mask;
     				pwm_write_buffer->channel[index].time=time-1;
     				pwm_write_buffer->channel[index].mask=mask;
     				if (time!=0)
     					pwm_init_mask &= ~mask;
     					pwm_write_buffer->init_mask &= ~mask;
+    			}
+    		}
     		// 2. Sort the values. Use bubble sort for now.
     		for (uint8_t count=num_pwm_channels-1; count>0; --count)
     		// 2. Sort the values. Use bubble sort.
     		// Considering the low number of data points, more
     		// sophisticated algorithms are unlikely to be faster.
     		bool done;
     		// For 6 channels, we count i=0..4 and compare i with i+1
     		uint8_t top=num_pwm_channels-1;
     		do
+    		{
     			for (uint8_t i=num_pwm_channels-1; i>0; --i)
     			done=true; // We are done unless we do some swapping
     			for (uint8_t i=0; i<top; ++i)
+    			{
     				if (pwm_channels[i].time<pwm_channels[i-1].time)
     				#define channel_a pwm_write_buffer->channel[i]
     				#define channel_b pwm_write_buffer->channel[i+1]
     				if (channel_a.time>channel_b.time)
+    				{
     					uint8_t temp;
     					// Swap the times
     					temp=pwm_channels[i].time;
     					pwm_channels[i].time=pwm_channels[i-1].time;
     					pwm_channels[i-1].time=temp;
     					temp           = channel_a.time;
     					channel_a.time = channel_b.time;
     					channel_b.time = temp;
     					// Swap the masks
     					temp=pwm_channels[i].mask;
     					pwm_channels[i].mask=pwm_channels[i-1].mask;
     					pwm_channels[i-1].mask=temp;
     					temp           = channel_a.mask;
     					channel_a.mask = channel_b.mask;
     					channel_b.mask = temp;
     					done=false; // No, we're not done yet.
+    				}
     				#undef channel_a
     				#undef channel_b
+    			}
     			// On the next iteration, we need one less comparison
     			top--;
     		} while (!done);
     		// Flip the write buffer with the free buffer
     		SYNC
+    		{
     			struct pwm_t *temp = pwm_write_buffer;
     			pwm_write_buffer   = pwm_free_buffer;
     			pwm_free_buffer    = temp;
+    		}
+    }
     //SYNC_END;
     		// On the next overflow, do the page flip.
     		pwm_page_flip=true;
     PORTF&=~2;
+    	}
     	else
+    	{
-...
     	//orbs_set (255, 127, 0, 0, 127, 255); // Pretty colors with extreme values
     	//orbs_set (0, 1, 2, 253, 254, 255); // Timing tests
     	orbs_set (255, 255, 255, 0, 0, 0);
     	delay_ms (1000);
     //	orbs_set (255, 255, 255, 0, 0, 0);
     //	delay_ms (1000);
     	while (1)
+    	{
     		//orbs_set (250, 127, 3, 3, 127, 250); // Pretty colors
     	orbs_set (255, 255, 255, 1, 1, 1);
     		_delay_us(400);
+    	}
     	// Test the time of the sorting routine
     	//while (1)
     	//{
     	//	orbs_set (10, 20, 30, 40, 50, 60);	// Correct order
     	//	//orbs_set (60, 50, 40, 30, 20, 10); // Reverse order
     	//	delay_ms (10);
     	//	orbs_set (250, 127, 3, 3, 127, 250); // Pretty colors
     	//	//orbs_set (255, 255, 255, 1, 1, 1);
     	//	//_delay_us(400);
     	//}
     	// Test the time of the sorting routine
     //	while (1)
     //	{
     //		orbs_set (10, 20, 30, 40, 50, 60);	// Correct order
     //		//orbs_set (60, 50, 40, 30, 20, 10); // Reverse order
     //		delay_ms (10);
     //	}
+    }
     // Pure sorting time/us (interrupts disabled!) (difference to naive bs):
     //                        Correct order    Reverse order
     // Naive bubble sort:     147              216
     // Aborting bubble sort:   70 (-52%)       231 (+7%)
     // Aborting w/ top:        72 (-51%)       188 (-13%)

Also available in: Unified diff

Project

General

Profile

Colony

Revision 1107