Хитрые, необычные алгоритмы и код

[ARV]

а я вот столкнулся с таким "необычным" кодом

Код: Выделить всё

                      mov     R30, R31
                      clr     R31
                      sbrc    R30, 7
                      ser     R31
                      ret

это подпрограммка, которая в регистровой паре Z (R31:R30) получает двухбайтное число... что она делает? долго я ломал голову над смыслом этой подпрограммы... кто первым догадается, что происходит?

[ПростоНуб]

Сдвигает это знаковое 16-ти битное целое на 8 бит вправо.

[ARV]

Ну никакой интриги...

[ПростоНуб]

[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);
}

[ARV]

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

[Reflector]

[uquote="ARV",url="/forum/viewtopic.php?p=3582052#p3582052"]похоже, она выдает сумму битов числа по модулю 2.[/uquote]
Проверка на четность.

[ПростоНуб]

[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)));
}

[Reflector]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=3582083#p3582083"]Еще одна необычная функция. Полезна для CPU с конвеерной архитектурой, так как позволяет избежать команд условного перехода.[/uquote]
Проверил на STM32F0, max() работает где-то на треть быстрее, а на M3/M4 уже есть инструкция IT, тогда можно вообще без перехода обойтись.

[ПростоНуб]

Так от оптимизатора еще многое зависит. Если оптимизатор влепит уловный переход сам, выигрыша не будет.

[ARV]

а где эта проверка на четность используется? не раз встречал в "теории" упоминание о ней, но на практике никогда не сталкивался...

[OKF]

Да мало ли. К примеру, у вас софтовый UART. Вот и простенькая защита.)

[ПростоНуб]

[uquote="ARV",url="/forum/viewtopic.php?p=3582306#p3582306"]а где эта проверка на четность используется? не раз встречал в "теории" упоминание о ней, но на практике никогда не сталкивался...[/uquote]
Проверка на четность используется в случаях, когда есть повышенные требования к надежности передачи данных или достоверности их хранения, а вычислительные ресурсы не позволяют воспользоваться БЧХ-кодами или даже кодом Хемминга.
Контрольные суммы позволяют надежно детектировать только одиночную ошибку (один бит) в блоке данных. Несмотря на то, что вероятность совпадения контрольной суммы при возникновении двух ошибок в блоке данных очень мала, она существует. Криптографические функции двойную ошибку детектируют всегда, но ценой весьма приличных затрат на вычисление криптографического хеша.
Четность же считается очень быстро, нередко аппаратным путем (например в UART), но при этом позволяет детектировать одиночные ошибки (бит четности на байт), исправлять одиночные (или детектировать тройные) и детектировать двойные ошибки (дополнительно байт перекрестной четности на блок данных) или даже исправлять двойные (или детектировать пятерные) и детектировать четверные (дополнительный байт перекрестной циклической четности на блок данных).

Байт перекрестной четности - это сумма по модулю 2 всех байтов блока плюс собственный 9-й бит четности.
Байт перекрестной циклической четности - это тоже сумма по модулю 2 всех байтов блока, но после каждого суммирования циклически сдвигаемая на один бит.

Впервые с этим подходом я столкнулся в начале 80-х на магнитных лентах ЕС ЭВМ (IBM-370).

[ARV]

меня интересовала конкретика: например, на каком-то там уровне TCP/IP, или там в каком-нибудь ModBus-е... т.е. кокнертные применения, с которыми я просто не имел дела в силу своего дремучего любительства. а все эти рассказы о том, где и как - это я еще из лекций ВУЗа помню.

[ПростоНуб]

В старой технике контроль четности использовался сплошь и рядом (как в последовательных, так и в параллельных интерфейсах). В современной - вытесняется БЧХ-кодами.
UART, в качестве примера, Вам уже привели. SCSI и PCI, боюсь, Вам не слишком интересны.

[ARV]

UART, в качестве примера, Вам уже привели

UART имеет такую возможность, но вопрос в том, где эта возможность используется? я ни разу не встречал устройств, работающих через RS-232, в которых бы использовалась опция "бита четности". хотя в настройках драйвера она присутствует, но на моеём веку ни разу не была установлена.

SCSI и PCI

в них на самом деле используется бит четности? аж не верится... но вообще таки да, страшно далеки они от народа

[Reflector]

[uquote="ARV",url="/forum/viewtopic.php?p=3582510#p3582510"]UART имеет такую возможность, но вопрос в том, где эта возможность используется?[/uquote]
PS/2 клава с мышкой, при чтении то все равно, но при записи они игнорят посылаемые команды если бит четности не совпадает.

[ARV]

PS/2 клава с мышкой

благодарю!

[ПростоНуб]

[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-битный.

[SIM31]

[uquote="ARV",url="/forum/viewtopic.php?p=3582510#p3582510"]UART имеет такую возможность, но вопрос в том, где эта возможность используется? я ни разу не встречал устройств, работающих через RS-232, в которых бы использовалась опция "бита четности". хотя в настройках драйвера она присутствует, но на моеём веку ни разу не была установлена.[/uquote]

Некоторые ПЛК используют, причем там есть бит четности или нечетности, один раз встречал, просто поставил в настройках конвертора Ethernet-RS232 эту опцию и всё заработало ))
Смысла не было особого, так как там применялся Modbus с более "сильной" проверкой на ошибки.
И мне лично непонятно как эта защита себя проявит, например в Modbus я увижу ошибку в логе сервера. А ошибка низкого уровня как себя проявит, просто блокирует дальнейшую передачу? Это же личное дело конвертора и ПЛК, оба на удаленном объекте, на верхний уровень они не сообщат об ошибке.

[ПростоНуб]

[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