ASN.1 простыми словами (кодирование типа REAL)

Введение для Хабра

Приведённый ниже текст является на самом деле первыми двумя главами моей статьи "ASN.1 простыми словами". Так как сама статья достаточно большая по меркам Хабра я решил сначала проверить являются ли знания по кодированию простых типов востребованными на этом ресурсе. В случае положительной реакции аудитории я продолжу публикацию всех остальных глав.

Введение

Уже на протяжение достаточно большого периода мне приходится иметь дело с ASN.1. Мне посчастливилось работать как в сфере создания криптографических программ, так и в сфере телекоммуникаций. И в той, и в другой сфере изначально крайне активно и повсеместно используется стандарт ASN.1.

Однако и в процессе создания программ криптографической направленности, и в процессе создания программ для телекоммуникационной отрасли я постоянно встречался с одним и тем же мнением — ASN.1 это сложный и не понятный формат, а следовательно для кодирования / декодирования лучше применять сторонние компиляторы (а иногда даже другие стандарты кодирования передаваемой информации).

Одной из причин по которой сложилась ситуация, когда подавляющее большинство разработчиков программ считаю стандарт ASN.1 сложным, это отсутствие книг по данному вопросу. Да, не смотря на почтенный возраст данного стандарта, множество свободно распространяемых компиляторов и различных статей, всё ещё крайне мало книг (или даже статей в Интернете) где бы простым и понятным языком, с большим количеством примеров, прояснялись вопросы кодирования простых типов ASN.1.

Исправляя сложившуюся ситуацию данная статья отчасти служит неким пособием, помогающим даже не сталкивавшемуся ранее с этим форматом человеку разобраться в тонкостях кодирования ASN.1. Статья охватывает вопросы исключительно только кодирования простых (не составных) типов — REAL, INTEGER, OBJECT IDENTIFIER, все виды строк, BOOLEAN, NULL, SEQUENCE, SET. В статье приводится подробнейшее объяснение всех тонкостей кодирования для каждого из типов, также приводятся подробные примеры, поясняющий тонкости кодирования для данного типа. В отдельном файле, прилагающемся к данной статье, можно найти код на С++, формирующий все примеры из статьи. Кроме того в этом файле с примерами приводятся дополнительные материалы, не рассмотренные в рамках данной статьи.  Все материалы статьи опираются на последний стандарт ASN.1 от 2008 года, все составляющие под-стандарты которого можно скачать одним файлом по ссылке http://www.itu.int/rec/T-REC-X.680-X.693-200811-I/en. Если это специально не оговаривается, то приведенные в статье примеры кодируют типы в стандарте ASN.1 BER (Basic Encoding Rules).

В большинстве пособий и книг по ASN.1 изучение кодирования начинается с простейших, не сложных, типов и заканчивается наисложнейшими. В этой статье порядок будет строго противоположный — читателю сначала будет предложено изучить кодирование сложных типов, и только потом постепенно перейдём к изучению простейших. Это позволит однажды усвоив методы кодирования для сложного типа просто и быстро понять методику кодирования более простого.

Глава 1. Общие правила кодирования ASN.1

Первично всё же необходимо пояснить некоторые основы кодирования в формате ASN.1.

Для начала поясним для чего же создавался этот стандарт. В мире существует множество различных компьютеров. И кроме того существует множество стандартов представления данных в этих компьютерах. ASN.1 создавался как некий общий стандарт, позволяющий описывать произвольную информацию, которая бы понималась любым компьютером, имеющим представление об этом стандарте. В стандарте ASN.1 поэтому предъявляются жесткие правила кодирования даже на уровне отдельных битов информации, а также взаимного их расположения. Дополнительно нужно сказать, что стандарт ASN.1 кодирует информацию не в виде текста, а виде двоичных последовательностей. Сейчас уже появились вариации форматов кодирования, позволяющие представлять данные и в виде текста (XML), но обзор этих форматов выходит за рамки данной статьи. Здесь мы рассмотрим только самое сложное — двоичное кодирование (формат ASN.1 BER — Basic Encoding Rules).

Данные закодированные в формате ASN.1 данные представляют из себя последовательность байт (или "октетов"), которые идут один за другим, без каких либо разрывов. Последовательность закодированную в ASN.1 можно передавать по линиям связи, сохранять в файл — блок закодированной информации в ASN.1 уже содержит необходимое описание его общей длины и содержимого.

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

1. Часть идентификатора блока (до нескольких октетов);
2. Часть общей длины блока (до нескольких октетов);
3. Часть, содержащая собственно значение, которое переносит этот блок (до нескольких октетов);

Кроме этого может быть ещё 4-ая, не обязательная часть — часть октетов окончания значения блока (несколько октетов). Про эту часть будет рассказано несколько позже.

Перейдём к описанию каждой части ASN.1-кодированного блока.

Часть идентификатора блока состоит минимум из одного октета. Формат этого первого октета строго фиксирован.

• биты 8 и 7 (старшие биты, обычно их записывают крайними слева) кодируют так называемый "класс" текущего блока;
• бит 6 должен быть установлен в 0 если текущий блок содержит информацию только об одном значении и должен быть установлен в 1, если внутри значения блока содержатся дополнительные ASN.1-кодированные блоки;
• биты с 5 по 1 кодируют собственно идентификатор типа для данного блока;

В случае если идентификатор типа для блока находится в диапазоне значений 0-30 идентификационный блок состоит только из одного октета. Если же идентификатор типа для блока имеет значение 31 и выше, то в битах 5-1 выставляются все 1, а в последующих октетах кодируется нужный номер. Номер идентификатора типа кодируется как без знаковое целое, разложенное по основанию 128. В каждом октете, кодирующем идентификатор типа для блока, старший бит должен быть равен 1, кроме самого крайнего, завершающего октета (способ кодирования полностью совпадает со способом, которым кодируются SID для OBJECT IDENTIFIER, см. ниже).

Часть общей длины блока содержит минимум 1 октет, кодирующий длину значения, которое содержит блок (именно только длину блока, содержащего закодированное значение, а не общую длину всего закодированного блока вместе с идентификатором блока и частью общей длины!). Длина блока в простейшем случае кодируется как без знаковое целое, разложенное по основанию 128. Бит 8 (старший бит) в этом случае является дополнительным флагом. Если общая длина закодированного блока превышает 128, то старший бит первого октета части общей длины блока должен быть установлен в 1, а следующие 7 бит должны кодировать без знаковое целое значение количества последующих октетов, которые и будут кодировать реальную общую длину блока.

Например если общая длина блока равна L = 201 то она будет кодироваться с помощью двух октетов:

1. 1000 0001 (81)
2. 1100 1001 (C9)

Кроме явного задания общей длины блока возможно определять окончание данного блока непосредственно в процессе декодирования блока. Это важно, когда при начальном кодировании блока не ясно, сколько именно октетов он будет содержать (потоковое кодирование). В этом случае первый октет части общей длины блока должен быть равен 80 (старший бит 8 равен 1 и все остальные биты равны 0). Окончание всего блока определяется по наличию в блоке значения двух последовательно идущих октетов 00 00.

Глава 2. Кодирование типа REAL

Общее описание типа:

• Класс тэга — UNIVERSAL (00);
• Номер тэга — 9;
• Форма кодирования значения — примитивная (не конструктивная форма);

Для начала немного теории, касающейся собственно чисел с плавающей запятой. Числа с плавающей запятой обычно представляют состоящими из трёх частей: мантиссы, основания и экспоненты. Более просто это можно объяснить с помощью формулы: REAL = (мантисса)*(основание)^{(экспонента)}. Если по этой формуле представлять обычные десятичные числа, то получится REAL = (мантисса)*10^{(экспонента)}. Так как в ASN.1 и мантисса и экспонента могут быть как положительными, так и отрицательными, то возможно как представление сколь угодно больших и сколь угодно маленьких значений, с произвольным знаком.

В отличие от обычного, машинного, представления чисел с плавающей запятой (IEEE 754) в ASN.1 тип REAL практически не ограничен по размеру как мантиссы (мантисса может состоять из практически не ограниченного числа октетов и представлять сколь угодно большое число), так и по размеру экспоненты (значение экспоненты также может состоять из произвольного количества октетов). Ограничения при кодировании накладываются только на значение "основания": в качестве "основания" могут выбраны только числа 10, 2, 8 или 16.

Для кодирования типа REAL применяются следующие три основных блока:

1. Служебный информационный октет;
2. Значение экспоненты числа;
3. Значение мантиссы числа;

В служебной информационном октете содержится следующая информация:

• Возможные комбинации битов 8 и 7 (крайние слева):
  • Бит 8 = 1 — применяется двоичное кодирование (по одному из оснований 2, 8 или16);
  • Бит 8 = 0 и бит 7 = 0 — применяется десятичное кодирование (фактически кодирование строкового стандартного представления числа, см. далее);
  • Бит 8 = 0 и бит 7 = 1 — закодированное значение является "специальным значением" (NaN, INFINITE etc.) или закодированное значение кодирует "-0";

• Бит 7 установлен в 0 когда кодируемое число положительно, и установлен в 1 когда кодируемое число отрицательно;
• Комбинация битов 6 и 5 определяет базу двоичного кодирования:
  • 00 — кодируемое число разложено по основанию 2;
  • 01 — кодируемое число разложено по основанию 8;
  • 10 — кодируемое число разложено по основанию 16;
  • 11 — зарезервировано для будущих возможных изменений;

• Биты 4 и 3 кодируют значение "scaling factor" (F, см. далее) в двоичном коде;
• Биты 2 и 1 кодируют формат представления экспоненты в закодированном числе:
  • 00 — следующий октет представляет собой единственный октет, кодирующий значение экспоненты;
  • 01 — следующие два октета кодируют значение экспоненты;
  • 10 — следующие три октета кодируют значение экспоненты;
  • 11 — следующий октет содержит количество последующих октетов, кодирующих значение экспоненты (количество октетов кодируется как обычное число без знака (допускаются только положительные значения, естественно), а последующие октеты кодируют значение экспоненты;

Значение экспоненты числа кодируется целым числом, состоящим из произвольного количества октетов. Здесь необходимо сделать маленькое отступление и рассказать как именно в ASN.1 кодируются как положительные целые числа, так и отрицательные.

Положительные целые числа в ASN.1 представляют собой последовательность "индексов" при соответствующих степенях разложения по основанию 256. То есть целое число, представленное в обычном десятичном формате, сначала раскладывается по основанию 256, а потом индексы при соответствующих степенях 256 записываются в качестве кодирующих октетов. Для наглядного примера возьмём число 32639. Данное число разлагается по основанию 256 как: 32639₁₀ = 127*256¹ + 127*256⁰. Следовательно коэффициенты при соответствующих степенях 256 будут равны (127, 127). Представляя десятичное значение 127 в виде последовательности битов получаем: 127 = 0111 1111, или представляя каждую группу из четырех битов в качестве числа от 0 до F получаем: 127 = 0111 1111 = 7F. Таким образом начальное число 32639 будет кодироваться последовательностью из двух октетов 7F 7F.

Рассмотренным выше способом можно закодировать сколь угодно большое целое положительное число. Однако как быть с кодированием отрицательных целых значений? Именно для кодирования отрицательных целых применяется специальная процедура кодирования значений.

Для примера опять возьмем число 32639, но теперь пусть оно будет отрицательным (-32639). Кодирование отрицательных целых построено так, что на самом деле кодируется не одно, а два целых значения — одно основное значение и другое целое значение, которое нужно вычесть из основного значения. То есть при декодировании для получения закодированного отрицательного числа просто вычислить результат (x — y). Как видно из этой простейшей формулы если значение "x" меньше, чем значение "y" то результат будет меньше нуля (то есть отрицательное число).

Вышеупомянутые два числа (основное число и число, которое надо вычесть из основного) формируются по следующим правилам:

• Пусть закодированное в ASN.1 число состоит из последовательности из N бит;
• Тогда число, которое надо вычесть из основного числа, образуется как число также состоящее из N бит, но где все биты, кроме самого старшего (крайний левый бит), установлены в 0;
• Основное число также состоит из N бит, но в нем самый старший бит установлен в 0. Значения всех остальных битов полностью соответствуют соответствующим битам из изначально закодированного числа (остаются неизменными);

Перейдём к кодированию конкретного числа из примера (-32639). Так как число, которое надо вычесть из основного, должно быть больше основного числа, то кодирование отрицательных целых чисел начинается именно с выбора этого вычитаемого. Так как по правилам это вычитаемое должно разлагаться по основанию 256 так, чтобы все биты, представляющие индексы при соответствующих степенях 256, были равны 0 кроме первого бита, то ряд возможных вычитаемых представляет собой лидирующий октет 80 (1000 0000) и какое-то количество октетов 00, следующих за ним. То есть в качестве вычитаемых могут использоваться: 80 (128₁₀), 80 00 (32768₁₀), 80 00 00 (8388608₁₀) и т.п. Для кодирования нашего числа "-32639" выберем первое подходящее вычитаемое, большее кодируемого числа по модулю (то есть большее чем число 32639). Ближайшее такое число равно 32768 (80 00).

Теперь необходимо получить значение основного числа. Для этого надо опять решить простейшую формулу: x — 32768 = -32629. Решая уравнение получаем значение x = 129 = 129*256⁰, следовательно число 129 кодируется одним байтом 81₂₅₆. Так как если более внимательно рассматривать правила то можно понять, что количество бит в основном и вычитаемом числах должно быть равно. Количество бит в вычитаемом равно 16. В то же время количество бит в основном числе равно всего 8. Для увеличения числа бит  в основном числе просто добавим не значащие нули для старших бит. Тогда получим 129 = 0*256¹ + 129*256⁰, а следовательно основное число будет кодироваться двумя октетами как (00 81). Теперь устанавливая первый бит в 1 для полученного двух октетного основного числа получаем окончательное число, которое кодирует "-32639". Это число будет кодироваться двумя октетами 80 81. Ещё раз — основное число образуется из всех битов закодированного числа, кроме самого старшего бита (получаем что основное число у нас кодируется 00 81), а вычитаемое число образуется только из одного первого бита, установленного в 1, и всех остальных бит, установленных в 0 (получаем, что вычитаемое число у нас кодируется как 80 00).

А теперь приятная информация — в современных компьютерных системах целые числа (как положительные, так и отрицательные) автоматически кодируются и хранятся именно в том формате, который и был описан выше. То есть для кодирования целых чисел в ASN.1 не нужно выполнять вообще никаких действий — просто нужно сохранить их байт за байтом и всё.

Значение мантиссы числа представляет собой всегда без знаковое целое. То есть мантисса числа, кодированного в ASN.1, всегда является положительным числом. Для того чтобы кодировать отрицательные числа с плавающей точкой в ASN.1 предусмотрен отдельный бит (бит 7) в служебном октете (см. выше).

Мантисса кодируется как последовательность байт представляющих собой коэффициенты разложения начального числа по основанию 256. То есть если мантисса числа в десятичном виде равна 32639 то значит закодированное число будет состоять из двух октетов 7F 7F (32639₁₀ = 127*256¹ + 127*256⁰ = 7F*FF¹ + 7F*FF⁰).

Примеры кодирования чисел REAL в ASN.1 в двоичном представлении:

Для примера возьмём число 0.15625. Для начала закодируем его в двоичном представлении по основанию 2. Коэффициенты разложения этого числа по основанию 2 будут находится как: 0.15625₁₀ = 1*2^-3 + 1*2^-5. То есть мантисса для нашего тестового числа будет иметь значение М = 101₂, а значение экспоненты будет равно -5. Служебный октет для этого числа будет 1000 0000₂ = 80₁₆. Значение экспоненты будет кодироваться одним октетом: -5 = 123 — 128 и следовательно основное число будет равно 123₁₀ = 7B₁₆, а вычитаемое число равно 128₁₀ = 80₁₆. Тогда окончательный октет, кодирующий число -5, будет равен FB₂₅₆. Значение мантиссы также кодируется одним октетом: 101₂ = 05₁₆. Теперь нам известны все части блока, кодирующего значение 0.15625 в двоичном коде по основанию 2 и весь кодирующий блок будет состоять из трёх октетов (80 FB 05)₂₅₆.

Теперь закодируем это же число 0.15625, но уже по основанию 8. Коэффициенты разложения этого числа по основанию 8 будут находится как: 0.15625₁₀ = 1*8^-1 + 2*8^-2. То есть мантисса для нашего тестового числа будет иметь значение М = 12₈ = (001 010)₂ (при кодировании числа в 8-миричной системе для каждого значения требуется три отдельных бита). Значение экспоненты будет равно -2. Служебный октет для этого числа будет 1001 0000₂ = 90₂₅₆. Значение экспоненты будет кодироваться одним октетом, где основное и вычитаемое число находятся из формулы: -2 = 126 — 128. Следовательно октет, кодирующий значение экспоненты -2, будет FE₂₅₆. Значение мантиссы числа будет также кодироваться одним октетом 0A₂₅₆.

В этом примере разложим число 0.15625 по основанию 16. Коэффициенты этого разложения будут находится как: 0.15626₁₀ = 2*16^-1 + 8*16^-2. Следовательно получаем выражение для мантиссы М = 28₁₆ = (0010 1000)₂ и значение экспоненты Е = -2. Теперь поставим дополнительное условие: значение мантиссы должно быть "нормализовано", то есть не должно содержать нулей в младших разрядах числа (также это требование зачастую звучит как "мантисса должна быть нечетной", так как если крайний младший бит равен 1, то всё число получается нечетным ввиду того, что к степеням двойки добавляется 1*2⁰). Как может быть выполнено подобное условие "нормализации"? Очевидно, что основной способ — изменение значения экспоненты числа, сдвигающее плавающую точку. В случае использования разложения по основанию 2 всё представляется простым — изменение значения экспоненты на 1 сдвигает плавающую точку (или добавляет/удаляет нули в младших разрядах мантиссы) ровно на одну позицию. Однако в случае использования разложения по основаниям 8 и 16 получаем, что изменение значения экспоненты на 1 сдвигает плавающую точку в мантиссе сразу на 3 и 4 бита соответственно (так как в случае разложения по основанию 8 для представления числа требуется 3 бита, а в случае разложения по основанию 16 для представления числа требуется 4 бита). Следовательно далеко не всегда полученное для разложения по основаниям 8 и 16 значение мантиссы может быть "нормализовано" просто изменением значения экспоненты. Для более "тонкой настройки" возможности сдвига плавающей точки в мантиссе был введен дополнительный множитель: умножающий фактор, F. Умножающий фактор сдвигает плавающую точку в мантиссе вправо (или добавляет необходимое количество нулевых бит справа от числа). Для этого перед декодированием значение мантиссы получается как результат умножения M = N * 2^F. Общеизвестно, что умножение целого числа на 2 равноценно битовому сдвигу влево на 1 бит. Соответственно умножение на 2^F равноценно битовому сдвигу влево на F бит. Таким образом получаем следующий процесс кодирования/декодирования мантиссы при предъявлении требования её нормализации:

1. Пусть дана мантисса 0010 1000;
2. При кодировании "нормализуем" её (или сдвигаем вправо на 3 бита), получая 0000 0101, одновременно устанавливая значение умножающего фактора F = 3;
3. При декодировании умножаем закодированное значение мантиссы на 2^F, чем сдвигаем закодированную мантиссу обратно на F = 3 бита влево;

Следовательно все число с плавающей точкой из нашего примера (при условии "нормализации" мантиссы) будет кодироваться следующей последовательностью октетов:

AC FE 05

Кроме кодирования всех частей числа с плавающей точкой в виде двоичного представления  в разложении по различным степеням двойки дополнительно есть прекрасная возможность представлять подобные числа в ASN.1 в обычном строковом виде, в каком мы обычно и видим такие числа. В этом случае считается, что число кодируется с основанием 10.

При кодировании по основанию 10 дополнительно вводится понятие "форм представления числа". Всего таких форм 3 (формы NR1, NR2 и NR3) и описываются они в отдельном стандарте ISO 6093. Так как этот стандарт является платным, то для ознакомления с формами представления чисел можно порекомендовать "предка" ISO 6093 — стандарт ECMA-63, который легко может быть найден в Интернете.

При кодировании числа с плавающей точкой в представлении разложения по основанию 10 в служебном информационном октете указывается код  формы представления числа (01, 02 или 03 для соответствующих форм), а сразу после служебного информационного октета указываются коды символов, представляющих кодированное число. Разрешены следующие коды символов:

1. Символы, обозначающие цифры 0-9 (коды 30-39 соответственно);
2. Пробел (код 20);
3. Разделительный символ "." (код 2E);
4. Разделительный символ "," (код 2C);
5. Символ представление экспоненты "E" (код 45), либо другой символ представления экспоненты "e" (код 65);
6. Символ "-" (код 2D);
7. Символ "+" (код 2B);

Все остальные символы запрещены к кодированию (при декодировании символов, отличных от приведенных выше, декодер ASN.1 обязан выдать ошибку).

Примеры кодирования числа с плавающей точкой в десятичной форме:

Для примера закодируем обычное число 1. В случае представления в форме NR1 число будет кодироваться строкой "1" (или "+1"). В случае представления числа в форме NR2 число уже должно быть закодировано с указанием разделительного символа, поэтому все представленные ниже строки равноценны:

1. "1,"
2. "+1.0"
3. "1,000000"
4. " 1.0" (в начале строки может присутствовать неограниченное количество пробелов)

Теперь представим 1 в форме NR3. Здесь уже обязательно применение как разделительного символа, так и символа экспоненты. В форме NR3 по стандарту 1 может представляться в виде "+1,0Е+0" ("1.0Е+0" в случае разделительного символа "."), то есть значение экспоненты всегда должно быть нулевым.

Кроме обычных чисел ASN.1 позволяет кодировать также и ряд "специальных" чисел:

• PLUS-INFINITY (плюс бесконечность);
• MINUS-INFINITY (минус бесконечность);
• NOT-A-NUMBER (так называемое "не-число");
• minus zero (для возможности кодирования "-0");

Все специальные числа кодируются только одним служебным информационным октетом, без указания октетов для экспоненты и мантиссы:

• PLUS-INFINITY — 40₂₅₆;
• MINUS-INFINITY — 41₂₅₆;
• NOT-A-NUMBER — 42₂₅₆;
• minus zero — 43₂₅₆;

Автор: ystr