How to Bitwise compare a String

Question

I am working on a function that takes in a series of permission strings, less than 255 characters and assigns them to an entity. Each string assigned is unique, but there are so many that dropping them into an array, serializing them and pushing into a database and pulling them out later and de-serializing them or recalculating from a query every time there is a load has been causing delay problems. Especially with inherited permissions.

So I was thinking of taking the string, generating a mask from it then OR'ing into the permissions glob. As more permissions are added continue to OR them to the glob. Then when you need to verify the permission AND the string against the glob.

The question is how to generate the mask. At first I was thinking of just hashing the string for a unique mask, however it is conceivable, but I don't know how likely, that as more hash values are OR'ed onto the glob the potential for filling the glob in such a way that and AND test with a permission they don't have, yet return a true value.

if($glob&&$test == $test)

The other option would be just auto-number the permission strings and have their mask be 2^auto-number. But that would limit the number of permission strings to around 64ish.

What I really want is a glob of some sort that I can pull out of a database once and associate it with the user. Then test that glob against a string or associated value representing a permission set.

Answer 1

Since each string is unique, why not load them from the database once into a hashtable (or similiar) and cache them for the duration of the user session?

Answer 2

The essential thought here is this:

The other option would be just auto-number the permission strings and have their mask be 2^auto-number. But that would limit the number of permission strings to around 64ish.

If your permission strings are truly independent of one another, then, obviously, whatever you do, you will need at least 1 bit to store whether or not a permission exists. There's no way around that (it is 1 bit of actual, independent, information).

A possible solution to your issue would be to encode the permissions in a compact manner (say assign an Int16 to each), and store the list of the user's permission as a binary array of all his permissions. It's ugly-ish, but it would vaguely solve your problem. Depending on the DB you might actually have some kind of array/collection column types available that could do this for you.

Answer 3

I found an interesting solution but I am unsure if how logically correct it is because I am not very familiar with how PHP handles string data. I decided to cut away everything and try to do it straight without any hashing or assigning or whatnot and just do bitwise operations on strings. It seemed to work, but I am not sure I can prove my logic true enough.

$key1 = "Access to Black Box";
$key2 = "Managing Black Box";
$key3 = "Nothing too see here";
$key3a = "Nothingg B";
$key3b = "too see";
$glob = "";

$glob = $glob | $key1;
if(($glob & $key1) == $key1){echo "<p>Key one exists in glob: " . $glob;}

$glob = $glob | $key2;
if(($glob & $key2) == $key2){echo "<p>Key one exists in glob: " . $glob;}

if(($glob & $key3) == $key3){echo "<p>Key three exists in glob: " . $glob;}
else{echo "<p>Key three does not exists in glob: " . $glob;}

$glob = $glob | $key3;
if(($glob & $key3) == $key3){echo "<p>Key three exists in glob: " . $glob;}

if(($glob & $key3a) == $key3a){echo "<p>Key three a exists in glob: " . $glob;}

if(($glob & $key3b) == $key3b){echo "<p>Key three b exists in glob: " . $glob;} 
else{echo "<p>Key three b does not exists in glob: " . $glob;}

Outputs:

Key one exists in glob: Access to Black Box
Key two exists in glob: Mcoew{nwobnmckkbox
Key three does not exists in glob: Mcoew{nwobnmckkbox
Key three exists in glob: Oomowoomsooboze
Key three a exists in glob: Oomowoomsooboze
Key three b does not exists in glob: Oomowoomsooboze

So this works, but what would I be looking at collision wise? With key3a I showed that a string that has a combination of characters that match positions with characters in other keys I can get a false positive. But can I get around it with strict rules on the permission strings? Each resource type is named and each resource type has a limited number of associated permissions. So something like "Blog....Write Post", "Blog...Publish Post", "Blog....Moderate Post", "Podcast.......Upload", "Podcast.......Publish" to compensate for the increasing probability of a collision since string length has little impact on PHP's speed.