Резюме. Понимание установки битов, очистки и арифметики указателя полезно при изучении протоколов p2p и низкоуровневого кода, задействованного в протоколах консенсуса. Также важно знать, почему одни алгоритмы предпочтительнее других, особенно при изучении мотивации каждого фрагмента кода, существующего в протоколе. Системы, которые имеют тысячи участников в консенсусе по шагам блокировки, должны быть построены таким образом, чтобы поощрять согласованность и эффективность, но также должны быть удобочитаемыми для инженеров, работающих над кодом. Надеюсь, этот и другие посты будут способствовать образованию по этой теме и демистифицировать некоторые загадочные коды, которые существуют в коде самого низкого уровня технологического стека.

Битовый сдвиг

Читая о MiniSSDPd (http://miniupnp.free.fr/minissdpd.html), мы обнаружили метод кодирования длины, которого раньше не видели. Вот его краткое описание: «Первый байт запроса - это тип запроса. Отправленные или полученные строки не заканчиваются нулем, а имеют префикс в соответствии с их длиной в формате переменной длины. Используйте следующие макросы для кодирования и декодирования в этот формат: "

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

Прежде чем углубиться, давайте вспомним несколько тем, которые необходимы для понимания приведенного выше кода:

  1. «Установка» и «очистка» битов с поразрядными AND и OR
  2. Арифметика указателей и массивы
  3. Первый байт установлен в 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:”…. Второй разделен на три части.

  1. Второй байт (иначе известный как n) - это целое число с кодировкой переменной длины для имени устройства.
  2. n байтов после длины содержат имя устройства.
  3. Величина переменной длины обеспечивает удобное средство представления произвольно больших целых чисел без создания излишне больших целых чисел фиксированной ширины.

В конце 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. Все права защищены.

Основы понимания кода протокола