LEB128

LEB128 o Little Endian Base 128 es un sistema de compresión de código de longitud variable que se utiliza para almacenar números enteros arbitrariamente grandes en una pequeña cantidad de bytes. LEB128 se utiliza en el formato de archivo de depuración DWARF ^{[1] [2]} y en la codificación binaria WebAssembly para todos los literales enteros. ^[3]

El formato LEB128 es muy similar al formato de cantidad de longitud variable (VLQ); la principal diferencia es que LEB128 es little-endian mientras que las cantidades de longitud variable son big-endian . Ambos permiten almacenar números pequeños en un solo byte, al mismo tiempo que permiten la codificación de números arbitrariamente largos. Hay dos versiones de LEB128: LEB128 sin signo y LEB128 con signo. El decodificador debe saber si el valor codificado es LEB128 sin signo o LEB128 con signo.

Para codificar un número sin signo utilizando LEB128 sin signo ( ULEB128 ), primero se representa el número en binario. Luego , se extiende el número a un múltiplo de 7 bits (de modo que si el número no es cero, los 7 bits más significativos no sean todos 0). Se divide el número en grupos de 7 bits. Se genera un byte codificado para cada grupo de 7 bits, desde el menos significativo hasta el más significativo. Cada byte tendrá el grupo en sus 7 bits menos significativos. Se establece el bit más significativo en cada byte, excepto en el último. El número cero suele codificarse como un solo byte 0x00. WebAssembly permite codificaciones alternativas de cero (0x80 0x00, 0x80 0x80 0x00, ...). ^[3]

A modo de ejemplo, así es como se codifica el número sin signo 624485:

Número más alto ------------------ Número más bajo
      10011000011101100101 En binario sin procesar
     010011000011101100101 Rellenado a un múltiplo de 7 bits
 0100110 0001110 1100101 Dividido en grupos de 7 bits
00100110 10001110 11100101 Agrega bits altos 1 en todos los grupos excepto el último (el más significativo) para formar bytes
    0x26 0x8E 0xE5 En hexadecimal

→ 0xE5 0x8E 0x26 Flujo de salida (LSB a MSB)

Tanto el LEB128 sin signo como el VLQ ( cantidad de longitud variable ) comprimen cualquier entero dado no solo en la misma cantidad de bits, sino exactamente los mismos bits; los dos formatos difieren solo en cómo se organizan exactamente esos bits.

Un número con signo se representa de manera similar: comenzando con una representación de complemento a dos de 0 bits , donde es un múltiplo de 7, el número se divide en grupos como para la codificación sin signo. ${\estilo de visualización N}$${\estilo de visualización N}$

Por ejemplo, el número con signo -123456 se codifica como 0xC0 0xBB 0x78:

Número más alto ------------------ Número más bajo
         11110001001000000 Codificación binaria de 123456
     000011110001001000000 Como un número de 21 bits
     111100001110110111111 Negación de todos los bits ( complemento a uno )
     111100001110111000000 Sumando uno (complemento a dos)
 1111000 0111011 1000000 Dividido en grupos de 7 bits
01111000 10111011 11000000 Agrega bits altos 1 en todos los grupos excepto el último (el más significativo) para formar bytes
    0x78 0xBB 0xC0 En hexadecimal

→ 0xC0 0xBB 0x78 Flujo de salida (LSB a MSB)

Una implementación escalar sencilla de la decodificación LEB128 es bastante lenta, más aún en hardware moderno donde la predicción errónea de bifurcaciones es relativamente costosa. Una serie de artículos presentan técnicas SIMD para acelerar la decodificación (se denomina VByte en estos artículos, pero es otro nombre para la misma codificación). El artículo "Vectorized VByte Decoding" ^[4] presentó "Masked VByte", que demostró velocidades de 650 a 2700 millones de enteros por segundo en hardware Haswell comercial , dependiendo de la densidad de codificación. Un artículo de seguimiento presentó una codificación variante, "Stream VByte: Faster Byte Oriented Integer Compression", ^[5] que aumentó las velocidades a más de 4 mil millones de enteros por segundo. Esta codificación de flujo separa el flujo de control de los datos codificados, por lo que no es compatible binariamente con LEB128.

do { byte = 7 bits de valor de orden bajo ; valor >> = 7 ; if ( valor != 0 ) /* más bytes por venir */ establecer el bit de orden alto de byte ; emitir byte ; } while ( valor ! = 0 ); 
        
    
      
        
   
    

más = 1 ; negativo = ( valor < 0 );  
    


/* el tamaño en bits del valor de la variable, por ejemplo, 64 si el tipo del valor es int64_t */ tamaño = número de bits en entero con signo ;       

mientras ( más ) { byte = 7 bits de valor de orden bajo ; valor >> = 7 ; /* lo siguiente solo es necesario si la implementación de >>= usa un      desplazamiento lógico en lugar de un desplazamiento aritmético para un operando izquierdo con signo */ si ( negativo ) valor |= ( ~ 0 << ( tamaño - 7 )); /* signo extendido */  
        
    
  

   
           

  /* el bit de signo del byte es el segundo bit de orden superior (0x40) */ 
if (( valor == 0 && el bit de signo del byte está limpio ) || ( valor == -1 && el bit de signo del byte está establecido )) more = 0 ; else establecer el bit de orden superior del byte ; emitir byte ; }                       
      
  
        
   

resultado = 0 ; desplazamiento = 0 ; mientras ( verdadero ) { byte = siguiente byte en la entrada ; resultado |= ( 7 bits de orden inferior del byte ) << desplazamiento ; si ( bit de orden superior del byte == 0 ) interrupción ; desplazamiento + = 7 ; }  
  
  
       
          
        
    
    

resultado = 0 ; desplazamiento = 0 ;  
  

/* el tamaño en bits de la variable de resultado, por ejemplo, 64 si el tipo del resultado es int64_t */ 
tamaño = número de bits en entero con signo ;       

do { byte = siguiente byte en la entrada ; resultado |= ( 7 bits de orden inferior del byte << desplazamiento ) ; desplazamiento += 7 ; } while ( bit de orden superior del byte ! = 0 ); 
       
          
    
       

/* el bit de signo del byte es el segundo bit de orden superior (0x40) */ 
if (( shift < size ) && ( el bit de signo del byte está establecido )) /* signo extendido */ result |= ( ~ 0 << shift );         
  
      

función encodeUnSignedInt32toLeb128 ( valor ) {  

    var rawbine = value.toString ( 2 ) ; // En binario sin formato var paded = rawbine.padStart ( Math.ceil ( (( rawbine.length ) / 7 )) * 7 , ' 0' ) // Rellenado a un múltiplo de 7 bits var splited = paded.match ( / . { 1,7 }/g ); //Dividido en grupos de 7 bits const result = []; // Agrega los bits altos 1 en todos los grupos excepto el último (el más significativo ) para formar bytes var y = splited.length - 1 for ( let i = 0 ; i < splited.length ; i ++ ) { if ( i === 0 ) { var str = " 0" + splited [ i ]; result [ y ] = parseInt ( str , 2 ) .toString ( 16 ) .padStart ( 2 , ' 0' ) ; } else { var str = "1" + dividido [ i ]; resultado [ y ] = parseInt ( cadena , 2 ). a Cadena ( 16 ). padInicio ( 2 , '0' ); } y- ;​ }    
              
        
       
    
        
             
           
             
            
        
             
            
      
      
    

  devolver resultado .join ( '' ); } ; 

función decodeLeb128toUnSignedInt32 ( valor ) { var valor_tab = valor . split ( "" ); var resultado = "" ; const tabtemp = []; var y = valor_tab . length / 2 - 1 ; para ( dejar i = 0 ; i < valor_tab . length ; i ++ ) { si ( i % 2 != 0 ) { tabtemp [ y ] = (( parseInt ( valor_tab [ i - 1 ], 16 ). toString ( 2 )). padStart ( 4 , ' 0' ) + ( parseInt ( valor_tab [ i ], 16 ). toString ( 2 )). padStart ( 4 , '0' )). slice ( 1 ) ; y -- ; } } resultado = parseInt ( valor_tab . join ( '' ), 2 ). toString ( 10 ) devuelve resultado ; };  
   
   
     
        
           
            
                    
         
      
  
    
   

const encodeSignedLeb128FromInt32 = ( valor ) => { valor |= 0 ; const resultado = []; while ( verdadero ) { const byte_ = valor & 0x7f ; valor >>= 7 ; if ( ( valor === 0 && ( byte_ & 0x40 ) === 0 ) || ( valor === - 1 && ( byte_ & 0x40 ) !== 0 ) ) { resultado . push ( byte_ ); return resultado ; } resultado . push ( byte_ | 0x80 ); } };     
    
     
    
         
      
     
               
              
     
      
       
    
      
  

const decodeSignedLeb128 = ( entrada ) => { dejar resultado = 0 ; dejar desplazamiento = 0 ; mientras ( verdadero ) { const byte = entrada . desplazamiento (); resultado |= ( byte & 0x7f ) << desplazamiento ; desplazamiento += 7 ; si (( 0x80 & byte ) === 0 ) { si ( desplazamiento < 32 && ( byte & 0x40 ) !== 0 ) { devolver resultado | ( ~ 0 << desplazamiento ); } devolver resultado ; } } };     
     
     
    
       
          
      
          
                
             
      
       
    
  

• El proyecto Android utiliza LEB128 en su formato de archivo Dalvik Executable Format (.dex). ^[6]
• Compresión de tablas en el manejo de excepciones de Hewlett-Packard IA-64. ^[7]
• El formato de archivo DWARF utiliza codificación LEB128 con y sin signo para varios campos. ^[2]
• LLVM , en su formato de mapeo de cobertura ^[8] La implementación de la codificación y decodificación LEB128 de LLVM es útil junto con el pseudocódigo anterior. ^[9]
• .NET admite un formato "int codificado de 7 bits" en las clases BinaryReader y BinaryWriter . ^[10] Al escribir una cadena en un BinaryWriter , la longitud de la cadena se codifica con este método.
• Minecraft utiliza LEB128 en su protocolo para medir la longitud de los datos dentro de los paquetes. ^[11]
• La herramienta de depuración mpatrol utiliza LEB128 en su formato de archivo de seguimiento. ^[12]
• osu! utiliza LEB128 en su formato de reproducción osu! (.osr). ^[13]
• El Intercambio XML Eficiente (EXI) del W3C representa números enteros sin signo utilizando LEB128, exactamente de la misma manera que se describe aquí. ^[14]
• WebAssembly , en su codificación binaria portátil de los módulos ^[3]
• En formato de archivo xz ^[15]

• La codificación de enteros de longitud variable de Dlugosz (original) utiliza múltiplos de 7 bits para los tres primeros saltos de tamaño, pero después los incrementos varían. También coloca todos los bits del prefijo al principio de la palabra, en lugar de al principio de cada byte.
• Los bytes del descriptor de informe del dispositivo de interfaz humana utilizan un campo de bits de conteo de bytes de 2 bits para codificar el tamaño del siguiente entero de cero, uno, dos o cuatro bytes, siempre little endian. El signo, es decir, si se debe expandir o no el entero acortado con un signo, depende del tipo de descriptor.
• El formato de archivo de código de bits LLVM utiliza una técnica similar ^[16] excepto que el valor se divide en grupos de bits de tamaño dependiente del contexto, donde el bit más alto indica una continuación, en lugar de 7 bits fijos.
• Los búferes de protocolo (Protobuf) utilizan la misma codificación para los enteros sin signo, pero codifican los enteros con signo anteponiendo el signo como el bit menos significativo del primer byte.
• ASN.1 BER, DER Codifica los valores de cada tipo ASN.1 como una cadena de octetos de ocho bits

• El formato de archivo de depuración DWARF
• UTF-7