Страница 9 из 22
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 08:33:10
ARV
а я вот столкнулся с таким "необычным" кодом
Код: Выделить всё
mov R30, R31
clr R31
sbrc R30, 7
ser R31
ret
это подпрограммка, которая в регистровой паре Z (R31:R30) получает двухбайтное число... что она делает?
долго я ломал голову над смыслом этой подпрограммы... кто первым догадается, что происходит?
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 08:57:11
ПростоНуб
Сдвигает это знаковое 16-ти битное целое на 8 бит вправо.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 13:59:49
ARV
Ну никакой интриги...
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 16:54:22
ПростоНуб
[uquote="ARV",url="/forum/viewtopic.php?p=3581685#p3581685"]Ну никакой интриги...[/uquote]
Попробую тогда я. Что делает эта функция?
Код: Выделить всё
uint8_t myfunc(uint8_t v)
{
v^=v>>4;
return(0x6>>((v^(v>>2))&3)&1);
}
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 18:39:12
ARV
вообще говоря, это какая-то загадка, а не хитрый алгоритм... не знаю, так ли это, но похоже, она выдает сумму битов числа по модулю 2.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 19:03:25
Reflector
[uquote="ARV",url="/forum/viewtopic.php?p=3582052#p3582052"]похоже, она выдает сумму битов числа по модулю 2.[/uquote]
Проверка на четность.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 19:35:22
ПростоНуб
[uquote="Reflector",url="/forum/viewtopic.php?p=3582077#p3582077"]Проверка на четность.[/uquote]
Именно так. Многие CPU не умеют сами считать бит четности. Расчет четности в цикле требует заметно больше операций, чем обмен полубайтами, XOR, два сдвига, AND, XOR и снова AND.
Добавлено after 16 minutes 42 seconds:
Еще одна необычная функция. Полезна для CPU с конвеерной архитектурой, так как позволяет избежать команд условного перехода.
Код: Выделить всё
int myfunc(int x, int y)
{
return (x^((x^y)&-(x<y)));
}
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 19:50:17
Reflector
[uquote="ПростоНуб",url="/forum/viewtopic.php?p=3582083#p3582083"]Еще одна необычная функция. Полезна для CPU с конвеерной архитектурой, так как позволяет избежать команд условного перехода.[/uquote]
Проверил на STM32F0, max() работает где-то на треть быстрее, а на M3/M4 уже есть инструкция IT, тогда можно вообще без перехода обойтись.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Вс мар 03, 2019 19:59:06
ПростоНуб
Так от оптимизатора еще многое зависит. Если оптимизатор влепит уловный переход сам, выигрыша не будет.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 07:52:20
ARV
а где эта проверка на четность используется? не раз встречал в "теории" упоминание о ней, но на практике никогда не сталкивался...
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 08:10:48
OKF
Да мало ли. К примеру, у вас софтовый UART. Вот и простенькая защита.)
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 09:01:26
ПростоНуб
[uquote="ARV",url="/forum/viewtopic.php?p=3582306#p3582306"]а где эта проверка на четность используется? не раз встречал в "теории" упоминание о ней, но на практике никогда не сталкивался...[/uquote]
Проверка на четность используется в случаях, когда есть повышенные требования к надежности передачи данных или достоверности их хранения, а вычислительные ресурсы не позволяют воспользоваться БЧХ-кодами или даже кодом Хемминга.
Контрольные суммы позволяют надежно детектировать только одиночную ошибку (один бит) в блоке данных. Несмотря на то, что вероятность совпадения контрольной суммы при возникновении двух ошибок в блоке данных очень мала, она существует. Криптографические функции двойную ошибку детектируют всегда, но ценой весьма приличных затрат на вычисление криптографического хеша.
Четность же считается очень быстро, нередко аппаратным путем (например в UART), но при этом позволяет детектировать одиночные ошибки (бит четности на байт), исправлять одиночные (или детектировать тройные) и детектировать двойные ошибки (дополнительно байт перекрестной четности на блок данных) или даже исправлять двойные (или детектировать пятерные) и детектировать четверные (дополнительный байт перекрестной циклической четности на блок данных).
Байт перекрестной четности - это сумма по модулю 2 всех байтов блока плюс собственный 9-й бит четности.
Байт перекрестной циклической четности - это тоже сумма по модулю 2 всех байтов блока, но после каждого суммирования циклически сдвигаемая на один бит.
Впервые с этим подходом я столкнулся в начале 80-х на магнитных лентах ЕС ЭВМ (IBM-370).
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 09:33:57
ARV
меня интересовала конкретика: например, на каком-то там уровне TCP/IP, или там в каком-нибудь ModBus-е... т.е. кокнертные применения, с которыми я просто не имел дела в силу своего дремучего любительства. а все эти рассказы о том, где и как - это я еще из лекций ВУЗа помню.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 09:59:07
ПростоНуб
В старой технике контроль четности использовался сплошь и рядом (как в последовательных, так и в параллельных интерфейсах). В современной - вытесняется БЧХ-кодами.
UART, в качестве примера, Вам уже привели. SCSI и PCI, боюсь, Вам не слишком интересны.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 14:51:12
ARV
ПростоНуб писал(а):UART, в качестве примера, Вам уже привели
UART имеет такую возможность, но вопрос в том, где эта возможность используется? я ни разу не встречал устройств, работающих через RS-232, в которых бы использовалась опция "бита четности". хотя в настройках драйвера она присутствует, но на моеём веку ни разу не была установлена.
ПростоНуб писал(а):SCSI и PCI
в них на самом деле используется бит четности? аж не верится... но вообще таки да, страшно далеки они от народа
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 15:40:53
Reflector
[uquote="ARV",url="/forum/viewtopic.php?p=3582510#p3582510"]UART имеет такую возможность, но вопрос в том, где эта возможность используется?[/uquote]
PS/2 клава с мышкой, при чтении то все равно, но при записи они игнорят посылаемые команды если бит четности не совпадает.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 15:46:48
ARV
Reflector писал(а):PS/2 клава с мышкой
благодарю!
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пн мар 04, 2019 16:18:25
ПростоНуб
[uquote="ARV",url="/forum/viewtopic.php?p=3582510#p3582510"]страшно далеки они от народа
[/uquote]
Хотите ближе к народу, тогда могу назвать расширения на базе проверки на четность. Например LDPC (Low-density parity-check code), который используется в:
- 802.3an (10Gb Ethernet)
- ряд DVB стандартов (Digital video broadcasting)
- WiMAX
- 802.11n (WiFi)
Добавлено after 6 minutes 23 seconds:
[uquote="ARV",url="/forum/viewtopic.php?p=3582510#p3582510"]UART имеет такую возможность, но вопрос в том, где эта возможность используется?[/uquote]
Я наоборот, часто нарывался в местах, где допускается длина кабеля RS-232 свыше 3м (10ft). При этом до сих пор попадается 7E1, когда код передачи 7-битный.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пт мар 08, 2019 16:45:52
SIM31
[uquote="ARV",url="/forum/viewtopic.php?p=3582510#p3582510"]UART имеет такую возможность, но вопрос в том, где эта возможность используется? я ни разу не встречал устройств, работающих через RS-232, в которых бы использовалась опция "бита четности". хотя в настройках драйвера она присутствует, но на моеём веку ни разу не была установлена.[/uquote]
Некоторые ПЛК используют, причем там есть бит четности или нечетности, один раз встречал, просто поставил в настройках конвертора Ethernet-RS232 эту опцию и всё заработало ))
Смысла не было особого, так как там применялся Modbus с более "сильной" проверкой на ошибки.
И мне лично непонятно как эта защита себя проявит, например в Modbus я увижу ошибку в логе сервера. А ошибка низкого уровня как себя проявит, просто блокирует дальнейшую передачу? Это же личное дело конвертора и ПЛК, оба на удаленном объекте, на верхний уровень они не сообщат об ошибке.
Re: Хитрые, необычные алгоритмы и код
Добавлено: Пт мар 08, 2019 18:42:36
ПростоНуб
[uquote="SIM31",url="/forum/viewtopic.php?p=3585860#p3585860"]А ошибка низкого уровня как себя проявит, просто блокирует дальнейшую передачу?[/uquote]
Нет, конечно. Просто сообщит на верхний уровень о наличии ошибки.
А что может верхний уровень с этим делать я уже писал выше:
ПростоНуб писал(а):Четность же считается очень быстро, нередко аппаратным путем (например в UART), но при этом позволяет детектировать одиночные ошибки (бит четности на байт), исправлять одиночные (или детектировать тройные) и детектировать двойные ошибки (дополнительно байт перекрестной четности на блок данных) или даже исправлять двойные (или детектировать пятерные) и детектировать четверные (дополнительный байт перекрестной циклической четности на блок данных).
Добавлено after 1 hour 33 minutes 15 seconds:
Подкину еще хитрый алгоритм - CORDIC
https://ru.wikipedia.org/wiki/CORDIC . Кстати, его реализация STMicro достаточно удобная и применима почти на любом МК:
https://www.st.com/content/ccc/resource ... 441302.pdf