November 2005 Archives

This can be useful for extracting the lowest numbered element of a bit set. Given a 2's complement binary integer value x, (x&-x) is the least significant 1 bit. The reason this works is that it is equivalent to (x & ((~x) + 1)); any trailing zero bits in x become ones in ~x, adding 1 to that carries into the following bit, and AND with x yields only the flipped bit... the original position of the least significant 1 bit.

Alternatively, since (x&(x-1)) is actually x stripped of its least significant 1 bit, the least significant 1 bit is also (x^(x&(x-1))).

A branchless, lookup-free, alternative to code like if (a<b) x=c; else x=d; is ((((a-b) >> (WORDBITS-1)) & (c^d)) ^ d). This code assumes that the shift is signed, which, of course, C does not promise.

Given 2's complement integer values x and y, the minimum can be computed without any branches as x+(((y-x)>>(WORDBITS-1))&(y-x)). Logically, this works because the shift by (WORDBITS-1) replicates the sign bit to create a mask -- be aware, however, that the C language does not require that shifts are signed even if their operands are signed, so there is a potential portability problem. Additionally, one might think that a shift by any number greater than or equal to WORDBITS would have the same effect, but many instruction sets have shifts that behave strangely when such shift distances are specified.

Of course, maximum can be computed using the same trick: x-(((x-y)>>(WORDBITS-1))&(x-y)).

Normally, a dual-linked circular list would contain both previous and next pointer fields and the current position in the list would be identified by a single pointer. By using two current pointers, one to the node in question and the other to the one just before/after it, it becomes possible to store only a single pointer value in each node. The value stored in each node is the XOR of the next and previous pointers that normally would have been stored in each node. Decoding is obvious.

Unfortunately, using this trick in C is awkward because the XOR operation is not defined for pointers.

I just had the experience of watching 'The Skeleton Key', a bit of a scary one. I don't want to spoil the movie for anyone, but once you've seen it, and if you're familiar with the tales of H.P. Lovecraft, then you should know what I mean when I say almost complete rip-off (cough - Thing On The Doorstep - cough). That said, the movie is quite well done, and I've got shivers following it.
Now I'm watching 'Old Boy'. Fun for all the family.

I was recently reintroduced to the mini-movie 'Truth In Advertising', which is really funny and reminds me that the current batch of Rabo Direct ads are based on it. I just didn't make the connection until someone reminded me of it.

Quite a few people died this week, not the least of which was Arthur (Artie) MacGrath, George Best and Pat Morita.

I was in London last weekend, and I went shopping. I got to a store that sold movies. Interestingly enough, they only sold DVDs, which only goes to show how technology progresses - even HMV sells VHS tapes still.
Having purchased a DVD from them I was given an option to purchase a DVD at a really low price. The only two that stuck in my head were 'The Punisher' and 'Chitty Chitty Bang Bang'. I had the unenviable benefit of seeing 'The Punisher' once before on Sky Movies. All I can say is that it reminded me of the game 'Far Cry', rather than the actual character of 'The Punisher', as portrayed in the recent Garth Ennis punisher comic.
I chose 'Chitty Chitty Bang Bang'. Can you blame me? At the moment I'm enjoying it on the laptop as I type this entry.
If anyone cares, I'm using DVDidle Pro to watch the movie. It saves battery on my laptop, as well as allowing me to watch non region 2 DVDs, which is kind of important.

Just a general wave out to all those folks celebrating thanksgiving. I'm off to dinner myself later this evening.

I never really read the documentation for the built in quick sort function for Palm OS. The only thing I ever looked at was how to swallow the extra parameter for the function. If I had read the documentation properly I would have noticed that it possesses several very handy optimizations that come (mostly) for free. The first is that it automatically uses an insertion sort if the number of records are 'low'. This is very handy, as it means you don't need to decided to use one algorithm over the other. It also swaps to an insertion sort if at a point in the sorting it discovers that the stack is about to be consumed completely, which means no mysterious application crashes due to the recursive nature of the quick sort.
The only real problem with it is that it, like all other versions of quicksort is that it's unstable. If two items have the same key then they may appear on the output in a different order than they were input. Not a big pain really.

a minor addendum to the previous post, perhaps we need to work on Non Uniform Processor Access :)

Yawn, an article on zdnet news tells us that hyperthreading isn't all that for overloaded servers. All I have to say is duh! that's not what it's intended for. Mind you the benchmark was:

Ocks then detailed testing which showed this behaviour where a system thread — in this case one cleaning out blocks of disk cache memory — is running at the same time as worker threads. "With Intel HT technology, logical processors share L1 & L2 caches. As you would guess [this] behaviour can potentially trash L1 & L2 caches," he said.

It looks like all this information came from a blog posting from a SQL server bod in Microsoft. Hyperthreading was never intended to be a replacement for multiple processors. It is evident from the examples cited that the systems in question were not designed with a two-tier processor model in mind, it treats both processors as if they were actual separate processors, and as such makes utterly bone-headed decisions in scheduling that cause massive performance degredation.
That and the fact that there is a thread that churns through vast amounts of memory deciding to store certain database pages out to disk. Ouch! That sounds a tad slow and broken.
Considering the blog entry and the two comments at the end, I'd have to say that yes, indeed, treating a multi-threaded processor like multiple processors is a bad thing to do.

Go placidly amid the noise and the haste,
and remember what peace there may be in silence.

As far as possible, without surrender,
be on good terms with all persons.
Speak your truth quietly and clearly;
and listen to others,
even to the dull and the ignorant;
they too have their story.
Avoid loud and aggressive persons;
they are vexatious to the spirit.

If you compare yourself with others,
you may become vain or bitter,
for always there will be greater and lesser persons than yourself.
Enjoy your achievements as well as your plans.
Keep interested in your own career, however humble;
it is a real possession in the changing fortunes of time.

Exercise caution in your business affairs,
for the world is full of trickery.
But let this not blind you to what virtue there is;
many persons strive for high ideals,
and everywhere life is full of heroism.
Be yourself. Especially do not feign affection.
Neither be cynical about love,
for in the face of all aridity and disenchantment,
it is as perennial as the grass.

Take kindly the counsel of the years,
gracefully surrendering the things of youth.
Nurture strength of spirit to shield you in sudden misfortune.
But do not distress yourself with dark imaginings.
Many fears are born of fatigue and loneliness.

Beyond a wholesome discipline,
be gentle with yourself.
You are a child of the universe
no less than the trees and the stars;
you have a right to be here.
And whether or not it is clear to you,
no doubt the universe is unfolding as it should.

Therefore be at peace with God,
whatever you conceive Him to be.
And whatever your labors and aspirations,
in the noisy confusion of life,
keep peace in your soul.

With all its sham, drudgery, and broken dreams,
it is still a beautiful world.
Be cheerful. Strive to be happy.

You've probably never heard of it before. It's a japanese service called a daiko. What they do is drive you home in a taxi while the substitute taxi driver takes your car home. This means that you have the car in the morning. Kind of like the beer scooter service that was on offer about 2 years ago, but slightly different. double taxi fare would probably be the price tag, but to have the car in the morning (more like afternoon) priceless.

I just want to wait until after Christmas before making any decisions. Of course by that time the Intel dual core laptops will be just around the corner. Rockdirect have been selling dual core laptops for a while. I need to see some reviews about them. Fun for all the family.

I decided I needed some more music today so I went out and bought the Sigur Rós album Takk... and the Tori Amos album The Beekeeper. The Sigur Rós album was purchased because I heard the track 'Glósóli', Tori Amos, quite simply because I have no choice in the matter.
This coming weekend I'm in London. A bit of interviewing and a few drinks with the big sister (followed by the usual life advice).
I wanted to browse the iTunes library XML file. The problem is that Dreamweaver crashes before it loads the file; consuming > 600Mb before falling over. GoLive has churned up about 1.5gb of VMEM usage and is still scanning the document - after about 30 minutes. I haven't the patience to see what the microsoft development environmnent does, but as you can guess, none of them are optimized towards large file editing (about 30mb doc).

Fintan, this one is for you... Everything sounds like Coldplay Now. By a band called Mitch Benn and the Distractions.

What's in a file? If you're to believe Windows, a .doc file is a Word Document, a .xls is a spreadsheet, a .jpg is a jpeg file. The reality is in the business you will encounter a bunch of anonymous files. If you'fe fscked a file system or ran chkdsk /f you can end up with a bunch of unlabelled or labelled badly files. Identifying them is a bit tricky. Some people don't care, they just wipe the recovered files, but if you care, probably the first thing you want to do is figure out what file type they are.
For Unix and Linux we have the file command. This command determines what a file is based on the content of the file. How it does this is based on the contents of the /usr/share/file/magic file, which describes in simple means how we identify the file. It's not 100% accurate, and regularly makes a pigs ear out of identifying text files properly (curses and your free format), but it works most of the time for images, programs and most of your annoying microsoft files.
Convenience aside, most of the work on the file command is actually performed by the libmagic library. You, as an application developer can take advantage of this library to provide useful information about a file to the consumer.
Apple Macs (and PalmOS devices) have it easy. Each file carries along with it identifying marks of it's creator application and file type. This information is stored in the resource fork of the file, which for Macs can mean problems when transporting it from platform to platform. Self identification goes a long way though. As creator codes are registered with Apple, it means you generally avoid treading on other applications and co-opting their file types, as happens on windows all the time.

Here I am with a shiny new Motorola phone which I find really really shiny and nice, but as you may have guessed from the previous blog entry, I'm not happy with the software. I must hearken back to the past when we had a separate Sony and Ericsson phone company. Sony manufactured really pretty phones, with good user interfaces, but the hardware behind the phone itself sucked. Ericsson created technically good phones, but their software and look sucked. When they came together it has been good for the both of them. The phones look good, they have good software and they make good calls (for the most part, don't buy the low end phone models). With Motorola they've always had technically good stuff, it's worked well, but their software has always made me want to hurl. My first phone was an old Timeport. It had an IR port, Bluetooth didn't exist at that time. I thought that the phone software was good. Oh foolish, foolish me. I went back to have a look at it again recently. What a piece of shite. The menu system is incomprehensible and performing the simplest of tasks on the phone is a nightmare. Fast forward to today. The menu system has improved significantly, but they've still got things wrong in the most critical of ways, the extra click here, the missing option there. The fact that practically all the configuration in the phone is accessible through the initial setup screen. I mean really folks, the purpose of an initial setup screen is to get enough information to use the phone - like a wizard. Ask the person if they want to set the date/time or use auto-update (missing on the Vodafone branded ones; I think it's because they can't actually get the network clock correct - lazy buggers!), then off they go with their new phone.

How do I configure Bluetooth? Menu -> Connectivity -> Bluetooth Link (only option, I know there's a possibility of truesync and IR, but if there's only one then take the fucker and don't ask me) -> Setup

How do I compose a text message? Menu -> Messages -> New Message -> New Short Message. Considering that 85% of all phone messages are text messages a shortcut to go straight to a compose window would be nice.

I won't even pretend to understand how the Speed No 'feature' works, it really is that bad; mind you the Sony one wasn't much good either for the non-smartphone models.

I regularly have to switch my phone to silent and back to my regular profile. How do I do this on these phones? I have to navigate through to the specific profile for silent, or else change the volume for the current profile using the volume control keys.

The phone book. Again, multiple entries for each name, the only thing identifying them is the tiny logo in the corner. The 'preferred number' feature is laughingly ineffectual, as far as I can tell it just puts one number ahead of the others.

Let's see, now for the slogan: Motorola, solid phones, shitty interfaces.

My old, unreliable mobile phone died a couple of days ago, and I needed to buy a replacement. I'm not able to upgrade my phone for another 2 months so I decided to buy a pay-as-you-go phone and just slip my SIM into it (same network, no issues with locking). People who know me, will understand that I have a liking for flip-phones, so I went for the Motorola V3 (Razr). Aargh! christ, but the phonebook is the biggest piece of shit I've ever come across. I understand this misbegotten need to have the phone book maintain some compatibility with the SIM, but for christ's sake, they need to get their act together on this. Practically every contact in my phone book has two entries, in fact most have 3. On the motorola phone book every contact is a separate entry on the person list. This means I have to wade through 2+ entries per person to scroll from one person to the next. Factor in that I store people's full names on the phone, in surname order, wading through the 9 Shanahan's in the book takes a long time. It always integrates the SIM contacts onto the phone book. There is no visible option to disable this 'feature' (my SIM contacts always were a backup of my phone entries), so I end up with loads of duplicates (or purge my SIM). I can't send my entire contact details to someone, I have to send it piece by piece. It shows the email addresses interspersed with the phone numbers which is pointless most of the time.

The next complaint is really a bit of a click-fascist thing. You know what I mean by this - it just seems to take an extra click or two to perform some tasks. Just enough to annoy perceptibly.

Then there's the syncing software. Following the really annoying splash screen - slow, irritating and serving no purpose, we are presented with a rendering of my phone on the bottom right corner of the screen, a bunch of icons and no idea what does what without mousing over one of the icons and seeing what it does, based on the tooltip! Come on people, tooltips cannot replace text! Apparently I can dial numbers from the number pad (never would have guessed at that). The only way to pop up the menu is to hit a box that's about 20 pixels square, replicating the menu button on the phone itself. Too small to hit easily, and there is no keyboard navigation, unless you can guess at the magic hotkeys. Most of the hard work is farmed off to other applications, none of which share details of the current state of the phone (contacts, calendar), each sub-application launch causes the data to be re-read, which takes ~30 seconds each. None of these sub-applications are keyboard navigable (bugbear of mine). Quitting the application requires either clicking on the really small off switch, or doing the acme Alt+F4 close the window trick. Practically everything visual about this application could do with a rewrite.
On the plus side, it does synchronize, which is it's primary role, but I just wish it wasn't so annoying about it.

Badly implemented phonebook aside, practically everything else about the phone is good. It's small, neat and call quality is great. I've not tested the bluetooth functionality very much so I can't say either way on it. Over all, I'd consider it a good replacement phone, but unless something good happens with the phone book, I'm not planning on buying another Motorola phone in the forseeable future after this one.

Now if only I could make my own phone book. I wonder if it's even possible on these kinds of phone. Maybe I should check this out.

Ooh! this one really annoys me. I'm using iTunes for syncing with my iPod. But when I'm playing music on the desktop if I right-click on anything in the explorer and don't select something really fast iTunes stops playing the music. What a piece of junk.

This one is beautiful. If you get an unhandled run-time exception in the public void main(String args[]) method then your application simply won't launch. You should make sure to intercept all exceptions in the main class and then throw up a simple error dialog.
Of course this doesn't work if you are missing a class in the distribution, the exception happens before you get to the main method.
Quick tip: enable and show the java console (JavaCPL on linux, java control panel under windows) it's under Java console in the Advanced tab.

I got an email purporting to be from paypal, asking me to download a security tool that will help protect my computer. Well guess what, it doesn't (well duh!). It turns out to be changing the NameServer entries for all the interfaces in in the registry keys under SYSTEM\ControlSet001\Services\Tcpip\Parameters\Interfaces to something else. Firing up a disassembler, we find out that the value it's trying to set is:

aRstpuucpuucpur	db 90h			; DATA XREF: start+Ao start+101o ...
		db  98h	; 
		db  92h	; 
		db  8Fh	; 
		db  93h	; 
		db  93h	; 
		db  96h	; 
		db  8Fh	; 
		db  93h	; 
		db  93h	; 
		db  96h	; 
		db  8Fh	; 
		db  93h	; 
		db  90h	; 
		db  99h	; 
		db    0	;  

Not surprisingly, this is not a kosher string, it's been encoded. One of the first things the code does is decode this, using the following bit of code

sub_0_40107E	proc near		; CODE XREF: start+Fp

arg_0		= dword	ptr  4

		mov	eax, [esp+arg_0]
		mov	ecx, eax
		mov	dl, [eax]

loc_0_401086:				; CODE XREF: sub_0_40107E+15j
		test	dl, dl
		jz	short locret_0_401095
		xor	dl, 0A1h
		mov	[ecx], dl
		mov	dl, [ecx+1]
		inc	ecx
		jmp	short loc_0_401086

<sarcasm>Terribly complicated</sarcasm>. The code xor's each value in the string with 0A1h. We can step by step this, or you can trust me that it's 193.227.227.218. A traceroute reveals that it's probably somewhere in romania (.ro top level domain)

Tracing route to 193.227.227.218 over a maximum of 30 hops

  1     1 ms    <1 ms    <1 ms  10.0.0.71 
  2    57 ms    21 ms    23 ms  b-ras1.lmk.limerick.eircom.net [159.134.155.24] 
  3    21 ms    22 ms    20 ms  ge15-2.corea.lmk.limerick.eircom.net [83.71.114.97] 
  4    36 ms    36 ms    35 ms  83.71.112.94 
  5    36 ms    40 ms    39 ms  london1-br2-fe0-0.rdsnet.ro [195.66.226.46] 
  6    54 ms    53 ms    52 ms  fra2-cr1-ge5-0.539.rdsnet.ro [62.231.127.89] 
  7     *        *        *     Request timed out.
  8    89 ms    90 ms    87 ms  constanta1-cr1-vlan25.rdsct.ro [212.93.137.51] 
  9    94 ms    88 ms    96 ms  constanta1-fo-vlan10.rdsct.ro [212.93.137.10] 
 10    89 ms   101 ms    90 ms  81.196.163.89 
 11    95 ms    95 ms   101 ms  cr1.micos.ro [193.227.226.254] 
 12    91 ms    96 ms    97 ms  193.227.227.218 

The short answer is never run code that you're uncertain of the origin of, and 2. never run code that you're uncertain of the origin of.

Quick XOR tutorial. Exclusive OR. Either A is true or B is true but not both. so 0 xor 0 = 0, 0 xor 1 = 1, 1 xor 0 = 1, 1 xor 1 = 0. Each hex digit is a run of 4 binary numbers. 0 = 0000, 9 = 1001, A = 1010, F = 1111.
90h xor 0A1h == 1001 0000 xor 1010 0001 = 0011 0001 = 31
Conveniently, 30h = '0', 39h = '9' and 2eh = '.', so it's easy to translate them.