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.

A simple custom iterator example

Someone recently asked me about custom iterators in C++. It turns out most of the examples and tutorials are not ideal, especially if you get the principle but not the mechanics.

Without getting bogged down in boilerplate, here’s a complete standalone example which compiles and runs. It provides an iterator that iterates over a string one chunk at a time, returning those chunks (words and gaps):

#include <string>
#include <cctype>  //for isgraph
#include <iterator>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//Iterate over a string one chunk at a time.
//
//Deriving from std::iterator is necessary to make the code work with 
//the standard algorithms (for now). Either that or specialising the
//std::iterator_traits type. We're telling it that we have a forward 
//iterator and that the value returned from dereferencing is a string.
//
//Note that this derivation is not necessary for simple for-loops or
//using the iterator in any custom context.
class ChunkStringIterator: public iterator<forward_iterator_tag, string>
{
	//Represent the string remaining to be iterated over as a
	//string iterator pair.
	string::const_iterator b, e;
	
	public:
		ChunkStringIterator(string::const_iterator b_, string::const_iterator e_)
		:b(b_), e(e_)
		{}
		
		//Return the chunk starting at the current position
		string operator*()
		{
			auto n = find_next();
			return string(b, n);
		}
	
		//Advance to the next chunk
		ChunkStringIterator& operator++()
		{
			b = find_next();
			return *this;
		}

		//We need this operator for the classic iteration loop
		bool operator!=(const ChunkStringIterator& i) const
		{
			return b != i.b;
		}

	private:
		
		//This is the meat: it returns an iterator to one-past-the-end of
		//the current chunk. Chunk is defigned as a contiguous region of 
		//chars of the same category.
		string::const_iterator find_next()
		{
			auto current = b;
			bool printable = isgraph(*current);
			
			while(current != e && (bool)isgraph(*current) == printable)
			{	
				++current;
			}
			
			return current;
		}

};


//This class is a trivial wrapper for string that dishes out
//the custom iterators.
class ChunkString
{
	const string& data;
	public:
		ChunkString(const string& s)
		:data(s)
		{}
		
		ChunkStringIterator begin()
		{
			return ChunkStringIterator(data.begin(), data.end());
		}

		ChunkStringIterator end()
		{
			return ChunkStringIterator(data.end(), data.end());
		}
};


int main()
{
	string foo = "Hello, world. This is a bunch of chunks.";
	
	//A for-each loop to prove it works.
	for(auto w: ChunkString(foo))
		cout << "Chunk: -->" << w << "<--\n";

	//Use a standard algorithm to prove it works
	vector<string> chunks;
	copy(ChunkString(foo).begin(), ChunkString(foo).end(), back_inserter(chunks));
	cout << "there are " << chunks.size() << " chunks.\n";


}

Note: this is not complete. I haven’t implemented anything that’s not necessary to the the for each example working. It’s basically missing the other comparison operator (==) and the other dereference operator (->). Probably some other things too.

Enhanced constexpr

In an earlier post I wrote about using constexpr to generate compile time lookup tables. Unfortunately it turns out that that was dependent on a GCC extension. In actual C++14, pretty much nothing in <cmath> is constexpr.

My brother and I have written a proposal, currently P0533R0 to introduce a number of constexpr functions into <cmath>. Making functions constexpr is slightly tricky because some of them may set the global variable errno and/or floating point exception flags (effectively global variables),  and so it needs to be a language solution, not a pure library one. However, the basic arithmetic operators also fall into similar traps, so it’s not that bad.

The initial paper is to constexpr-ify all “simple” functions which don’t have pointer arguments. In this case, simple is defined as “closed over the extended rationals”, which includes the standard arithmetic operators, comparison operators and things like floor() and ceil(). It turns out there are actually rather a lot of these including many I’d never heard of before ploughing through <cmath>.

I think it should be straightforward to implement since GCC and LLVM both already do compile time evaluation of even non-simple functions (e.g. sqrt), the former actually making them constexpr as an extension of C++14, the latter only using them in the optimizer.

 

 

 

libble++: simple Bluetooth Low Energy on Linux.

Here’s the code on github!

I’ve been working on a Bluetooth Low Energy library for Linux. The emphasis is on modern C++ design, and simplicity of use. I started before BlueZ supported BLE in a meaningful manner, so this library uses bits and bobs from BlueZ, some linked from libbluetooth, and some extracted from the source code.

I don’t make use of any of the GATT (that’s the high level interface, which is implemented over the ATT protocol which itself is sent over bluetooth sockets) code within BlueZ, which is all implemented over DBus. I just construct the packets (that’s the code I pulled out of BlueZ) and send them over a bluetooth socket myself.

With the brief introduction out of the way, how about some code :).

Here’s a complete program which scans for BLE devices:

#include <blepp/lescan.h>

int main()
{
   BLEPP::log_level = BLEPP::LogLevels::Info;
   BLEPP::HCIScanner scanner;
   while (1) {
    std::vector<BLEPP::AdvertisingResponse> ads = scanner.get_advertisements();
   }
}

Is that about the shortest scanning example you’ve ever seen? 😎 I cheated very slightly by bumping up the log level. Otherwise it’d sit there scanning and generating no output whatsoever, which would not be all that much use.

I’ve also not commented this because I think it’s reasonably self evident. There are only two active lines, creating a scanner object and getting the scan results. I also bump up the logging level so it shows scan results without having to print stuff from the ads struct. Not that that is hard, but since more or less everything is optional information, it’s mildly tedious.

With that little hook out of the way, the library follows a socket-and-function design, much like XLib if you happen to know that. In other words, there’s a socket which all the functions use and which is created for you. If you have a simple interaction with BLE to write, you can just use the functions and never worry further. If you have a slightly more complex interaction, for example if you don’t want to block, then you can get the socket and select(), poll(), epoll() or use any other of your favourite system calls.

So as a result, there’s no framework. It’s just a library. It won’t steal your main loop or make it hard to integrate with any other I/O system you happen to have kicking around.

Interacting with a bluetooth device beyond scanning is a bit more complicated, because devices with interaction are a bit more complicated. It’s more or less the same model, except it uses callbacks (set via std::functions), because various bits of information can arrive asynchronously.

Here’s a complete example which shows how to connect to a temperature monitor and log the readings it gives. I’ve highlighted the non-trivial lines so you can see how much code and how much boilerplace there is (not much!):

#include <iostream>
#include <iomanip>
#include <blepp/blestatemachine.h>
#include <blepp/float.h>  //BLE uses the obscure IEEE11073 decimal exponent floating point values
#include <unistd.h>
#include <chrono>
using namespace std;
using namespace chrono;
using namespace BLEPP;

int main(int argc, char **argv)
{
	if(argc != 2)
	{	
		cerr << "Please supply address.\n";
		cerr << "Usage:\n";
		cerr << "prog <addres>";
		exit(1);
	}

	log_level = Error;

	//This class does all of the GATT interactions for you.
	//It's a callback based interface, so you need to provide 
	//callbacks to make it do anything useful. Don't worry: this is
	//a library, not a "framework", so it won't steal your main loop.
	//In other examples, I show you how to get and use the file descriptor, so 
	//you will only make calls into BLEGATTStateMachine when there's data
	//to process.
	BLEGATTStateMachine gatt;

	//This function will be called when a push notification arrives from the device.
	//Not much sanity/error checking here, just for clarity.
	//Basically, extract the float and log it along with the time.
	std::function<void(const PDUNotificationOrIndication&)> notify_cb = [&](const PDUNotificationOrIndication& n)
	{
		auto ms_since_epoch = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
		float temp = bluetooth_float_to_IEEE754(n.value().first+1);

		cout << setprecision(15) << ms_since_epoch.count()/1000. << " " << setprecision(5) << temp << endl;
	};
	
	//This is called when a complete scan of the device is done, giving
	//all services and characteristics. This one simply searches for the 
	//standardised "temperature" characteristic (aggressively cheating and not
	//bothering to check if the service is correct) and sets up the device to 
	//send us notifications.
	//
	//This will simply sit there happily connected in blissful ignorance if there's
	//no temperature characteristic.
	std::function<void()> found_services_and_characteristics_cb = [&gatt, &notify_cb](){
		for(auto& service: gatt.primary_services)
			for(auto& characteristic: service.characteristics)
				if(characteristic.uuid == UUID("2a1c"))
				{
					characteristic.cb_notify_or_indicate = notify_cb;
					characteristic.set_notify_and_indicate(true, false);
				}
	};
	
	//This is the simplest way of using a bluetooth device. If you call this 
	//helper function, it will put everything in place to do a complete scan for
	//services and characteristics when you connect. If you want to save a small amount
	//of time on a connect and avoid the complete scan (you are allowed to cache this 
	//information in certain cases), then you can provide your own callbacks.
	gatt.setup_standard_scan(found_services_and_characteristics_cb);

	//I think this one is reasonably clear?
	gatt.cb_disconnected = [](BLEGATTStateMachine::Disconnect d)
	{
		cerr << "Disconnect for reason " << BLEGATTStateMachine::get_disconnect_string(d) << endl;
		exit(1);
	};
	
	//This is how to use the blocking interface. It is very simple. You provide the main 
	//loop and just hammer on the state machine struct. 
	gatt.connect_blocking(argv[1]);
	for(;;)
		gatt.read_and_process_next();

}

OK so there are come caveats.

Mostly, it’s not finished. I wrote the library to support the work I’m currently doing, and so I’ve not needed to do anything like everything that the BLE protocol supports. BLE also has a lot of features I doubt anyone’s seen in the wild. I don’t like implementing code I can’t use and test, so I’ve not got any interface to features I don’t currently use.

It’ll likely grow over time and get more features, but if there’s something you’d like in there, let me know. It might be easy for me to put in, or I can give pointers to help you write the necessary code.

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/

The best of both worlds

I currently run Ubuntu LTS (14.04 at the moment) on my work laptop and Arch on my home laptop. I like the stability of Ubuntu, and very much like that I  can run security updates without breaking anything. However, the old versions of programs are annoying in some cases. I love running Arch because I always have the latest versions. This bit me today since the version of gerbv I was running was too old to support the high resolution drill placements in Eagle 7 and so my gerbers looked bad.

Give me Archbuntu!

First, get arch-bootstrap.sh and run it in (say) /other_OS to make /other_OS/ARCH_x64. You now have a bootstrapped arch installation. You can chroot into it and it looks arch-like but won’t work properly.

The main reason is that none of the special files are there. Essentially you want everything to mirror your main OS, except for the the OS itself. This can be done with bind mounts. Add the following to /etc/fstab and run mount -a

/proc          /other_OS/ARCH_x64/proc          none defaults,bind 0 0
/sys           /other_OS/ARCH_x64/sys           none defaults,bind 0 0
/dev           /other_OS/ARCH_x64/dev           none defaults,bind 0 0
/tmp           /other_OS/ARCH_x64/tmp           none defaults,bind 0 0
/home          /other_OS/ARCH_x64/home          none defaults,bind 0 0
/etc/passwd    /other_OS/ARCH_x64/etc/passwd    none defaults,bind 0 0
/etc/shadow    /other_OS/ARCH_x64/etc/shadow    none defaults,bind 0 0
/etc/group     /other_OS/ARCH_x64/etc/group     none defaults,bind 0 0
/etc/sudoers   /other_OS/ARCH_x64/etc/sudoers   none defaults,bind 0 0
/etc/sudoers.d /other_OS/ARCH_x64/etc/sudoers.d none defaults,bind 0 0

Now you can chroot into /other_OS/ARCH_x64 and run pacman. Note that /tmp is shared partly to avoid duplication, but also because that’s where the X11 socket it. Without it, you’ll need to use xhost to allow chroot’d programs to connect. And the password related files are duplicated to so sudo still works.

While you can sudo, chroot, then su – to yourself then run programs, that’s a little inconvenient. chroot is root only for security reasons, but since the chroot image is legitimate, we can chroot into that safely as anyone. The following code essentially chroots into /other_OS/ARCH_x64, drops root and then executes its arguments.

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>

int main(int argc, char** argv)
{
	int r = chroot("/other_OS/ARCH_x64/");

	if(argc == 1)
		return 0;
	
	if(r == -1)
	{
		fprintf(stderr, "Error chrooting: %s\n", strerror(errno));
		return 1;
	}
	
	r = setuid(getuid());

	if(r == -1)
	{
		fprintf(stderr, "Error dropping root: %s\n", strerror(errno));
		return 1;
	}

	r = setgid(getgid());

	if(r == -1)
	{
		fprintf(stderr, "Error dropping root: %s\n", strerror(errno));
		return 1;
	}

	execvp(argv[1], argv+1);

	fprintf(stderr, "Error: %s\n", strerror(errno));
}

Compiling this as ae (think arch exec) and putting it in the path allows you to do “ae gerbv” instead of “gerbv” to get the Arch version, for example. Note that unlike the commandline version, the chroot function doesn’t alter the CWD, so it all works just fine.

Now I have the best of both worlds!

Compile time lookup tables

There are many good reasons to have lookup tables computed at compile time. In C++ 14 this is now very easy with generalized constexpr. It took me a while thinking about it before I realised that it really was that easy! Here’s an example of one:

#include <iostream>
#include <cmath>

//Trivial reimplementation of std::array with the operator[]
//methods set to constexpr
template<class T, int N>
struct array
{
	T elems[N];

	constexpr T& operator[](size_t i)
	{
		return elems[i];
	}

	constexpr const T& operator[](size_t i) const
	{
		return elems[i];
	}
};

//Function to build the lookup table
constexpr array<float, 10> foo()
{
	array<float, 10> a = {};

	for(int i=0; i < 10; i++)
		a[i] = exp(i);

	return a;
}

constexpr static array<float, 10> lut = foo<float>();

//This simply serves as a class to be instantiated.
template<int I> struct Silly
{
	Silly()
	{
		std::cout << "Hello " << I << "\n";
	}
};

int main()
{
	//Prove they're compile time constants
	Silly<(int)lut[0]> s0;
	Silly<(int)lut[1]> s1;
	Silly<(int)lut[2]> s2;
	Silly<(int)lut[3]> s3;
	Silly<(int)lut[4]> s4;
	Silly<(int)lut[5]> s5;
	Silly<(int)lut[6]> s6;
	Silly<(int)lut[7]> s7;
	Silly<(int)lut[8]> s8;
	Silly<(int)lut[9]> s9;
}

The only minor wrinkle is that std::array does not have its members set to constexpr to a sufficient degree, so it doesn’t work in this context. However, since few features are needed, a minimal reimplementation is pretty straightforward.