This is the 21st day of my participation in the August Text Challenge.More challenges in August

Introduction to the

How does a protocol buffer, which is a great way to encode information, actually work at the bottom? Why can it achieve efficient and fast data transmission? It all starts with the way it’s coded.

Define a simple message

We know that the main body of a Protocol buffer is a message, so let’s start with a simple message and explain how protobuf is encoded in detail.

For example, here is a very simple message object:

message Student {
  optional int32 age = 1;
}
Copy the code

In the example above, we define a Student message object and give it a field named age and a value called 22. It is then serialized using a protobuf, an object of this size, and the bytes it serializes are as follows:

08 96, 00Copy the code

Very simple, you can represent a Messag object with three bytes, and the amount of data is very small.

So what do these three bytes mean? Take a look.

Base 128 Varints

Before we explain the meaning of the above three bytes, we need to understand the concept of varints.

What are Varints? A small integer takes up a small amount of space while a large integer takes up a large amount of space. In this way, there is no need to fix a specific length, which can reduce the length of data, but brings about complexity of parsing.

So how do you know how many bytes are needed for this data? In a protobuf, the highest bit of each byte is a judgment bit. If this bit is set to 1, it indicates that the next byte and this byte are the same number. If this bit is set to 0, it indicates that the next byte is unrelated to this byte and data ends at this byte.

For example, a byte is 8 bits. If the byte represents the integer 1, it can be represented by the following byte:

0000, 0001,Copy the code

If an integer does not fit into a single byte, then multiple bytes are required for concatenation, such as 300:

1010 1100 0000 0010
Copy the code

Why 300? First, look at the first byte, whose prefix is 1, indicating that there is another byte following it. Look at the second byte, which starts with 0, indicating that we are done. Let’s get rid of the judgment bits and replace them with the following numbers:

010 1100 000 0010
Copy the code

For a protobuf, the byte number is reversed, so we need to swap the two bytes:

000 0010 010 1100 
Copy the code

That is:

10, 010, 1100Copy the code

=256 + 32 + 8 + 4 = 300

The structure of the message body

The structure of a protobuf message body is key=value, where the key is the integer value 1,2,3,4 of the field defined in message. And value is the actual value set to it.

When a message is encoded, the keys and values are concatenated to form a Byte stream. When parsing it, you need to locate the specific length of the key and value, so the key needs to contain two parts. The first part is the value of the field in the PROto file, and the second part is the length occupied by the value part.

Only by combining the values of these two parts can the parser parse the field correctly.

This form of key is called wire types. What wire types are there? Let’s see:

type	meaning	Usage scenarios
0	Varint	int32, int64, uint32, uint64, sint32, sint64, bool, enum
1	64-bit	fixed64, sfixed64, double
2	Length-delimited	string, bytes, embedded messages, packed repeated fields
3	Start group	groups (deprecated)
4	End group	groups (deprecated)
5	32-bit	fixed32, sfixed32, float

It can be seen that except for 3 and 4 types, the other types can be divided into three types. The first type is fixed length type, such as 1 and 5, which are 64-bit and 32-bit digits respectively.

The second type is 0, which represents Varint, which is a mutable type used to represent general numeric types, bool types and enumerations. The third type, 2, represents the length – dependent type, which is usually used to represent strings, byte numbers, etc.

All the key is a varint type, its value is: (field_number < < 3) | wire_type, that is to say the last three key, used to store the wire type.

The value of key in our example above is 08, expressed in binary:

000, 1000,Copy the code

The last three digits are 0, which means it’s a Varint. Move 08 three Spaces right to get 1, which means the key is the field 1, which is the age.

And then let’s look at the rest of this 96, 00, in binary:

96 00 = 1001 0110  0000 0000
Copy the code

By Varint’s definition, the first byte represents the connection bit, indicating that the contents of the second byte are together with the contents of the first byte. For Varint, we need to swap the lowest byte with the highest byte as follows:

1001 0110 0000 0000 discard the highest bit 1:001 0110 0000 0000 swap the lowest and highest bits: 0000 0000 001 0110Copy the code

The value above is 16 + 4 + 2 = 22

So we have a key of value 1, value 22.

integer

We know that there are two ways to represent signed integers: the standard int types int32 and int64, and the signed int types sint32 and sint64.

The two types differ in the representation of the corresponding negative integers. For int32 and int64, all negative integers are represented in ten bytes, so they take up too much space to represent negative integers.

If sint32 and sint64 are used, the ZigZag encoding is used, which is more efficient for negative integers.

ZigZag maps signed and unsigned integers, and for each n, it will be encoded using the following formula:

(n << 1) ^ (n >> 31)
Copy the code

For sint64, this is:

(n << 1) ^ (n >> 64)
Copy the code

Here’s an example:

integer	Coding results
0	0
– 1	1
1	2
2 –	3
2147483647	4294967294
– 2147483648.	4294967295

string

The wire type of the string is 2, indicating that its value is the length of a varint encoding. Here’s an example:

 message Student {
  optional string name = 2;
}
Copy the code

We define the second attribute name for Student. If we assign name to “testing”, we get the encoding:

12 07 [74 65 73 74 69 6e 67]
Copy the code

The encoding in brackets is the UTF8 representation of “testing”.

0x12 can be resolved like this:

 0x12
→ 0001 0010  (binary representation)
→ 00010 010  (regroup bits)
→ field_number = 2, wire_type = 2
Copy the code

0x12 indicates that field 2 is of type 2, followed by 07 which indicates the length of subsequent bytes.

Nested messages

Messages can be nested within a message. Let’s look at an example:

message Teacher {
  optional Student s = 3;
}
Copy the code

If we set the age field of S to 22, as in the first example, the encoding above would be:

 1a 03 08 96 00
Copy the code

You can see that the next three bytes are the same as in the first example. The first two bytes are the same value as the string, so I won’t go into more details.

conclusion

Okay, basic coding rules and implementations for Protobuf are covered. Sounds wonderful, doesn’t it?

This article is available at www.flydean.com/03-protobuf…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!