← older articles

Use sshuttle to Keep Safe on Insecure Wi-Fi

If you’ve ever used an insecure Wi-Fi connection in a public place (think coffee shop, airport, etc.), your personal information could be at risk. Anyone on the local network could potentially be monitoring your traffic and they could even hijack your sessions to control accounts that you’ve logged into.

Every week I meet up with some friends to work on personal projects, and the venue only offers an open wireless connection with no encryption. To mitigate the risk of leaking personal information, I’ve tried a handful of strategies and eventually settled on using sshuttle.

What is sshuttle?

The sshuttle utility is part transparent proxy, part Virtual Private Network (VPN), and part SSH. It solves a lot of common problems with encrypting your traffic, and it does so in a very efficient way.

There’s no need for a complicated pre-existing infrastructure. All you need is Python 2.x, and a remote machine you can SSH to that also has Python installed. You don’t even have to be an administrator on the remote machine. The project’s README has a lot more information on its theory, design, and alternate uses.

Previous Method

As an aside, I had previously relied on creating a SOCKS proxy with SSH, and then tunnelling my web traffic through it…

$ ssh -fqND 1080 example.com

But, you have to adjust your machine’s proxy configuration settings each time you set up the tunnel, and then tear it all down when you’re done. This method will not force absolutely all traffic over the tunnel, as things like DNS lookups and a lot of command-line tools will just ignore the proxy. You’re also encapsulating TCP-over-TCP, which can cause performance problems.

I briefly messed with the Sidestep project to automate these setup/teardown steps on OS X, but ran across repeated authentication issues and wasn’t overly impressed with its developer. Overall, I needed a more elegant solution.

Installation

I wanted to use sshuttle on OS X Lion, and even though it’s primarily a command-line utility, it also comes with a graphical user interface wrapper that will sit in the menu bar. If you just want the command-line script and already use Homebrew, brew install sshuttle is the way to go. If you don’t use Homebrew and/or want the GUI, I’ve got your back…

Building sshuttle from Source

Unfortunately, pre-compiled binaries are not made available for every release, and documentation for building sshuttle is non-existent. The project uses a build system called ‘redo’ instead of the more-customary ‘make’, so the process is a bit different than what most people are used to.

Luckily, the sshuttle repository includes a shell script named ‘do’, which is a simplified version of redo, so you won’t need to install any additional build software. The only real dependencies are Python and two Python modules to generate the man page (feel free to use pip install instead of easy_install, if you prefer):

$ easy_install markdown BeautifulSoup

Once you’ve installed those two modules, you’re all set to build…

NOTE: You may have to adjust paths or permissions slightly depending on your machine’s setup.

$ mkdir -p /usr/local/libexec
$ git clone git://github.com/apenwarr/sshuttle.git /usr/local/libexec/sshuttle
$ cd /usr/local/libexec/sshuttle/
$ ./do all

Once sshuttle is built, we just make symlinks so the binary and man page are in the proper places:

$ ln -s /usr/local/libexec/sshuttle/sshuttle /usr/local/bin
$ mkdir -p /usr/local/share/man/man8
$ ln -s /usr/local/libexec/sshuttle/Documentation/sshuttle.8 /usr/local/share/man/man8

For the GUI app, we need to create an alias instead a symlink, because Spotlight will not index symlinks. Yes, you could just copy Sshuttle VPN.app directly into /Applications, but then you’d have to remember to copy it every time you update/rebuild sshuttle.

Without getting too technical, aliases are a lot like symlinks but they use extra metadata called “resource forks” to follow a file (even when it’s moved) rather then blindly pointing to a path. More importantly, Spotlight will index them. There’s no way to create an alias from the command line, so you have to use Finder:

Open Finder and press Command-Shift-G to open the “Go to the folder:” dialog box.
Type /usr/local/libexec/sshuttle/ui-macos in the box and click the Go button.
Click and hold Sshuttle VPN.app, then while holding down both the Command and Option keys, drag the app over to Applications on the left and release the mouse button.

Configuration

Due to some sysctl changes in OS X Lion, you will have to reboot your machine after you run sshuttle for the first time. An adjustment to the net.inet.ip.scopedroute kernel flag needs to be made, and it can no longer be done during runtime. This is required so forwarding rules will be honored by the firewall.

Everything should be handled automatically by sshuttle, but if your curious to see the change, you can display the boot kernel flags and current settings with the following commands:

$ defaults read /Library/Preferences/SystemConfiguration/com.apple.Boot
{
    "Kernel Flags" = "";
}
$ sysctl -a | grep scopedroute
net.inet.ip.scopedroute: 1
net.inet6.ip6.scopedroute: 1

After you run sshuttle for the first time and then reboot the machine, you can confirm the updated status:

$ defaults read /Library/Preferences/SystemConfiguration/com.apple.Boot
{
    "Kernel Flags" = "net.inet.ip.scopedroute=0";
}
$ sysctl -a | grep scopedroute
kern.bootargs: net.inet.ip.scopedroute=0
net.inet.ip.scopedroute: 0
net.inet6.ip6.scopedroute: 1

Usage

Finally we can get down to actually using sshuttle! It’s flexible enough to do fancier things, but for our particular use case, we just need to forward all traffic over the tunnel.

The basic command to achieve our goal looks like this:

$ sshuttle --dns -r example.com 0/0

NOTE: Sshuttle will honor your ~/.ssh/config connection settings, but you can also manually specify a different username/port, if necessary:

$ sshuttle --dns -r username@example.com:2222 0/0

Run that, and all of your traffic (including DNS requests) will be transparently proxied through an SSH connection to example.com. You can verify this by browsing to http://ifconfig.me.

To stop forwarding traffic, just press Ctrl-c back in the terminal. We can do a bit better though by forking the process into the background so we don’t tie up our terminal session. These are the aliases I use to make setting up and tearing down the tunnel easier:

alias tunnel='sshuttle --dns --daemon --pidfile=/tmp/sshuttle.pid --remote=example.com 0/0'
alias tunnelx='[[ -f /tmp/sshuttle.pid ]] && kill $(cat /tmp/sshuttle.pid) && echo "Disconnected."'

The Sshuttle VPN.app GUI is pretty self-explanatory, just make sure to enable the Send DNS requests through this server checkbox, and select Send all traffic through this server for the “Network routes:” option.

Known Bugs

You may see a bunch of “warning: closed channel …” messages when running sshuttle (either on STDOUT or in your system.log), but these warnings are safe to ignore. The developer knows about the issue and is thinking of the best way to suppress/eliminate the condition.

Also, prior to version 0.60 of sshuttle, there was a bug in the GUI application when disconnecting tunnels, where the controlling terminal would disappear before firewall rules could cleaned up. This would leave the network in an odd state and all DNS lookups would fail. It should be fixed now, but if you experience networking trouble after disconnecting a sshuttle tunnel, you can see the current firewall rules using:

$ sudo ipfw list

…and you can manually flush out those rules to fix connectivity by running:

$ sudo ipfw -f flush

Be aware though, this will flush out all rules, not just the rules set by sshuttle, so it may have unintended consequences. If you’re unsure, you can always reboot the machine to get connectivity back to normal.

Update sshuttle

Since our installation of sshuttle is managed via git, updating to the latest version is pretty straightforward:

$ cd /usr/local/libexec/sshuttle
$ git pull
$ ./do all

Conclusion

Admittedly, sshuttle takes a bit more work than other solutions to get up and running, but the security it provides gives me peace of mind when forced to use insecure Wi-Fi networks.

If you have any issues, there is an active mailing list for the project, or you can always send me a note and I’ll see what I can do to help.

Shelf-Made Standing Desk

Since I started working from home, I’ve found that I spend even more time sitting at my desk than I did when I worked at the office. I’ve never had great posture and started noticing that my back and shoulders were pretty achy by the end of the day. Once I got to that point, it was harder to stay focused on work and I was becoming noticably fatigued.

I started researching alternative workspaces, and found ideas ranging from sitting on an excercise ball to walking on a treadmill desk. Having sat on excercise balls before, I knew that I would quickly regress back to slouching; and the idea of working on a treadmill seemed too impractical. I needed something in between…

A Standing Desk

There seems to be a surge of people converting to standing desks recently, and there’s no shortage of personal stories and information on why they can be beneficial. Some very nice commercially-made standing desks are available, but not knowing if I’d actually like using one, I didn’t want to make a big up-front investment.

My Old Desk

For reference, my old desk was simply a cubicle desk surface that had been reclaimed from a dumpster. I always liked the amount of horizontal space it provided, and it was extremely solid, but not completely ideal.

My New Desk

I decided to convert a cheap shelving unit into a standing desk as a way to test the waters. At 48"W x 24"D x 72"H, this $80 rack from Lowes was pretty ideal, and I figured that after a month if I didn’t like it, the shelf could always be used in my garage.

I tried to follow OSHA guidelines as closely as possible when setting up the height of each shelf. The bottom shelf is about 7" above the ground to give my feet ample space below the rack; the upper shelf was placed so the top of the displays are right about eye-level; and the middle shelf was placed just below my elbow height for the keyboard and mouse. I used the extra shelf (which would have been on the very top) as a keyboard “tray” by cutting some notches in the corners to create a ledge that sticks out about six inches in the front.

Some friends pointed out that MDF could potentially contain Formaldehyde in the resin used to bind it together, and that prolonged contact might cause skin irritation. To prevent this, I wrapped the front part of the keyboard tray in faux leather contact paper. It looks nice, and prevents my wrists from getting itchy.

Here’s how everything came together…

So my hands always stay at the proper height, I use Synergy to control both my Linux desktop and my MacBook Pro laptop with the same keyboard and mouse.

The medical community points out that staying in one position for too long (whether that’s sitting or standing) can be bad for you, so there’s also a futon in my office where I can switch to using my laptop with a Logitech Comfort Lapdesk. Eventually, I may order a tall stool, so the option to sit at the desk will also be available; although, I do plan on standing for the majority of the time.

Accessories

To make the standing desk more ergonomic, I purchased a few accessories:

A Rain Design mStand laptop stand to bring my MacBook Pro’s display up to the proper height
A Kensington SoleMate Plus adjustable footrest to help facilitate shifting my weight throughout the day
A 16" Zilotek LED strip light to help eliminate shadows and illuminiate the shelf with the keyboard and mouse

Here’s an idea of roughly how the keyboard tray looks without the LED strip light installed; and if you mouse over the image, you’ll see what it looks like with the LED lights turned on…

Conclusions

My first full day of standing was January 19th, 2011, and so far, I really love the desk. The first week was definitely a little rough, with my feet and back becoming sore by the end of the day, but it’s getting better. I’ve read that it takes a couple of weeks to fully adjust, so after I’ve given the desk a bit more time, I’ll post another update. At this point, I’m optimistic that it will be a permanent change to my home office setup.

Update

It has been almost 8 months since I started using the standing desk, and I don’t think I could go back. My posture has noticeably improved, and I quickly got over the initial soreness. I stand up about 85–90% of the time, and sit down with my lapboard for the rest (mostly later in the day). I’ve only made a few changes to my setup so far:

I switched to an Kenesis Freestyle ergonomic keyboard to help improve wrist positioning and limit overreaching when using the mouse
I added an Imprint anti-fatigue floor mat to make standing more comfortable (even though my office is carpeted)
I added an Apple Magic Trackpad near my mouse pad so I wouldn’t need to reach to the upper level of the desk to perform multi-touch gestures

It’s safe to say that I enjoy utilizing a standing desk, and even though my shelving unit was originally purchased as an inexpensive way to get my feet wet, it has worked out better than expected. For now, it gets the job done and I don’t see the need to purchase a more expensive standing desk.

The only other planned improvements I have would be, to finally cut off the extra portion of each of the metal support rails that stick out from the top, and to build small side shelves that could support a pair of KRK Rokit 5 studio monitors. Once I’ve done those things, I’ll post an updated photo of how it looks.

Since posting this original article, I’ve inspired a handful of friends to try out standing desks, and all of them have stuck with it. If you’ve been on the fence about trying a standing desk, I can easily say that it’s worth the effort to give it a shot. I’d love to hear from you if you end up taking the plunge!

Update²

Well, I finished all of my planned improvements and here are the updated pics…ignore the dust and messy cabling :-)

I found the shelves as a kit from Knape & Vogt for ~$20 each, but had to purchase some additional hardware (bolts, washers, and locking nuts) since they were originally designed for mounting with wood screws. The shelves can supposedly support up to 50 pounds each; they are stable, but I wouldn’t be comfortable adding much more than the current 15 pounds on them.

Cutting the metal support rails and trimming the shelf mounts to fit took a fair bit of time, a steady hand, and a Dremel. If you try it, the one thing I’ll say is to definitely wear safety glasses!

Anyway, I think I’m finally done tweaking things for a bit, but am incredibly happy with the results. Go forth and stand!

Porting a Poker Hand Evaluator from C to Factor

To help teach myself Factor, I started solving a lot of the problems at Project Euler and approached each one, not only as a way to learn a new language, but as a means of exploring unfamiliar programming/mathematical methods, structures, and algorithms. This article explains the process I went through to port a fairly complicated poker hand evaluation algorithm from C to Factor.

Problem 54

In order to solve Problem 54, I needed to come up with a way to programatically determine the winner when comparing two poker hands. I had recently read an extensive blog post covering various poker hand evaluators, so I knew that I didn’t want to bother with a naive solution when there were much better options out there. After reading through the different techniques, one stood out to me in particular; it was a relatively small amount of code, it didn’t require a ton of storage space, and it was plenty fast…

Cactus Kev’s Poker Hand Evaluator

Through the power of mathematics (combinatorics in particular), you can ascertain that out of all 2,598,960 possible poker hands (52 choose 5), there are actually only 7462 distinct hand values that you need to be concerned with. The basic idea behind Cactus Kev’s Poker Hand Evaluator is that you can take advantage of this fact by storing a card’s representation in an efficient manner, do some basic bit twiddling, some multiplication (which is computationally cheap), add in a couple lookup tables, and you can determine a hand’s equivalence class value very quickly.

The key concept here is that each of a card’s possible 13 ranks (deuce through ace) is stored as a different prime number, and by multiplying a hand’s five prime numbers together, you’ll get a unique result that can then be used to determine that hand’s overall value. If you handle the special cases of flushes, straights, and high cards, the rest can be boiled down to a simple binary search. You can read the gory details at Kevin Suffecool’s site.

The Porting Process

Bitfield Representation

Each card will be stored as a bitfield, inside of an interger that’s 4-bytes long:

+-------------------------------------+
| xxxbbbbb bbbbbbbb ssssrrrr xxpppppp |
+-------------------------------------+
  xxxAKQJT 98765432 CDHSrrrr xxpppppp
  -----------------------------------
  00001000 00000000 01001011 00100101  =  134236965  =  King of Diamonds
  00000000 00001000 00010011 00000111  =     529159  =  Five of Spades
  00000010 00000000 10001001 00011101  =   33589533  =  Jack of Clubs

x = bit turned off, not used
b = bit turned on depending on rank of card
s = bit turned on depending on suit of card
r = rank of card (deuce = 0, trey = 1, four = 2, …, ace = 12)
p = prime number value of rank (deuce = 2, trey = 3, four = 5, …, ace = 41)

For now, I’m going to ignore how we get cards into this particular format, but I’ll come back to that in a bit.

Constants

Now that we have an efficient means of representing individual cards, we need to establish some basic constants to align with the above bitfield representation and overall hand values…

Constants In C:

#define CLUB     0x8000
#define DIAMOND  0x4000
#define HEART    0x2000
#define SPADE    0x1000

#define Deuce  0
#define Trey   1
#define Four   2
#define Five   3
#define Six    4
#define Seven  5
#define Eight  6
#define Nine   7
#define Ten    8
#define Jack   9
#define Queen  10
#define King   11
#define Ace    12

#define STRAIGHT_FLUSH   1
#define FOUR_OF_A_KIND   2
#define FULL_HOUSE       3
#define FLUSH            4
#define STRAIGHT         5
#define THREE_OF_A_KIND  6
#define TWO_PAIR         7
#define ONE_PAIR         8
#define HIGH_CARD        9

static char *value_str[] = {
    "",
    "Straight Flush",
    "Four of a Kind",
    "Full House",
    "Flush",
    "Straight",
    "Three of a Kind",
    "Two Pair",
    "One Pair",
    "High Card"
};

Constants In Factor:

CONSTANT: CLUB     8
CONSTANT: DIAMOND  4
CONSTANT: HEART    2
CONSTANT: SPADE    1

CONSTANT: DEUCE  0
CONSTANT: TREY   1
CONSTANT: FOUR   2
CONSTANT: FIVE   3
CONSTANT: SIX    4
CONSTANT: SEVEN  5
CONSTANT: EIGHT  6
CONSTANT: NINE   7
CONSTANT: TEN    8
CONSTANT: JACK   9
CONSTANT: QUEEN  10
CONSTANT: KING   11
CONSTANT: ACE    12

CONSTANT: STRAIGHT_FLUSH   0
CONSTANT: FOUR_OF_A_KIND   1
CONSTANT: FULL_HOUSE       2
CONSTANT: FLUSH            3
CONSTANT: STRAIGHT         4
CONSTANT: THREE_OF_A_KIND  5
CONSTANT: TWO_PAIR         6
CONSTANT: ONE_PAIR         7
CONSTANT: HIGH_CARD        8

CONSTANT: VALUE_STR { "Straight Flush" "Four of a Kind" "Full House" "Flush"
    "Straight" "Three of a Kind" "Two Pair" "One Pair" "High Card" }

Here, the only difference I made in the Factor version was to start the hand value types at 0 instead of 1 to eliminate the empty string at index 0…it’s unneccessary.

Prime Number Representations

As mentioned above, each card rank will be represented by its own prime number, so we’ll need a way to reference that…

Prime Numbers In C:

int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 };

Prime Numbers In Factor:

CONSTANT: RANK_STR { "2" "3" "4" "5" "6" "7" "8" "9" "T" "J" "Q" "K" "A" }

: card-rank-prime ( rank -- n )
    RANK_STR index { 2 3 5 7 11 13 17 19 23 29 31 37 41 } nth ;

A minor change I made here was to establish a RANK_STR constant to make it easier to develop ways to parse and print card representations later (see the section on printing below for the C equivalent). That said, card-rank-prime in the Factor version has the same purpose as the primes array in the C version, but it performs the lookup for you.

Initializing Cards

Now that we have some basic infrastructure in place, we can tackle initializing cards in the desired format. Cactus Kev’s code glosses over this process and only demonstrates how to generate an entire deck, so I’ll just cover the Factor code here…

Initializing Cards In Factor:

: card-rank ( rank -- n )
    {
        { "2" [ DEUCE ] }
        { "3" [ TREY  ] }
        { "4" [ FOUR  ] }
        { "5" [ FIVE  ] }
        { "6" [ SIX   ] }
        { "7" [ SEVEN ] }
        { "8" [ EIGHT ] }
        { "9" [ NINE  ] }
        { "T" [ TEN   ] }
        { "J" [ JACK  ] }
        { "Q" [ QUEEN ] }
        { "K" [ KING  ] }
        { "A" [ ACE   ] }
    } case ;

: card-suit ( suit -- n )
    {
        { "C" [ CLUB    ] }
        { "D" [ DIAMOND ] }
        { "H" [ HEART   ] }
        { "S" [ SPADE   ] }
    } case ;

: card-rank-bit ( rank -- n )
    RANK_STR index 1 swap shift ;

: card-bitfield ( rank rank suit rank -- n )
    {
        { card-rank-bit 16 }
        { card-suit 12 }
        { card-rank 8 }
        { card-rank-prime 0 }
    } bitfield ;

:: (>ckf) ( rank suit -- n )
    rank rank suit rank card-bitfield ;

: >ckf ( string -- n )
    #! Cactus Kev Format
    >upper 1 cut (>ckf) ;

: parse-cards ( string -- hand )
    " " split [ >ckf ] map ;

To use this code, you’d start with a string representing a card, like "AS" for the Ace of Spades or "7H" for the Seven of Hearts, and then pass it to >ckf to get its integer representation. The parse-cards word simply does this conversion for an entire hand; given a string like "7C 5D 4H 3S 2C", it will output an array of the proper integers:

(scratchpad) "7C 5D 4H 3S 2C" parse-cards .
{ 2131213 541447 270853 135427 98306 }

Due to Factor’s concatenative nature, you tend to write a lot of small words that do one specific thing, and then tie them together. Words are expected to be defined before you reference them (unless they’ve been deferred), so when reading code from top to bottom, you’ll see big-picture words defined after the more-focused words they use. It’s also a convention to name helper words the same as the word from which they’re called, but with parentheses around the name.

One special thing to note is the use of locals in the (>ckf) helper word…if you start a word definition with :: instead of just :, Factor will bind the named inputs (from the stack declaration) to lexical variables from left to right. It’s used in this case because we need to pass these values to the card-bitfield word in a specific order, and shufflers would make this a bit more confusing.

The last thing to explain is the card-bitfield word itself…it looks up the proper bit values for the different parts of our card representation, and then constructs the final 4-byte integer from those values. See the bitfield documentation for more details on its syntax.

Shuffling Decks and Printing Hands

Initializing and shuffling a deck wasn’t strictly necessary for solving the Project Euler problem, but it was a useful abstraction and would be expected in a general poker library. Printing out a poker hand falls under this same category, but I’ve included it here as well since it was part of Cactus Kev’s original code. This is where the languages start to noticibly deviate in their implementations…

Initializing a Deck In C:

init_deck( int *deck )
{
    int i, j, n = 0, suit = 0x8000;

    for ( i = 0; i < 4; i++, suit >>= 1 )
        for ( j = 0; j < 13; j++, n++ )
            deck[n] = primes[j] | (j << 8) | suit | (1 << (16+j));
}

Initializing a Deck In Factor:

: <deck> ( -- deck )
    RANK_STR SUIT_STR 2array [ concat >ckf ] product-map ;

Shuffling a Deck In C:

double  drand48();

shuffle_deck( int *deck )
{
    int i, n, temp[52];

    for ( i = 0; i < 52; i++ )
        temp[i] = deck[i];

    for ( i = 0; i < 52; i++ )
    {
        do {
            n = (int)(51.9999999 * drand48());
        } while ( temp[n] == 0 );
        deck[i] = temp[n];
        temp[n] = 0;
    }
}

Shuffling a Deck In Factor:

ALIAS: shuffle randomize

Printing a Hand In C:

print_hand( int *hand, int n )
{
    int i, r;
    char suit;
    static char *rank = "23456789TJQKA";

    for ( i = 0; i < n; i++ )
    {
        r = (*hand >> 8) & 0xF;
        if ( *hand & 0x8000 )
            suit = 'c';
        else if ( *hand & 0x4000 )
            suit = 'd';
        else if ( *hand & 0x2000 )
            suit = 'h';
        else
            suit = 's';

        printf( "%c%c ", rank[r], suit );
        hand++;
    }
}

Printing a Hand In Factor:

: >card-rank ( card -- string )
    -8 shift HEX: F bitand RANK_STR nth ;

: >card-suit ( card -- string )
    {
        { [ dup 15 bit? ] [ drop "C" ] }
        { [ dup 14 bit? ] [ drop "D" ] }
        { [ dup 13 bit? ] [ drop "H" ] }
        [ drop "S" ]
    } cond ;

: card>string ( card -- string )
    [ >card-rank ] [ >card-suit ] bi append ;

: print-hand ( hand -- )
    [ card>string ] map " " join print flush;

I’m cheating a bit here with the shuffle word, as Factor already implements randomize using the Fisher-Yates algorithm; so rather than re-inventing the wheel, I just aliased the wheel. With Factor, you’ll also notice that count-controlled loops are much less common in comparison to using sequence operators directly on the elements of a data structure.

Lookup Tables

We can almost get to the actual evaluation of hands to determine their relative value, but before that, we’ll need the proper lookup tables. These are all straight-forward arrays, and we have four to consider:

a table for all flushes (including straight flushes)
a table for all non-flush hands consisting of five unique ranks (i.e. either straights or high card hands)
a table of the product of prime values associated with a hand
a table covering the final hand values of all hands not covered by the flushes/unique5 tables

A zero means that specific combination is not possible for that type of hand…

Lookup Tables In C:

short flushes[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1599, 0, 0, 0, 0, 0, 0, 0, 1598, 0, 0, 0, 1597, 0, 1596,
...
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
};

short unique5[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1608, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 7462, 0, 0, 0, 0, 0, 0, 0, 7461, 0, 0,  0,  7460,  0,
...
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0,  0,  0,  0,  0, 0, 0, 0, 0, 0, 0, 1600
};

int products[] = {
48, 72, 80, 108, 112, 120, 162, 168, 176,  180,  200,  208,  252,
264,  270, 272, 280, 300, 304, 312, 368, 378, 392, 396, 405, 408,
420, 440, 450, 456, 464, 468, 496, 500, 520, 552, 567, 588,  592,
...
66737381,   71339959,  73952233,  76840601,  79052387,  81947069,
85147693, 87598591, 94352849, 104553157
};

short  values[] = {
166, 322, 165, 310, 164, 2467, 154, 2466, 163,  3325,  321,  162,
3324,  2464,  2401,  161,  2465, 3314, 160, 2461, 159, 2400, 320,
3323, 153, 2457, 6185, 2463, 3303, 2452,  158,  3322,  157,  298,
...
1676, 14, 168, 2469, 2468, 1611, 23, 1610, 13, 179, 12, 167, 11
};

Lookup Tables In Factor:

CONSTANT: flushes-table
{ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1599 0 0 0 0 0 0 0 1598 0 0 0 1597 0 1596 8 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1595 0 0 0 0 0 0 0 1594 0 0 0 1593 0 1592 1591 0 0 0 0 0 0 0 0 1590
...
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 }

CONSTANT: unique5-table
{ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1608 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 7462 0 0 0 0 0 0 0 7461 0 0 0 7460 0 7459 1607 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 7458 0 0 0 0 0 0 0 7457 0 0 0 7456 0 7455 7454 0 0 0 0 0 0
...
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1600 }

CONSTANT: products-table
{ 48 72 80 108 112 120 162 168 176 180 200 208 252 264 270 272 280 300 304 312
368 378 392 396 405 408 420 440 450 456 464 468 496 500 520 552 567 588 592 594
612 616 630 656 660 675 680 684 696 700 702 728 744 750 760 780 828 882 888 891
...
64379963 64992503 66233081 66737381 71339959 73952233 76840601 79052387
81947069 85147693 87598591 94352849 104553157 }

CONSTANT: values-table
{ 166 322 165 310 164 2467 154 2466 163 3325 321 162 3324 2464 2401 161 2465
3314 160 2461 159 2400 320 3323 153 2457 6185 2463 3303 2452 158 3322 157 298
2460 2446 152 3292 156 2398 3321 2462 5965 155 6184 309 2456 3320 2439 3313
...
1622 191 3546 2490 2470 15 2600 25 3326 169 24 1612 2479 1677 1621 1676 14 168
2469 2468 1611 23 1610 13 179 12 167 11 }

Hand Evaluation

Finally, we can get to the actual evaluation of hands…

Hand Evaluation In C:

int findit( int key )
{
    int low = 0, high = 4887, mid;

    while ( low <= high )
    {
        mid = (high+low) >> 1;      // divide by two
        if ( key < products[mid] )
            high = mid - 1;
        else if ( key > products[mid] )
            low = mid + 1;
        else
            return( mid );
    }
    fprintf( stderr, "ERROR:  no match found; key = %d\n", key );
    return( -1 );
}

short
eval_5cards( int c1, int c2, int c3, int c4, int c5 )
{
    int q;
    short s;

    q = (c1|c2|c3|c4|c5) >> 16;

    /* check for Flushes and StraightFlushes
    */
    if ( c1 & c2 & c3 & c4 & c5 & 0xF000 )
    return( flushes[q] );

    /* check for Straights and HighCard hands
    */
    s = unique5[q];
    if ( s )  return ( s );

    /* let's do it the hard way
    */
    q = (c1&0xFF) * (c2&0xFF) * (c3&0xFF) * (c4&0xFF) * (c5&0xFF);
    q = findit( q );

    return( values[q] );
}

Hand Evaluation In Factor:

: flush? ( hand -- ? )
    HEX: F000 [ bitand ] reduce 0 = not ;

: rank-bits ( hand -- q )
    0 [ bitor ] reduce -16 shift ;

: lookup ( hand table -- value )
    [ rank-bits ] dip nth ;

: prime-bits ( hand -- q )
    [ HEX: FF bitand ] map-product ;

: hand-value ( hand -- value )
    dup flush? [ flushes-table lookup ] [
        dup unique5-table lookup dup 0 > [ nip ] [
            drop prime-bits products-table sorted-index
            values-table nth
        ] if
    ] if ;

Each language’s implementation checks for flushes first, then for hands with five unique ranks, and if all else fails, multiplies the primes together, searches for that product in a lookup table, and then uses that index to determine the hand’s final value. The findit function in C is the binary search, and once again I used Factor’s built-in libraries to do the same thing with the sorted-index word.

Hand Ranking

We’re basically done at this point…the hand with the lowest value (from 1 to 7462) wins. If the values are the same, the hands are tied. A simple comparison function can tell you which hand is best.

One last function that’s handy though, is the ability to output what that value actually means…

Hand Ranking in C:

int
hand_rank( short val )
{
    if (val > 6185) return(HIGH_CARD);        // 1277 high card
    if (val > 3325) return(ONE_PAIR);         // 2860 one pair
    if (val > 2467) return(TWO_PAIR);         //  858 two pair
    if (val > 1609) return(THREE_OF_A_KIND);  //  858 three-kind
    if (val > 1599) return(STRAIGHT);         //   10 straights
    if (val > 322)  return(FLUSH);            // 1277 flushes
    if (val > 166)  return(FULL_HOUSE);       //  156 full house
    if (val > 10)   return(FOUR_OF_A_KIND);   //  156 four-kind
    return(STRAIGHT_FLUSH);                   //   10 straight-flushes
}

Hand Ranking in Factor:

: value>rank ( value -- rank )
    {
        { [ dup 6185 > ] [ drop HIGH_CARD ] }        ! 1277 high card
        { [ dup 3325 > ] [ drop ONE_PAIR ] }         ! 2860 one pair
        { [ dup 2467 > ] [ drop TWO_PAIR ] }         !  858 two pair
        { [ dup 1609 > ] [ drop THREE_OF_A_KIND ] }  !  858 three-kind
        { [ dup 1599 > ] [ drop STRAIGHT ] }         !   10 straights
        { [ dup 322 > ]  [ drop FLUSH ] }            ! 1277 flushes
        { [ dup 166 > ]  [ drop FULL_HOUSE ] }       !  156 full house
        { [ dup 10 > ]   [ drop FOUR_OF_A_KIND ] }   !  156 four-kind
        [ drop STRAIGHT_FLUSH ]                      !   10 straight-flushes
    } cond ;

: string>value ( string -- value )
    parse-cards hand-value ;

: hand-rank ( string -- string )
    string>value value>rank VALUE_STR nth ;

Cactus Kev’s code didn’t include the code for explicit output of a string, but he did include the value_str array which could be used for this purpose.

Putting it All Together

To use the poker evaluator directly in Factor’s interactive listener environment, you can enter something like these examples:

(scratchpad) "7H 7S 7D AS AC" hand-rank .
"Full House"

(scratchpad) "7C 5D 4H 3S 2C" "KD QS JC TH 9S" [ string>value ] bi@ > .
t

Solving Problem 54

Getting back to our original goal of solving Project Euler’s Problem 54, we can now quite easily determine how many times Player 1 wins out of 1000 random hands dealt to two players…

: source-054 ( -- seq )
    "resource:extra/project-euler/054/poker.txt" ascii file-lines
    [ [ 14 head-slice ] [ 14 tail-slice* ] bi 2array ] map ;

: euler054 ( -- answer )
    source-054 [ [ string>value ] map first2 before? ] count ;

The source-054 word simply converts the provided text file into the format our evaluator expects and the hand comparisons are subsequently handled by the euler054 word and counted up! Let’s just say that Player 2 is much better at poker :-)

Vocabulary Improvements

Since porting the initial version of the poker vocabulary, many improvements have been made to generalize the code for use beyond just solving Project Euler problems. I ended up dropping the binary search in favor of using the Senzee Perfect Hash Optimization, and other Factor contributors have added code specifically for Texas Hold’em and Omaha evaluation. I didn’t want to cover all of that here, as the focus of this article is the direct comparison between C and Factor, but you can view the current poker vocabulary to see all of these enhancements.

As always, feel free to drop me a line if you’d like to discuss things further.

← older articles

ElasticDog.com …the ballyhoo of Aaron Bull Schaefer

Survey my Influence or Peruse my Relics