arraysalgorithmsortingbit-manipulationbitwise-operators

Shrinking array of elements when size of each element is reduced from 8 bits to 3 bits


I have items inside an array. Each item has a 1-byte i.e. 8-bit size. I did shrink each item from 8-bit to 3-bit by this approach: https://stackoverflow.com/a/78870606/3405291

Then I'm going to pack the shrunk items into a smaller array while splitting the 3-bit chunks between consecutive bytes.

split 3 bits between bytes

I'm looking for the terminology of such an algorithm. Is there any standard algorithm to do so? A code snippet/example would be a great help.

Result

Following the solution by @trincot now the image pixels can be bit packed from 8-bit to 3-bit.

Original gray image

Each pixel is 8-bit:

Original gray image

Bit-packed gray image

Every 3 bits of data on the pixel array would correspond to an original pixel:

Bit-packed gray image


Solution

  • In C, you could do it as follows:

    void pack(unsigned char *arr, size_t len, unsigned char *result) {
        size_t num_bytes = (len * 3 + 7) >> 3;
        size_t j = 0;
        char shift = 5;
        for (size_t i = 0; i < len; i++) {
            unsigned char color = arr[i] >> 5;
            if (shift < 0) {
                result[j] |= color >> -shift;
                j++;
                shift += 8;
            }
            result[j] |= color << shift;
            shift -= 3;
        }
    }
    

    So, here the input is given as an array of bytes (unsigned char) and its length, and the output is written to result that should be initialised with 0, and have a size that corresponds to num_bytes.

    Here is an example call:

    int main(void) {
        unsigned char arr[8] = {0xFF, 0x33, 0x66, 0x88, 0x22, 0x99, 0x11, 0x77};
        unsigned char result[3] = {0};
        pack(arr, 8, result);
        // Verify that result is as expected
        if (result[0] == 0xE5 && result[1] == 0xC3 && result[2] == 0x03 ) {
            printf("test passed.\n");
        } else {
            printf("test failed.\n");
        }
        return 0;
    }