Зачем менять местами байты в кодировке переменной длины в Thrift CompactProtocol?

Мне было интересно, почему вам приходилось менять местами байты в Trift CompactProtocol при кодировании целых чисел с переменной длиной.

Example taken from Приложения, интенсивно использующие данные (онлайн, стр. 120):

Number in Base 10 to be encoded: 1337
1337 in Base 2: 0010100 111001
Encoding first byte:  1|111011|0
Encoding second byte: 0|0010100

Как видите, байты поменялись местами. Почему это?

Дополнительная информация: Первый бит в первом байте означает, что впереди еще один байт. Последний бит в первом байте представляет знак (в данном случае положительный). Первый бит в последнем знаке означает, что больше нет дополнительных байтов, принадлежащих этому числу.


encoding thrift integer variable-length
person User12547645    schedule 01.02.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Это эффективный способ кодирования небольших целых чисел или, точнее, небольших абсолютных значений. Идея очень хорошо объясняется в документации по protobuf:

Кодирование ZigZag сопоставляет целые числа со знаком с целыми числами без знака, так что числа с небольшим абсолютным значением (например, -1) также имеют небольшое значение, закодированное в варианте. Он делает это таким образом, что "зигзагами" проходит вперед и назад между положительными и отрицательными целыми числами, так что -1 кодируется как 1, 1 кодируется как 2, -2 кодируется как 3 и т.д. можно увидеть в следующей таблице [...]

Небольшие абсолютные значения - очень распространенный случай. Большие значения встречаются довольно редко. Следовательно, для большинства случаев использования мы будем носить с собой много (ненужных) нулей без какой-либо дополнительной ценности. К сожалению, для отрицательных значений это немного сложнее, потому что мы должны заботиться о бите знака.

Алгоритм ZigZag позаботится об этом очень элегантно и очень эффективно.

person JensG    schedule 01.02.2019
comment
но они разные, 1337 в каждом: - экономный способ: 0xf214 (в книге) - ZigZag кодировка: 0x0a72 ((1337‹‹ 1)^(1337››63)) - person 홍한석; 31.08.2020