How to convert a large decimal number to binary MSb first quickly

[SuzyC]

I want my robots to talk!

I have stored phrases in a 8-Megabit serial EEPROM that requires a starting read address in a MSb first binary format.

That is, the EEPROM is  a sound file that stores phrases in streams of signed 8-bit data sampled values where I  specify the read starting address from 0 to i million binary. 

How do I convert quickly using C code

from decimal to MSb first binary to feed a 24-bit binary address  into the serial input of the EEPROM?

Each phrase has a starting address and a length in bytes to be read  to stream out the desired phrase.

[themadhippy]

is  modulo  and diving by 2 until you get 0 too slow?

[mariush]

Considering the amount of space you have, you could just arrange it so each sample uses multiples of 256 bytes, and you pad the last 256 byte chunk with null bytes. Then you'll only need two bytes to store the offset where each file goes.

Crudest way would be to simply divide the number by 256 several times and put the remainder in an array of bytes.

[Kalvin]

Write using the address lsb first, so you can output the read address lsb first as well.

[SiliconWizard]

Write using the address lsb first, so you can output the read address lsb first as well.

Yes, no conversion at all would be the fastest conversion.
The problem is that this "virtual" address must be carefully handled because when writing to EEPROM by bursts, it writes to consecutive addresses while your virtual addressing would not be consecutive in EEPROM at all. So could become a headache to avoid overwriting data at the "wrong" address.

[free_electron]

just store the target address in a lookup table. no need for conversion shenanigans.
a one dimensional table of 32 bit numbers would do it.

[SuzyC]

themadhippy..using modulo to do this task is very much too slow.

I recorded my phrases by recording samples of my voice with an audio editing program. I am recording using 8-bit unsigned samples at 4000 samples /sec. The sound editing program I used to record with shows the exact sample number of each phrase in a single long stream of all samples. Using the editor program I can see and hear clearly the start and stop of each phrase and this info is stored in a file on the computer. I can see the exact sample number of the start of a phrase as an offset from the start of the recording, and the start address is a decimal number and the end address is also a decimal number of samples.
The sound is stored by the sound editing program to a single file and I copy this entire single file to the EEPROM.

I then create an index of all phrases as individual 'tunes' and I name them in my MCU program.
 
The program then selects a phrase that I want to playback by searching my 'tune list'  and each 'tune' has the starting address and length.

The problem then is to rapidly convert the decimal address to a MSb first 24-bit binary address to send to the EEPROM.

Kelvin:  The idea of sending the address lsb first will result in setting the starting read address to some unexpected and completely wrong address.

Mariush:  To make the most use of the limited EEPROM storage space, I don't see the advantage to create fixed-length clusters.

SiliconWizard: Writing to the EEPROM is accomplished in writing 256-byte clusters of data. The entire sound file is stored on the EEPROM until the whole PC's MSDOS raw binary sound file is consecutively written to the EEPROM. There is no problem with this approach, exactly 8-MBits are written to the EEPROM in this way.

[Alien Brother]

I assume, the decimal number arrives as text through some text-based communication protocol? I think, you'll benefit from changing the protocol to send either hexadecimal text or some binary representation. Exchanging decimal text makes you multiply/divide by 10 whether you like it or not.

[SiliconWizard]

Modulo 2 and div 2 are of course trivial operations on a MCU: and, right shift. This is very fast.
The naive, yet possibly more than fast enough way to bit reverse a 24-bit integer would be:

Code: [Select]

static inline uint8_t Reverse8(uint8_t n)
{
uint8_t out = 0;

for (int i = 0; i < 8; i++)
{
out = (out << 1) | (n & 1);
n >>= 1;
}

return out;
}

static inline void Reverse24(uint8_t out[3], uint32_t address)
{
for (int i = 2; i >= 0; i--)
{
out[i] = Reverse8(address & 0xFF);
address >>= 8;
}
}
An optimizing compiler will automatically unroll all these loops.

If you are using a cortex-M4/M7 or later, they have a bit reverse instruction, which will of course be much faster:

Code: [Select]

static inline uint32_t Reverse24(uint32_t address)
{
#if (__ARM_ARCH_ISA_THUMB >= 2)
uint32_t nResult;

__asm__ volatile
(
"rbit %0, %1\n"
"lsrs %0, %0, #8\n"
: "=r" (nResult) : "r" (address)
);

return (uint8_t) nResult;
#endif
}
Here it will return the bit-reversed address in a 32-bit integer, send the least significant byte first (on a Cortex-M MCU, you can directly take the pointer to the return value and send it as 3 bytes as it's little-endian).

RISC-V MCUs have a similar rev instruction in the B extension if they support it.

There's otherwise a faster way of bit reversing than the first "naive" version using bitwise operations.
(Cf. https://aggregate.org/MAGIC/#Bit%20Reversal )

But if you are using a Cortex-M4+ MCU, just use the rbit instruction as I showed above. I don't think GCC supports a builtin function for this, so you'd have to resort to the inline assembly I wrote above.

[mariush]

You could also pre-calculate the offsets and store an "index file" at the beginning of your eeprom ... ex first two bytes represents the number of entries, then you have 2 bytes per entry giving you the offset to where the sound file starts.
At the start of each sound file, the first 2 or 4 bytes could tell you the actual amount of bytes the sample consumes (so you won't read a few null bytes).
 
You could still choose to make the minimum read size some amount that would allow you to more efficiently do that index, while wasting as little eeprom space as possible.

For example, let's say you use multiples of 16, that means each file will start at a multiple of 16, so 16 bits are enough to access 1 MB :  0..65535 x 16 = 0..1,048,560 bytes

You also don't even need to load this index file into microcontroller's memory, if you want to play sound file 100, you simply seek to 2 bytes + 2 x 100 = 202, read two bytes to get the offset, then convert these 2 bytes to actual offset and start reading from there.

[aeg]

atol()

[cfbsoftware]

If you are using a cortex-M4/M7 or later, they have a bit reverse instruction, which will of course be much faster:

FYI Cortex-M3 also has the RBIT instruction.

[Sacodepatatas]

I then create an index of all phrases as individual 'tunes' and I name them in my MCU program.
 
The program then selects a phrase that I want to playback by searching my 'tune list'  and each 'tune' has the starting address and length.

The only reason I can imagine you want to do the conversion at run time, is because you include the index list from outside the MCU. Because if you want to include the "tune list" as array of const offsets stored in the MCU flash, then the compiler does the conversion to binary transparently. In fact it is what a compiler does 99% of the time when dealing with decimal numbers at source code.

But if you want to do it at run time, either atol(), or if you find atol slow, then this:

Code: [Select]


uint32_t myAtoUL(char *input){
  uint32 result;
  for(result=0;*input;input++){result*=10; result+=*input-'0';}
  return result;
}


[brucehoult]

I assume, the decimal number arrives as text through some text-based communication protocol? I think, you'll benefit from changing the protocol to send either hexadecimal text or some binary representation. Exchanging decimal text makes you multiply/divide by 10 whether you like it or not.

Multiplying by 10 is not slow! Even if you don't have a multiply instruction it's just 2-3 instructions on Arm or RISC-V (and probably faster than a multiply instruction anyway).

Arm:

Code: [Select]

    add r0, r0, r0, lsl #2
    lsl  r0, r0, #1

RISC-V, base ISA (or two instructions with Zba extension using sh2add e.g. on RP2350):

Code: [Select]

    slli t0, a0, 2
    add a0, a0, t0
    slli a0, a0, 1

Heck it's not even hard on a 6502:

Code: [Select]

    lda N
    asl
    asl
    clc
    adc N
    asl
    sta N

Of course it's longer for a 16 or 24 bit integer. e.g. 24 bit

Code: [Select]

    lda N+2
    sta T+2
    lda N+1
    sta T+1
    lda N
    sta T
    asl
    rol N+1
    rol N+2
    asl
    rol N+1
    rol N+2
    clc
    adc T
    sta N
    lda N+1
    adc T+1
    sta N+1
    lda N+2
    adc T+2
    sta N+2
    asl N
    rol N+1
    rol N+2

I make that as 83 cycles on 6502 ...

Read a char from a serial port and add it to N ...

Code: [Select]

again:
    lda uart
    beq again
    clc
    sbc #'0'
    adc N
    sta N
    bcc done
    inc N+1
    bne done
    inc N+2
done:

I get 30 cycles worst case for that. So 113 cycles per character. Over 9000 characters per second at 1.023MHz. It's 50% faster than needed to keep up with 57600 8N1, converting decimal strings of numbers between 0 and 16,777,215  to binary.

I give the extended 6502 example not because you're using a 6502, but because you're almost certainly using something better than a 6502. AVR or PIC or 8051 are all going to be similar but better.

On Arm or RISC-V converting a decimal string to binary is reading the next input character from the UART, plus 3-4 clock cycles.

[Alien Brother]

Multiplying by 10 is not slow!

Ok, you are right that it's not a big deal if numbers fit into registers. But still, using decimal text in a protocol makes you (and the machine) do more work for possibly little benefit.

Although it could be that if you only need to parse numbers that fit in registers, decimal text won't be worse than hexadecimal text, because maybe checking the input against one range '0'-'9' and multiplying is not worse than checking against two or three ranges (added 'a'-'f' and maybe 'A'-'F') and shifting.

[westfw]

The problem then is to rapidly convert the decimal address to a MSb first 24-bit binary address to send to the EEPROM.

I don't understand.

Are you perhaps under the impression that a statement like:Code: [Select]   send_eeprom_address(myEEPROM, 7234567);needs to somehow convert the number to "binary"?  You don't - once the compiler and hardware is involved, the number is already in binary, internally.  (I've seen other beginners make this mistake.  I don't know whether you are a beginner.)

And the MSb vs LSb thing ought to be a red herring - most modern SPI hardware has a configuration option to send bytes either LSb or MSb first (what hardware and software environment are you using?)  If you're sending bits manually, you can equally easily start at either end of the word.

And finally, "rapidly" would seem irrelevant.  Even if you're converting decimal text numbers to binary by traditional multiply and add algorithms on an 8bit CPU with no multiply instruction, that's going to already be "blindingly fast" compared to the time between values sent to a DAC to create audio (~23us per sample at CD-quality 44.1kHz, compared to about 14us for atol("12345") on a 16Mhz AVR (according to a benchmark))

[cv007]

and the start address is a decimal number and the end address is also a decimal number of samples

westfw is correct (maybe others mentioned this also), it doesn't seem there is a problem that needs solving-

https://godbolt.org/z/Mdrxa5Mfo

The compiler using your audio program decimal values is not a problem that needs any conversion on your part. The compiler is reading your source code as ascii text and making number conversions based on the number format (such as 123 vs 0x123).