Резюме. Понимание установки битов, очистки и арифметики указателя полезно при изучении протоколов p2p и низкоуровневого кода, задействованного в протоколах консенсуса. Также важно знать, почему одни алгоритмы предпочтительнее других, особенно при изучении мотивации каждого фрагмента кода, существующего в протоколе. Системы, которые имеют тысячи участников в консенсусе по шагам блокировки, должны быть построены таким образом, чтобы поощрять согласованность и эффективность, но также должны быть удобочитаемыми для инженеров, работающих над кодом. Надеюсь, этот и другие посты будут способствовать образованию по этой теме и демистифицировать некоторые загадочные коды, которые существуют в коде самого низкого уровня технологического стека.
Битовый сдвиг
Читая о MiniSSDPd (http://miniupnp.free.fr/minissdpd.html), мы обнаружили метод кодирования длины, которого раньше не видели. Вот его краткое описание: «Первый байт запроса - это тип запроса. Отправленные или полученные строки не заканчиваются нулем, а имеют префикс в соответствии с их длиной в формате переменной длины. Используйте следующие макросы для кодирования и декодирования в этот формат: "
Наша цель - пройти от нуля к точному пониманию 100% этого, казалось бы, сложного и запутанного кода, раскрыть, что он на самом деле делает, какова его история и предназначение.
Прежде чем углубиться, давайте вспомним несколько тем, которые необходимы для понимания приведенного выше кода:
- «Установка» и «очистка» битов с поразрядными
AND
иOR
- Арифметика указателей и массивы
- Первый байт установлен в
0x01
для правила протокола, не имеющего отношения к этому сообщению.
Оператор левого сдвига: `<<
`
Битовый сдвиг - это побитовая операция, которая сдвигает биты влево или вправо. Лишние биты, смещенные за допустимые пределы, отбрасываются.
Оператор правого сдвига: `>>
`
При сдвиге влево биты, заполненные на противоположной стороне, являются нулями. В качестве примера, вот результат сдвига 32-битного целого числа без знака 0xae
(174
в десятичной системе) влево на две позиции:
Однако предположим, что целое число является 8-битным, а не 32-битным. Сдвиг 8-битного целого числа 0xae
влево на две позиции приведет к тому, что вместо этого будут отброшены самые левые биты:
Сравните это с приведенными выше результатами. Опять же, обратите внимание, что биты, добавленные справа, являются нулями.
Очистка и установка битов с помощью побитового И и ИЛИ
При работе с целыми числами без знака оператор сдвига вправо действует точно так же, как оператор сдвига влево, но в противоположном направлении.
Однако при использовании целого числа со знаком оператор сдвига вправо работает немного иначе. Крайние левые биты заполняются с использованием знакового бита для сохранения знака. Вот некоторые примеры:
В приведенном выше примере отрицательное число -82
сдвинуто на две позиции по битам, а крайние левые биты заполнены 1
. Давайте попробуем другой пример, на этот раз целые числа со знаком битового сдвига вправо, а не влево.
В этом примере положительное число 75
сдвинуто на две позиции вправо. Однако крайние левые биты заполняются 0
, потому что q
- положительное число.
Клиринговые биты
Побитовые операторы позволяют устанавливать и очищать биты. Не зная этого, может быть трудно понять мотивацию или цель таких выражений:
Давайте разберемся, почему этот код используется в макросе, который мы изучаем выше.
Установка битов
Это выражение *p&0x7f
является частью макроса CODELENGTH
. Но что это значит? Давайте разберемся. *p
указывает на значение, в нашем примере это 0xaa
. &
- это побитовый оператор AND. 0x7f
это 01111111
. Давайте расширим выражение *p&0x7f
.
Как видно выше, использование поразрядного AND
очистит все биты в позиции, совпадающей с нулем. В этом случае использование &0x7f
всегда очищает первый бит (устанавливает его в ноль). Однако из-за поведения работы с числом с поразрядным AND
все остальные биты остаются в покое, потому что им соответствует 1
. Это делает побитовое AND
в сочетании с числами типа 0x7f
чрезвычайно мощным для очистки отдельных битов, оставляя другие нетронутыми.
Выражение *(p++)&0x80
также используется в макросе CODELENGTH
. Давайте посмотрим, как это работает, если значение, на которое указывает *(p++)
, снова, например, 0xaa
.
Все биты в позиции, совпадающей с 0
, очищаются, а бит в первой позиции остается прежним, потому что он совпадает с 1
.
Указатели не волшебство
Установка битов аналогична очистке битов. Используя поразрядный оператор OR|
, любые биты в позиции, совпадающей с 1
, устанавливаются в 1
.
Например, этот код в макросе CODELENGTH
всегда будет устанавливать первый бит в единицу:
Допустим, n >> 7
оценивается как 0x3b
, давайте разберемся, как OR
операция, примененная к 0x3b
, устанавливает первый бит:
В этом случае был установлен первый бит, а остальные остались нетронутыми.
Собираем все вместе
Здесь не так много всего, что сбивает с толку указатели, кроме операции *(p++) = …
, которая похожа на высказывание установите указатель p
на это значение, затем сделайте шаг p
вперед. Вот ускоренный курс по указателям: (https://www.cs.rpi.edu/academics/courses/fall18/csci1200/lectures/05_pointers.pdf).
Работа с битами с использованием битового сдвига
Давайте еще раз посмотрим на макрос CODELENGTH
.
Чтобы разбить макрос CODELENGTH
, проще всего начать снизу и двигаться вверх, поэтому давайте посмотрим на первую строку снизу:
Помните из раздела битов очистки, что 0x7f = 01111111
, которое в сочетании с побитовой операцией AND
приводит к очищению первого бита.
Вторая строка снизу:
Помните раздел битов установки, 0x80 = 10000000
, который в сочетании с побитовой операцией OR
приводит к установке первого бита.
Соединяя эти две строки вместе, мы можем заключить, что для любого целого числа p
длины 127
или ниже первый бит будет очищен, а остальная часть n
будет сохранена в p
с использованием поразрядной AND
операции: *(p++) = n & 0x7f;
. Это работает, потому что 127
- это наибольшее целое число, которое может уместиться в 7 битах:
Теперь, глядя на вторую строку снизу, когда n
больше 128 (но меньше 16384), он сохранит n
сдвинутых на 7 бит вправо в p
с установленным первым битом, а затем переместит указатель на один байт вперед. Переходя к первой строке снизу, последние 7 бит, которые изначально были сдвинуты вправо, теперь будут сохранены в p
после нуля.
Двигаясь вверх на несколько строк снизу, мы видим, что этот шаблон повторяется для чисел, равных 1 плюс максимальное целое число, которое может быть сохранено в каждом кратном 7 битах:
…и так далее.
Давайте посмотрим на это во фрагменте кода, поскольку это реализовано в MiniSSDPd с уже определенным CODELENGTH
:
В приведенном выше примере кода мы будем использовать макрос CODELENGTH
и функцию void DECODELENGTH
, аналогичную макросу DECODELENGTH
из MiniSSDPd:
Вот результат выполнения приведенного выше кода:
Первая двоичная строка - это значение ASCII имени устройства ”urn:”…
. Второй разделен на три части.
- Второй байт (иначе известный как
n
) - это целое число с кодировкой переменной длины для имени устройства. n
байтов после длины содержат имя устройства.- Величина переменной длины обеспечивает удобное средство представления произвольно больших целых чисел без создания излишне больших целых чисел фиксированной ширины.
В конце n
печатается в шестнадцатеричном виде 0x33
или 51
в десятичном виде. Если это еще не имеет смысла, попробуйте сравнить это с тем, как хранится имя устройства длиной 153
:
Обратите внимание, что буфер в этом случае имеет длину 2 байта. Первый байт, 1000 0001
, использует первый установленный бит, чтобы сообщить программе, что есть еще один байт в пределах переменной длины. Второй байт 0001 1001
затем объединяется с первым байтом для хранения длины. Давайте разберемся:
Удаление сигнальных битов из двоичных строк, оставление оставшихся 7-битных полезных данных:
Объединение двух двоичных строк:
10011001 = 153
, и мы видим, что функция DECODELENGTH
в этой программе правильно выполняет итерацию по p
, чтобы найти n = 0x99
.
10011001 = 0x99 = 153
.
Тайна раскрыта! Это формат переменной длины для хранения длины буфера в протоколе, отправляющем информацию переменной длины по сети в сетевой библиотеке p2p.
Интересный факт: этот формат переменной длины был впервые изобретен для формата файлов MIDI в начале 2000-х годов. Таблица с примерами существует в спецификации MIDI, что также является мотивацией для создания такого формата:
- Величина переменной длины представляет собой серию 7-битовых значений от наиболее значимого до наименее значимого. где последний байт последовательного бита 7 (старший значащий бит) установлен в 0, а в предыдущих байтах бит 7 установлен в 1.
- Источник: «https://www.csie.ntu.edu.tw/~r92092/ref/midi/#vlq»
- Правовая информация: этот документ и содержащаяся в нем информация были предоставлены вам компанией Galaxy Digital Holdings LP и ее аффилированными лицами (Galaxy Digital) исключительно в информационных целях. Этот документ не может быть воспроизведен или распространен полностью или частично в любом формате без письменного разрешения Galaxy Digital. Ни информация, ни какое-либо мнение, содержащиеся в этом документе, не являются предложением о покупке или продаже или предложением о покупке или продаже каких-либо консультационных услуг, ценных бумаг, фьючерсов, опционов или других финансовых инструментов или участия в каких-либо консультационных услугах. услуги или торговая стратегия. Ничто, содержащееся в этом документе, не является инвестиционной, юридической или налоговой консультацией. Вам следует провести собственное расследование и оценить содержащуюся здесь информацию. Любые решения, основанные на информации, содержащейся в этом документе, являются исключительной ответственностью читателя. Некоторые утверждения в этом документе отражают взгляды, оценки, мнения или прогнозы Galaxy Digital (которые могут быть основаны на собственных моделях и предположениях, включая, в частности, взгляды Galaxy Digital на текущий и будущий рынок определенных цифровых активов), и нет гарантировать, что эти взгляды, оценки, мнения или прогнозы на данный момент точны или что они в конечном итоге будут реализованы. В той степени, в которой эти допущения или модели неверны или изменяются обстоятельства, фактическая производительность может существенно отличаться от приведенных здесь оценок и быть меньше них. Ни компания Galaxy Digital, ни ее аффилированные лица, акционеры, партнеры, члены, директора, должностные лица, руководство, сотрудники или представители не делают никаких заявлений или гарантий, явных или подразумеваемых, в отношении точности или полноты любой информации или любой другой информации. (сообщается в письменной или устной форме) передается или предоставляется вам. Каждая из вышеупомянутых сторон прямо отказывается от любой ответственности, связанной с использованием этой информации или возникшей в результате ее использования. Определенная информация, содержащаяся в данном документе (включая финансовую информацию), была получена из опубликованных и неопубликованных источников. Такая информация не проверялась независимым образом Galaxy Digital, и Galaxy Digital не несет ответственности за точность такой информации. Филиалы Galaxy Digital инвестируют в некоторые цифровые активы и протоколы, обсуждаемые в этом документе, включая Биткойн. За исключением случаев, когда указано иное, информация в этом документе основана на вопросах, существующих на дату подготовки, а не на какую-либо дату в будущем, и не будет обновляться или иным образом исправляться для отражения информации, которая впоследствии становится доступной, или существующих обстоятельств. или изменения, происходящие после даты настоящего Соглашения. По всем вопросам обращайтесь по адресу [email protected]. © Авторские права Galaxy Digital Holdings LP 2019. Все права защищены.
Основы понимания кода протокола