[Protocol Buffers] Base 128 Varints

프로토콜 버퍼의 인코딩 방식을 이해하려면 우선 Varint를 이해해야 한다. Varint는 하나 이상의 바이트를 사용해 정수를 직렬화 하는 방법으로 숫자가 작을수록 적은 바이트 수를 차지하게 된다. (아주 큰 숫자가 아니면 데이터 크기가 절약된다.)

Varint에서 마지막 바이트를 제외한 각 바이트의 최상위 비트(msb)는 1로 하기로 약속되어 있다. 이는 앞으로 올 바이트가 더 있음을 나타내기 위함이다. 

반대로 msb가 0이라면 Varint의 끝을 의미하게 된다. 따라서 1바이트를 차지하는 Varint로 표현할 수 있는 가장 큰 숫자는 127(0111 1111)이 된다. 또 하나의 룰로 Varint는 최하위 그룹을 먼저 위치시키는 방식을 택한다. (least significant group first).

표현 예시.

웹 페이지 설명에 나온 것처럼 숫자 1은 1바이트로 표현이 가능하므로 msb는 0이 되고 표현은 '0000 0001'이 된다.

그렇다면 숫자 300은 어떻게 표현될까? 앞서 언급된 것처럼 숫자 300은 하나의 바이트로 표현이 불가능 하므로 첫 바이트의 msb는 1로 셋 되어야 한다.

결과적으로 숫자 300은 아래와 같이 표현된다.

→ 1010 1100 0000 0010

여기서 msb를 떼면 010 1100 000 0010이 되는데, 앞서 적혀있는 대로 최하위 그룹이 먼저 위치하게 되므로 우리가 이해하는 숫자로 인식하기 위해선 7비트 단위 그룹의 위치를 서로 바꾸어 주어야 한다.

따라서 010 1100 000 0010은, 000 0010 010 1100 되어야 하고, 의미 없는 비트를 버린 뒤 두 그룹을 연결하면

→ 100101100 = 300 (256 + 32 + 8 + 4)이 된다.

https://developers.google.com/protocol-buffers/docs/encoding#varints