SSE4: instrukcje działające na łańcuchach

Autor: Wojciech Muła
Dodane:2.09.2007
Aktualizacja:27.04.2008

Treść

Wstęp update

UWAGA: niniejszy artykuł powstał na postawie Intel SSE4 Programming Reference, bez dostępu do działającego sprzętu. Zatem zastrzegam sobie prawo do grubych błędów; zastrzegam także, że tekst nie jest kompletny. Więcej na temat SSE4 można znaleźć na Wikipedii.

Motywacją do powstania tekstu jest koszmarnie zagmatwany opis rozkazów PCMPESTRI, PCMPESTRM, PCMPISTRI oraz PCMPISTRM --- musiałem to sobie jakoś poukładać i oto efekt. Omawiane rozkazy pozwalają na porównywanie łańcuchów, testowanie przynależności do zbiorów, wyszukiwanie wystąpień określonych ciągów i pewnie sporo innych rzeczy, które teraz nie przychodzą mi do głowy.

Dopisek 27.04.2008:

Na stronie http://softwareprojects.intel.com/avx/ dotyczącej zasadniczo AVX zostały udostępnione dwie noty aplikacyjne opisujące zastosowanie opisanych tutaj rozkazów do:

Wprowadzenie

Składnia intelowska:

PCMPxSTRx xmm1, xmm2/mem, imm8

Składnia AT&T (GNU as już rozpoznaje rozkazy SSE4):

PCMPxSTRx $imm8, xmm2/mem, xmm1

Stała natychmiastowa określa sposób działania, typ danych etc. Jej znaczenie zostało dokładnie opisane w dokumentacji, tutaj raczej mniej szczegółowo.

Wszystkie instrukcje w zależności od wyników modyfikują rejestr flag (CF, ZF, SF, OF; zerują AF i PF). Ponadto rozkazy łańcuchowe uwzględniają koniec łańcucha (ograniczony albo zerem, albo zadany długością), ignorując znaki nie należące do łańcuchów.

Typy danych

Rozkazy PCMPxSTRx działają na łańcuchach bajtów bądź słów; na liczbach ze znakiem, jak i bez znaku — bity 1:0 stałej imm8 określają typ (patrz sekcja 5.3.1.1):

W tym tekście ograniczę się do bajtów bez znaków, żeby za bardzo nie gmatwać.

Długość łańcuchów

Jednocześnie przetwarzane są całe rejestry XMM, czyli 16 lub 8 elementów; jednak koniec łańcucha może wypaść gdzieś w środku rejestru — rozkazy PCMPxSTRx pozwalają dwojako określić długości łańcuchów:

  1. Bezpośrednio (explicit, rozkazy PCMPESTRx) — długości zapisane są w rejestrach EAX (RAX) oraz EDX (RDX); rozkazy wewnętrznie nasycają je do maksymalnej długości (tj. 16 lub 8), zatem w głównej pętli wystarczy pamiętać liczbę znaków pozostałych do końca:

    mov     n,      %eax    # długość xmm1
mov     k,      %edx    # długość xmm2/mem
loop:
        # przetwarzanie 16 bajtów
        # przez PCMPESTRx

        sub     $16, %eax       # zmniejsz
        js      end             # liczbę
        sub     $16, %edx       # znaków
        jns     loop            # w obu łańcuchach
end:

  2. Obliczane (implict, rozkazy PCMPISTRx) — długość łańcucha wyznaczana jest automatycznie, pierwszy bajt/słowo o wartości zero markuje koniec.

Wszystkie znaki poza końcem są oznaczane jako nieprawidłowe (invalid); Przy obliczaniu wyników brane są tylko znaki należące do łańcuchów (valid); końcowe zero w rozkazach PCMPISTRx nie jest uznawane za część łańcuchów.

Zasada działania

Po wyznaczeniu długości łańcuchów mają miejsce następujące kroki:

1. Tworzenie pośredniego wyniku na podstawie macierzy porównań

Rozkazy PCMPxSTRx mogą wyznaczać wyniki na cztery różne sposoby:

  1. equal any — przynależność do zbioru znaków
  2. equal each — równość łańcuchów
  3. equal ordered — wyszukiwanie podciągów
  4. ranges — przynależność do pewnego przedziału/przedziałów

Działanie jest zakodowane w stałej imm8 na bitach 3:2:

  • 00b — equal any
  • 01b — ranges
  • 10b — equal each
  • 11b — equal ordered

equal any, each, ordered

Najpierw wykonywane jest porównanie typu każdy-z-każdym znaków z obu łańcuchów, czego wynikiem jest macierz 16 x 16 bitów. Sprawdzana jest równość elementów — wynik prawdziwy jest oznaczany przez zapalenie odpowiedniego bitu.

W zależności od wybranego sposobu wyznaczania wyniku, elementy macierzy odpowiadające znakom spoza końców łańcuchów (tj. oznaczone jako invalid) są ustawiane lub zerowane, tak aby finalne wyniki były sensowne (patrz sekcja 5.3.1.5).

Ostatecznie na podstawie macierzy wyznaczany jest pośredni wynik IntRes1.

Jeszcze tylko przypomnę składnię:

PCMPxSTRx xmm1, xmm2/mem, imm8          # Intel
PCMPxSTRx $imm8, %xmm2/mem, %xmm1       # AT&T

equal any

Wynik equal any mówi, które ze znaków z xmm2/mem znajdują się także w xmm1.

Zastosowania to np. funkcje z języka C działające na zbiorach znaków, czyli strspn(), strnspn(), strpbrk, ale także funkcje weryfikujące napisy, np. czy reprezentują liczbę dziesiętną, szesnastkową, identyfikator itp.

Przykład działania:

xmm1     -> "-+*/0123456789__"  # _ zamiast spacji
xmm2/mem -> "15_+_x*(9/var)%5"  # jakiś łańcuch

Po porównaniu wszystkie bity z danego wiersza z macierzy są łączone za pomocą operacji OR a wynik zapisywany jako bit w słowie IntRes1:

IntRes1[i] = (xmm2[i] == xmm1[0]) OR (xmm2[i] == xmm1[1]) OR ...

Wynikowa macierz:

+------------------------------------------+---------+
| xmm1 ->  - + * / 0 1 2 3 4 5 6 7 8 9 _ _ | IntRes1 |
+------------------------------------------+---------+-----+
     | 1 | . . . . . 1 . . . . . . . . . . |    1   <- LSB |
     | 5 | . . . . . . . . . 1 . . . . . . |    1    |     |
     | _ | . . . . . . . . . . . . . . 1 1 |    1    |     |
     | + | . 1 . . . . . . . . . . . . . . |    1    |     |
     | _ | . . . . . . . . . . . . . . 1 1 |    1    |     |
     | x | . . . . . . . . . . . . . . . . |    0    |     |
     | * | . . 1 . . . . . . . . . . . . . |    1    |     |
     | ( | . . . . . . . . . . . . . . . . |    0    |     |
     | 9 | . . . . . . . . . . . . . 1 . . |    1    |     |
     | / | . . . 1 . . . . . . . . . . . . |    1    |     |
     | v | . . . . . . . . . . . . . . . . |    0    |     |
     | a | . . . . . . . . . . . . . . . . |    0    |     |
     | r | . . . . . . . . . . . . . . . . |    0    |     |
     | ) | . . . . . . . . . . . . . . . . |    0    |     |
     | % | . . . . . . . . . . . . . . . . |    0    |     |
     | 5 | . . . . . . . . . 1 . . . . . . |    1   <- MSB |
     |   +---------------------------------+---------+-----+
     | xmm2/mem |
     +----------+

Z przykładowego wyniku widać, że nie wszystkie znaki należą do zbioru podanego w xmm1.

equal each

Wynik equal each mówi, które znaki z xmm2/mem odpowiadają znakom z xmm1 — innymi słowy testowana jest równość łańcuchów. Teoretycznie to samo można uzyskać za pomocą rozkazu pcmpeqb xmm1, xmm2/mem, lecz należy pamiętać, że rozkazy PCMPxSTRx uwzględniają długości napisów i umożliwiają za jednym zamachem wykonać jeszcze kilka dodatkowych działań.

Zastosowania to np. funkcje z języka C porównujące znaki, czyli strcmp(), strncmp(); ale może również służyć do wyznaczania najdłuższego prefiksu, co może przyspieszyć kompresję metodami LZ77 czy LZSS.

Przykładowe dane:

xmm1     -> "SSE3 => today   "  # jakiś łańcuch
xmm2/mem -> "SSE4 >> tomorrow"  # inny łańcuch

Słowo wynikowe IntRes1 zawiera bity z przekątnej macierzy.

Wynikowa macierz:

+------------------------------------------+---------+
| xmm1 ->  S S E 3   = >   t o d a y       | IntRes1 |
+------------------------------------------+---------+-----+
     | S | 1 1 . . . . . . . . . . . . . . |    1   <- LSB |
     | S | 1 1 . . . . . . . . . . . . . . |    1    |     |
     | E | . . 1 . . . . . . . . . . . . . |    1    |     |
     | 4 | . . . . . . . . . . . . . . . . |    0    |     |
     |   | . . . . 1 . . . . . . . . . . . |    1    |     |
     | > | . . . . . . . . . . . . . . . . |    0    |     |
     | > | . . . . . . 1 . . . . . . . . . |    1    |     |
     |   | . . . . . . . 1 . . . . . . . . |    1    |     |
     | t | . . . . . . . . 1 . . . . . . . |    1    |     |
     | o | . . . . . . . . . 1 . . . . . . |    1    |     |
     | m | . . . . . . . . . . . . . . . . |    0    |     |
     | o | . . . . . . . . . . . . . . . . |    0    |     |
     | r | . . . . . . . . . . . . . . . . |    0    |     |
     | r | . . . . . . . . . . . . . . . . |    0    |     |
     | o | . . . . . . . . . . . . . . . . |    0    |     |
     | w | . . . . . . . . . . . . . . . . |    0   <- MSB |
     |   +---------------------------------+---------+-----+
     | xmm2/mem |
     +----------+

Np. z wyniku widać, że trzy pierwsze bity są ustawione, zatem łańcuchy mają wspólny prefiks. Ale ponieważ słowo IntRes1 nie jest wypełnione jedynkami, stąd wiadomo, że łańcuchy nie są identyczne.

equal ordered

UWAGA: dla tego przypadku nie jestem pewien czy dobrze zrozumiałem pseudokod umieszczony w dokumentacji.

Metoda equal ordered pozwala wyszukać w xmm2/mem wystąpienia łańcucha xmm1 (bądź prefiksy, jeśli przekraczana jest długość xmm2/mem).

Przykładowe dane:

xmm1     -> "abc"               # szukany łańcuch (długość 3 znaki)
xmm2/mem -> "__abcab___abc_ab"  # jakiś łańcuch

Algorytm przetwarzania macierzy wykrywa ukośne ciągi jedynek ulokowane przy lewej krawędzi — w IntRes1 ustawiane są te bity, które odpowiadają początkom ciągów. Ciągi jedynek mają długość max(długość xmm1, 16 - indeks w xmm2/mem), tj. albo dokładnie długość łańcucha xmm1, albo mniej, jeśli zaczynają się przy końcu bloku.

Wynikowa macierz:

+------------------------------------------+---------+
| xmm1 ->  a b c                           | IntRes1 |
+------------------------------------------+---------+-----+
     | _ | . . . . . . . . . . . . . . . . |    0   <- LSB |
     | _ | . . . . . . . . . . . . . . . . |    0    |     |
     | a | 1 . . . . . . . . . . . . . . . |    1    |     |
     | b | . 1 . . . . . . . . . . . . . . |    0    |     |
     | c | . . 1 . . . . . . . . . . . . . |    0    |     |
     | a | 1 . . . . . . . . . . . . . . . |    0    |     |
     | b | . 1 . . . . . . . . . . . . . . |    0    |     |
     | _ | . . . . . . . . . . . . . . . . |    0    |     |
     | _ | . . . . . . . . . . . . . . . . |    0    |     |
     | _ | . . . . . . . . . . . . . . . . |    0    |     |
     | a | 1 . . . . . . . . . . . . . . . |    1    |     |
     | b | . 1 . . . . . . . . . . . . . . |    0    |     |
     | c | . . 1 . . . . . . . . . . . . . |    0    |     |
     | _ | . . . . . . . . . . . . . . . . |    0    |     |
     | a | 1 . . . . . . . . . . . . . . . |    1    |     |
     | b | . 1 . . . . . . . . . . . . . . |    0   <- MSB |
     |   +---------------------------------+---------+-----+
     | xmm2/mem |
     +----------+

Z przykładowego wyniku widać, że w xmm2/mem trzykrotnie występują prefiksy ciągu "abc" — potrzebne są jednak dodatkowe testy, aby stwierdzić, które prefiksy są równe xmm1.

ranges

Ta metoda jest dość podobna do equal any, z tą różnicą, że xmm1 nie zawiera zbioru znaków, ale zbiór przedziałów obustronnie domkniętych. Przedziały definiują dwa kolejne elementy: element o parzystym indeksie zawiera dolną granicę, a o nieparzystym — górną. Wynik mówi, czy poszczególne znaki z xmm2/mem należą do przynajmniej jednego przedziału.

Przykładowe zastosowania to funkcje w rodzaju isdigit() dla łańcuchów, czy inne weryfikujące poprawność napisów.

Przykładowe dane:

xmm1     -> "AZaz09__.."        # [A-Za-z0-9_.] -- np. nazwy plików
                                # długość xmm1 = 10
xmm2/mem -> " Some_file5.pdf!"  # przykładowa nazwa pliku

Łańcuch xmm2/mem jest porównywany relacją „większy lub równy” z elementami xmm1 o indeksach parzystych (tj. z dolną granicą każdego przedziału), a relacją „mniejszy lub równy” z elementami o indeksach nieparzystych.

Następnie każde dwie sąsiednie kolumny są łączone operatorem AND, a na końcu wszystkie bity z każdego wiersza operatorem OR (tak jak w działaniu equal any), tworząc słowo wynikowe:

IntRes1[i] = (xmm2[i] >= xmm1[0] AND xmm2[i] <= xmm1[1]) OR
             (xmm2[i] >= xmm1[2] AND xmm2[i] <= xmm1[3]) OR ...

Wynikowa macierz, przed wykonaniem AND:

+------------------------------------------+
| xmm1 ->  A Z a z 0 9 _ _ . .             |
+------------------------------------------+
     |   | . 1 . 1 . 1 . 1 . 1 . . . . . . |
     | S | 1 1 . 1 1 . . 1 1 . . . . . . . |
     | o | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | m | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | e | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | _ | 1 . . 1 1 . 1 1 1 . . . . . . . |
     | f | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | i | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | l | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | e | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | 5 | . 1 . 1 1 1 . 1 1 . . . . . . . |
     | . | . 1 . 1 . 1 . 1 1 1 . . . . . . |
     | P | 1 1 . 1 1 . . 1 1 . . . . . . . |
     | d | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | f | 1 . 1 1 1 . 1 . 1 . . . . . . . |
     | ! | . 1 . 1 . 1 . 1 . 1 . . . . . . |
     |   +---------------------------------+
     | xmm2/mem |
     +----------+

Macierz po wykonaniu operacji AND:

+--------------+-----+-----+-----+-----+---------+
| xmm1 ->  A Z | a z | 0 9 | _ _ | . . | IntRes1 |
+--------------+-----+-----+-----+-----+---------+-----+
     |   |  .  |  .  |  .  |  .  |  .  |    0   <- LSB |
     | S |  1  |  .  |  .  |  .  |  .  |    1    |     |
     | o |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | m |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | e |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | _ |  .  |  .  |  .  |  1  |  .  |    1    |     |
     | f |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | i |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | l |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | e |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | 5 |  .  |  .  |  1  |  .  |  .  |    1    |     |
     | . |  .  |  .  |  .  |  .  |  1  |    1    |     |
     | P |  1  |  .  |  .  |  .  |  .  |    1    |     |
     | d |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | f |  .  |  1  |  .  |  .  |  .  |    1    |     |
     | ! |  .  |  .  |  .  |  .  |  .  |    0   <- MSB |
     |   +-----+-----+-----+-----+-----+---------+-----+
     | xmm2/mem |
     +----------+

2. Wstępne przetwarzanie wyników

Słowo IntRes1 może zostać przed ostatecznym utworzeniem wyniku zanegowane lub zanegowane mogą być tylko bity odpowiadające znakom należącym do łańcucha xmm2/mem (tj. znakom oznaczonym jako valid). Wynikiem tego etapu jest nowe słowo — IntRes2:

Działanie określają bity 5:4 argumentu imm8:

  • 00b, 10b — bez zmian
  • 01b — negacja
  • 11b — negacja tylko tych bitów, które odpowiadają elementom łańcucha xmm2/mem

a bardziej formalnie:

00b, 10b: IntRes2 := IntRes1
01b:      IntRes2 := IntRes1 XOR 0xffff
11b:      mask := 0xffff AND valid_mask (np. 0x01ff dla łańcucha o długości 9)
          IntRes2 := IntRes1 XOR mask

3. Utworzenie wyniku

Słowo IntRes2 jest ostatecznie używane do utworzenia wyniku.

  wynik
bit 6. w imm8 = 0 bit 6. w imm8 = 1
PCMPESTRI PCMPISTRI numer pierwszego ustawionego bitu w IntRes2 zapisywany do ECX numer ostatniego ustawionego bitu w IntRes2 zapisywany do ECX
PCMPESTRM PCMPISTRM IntRes2 zapisywane w XMM0 (najstarsze bity są zerowane) maska bajtowa/słów na podstawie IntRes2 zapisywana w XMM0

UWAGA 1: Jeśli IntRes2 = 0, wówczas ECX = 16 (lub 8).

UWAGA 2: XMM0 odnosi się do rzeczywistego rejestru — zatem pierwszy argument rozkazu, tj. xmm1, nie musi zostać nadpisany.

4. Modyfikacja flag

  PCMPESTRI, PCMPESTRM (explicit string length) PCMPISTRI, PCMPISTRM (implict string length)
CF ustawiony gdy InRes2 <> 0 ustawiony gdy InRes2 <> 0
ZF ustawiony gdy ABS(EDX) < 16 (lub 8) ustawiony jeśli w xmm2/mem był jakiś zerowy bajt (lub słowo)
SF ustawiony gdy ABS(EAX) < 16 (lub 8) ustawiony jeśli w xmm1 był jakiś zerowy bajt (lub słowo)
OF bit 0. IntRes2 bit 0. IntRes2
AF 0 0
PF 0 0

Podsumowując:

  • flaga CF jest ustawiana, gdy IntRes2 jest niezerowe
  • flaga ZF jest ustawiana, jeśli w xmm2/mem jest zlokalizowany koniec łańcucha
  • flaga SF jest ustawiana, jeśli w xmm1 jest zlokalizowany koniec łańcucha
  • OF = najmłodszy bit IntRes2

Przykłady

W pliku sse4-string-instr.S znajduje się kilka funkcji łańcuchowych:

strcmp

/* int strcmp(const char* s1, const char* s2);

   inputs:
   - %esi -- s1
   - %edi -- s2

   result:
   - %eax
 */
strcmp:
        imm8 = SSESTR_PACKED_UBYTE  | \
               SSESTR_EQUAL_EACH    | \
               SSESTR_NEGATED_VALID | \
               SSESTR_FIRSTBIT

    L(mainloop):
        movups  (%esi), %xmm1           # load 16 bytes
        movups  (%edi), %xmm2           # from s1 & s2
        add     $16,    %esi
        add     $16,    %edi

        # implict length string compare for equal

        pcmpistri $imm8, %xmm2, %xmm1
        # sample 1 (strings different):
        #       xmm1 -> "string are diff"
        #       xmm2 -> "strXng are equa"
        #
        #       IntRes1 -> 111011111110111b
        #       IntRes2 -> 000100000001000b (negated valid)
        #       ECX     := bfs(IntRes2) = 3
        #       CF      := 1 (IntRes2 <> 0)
        #       ZF      := 0
        #
        # sample 2 (strings equal, but null byte found):
        #       xmm1 -> "string\0..."
        #       xmm2 -> "string\0..."
        #
        #       IntRes1 -> 000000001111111b
        #       IntRes2 -> 000000000000000b (negated valid)
        #       ECX     := 16 (there isn't any bit set in IntRes2)
        #       CF      := 0 (IntRes2 == 0, no diffs)
        #       ZF      := 1 (EOS, i.e. null byte in xmm2)

        ja  L(main_loop)  # CF=0 and ZF=0 (no diff, no null byte)

        jc  L(diff_found) # CF=1 -> offset is given
    L(null_found):
        # ZF=1 -> # calculate EOS position
        pxor     %xmm0, %xmm0
        pcmpeqb  %xmm2, %xmm0
        pmovmskb %xmm0, %ecx
        bsf      %ecx,  %ecx
    L(diff_found):
        movzbl  -16(%edi, %ecx), %edx
        movzbl  -16(%esi, %ecx), %eax
        sub     %edx, %eax
        ret

memcmp

/* int memcmp(const char* s1, const char* s2, size_t n);

   inputs:
   - %esi -- s1
   - %edi -- s2
   - %eax -- n

   result:
   - %eax
 */
memcmp:
        imm8 = SSESTR_PACKED_UBYTE  | \
               SSESTR_EQUAL_EACH    | \
               SSESTR_NEGATED_VALID | \
               SSESTR_FIRSTBIT


        xor  %ecx, %ecx
        test %eax, %eax  # n == 0 ?
        jz   L(diff_found)

        # n > 0
        add  $16,  %eax
        mov  %eax, %edx  # make length of both strings equal

    L(mainloop):
        movups  (%esi), %xmm1           # load 16 bytes
        movups  (%edi), %xmm2           # from s1 & s2
        add     $16,    %esi
        add     $16,    %edi

        sub     $16,    %eax            # decrement
        sub     $16,    %edx            # both lengths

        # explicit length string compare for equal

        pcmpestri $imm8, %xmm2, %xmm1
        # for some samples see comments in strcmp

        ja  L(mainloop)
        jc  L(diff_found)

    L(null_found):
        # get EOS position
        pxor     %xmm0, %xmm0
        pcmpeqb  %xmm2, %xmm0
        pmovmskb %xmm0, %ecx
        bsf      %ecx,  %ecx
    L(diff_found):
        movzbl  -16(%edi, %ecx), %edx
        movzbl  -16(%esi, %ecx), %eax
        sub     %edx, %eax
        ret

strchr

/* char* strchr(const char* s, int c);

   comment:
     If c > 256 then one can search for up to four chars; for
     example strchr(s, (int)'a' | ((int)'A' << 8) will
     find 'a' case insensitive.  It is not C-function feature!

   inputs:
   - %esi -- s
   - %eax -- c

   result:
   - %eax
 */
strchr:
        imm8 = SSESTR_PACKED_UBYTE | \
               SSESTR_EQUAL_ANY    | \
               SSESTR_UNCHANGED    | \
               SSESTR_FIRSTBIT

        movd    %eax, %xmm0     # xmm1 := string of length 1 contains char c
        xor     %edx, %edx      # edx  := NULL

    L(mainloop):
        add $16, %esi

        # implict string length - find first occurence of c or EOS
        pcmpistri $imm8, -16(%esi), %xmm0
        # sample 1 (char found)
        #       c       -> 's'
        #       mem     -> "Sunrise\0"
        #
        #                  .........esirnuS <- '.' = invalid
        #       IntRes2 -> 0000000000100000b
        #       ECX     -> bsf(IntRes2) = 5
        #       CF      -> 1 (IntRes2 <> 0)
        #       ZF      -> 1 (there is a null byte)
        #
        # sample 2 (null found)
        #       c       -> 'x'
        #       mem     -> "assembler\0"
        #
        #                  .......relbmessa <- '.' = invalid
        #       IntRes2 -> 0000000000000000b
        #       ECX     -> 16 (IntRes2 = 0)
        #       CF      -> 0
        #       ZF      -> 1 (there is a null byte)

        ja L(mainloop)  # CF=0 and ZF=0 (no char, no null found)

        lea -16(%esi, %ecx), %eax # eax := char address (valid if CF=1, i.e. char found)
        cmovnc %edx, %eax         # eax := NULL (if CF=0)
        ret

strchr (inna realizacja)

/* char* strchr2(const char* s, int c);

   inputs:
   - %esi -- s
   - %eax -- c

   result:
   - %eax
 */
strchr2:
        imm8 = SSESTR_PACKED_UBYTE | \
               SSESTR_EQUAL_ANY    | \
               SSESTR_UNCHANGED    | \
               SSESTR_FIRSTBIT

        movd    %eax, %xmm0     # xmm1 := string contains 'c' and '\0'
        mov     $2,   %eax      # eax  := length(xmm1) = 2
        mov     $16,  %edx      # edx  := length(xmm2/mem) = 16 (we'll
                                #         process all chars)

    L(mainloop):
        add $16, %esi

        # explicit string length - find first occurence of c or EOS
        pcmpestri $imm8, -16(%esi), %xmm0
        # sample (char or null found)
        #       c       -> 's'
        #       mem     -> "Sunrise0s00ssA0s"
        #
        #                  s\0Ass\0\0s\0esirnuS
        #       IntRes2 -> 1 1011 1 11 10100000b
        #       ECX     -> bsf(IntRes2) = 5
        #       CF      -> 1 (IntRes2 <> 0)

        jnc L(mainloop)  # CF=0 (no char, no null found)

        mov    $0, %edx           # edx := NULL
        lea -16(%esi, %ecx), %eax # eax := char address
                                  # (valid if CF=1, i.e. char or null found)
        cmovnc %edx, %eax         # eax := NULL (if CF=0)
        ret

strrchr

/* char* strrchr(const char* s, int c);

   comment:
     If c > 256 then one can search for up to four chars; for
     example strrchr(s, (int)'a' | ((int)'A' << 8) will
     find 'a' case insensitive.  It is not C-function feature!

   inputs:
   - %esi -- s
   - %eax -- c

   result:
   - %eax
 */
strrchr:
        imm8 = SSESTR_PACKED_UBYTE | \
               SSESTR_EQUAL_ANY    | \
               SSESTR_UNCHANGED    | \
               SSESTR_LASTBIT

        movd    %eax, %xmm0     # xmm1 := string of length 1 contains char c
        xor     %eax, %eax      # eax  := NULL

    L(mainloop):
        add $16, %esi

        # implict string length - find last occurence of c or EOS
        pcmpistri $imm8, -16(%esi), %xmm0
        # sample 1 (char found)
        #       c       -> 'c'
        #       mem     -> "cat catch scarab"
        #
        #                  baracs hctac tac
        #       IntRes2 -> 0000100010010001b
        #       ECX     -> bsr(IntRes2) = 11
        #       CF      -> 1 (IntRes2 <> 0)
        #       ZF      -> 0
        #
        # sample 2 (null found)
        #       c       -> 's'
        #       mem     -> "assembler\0"
        #
        #                  .......relbmessa <- '.' = invalid
        #       IntRes2 -> 0000000000000110b
        #       ECX     -> bsr(IntRes2) = 2
        #       CF      -> 1 (IntRes2 <> 0)
        #       ZF      -> 1 (there is a null byte)

        ja   L(mainloop)   # CF=0 and ZF=0 (no char, no null found)
        jz   L(null_found) # ZF=1 -> null byte
    L(update): # CF=1 -> position update needed
        lea -16(%esi, %ecx), %eax  # update: last char pos.
        jmp  L(mainloop)


        # XXX: use conditional moves?
    L(null_found):
        jnc  L(end)     # CF = 0, no update needed
        lea -16(%esi, %ecx), %eax  # update last char pos.
    L(end):
        ret

is_sxdigit

/* int is_sxdigit(const char* s);

   comment:
     Function test if all chars from s matches [0-9A-Fa-f]
     (sxdigit describe pattern).

   inputs:
   - %esi -- s

   result:
   - %eax (0 or 1)

   destroy:
   - %xmm0, %xmm1
 */
is_sxdigit:
        imm8 = SSESTR_PACKED_UBYTE  | \
               SSESTR_RANGES        | \
               SSESTR_NEGATED_VALID | \
               SSESTR_BITMASK

        movaps  sxdigit, %xmm1
    L(mainloop):
        add     $16, %eax

        # implict string length - test if all chars in range or EOS occured
        pcmpistrm $imm8, -16(%eax), %xmm1
        # sample 1 (not all chars match):
        #       mem   -> "10 x 1af7\0"
        #       xmm1  -> "09AZaz"
        #
        #                 .......7fa1 x 01 <- '.' = invalid
        #       IntRes1 = 0000000111100011b
        #       IntRes2 = 0000000000011100b (negated valid)
        #       CF      = 1 (IntRes2 <> 0)
        #       ZF      = 1 (null in mem)
        #
        # sample 2 (all chars match, no null byte):
        #       mem   -> "5afffefff00011fb"
        #       xmm1  -> "09AZaz"
        #
        #                 bf11000fffefffa51
        #       IntRes1 = 1111111111111111b
        #       IntRes2 = 0000000000000000b (negated valid)
        #       CF      = 0 (IntRes2 == 0)
        #       ZF      = 0
        #
        # sample 3 (all chars match):
        #       mem   -> "5afffefff\0"
        #       xmm1  -> "09AZaz"
        #
        #                 .......fffefffa51 <- '.' = invalid
        #       IntRes2 = 0000000111111111b
        #       IntRes2 = 0000000000000000b
        #       CF      = 0 (IntRes2 == 0)
        #       ZF      = 1 (null byte in mem)

        ja      L(main_loop)    # CF=0 and ZF=0 (all match, no EOS)

    L(end_of_string):
        mov     $1,   %eax
        mov     $0,   %edx
        cmovc   %edx, %eax      # eax := CF ? 0 : 1
        ret

strtolower

/* void strtolower(const char* s);

   comment:
     Function modify s; encoding of string is ASCII.
     Initial value of eax (see line marked with X)
     determine action preformed by function:
     * 0x00005a41 ("AZ")    - to lower
     * 0x00007a61 ("az")    - to upper
     * 0x7a615a41 ("azAZ")  - swap case

   inputs:
   - %eax -- s
 */
strtolower:
        imm8 = SSESTR_PACKED_UBYTE  | \
               SSESTR_RANGES        | \
               SSESTR_UNCHANGED     | \
               SSESTR_BYTEMASK

        mov     $0x00005a41, %edx       # 0x5a41 := 'AZ' (X)
        movd    %edx, %xmm1             # xmm1 -> range [A-Z]
        movd    pb_0x20, %xmm3          # xmm3 := packed_byte(0x20)

    L(mainloop):
        movaps  (%eax), %xmm2
        add     $16, %eax

        # implict string length - make mask for chars [A-Z] or locate EOS
        pcmpistrm $imm8, %xmm2, %xmm1
        # sample:
        #       xmm2 -> "REAd SoME TEXt\0" (length 15)
        #
        #
        #                   ..tEXT EMoS dAER   <- '.' = invalid
        #       IntRest2 := 0001110110100111b
        #       xmm0     := |000000ff|ffff00ff|ff00ff00|00ffffff|
        #       CF       := 1 (IntRes2 <> 0)
        #       ZF       := 1 (null byte in mem)

        ja L(mainloop)    # CF=0 and ZF=0 (no update needed, no EOS)

    L(update):
        pand %xmm3, %xmm0 # xmm0 := |00000020|20200020|20002000|00202020|
        pxor %xmm0, %xmm2 # reset 5th bit in big letters
                          # xmm2 -> "read some text\0"
        movups %xmm2, -16(%eax) # write back modified fragment
        jnz L(mainloop)

        ret