Colony

Controls orb1 and orb2. Can be extended for a software PWM that may be used for servos in the future (although maybe

using a different timer might be preferable).

    Rewritten from scratch. Fixes code duplication, long ISRs, bugs, unnecessary synchronized code, memory waste

/**

 * Quick start: call orb_init_pwm or orb_init_binary, depending on which mode you want to use. Call orb*set or

 * orb*set_color to set the orbs.

 * 

 * The orbs have two modes of operation: PWM mode and binary mode. In PWM mode, a pwm signal is generated by a hardware

 * timer and the orbs can be set to a value of 0 through 255. In binary mode, the orbs can only be turned on or off and

 * a value of 0 means "off" and any other value means "on". The mode can be chosen on initialization and can be changed

 * at runtime using the orb_set_mode function.

 *

 * Operation (PWM mode): On timer overflow, all LEDs with a value>0 are turned on and the output compare value for the

 * first LED is loaded. On compare match, the corresponding LED is turned off and the next output compare value is

 * loaded. All masks are precomputed and sorted by time when setting the values.

 *

 * The data structure (pwm_t) containing the PWM times and masks is triple buffered. This is because the buffer the ISR

 * is reading from may only be modified on timer overflow before the next PWM sequence is started, because otherwise the

 * next OCR value might be sed to a value smaller than the current timer value, resulting in the remaining channels not

 * being turned off in that PWM period (flash to on). When using two buffers, the page flip can only occur on a timer

 * overflow for the same reason. So after writing a buffer and marking it for page flip, neither of the buffers could be

 * modified because the front buffer is read by the ISR and the back buffer could be switched at any time. So the

 * calling thread would have to be delayed by up to one full PWM period (8ms in the current implementation, but

 * 20ms-50ms would be a reasonable value to expect here). To avoid this, triple buffering is used.

 *

 * The code for applying the orbs is fairly optimized. See the apply_orbs function for some time measurements and

 * further nodes.

 *

 * The PWM frequency is 120Hz (8ms period time). The next lower frequency (determined by the prescaler) is 30 Hz which

 * is too slow (orbs flicker).

 *

 * The orbs code is thread safe, which means that the functions may be called from another interrupt handler. If there

 * are multiple concurrent calls to the orb*set* functions, one of them is ignored and the orbs are never left in an

 * inconsistent state. For example, if the orbs are set to green by the main thread and to red by an interrupt handler,

 * the resulting color will be either red or green, but never yellow.

 *

 * Some performance measurements:

 *   - Time for setting new orb values (PWM mode): 35us-72us (depending on the degree to which the array is already in

 *     order)

 *   - Time for setting new orb values (binary mode): 5.5us

 *   - Maximum interrupt time (PWM mode only): overflow 2.5us, compare 6*10us (all values different) to 1*26us (all

 *     values identical). (TODO old values)

 *   - Total CPU use for interrupts (PWM mode only): 0.03%+0.75% max (TODO old values)

 *   - Maximum time spent in synchronized code: TODO

 * There are some possible optimizations. See the source code for more information.

 **/

 * Test cases:

 *   - The following code has to work without flickering:

 *     orb_init_pwm(); while(1) { orbs_set(1,1,1,254,254,254); }

 */

/*

 * Possible optimizations:

 *   - Use pointers instead of indicies for current_pwm_channel

 *   - Optimize the output compare interrupt

 *   - Use a different sorting algorithm (see sort_orbs_buffer for further comments on this issue)

 *   - Use pointers in fill_orbs_buffer

 *   - Optimized orb_set (use the knowledge that there are only 3 distinct values)

 *   - Use a lower update frequency. The next higher prescaler value leads to a frequency of 30Hz which is too low (the

 *     orbs are flickering). So the timer would have to be reloaded manually after 127 to generate 60Hz. This would

 *     decrease the resolution from 8 to 7 bit, but 128 steps should still be enough.

    - Make thread safe

	- Check delayed interrupts

	- Timing tests

	  - How long do the interrupt handlers take?

      - How long may interrupts be blocked?

    - Complete Doxygen comments (after merge, no docs in the branch)

      - Introduction included?

// ***************

// ** Debugging **

// ***************

#define LIGHTS_DEBUG

#define LIGHTS_DEBUG_INIT                             DDRF=6;

#define LIGHTS_DEBUG_OVERFLOW_INTERRUPT_START         PORTF|=4;

#define LIGHTS_DEBUG_OVERFLOW_INTERRUPT_END           PORTF&=~4;

#define LIGHTS_DEBUG_OUTPUT_COMPARE_INTERRUPT_START   PORTF|=4;

#define LIGHTS_DEBUG_OUTPUT_COMPARE_INTERRUPT_END     PORTF&=~4;

#define LIGHTS_DEBUG_APPLY_START                      PORTF|=2;

#define LIGHTS_DEBUG_APPLY_END                        PORTF&=~2;

// Some useful bit masks. All of them are are calculated from the I/O definitions above. The calculations should be done

// at compile time (even if they are not, they are only executed once at startup).

    orb1_red_mask | orb1_green_mask | orb1_blue_mask | \

    orb2_red_mask | orb2_green_mask | orb2_blue_mask;

// Mask for the individual LEDs, organized as an array for programmatic access. The layout of this array is

// orb_mask[orb_num, color_num]

const uint8_t orb_mask[NUM_ORBS][NUM_COLORS]={

    { orb1_red_mask, orb1_green_mask, orb1_blue_mask },

    { orb2_red_mask, orb2_green_mask, orb2_blue_mask }

struct pwm_channel_t { // 2 bytes

struct pwm_t { // 13 bytes

    uint8_t init_mask;

    struct pwm_channel_t channel[num_pwm_channels];

// Whether to use PWM (true) or binary (false) orb mode. Not volatile because it's only read once per function.

// The PWM channels and the buffer pointers. This data structure is triple buffered, see above for the reasons. Not

// volatile because they are not modified asynchronously (the read buffer is never written to asynchronously).

// The front buffer the ISR reads from. Other threads may not touch this pointer or the buffer it points to. Not

// volatile because it may only be modified by the ISR.

struct pwm_t *pwm_read_buffer =&pwm_buffer[0];

// The back buffer we can write to. The ISR may not touch this pointer or the buffer it points to. Not volatile because

// it may only be modified by the caller.

struct pwm_t *pwm_write_buffer=&pwm_buffer[1]; 

// The middle buffer to flip the write or read buffer with. Not volatile because it is only read once per function.

struct pwm_t *pwm_free_buffer =&pwm_buffer[2]; 

// Whether to perform a page flip on the beginning of the next PWM cycle. Not volatile because it is only read once

// per function.

// The orb value array. Orb values are written here to be sorted into pwm_channels. Not volatile because all accesses

// are from guarded (thread safe) functions.

// Not volatile because it is only accessed in the interrupt handler.

SIGNAL (SIG_OVERFLOW0) {

#ifdef LIGHTS_DEBUG

    LIGHTS_DEBUG_OVERFLOW_INTERRUPT_START

#endif

    if (pwm_page_flip) {

        // Flip the read buffer with the free buffer. We are in an ISR (and we didn't re-enable interrupts), 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 only the appropriate PWM channels on. Do this directly on the orb port because at this point all orbs should

    // be off anyway.

    ORBPORT|=all_orbs_mask;

    ORBPORT&=pwm_read_buffer->init_mask;

    // Start at the first channel

    current_pwm_channel=0;

    // Load the first OCR

    OCR0=pwm_read_buffer->channel[current_pwm_channel].time;

#ifdef LIGHTS_DEBUG

    LIGHTS_DEBUG_OVERFLOW_INTERRUPT_END

#endif

SIGNAL(SIG_OUTPUT_COMPARE0) {

#ifdef LIGHTS_DEBUG

    LIGHTS_DEBUG_OUTPUT_COMPARE_INTERRUPT_START

#endif

    // If this interrupt is executed without delay, TCNT0==time+1 (where time==OCR0)

    // TODO delayed interrupt

    while (TCNT0==pwm_read_buffer->channel[current_pwm_channel].time+1) {

        // Turn the current channel off

        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_read_buffer->channel[current_pwm_channel].time<255)

                OCR0=pwm_read_buffer->channel[current_pwm_channel].time;

    }

#ifdef LIGHTS_DEBUG

    LIGHTS_DEBUG_OUTPUT_COMPARE_INTERRUPT_END

#endif

static void sort_orbs_buffer (void) {

    // This function applies a bubble sort to sort the elements of the pwm_write_buffer->channel array by the time

    // field.

    // This implementation is heavily optimized. Note that due to the low (and constant) number of elements to be

    // sorted, the runtime complexity (O(n^2) for bubble sort) is not relevant here. In fact, a more advanced algorithm

    // like quick sort or merge sort might even be slower due to higher overhead.

    // That said, it is possible that selection sort (which is also in O(n^2)) would be faster that bubble sort because

    // it only has to do a maximum of (n-1) swapping steps (as opposed to n*(n-1)/2 for bubble sort). However, the check

    // if the elements are already in the correct order would either have to be left out (doing the full search every

    // time, even if the array is already sorted) or done explicitly, so selection sort might actually be slower than

    // bubble sort, especially if the array is already sorted or almost sorted.

    // This implementation uses macros to make the algorithm more clear because the loop is rolled out and the function

    // would become quite long without macros.

    // Macro to swap two values of any type. Requires a variable of the appropriate type called swap_temp.

    #define swap(a,b) { swap_temp=a; a=b; b=swap_temp; }

    // Macro to do one bubble sorting step (compare & swap)

    #define bubble \

        if(a->time > b->time) \

        { \

            swap (a->time, b->time); \

            swap (a->mask, b->mask); \

            done=false; \

        }

    // Macro to move to the next bubble sort pair

    #define next { a++; b++; }

    // Whether no change was made during the last run, which means that all values are already in correct order.

    bool done;

    // A temporary variable for swapping.

    uint8_t swap_temp;

    // Precompute the first PWM channel (tested faster).

    struct pwm_channel_t *first=&(pwm_write_buffer->channel[0]);

    // Pointers to the two PWM channels under inspection

    struct pwm_channel_t *a, *b;

    // The actual sorting

    a=first; b=a+1; done=true;

    bubble next bubble next bubble next bubble next bubble

    if (done) return;

    a=first; b=a+1; done=true;

    bubble next bubble next bubble next bubble

    if (done) return;

    a=first; b=a+1; done=true;

    bubble next bubble next bubble

    if (done) return;

    a=first; b=a+1; done=true;

    bubble next bubble

    if (done) return;

    a=first; b=a+1; done=true;

    bubble

    if (done) return;

    // Undefine the macros so they do not disturb some other function.

    #undef next

    #undef bubble

    #undef swap

static void fill_orbs_buffer (void) {

    // We do not use a loop here because it introduces 27us overhead, which is quite much, given the total time for

    // optimized copying and sorting of 34us (elements already in correct order) to 71 us (elements in reverse order).

    #define copy_value(orb, color) \

        index=NUM_COLORS*orb+color; \

        time=orb_values[orb][color]; \

        mask=orb_mask[orb][color]; \

        \

        pwm_write_buffer->channel[index].time=time-1; \

        pwm_write_buffer->channel[index].mask=mask; \

        \

        if (time!=0) \

            pwm_write_buffer->init_mask &= ~mask; \

    uint8_t index, time, mask;

    copy_value(0,0); copy_value(0,1); copy_value(0,2);

    copy_value(1,0); copy_value(1,1); copy_value(1,2);

    #undef copy_value

static void apply_orbs (void) {

	/*

	 * Some timing tests: Time for apply_orbs with interrupts disabled, in us:

     *             Values in:     Correct order      Reverse order

     * Naive bubble sort:         148                217

     * Aborting bubble sort:       71                232

     * Only count to top:          73                189

     *

     * Loops rolled out:           61                120

     * Using pointers:             62                 98

     * Copy loop also rolled out:  35                 72

	 *

	 * Note that rolling out both loops and using pointers saves 52%/62% of time! 27us were spent on loop overhead,

	 * which is quite much, considering an optimized total time for copying and sorting or 35us.

	 */

#ifdef LIGHTS_DEBUG

    LIGHTS_DEBUG_APPLY_START

#endif

    if (enable_orb_pwm) {

        // PWM mode

        pwm_write_buffer->init_mask=~0;

        // 1. Write the orb values and corresponding masks to the pwm channels

        // array unsorted.

        fill_orbs_buffer ();

        // 2. sort the buffer.

        sort_orbs_buffer ();

        // 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;

        }

        // On the next overflow, flip the read buffer with the free buffer.

        pwm_page_flip=true;

    }

    else {

        // Binary mode.

        // The outputs are inverted.

        uint8_t on=0;

        if (orb_values[0][0]) on |= orb_mask[0][0];

        if (orb_values[0][1]) on |= orb_mask[0][1];

        if (orb_values[0][2]) on |= orb_mask[0][2];

        if (orb_values[1][0]) on |= orb_mask[1][0];

        if (orb_values[1][1]) on |= orb_mask[1][1];

        if (orb_values[1][2]) on |= orb_mask[1][2];

        // Write the new orb states to the output port. Synchronized because it is a RMW operation.

        SYNC {

            uint8_t value=ORBPORT;

            value |= all_orbs_mask; // All orbs off

            value &= ~on; // Selected orbs on

            ORBPORT=value;

        }

    }

#ifdef LIGHTS_DEBUG

    LIGHTS_DEBUG_APPLY_END

#endif

static void set_orb_values (uint8_t num, uint8_t red, uint8_t green, uint8_t blue) {

    // Write the values to the array, but do not sort them yet, as we might want to write the other orb values first so

    // we don't have to sort twice.

    // Any function calling this function will probably want to call apply_orbs() afterwards.

    orb_values[num][0]=red;

    orb_values[num][1]=green;

    orb_values[num][2]=blue;

 * Sets the specified orb to the specified color. The orbs must be initialized before this function may be used.

 * Note that, when setting both orbs, using orbs_set is faster then setting the orbs individually because the values are

 * only sorted once.

 *

 * @param red the red value for the specified orb

 * @param green the green value for the specified orb

 * @param blue the blue value for the specified orb

 * @see 

void orb_n_set (uint8_t num, uint8_t red, uint8_t green, uint8_t blue) {

    set_orb_values (num, red, green, blue);

    apply_orbs ();

 * Set orb1 to the color specified. The orbs must be initialized before this function may be used. Note that, when

 * setting both orbs, using orbs_set is faster then setting the orbs individually because the values are only sorted

 * once.

void orb1_set (uint8_t red, uint8_t green, uint8_t blue) {

    set_orb_values (0, red, green, blue);

    apply_orbs ();

 * Set orb2 to the color specified. The orbs must be initialized before this function may be used. Note that, when

 * setting both orbs, using orbs_set is faster then setting the orbs individually because the values are only sorted

 * once.

void orb2_set (uint8_t red, uint8_t green, uint8_t blue) {

    set_orb_values (1, red, green, blue);

    apply_orbs ();

 * Set both orbs to the color specified. The orbs must be initialized before this function may be used.

void orb_set (uint8_t red, uint8_t green, uint8_t blue) {

    set_orb_values (0, red, green, blue);

    set_orb_values (1, red, green, blue);

    apply_orbs ();

/**

 * Set the orbs to the respective values. The orbs must be initialized before this function may be used. Note that, when

 * setting both orbs, this function is faster than calling orb1_set and orb2_set (or orb_n_set) because the values are

 * only sorted once.

 *

 * @param red1

 * @param green1

 * @param blue1

 * @param red2

 * @param green2

 * @param blue2

 * @see orb1_set

 * @see orb2_set

 * @see orb_n_set

 **/

    uint8_t red1, uint8_t green1, uint8_t blue1,

    uint8_t red2, uint8_t green2, uint8_t blue2) {

    set_orb_values (0, red1, green1, blue1);

    set_orb_values (1, red2, green2, blue2);

    apply_orbs ();

 * Set the specified orb to the specified color. This function is intended to be used with the predefined colors.

 * @param num the number of the orb to set (0 or 1)

void orb_n_set_color(uint8_t num, uint8_t col) {

    orb_n_set(num, C_RED(col), C_GREEN(col), C_BLUE(col));

void orb1_set_color(uint8_t col) {

    orb1_set (C_RED(col), C_GREEN(col), C_BLUE(col));

void orb2_set_color(uint8_t col) {

    orb2_set(C_RED(col), C_GREEN(col), C_BLUE(col));

 * Set both orbs to the specified color. This function is intended to be used with the predefined colors.

void orb_set_color(uint8_t col) {

    orb_set (C_RED(col), C_GREEN(col), C_BLUE(col));

 * Set the orbs to the respective color. This function is intended to be used with the predefined colors.

void orbs_set_color(uint8_t col1, uint8_t col2) {

    orbs_set (C_RED(col1), C_GREEN(col1), C_BLUE(col1), C_RED(col2), C_GREEN(col2), C_BLUE(col2));

/**

 * Enables the orb timer. Note that you usually don't want to use this function directly. Instead, use orb_set_mode.

 * @see orb_set_mode

 **/

void orb_enable_timer (void) {

    // Use 8 bit TC0.

    //

    // Timer mode: We cannot use CTC mode because it can only clear on OCR0 (in contrast to the 16 bit timers which can

    // also use the ICR for that) and OCR0 is already used for generating output compare interrupts. We also need

    // immediate (non double buffered) update of OCR0, so the only mode left is "Normal".

    //

    // Note that for a timer counting from 0 to 255, there are 256 states and thus 257 output possibilities

    // (0/256...256/256)! However, there are only 256 values in the byte used to specify the PWM value. Possible ways

    // to deal with that:

    //   1. use a 16 bit variable for the PWM value (memory waste, overhead)

    //   2. use an additional flag for the 257th value (inconvenient)

    //   3. use 1/256...256/256 (skip 0, never complete off)

    //   4. use 0/256...256/256 (skip 256, never complete on)

    //   5. skip a value somewhere in the middle

    //   6. reload the timer after 254

    // For this implementation, variant 4 was chosen.

    //

    // Using an 8 bit timer has the added advantage that all the comparisons are faster.

    // Normal mode, Compare match output off, Prescaler

    TCCR0=_BV(CS02) | _BV(CS01); // 1024, 30 Hz

    // Enable the interrupts

    TIMSK|= _BV(OCIE0) | _BV(TOIE0);

/**

 * Disables the orb timer. Note that you usually don't want to use this function directly. Instead, use orb_set_mode.

 * @see orb_set_mode

 **/

void orb_disable_timer (void) {

    // Disable the interrupts

    TIMSK&=~( _BV(OCIE0) | _BV(TOIE0));

void orb_set_mode (orb_mode_t mode) {

    // Set enable_orb_pwm to the appropriate value and disable or enable the timer.

    if (mode==orb_mode_binary) {

        orb_disable_timer ();

        enable_orb_pwm=false;

        apply_orbs ();

    }

    else { // orb_mode_pwm

        enable_orb_pwm=true;

        apply_orbs ();

        orb_enable_timer ();

    }

static void orb_init_common (void) {

    // Enable the output ports and turn off the LEDs

    ORBPORT |=  all_orbs_mask;

    ORBDDR  |=  all_orbs_mask;

    // Set all orbs to "off"

    orb_set (0, 0, 0);

#ifdef LIGHTS_DEBUG

    LIGHTS_DEBUG_INIT

#endif

void orb_init_binary (void) {

    orb_init_common ();

    orb_set_mode (orb_mode_binary);

void orb_init_pwm (void) {

    orb_init_common ();

    orb_set_mode (orb_mode_pwm);

 * Initializes the orbs in default mode. One of the orb_init* functions must be called before the orbs can be used. Use

 * the orb_init_binary or orb_init_pwm function if you want one specific mode.

 * @see orb_init_binary

void orb_init () {

    orb_init_pwm ();