Phil CK

Better Decision Tables

Last updated on

I covered a simple way of dealing with decisions, but there is an issue with it. for some things you just dont care about, you want a null type, but or’ing bits together doesn’t give you that. This is a bigger example on how you might want to deal with bits you don’t care about.

Say we want to execute tasks given certain criteria.

We want to execute these tasks on the left, when the requirements have been met.

  • 1 is when a bit must be set
  • 0 is when a bit must be clear
  • ‘-’ when we don’t care if the bit is set or not
ruleinputrenderplayersenemiesmenu_open
update_player1-1-0
update_enmies--110
update_menu1---1
play_menu_audio1---1
render-1---
game_timer--1-0

We can add support for bits ‘-’ we dont care about by having an ignore mask.

/* we can't represent a bit as yes/no/null, so we have a enum */
enum state {
        STATE_NULL,
        STATE_ON,
        STATE_OFF,
};


struct task {
        uint32_t ign_bits; /* bits we don't care about */
        uint32_t req_bits; /* bits that must be set */

        void(*task_fn)(); /* task function */
};


void
task_init(struct task *t, enum state *conditions) {
        int i;

        uint32_t ibits = (uint32_t)0;
        uint32_t rbits = (uint32_t)-1;

        /* set bits */

        for(i = 0; i < 5; ++i) {
                if(conditions[i] == STATE_NULL) {
                        ibits |= 1 << i;
                }

                else if(conditions[i] == STATE_ON) {
                        rbits = 1 << i;
                }

                else if(conditions[i] == STATE_OFF) {
                        rbits &= ~(1 << i);
                }
        }

        t->ign_bits = ibits;
        t->req_bits = rbits;
}

So if we had an array of tasks like …

/* possible tasks based on inputs */
struct task tasks[6];

/* setup the tasks */

/* update player */ {
        enum state task_state[5] = {
                STATE_ON, STATE_NULL, STATE_ON, STATE_NULL, STATE_OFF,
        };

        task_init(&tasks[0], task_state);
        tasks[0].task_fn = task_update_player; }

/* update enemies */ {
        enum state task_state[5] = {
                STATE_NULL, STATE_NULL, STATE_ON, STATE_ON, STATE_OFF,
        };

        task_init(&tasks[1], task_state);
        tasks[1].task_fn = task_update_enemies; }

/* update menu */ {
        enum state task_state[5] = {
                STATE_ON, STATE_NULL, STATE_NULL, STATE_NULL, STATE_ON,
        };

        task_init(&tasks[2], task_state);
        tasks[2].task_fn = task_update_menu; }

/* play menu audio */ {       
        enum state task_state[5] = {
                STATE_ON, STATE_NULL, STATE_NULL, STATE_NULL, STATE_ON,
        };

        task_init(&tasks[3], task_state);
        tasks[3].task_fn = task_play_menu_audio; }

/* render */ {
        enum state task_state[5] = {
                STATE_NULL, STATE_ON, STATE_NULL, STATE_NULL, STATE_NULL,
        };

        task_init(&tasks[4], task_state);
        tasks[4].task_fn = task_render; }

/* game timer */ {
        enum state task_state[5] = {
                STATE_NULL, STATE_NULL, STATE_ON, STATE_NULL, STATE_OFF,
        };

        task_init(&tasks[5], task_state);
        tasks[5].task_fn = task_game_timer; }

We can check to see if we want to submit the task for processsing by clearing the bits we don’t care about, and comparing the rest.

/* world state set by various data */

uint32_t world_state = 0;

// world_state |= 1 << 0; /* input */
world_state |= 1 << 1; /* render */
world_state |= 1 << 2; /* player */
world_state |= 1 << 3; /* enemies */
world_state |= 1 << 4; /* menu open */

/* loop across tasks and check to see if the data reqs are met */
int i;
for(i = 0; i < 6; ++i) {
        uint32_t ibits = tasks[i].ign_bits;
        uint32_t rbits = tasks[i].req_bits;

        /* clear the bits we dont care about */
        uint32_t cleared = world_state;
        cleared &= ~ibits;

        /* submit the task if the req_bits match */
        if(cleared == rbits) {
                tasks[i].task_fn();
        }

}

Full Code

#include <stdint.h>
#include <stdio.h>

/*
        We want to execute these tasks on the left, when the requirements
        have been met. 
        1 is when a bit must be set
        0 is when a bit must be clear
        - is when we don't care if the bit is set or not

                        | input | renderables | players | enemies | menu_open 
        update_player   | 1     | -           | 1       | -       | 0
        update_enmies   | -     | -           | 1       | 1       | 0
        update_menu     | 1     | -           | -       | -       | 1
        play_menu_audio | 1     | -           | -       | -       | 1
        render          | -     | 1           | -       | -       | -         
        game_timer      | -     | -           | 1       | -       | 0
*/


/* we can't represent a bit as yes/no/null, so we have a enum */
enum state {
        STATE_NULL,
        STATE_ON,
        STATE_OFF,
};


struct task {
        uint32_t ign_bits; /* bits we don't care about */
        uint32_t req_bits; /* bits that must be set */

        void(*task_fn)(); /* task function */
};


void
task_init(struct task *t, enum state *conditions) {
        int i;

        uint32_t ibits = (uint32_t)0;
        uint32_t rbits = (uint32_t)-1;

        /* set bits */

        for(i = 0; i < 5; ++i) {
                if(conditions[i] == STATE_NULL) {
                        ibits |= 1 << i;
                }

                else if(conditions[i] == STATE_ON) {
                        rbits = 1 << i;
                }

                else if(conditions[i] == STATE_OFF) {
                        rbits &= ~(1 << i);
                }
        }

        t->ign_bits = ibits;
        t->req_bits = rbits;
}


/* https://stackoverflow.com/questions/111928/is-there-a-printf-converter-to-print-in-binary-format */
void printB(size_t const size, void const * const ptr)
{
    unsigned char *b = (unsigned char*) ptr;
    unsigned char byte;
    int i, j;

    for (i=size-1;i>=0;i--)
    {
        for (j=7;j>=0;j--)
        {
            byte = (b[i] >> j) & 1;
            printf("%u", byte);
        }
    }
    puts("");
}


/* tasks */
void task_update_player()       { printf("task_update_player()\n");     }
void task_update_enemies()      { printf("task_update_enemies()\n");    }
void task_update_menu()         { printf("task_update_menu()\n");       }
void task_play_menu_audio()     { printf("task_play_menu_audio()\n");   }
void task_render()              { printf("task_render()\n");            }
void task_game_timer()          { printf("task_game_timer()\n");        }


int
main() {

        /* possible tasks based on inputs */
        struct task tasks[6];

        /* setup the tasks */
        
        /* update player */ {
                enum state task_state[5] = {
                        STATE_ON, STATE_NULL, STATE_ON, STATE_NULL, STATE_OFF,
                };

                task_init(&tasks[0], task_state);
                tasks[0].task_fn = task_update_player; }

        /* update enemies */ {
                enum state task_state[5] = {
                        STATE_NULL, STATE_NULL, STATE_ON, STATE_ON, STATE_OFF,
                };

                task_init(&tasks[1], task_state);
                tasks[1].task_fn = task_update_enemies; }

        /* update menu */ {
                enum state task_state[5] = {
                        STATE_ON, STATE_NULL, STATE_NULL, STATE_NULL, STATE_ON,
                };

                task_init(&tasks[2], task_state);
                tasks[2].task_fn = task_update_menu; }

        /* play menu audio */ {       
                enum state task_state[5] = {
                        STATE_ON, STATE_NULL, STATE_NULL, STATE_NULL, STATE_ON,
                };

                task_init(&tasks[3], task_state);
                tasks[3].task_fn = task_play_menu_audio; }

        /* render */ {
                enum state task_state[5] = {
                        STATE_NULL, STATE_ON, STATE_NULL, STATE_NULL, STATE_NULL,
                };

                task_init(&tasks[4], task_state);
                tasks[4].task_fn = task_render; }

        /* game timer */ {
                enum state task_state[5] = {
                        STATE_NULL, STATE_NULL, STATE_ON, STATE_NULL, STATE_OFF,
                };

                task_init(&tasks[5], task_state);
                tasks[5].task_fn = task_game_timer; }


        /* world state set by various data */

        uint32_t world_state = 0;
        // world_state |= 1 << 0; /* input */
        world_state |= 1 << 1; /* render */
        world_state |= 1 << 2; /* player */
        world_state |= 1 << 3; /* enemies */
        world_state |= 1 << 4; /* menu open */

        /* loop across tasks and check to see if the data reqs are met */
        int i;
        for(i = 0; i < 6; ++i) {
                uint32_t ibits = tasks[i].ign_bits;
                uint32_t rbits = tasks[i].req_bits;

                /* clear the bits we dont care about */
                uint32_t cleared = world_state;
                cleared &= ~ibits;

                /* submit the task if the req_bits match */
                if(cleared == rbits) {
                        printf("Submit: ");
                        tasks[i].task_fn();
                } else {
                        printf("Don't Submit: ");
                        tasks[i].task_fn();
                }

                /* output state of the world */
                printf("World State: \t");
                printB(sizeof(world_state), &world_state);
                printf("Cleared State: \t");
                printB(sizeof(cleared), &cleared);
                printf("Required: \t");
                printB(sizeof(rbits), &rbits);
                printf("Ignore: \t");
                printB(sizeof(ibits), &ibits);

                printf("--\n");
        }

        return 0;
}

build and go

cc better_decision_table.c && ./a.out

Outputs

Don't Submit: task_update_player()
World State:    00000000000000000000000000011110
Cleared State:  00000000000000000000000000010100
Required:       00000000000000000000000000000100
Ignore:         00000000000000000000000000001010
--
Don't Submit: task_update_enemies()
World State:    00000000000000000000000000011110
Cleared State:  00000000000000000000000000011100
Required:       00000000000000000000000000001000
Ignore:         00000000000000000000000000000011
--
Submit: task_update_menu()
World State:    00000000000000000000000000011110
Cleared State:  00000000000000000000000000010000
Required:       00000000000000000000000000010000
Ignore:         00000000000000000000000000001110
--
Submit: task_play_menu_audio()
World State:    00000000000000000000000000011110
Cleared State:  00000000000000000000000000010000
Required:       00000000000000000000000000010000
Ignore:         00000000000000000000000000001110
--
Submit: task_render()
World State:    00000000000000000000000000011110
Cleared State:  00000000000000000000000000000010
Required:       00000000000000000000000000000010
Ignore:         00000000000000000000000000011101
--
Don't Submit: task_game_timer()
World State:    00000000000000000000000000011110
Cleared State:  00000000000000000000000000010100
Required:       00000000000000000000000000000100
Ignore:         00000000000000000000000000001011

This is a more powerful but more verbose way of doing decision tables, it may suit your needs, it may not.