Cogs and Levers A blog full of technical stuff

numpy

numpy is an excellent library for dealing with array-based math problems. According to the website:

NumPy is the fundamental package for scientific computing with Python

In today’s post, I’ll go through some very basic operations of the library while piecing together the transformation segment that you might see in the back-end of a 3D rendering pipeline. We’ll focus on some vector and matrix math, but most importantly we’ll look at the creation of specialised matricies and matrix multiplication.

Vectors

All points in our 3D world is going to be re-presented by a 4D Homogenous co-ordinate. numpy provide the perfect abstraction here with the array function.

p = np.array([1, 0, 0, 1])

There are many other construction functions available for this single dimension value series that you can find in the documentation.

Once we’ve created the array, we can start to perform arithmetic on it.

>>> np.array([1, 0, 0, 1]) + np.array([0, 1, 0, 1])
array([1, 1, 0, 2])

>>> np.linalg.norm(np.array([1, 0, 0, 1]))
1.4142135623730951

>>> np.array([1, 0, 0, 1]).dot(np.array([0, 1, 0, 1]))
1

Matrices

Graduating from the vector, we now need a tabular representation for our linear algebraic operations that we’ll perform. To do this, we’ll use a matrix which numpy has a direct analog for.

First of all, every math library needs a shortcut to the identity matrix:

>>> np.identity(4)
array([[ 1.,  0.,  0.,  0.],
       [ 0.,  1.,  0.,  0.],
       [ 0.,  0.,  1.,  0.],
       [ 0.,  0.,  0.,  1.]])

Getting back into our 3D engine, we’re going to need a way to translate, scale and rotate the array points.

Translation

A translation matrix in 3-space using a 4x4 matrix looks like this:

[ 1 0 0 tx ]
[ 0 1 0 ty ]
[ 0 0 1 tz ]
[ 0 0 0 1  ]

So, when we apply this matrix to a column vector; we’ll end up with a simple addition of each of the components:

[ 1 0 0 tx ] [ vx ]   [ tx + vx ]
[ 0 1 0 ty ] [ vy ]   [ ty + vy ]
[ 0 0 1 tz ] [ vz ] = [ tz + vz ]
[ 0 0 0 1  ] [ 1  ]   [    1    ]

In python using numpy, this is greatly simplified:

def create_translation(x, y, z):
  return np.matrix([
      [1, 0, 0, x], 
      [0, 1, 0, y], 
      [0, 0, 1, z], 
      [0, 0, 0, 1]
  ])

With this function in hand, we can now start to move our vectors around in space:

# v sits at the origin
v = np.array([0, 0, 0, 1])

# translation matrix to move vectors along
# the x-axis by 1
t = create_translation(1, 0, 0)

# move v
t.dot(v)

With the output of this function:

matrix([[1, 0, 0, 1]])

Scale

We scale points geometry to adjust proportionality of objects. A scale matrix will do just this on any point around the origin 0, 0, 0, 1.

[ sx 0  0  0 ]
[ 0  sy 0  0 ]
[ 0  0  sz 0 ]
[ 0  0  0  1 ]

Applying a matrix of this shape to a column vector, we now get a multiplication effect:

[ sx 0  0  0 ] [ vx ]   [ sx * vx ]
[ 0  sy 0  0 ] [ vy ]   [ sy * vy ]
[ 0  0  sz 0 ] [ vz ] = [ sz * vz ]
[ 0  0  0  1 ] [ 1  ]   [    1    ]

The python for this process is pretty simple, again:

def create_scale(x, y, z):
  return np.matrix([
    [x, 0, 0, 0], 
    [0, y, 0, 0], 
    [0, 0, z, 0], 
    [0, 0, 0, 1]
  ])

Rotation

We’ll treat rotation on each axis separately.

x-axis rotation performs spherical movement between the y and z axis:

[  1   0     0    0  ]
[  0  cos∅ -sin∅  0  ]
[  0  sin∅  cos∅  0  ]
[  0   0     0    1  ]

y-axis rotation performs spherical movement between the x and z axis:

[  cos∅   0   sin∅  0 ]
[   0     1    0    0 ]
[ -sin∅   0   cos∅  0 ]
[   0     0    0    1 ]

z-axis rotation performs spherical movement between the x and y axis:

[  cos∅ -sin∅   0    0 ]
[  sin∅  cos∅   0    0 ]
[   0     0     1    0 ]
[   0     0     0    1 ]

These translate really well into python code, too!

def create_rotate_x(theta):
  ct = math.cos(theta)
  st = math.sin(theta)
  
  return np.matrix([
    [1, 0, 0, 0], 
    [0, ct, -st, 0], 
    [0, st, ct, 0], 
    [0, 0, 0, 1]
  ])

def create_rotate_y(theta):
  ct = math.cos(theta)
  st = math.sin(theta)
  
  return np.matrix([
    [ct, 0, st, 0], 
    [0, 1, 0, 0], 
    [-st, 0, ct, 0], 
    [0, 0, 0, 1]
  ])

def create_rotate_z(theta):
  ct = math.cos(theta)
  st = math.sin(theta)
  
  return np.matrix([
    [ct, -st, 0, 0], 
    [st, ct, 0, 0], 
    [0, 0, 1, 0], 
    [0, 0, 0, 1]
  ])

Armed with all of these functions, we have a basic (local) co-ordinate transform pipeline. We can start to make a little more sense out of these mathematical constructs by binding the results to variables that are named by their side effects.

# the cartesian plane moves positive, to the right
move_right_by_2 = create_translation(2, 0, 0)

# make any point twice the distance away from the origin
make_twice_bigger = create_scale(2, 2, 2)

# π radians is 180° 
turn_the_other_way = create_rotate_x(math.pi)

What is interesting about the matricies that we’ve just created, is that they’re reusable for as many points as we want. We can uniformly transform a group of vectors with the same matrix.

So, if I wanted to not only move right by 2, but also make twice bigger and turn the other way; I could multiply these matricies together to form a new transformation:

do_all_the_things = (turn_the_other_way * make_twice_bigger * move_right_by_2)

Now we can use do_all_the_things to transform our vector objects to perform all of these transformations at once:

>>> do_all_the_things.dot(np.array([0, 0, 1, 1]))
matrix([[  4.00000000e+00,  -2.44929360e-16,  -2.00000000e+00,
           1.00000000e+00]])

We did start, pointing towards the camera 0, 0, 1 and then after moving to the right by 2 and doubling our size, we’re now at 4 on the x-axis. We turn around about the x axis and we’re now facing away from the camera; twice the distance (-2 on the z-axis). Note that the y-axis has some epsilon garbage after our multiplies.

Well, it was a quick tour; but this has been numpy in (a little bit of) action.

Pyramid, Bottle and Tornado

As web application developers, we’re given a vast array of web application development frameworks at our disposal, In today’s post, I’m going to go through three of these; all based on the Python programming language. The frameworks are:

These really are micro-frameworks for this purpose.

Pyramid

Pyramid, or the Pylons Project is a straight-forward application framework where most of the focus is placed on the application’s configuration. This isn’t an ancillary file supplied to the application, but defined in code, in module. From the web site:

Rather than focusing on a single web framework, the Pylons Project will develop a collection of related technologies. The first package from the Pylons Project was the Pyramid web framework. Other packages have been added to the collection over time, including higher-level components and applications. We hope to evolve the project into an ecosystem of well-tested, well-documented components which interoperate easily.

The Pylons project is a greater umbrella for the Pyramid-piece which is the web application framework.

Following is a “Hello, world” application using this framework.

from wsgiref.simple_server import make_server
from pyramid.config import Configurator
from pyramid.response import Response

def hello_world(request):
  return Response('Hello %(name)s!' % request.matchdict)

if __name__ == '__main__':
  config = Configurator()
  config.add_route('hello', '/hello/{name}')
  config.add_view(hello_world, route_name='hello')
  app = config.make_wsgi_app()
  server = make_server('0.0.0.0', 8080, app)
  server.serve_forever()

The Configurator class holding a lot of the application’s runtime, which is where routes and views come together.

Bottle

Bottle is a no-frills framework, with four main responsibilities: routing, templates, utilities and server.

It’s actually quite amazing (from a minimalist’s perspective) exactly how much you can get accomplished in such little code. Here’s the “Hello, world” example from their site:

from bottle import route, run, template

@route('/hello/<name>')
def index(name):
    return template('<b>Hello </b>!', name=name)

run(host='localhost', port=8080)

The simplistic feel to the framework certainly makes it very clear. template providing a direct text template with a model. run performing the job of the server and the @route attribute performing route configuration.

They’re faithful to their words:

Bottle is a fast, simple and lightweight WSGI micro web-framework for Python. It is distributed as a single file module and has no dependencies other than the Python Standard Library.

Tornado

Tornado is a web application framework that has been based around event-driven I/O. It’s going to be better suited to some of the persistent connection use-cases that some applications have (like long-polling or web sockets, etc). The following is from their site:

Tornado is a Python web framework and asynchronous networking library, originally developed at FriendFeed. By using non-blocking network I/O, Tornado can scale to tens of thousands of open connections, making it ideal for long polling, WebSockets, and other applications that require a long-lived connection to each user.

In its own way, Tornado can also be quite minimalist. Here’s their example:

import tornado.ioloop
import tornado.web

class MainHandler(tornado.web.RequestHandler):
  def get(self):
    self.write("Hello, world")

def make_app():
  return tornado.web.Application([
      (r"/", MainHandler),
  ])

if __name__ == "__main__":
  app = make_app()
  app.listen(8888)
  tornado.ioloop.IOLoop.current().start()

Key difference on this particular framework is the involvement of the IOLoop class. This really is event-driven web programming.

Networking with Twisted Python

Network programming is a delicate mix of sending messages, waiting for events and reacting. Twisted is a python library that aims to simplify this process. From their website:

Twisted is an event-driven networking engine written in Python

Pretty straight forward.

Echo Server

The first example (lifted directly from their website) is an Echo Server:

from twisted.internet import protocol, reactor, endpoints

class Echo(protocol.Protocol):
    def dataReceived(self, data):
        self.transport.write(data)

class EchoFactory(protocol.Factory):
    def buildProtocol(self, addr):
        return Echo()

endpoints.serverFromString(reactor, "tcp:1234").listen(EchoFactory())
reactor.run()

The method dataReceived which is provided by the Protocol class is called by the reactor when a network event of interest presents itself to your program.

HTTP

Out of the box, you’re also given some tools to talk web actions. Again, lifted from the twisted website is an example web server:

from twisted.web import server, resource
from twisted.internet import reactor, endpoints

class Counter(resource.Resource):
  isLeaf = True
  numberRequests = 0

  def render_GET(self, request):
    self.numberRequests += 1
    request.setHeader(b"content-type", b"text/plain")
    content = u"I am request #{}\n".format(self.numberRequests)
    return content.encode("ascii")

endpoints.serverFromString(reactor, "tcp:8080").listen(server.Site(Counter()))
reactor.run()

It’s a pretty brute-force way to deal with assembling a web server, but it’ll get the job done. The render_GET method of the Resource derived Counter class will perform all of the work when a GET request is received by the server.

Chat Server

I’ll finish up with some original content here, that is a PubSub example (which twisted website has an example of).

Getting a leg up using the LineReceiver protocol as a base, really simplifies our implementation. This allows us little gems like connectionMade, connectionLost and lineReceived . . all pieces that you’d expect in a chat server:

def connectionMade(self):
  '''When a connection is made, we'll assume that the client wants to implicitly join
     out chat server. They'll gain membership automatically to the conversation'''

  self.factory.clients.add(self)

def connectionLost(self):
  '''When a connection is lost, we'll take the client out of the conversation'''

  self.factory.clients.remove(self)

We use a really crude regular expression with some basic captures to pull apart the instruction sent by the client:

# our very crude, IRC instruction parser
irc_parser = re.compile('/(join|leave|msg|nick) ([A-Za-z0-9#]*)(| .*)')

When receiving a line, we can respond back to the client; or we can broadcast to the portfolio of connections:

def lineReceived(self, line):
  '''When a client sends a line of data to the server, it'll be this function that handles
     the action and re-acts accordingly'''

  matches = irc_parser.match(line)

  if matches == None:
    # send an error back (to this client only)
    self.sendLine('error: line did not conform to chat server requirements!')
  else:
    (act, obj, aux) = matches.groups()

    if act == 'join':
      self.broadcast(self.nick + ' has joined the channel ' + obj)
    elif act == 'leave':
      self.broadcast(self.nick + ' has left the channel ' + obj)
    elif act == 'nick':
      client_ip = u"<{}> ".format(self.transport.getHost()).encode("ascii")
      self.broadcast(client_ip + ' is changing nick to ' + obj)
      self.nick = obj

The only part left out here, is the broadcast method. Which is simply a for-loop:

def broadcast(self, line):
  for client in self.factory.clients:
    client.sendLine(line)

Here’s the full example:

from twisted.internet import reactor, protocol, endpoints
from twisted.protocols import basic

import re

# our very crude, IRC instruction parser
irc_parser = re.compile('/(join|leave|msg|nick) ([A-Za-z0-9#]*)(| .*)')

class ChatProtocol(basic.LineReceiver):
  '''The chat server is responsible for maintaing all client connections along with
     facilitating communication between interested chat clients'''

  def __init__(self, factory):
    self.factory = factory

    self.channels = { }

  def connectionMade(self):
    '''When a connection is made, we'll assume that the client wants to implicitly join
       out chat server. They'll gain membership automatically to the conversation'''

    self.factory.clients.add(self)

  def connectionLost(self):
    '''When a connection is lost, we'll take the client out of the conversation'''

    self.factory.clients.remove(self)

  def lineReceived(self, line):
    '''When a client sends a line of data to the server, it'll be this function that handles
       the action and re-acts accordingly'''

    matches = irc_parser.match(line)

    if matches == None:
      # send an error back (to this client only)
      self.sendLine('error: line did not conform to chat server requirements!')
    else:
      (act, obj, aux) = matches.groups()

      if act == 'join':
        self.broadcast(self.nick + ' has joined the channel ' + obj)
      elif act == 'leave':
        self.broadcast(self.nick + ' has left the channel ' + obj)
      elif act == 'nick':
        client_ip = u"<{}> ".format(self.transport.getHost()).encode("ascii")
        self.broadcast(client_ip + ' is changing nick to ' + obj)
        self.nick = obj

  def broadcast(self, line):
    for client in self.factory.clients:
        client.sendLine(line)

class ChatFactory(protocol.Factory):
  def __init__(self):
      self.clients = set()

  def buildProtocol(self, addr):
      return ChatProtocol(self)

endpoints.serverFromString(reactor, "tcp:1234").listen(ChatFactory())
reactor.run()            

Writing networked servers couldn’t be easier.

Loading dynamic libraries in C

Today’s post is going to be a quick demonstration of the dynamic library loading available through Glibc.

Some really important links that shouldn’t be glossed over if you’re serious about some dynamic library development are:

Simple library

To start, we’re going to write a tiny library. It’ll have one function it it called greet that will send out a string:

char *greeting = "Hello";

char *greet(void) {
  return greeting;
}

We can make libtest.so out of this with the following:

gcc -c -Wall -fPIC greet.c -o greet.o
gcc --shared greet.o -o libtest.so

We now have libtest.so as our shared library, ready to be loaded by our host program.

Host program

The executable that takes care of loading this shared library, engaging the functions within it and executing the code will be called the host in this instance. First up, we’ll use dlopen to load the shared library off of disk:

void *test_lib = dlopen(LIBTEST_SO, RTLD_LAZY);

if (!test_lib) {
  fprintf(stderr, "%s\n", dlerror());
  exit(EXIT_FAILURE);
}

Now that we’ve opened the library up, we’ll use dlsym to bury into the library and extract the greet function:

char* (*greet)(void);

greet = (char * (*)(void)) dlsym(test_lib, "greet");

if ((error = dlerror()) != NULL) {
  fprintf(stderr, "%s\n", error);
  exit(EXIT_FAILURE);
}

We’re referencing the function now. Notice the goofy cast: (char * (*)(void)). Here’s a blurb from the manpage:

/* According to the ISO C standard, casting between function pointers and ‘void *’, as done above, produces undefined results. POSIX.1-2003 and POSIX.1-2008 accepted this state of affairs and proposed the following workaround:

  *(void **) (&cosine) = dlsym(handle, "cos");

This (clumsy) cast conforms with the ISO C standard and will avoid any compiler warnings.

The 2013 Technical Corrigendum to POSIX.1-2008 (a.k.a. POSIX.1-2013) improved matters by requiring that conforming implementations support casting ‘void *’ to a function pointer. Nevertheless, some compilers (e.g., gcc with the ‘-pedantic’ option) may complain about the cast used in this program. */

Now we can call the greeter, and clean up with dlclose!

printf("%s\n", greet());

dlclose(test_lib);
exit(EXIT_SUCCESS);

Because we do the dynamic loading of the library inside of our application, we don’t need to tell the compiler of the library’s existence. The host application will need to know about Glibc’s dl library though:

gcc -Wall host.c -ldl -o host

In closing

This has been a really quick lap around the dl library. The working prototype is crude, but forms the skeletal basis of a plugin-architecture should you be able to establish a strong contract between the pieces of library code and the host!

dblink

There are a few tools at a developers disposal to perform queries that go cross-database. In today’s post, I’ll quickly go over using dblink to establish links between Postgres databases.

Example Usage

First up, we need to make sure that the dblink extension is available to our server. CREATE EXTENSION is what we’ll use to do this:

CREATE EXTENSION dblink;

Prior to being able to query against a remote database, we need to use dblink_connect to establish a link from the local context.

-- create the crumbs link
select  dblink_connect(
    'remotedb',
    'host=127.0.0.1 port=5432 dbname=remotedb user=postgres password=password'
);

The connection string that you supply are fairly straight forward details to connect to a server with given credentials.

Using dblink, you can now invoke a query on the remote server and have the result mixed into your local code.

select  *
from    dblink('remotedb', 'SELECT "ID", "Name" FROM "People"')
as      people("ID" int4, "Name" character varying);

When you’re done with the connection, you use dblink_disconnect.

select dblink_disconnect('dbl-crumbs');  

Async Queries

dblink also gives you the opportunity to perform async queries which is really handy. You kick the query off, do something and then start fetching the results later on in your code.

/* start the query off */
select  *
from    dblink_send_query('remotedb', 'SELECT "ID", "Name" FROM "People"')
as      people;

/* Do some other work here */

/* start drawing the results */
select  *
from    dblink_get_result('remotedb')
as      people("ID" int4, "Name" character varying);

That’s a bit fancy.