Décoder une quantité de longueur variable

16

Une quantité de longueur variable (également appelée VLQ ou uintvar) est un moyen de coder jusqu'à une valeur entière de 28 bits en utilisant uniquement autant d'octets que nécessaire. Cela a été utilisé au format de fichier MIDI comme un moyen de minimiser la taille de certaines données d'événements.

La façon dont cela fonctionne est assez simple. En tant que série d'octets big-endian, le bit le plus significatif (MSB) de chaque octet est un 1pour indiquer qu'un autre octet VLQ suit. Les 7 bits restants de chaque octet constituent la valeur décodée.

Exemple (de Wikipedia):

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

entrez la description de l'image ici Références supplémentaires: Wikipedia , Some Guy .

Défi:

Étant donné une quantité de longueur variable, convertissez-la en sa valeur entière.

Contribution:

Une liste d'un à quatre octets ou un type de valeur 32 bits représentant un VLQ valide d'un entier.

Production:

La valeur entière de l'entrée VLQ.

Règles et notation:

  • Il s'agit de code-golf, donc la réponse la plus courte en octets pour chaque langue gagne.
  • Les règles standard et les règles d' E / S par défaut s'appliquent.
  • Échappatoires interdites (bien sûr).
  • Veuillez fournir un lien avec un test pour votre code ( TIO.run , etc.).
  • Une explication claire de votre réponse est fortement recommandée.
  • Encastrements qui gèrent cette conversion ne sont pas interdits, mais pas les utiliser est beaucoup plus intéressant.

Cas de test:

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

Remarque: vous n'êtes pas obligé d'utiliser des littéraux hexadécimaux pour représenter un octet comme entrée ou sortie. Vous pouvez utiliser littéral décimal ( [ 129, 128, 0 ]), entier ( 0x80818000) ou toute autre représentation d'octet / octet raisonnable si elle est mieux adaptée à votre plate-forme. Le format est flexible tant qu'il représente 1 à 4 octets / octets.

Golf loin!

code-golf conversion bitwise 640 Ko
la source
Le dernier octet de l'entrée est-il garanti <128? Ou devons-nous prendre en charge des cas tels que [0x01, 0x80, 0x02] => 1?
Arnauld
5
@Arnauld Je vois mieux maintenant ce que vous vouliez dire et, rétrospectivement, le cas que vous mentionnez aurait été bon d'avoir exigé. En MIDI, par exemple, vous lirez un flux de données et vous ne savez donc pas nécessairement quel octet est le dernier. La façon dont il est écrit, garantissant que le dernier octet de la liste est le dernier octet du VLQ, rend le MSB non pertinent et en fait, en quelque sorte, défait le but du VLQ. Comme dans, vous ne seriez pas nécessairement en mesure d'utiliser ces routines (valides pour le défi) pour le décodage de fichiers MIDI. Totalement ma mauvaise! Aurait dû garder cela dans le bac à sable beaucoup plus longtemps ...
640KB
5
C'est aussi en partie mon problème parce que je pense avoir vu le défi dans le bac à sable et n'y avoir pas prêté suffisamment d'attention. Mais oui, c'est ce que j'avais à l'esprit: étant donné une liste d'octets, soit sortir la première valeur VLQ ou sortir toutes les valeurs VLQ .
Arnauld
1
@KevinCruijssen, une quantité de longueur variable est supposée être un flux d'octets, où techniquement vous ne savez que quand elle se termine en atteignant le marqueur MSB = 0. Je sais que les règles ne reflètent pas tout à fait cela, mais d'après la définition de VLQ, je vais devoir dire non.
640 Ko
1
@gwaugh Ok, cela a du sens et je peux comprendre le raisonnement. Je modifierai ma réponse MathGolf en conséquence. :)
Kevin Cruijssen

Réponses:

4

J , 10 octets

128#.128|]

Essayez-le en ligne!

Inspiré de la réponse APL de J Salle.

  • 128|] Reste des nombres entrants divisé par 128
  • 128#. Interprété comme les chiffres d'un nombre de base 128
Jonas
la source
3

05AB1E , 6 octets

žy%žyβ

Essayez-le en ligne!

1282sept

M. Xcoder
la source
Oui, ce builtin est inutile de nos jours. Dans la version héritée, je pouvais en voir l'utilité, uniquement lorsque vous avez un chiffre devant lui dans votre programme. Sinon, vous pourriez simplement utiliser 7o. De nos jours, vous pouvez compresser certains entiers de 3 octets (plage [101,355]) en 2 octets, donc 128 peut être de ƵRtoute façon .. Je me suis également demandé la même chose à propos de la fonction intégrée de 2 octets pour 16 .. Habituellement, vous utiliseriez simplement le littéral , ou sinon nous aurions 4o/ 4n/ 8·si un chiffre est derrière dans le programme. Ce n'est que lorsqu'un chiffre est avant le 16, ce qui ne devrait pas arriver, que la fonction intégrée est utile ..
Kevin Cruijssen
3

Stax , 8 octets

å→♂á╣>nt

Exécuter et déboguer

Algorithme:

  • Convertissez chaque octet en tableau à 7 bits de largeur fixe.
  • Aplatissez les tableaux de bits en un seul.
  • Convertissez le tableau de bits en nombre.
récursif
la source
2

JavaScript (ES6), 29 octets

-2 octets grâce à @Shaggy

Prend l'entrée comme un tableau d'octets.

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

Essayez-le en ligne!

Arnauld
la source
2

APL + WIN, 22 octets

Demande un vecteur d'entiers:

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

Essayez-le en ligne! Gracieuseté de Dyalog Classic

Explication:

¯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
la source
2

Stax , 12 octets

ü╫ôà¡k2Wù}a☺

Exécutez-le et déboguez-le sur staxlang.xyz!

Déballé (14 octets) et explication:

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 a une conversion de base intégrée, mais il ne fonctionne que sur les chaînes. Il presque fonctionne sur les listes d'entiers, bien que; le problème est dans la gestion de Stax de0 .

Une chaîne est une liste d'entiers. Lorsque vous utilisez une telle liste en tant que chaîne, tous les zéros sont automatiquement convertis en 32 en tant que raccourci pour les espaces. Étant donné que le code intégré |bpour la conversion de base traite son opérande comme une chaîne plutôt que comme une liste brute d'entiers, tout cas avec un zéro échouera.

10 octets, échoue sur les zéros

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

Exécutez-le et déboguez-le sur staxlang.xyz!

Khuldraeseth na'Barya
la source
1
Je vois d'où vient ce problème. {:B7)m$:bpacks à 8, et semble fonctionner aussi, bien que ce soit une utilisation exotique de $.
récursif
@recursive C'est intelligent. Affichez-le comme une réponse distincte.
Khuldraeseth na'Barya
Terminé. codegolf.stackexchange.com/a/189554/527
récursif
2

C (gcc) , 48 octets

Prend un entier dans l'ordre big-endian en entrée, qui est le même ordre qu'un tableau d'octets.

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

Essayez-le en ligne!

C (gcc) , 53 octets

Si un tableau d'octets est nécessaire:

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

Essayez-le en ligne!

ErikF
la source
Lorsque je compile votre code de test TIO avec -Os, il ne gère que les deux derniers cas. Je ne connais pas assez C pour dire pourquoi.
qwr
La valeur par défaut de @qwr TIO est -O0, ce qui vous permet de stocker (généralement) une valeur de retour dans le premier paramètre. C'est une particularité dans le golf de code, mais ne fonctionne pas avec des niveaux d'optimisation plus élevés.
ErikF
Vous pouvez raser un octet en le remplaçant &128par >>7.
G. Sliepen
2

MathGolf , 14 octets

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

Entrez sous forme d'entiers.

Essayez-le en ligne.

J'ai le sentiment que cela peut être plus court. C'est un peu ennuyeux que MathGolf ait un intégré de 1 octet pour la constante 128, mais pas de conversion de base (sauf pour binaire / hexadécimal).

Explication:

ê              # 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
la source
La conversion de base est sur la table depuis le jour 1, mais il y a d'autres révisions concernant la conversion de base que je veux aborder en même temps. Par exemple, je ne veux pas que différents opérateurs convertissent vers / à partir de chaînes hexadécimales.
max
2

Python 3 , 58 49 octets

-9 octets grâce à @Chas et @ ar4093

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

Essayez-le en ligne!

ou

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

Essayez-le en ligne!

Entrée via une liste d'entiers.

La binfonction de Python ajoute "0b" au début de la chaîne, donc ceux-ci doivent être supprimés avant de pouvoir être concaténés. Il ne conserve pas non plus les zéros non significatifs, donc s'il n'y en a pas (alias le dernier octet) ceux-ci doivent être rajoutés. Et s'il y en a un (alias tous sauf le dernier octet) qui doit être supprimé comme bien.Merci à @Chas d'avoir compris qu'en définissant toujours le premier bit, je peux simplement supprimer les trois premiers caractères et terminer.

Apparemment (selon @ ar4093), la formatfonction permet non seulement de ne pas avoir le préfixe '0b', mais aussi de supprimer le premier bit et le remplissage à 7 caractères en même temps.

Hiatsu
la source
Bienvenue à CGCC, qui fera de vous un pire programmeur! :). J'ai eu la même pensée que toi au début. Vous pouvez enregistrer 9 octets avec bin(a|128)[3:]car vous n'avez alors pas besoin de zfill.
Chas Brown
Comme vous l'avez dit, avec la fonction format, vous pouvez économiser 9 octets: bin(a)[2:].zfill(8)[1:]->f"{a%128:07b}"
ar4093
1

Japt , 10 8 octets

Prend l'entrée comme un tableau d'entiers.

muIÑ ìIÑ

Essayez-le ou exécutez tous les cas de test (l'en-tête dans les deux convertis à partir du format d'entrée utilisé dans le défi)

Enregistré 2 octets en s'inspirant de la solution d' 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
Hirsute
la source
1

Fusain , 11 octets

Ｉ↨﹪θ¹²⁸¦¹²⁸

Essayez-le en ligne! Le lien est vers la version détaillée du code. Prend l'entrée comme un tableau. Explication:

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

Windows Batch, 76 octets

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

Passez les paramètres préfixés avec "0x" et l'espace entre (par exemple 0xC0 0x80 0x80 0x00).

peter ferrie
la source
Bien fait. De toute évidence, pour quiconque le testera, vous devrez vous assurer de faire un @set y=,ax=entre deux exécutions.
640 Ko
1
le "set y =" suffit.
peter ferrie