Integers
All integers are encoded using the LEB128 variable-length integer encoding, in either unsigned or signed variant.
Unsigned integers are encoded in unsigned LEB128 format.
As an additional constraint, the total number of bytes encoding a value of type \(\href{../syntax/values.html#syntax-int}{\mathit{u}N}\) must not exceed \(\mathrm{ceil}(N/7)\) bytes.
\[\begin{split}\begin{array}{llclll@{\qquad}l}
\def\mathdef1983#1{{}}\mathdef1983{unsigned integer} & \href{../binary/values.html#binary-int}{\def\mathdef1984#1{{\mathtt{u}#1}}\mathdef1984{N}} &::=&
n{:}\href{../binary/values.html#binary-byte}{\mathtt{byte}} &\Rightarrow& n & (\mathrel{\mbox{if}} n < 2^7 \wedge n < 2^N) \\ &&|&
n{:}\href{../binary/values.html#binary-byte}{\mathtt{byte}}~~m{:}\def\mathdef2026#1{{\mathtt{u}#1}}\mathdef2026{(N\mathtt{-7})} &\Rightarrow&
2^7\cdot m + (n-2^7) & (\mathrel{\mbox{if}} n \geq 2^7 \wedge N > 7) \\
\end{array}\end{split}\]
Signed integers are encoded in signed LEB128 format, which uses a two’s complement representation.
As an additional constraint, the total number of bytes encoding a value of type \(\href{../syntax/values.html#syntax-int}{\mathit{s}N}\) must not exceed \(\mathrm{ceil}(N/7)\) bytes.
\[\begin{split}\begin{array}{llclll@{\qquad}l}
\def\mathdef1983#1{{}}\mathdef1983{signed integer} & \href{../binary/values.html#binary-int}{\def\mathdef1990#1{{\mathtt{s}#1}}\mathdef1990{N}} &::=&
n{:}\href{../binary/values.html#binary-byte}{\mathtt{byte}} &\Rightarrow& n & (\mathrel{\mbox{if}} n < 2^6 \wedge n < 2^{N-1}) \\ &&|&
n{:}\href{../binary/values.html#binary-byte}{\mathtt{byte}} &\Rightarrow& n-2^7 & (\mathrel{\mbox{if}} 2^6 \leq n < 2^7 \wedge n \geq 2^7-2^{N-1}) \\ &&|&
n{:}\href{../binary/values.html#binary-byte}{\mathtt{byte}}~~m{:}\def\mathdef2027#1{{\mathtt{s}#1}}\mathdef2027{(N\mathtt{-7})} &\Rightarrow&
2^7\cdot m + (n-2^7) & (\mathrel{\mbox{if}} n \geq 2^7 \wedge N > 7) \\
\end{array}\end{split}\]
Uninterpreted integers are encoded as signed integers.
\[\begin{array}{llclll@{\qquad\qquad}l}
\def\mathdef1983#1{{}}\mathdef1983{uninterpreted integer} & \href{../binary/values.html#binary-int}{\def\mathdef1995#1{{\mathtt{i}#1}}\mathdef1995{N}} &::=&
n{:}\href{../binary/values.html#binary-int}{\def\mathdef1990#1{{\mathtt{s}#1}}\mathdef1990{N}} &\Rightarrow& i & (\mathrel{\mbox{if}} n = \href{../exec/numerics.html#aux-signed}{\mathrm{signed}}_N(i))
\end{array}\]
Note
The side conditions \(N > 7\) in the productions for non-terminal bytes of the \(\def\mathdef2028#1{{\mathit{u#1}}}\mathdef2028{}\) and \(\def\mathdef2029#1{{\mathit{s#1}}}\mathdef2029{}\) encodings restrict the encoding’s length.
However, “trailing zeros” are still allowed within these bounds.
For example, \(\def\mathdef2030#1{\mathtt{0x#1}}\mathdef2030{03}\) and \(\def\mathdef2031#1{\mathtt{0x#1}}\mathdef2031{83}~\def\mathdef2032#1{\mathtt{0x#1}}\mathdef2032{00}\) are both well-formed encodings for the value \(3\) as a \(\href{../syntax/values.html#syntax-int}{\mathit{u8}}\).
Similarly, either of \(\def\mathdef2033#1{\mathtt{0x#1}}\mathdef2033{7e}\) and \(\def\mathdef2034#1{\mathtt{0x#1}}\mathdef2034{FE}~\def\mathdef2035#1{\mathtt{0x#1}}\mathdef2035{7F}\) and \(\def\mathdef2036#1{\mathtt{0x#1}}\mathdef2036{FE}~\def\mathdef2037#1{\mathtt{0x#1}}\mathdef2037{FF}~\def\mathdef2038#1{\mathtt{0x#1}}\mathdef2038{7F}\) are well-formed encodings of the value \(-2\) as a \(\href{../syntax/values.html#syntax-int}{\mathit{s16}}\).
The side conditions on the value \(n\) of terminal bytes further enforce that
any unused bits in these bytes must be \(0\) for positive values and \(1\) for negative ones.
For example, \(\def\mathdef2039#1{\mathtt{0x#1}}\mathdef2039{83}~\def\mathdef2040#1{\mathtt{0x#1}}\mathdef2040{10}\) is malformed as a \(\href{../syntax/values.html#syntax-int}{\mathit{u8}}\) encoding.
Similarly, both \(\def\mathdef2041#1{\mathtt{0x#1}}\mathdef2041{83}~\def\mathdef2042#1{\mathtt{0x#1}}\mathdef2042{3E}\) and \(\def\mathdef2043#1{\mathtt{0x#1}}\mathdef2043{FF}~\def\mathdef2044#1{\mathtt{0x#1}}\mathdef2044{7B}\) are malformed as \(\href{../syntax/values.html#syntax-int}{\mathit{s8}}\) encodings.
Names
Names are encoded as a vector of bytes containing the Unicode (Section 3.9) UTF-8 encoding of the name’s character sequence.
\[\begin{split}\begin{array}{llclllll}
\def\mathdef1983#1{{}}\mathdef1983{name} & \href{../binary/values.html#binary-name}{\mathtt{name}} &::=&
b^\ast{:}\href{../binary/conventions.html#binary-vec}{\mathtt{vec}}(\href{../binary/values.html#binary-byte}{\mathtt{byte}}) &\Rightarrow& \href{../syntax/values.html#syntax-name}{\mathit{name}}
&& (\mathrel{\mbox{if}} \href{../binary/values.html#binary-utf8}{\mathrm{utf8}}(\href{../syntax/values.html#syntax-name}{\mathit{name}}) = b^\ast) \\
\end{array}\end{split}\]
The auxiliary \(\href{../binary/values.html#binary-utf8}{\mathrm{utf8}}\) function expressing this encoding is defined as follows:
\[\begin{split}\begin{array}{@{}l@{}}
\begin{array}{@{}lcl@{\qquad}l@{}}
\href{../binary/values.html#binary-utf8}{\mathrm{utf8}}(c^\ast) &=& (\href{../binary/values.html#binary-utf8}{\mathrm{utf8}}(c))^\ast \\[1ex]
\href{../binary/values.html#binary-utf8}{\mathrm{utf8}}(c) &=& b &
(\begin{array}[t]{@{}c@{~}l@{}}
\mathrel{\mbox{if}} & c < \def\mathdef2045#1{\mathrm{U{+}#1}}\mathdef2045{80} \\
\wedge & c = b) \\
\end{array} \\
\href{../binary/values.html#binary-utf8}{\mathrm{utf8}}(c) &=& b_1~b_2 &
(\begin{array}[t]{@{}c@{~}l@{}}
\mathrel{\mbox{if}} & \def\mathdef2046#1{\mathrm{U{+}#1}}\mathdef2046{80} \leq c < \def\mathdef2047#1{\mathrm{U{+}#1}}\mathdef2047{800} \\
\wedge & c = 2^6(b_1-\def\mathdef2048#1{\mathtt{0x#1}}\mathdef2048{C0})+(b_2-\def\mathdef2049#1{\mathtt{0x#1}}\mathdef2049{80})) \\
\end{array} \\
\href{../binary/values.html#binary-utf8}{\mathrm{utf8}}(c) &=& b_1~b_2~b_3 &
(\begin{array}[t]{@{}c@{~}l@{}}
\mathrel{\mbox{if}} & \def\mathdef2050#1{\mathrm{U{+}#1}}\mathdef2050{800} \leq c < \def\mathdef2051#1{\mathrm{U{+}#1}}\mathdef2051{D800} \vee \def\mathdef2052#1{\mathrm{U{+}#1}}\mathdef2052{E000} \leq c < \def\mathdef2053#1{\mathrm{U{+}#1}}\mathdef2053{10000} \\
\wedge & c = 2^{12}(b_1-\def\mathdef2054#1{\mathtt{0x#1}}\mathdef2054{E0})+2^6(b_2-\def\mathdef2055#1{\mathtt{0x#1}}\mathdef2055{80})+(b_3-\def\mathdef2056#1{\mathtt{0x#1}}\mathdef2056{80})) \\
\end{array} \\
\href{../binary/values.html#binary-utf8}{\mathrm{utf8}}(c) &=& b_1~b_2~b_3~b_4 &
(\begin{array}[t]{@{}c@{~}l@{}}
\mathrel{\mbox{if}} & \def\mathdef2057#1{\mathrm{U{+}#1}}\mathdef2057{10000} \leq c < \def\mathdef2058#1{\mathrm{U{+}#1}}\mathdef2058{110000} \\
\wedge & c = 2^{18}(b_1-\def\mathdef2059#1{\mathtt{0x#1}}\mathdef2059{F0})+2^{12}(b_2-\def\mathdef2060#1{\mathtt{0x#1}}\mathdef2060{80})+2^6(b_3-\def\mathdef2061#1{\mathtt{0x#1}}\mathdef2061{80})+(b_4-\def\mathdef2062#1{\mathtt{0x#1}}\mathdef2062{80})) \\
\end{array} \\
\end{array} \\
\mathrel{\mbox{where}} b_2, b_3, b_4 < \def\mathdef2063#1{\mathtt{0x#1}}\mathdef2063{C0} \\
\end{array}\end{split}\]
Note
Unlike in some other formats, name strings are not 0-terminated.
