Если ваш вопрос не влез ни в одну из вышеперечисленных тем, вам сюда.
Ответить

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

Вс мар 03, 2019 08:33:10

а я вот столкнулся с таким "необычным" кодом :)
Код:
                      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

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

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

Вс мар 03, 2019 16:54:22

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

Попробую тогда я. Что делает эта функция?
Код:
uint8_t myfunc(uint8_t v)
{
  v^=v>>4;
  return(0x6>>((v^(v>>2))&3)&1);
}

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

Вс мар 03, 2019 18:39:12

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

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

Вс мар 03, 2019 19:03:25

похоже, она выдает сумму битов числа по модулю 2.

Проверка на четность.

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

Вс мар 03, 2019 19:35:22

Проверка на четность.

Именно так. Многие 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

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

Проверил на STM32F0, max() работает где-то на треть быстрее, а на M3/M4 уже есть инструкция IT, тогда можно вообще без перехода обойтись.

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

Вс мар 03, 2019 19:59:06

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

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

Пн мар 04, 2019 07:52:20

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

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

Пн мар 04, 2019 08:10:48

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

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

Пн мар 04, 2019 09:01:26

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

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

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

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

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

Пн мар 04, 2019 09:33:57

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

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

Пн мар 04, 2019 09:59:07

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

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

Пн мар 04, 2019 14:51:12

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

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

Пн мар 04, 2019 15:40:53

UART имеет такую возможность, но вопрос в том, где эта возможность используется?

PS/2 клава с мышкой, при чтении то все равно, но при записи они игнорят посылаемые команды если бит четности не совпадает.

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

Пн мар 04, 2019 15:46:48

Reflector писал(а):PS/2 клава с мышкой
благодарю!

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

Пн мар 04, 2019 16:18:25

страшно далеки они от народа :)

Хотите ближе к народу, тогда могу назвать расширения на базе проверки на четность. Например LDPC (Low-density parity-check code), который используется в:
- 802.3an (10Gb Ethernet)
- ряд DVB стандартов (Digital video broadcasting)
- WiMAX
- 802.11n (WiFi)

Добавлено after 6 minutes 23 seconds:
UART имеет такую возможность, но вопрос в том, где эта возможность используется?

Я наоборот, часто нарывался в местах, где допускается длина кабеля RS-232 свыше 3м (10ft). При этом до сих пор попадается 7E1, когда код передачи 7-битный.

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

Пт мар 08, 2019 16:45:52

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


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

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

Пт мар 08, 2019 18:42:36

А ошибка низкого уровня как себя проявит, просто блокирует дальнейшую передачу?

Нет, конечно. Просто сообщит на верхний уровень о наличии ошибки.
А что может верхний уровень с этим делать я уже писал выше:
ПростоНуб писал(а):Четность же считается очень быстро, нередко аппаратным путем (например в 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
Ответить