I came across this algorithm by chance - it allows arbitrary bit length integers to be converted to a string (or BCD - binary coded decimal) - and as I had an hour to while away.
So Some Fun for Fans of Flowcode. Lovers of alliteration will have to look elsewhere.
You can find details of the algorithm at https://en.wikipedia.org/wiki/Double_dabble - I've implemented it twice here - once that takes an array of bytes as a (possibly very) large integer (if you're working with public keys?) - and once where it takes a long (32bit) unsigned integer.
I was impressed that it converts an binary value to a decimal string without a single division (except one - that calculates an approximate number of characters in the resultant string) 'Main' here just runs lots of conversions for timing. ToString$ is quicker for small integers but slower as the numbers get bigger (on AVR at least) - but if you want to work with larger integers (and who doesn't?) - then this would be good. Other MCUs mileage may vary depending on the efficiency of the divide instruction.
So - first a challenge - anyone like to create a string to binary conversion (that works for any length string?)
I've also left leading zeroes on the resultant string - an easy fix?
Second a gotcha (at least with the AVR compiler)
Here the first icon works - as expected but the second (which was the first I tried) doesn't
Code: Select all
1 << (31 - .j)
Only shifts a byte value left - not a 32 bit value (as I expected). I worked around it by tweaking the size of .j (which was unnecessary) and then by using a mask variable (32 bit - as in first icon). This doesn't seem to affect most C compilers - maybe someone could test with some different toolchains? A possible work around would be to allow '1L' or '1ul' which in C would define a long or unsigned long integer constant (but this doesn't currently work in FC)..