Today’s hack

Let’s say you’re automating a git workflow for a variety of good and bad reasons. Commits are fine, you can just do a:

commit -am 'a message'

and it goes through non interactively. Now let’s say you have a merge and you try:

git merge

It pop open an editor window to let you type a message. There’s no merge -m option to let you provide a message. If you look closely, you’ll see that the editor window already has a message filled in saying it’s a merge. This means if you save without exiting, git sees a message and decides all is OK and it can proceed. So all you have to do is provide an “editor” which quits without saving every time. The program which does nothing except exit successfully is /true so you can simply do:

EDITOR=true git merge

for a non interactive merge.

I don’t know whether to be proud or ashamed, but it works.

 

Small hack of the day

Two things:

  1. syntax highlighting is nice
  2. wouldn’t it be nice to copy /paste it

The main problem is many terminals don’t for no especially good reason allow copy/paste of formatted text. There are three tools which help:

  1. xclip -t text/html this eats standard input and allows pasting of it as HTML, so it can include formatting and color and so on. By default, xclip does plain text, so you have to specify that it’s HTML.
  2. aha this takes ANSI formatted text (i.e. the formatting scheme used by terminals and turns it into HTML).
  3.  unbuffer many tools will only write color output to a terminal, not a pipe. Through the magic of PTYs (pseudoterminals) this program fools other programs into thinking they’re running on a terminal when they’re not.

Now all you have to do is pipe them together. So, take a silly C++ program like this:

void silly;

And compile it like this:

unbuffer g++-7 error.cc -std=c++1z  | aha | xclip -t text/html

Then a simple paste into a box which accepts HTML (e.g. email, etc) gives:

error.cc:2:6: error: variable or field 'silly' declared void
 void silly;
      ^~~~~

 

Server Send Events

Server send events are a way of getting data pushed over an http connection to a browser. The JavaScript interface is very simple. Here’s some useful info:

I thought it would be a neat way of debugging some GIS code in C++: all I had to do was write the data to a socket, and have a page that collected it in JavaScript and plugged it into Google maps. It was that simple, sort of, except that it was actually incredibly awkward getting it up and running since web browsers are both finicky and don’t provide much error information.

All you have to do is open a socket, write the right HTTP headers and send the correct data. I eventually ended up sending it in chunked encoding, which means each message is essentially preceded by a length so the browser knows how much data to accept and put together into a message.  The alternative is to use Content-Length and have fixed length messages (like the w3schools example), but I couldn’t manage to get my browser (Firefox) to accept more than one message before closing the connection due to an error. No idea why, but the chunked encoding is much more flexible anyway.

Probably the biggest hurdle is that my HTLM page was just a file, but the server send events were from a (local) server. Either way that meant it was cross domain and so Firefox would block the request because of CORS. Turns out the fix was a simple headre tweak but that had me going for a while!

Anyway, here’s the code:

#include <iostream>
#include <cstring>
#include <cerrno>
#include <vector>
#include <iomanip>


#include <unistd.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netinet/ip.h>


using namespace std;

class VeryBasicServer
{
	private:
		int sockfd=-1; 
		int connection_fd{-1};
	
	public:

		VeryBasicServer()
		{
			//Incantation to create a socket 
			//Address famile: AF_INET (that is internet, aka IPv4)
			//Type is a reliable 2 way stream, aka TCP
			//Note this just creates a socket handle, it doesn't do anything yet.
			//The 0 is the socket type which is pretty redundant for SOCK_STREAM (only one option)
			sockfd = socket(AF_INET, SOCK_STREAM, 0);
			if (sockfd < 0)
				throw runtime_error("Error opening socket:"s + strerror(errno));

			
			//Set options at the socket level (a socket has a stack of levels, and 
			//all of them have options). This one allows reuse of the address, so that
			//if the program crashes, we don't have to wait for the OS to reclaim it, before
			//we can use this socket again. Useful for debugging!
			int true_ = 1; 
			setsockopt(sockfd,SOL_SOCKET,SO_REUSEADDR,&true_,sizeof(int));
			
			
			//Binding a socket is what sets the port number for a particular
			//socket.
			sockaddr_in serv_addr = {};
			serv_addr.sin_family = AF_INET;          //internet address family
			serv_addr.sin_addr.s_addr = INADDR_ANY;  //allow connections from any address
			serv_addr.sin_port = htons(6502);        //Still fighting the 80s CPU wars. 6502 > 8080
			if (bind(sockfd, (struct sockaddr *) &serv_addr, sizeof(serv_addr)) < 0) 
				throw runtime_error("Error binding socket:"s + strerror(errno));
			
			//This is necessary for stream sockets (e.g. TCP). When a client_ connects
			//a new socket will be created just for that connection on a high port.
			listen(sockfd,5);
		}
		

		void read_ignore_and_dump_incoming_data()
		{
			vector<char> buf(65536, 0);
			int n = read(connection_fd,buf.data(),buf.size());
			if (n < 0) 
				throw runtime_error("Error reading from socket:"s + strerror(errno));
			cout << "Message reads: ";
			cout.write(buf.data(), n);
		}

		void accept()
		{
			//Listen blocks until a cnnection is made, then hands over the newly created
			//socket for the connection
			connection_fd = ::accept(sockfd, nullptr, nullptr);

			if (connection_fd < 0) 
				throw runtime_error("Error accepting:"s + strerror(errno));
			
			//We can actually ignore the HTTP header just to get up
			//and running. For ServerSendEvents, there's only one accepted
			//MIME type, and uncompressed is always a valid compression option
			//even if the client_ doesn't request it.
			read_ignore_and_dump_incoming_data();


			//Construct a valid working header.
			//
			//Two important things to note. One is the access control. Since
			//this server isn't serving anything except SSEs, the web page
			//which is using them ust come from elsewhere. Unless we allow 
			//connections from places other than the originating server, then
			//the web browser will block the attempt for security.
			//
			//The other point is the chunked encodeing. The browser connecting
			//has to know when we've finished sending an event in the stream
			//of data. Chunked encoding allows us to send data blocks along with a 
			//length so the server knows when a block is finished. The other option
			//is to have a fixed Content-Length instead. I never got it working,
			//but it's much less flexible so I didn't try hard.
			//
			//Note also the \r\n line terminations, not just \n. Part of the HTTP spec.
			write("HTTP/1.1 200 OK\r\n"                          //Standard HTTP header line
			      "Content-Type: text/event-stream\r\n"          //This is the only allowed MIME type for SSE
                  "Transfer-Encoding: chunked\r\n"               //Chunked encoding lets it know when an event is done without knowing packet boundaries.
				  "Access-Control-Allow-Origin: *\r\n"           //Because the HTML comes from a file, not this server, we have to allow access
			      "\r\n");                                       //End of header indicator

		}
		
		//Write data with less than the minimal amount of error checking.
		void write(const string& str)
		{
			int n = ::write(connection_fd, str.data(), str.size());

			if(n < 0)
				throw runtime_error("Error writing:"s + strerror(errno));
		}

		void write_chunk(const string& str)
		{
			//Chunked encoding is the size in hex followed by the data. Note that both
			//the size and data fields are terminated by HTTP line terminations (\r\n)
			ostringstream o;
			o << hex << str.size() << "\r\n" << str << "\r\n";
			write(o.str());
		}

		~VeryBasicServer()
		{
			cerr << "closing\n";
			close(connection_fd);
			close(sockfd);
		}
};


int main()
{
	VeryBasicServer hax;

	hax.accept();
	
	cout << "Press enter to send an event" << endl;
	for(int i=1;;i++)
	{
		if(cin.get() == EOF)
			break;
		
		//Build up an event in server-send-event format. The message consists of 
		//one or more fields of the form:
		//field: value\n
		//Followed by an empty line.
		//
		//The main tag is "data:" which carries the data payload.
		//See https://developer.mozilla.org/en-US/docs/Web/API/Server-sent_events/Using_server-sent_events
		//for more info (e.g. different message types and dispatch)
		string sse;
		sse += "data: " + to_string(i) + "\n";  //Send the current number as the data value
		sse += "\n";                            //Empty field ends the message.

		//Send the message data using chunked encoding
		hax.write_chunk(sse);

	}

}

And the corresponding HTML page is:

<!DOCTYPE html>
<html>
<head>  <meta charset="UTF-8"> </head>
<body>

<h1>Getting server updates</h1>
<div id="result"></div>

<script>
if(typeof(EventSource) !== "undefined") {
    var source = new EventSource("http://127.0.0.1:6502");
    source.onmessage = function(event) {
        document.getElementById("result").innerHTML += "Data: " + event.data + "<br>";
    };
    source.onerror = function(event) {
        document.getElementById("result").innerHTML += "Connection failed<br>";
    };
} else {
    document.getElementById("result").innerHTML = "Sorry, your browser does not support server-sent events...";
}
</script>

</body>
</html>

And that’s basically it. It’s a handy and rather silly chunk you can put in a C++ file. It’s a lot of very poor practices and does all the wrong things for scalability, security, generality and good sense, but it’s handy for debugging hacks.

Code is on github.

Blog as you go: sigma delta DAC

I have some piezo speakers from another project. That one used a bi-level amp to drive them. I figured it would  be fun to try a tri-level drive, using an H bridge allows you to have +, – and 0V across the device. And for fun, why not make it a direct sigma delta encoder?

It’s going to run on a microcontroller (an arduino). It’ll need very precise timings, so I’ll not be using the arduino environment.

Here’s a first pass in C++ for linux:


#include <iostream>
#include <cmath>
#include <utility>

using namespace std;

float signal(int t)
{
	//Roughly 0-1
	return (1 + sin(t/20. - 1))/2.1;
}

float quantize(float f, int levels)
{
	return min(levels-1.f, max(0.f, floor(f*levels)))/(levels-1);
}

int main()
{

	float integral = 0;

	for(int i=0; i < 200; i++)
	{
		float output = quantize(integral, 3);
		float difference = signal(i) - output;
		integral += difference;

		cout << signal(i) << " " << output << endl;
	}

}

And this produces output like this (mildly prettified):
graph.png

Which looks about right. The code will pretty much stink on an arduino since it’s all floating point. It’s easy to convert to integer code though:

#include <iostream>
#include <cmath>
#include <utility>

using namespace std;

uint16_t signal(int t)
{
	//Roughly 0-1
	return 65535 * (1 + sin(t/20. - 1))/2.1;
}

uint16_t quantize(int32_t i)
{
	if(i < 21845)
		return 0;
	else if (i < 43690)
		return 32768;
	else
		return 65535;
}

int main()
{

	int32_t integral = 0;

	for(int i=0; i < 200; i++)
	{
		uint16_t output = quantize(integral);
		float difference = signal(i) - output;
		integral += difference;

		cout << signal(i) << " " << integral << " " << output << endl;
	}

}

I’ve used a uint16_t for the value, which will effectively represent both positive and negative levels with 32768 being the zero point. Note that the error integral must be both signed and wider since the errors can grow beyond the signal range:

graph.png

Now to port to the arduino. So, I’ll get my Makefile from here.

I’m going to pick pins 8 and 9 on the UNO, that is PB0,1 on the chip for my outputs. and here’s how you get 3 way opposed outputs as +/-/0. To demo, I connected a pair of LEDs in parallel but facing the other way:


#include <avr/io.h>
#include <util/delay.h>
int main()
{
	int i=0;

    while(1)
    {
		if(i==0)
		{
			DDRB = 3;
			PORTB = 1;
		}
		else if(i==1)
		{

			DDRB = 3;
			PORTB = 2;
		}
		else
		{
			DDRB=0;
			PORTB = 0;
		}

		i++;
		if(i > 2)
			i=0;

        _delay_ms(200);
    }
}

So I started the port and BOOM! 😦

It stopped working. The reason was simple: the simple makefile takes one object file and converts it to HEX. Since I’m using sin(), we actually need to link the .o and .a into a .elf file, then convert THAT to HEX. The snippet is:

%.hex: %.elf
avr-objcopy -j .text -j .data -O ihex $< $@

prog.elf: delta_sigma.o
avr-gcc $(FLAGS) -o prog.elf delta_sigma.o -lm

Obvious, really, in hindsight…

So, OK, now to convert the modulator code to the arduino. Lots of things went wrong. But first, here’s the code:

#include <math.h>
#include <stdint.h>
#include <avr/io.h>

uint16_t signal(int32_t t)
{
	float u = t / 1024.f;

	//Roughly 0-1
	return 65535 * (1 + sin(2*3.151592f*u))/2.1;

}

uint16_t quantize(int32_t i)
{
	if(i < 21845)
		return 0;
	else if (i < 43690)
		return 32768;
	else
		return 65535;
}

int main()
{

	int32_t integral = 0;

	DDRB|=32;

	for(uint32_t i=0; ; i++)
	{
		uint16_t output = quantize(integral);
		int32_t difference = (int32_t)signal(i) - output;
		integral += difference;

		if(output == 0)
		{
			DDRB=255;
			PORTB=1; //Output 1 0
		}
		else if(output == 65535)
		{
			DDRB =255;
			PORTB=2; //Output 0 1
		}
		else
		{
			DDRB=255;
			PORTB=0; //Output 0 0
		}
	}
}

What didn’t go wrong? Nothing! I wasn’t nearly careful enough with my ints (only 16 bits on AVR), ints of specific width, overflow and that sort of thing. Also, initially, I decided to output a 0 level by tri-stating the two outputs, so they both float to the middleish. Turns out that didn’t work well since they float extremely slowly (not surprising really!). Forcing them both down to 0 worked much better.

After all that, I then connected a simple RC filter across it so you an see the results:

That’s actually a pretty nice sine wave there! It ought to be: there’s really not much room for nonlinearity and other distortions to creep in. I’ve zoomed in a few levels so you can see how it looks in detail.

It is however really really slow. I’m using full floating point, and a transcendental operation every iteration of the sigma delta encoder. That is really slowing down the cycle time since the AVR isn’t very fast. That accidentally solves the other problem which I’ve made no attempt to make sure every path takes the same number of cycles. But that sin() is dominating so heavily that it doesn’t matter.

And that’s it for part 1: a working sigma delta encoder. For part 2, I’ll make it fast enough to generate audio tones which aren’t simply the sigma-delta encoder transitions (I hope).

Oh also here’s tehe obligatory github link.

 

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.