Выбор уникального идентификатора в C для встроенного приложения

Я думаю, у вас есть несколько вариантов, но еще один, который следует рассмотреть, — это Bloom Filter. Это может привести к ложным срабатываниям (т.е. вы можете исключить идентификатор как уже использованный, даже если он не был), но это может позволить вам выбрать точное количество места, которое вы можете выделить для этих данных.

Если оперативной памяти недостаточно для реализации растрового изображения, достаточно большого для 64-килобайтных записей, количество сканирований во флэш-памяти для поиска неиспользуемого идентификатора можно уменьшить за счет использования меньшего временного растрового изображения для каждого сканирования. 16-байтовая битовая карта может записывать найденные идентификаторы в диапазоне 0-255 при первом проходе, 256-511 при втором сканировании и т. д. в конце каждого сканирования, если в растровом изображении есть хотя бы один непомеченный бит. снова сделано. Я считаю, что это будет хорошо работать в сочетании со случайным начальным диапазоном.

С другой стороны, если бы у меня была высокая уверенность в варианте 5, я бы просто выбрал его.

Я предполагаю, что устройство FLASH не является съемным из-за упоминания SPI, но SD-карты IIRC имеют режим доступа SPI, так что это может быть не так.

Если FLASH является постоянным и у вас есть надежное, энергонезависимое место для запоминания последнего выпущенного идентификатора, то, вероятно, это то, что нужно сделать. Это, безусловно, быстро и мало памяти во время выполнения. Это должно быть легко объяснить, реализовать и протестировать.

Если FLASH является съемным, то, вероятно, следует использовать генератор псевдослучайных чисел и проверку на коллизии. Предполагая, что ваши числа хорошо распределены, ваши шансы на столкновение легко предсказать, исходя из общего количества используемых. Просто выберите генератор с достаточно большим интервалом повторения. Может быть хорошей идеей смоделировать это в моделировании в качестве приемочного теста для выбранного алгоритма.

Мне интересно, почему вы просто не сохраняете последний идентификатор и не увеличиваете его. Есть ли причина, по которой вы колеблетесь? Вы не даете ни одного на свой вопрос, просто общее беспокойство.

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

[EDIT] Поскольку вас интересуют коллизии, должны быть некоторые данные, в которых может произойти коллизия, например, в именах файлов или что-то в этом роде. Если очевидный подход (создайте имя файла и проверьте, существует ли он) слишком медленный и у вас есть огромные пробелы в «карте распределения», сгенерируйте случайный идентификатор и проверьте его. Это должно позволить вам найти неиспользуемый идентификатор всего за несколько итераций.

Используйте Maximum Linear Feedback Shift Register и сохраните последнее значение, которое вы передали вне. LFSR, учитывая конкретную начальную точку (не включая ноль), даст вам все числа в последовательности 1..2^n в псевдослучайном порядке. Если вы начнете с k-го элемента, вы всегда получите один и тот же k+1-й элемент. Реализация крошечная:

if (IsEven(sequence)) {
    sequence /= 2;
}
else {
    sequence = (sequence / 2) ^ feedback;
}

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

С другой стороны, почему бы вам просто не подсчитать и не сохранить последнее выданное число?

Я выберу 2. Однако будьте осторожны при выборе генератора и семени. Все псевдочисловые последовательности повторяются после некоторого количества итераций. Поэтому вам нужно проверить свой, чтобы он не повторился слишком рано.

Я бы попробовал вариант 3. Вместо хранения отсортированного массива значений я бы сохранил отсортированный массив диапазонов.

Сколько у вас оперативной памяти? Трудно сказать, «встроенный» может значить так много в наши дни. :) Для растрового изображения потребуется 8192 байта на время генерации, и каждый раз гарантируется идеальный результат.

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

Сохраняйте текущий счетчик последовательным идентификатором.
Пропустите идентификатор через MD5.
Используйте младшие 16 бит.

Теоретически MD5 создает разные хэши для каждого входа. Самые младшие 16 бит должны быть такими же «случайными», как и весь хэш.

Если бы вы могли использовать более крупные идентификаторы, то 5 было бы несложно.

Интерес к вашему CRC-подобному алгоритму...

Похоже, вы ищете алгоритм, который будет проходить через случайный список менее 64 КБ 16-битных чисел и генерировать новое 16-битное число, которого еще нет в списке; предпочтительно делать это за один проход по заданному списку.

Если последовательность, в которой освобождаются идентификаторы, не имеет отношения к последовательности, в которой они распределяются (как я чувствую, это ваш случай), вы ничего не можете сделать с генерацией или распределением идентификаторов, чтобы получить свой алгоритм.

Лучшей ставкой тогда кажется 5 из вашего списка.

Если вы авантюрист...

и, если вы можете перенумеровать свои идентификаторы (то есть изменить выделенный идентификатор на другой нераспределенный идентификатор), вы можете время от времени запускать итерацию типа «дефрагментация», чтобы переместить все выделенные идентификаторы на более низкие значения и найти самый высокий свободный Идентификационный номер для следующего распределения. Было бы полезно запомнить общее количество выделений и освобождений, выполненных с момента последнего запуска такой «дефрагментации». Выделять последовательно, начиная с 0.

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

Другой вариант - сохранить файл с действительными идентификаторами на флэш-накопителе. Таким образом, вы не запрашиваете все возможности каждый раз. Если вам нужны случайные идентификаторы, рандомизируйте файл. Сохраните смещение к последнему как первое число в файле. Когда он вам понадобится, удалите последний из файла, а когда освободите, добавьте его обратно в файл. Со смещением и флэш-накопителем это должно быть почти постоянной операцией независимо от количества оставшихся идентификаторов. В качестве бонуса смещение в начале сообщит вам, сколько идентификаторов у вас осталось, если вам нужно знать это в любой момент. Недостатком будет то, что вам нужно получить доступ к флэш-памяти для каждого идентификатора (постоянное время, но все же доступ), и как обрабатывать случай ошибки, если файл отсутствует.