Журнал LinuxFormat - перейти на главную

LXF156:Erlang

Материал из Linuxformat
Перейти к: навигация, поиск


Erlang Опи­сы­ва­ет­ся сле­дую­щей фор­му­лой:функ­цио­наль­ный язык + про­цес­сы

=Erlang: Ма­гия би­то­вых строк 2=

При­шла по­ра оп­ро­бо­вать «чер­ную ма­гию» би­то­вых строк на боль­шом при­ме­ре, воодушевился Ан­д­рей Уша­ков.

232268.png


В этом но­ме­ре мы про­дол­жа­ем наш прак­ти­кум по функ­цио­наль­но­му про­грам­ми­ро­ванию: при­шла по­ра оп­ро­бо­вать «чер­ную ма­гию» би­то­вых строк на боль­шом при­ме­ре. В ка­че­­ст­ве та­ко­го боль­шо­го при­ме­ра мы реа­ли­зу­ем ASN.1-со­вмес­ти­мую се­риа­ли­за­цию и де­се­риа­ли­за­цию объ­ек­тов язы­ка Erlang.

Что же та­кое ASN.1? Это на­бор стан­дар­тов для опи­сания аб­ст­ракт­но­го син­так­си­са дан­ных в об­лас­ти те­ле­ком­муника­ций и ком­пь­ю­тер­ных се­тей. Стан­дар­ты ASN.1 опи­сы­вают струк­ту­ры дан­ных для пред­став­ления, ко­ди­ро­вания, пе­ре­да­чи и де­ко­ди­ро­вания дан­ных. Они слиш­ком мно­го­чис­лен­ны, что­бы рас­смат­ри­вать их пол­но­стью; мы крат­ко оста­но­вим­ся на той их час­ти, что касается ко­ди­ро­вания и де­ко­ди­ро­вания дан­ных. Для на­шей за­да­чи мы применим пра­ви­ла ко­ди­ро­вания и де­ко­ди­ро­вания ASN.1 BER [basic encoding rules]. В со­от­вет­ст­вии с ни­ми, за­ко­ди­ро­ван­ное зна­чение лю­бо­го эле­мен­та дан­ных со­сто­ит из 3-х час­тей: опи­са­те­ля ти­па дан­ных (тэ­га), дли­ны за­ко­ди­ро­ван­но­го зна­чения эле­мен­та дан­ных и соб­ст­вен­но за­ко­ди­ро­ван­но­го зна­чения эле­мен­та дан­ных. Опи­са­тель ти­па дан­ных (тэг) со­дер­жит иден­ти­фи­ка­тор ти­па дан­ных, класс опи­са­те­ля (од­но из сле­дую­щих зна­чений: универ­саль­ный тип дан­ных, спе­ци­фич­ный для при­ло­жения, спе­ци­фич­ный для кон­тек­ста, при­ват­ный тип дан­ных) и фор­му дан­ных (од­но из сле­дую­щих зна­чений: про­стые дан­ные, со­став­ные дан­ные). Все час­ти со­сто­ят из це­ло­го чис­ла ок­те­тов (в стан­дар­те ASN.1 при­ме­ня­ет­ся тер­мин не бай­ты, а ок­те­ты).

(thumbnail)
Рис.1.

Для стан­дарт­ных ти­пов дан­ных (та­ких как це­лые чис­ла, дей­ст­ви­тель­ные чис­ла, би­то­вые стро­ки и т. д.) пра­ви­ла ко­ди­ро­вания со­дер­жи­мо­го со­дер­жат­ся в ASN.1 BER (о неко­то­рых из этих пра­вил мы по­го­во­рим далее); для осталь­ных ти­пов пра­ви­ла ко­ди­ро­вания мо­гут быть лю­бы­ми. Ес­ли тип дан­ных яв­ля­ет­ся со­став­ным (то есть включает несколь­ко эле­мен­тов дан­ных), то его со­дер­жи­мое – за­ко­ди­ро­ван­ные зна­чения эле­мен­тов дан­ных, со­став­ляю­щих тип дан­ных; ка­ж­дое за­ко­ди­ро­ван­ное зна­чение со­дер­жит трой­ку тэг, дли­на, со­дер­жи­мое. Дли­на со­дер­жи­мо­го со­став­но­го ти­па дан­ных рав­ня­ет­ся сум­ме длин за­ко­ди­ро­ван­ных зна­чений эле­мен­тов дан­ных. При­ме­р со­став­но­го ти­па дан­ных – по­сле­до­ва­тель­ность (спи­сок эле­мен­тов, в тер­ми­нах ASN.1). Эти кон­цеп­ции пра­вил ко­ди­ро­вания ASN.1 BER по­ка­за­ны на рис. 1 и 2: рис. 1 по­ка­зы­ва­ет при­мер про­сто­го ти­па дан­ных, рис. 2 – со­став­но­го ти­па дан­ных (здесь T – это тэг, L – дли­на, V – со­дер­жи­мое).

Про ASN.1 мож­но ска­зать еще сле­дую­щее: ASN.1 – это ана­лог XML для дво­ич­ных про­то­ко­лов. Чем же плох XML, ес­ли для дво­ич­ных про­то­ко­лов при­ме­ня­ет­ся дру­гое, в чем-то ана­ло­гич­ное ему ре­шение? Глав­ный недоста­ток XML в том, что это тек­сто­вое пред­став­ление дан­ных, и, со­от­вет­ст­вен­но, его раз­мер боль­ше (в гру­бых оцен­ках, где-то на по­ря­док) дво­ич­но­го пред­став­ления дан­ных. Дру­гой боль­шой недостат­ок XML – тот факт, что оп­ре­де­ление ти­пов дан­ных (на­при­мер, с ис­поль­зо­ванием схем XSD) ото­рва­но от са­мих дан­ных. С дру­гой сто­ро­ны, ASN.1 – это на­бор стан­дар­тов для ко­ди­ро­вания дво­ич­ных дан­ных, об­ра­бот­ка ко­то­рых, в це­лом, бо­лее слож­на. К то­му же для ра­бо­ты с XML су­ще­ст­ву­ет це­лый ряд тех­но­ло­гий (та­ких как XQuery, XSLT), ко­то­рых нет для ASN.1.

Да­вай­те пе­рей­дем непо­сред­ст­вен­но к при­ме­ру. На­ша за­да­ча – на­пи­сать се­риа­ли­за­цию и де­се­риа­ли­за­цию (ко­ди­ро­вание и де­ко­ди­ро­вание) объ­ек­тов язы­ка Erlang в со­от­вет­ст­вии с пра­ви­ла­ми ASN.1 BER. Вполне оче­вид­но, что дан­ная за­да­ча со­сто­ит из двух прак­ти­че­­ски неза­ви­си­мых друг от дру­га час­тей: из ко­ди­ро­вания и де­ко­ди­ро­вания дан­ных. Так­же вполне оче­вид­но, что начнем мы с час­ти, от­ве­чаю­щей за ко­ди­ро­вание дан­ных.

Тип дан­ных (он же тэг дан­ных) – ве­ли­чи­на трех­ком­понент­ная: он со­сто­ит из клас­са ти­па дан­ных, фор­мы ти­па дан­ных и иден­ти­фи­ка­то­ра ти­па дан­ных. Поэтому для него ло­гич­но оп­ре­де­лить со­от­вет­ст­вую­щую запись (и по­мес­тить ее в файл asn1_tag.hrl):

-record(tag, {class, form, tag_value}).

(thumbnail)
Рис.2.

Как и во всех дру­гих при­ме­рах, в ка­че­­ст­ве пер­во­го ша­га мы оп­ре­де­ля­ем мо­дуль (и не за­бы­ва­ем, что имя фай­ла – это имя мо­ду­ля с рас­ши­рением .hrl), под­клю­ча­ем фай­лы с оп­ре­де­ления­ми и задаем спи­сок экс­пор­ти­руе­мых функ­ций. Экс­пор­ти­руе­мых функ­ций у нас все­го две: функ­ция build/1 для по­строения функ­ции дис­пет­че­ра для вы­бо­ра под­хо­дя­щей функ­ции ко­ди­ро­вания дан­ных и функ­ция encode/2 для ко­ди­ро­вания объ­ек­тов Erlang.

-module(asn1_encoder).

-include(“asn1_tag.hrl”).

-export([build/1, encode/2]).

Функ­ция build/1, как уже го­во­ри­лось вы­ше, слу­жит для соз­дания функ­ции-дис­пет­че­ра для вы­бо­ра под­хо­дя­щей функ­ции ко­ди­ро­вания дан­ных. Для это­го она ис­поль­зу­ет спи­сок пар (кор­те­жей из двух зна­чений) из двух аноним­ных функ­ций (лям­бда-вы­ра­жений): пер­вая функ­ция про­ве­ря­ет, мо­жет ли пе­ре­дан­ный ей объ­ект быть за­ко­ди­ро­ван при по­мо­щи вто­рой функ­ции в этой па­ре.

Ре­шение о том, под­хо­дит ли объ­ект (мо­жет ли функ­ция для ко­ди­ро­вания за­ко­ди­ро­вать дан­ный объ­ект), принима­ет­ся не толь­ко на осно­вании ти­па объ­ек­та, но и на осно­вании зна­чения объ­ек­та. Это свя­за­но с тем, что объ­ек­ты Erlang од­но­го и то­го же ти­па в за­ви­си­мо­сти от зна­чения объ­ек­та долж­ны ко­ди­ро­вать­ся по-раз­но­му; так, на­при­мер, ато­мы true и false яв­ля­ют­ся ло­ги­че­­ски­­ми зна­чения­ми и долж­ны ко­ди­ро­вать­ся от­лич­ным от ато­мов об­ра­зом.

При соз­дании функ­ции-дис­пет­че­ра мы ис­поль­зу­ем как внут­ренний (за­дан­ный на­ми) спи­сок пар функ­ций, так и внешний (за­да­вае­мый поль­зо­ва­те­лем функ­ции че­рез един­ст­вен­ный па­ра­метр) спи­сок пар функ­ций. Внут­ренний спи­сок пар функ­ций об­ра­ба­ты­ва­ет об­щие си­туа­ции ко­ди­ро­вания (когда объ­ект яв­ля­ет­ся спи­ском, кор­те­жем, це­лым чис­лом и т. д.); внешний спи­сок (за­да­вае­мый поль­зо­ва­те­лем) слу­жит для об­ра­бот­ки спе­ци­фич­ных си­туа­ций ко­ди­ро­вания – на­при­мер, ес­ли мы хо­тим ко­ди­ро­вать за­пи­си от­лич­ным от обыч­ных кор­те­жей об­ра­зом. Для это­го па­ры функ­ций из внешнего спи­ска идут всегда пе­ред па­ра­ми функ­ций из внут­реннего спи­ска – это оз­на­ча­ет, что у них бо­лее вы­со­кий при­ори­тет. Бо­лее то­го, ес­ли од­на па­ра функ­ций идет пе­ред дру­гой, то это оз­на­ча­ет, что при­ори­тет у этой па­ры функ­ций вы­ше, т. к. эта па­ра функ­ций бу­дет ис­поль­зо­ва­на в про­це­ду­ре вы­бо­ра под­хо­дя­щей функ­ции ко­ди­ро­вания пер­вой. Для пар из внут­реннего спи­ска в ка­че­­ст­ве пер­вой функ­ции (функ­ции, ко­то­рая про­ве­ря­ет, мо­жет ли быть за­ко­ди­ро­ван объ­ект дру­гой функ­ци­ей из па­ры) ис­поль­зу­ет­ся BIF is_XXX/1, где XXX – тип ко­ди­руе­мо­го объ­ек­та (для функ­ций про­вер­ки из внешнего спи­ска мо­жет ис­поль­зо­вать­ся лю­бой ал­го­ритм).

 
build(ExternalEncoders) when is_list(ExternalEncoders) ->

InternalEncoders =

[

{fun is_boolean/1, fun encode_boolean/2},

{fun is_integer/1, fun encode_integer/2},

{fun is_float/1, fun encode_real/2},

{fun is_binary/1, fun encode_octetstring/2},

{fun is_bitstring/1, fun encode_bitstring/2},

{fun is_list/1, fun encode_sequence/2},

{fun is_tuple/1, fun encode_tuple/2},

{fun is_atom/1, fun encode_atom/2}

],

EncodersList = ExternalEncoders ++ InternalEncoders,

fun(Value, Dispatcher) -> first(EncodersList, Value, Dispatcher) end.

Функ­ция encode/2 ис­поль­зу­ет функ­цию-дис­пет­чер ко­ди­ро­вания (ко­то­рую мы по­строи­ли при по­мо­щи функ­ции build/1) для ко­ди­ро­вания объ­ек­та, пе­ре­да­вае­мо­го в ка­че­­ст­ве пер­во­го па­ра­мет­ра. Ра­бо­та этой функ­ции пол­но­стью осно­ва­на на ис­поль­зо­вании функ­ции-дис­пет­че­ра ко­ди­ро­вания: мы вы­зы­ва­ем функ­цию-дис­пет­чер, пе­ре­да­вая в ка­че­­ст­ве па­ра­мет­ров ко­ди­руе­мый объ­ект и са­му функ­цию-дис­пет­чер ко­ди­ро­вания (т. к. ана­ло­га ука­за­те­ля this из язы­ка Java и ему по­доб­ным у нас нет). Ес­ли пе­ре­да­вае­мый объ­ект мо­жет быть за­ко­ди­ро­ван, то бу­дет воз­вра­щен кор­теж, со­стоя­щий из ато­ма ok и за­ко­ди­ро­ван­но­го ис­ход­но­го объ­ек­та (в ви­де би­то­вой стро­ки); ес­ли же пе­ре­да­вае­мый объ­ект не мо­жет быть за­ко­ди­ро­ван, то бу­дет воз­вра­щен атом false. В по­следнем слу­чае, мы генери­ру­ем ис­клю­чение вре­мени вы­полнения.

encode(Value, EncodeDispatcher) ->

case EncodeDispatcher(Value, EncodeDispatcher) of

{ok, Result} -> Result;

false -> erlang:error(unsuitable_value)

end.

Ра­бо­та функ­ции дис­пет­че­ра осно­ва­на на функ­ции first/3. Эта функ­ция по­сле­до­ва­тель­но про­ве­ря­ет па­ры функ­ций, и как толь­ко про­вер­ка для па­ры бу­дет по­ло­жи­тель­на (про­вер­ка осу­ще­ст­в­ля­ет­ся при по­мо­щи пер­вой функ­ции из па­ры), ис­ход­ный объ­ект бу­дет за­ко­ди­ро­ван при по­мо­щи вто­рой функ­ции из па­ры (в ви­де кор­те­жа из ато­ма ok и ре­зуль­та­та ко­ди­ро­вания). Ес­ли же объ­ект не удов­ле­тво­ря­ет ни од­ной па­ре, то бу­дет воз­вра­щен атом false.

 
first([], _Value, _EncoderDispatcher) -> false;

first([{Predicate, Encoder} | Rest], Value, EncoderDispatcher) ->

case Predicate(Value) of

true -> {ok, Encoder(Value, EncoderDispatcher)};

false -> first(Rest, Value, EncoderDispatcher)

end.

Те­перь пе­рей­дем непо­сред­ст­вен­но к ко­ди­ро­ванию дан­ных. Начнем с ко­ди­ро­вания ти­па дан­ных (он же тэг). Он у нас со­сто­ит из трех час­тей (и для его пред­став­ления мы ис­поль­зу­ем запись ти­па tag). По­это­му мы от­дель­но ко­ди­ру­ем класс (и по­лу­ча­ем би­то­вую стро­ку раз­ме­ром 2 би­та), фор­му (и по­лу­ча­ем би­то­вую стро­ку раз­ме­ром 1 бит) и иден­ти­фи­ка­тор ти­па дан­ных, по­сле че­го склеи­ва­ем три по­лу­чен­ных би­то­вых стро­ки в од­ну при по­мо­щи BIF list_to_bitstring/1.

 
encode_tag(#tag{class = Class, form = Form, tag_value = Value}) ->

list_to_bitstring([encode_tag_class(Class), encode_tag_form(Form), encode_tag_value(Value)]).

Функ­ция encode_tag_class/1 от­ве­ча­ет за ко­ди­ро­вание клас­са ти­па дан­ных (тэ­га). В ка­че­­ст­ве зна­чения клас­са ис­поль­зу­ет­ся мно­же­ст­во пре­до­пре­де­лен­ных ато­мов. Прин­цип ра­бо­ты этой функ­ции три­виа­лен; сто­ит лишь от­ме­тить, что воз­вра­ща­ет она би­то­вую стро­ку раз­ме­ром 2 би­та.
<pre> 
encode_tag_class(universal) -> <<2#00:2>>;

encode_tag_class(application) -> <<2#01:2>>;

encode_tag_class(context_specific) -> <<2#10:2>>;

encode_tag_class(private) -> <<2#11:2>>.

Функ­ция encode_tag_form/1 от­ве­ча­ет за ко­ди­ро­вание фор­мы дан­ных. В ка­че­­ст­ве зна­чения фор­мы ис­поль­зу­ет­ся мно­же­ст­во пре­до­пре­де­лен­ных ато­мов. Прин­цип ра­бо­ты этой функ­ции также три­виа­лен; от­ме­тим, что воз­вра­ща­ет она би­то­вую стро­ку раз­ме­ром 1 бит.

 
encode_tag_form(primitive) -> <<0:1>>;

encode_tag_form(constructed) -> <<1:1>>.

При­шла по­ра бо­лее ин­те­рес­ной функ­ции: encode_tag_value/1, ко­то­рая при­ме­ня­ет­ся для ко­ди­ро­вания иден­ти­фи­ка­то­ра ти­па дан­ных. Ко­ди­ро­вание иден­ти­фи­ка­то­ра за­ви­сит от то­го, мень­ше его зна­чение 31 или нет. Ес­ли зна­чение иден­ти­фи­ка­то­ра мень­ше 31, то иден­ти­фи­ка­тор ко­ди­ру­ет­ся как би­то­вая стро­ка раз­ме­ром 5 бит. Ес­ли зна­чение иден­ти­фи­ка­то­ра боль­ше или рав­но 31, то он ко­ди­ру­ет­ся бо­лее слож­ным спо­со­бом: сна­ча­ла идет сег­мент раз­ме­ром 5 бит, со­дер­жа­щий чис­ло 31 (или 2#11111), по­сле че­го идут сег­мен­ты раз­ме­ров 8 бит, со­дер­жа­щие за­ко­ди­ро­ван­ное зна­чение иден­ти­фи­ка­то­ра. Зна­чение иден­ти­фи­ка­то­ра ко­ди­ру­ет­ся сле­дую­щим об­ра­зом: сна­ча­ла иден­ти­фи­ка­тор ко­ди­ру­ет­ся как би­то­вая стро­ка, со­стоя­щая из сег­мен­тов раз­ме­ром 7 бит; по­сле че­го ка­ж­дый сег­мент уве­ли­чи­ва­ет­ся до 8 бит до­бав­лением в ка­че­­ст­ве стар­ше­го би­та 1, ес­ли это не по­следний сег­мент в би­то­вой стро­ке, и 0 – в про­тив­ном слу­чае. Та­ким об­ра­зом, при де­ко­ди­ро­вании зна­чения иден­ти­фи­ка­то­ра мы смо­жем по­нять, когда нам необ­хо­ди­мо оста­но­вить­ся. Сле­ду­ет до­ба­вить еще сле­дую­щее: раз­мер би­то­вой стро­ки, со­дер­жа­щей за­ко­ди­ро­ван­ное зна­чение ти­па дан­ных, всегда бу­дет кра­тен 8 би­там, в чем лег­ко мо­жет убе­дить­ся ка­ж­дый.

 
encode_tag_value(Value) when (Value >= 0) and (Value =< 30) -> <<Value:5>>;

encode_tag_value(Value) when Value >= 31 ->

SegmentCount = (Value div 128) + 1,

SegmentList = encode_tag_value(<<TagValue:(SegmentCount * 7)>>, []),

list_to_bitstring([<<2#11111:5>>] ++ lists:reverse(SegmentList)).

Функ­ция encode_tag_value/2 занима­ет­ся уве­ли­чения сег­мен­тов раз­ме­ром 7 бит до 8 бит при по­мо­щи до­бав­ления в ка­че­­ст­ве стар­ше­го би­та 1, ес­ли со­от­вет­ст­вую­щий сег­мент раз­ме­ром 7 бит в би­то­вой стро­ке не по­следний, и 0 – в про­тив­ном слу­чае.

 
encode_tag_value(<<Segment:7>>, SegmentList) -> [<<0:1, Segment:7>>] ++ SegmentList;

encode_tag_value(<<Segment:7, Rest/bitstring>>, SegmentList) ->

encode_tag_value(Rest, [<<1:1, Segment:7>>] ++ SegmentList).

Сле­дую­щий необ­хо­ди­мый шаг при ко­ди­ро­вании дан­ных – ко­ди­ро­вание дли­ны (или ко­ли­че­­ст­ва ок­те­тов, необ­хо­ди­мых для со­хранения дан­ных) ко­ди­руе­мых дан­ных. Ко­ди­ро­вание дли­ны про­ще ко­ди­ро­вания ти­па, но и тут у нас есть два ва­ри­ан­та, в за­ви­симости от то­го, мень­ше ли зна­чение дли­ны 128 или нет. В пер­вом слу­чае мы ко­ди­ру­ем дли­ну одним сег­мен­том, раз­ме­ром 8 бит, стар­ший бит ко­то­ро­го ра­вен 0, а млад­шие 7 бит со­дер­жат зна­чение дли­ны. Во вто­ром слу­чае мы ко­ди­ру­ем дли­ну несколь­ки­ми сег­мен­та­ми раз­ме­ром 8 бит: при этом у пер­во­го сег­мен­та стар­ший бит ра­вен 1, млад­шие 7 бит со­дер­жат ко­ли­че­­ст­во ок­те­тов, необ­хо­ди­мых для ко­ди­ро­вания дли­ны, а все осталь­ные ок­те­ты со­дер­жат за­ко­ди­ро­ван­ное зна­чение дли­ны.

 
encode_length(LengthValue) when (LengthValue >= 0) and (LengthValue =< 127) -> <<0:1, LengthValue:7>>;

encode_length(LengthValue) when LengthValue >= 128 ->

OctetCount = (LengthValue div 256) + 1,

list_to_binary([<<1:1, OctetCount:7>>] ++ [binary:encode_unsigned(LengthValue, big)]).

Те­перь пе­ре­хо­дим непо­сред­ст­вен­но к ко­ди­ро­ванию са­мих дан­ных (объ­ек­тов Erlang). Начнем с ло­ги­че­­ских зна­чений (в язы­ке Erlang ло­ги­че­­ские зна­чения пред­став­ле­ны ато­ма­ми true и false). Ло­ги­че­­ские зна­чения ко­ди­ру­ют­ся сле­дую­щим об­ра­зом: тип дан­ных име­ет зна­чение 1 (класс – universal, фор­ма – primitive, иден­ти­фи­ка­тор – 1), дли­на – 1 ок­тет, ло­ги­че­­ское зна­чение false ко­ди­ру­ет­ся зна­чением 0, ло­ги­че­­ское зна­чение true – лю­бым нену­ле­вым зна­чением (мы бу­дем ко­ди­ро­вать зна­чением 2#11111111=255).

 
encode_boolean(true, _EncodeDispatcher) ->

Tag = encode_tag(#tag{class = universal, form = primitive, tag_value = 1}),

list_to_binary([Tag, encode_length(1), <<2#11111111:8>>]);

encode_boolean(false, _EncodeDispatcher) ->

Tag = encode_tag(#tag{class = universal, form = primitive, tag_value = 1}),

list_to_binary([Tag, encode_length(1), <<2#00000000:8>>]).

Сле­дую­щий тип дан­ных, ко­ди­ро­вание ко­то­ро­го мы рас­смот­рим – это це­лые чис­ла. Це­лые чис­ла ко­ди­ру­ют­ся сле­дую­щим об­ра­зом: тип дан­ных име­ет зна­чение 2 (класс – universal, фор­ма – primitive, иден­ти­фи­ка­тор – 2), дли­на ничем не ог­раниче­на.

 
encode_integer(Number, _EncodeDispatcher) ->

Tag = encode_tag(#tag{class = universal, form = primitive, tag_value = 2}),

NumberBinary = encode_integer_value(Number),

list_to_binary([Tag, encode_length(size(NumberBinary)), NumberBinary]).

Ме­тод encode_integer_value/1 ко­ди­ру­ет непо­сред­ст­вен­но зна­чение це­ло­го чис­ла. Ко­ди­ро­вание це­лых чи­сел, по­жа­луй, яв­ля­ет­ся са­мой слож­ной опе­ра­ци­ей, в свя­зи со спо­со­бом ко­ди­ро­вания по­ло­жи­тель­ных и от­ри­ца­тель­ных це­лых чи­сел. По­ло­жи­тель­ные це­лые чис­ла ко­ди­ру­ют­ся сле­дую­щим об­ра­зом: це­лое чис­ло со­хра­ня­ет­ся как би­то­вая стро­ка с раз­ме­ром, крат­ным 8 бит (с по­ряд­ком за­пи­си байт big-endian); ес­ли стар­ший бит би­то­вой стро­ки ра­вен 1, то к би­то­вой стро­ке сле­ва до­пи­сы­ва­ет­ся ок­тет, со­дер­жа­щий 0. От­ри­ца­тель­ные це­лые чис­ла ко­ди­ру­ют­ся в до­полнитель­ном ко­де пред­став­ления чис­ла, при этом ко­ли­че­­ст­во ок­те­тов раз­ме­ром 8 бит и зна­чением 16#FF долж­но быть минималь­но необ­хо­ди­мым. Это оз­на­ча­ет (для ко­ди­ро­вания от­ри­ца­тель­но­го чис­ла), на­при­мер, что для ко­ди­ро­вания чис­ла -128 = 16#80 доста­точ­но од­но­го ок­те­та, а для ко­ди­ро­вания чис­ла -129 = 16#FF7F уже нужно два ок­те­та.

 
encode_integer_value(Number) when Number >= 0 ->

OctetCount = get_octet_count(Number, 0),

NumberBinary = <<Number:(8 * OctetCount)/integer-signed-big>>,

<<OldestBit:1, _Rest/bitstring>> = NumberBinary,

if

OldestBit == 1 -> list_to_binary([<<0:8>>, NumberBinary]);

OldestBit == 0 -> NumberBinary

end;

encode_integer_value(Number) when Number < 0 ->

OctetCount = get_octet_count(Number, 0),

<<Number:(8 * OctetCount)/integer-signed-big>>.

Ме­тод get_octet_count/2 слу­жит для под­сче­та ко­ли­че­­ст­ва ок­те­тов, необ­хо­ди­мых для ко­ди­ро­вания це­ло­го чис­ла. Прин­цип его ра­бо­ты три­виа­лен.

 
get_octet_count(0, 0) -> 1;

get_octet_count(0, Count) -> Count;

get_octet_count(Number, 0) when Number < 0 -> get_octet_count(Number div -129, 1);

get_octet_count(Number, Count) -> get_octet_count(Number div 256, Count + 1).

Пе­рей­дем те­перь к дей­ст­ви­тель­ным чис­лам. С ни­ми все про­ще, чем с це­лыми: дей­ст­ви­тель­ные чис­ла (по осно­ванию 10) ко­ди­ру­ют­ся в стро­ко­вом пред­став­лении. При этом тип дан­ных име­ет зна­чение 9 (класс – universal, фор­ма – primitive, иден­ти­фи­ка­тор – 9).

 
encode_real(0.0, _EncodeDispatcher) ->

Tag = encode_tag(#tag{class = universal, form = primitive, tag_value = 9}),

list_to_binary([Tag, <<0:8>>]);

encode_real(Number, _EncodeDispatcher) ->

Tag = encode_tag(#tag{class = universal, form = primitive, tag_value = 9}),

NumberStr = float_to_list(Number),

list_to_binary([Tag, encode_length(length(NumberStr) + 1), <<2#00000011>>, NumberStr]).

Разберемся с ко­ди­ро­ванием бо­лее слож­ных ти­пов дан­ных. Нач­нем с би­то­вых строк – в дан­ном кон­тек­сте под би­то­вой стро­кой мы понима­ем по­сле­до­ва­тель­ность бит, ко­ли­че­­ст­во ко­то­рых не крат­но 8. Би­то­вая стро­ка ко­ди­ру­ет­ся сле­дую­щим об­ра­зом: она раз­би­ва­ет­ся на сег­мен­ты раз­ме­ром 8 бит и оста­ток, раз­мер ко­то­ро­го мень­ше 8 бит. По­сле че­го спра­ва до­бав­ля­ем сег­мент та­ко­го раз­ме­ра (от 1 до 7 бит), что­бы оста­ток и этот сег­мент в сум­ме име­ли раз­мер 8 бит, и за­пол­ня­ем этот сег­мент зна­чением 0. Затем пе­ред би­то­вой стро­кой до­пи­сы­ва­ем ок­тет, со­дер­жа­щий ко­ли­че­­ст­во бит до­бав­лен­но­го спра­ва сег­мен­та (от 1 до 7). Это нуж­но по­то­му, что дли­на дан­ных за­да­ет­ся в ко­ли­че­­ст­ве ис­поль­зуе­мых ок­те­тов. Со­от­вет­ст­вен­но, дли­на за­ко­ди­ро­ван­ной би­то­вой стро­ки бу­дет на единицу боль­ше чис­ла ис­поль­зуе­мых для хранения би­то­вой стро­ки ок­те­тов. Для би­то­вых строк тип дан­ных име­ет зна­чение 3 (класс – universal, фор­ма – primitive, иден­ти­фи­ка­тор – 3).

encode_bitstring(BitString, _EncodeDispatcher) ->
OctetCount = (bit_size(BitString) div 8) + 1,
UnusedBitCount = 8 - bit_size(BitString) rem 8,
Tag = encode_tag(#tag{class = universal, form = primitive, tag_value = 3}),
EncodedValue = list_to_bitstring([BitString, <<0:UnusedBitCount>>]),
list_to_binary([Tag, encode_length(OctetCount + 1), <<UnusedBitCount:8>>, EncodedValue]).

Стро­ки ок­те­тов ко­ди­ру­ют­ся го­раз­до про­ще: сна­ча­ла идет тип дан­ных, рав­ный 4 (класс – universal, фор­ма – primitive, иден­ти­фи­ка­тор – 4), по­том дли­на за­ко­ди­ро­ван­ных дан­ных (в на­шем слу­чае, ко­ли­че­­ст­во ок­те­тов в стро­ке), по­сле че­го идет са­ма стро­ка.

encode_octetstring(OctetString, _EncodeDispatcher) ->
Tag = encode_tag(#tag{class = universal, form = primitive, tag_value = 4}),
list_to_binary([Tag, encode_length(size(OctetString)), OctetString]).

Те­перь займемся ко­ди­ро­ванием со­став­ных ти­пов дан­ных: спи­сков и кор­те­жей. Как ко­ди­ру­ет­ся со­дер­жи­мое со­став­ных ти­пов дан­ных? От­вет оче­ви­ден: мы бе­рем пер­вый эле­мент со­дер­жи­мо­го и ко­ди­ру­ем у него по­сле­до­ва­тель­но тип дан­ных, дли­ну и со­дер­жи­мое, за­тем то же са­мое де­ла­ем для вто­ро­го эле­мен­та, и так до тех пор, по­ка все эле­мен­ты со­дер­жи­мо­го не бу­дут за­ко­ди­ро­ва­ны. Дли­на (или, что то же са­мое, число ок­те­тов), по­лу­чен­ная в ре­зуль­та­те ко­ди­ро­вания со­дер­жи­мо­го, ста­но­вит­ся дли­ной за­ко­ди­ро­ван­но­го со­став­но­го эле­мен­та. Для спи­сков зна­чение типа дан­ных рав­ня­ет­ся 48 (класс – universal, фор­ма – constructed, иден­ти­фи­ка­тор – 16)

encode_sequence(Sequence, EncodeDispatcher) ->
Tag = encode_tag(#tag{class = universal, form = constructed, tag_value = 16}),
{ContentLength, ContentBinary} = encode_sequence_content(Sequence, EncodeDispatcher),
list_to_binary([Tag, encode_length(ContentLength), ContentBinary]).

Кор­те­жи, как го­во­ри­лось вы­ше, ко­ди­ру­ют­ся точ­но так же, как и спи­ски. Толь­ко для кор­те­жей зна­чение ти­па дан­ных рав­ня­ет­ся 16160 = 2#0011111100100000 (класс – universal, фор­ма – constructed, иден­ти­фи­ка­тор – 32). Сле­ду­ет ска­зать про зна­чение иден­ти­фи­ка­то­ра сле­дую­щее: до это­го все ти­пы дан­ных ко­ди­ро­ва­лись с ис­поль­зо­ванием стан­дарт­ных иден­ти­фи­ка­то­ров ти­пов, но но­та­ция ASN.1 не по­зво­ля­ет раз­ли­чать та­кие ти­пы дан­ных, как спи­ски и кор­те­жи. По­это­му для кор­те­жей был вы­бран иден­ти­фи­ка­тор, рав­ный 32, но не яв­ляю­щий­ся стан­дарт­ным. По­это­му, когда мы бу­дем ис­поль­зо­вать наш при­мер универ­саль­ным об­ра­зом, с ко­ди­ро­ванием и де­ко­ди­ро­ванием кор­те­жей, ско­рее все­го, бу­дут про­бле­мы. Вы­хо­дов из этой си­туа­ции два: ли­бо не ис­поль­зо­вать на­шу сис­те­му универ­саль­ным спо­со­бом, ли­бо ог­раничит­ся стан­дарт­ны­ми ти­па­ми дан­ных (что оз­на­ча­ет – вме­сто кор­те­жей ис­поль­зо­вать спи­ски).

encode_tuple(Tuple, EncodeDispatcher) ->
Tag = encode_tag(#tag{class = universal, form = constructed, tag_value = 32}),
{ContentLength, ContentBinary} = encode_sequence_content(tuple_to_list(Tuple), EncodeDispatcher),
list_to_binary([Tag, encode_length(ContentLength), ContentBinary]).

Ме­тод encode_sequence_content/2 реа­ли­зу­ет ал­го­ритм ко­ди­ро­вания со­дер­жи­мо­го объ­ек­та со­став­но­го ти­па дан­ных, о ко­то­ром мы го­во­ри­ли вы­ше. В этой реа­ли­за­ции мы счи­та­ем, что со­став­ной тип дан­ных яв­ля­ет­ся спи­ском, по­это­му для всех дру­гих со­став­ных ти­пов дан­ных необ­хо­ди­мо пре­об­ра­зо­вы­вать их со­дер­жи­мое в спи­сок (что де­ла­ет­ся, на­при­мер, в ме­то­де encode_tuple/2).

encode_sequence_content(Sequence, EncodeDispatcher) ->
lists:foldl(fun(Element, {Length, Binary}) ->
EncodedElement = encode(Element, EncodeDispatcher),
EncodedSize = size(EncodedElement),
{Length + EncodedSize, list_to_binary([Binary, EncodedElement])}
end, {0, <<>>}, Sequence).

По­следний под­дер­жи­вае­мый в на­шем при­ме­ре тип дан­ных – атом. Он ко­ди­ру­ет­ся по тем же прин­ци­пам, что и стро­ка ок­те­тов; для это­го атом пре­об­ра­зу­ет­ся в би­то­вую стро­ку при по­мо­щи BIF atom_to_binary/2 в ко­ди­ров­ке utf8. Для ато­мов зна­чение ти­па дан­ных рав­ня­ет­ся 16161 = 2#0011111100100001 (класс – universal, фор­ма – constructed, иден­ти­фи­ка­тор – 33)

encode_atom(Atom, _EncodeDispatcher) ->
Tag = encode_tag(#tag{class = universal, form = primitive, tag_value = 33}),
AtomBinary = atom_to_binary(Atom, utf8),
list_to_binary([Tag, encode_length(size(AtomBinary)), AtomBinary]).

Вот и все с ко­ди­ро­ванием дан­ных, но оста­ет­ся еще за­да­ча, как за­ко­ди­ро­ван­ные на­ми дан­ные по­том рас­ко­ди­ро­вать. Об этом мы по­го­во­рим в сле­дую­щей ста­тье – за­вер­шаю­щей цик­л «Прак­ти­кум функ­цио­наль­но­го про­грам­ми­ро­вания на язы­ке Erlang».

Персональные инструменты
купить
подписаться
Яндекс.Метрика