This is an automated email from the ASF dual-hosted git repository.
Jens-G pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/thrift.git
The following commit(s) were added to refs/heads/master by this push:
new fd8763dd9 No ticket: Clarify when the zigzag encoding is used. Client:
all Patch: Andrew Bell
fd8763dd9 is described below
commit fd8763dd95b58bc6b789e947f2c7282f285d6cdd
Author: Andrew Bell <[email protected]>
AuthorDate: Wed May 20 18:35:50 2026 +0200
No ticket: Clarify when the zigzag encoding is used.
Client: all
Patch: Andrew Bell
This closes #3503
---
doc/specs/thrift-compact-protocol.md | 154 +++++++++++++++++++----------------
1 file changed, 85 insertions(+), 69 deletions(-)
diff --git a/doc/specs/thrift-compact-protocol.md
b/doc/specs/thrift-compact-protocol.md
index 3e1c4b454..b73df4dce 100644
--- a/doc/specs/thrift-compact-protocol.md
+++ b/doc/specs/thrift-compact-protocol.md
@@ -1,4 +1,4 @@
-Thrift Compact protocol encoding
+Thrift Compact protocol encoding
================================
<!--
@@ -24,7 +24,7 @@ under the License.
--------------------------------------------------------------------
-->
-This documents describes the wire encoding for RPC using the Thrift *compact
protocol*.
+This documents describes the encoding for RPC using the Thrift *compact
protocol*.
The information here is _mostly_ based on the Java implementation in the
Apache thrift library (version 0.9.1) and
[THRIFT-110 A more compact
format](https://issues.apache.org/jira/browse/THRIFT-110). Other implementation
however,
@@ -35,6 +35,8 @@ For background on Thrift see the [Thrift whitepaper
(pdf)](https://thrift.apache
# Contents
* Compact protocol
+ * ZigZag encoding
+ * Varint encoding
* Base types
* Message
* Struct
@@ -44,26 +46,30 @@ For background on Thrift see the [Thrift whitepaper
(pdf)](https://thrift.apache
# Compact protocol
-## Base types
-
-### Integer encoding
+### ZigZag encoding
-The _compact protocol_ uses
[ZigZag](https://en.wikipedia.org/wiki/Variable-length_quantity#Zigzag_encoding)'ed
-varint (aka [ULEB128](https://en.wikipedia.org/wiki/LEB128)) encoding.
+Integers that *might* be negative are transformed using
+[ZigZag](https://en.wikipedia.org/wiki/Variable-length_quantity#Zigzag_encoding)
+encoding. Zigzag encoding maps signed integers to another domain, one where
the sign bit
+is encoded in the least significant bit (LSB). For example 0 maps to 0, -1 to
1, 1 to 2, -2 to 3,
+etc., hence the term zigzag. Mapping the sign bit to the LSB is important for
compactness when
+the absolute value of the value is small.
-Values of type `int8` are encoded as one byte, rest are converted to `int64`,
Zigzag'ed then encoded as varint.
-Zigzag encoding maps signed integers to another domain, one where the sign bit
is encoded in the least significant
-bit (LSB). For example 0 maps to 0, -1 to 1, 1 to 2, -2 to 3, etc. Hence the
term zigzag. Mapping the sign bit to
-the LSB is important for compactness when the absolute value of the value is
small, as ULEB encoding is more
-efficient for small values. Here are the (Scala) formulas to convert from
`int64` to a zigzag `int64` and back:
+Here are the (Scala) formulas to convert from `int64` to a zigzag `int64` and
back:
```scala
def ToZigzag(n: Long): Long = (n << 1) ^ (n >> 63)
def FromZigzag(n: Long): Long = (n >>> 1) ^ - (n & 1)
```
-A ULEB128 is encoded 7-bits at a time, starting from the LSB. Each 7-bits are
encoded as 8-bits with the top bit set
-if this is not the last byte, unset otherwise.
+### Varint encoding
+
+Integers larger than a single byte are encoded using varint
+(aka [ULEB128](https://en.wikipedia.org/wiki/LEB128)) encoding.
+
+A ULEB128 value is encoded 7 bits at a time,
+starting from the LSB. Each 7 bits are encoded as 8 bits with the top bit set
+if it is not the last byte.
For example, the integer 50399 is encoded as follows:
@@ -75,15 +81,21 @@ For example, the integer 50399 is encoded as follows:
→ 0xDF 0x89 0x03 (write to ram LSB first)
```
-Varints are sometimes used directly inside the compact protocol to represent
positive numbers.
+## Base types
+
+### Integer encoding
+
+Values of type `i8` and `byte` are encoded as one byte.
+Values of type `i16`, `i32` and `i64` are first transformed to using
[ZigZag](#zigzag-encoding)
+and that result is then [varint](#varint-encoding) encoded before being
written.
### Enum encoding
-The generated code encodes `Enum`s by taking the ordinal value and then
encoding that as an `int32`.
+`enum`s are encoded as their integer value as defined by the Thrift IDL.
### Binary encoding
-Binary is sent as follows:
+`binary` is sent as follows:
```
Binary protocol, binary data, 1+ bytes:
@@ -94,32 +106,32 @@ Binary protocol, binary data, 1+ bytes:
Where:
-* `byte length` is the length of the byte array, using varint encoding (must
be >= 0).
+* `byte length` is the length of the byte array (non-negative), encoded as a
+ [varint](#varint-encoding) (**not** [ZigZag'ed](#zigzag-encoding)).
* `bytes` are the bytes of the byte array.
### String encoding
-*String*s are first encoded to UTF-8, and then send as binary. They do not
include a NUL delimiter.
+`string`s are written as [binary](#binary-encoding) and must be encoded as
UTF-8. Strings do
+ not include a NULL(0) terminator.
### Double encoding
-Values of type `double` are first converted to an `int64` according to the
IEEE 754 floating-point "double format"
-bit layout. Most run-times provide a library to make this conversion. But
while the binary protocol encodes the
-`int64` in 8 bytes in big endian order, the compact protocol encodes it in
little endian order - this is due to an
-early implementation bug that finally became the de-facto standard.
+Values of type `double` are written in IEEE 754 format (the standard
representation on almost
+all systems) in little-endian byte order (8 bytes).
### Boolean encoding
-Booleans are encoded differently depending on whether it is a field value (in
a struct) or an element value (in a set,
-list or map). Field values are encoded directly in the field header. Element
values of type `bool` are sent as an
-`int8`; true as `1` and false as `2`.
+`bool`s are encoded differently depending on whether a field value (in a
struct) or an
+element value (in a set, list or map). Field values are encoded directly in
the field header.
+Element values of type `bool` are sent as an `i8`; true as `1` and false as
`2`.
### Universal unique identifier encoding
-Values of `uuid` type are expected as 16-byte binary in big endian order. Byte
order conversion might be necessary on
-certain platforms, e.g. Windows holds GUIDs in a complex record-like structure
whose memory layout differs.
-
-*Note*: Since the length is fixed, no `byte length` prefix is necessary and
the field is always 16 bytes long.
+Values of `uuid` type are not encoded. That is, the 128 bits that make up the
source `uuid`
+are written without modification. UUIDs not stored in the
+[standard big-endian
format](https://en.wikipedia.org/wiki/Universally_unique_identifier#Encoding)
+should be converted to such before encoding with the compact protocol.
## Message
@@ -127,19 +139,19 @@ A `Message` on the wire looks as follows:
```
Compact protocol Message (4+ bytes):
-+--------+--------+--------+...+--------+--------+...+--------+--------+...+--------+
-|pppppppp|mmmvvvvv| seq id | name length | name
|
-+--------+--------+--------+...+--------+--------+...+--------+--------+...+--------+
++--------+--------+--------+...+--------+--------+...+--------+
+|pppppppp|mmmvvvvv| seq id | name |
++--------+--------+--------+...+--------+--------+...+--------+
```
Where:
* `pppppppp` is the protocol id, fixed to `1000 0010`, 0x82.
-* `mmm` is the message type, an unsigned 3 bit integer.
-* `vvvvv` is the version, an unsigned 5 bit integer, fixed to `00001`.
-* `seq id` is the sequence id, a signed 32 bit integer encoded as a varint.
-* `name length` is the byte length of the name field, a signed 32 bit integer
encoded as a varint (must be >= 0).
-* `name` is the method name to invoke, a UTF-8 encoded string.
+* `mmm` is the message type, an unsigned 3-bit value.
+* `vvvvv` is the version, an unsigned 5-bit integer, fixed to `00001`.
+* `seq id` is the sequence id, a signed 32-bit value encoded as a
[varint](#varint-encoding).
+ The value is **not** [ZigZag'ed](#zigzag-encoding).
+* `name` is the method name to invoke, encoded as a [string](#string-encoding).
Message types are encoded with the following values:
@@ -150,8 +162,9 @@ Message types are encoded with the following values:
### Struct
-A *Struct* is a sequence of zero or more fields, followed by a stop field.
Each field starts with a field header and
-is followed by the encoded field value. The encoding can be summarized by the
following BNF:
+A `struct` is a sequence of zero or more fields, followed by a stop field.
Each field
+other than a stop field starts with a field header and is followed by the
encoded field value.
+The encoding can be summarized by the following BNF:
```
struct ::= ( field-header field-value )* stop-field
@@ -159,19 +172,18 @@ field-header ::= field-type field-id
```
Because each field header contains the field-id (as defined by the Thrift IDL
file), the fields can be encoded in any
-order. Thrift's type system is not extensible; you can only encode the
primitive types and structs. Therefore is also
-possible to handle unknown fields while decoding; these are simply ignored.
While decoding the field type can be used to
-determine how to decode the field value.
+order. Thrift's type system is not extensible; you can only encode the
primitive types and structs. Therefore it is also
+possible to handle unknown fields while decoding by ignoring them. The field
type is used to determine how to decode field values.
-Note that the field name is not encoded so field renames in the IDL do not
affect forward and backward compatibility.
+Note that the fields are identified by their integer value and not their name.
The default Java implementation (Apache Thrift 0.9.1) has undefined behavior
when it tries to decode a field that has
another field-type than what is expected. Theoretically this could be detected
at the cost of some additional checking.
Other implementation may perform this check and then either ignore the field,
or return a protocol exception.
-A *Union* is encoded exactly the same as a struct with the additional
restriction that at most 1 field may be encoded.
+A `union` is encoded the same as a struct with the additional restriction that
at most 1 field may be encoded.
-An *Exception* is encoded exactly the same as a struct.
+An `exception` is encoded exactly the same as a struct.
### Struct encoding
@@ -186,7 +198,7 @@ Compact protocol field header (1 to 3 bytes, long form) and
field value:
|0000tttt| field id | field value |
+--------+--------+...+--------+--------+...+--------+
-Compact protocol stop field:
+Compact protocol stop-field:
+--------+
|00000000|
+--------+
@@ -194,13 +206,14 @@ Compact protocol stop field:
Where:
-* `dddd` is the field id delta, an unsigned 4 bits integer, strictly positive.
-* `tttt` is field-type id, an unsigned 4 bit integer.
-* `field id` the field id, a varint (int16). Max field id is 32767.
-* `field-value` the encoded field value.
+* `dddd` is the field id delta, an unsigned 4-bit integer.
+* `tttt` is field-type, an unsigned 4-bit integer (see below).
+* `field id` the field id (i16), [ZigZag'ed](#zigzag-encoding)
[varint](#varint-encoding) encoded.
+* `field-value` is the encoded field value.
-The field id delta can be computed by `current-field-id - previous-field-id`,
or just `current-field-id` if this is the
-first of the struct. The short form should be used when the field id delta is
in the range 1 - 15 (inclusive).
+The field id delta can be computed by `current-field-id - previous-field-id`,
or just
+`current-field-id` if this is the first of the struct. The short form should
be used when
+the field id delta is in the range 1 - 15 (inclusive).
The following field-types can be encoded:
@@ -223,8 +236,8 @@ length (0 bytes).
## List and Set
-List and sets are encoded the same: a header indicating the size and the
element-type of the elements, followed by the
-encoded elements.
+`list`s and `set`s are encoded the same: a header indicating the size and the
element-type of
+the elements, followed by the encoded elements.
```
Compact protocol list header (1 byte, short form) and elements:
@@ -240,9 +253,10 @@ Compact protocol list header (2+ bytes, long form) and
elements:
Where:
-* `ssss` is the size, 4 bit unsigned int, values `0` - `14`
-* `tttt` is the element-type, a 4 bit unsigned int
-* `size` is the size, a varint (int32), positive values `15` or higher
+* `ssss` is the size, 4-bit unsigned values `0` - `14`
+* `tttt` is the element-type, a 4-bit unsigned value
+* `size` is the size, an unsigned 32-bit [varint](#varint-encoding),
+ `15` or higher (**not** [ZigZag encoded](#zigzag-encoding)).
* `elements` are the encoded elements
The short form should be used when the length is in the range 0 - 14
(inclusive).
@@ -262,15 +276,15 @@ The following element-types are used (see note 1 below):
* `STRUCT`, used for structs and union fields, encoded as `12`
* `UUID`, encoded as `13`
-*Note*:
+*Note*:
1. Although field-types and element-types lists are currently very similar,
there is _no guarantee_ that this will
remain true after new types are added.
-2. For historical and compatibility reasons, a reader should be capable to
deal with *both* cases.
-The only valid value in the original spec was `2`, but due to an widespread
implementation bug the defacto
+2. For historical and compatibility reasons, a reader should be capable to
deal with *both* cases.
+The only valid value in the original spec was `2`, but due to an widespread
implementation bug the defacto
standard across large parts of the library became `1` instead. As a result,
both values are now allowed.
-The maximum list/set size is configurable. By default there is no limit
(meaning the limit is the maximum int32 value:
-2147483647).
+The maximum list/set size is configurable. By default there is no limit
(meaning the limit
+is the maximum signed 32-bit integer value: 2147483647).
## Map
@@ -297,15 +311,17 @@ Compact protocol map header (2+ bytes, non empty map) and
key value pairs:
Where:
-* `size` is the size, a var int (int32), strictly positive values
-* `kkkk` is the key element-type, a 4 bit unsigned int
-* `vvvv` is the value element-type, a 4 bit unsigned int
+* `size` is the 32-bit unsigned size, [varint](#varint-encoding) encoded
+ (**not** [ZigZag'ed](#zigzag-encoding)).
+* `kkkk` is the key element-type, a 4-bit unsigned value
+* `vvvv` is the value element-type, a 4-bit unsigned value
* `key value pairs` are the encoded keys and values
-The element-types are the same as for lists. The full list is included in the
'List and set' section.
+The element-types are the same as for lists. The full list is included in the
+'List and set' section.
-The maximum map size is configurable. By default there is no limit (meaning
the limit is the maximum int32 value:
-2147483647).
+The maximum map size is configurable. By default there is no limit
+(meaning the limit is the maximum 32-bit value: 2147483647).
# BNF notation used in this document
