понедельник, 22 августа 2016 г.

[Delphi XE2] Indy Parse Cookie Bug

В Delphi XE2 отыскался баг в TIdCookie.ParseServerCookie. Смотрим код:


  function GetLastValueOf(const AName: String; var VValue: String): Boolean;
  var
    I: Integer;
  begin
    Result := False;
    for I := CookieProp.Count-1 downto 0 do
    begin
      if TextIsSame(CookieProp.Names[I], AName) then
      begin
        {$IFDEF HAS_TStrings_ValueFromIndex}
        VValue := CookieProp.ValueFromIndex[I];
        {$ELSE}
        VValue := Copy(CookieProp[I], Pos('=', CookieProp[I])+1, MaxInt); {Do not Localize}
        {$ENDIF}
        Result := True;
        Exit;
      end;
    end;
  end;

...

    if GetLastValueOf('MAX-AGE', S) then begin {Do not Localize}
      FPersistent := True;
      FExpires := StrToFloat(S);
    end
    else if GetLastValueOf('EXPIRES', S) then {Do not Localize}
    begin
      FPersistent := True;
      FExpires := StrToFloat(S);
    end else
    begin
      FPersistent := False;
      FExpires := EncodeDate(9999, 12, 31) + EncodeTime(23, 59, 59, 999);
    end;

    if GetLastValueOf('DOMAIN', S) then {Do not Localize}
    begin
             
      {
        If the user agent is configured to reject "public suffixes" and
        the domain-attribute is a public suffix:

           If the domain-attribute is identical to the canonicalized
           request-host:

              Let the domain-attribute be the empty string.

           Otherwise:

              Ignore the cookie entirely and abort these steps.

           NOTE: A "public suffix" is a domain that is controlled by a
           public registry, such as "com", "co.uk", and "pvt.k12.wy.us".
           This step is essential for preventing attacker.com from
           disrupting the integrity of example.com by setting a cookie
           with a Domain attribute of "com".  Unfortunately, the set of
           public suffixes (also known as "registry controlled domains")
           changes over time.  If feasible, user agents SHOULD use an
           up-to-date public suffix list, such as the one maintained by
           the Mozilla project at <http://publicsuffix.org/>.
      }
    end;

    if Length(S) > 0 then
    begin
      if not IsDomainMatch(AURI.Host, S) then begin
        Exit;
      end;
      FHostOnly := False;
      FDomain := S;
    end else
    begin
      FHostOnly := True;
      FDomain := CanonicalizeHostName(AURI.Host);
    end;

Ошибка происходит если строка S после вызова GetLastValueOf('EXPIRES', S) содержит что-нибудь (Length(S) > 0), а GetLastValueOf('DOMAIN', S) возвращает False.

Такое случается, если на вход TIdCookie.ParseServerCookie поступает строка ACookieText типа такой:

CookieName=CookieValue;Path=/;Expires=Wed, 20-Aug-2017 02:20:00 GMT;

Интересно, что ошибки бы не случилось, если бы параметр VValue у функции GetLastValueOf был объявлен как out, а не как var.

Fix. Для исправления этого бага я сделал класс TVCookieManager, который служит заменой для TIdCookieManager. Взять можно тут: https://github.com/coolsoftware/VCookieManager.
Использовать так:

var
  FixedCookieManager: TVCookieManager;
  IdHTTP: TIdHTTP;
  
  ...
  
  FixedCookieManager := TVCookieManager.Create;
  IdHTTP := TIdHTTP.Create;
  IdHTTP.CookieManager := FixedCookieManager;


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

среда, 27 июля 2016 г.

Base64 Encode/Decode Tool

Bae64 Tool - это утилита для кодирования и раскодирования данных в Base64 (https://ru.wikipedia.org/wiki/Base64).

Исходники доступны здесь: https://github.com/coolsoftware/Base64Tool




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

четверг, 7 июля 2016 г.

VPN через Amazon EC2

Отличная инструкция по настройке VPN через Amazon EC2: https://dxdt.ru/2012/08/06/5063/.

Два замечания:

1. Если отсутствует файл /etc/VPNCA/CA/index.txt, то может вылезти ошибка на шаге выпуска сертификата:

# openssl ca -config openssl.vpn.cnf -policy policy_anything -out certs/vpn-node.crt -infiles vpn-node.csr

Чтобы ее не было надо создать пустой index.txt:

# touch /etc/VPNCA/CA/index.txt

2. Нужно обратить внимание на следующую строчку в конфигурационном файле named.conf:

listen-on port 53 { localhost; };

Должно быть именно localhost, а не 127.0.0.1, иначе DNS в OpenVPN-соединении работать не будет.

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

среда, 23 марта 2016 г.

Построение дерева цифрового поиска

Ниже приведена иллюстрация построения дерева цифрового поиска на Python (см. алгоритм в посте http://blog.coolsoftware.ru/2016/03/blog-post.html):

f = open("f1.txt")
lines = f.read().split()
f.close()
 
def sort(array):
    equal = []
    greater = []
    less = []
    if len(array) <= 1:
        return array
    linem = array[int((len(array)-1)/2)]
    for line in array:
        if linem < line:
            greater.append(line)
        elif linem > line:
            less.append(line)
        elif linem == line:
            equal.append(line)
    return sort(less) + equal + sort(greater)
 
sorted_lines = sort(lines) 
print(sorted_lines)
 
def node(C, P):
    print(P + C)
    return P + " "
 
def R(P, K, I0, J0):
    I = I0
    Si = sorted_lines[I]
    Li = len(Si)
    if K >= Li and I == J0:
        return
    if K < Li:
        C = Si[K]
    else:
        C = "{0}"
    X = node(C, P)
    J = I
    while True:
        if J == J0 or sorted_lines[J+1][K] != C:
            R(X, K+1, I, J)
            if J == J0:
                break
            I = J + 1
            Si = sorted_lines[I]
            Li = len(Si)
            C = Si[K]
            X = node(C, P)
        J = J + 1
 
N = len(sorted_lines)
X = node("[ROOT_NODE]", "")
R(X, 0, 0, N-1)

f1.txt:

BC
ABBA
ABC
ABA
ABB
BAC
A

Вывод:

['A', 'ABA', 'ABB', 'ABBA', 'ABC', 'BAC', 'BC']
[ROOT_NODE]
 A
  {0}
  B
   A
   B
    {0}
    A
   C
 B
  A
   C
  C

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

среда, 16 марта 2016 г.

Поиск подстрок с помощью дерева цифрового поиска

Теория

Задача: имеется два больших (100 000+) списка строк, и требуется отфильтровать первый список (Source List) таким образом, чтобы в нем остались только строки, содержащие подстроки из второго списка (Search List).

Решать эту задачу будем следующим образом: для каждой строки Z из Source List будем искать строку S из Search List, такую, что S является подстрокой Z.

Примитивный алгоритм

Можно решить задачу нахождения подстроки из списка Search List при помощи следующего очевидного (примитивного), но крайне медленного алгоритма: будем последовательно перебирать все строки S из Search List до тех пор, пока не окажется, что S является подстрокой Z. При этом, алгоритм поиска подстроки в строке можно использовать либо примитивный, либо один из более продвинутых (например, Бойера-Мура, см. https://ru.wikipedia.org/wiki/Поиск_подстроки). Однако, использование более быстрого алгоритма поиска подстроки в строке не сильно ускоряет поиск подстроки из списка, т.к. все-равно требуется перебрать в среднем N/2 строк (здесь N - количество строк в Search List).

Дерево цифрового поиска

Дерево цифрового поиска (также бор, Trie, Префиксное дерево) - структура данных, которая используется для осуществления поразрядного поиска. Каждый узел дерева содержит значение одного "разряда" (в нашем случае - строковый символ). Вся строка представлена последовательностью узлов от корня до листа дерева. Пример - дерево цифрового поиска для строк A, ABA, ABB, ABBA, ABC, BAC, BC:

    [ROOT NODE]
    /         \
   A           B
  / \         / \
{0}  B       A   C
   / | \    /
  A  B  C  C
    / \
  {0}  A

Почитать про эту структуру можно, например, тут: https://en.wikipedia.org/wiki/Trie.

Алгоритм A1 поиска префикса строки S по дереву:

1. Пусть L = длина строки S.
2. Если L = 0 ("пустая" строка), то выход: префикс не найден.
3. Если дерево не содержит узлов ("пустое" дерево), то выход: префикс не найден.
4. Терминальный узел T = NULL.
5. Текущий узел P = корень дерева ( [ROOT NODE] ).
6. Цикл по K = 1..L:
7.   Если у текущего узла нет дочернего, соответствующего символу S[K], то выход из цикла.
8.   Текущий узел P = дочерний, узел, соответствующий символу S[K].
9.   Если у узла P есть дочерний узел с терминальным символом {0}, то присваиваем его T.
10. Конец цикла.
11. Если узел P - лист, то выход: префикс найден.
12. Если T не равно NULL, то выход: префикс найден.
13. Префикс не найден.

В качестве терминального символа {0} как правило используется символ NUL с ASCII-кодом 0, который не может встретиться в строке.

Алгоритм A2 поиска подстроки строки S по дереву.

1. Пусть L = длина строки S.
2. Если L = 0 ("пустая" строка), то выход: подстрока не найдена.
3. Если дерево не содержит узлов ("пустое" дерево), то выход: подстрока не найдена.
4. Цикл по K = 1..L:
5.  Пусть Sk - суффикс строки S, начиная с K-го символа (суффикс длины L-K+1).
6.  Используем алгоритм A1 для поиска префикса строки Sk по дереву; если префикс найден, то выход: подстрока найдена.
7. Конец цикла.
8. Подстрока не найдена.

В алгоритмах A1 и A2 использованы определения префикса и суффикса строки из статьи: https://ru.wikipedia.org/wiki/Подстрока. По-простому: префикс строки длины X - это первые X символов строки, суффикс строки длины Y - последние Y символов строки.

Построение дерева цифрового поиска

Обозначения:

N - количество строк.
Si - i-я строка, i = 1..N.
Li - длина i-ой строки.
[ROOT NODE] - корневой узел.

Построение дерева цифрового поиска:

1. Сортировка списка строк по возрастанию, удаление дубликатов.
2. Вызов рекурсивной процедуры R( [ROOT NODE], 1, 1, N).

Рекурсивная процедура R (параметры: P - узел-родитель, K - позиция текущего символа, I0, J0 - индексы строк; I0<=J0):

1. Индекс i = I0.
2. Если K > Li и i = J0, то выход из процедуры R.
3. Если K <= Li, то символ C = Si[K], иначе C = {0}.
4. Создать X = узел (C, P).
5. Индекс j = i.
6. Цикл:
7.      Если j = J0 или S(j+1)[K] не равно C, то:
8.        Вызвать R (X, K+1, i, j)
9.        Если j = J0, то выход из цикла.
10.      i = j+1.
10.      C = Si[K].
11.      Создать X = узел (C, P).
12.    Конец если.
13.    j = j + 1.
14. Конец цикла.

См. иллюстрацию на Python: http://blog.coolsoftware.ru/2016/03/blog-post_23.html.

Оптимизация (сжатие)

Под-деревья, узлы которых содержат не более одного потомка, можно объединить в один узел - см. узел (AC) в примере ниже.

    [ROOT NODE]
    /         \
   A           B
  / \         / \
{0}  B      (AC) C
   / | \
  A  B  C
    / \
  {0}  A

Эффективная реализация цифрового дерева поиска

Реализацию цифрового дерева поиска на Lazarus можно посмотреть тут: https://github.com/coolsoftware/LSearchStrings - класс TSearchTree в uSearchStrings.pas.

Вы можете сравнить скорость работы, выбирая метод поиска (Search Method): Search Tree - быстрый поиск с использованием дерева цифрового поиска, или Search List - медленный, "примитивный" поиск.

Проекты на Lazarus под Windows и Linux находятся в win и lnx соответственно.

Search Strings (написан на Delphi XE 2), который также использует TSearchTree, можно посмотреть тут: http://www.coolsoftware.ru/search-strings. См. также http://blog.coolsoftware.ru/2016/02/search-strings.html

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

вторник, 1 марта 2016 г.

Lazarus Exe

Чтобы уменьшить размер генерируемого Lazarus exe файла, нужно включить следующие опции в параметрах компилятора:


  1. "Компиляция и компоновка"->"Стиль модулей"->"Умная компоновка (-CX)"
  2. "Компиляция и компоновка"->"Компоновка"->"Умная компоновка (-XX)"
  3. "Отладка"->"Информация для GDB"->"Использовать внешний файл отладочных символов GDB (-Xg)"
  4. "Отладка"->"Прочая отладочная информация"->"Вырезать символы из исполнимого файла (-Xs)"






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

четверг, 18 февраля 2016 г.

ASUS N10 Nano vs TP-LINK TL-WN823N

Решил сравнить скорость двух беспроводных сетевых USB-адаптеров: ASUS N10 Nano и TP-LINK TL-WN823N. На первом написно до 150 Mbps, на втором - до 300 Mbps.

Оба адаптера втыкались в Raspberry Pi B+. Для тестов использовался iperf.

Результаты тестов представлены на Рис. 1,2. Как видим, ASUS показывает скорость около 42 Mbit/sec, TP-LINK - около 74 Mbit/sec.

Рис.1. ASUS N10 Nano.


Рис.2. TP-LINK TL-WN823N.




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