Variable length quantity, unsigned integer, base128, big-endian: GraphViz block diagram (.dot) source

A variable-length unsigned integer using base128 encoding. 1-byte groups consist of 1-bit flag of continuation and 7-bit value chunk, and are ordered "most significant group first", i.e. in "big-endian" manner.

This particular encoding is specified and used in:

  • Standard MIDI file format
  • ASN.1 BER encoding
  • RAR 5.0 file format

More information on this encoding is available at https://en.wikipedia.org/wiki/Variable-length_quantity

This particular implementation supports serialized values to up 8 bytes long.

KS implementation details

License: CC0-1.0
Minimal Kaitai Struct required: 0.9

References

This page hosts a formal specification of Variable length quantity, unsigned integer, base128, big-endian using Kaitai Struct. This specification can be automatically translated into a variety of programming languages to get a parsing library.

GraphViz block diagram source

vlq_base128_be.dot

Download 

digraph {
	rankdir=LR;
	node [shape=plaintext];
	subgraph cluster__vlq_base128_be {
		label="VlqBase128Be";
		graph[style=dotted];

		vlq_base128_be__seq [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
			<TR><TD BGCOLOR="#E0FFE0">pos</TD><TD BGCOLOR="#E0FFE0">size</TD><TD BGCOLOR="#E0FFE0">type</TD><TD BGCOLOR="#E0FFE0">id</TD></TR>
			<TR><TD PORT="groups_pos">0</TD><TD PORT="groups_size">1</TD><TD>Group</TD><TD PORT="groups_type">groups</TD></TR>
			<TR><TD COLSPAN="4" PORT="groups__repeat">repeat until !(_.has_next)</TD></TR>
		</TABLE>>];
		vlq_base128_be__inst__last [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
			<TR><TD BGCOLOR="#E0FFE0">id</TD><TD BGCOLOR="#E0FFE0">value</TD></TR>
			<TR><TD>last</TD><TD>groups.length - 1</TD></TR>
		</TABLE>>];
		vlq_base128_be__inst__value [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
			<TR><TD BGCOLOR="#E0FFE0">id</TD><TD BGCOLOR="#E0FFE0">value</TD></TR>
			<TR><TD>value</TD><TD>(((((((groups[last].value + (last &gt;= 1 ? groups[last - 1].value &lt;&lt; 7 : 0)) + (last &gt;= 2 ? groups[last - 2].value &lt;&lt; 14 : 0)) + (last &gt;= 3 ? groups[last - 3].value &lt;&lt; 21 : 0)) + (last &gt;= 4 ? groups[last - 4].value &lt;&lt; 28 : 0)) + (last &gt;= 5 ? groups[last - 5].value &lt;&lt; 35 : 0)) + (last &gt;= 6 ? groups[last - 6].value &lt;&lt; 42 : 0)) + (last &gt;= 7 ? groups[last - 7].value &lt;&lt; 49 : 0))</TD></TR>
		</TABLE>>];
		subgraph cluster__group {
			label="VlqBase128Be::Group";
			graph[style=dotted];

			group__seq [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
				<TR><TD BGCOLOR="#E0FFE0">pos</TD><TD BGCOLOR="#E0FFE0">size</TD><TD BGCOLOR="#E0FFE0">type</TD><TD BGCOLOR="#E0FFE0">id</TD></TR>
				<TR><TD PORT="has_next_pos">0</TD><TD PORT="has_next_size">1b</TD><TD>b1be→bool</TD><TD PORT="has_next_type">has_next</TD></TR>
				<TR><TD PORT="value_pos">0:1</TD><TD PORT="value_size">7b</TD><TD>b7be</TD><TD PORT="value_type">value</TD></TR>
			</TABLE>>];
		}
	}
	vlq_base128_be__seq:groups_type -> group__seq [style=bold];
	group__seq:has_next_type -> vlq_base128_be__seq:groups__repeat [color="#404040"];
	vlq_base128_be__seq:groups_type -> vlq_base128_be__inst__last [color="#404040"];
	group__seq:value_type -> vlq_base128_be__inst__value [color="#404040"];
	vlq_base128_be__inst__last:last_type -> vlq_base128_be__inst__value [color="#404040"];
}