How do you sort a list of unsigned integers that rollover?

tonyp12

I have this 24bit unsigned Counter (RTC) with a 24bit CompareRegister, they both use uint32_t (upper 8bit is unused)

After a IRQ hits, I want to find the next closest value from 32 possible values.

As example with keep it as it 4bit 0-15 with four in a list:
___________________________________________________________________________________________
Say IRQ hit at 5, it now need to find the nearest
values in list is 5, 0, 8,14
It will signal the task that asked for the 5 match and then it needs to find 8 in list to prepare next IRQ
___________________________________________________________________________________________
IRQ now hit at 8, it now need to find the nearest
values in list is now 10, 0, 8,14 (the first thread added 5 to its match)
So it needs to find 10.
___________________________________________________________________________________________
IRQ now hit at 10, it now need to find the nearest
values in list is now 10, 0, 0,14 (the third thread added 8 to its match)
So it needs to find 14.
___________________________________________________________________________________________
IRQ now hit at 14, it now need to find the nearest
values in list is now 3, 0, 0,14 (the first thread added 8 to its match)
So it needs to find both zeros, two of the same values should ORa the eventflags.

If a thread ask for lower value than next prepared IRQ, it will just over write CompareRegister and change eventflag.
If value is same it will just ORa itself to pending eventflags.
I use C, but SPIN example should be easy to translate.


Maybe two pass?, but I want it to be fast though.
First pass if no values above current counter, then do a seconds pass treating values low-to-high just like normal sorting.

tonyp12

As there is also RollerOverIRQ, I think I will just re-sort the list when that happens.
I divide the freq to get 0.97ms rtc steps, so rollover only happens every 4hrs.

Publison

Tony,

Is this P1 or P2?

tonyp12

No, just general MCU.
Math is math on any platform.

I endup looking for lowest & still higher than last (e.g current) counter value. (not final, hardcoded unrolled loop for testing)

if (mytask1.outbox > rtcmatch){
	  if (mytask1.outbox == lowest) rtcevent |= 1;
	  else if (mytask1.outbox < lowest) { rtcevent = 1; lowest = mytask1.outbox; }
}

I do this again when counter is at zero, when rollover values will fall in place.

Heater.

Indeed: "Math is math on any platform."

This is a trick question right?

It's not possible to sort things unless there is a concept of order: "greater than", "equal to", "less than".

If N + 1 turns out to be less than N, due to rollover, overflow, whatever, then you have a problem.

What actually are you wanting to do?

tonyp12

I though maybe some trick to it, like type casting them as signed int's etc.

I'm creating a mailbox cooperative-multitasking OS.
When a tasks-statemachine is done, it sets its outbox with a time it want to be invoked again.
Turning off HighFreq Osc as often as possible, even for short sleeps like 2ms, saving battery.

There is no greatest common denominator, any task can sleep any length (in my case 1ms to 4hours)

evanh

Tony,
The method I've historically used is to make everything relative. It takes some more adds and subtracts but you get way less conditional execution.

To do this there is always a local reference position upon which the calculation is based. The calculation is done with the reference treated as zero and only at the end is it added on to provide the absolute position.

For a straight threshold compare like, you only need subtract the reference before doing the compare. In C that becomes:

if( reading - threshold > 0 ) {
//  An increasing position has crossed the threshold
}

In this case the threshold is your reference.

evanh

You can cheat a little bit in one case. If there is a known small constant offset on that threshold then that offset can replace the zero on the right side of the compare.

NOTE: Be careful not to let absolutes creep into the comparison stage.

tonyp12

Re-roll the values so they start from current counter, should work as underflow will roll in to a higher value.

uint32_t lowest = 0xffffff;  // 24bit max

if (mytask1.outbox-rtmatch == lowest) rtcevent |= 1;
else if (mytask1.outbox-rtmatch < lowest) { rtcevent = 1; lowest = mytask1.outbox-rtmatch; }
...
rtcmatch += lowest; CompRegSet(rtcmatch);

I guess have to look how many cycles the assembly code ending up taking for either type.

The three mytask1.outbox-rtmatch should be stored in a register for quick access,
as ARM is load-and-store so better hope the compiler sees that, in high optimization mode at least.
Could always: uint32_t myvalue =mytask1.outbox-rtmatch; as local var is always trying to use a register first.

evanh

As for the hardware producing a 24 bit position reading. Best to convert that to the CPU's native word size of 32 bits. This way the natural 2's complement roll-over of the CPU will work in your favour ...

PS: Ditch all the unsigned variables. With all the calculations centred around zero you'll be getting negative results as much as positives.

evanh

One way to do the word size conversion that's easy on the CPU is to truncate the sampling down to 16 bit size (removing the higher significant bits). Then do the deltas from that. C will automatically handle the size promotion, handling sign-extention, into the 32-bit position accumulation.

int16_t  latest_sample;
int16_t  previous_sample;
int32_t  position;


position += latest_sample - previous_sample;

That example doesn't show the sample being truncated because once its a 16-bit integer then that part is done. The truncation depends on how the hardware is being read, and what datatypes are involved.

pjv

Tony,

I have solved this problem for my Propeller multi-tasking co-operative scheduler in the following manner, and is Propeller specific. Not sure if it could be effectively modified for other architectures.

I keep an arbitrarily long sorted list of delta time that each task wants to run, relative to the next task. These times can be 0 to 31 bit ticks long, so the longest delay may not exceed 26 seconds at 80 MHz.

A WAITCNT is executed until the-next-to-run thread's time match occurs, and that thread then continues from where it left off last time it ran. On completing its short task (NO loops or WAITs permitted) it calculates the delta match value for its next run time. It then sorts though the list sequentially until it finds a delta time that is larger than itself, or the end of the list, each time reducing its own delta time by the value of each entry it compares to and skips. The scheduler then inserts its remaining delta value at that point in the list. This keeps the list sorted. Then the scheduler takes the bottom entry (lowest delta value) off the list and adds that to the WAITCNT match register, thereby setting the time for the next to run.

By using delta times of 31 bits or less, there are no overflows, so comparisons become easy. I tried so many other ways of doing this, all to no avail, and have had perfect luck with this simple approach.

Any (practical) number of threads, each with 0 to 2^31 ticks, hence a resolution of 12.5 nS. In the case of a zero delta, when two threads calculate to run at the same time, the thread is already "behind", and runs immediately.

Just for fun, I've had 256 LED flash threads running in a single Cog.

Cheers,

Peter (pjv)

tonyp12

As every time a task sets/update a new time, it need to see if lower than current pending, so it can overwrite CompareRegister.
The problem is of course if that value rolled over.

4bit example:
current time is 14, and it wants to comeback at 15, another task have already set CompareRegister to 1,
15 is not lower than 1, but is sooner than 1.

Having a flag set that detected if sort routine set Comparegister to a values that rolled over?
Or
As rtc is 24bit only, I could keep values flowing over in to 25bit and then the rollover IRQ hits it could then ANDing all values with a 24bit mask.
But if a MCU series comes with a 32bit timer I could only use 31bit.

msrobots

right, that is what @pjv did, just allowing 31 bit on a 32 bit counter for the longest wait.

Mike

tonyp12

Pretty much finished it, just need to double check some exclusivity rules, like what happen if overflow iRQ just truncates rtcmatch while a task was calling OS_sleep().
id1: 1ms to 4.5hrs
id2: date in seconds since 2000, that the overflow-irq check if within the next 4.5hrs and change it to id1.
So total range is 1ms to year2138.

/**************************************************************************
 * @brief 	       RTC Interrupt Handler				 *
 **************************************************************************/
void RTC_IRQHandler(void) 
{
  if (RTC_IntGetEnabled() & RTC_IF_OF) {                                                // is it overflow IRQ?
    secondsY2K += 16384;                                                                // add to seconds since2000 counter
    rtcmatch &= 0xffffff;                                                               // truncate it to 24bits
    for (int i = 0; i < TaskListEnd; i++) {
      if (task[i].outboxid == 1)
        task[i].outbox &= 0xffffff;				  		        // truncate them to 24bits
      else if (task[i].outboxid == 2 && task[i].outbox - secondsY2K < 16384)
        OS_sleep(i, (task[i].outbox - secondsY2K) << 10);	                        // 11th bit is second counter
    }
  RTC_IntClear(RTC_IFC_OF);								// Clear interrupt source
  }

  if (RTC_IntGetEnabled() & RTC_IF_COMP0) {						// is it compare0 IRQ
    uint32_t temp = eventrtc.all;						        // volatile rule needs temp register
    eventset.all |= temp;	                                                        // merge pending events to events
    eventrtc.all = 0;									// clear it
    uint32_t lowest = 0x1ffffff;					                // as we keep rtcmach up to 25bit math
    for (int i = 0; i < TaskListEnd; i++) {
      if (task[i].outboxid == 1 && task[i].outbox > rtcmatch) {
        if (task[i].outbox < lowest) {
          eventrtc.all = (1 << i);
          lowest = task[i].outbox;
        } else if (task[i].outbox == lowest)
          eventrtc.all |= (1 << i);
      }
    }
    RTC_IntClear(RTC_IFC_COMP0);						          // Clear interrupt source
    if (eventrtc.all) {									  // was there any new request
      rtcmatch = lowest;						                  // this is the next pending
      lowest &= 0xffffff;								  // now just keep the 24bit part
      if (RTC_CounterGet() == lowest)
        RTC_IntSet(RTC_IFS_COMP0);							  // already that time?
      else
        RTC_CompareSet(0, lowest);
    }
  }
}
/**************************Function***********************************/
void OS_sleep(uint32_t taskn, uint32_t secdivbyK) 
{
  if (task[taskn].outboxid != 1) {							  // set up from scratch
    task[taskn].outbox = RTC_CounterGet();
    task[taskn].outboxid = 1;
  }
  task[taskn].outbox += secdivbyK;						          // else treat it as interval
  if (task[taskn].outbox < rtcmatch || !eventrtc.all) { 	                          // we are lowest or non pending
    rtcmatch = task[taskn].outbox;							  // overwrite current
    eventrtc.all = (1 << taskn);			 				  // set us a next event
    RTC_CompareSet(0, task[taskn].outbox & 0xffffff);	                                  // prepare next irq masked to 24bits
  } else if (task[taskn].outbox == rtcmatch)
    eventrtc.all |= (1 << taskn);
}

example of usage:

#include "em_gpio.h"
#include "common.h"
#define this blinkled1

void blinkled1F(void)
{
  GPIO_PinOutToggle(gpioPortC,10);
  OS_sleep(this,500);
}