Anzahl eines Zeichens im String ermitteln

[jbg]

So und jetzt eine Variante mit SIMD (SSE2, benötigt mindestens Nehalem Prozessorarchitektur von 2008). Sie ist mit Delphi 2009 kompilierbar und dürfte alle bisherigen Funktion "wegblasen".

Zitat:

00000 Calibrate
03279 1234588 miep
05454 Ydobon
02642 marabu
03377 Missionar
03252 alzaimar
02661 Uwe Raabe StringCountChar
02635 Uwe Raabe StringCountCharFor
02346 KodeZwerg CountCharInString
06970 KodeZwerg CharInStringA
03529 Neutral General CharCountAsm
01779 Andreas Hausladen CountCharAsm
00515 Andreas Hausladen CountCharAsmSIMD
01953 Uwe Raabe CharCount
02713 Egon Hugeist CharCount_1
03261 Egon Hugeist CharCount_2
02640 Egon Hugeist CharCount_Double_Sided_3
02695 Egon Hugeist CharCount_Double_Sided_4
03328 Delphi CountChar

Delphi-Quellcode:

function AH_CountCharAsmSIMD(const Str: String; c: Char): Cardinal;
asm
{$IFNDEF CPUX64}
  test eax, eax
  jz @@Empty       // wenn S = '' then gibt es nichts zu tun

  push ebx
  push esi
  mov esi, eax
  xor eax, eax // Rückgabewert auf 0 setzen

  // Stringlänge ermitteln
  //mov ecx, DWORD PTR [esi-skew].StrRec.Length
  mov ecx, DWORD PTR [esi-$04]
  shl ecx, 1 // Auf Byte-Offsets umrechnen
  lea esi, [esi+ecx] // ESI so umrechnen, dass ESI+ECX auf das String-Ende zeigen
  neg ecx
  cmp ecx, -8
  ja @@SingleChars

  // DX in XMM0 als DX:DX:DX:DX:DX:DX:DX:DX verteilen
  movd xmm0, edx
  pshuflw xmm0, xmm0, 0
  pshufd xmm0, xmm0, 0

  // Offset so ändern, damit nicht über das String-Ende hinauslesen gelesen wird
  add ecx, 16
  jc @@RemainingChars
  sub esi, 16

  nop // Alignment
  // 8 Zeichen auf einmal verarbeiten
@@Loop8WideChars:
  movdqu xmm1, [esi+ecx] // 16 Bytes (8 Zeichen) laden
  pcmpeqw xmm1, xmm0 // Vergleichen. in XMM1 steht danach für jedes gefundene Zeichen $FFFF an der WORD Position
  pmovmskb ebx, xmm1 // Das oberste Bit jedes Bytes in XMM1 in EBX als Bit-Maske übertragen
  popcnt ebx, ebx // Anzahl der Bits ermitteln (CPU muss POPCNT unterstützen, Nehalem von 2008)
  shr ebx, 1 // Da PMOVMSKB auf Bytes anstatt auf WORDs arbeitet, haben wir doppelt so viele Bits => div 2
  add eax, ebx

  add ecx, 16
  jz @@Leave
  jnc @@Loop8WideChars

  // Offset für den Einzelzeichen-Vergleich wiederherstellen
  add esi, 16
@@RemainingChars:
  sub ecx, 16
  cmp ecx, -8
  ja @@SingleChars

  // 4 Zeichen auf einmal verarbeiten
  movq xmm1, QWORD PTR [esi+ecx] // 8 Bytes (4 Zeichen) laden
  pcmpeqw xmm1, xmm0 // Vergleichen. In XMM1 steht danach für jedes gefundene Zeichen $FFFF an der WORD Position
  pmovmskb ebx, xmm1 // Das oberste Bit jedes Bytes in XMM1 in EBX als Bit-Maske übertragen
  movzx ebx, bl // Nur die unteren 8 Bits sind korrekt befüllt alle anderen auf 0 setzen
  popcnt bx, bx // Anzahl der Bits ermitteln (CPU muss POPCNT unterstützen, Nehalem von 2008)
  shr ebx, 1 // Da PMOVMSKB auf Bytes anstatt auf WORDs arbeitet, haben wir doppelt so viele Bits => div 2
  add eax, ebx

  add ecx, 8
  jz @@Leave

  nop
@@SingleChars:
  xor ebx, ebx
@@Loop:
  cmp WORD PTR [esi+ecx], dx
  sete bl
  add eax, ebx
  add ecx, 2
  jnz @@Loop

@@Leave:
  pop esi
  pop ebx
@@Empty:
{$ELSE}
  xor rax, rax // Rückgabewert auf 0 setzen

  test rcx, rcx
  jz @@Leave       // wenn S = '' then gibt es nichts zu tun

  mov r8, rcx

  // Stringlänge ermitteln
  //movsxd r9, DWORD PTR [r8-skew].StrRec.Length
  movsxd r9, DWORD PTR [r8-$04]
  shl r9, 1  // Auf Byte-Offsets umrechnen
  lea r8, [r8+r9]  // E8 so umrechnen, dass R8+R9 auf das String-Ende zeigen
  neg r9
  cmp r9, -8
  ja @@SingleChars

  // DX in XMM0 als DX:DX:DX:DX:DX:DX:DX:DX verteilen
  movd xmm0, edx
  pshuflw xmm0, xmm0, 0
  pshufd xmm0, xmm0, 0

  // Offset so ändern, damit nicht über das String-Ende hinauslesen gelesen wird
  add r9, 16
  jc @@RemainingChars
  sub r8, 16

  nop; nop // alignment
  // 8 Zeichen auf einmal verarbeiten
@@Loop8WideChars:
  movdqu xmm1, [r8+r9] // 16 Bytes (8 Zeichen) laden
  pcmpeqw xmm1, xmm0 // Vergleichen. In XMM1 steht danach für jedes gefundene Zeichen $FFFF an der WORD Position
  pmovmskb ecx, xmm1 // Das oberste Bit jedes Bytes in XMM1 in ECX als Bit-Maske übertragen
  popcnt ecx, ecx // Anzahl der Bits ermitteln (CPU muss POPCNT unterstützen, Nehalem von 2008)
  shr ecx, 1 // Da PMOVMSKB auf Bytes anstatt auf WORDs arbeitet, haben wir doppelt so viele Bits => div 2
  add eax, ecx

  add r9, 16
  jz @@Leave
  jnc @@Loop8WideChars

  // Offset für den Einzelzeichen-Vergleich wiederherstellen
  add r8, 16
@@RemainingChars:
  sub r9, 16
  cmp r9, -8
  ja @@SingleChars

  // 4 Zeichen auf einmal verarbeiten
  movq xmm1, QWORD PTR [r8+r9] // 8 Bytes (4 Zeichen) laden
  pcmpeqw xmm1, xmm0 // Vergleichen. in XMM1 steht danach für jedes gefundene Zeichen $FFFF an der WORD Position
  pmovmskb ecx, xmm1 // Das oberste Bit jedes Bytes in XMM1 in ECX als Bit-Maske übertragen
  movzx ecx, cl // Nur die unteren 8 Bits sind korrekt befüllt alle anderen auf 0 setzen
  popcnt cx, cx // Anzahl der Bits ermitteln (CPU muss POPCNT unterstützen, Nehalem von 2008)
  shr ecx, 1 // Da PMOVMSKB auf Bytes anstatt auf WORDs arbeitet, haben wir doppelt so viele Bits => div 2
  add eax, ecx

  add r9, 8
  jz @@Leave

  nop // Alignment
@@SingleChars:
  xor ecx, ecx
@@Loop:
  cmp WORD PTR [r8+r9], dx
  sete cl
  add eax, ecx
  add r9, 2
  jnz @@Loop
@@Leave:
{$ENDIF ~CPUX64}
end;