Twenty years of Skidmarks

Lately I've been digging through the old Skidmarks archives, and I came across this wee gem from 1993, no doubt written with lots of help from Simon:

Function.q hite {di.q,dj.q,oset.l}

  UNLK a4

  MOVE.l d2,a0

  MOVE.l d1,d2:SWAP d2:EXT.l d2:ASL.l #7,d2:ADD.l d2,a0

  MOVE.l d0,d2:SWAP d2:EXT.l d2:ASL.l #1,d2:ADD.l d2,a0

  MOVEM (a0)+,d2-d3 ;d0-d1 xy d2-d5 p0-p3

  LEA 124(a0),a0:MOVEM (a0)+,d4-d5

         MOVE d0,d6:MULU d1,d6:SWAP d6:MULU d6,d5  ; x. y.p3

  NOT d0:MOVE d0,d6:MULU d1,d6:SWAP d6:MULU d6,d4  ;-x. y.p2

  NOT d1:MOVE d0,d6:MULU d1,d6:SWAP d6:MULU d6,d2  ;-x.-y.p0

  NOT d0:           MULU d1,d0:SWAP d0:MULU d3,d0   ; x.-y.p1

  ADD.l d2,d0:ADD.l d4,d0:ADD.l d5,d0 ;total

  LSR.l#6,d0:RTS

End Function

For those not quite brave enough to decipher the 68000 assembly, here's what a strictly literal translation might be:

float Height(float x, float y, short *heightField){

  //__asm{...}

  heightField += int(x) * 64;

  heightField += int(y);

  short height2 = *heightfield++, height3 = *heightField++;

  heightField += 62; short height4=*heightfield++, height5 = *heightField++;

  float result5 = frac( x) * frac( y) * height5;

  float result4 = frac(-x) * frac( y) * height4;

  float result2 = frac(-x) * frac(-y) * height2;

  float result0 = frac( x) * frac(-y) * height0;

  float result = (result0 + result2 + result4 + result5);
  return result / 64;

}

The motivation is that I've been working towards a new version for mobile devices, with a working title of "Super Skidmarks 2000" (hashtag #SS2K)

Here's what the modern version of that same function looks like, this time in C++ :

float SKTrack::GetHeight(float axisI,float axisJ)const{

  int fi=(int)floor(axisI);

  int fj=(int)floor(axisJ);

  if(fi<0||fi>=63){

    return 0.0f;

  }

  if(fj<0||fj>=63){

   return 0.0f;

  }

  int index=fi+fj*64;

  float v0=HeightField[index];

  float v1=HeightField[index+1];

  float v2=HeightField[index+64];

  float v3=HeightField[index+65];

  float s=axisI-floor(axisI);

  float t=axisJ-floor(axisJ);

  float v01=v0*(1.0f-s)+v1*s;

  float v23=v2*(1.0f-s)+v3*s;

  float height=v01*(1.0f-t)+v23*t;

  return height;

}

As always, any questions / comments, or suggestion for a better name etc, please leave a comment below!

Why he vertically aligns his code (And why you shouldn't)

Over on Terence Eden's blog, the latest post is about vertically aligning code : https://shkspr.mobi/blog/2014/11/why-i-vertically-align-my-code-and-you-should-too

The "bad" example looks like this:

Which is then "fixed" to make it look like this :

Just for comparison, I typed it into my regular text editor:

The point being, because I'm using a well designed syntax highlighting where the numbers (green) contrast with the operators.  If you so choose, you can visually inspect just the green numbers and just as easily spot the outlier.

(Pro-tip: To concentrate on just one color, defocus your eyes slightly by staring "through" the plane of the monitor to engage your eye's cone cells.  With a little practice, you'll find yourself doing this automatically when you want to focus on the structure of the code instead of the details.  For best results, you might need to make the glyphs larger on screen....)

Note too, how the combination of proportional font and camelCase instead of under_scores keep the code density onscreen the same, but the individual glyphs appear larger in-place.

My code editor also uses syntax highlighting to hint the kerning.  So for example, the kerning around the equals sign and the semi-colon are particularly loose to aid in their recognition. Similarly, the single space character (' ')  has a width 50% larger than would be used for normal paragraph text.

But here's the big change that Terence missed, I've sorted all the variable declarations alphabetically to ensure there are no duplicates.  This is a zero-cost policy that can simplify merges and conflict resolution when multiple variables (possibly duplicate) have been added upstream.

Coding Atoms

The bigger problem is the coding atom is the line-of-code.

Lets take another code example from Terence's blog post, this time a function declaration :

extern int SomeDemoCode(int fred,
                        int wilma);

That's an atom right there - you can't split that up without changing its meaning. Watch what happens if I try to add a parameter in an excess white-space environment:

extern int SomeDemoCode(int fred,
+                       int barney,

                        int wilma);

The diff splits our (atomic) function signature across 3 lines, exposing us to problems where a git merge might accidentally succeed, when really we need it to flag a merge conflict.

(For a real world case of how bad automatic merging can be, take a look at the Goto Fail Bug)

Now compare if everything had been on the same line, the diff would look like :

-extern int SomeDemoCode(int fred, int wilma);
+extern int SomeDemoCode(int fred, int barney, int wilma);


TL;DR: Using whitespace to control your code presentation is a hack from the '70s.. get a better editor.

p.s. Some formatting edits have been made to make this post clearer.

Half-Open Squares

Allow me to re-introduce our friends, the half-open intervals :

The half-open interval,  [a,b)

They're the set of all x, such that a ≤ x and x < b.

We use them all the time.  Here's one :

An iterator in C++, over a half-open interval.

Open and Closed

What does it mean for a set to be open? What does it mean for it to be closed?  And half-open? What's up with that?

I'll save the formal definition for another time, but intuitively, we can think of an open set as one where every member has a little bit of wiggle room.  No matter how closely you zoom in to the edge of the set, there's always a little bit more before you get to the edge :

The open interval,  (a,b)

And a closed set? That's the set where if you start from the outside side of the set, there's always a little bit of wiggle room before you get to the edge. No matter how close to the edge of the set you are, there's always just a little bit of gap before you can get inside.

A set is closed iff its complement is open.

So half-open?  What's that?  Given the strange definitions for open and closed, it should come as no surprise we have another strange definition : A half-open set is one that has one side closed, and one side open!

Half open: one side closed, one side open.

Splitters and Joiners

Half open intervals are great for joining.  Suppose we have two half-open intervals, [a,b) and [b,c).  Then their union is just [a,c) .

Further more, if we know that if x is in [a,c), then it must be in either [a,b) or [b,c).

You'll see this all the time when we write recursive algorithms on containers with iterators, we use an iterator to split the container into two smaller containers, which each member is in one, and only one, of the children.

Rectangles

And what of the half-open rectangles?
Here's one:

1 ≤ x < 3 and  1 ≤ y < 3

If we use half-open rectangles, we get all of the same benefits as the 1 dimensional case.  We can easily form the union and intersection.  The empty rectangle has a simple representation.  We can subdivide, etc, etc

Here's what it might look like in code :

A Half-Open rectangle class.

Still not convinced?  Consider an 800 x 600 bitmap, whose pixels are [0,800) x [0,600)

for ( int y = 0; y < height; y++ )

{

    for ( int x = 0; x < width; x++ )

    {

        PlotPixel ( x, y, Color );

    }

}

Or this unbound function:

  Rectangle Intersect ( const Rectangle &a, const Rectangle &b )

  {
      return Rectangle (

          max ( a.X0, b.X0 ), max ( a.Y0, b.Y0 ),

          min ( a.X1, b.X1 ), min ( a.Y1, b.Y1 ) );
  }

Next time you make an interval, rectangle, or cube class, why not try using the half-open convention?  You'll almost certainly arrive at a smaller, more robust code.