Codificación de entero de longitud variable

Question

Estoy intentando realizar una ingeniería inversa de un algoritmo de descompresión LZ1/LZ77. La longitud de un área de la memoria intermedia/ventana de decodificación a emitir se codifica en el archivo como un entero de longitud variable. He leído todo lo que puedo sobre la codificación de enteros de longitud variable y el método que se utiliza en este caso no parece ser como los que he visto. Tal vez para evitar problemas de patentes o tal vez solo para ofuscar. El código incluido puede no estar completo, pero está trabajando en al menos varios archivos en este punto.

No puedo ver cómo, en todo caso, las fórmulas que se utilizan a continuación podrían reducirse a algo más simple. La mayoría de los algoritmos de codificación de enteros de longitud variable utilizan algún tipo de bucle, pero para este, no he podido hacer eso porque la fórmula no parece ser consistente cuando se evalúa cada mordisco.

Las sugerencias son muy apreciadas.

private static int getLength(BitReader bitStream) 
{ 
    const int minSize = 2; 

    int length = 0; 

    byte nibble3, nibble2, nibble1; 

    nibble3 = bitStream.ReadNibble(); 

    if (nibble3 >= 0xc) 
    { 
     nibble2 = bitStream.ReadNibble(); 
     nibble1 = bitStream.ReadNibble(); 

     if (nibble3 == 0xF & nibble2 == 0xF & nibble1 == 0xF) return -1; 

     if ((nibble3 & 2) != 0) 
     { 
      length = (((((nibble3 & 7) + 3) << 6) + 8)) + 
       ((nibble2 & 7) << 3) + nibble1 + minSize; 
     } 
     else if ((nibble3 & 1) != 0) 
     { 
      length = (((nibble3 & 7) << 6) + 8) + 
       ((((nibble2 & 7)) + 1) << 3) + nibble1 + minSize; 
     } 
     else 
     { 
      length = ((((nibble3 & 7) << 4) + 8)) + 
       ((nibble2 & 7) << 4) + nibble1 + minSize; 
     } 
    } 
    else if ((nibble3 & 8) != 0) 
    { 
     nibble1 = bitStream.ReadNibble(); 

     length = ((((nibble3 & 7) << 1) + 1) << 3) + nibble1 + minSize; 
    } 
    else 
    { 
     length = nibble3 + minSize; 
    } 

    return length; 
} 

Answer 1

Resulta que la longitud número entero algoritmo de codificación variable que se utiliza es muy similar al método Dlugosz' Variable-Length Integer Encoding. De hecho, hay varios cálculos que se requieren, en lugar de una sola fórmula.

Basado en eso, reescribí el código de la siguiente manera. Todavía estoy tratando de descubrir el formato exacto del mecanismo donde se usa un 0xFFF líder.

private static int getLength(BitReader bitStream) 
    { 
     const int minSize = 2; 
     int length = 0; 
     byte nibble3, nibble2, nibble1; 
     byte nibble; 
     nibble = bitStream.ReadNibble(); 
     if (nibble == 0xF) 
     { 
      nibble2 = bitStream.ReadNibble(); 
      nibble1 = bitStream.ReadNibble(); 
      if (nibble2 == 0xf && nibble1 == 0xF) 
      { 
       //The next nibble specifies the number of nibbles to be read, maybe. 
       byte nibblesToRead = (byte) (bitStream.ReadNibble()) ; 
       //The Dlugosz' mechanism would use a mask on the value but that doesn't appear to be the case here. 
       //nibblesToRead &= 7; 
       //switch (nibblesToRead & 7){ 
       // case 0: nibblesToRead = 5; break; 
       // case 1: nibblesToRead = 8; break; 
       // case 2: nibblesToRead = 16; break;       
       //} 
       byte value=0; 
       byte[] values = new byte[nibblesToRead]; 
       bool c=true; 
       for (int i = 0; i < nibblesToRead; i++) 
       { 
        value = bitStream.ReadNibble(); 
        //values[i] = value; 
        length += (((value << 1) | 1) << 3); 
       } 
       value = bitStream.ReadNibble(); 
       length += value; 
      } 
     } 
     else if((nibble >= 0xC)){ 
      nibble2 = bitStream.ReadNibble(); 
      nibble1 = bitStream.ReadNibble(); 
      length = ((((((nibble & 1) <<1)|1))<< 3) + ((nibble2<<1)|1)<<3)+nibble1; 
     } 
     else if ((nibble & 8)!=0){ 
      nibble1 = bitStream.ReadNibble(); 
      length = ((((nibble & 3)<<1) | 1) << 3) + nibble1; 
     } 
     else{ 
      length=nibble; 
     } 
     return length + minSize; 
     };