суббота, 29 ноября 2014 г.

Throttling


Троттлинг (throttling) - это регулирование (ограничение) скорости какого-нибудь процесса. Например, bandwidth throttling - регулирование пропускной способности канала (обычно измеряется в килобайтах в секунду, kB/s).

В листинге ниже показано, как можно реализовать троттлинг.

  1. for (int i = 0; i < 1000; i++)
  2. {
  3.     while (!throttle_acquire()); //цикл ожидания
  4.     doWork(); //выпоняем работу
  5. }

В этом примере процесс состоит из 1000 итераций. Каждая итерация заключается в вызове функции doWork(), которая, например, отправляет очередную порцию данных. Ограничение скорости заключается в введении лимита на количество этих вызовов N за период времени dT. Перед вызовом doWork() осуществляется проверка превышения лимита: функция throttle_acquire() возвращает false, если лимит превышен, и true, в противном случае.

Троттлинг можно реализовать с использованием кольцевого буфера. Этот кольцевой буфер заполняется моментами времени последних вызовов функции doWork() (см пример выше). Размер буфера равен максимально разрешенному количеству этих вызовов N за период времени dT. Если буфер полностью заполнен, то функция acquire() возвращает false. Это означает, что необходимо подождать, пока из буфера не будет удален хотя бы один момент времени, который располагается от текущего момента ("сейчас") дальше, чем dT.

Реализацию троттлинга на C++ (throttle.h)  я выложил на github: https://github.com/coolsoftware/Throttle.

Пример использования класса throttle можно посмотреть в TestThrottle.cpp.

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

четверг, 27 ноября 2014 г.

Сборка zlib в Visual Studio 2010


1. Скачиваем zlib 1.2.8 с http://www.zlib.net/
2. Распаковываем архив в c:\zlib-1.2.8
3. Открываем в Visual Studio 2010 проект C:\zlib-1.2.8\contrib\vstudio\vc10\zlibvc.sln
4. Меняем следующие настройки проекта zlibstat:

  Конфигурация Debug:

    General->Output Directory: ..\..\..\win32-MDd\
    General->Intermediate Directory: ..\..\..\win32-MDd\Tmp\
    C/C++->Preprocessor->Preprocessor Definitions: <удаляем ZLIB_WINAPI>
    C/C++->Code Generation->Runtime Library: Multi-threaded Debug DLL (/MDd)
    Librarian->General->Output File: $(OutDir)\..\zlibMDd.lib

  Конфигурация Release:

    General->Output Directory: ..\..\..\win32-MT\
    General->Intermediate Directory: ..\..\..\win32-MT\Tmp\
    C/C++->Preprocessor->Preprocessor Definitions: <удаляем ZLIB_WINAPI>
    C/C++->Code Generation->Runtime Library: Multi-threaded (/MT)
    Librarian->General->Output File: $(OutDir)\..\zlibMT.lib
   
5. Собираем Debug и Release версии zlibstat. На выходе получаем:

  C:\zlib-1.2.8\zlibMDd.lib
  C:\zlib-1.2.8\zlibMT.lib

6. Открываем в Visual Studio 2010 любой проект C++ и открываем Property Manager->(Project Name)->Debug | Win32->Microsoft.Cpp.Win32.user->Common Properties->VC++ Directories. Добавляем c:\zlib-1.2.8 в Include Directories, Library Direcories и Source Directories.


===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

четверг, 29 мая 2014 г.

Генерация пар открытых/закрытых ключей (RSA) на C#

Понадобилось мне создать пару открытый/закрытый ключ на C#. Я поискал немного и нашел замечательную криптографическую библиотеку под названием Bouncy Castle: https://www.bouncycastle.org/. Для C# исходники можно скачать здесь: http://www.bouncycastle.org/csharp/. Ниже описан порядок установки и использования.
  1. Качаем bccrypto-net-1.7-src.zip, распаковываем в какой-нибудь каталог на диске.
  2. Открываем проект csharp.sln в Visual Studio 2010.
  3. В свойствах проекта crypto в Build->General->Conditional compilation symbols комментируем INCLUDE_IDEA.


  4. Пробуем выполнить Build и видим ошибки:
    error CS1504: Source file 'C:\temp\csharp\crypto\src\crypto\engines\IDEAEngine.cs' could not be opened ('Неопознанная ошибка ')
    error CS1504: Source file 'C:\temp\csharp\crypto\test\src\crypto\test\IDEATest.cs' could not be opened ('Неопознанная ошибка ')
    error CS1504: Source file 'C:\temp\csharp\crypto\src\asn1\misc\IDEACBCPar.cs' could not be opened ('Неопознанная ошибка ')
  5. Удаляем из проекта crypto отсутствующие файлы:
    src\crypto\engines\IDEAEngine.cs
    src\asn1\misc\IDEACBCPar.cs
    test\src\crypto\test\IDEATest.cs
  6. Пробуем еще раз выполнить Build - на этот раз все должно получиться и будет создана библиотека crypto.dll.
  7. Прописываем созданную библиотеку в References проекта.


  8. Код для генерации пары открытый/закрытый ключ приведен ниже. Открытый ключ - в формате PKCS#8. Закрытый ключ - в формате PKCS#1.

    1. using Org.BouncyCastle.Asn1.Pkcs;
    2. using Org.BouncyCastle.Asn1.X509;
    3. using Org.BouncyCastle.Crypto;
    4. using Org.BouncyCastle.Crypto.Parameters;
    5. using Org.BouncyCastle.Pkcs;
    6. using Org.BouncyCastle.Security;
    7. using Org.BouncyCastle.X509;
    8. using Org.BouncyCastle.Crypto.Generators;
    9.  
    10. RsaKeyPairGenerator rsa = new RsaKeyPairGenerator();
    11. rsa.Init(new KeyGenerationParameters(new Org.BouncyCastle.Security.SecureRandom(), 1024));
    12. AsymmetricCipherKeyPair pair = rsa.GenerateKeyPair();
    13. PrivateKeyInfo privateKeyInfo = PrivateKeyInfoFactory.CreatePrivateKeyInfo(pair.Private);
    14. byte[] serializedPrivateBytes = privateKeyInfo.PrivateKey.ToAsn1Object().GetDerEncoded();
    15. string privateKey = Convert.ToBase64String(serializedPrivateBytes);
    16. SubjectPublicKeyInfo publicKeyInfo = SubjectPublicKeyInfoFactory.CreateSubjectPublicKeyInfo(pair.Public);
    17. byte[] serializedPublicBytes = publicKeyInfo.ToAsn1Object().GetDerEncoded();
    18. string publicKey = Convert.ToBase64String(serializedPublicBytes);

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

воскресенье, 20 апреля 2014 г.

Вызов скриптов Perl из программы на C++

Оказалось, что организовать вызов Perl-скриптов из C/C++ (MS Visual C++ 2010) достаточно просто:
  1. Прописываем в Include Directories и Library Directories проекта путь к Perl\CORE:


  2. Добавляем perl512.lib в Linker->Input->Additional Dependencies.


  3. Ниже приведен пример кода, вызывающего perl из консольного приложения C++. Обращу внимание на два момента: a) #pragma warning (disable:4005) для подавления сообщения компилятора "'ENOTSOCK' : macro redefinition"; b) если опустить вызов PERL_SYS_INIT(0, NULL), то на шаге perl_parse получим Access Violation.

    1. #include "stdafx.h"
    2. //avoid warning C4005: 'ENOTSOCK' : macro redefinition
    3. #ifdef _MSC_VER
    4. #pragma warning ( disable : 4005 )
    5. #endif
    6. #include <perl.h>
    7.  
    8. PerlInterpreter *my_perl;
    9.  
    10. int _tmain(int argc, _TCHAR* argv[])
    11. {
    12.     PERL_SYS_INIT(0, NULL);
    13.  
    14.     my_perl = perl_alloc();
    15.     perl_construct(my_perl);
    16.  
    17.     perl_parse(my_perl, NULL, argc, argv, NULL);
    18.     perl_run(my_perl);
    19.  
    20.     perl_destruct(my_perl);
    21.     perl_free(my_perl);
    22.  
    23.     return 0;
    24. }

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

пятница, 24 января 2014 г.

Дерево Интервалов (Отрезков)

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

Когда интервалов не много, то можно обойтись полным перебором (brute-force). Но когда их несколько десятков тысяч, а искать приходится часто, то нужна оптимизация.

Подходящая структура для быстрого поиска в списке интервалов называется "Дерево Интервалов" (Interval Tree) или "Дерево Отрезков". Хорошее описание (англ.), а также пример реализации я нашел тут: http://www.drdobbs.com/cpp/interval-trees/184401179.

Теория


Коротко описание структуры дерева отрезков и алгоритма поиска приведу на примере: пусть есть список именованных отрезков:

a=[75, 76], b=[75, 79], c=[75, 84],
d=[76, 80], e=[79, 80], f=[79, 83],
g=[79, 91], h=[80, 84], i=[80, 90],
j=[83, 84], k=[84, 85], l=[91, 92],
m=[91, 92]

Выпишем координаты вершин отрезков, отсортированные по-возрастанию:

X = {75, 76, 79, 80, 83, 84, 85, 90, 91, 92}

Массив X содержит 10 элементов: X[0], X[1], ..., X[9].
Возьмем среднее значение (медиану): 83 = X[m], m = (9-0) div 2.

Возможны три варианта расположения отрезков относительно медианы:
1. отрезки, которые содержат медиану.
2. отрезки, которые лежат слева от медианы.
3. отрезки, которые лежат справа от медианы.

Создадим узел дерева, который будет включать в себя значение медианы (дискриминант = 83) и список всех отрезков, которые содержат медиану:

R = {83, [c, f, g, h, i, j]}

Оставшиеся отрезки слева от R: {a, b, d, e} и справа от R: {k, l, m}.

Построим левый узел дерева для отрезков {a, b, d, e}, находящихся левее медианы, рассматривая вершины слева от медианы: {75, 76, 79, 80}. Получим: O = {76, [a, b, d]}.
Аналогично правый узел для отрезков {k, l, m} и вершин {84, 85, 90, 91, 92}: U = {90, []}. Обратите внимание на возможность существования узлов, не содержащих отрезков.
Продолжая процесс рекурсивно, получим следующие узлы:
N = {75, []}, P = {79, [e]}, S = {84, [k]}, V = {91, [l, m]}, Q = {80, []}, T = {85, []}, W = {92, []}.

      R
   /     \
  O       U
 / \     / \
N   P   S   V
     \   \   \
      Q   T   W

Висячие вершины N, Q, T и W можно убрать. Окончательно получим дерево:

     R
   /   \
  O     U
   \   / \
    P S   V

Алгоритм поиска выглядит следующим образом. Начинаем с вершины дерева. Сравниваем дискриминант текущего узла с искомым значением q. Если они равны (случай 1), то выводим все отрезки, на которые указывает текущий узел, и завершаем процесс. Если дискриминант текущего узла больше, чем q (случай 2), то перебираем все отрезки, на которые указывает текущий узел, и выводим такие, которые содержат q. Затем переходим к левому узлу. Если дискриминант текущего узла меньше, чем q (случай 3), то аналогично перебираем все отрезки текущего узла и выводим те, которые содержат q, а затем переходим к правому узлу.

В двух последних случаях (когда дискриминант узла не равен q) нужен перебор отрезков, на которые указывает узел. Этот перебор можно оптимизировать, если иметь два отсортированных массива отрезков: первый массив AL должен быть отсортирован по возрастанию левой (меньшей) координаты отрезка, а второй массив DH должен быть отсортирован по убыванию правой (большей) координаты отрезка. Для узла R из нашего примера:

AL = {c, f, g, h, i, j}
DH = {g, i, j, h, c, f}

Тогда, если дискриминант узла больше q (случай 2), то перебираем отрезки из массива AL до тех пор, пока левая координата отрезка  не будет больше q. Если дискриминант узла меньше q (случай 2), то перебираем отрезки из массива DH до тех пор, пока правая координата отрезка не будет меньше q.

Практика


Реализацию дерева интервалов можно взять на github: https://github.com/coolsoftware/ITree.
Класс itree в itree.h.

За основу я взял реализацию Yogi Dandass, в которую добавил некоторые недостающие (ommited) определения, исправил пару багов и существенно оптимизировал построение дерева (метод construct_tree).

Баг 1 в методе itree::construct_tree. Код ниже вызывал выход за границы массива.

  1. std::sort(&(al[list_start]),
  2.     &(al[list_start + list_size]), comp_for_al);
  3. std::sort(&(dh[list_start]),
  4.     &(dh[list_start + list_size]), comp_for_dh);

Он заменен на следующее:

  1. std::sort(al.begin()+list_start,
  2.   al.begin()+list_start+list_size,
  3.   comp_for_al);
  4. std::sort(dh.begin()+list_start,
  5.   dh.begin()+list_start+list_size,
  6.   comp_for_dh);

Баг 2 в методе query_iterator::init_node. Если value == cur_node->discrim, то требуется проверка, что cur_node->size != 0, а иначе возможен выход за границы массива.

  1. void init_node(void)
  2. {
  3.     index = 0;        
  4.     while (cur_node != NULL)
  5.     {
  6.         if (value < cur_node->discrim)
  7.         {
  8.             if ((cur_node->size != 0) &&
  9.                 ((*p_al)[cur_node->start]->low() <= value))
  10.                 return;
  11.             else
  12.                 cur_node = cur_node->left;
  13.         }
  14.         else if (value > cur_node->discrim)
  15.         {
  16.             if ((cur_node->size != 0) &&
  17.                 ((*p_dh)[cur_node->start]->high() >= value))
  18.                 return;
  19.             else
  20.                 cur_node = cur_node->right;
  21.         }
  22.         else //(value == cur_node->discrim)
  23.         {
  24.             if (cur_node->size == 0) //VIT 2014 bugfix!
  25.             {
  26.                 cur_node = NULL;
  27.             }
  28.             return;
  29.         }
  30.     }
  31. }

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru