Байт стаффинг. Алгоритм.

← →
Kolan © (2006-02-01 12:21) [0]

Здравствуйте,
Есть такая вещь - байтстаффинг. Смысл в том что посылка обрамляется начальным и конечным байтом. Кроме того для избежания коллизий, когда нутри покета оказывается байт равный начальному или конечному, эти быйты удваиваются. Ну и естественно обратная задача - избавится от повторений...

Вот как "зшифровать" понятно - конечный автома:

procedure TSendStuffer.StaffByteArray(SourceBuffer: TByteArray; var ResultBuffer: TByteArray); var I: Integer; begin SetLength(ResultBuffer, 0); if FState = ssIdle then FState := ssPackageSendStart; I := Low(SourceBuffer); while FState <> ssIdle do begin case FState of ssWaitForSecondEndByte: begin AddByteToArray(ResultBuffer, EndByte); FState := ssSendAnyByte; end; ssWaitForSecondStartByte: begin AddByteToArray(ResultBuffer, StartByte); FState := ssSendAnyByte; end; ssAfterEndByte: begin AddByteToArray(ResultBuffer, AfterEndByte); FState := ssPackageSendFinished; end; ssSendAnyByte: begin if I > High(SourceBuffer) then begin AddByteToArray(ResultBuffer, EndByte); FState := ssAfterEndByte; end else begin AddByteToArray(ResultBuffer, SourceBuffer[I]); case SourceBuffer[I] of EndByte: FState := ssWaitForSecondEndByte; StartByte: FState := ssWaitForSecondStartByte; end; I := I + 1; end; end; ssPackageSendFinished: begin FState := ssIdle; end; ssPackageSendStart: begin AddByteToArray(ResultBuffer, StartByte); FState := ssSendAnyByte; end; end; end; end;

И как разобрать тоже вроде ясно:

function TReceiveStuffer.DeleteStaffingInByteArray( SourceBuffer: array of Byte; var ResultBuffer: TByteArray): Boolean; var I: Integer; begin Result := False; if (SourceBuffer[Low(SourceBuffer)] = StartByte) and (SourceBuffer[High(SourceBuffer) - 1] = EndByte) and (SourceBuffer[High(SourceBuffer)] = AfterEndByte) then begin Result := True; SetLength(ResultBuffer, 0); if FState = rsIdle then FState := rsPackageReceiveStart; I := Low(SourceBuffer); while FState <> rsIdle do begin case FState of rsPackageReceiveStart: begin if SourceBuffer[I] = StartByte then begin FState := rsSendAnyByte; I := I + 1; end; end; rsSendAnyByte: begin case SourceBuffer[I] of StartByte: FState := rsWaitForSecondStartByte; EndByte: FState := rsWaitForSecondEndByte; else AddByteToArray(ResultBuffer, SourceBuffer[I]); FState := rsSendAnyByte; end; I := I + 1; end; rsWaitForSecondStartByte: begin case SourceBuffer[I] of StartByte: begin AddByteToArray(ResultBuffer, StartByte); I := I + 1; FState := rsSendAnyByte; end; EndByte: FState := rsWaitForSecondEndByte; end; end; rsWaitForSecondEndByte: begin if SourceBuffer[I] = EndByte then begin AddByteToArray(ResultBuffer, EndByte); I := I + 1; FState := rsSendAnyByte; end else FState := rsPackageReceiveFinished; end; rsPackageReceiveFinished: begin FState := rsIdle; end; end; end; end; end;

Но обратный разбор работает только если потек пришел целый... И условие я соответствующие добавил.

Проблемма в том что пакет может разорваться. те состоять из нескольких частей. есть идей как это учесть?

Те надо как-то добавлять полученный массивы в анализируемый. Желательно обойтись без потоков... Но это не обезательно..

← →
Evgeny V © (2006-02-01 13:01) [1]

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

Если не изменяет память, то стартовый и завершающий байт - уникален -например всегда 0EFH (точно какие байты используются не помню, но выбраны довольно редко встречающиеся байты) заменяется на другой к примеру 0EDH (тоже написал примерно) в блоке данных. А вот уже при встрече этого байта в блоке происходит удвоение байтов. В этом случае ьы однозначно можешь определить начало и конец пакета даже при фрагментации, используя в добавок тайм-ауты ожидания полного приема пакета, так как начало и конец уникальны. И если за время тайм-аута пакет не завершен, то можно сбросить флаг начала пакета(а это уже логический флаг, который взводится при старте пакета и сбрасывается при окончании пакета или истечении тайм-аута). И это еще не все. На всякий случай в конец блока помещается его контрольная сумма, и блок считается принятым, если совпала еще и сумма. Примерно похожий алгоритм реализуется, но на уровне битов (подмена бит) в протоколе AX25 (пакетный радио протокол).

← →
Kolan © (2006-02-01 13:50) [2]

Протокол менять нельзя...
Ладно что-нить придумаю...

← →
Rouse_ © (2006-02-01 14:33) [3]

> Проблемма в том что пакет может разорваться. те состоять
> из нескольких частей. есть идей как это учесть?

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

← →
Kolan © (2006-02-01 22:29) [4]

Начинай разбор только после прихода целого пакета. т.е. жди пога до тебя дойдт все оставшиеся части...

Хорошая мысль. Она мне пришла. Вопрос как? Есть желание этот алгоритм не трогать, а написать еще один класс, который кокраз и будет отвечать за склеивание и выделение пакета.

Чуть помозгую и еще вопросы будут не могу понять как это технически делать...

← →
GanibalLector © (2006-02-01 22:48) [5]

2 Kolan
> в том что пакет может разорваться. те состоять из нескольких частей.
с СОМ"ом работаешь ;) По схеме tesseract"а.
Я делаю не так.Когда протокол подобный [0] я читаю все,до TimeOut(или даже до нескольких TimeOut).А только потом,смотрю начало\конец.Если в пакете есть и начало и конец и CRC вырный,то только тогда начинаю разбор пакета.

← →
Defunct © (2006-02-02 02:32) [6]

Я вообще стараюсь такой протокол избегать.
либо кодировку применяю, чтобы четко были упр. символы START/CR (CRLF). Либо заголовок пакета, по аналогии с IP стеком.

Но в тех редких случаях когда все-таки приходилось иметь дело с таким монстриком да еще и без CRC - выделял пакет на ходу. Просто закрывал глаза на ошибки разбора (в виду дибильности протокола).

← →
Defunct © (2006-02-02 02:32) [7]

Удалено модератором
Примечание: Дубль...

← →
REA (2006-02-02 11:57) [8]

CRC все же не помешает

← →
Kolan © (2006-02-02 12:37) [9]

GanibalLector © (01.02.06 22:48) [5]
Нет. Этот протокол мне навязан разработчиком устройства.
Я вот с чем парюсь: Алгоритм позволяет выделить пакет даже если он разбит на множество частей.

Допустим этому "стафферу" пришел массив (пол пакета, допустим) если добавить соотв условие, то прочитав весь массив до конца, он должен будет уснуть...

Вот как добавить второй массив не пойму. Допустим "стаффер" прочел и уснул. А другой поток, получив вторую часть массива приклеит ее к первой, тогда стаффер должен проснутся и доделать работу после чего, он должен сообшить что патек готов и отправить его...

Основная проблемма - никак четко себе это не представлю.
Может очередь вх массивов и очередь выходных пакетов делать. Плюс надо наверно все это крит. секциями зашишать...

REA (02.02.06 11:57) [8]
CRC все же не помешает

CRC - это контрольная сумма?

Если да, то там сам покет состоит из двух частей грубо говоря служнебная инфо. данные. В обеих частях есть контро суммы...

← →
Verg © (2006-02-02 12:52) [10]

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

Вместо такого я бы применял три символа
STX - признак старта пакета
ETX - признак окончания пакета
ESC - для замены возможных STX, ETX и ESC в полезных данных

замена символа x в полезных данных ( where x in [stx, etx, esc] )
x -> ESC, 0x80|x

В таком варианте начало и конец пакета четко обозначены и нет неоднозначности при приеме etx: что это либо конец пакета, либо дубликат, замещающий etx в полезных данных.

← →
Defunct © (2006-02-02 12:56) [11]

Kolan © (02.02.06 12:37) [9]
Основная проблемма - никак четко себе это не представлю.
Может очередь вх массивов и очередь выходных пакетов делать. Плюс надо наверно все это крит. секциями зашишать...

Принимайте непрерывный поток данных в одном кодовом потоке c infinite тайм-аутом, в принятом кодовом потоке выделяйте пакеты про принципу fifo. При выполнении условия распознавания пакета (start-данные-stop-не стоп) - выдавайте пакет наверх у удаляйте этот пакет и весь принятый до него мусор из входного потока данных.

← →
Defunct © (2006-02-02 13:06) [12]

дополню 11.

Итого, организовываем кольцевой буфер объемом ~3*(Max_длина_пакета), непрерывно ведем прием и складываем все принятый байты в буфер. При обаружении условия старта пакета (2 символа - start-не start), запоминаем позицию старта. При обнаружении условия стопа (2 символа stop-не stop) копируем данные с позиции ранее обнаруженного старта по до позиции символа "не stop" в буфер принятого пакета и "вызываем" получателя.

Ну и обрабатываем коллизии - она здесь может быть только одна:
условие стопа без условия старта - ничего не далаем.

← →
Kolan © (2006-02-02 13:12) [13]

Verg © (02.02.06 12:52) [10]
Я покажу ветку разработчику железа...

( where x in [stx, etx, esc] ) x -> ESC, 0x80|x

По русски - если тек байт равен stx или etx или esc, то заменить его - тут не понял на что?...

Defunct © (02.02.06 12:56) [11]
Буду пробовать.

← →
Kolan © (2006-02-02 13:22) [14]

Defunct © (02.02.06 13:06) [12]
Благодарю. Вот еще вопрос: Есть допустим у меня буффер, вида:
[мусор, пакет]
Я отловил что есть пакет и передат его тому кто произведет разбор.
Теперь мне дано удалить мусор и сам покет?
Как это сделать. Может буфер должен быть дин структурой(Стек, список очередь). Или просто начинать записывать новые данные с начала(те как - бы перетирать старые)?

Тогда может выйти так:
[мусор, пакет, пакет2. Первый пакет выделил и отправил... Начинаю заполнять сначала, могу случайна потерять паке2.

А если дин массивы? Там как удалять?...

Пакеты довольно внушительные....

← →
Verg © (2006-02-02 13:27) [15]

const STX = 2; ETX = 3; EXC = $1b; procedure TransmitBuffer .... begin Transmit( STX ); for i:=0 to length(buffer)-1 do begin x := buffer[i]; if x in [ESC, STX, ETX] then begin Transmit( ESC ); Transmit( x or $80 ); end else Transmit( x ); end; Transmit( ETX ); end;

← →
TUser © (2006-02-02 13:28) [16]

> По русски - если тек байт равен stx или etx или esc, то
> заменить его - тут не понял на что?...

На ESC + некоторое обозначение заменяеморго символа, которое не совпадает с ESC и началом/концом пакета.

← →
Kolan © (2006-02-02 13:29) [17]

Verg © (02.02.06 13:27) [15]

Понятно. Благодарю.

← →
Defunct © (2006-02-02 13:34) [18]

> Kolan © (02.02.06 13:22) [14]
Теперь мне дано удалить мусор и сам пакет?

В [12] я написал полный алгоритм работы. Удаление будет производиться само собой поскольку буфер кольцевой. Анализируем на условие старта/стопа по мере поступления данных с COM-порта. Данные COM порта читаем по одному байту, если есть что читать (см. ClearCommError, ComStat, cbInQue)

← →
Kolan © (2006-02-02 14:10) [19]

буфер кольцевой
А что это?

Данные COM порта читаем по одному байту, если есть что читать (см. ClearCommError, ComStat, cbInQue)

Я убежден что прием передача байт и разделение пакета должны быть НЕ связаны. Поэтому что дали то и разбирай... Хоть байт хоть массив...

← →
Kolan © (2006-02-02 14:29) [20]

Вообщеи я оределился:
1. Есть объект, который вычитывает все что есть из порта. И если что-то пришло посылает сообщение...

2. Есть обьект, который будет выделать пакеты.

3. И есть объект который работает только с готовым пакетом...

Второй обект получив сообшение забирает данные у того кто читает...
Выделив пакет он посылает сообщение что паект готов. После того как пакет забрали он отчистит совй буффер и ждет постипления следующих уведомлений...

Ну как идея?

← →
Kolan © (2006-02-02 14:35) [21]

Verg © (02.02.06 13:27) [15]

Вот мнение разработчика железа:

Lex (02:20 PM) : Verg предлогает идею которую мы когдато "прошли" потому что: чем меньше разных флагов используется тем меньше избыточной информации в канале!!! Была идея с одним флагом (флаг начала он же флаг конца) но в этом случае страдает надежность!!!!!! Lex (02:20 PM) : и это по результатам реального (3-х летнего) использования протокола :-)

← →
Verg © (2006-02-02 14:41) [22]

1. и 2. объекты можно объединить и назвать канальным уровнем. Унифицировать его интерфейс базовым объектом с которым и будет взаимодействовать 3-й объект. От него будут наследовать объекты канального уровня конкретной физики (COM порт, UDP или еще чего-нибудь там ).

← →
Verg © (2006-02-02 14:52) [23]

> Kolan © (02.02.06 14:35) [21]

Это их мнение.

Избыточность в моем методе не больше, чем с дублированием спец-символов (сам посчитай, на один и тот же фрейм будет потрачено одинаковое количество избыточных байтов вне зависимости от метода). То, что спецсимволов несколько разных, на пропускную способность никак повлиять не может, а простоту фрейминга (а значит и надежность) повышает.

P.S. Про "трехлетность опыта" не понял. М.м. если это рассматривается как аргумент, то могу назвать число 12. Устроит? :))

← →
Kolan © (2006-02-02 14:59) [24]

Verg © (02.02.06 14:41) [22]
К сожалению незнаю как работать с интерфейсами... :(

← →
Lex_N (2006-02-02 15:02) [25]

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

Господа
Lex_N = разработчик аппаратной части...

:)

← →
Lex_N (2006-02-02 15:10) [27]

Теперь о избыточности: допустим все символы равновероятно появляются в канале: тогда кол-во дополнительно переданных симдолов будет прямо пропорционально кол-ву различных символов флаго (это справедливо для обоих алгоритмов), следовательно чем меньше различных символов флагов тем меньше избыточность.

← →
Lex_N (2006-02-02 15:19) [28]

вариант с 3 спец символами (if x in [ESC, STX, ETX]) и с двумя отличаются избыточностью ровно на треть.

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

← →
Lex_N (2006-02-02 15:21) [29]

> Kolan © (02.02.06 14:10) [19]
> буфер кольцевой
> А что это?
>
> Данные COM порта читаем по одному байту, если есть что читать
> (см. ClearCommError, ComStat, cbInQue)
>
> Я убежден что прием передача байт и разделение пакета должны
> быть НЕ связаны. Поэтому что дали то и разбирай... Хоть
> байт хоть массив...

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

Наибольшая эффективность достигается как раз если объединить прием и передачу байт и выделение пакета из входного потока. Если бы это был пакетный драйвер для работы с COM портом, то он именно так бы и был построен, поскольку входные данные принимались бы в обработчике прерывания.

> Lex_N

Вы же можете пакет закрывать контрольной суммой или CRC (последние 2 байта пакета). Тогда при обнаружении условия "стОпа", принимающая сторона просто пересчитывает контрольную сумму или CRC: совпадает - пакет принят, не совпадает - слушаем дальше.

← →
Lex_N (2006-02-03 11:20) [32]

> Defunct ©

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

Lex_N (03.02.06 11:20) [32]
> Речь шла только о выделении пакета из потока байт в канале, расчет КС и проверка правильности формата пакета - это задачи следующего уровня в стеке протоколов связи

Кто вам такое сказал?
Рекоменндую познакомиться с MAC (канальный уровень). Расчет КС совмещен с выделением пакета из входного потока.

Всех благодарю...
Defunct © (03.02.06 19:02) [30]
Получилось. :)

Вопрос еще такой.

Если есть массив(тот самый циклический быфер). И два потока одновременно будут работать с ним - один читать, другой писать, но гарантированно по разным индексам, нужно ли здесь использовать кр секции?

Kolan © (06.02.06 19:10) [34]

Конкретно по Вашему вопросу - да, обязательно нужно использовать кс.

а теперь, в обход Вашего вопроса, можете прислушаться, а можете пропустить.

Поток который пишет и отвечает за выделение пакета при обнаружении пакета тут же должен скопировать его в выходной буфер требуемого размера, например в динамический массив или просто в выделенную область памяти (GetMem). После чего этот же поток должен оповестить получателя (передать ему указатель на принятый пакет/размер пакета) и вернуться к приему. Т.о. получатель (другой поток) будет читать из гарантировано потокобезопастного места и не будет мешать заполнению циклического буфера.

Байт стаффинг. Алгоритм. Найти похожие ветки