Older blog entries for Michael (starting at number 23)

25 Oct 2000 (updated 25 Oct 2000 at 23:39 UTC) »

DES

Been, amoungst other stuff, optimising my DES implemenation today. The key setup time has tripled at the moment (though I have an idea how to get that down), but the number of cycles taken to process a 64 bit block is down to 12% of the original. This was achived by a mixture of static preprocessing, preprocessing the key setup, removing most uint64_t values and using two uint32_t values where possible (my target plaform is the ARM, so 32 bit operations are a Good Thing(tm)), and applying some human optimisation to the bit permutations. So far this has been just using C - I've not needed to use any asm - I've managed to express everything I want so far in C.

Next a little more optimisation of the C version, before I try and apply hardware to some parts of the algorithm (mainly the bit swizling). I have two hardware versions in mind - one a plain partial hardware/software implementation, and one which uses partial evalution to put the key into the round calculations.

Update

Managed to half the key setup time. I've completely removed 64 bit values except as the inputs to the algorithm. By a BOE calculation, it can now process about 0.8Mbytes/sec on a 1GHz XScale/StrongARM, but that's not including cache-misses. Not particularly impressive.

Other

Had to reboot a keyboard today. I think the microcontroller inside had got confused, and the PC it was attached to refused to acknowledge it until I powered off the machine (rebooting it didn't help).

Installed GNAT (the gnu Ada compiler) today - scary. I got flashbacks to when I was being taught Real Time Systems in Ada.

Learned how to use a diablo.

Oh, and I forgot to say congrats to adamd who submitted his PhD dissertation last week. He now seems to have a perpetual smile on his face :-)

D35

Still got a broken DES implementation. Tried various kludges to see if I could get it to work with the test vectors I'd found, but to no avail. But it has the correct timing properties, which is what I'm interested in, so for now I'll just go with what I've got (pressing deadlines...).

Music

iain: Placebo dull? I guess Brian Malco's voice is something you like or hate - forages I couldn't stand Brett Anderson's voice, but eventually came round. I don't think Placebo qualify for boring though. When I say them live the other week the momentum of the show was really good. It dipped a bit with too many slow songs strung together, but came out tops again finishing with Pure Morning, Taste in Me, and Nancy Boy.

On a side note, Lettucehead will hopefully be playing on Saturday - nothing spectacular, just an open stage affair, but it'll be good to play again.

WebCam

Hmmm. Fixed itself - this, of course, just means it will go wrong again. Went through our second power-supply unit too - I think being continuously plugged in to power the camera overheats the wee things. Now our second camera is without power.

23 Oct 2000 (updated 23 Oct 2000 at 22:25 UTC) »

DES

Yeah, yeah - DES is old news, but I wanted to start simple, so DES it is. I've written a naive DES implementation, optimisation comes next, then the software/hardware hybrid. Then something more whizzy like Rijndael.

But... there's always a but isn't there? I have got my DES implementation to a stage where:

D(E(x)) = x

However, when I run the test cases I've found on the web, they don't show the correct ciphertext for a given plaintext/key combination. I've got a feeling that it lies in the bit ordering - all the documentation starts with the LSB on the left - but they continue this notation down to the hex values - to decimal five would be written in hex as A - because the binary is 1010. I'm confused. I can't really find documentation to back up this suspition, but the blank key with the parity bits every eigth bit is written 0x0101010101010101, rather than 0x8080808080808080 as I'd expect.

I'll try munging some things tomorrow to try and fix it, but as I'm doing it as an academic exercise - i.e. I need the general alg, and something which will do D(E(x)) = x, but I don't need to interface with other DES software, I think I'll leave it if there is no obvious solution. Perhaps I can call it D35 :-)

Music

Generally I try and keep it just coding up here, but seeing as Kid A generated so much traffic on here, I thought I'd add a couple of recommendations. First is Black Market Music by Placebo and the second is Showbiz by Muse. Saw Placebo live last weekend in Glasgow. Really good show. The album is more pop than there last album (which I think is the best they've done). Muse are new to me, but I keep seeing them live on tele and they're really good.

Misc

The webcam is broken, but I've just not had time to look into the why yet - been too busy.

18 Oct 2000 (updated 18 Oct 2000 at 23:35 UTC) »

SysAdmin

Dipped my fingers into the messy world of ad hoc distributed sys admin today. I got using my NetBSD enabled shark so much (see previous episodes for details :-) that I wanted to mount my home space there. Being a largish dept we have a central place for such things. However, to access this a machine needs to be "trusted" by the dept. The first stage of reaching this was teaching master about both NetBSD and sharks.

Master is what we use as a centralised point of configuration for (almost) all our unix boxen (it originated from cl.cam.ac.uk, but came up Glasgow via a couple of people we hired from there). Master is responsible for distributing standard files (such as those in /etc), tools (our version of arch), setting up the automount maps etc., and it does this for a hetrogenous collection of machine types and Unix types. Anyway, breaking this would not make me popular.

Thus I spent a while understanding how a NetBSD machine is setup (who stole tcpd? :-) on both ix86 and the sharks. I then compiled up the correct version of essential binaries for both platforms (e.g. rdist), secured the boxes with hosts.[allow|deny] and inetd, plus all the other magic the department requires, and distilled it all into master, along with the documentation of what I'd done.

And it looks like it works. The proof will be when I come in tomorrow morning and the nightly dist has happened with no errors. Now adding a new NetBSD box to the dept should be real easy.

Now I can go back to real work...

Update

All seemed to go well with master - phew!

Went juggling with Greg -- first time in an age I've been. Good fun.

Misc

Lazy weekend. Spent yesterday getting new trainers and looking for knee pads, but failing to find any. Today I regretted not getting knee pads, as I'm buised all over after today's snowboarding lesson. Ouch. Now I'm off to grab a sandwich and go see Billy Elliot with my better half. Tired (though probably not as tired as adamd is at the moment...).

Upgraded my network card to 100 Mbit. Had to tell Kudzu to "F*ck off, I know better than ye!" The driver for the card that RedHat uses by default hangs our network - it drives the line constantly, something that is not good on an ethernet network :-) But by using the de4x5 driver rather than the default tulip one, and a bit of documentation reading, I was able to get it up and working.

LaTeX

Started work on the site. The html is at home, but I'll try and put it up on G141 at some point tomorrow. It's bare - submissions will be needed :-)

SWARM

Bah. Need to write documentation before putting it on the web. :-( Give me a day or so...

SWARM

Phew. Got my first coprocessor working in SWARM. I've started to implement an extended system coprocessor (in the ARM7TDMI system information is stored in an on-chip coprocessor). Now my applications can access a cycle counter by doing:

mrc 15, 0, r0, c11, c0, 0

This leaves the result in register 0. Question for the community now: I hacked up a C macro to let test applications in C directly access this like so:

#define rpcc() ({ uint32_t __t; __asm__ volatile\
 ("mrc 15, 0, %0, c11, c0, 0" : "=r" (__t) :);\
__t; })

Now, I found the __asm__ format by lots of looking at the NetBSD and Nemesis source code, same for the mrc operand formating. Can anyone suggest a source of documentation for either of these? I fed a few obvious searches into google, but to no avail.

Anyway, tomorrow I can profile that bit of ARM core I've had sitting about. I'll try and feed the changes up to freshmeat too.

hacking

Fixed some stuff in SWARM, expanded libc. It's quite cool - I've got enough of libc implemented that I can simply compile my test apps for SWARM these days without thinking about it. Of course, I look forward to the day's when I don't have to write bits of POSIX anymore (I worked on the POSIX/sockets later for Nemesis). Any hows, the coprocessor stuff is nearly there. If anyone knows stuff about instruction timings on the ARM, and knows why MCR is one cycle longer the MRC (see my posting on comp.sys.arm today) then let me know please!

Kid A

iain: Radiohead to me are tracks like Paranoid Android, The Bends, Planet Telex, etc. I prefer my Radiohead served live where it has much more spirit to it. The National Anthem live is quite gutsy. But, I really liked Climbing Up The Walls on OK Computer, and I think Kid A picks up on that kind of track. As much as I miss the more rock tracks, I can take Kid A in parallel. It's just another side of the coin. I can see that we're going to have to agree to disagree over this one :-)

LaTeX

Okay, I'll set up the LaTeX site over the weekend. I'll post here when it's up. I've just far too much to do during the week to fit it in. I think I'll make it a place for both styles and for cunning macros too. And anything else LaTeXy.

Work

Back in the dept today - decided that the work I was going to do at Xilinx was best started from here. All the tool flow that I need is here, and it would be more effort to run it there. I'll probably go back in a couple of weeks when I have some circuits that need to be done.

Toys

Decided I needed to finally get a LART, so I pop over to thinkgeek (where else?) to grab that green koosh gun they were touting on their banner adds for a while, but it's gone :-( Looks like I'll have to settle for a Net Splitfire instead. Will come in handy when I have to do some teaching next term ;-)

Kid A

Kid A, the latest Radiohead album is really good (I saw a mixed review earlier here). Really good sound, more mellow than previous outings. At first I really missed the usual gutsy Radiohead tracks (Airbag, Electioneering, Paranoid Android, My Iron Lung, Just, yada yada yada) but I got over it. Optismistic and The National Anthem are my faves (though I'm natoriously contrary about these things - it'll probably change in a day or so :-). If you'd not heard OK Computer then you probably wouldn't realise that this was the same band that brought you The Bends and Pablo Honey.

Latex

Ha, no takers on my LaTeX site then? I might knock it up anyway and see if the saying "build it and they will come" is true or not. Watch this space.

ErikLevy: More on 64 bit systems. Besides Nemesis, You might want to look at Opal done at U-dub, they have a paper on just what I hinted at yesterday: "Opal: A Single Address Space System for 64-Bit Architectures". In relation, I was chatting with a friend about this and he said that the original Alpha chips, despite using 64 bit addresses internally, only had 43 (or there abouts) address pins, as at the time they didn't think people were likely to use more than that outside the processor.

Community suggestion: I'm a big believer in seperating style and content - thus do my documenting in LaTeX. However an often cited complaint is that unless you really know LaTeX well, defining your own document styles is hard, so you're stuck with the default LaTeX styles, which can wear a bit thin after a while and makes it hard to create a doc that stands out from the crowd. My suggestion is that we need a themes.org for LaTeX, somewhere where people can upload and download LaTex style files. What do people think? We could even shove the arhive on g141.com - though I've not got the time to do anything as glitzy as themes.org :-)

ErikLevy: "A 32 bit based computer (hardware, kernel, software) has 4 GB's memory possible and a 64 bit one has 18 billion GBs. How many companies has needs of more than 4 gigs? "

AltaVista servers ;-) I'm sure that each one of the AltaVista back ends has (or at least had) 4 gig in them. It can also be useful to have a logical 64 bit address space - some OSs (for example Nemesis) use a single address space (which makes sharing of libraries and data easier than it is in a multiple virtual address space OS). Thus, though you're not physically ever going to use it, you logically might reach beyond 4 gig. Of course these are only virtual addresses that you'd want to translate to physical addresses (though Nemesis didn't implement this - we were interested in more the scheduling side of things).

Misc:

I start my internship at Xilinx tomorrow (at Edinburgh, Scotland). I'll be writing some bits of hardware for them which I can also use in my PhD, so we both get something out of it. I'm looking forward to the change of pace (though not the commute each day from Glasgow - it's two hours door to door, but it's only for a month or so).

Installed RedHat 6.2 on the new postgrad machine in our office and am in the process of mastering it (master is our nightly automated patch/update system - once a machine is mastered it gets updates automatically once they given to master). It's one of these things that I do so infreqently that despite having done loads of them I need to relearn it each time.

Snowboarding again - it rocks :-) I'm getting quite confident now - I can steer across the slope on both toe and heal edges, so I'm less of a danger to society :-)

14 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!