Ganzzahlige Codierung mit variabler Länge

Question

Ich versuche, einen LZ1/LZ77-Dekomprimierungsalgorithmus rückzuentwickeln. Die Länge eines auszugebenden Bereichs des Dekodierpuffers/-fensters wird in der Datei als eine Ganzzahl variabler Länge codiert. Ich habe so viel wie möglich über die Ganzzahlkodierung mit variabler Länge gelesen, und die Methode, die in diesem Fall verwendet wird, scheint nicht wie andere zu sein, die ich gesehen habe. Vielleicht, um Patentprobleme zu vermeiden oder vielleicht nur zu verschleiern. Der enthaltene Code ist möglicherweise nicht vollständig, aber er arbeitet an mindestens einigen Dateien zu diesem Zeitpunkt.

Ich kann nicht sehen, wie, wenn überhaupt, die unten verwendeten Formeln in etwas einfacheres reduziert werden könnten. Die meisten Integer-Codieralgorithmen mit variabler Länge verwenden irgendeine Art von Schleife, aber für diese eine war ich nicht in der Lage, dies zu tun, weil die Formel bei der Auswertung jedes Nibbles nicht einheitlich zu sein scheint.

Vorschläge werden sehr geschätzt.

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

Es stellt sich heraus, dass die variable Länge ganzzahlige Codieralgorithmus ist zum Dlugosz' Variable-Length Integer Encoding Verfahren sehr ähnlich verwendet wird. Tatsächlich sind mehrere Berechnungen erforderlich und nicht eine einzige Formel.

Basierend darauf habe ich den Code wie folgt neu geschrieben. Ich versuche immer noch, das genaue Format des Mechanismus herauszufinden, in dem ein führender 0xFFF verwendet wird.

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; 
     };