Codage entier de longueur variable

Question

Je tente de faire de l'ingénierie inverse d'un algorithme de décompression LZ1/LZ77. La longueur d'une zone du tampon/fenêtre de décodage à sortir est codée dans le fichier sous la forme d'un entier de longueur variable. J'ai lu autant que possible sur l'encodage des entiers de longueur variable et la méthode utilisée dans ce cas ne semble pas être comme les autres que j'ai vu. Peut-être pour éviter les problèmes de brevets ou peut-être juste pour obscurcir. Le code inclus peut ne pas être tout à fait complet, mais il travaille sur au moins plusieurs fichiers à ce stade.

Je ne vois pas comment, le cas échéant, les formules utilisées ci-dessous pourraient être réduites à quelque chose de plus simple. La plupart des algorithmes de codage d'entiers de longueur variable utilisent une sorte de boucle mais pour celui-ci, je n'ai pas été capable de le faire parce que la formule ne semble pas être cohérente lors de l'évaluation de chaque grignotage.

Les suggestions sont grandement appréciées.

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

Il se trouve que le nombre entier de longueur variable algorithme de codage utilisé est très similaire à la méthode Dlugosz' Variable-Length Integer Encoding. En effet, plusieurs calculs sont requis, plutôt qu'une seule formule. Sur cette base, j'ai réécrit le code comme suit. J'essaye toujours de comprendre le format exact du mécanisme où un 0xFFF principal est employé.

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