быстрый алгоритм, определения отсуствующего байта произвольного массива байтов размером Опции

[sergeeff]

При чисто двоичной передаче данных со всякими преамбулами вначале и crc в конце все отлично, до тех пор пока не имеет место выпадение байта из середины. Что может быть в практической жизни запросто. При этом может накрыться вся идеология разборки пакета.

[tag]

При чисто двоичной передаче данных со всякими преамбулами вначале и crc в конце все отлично, до тех пор пока не имеет место выпадение байта из середины. Что может быть в практической жизни запросто. При этом может накрыться вся идеология разборки пакета.

...для чего и придумали crc и приамбулу... и в целом протокол обмена

Используйте пакетную передачу данных.
Например
1. Преамбула.
2. Преамбула2.
3. Код команды (или назначение пакета..., опционально).
4. Размер данных.
5. КС. (опция)
6. Данные.
7. CRC16
8. Признак конца пакета.

Код

1    2    3    4    5    6    6    6    7    7    8
0x55 0xaa 0xXX 0x03 0x55 0xab 0xbc 0xcd crc0 crc1 0xfe

Это всего лишь пример. У меня в проектах используется чуть более сложная структура (зато более гибкая), но Вы можете выбрать поля как Вы считаете нужным. Размер каждого поля тоже.

Вот пример команды (вытянул из старого проекта) чтения системного времени устройства (МК шлет ответ ПК, в поле данных системное время, все hex):

55 AA 01 07 55 07 06 01 03 17 57 18 83 9A FE

...еще один вариант оформления пакета, здесь пример:

55h 0aah 86h 6h 18h 55h 55h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55h 5ah


55h 0aah - маркер начала, 55h 5ah - маркер конца, если внутри пакета встречается байт с кодом 55h то он дублируется, т.е. в случае когда весь пакет содержит 55h его реальная длина будет в два раза больше. В примере выше содержимое пакета будет 86h 6h 18h 55h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

[ANV]

При чисто двоичной передаче данных со всякими преамбулами вначале и crc в конце все отлично, до тех пор пока не имеет место выпадение байта из середины. Что может быть в практической жизни запросто. При этом может накрыться вся идеология разборки пакета.

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

...для чего и придумали crc и приамбулу... и в целом протокол обмена
...еще один вариант оформления пакета, здесь пример:

55h 0aah 86h 6h 18h 55h 55h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 55h 5ah
55h 0aah - маркер начала, 55h 5ah - маркер конца, если внутри пакета встречается байт с кодом 55h то он дублируется, т.е. в случае когда весь пакет содержит 55h его реальная длина будет в два раза больше. В примере выше содержимое пакета будет 86h 6h 18h 55h 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

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

В любом случае такой подход имеет право на жизнь, все ведь зависит от задачи. Не так ли?

[zltigo]

Какая идеология разборки пакета может накрыться???

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

Выпадение байта (равно как и его искажение при приеме) просто приведут к тому, что что-то не сойдется.

Ага, а после этого предстоит "просто" искать начало целого пакета в приходящем потоке, причем в обе стороны, при этом раздувая для этого буфера и тратя огромное по сравнению с нормальным режимом приема время. И/Или гарантировано терять несколько пакетов.
Это называется "кривизна" и обвешивание изначально ущебного механизма всякими "преамбула2" и вообще уже максимально бесполеным "концом пакета" ничего принципиально изменить не могут.
Если делать нормально работающие процедуры передачи по последовательным каналам, то только на механизмах бит/байт стаффинга.

[ANV]

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

Ага, а после этого предстоит "просто" искать начало целого пакета в приходящем потоке, причем в обе стороны, при этом раздувая для этого буфера и тратя огромное по сравнению с нормальным режимом приема время. И/Или гарантировано терять несколько пакетов.

Все это красиво конечно, но к сожалению бессмысленно, если уточнить, что такой протокол создан/используется для работы в режиме "запрос-ответ". Вас что-то не устраивает?

Вспомните вопрос автора, для чего "мы здесь все собрались".

Это называется "кривизна" и обвешивание изначально ущебного механизма всякими "преамбула2" и вообще уже максимально бесполеным "концом пакета" ничего принципиально изменить не могут.

Вы можете характеризовать что угодно и какими угодно словами, но, пожалуйста, добавляйте волшебное слово "ИМХО".

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

Если делать нормально работающие процедуры передачи по последовательным каналам, то только на механизмах бит/байт стаффинга.

И это все про COM порт? Или Вы отвечаете на какой-нибудь другой, абстрагированный от этой темы, вопрос типа - "Ребята! А как сделать это по самому правильному"? Вы пытаетесь помочь автору этого топика, т.к. проблема была/есть только у него? Вы знаете что конкретно ему нужно?
Тут тоже бы ИМХО добавить.

з.ы. Ничего личного.

[SasaVitebsk]

Практически всё упомянули. И похоже парня совсем подзапугали.

Для упрощения ситуации скажу следующее. Чем вероятнее возникновение ошибки, чем большие размеры передаются, чем длинее линия, чем выше скорость и выше требования к надёжности передачи - тем сложнее протокол.

Я делал двухсторонние эффективные протоколы с вероятностью битовой ошибки более 0,3%. Там было всё перечисленное только после метки начала - команды кодировались кодом хеминга. Но это же реально не всегда надо.

Но таймауты я применяю практически всегда.



А вот есть момент который не упомянули.
При высокой скорости передачи и при требовании высокой пропускной способности применяют следующее. Пакеты (типовые уже были расписаны) нумеруются псевдослучайным образом.
Зачем?
Дело в том, что при описанной структуре пакета, от принимающей стороны требуется подтверждение правильности приёма. Если передача - дуплексная, то, во-первых это дополнительно нагружает линию, а во вторых передающий канал простаивает в ожидании ответа.
Если нумеровать пакеты, то ответ передаётся только на битый пакет (с указанием его номера) и он повторяется.


Мне очень нравится эта область деятельности и при грамотном протоколе размер избыточности информации можно свести к единицам процентов. Даже при отсутствии сжатия. Да ещё скажу при самом крутом протоколе и в разности скоростей 115/32 (От компа/Линия) рост скорости от размера буфера затормаживается начиная с 1кб.

[zltigo]

добавляйте волшебное слово "ИМХО".

В данном случае не буду , ибо описанное есть объективная реальность.

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

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

И это все про COM порт?

Да, про COM за которым находится не только метровый кусок кабеля, но и оборудование передачи даных по произвольным каналам.

Вы знаете что конкретно ему нужно?

Нет, Но я знаю, что НЕ нужно - не нужна передача даных в паркетных условиях.

з.ы. Ничего личного.

Естественно!

Пакеты (типовые уже были расписаны) нумеруются псевдослучайным образом.
Зачем?

Зачем?
Псевдослучайность для данного применения хуже обычной последовательной нумерации переданных пакетов! Для непрягающего подтверждения хорошо годится введение номера последнего принятого пакета в заголовок с целью частичной замены отдельного пакета для подтверждения. Заодно вкупе с номером переданного получается приличный иденификатор конкретного пакета.
Для заметного увеличения пропускной способности канала при наличии подтверждений классически применяются 'sliding windows' (смотрите TCP). Применение протоколов только с Neganive Acknowledgment
черевато тем, что осутвующий намертво адресат не идентифицируется.

[ANV]

В данном случае не буду , ибо описанное есть объективная реальность.

Ага. Есть ИМХО описанное как объективная реальность.

Я говорю о бесполезности в предложенном Вами протоколе

И какую же бесполезность Вы увидели? (Впрочем, можете не отвечать.)
К тому же, был приведен пример структуры пакета, а именно свой протокол я никому не навязываю. Он особо и не был озвучен, ибо автор топика сам решит, что именно ему нужно под его задачу.

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

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

Да, про COM за которым находится не только метровый кусок кабеля, но и оборудование передачи даных по произвольным каналам.

Ну что ж. Проблема передачи даных по произвольным каналам есть проблема произвольного оборудования для осуществления онного, а не COM за которым находится не только метровый кусок кабеля. Или не так?

...не нужна передача даных в паркетных условиях.

Онную никто и не предлагает.

[zltigo]

И какую же бесполезность Вы увидели? (Впрочем, можете не отвечать.)

Может тогда про полезность расскажете? Ибо для меня отсутствие полезности это и есть бесполезность. Единственную полезность я более, чем подробно уже описал.

..ибо автор топика сам решит, что именно ему нужно под его задачу.
Непонятно зачем вот это все, в контексте разговора.

Помочь Автору вопроса не ломать голову над доморощенными протоколами.

Передаются данные в том количестве сколько их есть (пакет переменной длинны). Никаких потеряных информационных байтов заполнятся не будет...

Так и скажите - байтам ПРИКАЗАНО НЕ ТЕРЯТЬСЯ.

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

Понятно, а оборудованию ПРИКАЗАНО УМЕРЕТЬ, НО КАНАЛ ОБЕСПЕЧИТЬ.
Вот такие условия работы я и называю паркетными. Дальше Вам может казаться, что волшебными словами CRC, повтор Вы решите все проблемы, но это не так, поскольку заложенный в базис принцип формирования фрейма гниловат изначально и рюшечки (совершенно правильные сами по себе!) навешиваемые на него не смогут надежно отработать.

P.S.
Если Вы думаете, что я таким умным сразу родился, то Вы к сожалению ошибаетесь - я тоже пару десятков лет тому назад писал подобные протоколы и боролся с последствиями. Поумнел уже потом - набив шишки и изучив чужой опыт (HDLC, SLIP, UUE и прочее здесь поминавшееся).
Отдельное спасибо Dr.NoA за ссылку на статью.

[tag]

Какая идеология разборки пакета может накрыться???
Выпадение байта (равно как и его искажение при приеме) просто приведут к тому, что что-то не сойдется. Ведь, кроме CRC, может не сойтись межбайтная пауза (ее обрабатывать просто необходимо), сигнатура конца пакета и пр. Инициатор пакета не дождется ответа и просто его повторит. А если ошибок так много, что и в повторных пакетах есть ошибки, то скорее всего у Вас проблема с железом.
Дело в том, что мне кажется, что надежность такой структуры пакета чуть неоптимальна. Добавление своих символов в полезные данные (т.е. зависимость по данным) в некоторых случаях может создавать некоторую избыточность информации в пакете. ИМХО, лучше ее (и не только) направить на более полезные нужды, чем просто передача информации. К тому же, все равно необходимо контроллировать целостность данных (CRC), иногда требуется передать некоторую дополнительную информацию, например, о назначении пакета, некоторые метаданные и др.

В любом случае такой подход имеет право на жизнь, все ведь зависит от задачи. Не так ли?

...подразумевается что внутри пакета между маркером начала и маркером конца и есть доп. и полезная информация, в частности CRC. Что касается избыточности, то насколькоя помню это один из постулатов надежности передачи информации...

[sergeeff]

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

Нет желания послушать, понять и намотать на ус - так, вроде, никто никого силком на форум не загонял.

Лично меня такая тональность в общении удивляет и печалит.

[SasaVitebsk]

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

Но существует какая-то достаточность. Пусть автор сам оценит её исходя из тех наработок и общих принципов, которые здесь описали. Оценит и сделает выводы.



А спор, - совсем не лишний. И совершенно не обидный. Это мы его так воспринимаем. Я, например, узнаю некоторые свои подходы - которые отрабатывал и совершенствовал. Видите ли здесь лучше учесть опыт специалистов. Самому конечно можно, ничего сложного нет, но слишком много надо исследований провести, чтобы оценить эффективность работы разработанного вами протокола. А ИССЛЕДОВАНИЯ и РАЗРАБОТКА - это совершенно разные вещи. И занимают разное время! Надо это понимать. Поэтому лучше ещё раз перечитать написанное, попытаться осмыслить, возможно почитать литературу по данному вопросу, чтобы понять что к чему. (например про заполнение ) и принять решение. Например сейчас я применяю не самый навороченный протокол, но знаю его слабые стороны. То есть применяю его сознательно. Конечно zltigo несколько пыжит с высоты своих знаний. Чтож - имеет право. И лучше его внимательно послушать, даже если не планируешь всё применять. Он не только не злоупотребляет и не усложняет, а, скажем, немного не договаривает. В этом направлении можно идти дальше.