Lectura de datos de bits alineados

Question

He estado leyendo el SWF format disponible en el sitio de Adobe y se menciona que con el fin de ahorrar espacio, los bits variables se utilizan para los enteros de la tienda o flotadores (página 17 del PDF)

tengo siempre trabajó con datos alineados con bytes, por lo que no le dio mucha importancia a los archivos que están alineados con los bits, o tienen una alineación variable donde la información se almacena en cada byte.

Así, por ejemplo, puede tener una estructura que contenga cuatro enteros de 13 bits almacenados secuencialmente (en lugar de almacenarlos como cuatro enteros de 16 bits).

Los primeros 13 bits son el primer entero, los siguientes 13 bits son el segundo entero, y así sucesivamente. Rellena el último byte apropiado para hacer que la estructura esté alineada con byte con el resto del archivo, de modo que los 52 bits se rellenarán a 56 bits, requiriendo 7 bytes para almacenar esos cuatro enteros en oposición a 8 bytes.

• ¿Cómo me acerco a este tipo de problema?
• ¿Cómo puedo trabajar con una secuencia de bytes en el nivel de bit?
• ¿Hay algo que pueda usar para ayudar a que sea más fácil trabajar con estos datos?

Imagino que la solución se reduce a usar operaciones de bits en matrices de bytes.

Una solución de ejemplo para analizar los cuatro enteros de 13 bits sería bueno también para demostrar el uso de su método sugerido.

Answer 1

Hay dos formas de tratar con esto que yo sepa. La primera es hacerlo manualmente, utilizando operadores de bits, división, módulo, etc. en arreglos de bytes [o entero/ulong, etc., si estuviste aburrido]. IsBitSet Example

La otra forma es un BitArray - que maneja la mayor parte de esto para usted :)

---

Sería bueno añadir un ejemplo de cómo exactamente BitArray maneja conseguir los bits 13..25 como un int, ya que esa sería la operación principal. A primera vista, solo veo un ciclo.

fina ... escribí una rápida prueba de & sucia prueba de concepto:

var rnd = new Random(); 
//var data = Enumerable.Range(0, 10).ToArray(); 
var data = Enumerable.Range(0, 10).Select(x => rnd.Next(1 << 13)).ToArray(); 

foreach (var n in data) Console.WriteLine(n); 

Console.WriteLine(new string('-', 13)); 

var bits = new BitArray(data.Length * 13); 

for (int i = 0; i < data.Length; i++) 
{ 
    var intBits = new BitArray(new[] { data[i] }); 
    for (int b = 12; b > -1; b--) 
    { 
     bits[i * 13 + b] = intBits[b]; 
     Console.Write(intBits[b] ? 1 : 0); 
    } 
    Console.WriteLine(); 
} 
Console.WriteLine(new string('-', 13)); 

for (int i = 0; i < bits.Length/13; i++) 
{ 
    int number = 0; 
    for (int b = 12; b > -1; b--) 
     if (bits[i * 13 + b]) 
      number += 1 << b; 

    Console.WriteLine(number); 
} 
Console.ReadLine(); 

que da salida:

910 
3934 
7326 
7990 
7712 
1178 
6380 
3460 
5113 
7489 
------------- 
0001110001110 
0111101011110 
1110010011110 
1111100110110 
1111000100000 
0010010011010 
1100011101100 
0110110000100 
1001111111001 
1110101000001 
------------- 
910 
3934 
7326 
7990 
7712 
1178 
6380 
3460 
5113 
7489 

La matriz de bits no hace mucho aparte de simplificar el acceso a - Todavía es bastante manual.Espero que iba a escribir sus propias clases que simplemente esto y que sea limpio y reutilizable - por ejemplo, aquí hay otro concepto rápida:

//Improved to take sign into account. 
//Sign is in addition to bits allocated for storage in this version. 
//Stored as {sign}{bits} 
//E.g. -5, stored in 3 bits signed is: 
//  1 101 
//E.g. 5, stored in 3 bits [with sign turned on] 
//  0 101 
//E.g. 5, stored in 3 bits no sign 
//   101 
//This may differ from your exiting format - e.g. you may use two's compliments. 
static void Main(string[] args) 
{ 
    int bitsPerInt = 13; 

    //Create your data 
    var rnd = new Random(); 
    //var data = Enumerable.Range(-5, 10).ToArray(); 
    var data = Enumerable.Range(0, 10).Select(x => rnd.Next(-(1 << bitsPerInt), 1 << bitsPerInt)).ToArray(); 

    var bits = new BitSerlializer(); 

    //Add length header 
    bits.AddInt(data.Length, 8, false); 
    foreach (var n in data) 
    { 
     bits.AddInt(n, bitsPerInt); 
     Console.WriteLine(n); 
    } 

    //Serialize to bytes for network transfer etc. 
    var bytes = bits.ToBytes(); 

    Console.WriteLine(new string('-', 10)); 
    foreach (var b in bytes) Console.WriteLine(Convert.ToString(b, 2).PadLeft(8, '0')); 
    Console.WriteLine(new string('-', 10)); 

    //Deserialize 
    bits = new BitSerlializer(bytes); 
    //Get Length Header 
    var count = bits.ReadInt(8, false); 
    for (int i = 0; i < count; i++) 
     Console.WriteLine(bits.ReadInt(bitsPerInt)); 

    Console.ReadLine(); 
} 

public class BitSerlializer 
{ 
    List<byte> bytes; 
    int Position { get; set; } 

    public BitSerlializer(byte[] initialData = null) 
    { 
     if (initialData == null) 
      bytes = new List<byte>(); 
     else 
      bytes = new List<byte>(initialData); 
    } 

    public byte[] ToBytes() { return bytes.ToArray(); } 

    public void Addbit(bool val) 
    { 
     if (Position % 8 == 0) bytes.Add(0); 
     if (val) bytes[Position/8] += (byte)(128 >> (Position % 8)); 
     Position++; 
    } 

    public void AddInt(int i, int length, bool isSigned = true) 
    { 
     if (isSigned) Addbit(i < 0); 
     if (i < 0) i = -i; 

     for (int pos = --length; pos >= 0; pos--) 
     { 
      var val = (i & (1 << pos)) != 0; 
      Addbit(val); 
     } 
    } 

    public bool ReadBit() 
    { 
     var val = (bytes[Position/8] & (128 >> (Position % 8))) != 0; 
     ++Position; 
     return val; 
    } 

    public int ReadInt(int length, bool isSigned = true) 
    { 
     var val = 0; 
     var sign = isSigned && ReadBit() ? -1 : 1; 

     for (int pos = --length; pos >= 0; pos--) 
      if (ReadBit()) 
       val += 1 << pos; 

     return val * sign; 
    } 
} 

Answer 2

Por otro lado, el enfoque basado en la matriz de bytes podría ir así:

int extend(uint raw, int bits) 
    { 
     int sh = 32 - bits; 
     int x = (int)raw << sh; // puts your sign bit in the highest bit. 
     return x >> sh; // since x is signed this is an arithmatic signed shift 
    } 

    int read(byte[] data, int pos, int bits, bool signed) 
    { 
     int fbi = pos/8; // first byte index 
     int lbi = (pos + bits - 1)/8; // last byte index 
     int cnt = lbi - fbi + 1; // bytes spanned 
     if (cnt > 3 || lbi >= data.Length) { throw new ArgumentException(); } 

     uint raw = (uint)(
      (data[fbi] << (24 + pos % 8)) + 
      (cnt < 2 ? 0 : data[fbi + 1] << (16 + pos % 8)) + 
      (cnt < 3 ? 0 : data[fbi + 2] << (8 + pos % 8)) 
      ) >> (32 - bits); 
     return signed ? extend(raw, bits) : (int)raw; 
    } 

prueba para esto:

byte[] test = { 0x55, 0xAA, 0x10 }; 

    string s = ""; 
    s += read(test, 0, 8, false) + "\r\n"; 
    s += read(test, 0, 8, true) + "\r\n"; 
    s += read(test, 8, 8, false) + "\r\n"; 
    s += read(test, 8, 8, true) + "\r\n"; 
    s += read(test, 4, 8, false) + "\r\n"; 
    s += read(test, 7, 9, true) + "\r\n"; 
    s += read(test, 7, 10, true) + "\r\n"; 
    s += read(test, 7, 11, true) + "\r\n"; 
    s += read(test, 7, 12, true) + "\r\n"; 
    s += read(test, 7, 13, true) + "\r\n"; 
    s += read(test, 7, 14, true) + "\r\n"; 
    s += read(test, 7, 15, true) + "\r\n"; 
    s += read(test, 7, 16, true) + "\r\n"; 
    s += read(test, 7, 17, true) + "\r\n"; 
    s += read(test, 18, 2, true) + "\r\n"; 
    s += read(test, 18, 3, true) + "\r\n"; 
    s += read(test, 23, 1, true) + "\r\n"; 
    s += read(test, 23, 2, true) + "\r\n"; 

la prueba se basa la cadena como la siguiente:

85 
    85 
    170 
    -86 
    90 
    -86 
    -172 
    -344 
    -688 
    -1375 
    -2750 
    -5500 
    -11000 
    -22000 
    1 
    2 
    0 

luego arroja una excepción en la última línea.