Embedded C--Recursion, C Macros, Stupid Stack Tricks, and a Clever Hex to Binary Function

....if that blog post title doesn't make you want to watch paint dry then what will?

Working on an AD9833 library for RP2040? Maybe next post....getting there....

Onward!

I am always trying to sharpen my Embedded C skills, the programming language I primarily use to program MCUs.

This week I continue to work on an AD9833 SPI library (already written for Atmel 328--here), ported to work with 32bit MCUs like the RP2040. 

Today though I went down the rabbit hole, trying to find the simplest function for hex or decimel to binary conversion for printf()'s 

Why? Why not?

A lot of embedded C programming (and digital electronics in general) comes down to sending 1's and 0's from one component to another. 

Doh?

However at times I can visualize what 0b0001011001110111 is going to do when viewing the dataflow on a logic analyzer 

Something like 0x1677 doesn't fire up my neurons the same way. 

Is that just me? A lack of experience with hex? Maybe. 

Unfortunately, C has no easy means I know to printf() a binary number--hex, yes, decimel, yes, floats, yes, but binary, no. 

So, it's a matter of finding a hex to binary function I like online and stealing it? Sure. 

I found plenty of C hex to binary functions online that start with a string array and produce binary output as a string (for instance, here), but for what we embedded C folks work on (mostly numbers, not a lot of strings) that's not much help. 

I needed the input parameter to be a number, not an array.

After a bit more searching I found a brilliant little recursive function--original post is here.  

It's only 4 lines of code!

#include "hex2bin.h"

void hex2bin(int16_t h)

{

if (!h) return; 

hex2bin(h>>1);

printf("%d",h&1);  

return;

}

It works!!  

Orig number:  0xdc or 7618976

11011100

  

How does this wonderful fragment work?  At first I didn't care, don't look gift code in the mouth? 

But then it started to drive me crazy. I could see no logical reason why bin2hex() should not present its output in the wrong order!

Why did I think that?

once you run this

h  >> 1 

The number you're converting (say, x = 200) decreases down to 0, so you're done. 

But, if you don't recurse, the printf()'d output shows an incorrect binary value because it's backwards; for example, 0b1100111 is output when you wanted 0b1110011.  

However the 4 line fragment doesn't do this--somehow it prints the final result in the correct order.

But how, Scotty, how?

Sadly Cap'n Kirk's C skills were shit, but could he kick ass with Esperanto....

Turns out, it's a call stack trick--using Codeblocks, in debug mode, with the stack and watches debug windows visible (good tutorial for Codeblocks C debugging is here), it was easy to see what was happening.

I created a simple (and very similar) function that subtracts 20 from "h" which in this case is 220:

void hex2bin(int16_t h)

{

printf("h is: %d \n",h);

if (!h)

{   printf("IN RETURN. H is %d \n",h);

    return;}

else

{

    printf("not there yet \n");

}

hex2bin(h - 20);

printf("h is: %d \n",h);

}

The stack looks like this--the call stack loads its data "upwards"--so the values of h - 20 appear in reverse order:

  

Here is the output from the hex2bin function, called from main.c, with a parameter value of 220:

0bh is: 220

not there yet

h is: 200

not there yet

h is: 180

not there yet

h is: 160

not there yet

h is: 140

not there yet

h is: 120

not there yet

h is: 100

not there yet

h is: 80

not there yet

h is: 60

not there yet

h is: 40

not there yet

h is: 20

not there yet

h is: 0

IN RETURN. H is 0

h is: 20

h is: 40

h is: 60

h is: 80

h is: 100

h is: 120

h is: 140

h is: 160

h is: 180

h is: 200

h is: 220

The trick: when the code runs the printf() over and over, printf() starts at the top of the stack and pops the data off from top to bottom--from 20 to 220--which is the same behavior as hex2bin(), giving us exactly what we need.

Stupid stack tricks!  It works!! Genius!!!

Experimenting with this I found that any intelligently written recursive algorithm that stopped when a true was reached, with return statements in the right spots, would load the stack in the same manner and thus allow the function to return data backwards. I figure other use cases are possible--for instance, load an array in reverse order. I will experiment with this....in the meantime, it shows how to really master C, you have to know how the underlying hardware works.

Cool! Here's the call stack video again.

Not done yet! this is a recursive function, so, how could I put a 0b in front of the 010111, and an \n at the end, and any other window dressing needed? 

Since the 4 lines recurse, I couldn't put more printf() statements elsewhere in the function--I ended up with a whole bunch of 0b's at stdout each time the function recursed--something like

0b00b10b00b10b10b1

Yuck!

I ended up using a macro with a parameter in the .h file--another stupid C trick I didn't know about; but now I'm playing with power.

#include <stdint.h>

#include <stdio.h>

#ifndef HEX2BIN_H_INCLUDED

#define HEX2BIN_H_INCLUDED

//here's the macro....watch the line wrap....

#define HEX2BIN(X) printf("Orig number:  0x%x or %d \n",X);printf("0b");hex2bin(X);printf("\n")

 

void hex2bin(int16_t h); // c

#endif // HEX2BIN_H_INCLUDED

the #define prints a 0b in front of the conversion, and a carriage return at the end. Took me a bit to get the syntax right, but now, I know it.

Then I could call the macro from main.c arguing in a value of 220:

#include <stdio.h>

#include <stdlib.h>

#include "hex2bin.h"

int main()

{

    HEX2BIN(220);

    return 0;

}

Yeh baby!  Seems working!!!!  Get bin2hex C code from Github here. 

OK enough C for a Sunday. I worked most of the day digging into this. Did I get outside the house much? Nope.

 A very fine day it was.