Empaquetado de bits de una matriz de enteros

Question

Tengo una matriz de enteros, supongamos que son del tipo int64_t. Ahora, sé que solo cada primer n bits de cada entero es significativo (es decir, sé que están limitados por algunos límites).

¿Cuál es la forma más eficiente de convertir la matriz en la forma en que se elimina todo el espacio innecesario (es decir, tengo el primer entero en a[0], el segundo en a[0] + n bits y así sucesivamente)?

Me gustaría que fuera lo más general posible, porque n variaría de vez en cuando, aunque supongo que podría haber optimizaciones inteligentes para n específicos como potencias de 2 o sth.

Por supuesto que sé que puedo iterar el valor sobre el valor, solo quiero preguntarte StackOverflowers si se te ocurre alguna forma más inteligente.

Editar:

Esta pregunta no es acerca de la compresión de la matriz a tomar como mínimo espacio posible. Solo necesito "cortar" n bits de cada entero y dado el conjunto, sé exactamente n de bits que puedo cortar con seguridad.

Answer 1

Sé que esto podría parecer obvio, ya que estoy seguro de que en realidad hay una solución, pero ¿por qué no utilizar un tipo más pequeño, como uint8_t (255 como máximo)? o uint16_t (max 65535) ?. Estoy seguro de que podría manipular un bit en un int64_t usando valores y/o operaciones definidas, pero, aparte de un ejercicio académico, ¿por qué?

Y en la nota de ejercicios académicos, Bit Twiddling Hacks es una buena lectura.

Answer 2

La mayoría de los algoritmos de compresión se acercarán a la entropía mínima necesaria para codificar los enteros, por ejemplo, la codificación Huffman, pero acceder a ella como una matriz no será trivial.

Answer 3

Estoy de acuerdo con Keraba en que necesita usar algo como la codificación Huffman o quizás el algoritmo Lempel-Ziv-Welch. El problema con el empaque de bit de la manera en que está hablando es que tiene dos opciones:

• Elija una constante n tal que se pueda representar el entero más grande.
• Permitir que n varíe de un valor a otro.

La primera opción es relativamente fácil de implementar, pero realmente va a perder mucho espacio a menos que todos los números enteros sean más bien pequeños.

La segunda opción tiene la gran desventaja de que debe transmitir los cambios en n de alguna manera en el flujo de bits de salida. Por ejemplo, cada valor tendrá que tener una longitud asociada a él. Esto significa que está almacenando dos enteros (aunque sean enteros más pequeños) para cada valor de entrada. Es muy probable que incremente el tamaño del archivo con este método.

La ventaja de Huffman o LZW es que crean libros de códigos de tal manera que la longitud de los códigos puede derivarse del flujo de bits de salida sin almacenar realmente las longitudes. Estas técnicas te permiten acercarte mucho al límite de Shannon.

decidí a dar a su idea original (constante n, eliminar los bits no utilizados y el paquete) una oportunidad para la diversión y aquí es la implementación ingenua que se me ocurrió:

#include <sys/types.h> 
#include <stdio.h> 

int pack(int64_t* input, int nin, void* output, int n) 
{ 
    int64_t inmask = 0; 
    unsigned char* pout = (unsigned char*)output; 
    int obit = 0; 
    int nout = 0; 
    *pout = 0; 

    for(int i=0; i<nin; i++) 
    { 
     inmask = (int64_t)1 << (n-1); 
     for(int k=0; k<n; k++) 
     { 
      if(obit>7) 
      { 
       obit = 0; 
       pout++; 
       *pout = 0; 
      } 
      *pout |= (((input[i] & inmask) >> (n-k-1)) << (7-obit)); 
      inmask >>= 1; 
      obit++; 
      nout++; 
     } 
    } 
    return nout; 
} 

int unpack(void* input, int nbitsin, int64_t* output, int n) 
{ 
    unsigned char* pin = (unsigned char*)input; 
    int64_t* pout = output; 
    int nbits = nbitsin; 
    unsigned char inmask = 0x80; 
    int inbit = 0; 
    int nout = 0; 
    while(nbits > 0) 
    { 
     *pout = 0; 
     for(int i=0; i<n; i++) 
     { 
      if(inbit > 7) 
      { 
       pin++; 
       inbit = 0; 
      } 
      *pout |= ((int64_t)((*pin & (inmask >> inbit)) >> (7-inbit))) << (n-i-1); 
      inbit++; 
     } 
     pout++; 
     nbits -= n; 
     nout++; 
    } 
    return nout; 
} 

int main() 
{ 
    int64_t input[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; 
    int64_t output[21]; 
    unsigned char compressed[21*8]; 
    int n = 5; 

    int nbits = pack(input, 21, compressed, n); 
    int nout = unpack(compressed, nbits, output, n); 

    for(int i=0; i<=20; i++) 
     printf("input: %lld output: %lld\n", input[i], output[i]); 
} 

Esto es muy ineficaz porque es pasos un poco a la vez, pero esa fue la forma más fácil de implementarlo sin tener que lidiar con problemas de endianess. No he probado esto tampoco con una amplia gama de valores, solo los que están en la prueba. Además, no hay comprobación de límites y se supone que los búferes de salida son lo suficientemente largos. Entonces, lo que estoy diciendo es que este código probablemente solo sea bueno para fines educativos para que comiences.

Answer 4

No creo que pueda evitar iterar a través de los elementos. AFAIK La codificación Huffman requiere las frecuencias de los "símbolos", que a menos que conozca las estadísticas del "proceso" que genera los enteros, tendrá que calcular (iterando a través de cada elemento).

Answer 5

Si tiene tamaños fijos, p. usted sabe que su número es de 38 bits en lugar de 64, puede construir estructuras usando especificaciones de bits. Es divertido también tienes elementos más pequeños para caber en el espacio restante.

struct example { 
    /* 64bit number cut into 3 different sized sections */ 
    uint64_t big_num:38; 
    uint64_t small_num:16; 
    uint64_t itty_num:10; 

    /* 8 bit number cut in two */ 
    uint8_t nibble_A:4; 
    uint8_t nibble_B:4; 
}; 

Esto no es seguro grande/pequeño endian sin algún aro de salto, por lo que sólo se puede utilizar dentro de un programa en lugar de en un formato de datos exportados. A menudo se usa para almacenar valores booleanos en bits individuales sin definir turnos y máscaras.

Answer 6

Hoy lancé: PackedArray: Packing Unsigned Integers Tightly (github project).

Implementa un contenedor de acceso aleatorio donde los artículos se empaquetan a nivel de bit. En otras palabras, actúa como si pudieras manipular una p. Ej. uint9_t o uint17_t matriz:

PackedArray principle: 
    . compact storage of <= 32 bits items 
    . items are tightly packed into a buffer of uint32_t integers 

PackedArray requirements: 
    . you must know in advance how many bits are needed to hold a single item 
    . you must know in advance how many items you want to store 
    . when packing, behavior is undefined if items have more than bitsPerItem bits 

PackedArray general in memory representation: 
    |-------------------------------------------------- - - - 
    |  b0  |  b1  |  b2  | 
    |-------------------------------------------------- - - - 
    | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 | 
    |-------------------------------------------------- - - - 

    . items are tightly packed together 
    . several items end up inside the same buffer cell, e.g. i0, i1, i2 
    . some items span two buffer cells, e.g. i3, i6 

Answer 7

A partir de la implementación de Jason B, que finalmente escribí mi propia versión que procesa bit-bloques en lugar de bits individuales. Una diferencia es que es lsb: comienza desde los bits de salida más bajos hasta el más alto. Esto solo hace que sea más difícil de leer con un volcado binario, como Linux xxd -b. Como detalle, int* puede cambiarse trivialmente a int64_t*, y debería ser incluso mejor unsigned. Ya he probado esta versión con unos pocos millones de matrices y parece sólida, así que comparto el resto:

int pack2(int *input, int nin, unsigned char* output, int n) 
{ 
     int obit = 0; 
     int ibit = 0; 
     int ibite = 0; 
     int nout = 0; 
     if(nin>0) output[0] = 0; 
     for(int i=0; i<nin; i++) 
     { 
       ibit = 0; 
       while(ibit < n) { 
         ibite = std::min(n, ibit + 8 - obit); 
         output[nout] |= (input[i] & (((1 << ibite)-1)^((1 << ibit)-1))) >> ibit << obit; 
         obit += ibite - ibit; 
         nout += obit >> 3; 
         if(obit & 8) output[nout] = 0; 
         obit &= 7; 
         ibit = ibite; 
       } 
     } 
     return nout; 
} 

int unpack2(int *oinput, int nin, unsigned char* ioutput, int n) 
{ 
     int obit = 0; 
     int ibit = 0; 
     int ibite = 0; 
     int nout = 0; 
     for(int i=0; i<nin; i++) 
     { 
       oinput[i] = 0; 
       ibit = 0; 
       while(ibit < n) { 
         ibite = std::min(n, ibit + 8 - obit); 
         oinput[i] |= (ioutput[nout] & (((1 << (ibite-ibit+obit))-1)^((1 << obit)-1))) >> obit << ibit; 
         obit += ibite - ibit; 
         nout += obit >> 3; 
         obit &= 7; 
         ibit = ibite; 
       } 
     } 
     return nout; 
}