3位元对的数组 [英] Array of pairs of 3 bit elements

问题描述

由于内存的限制，我必须以6位/对(3位/值)的形式将一些值对存储在数组中.当我想根据该对的索引将该数组作为普通数组访问时，就会出现问题. 数组看起来像这样

Because of memory constrains, I have to store some pairs of values in an array with 6 bits/pair (3 bits/value). The problem comes when I want to access this array as a normal one, based on the index of the pair. The array looks like this

|--byte 0 | --byte 1 | --byte 2  
|00000011 | 11112222 | 22333333   ...  and so on, the pattern repeats.  
|------|-------|--------|------|  
 pair 0  pair 1  pair 2  pair 3 

 => 4 pairs / 3 bytes

您可以看到有时(对于被1和2整除的索引)需要2个字节来提取值.
我做了一个给定索引的函数，该函数返回该对中的第一个值(3位)，另一个返回该值(也是3位).

You can see that sometimes (for indexes divisible by 1 and 2) 2 bytes are required to extract the values.
I made a function that given an index, returns the first value from the pair (3 bits) and the other one (also 3 bits).

void GetPair(char *array, int index, int &value1, int &value2) {
    int groupIndex = index >> 2; // Divide by 4 to get the index of the group of 3 bytes (with 4 pairs)
    // We use 16 bits starting with the first byte from the group for indexes divisible by 0 and 1,  
    // 16 bits starting with the second byte when divisible by 2 and 3
    short int value = *(short int *)(array + groupIndex + ((index & 0x02) >> 1));

    switch(index & 0x03) { // index % 4
        case 0: { 
            // extract first 3 bits
            value1 = (value & 0xE000) >> 13;
            // extract the next 3 bits
            value2 = (value & 0x1C00) >> 10;
            break;
        }
        case 1: {
            value1 = (value & 0x380) >> 7;
            value2 = (value & 0x70) >> 4;
            break;
        }
        case 2: {
            value1 = (value & 0xE00) >> 9;
            value2 = (value & 0x1C0) >> 6;
            break;
        }
        case 3: {
            value1 = (value & 0x38) >> 2;
            value2 = value & 0x7;
            break;
        }
}

现在我的问题是:有没有更快的方法来提取这些值?

我进行了一次测试，当使用2个字节/对(1个字节/值)时，大约需要6秒钟才能访问所有对(共53个)1亿次.使用紧凑型数组时，它大约需要22秒:((可能是因为它需要计算所有这些掩码和位移位).
我试图尽我所能地清楚地解释...如果没有，请原谅我.

I made a test and when using 2 bytes/pair (1 byte/value) it takes about 6 seconds to access all pairs (53 in total) 100 million times. When using the compact array, it takes about 22 seconds :( (probably because it needs to compute all those masks and bit shifts).
I tried to explain as clearly as i could... forgive me if not.

推荐答案

这个怎么样?它消除了对掩码和移位值的存储器访问. (当然，(不可移植的)假设是char是8位，short是16位.还假设index * 6不会溢出int.)

How about this? It eliminates memory accesses for the masks and shift values. (Of course, the (non-portable) assumption is that char is 8 bit and short is 16 bit. It is also assumed that index * 6 does not overflow int.)

void GetPair(char *array, int index, int &value1, int &value2)
{
   unsigned shift = 10 - index * 6 % 8;
   unsigned short data = (*(unsigned short *)(array + index * 6 / 8) >> shift) & 0x3f;
   value2 = data & 7;
   value1 = data >> 3;
}

但是，读取跨越16位边界的短路可能会受到惩罚.当我仍在跟踪此类事情时，曾经有过这样的问题.如果是这样，最好从16位边界开始读取32位值，并相应地调整移位和掩码.

There might be a penalty for reading a short crossing a 16 bit boundary, though. There used to be such issues way back when I was still keeping track of such things. If that is the case, it would probably be better to read a 32 bit value starting at a 16 bit boundary and adjust the shifts and masks accordingly.

这篇关于3位元对的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！