Random Hack: Calculations in GNU make

Posted on 07.03.2014

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)))
_prune_leading_0=$(if $(filter 0 00,$(word 1,$(1))),$(call _prune_leading_0,$(wordlist 2,2000,$(1))),$(1))
_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
_shuffle=$(call _prune_leading_0,$(subst $(space)$(space),,$(call _split,$(call _fill_all_to_2,$(1)))))
_add_up=$(foreach item,$(1),$(if $(filter-out 0 00,$(item)),$(word $(item),$(_addition_table)),0))
_add_up_till_done=$(if $(filter-out 0 1 2 3 4 5 6 7 8 9 00 10 20 30 40 50 60 70 80 90,$(1)),$(call _add_up_till_done,$(call _shuffle,$(call _add_up,$(1)))),$(1))
_add_inner=$(if $(1)$(2),$(call _add_inner,$(wordlist 2,2000,$(1)),$(wordlist 2,2000,$(2)),$(word 1,$(1))$(word 1,$(2)) $(3)),$(3))
_add=$(call _add_up,$(call _add_up_till_done,$(call _add_inner,$(1),$(2))))

add=$(subst $(space),,$(call _add,$(call _sar,$(1)),$(call _sar,$(2))))

$(warning $(call add,9995,5))

Feel free to use it under ISC-License, © 2013 Patrick Georgi <patrick@georgi-clan.de>