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

LXF155:Вникать в Erlang

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


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

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

Ма­ни­пу­ли­руя би­та­ми и бай­та­ми, Ан­д­рей Уша­ков кол­ду­ет над стро­ка­ми: то пе­ре­стро­ит их в дру­гом по­ряд­ке, то ин­вер­ти­ру­ет...

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

Наш эксперт

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

Да­вай­те вспомним, что та­кое би­то­вые стро­ки и для че­го они нуж­ны (бо­лее под­роб­но см. LXF148). Би­то­вые стро­ки – это тип дан­ных, по­зво­ляю­щий ра­бо­тать с низ­ко­уровневы­ми дан­ны­ми бо­лее струк­ту­ри­ро­ван­ным, чем на­бор (мас­сив) байт, спо­со­бом. Это оз­на­ча­ет, что мы мо­жем за­да­вать или из­вле­кать дан­ные пор­ция­ми (ко­то­рые на­зы­ва­ют­ся сег­мен­та­ми) про­из­воль­но­го раз­ме­ра, имею­щи­ми один из пре­до­пре­де­лен­ных ти­пов. За­да­вать сег­мен­ты мы мо­жем как в вы­ра­жениях, так и в опе­ра­ци­ях со­от­вет­ст­вия шаб­ло­ну [pattern-matching], а из­вле­кать дан­ные сег­мен­та­ми – толь­ко в опе­ра­ци­ях со­от­вет­ст­вия шаб­ло­ну. Ка­ж­дый сег­мент со­сто­ит из зна­чения или пе­ре­мен­ной (инициа­ли­зи­ро­ван­ной ли­бо неинициа­ли­зи­ро­ван­ной), раз­ме­ра и спи­ска спе­ци­фи­ка­то­ров, оп­ре­де­ляю­щих тип сег­мен­та. Раз­мер и спи­сок спе­ци­фи­ка­то­ров, оп­ре­де­ляю­щих тип сег­мен­та, яв­ля­ют­ся необя­за­тель­ны­ми; ес­ли ка­кой-то из этих ат­ри­бу­тов не за­дан, то для это­го ат­ри­бу­та бе­рет­ся зна­чение по умол­чанию. У сег­мен­тов, ко­то­рые са­ми яв­ля­ют­ся би­то­вы­ми стро­ка­ми (для них спе­ци­фи­ка­тор ти­па бу­дет ли­бо binary, ли­бо bitstring), раз­мер по умол­чанию – вся би­то­вая стро­ка. По­это­му в опе­ра­ции со­от­вет­ст­вия шаб­ло­ну толь­ко по­следний сег­мент в шаб­лоне мо­жет быть би­то­вой стро­кой с раз­ме­ром по умол­чанию (ина­че непо­нят­но, где дол­жен за­кон­чить­ся сег­мент, яв­ляю­щий­ся би­то­вой стро­кой, и на­чать­ся сле­дую­щий за ним сег­мент).

Поби­то­вые опе­ра­то­ры
  • Опе­ра­тор унар­но­го по­би­то­во­го «НЕ» bnot
  • Опе­ра­тор би­нар­но­го по­би­то­во­го «И» band
  • Опе­ра­тор би­нар­но­го по­би­то­во­го «ИЛИ» bor
  • Опе­ра­тор би­нар­но­го по­би­то­во­го «ИСКЛЮЧАЮЩЕЕ ИЛИ» bxor
  • Опе­ра­тор би­нар­но­го би­то­во­го сдви­га вле­во bsl
  • Опе­ра­тор би­нар­но­го би­то­во­го сдви­га впра­во bsr

Так, на­при­мер, пусть X и Y – неинициа­ли­зи­ро­ван­ные пе­ре­мен­ные. Тогда в ре­зуль­та­те вы­полнения вы­ра­жения со­от­вет­ст­вия шаб­ло­ну <<X:1/binary, 2, Y/binary>> = <<1, 2, 3, 4>>, пе­ре­мен­ная X бу­дет иметь зна­чение <<1>>, а пе­ре­мен­ная Y бу­дет иметь зна­чение <<3, 4>>.

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

По­сле крат­ко­го об­зо­ра тео­рии по­ра пе­рей­ти к прак­ти­ке. В ка­че­­ст­ве прак­ти­ки мы рас­смот­рим ряд за­дач, свя­зан­ные с манипу­ля­ци­ей би­та­ми и бай­та­ми в би­то­вых стро­ках и це­лых чис­лах. Спо­соб ре­шения, ко­то­рый мы бу­дем ис­поль­зо­вать в на­ших при­ме­рах, от­ли­ча­ет­ся от спо­со­ба ре­шения та­ких за­дач в та­ких язы­ках, как C/C++ и им по­доб­ные. Обыч­но та­кие за­да­чи ре­ша­ют­ся с ис­поль­зо­ванием по­би­то­вых опе­ра­то­ров «И», «ИЛИ», «НЕ», «ИСКЛЮЧАЮЩЕЕ ИЛИ» и опе­ра­то­ров сдви­га. Та­кой ва­ри­ант ре­шения есть и у нас (язык Erlang со­дер­жит та­кой на­бор опе­ра­то­ров). Но мы пой­дем дру­гим пу­тем: бу­дем ре­шать эти за­да­чи с ис­поль­зо­ванием би­то­вых строк и опе­ра­ций с ними. Но это не оз­на­ча­ет, что мы пол­но­стью от­ка­зы­ва­ем­ся от ис­поль­зо­вания по­би­то­вых опе­ра­то­ров: там, где нам удоб­но их ис­поль­зо­вать, мы бу­дем их ис­поль­зо­вать.

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

Оп­ре­де­лить минималь­ное необ­хо­ди­мое ко­ли­че­­ст­во байт для це­ло­го чис­ла без зна­ка – доста­точ­но три­ви­аль­ная за­да­ча: мы бе­рем ис­ход­ное чис­ло, де­лим его на 256, по­сле че­го бе­рем це­лую часть от де­ления и по­вто­ря­ем пре­ды­ду­щую опе­ра­цию. Чис­ло опе­ра­ций, необ­хо­ди­мых, что­бы по­лу­чить 0 в ка­че­­ст­ве це­лой час­ти ре­зуль­та­та де­ления, бу­дет рав­но минималь­но­му необ­хо­ди­мо­му ко­ли­че­­ст­ву байт для хранения по­ло­жи­тель­но­го це­ло­го чис­ла.

Те­перь да­вай­те раз­бе­рем­ся с це­лы­ми чис­ла­ми со зна­ком. Начнем с от­ри­ца­тель­ных чи­сел. От­ри­ца­тель­ные чис­ла хра­нят­ся в до­полнитель­ном ко­де, для ко­то­ро­го спра­вед­ли­во сле­дую­щее ут­вер­ждение: стар­ший байт чис­ла дол­жен быть в диа­па­зоне от 2#10000000 = 128 до 2#11111111 = 255 (или, что то же са­мое, стар­ший бит чис­ла дол­жен быть ра­вен 1). По­это­му пер­вым ша­гом мы мо­жем раз­де­лить от­ри­ца­тель­ное чис­ло на -129 и взять це­лую часть; по­сле это­го с ре­зуль­та­том це­лой час­ти от де­ления по­сту­па­ем точ­но так же, как и с це­лым чис­лом без зна­ка. Чис­ло опе­ра­ций, необ­хо­ди­мых, что­бы по­лу­чить 0 в ка­че­­ст­ве це­лой час­ти ре­зуль­та­та де­ления, бу­дет рав­но минималь­но­му необ­хо­ди­мо­му ко­ли­че­­ст­ву байт для хранения от­ри­ца­тель­но­го це­ло­го чис­ла.

Пе­рей­дем к по­ло­жи­тель­ным це­лым чис­лам. Ес­ли зна­чение стар­ше­го бай­та по­ло­жи­тель­но­го це­ло­го чис­ла ле­жит в диа­па­зоне от 2#10000000 = 128 до 2#11111111 = 255, то та­кое по­ло­жи­тель­ное це­лое чис­ло мы не смо­жем от­ли­чить от от­ри­ца­тель­но­го це­ло­го чис­ла. Что мы мо­жем сде­лать в та­кой си­туа­ции – это до­ба­вить до­полнитель­ный байт со зна­чением 0 в ка­че­­ст­ве стар­ше­го бай­та. По­это­му пер­вым ша­гом мы мо­жем раз­де­лить по­ло­жи­тель­ное чис­ло на 128, и взять це­лую часть; по­сле это­го с ре­зуль­та­том це­лой час­ти от де­ления по­сту­па­ем точ­но так же, как и с це­лым чис­лом без зна­ка. Чис­ло опе­ра­ций, необ­хо­ди­мых, что­бы по­лу­чить 0 в ка­че­­ст­ве це­лой час­ти ре­зуль­та­та де­ления, бу­дет рав­но минималь­но­му необ­хо­ди­мо­му ко­ли­че­­ст­ву байт для хранения по­ло­жи­тель­но­го це­ло­го чис­ла.

При­ве­ден­ный вы­ше ал­го­ритм для це­лых чи­сел без зна­ка реа­ли­зо­ван в функ­ции integer_size/1. Эта функ­ция яв­ля­ет­ся ин­тер­фейс­ной; вся ра­бо­та по под­сче­ту со­дер­жит­ся в функ­ции integer_size/2, реа­ли­зую­щей при­ве­ден­ный вы­ше ал­го­ритм для це­лых чи­сел без зна­ка. Сле­ду­ет от­ме­тить, что функ­ция integer_size/1 со­дер­жит от­дель­ный ва­ри­ант для 0; это сде­ла­но для удоб­ст­ва реа­ли­за­ции под­сче­та.

integer_size(0) -> 1;

integer_size(Number) when is_integer(Number) ->

integer_size(Number, 0).

integer_size(0, ByteCount) -> ByteCount;

integer_size(Number, ByteCount) ->

integer_size(Number div 256, ByteCount + 1).

Прак­ти­че­­ски то же са­мое мож­но ска­зать и о функ­ци­ях integer_signed_size/1 и integer_signed_size/2: пер­вая яв­ля­ет­ся ин­тер­фейс­ной, а вто­рая реа­ли­зу­ет ал­го­ритм для це­лых чи­сел со зна­ком. И точ­но так же, функ­ция integer_signed_size/1 со­дер­жит от­дель­ный ва­ри­ант для 0, ко­то­рый вве­ден для удоб­ст­ва реа­ли­за­ции под­сче­та.

integer_signed_size(0) -> 1;

integer_signed_size(Number) when is_integer(Number) ->

integer_signed_size(Number, 0).

integer_signed_size(Number, ByteCount) when Number < 0 ->

integer_size(Number div -129, ByteCount + 1);

integer_signed_size(Number, ByteCount) when Number > 0 ->

integer_size(Number div 128, ByteCount + 1).

Да­вай­те про­ве­рим, что на­пи­сан­ные на­ми функ­ции ра­бо­та­ют пра­виль­но. Для це­ло­го чис­ла 127 = 2#01111111 минималь­ное необ­хо­ди­мое для хранения ко­ли­че­­ст­во байт рав­но 1 и для слу­чая, когда мы счи­та­ем его чис­лом без зна­ка, и для слу­чая, когда мы счи­та­ем его чис­лом со зна­ком. Про­ве­ря­ем это: вы­зов bit_utils:integer_size(127) воз­вра­ща­ет 1, вы­зов bit_utils:integer_signed_size(127) так­же воз­вра­ща­ет 1.

Возь­мем бо­лее слож­ный при­мер. Для це­ло­го чис­ла 128 = 2#10000000, когда мы счи­та­ем его чис­лом без зна­ка, минималь­ное необ­хо­ди­мое для хранения ко­ли­че­­ст­во байт рав­но 1, а в слу­чае, когда мы счи­та­ем его чис­лом со зна­ком, минималь­ное необ­хо­ди­мое для хранения ко­ли­че­­ст­во байт рав­но уже 2. Про­ве­ря­ем это: вы­зов bit_utils:integer_size(128) воз­вра­ща­ет 1, а вы­зов bit_utils:integer_signed_size(128) воз­вра­ща­ет 2. Те­перь про­ве­рим для от­ри­ца­тель­ных чи­сел. Для хранения от­ри­ца­тель­но­го чис­ла -128 = 2#10000000 доста­точ­но 1 бай­та, тогда как для хранения от­ри­ца­тель­но­го чис­ла -129 = 2#1111111101111111 уже необ­хо­ди­мо 2 бай­та. Про­ве­ря­ем это: вы­зов bit_utils:integer_signed_size(-128) воз­вра­ща­ет 1, а вы­зов bit_utils:integer_signed_size(-129) воз­вра­ща­ет 2.

По­сле ре­шения пре­ды­ду­щей за­да­чи мы мо­жем ре­шить дру­гую, свя­зан­ную с ней за­да­чу: соз­дать би­то­вую стро­ку, со­дер­жа­щую зна­чение ис­ход­но­го це­ло­го чис­ла. Для ре­шения этой за­да­чи мы долж­ны знать ко­ли­че­­ст­во байт, необ­хо­ди­мое для пред­став­ления ис­ход­но­го це­ло­го чис­ла. Ес­ли при соз­дании сег­мен­та (с ти­пом integer), ко­то­рый дол­жен со­дер­жать це­лое чис­ло, мы не за­да­дим раз­мер сег­мен­та, то бу­дет ис­поль­зо­ван раз­мер по умол­чанию (для це­лых чи­сел это 8 бит), и сег­мент бу­дет со­дер­жать толь­ко млад­ший байт це­ло­го чис­ла. Так, на­при­мер, би­то­вая стро­ка <<256/integer>> бу­дет рав­на би­то­вой стро­ке <<0>>. По­это­му при по­строении би­то­вой стро­ки, со­дер­жа­щей зна­чение це­ло­го чис­ла, знание минималь­но­го необ­хо­ди­мо­го для хранения это­го це­ло­го чис­ла раз­ме­ра яв­ля­ет­ся обя­за­тель­ным. Обя­за­тель­ным яв­ля­ет­ся так­же знание по­ряд­ка хранения байт и яв­ля­ет­ся ли ис­ход­ное чис­ло чис­лом со зна­ком. Оба эти па­ра­мет­ра неза­ви­си­мые и пе­ре­да­ют­ся в ка­че­­ст­ве ис­ход­ных па­ра­мет­ров в на­шу функ­цию. Сле­ду­ет ска­зать, что па­ра­метр, оп­ре­де­ляю­щий, яв­ля­ет­ся ли ис­ход­ное чис­ло чис­лом со зна­ком, влия­ет на то, ка­кой ал­го­ритм вы­чис­ления минималь­но­го необ­хо­ди­мо­го ко­ли­че­­ст­ва байт для хранения це­ло­го чис­ла бу­дет ис­поль­зо­ван.

Эта за­да­ча реа­ли­зо­ва­на в функ­ции integer_to_binary/3. Функ­ция доста­точ­но три­ви­аль­на: в за­ви­си­мо­сти от ис­ход­ных па­ра­мет­ров, оп­ре­де­ляю­щих по­ря­док байт, и яв­ля­ет­ся ли ис­хо­дя­щее це­лое чис­ло чис­лом без зна­ка, мы вы­чис­ля­ем минималь­ное необ­хо­ди­мое ко­ли­че­­ст­во байт для хранения ис­ход­но­го це­ло­го чис­ла и кон­ст­руи­ру­ем со­от­вет­ст­вую­щую би­то­вую стро­ку.

integer_to_binary(Number, Signedness, ByteOrder) when is_integer(Number) ->

case {Signedness, ByteOrder} of

{signed, big} ->

IntegerSize = 8 * integer_signed_size(Number),

<<Number:IntegerSize/signed-integer-big>>;

{signed, little} ->

IntegerSize = 8 * integer_signed_size(Number),

<<Number:IntegerSize/signed-integer-little>>;

{unsigned, big} ->

IntegerSize = 8 * integer_size(Number),

<<Number:IntegerSize/unsigned-integer-big>>;

{unsigned, little} ->

IntegerSize = 8 * integer_size(Number),

<<Number:IntegerSize/unsigned-integer-little>>

end.

Да­вай­те про­ве­рим, что на­ше ре­шение пра­виль­но. Для чис­ла 128, ес­ли счи­тать это чис­ло чис­лом без зна­ка, мы долж­ны по­лу­чить сле­дую­щую би­то­вую стро­ку: <<128>>. Вы­зов bit_utils:integer_to_binary(128, unsigned, big) воз­вра­ща­ет нам <<128>>. Ес­ли же мы счи­та­ем чис­ло 128 чис­лом со зна­ком, то мы долж­ны по­лу­чить би­то­вую стро­ку <<0, 128>>, при усло­вии, что по­ря­док байт у нас от стар­ше­го бай­та к млад­ше­му [big-endian]. Вы­зов bit_utils:integer_to_binary(128, signed, big) воз­вра­ща­ет нам <<0, 128>>. Для чис­ла -128 мы долж­ны по­лу­чить би­то­вую стро­ку <<128>>, а для чис­ла -129 – би­то­вую стро­ку <<255, 127>> (при усло­вии, что по­ря­док байт у нас от стар­ше­го бай­та к млад­ше­му). Вы­зов bit_utils:integer_to_binary(-128, signed, big) воз­вра­ща­ет нам <<128>>; вы­зов bit_utils:integer_to_binary(-129, signed, big) воз­вра­ща­ет <<255, 127>>.

Пой­дем даль­ше: зай­мем­ся те­перь за­да­ча­ми, свя­зан­ны­ми непо­сред­ст­вен­но с би­то­вы­ми стро­ка­ми. В ка­че­­ст­ве пер­вой та­кой за­да­чи мы возь­мем сле­дую­щую: из­менение по­ряд­ка сле­до­вания байт в би­то­вой стро­ке с раз­ме­ром, крат­ным 8 бит. Ре­шение этой за­да­чи три­ви­аль­ное: мы пре­об­ра­зу­ем би­то­вую стро­ку в спи­сок це­лых чи­сел (ка­ж­дый эле­мент спи­ска яв­ля­ет­ся пред­став­лением со­от­вет­ст­вую­ще­го 8-бит­но­го сег­мен­та в ви­де це­ло­го чис­ла), ме­ня­ем по­ря­док сле­до­вания эле­мен­тов в спи­ске на об­рат­ный и пре­об­ра­зу­ем спи­сок це­лых об­рат­но в би­то­вую стро­ку.

reverse_bytes(Binary) when is_binary(Binary) ->

list_to_binary(lists:reverse(binary_to_list(Binary))).

Те­перь мы мо­жем про­ве­рить, что на­ша функ­ция кор­рект­но ра­бо­та­ет: вы­зов bit_utils:reverse_bytes(<<1, 2, 3>>) да­ет впол­не ожи­дае­мый ре­зуль­тат <<3, 2, 1>>.

Да­вай­те усложним пре­ды­ду­щую за­да­чу: бу­дем ме­нять по­ря­док сле­до­вания бит в би­то­вой стро­ке на об­рат­ный. За­ме­тим, что сле­дую­щие дей­ст­вия да­ют тот же ре­зуль­тат, что и ре­шение «в лоб»: раз­де­ля­ем би­то­вую стро­ку на 8-би­то­вые сег­мен­ты (и воз­мож­ный оста­ток, раз­мер ко­то­ро­го мень­ше 8 бит), ме­ня­ем по­ря­док сле­до­вания сег­мен­тов на об­рат­ный и, для ка­ж­до­го сег­мен­та, ме­ня­ем по­ря­док сле­до­вания би­тов в нем на об­рат­ный. По­сле че­го со­би­ра­ем спи­сок сег­мен­тов об­рат­но в би­то­вую стро­ку. Раз­де­лить би­то­вую стро­ку на 8-би­то­вые сег­мен­ты и воз­мож­ный оста­ток (раз­мер ко­то­ро­го будет мень­ше 8 бит) мы мо­жем с по­мо­щью BIF bitstring_to_list/1.

reverse_bits(Bitstring) when is_bitstring(Bitstring) ->

Segments = bitstring_to_list(Bitstring),

ReversedSegments = lists:map(fun reverse_segment/1, lists:reverse(Segments)),

list_to_bitstring(ReversedSegments).

Для из­менения по­ряд­ка сле­до­вания бит в ка­ж­дом эле­мен­те спи­ска сег­мен­тов мы ис­поль­зу­ем функ­цию reverse_segment/1 (эту функ­цию мы ис­поль­зу­ем из lists:map/2 для пре­об­ра­зо­вания сег­мен­тов с нор­маль­ным по­ряд­ком бит в сег­мен­ты с об­рат­ным по­ряд­ком бит). Эта функ­ция име­ет ва­ри­ант для це­лых чи­сел, т. к. обыч­ные 8-бит­ные сег­мен­ты в спи­ске у нас пред­став­ле­ны в ви­де це­лых чи­сел, и ва­ри­ан­ты для об­ра­бот­ки би­то­вых сег­мен­тов раз­ме­ром от 1 до 8 бит.

reverse_segment(Number) when is_integer(Number) ->

reverse_segment(<<Number:8>>);

reverse_segment(<<B7:1, B6:1, B5:1, B4:1, B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1, B4:1, B5:1, B6:1, B7:1>>;

reverse_segment(<<B6:1, B5:1, B4:1, B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1, B4:1, B5:1, B6:1>>;

reverse_segment(<<B5:1, B4:1, B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1, B4:1, B5:1>>;

reverse_segment(<<B4:1, B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1, B4:1>>;

reverse_segment(<<B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1>>;

reverse_segment(<<B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1>>;

reverse_segment(<<B1:1, B0:1>>) ->

<<B0:1, B1:1>>;

reverse_segment(<<B0:1>>) ->

<<B0:1>>.

Те­перь при­шла по­ра про­ве­рить, что на­ша реа­ли­за­ция ал­го­рит­ма из­менения по­ряд­ка бит в би­то­вом сло­ве ра­бо­та­ет пра­виль­но. В ка­че­­ст­ве ис­ход­ной би­то­вой стро­ки возь­мем стро­ку <<1, 2, 3:4>>. В дво­ич­ном пред­став­лении она име­ет сле­дую­щий вид: <<2#00000001, 2#00000010, 2#0011>>. По­сле из­менения по­ряд­ка сле­до­вания бит на об­рат­ный эта би­то­вая стро­ка в дво­ич­ном пред­став­лении при­мет вид <<2#1100, 2#01000000, 2#10000000>>. По­сле пе­ре­груп­пи­ров­ки сег­мен­тов со­глас­но пра­ви­лам пред­став­ления би­то­вых строк в язы­ке Erlang (когда оста­ток, не крат­ный 8 бит, идет в кон­це) би­то­вая стро­ка в дво­ич­ном пред­став­лении бу­дет иметь вид <<2#11000100, 2#00001000, 2#0000>>, а в де­ся­тич­ном пред­став­лении – <<196, 8, 0:4>>. Вы­зов bit_utils:reverse_bits(<<1, 2, 3:4>>) да­ет ожи­дае­мый ре­зуль­тат <<196, 8, 0:4>>. Это да­ет нам пра­во счи­тать, что на­ша реа­ли­за­ция ра­бо­та­ет пра­виль­но.

Да­вай­те пе­рей­дем к сле­дую­щей за­да­че: по­счи­та­ем ко­ли­че­­ст­во бит со зна­чением 1 в би­то­вой стро­ке (чи­та­тель мо­жет обоб­щить эту за­да­чу и реа­ли­зо­вать функ­цию по под­сче­ту ко­ли­че­­ст­ва бит с оп­ре­де­лен­ным зна­чением в би­то­вой стро­ке). Са­мо по се­бе ре­шение этой за­да­чи доста­точ­но три­ви­аль­но: необ­хо­ди­мо ре­кур­сив­но (при по­мо­щи хво­сто­вой ре­кур­сии) об­ра­бо­тать би­то­вую стро­ку, вы­де­ляя пер­вый бит и оста­ток. Реа­ли­за­ция со­сто­ит из двух функ­ций: setbit_count/1 и setbit_count/2. Пер­вая яв­ля­ет­ся ин­тер­фейс­ной функ­ци­ей, а вто­рая при по­мо­щи раз­ных ва­ри­ан­тов оп­ре­де­ления функ­ции реа­ли­зу­ет ре­шение дан­ной за­да­чи.

setbit_count(Bitstring) when is_bitstring(Bitstring) ->

setbit_count(Bitstring, 0).

setbit_count(<<>>, Count) -> Count;

setbit_count(<<1:1, Rest/bitstring>>, Count) ->

setbit_count(Rest, Count + 1);

setbit_count(<<0:1, Rest/bitstring>>, Count) ->

setbit_count(Rest, Count).

Мож­но эту за­да­чу ре­шить дру­гим спо­со­бом: с по­мо­щью вы­ра­жения кон­ст­руи­ро­вания би­то­вой стро­ки [Bitstring Comprehensions]. В этом вы­ра­жении ис­точником бу­дет ис­ход­ная би­то­вая стро­ка, из ко­то­рой мы бу­дем из­вле­кать сег­мен­ты раз­ме­ром 1 бит, а фильт­ром бу­дет вы­ра­жение, про­пускаю­щее толь­ко те сег­мен­ты, ко­то­рые со­дер­жат 1. Ко­ли­че­­ст­во бит со зна­чением 1 бу­дет рав­но длине по­лу­чен­ной би­то­вой стро­ки, ко­то­рую мы мо­жем под­счи­тать при по­мо­щи BIF bit_size/1. Вы­гля­дит это вы­ра­жение сле­дую­щим об­ра­зом (здесь Bitstring – пе­ре­мен­ная, со­дер­жа­щая ис­ход­ную би­то­вую стро­ку): bit_size(<< <<Bit:1>> || <<Bit:1>> <= Bitstring, Bit == 1 >>).

Те­перь мож­но про­ве­рить ра­бо­ту на­шей функ­ции. Би­то­вая стро­ка <<2#110010101:9>> со­дер­жит 5 бит со зна­чением 1. Вы­зов bit_utils:setbit_count(<<2#110010101:9>>) да­ет нам число 5.

Да­вай­те рас­смот­рим еще па­ру по­доб­ных за­дач: под­счи­та­ем ко­ли­че­­ст­во ве­ду­щих и за­вер­шаю­щих би­тов со зна­чением 0 в би­то­вой стро­ке. Эти за­да­чи схо­жи с пре­ды­ду­щей ре­шением: мы ре­кур­сив­но (при по­мо­щи хво­сто­вой ре­кур­сии) об­ра­ба­ты­ва­ем би­то­вую стро­ку, вы­де­ляя пер­вый или по­следний (в за­ви­си­мо­сти от за­да­чи) бит и оста­ток. От­ли­ча­ет эти за­да­чи от пре­ды­ду­щей усло­вие пре­кра­щения ра­бо­ты: ес­ли в пре­ды­ду­щей за­да­че мы пол­но­стью про­хо­ди­ли по би­то­вой стро­ке, то в рас­смат­ри­вае­мых в дан­ный мо­мент за­да­чах мы пре­кра­ща­ем об­ра­бот­ку, как толь­ко нам встре­тит­ся бит со зна­чением 1. Что ин­те­рес­но, дан­ные две за­да­чи ре­шить с по­мо­щью вы­ра­жения кон­ст­руи­ро­вания би­то­вых строк [Bitstring Comprehensions] невоз­мож­но.

За­да­ча по под­сче­ту ко­ли­че­­ст­ва ве­ду­щих бит со зна­чением 0 ре­ша­ет­ся в сле­дую­щих двух функ­ци­ях: head_unsetbit_count/1 и head_unsetbit_count/2. Пер­вая функ­ция яв­ля­ет­ся ин­тер­фейс­ной, вто­рая функ­ция реа­ли­зу­ет ал­го­ритм по под­сче­ту ко­ли­че­­ст­ва ве­ду­щих бит со зна­чением 0; усло­ви­ем окон­чания ра­бо­ты яв­ля­ет­ся факт по­яв­ления би­та со зна­чением 1 на мес­те об­ра­ба­ты­вае­мо­го, ли­бо об­ра­бот­ка всей би­то­вой стро­ки.

head_unsetbit_count(Bitstring) when is_bitstring(Bitstring) ->

head_unsetbit_count(Bitstring, 0).

head_unsetbit_count(<<>>, Count) -> Count;

head_unsetbit_count(<<0:1, Rest/bitstring>>, Count) ->

head_unsetbit_count(Rest, Count + 1);

head_unsetbit_count(<<1:1, _Rest/bitstring>>, Count) -> Count.

За­да­ча по под­сче­ту ко­ли­че­­ст­ва за­вер­шаю­щих бит со зна­чением 0 ре­ша­ет­ся в сле­дую­щих двух функ­ци­ях: tail_unsetbit_count/1 и tail_unsetbit_count/2. Как и во всех по­доб­ных за­да­чах, пер­вая функ­ция яв­ля­ет­ся ин­тер­фейс­ной, а вто­рая реа­ли­зу­ет ал­го­ритм за­да­чи. От­ли­чие этой за­да­чи от пре­ды­ду­щей за­клю­ча­ет­ся в том, с ка­ко­го кон­ца би­то­вой стро­ки бе­рут­ся би­ты на об­ра­бот­ку. В пре­ды­ду­щей за­да­че мы бра­ли би­ты с на­ча­ла би­то­вой стро­ки, а в те­ку­щей за­да­че – с кон­ца би­то­вой стро­ки. Когда мы ре­кур­сивно об­ра­ба­ты­ва­ем би­то­вую стро­ку с на­ча­ла, раз­де­ляя ее на сег­мент и оста­ток, то в этом слу­чае мы име­ем доста­точ­но про­стое вы­ра­жение со­от­вет­ст­вия шаб­ло­ну, т. к. мы мо­жем не за­да­вать раз­мер остат­ка. Когда мы ре­кур­сив­но об­ра­ба­ты­ва­ем би­то­вую стро­ку с кон­ца, раз­де­ляя ее на сег­мент и оста­ток, то в этом слу­чае вы­ра­жение со­от­вет­ст­вия шаб­ло­ну бо­лее слож­ное, т. к. мы обя­за­ны вы­чис­лить и за­дать раз­мер остат­ка яв­но. Разницу в реа­ли­за­ции об­ра­бот­ки би­то­вой стро­ки с на­ча­ла и с кон­ца мож­но уви­деть в реа­ли­за­ции пре­ды­ду­щей и те­ку­щей за­дач (в ка­че­­ст­ве со­ве­та: когда есть та­кая воз­мож­ность, всегда реа­ли­зуй­те об­ра­бот­ку би­то­вой стро­ки с ее на­ча­ла).

tail_unsetbit_count(Bitstring) when is_bitstring(Bitstring) ->

tail_unsetbit_count(Bitstring, 0).

tail_unsetbit_count(<<>>, Count) -> Count;

tail_unsetbit_count(Bitstring, Count) ->

RestSize = bit_size(Bitstring) - 1,

<<Rest:RestSize/bitstring, TailBit:1>> = Bitstring,

case TailBit of

0 -> tail_unsetbit_count(Rest, Count + 1);

1 -> Count

end.

Как обыч­но, по­сле реа­ли­за­ции за­да­чи про­ве­рим пра­виль­ность этой реа­ли­за­ции. В би­то­вой стро­ке <<2#000110000:9>> – 3 ве­ду­щих би­та со зна­чением 0 и 4 за­вер­шаю­щих би­та со зна­чением 0. Пусть пе­ре­мен­ная Bitstring со­дер­жит зна­чение <<2#000110000:9>>; тогда вы­зов bit_utils:head_unsetbit_count(Bitstring) воз­вра­ща­ет 3, а вы­зов bit_utils:tail_unsetbit_count(Bitstring) воз­вра­ща­ет 4.

В ка­че­­ст­ве по­следней за­да­чи на се­го­дня, рас­смот­рим за­да­чу ин­вер­ти­ро­вания со­дер­жи­мо­го би­то­вой стро­ки. Эту за­да­чу мож­но ре­шить дву­мя раз­ны­ми спо­со­ба­ми: с ис­поль­зо­ванием хво­сто­вой ре­кур­сии и с ис­поль­зо­ванием вы­ра­жений кон­ст­руи­ро­вания би­то­вых строк [Bitstring Comprehensions].

Да­вай­те ре­шим эту за­да­чу с ис­поль­зо­ванием вы­ра­жений кон­ст­руи­ро­вания би­то­вых строк; оче­вид­но, что вы­ра­жение по­лу­чит­ся три­ви­аль­ное, т. к. у нас толь­ко один ис­точник, из ко­то­ро­го мы бу­дем доста­вать дан­ные сег­мен­та­ми раз­ме­ром в 1 бит, и от­сут­ст­ву­ют ка­кие-ли­бо фильт­ры.

Един­ст­вен­ный мо­мент, ко­то­рый мо­жет вы­звать во­прос – это как по­лу­чить ин­вер­ти­ро­ван­ное зна­чение би­та. В язы­ке Erlang есть опе­ра­тор bnot, ко­то­рый яв­ля­ет­ся по­би­то­вым опе­ра­то­ром «НЕ». Это оз­на­ча­ет, что bnot 0 ра­вен -1, а bnot 1 ра­вен -2. Конеч­но, мож­но ис­поль­зо­вать и этот опе­ра­тор с уче­том об­ре­зания зна­чения до од­но­го би­та, когда мы бу­дем соз­да­вать сег­мент раз­ме­ром 1 бит. Но мы вос­поль­зу­емся дру­гим би­то­вым опе­ра­тором, ко­то­рый без вся­ко­го об­ре­зания по­зво­ля­ет нам ин­вер­ти­ро­вать зна­чения би­тов: это по­би­то­вый опе­ра­тор «ИСКЛЮЧАЮЩЕГО ИЛИ» или bxor.

inverse(Bitstring) when is_bitstring(Bitstring) ->

<< <<(Bit bxor 1):1>> || <<Bit:1>> <= Bitstring >>.

Ос­та­лось толь­ко про­ве­рить пра­виль­ность реа­ли­за­ции на­ше­го ал­го­рит­ма: для би­то­вой стро­ки <<2#01101001>> ин­вер­ти­ро­ван­ное зна­чение бу­дет <<2#10010110>> или <<150>>. Вы­зов bit_utils:inverse(<<2#01101001>>) воз­вра­ща­ет <<150>>.

Что­бы все при­ве­ден­ные здесь при­ме­ры ра­бо­та­ли, необ­хо­ди­мо ор­ганизо­вать их в мо­дуль и соз­дать спи­сок экс­пор­ти­руе­мых функ­ций. При­ве­ден­ные ниже стро­ки де­ла­ют это (и не за­бы­ва­ем, что имя фай­ла долж­но быть имя мо­ду­ля с рас­ши­рением “.erl”):

-module(bit_utils).

-export([reverse_bytes/1, reverse_bits/1]).

-export([integer_size/1, integer_signed_size/1, integer_to_binary/3]).

-export([setbit_count/1, head_unsetbit_count/1, tail_unsetbit_count/1, inverse/1]).

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

Оп­ре­де­ление сег­мен­тов в би­то­вых стро­ках

Би­то­вая стро­ка со­сто­ит из сег­мен­тов: <<E1, …, En>> (воз­мож­на си­туа­ция, когда в би­то­вой стро­ке нет ни од­но­го сег­мен­та; та­кая би­то­вая стро­ка на­зы­ва­ет­ся пустой – <<>>) Ка­ж­дый сег­мент Ei со­сто­ит из зна­чения ли­бо пе­ре­мен­ной (инициа­ли­зи­ро­ван­ной или неинициа­ли­зи­ро­ван­ной), необя­за­тель­но­го раз­ме­ра и необя­за­тель­но­го спи­ска спе­ци­фи­ка­то­ров фор­ма­та. Та­ким об­ра­зом, сег­мент би­то­вой стро­ки Ei мо­жет иметь один из сле­дую­щих ви­дов:

  • Ei = Value
  • Ei = Value:Size
  • Ei = Value/TypeSpecifierList
  • Ei = Value:Size/TypeSpecifierList

Здесь Value – зна­чение ли­бо пе­ре­мен­ная (как инициа­ли­зи­ро­ван­ная, так и неинициа­ли­зи­ро­ван­ная), Size – раз­мер сег­мен­та в неко­то­рых единицах (см. да­лее), TypeSpecifierList – спи­сок спе­ци­фи­ка­то­ров ти­па сег­мен­та.

Зна­чение Value долж­но быть од­но­го из сле­дую­щих ти­пов: це­лое чис­ло, дей­ст­ви­тель­ное чис­ло, би­то­вая стро­ка. Для раз­ме­ра сег­мен­та Size зна­чение по умол­чанию для сег­мен­тов с ти­пом integer – 8, для сег­мен­тов с ти­пом float – 64, для сег­мен­тов с ти­пом binary и bitstring – вся би­то­вая стро­ка. Раз­мер сег­мен­та Size не за­да­ет­ся для сег­мен­тов с одним из сле­дую­щих ти­пов: utf8, utf16, utf32. Спи­сок спе­ци­фи­ка­то­ров ти­па сег­мен­та TypeSpecifierList – это спи­сок из сле­дую­щих зна­чений, раз­де­лен­ных де­фи­сом “-”, ко­то­рые мо­гут ид­ти в лю­бом по­ряд­ке:

  • Тип сег­мен­та, од­но из сле­дую­щих зна­чений: integer, float, binary, bytes, bitstring, bits, utf8, utf16, utf32. Зна­чение по умол­чанию для ти­па сег­мен­та – integer. Ти­пы binary и bytes эк­ви­ва­лент­ны; ана­ло­гич­но, ти­пы bitstring и bits эк­ви­ва­лент­ны.
  • На­ли­чие зна­ка у зна­чения Value, од­но из сле­дую­щих зна­чений: signed, unsigned. При­меним толь­ко для сег­мен­тов с ти­пом integer. Зна­чение по умол­чанию – unsigned.
  • По­ря­док байт, од­но из сле­дую­щих зна­чений: big, little, native. При­меним толь­ко для сег­мен­тов с одним из сле­дую­щих ти­пов: integer, utf16, utf32, float. Зна­чение по умол­чанию – big.
  • Раз­мер единицы, в ко­то­рых за­да­ет­ся раз­мер сег­мен­та Size. Име­ет сле­дую­щий вид unit:IntegerLiteral, где зна­чение IntegerLiteral долж­но быть в диа­па­зоне от 1 до 256. Непри­меним для сег­мен­тов од­но­го из сле­дую­щих ти­пов: utf8, utf16, utf32. Зна­чение по умол­чанию – 1 для сег­мен­тов с одним из сле­дую­щих ти­пов: integer, float, bitstring; зна­чение по умол­чанию – 8 для сег­мен­тов с ти­пом binary. Ре­аль­ное зна­чение раз­ме­ра сег­мен­та (в би­тах) рав­ня­ет­ся Size * unit. Для сег­мен­тов ти­па binary (bytes) ре­аль­ный раз­мер дол­жен быть кра­тен 8.

В вы­ра­жении со­от­вет­ст­вия шаб­ло­ну [pattern matching] толь­ко крайний спра­ва сег­мент мо­жет иметь тип bitstring или binary и зна­чение раз­ме­ра сег­мен­та по умол­чанию. Для всех осталь­ных сег­мен­тов с ти­пом binary или bitstring раз­мер сег­мен­та дол­жен быть за­дан яв­но.

Так, на­при­мер, следующее вы­ра­жение: << X:1/binary, Y/binary >> = <<1, 2, 3>> яв­ля­ет­ся кор­рект­ным, а вы­ра­жение << X/binary, Y/binary >> = <<1, 2, 3>> кор­рект­ным не яв­ля­ет­ся.

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