Time

This post is a description of a possible addition to the Tiny Core for managing time: the ticks function.

There are currently four time-related functions: millis, micros, delay, and delayMicroseconds.  Because timer 0 is typically used for the time functions, for this and future posts, “timer 0″ is always used to reference the timer used for the time functions.

Like millis and micros, the ticks function returns an unsigned long.  Unlike the existing functions, the value returned by ticks is unit-less.  Utility functions can be used to convert a ticks-value to various units: ticks2us (convert ticks to microseconds), ticks2ms (to milliseconds), and ticks2s (to seconds).  Other utility functions can be used to convert from various units to a ticks-value: us2ticks, ms2ticks, s2ticks.

The current time-related functions are carefully crafted to eliminate all mathematical error.  Unfortunately, that is not possible with ticks.  At some processor speeds converting a ticks-value introduces an error.  Except in extreme circumstances (like trying to convert a very small ticks-value to a small number of microseconds) the error is much smaller than the error from the internal oscillator or an external resonator.  Typically, only if the application needs the accuracy of a crystal will the ticks-value conversion be a concern.

The ticks function is smaller and uses less SRAM than the current time functions.  Theoretically, the interrupt service routine will be fast enough that timer 0 can be configured for very high frequency PWM.  If only tick-values are used at run-time, the overall program size will be a bit smaller and a bit faster.  For the kinds of ATtiny applications that are typically develop, ticks is a very welcome addition.

Random: Overview

Overview

From this overview it is clear there are better choices for the random function in Tiny Core.  Even the Xorshift-16 generator is a good choice for some applications (like a Blinky).

Algorithm Code Data Speed Quality Notes
Park-Miller 498  4 1.947 – 6
Xorshift 126  4 0.323 – 4 primary choice, normal quality
JKISS32 356 20 0.433 +1 high quality
CRC32 104  4 0.610 – 1 secondary choice, better quality
Xorshift-16  34  2 0.044 low use for ’13, maybe ‘2n

The Plan

The current plan is to use Xorshift as the default generator.  Of the generators evaluated, it isn’t the smallest nor the fastest nor the best quality.  It is small, fast, andgood quality so it is a very nice compromise.

The CRC32 generator will be an available option as a better quality smaller generator.

The JKISS32 generator will be an available option as a very high quality generator on all but the processors with the least memory (probably only excluding the ATtiny13).

The Xorshift-16 generator will be the default for the ATtiny13 processor and possibly the ATtiny25 and ATtiny24 processors.

Random: Xorshift-16

The last generator tested is a 16 bit Xorshift.  With such a short cycle length (64K) a 16 bit generator is not expected to perform well on any meaningful statistical tests like dieharder and this generator does not disappoint.  It consistently fails every dieharder test!

However, it does perform well on the ent tests.  Obviously, it is extremely fast and very small making it a good candidate for the Tiny Core.

Size

Xorshift-16 adds 34 bytes to the image which is significantly less than all the other generators.

Speed

On a 1 MHz ATtiny85 processor Xorshift-16 takes 0.044 milliseconds (44 microseconds) to generate the next value which is more the 44 times (!) faster than the Libc random function and significantly faster than all the other generators.

Quality

Xorshift-16 consistently fails all the dieharder tests.  It performs well on the ent tests.

Seeds

Valid seeds are in the range 1 to 216-1 (0xFFFF).  Zero is the only bad seed and is fatal.

References

Status

Matches Delphi.

Random: CRC32

The 32 bit CRC polynomial 0xEDB88320 is a good quality very small random number generator.  Unfortunately, the simple loop version is also very slow.

Size

CRC32 adds a very modest 104 bytes to the image which is significantly less than the 454 bytes added by the Libc random function.

Speed

On a 1 MHz ATtiny85 processor CRC32 takes 0.610 milliseconds to generate the next value which is significantly faster than the 1.947 milliseconds taken by the Libc random function.

Quality

On the dieharder tests, CRC32 always fails one test: diehard_rank_32x32.

References

Status

Matches Delphi.

Random: JKISS32

May 2010 David Jones published Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications.  Even though the article has “for Bioinformatics Applications” in the title the material applies to most applications that make use of pseudo-random number generators.  The article includes a generator (JKISS32) that may be of interest to Tiny Core users.  The generator uses considerably more SRAM than the other generators (20 bytes versus 4 bytes) but it is smaller, faster, and much higher quality than the Libc random function.

Size

JKISS32 adds 356 bytes to the image which is less than the 454 bytes added by the Libc random function.

Speed

On a 1 MHz ATtiny85 processor JKISS32 takes 0.433 milliseconds to generate the next value which is significantly faster than the 1.947 milliseconds taken by the Libc random function.

Quality

Outstanding.  Refer to the article for details.

References

Random: Xorshift

July 2003 George Marsaglia introduced the world to xorshift random number generators.  His claim that they “pass tests of randomness very well” is arguable.  His claim that they are “simple, extremely fast random number generators” is not.  They are definitely simple and extremely fast.  They also produce small code.  A perfect candidate for the Tiny Core!

All combinations of 32-bit triples and xorshift formulas were tested using dieharder.  Marsaglia’s “favorite” seems to perform better than the others.  However, it also produces slightly larger and slightly slower code.

Size

Marsaglia’s favorite adds 126 bytes to the image which is significantly less than the 454 bytes added by the Libc random function.

Speed

On a 1 MHz ATtiny85 processor Marsaglia’s favorite takes 0.323 milliseconds to generate the next value which is significantly faster than the 1.947 milliseconds taken by the Libc random function.

Quality

On the dieharder tests, Marsaglia’s favorite (and the other xorshift generators) always fails four tests including: diehard_rank_32x32, diehard_count_1s_str, rgb_bitdist, dab_monobit2.

Seeds

Valid seeds are in the range 1 to 232-1 (0xFFFFFFFF).  Zero is the only bad seed and is fatal.

References

Random: Park-Miller ala Arduino

With the macro-functions coded and tested I’ve decided to spend some time on the random functions.  Hard to believe the Park-Miller minimal standard is still in use almost 25 years after its introduction.  Well, it’s life with the Tiny Core is about to end.  It’s big, slow, and the quality can best be described as “OK”.  There are much smaller, much faster, slightly better quality choices available.  But first let’s take a closer look at the Park-Miller minimal standard generator ala Arduino.

Size

Arduino’s random function adds as much as 498 bytes to the image.  For a processor like the ATmega328, the baggage is essentially insignificant at 1.5% of the available Flash.  However, for an ATiny85 processor random consumes 6.1% of the available Flash; not devastating but a bit painful.  For the ATtiny13 random uses half of the available Flash.  Ouch!

Speed

On a 16 MHz Uno, the Libc random function takes 94.481 microseconds to generate the next value.  Fairly fast but the Tiny Core supports processors running at 1 MHz.  The Libc random function takes 1.947 milliseconds on a 1 MHz ATtiny85 processor.  On the same processor, the Arduino random function takes as much as 2.717 milliseconds to generate the next value.  That’s too long.

Quality

On the dieharder tests, Park-Miller always fails six or more tests including: diehard_dna, marsaglia_tsang_gcd, and rgb_minimum_distance.

Seeds

Valid seeds are in the range 1 to 2147483646.  Zero is fatal.

References

 

Macros are evil

After months of on-again off-again research I’ve reached the point where I can start coding in earnest.  The first problem to tackle are the macro-functions (min, abs, round).  They have undesirable side-effects; some details are available here.. http://arduino.cc/forum/index.php/topic,84364.0.html

The goal with Tiny Core Version 2 is “always choose tiny”.  When more than one implementation is available, choose the one that produces less code.

With abs the built-in functions produce less code so inline functions and overloading are the better choice.

round is the name of a Libc function.  Because of the name conflict, the old macro has caused problems… http://code.google.com/p/arduino-tiny/issues/detail?id=29  I have not been able to create a clean solution so round has been removed.

bperrybap provided the best solution for the remaining macro-functions… http://arduino.cc/forum/index.php/topic,84364.msg640438.html#msg640438