You Are Here Home > July 2009

July 2009

How to write a permission system using bits and bitwise operations in PHP

I wrote this in PHP but you can use the same concept in other languages, I also assume an understanding of bits, bytes, binary to decimal conversion and vice-versa and bitwise operations on numbers like ‘or’, ‘and’ and ‘xor’ etc. if you have no idea, search and read about these first. You don’t have to be a guru but you should have an idea. Here are some pages to get you started:

http://en.wikipedia.org/wiki/Byte
http://en.wikipedia.org/wiki/Bitwise_operation
http://us.php.net/manual/en/language.operators.bitwise.php
Some binary to decimal calculators to make it easier

We will use simple numbers to represent different permissions and as you might know a number is a collection of bytes. For example: an integer is usually 4 bytes. Although you don’t have to worry about the size of a number in a high level language like PHP but a little understanding of representation of numbers will help you better understand this technique.

So let’s assume when I say:

<?php
 
	$user_perms = 7;
 
?>

Internally the variable $user_perms looks like this:

|0|0|0|0|0|0|0|0|0|0|0|0|0|1|1|1|

This is a 2 byte representation of number 7, although, it might not look like this internally – it looks similar. Just assume this for now.

Let’s say that your application supports 4 functions that a user can use:

1 – Post a blog post
2 – Comment on blog posts
3 – Edit posts
4 – Delete posts

Normally, you could have 4 fields in your database table (structure or whatever) for a user titled:

1 – can_post
2 – can_comment
3 – can_edit
4 – can_delete

This is not good, 4 additional fields for your user table and who knows, what if your application has 100 functions? Do you want to add 100 fields to your user table?

With bits, you can have only 1 column and track all the permissions.

1 – perms

To do this, we will have to assign numbers for each of the functions: (Tip: use one of the calculators in the above list ;) )

1 – Post a blog post |0|0|0|0|0|0|0|1| is 1 in decimal
2 – Comment on blog posts |0|0|0|0|0|0|1|0| is 2 in decimal
3 – Edit posts |0|0|0|0|0|1|0|0| is 4 in decimal
4 – Delete posts |0|0|0|0|1|0|0|0| is 8 in decimal

So you could have an array like this:

<?php
 
	$perms = array(
		'can_post' => 1,
		'can_comment' => 2,
		'can_edit' => 4,
		'can_delete' => 8
	);
 
?>

Almost there, let’s look at user’s perms field now.

I hope you know about bitwise ‘or’, when you ‘or’ 1 and 1 you get 1; 0 ‘or’ 1 is 1; 1 ‘or’ 0, is 1 and finally 0 ‘or’ 0 is 0, it’s just like the meaning of ‘or’ in the English language.

Similarly, bitwise ‘and’; when you ‘and’ 1 and 1 you get 1; 0 ‘and’ 1 is 0; 1 ‘and’ 0, is 0 and finally 0 ‘and’ 0 is 0, again it’s just like the meaning of ‘or’ in the English language.

Bitwise ‘xor’; when you ‘xor’ 1 and 1 you get 0; 0 ‘xor’ 1 is 1; 1 ‘xor’ 0, is 1 and finally 0 ‘xor’ 0 is 0.

So suppose you want to give a user permissions to post a blog post, post a comment and edit posts but not delete posts, you do it like this:

<?php
 
	$user_perms = $perms['can_post'] | $perms['can_comment'] | $perms['can_edit'];
 
?>

Note that, in PHP ‘|’ means ‘or’, so what just happened is something like this:

|0|0|0|0|0|0|0|1| ‘or’
|0|0|0|0|0|0|1|0| ‘or’
|0|0|0|0|0|1|0|0|
_______________________
|0|0|0|0|0|1|1|1|

Now $user_perms has the value 7 and |0|0|0|0|0|1|1|1| in it internally.

Suppose that this is on top of your post_blog.php or where ever you want to handle permissions for posting a blog, the only thing you need to do is:

<?php
 
	if ($user_perms & $perms['can_post']) {
		/* He/She has permissios to do this */
	} else {
		/* He/She doesn't */
	}
 
?>

In PHP ‘&’ is for bitwise ‘and’, please also note that ‘&&’ is logical ‘and’ and doesn’t operate on individual bits.

This is exactly what just happened:

|0|0|0|0|0|1|1|1| ‘and’
|0|0|0|0|0|0|0|1|
_______________________
|0|0|0|0|0|0|0|1|

So that’s ‘one’ not ’0′, which means ‘if’ passes and the user has permissions to do this. But when it comes to deleting posts:

<?php
 
	if ($user_perms & $perms['can_delete']) {
		/* He/She does permissios to do this */
	} else {
		/* He/She doesn't */
	}
 
?>

Thus:

|0|0|0|0|0|1|1|1| ‘and’
|0|0|0|0|1|0|0|0|
_______________________
|0|0|0|0|0|0|0|0|

It’s ‘zero’ so ‘if’ fails and you show an error message or whatever it is you do.

To add ‘delete’ permissions, you use ‘or’ again:

<?php
 
	$user_perms |= $perms['can_delete'];
 
?>

So this happens:

|0|0|0|0|0|1|1|1| ‘or’
|0|0|0|0|1|0|0|0|
_______________________
|0|0|0|0|1|1|1|1|

To take away permissions you use ‘xor’:

<?php
 
	$user_perms ^= $perms['can_delete'];
 
?>

And this will happen:

|0|0|0|0|1|1|1|1| ‘xor’
|0|0|0|0|1|0|0|0|
_______________________
|0|0|0|0|0|1|1|1|

And delete permissions are gone!

Now let’s take away post permissions:

<?php
 
	$user_perms ^= $perms['can_post'];
 
?>

Thus:

|0|0|0|0|0|1|1|1| ‘xor’
|0|0|0|0|0|0|0|1|
_______________________
|0|0|0|0|0|1|1|0|

So this was just the basics, you can build on this and do more once you understand.

I hope this post will help someone :)

How to write a permission system using bits and bitwise operations in PHP
Comments (10)   Filed under: PHP,Programming,Security,Web Development   Posted by: Hamid

Implementation of a Vector data structure in C

I use Python a lot but it’s very slow in some cases which I then use C because it can be 1,000s X faster than Python.

Here is a Vector that I just wrote to use in my new project:

vector.h

/**
 * Hamid Alipour
 */
 
#ifndef __VECTORH__
#define __VECTORH__
 
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
 
#define VECTOR_INIT_SIZE    4
#define VECTOR_HASSPACE(v)  (((v)->num_elems + 1) <= (v)->num_alloc_elems)
#define VECTOR_INBOUNDS(i)	(((int) i) >= 0 && (i) < (v)->num_elems)
#define VECTOR_INDEX(i)		((char *) (v)->elems + ((v)->elem_size * (i)))
 
typedef struct _vector {
	void *elems;
	size_t elem_size;
	size_t num_elems;
	size_t num_alloc_elems;
    void (*free_func)(void *);
} vector;
 
extern void vector_init(vector *, size_t, size_t, void (*free_func)(void *));
extern void vector_dispose(vector *);
extern void vector_copy(vector *, vector *);
extern void vector_insert(vector *, void *, size_t index);
extern void vector_insert_at(vector *, void *, size_t index);
extern void vector_push(vector *, void *);
extern void vector_pop(vector *, void *);
extern void vector_shift(vector *, void *);
extern void vector_unshift(vector *, void *);
extern void vector_get(vector *, size_t, void *);
extern void vector_remove(vector *, size_t);
extern void vector_transpose(vector *, size_t, size_t);
extern size_t vector_length(vector *);
extern size_t vector_size(vector *);
extern void vector_get_all(vector *, void *);
extern void vector_cmp_all(vector *, void *, int (*cmp_func)(const void *, const void *));
extern void vector_qsort(vector *, int (*cmp_func)(const void *, const void *));
static void vector_grow(vector *, size_t);
static void vector_swap(void *, void *, size_t);
 
#endif

And vector.c

/**
 * Hamid Alipour
 */
 
#include "vector.h"
 
extern void vector_init(vector *v, size_t elem_size, size_t init_size, void (*free_func)(void *))
{
	v->elem_size = elem_size;
	v->num_alloc_elems = (int) init_size > 0 ? init_size : VECTOR_INIT_SIZE;
	v->num_elems = 0;
	v->elems = malloc(elem_size * v->num_alloc_elems);
	assert(v->elems != NULL);
	v->free_func = free_func != NULL ? free_func : NULL;
}
 
extern void vector_dispose(vector *v)
{
	size_t i;
 
	if (v->free_func != NULL) {
		for (i = 0; i < v->num_elems; i++) {
			v->free_func(VECTOR_INDEX(i));
		}
	}
 
	free(v->elems);
}
 
 
extern void vector_copy(vector *v1, vector *v2)
{
	v2->num_elems = v1->num_elems;
	v2->num_alloc_elems = v1->num_alloc_elems;
	v2->elem_size = v1->elem_size;
 
	v2->elems = realloc(v2->elems, v2->num_alloc_elems * v2->elem_size);
	assert(v2->elems != NULL);
 
	memcpy(v2->elems, v1->elems, v2->num_elems * v2->elem_size);
}
 
extern void vector_insert(vector *v, void *elem, size_t index)
{
	void *target;
 
	if ((int) index > -1) {
		if (!VECTOR_INBOUNDS(index))
			return;
		target = VECTOR_INDEX(index);
	} else {
		if (!VECTOR_HASSPACE(v))
			vector_grow(v, 0);
		target = VECTOR_INDEX(v->num_elems);
		v->num_elems++; /* Only grow when adding a new item not when inserting in a spec indx */
	}
 
	memcpy(target, elem, v->elem_size);
}
 
extern void vector_insert_at(vector *v, void *elem, size_t index)
{
	if ((int) index < 0)
		return;
 
	if (!VECTOR_HASSPACE(v))
		vector_grow(v, 0);
 
	if (index < v->num_elems)
		memmove(VECTOR_INDEX(index + 1), VECTOR_INDEX(index), (v->num_elems - index) * v->elem_size);
 
	/* 1: we are passing index so insert won't increment this 2: insert checks INBONDS... */
	v->num_elems++;
 
	vector_insert(v, elem, index);
}
 
extern void vector_push(vector *v, void *elem)
{
	vector_insert(v, elem, -1);
}
 
extern void vector_pop(vector *v, void *elem)
{
	memcpy(elem, VECTOR_INDEX(v->num_elems - 1), v->elem_size);
	v->num_elems--;
}
 
extern void vector_shift(vector *v, void *elem)
{
	memcpy(elem, v->elems, v->elem_size);
	memmove(VECTOR_INDEX(0), VECTOR_INDEX(1), v->num_elems * v->elem_size);
 
	v->num_elems--;
}
 
extern void vector_unshift(vector *v, void *elem)
{
	if (!VECTOR_HASSPACE(v))
		vector_grow(v, v->num_elems + 1);
 
	memmove(VECTOR_INDEX(1), v->elems, v->num_elems * v->elem_size);
	memcpy(v->elems, elem, v->elem_size);
 
	v->num_elems++;
}
 
extern void vector_transpose(vector *v, size_t index1, size_t index2)
{
	vector_swap(VECTOR_INDEX(index1), VECTOR_INDEX(index2), v->elem_size);
}
 
static void vector_grow(vector *v, size_t size)
{
	if (size > v->num_alloc_elems)
		v->num_alloc_elems = size;
	else
		v->num_alloc_elems *= 2;
 
	v->elems = realloc(v->elems, v->elem_size * v->num_alloc_elems);
	assert(v->elems != NULL);
}
 
extern void vector_get(vector *v, size_t index, void *elem)
{
	assert((int) index >= 0);
 
	if (!VECTOR_INBOUNDS(index)) {
		elem = NULL;
		return;
	}
 
	memcpy(elem, VECTOR_INDEX(index), v->elem_size);
}
 
extern void vector_get_all(vector *v, void *elems)
{
	memcpy(elems, v->elems, v->num_elems * v->elem_size);
}
 
extern void vector_remove(vector *v, size_t index)
{
	assert((int) index > 0);
 
	if (!VECTOR_INBOUNDS(index))
		return;
 
	memmove(VECTOR_INDEX(index), VECTOR_INDEX(index + 1), v->elem_size);
	v->num_elems--;
}
 
extern void vector_remove_all(vector *v)
{
	v->num_elems = 0;
	v->elems = realloc(v->elems, v->num_alloc_elems);
	assert(v->elems != NULL);
}
 
extern size_t vector_length(vector *v)
{
	return v->num_elems;
}
 
extern size_t vector_size(vector *v)
{
	return v->num_elems * v->elem_size;
}
 
extern void vector_cmp_all(vector *v, void *elem, int (*cmp_func)(const void *, const void *))
{
	size_t i;
	void *best_match = VECTOR_INDEX(0);
 
	for (i = 1; i < v->num_elems; i++)
		if (cmp_func(VECTOR_INDEX(i), best_match) > 0)
			best_match = VECTOR_INDEX(i);
 
	memcpy(elem, best_match, v->elem_size);
}
 
extern void vector_qsort(vector *v, int (*cmp_func)(const void *, const void *))
{
	qsort(v->elems, v->num_elems, v->elem_size, cmp_func);
}
 
static void vector_swap(void *elemp1, void *elemp2, size_t elem_size)
{
	void *tmp = malloc(elem_size);
 
	memcpy(tmp, elemp1, elem_size);
	memcpy(elemp1, elemp2, elem_size);
	memcpy(elemp2, tmp, elem_size);
 
             free(tmp); /* Thanks to gromit */
}

It works :) I will write another post with some example usage soon…

Notice that, all the functions that return a value, return it through their arguments and not the “return” statement, this is because I wanted the client to be responsible for allocating/freeing memory for these variables and that makes everyone’s job easier.

As always, I’m open to criticism/ideas and please use it at your own risk.

Implementation of a Vector data structure in C
Comments (9)   Filed under: C Programming,Data Structures,Low Level,Programming   Posted by: Hamid
Older Posts »