I keep forgetting this when I decide to accidentally create files with names that turn out to be undeletable under windows. What makes a valid Windows file name? is a blog entry on Brian Dewey’s blog and it reminds me that using the \\?\ feature bypasses the MAX_PATH check for a file name’s length when trying to manipulate it (or delete it). I’ve accidentally created files with long names a few times, and been unable to delete them. Thankfully I’ve created a little application that allows me to do this now.
Least Significant 1 Bit
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))).
Integer Selection
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.
Integer Minimum or Maximum
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)).
[Listening to: Queen Bitch (live) – David Bowie – RarestOneBowie (3:15)]
Dual-Linked List with One Pointer Field
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.
[Listening to: Space Oddity – David Bowie – Changesbowie (5:17)]
SysQSort for sorting on PalmOS – optimizations
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.
There’s NUMA perhaps we need NUPA
a minor addendum to the previous post, perhaps we need to work on Non Uniform Processor Access 🙂
When you don’t know, then you need is a little magic(5)
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.
Bad Motorola, no cookie for you
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.
Java webstart – absence of errors, absence of forms
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.
[Listening to: Funny Break – Orbital – Orbital (4:56)]