Толик Панков
hex_laden
............ .................. ................
November 2020
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30

Толик Панков [userpic]
SxGeoSharp. Интерфейс на C# для базы данных SypexGeo. - Часть II. Поиск.

Итак, наша основная задача вообще-то найти регион (страну, город) соответствующего IP-адреса. Вот этим и займемся. Точнее, найдем либо ID страны, либо смещение в файле БД, откуда потом вытащим данные. Этот функционал реализован в функции
private uint SearchID(string IP).


Трехбайтовые числа


К сожалению, мы с ними столкнемся еще не один раз, поэтому надо их как-то преобразовывать, хотя в C# вообще нет понятия "трехбайтовое число", все числовые данные кратны 2 (т.е. либо 2, либо 4 байта и т.д.). Соответственно, чтобы с ними работать, придется научиться их приводить к нормальным типам C#. В ushort они уже не влезают, так что будем их приводить к int или uint.

Плюс возникает еще одна проблема, числа могут быть в big-endian или little-endian, т.е. читаться с переду назад, или с заду наперед. В случае 2 байт или 4 - сразу понятно, надо просто перевернуть массив, если нужен другой порядок байт. А с трехбайтными как быть? Перевернуть, это понятно, но при конверсии из 3-байтного в 4-байтное остается лишний нуль, который должен занимать ячейку массива. И где этот нуль должен быть, с начала или конца массива? Как быть? Как разобраться?

Итак, представим себе десятичный байт, т.е. такой виртуальный байт, в который помещаются цифры от 0 до 9. И "трехбайтовое" число, например 149. Задача, преобразовать его в 4-байтовое в формате big-endian или little-endian.

В big-endian все просто, дописываем 0 спереди, поскольку 0 спереди незначащий, то он игнорируется.


А для little-endian необходима схемка:


Поэтому была сделана функция преобразования:

//делает uint из 3 байтов
//порядок входного массива BigEndian
private uint getUintFrom3b(byte[] bytes)
{
    byte[] buf = new byte[4];
    if (RevBO)
    {
        Array.Copy(bytes, 0, buf, 1, 3);
        Array.Reverse(buf);
    }
    else
    {
        Array.Copy(bytes, 0, buf, 0, 3);
    }
    return BitConverter.ToUInt32(buf, 0);
}

Байтовый substr


PHP весьма фривольно обращается с типами данных, т.е. может работать со строкой, как с массивом байт, с массивом байт, как со строкой или набором чисел, и т.д. C# так не может. Сходу возникла идея сконвертировать массивы в однобайтовые строки, но такой подход вызвал дикое замедление, поскольку строка считается неизменяемой и постоянно копируется. Поэтому просто сделали вариант функции string.substr() для массива байт:

private byte[] bSubstr(byte[] Source, uint StartIndex, uint Length)
{
    byte[] Dest = new byte[Length];
    Array.Copy(Source, StartIndex, Dest, 0, Length);
    return Dest;
}


Теперь переходим непосредственно к функции поиска, она будет получать в результате или ID страны (Для базы SxGeoCountry) или смещение в файле, по которому можно получить дополнительные данные: город, регион, страна (SxGeoCity). Я старался сделать эту функцию максимально приближенной к оригиналу на PHP, но из-за особенностей языков, естественно, пришлось пойти на некоторые отступления. Так что далее не всегда форк и копипаст, а скорее "вольный пересказ" с сохранением функциональности.

1. Преобразуем строковое представление IP-адреса, например 8.8.4.4 в беззнаковое целое число:

uint ipn = IPConverter.IPToUInt32(IP);

Про класс IPConverter я писал ранее.

2. Получаем первый байт IP-адреса, т.е. если IP 196.22.41.11, то надо получить 196. Как я ранее заметил, PHP фривольно обращается со строками, массивами байт или числами, интерпретируя данные без участия программиста. Это иногда хорошо, иногда нет, но в C# таких вольностей нет. Самый оптимальный способ - применить простое математическое преобразование - разделить целочисленное 4-байтовое представление IP-адреса нацело на 100000016:

//получаем 1-й байт IP-адреса
byte ip1n = (byte)(ipn / 0x1000000);


3. Делаем проверку (взята из оригинального исходника):

if (ip1n == 0 || ip1n == 10 || ip1n == 127 ||
    ip1n >= Header.fbIndexLen)
    return 0; 


Если первый байт 0, 10 или 127 (попадает в специальные диапазоны, отсутствующие в БД SxGeo) или больше индекса первых байт, значит в базе его нет - возвращаем 0.
4. Получаем 3 оставшихся байта IP-адреса:

//достаем 3 младших байта
uint ipn3b = (uint)(ipn - ip1n * 0x1000000);


5. Теперь ищем блок данных в индексе первых байт:

uint blocks_min = fb_idx_arr[ip1n - 1];
uint blocks_max = fb_idx_arr[ip1n];
uint min = 0; uint max = 0;


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

//если длина блока > кол-ва эл-тов в основном индексе
if (blocks_max - blocks_min > Header.Range)
{
	//рассмотрим далее
}
else
{
    min = blocks_min;
    max = blocks_max;
}


6. Обычно, такого хорошего совпадения не бывает, и приходится искать нужный блок данных в основном индексе.

6.1. Поиск в основном индексе. Он маленький, и был загружен в память еще на этапе инициализации БД:

uint part = SearchIdx(ipn,blocks_min / Header.Range,
    (blocks_max / Header.Range)-1); 


В оригинальном исходнике тут были округления при делении к ближайшему меньшему, но в C# целочисленное деление (которое автоматически работает, если целое делишь на целое) и так дает ближайшее целое в меньшую сторону - отбрасывает дробную часть.

6.2. Функция SearchIdx целиком и без изменений взята из оригинального исходника:

private uint SearchIdx(uint ipn, uint min, uint max)
{
    while (max - min > 8)
    {
        uint offset = (min + max) >> 1;
        if (ipn > m_idx_arr[offset])
            min = offset;
        else
            max = offset;
    }

    while (ipn > m_idx_arr[min] && min++ < max) { }
    
    return min;
}


6.3. Номер блока, в котором нужно искать IP нашли, теперь надо найти нужный блок в "Диапазонах":
min = part > 0 ? part * Header.Range : 0;
max = part > Header.mIndexLen ? Header.DiapCount : (part + 1) * Header.Range;


6.4. Нужно произвести коррекцию, если найденный ранее блок вылетел за пределы блока первого байта:

if (min < blocks_min) min = blocks_min;
if (max > blocks_max) max = blocks_max;


7. В результате мы получили 3 параметра:

- младшие 3 байта IP адреса (ipn3b)
- начало для поиска в "Диапазонах" (см.спецификацию п. 4), которое хранится в переменной min
- конец диапазона - max.

8. Вычисляем еще один параметр - длину зоны поиска в "Диапазонах". Он понадобится немного ниже:

uint len = max - min;

Все готово к получению индекса страны (либо смещения в справочнике).

Поиск ID или смещения в "Диапазонах IP"


Итак, все переменные для поиска в "Диапазонах" у нас есть. Но тут возникают проблемы, связанные с архитектурой нашего алгоритма. Помните, мы договорились, что можно будет устанавливать режим использования памяти.
В случае если режим полностью файловый (DatabaseMode == SxGeoMode.FileMode), то мы должны найти нужный кусок БД "Диапазонов" и загрузить его в память, чтобы найти уже в нем данные о конкретном IP. Иначе, БД диапазонов уже в памяти, и надо найти в ней.
В коде все наоборот - ориентируемся на режим "в памяти", а для другого режима пришлось изобретать подгрузку с диска:

//поиск в БД диапазонов
if (DatabaseMode != SxGeoMode.FileMode) //БД диапазонов в памяти
{
    ID = SearchDB(db_b, ipn3b, min, max);
}
else //БД диапазонов на диске
{
    byte[] db_part = LoadDBPart(min, len);
    ID = SearchDB(db_part, ipn3b, 0, len);
}


Функция подгрузки диапазонов с диска:
private byte[] LoadDBPart(uint min, uint len)
{
    //перемещаемся на начало диапазонов + 
    //найденное минимальное значение

    try
    {
        SxStream.Seek(Header.db_begin + min * Header.block_len,
            SeekOrigin.Begin);
    }
    catch (Exception ex)
    {
        ErrorMessage = ex.Message;
        return null;
    }

    return ReadBytes(SxStream, (int)(len * Header.block_len));
}


Функция поиска в "Диапазонах" (SearchDB)


Чтоб не загромождать текст, здесь

В принципе, функция практически полностью скопирована с оригинала на PHP, внесено только одно дополнительное условие. Если база данных SxGeoCity, то необходимо вернуть 3 байта смещения в справочнике городов/стран (преобразуем их в 4-байтный uint). Если БД SxGeoCountry - то нужно вернуть однобайтовый ID страны.

uint ans = 0;

if (Header.IdLen == 3) //БД с городами
{
    ans = getUintFrom3b(
    bSubstr(db, min * Header.block_len - Header.IdLen, Header.IdLen));
}
else //только ID стран
{
     ans = bSubstr(db, min * Header.block_len - Header.IdLen, Header.IdLen)[0];
}

 return ans; 


Все функции из этой части

Это репост с сайта http://tolik-punkoff.com
Оригинал: http://tolik-punkoff.com/2018/09/29/sxgeosharp-interfejs-na-c-dlya-bazy-dannyh-sypexgeo-chast-ii-poisk/