Multi-layer bitmap lookup table method

In embedded operating systems, especially real-time operating systems, bitmap methods are often used to solve the task readiness and find the highest priority quickly, that is, by looking up all possibilities, it can be realized. For a small system like uC/OS-II with 64 (2^8) priority tasks, the corresponding highest priority value can be obtained by obtaining x, y, and in the process of looking up the table, there are only 256 possibilities, which can be quickly realized by a simple table lookup, but when the number of task priorities is greater than 64, how can it be realized? Because the table lookup is not so easy at this time. When there are 16 bits, 2^16=65536, that is, there are 65536 possibilities. This data table is too large and therefore is not the form we consider. So how to determine it? At this time, the hierarchical form can be used to achieve it more quickly. When there are 64 tasks, a ready table can be used first. Each bit represents a task priority. In addition, a flag variable is prepared. Each bit represents a specific group. Each group has eight data. Through this x, y form, the search can be quickly realized. When there are 64 tasks, we can try to add one more dimension z to represent different tasks, that is, to achieve layering, divided into three layers in total, so that through this multi-layer form, we can quickly determine x, y, z through the use of the same query table (256 possibilities), and then get the highest priority number. This three-layer form can support an operating system with up to 512 priority numbers. When there are more than this situation, it is necessary to increase the number of layers again.

The specific implementation is as follows:

Each bit of z corresponds to 1 y, which means there are 8 ys in total.

Each bit of y corresponds to one x, which means a total of 8*8 xs.

Each x corresponds to 8 task priority numbers. In this way, the priority can be set by x, y, and z.

Therefore, a structure can be defined in the following form:

 

    #ifndef __HIGH_BITMAP_H_H__
    #define __HIGH_BITMAP_H_H__

    #define LENGTH_HIGHLAYER 8
    #define LENGTH_BYTE 8
    typedef unsigned char Byte;

    typedef struct
    {
        Byte high_Layer;
        Byte mid_Layer[LENGTH_HIGHLAYER];
        Byte low_Layer[LENGTH_HIGHLAYER*LENGTH_BYTE];
    }BitMaps;

    #ifdef __cplusplus
    extern "C"
    {
    #endif

    void inital_bitmap(BitMaps *bitmap);
    void set_bitmap(BitMaps *bitmap,int prio);
    int calculate_high_prio(BitMaps *bitmap);

    #ifdef __cplusplus
    }
    #endif

    #endif

The basic operation functions are as follows:

 

 

    #include"high_bitmap.h"
    #include

    int const OSUnMapTbl[256] = {
         0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x00 to 0x0F */    
            4, 0 , 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x10 to 0x1F */
            5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x20 to 0x2F */    
            4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2 , 0, 1, 0, /* 0x30 to 0x3F */
            6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x40 to 0x4F */
            4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x50 to 0x5F */
            5, 0, 1, 0, 2, 0 , 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x60 to 0x6F */
            4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x70 to 0x7F */
            7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x80 to 0x8F */
            4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x90 to 0x9F */
            5, 0, 1, 0 , 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xA0 to 0xAF */
            4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xB0 to 0xBF */
            6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 , /* 0xC0 to 0xCF */
            4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xD0 to 0xDF */
            5, 0 , 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xE0 to 0xEF */    
            4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 /* 0xF0 to 0xFF */        
    };

    void inital_bitmap(BitMaps *bitmap)
    {
        int i = 0;
        if(NULL == bitmap)
        {
            return;
        }

        bitmap->high_Layer = 0x00;
        for(; i < sizeof(bitmap->mid_Layer); ++ i)
        {
            bitmap->mid_Layer[i] = 0x00;
        }

        for (i = 0; i < sizeof(bitmap->low_Layer); ++ i)
        {
            bitmap->low_Layer[i] = 0x00;
        }
    }

    void set_bitmap(BitMaps *bitmap,int prio)
    {
        int x,y,z;
        if(NULL == bitmap || prio >= 512)
        {
            return ;
        }

        z = (prio >> 6)& 0x7;
        bitmap->high_Layer |= 1<         
        y = (prio >> 3) & 0x7;
        bitmap->mid_Layer[z] |= 1<

        x = prio & 0x7;
        bitmap->low_Layer[z*8+y] |= 1<     }

    int calculate_high_prio(BitMaps *bitmap)
    {
        int x,y,z;

        if(NULL == bitmap)
        {
            return -1;
        }

        z = OSUnMapTbl[bitmap->high_Layer];
        y = OSUnMapTbl[bitmap->mid_Layer[z]];
        x = OSUnMapTbl[bitmap->low_Layer[(z << 3)+y]];

        z = (z << 6) + (y << 3) + x;

        return z;
    }

This layered implementation can easily solve the problem of multiple possibilities in the bitmap. Through layering, each variable x, y, and z can use the lookup table (256 possibilities), solving the problem of extremely large possibilities. Of course, this method is not the only one, but it is indeed a feasible solution to share the lookup table.

 

The idea of ​​the article query is the same as the query format in uC/OS-II, that is, when the corresponding task needs to be ready, you can set the corresponding x, y, z corresponding bit to 1.