Unsigned comparison in Java/Scala

Java (and consequently Scala) lack unsigned integer types. Most of the time this isn’t an issue – the majority of the operations you’re likely to care about (addition, subtraction, bitwise operations) work the same regardless of whether you treat the integer as unsigned. There are a few cases where it is a pain though – one that bit me in the context of the work I’ve been doing on and off with Java classfiles is that converting between types of different size. The other one that’s an issue is comparison – integer comparison is signed in Java and there are no operations for doing the unsigned compare.

One way to fix this is to delegate to a solution to the previous problem: Bump the integers up to a type one size up in an unsigned way so that they get converted to positive values, do a comparison on there. This works fine for the smaller values, but if you were to do this with a long you’d have to upgrade to a BigInt, which is a bit sad. I’d previously been doing it this way but earlier when I needed to do unsigned comparisons on longs I decided to look for a better route. (Full disclosure: Actually what happened is I converted some code using ints to code using long and suddenly all my unit tests broke. At that point I discovered that I’d still been trying to do an unsigned comparison using the code for doing it for integers).

Anyway, I popped into ##java to see if anyone there had any ideas for how to do it. Totally counter to form, ##java was actually incredibly useful. The best solution came from someone who went by Tamutnefret and is as follows:

  def unsignedCompare(i : Long, j : Long) = (i < j) ^ (i < 0) ^ (j < 0)

Which is really neat and avoids doing any branching.

Let’s see why this works. We’ll break it down by cases on i (there’s probably a nicer way to see that it works, but I’m blanking on what it is).

Suppose i = 0. This becomes (0 < j) ^ false ^ (j < 0), which is (0 < j) ^ (j < 0), or j != 0. Which is correct, as the only unsigned integer not > 0 is 0.

Suppose now i < 0. This becomes (i < j) ^ true ^ (j < 0).
If (j < 0) this becomes i < j, as x ^ true ^ true = x ^ false = x. If j >= 0 then we certainly have i < j, so we get true ^ true ^ false = false, which is again correct: In unsigned comparison any negative number is greater than any non-negative one. The case i > 0 follows similarily (the standard mathematician’s weasel words).

Anyway, the explanation of why is boring. It takes less time to convince yourself of its truth than it did to read that. :-) But the point is that it’s a cute, useful formula which I’d not previously encountered so I thought I’d record it here.

Removing myself from planet haskell

Hi all,

I’ve asked to be removed from planet Haskell. There’s just too little Haskell related content on this blog these days for me to think it’s really appropriate for me to be on it. If you want to keep reading my blog, please subscribe directly.

They called me mad

I haven’t written any fiction in ages, mostly because I kept dropping ideas as they were taking too long, so I’ve decided to start experimenting with microfiction as a format. Here’s the first of these.

They called me mad

I wake up on an operating table. I try to sit up, but I’m strapped down. Of course. Why is this never easy?

“Ah, Mr Michaels. You’re awake. Terribly sorry for the inconvenience, but we couldn’t have you interfering with the experiment. I’ll let you go as soon as we’re done here”.

I look at the speaker. An older man in a lab coat (why do they always wear lab coats? It’s not like they really need them. They’re always pristine white), fiddling around with some computer setup. My target.

There’s another table to my left. A dead woman on it – quite far gone. Well preserved, but withered and with a trace of decay. He’s further along than I’d hoped.

I strain against the bonds. No luck. I try to get to the knife in my hidden pocket, but it’s been taken. No way out but talking I guess.

“There’s still time to stop. I can guarantee you won’t be harmed.”

He looks genuinely puzzled.

“Why would I stop? Things are going so well”.

“What you’re doing is against nature! It will turn around and bite you if you don’t stop before it’s too late!”

“Do you live in a tree, Mr Michaels?”

“What?”

“Simple question. Do you live in a tree?”

“No. Why would I live in a tree?”

“Natural state of living for monkeys like ourselves. This modern housing, very unnatural.”

“That’s different”.

“Is it? Oh well, I suppose you’ve convinced me. I have seen the error of my ways and shall come quietly”.

“Really?”

“No, I’m afraid not. Anyway”, he said smiling brightly “all ready. We might as well begin”.

He presses a few buttons and a background humming noise I had hardly noticed raised in volume and pitch. My jaw dropped

“But how can you be ready? The storm isn’t for another two days!”

More bemused looks.

“Why would I need a storm? That sounds like a very unreliable way of working. I have a generator in the basement, and capacitors for storing the electric charge”.

I’m panicking now. I’d never let them get this close before. “Look, just stop! It’s all going to be horribly wrong!”

“Don’t be ridiculous. Do you think I haven’t tested this? I’m a scientist Mr Michaels. There is a process for these things. They called me mad, but the one accusation they never leveled was that my methods were insufficiently rigorous”.

“But you’ve never tested it on a human. Never on a being with a soul!”

He laughs. Not a cackle, just an amused little chuckle. I’ve heard a lot of mad laughs. I’m practically a connoisseur of a good diabolical laugh. Believe me, this chuckle is a lot worse.

“Of course I’ve tested it on a human. Tell me, Mr Michaels, did you think people normally wake up feeling quite so well rested after being shot in the face?”

I remember. I had my gun out, pointing at him, when there was a loud bang and then blackness. Oh god, he actually did it.

The humming raises to a fever pitch. There’s a crack, as if of thunder, and a bright white light fills the room. The dead woman sits up, decay fading and color and flesh returning to her. She smiles.

“Now, Mr Michaels, would you care to join Alice and myself for tea?”

java.lang.String#hashCode

Apologies in advance. This is a really boring post.

For reasons you either know about by now or don’t care about, I was curious as to how well String’s hashCode was distributed (I suspected the answer was “not very”). I ran a few quick experiments to verify this.

For your amusement, here is a list of all hash collisions between alphanumeric strings of size 2: http://www.drmaciver.com/collisions.txt and here is a list of all which don’t collide with any others http://www.drmaciver.com/noncolliding.txt

Some statistics: There are 3844 alphanumeric strings of size 2. Of these 3570 collide with at least one other string. That is, 274 of these strings (or about 7% of them) *don’t* collide with something else.

Oh well. It’s a good thing no one would be stupid enough to rely on hashCode to distinguish the contents of two objects.

Edit: Additional facts I originally posted in the comments.

For what it’s worth, even fewer strings have unique hash codes for 3 characters. 3948 don’t collide, or about 1.6% of them.

This of course doesn’t mean that probability of a hash collision is really high. In reality it’s acceptably low. It’s just a demonstration that it’s not hard to find colliding pairs.

The following consist of all the String hash collisions contained in the sowpods scrabble dictionary:

isohel, epistolaries
righto, buzzards
hierarch, crinolines
inwork, hypercatalexes
wainages, presentencing
variants, gelato
misused, horsemints
trichothecenes, locular
pomatoes, eructation

Lessons learned in class

(Warning: I’m half asleep, and this post is somewhere between a brain dump and a rant. Coherency is strictly optional).

So, my latest random personal project has turned into a bit of a debacle.

I decided I wanted a Java bytecode manipulation library with a decent Scala API. The options were either “Write my own” or “Write bindings to an existing one”. I chose something of a middle ground: “Port an existing one”. Rather than go for any of the normal big names I went for an obscure little internal library at EPFL called FJBG (Fast Java Bytecode Generator). It’s basically a low level interface onto the classfile format, and I’d used it before for code generation (e.g. for the structural proxies stuff) and found it pretty straightforward. Kindof hard to debug programming errors, but otherwise pretty robust.

One slight flaw: No test suite to speak of. But that’s ok, it’s used as part of the compiler backend for scalac, so I assume it gets relatively well covered by the scalac test suite. And it’s been around for quite a while, so has had itme to stabilise. Should be fine.

Right?

Anyway, the initial porting process went pretty smoothly. I was astonished at how smoothly in fact – after about 6 hours of work I had the bytecode generation code working in Scala and prettified to have nicer method names, etc. Pretty good going. I was frankly astonished – I basically ran it through jatran, spent about 6 hours fixing compiler errors and then at the end it took about 10 minutes of bug fixing before it just worked. Not bad. The only slight problem was that the class file parsing code wasn’t working.

The problem was that the way the code worked there was a fairly deeply nested inheritance strategy, and maintained two constructor hierarchies – one for creating things in memory, one for creating them from a DataInputStream. because of the way Scala handles constructors this is essentially impossible to do in Scala.

I’ve never thought this was a problem before, but this seemed to me to be quite a reasonable thing to do and I started to have doubts about Scala’s approach to constructors. I still have some, but not to the point that I previously had. The thing is, this approach is really fragile. It means that each constructor needs to balance the class’s invariants in different ways – you’ve given yourself twice as many opportunities to screw up.

Anyway, after some struggling with approaches I eventually (took me several times as long as the previous part of the porting) got this ported in a reasonably straightforward way. It wasn’t the prettiest code ever, but the mapping onto the original wasn’t bad. So I tried it out on a few simple tests – generate a class file, read it back in again, compare them to make sure you got approximately the same thing.

Hm. And it didn’t work. How curious.

I stared at the implementation for a bit, stared at the original Java, couldn’t see a difference. So I ran the same test on the original Java and it broke in the same way. Great.

That turned out to be an easy fix. But it was an easy fix to a problem very definitely caused by the multiple constructor hierarchy. Oh well, that worked now.

Next part of the test. Write the newly read class file to a file, load it and try to run it.

Oops. It NPEs when I try to write the file. Guess I did something wrong – I wonder why that array is null there. Looks like the logic for initialising it is rather complex, lets see how the original Java version handles this. So I wrote a simplified test case using the original which took a class file, read it to the in memory representation and wrote it out again and tested it against a random class file. It broke. In a totally different way to the way my version did – it didn’t even manage to read the file (I think the difference here is that this was a classfile found in the wild rather than one generated by FJBG). Tried it on a different, simpler one – Specifically the class generated by the obvious HelloWorld.java. That broke too.

So at this point I was forced to conclude that the class file reading code in FJBG just didn’t work at all. What the hell? Wasn’t this used in the Scala compiler? Clearly it has to be able to parse class files in order to know what’s available on the classpath to compile against!

So, some digging through the compiler source later: scalac doesn’t use FJBG’s class reading code at all. It has its own entirely separate code for that. So this code which I thought was part of a fairly mature and robust compiler backend was in fact completely and utterly untested and unused. No wonder it was broken.

So, new rule (to many of you, a very old rule): If it’s library code and it’s not tested, it’s broken. An application you can judge by “Does it do the right thing?” to at least get some sense of how not broken it is. Besides, I only have to use it, no code against it. But if my code is going to depend on yours, yours better be tested.

I’m usually pretty bad at tests actually. Applications I’ve written are certainly woefully undertested. SBinary’s tests are… well, adequate. And I don’t really recommend depending on any other libraries I’ve written – they’re all a bit incomplete and half assed. :-) Hopefully this will teach me to be better.

At this point I was already rather upset with FJBG’s object model – too mutable, too many back references. So on top of fixing the reading code I was going to have to fix that. At this point I decided that it was time to cut my losses, so I’m going to go back to option 1: Write my own. I’ll certainly reuse what I can salvage from the FJBG code (assuming some worries I have about licensing are resolved), but honestly the class file format is pretty easy. The overarching format took me two hours to write a parser for (I did it the same night as discovering that . The bytecode format for method bodies is harder, but I expect to be able to reuse FJBG code for this bit (and probably write a fair bit of my own).

Anyway, hopefully this will turn out to be a good thing and I’ll end up with something much more scalic than a straight port of FJBG would have been. We’ll see. Watch this space to see if anything comes of this, and watch this repo to keep an eye on the code.