Automatic dependencies for C++ in 3 very simple lines of make

I like Make. Make is best ponbuild tool. If you don’t know it already, it expresses dependencies as a DAG (directed acyclic graph), so a node lists it’s dependencies and has a rule about how to generate the file(s) from the dependencies. If a file is older than its dependencies, then it’s stale and needs to be rebuilt.

If the DAG is specified correctly, then if you change one source file, you’ll rebuild the minimum necessary with the maximum possible parallelism…

…I meant GNU Make by the way, of course.

In Make, dependencies are generally specified statically, like this:

target: dependency1 dependency2

The problem with this is that in many cases dependencies are not static. That is, the dependencies are a function of the dependencies. What? OK, let me illustrate. Suppose you have a dependency:

foo.o: foo.cc

OK, so the object file foo.o depends on foo.cc. So far, so good. But it’s almost certainly incomplete. If foo.cc #include’s anything then foo.o also relly depends on that too. In other words with the incomplete dependencies, if you modify that header and type “make”, foo.o won’t rebuild because make doesn’t know it ought to. This has the annoying problem that when you’re modifying headers, you keep having to “make clean” and rebuild everything.

Fortunatley, make provides a solution for you in typical make fashion: it provides the mechanism to deal with dynamic dependencies and you provide the language specific tools. You can just do:

include morestuff

Naturally, morestuff is going to be dynamically generated. GCC is nice and since it knows about the dependencies (it has to when it actually does the compile), and will emit them in make format while it does the build, ready to be included next time. So if a source file changes, the .o is rebuilt and new dependencies are generated. Next time we come to build, it checks those fresh new dependencies.

.PHONY: all clean

all: prog

clean:
	rm -f *.o *.d prog .deps

prog: a.o b.o
	$(CXX) -o prog $^


#We can't use the built in rule for compiling c++.
#
#Let's say a header changed to include a new header.
#That change would cause a rebuild of the .cc file
#but not the .d file. 
#
# Arguments mean:
# -MMD output #include dependencies, but ignore system headers, while
#      the build continues
# -MF output dependencies to a file, so other crud goes to the screen
# -MP make a blank target for dependencies. That way if a dependency is
#     deleted, make won't fail to build stuff 
%.o %d: %.cc
	$(CXX) -c $< $(CXXFLAGS) -MMD -MP -MF $*.d

#Search for all .d files and add them
#Note that .d files are built in with .o files. If there's no .o yet,
#then there's no .d. But that's OK; there are no precise dependencies,
#but we know we have to rebuild it anyway because the .o is not there.
#So, it's OK to only pick up .d files that have alredy been generted.
include $(wildcard *.d)

And the full set of files.

Now try creating an empty “c.h” and make b.h include it. Type make (you’ll see a.o rebuild). Now touch “c.h”. Make will rebuild a.o again as it should. Revert b.h and remove c.h. Make again builds it correctly. Touch c.h again and type make and nothing (correctly) gets rebuilt.

Actually, the mechanism is is subtle and interesting. It looks like a simple include directive, but the key is that if morestuff doesn’t exist, make will build it first, include it and then process the rest of the build. You cn do cool stuff there, but fortunately it’s not needed here.

Advertisements

A long overdue rewrite of my Autoconf tutorial

In 2003, I learned Autoconf in order to write a configure script for libCVD. There were not many good resources for those getting started so I wrote a tutorial.  The tutorial was rather dated and contained some bad practices and missed things I should have covered properly. I also made the mistake of documenting just Autoconf on its own without doing a more in depth treatment of how it integrates with Make. In hindsight that was a mistake. Technically Autoconf is entirely independent of Make. In practice you’re almost always going to use them as a pair and without showing them together it’s hard to convey how to get Autoconf to control Make properly.

I also didn’t have any complete, working examples. Now I have 13.

The new version is now hosted on github:

https://github.com/edrosten/autoconf_tutorial

and on my website here as well:

http://www.edwardrosten.com/code/autoconf/

Arduino without the arduino environment (a minute guide)

The only way to learn a new programming language is by writing programs in it. The first program to write is the same for all languages:

Print the words
hello, world

This is the big hurdle; to leap over it you have to be able to create the program text somewhere, compile it successfully, load it, run it, and find out where the output went. With these mechanical details mastered, everything else is comparatively easy.

–Kernighan & Ritchie, 1978

This quote is annoyingly true in the world of microcontrollers. “Hello, world” is considered to be flashing an LED, and it’s more a case of learning the microcontroller rather than a language, though there’s often not that much different, due to the idiosyncrasies of microcontrollers.

This time, I’m diving in to Atmel, via Arduino. Today I came to the conclusion that I needed some reasonably precise timing on some I/O lines. So, I went off to Maplin to see what they had and perhaps not very surprisingly they had a selection of Arduinos (they no longer stock PICKIT in store), so I picked one up. The device consists of an Atmega328p MCU, another Atmega acting as a USB-serial device, a USB port, some bootloader software and some headers including in circuit programming ones.

Essentially the Arduino is everything you need to do to get started with microcontrollers (except the USB cable), a standard breakout layout and an easy to use programming environment. The Arduino environment is not suitable for me today. This is not a criticism, but the trade of simplicity for flexibility means it deals with all the interrupts and timers and good control over them is precisely what I need.

Without the nice environment, the main problem is figuring out the correct magic incantations to go from some C code to a blinking LED. It of course also took me far longer than it ought to have done to figure out, which is why I’m writing about it here.

Here’s the C++ program (test.cc) which I want to run. Note that avr-gcc comes with some nice utilities like time delays, and the Arduino UNO (and most other arduinos) have an LED wired up to what is labelled as pin 13 on the board which corresponds to B5 for the UNO.

#include <avr/io.h>
#include <util/delay.h>
int main()
{
    // DDRB  Data Direction Register for port B
    // 1 corresponds to output. 0 for input.
    // _BV is Bit Value, i.e. BV(x) is 1<<x
    DDRB |= _BV(DDB5); 

    while(1) 
    {
	PORTB^=_BV(PB5);
        _delay_ms(100);
    }
}

And here are the magic incantations in the form of a Makefile:

#This is the form of names cross compilers usually have
CXX=avr-g++
CC=avr-gcc
LD=avr-g++

#atmega328p is used on the Arduino Uno
#It needs to be specified in several places so it's in the 
#Makefile, not the source code.
MCU=atmega328p

#serial port for programmer
#Find this by typing "dmesg" after plugging in the cable
PORT=/dev/ttyACM0

#Specify the CPU frequency in Hz
#Required for the delay() function in the C source.
F_CPU=16000000UL

#Specify optimizations:t's more common to optimize for size
#not speed (-Os) due to limited flash. We need to tell the compiler
#what the MCU is (of course), and F_CPU needs to be #defined before
#the util header is included.
FLAGS=-Os -mmcu=$(MCU) -DF_CPU=$(F_CPU)

#Set these flags so they're picked up by the implicit C and C++ 
#compiler rules.
CXXFLAGS=$(FLAGS)
CFLAGS=$(FLAGS)


OBJECTS=test.o

#Bog standard linker line
test:$(OBJECTS)
	$(LD) -o $@ $<


# Programmers expect HEX files not ELF files.
# Copy the text and data sections to make a hex file.
# .text is the machine code. .data is all the static data
# I don't believe we need anything else
%.hex: %
	avr-objcopy -j .text -j .data -O ihex $< $@

clean:
	rm -f *.o *.hex test

# "make upload" target to program the MCU
# -p specify MCU
# -c progrmmer type.
# -e erase
# -U actions which are flash memory write test.hex
# -P perial port
upload:test.hex
	avrdude -p $(MCU) -c arduino -e -U flash:w:test.hex  -P $(PORT)

And that’s it. It was as simple as I expected/hoped. Other than a bit of Make guff and some verbosification to make it a bit more managable and obvious, there’s 4 lines of active code, one of which is a completely standard linker instruction. How many LOC per day would that make it? 🙂

I’d like to thank Micah Carrick and Sudar Muthu for their guides/tools which is where I got most of the information from in the end.

Simple unit testing with a Makefile

Automated unit tests are very useful. They’re an excellent way of making sure you haven’t broken something in an obvious way when you change things. You can also implement them with very little work and without needing to pull in an external framework, just by using Makefiles. Since Make understands dependencies, this also ensures that when edits are made, only the minimal number of tests need to be rerun.

This is slightly simplified example on the method I’ve been using on the TooN library and my own projects.

Let’s say you have a very simple matrix class:

#ifndef MATRIX_H
#define MATRIX_H

#include <cmath>
#include <initializer_list>
#include <array>
#include <cassert>
#include <iostream>
struct Matrix2
{
	
	std::array<std::array<double, 2>, 2> data;

	public:

		Matrix2(std::initializer_list<double> i)
		{
			assert(i.size() == 4);
			auto d = i.begin();
			data ={ *(d+0), *(d+1), *(d+2), *(d+3)};
		}

		std::array<double,2>& operator[](int i)
		{
			return data[i];
		}	

		const std::array<double,2>& operator[](int i) const
		{
			return data[i];
		}	


		Matrix2 operator*(const Matrix2& m) const
		{
			Matrix2 ret = {0,0,0,0};

			for(int r=0; r < 2; r++)	
				for(int c=0; c < 2; c++)	
					for(int i=0; i < 2; i++)
						ret[r][c] += (*this)[r][i] * m[i][c];
			return ret;
		}

};

inline double norm_fro(const Matrix2& m)
{
	double f=0;
	for(int r=0; r < 2; r++)	
		for(int c=0; c < 2; c++)	
			f+=m[r][c];

	return sqrt(f);
}

inline Matrix2 inv(const Matrix2& m)
{
	double d = 1./(m[0][0]*m[1][1] - m[1][0]*m[0][1]);

	return {
		 m[1][1]*d,   m[0][1]*d ,
		 -m[1][0]*d,  m[0][0]*d 
	};
}

std::ostream& operator<<(std::ostream& o, const Matrix2& m)
{
	o<< m[0][0] << " " << m[0][1] << std::endl;
	o<< m[1][0] << " " << m[1][1] << std::endl;
	return o;
}

#endif

(did you spot the error?)

And you want to find the inverse of a 2×2 matrix:

#include "matrix.h"

using namespace std;

int main()
{
	Matrix2 m = {1, 1, 0, 1};
	cout << "Hello, this is a matrix:\n" << m << endl 
	     << "and this is its inverse:\n" << inv(m) << endl;

}

Simple enough. In order to build it, you can write a very simple makefile:

CXX=g++-5
CXXFLAGS=-std=c++14 -g -ggdb -Wall -Wextra -O3  -Wodr -flto


prog:prog.o
	$(CXX) -o prog prog.o $(LDFLAGS)	

We can make:

make

And get a result:

Hello, this is a matrix:
1 1
0 1

and this is its inverse:
1 -1
-0 1

Plausible, but is it right? (a clue: no.) So, let’s write a test program that creates matrices and multiplies them by their inverse and checks their norm against the norm of I. This will go in tests/inverse.cc


#include "matrix.h"
#include <random>
#include <iostream>
using namespace std;


int main()
{
	mt19937 rng;
	uniform_real_distribution<> r(-1, 1);
	int N=10000;
	double sum=0;
	
	for(int i=0; i < N; i++)
	{
		Matrix2 m = {r(rng), r(rng), r(rng), r(rng) };
		sum += norm_fro(m * inv(m))-sqrt(2);
	}

	cout << sum / N << endl;

	//Looks odd? Imagine if sum is NaN
	if(!(sum / N < 1e-8 ))
	{
		return EXIT_FAILURE;
	}

	cout << "OK\n";
}

And we get the output:

6.52107

So there’s an error. At the moment the test is ad-hoc. We have to remember to compile it (there’s no rule for that) and we have to remember to run it whenever we make some edits. This can all be automated with Make.

So, let’s first make a rule for building tests:


#Build a test executable from a test program. On compile error,
#create an executable which declares the error.
tests/%.test: tests/%.cc
	$(CXX) $(CXXFLAGS) $< -o $@ -I . $(LDFLAGS) ||\ { \ echo "echo 'Compile error!'; return 126" > $@ ; \
	  chmod +x $@; \
	}

This is a bit unusual, instead of just building the executable, if it fails, we make a working executable which indicates a compile error. This will eventually allow us to run a battery of tests and get a neat report of any failures and compile errors rather than the usual spew of compiler error messages.

So now we can (manually) initiate make and run the test. Note that if the test fails, the program returns an error.

We’re now going to take this a bit further. From the test program we’re going to generate a file with a similar name, but that has one line in it. The line will consist of the test name, followed by a status of the result. We do this in two stages. First, run the test and append either “OK”, “Failed” or “Crash!!” to the output depending on the exit status. If a program dies because of a signal, the exit status is 128+signal number, so a segfault has exit status 139. From the intermediate file, we’ll then create the result file with the one line in it.

#Build a test executable from a test program. On compile error,
#create an executable which declares the error.
tests/%.test: tests/%.cc
	$(CXX) $(CXXFLAGS) $< -o $@ -I . $(LDFLAGS) ||\ { \ echo "echo 'Compile error!'" > $@ ; \
	  chmod +x $@; \
	}

#Run the program and either use it's output (it should just say OK)
#or a failure message
tests/%.result_: tests/%.test
	$< > $@ ; \
	a=$$? ;\
	if [ $$a != 0 ]; \
	then \
	   if [ $$a -ge 128 ] ; \
	   then \
	       echo Crash!! > $@ ; \
	   elif [ $$a -ne 126 ] ;\
	   then \
	       echo Failed > $@ ; \
	   fi;\
	else\
	    echo OK >> $@;\
	fi


tests/%.result: tests/%.result_
	echo $*: `tail -1 $<` > $@

We can now make test/inverse.result and we get the following text:

g++-5 -std=c++14 -g -ggdb -Wall -Wextra -O3  -Wodr -flto tests/inverse.cc -o tests/inverse.test -I .  ||\
        { \
          echo "echo 'Compile error!'" > tests/inverse.test ; \
          chmod +x tests/inverse.test; \
        }
tests/inverse.test > tests/inverse.result_ ; \
        a=$? ;\
        if [ $a != 0 ]; \
        then \
           if [ $a -ge 128 ] ; \
           then \
               echo Crash!! > tests/inverse.result_ ; \
           else\
               echo Failed > tests/inverse.result_ ; \
           fi;\
        else\
            echo OK >> tests/inverse.result_;\
        fi
echo inverse: `tail -1 tests/inverse.result_` > tests/inverse.result

And the contents is:

inverse: Failed

Just to check the other options, we can add the following line to tests/inverse.cc

*(int) 0 = 1;

And sure enough we get:

inverse: Crash!!

So it seems to be working. The next thing is to be able to run all the tests at once and generate a report. So we’ll add the following lines to use every .cc file in tests/ as a test and process the strings accordingly:

#Every .cc file in the tests directory is a test
TESTS=$(notdir $(basename $(wildcard tests/*.cc)))


#Get the intermediate file names from the list of tests.
TEST_RESULT=$(TESTS:%=tests/%.result)


# Don't delete the intermediate files, since these can take a
# long time to regenerate
.PRECIOUS: tests/%.result_ tests/%.test


#Add the rule "test" so make test works. It's not a real file, so
#mark it as phony
.PHONY: test
test:tests/results


#We don't want this file hanging around on failure since we 
#want the build depend on it. If we leave it behing then typing make
#twice in a row will suceed, since make will find the file and not try
#to rebuild it.
.DELETE_ON_ERROR: tests/results 

tests/results:$(TEST_RESULT)
	cat $(TEST_RESULT) > tests/results
	@echo -------------- Test Results ---------------
	@cat tests/results
	@echo -------------------------------------------
	@ ! grep -qv OK tests/results 

Now type “make test” and you’ll get the following output:

-------------- Test Results ---------------
inverse: OK
-------------------------------------------

The system is pretty much working. You can now very easily add tests. Create a .cc file in the tests directory and make it return s standard code and… that’s it. The very final stage is to make the target we want to build depend on the results of the test:

prog:prog.o tests/results
	$(CXX) -o prog prog.o $(LDFLAGS)	

At this point you can now type “make prog” and the executable will only build if all the tests pass. There’s one minor wrinkle remaining: make has no mechanism for scanning C++ source files to check for dependencies. So, if you update matrix.h then it won’t rerun the tests because it doesn’t know about the dependency of the test results on matrix.h. This problem can also be solved in make. The complete makefile (with the dependency scanner at the bottom is):

CXX=g++-5
CXXFLAGS=-std=c++14 -g -ggdb -Wall -Wextra -O3  -Wodr -flto


prog:prog.o tests/results
	$(CXX) -o prog prog.o $(LDFLAGS)	

clean:
	rm -f tests/*.result tests/*.test tests/*.result_ prog *.o


#Every .cc file in the tests directory is a test
TESTS=$(notdir $(basename $(wildcard tests/*.cc)))




#Get the intermediate file names from the list of tests.
TEST_RESULT=$(TESTS:%=tests/%.result)


# Don't delete the intermediate files, since these can take a
# long time to regenerate
.PRECIOUS: tests/%.result_ tests/%.test

#Add the rule "test" so make test works. It's not a real file, so
#mark it as phony
.PHONY: test
test:tests/results


#We don't want this file hanging around on failure since we 
#want the build depend on it. If we leave it behing then typing make
#twice in a row will suceed, since make will find the file and not try
#to rebuild it.
.DELETE_ON_ERROR: tests/results 

tests/results:$(TEST_RESULT)
	cat $(TEST_RESULT) > tests/results
	@echo -------------- Test Results ---------------
	@cat tests/results
	@echo -------------------------------------------
	@ ! grep -qv OK tests/results 


#Build a test executable from a test program. On compile error,
#create an executable which declares the error.
tests/%.test: tests/%.cc
	$(CXX) $(CXXFLAGS) $< -o $@ -I . $(LDFLAGS) ||\ { \ echo "echo 'Compile error!' ; return 126" > $@ ; \
	  chmod +x $@; \
	}

#Run the program and either use it's output (it should just say OK)
#or a failure message
tests/%.result_: tests/%.test
	$< > $@ ; \
	a=$$? ;\
	if [ $$a != 0 ]; \
	then \
	   if [ $$a -ge 128 and ] ; \
	   then \
	       echo Crash!! > $@ ; \
	   elif [ $$a -ne 126 ] ;\
	   then \
	       echo Failed > $@ ; \
	   fi;\
	else\
	    echo OK >> $@;\
	fi
	
tests/%.result: tests/%.result_
	echo $*: `tail -1 $<` > $@

#Get the C style dependencies working. Note we need to massage the test dependencies
#to make the filenames correct
.deps:
	rm -f .deps .sourcefiles
	find . -name "*.cc" | xargs -IQQQ $(CXX) $(CXXFLAGS) -MM -MG QQQ | sed -e'/test/s!\(.*\)\.o:!tests/\1.test:!'  > .deps

include .deps

The result is a basic unit testing system written in about 30 lines of GNU Make/bash. Being make based, you get all the nice properties of make: the building and testing all runs in parallel if you ask it to and if you update some file, it will only rerun the tests it needs to.The code along with some more sample tests is available here: https://github.com/edrosten/unit_tests_with_make