[Delphi XE2] MD4/MD5 Bug on x64

В библиотеке Indy, которая поставляется с  Delphi XE2 под 64-битной платформой, имеется баг в вычислении MD4/MD5 (компоненты TIdHashMessageDigest4, TIdHashMessageDigest5 соответственно).

Вот код для вычисления MD5:

var
md5indy: TIdHashMessageDigest5;
sMD5: String;
begin
md5indy := TIdHashMessageDigest5.Create;
sMD5 := md5indy.HashStringAsHex('123456');
md5indy.Free;
end;

Под Win32 результат будет: ‘e10adc3949ba59abbe56e057f20f883e’ (правильно)
Под Win64 результат будет: ‘6e692400e5c684b74314252e341b92c7’ (ошибка)

Этот баг был исправлен в более поздних версиях версиях Indy/Delphi (не скажу точно, в какой именно, в Delphi 10.2 Tokyo его нет).

Баг в asm-функциях ROL и ROR в модуле IdGlobalProtocols. Вот как они выглядят в XE2:


// Arg1=EAX, Arg2=DL
function ROL(const AVal: LongWord; AShift: Byte): LongWord; assembler;
asm
mov cl, dl
rol eax, cl
end;
function ROR(const AVal: LongWord; AShift: Byte): LongWord; assembler;
asm
mov cl, dl
ror eax, cl
end;
{$ENDIF}

А вот так это выглядит в Delpgi 10.2 Tokyo:

// 32-bit: Arg1=EAX, Arg2=DL
// 64-bit: Arg1=ECX, Arg2=DL
function ROL(const AVal: UInt32; AShift: Byte): UInt32; assembler;
asm
{$IFDEF CPU64}
mov eax, ecx
{$ENDIF}
mov cl, dl
rol eax, cl
end;
function ROR(const AVal: UInt32; AShift: Byte): UInt32; assembler;
asm
{$IFDEF CPU64}
mov eax, ecx
{$ENDIF}
mov cl, dl
ror eax, cl
end;

Чтобы можно было генерировать MD4/MD5 в XE2 под Win64 без установки новой версии Indy, я сделал модуль IdHashMessageDigestEx с “исправленными” классами TIdHashMessageDigest4Ex и TIdHashMessageDigest5Ex, которыми следует пользоваться вместо TIdHashMessageDigest4 и TIdHashMessageDigest5 соответственно. Замечу, что в XE2 не работает макрос CPU64 (как в более поздних версиях Delphi), а работает CPUX64.

unit IdHashMessageDigestEx;
interface
uses
IdFIPS, IdHashMessageDigest;
type
{$IFDEF VER230} //XE2
TIdHashMessageDigest4Ex = class(TIdHashMessageDigest4)
protected
procedure MDCoder; override;
end;
TIdHashMessageDigest5Ex = class(TIdHashMessageDigest4Ex)
protected
procedure MDCoder; override;
function InitHash : TIdHashIntCtx; override;
public
class function IsIntfAvailable : Boolean; override;
end;
{$ELSE}
TIdHashMessageDigest4Ex = TIdHashMessageDigest4;
TIdHashMessageDigest5Ex = TIdHashMessageDigest5;
{$ENDIF}
implementation
{$IFDEF VER230} //XE2
{$IFDEF NO_NATIVE_ASM)} //XE2
uses IdGlobalProtocols;
{$ELSE}
// 32-bit: Arg1=EAX, Arg2=DL
// 64-bit: Arg1=ECX, Arg2=DL
function ROL(const AVal: LongWord; AShift: LongWord): LongWord; assembler;
asm
{$IFDEF CPUX64}
mov eax, ecx
{$ENDIF}
mov cl, dl
rol eax, cl
end;
{$ENDIF}
{ TIdHashMessageDigest4Ex }
{$Q-} // Arithmetic operations performed modulo $100000000
procedure TIdHashMessageDigest4Ex.MDCoder;
var
A, B, C, D, i : LongWord;
buff : T16x4LongWordRecord; // 64-byte buffer
begin
A := FState[0];
B := FState[1];
C := FState[2];
D := FState[3];
for i := 0 to 15 do
begin
buff[i] := FCBuffer[i*4+0] +
(FCBuffer[i*4+1] shl 8) +
(FCBuffer[i*4+2] shl 16) +
(FCBuffer[i*4+3] shl 24);
end;
// Round 1
{ Note:
(x and y) or ( (not x) and z)
is equivalent to
(((z xor y) and x) xor z)
-HHellstrцm }
for i := 0 to 3 do
begin
A := ROL((((D xor C) and B) xor D) + A + buff[i*4+0], 3);
D := ROL((((C xor B) and A) xor C) + D + buff[i*4+1], 7);
C := ROL((((B xor A) and D) xor B) + C + buff[i*4+2], 11);
B := ROL((((A xor D) and C) xor A) + B + buff[i*4+3], 19);
end;
// Round 2
{ Note:
(x and y) or (x and z) or (y and z)
is equivalent to
((x and y) or (z and (x or y)))
-HHellstrцm }
for i := 0 to 3 do
begin
A := ROL(((B and C) or (D and (B or C))) + A + buff[0*4+i] + $5A827999, 3);
D := ROL(((A and B) or (C and (A or B))) + D + buff[1*4+i] + $5A827999, 5);
C := ROL(((D and A) or (B and (D or A))) + C + buff[2*4+i] + $5A827999, 9);
B := ROL(((C and D) or (A and (C or D))) + B + buff[3*4+i] + $5A827999, 13);
end;
// Round 3
A := ROL((B xor C xor D) + A + buff[ 0] + $6ED9EBA1, 3);
D := ROL((A xor B xor C) + D + buff[ 8] + $6ED9EBA1, 9);
C := ROL((D xor A xor B) + C + buff[ 4] + $6ED9EBA1, 11);
B := ROL((C xor D xor A) + B + buff[12] + $6ED9EBA1, 15);
A := ROL((B xor C xor D) + A + buff[ 2] + $6ED9EBA1, 3);
D := ROL((A xor B xor C) + D + buff[10] + $6ED9EBA1, 9);
C := ROL((D xor A xor B) + C + buff[ 6] + $6ED9EBA1, 11);
B := ROL((C xor D xor A) + B + buff[14] + $6ED9EBA1, 15);
A := ROL((B xor C xor D) + A + buff[ 1] + $6ED9EBA1, 3);
D := ROL((A xor B xor C) + D + buff[ 9] + $6ED9EBA1, 9);
C := ROL((D xor A xor B) + C + buff[ 5] + $6ED9EBA1, 11);
B := ROL((C xor D xor A) + B + buff[13] + $6ED9EBA1, 15);
A := ROL((B xor C xor D) + A + buff[ 3] + $6ED9EBA1, 3);
D := ROL((A xor B xor C) + D + buff[11] + $6ED9EBA1, 9);
C := ROL((D xor A xor B) + C + buff[ 7] + $6ED9EBA1, 11);
B := ROL((C xor D xor A) + B + buff[15] + $6ED9EBA1, 15);
Inc(FState[0], A);
Inc(FState[1], B);
Inc(FState[2], C);
Inc(FState[3], D);
end;
{$Q+}
{ TIdHashMessageDigest5Ex }
const
MD5_SINE : array[1..64] of LongWord = (
{ Round 1. }
$d76aa478, $e8c7b756, $242070db, $c1bdceee, $f57c0faf, $4787c62a,
$a8304613, $fd469501, $698098d8, $8b44f7af, $ffff5bb1, $895cd7be,
$6b901122, $fd987193, $a679438e, $49b40821,
{ Round 2. }
$f61e2562, $c040b340, $265e5a51, $e9b6c7aa, $d62f105d, $02441453,
$d8a1e681, $e7d3fbc8, $21e1cde6, $c33707d6, $f4d50d87, $455a14ed,
$a9e3e905, $fcefa3f8, $676f02d9, $8d2a4c8a,
{ Round 3. }
$fffa3942, $8771f681, $6d9d6122, $fde5380c, $a4beea44, $4bdecfa9,
$f6bb4b60, $bebfbc70, $289b7ec6, $eaa127fa, $d4ef3085, $04881d05,
$d9d4d039, $e6db99e5, $1fa27cf8, $c4ac5665,
{ Round 4. }
$f4292244, $432aff97, $ab9423a7, $fc93a039, $655b59c3, $8f0ccc92,
$ffeff47d, $85845dd1, $6fa87e4f, $fe2ce6e0, $a3014314, $4e0811a1,
$f7537e82, $bd3af235, $2ad7d2bb, $eb86d391
);
{$Q-} // Arithmetic operations performed modulo $100000000
function TIdHashMessageDigest5Ex.InitHash: TIdHashIntCtx;
begin
Result := GetMD5HashInst;
end;
class function TIdHashMessageDigest5Ex.IsIntfAvailable: Boolean;
begin
Result := IsHashingIntfAvail and IsMD5HashIntfAvail ;
end;
procedure TIdHashMessageDigest5Ex.MDCoder;
var
A, B, C, D : LongWord;
i: Integer;
x : T16x4LongWordRecord; // 64-byte buffer
begin
A := FState[0];
B := FState[1];
C := FState[2];
D := FState[3];
for i := 0 to 15 do
begin
x[i] := FCBuffer[i*4+0] +
(FCBuffer[i*4+1] shl 8) +
(FCBuffer[i*4+2] shl 16) +
(FCBuffer[i*4+3] shl 24);
end;
{ Round 1 }
{ Note:
(x and y) or ( (not x) and z)
is equivalent to
(((z xor y) and x) xor z)
-HHellstrцm }
A := ROL(A + (((D xor C) and B) xor D) + x[ 0] + MD5_SINE[ 1], 7) + B;
D := ROL(D + (((C xor B) and A) xor C) + x[ 1] + MD5_SINE[ 2], 12) + A;
C := ROL(C + (((B xor A) and D) xor B) + x[ 2] + MD5_SINE[ 3], 17) + D;
B := ROL(B + (((A xor D) and C) xor A) + x[ 3] + MD5_SINE[ 4], 22) + C;
A := ROL(A + (((D xor C) and B) xor D) + x[ 4] + MD5_SINE[ 5], 7) + B;
D := ROL(D + (((C xor B) and A) xor C) + x[ 5] + MD5_SINE[ 6], 12) + A;
C := ROL(C + (((B xor A) and D) xor B) + x[ 6] + MD5_SINE[ 7], 17) + D;
B := ROL(B + (((A xor D) and C) xor A) + x[ 7] + MD5_SINE[ 8], 22) + C;
A := ROL(A + (((D xor C) and B) xor D) + x[ 8] + MD5_SINE[ 9], 7) + B;
D := ROL(D + (((C xor B) and A) xor C) + x[ 9] + MD5_SINE[10], 12) + A;
C := ROL(C + (((B xor A) and D) xor B) + x[10] + MD5_SINE[11], 17) + D;
B := ROL(B + (((A xor D) and C) xor A) + x[11] + MD5_SINE[12], 22) + C;
A := ROL(A + (((D xor C) and B) xor D) + x[12] + MD5_SINE[13], 7) + B;
D := ROL(D + (((C xor B) and A) xor C) + x[13] + MD5_SINE[14], 12) + A;
C := ROL(C + (((B xor A) and D) xor B) + x[14] + MD5_SINE[15], 17) + D;
B := ROL(B + (((A xor D) and C) xor A) + x[15] + MD5_SINE[16], 22) + C;
{ Round 2 }
{ Note:
(x and z) or (y and (not z) )
is equivalent to
(((y xor x) and z) xor y)
-HHellstrцm }
A := ROL(A + (C xor (D and (B xor C))) + x[ 1] + MD5_SINE[17], 5) + B;
D := ROL(D + (B xor (C and (A xor B))) + x[ 6] + MD5_SINE[18], 9) + A;
C := ROL(C + (A xor (B and (D xor A))) + x[11] + MD5_SINE[19], 14) + D;
B := ROL(B + (D xor (A and (C xor D))) + x[ 0] + MD5_SINE[20], 20) + C;
A := ROL(A + (C xor (D and (B xor C))) + x[ 5] + MD5_SINE[21], 5) + B;
D := ROL(D + (B xor (C and (A xor B))) + x[10] + MD5_SINE[22], 9) + A;
C := ROL(C + (A xor (B and (D xor A))) + x[15] + MD5_SINE[23], 14) + D;
B := ROL(B + (D xor (A and (C xor D))) + x[ 4] + MD5_SINE[24], 20) + C;
A := ROL(A + (C xor (D and (B xor C))) + x[ 9] + MD5_SINE[25], 5) + B;
D := ROL(D + (B xor (C and (A xor B))) + x[14] + MD5_SINE[26], 9) + A;
C := ROL(C + (A xor (B and (D xor A))) + x[ 3] + MD5_SINE[27], 14) + D;
B := ROL(B + (D xor (A and (C xor D))) + x[ 8] + MD5_SINE[28], 20) + C;
A := ROL(A + (C xor (D and (B xor C))) + x[13] + MD5_SINE[29], 5) + B;
D := ROL(D + (B xor (C and (A xor B))) + x[ 2] + MD5_SINE[30], 9) + A;
C := ROL(C + (A xor (B and (D xor A))) + x[ 7] + MD5_SINE[31], 14) + D;
B := ROL(B + (D xor (A and (C xor D))) + x[12] + MD5_SINE[32], 20) + C;
{ Round 3. }
A := ROL(A + (B xor C xor D) + x[ 5] + MD5_SINE[33], 4) + B;
D := ROL(D + (A xor B xor C) + x[ 8] + MD5_SINE[34], 11) + A;
C := ROL(C + (D xor A xor B) + x[11] + MD5_SINE[35], 16) + D;
B := ROL(B + (C xor D xor A) + x[14] + MD5_SINE[36], 23) + C;
A := ROL(A + (B xor C xor D) + x[ 1] + MD5_SINE[37], 4) + B;
D := ROL(D + (A xor B xor C) + x[ 4] + MD5_SINE[38], 11) + A;
C := ROL(C + (D xor A xor B) + x[ 7] + MD5_SINE[39], 16) + D;
B := ROL(B + (C xor D xor A) + x[10] + MD5_SINE[40], 23) + C;
A := ROL(A + (B xor C xor D) + x[13] + MD5_SINE[41], 4) + B;
D := ROL(D + (A xor B xor C) + x[ 0] + MD5_SINE[42], 11) + A;
C := ROL(C + (D xor A xor B) + x[ 3] + MD5_SINE[43], 16) + D;
B := ROL(B + (C xor D xor A) + x[ 6] + MD5_SINE[44], 23) + C;
A := ROL(A + (B xor C xor D) + x[ 9] + MD5_SINE[45], 4) + B;
D := ROL(D + (A xor B xor C) + x[12] + MD5_SINE[46], 11) + A;
C := ROL(C + (D xor A xor B) + x[15] + MD5_SINE[47], 16) + D;
B := ROL(B + (C xor D xor A) + x[ 2] + MD5_SINE[48], 23) + C;
{ Round 4. }
A := ROL(A + ((B or not D) xor C) + x[ 0] + MD5_SINE[49], 6) + B;
D := ROL(D + ((A or not C) xor B) + x[ 7] + MD5_SINE[50], 10) + A;
C := ROL(C + ((D or not B) xor A) + x[14] + MD5_SINE[51], 15) + D;
B := ROL(B + ((C or not A) xor D) + x[ 5] + MD5_SINE[52], 21) + C;
A := ROL(A + ((B or not D) xor C) + x[12] + MD5_SINE[53], 6) + B;
D := ROL(D + ((A or not C) xor B) + x[ 3] + MD5_SINE[54], 10) + A;
C := ROL(C + ((D or not B) xor A) + x[10] + MD5_SINE[55], 15) + D;
B := ROL(B + ((C or not A) xor D) + x[ 1] + MD5_SINE[56], 21) + C;
A := ROL(A + ((B or not D) xor C) + x[ 8] + MD5_SINE[57], 6) + B;
D := ROL(D + ((A or not C) xor B) + x[15] + MD5_SINE[58], 10) + A;
C := ROL(C + ((D or not B) xor A) + x[ 6] + MD5_SINE[59], 15) + D;
B := ROL(B + ((C or not A) xor D) + x[13] + MD5_SINE[60], 21) + C;
A := ROL(A + ((B or not D) xor C) + x[ 4] + MD5_SINE[61], 6) + B;
D := ROL(D + ((A or not C) xor B) + x[11] + MD5_SINE[62], 10) + A;
C := ROL(C + ((D or not B) xor A) + x[ 2] + MD5_SINE[63], 15) + D;
B := ROL(B + ((C or not A) xor D) + x[ 9] + MD5_SINE[64], 21) + C;
Inc(FState[0], A);
Inc(FState[1], B);
Inc(FState[2], C);
Inc(FState[3], D);
end;
{$Q+}
{$ENDIF}
end.

===

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

AHCI

Wiki: “Advanced Host Controller Interface (AHCI) — механизм, используемый для подключения накопителей информации по протоколу Serial ATA, позволяющий пользоваться расширенными функциями, такими, как встроенная очерёдность команд (NCQ) и горячая замена.”

Как включить:

Windows 7

1. В реестре в разделе HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\msachi установить значение параметра “Start” (REG_DWORD) равным 0 (по-умолчанию Start=3).

2. В реестре в разделе HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\iaStorV установить значение параметра “Start” (REG_DWORD) равным 0 (по-умолчанию Start=3).

3. В BIOS включить режим AHCI вместо IDE.

Windows 10

1. В реестре в разделе HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\iaStorV установить значение параметра “Start” (REG_DWORD) равным 0.

2. В реестре в разделе HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\iaStorAV\StartOverride установить значение параметра “0” равным 0 (по-умолчанию значение этого параметра равно 3).

3. В реестре в разделе HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\storachi\StartOverride установить значение параметра “0” равным 0 (по-умолчанию значение этого параметра равно 3).

4. В BIOS включить режим AHCI вместо IDE.

CentOS 7

1. Выполнить:

sudo modprobe ahci
sudo cp /boot/initramfs-`uname -r`.img /boot/initramfs-`uname -r`.img.bak
sudo mkinitrd -f --with=ahci /boot/initramfs-`uname -r`.img `uname -r`

2. В BIOS включить режим AHCI вместо IDE.

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

MiniDLNA: refresh files and folders structure

Как обновить структуру файлов и каталогов в MiniDLNA:

sudo service minidlna stop
sudo rm -rf /var/cache/minidlna/files.db
sudo service minidlna restart

UPD.

sudo /etc/init.d/minidlna restart
sudo /etc/init.d/minidlna force-reload

UPD2

sudo minidlnad -R
sudo service minidlna restart

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

[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 .
}
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

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

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

Ниже приведена иллюстрация построения дерева цифрового поиска на 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

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

Теория

Задача: имеется два больших (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

Реализация на Delphi: https://github.com/optinsoft/SearchStrings

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

Lazarus Exe

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

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

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

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