| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Байт стаффинг. Алгоритм. [D7, WinXP]
Kolan © (2006-02-01 12:21:00)Здравствуйте,
Есть такая вещь - байтстаффинг. Смысл в том что посылка обрамляется начальным и конечным байтом. Кроме того для избежания коллизий, когда нутри покета оказывается байт равный начальному или конечному, эти быйты удваиваются. Ну и естественно обратная задача - избавится от повторений...
Вот как "зшифровать" понятно - конечный автома:
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;
Но обратный разбор работает только если потек пришел целый... И условие я соответствующие добавил.
Проблемма в том что пакет может разорваться. те состоять из нескольких частей. есть идей как это учесть?
Те надо как-то добавлять полученный массивы в анализируемый. Желательно обойтись без потоков... Но это не обезательно..
Defunct (2006-02-07 02:39:00) [1]Kolan © (06.02.06 19:10) [34]
Конкретно по Вашему вопросу - да, обязательно нужно использовать кс.
а теперь, в обход Вашего вопроса, можете прислушаться, а можете пропустить.
Поток который пишет и отвечает за выделение пакета при обнаружении пакета тут же должен скопировать его в выходной буфер требуемого размера, например в динамический массив или просто в выделенную область памяти (GetMem). После чего этот же поток должен оповестить получателя (передать ему указатель на принятый пакет/размер пакета) и вернуться к приему. Т.о. получатель (другой поток) будет читать из гарантировано потокобезопастного места и не будет мешать заполнению циклического буфера.
Kolan (2006-02-06 19:10:00) [2]Всех благодарю...
Defunct © (03.02.06 19:02) [30]
Получилось. :)
Вопрос еще такой.
Если есть массив(тот самый циклический быфер). И два потока одновременно будут работать с ним - один читать, другой писать, но гарантированно по разным индексам, нужно ли здесь использовать кр секции?
Defunct (2006-02-03 19:02:00) [3]Lex_N (03.02.06 11:20) [32]
> Речь шла только о выделении пакета из потока байт в канале, расчет КС и проверка правильности формата пакета - это задачи следующего уровня в стеке протоколов связи
Кто вам такое сказал?
Рекоменндую познакомиться с MAC (канальный уровень). Расчет КС совмещен с выделением пакета из входного потока.
Lex_N (2006-02-03 11:20:00) [4]> Defunct ©
Речь шла только о выделении пакета из потока байт в канале, расчет КС и проверка правильности формата пакета - это задачи следующего уровня в стеке протоколов связи (который работает уже с пакетами определенной длинны). В термин "востановление после сбоев" я вкладываю смысл: максимально надежное выделение пакетов из потока при ошибках в канале связи (ошибки могут пиходится как раз на спецсимволы) при этом могут появлятся рассогласования состояний конечных автоматов стафферов на приемной и передающей стороне. В результате принимается пакет в котором объеденены несколько пакетов или имеем пропус одного (нескольких) пакета.
Defunct (2006-02-03 00:32:00) [5]> Lex_N
Вы же можете пакет закрывать контрольной суммой или CRC (последние 2 байта пакета). Тогда при обнаружении условия "стОпа", принимающая сторона просто пересчитывает контрольную сумму или CRC: совпадает - пакет принят, не совпадает - слушаем дальше.
Defunct (2006-02-03 00:21:00) [6]
> Kolan © (02.02.06 14:10) [19]
> буфер кольцевой
> А что это?
>
> Данные COM порта читаем по одному байту, если есть что читать
> (см. ClearCommError, ComStat, cbInQue)
>
> Я убежден что прием передача байт и разделение пакета должны
> быть НЕ связаны. Поэтому что дали то и разбирай... Хоть
> байт хоть массив...
Кольцевой буфер (или циклический буфер) - это массив граничного размера, адресуемый одним или двумя индексами "на голову" и "на хвост". При приеме данные записываются по указателю "на хвост" при этом индекс увеличивает. При достижении индексом значения длины массива, индекс сбрасывается в 0, и данные пишутся опять в начало буфера.
Наибольшая эффективность достигается как раз если объединить прием и передачу байт и выделение пакета из входного потока. Если бы это был пакетный драйвер для работы с COM портом, то он именно так бы и был построен, поскольку входные данные принимались бы в обработчике прерывания.
Lex_N (2006-02-02 15:21:00) [7]с "Verg © (02.02.06 14:41) [22] " я полность согласен, первых два уровня разделять не целесообразно :)
Lex_N (2006-02-02 15:19:00) [8]вариант с 3 спец символами (if x in [ESC, STX, ETX]) и с двумя отличаются избыточностью ровно на треть.
Теперь о надежности: проводили тестирование в реальных условиях (канал с различным не нулевым BER и различным рапределением ошибок) для двух вариантов протокола: 1 или 2 спец символа. В результате протокол с 1 спец символом при единичных ошибках в канале иногда теряет поврежденный пакет и следующий за ним (на происходит востановление состояния конечного автомата), а вариант с 2-мя спецсимволами теряет всегда только один пакет (поврежденный). с груповыми ошибками ситуация чуть сложней но и вней первый протокол проигрывает.
Lex_N (2006-02-02 15:10:00) [9]Теперь о избыточности: допустим все символы равновероятно появляются в канале: тогда кол-во дополнительно переданных симдолов будет прямо пропорционально кол-ву различных символов флаго (это справедливо для обоих алгоритмов), следовательно чем меньше различных символов флагов тем меньше избыточность.
Kolan (2006-02-02 15:09:00) [10]Господа
Lex_N = разработчик аппаратной части...
:)
Lex_N (2006-02-02 15:02:00) [11]С избыточностью все просто.
Для начала опишу задачу: необходим метод выделения значащего пакета (сигнала или команды) из непрерывного (с точки зрения обработки, на самом деле могут встречатся паузы) потока символов, при этом протокол прозрачен для данных пользователя (содержимого сигнала), и обеспечен минимум избыточной информации в канале. Вопросы востановления при сбоях (ошибках в канале) тоже не последние.
Kolan (2006-02-02 14:59:00) [12]Verg © (02.02.06 14:41) [22]
К сожалению незнаю как работать с интерфейсами... :(
Verg (2006-02-02 14:52:00) [13]
> Kolan © (02.02.06 14:35) [21]
Это их мнение.
Избыточность в моем методе не больше, чем с дублированием спец-символов (сам посчитай, на один и тот же фрейм будет потрачено одинаковое количество избыточныхбайтов вне зависимости от метода). То, что спецсимволов несколько разных, на пропускную способность никак повлиять не может, а простоту фрейминга (а значит и надежность) повышает.
P.S. Про "трехлетность опыта" не понял. М.м. если это рассматривается как аргумент, то могу назвать число 12. Устроит? :))
Verg (2006-02-02 14:41:00) [14]1. и 2. объекты можно объединить и назвать канальным уровнем. Унифицировать его интерфейс базовым объектом с которым и будет взаимодействовать 3-й объект. От него будут наследовать объекты канального уровня конкретной физики (COM порт, UDP или еще чего-нибудь там ).
Kolan (2006-02-02 14:35:00) [15]Verg © (02.02.06 13:27) [15]
Вот мнение разработчика железа:
Lex (02:20 PM) :
Verg предлогает идею которую мы когдато "прошли" потому что: чем меньше разных флагов используется тем меньше избыточной информации в канале!!! Была идея с одним флагом (флаг начала он же флаг конца) но в этом случае страдает надежность!!!!!!
Lex (02:20 PM) :и это по результатам реального (3-х летнего) использования протокола :-)
Kolan (2006-02-02 14:29:00) [16]Вообщеи я оределился:
1. Есть объект, который вычитывает все что есть из порта. И если что-то пришло посылает сообщение...
2. Есть обьект, который будет выделать пакеты.
3. И есть объект который работает только с готовым пакетом...
Второй обект получив сообшение забирает данные у того кто читает...
Выделив пакет он посылает сообщение что паект готов. После того как пакет забрали он отчистит совй буффер и ждет постипления следующих уведомлений...
Ну как идея?
Kolan (2006-02-02 14:10:00) [17]буфер кольцевой
А что это?
Данные COM порта читаем по одному байту, если есть что читать (см. ClearCommError, ComStat, cbInQue)
Я убежден что прием передача байт и разделение пакета должны быть НЕ связаны. Поэтому что дали то и разбирай... Хоть байт хоть массив...
Defunct (2006-02-02 13:34:00) [18]
> Kolan © (02.02.06 13:22) [14]
Теперь мне дано удалить мусор и сам пакет?
В [12] я написал полный алгоритм работы. Удаление будет производиться само собой поскольку буфер кольцевой. Анализируем на условие старта/стопа по мере поступления данных с COM-порта. Данные COM порта читаем по одному байту, если есть что читать (см. ClearCommError, ComStat, cbInQue)
Kolan (2006-02-02 13:29:00) [19]Verg © (02.02.06 13:27) [15]
Понятно. Благодарю.
TUser (2006-02-02 13:28:00) [20]
> По русски - если тек байт равен stx или etx или esc, то
> заменить его - тут не понял на что?...
На ESC + некоторое обозначение заменяеморго символа, которое не совпадает с ESC и началом/концом пакета.
| |
Страницы: 