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

[sKWO]

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

Сообщение отредактировал sKWO - Jun 1 2007, 10:59

[sergeeff]

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

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

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

[zltigo]

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

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

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

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

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

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

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

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

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

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

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

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