| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / 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;
Но обратный разбор работает только если потек пришел целый... И условие я соответствующие добавил.
Проблемма в том что пакет может разорваться. те состоять из нескольких частей. есть идей как это учесть?
Те надо как-то добавлять полученный массивы в анализируемый. Желательно обойтись без потоков... Но это не обезательно..
Verg (2006-02-02 13:27:00) [21]
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;
Kolan (2006-02-02 13:22:00) [22]Defunct © (02.02.06 13:06) [12]
Благодарю. Вот еще вопрос: Есть допустим у меня буффер, вида:
[мусор, пакет]
Я отловил что есть пакет и передат его тому кто произведет разбор.
Теперь мне дано удалить мусор и сам покет?
Как это сделать. Может буфер должен быть дин структурой(Стек, список очередь). Или просто начинать записывать новые данные с начала(те как - бы перетирать старые)?
Тогда может выйти так:
[мусор, пакет, пакет2. Первый пакет выделил и отправил... Начинаю заполнять сначала, могу случайна потерять паке2.
А если дин массивы? Там как удалять?...
Пакеты довольно внушительные....
Kolan (2006-02-02 13:12:00) [23]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]
Буду пробовать.
Defunct (2006-02-02 13:06:00) [24]дополню 11.
Итого, организовываем кольцевой буфер объемом ~3*(Max_длина_пакета), непрерывно ведем прием и складываем все принятый байты в буфер. При обаружении условия старта пакета (2 символа - start-не start), запоминаем позицию старта. При обнаружении условия стопа (2 символа stop-не stop) копируем данные с позиции ранее обнаруженного старта по до позиции символа "не stop" в буфер принятого пакета и "вызываем" получателя.
Ну и обрабатываем коллизии - она здесь может быть только одна:
условие стопа без условия старта - ничего не далаем.
Defunct (2006-02-02 12:56:00) [25]Kolan © (02.02.06 12:37) [9]
Основная проблемма - никак четко себе это не представлю.
Может очередь вх массивов и очередь выходных пакетов делать. Плюс надо наверно все это крит. секциями зашишать...
Принимайте непрерывный поток данных в одном кодовом потоке c infinite тайм-аутом, в принятом кодовом потоке выделяйте пакеты про принципу fifo. При выполнении условия распознавания пакета (start-данные-stop-не стоп) - выдавайте пакет наверх у удаляйте этот пакет и весь принятый до него мусор из входного потока данных.
Verg (2006-02-02 12:52:00) [26]Кроме того для избежания коллизий, когда нутри покета оказывается байт равный начальному или конечному, эти быйты удваиваются.
Вместо такого я бы применял три символа
STX - признак старта пакета
ETX - признак окончания пакета
ESC - для замены возможных STX, ETX и ESC в полезных данных
замена символа x в полезных данных ( where x in [stx, etx, esc] )
x -> ESC, 0x80|x
В таком варианте начало и конец пакета четко обозначены и нет неоднозначности при приеме etx: что это либо конец пакета, либо дубликат, замещающий etx в полезных данных.
Kolan (2006-02-02 12:37:00) [27]GanibalLector © (01.02.06 22:48) [5]
Нет. Этот протокол мне навязан разработчиком устройства.
Я вот с чем парюсь: Алгоритм позволяет выделить пакет даже если он разбит на множество частей.
Допустим этому "стафферу" пришел массив (пол пакета, допустим) если добавить соотв условие, то прочитав весь массив до конца, он должен будет уснуть...
Вот как добавить второй массив не пойму. Допустим "стаффер" прочел и уснул. А другой поток, получив вторую часть массива приклеит ее к первой, тогда стаффер должен проснутся и доделать работу после чего, он должен сообшить что патек готов и отправить его...
Основная проблемма - никак четко себе это не представлю.
Может очередь вх массивов и очередь выходных пакетов делать. Плюс надо наверно все это крит. секциями зашишать...
REA (02.02.06 11:57) [8]
CRC все же не помешает
CRC - это контрольная сумма?
Если да, то там сам покет состоит из двух частей грубо говоря служнебная инфо. данные. В обеих частях есть контро суммы...
REA (2006-02-02 11:57:00) [28]CRC все же не помешает
Defunct (2006-02-02 02:32:00) [29]Удалено модератором
Примечание: Дубль...
Defunct (2006-02-02 02:32:00) [30]Я вообще стараюсь такой протокол избегать.
либо кодировку применяю, чтобы четко были упр. символы START/CR (CRLF). Либо заголовок пакета, по аналогии с IP стеком.
Но в тех редких случаях когда все-таки приходилось иметь дело с таким монстриком да еще и без CRC - выделял пакет на ходу. Просто закрывал глаза на ошибки разбора (в виду дибильности протокола).
GanibalLector (2006-02-01 22:48:00) [31]2 Kolan
> в том что пакет может разорваться. те состоять из нескольких частей.
с СОМ'ом работаешь ;) По схеме tesseract'а.
Я делаю не так.Когда протокол подобный [0] я читаю все,до TimeOut(или даже до нескольких TimeOut).А только потом,смотрю начало\конец.Если в пакете есть и начало и конец и CRC вырный,то только тогда начинаю разбор пакета.
Kolan (2006-02-01 22:29:00) [32]Начинай разбор только после прихода целого пакета. т.е. жди пога до тебя дойдт все оставшиеся части...
Хорошая мысль. Она мне пришла. Вопрос как? Есть желание этот алгоритм не трогать, а написать еще один класс, который кокраз и будет отвечать за склеивание и выделение пакета.
Чуть помозгую и еще вопросы будут не могу понять как это технически делать...
Rouse_ (2006-02-01 14:33:00) [33]
> Проблемма в том что пакет может разорваться. те состоять
> из нескольких частей. есть идей как это учесть?
Начинай разбор только после прихода целого пакета. т.е. жди пога до тебя дойдт все оставшиеся части... А вообще проще писать размер пакета перед отправкой тогда не нужно задумываться о завершающем байте и удвоении. Просто получаешь размер и тянешь нужное тебе кол-во данных, потом опять смотришь размер и т.д.
Kolan (2006-02-01 13:50:00) [34]Протокол менять нельзя...
Ладно что-нить придумаю...
Evgeny V (2006-02-01 13:01:00) [35]Поищи в инете инфо о протоколе Sleep, там байты не просто удваиваются. Насколько помнится PPP тоже использует стартовый и и завершающий флаги, но точно не помню, давненько отошел от этого.
Если не изменяет память, то стартовый и завершающий байт - уникален -например всегда 0EFH (точно какие байты используются не помню, но выбраны довольно редко встречающиеся байты) заменяется на другой к примеру 0EDH (тоже написал примерно) в блоке данных. А вот уже при встрече этого байта в блоке происходит удвоение байтов. В этом случае ьы однозначно можешь определить начало и конец пакета даже при фрагментации, используя в добавок тайм-ауты ожидания полного приема пакета, так как начало и конец уникальны. И если за время тайм-аута пакет не завершен, то можно сбросить флаг начала пакета(а это уже логический флаг, который взводится при старте пакета и сбрасывается при окончании пакета или истечении тайм-аута). И это еще не все. На всякий случай в конец блока помещается его контрольная сумма, и блок считается принятым, если совпала еще и сумма. Примерно похожий алгоритм реализуется, но на уровне битов (подмена бит) в протоколе AX25 (пакетный радио протокол).
| |
Страницы: 