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

Совершенно непонятны условия задачи. Опишиде более подробно.

Массив отсортирован?

массив размером 255 произвольных значений.
одно значение - размер один байт!!
Не охота цыкл использовать!

Два или более одинаковых значений в массиве допускаются?

Хеш функция для поиска байта, это нечто из серии-
"Когда Чак Норрис идет сдавать кровь, он не признает шприцов, но просит дать ему пистолет и ведро. "

Значение одно или несколько?

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


Ну пишите тогда линейную программу(:-)

Товарищ это применил для передачи пакетов от ПЭВМ в МК.
А вот для обратной передачи пришлось отказаться крутить циклы в МК.
Для формирования пакетов 8-битных данных и передачи по RS232.
Назначаю какой-то байт разделителем пакетов, например 0x55.
Дальше необходимо присоеденить произвольный пакет размером <= 254 байт. Но в этом
пакете могут быть байты 0x55. Поэтому их необходимо заменить каким-то
другим байтом, которого в пакете точно нет. А раз размер пакета <= 254,
то такой символ точно существует, например 0xAA.
Результирующий пакет выглядит так:
0x55, 0xAA, а дальше весь исходный пакет с замененными значениями 0x55 на 0xAA.
При приеме находим первый байт 0x55, запоминаем очередной байт 0xAA и
дальше принимаем остальные данные заменяя встретившиеся байты равные
запомненому (Для этого пакета 0xAA) на 0x55. Накладные расходы
информативности канала на такую передачу не большие и можна нормально
использовать RS232 для передачи проиозвольных 8-битных данных.

Что думаете по этому поводу? Спасибо.

Во время подготовки пакета к отправке из МК один раз в цикле проходите пакет и устанавливаете в 256-битном массиве (32-байтном) еденичный бит, соответствующий текущему байту в пакете. Пройдя весь пакет у вас будут установлены биты присутствующих байт. Далее первый не 0xff байт в этом массиве будет указывать на значение, которого нет в пакете.

Че за венегрет? а если ав пакете данные равны 0xAA? буете их менять на 0x55..? Проще добавить несколько байт в стартовую комбинацию, и распознавать ее. а пакет еще и отксорить..

Можно же и 256 байт в пакете использовать. То есть 1 байт - синхронизация и 255 байт данных

Я думаю:
Гораздо проще продублировать управляющий символ 0x55 два раза как делается в случает с printf("i want to print backslash \\");

Дык и в пакете с данными он может два раза подряд идти. Что тогда?

А как различать пакеты по байту?

Дык я уже говорил комбинация байт.последовательность..хоть до 20 байт если нелень перелапачивать а ксореная контрольная сумма подтвердит правильно принятый пакет.

printf("i want to print 2 backslashes in a row \\\\");

А может лень. По этому алгоритму всего один байт теряется. Разве не лучше это?


И так до бесконечности...

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

Делать это в ПВЭМ и отправлять в МК можно, а вот крутить эти циклы в МК для обратной передачи пакетов может быть накладно.

А вот если-бы существовал не слишком сложный алгоритм: в начале сброс какого-то значения (байта/слова), а дальше добавляется очередной байт и тут-же получаем значение байта, которого еще небыло.

"Кривизна" протокола вносит ограничение на допустимые комбинации данных в пакете. То есть случайно попавшаяся 20-байтная (100-байтная) последовательность в пакете, совпадающая с синхронизацией введёт канал передачи в ступор.

2 sKWO
Измени структуру кадра передачи. Например, на такую
1. длина 2 байта
2. поле данных (0...65531 ) - присоединяемый твой пакет
3. CRC 2 байта

Выберите управляющий символ так, чтобы он не часто встречался в пакете.
Да и размер пакета все-таки ограничен.

Конечно есть мнение что Чак Норрис достчитал до бесконечности дважды!

Но применительно к байтстаффинг протоколу - в худшем случае (если все байты данных в пакете будут равны управляющему символу, размер пакета увеличится всего лишь вдвое). Делать "strip" тобишь отцеплять лишние данные можно прямо в обработчике прерывания УАРТа нехитрой проверкой



добавлять избыточность, аналогично просто:

посмотрите в сторону битстаффинга. Пример - сигнализация MTP CCITT 7. Номер рекомендации не помню но можно и по поиску найти.

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

Смотрите PPP http://www.faqs.org/rfcs/rfc1171.html - там этих подставновок вообще немеряно, не только ограничитель пакета подставляется, а ещё куча байтов. И ничего.


Я сам использую рамку SLIP http://www.faqs.org/rfcs/rfc1055.html - там подставляется два байта, ограничитель пакетов и тот, который используется как флаг подстановки. Работал лет 10 назад с каким-то радиомодемом, ему нужно было в этой рамке посылать пакеты, так и привык с тех пор :-)
Очень удобно в WIN32 байт-ограничитель пакета задать как EVENT CHARACTER и буфер запросить гарантированно больше максимального пакета - и не дёргаться по каждому байту, а ждать только этого события и выгребать потом весь пакет.


Кстати, вопрос к автору вопроса - а что будете делать, если вдруг все 256 байт будут разные, все байты есть во входном потоке? Возьмёте как флаговый произвольный? Ну так и делайте это сразу "без этих хлопот".


Всё хорошо, максимальная растяжка пакета в худшей ситуации на 12.5%, а не вдвое, как у байт-стаффинга, но бит-стаффинг настолько муторно делать ручками до/после аппаратного UART, ориентированного на передачу байтов...

ну пускай тогда символьно передает, или сделает фреймовую синхронизацию как в G703)

Полагаю, что для Вас в самый раз будет алгоритм byte stuffing'а Consistent Overhead Byte Stuffing. В этом алгоритме всегда добавляется только 1 байт при длине пакета не более 254 байт, еще плюс 1 байт - признак начала (или конца) пакета. Т.е. не нужно выделять память под буферы с большим запасом, расчитывая на наихудший случай. Реализация его тоже очень простая. Сам давно пользуюсь и доволен.
Ссылка на описание: http://www.stuartcheshire.org/papers/COBSforToN.pdf

Ценю чувство юмора!
А пока рассбираюсь с COBSforToN.pdf

Если я верно Вас понял, то может быть поможет WAKE протокол? Он на основе SLIP'a, довольно прост в реализации... Ссылка на описание WAKE протокола

а про контрольную сумму забыли? чтоб еще и она совпала.:-) это уже слишком.:-)

Да не забыл я про кс. Просто пакет со случайно оказавшейся в нем синхронизацией (хоть 20, хоть 100 байт) не сможет быть передан через канал как ни извращайся. КС позволит обнаружить то, что что-то передано неправильно и потребует повторить передачу этого пакета. Но и во второй раз передача накроется, и в третий. Содержимое же пакета нельзя заменить на другое. Оно как совпадало, так и будет совпадать с синхронизацией.

Согласен, никто так не делает.

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

6 - CRC пакета очень желательно.

Использую такой протокол для радио передачи - по вине протокола практически ничего не теряется и нет сбоев с определением начала/конца которые часто встречаются если использовать чистый байтстаффинг.

Народ давно уже придумал способы передачи двоичных данных таким образом, чтобы оставалась возможность использовать управляющие символы для старт/стопа. Например BASE64. Среднее увеличение пакета в 1,4 раза максимум. Сам алгоритм прост и быстр (наверное не медленнее сканирования пакета в поисках чего-то).

Используйте пакетную передачу данных.
Например


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


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

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

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

При чисто двоичной передаче данных со всякими преамбулами вначале и 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, может не сойтись межбайтная пауза (ее обрабатывать просто необходимо), сигнатура конца пакета и пр. Инициатор пакета не дождется ответа и просто его повторит. А если ошибок так много, что и в повторных пакетах есть ошибки, то скорее всего у Вас проблема с железом.



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

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

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

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

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

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




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

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


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

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

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

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

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

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



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


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

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

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

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

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

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




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

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



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



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



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



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

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

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

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

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

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

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

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

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

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

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

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



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