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

Если ваш вопрос не влез ни в одну из вышеперечисленных тем, вам сюда.
Аватара пользователя
ARV
Ум, честь и совесть. И скромность.
Сообщения: 18544
Зарегистрирован: Чт дек 28, 2006 08:19:56
Откуда: Новочеркасск
Контактная информация:

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

Сообщение ARV »

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

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

                      mov     R30, R31
                      clr     R31
                      sbrc    R30, 7
                      ser     R31
                      ret
это подпрограммка, которая в регистровой паре Z (R31:R30) получает двухбайтное число... что она делает? :))) долго я ломал голову над смыслом этой подпрограммы... кто первым догадается, что происходит?
если рассматривать человека снизу, покажется, что мозг у него глубоко в жопе
при взгляде на многих сверху ничего не меняется...

Мой уютный бложик... заходите!
Аватара пользователя
ПростоНуб
Собутыльник Кота
Сообщения: 2723
Зарегистрирован: Пт сен 07, 2018 20:20:02
Откуда: деревня в Тульской губернии

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

Сообщение ПростоНуб »

Сдвигает это знаковое 16-ти битное целое на 8 бит вправо.
Аватара пользователя
ARV
Ум, честь и совесть. И скромность.
Сообщения: 18544
Зарегистрирован: Чт дек 28, 2006 08:19:56
Откуда: Новочеркасск
Контактная информация:

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

Сообщение ARV »

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

Мой уютный бложик... заходите!
Аватара пользователя
ПростоНуб
Собутыльник Кота
Сообщения: 2723
Зарегистрирован: Пт сен 07, 2018 20:20:02
Откуда: деревня в Тульской губернии

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

Сообщение ПростоНуб »

[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
Ум, честь и совесть. И скромность.
Сообщения: 18544
Зарегистрирован: Чт дек 28, 2006 08:19:56
Откуда: Новочеркасск
Контактная информация:

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

Сообщение ARV »

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

Мой уютный бложик... заходите!
Reflector
Поставщик валерьянки для Кота
Сообщения: 2089
Зарегистрирован: Вс июн 19, 2016 09:32:03

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

Сообщение Reflector »

[uquote="ARV",url="/forum/viewtopic.php?p=3582052#p3582052"]похоже, она выдает сумму битов числа по модулю 2.[/uquote]
Проверка на четность.
Аватара пользователя
ПростоНуб
Собутыльник Кота
Сообщения: 2723
Зарегистрирован: Пт сен 07, 2018 20:20:02
Откуда: деревня в Тульской губернии

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

Сообщение ПростоНуб »

[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
Поставщик валерьянки для Кота
Сообщения: 2089
Зарегистрирован: Вс июн 19, 2016 09:32:03

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

Сообщение Reflector »

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

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

Сообщение ПростоНуб »

Так от оптимизатора еще многое зависит. Если оптимизатор влепит уловный переход сам, выигрыша не будет.
Аватара пользователя
ARV
Ум, честь и совесть. И скромность.
Сообщения: 18544
Зарегистрирован: Чт дек 28, 2006 08:19:56
Откуда: Новочеркасск
Контактная информация:

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

Сообщение ARV »

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

Мой уютный бложик... заходите!
OKF
Это не хвост, это антенна
Сообщения: 1385
Зарегистрирован: Вт июн 07, 2011 08:03:18

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

Сообщение OKF »

Да мало ли. К примеру, у вас софтовый UART. Вот и простенькая защита.)
Аватара пользователя
ПростоНуб
Собутыльник Кота
Сообщения: 2723
Зарегистрирован: Пт сен 07, 2018 20:20:02
Откуда: деревня в Тульской губернии

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

Сообщение ПростоНуб »

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

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

Впервые с этим подходом я столкнулся в начале 80-х на магнитных лентах ЕС ЭВМ (IBM-370).
Аватара пользователя
ARV
Ум, честь и совесть. И скромность.
Сообщения: 18544
Зарегистрирован: Чт дек 28, 2006 08:19:56
Откуда: Новочеркасск
Контактная информация:

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

Сообщение ARV »

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

Мой уютный бложик... заходите!
Аватара пользователя
ПростоНуб
Собутыльник Кота
Сообщения: 2723
Зарегистрирован: Пт сен 07, 2018 20:20:02
Откуда: деревня в Тульской губернии

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

Сообщение ПростоНуб »

В старой технике контроль четности использовался сплошь и рядом (как в последовательных, так и в параллельных интерфейсах). В современной - вытесняется БЧХ-кодами.
UART, в качестве примера, Вам уже привели. SCSI и PCI, боюсь, Вам не слишком интересны.
Аватара пользователя
ARV
Ум, честь и совесть. И скромность.
Сообщения: 18544
Зарегистрирован: Чт дек 28, 2006 08:19:56
Откуда: Новочеркасск
Контактная информация:

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

Сообщение ARV »

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

Мой уютный бложик... заходите!
Reflector
Поставщик валерьянки для Кота
Сообщения: 2089
Зарегистрирован: Вс июн 19, 2016 09:32:03

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

Сообщение Reflector »

[uquote="ARV",url="/forum/viewtopic.php?p=3582510#p3582510"]UART имеет такую возможность, но вопрос в том, где эта возможность используется?[/uquote]
PS/2 клава с мышкой, при чтении то все равно, но при записи они игнорят посылаемые команды если бит четности не совпадает.
Аватара пользователя
ARV
Ум, честь и совесть. И скромность.
Сообщения: 18544
Зарегистрирован: Чт дек 28, 2006 08:19:56
Откуда: Новочеркасск
Контактная информация:

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

Сообщение ARV »

Reflector писал(а):PS/2 клава с мышкой
благодарю!
если рассматривать человека снизу, покажется, что мозг у него глубоко в жопе
при взгляде на многих сверху ничего не меняется...

Мой уютный бложик... заходите!
Аватара пользователя
ПростоНуб
Собутыльник Кота
Сообщения: 2723
Зарегистрирован: Пт сен 07, 2018 20:20:02
Откуда: деревня в Тульской губернии

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

Сообщение ПростоНуб »

[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
Это не хвост, это антенна
Сообщения: 1363
Зарегистрирован: Чт апр 04, 2013 22:22:57
Откуда: Белгород, РФ

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

Сообщение SIM31 »

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

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

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

Сообщение ПростоНуб »

[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
Ответить

Вернуться в «Разные вопросы по МК»