Arithmetic in GNU Makefiles

Docs and source on GitHub

GNU Make treats all variables as strings, which isn't so great when you want to count stuff. With access to a shell, though, problems like this tend to go away until you want to make your build process cross-platform. Then something like the GNU Make Standard Library (GMSL) was probably your best bet.

GMSL uses the length of a list of 'x' characters to represent a number, adding is then as easy as concatenating them.

4 -> "x x x x"
2 -> "x x"
4 + 2 -> "x x x x x x"

Subtraction is a little trickier, GMSL uses the join function to produce a list of the same length as the larger parameter, within which, the 'x's from the smaller parameter will be joined onto the elements to form elements with value 'xx', these elements can then be filtered out.

4 - 2 -> filter-out("xx", "xx xx x x") -> "x x"

These methods work well for smaller numbers, but there are obvious problems when the values become large. This led me to implement another algorithm that works in a much more intuitive way. I simply implemented addition, subtraction, multiplication and division similar to how you would do them on paper.

Encoding

GNU Make does not include a native method for obtaining the Nth character in a string, it does however, include a function for obtaining the Nth element(word) in a list. In order to make use of this, the digits of the number are split into elements of a list.

digits := 0 1 2 3 4 5 6 7 8 9
space :=
space +=
split = $(strip $(if $(1),$(foreach d,$(digits),$(if $(1:$(d)%=),,$(d) $(call split,$(1:$(d)%=%))))))
concat = $(subst $(space),,$(1))

The "hot" functions (inc, dec, add and sub) work out nicely if the list is reversed, i.e. word 1 is the least significant digit.

reverse = $(strip $(if $(1),$(call reverse,$(wordlist 2,$(words $(1)),$(1)))) $(firstword $(1)))

The functions prefixed with rl_ operate using this encoding, They do not take into account sign or leading zeros, these are handled at a higher level. Most of the lower level functions fall under this category.

The functions prefixed with l_ are similar except the list is not reversed.

Algorithms

Using the template of "written down on paper" arithmetic, the first thing required was to be able to increment and decrement a digit stored as a word, and for this to wrap around in the appropriate manner. This was done rather simply with 2 lookup tables and conditional statements looking for inputs of value 0 (necessary as the word indexing is 1 relative).

digit_inc = $(__gmsl_tr1)$(if $(call nlz_eq,$1,0),1,$(word $1,$(__gmsl_inc_lut)))
digit_dec = $(__gmsl_tr1)$(if $(call nlz_eq,$1,0),9,$(word $1,$(__gmsl_digits)))

The next thing required was to add two digits together, and have them wrap in a similar way to the increment and decrement. This function tests the 2nd argument for 0 and either returns the 1st argument if the 2nd is 0 or recurses with the 1st argument incremented and the 2nd decremented if it is not. This effectively takes one from the 2nd argument and adds it to the 1st until the 2nd is 0, then it returns the 1st. Something very similar can be done in order to subtract 2 digits, however instead of incrementing the 1st argument when the 2nd is decremented, it is decremented also.

digit_add = $(__gmsl_tr2)$(if $(call nlz_eq,$2,0),$1,$(call digit_add,$(call digit_inc,$1),$(call digit_dec,$2)))
digit_sub = $(__gmsl_tr2)$(if $(call nlz_eq,$2,0),$1,$(call digit_sub,$(call digit_dec,$1),$(call digit_dec,$2)))

In order to handle numbers with multiple digits, there would need to be a way of detecting overflow. Ideally this should be done by testing for the values that would cause overflow at the point of calling increment/decrement. However when this is not practical, a less than function prior to the whole operation could be used.

This less than function involves a check for argument equality, if the arguments are equal, the function returns false (an empty string) otherwise if the 1st argument is 0 the function returns true else it recurses with the 1st argument decremented.

digit_lt = $(__gmsl_tr2)$(if $(call nlz_eq,$1,$2),,$(if $(call nlz_eq,$1,0),1,$(call digit_lt,$(word $1,$(__gmsl_digits)),$2)))

03/11/16


I have now merged the standalone arithmetic library with GMSL.

16/11/16