logo elektroda
logo elektroda
X
logo elektroda
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

XMega 128 - Wyszukiwanie ciągu znaków (według wzorca) w łańcuchu znaków. ASM

ASMnauka_ 21 Maj 2017 07:26 2367 20
  • #1 16487415
    ASMnauka_
    Poziom 15  
    Cześć
    Napotkałem następujący problem.
    Otóż napisałem małego potworka, który działa prawie idealnie.
    Oto on:
    Kod: VB.net
    Zaloguj się, aby zobaczyć kod
    Prawie idealnie dlatego, że gdy napotka znak ze wzorca wcześniej, program się sypie.
    Skonstruowałem też drugiego potworka.
    Wygląda on tak:
    Kod: VB.net
    Zaloguj się, aby zobaczyć kod
    W tym przypadku też nie działa jak należy.
    Pętla ta jest odpowiednikiem pętli FOR NEXT STEP 4 więc czyta co cztery bajty.
    Zwracam się z prośbą o wskazanie miejsca, gdzie popełniam błąd.
    Ewentualnie o wskazówki, jak poprawić te potworki, by działały poprawnie.
    Pozdrawiam
  • #2 16492963
    BlueDraco
    Specjalista - Mikrokontrolery
    Napisać i przetestować algorytm w C, potem (jeśli musisz) przenieść na asembler i sprawdzić, o ile byłeś gorszy od kompilatora.
  • #3 16493960
    Freddie Chopin
    Specjalista - Mikrokontrolery
    BlueDraco napisał:
    Napisać i przetestować algorytm w C

    Tylko po co, skoro jest http://en.cppreference.com/w/c/string/byte/strstr ?

    Przykładowa implementacja - https://sourceware.org/git/gitweb.cgi?p=newli...0bce0af37fc242e24e94275346089cb6ef056;hb=HEAD
  • #4 16500549
    trol.six
    Poziom 31  
    ASMnauka_ napisał:
    Prawie idealnie dlatego, że gdy napotka znak ze wzorca wcześniej, program się sypie.

    I nic dziwnego, w końcu typowe wyszukiwanie ciągu znaków jest dwuetapowe.
    1. Najpierw wyszukujesz czy początek wzorca jest w wyszukiwanych danych.
    2. A następnie sprawdzasz czy ciąg znaków od tego znaku do końca wzorca jest identyczny.
    3. Jeśli nie jest identyczny, szukasz dalej punkt 1

    Czyli np. tworzysz dwie funkcje SZUKAJ (punkt 1) oraz TESTCMP (punkt 2)
    Musisz też informować program wywołujący aby wiedział czy dana została znaleziona.
  • #5 16500552
    ASMnauka_
    Poziom 15  
    trol.six napisał:
    1. Najpierw wyszukujesz czy początek wzorca jest w wyszukiwanych danych.
    Odpowiada za to ten programik:
    Kod: VB.net
    Zaloguj się, aby zobaczyć kod

    trol.six napisał:
    2. A następnie sprawdzasz czy ciąg znaków od tego znaku do końca wzorca jest identyczny.
    To już nie jest takie proste.
    Niestety moim zdaniem oprócz sprawdzenia czy oba znaki są takie same należy również sprawdzić umiejscowienie każdego znaku w ciągu znaków (numer indeksu).
    Bez sprawdzenia indeksu znaku program się posypie.
    Indeksy kolejnych znaków muszą się różnić jedynie o jeden.
    Oto wynik porównania czterech znaków bez sprawdzenia indeksów znaków:
    Kod: VB.net
    Zaloguj się, aby zobaczyć kod
    Jak widzisz pierwszy znak ma indeks o numerze 8384, następne mają indeks zawsze o jeden większy.
    Różnica między pierwszym a drugim znakiem wynika z faktu, iż pierwszy znak jest wcześniej od tego samego znaku w ciągu znaków.
    trol.six napisał:
    3. Jeśli nie jest identyczny, szukasz dalej punkt 1
    Baedzo ważna uwaga.
  • #6 16500562
    Konto nie istnieje
    Konto nie istnieje  
  • #7 16500916
    ASMnauka_
    Poziom 15  
    niveasoft dziękuję za pomoc.
    Ta funkcja w Bascom - ie dziwacznie działa.
    Mianowicie zwraca numer pierwszego znaku w ciągu.
    A nie o to mi chodzi.
    W tym przypadku trzeba jeszcze dodać długość szukanego ciągu i dodać do indeksu pierwszego znaku.

    W przypływie emocji naskrobałem programik zastępujący znaki.
    oto on:
    Kod: VB.net
    Zaloguj się, aby zobaczyć kod

    Nie mam pojęcia jak to jest skontruowane w Bascom-mie.
    Lecz ten przykład działa idealnie według moich potrzeb.
  • #8 16501007
    Konto nie istnieje
    Konto nie istnieje  
  • #9 16501061
    ASMnauka_
    Poziom 15  
    niveasoft napisał:
    Cieszę się że udało się osiągnąć to czego od programu wymagasz :D
    Nie wiem, czy ten uśmieszek jest ironicznym wyrazem moich starań, czy też nie.
    Jednak dziękuję za odpowiedz.
    Jednak najbardziej mnie irytują wypowiedzi typu:
    Napisać i przetestować algorytm w C, potem (jeśli musisz) przenieść na asembler i sprawdzić, o ile byłeś gorszy od kompilatora.
    Czy ja kiedykolwiek pisałem o języku C ???A po za tym jakim specjalistą w dziedzinie mikro kontrolerów uważa się autor tego zdania, skoro nie zna podstaw języka ASM ??? Owszem, jeżeli czuje się specjalistą w języku C proszę bardzo.
    Lecz tego typu wypowiedzi mijają się z tematem :(
    Nie omieszkam przetestować Twojego przykładu.
  • #10 16501137
    BlueDraco
    Specjalista - Mikrokontrolery
    Jako autor zacytowanego zdania wyjaśniam:

    Programuję w C od ponad 30 lat. Nie wiem, skąd pojawił Ci się pomysł, że nie znam języków asemblerowych - ja nic takiego nie napisałem.
    Programowałem i programuję (coraz mniej) w kilkunastu asemblerach, o 3 lata dłużej niż w C. Napisałem w tym czasie kilkaset tysięcy linii kodu asemblerowego, w tym dwa projekty po ponad 50 tysięcy linii i kilkadziesiąt projektów mniejszych - do 5 tysięcy linii. Mogę więc chyba napisać, że znam i języki asemblerowe, i możliwości kompilatorów języków wysokiego poziomu. Wydaje mi się również, że potrafię poprawnie dobierać narzędzia pracy, czyli języki programowania, do zadań projektowych.

    Masz problem z algorytmem - zapisz go w języku wysokiego poziomu i przetestuj. To jest poprawna metoda postępowania z projektami asemblerowymi, o ile w ogóle zachodzi potrzeba użycia asemblera. Wydaje Ci się, że potrafisz napisać w asemblerze kod lepszy, niż wygenerowany przez optymalizujący kompilator? No to Ci się wydaje. Ciekawe, że tak bardzo boisz się weryfikacji swojego wierzenia, że nawet nie dopuszczasz możliwości wykonania takiego eksperymentu.

    Z moim doświadczeniem mogę powiedzieć, że na ogół potrafię napisać w asemblerze kod lepszy od kompilatora. Na ogół, bo niekiedy kompilator na x86 albo (zwłaszcza) ARMa potrafi sprawić mi niespodziankę.
    Nie oznacza to bynajmniej, że obecnie piszę cokolwiek na serio w którymś z tych asemblerów. Nie piszę, bo nie ma to sensu. Zdarza mi się niekiedy popełniać niewielkie procedury w asemblerze, gdy mam przekonanie, że będę lepszy od kompilatora, np. przy dziwnych operacjach bitowych na ARM lub w przypadku użycia jednostek wektorowych na x86. Od wielu lat nie programuję już architektur, w których kod asemblerowy był zawsze lepszy od tego, co robił kompilator, czyli 51 i PIC16. Gdybym miał te zabytki programować, zapewne pisałbym w asemblerze.
    AVR jest z jednej strony świetnie przystosowany do współpracy z kompilatorem. Z drugiej strony, kiedy jeszcze robiłem coś na AVR (skończyłem z 5 lat temu), niekiedy okazywało się, że kod generowany przez kompilator był żenująco słaby, zupełnie nie wiadomo dlaczego. Podejrzewam, że przez tych 5 lat sporo się poprawiło w kompilatorach. Mógłbyś to sam sprawdzić, gdybyś się nie bał, że wyjdzie, że nie masz racji.

    Zdarzało mi się w projektach w C obsługiwać przerwania na AVR z częstotliwościami 16..39 kHz, a na ARM - do 600 kHz (procedury obsługi miały po 30..150 linii kodu, więc nie było to "ustawienie znacznika"). Ciekawe, ile musiałbyś się napracować w asemblerze, by osiągnąć takie częstotliwości przerwań (oczywiście jest to możliwe, tylko ile czasu zajmie napisanie i odpluskwienie takiego kodu)?
  • #12 16501694
    tmf
    VIP Zasłużony dla elektroda
    @BlueDraco Jakkolwiek masz rację, to jednak funkcje biblioteki standardowej zawierają relatywnie dużo asemblera i to często dopieszczanego przez pokolenia programistów. Akurat funkcje wyszukiwania ciągów są dobrym przykładem, kiedy w zależności od pewnych założeń i sprzętu można sporo poprawić. Np. w powyższym wątku można się zastanowić skąd pochodzi wyszukiwany ciąg? Bo jeśli np. z jakiegoś urządzenia seryjnego, np. UART to można funkcję wyszukiwania ciągów oprzeć o DMA - co prawda w XMEGA128 DMA nie potrafi wyszukiwać ciągów, ale już w XMEGA E5 potrafi. Taka optymalizacja może być sensowna, szczególnie jeśli procek w międzyczasie zasypia. Wtedy DMA go wybudzi po odebraniu określonego ciągu znaków. Oczywiście to są sytuacje wyjątkowe, a nie typowe. Autor powinien też zacząć od algorytmu, a potem dopiero bawić się jego implementacją w asemblerze. Rozpoczynanie od razu od implementacji algorytmu, który jest w trakcie powstawania, szczególnie w asemblerze, IMHO nie jest optymalnym sposobem postępowania.
  • #13 16501721
    BlueDraco
    Specjalista - Mikrokontrolery
    Czy ja gdzieś napisałem, że programowanie w asemblerze nie ma racji bytu? Chyba wręcz przeciwnie - ma ono sens, gdy potrafimy zrobić coś, czego kompilator nie potrafi tak dobrze jak my. Wydaje mi się jednak, że w tym wątku ten przypadek nie zachodzi. Mam również niejasne wrażenie, że to ja pisałem o testowaniu algorytmu w języku wysokiego poziomu i (twórczym) porównywaniu kodu z kompilatora z kodem z naszej głowy - takiej rady, identycznej z Twoją, kol. TMF, udzieliłem wyżej. Jak widać Autor wątku jest dziwnie uczulony na standardowe praktyki postępowania... ;)

    Od kompilatora można się sporo nauczyć, m.in. pisania programów asemblerowych. Czasem przyjemnie można sobie połechtać ego, widząc, jak kompilator coś sp... No, ale taka nauka jest możliwa tylko przy założeniu, że nie boimy się porównania naszych wypocin z produkcjami kompilatora. Jest to założenie nie spełnione w przypadku kol. ASMnauka, który wyraźnie odczuwa kompleks niższości wobec kompilatora... ;)
  • #14 16502204
    trol.six
    Poziom 31  
    ASMnauka_ napisał:
    Niestety moim zdaniem oprócz sprawdzenia czy oba znaki są takie same należy również sprawdzić umiejscowienie każdego znaku w ciągu znaków (numer indeksu).

    Do czego to "niestety" się odnosi?
    Ja napisałem ogólny zarys, to jak będzie wyglądać implementacja zależy od:
    1. Typu danych ...
    2. Od języka, bo może to być asm, C ...
    3. Od widzimisię programisty. :]

    A twój program nie realizuje tego w całości.

    ASMnauka_ napisał:
    trol.six napisał:
    1. Najpierw wyszukujesz czy początek wzorca jest w wyszukiwanych danych.
    Odpowiada za to ten programik:

    Skoro masz wyszukiwanie pierwszego znaku, to pozostaje napisać sprawdzanie reszty ciągu.

    ASMnauka_ napisał:
    Bez sprawdzenia indeksu znaku program się posypie.
    Indeksy kolejnych znaków muszą się różnić jedynie o jeden.

    Umiesz użyć instrukcji lpm,Z+ to pewnie i umiesz ld,Y+. A czy indeksy przy Z też sprawdzasz czy są co jeden?

    Ponieważ może i będziesz wracał z podprogramu, to i jakieś dane które ten program używa, może będzie trzeba zapamiętać, np poprzez odłożenie ich na stos.

    Z czego ty się uczysz? Jak sam nie potrafisz wykombinować, pozostaje przeglądać przykłady innych, choćby z kompilatora.

    Umiejętność programowania, to umiejętność operowania na danych. Musisz nauczyć się myśleć jakie dane masz i co z danymi chcesz zrobić. Czy wystarczy ci i jakich użyć zmiennych do algorytmu. Kod (czy to asm czy C) to tylko wynik wtórny.
    Nic ci nie da stwierdzenie użyj instrukcji ld,Y+ skoro np kompilator zrobi np lds,0x0100 , i też będzie działać. A inny programista powie ci że zmienną to on załaduje do rejestru r14. Tak samo jest z instrukcjami skoków. A takie małe pice to nie mają lpm i też czasem trzeba jakoś te dane odczytać.

    BlueDraco napisał:
    Masz problem z algorytmem - zapisz go w języku wysokiego poziomu i przetestuj. To jest poprawna metoda postępowania z projektami asemblerowymi, o ile w ogóle zachodzi potrzeba użycia asemblera.

    A właśnie że nie tak prosto jest napisać szybki i właściwy kod w C.
    To też wymaga poza podstawami, troche doświadczenia. Pomijam już sam aspekt algorytmu.
    To mając już doświadczenie, trudno napisać fatalny kod.

    PIC'e mają kilka kompilatorów. Jeśli chodzi o XC w wersji darmowej, to pisząc własne funkcje działa on całkiem znośnie. Choć nie zadowoli programistę który chce z mikrokontrolera wycisnąć max wydajności.
  • #15 16505212
    ASMnauka_
    Poziom 15  
    Dopisałem porównanie indeksów zmiennej.
    Jednak nie działa jak należy :(
    Teraz wygląda to tak:
    Kod: AVR assembler
    Zaloguj się, aby zobaczyć kod

    W rejestrze R30+R31 mam wynik dzielenia.
    I teraz jest problem dlaczego przy pierwszym odejmowaniu wynik jest równy 1, skoro różnica między adresami jest większa od 1.
    Adresy zmiennych to:
    8244
    8385
    8386
    8387
    Jak widać różnica pomiędzy adresem pierwszym i drugim wynosi 141.
    Nie mam pojęcia gdzie popełniłem błąd.
    Proszę o pomoc.
  • #16 16505510
    BlueDraco
    Specjalista - Mikrokontrolery
    Ewindentnie nie radzisz sobie z algorytmem.żadne indeksy ani ich odejmowanie nie są tu potrzebne. To jest do zrobienia w dwóch zagnieżdżonych pętlach, przy użyciu czterech wskaźników/adresów, w tym jednego stałego - początku szukanego wzorca. Jedyną potrzebną 16-bitową operacją arytmetyczną jest inkrementacja wskaźnika. Gdybyś skorzystał z rady Freddiego i zajrzał do wzorcowego kodu strstr() w C, nie tworzyłbyś takich potworków.
  • #18 16505895
    trol.six
    Poziom 31  
    ASMnauka_ napisał:
    Jednak nie działa jak należy :(

    Tak się nie pisze algorytmów, szczególnie na etapie nauki. Zaczynasz od danych i algorytmu, a nie od kodu.
    Przykład (mam nadzieje że prawidłowy):

    1. pobierasz pierwszą daną ciągu
    2. pobierasz pierwszą daną wzorca
    3. porównujesz, jeśli równe skok do 7
    4. pobierasz następną daną ciągu
    5. jeśli ciąg się kończy, nie ma danej, koniec
    6. porównujesz, jeśli różna skok do 4

    7. zapamiętujesz miejsce ciągu (np do rejestrów r14,r15) i jeśli trzeba początek wzorca
    8. pobierasz następną daną ciągu
    9. pobierasz następną daną wzorca
    10. jeśli wzorzec się kończy, znalazleś, początek jest w r14,r15 koniec
    11. porównujesz, jeśli równe skok do 8
    12. przypominasz sobie poczatek ciągu (odczytujesz np z r14,r15) i jeśli trzeba danych
    13. skok do 4

    I takie opisy powinieneś mieć przy kodzie, a nie takie jak:

    ld R16 , X+ ; załaduj znak ze zmiennej do rejestru R16

    Przecież każdy kto zna asm, wie że powyższa instrukcja wpisuje dane do r16.
    Tylko jakie dane? Wzorca czy ciągu? A może jeszcze inne? No z opisu nie wiadomo.
    Bez tego nikt ci nie pomoże nawet jak będzie chciał.

    Podstawa to wiedzieć:
    - gdzie są dane
    - jakie te dane są
    - co z danymi robić
    - jaki ma być wynik operacji

    Danymi nie jest "znak zmiennej", bo może chodzi o znak plus czy minus? ale np. "pierwsza dana wzorca"

    Kolejna rzecz, to kolejność pobierania danych i testowania czy dane sie kończą czy też nie.
    A to zależy od typu danych, a tych również nie podałeś.
    Założyłem że używasz ciągów zakończonych zerem.

    Wniosek, przy programowaniu istotna jest każda, ale to absolutnie każda drobnostka.


    Piotrus_999 napisał:
    To jest skutek uczenia się jako pierwszego języka asemblera. Ja nie neguję sensu znajomości, ale dopiero jak się trochę nauczy wymyślać i kodować algorytmy w czymś wyższego poziomu.

    Nonsens, trzeba mieć po prostu dobre źródło nauki.

    Faktem jest że wraz ze złożonością algorytmu, w C piszę się sprawniej,
    nie trzeba myśleć o pamiętaniu gdzie dane są, że należy je skądś odczytać itp. itd.
    I to jest główny powód przemawiający za pisaniem w C
    No, chyba że ktoś jest mistrzem asemblera.
    Zdaje się, nawet są jakieś kody mp3 w asm na x86.

    Poza tym, nie każdemu dany język musi spasować. Mi np. C++ kompletnie nie podchodzi.
  • #19 16510011
    ASMnauka_
    Poziom 15  
    BlueDraco, przepraszam, jeżeli Cię uraziłem.
    Owszem dla Ciebie nie jest to problemem, lecz ja się uczę.
    Proszę zrozum, nie chcę powielać wzorców innych.
    Pisząc tego potworka sądziłem, iż porównanie indeksu zmiennej, oraz stałej, następnie sprawdzenie różnicy pomiędzy nimi będzie dobrym rozwiązaniem.
    Freddie Chopin dziękuję za przykład.
    Piotrus_999 niestety żadna odmiana języka C mi nie "podchodzi".
    Wolę się uczyć ASM, aniżeli iść na prosto w Basco-mie.
    trol.six Serdecznie dziękuję na na prowadzenie na dobrą ścieżkę.
    Nie omieszkam skorzystać z Twych porad.
    Podsumowanie:
    Panowie, zrozumcie, że ja się uczę.
    Pozdrawiam osoby które potrafią mi, oraz innym użytkownikom Elektrody pomóc.
  • #20 16510062
    Konto nie istnieje
    Konto nie istnieje  
  • #21 16518695
    trol.six
    Poziom 31  
    Piotrus_999 napisał:
    W C to będzie 15 linijej kodu prymitywnego i 25 optymalnego. Ciekawe ile zajmie Ci napisanie takiej prościzny w asm.

    Piotrus_999 napisał:
    Każdy ma prawo się katować na sposób przez siebie wybrany :)

    Przyznaje ci racje i to podwójnie, :)
    1. Warto uczyć się C i innych języków, myśląc o programowaniu w szerszym kontekście.
    2. Twoje heroiczne wspieranie potrzebujących na forum to też jakaś forma katowania ;)

    Poza tym ktoś kto programuje więcej i poważniej w asm, ma gotowce, czy w postaci funkcji, czy też w postaci makr. Za to w C można skorzystać często jeszcze z gotowców producenta (choć czasem i w asm są przykłady), czy w ogóle znaleźć coś w sieci :) Z tym że z jakością takiego kodu różnie bywa ;)

    ASMnauka_ napisał:
    trol.six Serdecznie dziękuję na na prowadzenie na dobrą ścieżkę.

    Rzuciłem kilkoma uwagami. Ale w kwestii dobrej drogi myśle wróżki mają większe kompetencje. :]

    ASMnauka_ napisał:
    niestety żadna odmiana języka C mi nie "podchodzi".

    C jest bliski asemblerowi w podstawowych operacjach. Przykładowo dla liczby 8-bitowej konstrukcja C:

    w asemblerze może wyglądać np tak:
    ld r15,Z+
    sts 0x0200,r15 ;czasem nawet bez tej instrukcji

    W przypadku liczb typu uint32_t (32 bitowej) konstrukcja C zostaje ta sama, zmienia się tylko typ zmiennej, a przykładowy kod asm:
    ld r15,Z+
    sts 0x0200,r15
    ld r15,Z+
    sts 0x0201,r15
    ld r15,Z+
    sts 0x0202,r15
    ld r15,Z+
    sts 0x0203,r15
    

    Inną zaleta kodu C, to przenośność pomiędzy architekturami. Z tym, że czasem są drobne niuanse.
REKLAMA