Variable-length quantity: Difference between revisions
Added FreeBASIC
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added FreeBASIC) |
||
| (11 intermediate revisions by 8 users not shown) | |||
Line 157:
16#200000# = :16#81#:16#80#:16#80#: 16#0#</pre>
=={{header|
==={{header|ANSI BASIC}}===
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">INPUT s$
LET s$ = LTRIM$(RTRIM$(s$))
LET v = 0
Line 180 ⟶ 182:
PRINT hs$
END</syntaxhighlight>
{{out}}
<pre>
S= 200000 V= 2097152
Line 187 ⟶ 189:
1fffff
</pre>
==={{header|FreeBASIC}}===
{{trans|Wren}}
<syntaxhighlight lang="vbnet">Sub toOctets(n As Integer, octets() As Integer)
Dim As String s = Bin(n)
Dim As Integer le = Len(s)
Dim As Integer r = le Mod 7
Dim As Integer d = le \ 7
If (r > 0) Then
d += 1
s = Right("0000000" & s, 7 * d)
End If
For i As Integer = 0 To d - 2
Redim Preserve octets(i+1) As Integer
octets(i) = Val("&B1" & Mid(s, i * 7 + 1, 7))
Next i
octets(d - 1) = Val("&B0" & Mid(s, (d - 1) * 7 + 1, 7))
End Sub
Function fromOctets(octets() As Integer) As Integer
Dim As String s = ""
For i As Integer = 0 To Ubound(octets)
s &= Right("0000000" & Bin(octets(i)), 7)
Next i
Return Val("&B" & s)
End Function
Dim As Integer tests(1) = {2097152, 2097151}
Dim As Integer i
For i = 0 To Ubound(tests)
Dim As Integer octets()
toOctets(tests(i), octets())
Dim As String display = ""
For j As Integer = 0 To Ubound(octets)
display &= "0x" & Hex(octets(j), 2) & " "
Next j
Print tests(i); " -> "; display; "-> "; fromOctets(octets())
Next i
Sleep</syntaxhighlight>
{{out}}
<pre> 2097152 -> 0x81 0x80 0x80 0x00 -> 2097152
2097151 -> 0xFF 0xFF 0x7F -> 2097151</pre>
==={{header|Visual Basic .NET}}===
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
Function ToVlq(v As ULong) As ULong
Dim array(8) As Byte
Dim buffer = ToVlqCollection(v).SkipWhile(Function(b) b = 0).Reverse().ToArray
buffer.CopyTo(array, 0)
Return BitConverter.ToUInt64(array, 0)
End Function
Function FromVlq(v As ULong) As ULong
Dim collection = BitConverter.GetBytes(v).Reverse()
Return FromVlqCollection(collection)
End Function
Iterator Function ToVlqCollection(v As ULong) As IEnumerable(Of Byte)
If v > Math.Pow(2, 56) Then
Throw New OverflowException("Integer exceeds max value.")
End If
Dim index = 7
Dim significantBitReached = False
Dim mask = &H7FUL << (index * 7)
While index >= 0
Dim buffer = mask And v
If buffer > 0 OrElse significantBitReached Then
significantBitReached = True
buffer >>= index * 7
If index > 0 Then
buffer = buffer Or &H80
End If
Yield buffer
End If
mask >>= 7
index -= 1
End While
End Function
Function FromVlqCollection(vlq As IEnumerable(Of Byte)) As ULong
Dim v = 0UL
Dim significantBitReached = False
Using enumerator = vlq.GetEnumerator
Dim index = 0
While enumerator.MoveNext
Dim buffer = enumerator.Current
If buffer > 0 OrElse significantBitReached Then
significantBitReached = True
v <<= 7
v = v Or (buffer And &H7FUL)
End If
index += 1
If index = 8 OrElse (significantBitReached AndAlso (buffer And &H80) <> &H80) Then
Exit While
End If
End While
End Using
Return v
End Function
Sub Main()
Dim values = {&H7FUL << 7 * 7, &H80, &H2000, &H3FFF, &H4000, &H200000, &H1FFFFF}
For Each original In values
Console.WriteLine("Original: 0x{0:X}", original)
REM collection
Dim seq = ToVlqCollection(original)
Console.WriteLine("Sequence: 0x{0}", seq.Select(Function(b) b.ToString("X2")).Aggregate(Function(a, b) String.Concat(a, b)))
Dim decoded = FromVlqCollection(seq)
Console.WriteLine("Decoded: 0x{0:X}", decoded)
REM ints
Dim encoded = ToVlq(original)
Console.WriteLine("Encoded: 0x{0:X}", encoded)
decoded = FromVlq(encoded)
Console.WriteLine("Decoded: 0x{0:X}", decoded)
Console.WriteLine()
Next
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>Original: 0xFE000000000000
Sequence: 0xFF80808080808000
Decoded: 0xFE000000000000
Encoded: 0xFF80808080808000
Decoded: 0xFE000000000000
Original: 0x80
Sequence: 0x8100
Decoded: 0x80
Encoded: 0x8100
Decoded: 0x80
Original: 0x2000
Sequence: 0xC000
Decoded: 0x2000
Encoded: 0xC000
Decoded: 0x2000
Original: 0x3FFF
Sequence: 0xFF7F
Decoded: 0x3FFF
Encoded: 0xFF7F
Decoded: 0x3FFF
Original: 0x4000
Sequence: 0x818000
Decoded: 0x4000
Encoded: 0x818000
Decoded: 0x4000
Original: 0x200000
Sequence: 0x81808000
Decoded: 0x200000
Encoded: 0x81808000
Decoded: 0x200000
Original: 0x1FFFFF
Sequence: 0xFFFF7F
Decoded: 0x1FFFFF
Encoded: 0xFFFF7F
Decoded: 0x1FFFFF</pre>
=={{header|Bracmat}}==
Line 548 ⟶ 723:
Press any key to continue...</syntaxhighlight>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
sub VLQEncode(number: uint32, buf: [uint8]) is
var step := number;
while step > 0 loop
step := step >> 7;
buf := @next buf;
end loop;
var mark: uint8 := 0;
while number > 0 loop
buf := @prev buf;
[buf] := mark | (number as uint8 & 0x7F);
mark := 0x80;
number := number >> 7;
end loop;
end sub;
sub VLQDecode(buf: [uint8]): (result: uint32) is
result := 0;
loop
var byte := [buf];
buf := @next buf;
result := (result << 7) | (byte & 0x7F) as uint32;
if byte & 0x80 == 0 then
return;
end if;
end loop;
end sub;
sub VLQPrint(buf: [uint8]) is
loop
print_hex_i8([buf]);
if [buf] & 0x80 == 0 then
break;
end if;
buf := @next buf;
end loop;
end sub;
sub VLQTest(value: uint32) is
var buf: uint8[8];
print("Input: ");
print_hex_i32(value);
print_nl();
print("Encoded: ");
VLQEncode(value, &buf[0]);
VLQPrint(&buf[0]);
print_nl();
print("Decoded: ");
value := VLQDecode(&buf[0]);
print_hex_i32(value);
print_nl();
end sub;
VLQTest(0x200000);
print_nl();
VLQTest(0x1FFFFF);
print_nl();</syntaxhighlight>
{{out}}
<pre>Input: 00200000
Encoded: 81808000
Decoded: 00200000
Input: 001fffff
Encoded: ffff7f
Decoded: 001fffff</pre>
=={{header|D}}==
Line 649 ⟶ 897:
2: 1fffff = (FF:FF:7F)
3: 200000 = (81:80:80:00)</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function NumberToVLQ(Num: int64): string;
{Convert Num to Variable-Length Quantity VLQ Octets (bytes)}
{Octet = 7-bit data and MSB indicating the last data item = 0 }
{Note: String are being used as byte-array because they are easy}
var I: integer;
var T: byte;
var BA: string;
begin
Result:='';
BA:='';
{Get array of octets}
while Num>0 do
begin
BA:=BA+char($7F and Num);
Num:=Num shr 7;
end;
{Reverse data and flag more data is coming}
Result:='';
for I:=Length(BA) downto 1 do
begin
T:=Byte(BA[I]);
if I<>1 then T:=T or $80;
Result:=Result+char(T);
end;
end;
function VLQToNumber(VLQ: string): int64;
{Convert Variable-Length Quantity VLQ Octets (bytes) to numbers}
{Octet = 7-bit data and MSB indicating the last data item = 0 }
{Note: String are being used as byte-array because they are easy}
var I: integer;
var T: byte;
var BA: string;
begin
Result:=0;
for I:=1 to Length(VLQ) do
Result:=(Result shl 7) or (Byte(VLQ[I]) and $7F);
end;
function VLQToString(VLQ: string): string;
{Convert VLQ to string of hex numbers}
var I: integer;
begin
Result:='(';
for I:=1 to Length(VLQ) do
begin
if I>1 then Result:=Result+', ';
Result:=Result+IntToHex(byte(VLQ[I]),2);
end;
Result:=Result+')';
end;
procedure ShowVLQ(Memo: TMemo; Num: int64);
var VLQ: string;
var I: int64;
var S: string;
begin
VLQ:=NumberToVLQ(Num);
S:=VLQToString(VLQ);
I:=VLQToNumber(VLQ);
Memo.Lines.Add('Original Number: '+Format('%x',[Num]));
Memo.Lines.Add('Converted to VLQ: '+Format('%s',[S]));
Memo.Lines.Add('Back to Original: '+Format('%x',[I]));
Memo.Lines.Add('');
end;
const Num1 = $0;
const Num2 = $7F;
const Num3 = $4000;
const Num4 = $1FFFFF;
const Num5 = $200000;
const Num6 = $3FFFFE;
const Num7 = $3311A1234DF31413;
procedure VariableLengthOctets(Memo: TMemo);
begin
ShowVLQ(Memo, Num1);
ShowVLQ(Memo, Num2);
ShowVLQ(Memo, Num3);
ShowVLQ(Memo, Num4);
ShowVLQ(Memo, Num5);
ShowVLQ(Memo, Num6);
ShowVLQ(Memo, Num7);
end;
</syntaxhighlight>
{{out}}
<pre>
Original Number: 0
Converted to VLQ: ()
Back to Original: 0
Original Number: 7F
Converted to VLQ: (7F)
Back to Original: 7F
Original Number: 4000
Converted to VLQ: (81, 80, 00)
Back to Original: 4000
Original Number: 1FFFFF
Converted to VLQ: (FF, FF, 7F)
Back to Original: 1FFFFF
Original Number: 200000
Converted to VLQ: (81, 80, 80, 00)
Back to Original: 200000
Original Number: 3FFFFE
Converted to VLQ: (81, FF, FF, 7E)
Back to Original: 3FFFFE
Original Number: 3311A1234DF31413
Converted to VLQ: (B3, 88, E8, A4, B4, EF, CC, A8, 13)
Back to Original: 3311A1234DF31413
Elapsed Time: 42.717 ms.
</pre>
=={{header|Erlang}}==
Line 893 ⟶ 1,280:
i2v=: a. {~ [:;}.@(N+//.@,:N&#.inv)&.>
ifv=: v2i :. i2v
vfi=: i2v :. v2i
av=: 3 u: ] </syntaxhighlight>
<code>ifv</code> is an invertible function which gets an (unsigned, arbitrary precision) integer sequence from a variable-length quantity sequence. <code>vfi</code> is an invertable function which gets a variable-length quantity sequence from an unsigned integer sequence. <code>av</code> displays character code numbers corresponding to the characters in its argument.
Line 899 ⟶ 1,287:
Example use:
<syntaxhighlight lang="j">
av vlq=: vfi numbers
127 129 128 0 0 129 255 255 126 255 255 127 140 154 64
Line 1,012 ⟶ 1,399:
assert.strictEqual(got_back_number, number);
});</syntaxhighlight>
=={{header|jq}}==
{{works with|jq}}
'''Also works with gojq and fq, the Go implementations'''
'''With minor tweaks, also works with jaq, the Rust implementation'''
<syntaxhighlight lang=jq>
# "VARIABLE-LENGTH QUANTITY"
# A VLQ is a variable-length encoding of a number into a sequence of octets,
# with the most-significant octet first, and with the most significant bit first in each octet.
# The first (left-most) bit in each octet is a continuation bit: all octets except the last have the left-most bit set.
# The bits of the original number are taken 7 at a time from the right to form the octets.
# Thus, if the number is between 0 and 127, it is represented exactly as one byte.
# Produce a stream of the base $b "digits" of the input number,
# least significant first, with a final 0
def digits($b):
def mod: . % $b;
def div: ((. - mod) / $b);
recurse( select(. > 0) | div) | mod ;
# 2 <= $b <= 36
def tobase($b):
def digit: "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[.:.+1];
if . == 0 then "0"
else [digits($b) | digit] | reverse[1:] | add
end;
# input: a decimal integer
# output: the corresponding variable-length quantity expressed as an array of strings of length 2,
# each representing an octet in hexadecimal notation, with most-significant octet first.
def vlq:
def lpad: if length == 2 then . else "0" + . end;
[digits(128) + 128] | reverse[1:] | .[-1] -=128 | map(tobase(16) | lpad);
# Input: a VLQ as produced by vlq/0
# Output: the corresponding decimal
def vlq2dec:
def x2d: # convert the character interpreted as a hex digit to a decimal
explode[0] as $x
| if $x < 65 then $x - 48 elif $x < 97 then $x - 55 else $x - 87 end;
map( ((.[0:1] | x2d) * 16) + (.[1:] | x2d) - 128)
| .[-1] += 128 # the most significant bit of the least significant octet
| reduce reverse[] as $x ({x: 0, m: 1}; .x += ($x * .m) | .m *= 128)
| .x ;
# The task
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
2097152, 2097151
| vlq as $vlq
| "\(lpad(8)) => \($vlq|join(",")|lpad(12)) => \($vlq | vlq2dec | lpad(8))"
</syntaxhighlight>
{{output}}
<pre>
2097152 => 81,80,80,00 => 2097152
2097151 => FF,FF,7F => 2097151
</pre>
=={{header|Julia}}==
Line 1,632 ⟶ 2,079:
=={{header|Raku}}==
(formerly Perl 6)
vlq_encode() returns a string of
<syntaxhighlight lang="raku" line>sub vlq_encode ($number is copy) {
my
$number +>= 7;
while ($number) {
$number +>= 7;
}
@vlq.reverse.join: ':';
}
sub vlq_decode ($string
sum $string.split(':').reverse.map: {(:16($_) +& 127) +< (7 × $++)}
}
Line 1,660 ⟶ 2,100:
0x200000
) -> $testcase {
printf "%8s %12s %8s\n", $testcase,
my $encoded = vlq_encode($testcase),
vlq_decode($encoded);
}</syntaxhighlight>
Line 1,718 ⟶ 2,157:
All 4 numbers are OK.
</pre>
=={{header|RPL}}==
{{works with|Halcyon Calc|4.2.8}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
R→B { } SWAP 1 SF
'''WHILE''' DUP #0 ≠ '''REPEAT'''
DUP #7Fh AND
'''IF''' 1 FC?C '''THEN''' #80h OR '''END''''
ROT + SWAP
1 7 '''START''' SR '''NEXT '''
'''END''' DROP
≫ ''''R→VLQ'''' STO
≪
#0 SWAP 1 OVER SIZE '''FOR''' j
DUP j GET #7Fh AND
ROT SLB SR + SWAP
'''NEXT''' DROP B→R
≫ ''''VLQ→R'''' STO
|
'''R→VLQ''' ''( n -- { #VLQ } )''
initialize stack and flag
scan the input number
keep last 7 bits
set sign bit if not the first set of 7 bits
store in list
shift 7 bits right
clean stack
'''R→VLQ''' ''( { #VLQ } -- n )''
initialize stack and VLQ scan
get a byte, remove 1st bit
multiply previous sum by 128 then add byte
clean stack, convert to floating point
|}
{{in}}
<pre>
2097152 R→VLQ
2097151 R→VLQ
106903 R→VLQ
DUP VLQ→R
</pre>
{{out}}
<pre>
4: { #81h #80h #80h #0h }
3: { #FFh #FFh #7Fh }
2: { #86h #C3h #17h }
1: 106903
</pre>
Line 1,987 ⟶ 2,482:
This number requires two 32-bit units to store. Because <code>uint32</code> is in the native endian, opposite to the big endian storage of the integer, the words come out byte swapped. The <code>be-uint32</code> type could be used to change this.
=={{header|Wren}}==
{{libheader|Wren-fmt}}
{{libheader|Wren-str}}
<syntaxhighlight lang="
import "./str" for Str
var toOctets = Fn.new { |n|
Line 2,156 ⟶ 2,521:
System.print(fromOctets.call(octets))
}</syntaxhighlight>
{{out}}
<pre>
2097152 -> Ox81 Ox80 Ox80 Ox00 -> 2097152
2097151 -> Oxff Oxff Ox7f -> 2097151
</pre>
=={{header|XPL0}}==
Line 2,203 ⟶ 2,574:
81 FF FF 7E
8F FF FF FF 7F
</pre>
| |||