Code Dump

I've opened up a project on Google Code to host sample code that I write. It's intended to be a repository of files related to blog or forum posts that I write, allowing me to share full source code in a cleaner way that simply including it in the posts themselves. The posts will still include snippets, of course. For now all I have uploaded is the modified code for my Basic cgo article. The entire page is located at http://code.google.com/p/cheesesuncodedump/.

Basic cgo -- Redux!

I happened to notice that my Basic cgo article somehow ended up on go's Google Code page, and I thought that I should make sure my code still works. Some of the information is out of date, such as the files that cgo generates. As for the code: it both does and it doesn't. First off, the Makefile is out of date, so here's a new one:

include $(GOROOT)/src/Make.inc

TARG=gocurses

CGOFILES=gocurses.go

CGO_LDFLAGS=-lncurses

include $(GOROOT)/src/Make.pkg

CLEANFILES+=main

main: install main.go

$(GC) main.go

$(LD) -o $@ main.$O

Next, linking to ncurses via cgo currently does not work as a result of Issue 667. 6g spits out an "invalid recursive type" error and compilation fails. There is a way to work around this, however.

The file where the error occurs is _cgo_gotypes.go. In it is defined the go equivalents for the C types exposed in ncurses.h. The problem occurs where WINDOW is defined. If it is defined below the _win_st struct, 6g spits the error. If it is defined above _win_st, everything goes well. Fortunately, cgo will not recreate any files it generates as long as the original source file is unaltered. This allows us to modify any of those generated files and call make main again in order to continue building the project.

With that in mind, the fix is simple:

1. Run make main and see the error
2. Open _cgo_gotypes.go and move the line defining _Ctypedef_WINDOW to above _Ctype_struct__win_st
3. Run make main again

The program should work from there.

Rasterizing Circles and Ellipses

You might recall my post about a fast way of determining what grid squares fit within a circle of a given radius.  Beyond the roguelike applications, this algorithm also clearly useful for rasterizing a filled circle.  Here’s a modified version of the function:

def filled_circle(surface, x0, y0, r, c):
    for x in range(-r, r+1):
        dy = int(math.sqrt(r*r - x*x))
        for y in range(-dy, dy+1):
            surface.set(x0+x, y0+y, c)

surface is an object with the method set, which accepts x and y coordinates and a colour.  x0 and y0 are the coordinates of the circle’s origin, r is its radius, and c is its colour.

The function works by taking advantage of the circle equation: .  By solving for y we get the maximum value for a given x, and the function iterates between -y and y.  We can do the same thing for ellipses by substituting the ellipse equation: , where a is half the width of the ellipse and b is half the height.  Solving for y, we get the function:

def filled_ellipse(surface, x0, y0, a, b, c):
    for x in range(-a, a+1):
        dy = int(math.sqrt(b*b * (1.0 - float(x*x)/float(a*a))))
        for y in range(-dy, dy+1):
            surface.set(x0+x, y0+y, c)

That’s not a big change.

An unfilled circle uses a rather different algorithm.  If all we did was take the filled circle algorithm and for each x set pixels at dy and -dy, one would find that some pixels are missing.  This occurs in cases where there is more than one pixel for a given x.  We could account for these by swapping x and y in the function, but that results in plenty of redundant pixel setting.  Our goal is to set any given pixel only once.

A better method requires than one only finds the pixels for one-eighth of the circle and then rotate all of those pixels to find the rest of the circle.  This is simply done by going through all positive and negative combinations for the given coordinate.  For example, for (10, 1) we also have (-10, 1), (10, -1), and (-10, -1).  That’s four eighths of the circle, and the rest are determined by swapping x and y: (1, 10), (-1, 10), (1, -10), and (-1, -10).

Now the only issue is finding that eighth of a circle.  This is done in a similar way to finding the pixels in a filled circle.  We iterate through x coordinates, calculating the y coordinates.  We’ve reached an eighth when x is equal to or greater than y.  Unlike the filled circle, we will start at 1 instead of -r.  We could start at 0, but by doing that we will set the furthest top, bottom, left, and right pixels more than once.  Instead, we will set those before we start the loop.  Similarly, we will stop searching for pixels in our eighth before x is equal to y, otherwise the four more pixels will be set twice.  As such, we will set those once, when x equals y.  Thus:

def circle(surface, x0, y0, r, c):
    surface.set(x0, y0 + r, c)
    surface.set(x0, y0 - r, c)
    surface.set(x0 + r, y0, c)
    surface.set(x0 - r, y0, c)

    x = 1
    while True:
        y = int(math.sqrt(r*r - x*x))
        if x < y:
            surface.set(x0+x, y0+y, c)
            surface.set(x0-x, y0+y, c)
            surface.set(x0+x, y0-y, c)
            surface.set(x0-x, y0-y, c)
            surface.set(x0+y, y0+x, c)
            surface.set(x0-y, y0+x, c)
            surface.set(x0+y, y0-x, c)
            surface.set(x0-y, y0-x, c)
        else:
            if x == y:
                surface.set(x0+x, y0+y, c)
                surface.set(x0-x, y0+y, c)
                surface.set(x0+x, y0-y, c)
                surface.set(x0-x, y0-y, c)

            break
        x += 1

There’s a lot of lines there, but it’s mostly just pixel setting.  The actual algorithm is quite simple.

Ellipses follow a similar path, but not as simple.  Like with circles, one does not have to calculate the entire shape.  However, since ellipses are only symmetrical about two axes, we must find an entire quarter.

Recall what I mentioned about the use of the filled circle algorithm for determining the edge.  If we used that, the result is missing pixels.  Thus, when we come to the point at which pixels might be missing, we switch to iterating over the y axis.

Determining the point to switch over is not simple.  With circles it would be the halfway point, where x equals y.  With an ellipse that point is variable save for one constant: the point where the tangent is 45 degrees.  Another way of putting it is where the slope is 1 or -1.

Calculus tells us that the derivative of a function presents us with a function representing the slope of the original.  Thus we solve for y in the ellipse equation and take the derivative of the result.  I will not go into the steps involved (mostly because my calculus is rusty and I found a website to do it for me).  It suffices to say that when the slope for a given x is equal to or less than -1.0, we switch.

def ellipse(surface, x0, y0, a, b, c):
    surface.set(x0, y0+b, c)
    surface.set(x0, y0-b, c)
    surface.set(x0+a, y0, c)
    surface.set(x0-a, y0, c)

    y = 0
    for x in range(1, a):
        y = int(math.sqrt(b*b * (1.0 - float(x*x)/(float(a*a))))
        if -b * x / (a * math.sqrt(a*a - x*x)) < -1:

            break

        surface.set(x0+x, y0+y, c)
        surface.set(x0-x, y0+y, c)
        surface.set(x0+x, y0-y, c)
        surface.set(x0-x, y0-y, c)

    for dy in range(1, y+1):
        dx = int(math.sqrt(a*a*(1.0 - float(dy*dy)/float(b*b))))
        surface.set(x0+dx, y0+dy, c)
        surface.set(x0-dx, y0+dy, c)
        surface.set(x0+dx, y0-dy, c)
        surface.set(x0-dx, y0-dy, c)

That’s it and without setting any pixel more than once.

Circular Number System in C

In a previous post I discussed the idea of a circular number system. To reiterate: it is a system whereby the passing the maximum value will return one to the beginning. Take a twenty-four hour clock, for example, which has the range of [0, 23]. The hour that is two hours beyond 23 is not 25, but 1.

Another example is angle measurement. If one has two angles, one at 5 degrees and another at 355 degrees, how far is the second from the first. Linear measurement has one subtracting the two, resulting in an answer of 350 degrees, but looking at the two angles marked on a circle one can see that that is not entirely correct. It is a distance and in some situations has value, but it is not the shortest distance. For that, the correct answer is -10 degrees.

The implementation of this system that I posted was written in Python, but different programming languages have different behaviours for the modulo operator. In some cases, like C++, the behaviour depends upon the implementation. I will not discuss these differences here, as more knowledgeable individuals have already done so elsewhere. For the purpose of this article, I refer to the default C standard used by gcc under Ubuntu 10.04 Linux.

One further difference between C and Python is that Python's modulo operator also works with floating point numbers, while in C it works only with integers. For floating point numbers one must use fmod, which is found in math.h.

Here is the difference function in C:

double diff(double x0, double x1) {

double r = fmod(x1 - x0 + 0.5*UPPER, UPPER);

return (r <>

}

The function finds the shortest distance to x1 from x0 distance, assuming a range of [0, UPPER). The maximum absolute distance between any two values will never be more than half of UPPER.

The Heritage Universe

Looking back, there were two authors whose works enticed me to stop selecting random books based on their titles and focus instead on individual writers. One is Piers Anthony, whose Bio of a Space Tyrant series I read when I was sixteen. Briefly, I can describe that series as a combination of science fiction adventure and a dose of the erotic -- which is everything a sixteen year-old boy could want. The other author was Charles Sheffield, whose novel Summertide helped me break away from the science fantasy of so much other books under the "sci-fi" genre and into hard(er) science fiction.

There is no single aspect of Summertide that piqued my interest, but a combination. As I mentioned, it falls into the sub-genre of hard science fiction, whose "science" is generally based in some way on modern theories. Given the distance into the future Summertide takes place, this is difficult to apply to much of the technology involved, but there is enough that it has the feeling of possibility.

There is also the milieu of alien species, which is certainly not new to me in science fiction, but the range of shapes was. No species is humanoid save for Humanity itself. For somewhat whose introduction to science fiction came in the form of Star Trek and Star Wars this was something very special indeed.

Finally there is the Builders, the ancient and unbelievably advanced species and the mindbogglingly enormous artifacts that they left behind. Sure, Babylon 5, had such beings as the Vorlons and the Shadows, but while their motives might seem enigmatic, they remained clearly active participants in the interstellar scene. The Builders are never truly revealed and even their sentient creations have little useful to say about their creators' nature. This mystery is the basic premise of the series.

Interestingly, there is no real antagonist in any of the books. The conflict has more to do with the dangerous situations the environments present than anything else. One might argue that the Zardalu (an alien species in the series) were at times the antagonists. In two of the books this is in a way literally true, but I found them presented more as players in a scene written by others (namely the Builders). They acted antagonistic towards the protagonists, but they were never the main issue. The result is that throughout the series the theme is not simply one of overcoming other individuals (though that does happen), but one of exploration and learning.

As for the author himself, Sheffield may not be the greatest author I have read. His narrative lacked the flowing introspective style presented by authors such as Stephen R. Donaldson or the sweeping epic style of those such as Glen Cook, but it was not a bad style, either. His writing was competent and his characterisations were convincing. He understood how to write about people and given them personalities that felt real and possible to empathise with. This is really basic stuff when it comes to writing fiction, but I have read several books whose authors proved unable to do this (or unable to do it more than once, merely repeating the same characterisations under different names in each book). Basically, I never found myself at odds with the author, while at the same time wishing better for the story. Charles Sheffield was simply a good author.

Over a decade after reading the first volume, I have finally read the final one: Resurgence. I purchased the entire series via WebScription.net and read it start to finish. It is just as good a series as I remembered it.

It is unfortunate that Sheffield died the year the final volume was published. It ends with a newly discovered threat and a inference that a new set of protagonists would take over. I have to wonder if this was Sheffield's own indication that the series should continue with new blood directing it, knowing that he might not be able to do so himself. The series never gained the popularity that such iconic works as Isaac Asimov's Robot and Foundation series had, though, so such a future is in doubt. Ultimately, everything is left to the readers' imaginations.

Callbacks with cgo

A major limitation of cgo is the lack of support for callbacks or, in more general terms, the ability for C to call a Go function.  This is a major issue for bindings to event driven systems.  As part of impending support for SWIG, however, the Go team has expanded cgo to provide a facility by which Go functions may be exposed to C.

In one's cgo files, exposing a function is a very simple matter: one precedes the function header with a comment starting with the word export and followed by the function name.  For example:

//export Foo

func Foo() {

    // ...

}

When cgo sees this it generates two new C files: _cgo_export.c and _cgo_export.h.  These files provide the wrappers that enable a C program to call Go functions.

Provided with the current distribution of Go is an example program demonstrating this new feature.  It is found in:

$GOBIN/misc/cgo/life

Looking through that example, though, one should notice one problem: it is not an example classic callbacks.  That is, Go is not passing functions to C.  Instead, the functions are merely being exposed so that C can call them.  Thus the problem remains for event driven libraries such as GLUT.  Callbacks are achieved via a bit of indirection.

Let us start by creating a very simple library that adds number via a callback.  It has a single function, call_add, which takes a function pointer and calls it to add two integers.

// calladd.h

typedef int(*adder)(int, int);

extern void call_add(adder);

//callback.c

#include <stdio.h>

#include "calladd.h"

void

call_add(adder func) {

    printf("Calling adder\n");

    int i = func(3, 4);

    printf("Adder returned %d\n", i);

}

Nothing to it.  Compile it and turn it into a shared object:

gcc -g -c -fPIC calladd.c

gcc -shared -o calladd.so calladd.o

Now here's the interesting part: in order to pass a Go function to C we must create a wrapper that passes the wrapper to the Go function.  Wonderful, eh?  Two levels of indirection. . .

// funcwrap.h

extern void pass_GoAdd(void);

// funcwrap.c

#include "_cgo_export.h"

#include "calladd.h"

void

pass_GoAdd(void) {

    call_add(&GoAdd);

}

Our cgo file is rather simple:

//callback.go

package callback

// #include "callgo.h"

// #include "funcwrap.h"

import "C"

func Run() {

    // call the wrapper

    C.pass_GoAdd()

}

//export GoAdd

func GoAdd(a, b int) int {

    return a + b

}

This is still not really a callback, as we are not passing an arbitrary function.  That would require yet another level of indirection (for a total of three), whereby we store a function pointer and call it within GoAdd.  Hopefully in the future one level will be removed.  I suspect that this could be possible if cgo interpreted any passing of an exported function to a C function as passing the wrapper, but I cannot say that I have looked deeply into the matter.

To conclude, here's the Makefile for this project (a modified version of the life example's):

CGO_LDFLAGS=_cgo_export.o calladd.so funcwrap.so $(LDPATH_linux)

CGO_DEPS=_cgo_export.o calladd.so funcwrap.so

CLEANFILES+=main

include $(GOROOT)/src/Make.pkg

funcwrap.o: funcwrap.c _cgo_export.h

    gcc $(_CGO_CFLAGS_$(GOARCH)) -g -c -fPIC $(CFLAGS) funcwrap.c

funcwrap.so: funcwrap.o

    gcc $(_CGO_CFLAGS_$(GOARCH)) -o $@ funcwrap.o $(_CGO_LDFLAGS_$(GOOS))

main: calladd.so install main.go

    $(GC) main.go

    $(LD) -o $@ main.$O

Grid Squares in a Circle

I know that it's a minor operation, but for a long time I couldn't help but wonder if there were an optimized way of finding out which squares in a grid fall within a given radius. However, because it is such a minor operation and because the brute force method works adequately, I never actually went out of my way to try and solve this problem -- until now. Boredom is a wonderful thing. . .

First off, the brute force approach:

Given an origin (x0, y0) and a radius r, the maximum orthogonal extents of a circle is equal to (x0±r, y0±r). Given those extents, coordinates whose distance from the origin are less than or equal to the radius are within the circle.

def brute_coords(r):

    coords = []

    for y in range(-r, r+1):

        for x in range(-r, r+1):

            if math.hypot(x, y) <= r:

                coords.append((x, y))

    return coords

Very easy and with relatively small circles it is sufficiently fast. However, there should be a way to do this without even considering squares outside of the circle. There is and the solution comes thanks to the Pythagorean Theorem. Specifically, the circle's radius is the hypotenuse of a triangle and the distance along the x-axis is another length. The number of squares above and below that axis is equal to the final length. Thus we iterate along the minimum and maximum x-coordinates and calculate the verticals.

def smart_coords(r):

    coords = []

    for x in range(-r, r+1):

        dy = int(math.sqrt(r*r - x*x))

        for y in range(-dy, dy+1):

         coords.append((x, y))

    return coords

With small radii, such as a character's vision radius in a roguelike, the performance difference is a few milliseconds at most, on my system. With a radius of 100, smart_coords is twice as fast. At 1000, it takes 12 seconds, while brute_coords takes 17. That's pretty good!

As for whether the optimization is worthwhile in practical applications, I have no idea. I haven't made any real comparison and probably won't bother to. I will use it, though, if for no other reason than because it is better and it is not a very complex solution.

Go, syscall, and inotify

At the time of writing this article, Go does not implement all of the syscalls for which it has constants.  One of these is inotify, which allows one to monitor file system events.  It, and similar libraries are what allow file managers such as KDE's Dolphin or Gnome's Nautilus to almost immediately show a file's new date-stamp when it has been modified.

For information on inotify, check out the following article at LinuxJournal.com:

http://www.linuxjournal.com/article/8478

Fortunately, Go's syscall package exports the low-level function that it uses for all implemented syscalls.  This function is named, appropriately, Syscall.  There is also Syscall6, which receives six arguments (in addition to the syscall id) instead of three.  For our purposes, Syscall will be sufficient.

First, the basics:

Syscall receives and returns all values as the type uintptr.  This seems strange and at a glance would seem to indicate that it deals with pointers to all values, but that is actually not necessarily the case.  Integers, for example, are simply converted directly via a cast.

param := uintptr (num)

Strings, however, are a slightly more complex affair, but the syscall package provides a necessary function, StringBytePtr, which simply converts the string to a byte slice and returns a pointer to the first element.

param := uintptr (unsafe.Pointer (StringBytePtr (str)))

Although Syscall must receive three values (in addition to the syscall id), if the particular syscall requires less, one simply passes 0 to the remainder.  Similarily, it always returns three values, though not all are meaningful.  All are of the type uintptr: the first two being the actual return values, while the last is an error code.  Values that are not needed may be received as an empty variable: _.

The os package contains the functionality needed to print syscall error codes.  os.NewSyscallError receives a string and an integer.  The first should be the name of the syscall you attempted, while the last is the error code that Syscall returned (casted to int, of course).  The structure returned implements os.Error.

In C inotify consists of three functions: inotify_init, inotify_add_watch, and inotify_rm_watch.  The corresponding syscall ids are SYS_INOTIFY_INIT, SYS_INOTIFY_ADD_WATCH, and SYS_INOTIFY_RM_WATCH.  Given the above information, it is simple to call each.  For example:

fd , _, errptr = syscall.Syscall (syscall.SYS_INOTIFY_INIT, 0, 0, 0);
if err = os.NewSyscallError ("SYS_INOTIFY_INIT", int (errptr)); err != nil {
    // deal with the error
}

The first returned variable fd is the file descriptor, the second is ignored, and the last is the error code.

pth := "/home/ostsol/Programming/Go/notify/blah.txt"
str := uintptr (unsafe.Pointer (syscall.StringBytePtr (pth)));
wd, _, errptr = syscall.Syscall (syscall.SYS_INOTIFY_ADD_WATCH,
uintptr (fd), str, 0x00000002);
if err = os.NewSyscallError ("SYS_INOTIFY_ADD_WATCH", int (errptr)); err != nil {
    //deal with the error
}

Unfortunately, Go does not expose the event masks for inotify.  0x00000002 is the mask for the modify event.

The event can be read via syscall.Read, which receives the file descriptor (casted to int) and an empty byte buffer.  The inotify event structure is, of course, not implemented in Go, so one has to create one's own:

type NotifyEvent struct {
    Wd int32;
    Mask uint32;
    Cookie uint32;
    Len uint32
}

Decoding the buffer filled by syscall.Read is accomplished via the encoding/binary package.  The binary.Read function expects a type that fulfills the io.Reader interface, which one can create via the NewReader function in the strings package.

The original inotify_event structure exposed via the C header sys/inotify.h also contains a name field.  You'll notice that its type is char[0].  We did not add this field to our structure because binary.Read would try to find a value to put in it.  The value only exists if the Len field is greater than zero.  If it is, we can extract the string from the byte buffer manually.

chars := make ([]byte, 80);
ln, errno := syscall.Read (fd, chars);
if err = os.NewSyscallError ("SYS_READ", errno); err != nil {
    // deal with it
}

event := new (NotifyEvent);

reader := strings.NewReader (string (chars[0:]));
if err = binary.Read (reader, binary.LittleEndian, event); err != nil {
    // deal with it
}

fmt.Println ("Event:");
fmt.Printf ("\twd: %d\n\tmask: %d\n\tcookie: %d\n\tlen %d\n",
event.Wd, event.Mask >> 16, event.Cookie, event.Len);

if event.Len > 0 {
   fmt.Printf ("\tname: %s", string (chars[16:16+event.Len]))
}

In a real system, multiple events may be returned by syscall.Read.  Thus, the buffer may have to be much larger and one will have to iterate through it, each time creating a reader further along in the buffer.

event := new (NotifyEvent);

for i := uint32 (0); i < uint32 (ln); i += 16 + event.Len {
reader := strings.NewReader (string (chars[i:]));
 // ...
}

There are two problems that I encountered in the creation of this article.  First is the event.Mask field.  The value it returns is 32768, which is not the flag that I input via SYS_NOTIFY_ADD_WATCH.  Secondly, using SYS_NOTIFY_RM_WATCH tosses me an 'invalid argument' error.  Thinking it was a Go problem, I re-wrote the program in C, but the same issues occurred.  It's strange, but everything else I did works solidly.  Hopefully this article helps despite the issues.