Passcard

Secure passwords are hard to come up with and remember. Things like Key Ring for Palm are good, but it means you have to have your Palm Pilot on you constantly. Even worse is something tied to your desktop/laptop. Since the only thing I reliably have on me most all times is my wallet, a paper based solution is best.

I got the idea for this from ./. You have a matrix with the alphabet and random letters, then choose an easy to remember word for each site.

a sample passcard

So for GMail my password might be 4pfMnrMIZb. For extra security, in case someone finds the card, I can always prepend with something extra not on the card (maybe always put a ! first or something).

Latex/awk sources to make a business card sized PDF of random letters available here. Laminated it should make a fairly decent increase in online personal security with minimal effort.

Sun's Niagara

Discussions with Matt Chapman lead me to thinking more about processors. I read up on Sun's Niagara (Ars Technica or IEEE Micro vol 25, issue 2). Notes which may serve as a short introduction below.

In essence code generally shows low instruction parallelism. This means the processor finds it hard to find things it can do in parallel because instructions more often than not end up depending on each other. However, server workloads show high thread level parallelism -- we've all written multithreaded applications because we realised we could do some parts of a program in parallel.

Rather than look for ILP, Niagara goes after TLP. It does this by grouping four threads into a thread group, which then execute on a "SPARC pipeline". With 8 SPARC pipelines you have 8*4 = 32 threads in flight. It's not far off to think of each SPARC pipeline like a hyper threaded Pentium processor; each of the threads has it's own registers but shares the processor (pipeline) back ends. Each pipeline is 6 stages (fetch, thread select, decode, execute, memory, write-back) with the first two stages replicated for each thread. ALU instructions and shift instructions have single cycle latency, whilst mulitply and divide are multiple cycle and cause a thread switch.

Under ideal circumstances where all threads are ready to go, the on chip thread scheduler will attempt to run each waiting thread in a round-robin fashion (i.e. last to execute is the next to run).

Pipelines have small 8K L1 cache which implements random replacement (rather than more common LRU type schemes, though the paper quotes ~10% miss rates). The pipelines (all of them) share an L2 cache of only 3MB, compare this to about 27Mb of cache for a Montecito Itanium (dual thread, dual core). The theory is that cache miss latency is hidden since when one thread misses and has to go back to memory you switch into another thread which is ready to go. For the same reason you can ditch branch prediction logic too; you just switch a new thread in while you take the branch.

There are a lot of registers to keep this all happening; there is a register window scheme where the current 8 registers are kept in "fast" registers whilst registers out of the current window frame are moved into slower SRAM registers. There is a 1-2 cycle latency to move between them.

The processor predicts loads as cache hits, and thus will execute speculatively other instructions depending on this load; though speculative instructions have a lower thread priority so the thread scheduler will do "real" work first. It doesn't do any fancy instruction re-ordering on the fly.

Cache coherency traffic over busses is eliminated by having all this running on a single core. A single package also keeps power down; all this requires a quoted 60W; Montecito quotes ~100W.

This has very little in common with a Pentium. Pentium breaks down instructions into micro-ops which the hardware then tries to extract as much ILP out of as possible. Hyperthreading has not shown great wins on the Pentium. Itanium moves the task of finding ILP to the compiler, and then provides a pipeline optimised for running bundles of instructions together. The Itanium has a lot more cache; Niagara trades this off for threads. Something like POWER is somewhere in the middle of all that.

So, is more threads or more cache better? Can workloads keep a processor doing 32 separate things to take advantage of all these threads? I would suggest that a both a desktop and technical workload will not; a busy webserver running JSP maybe. Time will tell.

On optimisation

From comp.lang.c

Question: How can I optimise code better than the compiler?
Answer: If you ask, then you can't.

Making the Philips DVDR77 Region Free

The Philips DVDR77 is a DVD+RW recorder with an inbuilt PCMICA media reader, which due to apparent obsolence can be found quite cheap. To make it region free the easiest way is to use a Palm Pilot

  1. Download OmniRemote (the download version is a 15 day free trial).
  2. You need to send code RC6 (Codeset 4, Key 235) to the DVD. OmniPhilips955.pdb is an OmniRemote database with a big button to send this code.
  3. From the system menu of the DVD, select the 5th item and change the remote control type to DVD Player.
  4. Use OmniRemote to send the code to the DVD. It should now be showing dashes (- - - - - -). I had to press the button a few times before it seemed to register.
  5. videohelp.com has the procedure to enter the region free code from here. Enter 121212005255 and then PLAY.
  6. Reset the DVD remote type.

There is also a firmware upgrade (direct link).

Getting a decent font with Gnome terminal

I might be a bit slow, but I finally figured out how to get a decent font (i.e. not anti-aliased) for gnome-terminal on Debian.

  1. Ensure xfonts-100dpi is installed
  2. dpkg-reconfigure fontconfig and answer yes to the question about bitmapped fonts.
  3. You will now have under Desktop->Preferences->Fonts the ability to select the Fixed font.
  4. Restart all gnome-terminals. The font may look a little weird before you do that.
  5. Enjoy tabs without the fuzziness!

Update: it appears I'm not the only one who doesn't like the fuzzy fonts in my terminal.

Davyd Madeley suggested that rather than enabling bitmapped fonts you can just enable a single font with fontconfig. He gives this example (place it in /etc/fonts/conf.d).

He suggested

There was an issue of it choosing extra wide fonts sometimes. You can fix this by copying the version of Fixed you want (eg. 7x13.pcf.gz) into your ~/.fonts directory.

James Ballantine suggested copying the font as well, although for some reason his Firefox started to choose bitmapped fonts after following the above steps.

I can't really understand why, as it appears that bitmapped fonts are enabled by default on Debian; at least in my fontconfig package we have in the post-install script

case "$enable_bitmaps" in
"true")
#
# Bitmap fonts will be enabled by default, so there's no need
# to use this configuration file.  However, the file remains useful if
# you want to force bitmaps to be considered even when some application
# disables them.
#
#       ln -s $CONFDIR/$yes_bitmaps $CONFDIR/$bitmaps_prio$yes_bitmaps
        ;;
*)
        ln -s $CONFDIR/$no_bitmaps $CONFDIR/$bitmaps_prio$no_bitmaps
        ;;
esac

So the dpkg question is at least badly worded, but I haven't yet decided if this is a bug. Probably the only thing I did was install the xfonts-100dpi package which gave me the bitmapped fonts.

Any other feedback is appreciated.

Even numbers

Is

int even(int n)
{
        return (n & 1);
}

a valid way of determining the evenness of a number? For unsigned integers, yes. For signed positive integers also yes. However, C99 6.2.6.2-2 states

For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. [...] If the sign bit is one, the value shall be modified in one of the following ways

  • the corresponding value with the sign bit 0 is negated (sign and magnitude);
  • the sign bit has the value -(2:sup:N)(two's complement);
  • the sign bit has the value -(2:sup:N - 1)(one's complement).

In other words, there are three possible representations of a signed integer in C, and one of them (one's complement) has a negative representation that fails the above test. However, I don't think there are actually any one's complement machines, so you're pretty safe.

However, Murphy's law dictates that eventually your code will run on some bizarre device that uses one's complement. Thus the best bet is to use a remainder (%) and let the compiler figure it out for you. Have a look at what the compiler gets up to for the most straight forward case:

$ cat test.c
int function(int i)
{
        return (i % 2);
}

$ gcc -O2 -S test.c
$ cat test.s
        .file   "test.c"
        .text
        .p2align 4,,15
.globl function
        .type   function, @function
function:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        andl    $-2147483647, %eax
        js      .L5
        popl    %ebp
        ret
        .p2align 4,,15
.L5:
        decl    %eax
        orl     $-2, %eax
        incl    %eax
        popl    %ebp
        ret
        .size   function, .-function
        .ident  "GCC: (GNU) 4.0.2 20050821 (prerelease) (Debian 4.0.1-6)"
        .section        .note.GNU-stack,"",@progbits

It's a bit tricky because that remainder needs to account for negative values. So $-2147483657 == -0x7FFFFFFF, which in two's complement is binary 1000 0000 0000 0000 0000 0000 0000 0001. So the andl checks the last bit just like we did before, however having the top bit set means that if the top bit is set in the other operand (i.e. the sign bit, indicating it is a negative number), the sign flag will be set and the js (jump on sign bit) will be triggered (that next bit at .L5 is a consequence of C99 6.5.5 6 where we have the relation (a/b)*b + a%b == a).

We can reduce the even function down to

$ cat test.c
int function(int i)
{
        return ((unsigned int)i % 2);
}

$ gcc -O2 -S test.c

$ cat test.s
        .file   "test.c"
        .text
        .p2align 4,,15
.globl function
        .type   function, @function
function:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        andl    $1, %eax
        popl    %ebp
        ret
        .size   function, .-function
        .ident  "GCC: (GNU) 4.0.2 20050821 (prerelease) (Debian 4.0.1-6)"
        .section        .note.GNU-stack,"",@progbits

Which is the same as the original on this two's complement x86. In this trivial case the cast to unsigned could have been used with the original & 1 check and would have been OK, but my feeling is this the % is a little more clear (and if you need to worry about negative values your hand is forced).

I think the moral is to be worried whenever you pull out a bitwise operator and try to pass it off the work to the compiler (with a quick sanity check).

Directory stacks in bash

After looking at some shell scripts today it seems the very handy pushd and popd aren't used enough in the wild.

If you're just popping into a new directory for a moment to do something, then want to return to the directory you came from, use pushd newdir; it will push the current directory to the top of the directory stack (actually the DIRSTACK environment variable) and cd you there.

When you're done, use popd to go back to where you came from. Obviously you can keep pushing onto the stack and nest your directory changes deeper. Never again shall you need to manually remember $PWD!

ianw@lime:~$ pushd /tmp
/tmp ~
ianw@lime:/tmp$ echo do something in /tmp
do something in /tmp
ianw@lime:/tmp$ popd
~
ianw@lime:~$

Mighty Mouse with udev and horizontal scrolling on Debian

This may not be the best way to do things, but this was the combination I seemed to need to get an Apple Mighty Mouse working with an IA64 desktop and udev, including horizontal scrolling.

I found that the current event input drivers shipped with the Debian X.org release weren't quite up to the job for me; I ended up with something about not being able to connect to the brain. Upstream has a better version in CVS, but I had all sorts of problems with CVS X.org for IA64.

Firstly the udev rules. If you add to /etc/udev/rules.d/mightymouse.rules

KERNEL=="event*", SYSFS{manufacturer}="Mitsumi Electric", SYSFS{product}="Apple Optical USB Mouse", NAME="input/mightymouse", MODE="0644"

Your mouse should appear on /dev/input/mightymouse when you plug it in.

Next grab the X.org source with apt-get source xserver-xorg. Then in the exapanded directory go to debian/patches/general and do

wget http://bugs.debian.org/cgi-bin/bugreport.cgi/052_evdev.diff?bug=325807;msg=5;att=1

to get a backport (with an extra little bit I put in for the Mighty Mouse horizontal scroll). Then edit debian/patches/series to remove the 053_lnx_evdev.diff, 054_lnx_evdev_mouse.diff and 055_lnx_evdev_keyboard.diff patches from the list, and add 052_evdev.diff.

I'm a bit unclear as to how the manifest system works; I modified MAINIFEST.ia64.in to have the new usr/X11R6/lib/modules/input/evdev_drv.o file, but that didn't seem to get it included in the package. If anyone can tell me how it is supposed to work that would be great, and I'll update this.

So build with fakeroot debian/rules binary or similar, and install the new xserver-xorg package. I then had to hand copy from debian/tmp/usr/X11R6/lib/modules/input/evdev_drv.o to /usr/X11R6/lib/modules/input/evdev_drv.o because the manifest thing didn't work.

Anyway, finally modify your mouse section to look like

Section "InputDevice"
        Identifier      "Configured Mouse"
        Driver          "evdev"
        Option          "CorePointer"
        Option          "Device"                "/dev/input/mightymouse"
EndSection

and for me everything "just works", with the exception of Firefox which binds the horizontal scroll to the history buttons, which with such a small wheel makes surfing very hard. See this hint on how to fix it.