Создать уникальное число из результата вычислений.

jenya77

есть число которое должно быть уникальным кодом

Код:

uint32_t code;

есть массив данных который я обрабатываю

Код:

uint32_t result;
for (int i = 0; i < BITS_COUNT; i++)
{
     result = captures[i] / WIDTH;  
     // code |= (1<<result);   ???
}

result может быть в пределах 0-4. и на основе result я хочу модифицировать code в каждой итерации.
я думал делать так

Код:

data |= (1<<result);

но если result все время 4 то на i = 8 мы вылетим за пределы uint32_t.
есть какие нибудь простые алгоритмы позволяющее создать уникальное число(ключ)?

arm999

32-битная хеш функция? CRC32 или FNV-1a.

_pv

aamonster

См. хэш-функции.
Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности.

Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий)

jenya77

arm999 писал(а):

32-битная хеш функция? CRC32 или FNV-1a.

а как я в CRC32 увяжу result?

jenya77

_pv писал(а):

LFSR

не знаю такое

jenya77

aamonster писал(а):

См. хэш-функции.
Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности.

Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий)

а почему *5? у меня максимум 20 итераций. и потом + не даст уникальности. 3 1 3 1 будет равен 1 3 1 3

arm999

jenya77 писал(а):

а как я в CRC32 увяжу result?

А в чем проблема? Или может я не правильно понимаю задачу? Если нужно на каждое уникальное значение result получить другой уникальный "код" то можно и просто за-ксорить (xor) result с каким-нибудь ключем. А если нужно учесть и предыдущие значения result то можно использовать хеш функцию, вот пример использования этой библиотеки:

Код:

#include "fnv.h"
...
...
// в первый раз:
code = fnv_32a_buf((const unsigned char *)&result, sizeof result, FNV1_32A_INIT);

// в последующие разы
code = fnv_32a_buf((const unsigned char *)&result, sizeof result, code);

jenya77

arm999 писал(а):

jenya77 писал(а):

а как я в CRC32 увяжу result?

А в чем проблема? Или может я не правильно понимаю задачу? Если нужно на каждое уникальное значение result получить другой уникальный "код" то можно и просто за-ксорить (xor) result с каким-нибудь ключем. А если нужно учесть и предыдущие значения result то можно использовать хеш функцию, вот пример использования этой библиотеки:

Код:

#include "fnv.h"
...
...
// в первый раз:
code = fnv_32a_buf((const unsigned char *)&result, sizeof result, FNV1_32A_INIT);

// в последующие разы
code = fnv_32a_buf((const unsigned char *)&result, sizeof result, code);

даже не знаю.спасибо.попробую.мне скорость исолнения тоже важна.

aamonster

jenya77 писал(а):

aamonster писал(а):

См. хэш-функции.
Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности.

Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий)

а почему *5? у меня максимум 20 итераций. и потом + не даст уникальности. 3 1 3 1 будет равен 1 3 1 3

Потому что у вас 5 разных значений. Вашу последовательность result'ов можно рассматривать, как число в 5-ричной системе (цифры от 0 до 4), просто переводим в число...
Для 20 итераций для гарантированной уникальности надо 47 бит, меньше - есть какая-то вероятность коллизий.
(А ещё благодаря тому, что 5 взаимно простое с 2 - пришедшие в число цифры при переполнении 32-битного числа не будут потеряны, а "размажутся" по всему числу).

1 3 1 3 ==> 1*5^3 + 3*5^2 + 1*5 + 3 = 208
3 1 3 1 ==> 3*5^3 + 1*5^2 + 3*5 + 1 = 416
Числа разные.

jenya77

aamonster писал(а):

jenya77 писал(а):

aamonster писал(а):

См. хэш-функции.
Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности.

Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий)

а почему *5? у меня максимум 20 итераций. и потом + не даст уникальности. 3 1 3 1 будет равен 1 3 1 3

Потому что у вас 5 разных значений. Вашу последовательность result'ов можно рассматривать, как число в 5-ричной системе (цифры от 0 до 4), просто переводим в число...
Для 20 итераций для гарантированной уникальности надо 47 бит, меньше - есть какая-то вероятность коллизий.
(А ещё благодаря тому, что 5 взаимно простое с 2 - пришедшие в число цифры при переполнении 32-битного числа не будут потеряны, а "размажутся" по всему числу).

1 3 1 3 ==> 1*5^3 + 3*5^2 + 1*5 + 3 = 208
3 1 3 1 ==> 3*5^3 + 1*5^2 + 3*5 + 1 = 416
Числа разные.

понял. спасибо.

dosikus_2

Я так понимаю лепиться шифрование прошивки ...

jenya77

dosikus_2 писал(а):

Я так понимаю лепиться шифрование прошивки ...

нет. расшифровка протокола RC5. таймер считает каждое падение фронта. полученные значения делю на ширину пульса и создаю уникальный код на основе результата. с учетом веса бита уникальность должна быть соблюдена по идее. по крайней мере на бумаге работает. достаточно что где то есть переход 0-1 или 1-0 и получается уникальный паттерн.

aamonster

Простите, не могу удержаться...

RC5 - это же манчестерское кодирование, которое расшифровывается просто, дёшево и без таких сложностей... И на выходе сразу 12-битное число, а не 20 интервалов от 0 до 4, которое ещё надо преобразовывать.

jenya77

aamonster писал(а):

Простите, не могу удержаться...

RC5 - это же манчестерское кодирование, которое расшифровывается просто, дёшево и без таких сложностей... И на выходе сразу 12-битное число, а не 20 интервалов от 0 до 4, которое ещё надо преобразовывать.

ну самый простой вариант считать на таймере интервалы. не заморачиваясь отслеживанием переходов 1-0 0-1. ну потом надо придать уникальность полученному результату.

dosikus_2

jenya77, а пробежаться поиском? НА стм32 здесь уже было аппаратное...

jenya77

dosikus_2 писал(а):

jenya77, а пробежаться поиском? НА стм32 здесь уже было аппаратное...

поиск меня не удовлетворил. у ST есть пример реализации декодирования RC5. но там такая простыня, я просто не понимаю как они умудрились сделать такого слона из RC5.

dosikus_2

Вот те раз ... А это http://ziblog.ru/2013/05/14/distantsion ... pulta.html
http://ziblog.ru/2011/07/31/rabotaem-s-ik-pultom.html

http://we.easyelectronics.ru/ZiB/rabota ... ultom.html

jenya77

dosikus_2 писал(а):

Вот те раз ... А это http://ziblog.ru/2013/05/14/distantsion ... pulta.html
http://ziblog.ru/2011/07/31/rabotaem-s-ik-pultom.html

о! спасибо! это интересное решение.

Easyelectronics.ru

Создать уникальное число из результата вычислений.

Кто сейчас на конференции