Playing around with Karp-Rabin exact string search algorithm; did some assembler optimization -- the inner loop can be coded to use only registers. kr.c:

#define SHIFT 3
#define REHASH(a, b, h, m) ((((h) - ((a)<<(m))) << SHIFT) + (b))
#define OUTPUT(j) printf("%d\n", (j))

void KR(const char *pattern, int pattern_len, const char *text, int text_len) {
   int i;
   unsigned int hx, hy;

   /* Preprocessing */
   for (hy = hx = i = 0; i < pattern_len; ++i) {
      hx = ((hx<
kr_opt.s (loop only):
        mov     edi, DWORD PTR [ebp+16] /* text[i] pointer */
        lea     esi, [edi+eax] /* load text[i+pattern_len] pointer */
        mov     edx, DWORD PTR [ebp-32] /* load hy */
        jmp     .L7
.L6:
        mov     ch, BYTE PTR [esi] /* get text[i+pattern_len] */
        inc     esi
        movzx   eax, BYTE PTR [edi] /* get text[i] */

        inc     edi
        dec     ebx /* i <= (text_len-pattern_len) */
        jz      .L8

        sal     eax, cl /* tmp = text[i] << shift */
        sub     edx, eax /* hy - tmp */
        movzx   eax, ch
        lea     edx, [eax+edx*8] /* hy = (hy << 3) + text[i+pattern_len]
.L7:
        cmp     DWORD PTR [ebp-36], edx /* hx == hy */
        jne     .L6

The results against gcc 4.3.0, can this be improved?





  posted at: 17:16 | path: /programming | permanent link