ардуино, rc522. Поиск UID ключа в огромной базе

delphist79
Offline
Зарегистрирован: 11.10.2018

База ключей на SD. Считать в память и проверять все новые ключи на соответствие

2000р

man9913
man9913 аватар
Offline
Зарегистрирован: 19.03.2016

совет: малина

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

если база огромная, то и процессор должен быть с огромными яйками, иначе состаришься во время поиска последнего ключа.   Про Малину - правильно говорят. 

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

DetSimen пишет:

если база огромная, то и процессор должен быть с огромными яйками, иначе состаришься во время поиска последнего ключа.   Про Малину - правильно говорят. 

что за база, сортирована ли, тока я знаю 6 алгоритмов поиска, что говорить о профессионалах...на I-286  в несортированной базе поиск шел минуты (правда сначала делал сортировку)

sadman41
Offline
Зарегистрирован: 19.10.2016

Дак дибэйз сразу индексы правил при аппенде вроде. Зачем там доп.сортировка?

delphist79
Offline
Зарегистрирован: 11.10.2018

критично энергопотребление, поэтому nano. если не потянет то teensy 3.2

sadman41
Offline
Зарегистрирован: 19.10.2016

Вы бы для начала объем базы озвучили и требуемую скорость реакции. Может и полчаса - не срок.

delphist79
Offline
Зарегистрирован: 11.10.2018

объем базы - 5 тысяч 4х байтных ключей (UIDы mifare classic)

требуемая скорость - пара секунд

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

У milfare uid = 8 байт

delphist79
Offline
Зарегистрирован: 11.10.2018
база лежит в файле на SD выглядит так:
0xC2, 0x31, 0x85, 0x58
0x31, 0x85, 0x58, 0xC2
0xC2, 0x31, 0x85, 0x58
0xC2, 0x33, 0x85, 0x58
0x31, 0x85, 0x56, 0xC2
0xC2, 0x37, 0x85, 0x58
...
 
Если ее оптимальней держать в другом виде - принимается
 
В моем понимании скетч загружает всю базу для быстроты работы в память.
RC522 считывает, получаем уид, сравниваем с базой (секунда другая) и выдаем есть такой ключ в базе или нет.
 
delphist79
Offline
Зарегистрирован: 11.10.2018

DetSimen пишет:

У milfare uid = 8 байт

прошу прощения, ошибся, вы правы

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

delphist79 пишет:

база лежит в файле на SD выглядит так:
0xC2, 0x31, 0x85, 0x58
0x31, 0x85, 0x58, 0xC2
0xC2, 0x31, 0x85, 0x58
0xC2, 0x33, 0x85, 0x58
0x31, 0x85, 0x56, 0xC2
0xC2, 0x37, 0x85, 0x58
...
 
Если ее оптимальней держать в другом виде - принимается
 
В моем понимании скетч загружает всю базу для быстроты работы в память.
RC522 считывает, получаем уид, сравниваем с базой (секунда другая) и выдаем есть такой ключ в базе или нет.
 

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

sadman41
Offline
Зарегистрирован: 19.10.2016

8*5000=40000 байт. Как вы это в нану планировали запихать? Хотя бы на уровне идеи...

delphist79
Offline
Зарегистрирован: 11.10.2018

На уровне идеи - я планировал заплатить тому, кто сталкивался

Но если ткнуть пальцем в небо, то наверно действительно бы разделил базу на много частей, рассортировав на файлы скажем по первым двум байтам УИДа и плата бы загружала уже небольшой кусок для анализа.

 

 

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

delphist79 пишет:

На уровне идеи - я планировал заплатить тому, кто сталкивался

Но если ткнуть пальцем в небо, то наверно действительно бы разделил базу на много частей, рассортировав на файлы скажем по первым двум байтам УИДа и плата бы загружала уже небольшой кусок для анализа.

Не надо на несколько частей - простенькая программка для компа для сортировки, и запись в файл. Дальнейший поиск тривиален: размер записи известен (8 байт). Читаем посередине, если прочитанный ключ больше, чем проверяемый - уходим в поиске влево, делим напополам там и т.д. Если меньше - уходим вправо, делим напополам там.

Вот: https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA

Делов - на полчаса, вместе с проверкой. Надо только отсортированный массив в файле.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

40 килобайт это всего  80 секторов по 512 байт, думаю, даже в несортированной базе поиск в 2 секунды уложится. 

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

В самом худшем случае будет 80 чтений с SD и 64х80 сравнений uint64_t

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

DetSimen пишет:

40 килобайт это всего  80 секторов по 512 байт, думаю, даже в несортированной базе поиск в 2 секунды уложится. 

Может, и справится, но линейный поиск - такое себе, с точки зрения эффективности... У линейного поиска - O(n), у бинарного - O(log(n)), емнип.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

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

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

на СТМ32 точно справится линейный поиск, с запасом, там полфайла сразу прокэшировать можно. ТС, не думал про СТМ?

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

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

delphist79
Offline
Зарегистрирован: 11.10.2018

из-за других причин я могу пользоваться только nano или teensy

Парни, ну вот даже среди вас, собаку на этом съевших и то были разные мнения.

Ну чо я буду шишки набивать. Просто сделайте, а я буду благодарен

delphist79
Offline
Зарегистрирован: 11.10.2018

DIYMan пишет:

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

 

ну я так и представлял примерно, ведь если сделать 255 файлов (тупо по первому байту УИДа) то искать в файле совсем немного останется 

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

delphist79 пишет:

Ну чо я буду шишки набивать. Просто сделайте, а я буду благодарен

Так тебе как сделать? Линейным поиском? Давай так: могу проверить на Uno, сгенерировав твои 4000 записей и впихнув их на SD. Напишу линейный поиск, посмотрим, что по быстродействию. Стучись в скайп porokhnya_dmitry, даже цену обсудим - возможно, оно и не будет стоить озвученную тобой ;)

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

delphist79 пишет:

DIYMan пишет:

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

 

ну я так и представлял примерно, ведь если сделать 255 файлов (тупо по первому байту УИДа) то искать в файле совсем немного останется 

По первому байту UID'а - не покатит, будет ОООЧЕНЬ неравномерное распределение, посмотри сам на базу ключей ;)

sadman41
Offline
Зарегистрирован: 19.10.2016

По последнему. И читать задом-наперед. Заодно и враг не догадается.

b707
Онлайн
Зарегистрирован: 26.05.2017

DIYMan пишет:

По первому байту UID'а - не покатит, будет ОООЧЕНЬ неравномерное распределение, посмотри сам на базу ключей ;)

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

Меня прикололо заявление ТС, что Нано нужна "по причинам энергопотребления" :) На фоне этих слов условие использовать только Нано или Тенси выглядит высосанным из пальца.

Я бы "голубую таблетку" СТМ32 взял - она и по размеру не сильно больше Нано. и по "энергопотреблению" :) Зато у нее 128К флеша и 20К оперативки, в ней можно работать с базой в несколько раз больше требований ТС

 

Или пусть ТС четко озвучит, почему именно Нано?(диплом? :)) - потому что я не вижу смысла трахаться стоя в гамаке, когда рядом удобная кровать :)

delphist79
Offline
Зарегистрирован: 11.10.2018

в свое время при выборе полагались на эту таблицу:

где нано на CH340 выглядит неплохо. Сейчас их просто партия имеется и в куче устройств уже установлены. Зачем лезть в кровать, когда и в гамаке всех устраивает?

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

sadman41 пишет:

Дак дибэйз сразу индексы правил при аппенде вроде. Зачем там доп.сортировка?


а при чем тут дибэйз, база самописанная на Инфо-Бухгалтере ))) (интерпретатор)

b707
Онлайн
Зарегистрирован: 26.05.2017

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

Во-вторых, если вопрос энергопотребления реально важен для проекта, то в готовом виде ардуины никто не использует. Немного доработав плату, потребление любой из ардуино можно понизить в тысячи раз (я не ошибся - именно в тысячи - от одной батарейки плата будет работать годами). Поэтому, на самом деле - эти данные абсолютно "ни о чем". То. что вы на них ориентируетесь - доказывает как раз то. что энергосбережения в вашем проекте нет вовсе :)

Ну а СТМ32 я предлагаю не просто так. Она реально занчительно лучше подходит под задачу.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

я ему про это еще в #19 удочку закидывал

b707
Онлайн
Зарегистрирован: 26.05.2017

DetSimen пишет:

я ему про это еще в #19 удочку закидывал

ну, ТС похоже заранее закупился кучей Нано, не подумав. что вообще использование отладочных плат в готовых проектах - само по себе бред. А теперь ему надо эти Наны использовать. иначе будет убыток :)

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

Короче: решили с ТС вопрос, тупой линейный поиск по базе из 4000 ключей - 300 миллисекунд в самом худшем случае на 328-й меге. Взял по рублю за миллисекунду :)

Генерация 4000 8-байтовых ключей с записью на SD - 600 миллисекунд, за это брать не стал :))))

sadman41
Offline
Зарегистрирован: 19.10.2016

ua6em пишет:

а при чем тут дибэйз, база самописанная на Инфо-Бухгалтере ))) (интерпретатор)

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

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

DIYMan пишет:

Короче: решили с ТС вопрос, тупой линейный поиск по базе из 4000 ключей - 300 миллисекунд в самом худшем случае на 328-й меге. Взял по рублю за миллисекунду :)

Вот.  Я, значить, не ошибса. 

b707
Онлайн
Зарегистрирован: 26.05.2017

DIYMan пишет:

300 миллисекунд в самом худшем случае на 328-й меге. Взял по рублю за миллисекунду :)

300 рублей? :)))

delphist79
Offline
Зарегистрирован: 11.10.2018

вы конечно философы тут, потроллить ТС каждый может) а человек за 10 минут сделал

DIYMan большое спасибо
DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

b707 пишет:

DIYMan пишет:

300 миллисекунд в самом худшем случае на 328-й меге. Взял по рублю за миллисекунду :)

300 рублей? :)))

Угу :) Поддержка в комплекте - бесценно :)))

man9913
man9913 аватар
Offline
Зарегистрирован: 19.03.2016

delphist79 пишет:

вы конечно философы тут, потроллить ТС каждый может) а человек за 10 минут сделал

DIYMan большое спасибо

Ты б бревно сначала вытащил бы, а потом уже философов благодарил.

b707
Онлайн
Зарегистрирован: 26.05.2017

delphist79 пишет:

вы конечно философы тут, потроллить ТС каждый может) а человек за 10 минут сделал

DIYMan большое спасибо

ну это уважуха однозначно - я бы 2 дня только собирался бы :)

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

b707 пишет:

delphist79 пишет:

вы конечно философы тут, потроллить ТС каждый может) а человек за 10 минут сделал

DIYMan большое спасибо

ну это уважуха однозначно - я бы 2 дня только собирался бы :)

Хорош троллить :)

strarbit
Offline
Зарегистрирован: 12.06.2016

извините, не имела заметить, решена)
господин DIYMan, извините

karamzin01
Offline
Зарегистрирован: 08.03.2018

р е а л и з у е м о - maslachenko767@mail.ru

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

sadman41 пишет:

ua6em пишет:

а при чем тут дибэйз, база самописанная на Инфо-Бухгалтере ))) (интерпретатор)

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


 

Это было очень давно, версия под ДОС  - 1.07 ))) под винды ничего не писал, на ней кстати сделал расчет таблиц цистерн с горючкой удоженных на бок с измерением мерной динейкой через 1 миллиметр )))

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

Надо бы название темы откорректировать: 5000 - это не огоромная база, огромная начинается от 4294967297. С учетом того, что SD сейчас до 256 Гб - вполне реальная задача.

delphist79
Offline
Зарегистрирован: 11.10.2018

  не получается исправить)

 

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

DIYMan пишет:

Короче: решили с ТС вопрос, тупой линейный поиск по базе из 4000 ключей - 300 миллисекунд в самом худшем случае на 328-й меге. Взял по рублю за миллисекунду :)

Генерация 4000 8-байтовых ключей с записью на SD - 600 миллисекунд, за это брать не стал :))))


Я так понимаю авторские права себе оставил )))
Ну так поделись кодом для нас, ПИОНЭРОВ...
Я думаю у ТС возражений быть не может

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

ua6em пишет:

DIYMan пишет:

Короче: решили с ТС вопрос, тупой линейный поиск по базе из 4000 ключей - 300 миллисекунд в самом худшем случае на 328-й меге. Взял по рублю за миллисекунду :)

Генерация 4000 8-байтовых ключей с записью на SD - 600 миллисекунд, за это брать не стал :))))


Я так понимаю авторские права себе оставил )))
Ну так поделись кодом для нас, ПИОНЭРОВ...
Я думаю у ТС возражений быть не может

Вот и спроси у ТС - разрешит - выложу.

delphist79
Offline
Зарегистрирован: 11.10.2018

если это кому то пригодится - я только "за"

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

delphist79 пишет:

если это кому то пригодится - я только "за"

Ок, чуть позже выложу - сейчас не за рабочим компом.

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

Собственно, вот весь код для генерации 4000 ключей и тупого поиска наихудшего варианта (т.е. перебором всей БД):

//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// настройки прошивки
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#define KEY_SIZE 8 // размер ключа, байт
#define KEY_FILE F("keys.db") // имя файла с ключами на карточке
#define SD_CS_PIN 10 // номер пина CS для SD-карты
#define SERIAL_SPEED 57600 // скорость работы с Serial
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#include <SD.h>
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
typedef uint8_t KEY[KEY_SIZE];
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
bool generate(uint16_t count) // генерируем ключи
{
  File workFile = SD.open(String(KEY_FILE).c_str(),FILE_WRITE | O_TRUNC);

  KEY record = {0};
  uint16_t val = 0;
  if(workFile)
  {
    for(uint16_t i=0;i<count;i++)
    {
      val++;
      memcpy(record,&val,min(sizeof(val),KEY_SIZE));
      workFile.write(record,sizeof(record));
    }

    workFile.close();
    return true;
  }
  return false;
}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
bool linearFind(KEY& needle) // линейный поиск
{
  bool result = false;
  File workFile = SD.open(String(KEY_FILE).c_str(),FILE_READ);

  if(workFile)
  {

    KEY record;
    while(workFile.available())
    {
      workFile.read(record,sizeof(record));
      
      if(!memcmp(needle,record,sizeof(needle)))
      {
        result = true;
        break; 
      }
    }
    workFile.close();
  }

  return result;
}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
void setup() 
{
  Serial.begin(SERIAL_SPEED);
  if(!SD.begin(SD_CS_PIN))
  {
    Serial.println(F("CAN'T INIT SD!"));
    while(true);
  }

  // генерируем ключи
  Serial.println(F("Generating 4000 keys..."));
  uint32_t start = millis();
  bool generated = generate(4000);
  uint32_t elapsed = millis() - start;
  Serial.print(F("Generate time, ms: "));
  Serial.println(elapsed);

  if(!generated)
  {
    Serial.println(F("ERROR GENERATING KEYS!"));
    while(true);
  }
  // конец генерации ключей


  // линейный поиск, существующий ключ
  KEY toFind = {0xA0,0x0F,0,0,0,0,0,0}; // 4000
  Serial.println(F("Find last PRESENT key..."));
  start = millis();
  bool found = linearFind(toFind);
  elapsed = millis() - start;
  if(found)
    Serial.print(F("FOUND"));
  else
    Serial.print(F("NOT FOUND"));
    
  Serial.print(F(", search time, ms: "));
  Serial.println(elapsed);
  // конец линейного поиска существующего ключа

  // линейный поиск, не существующий ключ
  KEY toFind2 = {0xA0,0x0F,0xFD,0xFF,0x12,0x34,0x7D,0xED};
  Serial.println(F("Find last NOT PRESENT key..."));
  start = millis();
  found = linearFind(toFind2);
  elapsed = millis() - start;
  if(found)
    Serial.print(F("FOUND"));
  else
    Serial.print(F("NOT FOUND"));
    
  Serial.print(F(", search time, ms: "));
  Serial.println(elapsed);
  // конец линейного поиска не существующего ключа
  

}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------
void loop() 
{

}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------