REVO7000õVariable Length QuantityPü-- https://rosettacode.org/wiki/Variable-length_quantity#LiveCode
-- This task was completed a different (and better) way a long time ago
-- in UDI's PMD/MakeSMF Lib for LiveCode (back when it was MetaCard).
-- Here is my own (and probably slower) version. -- Paul McClernan
Function DecToVLQ tInput
put tInput into it
-- Ask "Enter base 10 value:" -- input dialog box
if it is not empty
then
if it is a number then
put it into theString
if isWholeNumString(theString) is false
then -- I think there is built in equivalent for this but I rolled my own!
answer "Only Whole Decimal Numbers Are Allowed!"
exit DecToVLQ
end if
if theString>4294967295 then
answer "This function fails with whole numbers over 4294967295!"&cr\
& "4294967295 is the maximum allowed value for 32bits (4 bytes)"
exit DecToVLQ
end if
if theString>268435455 then
answer "This function is not accurate with whole numbers over 268435455!"&cr\
& "268435455 is the maximum allowed value for 28bit (7bits per byte) MIDI delta-time VLQ"
end if
return "Original Whole Number="& theString & cr & \
"Original Whole Number in Hex="& baseConvert(theString,10,16) & cr & \ --- LC's built in baseConvert function
"Variable Length Quantity in Hex=" & wholeNumToVLQ(theString) -- into fld "Output"
else
answer "Only Whole Decimal Numbers Are Allowed!"
end if
end if
end DecToVLQ
function wholeNumToVLQ theWholeNum
-- baseConvert(number,originalBase,destinationBase) -- there is also bitwise operations in LC but I took the long road
if theWholeNum < 127 then -- if it fits into a single 7bit byte value and theres no need to process it
put baseConvert(theWholeNum,10,16) into VQLinHex
if the number of chars in VQLinHex=1 then put "0" before VQLinHex
return VQLinHex
exit wholeNumToVLQ
end if
put baseConvert(theWholeNum,10,2) into theBits
put number of chars in theBits into x
put 0 into bitCounter
put empty into the7bitBytes
repeat
if char x of theBits is not empty then
put char x theBits before the7bitBytes
delete char x of theBits
if theBits is empty then exit repeat
put number of chars in theBits into x
add 1 to bitCounter
if bitCounter=7 then
put "," before the7bitBytes
put 0 into bitCounter
next repeat
end if
else
exit repeat
end if
end repeat
get the number of chars in item 1 of the7bitBytes
if it<7 then
put 7 - it into x
repeat x
put "0" before item 1 of the7bitBytes
end repeat
end if
put the number of items in the7bitBytes into y
repeat with x = 1 to y
if x is not y then
put "1" before item x of the7bitBytes
else
put "0" before item x of the7bitBytes
end if
put baseConvert(item x of the7bitBytes,2,16) into item x of the7bitBytes
if the number of chars in item x of the7bitBytes<2 then put "0" before item x of the7bitBytes
put item x of the7bitBytes after VQLinHex
end repeat
return VQLinHex
end wholeNumToVLQ
function isWholeNumString theString
put the number of chars in theString into y
repeat with x = 1 to y
if char x of theString is not in "0123456789" then
return false
exit isWholeNumString
end if
end repeat
return true
end isWholeNumString
--Output:
--Original Whole Number=2097152
--Original Whole Number in Hex=200000
--Variable Length Quantity in Hex=81808000
--Convert back:
function VLQtoWholeNum theHexVLQ
if the number of chars of theHexVLQ < 3 and baseConvert(theHexVLQ,16,10) < 128
then
return baseConvert(theHexVLQ,16,10)
exit VLQtoWholeNum
else
-- The number must be an integer between zero and 4,294,967,295
if the number of chars of theHexVLQ < 3 then put theHexVLQ & "00" into theHexVLQ
put baseConvert(theHexVLQ,16,2) into theBits
put 0 into bitCounter
put empty into the8bitBytes
repeat
if char 1 of theBits is not empty then
put char 1 theBits after the8bitBytes
delete char 1 of theBits
if theBits is empty then exit repeat
add 1 to bitCounter
if bitCounter=8 then
put "," after the8bitBytes
put 0 into bitCounter
next repeat
end if
else
exit repeat
end if
end repeat
put the number of items in the8bitBytes into y
repeat with x = 1 to y
put char 1 of item x of the8bitBytes into lengthCntrlBit
delete char 1 of item x of the8bitBytes
if the number of chars in item x of the8bitBytes < 7 then
repeat 7 - (the number of chars in item x of the8bitBytes)
put "0" before item x of the8bitBytes
end repeat
end if
put item x of the8bitBytes after WholeNumInBinary
switch lengthCntrlBit
case "1"
next repeat
break
case "0"
exit repeat
break
end switch
end repeat
return baseConvert(WholeNumInBinary,2,10)
end if
end VLQtoWholeNum
function isHexString theString
---again there is probably an easier way to do this:
if char 1 to 2 of theString is "0x" then delete char 1 to 2 of theString
put the number of chars in theString into y
repeat with x = 1 to y
if char x of theString is not in "abcdefABCDEF0123456789" then
return false
end if
end repeat
end isHexString
on VLQHexToWholeNum
Ask "Enter Variable Length Quantity Hex Value:" -- input dialog
if it is not empty then
if char 1 to 2 of it is "0x" then delete char 1 to 2 of it
put it into hexString
if isHexString(hexString) is false then
answer "Only Valid Hex Digits Are Allowed!"
exit VLQHexToWholeNum
else
put "Original Variable Length Quantity in Hex="& hexString & cr & \
"Whole Number=" & VLQtoWholeNum(hexString) into fld "Output"
end if
end if
end VLQHexToWholeNum
--Output:
--Original Variable Length Quantity in Hex=FFFF7F
--Whole Number=2097151
€ïe,o=Variable-Length Quantity ÿÿÿÿUHelvetica,unicodecREVGeneral
stackfileversion7.0breakpointconditionsscripteditorvscrollscalefactorð?breakpointsbreakpointstatesscripteditorselection3825ê @,o:ìîïñòðô
ìField)`€6cREVGeneral
revUniqueIDP½|§uBê1920
'îEncode Decimal to VLQà‹pUon mouseUp
put fld 1 into tnumber
put DecToVLQ(tnumber) into fld 2
end mouseUp
€ÎšcREVGeneral
scripteditorselection36revUniqueID@Xƒ|§uBscripteditorvscroll
ïField)`€j=cREVGeneral
revUniqueID€†|§uBêOriginal Whole Number=1920
'4 Original Whole Number in Hex=780
'@$Variable Length Quantity in Hex=8F00
'H
ñField)`€ãcREVGeneral
revUniqueIDÐÛˆ}§uBê8F
'òDecode VLQ to DecimalàE‹pZon mouseUp
put fld 3 into tnumber
put VLQtoWholeNum(tnumber) into fld 4
end mouseUp
€ÁÎžcREVGeneral
scripteditorvscrollscripteditorselection57revUniqueIDÀÞˆ}§uB
ðField)`€=cREVGeneral
revUniqueIDÀÛˆ}§uBê1920
'
ôField†)`€4æBcREVGeneral
revUniqueID ¹Ž§uBê"Code from Paul McCleman posted in:
'D>https://rosettacode.org/wiki/Variable-length_quantity#LiveCode
'|
'Information from:
'"6https://en.wikipedia.org/wiki/Variable-length_quantity
'l
'Variable-length quantity
'0%From Wikipedia, the free encyclopedia
'J
'”This article is about codes that are a variable number of bytes. For a more general category of variable-bit-length codes, see variable-length code.
'(
'ôA variable-length quantity (VLQ) is a universal code that uses an arbitrary number of binary octets (eight-bit bytes) to represent an arbitrarily large integer. It was defined for use in the standard MIDI file format[1] to save additional space for a resource constrained system, and is also used in the later Extensible Music Format (XMF). A VLQ is essentially a base-128 representation of an unsigned integer with the addition of the eighth bit to mark continuation of bytes. See the example below.
'è
'îBase-128 is also used in ASN.1 BER encoding to encode tag numbers and Object Identifiers.[2] It is also used in the WAP environment, where it is called variable length unsigned integer or uintvar. The DWARF debugging format[3] defines a variant called LEB128 (or ULEB128 for unsigned numbers), where the least significant group of 7 bits are encoded in the first byte and the most significant bits are in the last byte (so effectively it is the little-endian analog of a variable-length quantity). Google's protocol buffers use a similar format to have compact representation of integer values,[4] as does Oracle's Portable Object Format (POF)[5] and the Microsoft .NET Framework's "7-bit encoded int" in the BinaryReader and BinaryWriter classes.[6]
'Ü
'«It's also used extensively in web browsers for source mapping - which contain a lot of integer line & column number mappings - to keep the size of the map to a minimum.[7]
'V
'General structure
'"
'·The encoding assumes an octet (an eight-bit byte) where the most significant bit (MSB), also commonly known as the sign bit, is reserved to indicate whether another VLQ octet follows.
'n
' VLQ Octet
'7 6 5 4 3 2 1 0
'27 26 25 24 23 22 21 20
'.A Bn
'.
'eIf A is 0, then this is the last VLQ octet of the integer. If A is 1, then another VLQ octet follows.
'Ê
'ªB is a 7-bit number [0x00, 0x7F] and n is the position of the VLQ octet where B0 is the least significant. The VLQ octets are arranged most significant first in a stream.
'T
'Removing Redundancy
'&
'9With the VLQ encoding described above, any number that can be encoded with N octets can also be encoded with more than N octets simply by prepending additional 0x80 octets. For example, the number 358 can be encoded as the 2-octet VLQ 0x8166 or the 3-octet VLQ 0x808166 or the 4-octet VLQ 0x80808166 and so forth.
'r
'åHowever, the VLQ format used in Git removes this prepending redundancy and extends the representable range of shorter VLQs by adding an offset to VLQs of 2 or more octets in such a way that the lowest possible value for such an (N+1)-octet VLQ becomes exactly one more than the maximum possible value for an N-octet VLQ. In particular, since a 1-octet VLQ can store a maximum value of 127, the minimum 2-octet VLQ (0x8000) is assigned the value 128 instead of 0. Conversely, the maximum value of such a 2-octet VLQ (0xff7f) is 16511 instead of just 16383. Similarly, the minimum 3-octet VLQ (0x808000) has a value of 16512 instead of zero, which means that the maximum 3-octet VLQ (0xffff7f) is 2113663 instead of just 2097151. And so forth.
'Ê
'Other variants
'
'&In the data format for Unreal Packages used by the Unreal Engine, a variable length quantity scheme called Compact Indices[8] is used. The only difference in this encoding is that the first VLQ has the sixth binary digit reserved to indicate whether the encoded integer is positive or negative.
'L
'First VLQ Octet
'7 6 5 4 3 2 1 0
',27 26 25 24 23 22 21 20
'.A B Cn
'*
'eIf A is 0, then this is the last VLQ octet of the integer. If A is 1, then another VLQ octet follows.
'Ê
'lIf B is 0, then the VLQ represents a positive integer. If B is 1, then the VLQ represents a negative number.
'Ø
'ªC is a 6-bit number [0x00, 0x3F] and n is the position of the VLQ octet where C0 is the least significant. The VLQ octets are arranged most significant first in a stream.
'T
'8Any consecutive VLQ octet follows the general structure.
'p
'EXAMPLES
'
'8Here is a worked out example for the decimal number 137:
'p
'=Represent the value in binary notation (e.g. 137 as 10001001)
'z¢Break it up in groups of 7 bits starting from the lowest significant bit (e.g. 137 as 0000001 0001001). This is equivalent to representing the number in base 128.
'DgTake the lowest 7 bits and that gives you the least significant byte (0000 1001). This byte comes last.
'ÎwFor all the other groups of 7 bits (in the example, this is 000 0001), set the MSB to 1 (which gives 1000 0001 in our example). Thus 137 becomes 1000 0001 0000 1001 where the bits in boldface are something we added. These added bits denote if there is another byte to follow or not. Thus, by definition, the very last byte of a variable length integer will have 0 as its MSB.
'î€Another way to look at this is to represent the value in base-128, and then set the MSB of all but the last base-128 digit to 1.
'
'FThe Standard MIDI File format specification gives more examples:[1][9]
'Œ
'*Integer Variable-length quantity
'T0x00000000 0x00
'$0x0000007F 0x7F
'$0x00000080 0x81 0x00
'.0x00002000 0xC0 0x00
'.0x00003FFF 0xFF 0x7F
'.0x00004000 0x81 0x80 0x00
'80x001FFFFF 0xFF 0xFF 0x7F
'8!0x00200000 0x81 0x80 0x80 0x00
'B!0x08000000 0xC0 0x80 0x80 0x00
'B!0x0FFFFFFF 0xFF 0xFF 0xFF 0x7F
'B
'õ `@
@
revOnline | RunRev