Cómo escribir un flujo de bits

Question

Estoy pensando en escribir algunos datos en un flujo de bits usando C. Hay dos maneras en que vienen a la mente. Uno es concatenar símbolos de longitud de bits variable en una secuencia de bits contigua, pero de esta manera mi decodificador probablemente tendrá un tiempo difícil separando esos símbolos de este flujo continuo de bits. Otra forma es distribuir la misma cantidad de bits para cada símbolo y de ese modo el decodificador puede recuperar fácilmente los datos originales, pero puede haber un desperdicio de bits ya que los símbolos tienen valores diferentes que a su vez causan muchos bits en la secuencia de bits. cero (estos bits de desecho, supongo).

¿Alguna pista de lo que debo hacer?

Soy nuevo en la programación. Cualquier ayuda será apreciada.

Answer 1

¿Parece que intenta hacer algo similar a un esquema de compresión de Huffman? Simplemente iría byte a byte (char) y mantendría un registro del desplazamiento dentro del byte donde leo el último símbolo.

Suponiendo que ninguno de sus símbolos sea más grande que char. Se vería algo como esto:

struct bitstream { 
    char *data; 
    int data_size;   // size of 'data' array 
    int last_bit_offset;  // last bit in the stream 

    int current_data_offset; // position in 'data', i.e. data[current_data_offset] is current reading/writing byte 
    int current_bit_offset; // which bit we are currently reading/writing 
} 

char decodeNextSymbol(bitstream *bs) { 

} 

int encodeNextSymbol(bitstream *bs, char symbol) { 

} 

El código coincidente para decodeNextSymbol y encodeNextSymbol habría que utilizar las operaciones de C bit a bit ('&' (AND bit a bit), y '|' (OR bit a bit), por ejemplo, yo. Luego aparecería una lista de todos mis símbolos, empezando por el más corto primero y haciendo un ciclo while que coincida con el símbolo más corto. Por ejemplo, si uno de tus símbolos es '101', entonces si el flujo es '1011101' , coincidiría con el primer '101' y continuaría coincidiendo con el resto de la secuencia '1101' También tendría que manejar el caso donde los valores de sus símbolos se desbordan de un byte al siguiente.