## Monday, October 11, 2010

### Code Dump

### Basic cgo -- Redux!

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

## Sunday, September 5, 2010

### Rasterizing Circles and Ellipses

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)

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)

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:

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)

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.

## Wednesday, August 11, 2010

### Circular Number System in C

*a*distance and in some situations has value, but it is not the shortest distance. For that, the correct answer is -10 degrees.

## Friday, May 21, 2010

### The Heritage Universe

**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.

**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.

**Star Trek**and

**Star Wars**this was something very special indeed.

**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.

**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.

**Robot**and

**Foundation**series had, though, so such a future is in doubt. Ultimately, everything is left to the readers' imaginations.

## Saturday, April 24, 2010

### Callbacks with cgo

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.

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.

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

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. . .

Our cgo file is rather simple:

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.

## Sunday, March 21, 2010

### Grid Squares in a Circle

## Sunday, January 10, 2010

### 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.