Decodifica una cantidad de longitud variable

16

Una cantidad de longitud variable (también conocida como VLQ o uintvar) es una forma de codificar un valor entero de hasta 28 bits utilizando solo tantos bytes como sea necesario. Esto se usó en formato de archivo MIDI como una forma de minimizar el tamaño de ciertos datos de eventos.

La forma en que funciona es bastante simple. Como una serie de bytes big-endian, el bit más significativo (MSB) de cada byte es un 1para indicar que sigue otro byte VLQ. Los 7 bits restantes de cada byte forman el valor decodificado.

Ejemplo (de Wikipedia):

[ 0x86, 0xc3, 0x17 ] => 106903

ingrese la descripción de la imagen aquí Referencias adicionales: Wikipedia , Some Guy .

Desafío:

Dada una cantidad de longitud variable, conviértala a su valor entero.

Entrada:

Una lista de uno a cuatro bytes o un tipo de valor de 32 bits que representa un VLQ válido de un entero.

Salida:

El valor entero de la entrada VLQ.

Reglas y puntuación:

  • Este es el código de golf, por lo que gana la respuesta más corta en bytes para cada idioma .
  • Se aplican las reglas estándar y las reglas de E / S predeterminadas .
  • Lagunas prohibidas (por supuesto).
  • Proporcione un enlace con una prueba para su código ( TIO.run , etc.).
  • Se recomienda encarecidamente una explicación clara de su respuesta.
  • Los elementos integrados que manejan esta conversión no están prohibidos, sin embargo, no usarlos es mucho más interesante.

Casos de prueba:

Input (VLQ)                   Output (int)

[                   0x00 ] => 0
[                   0x07 ] => 7
[                   0x7f ] => 127
[             0x81, 0x00 ] => 128
[             0xC0, 0x00 ] => 8192
[             0xff, 0x7f ] => 16383
[       0x81, 0x80, 0x00 ] => 16384
[       0x86, 0xc3, 0x17 ] => 106903
[       0xbd, 0x84, 0x40 ] => 1000000
[       0xff, 0xff, 0x7f ] => 2097151 
[ 0xC0, 0x80, 0x80, 0x00 ] => 134217728  
[ 0xFF, 0xFF, 0xFF, 0x7F ] => 268435455  

Nota: no es necesario que use literales hexadecimales para representar un byte como entrada o salida. Puede usar decimal literal ( [ 129, 128, 0 ]), entero ( 0x80818000) o cualquier otra representación razonable de byte / octeto si se adapta mejor a su plataforma. El formato es flexible siempre que represente 1-4 bytes / octetos.

¡Golf lejos!

640 KB
fuente
¿Se garantiza que el último byte de la entrada sea <128? ¿O necesitamos apoyar casos como [0x01, 0x80, 0x02] => 1?
Arnauld
55
@Arnauld Ahora veo mejor a qué te referías, y en retrospectiva, el caso que mencionas hubiera sido bueno haber requerido. En MIDI, por ejemplo, leerá un flujo de datos y, por lo tanto, no necesariamente sabrá qué byte es el último. La forma en que está escrito, lo que garantiza que el último byte de la lista es el último byte en el VLQ hace que el MSB sea irrelevante y, de hecho, frustra el propósito de VLQ. Como en, no necesariamente podría usar estas rutinas (válidas para el desafío) para la decodificación de archivos MIDI. Totalmente mi mal! Debería haber mantenido esto en la caja de arena mucho más tiempo ...
640 KB
55
Esto es en parte mi mal también porque creo que he visto el desafío en el sandbox y no he prestado suficiente atención. Pero sí, eso es lo que tenía en mente: dada una lista de bytes, ya sea generar el primer valor VLQ o generar todos los valores VLQ .
Arnauld
1
@KevinCruijssen, se supone que una cantidad de longitud variable es un flujo de bytes, donde técnicamente solo se sabe cuándo termina alcanzando el marcador MSB = 0. Sé que las reglas no capturaron eso, pero por la definición de VLQ voy a tener que decir que no.
640 KB el
1
@gwaugh Ok, eso tiene sentido y puedo entender el razonamiento. Modificaré mi respuesta MathGolf en consecuencia. :)
Kevin Cruijssen

Respuestas:

4

J , 10 bytes

128#.128|]

Pruébalo en línea!

Tomando inspiración de la respuesta APL de J Salle.

  • 128|] El resto de los números de entrada divididos por 128
  • 128#. Interpretado como los dígitos de un número base 128
Jonás
fuente
3

05AB1E , 6 bytes

žy%žyβ

Pruébalo en línea!

12827 7

Sr. Xcoder
fuente
Sí, esa construcción es inútil hoy en día. En la versión heredada, pude ver algún uso, solo cuando tienes un dígito antes en tu programa. De lo contrario, podría usar 7o. Hoy en día puedes comprimir ciertos números enteros de 3 bytes (rango [101,355]) en 2 bytes, así que 128 puede ser de ƵRtodos modos ... También me he preguntado lo mismo acerca de la construcción de 2 bytes para 16 ... Por lo general, solo usarías el literal , o de lo contrario tendríamos 4o/ 4n/ si un dígito está detrás de él en el programa. Solo cuando un dígito es anterior al 16, lo que no creo que suceda, el builtin es útil ...
Kevin Cruijssen
3

Stax , 8 bytes

å→♂á╣>nt

Ejecutar y depurarlo

Algoritmo:

  • Convierta cada byte en una matriz de 7 bits de ancho fijo.
  • Acoplar matrices de bits en uno.
  • Convierta la matriz de bits nuevamente a número.
recursivo
fuente
2

JavaScript (ES6), 29 bytes

-2 bytes gracias a @Shaggy

Toma la entrada como una matriz de bytes.

a=>a.map(p=c=>p=p<<7|c&127)|p

Pruébalo en línea!

Arnauld
fuente
2

APL + WIN, 22 bytes

Solicita un vector de enteros:

2⊥¯32↑,0 1↓⍉(8⍴2)⊤¯4↑⎕

Pruébalo en línea! Cortesía de Dyalog Classic.

Explicación:

¯4↑⎕ Pad the vector to 4 integers from the right.

⍉(8⍴2)⊤ Convert to a matrix of 8 bit values.

,0 1↓ drop the MSBs and flatten to a vector.

2⊥¯32↑ pad bit vector to 32 bits starting at LSB and convert back to integer.
Graham
fuente
2

Stax , 12 bytes

ü╫ôà¡k2Wù}a☺

¡Ejecútelo y depúrelo en staxlang.xyz!

Desempaquetado (14 bytes) y explicación:

rk128%128i^#*+
r                 Reverse 'cuz big-endian
 k                Fold from the left using block:
  128%              Modulize by 128
      128i^#        Push 128 to the power of (one plus the iteration index)
            *       Multiply
             +      Add to the total
                  Implicit print

Stax tiene una conversión de base integrada, pero solo funciona en cadenas. Sin embargo, casi funciona en listas de enteros; El problema está en el manejo de Stax de 0.

Una cadena es una lista de enteros. Cuando usa una lista como una cadena, los ceros se convierten automáticamente a 32 como una forma abreviada de espacios. Dado que la |bconversión integrada para la base trata su operando como una cadena en lugar de como una lista sin formato de enteros, cualquier caso con un cero fallará.

10 bytes, falla en ceros

Ç┘_A♥∙QZ►╣
{128%m128|b    Unpacked
{128%m         Modulize each by 128
      128|b    Convert from base 128

¡Ejecútelo y depúrelo en staxlang.xyz!

Khuldraeseth na'Barya
fuente
1
Veo de dónde vino ese problema. {:B7)m$:bpaquetes a 8, y parece funcionar también, aunque es una especie de uso exótico de $.
recursivo el
@recursivo Eso es inteligente. Publíquelo como una respuesta separada.
Khuldraeseth na'Barya
2

C (gcc) , 48 bytes

Toma un entero en orden big-endian como entrada, que es el mismo orden que una matriz de bytes.

f(i,j){for(j=0;j|=i&127,i&128;j<<=7,i>>=8);i=j;}

Pruébalo en línea!

C (gcc) , 53 bytes

Si se necesita una matriz de bytes:

f(c,j)char*c;{for(j=0;j|=*c&127,*c++&128;j<<=7);c=j;}

Pruébalo en línea!

ErikF
fuente
Cuando compilo su código de prueba TIO con -Os solo maneja los dos últimos casos. No sé suficiente C para decir por qué.
qwr
El valor predeterminado de @qwr TIO es -O0, lo que le permite (generalmente) almacenar un valor de retorno en el primer parámetro. Esta es una peculiaridad ^ Wfeature en golf de código, pero no funciona con niveles de optimización más altos.
ErikF
Puede eliminar un byte reemplazándolo &128con >>7.
G. Sliepen
2

MathGolf , 14 bytes

ê♣%hrx♣▬^mÅε*Σ

Entrada como enteros.

Pruébalo en línea.

Tengo la sensación de que esto puede ser más corto. Es un poco molesto que MathGolf tenga un byte incorporado de 1 byte para la constante 128, pero no conversión de base (excepto para binario / hexadecimal).

Explicación:

ê              # Take the inputs as integer-array
 ♣%            # Take modulo-128 on each value in this array
   h           # Push the length of the array (without popping the array itself)
    r          # Pop and push a list in the range [0, length)
     x         # Reverse the array to (length, 0]
      ♣▬       # Take 128 to the power of each value in this array
        ^      # Zip the two lists together to create pairs
         mÅ    # Map each pair to (using the following two commands):
           ε*  #  Reduce by multiplication (so basically the product of the pair)
             Σ # After multiplying each pair, take the total sum
               # (after which the entire stack joined together is output implicitly)
Kevin Cruijssen
fuente
La conversión de base ha estado sobre la mesa desde el día 1, pero hay algunas otras revisiones con respecto a la conversión de base que quiero abordar al mismo tiempo. Por ejemplo, no quiero que diferentes operadores conviertan a / desde cadenas hexadecimales.
maxb
2

Python 3 , 58 49 bytes

-9 bytes gracias a @Chas y @ ar4093

lambda x:int("".join(bin(a|128)[3:]for a in x),2)

Pruébalo en línea!

o

lambda x:int("".join(f"{a%128:07b}"for a in x),2)

Pruébalo en línea!

Entrada a través de la lista de enteros.

La binfunción de Python agrega "0b" al comienzo de la cadena, por lo que deben eliminarse antes de que puedan concatenarse. Tampoco mantiene los ceros a la izquierda, por lo que si no hay ninguno (también conocido como el último byte), esos deben agregarse nuevamente. bien. Gracias a @Chas por descubrir que al configurar siempre el primer bit, puedo eliminar los primeros tres caracteres y listo.

Aparentemente (según @ ar4093) la formatfunción permite no solo no tener el prefijo '0b', sino también eliminar el primer bit y el relleno a 7 caracteres, todo al mismo tiempo.

Hiatsu
fuente
¡Bienvenido a CGCC, que te hará un programador mucho peor! :). Al principio tuve el mismo pensamiento que tú. Puede guardar 9 bytes bin(a|128)[3:]ya que no necesita zfill.
Chas Brown
Como dijiste, con la función de formato puedes guardar 9 bytes: bin(a)[2:].zfill(8)[1:]->f"{a%128:07b}"
ar4093
1

Japt , 10 8 bytes

Toma datos como una matriz de enteros.

muIÑ ìIÑ

Pruébalo o ejecuta todos los casos de prueba (encabezado en ambos conversos del formato de entrada utilizado en desafío)

Ahorró 2 bytes al inspirarse en la solución de alephalpha .

muIÑ ìIÑ     :Implicit input of integer array
m            :Map
 u           :  Modulo
  I          :    64
   Ñ         :    Multiply by 2
     ì       :Convert to decimal
      IÑ     :  From base 64*2
Lanudo
fuente
1

Carbón , 11 bytes

I↨﹪θ¹²⁸¦¹²⁸

Pruébalo en línea! El enlace es a la versión detallada del código. Toma la entrada como una matriz. Explicación:

   θ        Input array
  ﹪ ¹²⁸    Elementwise modulo 128
 ↨      ¹²⁸ Convert from base 128
I          Cast to string for implicit print
Neil
fuente
1

Lote de Windows, 76 bytes

:a
@set/ax="%1&127",y=y*128+x
@if %2. neq . @shift&goto:a
@echo %y%

Pase los parámetros con el prefijo "0x" y el espacio entre ellos (por ejemplo, 0xC0 0x80 0x80 0x00).

Peter Ferrie
fuente
Bien hecho. Obviamente, para cualquier otra persona que lo pruebe, deberá asegurarse de hacer un @set y=,ax=recorrido entre ejecuciones.
640 KB el
1
solo el "set y =" es suficiente.
peter ferrie