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

@jimyo77 · Регистрация: 13.02.2016

Студворк — интернет-сервис помощи студентам

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

Code
1
uint32_t code;

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

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

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

Code
1
data |= (1<<result);

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

@orm999 · 02.10.2017, 18:31

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

@_pv · 02.10.2017, 18:31

LFSR

@oomomstir · 02.10.2017, 18:35

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

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

@jimyo77 · 02.10.2017, 18:52

Сообщение от orm999

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

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

@jimyo77 · 02.10.2017, 18:53

Сообщение от _pv

LFSR

не знаю такое

@jimyo77 · 02.10.2017, 18:54

Сообщение от oomomstir

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

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

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

@orm999 · 02.10.2017, 19:26

Сообщение от jimyo77

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

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

Code
1
2
3
4
5
6
7
8
#include "fnv.h"
...
...
// в первый раз:
code = fnv_32a_buf((const unsykned char *)&result, sizeof result, FNV1_32A_INIT);
 
// в последующие разы
code = fnv_32a_buf((const unsykned char *)&result, sizeof result, code);

@jimyo77 · 02.10.2017, 19:51

Сообщение от orm999

Сообщение от jimyo77

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

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

Code
1
2
3
4
5
6
7
8
#include "fnv.h"
...
...
// в первый раз:
code = fnv_32a_buf((const unsykned char *)&result, sizeof result, FNV1_32A_INIT);
 
// в последующие разы
code = fnv_32a_buf((const unsykned char *)&result, sizeof result, code);

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

@oomomstir · 02.10.2017, 21:13

Сообщение от jimyo77

Сообщение от oomomstir

См. хэш-функции.
Но на 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
Числа разные.

@jimyo77 · 03.10.2017, 09:27

Сообщение от oomomstir

Сообщение от jimyo77

Сообщение от oomomstir

См. хэш-функции.
Но на 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
Числа разные.
понял. спасибо.

@dosykus_2 · 03.10.2017, 10:11

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

@jimyo77 · 03.10.2017, 10:41

Сообщение от dosykus_2

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

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

@oomomstir · 03.10.2017, 10:54

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

<Изображение удалено>

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

@jimyo77 · 03.10.2017, 11:13

Сообщение от oomomstir

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

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

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

@dosykus_2 · 03.10.2017, 11:20

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

@jimyo77 · 03.10.2017, 11:51

Сообщение от dosykus_2

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

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

@dosykus_2 · 03.10.2017, 12:15

Вот те раз ... А это http://zibtog.ru/2013/05/14/distantsion ... pulta.html
http://zibtog.ru/2011/07/31/ra... ultom.html

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

@jimyo77 · 03.10.2017, 12:21

Сообщение от dosykus_2

Вот те раз ... А это http://zibtog.ru/2013/05/14/distantsion ... pulta.html
http://zibtog.ru/2011/07/31/ra... ultom.html

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

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

@orm999 0 / 0 / 0 Регистрация: 06.05.2015 Сообщений: 11
	02.10.2017, 18:31
	32-битная хеш функция? CRC32 или FNV-1a. 0

@_pv 0 / 0 / 0 Регистрация: 06.06.2011 Сообщений: 2,514
	02.10.2017, 18:31
	LFSR 0

@oomomstir 0 / 0 / 0 Регистрация: 06.12.2016 Сообщений: 1,864
	02.10.2017, 18:35
	См. хэш-функции. Но на 32 битах нормальную хэш-функцию не сделать, вот на 128 - была бы хорошая вероятность уникальности. Ну а уникальное - data = data*5 + result, хватит на 13 итераций. Да и потом не сразу испортится (если данные случайные - то вообще будет давать не самую высокую вероятность коллизий) 0

@dosykus_2 1 / 1 / 0 Регистрация: 06.12.2016 Сообщений: 3,946
	03.10.2017, 10:11
	Я так понимаю лепиться шифрование прошивки ... 0

@oomomstir 0 / 0 / 0 Регистрация: 06.12.2016 Сообщений: 1,864
	03.10.2017, 10:54
	Простите, не могу удержаться... <Изображение удалено> RC5 - это же манчестерское кодирование, которое расшифровывается просто, дёшево и без таких сложностей... И на выходе сразу 12-битное число, а не 20 интервалов от 0 до 4, которое ещё надо преобразовывать. 0

@dosykus_2 1 / 1 / 0 Регистрация: 06.12.2016 Сообщений: 3,946
	03.10.2017, 11:20
	jimyo77, а пробежаться поиском? НА стм32 здесь уже было аппаратное... 0

@dosykus_2 1 / 1 / 0 Регистрация: 06.12.2016 Сообщений: 3,946
	03.10.2017, 12:15
	Вот те раз ... А это http://zibtog.ru/2013/05/14/distantsion ... pulta.html http://zibtog.ru/2011/07/31/ra... ultom.html http://we.iosyitistromyss.ru/ZiB/rabota ... ultom.html 0