Bit Field in PHP

So, a coworker ran across a piece of legacy code and wasn't sure what it was doing.



His first guess was a typo in a logical AND (&&). I completely understand his confusion, binary operators are not commonly used in PHP programs. Being an old C programmer, when I saw this I knew immediately it was a bit field. Checking the database table that $external_reports was pull from confirmed this :

+----------+------+
| Name     | Type |
+----------+------+
| Report A |    1 |  
| Report B |    2 |
        ...
| Repord H |  256 |
| Report I |  512 |
+----------+------+

So, what is a bit field? Wikipedia says Bit Field is a "common idiom used in computer programming to compactly store multiple logical values as a short series of bits where each of the single bits can be addressed separately." These are extremely important when the memory usage is vital (and probably other scenarios that I can't think of while I write this). Infact, C/C++ has the idea of bit fields built into the struct type.

Okay, so the important part, how they work. First let's look at that table again with an extra piece of information, the binary representation of the numbers :

+----------+------+
| Name     | Type |
+----------+------+------------+
| Report A |    1 | 0000000001 |
| Report B |    2 | 0000000010 |
        ...
| Repord H |  256 | 0100000000 |
| Report I |  512 | 1000000000 |
+----------+------+------------+

So, if $show_reports = 512 (binary of 1000000011). So the code loops through each of the report types AND'ing it to the value. So the results are :

Report A                     Report B
  0000000001                   0000000010
& 1000000011                 & 1000000011
============                 ============
  0000000001 (TRUE)            0000000010 (TRUE)



Repord H                     Report I
  0100000000                   1000000000
& 1000000011                 & 1000000011
============                 ============
  0000000000 (FALSE)           1000000000 (TRUE)

So, display_report() will be displayed for A,B, & I.

So, how does the value change? Well to add a new report one just OR's it:


To remove a value, it's AND'ed on the ones' complement of the value:


Okay, so reading back over this, it doesn't seem a good blog post. Oh well :P

Expiring Rails3 login sessions the cheap way

Okay, so for my game Hexwar I needed some way to expire the login stored in the session. So, my first stop was google and the top answers Ruby On Rails Security Guide, Sessions and cookies in Ruby on Rails, and Rails Session Timeout all seemed a bit more involved than I wanted this early in the morning. So, I'll just roll my own!

First, to understand what I need, one must understand what I have. I'm using the classic pattern of a before_filter in the application controller that routes a person to the sessions controller to force a login.


Now, I wanted a login to last one day. I may change this in the future to expire if there's no activity for a period, but for now the hard one day limit works for me. So, I just add an expiration time to the session and unset it when past.


I realize this code is in no way impressive and there's probably a more Ruby-centric way to do this, but I haven't written for my blog in a while and this is what I just finished.

A Better Hex Coordinate System

When I started working on Hexwar, I used the simple approach to displaying hexagons from the article Pixel Coordinates to Hexagonal Coordinates. The problem with this coordinate system is that it's difficult to perform functions for distance on it. I ended up walking the entire grid from the starting hex and making an array of distances. This proved faulty (due to my faulty walking algorithm) and I decided to move to the coordinate system similar to Clark Verbrugge’s Hex Grids. The major difference being that I want my hexes to point horizontally instead of vertically. (I considered using the three coordinate hex space model, but that'd require a change to a lot of my code.)

Explanation of Coordinate Systems

Understanding this, one must see there are three different coordinate systems at work here.

Hex Space

First comes the hex space. This is the game world's coordinate system. It is the one which all the game mechanics rely upon. It looks like :

Hex Space
                      __   5
                   __/D \__   4
                __/  \__/  \__   3      "Y" coord
             __/  \__/  \__/  \__   2
          __/A \__/  \__/  \__/  \__   1
       __/  \__/  \__/E \__/B \__/  \__   0
      /  \__/G \__/  \__/  \__/F \__/C \
      \__/  \__/  \__/  \__/  \__/  \__/
         \__/  \__/  \__/  \__/  \__/   5
            \__/  \__/  \__/  \__/   4
               \__/  \__/  \__/    3
                  \__/  \__/    2     "X" coord
                     \__/    1
                         0  
Such that A =(2,5); B =(4,2); C =(5,0); D =(5,5); E =(3,3); F =(4,1); G =(1,4)  

Array Space

Next is the array space. This is a translation of the hex space into an orthogonal space. I've made it the same as the original hex space I was using. It begins with (0,0) in the top left and extends positively to the right and down. It looks like :

Array Space

 __    __    __    __
/M \__/O \__/  \__/  \__
\__/N \__/  \__/  \__/  \
/  \__/  \__/  \__/  \__/
\__/  \__/  \__/  \__/  \
/P \__/R \__/  \__/  \__/
\__/Q \__/  \__/  \__/  \
/  \__/  \__/  \__/  \__/
\__/  \__/  \__/  \__/

Such that M =(0,0); N =(1,0); O =(2,0); P =(0,3); Q =(1,3); R =(2,3)

The reason for this space is that computer screens are square, not diamond shaped. The hex space as described above would be displayed such that a large percentage of the screen would be unused, or a large percentage of world would be unseen.

Screen Space

Finally is the screen space. This represents the pixels on the screen. This could also be a viewport space if I need to implement scrolling, but I currently want the entire map to appear on screen at once. This starts at (0,0) for the pixel in the top left and proceeds positively to the right and down.

Converting Between Coordinate Systems

Between Array and Hex Coordinates

Between Screen and Array Coords

Calculating the distance between two hexes

Finally for the thing that I did the switch for. This hex coordinate system allows a quick (compared to walking the whole map) calculation of distance between two hexes. It also allows for some Line-of-Site calculations, but I don't currently need those. Anyways, the code :


Oh well, that's it for now!

Why JOIN ... USING clauses can be a bad habit

So first, let me say that I do like the JOIN ... USING clauses. They make straight forward joins look a lot better. The problem is if you get into a habit of using them and doing further join filtering in the WHERE clause. Most of the time, this is perfectly okay because the relational calculus handles things nicely. But what if your SQL becomes more complicated based on certain options? Let's look at an example. (This story is based on a subtle defect I had to work on today.)

Given two tables :

users
user_id	SERIAL
some_flag	BOOLEAN

user_attributes
user_attribute_id	SERIAL
user_id	FORIEGN KEY
name	VARCHAR
value	VARCHAR

Such that users have 0..n user_attributes (don't complain about this schema design, it's just for example).

You need a report that shows all users with a certain attribute, easy :


Bam! Done. Oh wait, the product owner wants an option to display all users that don't have that attribute set. Still easy :



...and done again! You're a master programmer. Of course, product owners are never happy. Now they want another option to display all users and that have that attribute or have some_flag set. That's easy too :



And done! I'm going home.
...
...
...
What do you mean the report isn't working?

So, because of "(name='CLOWN_ATTRIBUTE' OR some_flag = TRUE)" things aren't quite working right. The OR condition allows it to connect to any row in the user_attributes table that belongs to a user with some_flag set. While one can probably use some fancy SQL logic to make this still work with the JOIN ... USING clause, I find it much easier to :



Oh well, I know to look out for one more thing now.

Case Insensitive Diff Algorithm in PHP

So, one day the business analyst wanted to compare what people where typing in as their address and the corrected/validated results we use. My first thought was "Oh that'd be easy, we just use a diff function on a report!" What I didn't think about was that most people type in the lowercase, but the corrected address are in all caps (as per Post Office specs).

Okay, so we just need a case insensitive diff algorithm, but wait, there's more. "Marshal Hollow Rd" and "Maral Hollow Rd" only show up as a tiny difference, but obviously they're completely different addresses. We needed to highlight the differences in the words more. So, now we need a case insensitive diff that judges differences based on words rather than characters.

What follows was my solution to this need. I wrote this a number of years ago, and I no longer remember much about it. I do know that I did not invent the diff algorithm. There was a comment with this link in it. Likely I just wrote what is said on that page and modified it to handle our special needs. If I read the website in the comment and studied the code, I could probably regain my understanding of this algorithm, but I don't think I really need to understand it anymore as in the intervening years I've not needed a similar algorithm since.

Here's the code!

Levenshtein Distance in Javascript

Okay, now this is an odd code snippet. I really can't remember why I needed a javascript implementation of the Levenshtein Distance algorithm. I mean, most back end languages have an implementation in their libraries that'd be far more efficient. Oh well, since I saved it, I might as well share it.

Using Zend framework MVC in a subdirectory of an existing project

I like MVC frameworks. Zend framework isn't my favorite, but my company is using [an older] Zend framework for it's mobile site. I might as well stick with it. Unfortunately, the desktop web site is still a jumbled mess of plain old PHP scripts with logic, database calls, and HTML in a single file. So what does one do when they want to develop new features in an MVC framework? Create a new virtual host just for those features? (This is how our mobile site works, it's in /var/sites/example.com/mobile) Create your own framework or use one that was designed for standalone use? No, you figure out how to use the newest version of the Zend framework from within a subdirectory of the current site!!

Research

First, a quick trip to google.. this looks promising Zend Framework Run in a Subdirectory ... it's a dead link.. crap.. Well, I guess I should just try it and see what happens.

Experiment

I used the zf.sh command line tool to create a ZF project in a subdirectory /var/sites/example.com/zf_test. Changed my .htaccess file to include "RewriteBase /zf_test/public/" and then fired up Chrome and hit the URL.

Of course I got a blank white screen and a PHP error message. The odd part was the PHP error had a call stack in the mobile site's bootstrap file.. hmm... So the problem was that APPLICATION_PATH and APPLICATION_ENV where already being defined in the mobile site's code and for some reason (I'm still not sure why) the mobile site's bootstrap was being called. So I changed them to DESKTOP_APPLICATION_PATH and DESKTOP_APPLICATION_ENV in zf_test/public/index.php and zf_test/config/application.ini.

Save, upload, restart apache for good measure, and hit refresh.

PHP Fatal error: Undefined class constant 'EXCEPTION_NO_ROUTE' in ... Hmm... a quick trip to google helped me find this was because the version of zend framework on the server on the one on my development box where a bit off. So, can I include the full ZF library in the project locally like I can with Rails? Yep, and almost as easily. I simply copied the
library/Zend folder from my local install to zf_test/library, uploaded, refreshed :

PHP Fatal error: Cannot redeclare class zend_loader in ... Okay, so something is initializing the old zend loader before my new zend framework can (dang "php_value auto_prepend_file ..."). Well, there can't be that many differences between the versions of zend loader can there? Let's just get rid of the new one and let the old one handle loading.

rm -rf /var/sites/example.com/zf_test/library/Zend/Loader*

Refresh and ... An error occurred Page not found

I'm starting to get annoyed. Okay, it looks like it's actually loading something in the App. After a bit of playing around, I set resources.frontController.params.displayExceptions = 1 and find that it's searching for a controller called zf_test. That's what I was afraid would stop the subdirectory thing from working. I google and find Base URL and subdirectories that sounds promising. So, added to index.php :

<?php
$ctrl  = Zend_Controller_Front::getInstance();
$router = $ctrl->getRouter();
$router->setRewriteBase('/zf_test');

PHP Fatal error: Call to undefined method Zend_Controller_Router_Rewrite::setRewriteBase() in ... &^$%$#&@$#!^&*!! I dig into the ZF front controller code and find it has a function setBaseUrl() that is passed to the router. Well, that's easy.

<?php
$ctrl  = Zend_Controller_Front::getInstance();
$ctrl->setBaseUrl('/zf_test/');

Save, upload, refresh...

Success!!

Find something else to work on

Okay, now I'm tired of playing with Zend Framework in a subdirectory of a project. I'll implement something in it later.