¿Es esta la manera más óptima? C bitfields

Question

Hice una función para establecer o borrar un número específico de bits en un DWORD. Mi función funciona No necesito ayuda para hacerlo funcionar. Sin embargo, me pregunto si el método que elegí para hacerlo es la manera más rápida posible.

Es bastante difícil para mí explicar cómo funciona esto. Hay dos matrices que contienen DWORD que están llenas de bits en el lado izquierdo y derecho de DWORD (con todos los 1 binarios). Hace una máscara con todos los bits rellenos, excepto los que quiero establecer o borrar, y luego los establece con operadores bit a bit basados ​​en esa máscara. Parece bastante complicado para una tarea tan simple, pero parece ser la manera más rápida que pude llegar. Es mucho más rápido que configurarlos poco a poco.

static DWORD __dwFilledBitsRight[] = { 
     0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF 
    }; 

static DWORD __dwFilledBitsLeft[] = { 
     0x0, 0x80000000, 0xC0000000, 0xE0000000, 0xF0000000, 0xF8000000, 0xFC000000, 0xFE000000, 0xFF000000, 0xFF800000, 0xFFC00000, 0xFFE00000, 0xFFF00000, 0xFFF80000, 0xFFFC0000, 0xFFFE0000, 0xFFFF0000, 0xFFFF8000, 0xFFFFC000, 0xFFFFE000, 0xFFFFF000, 0xFFFFF800, 0xFFFFFC00, 0xFFFFFE00, 0xFFFFFF00, 0xFFFFFF80, 0xFFFFFFC0, 0xFFFFFFE0, 
     0xFFFFFFF0, 0xFFFFFFF8, 0xFFFFFFFC, 0xFFFFFFFE, 0xFFFFFFFF 
    }; 

    // nStartBitFromLeft must be between 1 and 32... 
    // 1 is the bit farthest to the left (actual bit 31) 
    // 32 is the bit farthest to the right (actual bit 0) 
    inline void __FillDWORDBits(DWORD *p, int nStartBitFromLeft, int nBits, BOOL bSet) 
    { 
     DWORD dwLeftMask = __dwFilledBitsLeft[nStartBitFromLeft - 1]; // Mask for data on the left of the bits we want 
     DWORD dwRightMask = __dwFilledBitsRight[33 - (nStartBitFromLeft + nBits)]; // Mask for data on the right of the bits we want 
     DWORD dwBitMask = ~(dwLeftMask | dwRightMask); // Mask for the bits we want 
     DWORD dwOriginal = *p; 
     if(bSet) *p = (dwOriginal & dwLeftMask) | (dwOriginal & dwRightMask) | (0xFFFFFFFF & dwBitMask); 
     else *p = (dwOriginal & dwLeftMask) | (dwOriginal & dwRightMask) | 0; 

    } 

Answer 1

¿Qué tal:

// Create mask of correct length, and shift to the correct position 
DWORD mask = ((1ULL << nBits) - 1) << pos; 
// Apply mask (or its inverse) 
if (bSet) 
{ 
    *p |= mask; 
} 
else 
{ 
    *p &= ~mask; 
} 

Es bastante probable que las operaciones bit a bit simples será más rápido que búsqueda en la tabla en cualquier procesador moderno.

Nota: Dependiendo de la relación entre DWORD y long long en esta plataforma, es posible que necesite un tratamiento especial para el caso en nBits == sizeof(DWORD)*8. O si nBits==0 no es una posibilidad, simplemente puede hacer DWORD mask = ((2ULL << (nBits - 1)) - 1) << pos;.

Actualización: Se ha mencionado que el if podría ser lento, lo cual es cierto. Aquí hay un reemplazo, pero necesitaría medir para ver si realmente es más rápido en la práctica.

// A bit hacky, but the aim is to get 0x00000000 or 0xFFFFFFFF 
// (relies on two's-complement representation) 
DWORD blanket = bSet - 1; 
// Use the blanket to override one or other masking operation 
*p |= (blanket | mask); 
*p &= ~(blanket & mask); 

Answer 2

Esta es la forma en que lo haría. Lo dividiría en dos funciones, setbits() y clearbits(). Se han roto los pasos para mayor claridad, y estoy seguro de que puede ser mucho más optimizado.

Esta versión depende del código de 32 bits tal como está. Además, en mi mundo, el bit 0 es el bit más a la derecha. Su experiencia puede ser diferente.

setbits(DWORD *p , int offset , int len) 
{ 
    // offset must be 0-31, len must be 0-31, len+offset must be 0-32 
    int right_shift = (!len ? 0 : 32 - (len+offset)) ; 
    int left_shift = offset ; 
    DWORD right_mask = 0xFFFFFFFF >> right_shift ; 
    DWORD left_mask = 0xFFFFFFFF << left_shift ; 
    DWORD mask  = left_mask & right_mask  ; 

    *p |= mask ; 

    return ; 
} 

clearbits(DWORD *p , int offset , int len) 
{ 
    // offset must be 0-31, len must be 0-31, len+offset must be 0-32 
    int right_shift = (!len ? 0 : 32 - (len+offset)) ; 
    int left_shift = offset ; 
    DWORD right_mask = 0xFFFFFFFF >> right_shift ; 
    DWORD left_mask = 0xFFFFFFFF << left_shift ; 
    DWORD mask  = ~(left_mask & right_mask) ; 

    *p &= mask ; 

    return ; 
} 

Me encontré con esta versión mejorada mientras buscaba otra cosa hoy. Cortesía de Sean Anderson de la Universidad de Stanford Bit Twiddling Hacks:

// uncomment #define to get the super scalar CPU version. 
// #define SUPER_SCALAR_CPU 
void setbits(unsigned int *p , int offset , int len , int flag) 
{ 
    unsigned int mask = ((1 << len) - 1) << offset ; 

#if !defined(SUPER_SCALAR_CPU) 
    *p ^= (- flag^*p) & mask ; 
#else 
    // supposed to be some 16% faster on a Intel Core 2 Duo than the non-super-scalar version above 
    *p = (*p & ~ mask) | (- flag & mask) ; 
#endif 

    return ; 

} 

Mucho depende de su compilador, sin embargo.