Variable-length quantity - Revision history

Jsummers at 15:50, 16 September 2017

2017-09-16T15:50:09Z

Jsummers: Category:Number formats

2017-09-16T15:35:39Z

Category:Number formats

Jsummers: /* Links */

2017-08-26T13:37:39Z

‎Links

Jsummers: Partial rewrite

2017-08-23T19:21:52Z

Partial rewrite

Jsummers: Jsummers moved page Variable-length base-128 to Variable-length quantity: Slightly generalizing this article

2017-08-23T19:18:30Z

Jsummers moved page Variable-length base-128 to Variable-length quantity: Slightly generalizing this article

Jsummers: Changed primary category

2015-12-04T18:59:53Z

Changed primary category

Jsummers at 01:13, 14 January 2015

2015-01-14T01:13:57Z

Jsummers: /* Related formats */

2015-01-14T01:00:16Z

‎Related formats

Jsummers: /* Related formats */

2014-12-27T14:59:11Z

‎Related formats

Jsummers: Created page with "{{FormatInfo |formattype=electronic |subcat=Binary Data }} '''Variable-length base-128''' refers a family of formats for encoding arbitrarily large integers. It does not seem ..."

2014-12-27T14:16:38Z

Created page with "{{FormatInfo |formattype=electronic |subcat=Binary Data }} '''Variable-length base-128''' refers a family of formats for encoding arbitrarily large integers. It does not seem ..."

New page

{{FormatInfo
|formattype=electronic
|subcat=Binary Data
}}
'''Variable-length base-128''' refers a family of formats for encoding arbitrarily large integers. It does not seem to have a well-established name, though it's sometimes called '''variable-length quantity''' ('''VLQ'''), and specific forms of it may be given names by the specifications that use them.

== Details ==
The integer to be encoded is written in binary, then partitioned into as many 7-bit blocks as necessary, each of which is stored in a byte. The remaining bit in each byte (usually the most-significant bit) is used as a flag to indicate whether there are any more bytes. Most commonly, the flag bit is 1 in every byte except the last.

Both little-[[Endianness|endian]] (where the 7 data bits of the first byte are the least-significant 7 bits of the encoded integer) and big-endian (where they are the most-significant) variants exist.

The encoded integer may be unsigned, or it may be a signed integer using, e.g., [[two's complement]] representation.

== Related formats ==
Among the formats that use variable-length base-128 are:
* [[BPG]]
* [[DWARF]]
* [[MIDI]]
* [[Protobuf]]
* [[WBMP]]

== Links ==
* [[Wikipedia:Variable-length quantity|Wikipedia: Variable-length quantity]]
* [[Wikipedia:LEB128|Wikipedia: LEB128]]

@@ Line 5: / Line 5: @@
 By '''variable-length quantity''' ('''VLQ'''), we refer to a variety of schemes for encoding an integer in a variable number of [[byte]]s, where the required number of bytes grows as the magnitude of the integer grows. Such formats can encode arbitrarily large integers, though artificial limits are sometimes imposed.
-As far as we know, there is no official standard for such number formats. Each file format specification that uses them typically uses its own definition, and invents its own name.
+As far as we know, there is no widely-used standard for such number formats. Each file format specification that uses them typically uses its own definition, and invents its own name.
 == Details ==
@@ Line 23: / Line 23: @@
 * [[BPG]] ("ue7")
 * [[DWARF]] ("LEB128", "ULEB128", "SLEB128")
-* [[HLP (WinHelp)]] and [[Segmented Hypergraphics]] ("compressed short"). The "compressed long" type is a 16-bit variant.
+* [[HLP (WinHelp)]] and [[Segmented Hypergraphics]] ("compressed short" and "compressed long").
 * [[MIDI]] ("variable-length quantity")
 * [[Protobuf]] ("base 128 varint")

← Older revision		Revision as of 15:35, 16 September 2017
Line 34:		Line 34:
	* [http://formats.kaitai.io/vlq_base128_le/index.html Kaitai Struct: vlq_base128_le]		* [http://formats.kaitai.io/vlq_base128_le/index.html Kaitai Struct: vlq_base128_le]

−	[[Category:~~Integer~~ formats]]	+	[[Category:Number formats]]

@@ Line 3: / Line 3: @@
 |subcat=Elements of File Formats
 }}
-'''Variable-length base-128''' refers a family of formats for encoding arbitrarily large integers. It does not seem to have a well-established name, though it's sometimes called '''variable-length quantity''' ('''VLQ'''), and specific forms of it may be given names by the specifications that use them.
+By '''variable-length quantity''' ('''VLQ'''), we refer to a variety of schemes for encoding an integer in a variable number of [[byte]]s, where the required number of bytes grows as the magnitude of the integer grows. Such formats can encode arbitrarily large integers, though artificial limits are sometimes imposed.
-== Details ==
+As far as we know, there is no official standard for such number formats. Each file format specification that uses them typically uses its own definition, and invents its own name.
-The integer to be encoded is written in binary, then partitioned into as many 7-bit blocks as necessary, each of which is stored in a byte. The remaining bit in each byte (usually the most-significant bit) is used as a flag to indicate whether there are any more bytes. Most commonly, the flag bit is 1 in every byte except the last.
-Both little-[[Endianness|endian]] (where the 7 data bits of the first byte are the least-significant 7 bits of the encoded integer) and big-endian (where they are the most-significant) variants exist.
+== Details ==
-The encoded integer may be unsigned, or it may be a signed integer using, e.g., [[two's complement]] representation.
+Even this simple case has a combinatorial explosion of variants:
-Many variations are possible. Instead of bytes, 16-bit (base-32768) or larger code units can be used. If there is a defined limit on the number of bytes (or code units), then for maximal-length codes, the final byte's flag bit can be repurposed.
+Instead of having one flag bit per byte, there could be one every two bytes, resulting in a base-32768 encoding.
 == Related formats ==
-Among the formats that use variable-length base-128 are:
+Among the formats that use variable-length quantities are:
 * [[BPG]] ("ue7")
 * [[DWARF]] ("LEB128", "ULEB128", "SLEB128")
@@ Line 27: / Line 32: @@
 * [[Wikipedia:LEB128|Wikipedia: LEB128]]
-[[Category:Binary Data]]
+[[Category:Integer formats]]

@@ Line 11: / Line 11: @@
 The encoded integer may be unsigned, or it may be a signed integer using, e.g., [[two's complement]] representation.
 == Related formats ==
@@ Line 16: / Line 18: @@
 * [[BPG]] ("ue7")
 * [[DWARF]] ("LEB128", "ULEB128", "SLEB128")
-* [[HLP (WinHelp)]] and [[Segmented Hypergraphics]] ("compressed short"). The "compressed long" type is a 16-bit (base-32768) variant.
+* [[HLP (WinHelp)]] and [[Segmented Hypergraphics]] ("compressed short"). The "compressed long" type is a 16-bit variant.
 * [[MIDI]] ("variable-length quantity")
 * [[Protobuf]] ("base 128 varint")

@@ Line 16: / Line 16: @@
 * [[BPG]] ("ue7")
 * [[DWARF]] ("LEB128", "ULEB128", "SLEB128")
 * [[MIDI]] ("variable-length quantity")
 * [[Protobuf]] ("base 128 varint")

@@ Line 1: / Line 1: @@
 {{FormatInfo
 |formattype=electronic
-|subcat=Binary Data
+|subcat=Elements of File Formats
 }}
 '''Variable-length base-128''' refers a family of formats for encoding arbitrarily large integers. It does not seem to have a well-established name, though it's sometimes called '''variable-length quantity''' ('''VLQ'''), and specific forms of it may be given names by the specifications that use them.
@@ Line 26: / Line 26: @@
 * [[Wikipedia:Variable-length quantity|Wikipedia: Variable-length quantity]]
 * [[Wikipedia:LEB128|Wikipedia: LEB128]]