28th September, 2006
Bitmasking 101
Thursday, 12:36 pm in CodeGirl
I totally did bitmasked permissions in sk.log yesterday; it’s something I’ve been putting off pretty much since I first started writing the damn thing, but have never gotten around to doing because I didn’t really understand the maths behind it. Some backstory; there are four levels of permission for all items (mainly posts and comments) at sk.log. There’s an ‘open’ permissions, viewable by everyone, a ‘closed’ permission viewable by no-one (except the site admin and the item author) and a registered-only permission viewable by, well, registered users only. I always knew I wanted to drill down the registered only into a LiveJournal-style system of groups, and I always wanted to do it with bitmasks (rather than an extra database table). I always knew ‘visually’ how bitmasks work. So say you have a a mask of 00000, now pretend that each of those zeroes is one ‘group’. Say I want to ‘set’ groups 1, 3 and 4; ie. these groups will be able to view a particular post, etc. That would then look like 11010 (going right-to-left starting at 0). 11010 in decimals is 26 (2^1 + 2^3 + 2^4), which is the bitmask number. If I have a personal bitmask of 00110 (2^1 + 2^3 = 6), then I can compare the two like so:
11010
00110
=====
00010
Because both have a 1 in the same column, then the mask ‘matches’ and I have permission to see… whatever it is I’m seeing.
Unfortunatley, I had no idea how to do this in code.
Luckily for me, it’s really, really easy! No-one ever uses logical AND or OR (& and | respectivley), but that’s what they’re there to do. A logical OR will give you the ‘combination’ of two binary numbers:
01011 |
10000
=====
11011
Whereas a logical AND will give you the ‘overlap’ of the two:
01011 &
10001
=====
00001
Obviously, logical AND is the awesome, no-thinking-involved choice forcomparing bitmasks. If the result of a logical AND between two numbers is greater than zero, then they ‘match’. The OR comes in handy, too. I’m not exactly sure why, but I’ve read that, when forming a bitmask, you should use logical OR as opposed to addition.
The really funky part of bitmasking is that you can also use it in MySQL queries:
SELECT * FROM `sometable` WHERE ( field1 & field2 ) != 0;
Anyway, because everyone loves some code, here are the two functions I wrote for sk.log:
<?php
// make a bitmask for an item
// in this case, $pmask is an array of decimals (1,2,3,...)
// these decimals should be used as the 'powers' for the
// bitmask
function doBitmask( $pmask ){
if( empty( $pmask ) )
return 0;
$mask = 0;
foreach( $pmask as $v )
$mask |= (1 << $v); // equivalent to: $mask = $mask | pow( 2, $v );
return $mask;
}
// check an item's bitmask ($pmask) against a user's mask ($umask)
function getBitmask( $pmask, $umask ){
if( ( $pmask & $umask ) != 0 )
return true;
}
?>
It should be noted that doBitmask is a ‘lazy’ function and doesn’t check for valid input. Feeding it non-integers will give you a result of 1. The other thing is that, with bitmasking, there are a finite number of groups (‘bits’) that you can have in any one system. It’s probably going to be either 16 (ie. 0,..,15) or 32 (0,…,31); this is a limitation of the underlying computer or language archetecture with how many bits it uses to define an integer.
- « Previous
- Next »