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

LXF156:Erlang

Материал из Linuxformat
(Различия между версиями)
Перейти к: навигация, поиск
Строка 10: Строка 10:
  
 
{{Врезка|left|Заголовок=Наш эксперт |Ширина=20%|Содержание= Ан­д­рей Уша­ков
 
{{Врезка|left|Заголовок=Наш эксперт |Ширина=20%|Содержание= Ан­д­рей Уша­ков
−
ак­тив­но при­бли­жа­ет тот день, ко­гда функ­цио­наль­ные язы­ки ста­нут мейн­ст­ри­мом.}  
+
ак­тив­но при­бли­жа­ет тот день, ко­гда функ­цио­наль­ные язы­ки ста­нут мейн­ст­ри­мом.}}
 
   
 
   
 
'''В''' этом но­ме­ре мы про­дол­жа­ем наш прак­ти­кум по функ­цио­наль­но­му про­грам­ми­ро­ванию: при­шла по­ра оп­ро­бо­вать «чер­ную ма­гию» би­то­вых строк на боль­шом при­ме­ре. В ка­че­­ст­ве та­ко­го боль­шо­го при­ме­ра мы реа­ли­зу­ем ASN.1-со­вмес­ти­мую се­риа­ли­за­цию и де­се­риа­ли­за­цию объ­ек­тов язы­ка Erlang.
 
'''В''' этом но­ме­ре мы про­дол­жа­ем наш прак­ти­кум по функ­цио­наль­но­му про­грам­ми­ро­ванию: при­шла по­ра оп­ро­бо­вать «чер­ную ма­гию» би­то­вых строк на боль­шом при­ме­ре. В ка­че­­ст­ве та­ко­го боль­шо­го при­ме­ра мы реа­ли­зу­ем ASN.1-со­вмес­ти­мую се­риа­ли­за­цию и де­се­риа­ли­за­цию объ­ек­тов язы­ка Erlang.

Версия 07:11, 13 июля 2018

Подписка на печатную версию
Весь 2015 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Подписка на электронную версию
Весь 2015 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Подшивки старых номеров журнала (печатные версии)
Весь 2014 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)


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».

232609.png 232610.png

Ushakov.A.psd Наш эксперт

Ан­д­рей Уша­ков ак­тив­но при­бли­жа­ет тот день, ко­гда функ­цио­наль­ные язы­ки ста­нут мейн­ст­ри­мом.

232549.png Рис. 1.

Pict1.psd 232640.png Рис. 2.

Pict2.psd 231831.png Не хотите пропустить номер? Подпишитесь на www.linuxformat.ru/subscribe/!

По­лез­ные за­мет­ки: Стан­дар­ты ASN.1

232246.png ITU-T Rec. X.680 | ISO/IEC 8824-1. Спе­ци­фи­ка­ция на ба­зо­вую но­та­цию.

232244.png ITU-T Rec. X.681 | ISO/IEC 8824-2. Спе­ци­фи­ка­ция на ин­фор­ма­ци­он­ные объ­ек­ты.

232242.png ITU-T Rec. X.682 | ISO/IEC 8824-3. Спе­ци­фи­ка­ция на ог­ра­ни­че­ния.

232240.png ITU-T Rec. X.683 | ISO/IEC 8824-4. Спе­ци­фи­ка­ция на па­ра­мет­ри­за­цию ASN.1.

232238.png ITU-T Rec. X.690 | ISO/IEC 8825-1. Спе­ци­фи­ка­ция на BER (Basic encoding rules), CER (Canonical encoding rules) и DER (Distinguished encoding rules).

232236.png ITU-T Rec. X.691 | ISO/IEC 8825-2. Спе­ци­фи­ка­ция на PER (Packed encoding rules).

232234.png ITU-T Rec. X.692 | ISO/IEC 8825-3. Спе­ци­фи­ка­ция на ECN (Encoding control notation).

232232.png ITU-T Rec. X.693 | ISO/IEC 8825-4. Спе­ци­фи­ка­ция на XER (XML Encoding rules).

232230.png ITU-T Rec. X.694 | ISO/IEC 8825-5. Спе­ци­фи­ка­ция на ото­бра­же­ние на XSD.

232228.png ITU-T Rec. X.695 | ISO/IEC 8825-6. Спе­ци­фи­ка­ция на ре­ги­ст­ра­цию и при­ме­не­ние ин­ст­рук­ций ко­ди­ро­ва­ния PER (Packed encoding rules).

Источник — «http://wiki.linuxformat.ru/wiki/index.php?title=LXF156:Erlang&oldid=16926»
Персональные инструменты
купить
подписаться
Яндекс.Метрика