この発言は
#01373　ぜえた          さんの高速文字列検索（BM法）
に対するコメントです



function TStringSearch.NSearch(StrStart, StrEnd: PChar): PChar; 
register;
asm
  push esi
  push edi
  push ebx
  sub  esp, 8
  mov  edi, eax
  mov  esi, edx
  mov  [esp], ecx
  mov  edx, [edi].TStringSearch.FPattern
  mov  eax, [edx - 4]
  dec  eax
  add  esi, eax
  mov  bl, [edx + eax]
  dec  eax
  xor  ecx, ecx
  mov  [esp + 4], eax
@@OuterLoop:
  cmp  esi, [esp]
  jae  @@NotFound
  mov  cl, [esi]
  cmp  cl, bl
  jne  @@NotMatchLastChar
@@MatchLastChar:
  mov  eax, [esp + 4]
@@InnerLoop:
  dec  esi
  mov  cl, [edx + eax]
  cmp  cl, [esi]
  jne  @@NotMatchChar
@@MatchChar:
  dec  eax
  jge  @@InnerLoop
@@Found:
  mov  eax, esi
  add  esp, 8
  pop  ebx
  pop  edi
  pop  esi
  ret
@@NotMatchChar:
  mov  ecx, [edi].TStringSearch.FNextTable
  add  esi, [ecx + eax * 4]
  xor  ecx, ecx
  jmp  @@OuterLoop
@@NotMatchLastChar:
  add  esi, dword ptr[edi + ecx * 4].TStringSearch.FSkipTable
  jmp  @@OuterLoop
@@NotFound:
  xor  eax, eax
  add  esp, 8
  pop  ebx
  pop  edi
  pop  esi
end;

function TStringSearch.NISearch(StrStart, StrEnd: PChar): PChar; 
register;
asm
  push esi
  push edi
  push ebx
  sub  esp, 8
  mov  edi, eax
  mov  esi, edx
  mov  [esp], ecx
  mov  edx, [edi].TStringSearch.FPattern
  mov  eax, [edx - 4]
  dec  eax
  add  esi, eax
  mov  bl, [edx + eax]
  dec  eax
  xor  ecx, ecx
  mov  [esp + 4], eax
@@OuterLoop:
  cmp  esi, [esp]
  jae  @@NotFound
  mov  cl, [esi]
  mov  cl, byte ptr CharTable[ecx]
  cmp  cl, bl
  jne  @@NotMatchLastChar
@@MatchLastChar:
  mov  eax, [esp + 4]
@@InnerLoop:
  dec  esi
  mov  cl, [esi]
  mov  cl, byte ptr CharTable[ecx]
  cmp  cl, [edx + eax]
  jne  @@NotMatchChar
@@MatchChar:
  dec  eax
  jge  @@InnerLoop
@@Found:
  mov  eax, esi
  add  esp, 8
  pop  ebx
  pop  edi
  pop  esi
  ret
@@NotMatchChar:
  mov  ecx, [edi].TStringSearch.FNextTable
  add  esi, [ecx + eax * 4]
  xor  ecx, ecx
  jmp  @@OuterLoop
@@NotMatchLastChar:
  add  esi, dword ptr[edi + ecx * 4].TStringSearch.FSkipTable
  jmp  @@OuterLoop
@@NotFound:
  xor  eax, eax
  add  esp, 8
  pop  ebx
  pop  edi
  pop  esi
end;

function TStringSearch.AnsiSearch(StrStart, StrEnd: PChar): PChar; 
register;
var
  ByteType : TMbcsByteType;
begin
  while True do begin
    Result := FInnerSearch(StrStart, StrEnd);
    if Result = nil then Exit;
    ByteType := StrByteType(StrStart, Result - StrStart);
    if ByteType <> mbTrailByte then Exit;
    Inc(Result);
    StrStart := Result;
  end;
end;

procedure TStringSearch.InitAnsiTable;
var
  Patterns: array[0..1] of string;
  L: Integer;
  c: Char;
  i: Integer;
  j, k: Integer;
  s, t: PAnsiStringSearchState;
  d: Integer;
  f: Boolean;
begin
  if ssFileName in FOptions then begin
    Patterns[0] := AnsiLowerCaseFileName(FPattern);
    Patterns[1] := AnsiUpperCaseFileName(FPattern);
  end else begin
    Patterns[0] := AnsiLowerCase(FPattern);
    Patterns[1] := AnsiUpperCase(FPattern);
  end;
  L := Length(FPattern);
  for c := #0 to #255 do
    FSkipTable[c] := L;
  for i := 1 to L - 1 do
    for j := 0 to 1 do
      FSkipTable[Patterns[j][i]] := L - i;
  GetMem(FAnsiNextTable, SizeOf(TAnsiStringSearchState) * (L+1) * 2);
  for k := 0 to 1 do
    FAnsiNextTable^[k].Fail := nil;
  f := False;
  for i := 1 to L do begin
    d := L - i;
    f := (not f) and (FPattern[i] in LeadBytes);
    for j := 0 to 1 do begin
      with FAnsiNextTable^[d*2+j] do begin
        Next := L + d;
        Skip := Next;
        Depth := d;
        if f then begin
          Ch[0] := Patterns[j][i];
          Trans[0] := @FAnsiNextTable^[d*2+2+j];
          Ch[1] := Ch[0];
          Trans[1] := Trans[0];
        end else begin
          Ch[0] := Patterns[0][i];
          Trans[0] := @FAnsiNextTable^[d*2+2];
          Ch[1] := Patterns[1][i];
          Trans[1] := @FAnsiNextTable^[d*2+3];
        end;
      end;
    end;
  end;
  for k := L*2 to L*2+1 do
    FAnsiNextTable^[k].Depth := L;
  for k := 0 to L*2-1 do begin
    with FAnsiNextTable^[k] do begin
      for j := 0 to 1 do begin
        s := Fail;
        while (s <> nil) and (s^.Ch[0] <> Ch[j])
                         and (s^.Ch[1] <> Ch[j]) do begin
          UpdateMin(s^.Next, Depth);
          s := s^.Fail;
        end;
        if s = nil then begin
          Trans[j]^.Fail := @FAnsiNextTable^[j];
        end else if s^.Ch[0] = Ch[j] then begin
          Trans[j]^.Fail := s^.Trans[0];
        end else begin
          Trans[j]^.Fail := s^.Trans[1];
        end;
      end;
    end;
  end;
  for j := 0 to 1 do begin
    t := @FAnsiNextTable^[L*2+j];
    s := t^.Fail;
    while True do begin
      if s = nil then Break;
      s^.Skip := t^.Depth;
      s := s^.Fail;
    end;
  end;
  for k := 0 to L*2-1 do begin
    with FAnsiNextTable^[k] do begin
      UpdateMin(Trans[0]^.Skip, Skip + 1);
      UpdateMin(Trans[1]^.Skip, Skip + 1);
      UpdateMin(Next, Skip);
    end;
  end;
  for k := L*2-2 to L*2-1 do begin
    FAnsiNextTable^[k].Trans[0] := nil;
    FAnsiNextTable^[k].Trans[1] := nil;
  end;
end;

function TStringSearch.AISearch(StrStart, StrEnd: PChar): PChar; 
register;
var
  s0, s: PAnsiStringSearchState;
begin
  Result := StrStart + Length(FPattern) - 1;
  s0 := @FAnsiNextTable^[0];
  while Result < StrEnd do begin
    s := s0;
    if Result^ = s^.Ch[0] then begin
      s := s^.Trans[0];
    end else if Result^ = s^.Ch[1] then begin
      s := s^.Trans[1];
    end else begin
      Inc(Result, FSkipTable[Result^]);
      Continue;
    end;
    while True do begin
      Dec(Result);
      if Result^ = s^.Ch[0] then begin
        s := s^.Trans[0];
        if s = nil then Exit;
      end else if Result^ = s^.Ch[1] then begin
        s := s^.Trans[1];
        if s = nil then Exit;
      end else begin
        Inc(Result, s^.Next);
        Break;
      end;
    end;
  end;
  Result := nil;
end;

procedure InitCharTable;
var
  c: Char;
begin
  for c := #0 to #255 do
    CharTable[c] := c;
  for c := 'a' to 'z' do
    Dec(CharTable[c], $20);
end;

initialization
  InitCharTable;
end.
 


- FDELPHI  MES(16):玉石混淆みんなで作るSample蔵【見本蓄積】 01/08/08 -

Original document by ぜえた          氏 ID:(QZC05100)

ここにあるドキュメントは NIFTY SERVEの Delphi Users' Forum の16番会議室「玉石混淆みんなで作るSample蔵」に投稿されたサンプルです。これらのサンプルはボーランド株式会社がサポートする公式のものではありません。また、必ずしも動作が検証されているものではありません。これらのサンプルを使用したことに起因するいかなる損害も投稿者、およびフォーラムスタッフはその責めを負いません。使用者のリスクの範疇でご使用下さい。