Dekodiere eine Menge variabler Länge

15

Eine Variable-Länge-Menge (auch als VLQ oder bezeichnet uintvar) ist eine Möglichkeit, mit nur so vielen Bytes wie nötig bis zu einem 28-Bit-Ganzzahlwert zu codieren. Dies wurde im MIDI-Dateiformat verwendet , um die Größe bestimmter Ereignisdaten zu minimieren.

Die Art und Weise, wie es funktioniert, ist ziemlich einfach. Als Big-Endian-Folge von Bytes gibt das höchstwertige Bit (MSB) jedes Bytes 1an, dass ein weiteres VLQ-Byte folgt. Die verbleibenden 7 Bits jedes Bytes bilden den decodierten Wert.

Beispiel (aus Wikipedia):

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

Bildbeschreibung hier eingeben Zusätzliche Referenzen: Wikipedia , Some Guy .

Herausforderung:

Konvertieren Sie eine Menge variabler Länge in ihren ganzzahligen Wert.

Eingang:

Eine Liste mit ein bis vier Bytes oder einem 32-Bit-Wertetyp, der eine gültige VLQ einer Ganzzahl darstellt.

Ausgabe:

Der ganzzahlige Wert der VLQ-Eingabe.

Regeln und Wertung:

  • Das ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes für jede Sprache .
  • Es gelten Standardregeln und Standard-E / A-Regeln .
  • Lücken verboten (natürlich).
  • Bitte geben Sie einen Link mit einem Test für Ihren Code an ( TIO.run usw.).
  • Eine klare Erklärung für Ihre Antwort wird dringend empfohlen.
  • Built-Ins, die diese Konvertierung handhaben, sind nicht gesperrt, aber es ist viel interessanter, sie nicht zu verwenden.

Testfälle:

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

Hinweis: Sie müssen keine Hex-Literale verwenden, um ein Byte als Eingabe oder Ausgabe darzustellen. Sie können dezimales Literal ( [ 129, 128, 0 ]), Ganzzahl ( 0x80818000) oder jede andere angemessene Byte- / Oktettdarstellung verwenden, wenn dies für Ihre Plattform besser geeignet ist. Das Format ist flexibel, solange es 1 bis 4 Byte / Oktett darstellt.

Golf weg!

code-golf conversion bitwise 640 KB
quelle
Ist das letzte Byte der Eingabe garantiert <128? Oder müssen wir Fälle wie unterstützen [0x01, 0x80, 0x02] => 1?
Arnauld
5
@Arnauld Ich verstehe jetzt besser, worauf du hinaus willst, und im Nachhinein wäre der von dir erwähnte Fall gut gewesen. In MIDI lesen Sie beispielsweise einen Datenstrom und wissen nicht unbedingt, welches Byte das letzte ist. Die Art und Weise, wie es geschrieben ist, garantiert, dass das letzte Byte in der Liste das letzte Byte in der VLQ ist, macht das MSB irrelevant und vereitelt in der Tat den Zweck der VLQ. Nach wie vor könnten Sie diese (für die Challenge gültigen) Routinen nicht unbedingt zur Dekodierung von MIDI-Dateien verwenden. Völlig mein Schlechtes! Hätte dies viel länger im Sandkasten aufbewahren sollen ...
640KB
5
Das ist zum Teil auch mein Nachteil, weil ich glaube, ich habe die Herausforderung im Sandkasten gesehen und nicht genug aufgepasst. Aber ja, das war es, woran ich gedacht hatte: Bei einer gegebenen Liste von Bytes entweder den ersten VLQ-Wert ausgeben oder alle VLQ-Werte ausgeben .
Arnauld
1
@ KevinCruijssen, eine Variable Länge Menge soll ein Strom von Bytes sein, wo Sie technisch nur wissen, wann es endet, indem Sie die MSB = 0-Markierung erreichen. Ich weiß, dass die Regeln das nicht ganz erfasst haben, aber nach der Definition von VLQ muss ich nein sagen.
8.
1
@gwaugh Ok, das macht Sinn und ich kann die Argumentation verstehen. Ich werde meine MathGolf-Antwort entsprechend ändern. :)
Kevin Cruijssen

Antworten:

4

J , 10 Bytes

128#.128|]

Probieren Sie es online!

Inspiriert von J Salles APL-Antwort.

  • 128|] Rest der eingegebenen Zahlen geteilt durch 128
  • 128#. Ausgelegt als die Ziffern einer 128er Basiszahl
Jona
quelle
3

05AB1E , 6 Bytes

žy%žyβ

Probieren Sie es online!

12827

Mr. Xcoder
quelle
Ja, das eingebaute ist heutzutage nutzlos. In der Vorgängerversion konnte ich eine Verwendung dafür sehen, nur wenn Sie in Ihrem Programm eine Ziffer davor haben. Ansonsten könntest du einfach benutzen 7o. Heutzutage können Sie bestimmte 3-Byte-Ganzzahlen (Bereich [101,355]) in 2 Bytes komprimieren , so dass 128 ƵRsowieso sein können. Ich habe mich auch über das 2-Byte-Builtin für 16 gewundert. Normalerweise verwenden Sie einfach das Literal wir würden oder auf andere Weise haben 4o/ 4n/ 8·wenn eine Ziffer dahinter im Programm ist. Nur wenn eine Ziffer vor der 16 steht, was meiner Meinung nach nicht passieren würde, ist das eingebaute nützlich.
Kevin Cruijssen
2

JavaScript (ES6), 29 Byte

-2 Bytes dank @Shaggy

Nimmt die Eingabe als Array von Bytes.

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

Probieren Sie es online!

Arnauld
quelle
2

APL + WIN, 22 Bytes

Fordert zur Eingabe eines Ganzzahlvektors auf:

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

Probieren Sie es online! Mit freundlicher Genehmigung von Dyalog Classic

Erläuterung:

¯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
quelle
2

Stax , 12 Bytes

ü╫ôà¡k2Wù}a☺

Führen Sie es aus und debuggen Sie es unter staxlang.xyz!

Entpackt (14 Bytes) und Erklärung:

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 hat eine integrierte Basiskonvertierung, die jedoch nur für Zeichenfolgen funktioniert. Es funktioniert jedoch fast auf Listen mit ganzen Zahlen. Das Problem liegt in der Handhabung von Stax 0.

Eine Zeichenfolge ist eine Liste von Ganzzahlen. Wenn Sie eine solche Liste als Zeichenfolge verwenden, werden alle Nullen automatisch in 32 umgewandelt, um eine gute Abkürzung für Leerzeichen zu erhalten. Da der |bfür die Basiskonvertierung eingebaute Operand als Zeichenfolge und nicht als unformatierte Liste von Ganzzahlen behandelt wird, schlägt jeder Fall mit einer Null fehl.

10 Bytes, fehlgeschlagen bei Nullen

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

Führen Sie es aus und debuggen Sie es unter staxlang.xyz!

Khuldraeseth na'Barya
quelle
1
Ich sehe, woher dieses Problem kam. {:B7)m$:bPacks zu 8, und scheint auch zu funktionieren, obwohl es eine Art exotische Verwendung von ist $.
rekursiver
@recursive Das ist schlau. Poste es als separate Antwort.
Khuldraeseth na'Barya
Erledigt. codegolf.stackexchange.com/a/189554/527
rekursiv
2

C (gcc) , 48 Bytes

Übernimmt eine Ganzzahl in Big-Endian-Reihenfolge als Eingabe. Dies entspricht der Reihenfolge eines Byte-Arrays.

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

Probieren Sie es online!

C (gcc) , 53 Bytes

Wenn ein Byte-Array benötigt wird:

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

Probieren Sie es online!

ErikF
quelle
Wenn ich Ihren TIO-Testcode mit -Os kompiliere, werden nur die letzten beiden Fälle behandelt. Ich weiß nicht genug C, um zu sagen warum.
qwr
@qwr TIO ist der Standardwert -O0, mit dem Sie (normalerweise) einen Rückgabewert im ersten Parameter speichern können. Dies ist eine Besonderheit beim Code-Golfen, funktioniert jedoch nicht mit höheren Optimierungsstufen.
ErikF
Sie können ein Byte durch Ersetzen abrasieren &128mit >>7.
G. Sliepen
2

MathGolf , 14 Bytes

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

Eingabe als Ganzzahl.

Probieren Sie es online aus.

Ich habe das Gefühl, dass dies kürzer sein kann. Es ist ein bisschen ärgerlich, dass MathGolf eine 1-Byte-integrierte Konstante hat 128, aber keine Basisumwandlung (außer binär / hexadezimal).

Erläuterung:

ê              # 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
quelle
Die Basiskonvertierung ist seit Tag 1 auf dem Tisch, aber es gibt einige andere Überarbeitungen in Bezug auf die Basiskonvertierung, die ich gleichzeitig ansprechen möchte. Zum Beispiel möchte ich nicht, dass verschiedene Operatoren in / aus hexadezimalen Zeichenfolgen konvertieren.
Maxb
2

Python 3 , 58 49 Bytes

-9 Bytes dank @Chas und @ ar4093

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

Probieren Sie es online!

oder

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

Probieren Sie es online!

Eingabe über Liste von Ganzzahlen.

Pythons binFunktion fügt "0b" am Anfang der Zeichenkette hinzu, sodass diese entfernt werden müssen, bevor sie verkettet werden können. Es werden auch keine führenden Nullen beibehalten. Wenn also keine (auch bekannt als das letzte Byte) vorhanden sind, müssen diese erneut hinzugefügt werden. Wenn es eine führende (auch bekannt als alle bis auf das letzte Byte) gibt, müssen diese als entfernt werden Gut. Vielen Dank an @Chas, der herausgefunden hat, dass ich durch Setzen des ersten Bits einfach die ersten drei Zeichen entfernen und fertig bin.

Anscheinend (gemäß @ ar4093) formaterlaubt die Funktion nicht nur, das Präfix '0b' nicht zu haben, sondern auch das erste Bit zu entfernen und alle gleichzeitig auf 7 Zeichen aufzufüllen.

Hiatsu
quelle
Willkommen bei CGCC, das Sie zu einem viel schlechteren Programmierer macht! :). Ich hatte den gleichen Gedanken wie du zuerst. Sie können mit 9 Bytes einsparen, bin(a|128)[3:]da Sie das dann nicht benötigen zfill.
Chas Brown
Wie Sie sagten, können Sie mit der Formatierungsfunktion 9 Bytes speichern: bin(a)[2:].zfill(8)[1:]->f"{a%128:07b}"
ar4093
1

Japt , 10 8 Bytes

Nimmt die Eingabe als Array von Ganzzahlen.

muIÑ ìIÑ

Probieren Sie es aus oder führen Sie alle Testfälle aus (Header in beiden Konvertierungen aus dem in challenge verwendeten Eingabeformat)

2 Bytes gespart, indem man sich von Alephalphas Lösung inspirieren ließ .

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

Holzkohle , 11 Bytes

Ｉ↨﹪θ¹²⁸¦¹²⁸

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Übernimmt die Eingabe als Array. Erläuterung:

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

Windows Batch, 76 Bytes

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

Übergeben Sie Parameter mit dem Präfix "0x" und einem Leerzeichen dazwischen (z. B. 0xC0 0x80 0x80 0x00).

Peter Ferrie
quelle
Schön gemacht. Natürlich müssen Sie für jeden anderen, der es testet, sicherstellen, dass @set y=,ax=zwischen den Läufen eine Prüfung durchgeführt wird .
16.
1
nur das "set y =" reicht aus.
Peter Ferrie