Random Hack: Calculations in GNU make

I built an efficient algorithm for decimal addition in GNU make last year. While I won’t vouch for its production quality (on the other hand: why not?), it’s too cute a hack to hide from the world.

Unlike other implementations, this isn’t using unary encoding, and as such doesn’t suffer from their limitations. While unary encoding can be implemented quickly (addition is simple concatenation, conversion to integer is \$(words)), maximum string length (and RAM use) preclude certain use cases.

Originally this hack was devised to calculate memory addresses in a 32bit address space (for coreboot, of course), and calculating a number close to 4 billion using at least two bytes for every increment is prohibitive for a build system. Those 8 GB would be better spent on a RAM disk for build collaterals.
This code uses a couple of bytes per digit in decimal representation, so those 4 billion end up with 40-or-so bytes of RAM needed (not sure about make’s overhead).

In the end, the code wasn’t used since we already have too much magic in the coreboot build system.

So here it is. Subtraction (or support for negative numbers) is left as an exercise to the reader.

reverse=\$(if \$(1),\$(call reverse,\$(wordlist 2,2000,\$(1)),\$(word 1,\$(1)) \$(2)),\$(2))

_fill_to_2=\$(if \$(filter 0 1 2 3 4 5 6 7 8 9,\$(1)),0\$(1),\$(1))
_fill_all_to_2=\$(foreach item,\$(1),\$(call _fill_to_2,\$(item)))
_split=\$(subst 0,0 ,\$(subst 1,1 ,\$(subst 2,2 ,\$(subst 3,3 ,\$(subst 4,4 ,\$(subst 5,5 ,\$(subst 6,6 ,\$(subst 7,7 ,\$(subst 8,8 ,\$(subst 9,9 ,\$(1)))))))))))
_sar=\$(call reverse,\$(call _split,\$(1)))
space=\$()
space+=
_addition_table:=1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11 12 4 5 6 7 8 9 10 11 12 13 5 6 7 8 9 10 11 12 13 14 6 7 8 9 10 11 12 13 14 15 7 8 9 10 11 12 13 14 15 16 8 9 10 11 12 13 14 15 16 17 9 10 11 12 13 14 15 16 17 18