가변 길이 정수 인코딩

Question

LZ1/LZ77 압축 해제 알고리즘을 리버스 엔지니어링하려고합니다. 출력 될 디코드 버퍼/윈도우 영역의 길이는 파일에서 가변 길이 정수로 인코딩됩니다. 난 가변 길이 정수 인코딩에 대해 할 수있는만큼 많이 읽었고이 경우에 사용되는 메서드는 내가 본 다른 어떤 것처럼 보이지 않습니다. 아마도 특허 문제를 피하거나 어쩌면 난독화할 수도 있습니다. 포함 된 코드가 완전하지 않을 수도 있지만이 시점에서 적어도 여러 파일에서 작업하고 있습니다.

나는 아래에서 사용되는 수식을 어떻게하면 더 간단하게 줄일 수 있는지 알 수 없습니다. 대부분의 가변 길이 정수 인코딩 알고리즘은 일종의 루프를 사용하지만이 경우에는 각 니블을 평가할 때 수식이 일관성이없는 것처럼 보이기 때문에이 작업을 수행 할 수 없었습니다.

제안 사항을 매우 높이 평가합니다.

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

사용되는 가변 길이 정수 인코딩 알고리즘은 Dlugosz' Variable-Length Integer Encoding 메서드와 매우 유사합니다. 사실, 단일 수식보다는 여러 계산이 필요합니다.

이를 바탕으로 다음과 같이 코드를 다시 작성했습니다. 나는 여전히 선두 0xFFF가 사용되는 메커니즘의 정확한 형식을 파악하려고 노력 중이다.

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