moar articles
Tweet
Follow @nicferrier

Bignums with EmacsLisp

This blog post is about how to use Emacs calc from EmacsLisp to get bignum support. It's also about hacking MongoDb in EmacsLisp.

Marmalade and Mongo

I've been working to convert marmalade to Elnode. Marmalade is based on a MongoDb database so the task is mainly ensuring that we get Mongo working from EmacsLisp properly.

There was an existing MongoDb adapter for EmacsLisp and it's pretty good. I noticed there were some missing things though and so I've been adding them to my fork.

Just recently I found that datetime's were not parsed by the existing module and so I had to add them.

The BSON specification specifies the MongoDb wire format so I started by doing some queries in the mongo shell tool and getting a view of what MongoDb was sending:

> db.fs.files.findOne()
{
	"_id" : ObjectId("4cfee12f74e6bf6256000004"),
	"filename" : "haml-mode.el/3.0.14",
	"contentType" : "text/plain",
	"length" : 28273,
	"chunkSize" : 262144,
	"uploadDate" : ISODate("2010-12-08T01:36:47.168Z"),
	"aliases" : null,
	"metadata" : null,
	"md5" : null
}

Here's a partial packet trace from that:

  6e 00 00 10 63 68 75 6e    6b 53 69 7a 65 00 00 00    n...chunkSize...
  04 00 09 75 70 6c 6f 61    64 44 61 74 65 00 40 a0    ...uploadDate.@.
  9f c3 2c 01 00 00 0a 61    6c 69 61 73 65 73 00 0a    ..,....aliases..
  6d 65 74 61 64 61 74 61    00 0a 6d 64 35 00 00       metadata..md5..

We can see the uploadDate field clearly thanks to BSON's neat use of plain ascii names. Following the BSON specification we can see that a datetime is a byte 0x09 followed by the field name (0 terminated) followed by a 64 bit integer representing the time since epoch in milliseconds.

That means the following are the bytes that represent the time:

40 A0 9F C3 2C 01 00 00 

Someone helpful on #emacs pointed out to me that network order is always low byte first, so the actual ordered bytes for the int are:

00 00 01 2C C3 9F A0 40

EmacsLisp and large ints

I was worried at first that EmacsLisp did not have large integers. EmacsLisp ints are only 29 bits wide (because the top 3 bits are used to signify things like whether the object is a function or an object, or is negative).

But then some other clever person on #emacs (are you seeing the pattern yet?) pointed out to me that EmacsLisp does have bignums. They are provided by the incredible calc package.

I found it difficult to find out how to use calc but I got there in the end:

(calc-eval
 "rsh(and(idiv($,1000),16#ffff0000),16)"
 'rawnum
 "16#0012CC39FA040")

calc has it's own functional language, it's all accessible directly from EmacsLisp as functions but it's much simpler to just use calc-eval with a string expression.

EmacsLisp and datetimes

EmacsLisp time values are lists of 2 or 3 integers, the hi-integer and the lo-integer of the seconds since epoch and then an integer representing the miliseconds.

The piece of code above produces just the hi-byte, let's break down the function:

This isn't perfect but it's the implementation I'm going with for now because it makes enough sense. I'm not handling the remaining miliseconds at all right now but when someone needs that granularity (maybe me) they'll add it.

I have added some test cases so the code should be easy enough to extend:

(ert-deftest bson-datetime-int64-to-time ()
  "Test the bson datetime conversion."
  (let ((december-10-2010
         ;; I know this is the the mongo rep for this time because
         ;; I've pulled it from a packet dump
         (list #x40 #xa0 #x9f #xc3 #x2c #x01 #x00 #x00)))
    (should
     (equal
      "12/08/10"
      (format-time-string
       "%D"
       (bson-datetime-int64-to-time
        (reverse december-10-2010)))))))

Emacs shows it's mettle

Once more EmacsLisp shows what a fantastic programming language it is. It's such a stable platform and practically everything you can think of has been implemented, and implemented pretty well. S'great.

If you want to help with the Elnode version of Marmalade please come check out the project on Github.