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

[x][C - AVR STUDIO] Search ROM 1-Wire; krótki i uniwersalny

gdL 08 Wrz 2010 19:17 3984 17
  • #1 8489638
    gdL
    Poziom 27  
    Widziałem tu sporo algorytmów Search ROM, na magistrali 1-Wire. Na dobrą sprawę, żaden nie był uniwersalny. Zacząłem się zastanawiać nad własnym, który jednocześnie byłby "zwięzły".

    Napisałem poglądowo, coś takiego. To tylko szkic (pseudokod), nie sprawdzałem, bo póki co nie mam "kilku" układów. Czy ma to szanse działać ? Jeśli trzeba, to opiszę tekstowo o co chodzi.

    
    // char buffer[N], gdzie N to liczba urządzeń, gdzie
    // liczba rozgałęzień wynosi max. N-1,
    // zainicjowany jest z zawartością {-1,-1,-1,...,-1}
    //
    // read/write czyta/pisze na magistralę
    // tablicaRekordow[N][64] przechowuje ID układu;
    
    	for(int i=0;i<N;i++) {
    	pozycja=-1;	
    	resetPulse();
    	searchROM();
    		for(char bitNo=0;bitNo<64;bitNo++) {
    		bit=read();
    		bit_complementary=read();
    			if ((~(bit|bit_complementary))&0x01) {
    			pozycja++;
    				if(buffer[pozycja+1]==-1) {
    				buffer[pozycja]++;
    				}
    			write(buffer[pozycja]);
    		    tablicaRekordow[i][bitNo]=buffer[pozycja];
    			} else {
    			write(bit);
    			tablicaRekordow[i][bitNo]=bit;
    			} 
    		}
    		while(buffer[pozycja]) {
    		buffer[pozycja]=-1;
    		pozycja--;
    		}
    	}


    Działa tak, na przykładzie, gdzie pominięto te bity, które nie prowadzą do rozgałęzień. Zawarto jedynie bity rozgałęzień. Kluczowe jest działanie zmiany bitu z 0 na 1, jedynie na końcu konfiguracji i następujące wyczyszczenie jedynek, co pozwala kontynuować przeszukiwanie drzewa.

    
    0,0,0,0,-1
    0,0,0,0,-1
        |
        V
    0,0,0,1,-1
    0,0,0,-1,-1
        |
        V załóżmy, że pojawiło się nowe rozgałęzienie
    0,0,1,0,-1
    0,0,1,0,-1
        |
        V
    0,0,1,1,-1
    0,0,-1,-1,-1
    


    Kod wydaje się [wstępnie] spełniać postulaty.
  • #2 8499999
    sulfur
    Poziom 24  
    Jeśli kolega ma zamiar przechowywać 64 bity w 64 bajtach to nie ma mowy o uniwersalności. Nie rozumiem pojęcia "zwięzły". Nie ma konkretnego kodu, więc nie bardzo jest o czym dyskutować. Nie oceniam.
  • #3 8500064
    gdL
    Poziom 27  
    Myślałem o samym rozwiązaniu przeszukiwania drzewa, nie optymalizacji pod kątem prędkości i objętości samych danych wynikowych. To jest już końcowa faza optymalizacji i nie jest taka trudna, bo identyczna w zasadzie dla każdego algorytmu.
  • Pomocny post
    #4 8500104
    tmf
    VIP Zasłużony dla elektroda
    Mało to uniwersalne i masz pewne błędy. Po pierwsze tablica ma być nie 64-bajtowa, a 64-bitowa, czyli 8-bajtowa. Poza tym CRC nie trzeba przechowywać, bo go można wyliczyć. Uniwersalna też nie jest, bo trzeba z góry wiedzieć ile można maksymalnie mieć urządzeń, bo tablice nie są strukturami dynamicznymi. Więc trzeba by to przerobić na listę. No i to nie zadziała, bo zapomniałeś, że w momencie "rozgałęzienia", czyli kiedy są dwa urządzenia różniące się bitem na danej pozycji to kontynuujemy skanowanie jednego z nich do końca, po czym musimy wrócić do początku, wysłać bity aż do tej pozycji i kontynuować skanowanie. To najprościej zrobić rekurencyjnie - funkcja się znacznie upraszcza, a i obciążenie stosu biorąc pod uwagę ilość urządzeń nie jest duże.
    Ale próbuj :) Jak już skończysz to pokaż wyniki. Jeśli napiszesz lepszą procedurę niż moja (której póki co nie podaję) to stawiam piwo :)
  • #5 8500131
    sulfur
    Poziom 24  
    tmf napisał:
    Uniwersalna też nie jest, bo trzeba z góry wiedzieć ile można maksymalnie mieć urządzeń, bo tablice nie są strukturami dynamicznymi. Więc trzeba by to przerobić na listę.


    Argument w mojej ocenie całkowicie chybiony jeśli chodzi o uniwersalność. Subiektywnie rzecz ujmując nieekonomiczne jest robienie dynamicznego zarządzania pamięcią, gdy do dyspozycji jest 1-8k SRAM. Zatem w tej kwestii rozwiązanie proponowane przez autora wydaje się być rozsądne.
  • #6 8500147
    gdL
    Poziom 27  
    Cytat:
    wysłać bity aż do tej pozycji i kontynuować skanowanie.


    Być może czegoś nie doczytałem, albo jest tutaj pewien skrót myślowy. Za drugim razem postępujemy tak samo jak za pierwszym, do momentu rozgałęzienia, po czym w miejscu rozgałęzienia wstawiamy bit przeciwny do wstawionego za pierwszym razem. Przynajmniej tak ma działać mój algorytm, jeśli dobrze zrozumiałem dokumentację 1Wire.
  • #7 8500322
    tmf
    VIP Zasłużony dla elektroda
    Dobrze zrozumiałeś, problem w tym, że twój program tak nie robi.
    sulfur - nie trzeba robić dynamicznego zarządzania pamięcią - ono już jest :) Pytanie, czy dodatkowe dwa bajty na wskaźnik rekompensują użycie dynamicznej alokacji pamięci - IMHO tak, gdyż jeśli zadeklaruję tablicę chociażby tylko z zapasem jednego urządzenia 1-wire, to tracę 8 bajtów - równowartość 4 pozycji na liście alokowanej dynamicznie.
  • Pomocny post
    #8 8500414
    sulfur
    Poziom 24  
    Zaczekaj bo nie wiem czy dobrze zrozumiałem. Lista przeważnie składa się ze wskaźnika do następnego elementu tego samego typu (w tym wypadku moim zdaniem 2 bajty) oraz wskaźnika do danych (jakieś struktury, moim zdaniem w tym wypadku 2 bajty) co daje razem 4 bajty. Chyba, że ma kolega na myśli wbudowanie wskaźnika do następnego elementu w strukturze przechowującą ROMKOD (ten adres o który się tutaj rozchodzi). Jeśli tak wtedy faktycznie jest to 2 bajty, a rozumowanie jest prawidłowe.

    A teraz dlaczego subiektywnie uważam to za zbędne rozwiązanie ? Otóż, mając 1k RAMu aby to zaalokować coś musi być wolne. Realnie patrząc trzeba pamiętać, że te 10 (8+2), 20 (16+4), 30 itd bajtów trzeba w pamięci zostawić (czyli nie można jej wykorzystać na jakieś niedynamiczne dane). Jeśli zatem dany kod jest jedynym w całym programie, to taka operacja jest warta funta kłaków. Przechodząc do sedna, w mojej ocenie lepiej jest określić docelową ilość urządzeń obsługiwanych na magistrali i przewymiarować ją o jedną czy dwie sztuki, niż bawić się w dynamiczną alokację.

    Nie udowadnia to w żadnym stopniu, że moja racja jest jedyna i najlepsza. Przedstawia tylko mój punkt widzenia.
  • #9 8500542
    tmf
    VIP Zasłużony dla elektroda
    Oczywiście myślałem o sytuacji w której przechowujemy tylko wskaźnik do następnej pozycji, bez wskaźnika na dane - nie jest on potrzebny, gdyż dane są o stałej długości. Można to dodatkowo zoptymalizować, wykorzystując fakt, że na małych procesorkach do adresacji SRAM wystarczy tylko 8-bitów, można też zamiast adresu bezwzględnego przechowywać offset. Oczywiście dynamiczna alokacja pamięci rodzi pewne problemy i trzeba się pilnować, żeby pamięci nie zabrakło, problem ten częściowo rozwiązuje statyczna alokacja pamięci, ale tylko częściowo, bo przecież zmienne lokalne są w pewnym sensie alokowane dynamicznie (z tym, że na stosie a nie na stercie). Oczywiście nie twierdzę, że któraś z tych metod jest perfekcyjna i dobra w każdej sytuacji. Każda ma wady i zalety. Niemniej przyznasz, że brak założenia co do ilości urządzeń 1-wire jest bardziej uniwersalny, niż rozwiązanie w którym takie założenie występuje :)
    A BTW, dlatego właśnie kocham język C. Stworzyłbym po prostu klasę przechowującą dane w dwóch wersjach - dynamicznej i statycznej. Użytkownik by sobie sam decydował którą zastosować.
  • #10 8500653
    sulfur
    Poziom 24  
    tmf napisał:
    Niemniej przyznasz, że brak założenia co do ilości urządzeń 1-wire jest bardziej uniwersalny, niż rozwiązanie w którym takie założenie występuje :)


    Brak założenia przy pisaniu klasy/struktury/funkcji obsługi tak. Przy pisaniu konkretnego programu wykorzystującego powyższą już takie założenie można uczynić.

    tmf napisał:
    A BTW, dlatego właśnie kocham język C. Stworzyłbym po prostu klasę przechowującą dane w dwóch wersjach - dynamicznej i statycznej. Użytkownik by sobie sam decydował którą zastosować.


    To jest najbardziej uniwersalne rozwiązanie, jakie mogę sobie wyobrazić w tej chwili.
  • #11 8514495
    gdL
    Poziom 27  
    Napisałem powyżej wspomnianą funkcję i sprawdziłem ją z 2 czujnikami (działa). Więcej nie mam, byłbym zobowiązany, gdyby ktoś ją sprawdził z >2.

    
    ///////////////////////////////////////////////////////
    //Szuka urzadzen 1Wire/////////////////////////////////
    // char buffer[N], gdzie N to liczba urządzeń, 
    // zainicjowany jest z zawartością {0,0,0...,0}
    // tablicaRekordow[N][8] przechowuje ID układu;
    ///////////////////////////////////////////////////////
    
    unsigned char searchROM1Wire(unsigned char tablicaRekordow[][8],char N) {
    unsigned char bit,bit_complementary,pozycja,buffer[N];
    
    for(unsigned char i=0;i<N;i++) {
    buffer[i]=0;
    }
    	for(unsigned char i=0;i<N;i++) {
    	pozycja=0;
    	if(~reset1Wire()&1) return 0;
    	sendByte1Wire(SEARCH_ROM);
    		for(unsigned char bitNo=0;bitNo<64;bitNo++) {
    		bit=readBit();
    		bit_complementary=readBit();
    			if ((~(bit|bit_complementary))&1) { 
    				if(buffer[pozycja+1]==0) {
    				buffer[pozycja]++;
    				}
    			writeBit((buffer[pozycja]-1));
    		    tablicaRekordow[i][bitNo/8]|=((buffer[pozycja]-1))<<(bitNo%8);
    			pozycja++;
    			} else {
    			writeBit(bit);
    			tablicaRekordow[i][bitNo/8]|=bit<<(bitNo%8);
    			} 
    		}
    		while(buffer[pozycja-1]==2) {
    		buffer[pozycja]=0;
    		pozycja--;
    		}
    	}
    	return 1;
    }
    //////////////////////////////////////////////////////


    EDIT: Wyjaśnię o co chodzi w tym algorytmie. Zasadniczo, uzyskiwanie 64 bitowych kodów urządzeń 1-Wire opiera się na przeszukiwaniu drzewa.

    [x][C - AVR STUDIO] Search ROM 1-Wire; krótki i uniwersalny

    Załóżmy, że wykonamy obrys naszego drzewa urządzeń w/g rysunku powyżej. Wchodząc z jednej strony i podążając wzdłuż czerwonej linii na pewno obejdziemy całe drzewo, wiedząc, że obrys jest ciągły.

    Obejście drzewa sukcesywnie składa się ze zmiany terminalnych bitów skrzyżowań i sprawdzanie, czy po zmianie nie pojawiły się kolejne. Wektor bitów skrzyżowań przechowywany jest w "buffer[N]". Wiemy, że istnieje N urządzeń, a więc N-1 skrzyżowań. N (a nie N-1) komórek jest jednak potrzebne do poprawnego działania algorytmu. buffer[N] można zoptymalizować!

    ///// OPTYMALIZACJA
    Tutaj składa się z N bajtów (N*256 stanów), a wymaga jedynie 3 stanów (N*3 stanów).

    0 - nie użyty [0,0]
    1 - stan 0 [1,0]
    2 - stan 1 [1,1]

    Najprościej zasocjować dwa wektory (np tablice char) : stan[int(N/8)+1], przechowujący bieżący wybór bitów rozgałęzień i zajetosc[int(N/8)+1], przechowujący zajętość powyższych bitów. Analogicznie [0,1] jest stanem zabronionym, oznaczałby, że istnieje bit 1 rozgałęzienia, ale nie ma rozgałęzienia. Istnienie wektora zajetosc[int(N/8)+1] pozwala na odróżnienie "nie użytego" od "stanu 0" jest kluczowe, żeby zorientować się w pozycji względem końca wektora.
    /////

    Obejście drzewa wiąże się ze zmianą jedynie ostatnich bitów. Należy "odwiedzić" sukcesywnie 0, następnie 1 w każdym z rozgałęzień, rozpoczynając od terminalnych. Zmiana stanu proksymalnych bitów jest możliwa dopiero po przeskanowaniu terminalnych!

    if(buffer[pozycja+1]==0) {
    buffer[pozycja]++;
    }


    Jeśli kolejna pozycja w buforze jest wolna(0), to bieżący stan zwiększa się o 1.
    
    0 ( "stan:0","zajętość:0") - bit rozumiany jako nie użyty
                    |
                    V
    1 ( "stan:0","zajętość:1") - wystawia stan 0 na magistralę
                    |
                    V
    2 ( "stan:1","zajętość:1") - wystawia stan 1 na magistralę
    


    Dlatego dla każdego skrzyżowania pojawi się najpierw stan 0, następnie 1. Po każdej zmianie stanu, zachodzi kontynuacja zapisywania bitów i szukania skrzyżowań.

    Przykład:

    [x][C - AVR STUDIO] Search ROM 1-Wire; krótki i uniwersalny

    
    s - wektor stanu
    z - wektor zajętości 
    
    Zaczynam skanowanie
    
    1.  s:0,z:1;  s:0,z:1;  s:0,z:0; <- 2 skrzyżowania
    2.  s:0,z:1;  s:1,z:1;  s:0,z:1;  s:0,z:0; <- po zmianie terminalnego bitu na 1 pojawiło się nowe skrzyżowanie.
    3. s:0,z:1;  s:1,z:1;  s:1,z:1;  s:0,z:0; <- zmiana terminalnego bitu na 1
    4. wyczyszczenie obu końcowych stanów s:1,z:1; na  s:0,z:0; 
    5. s:1,z:1;  s:0,z:0; <- zmiana nowego końcowego bitu na 1.
    6. wyczyszczenie terminalnego s:1,z:1;
    7. s:0,z:0; <- całe drzewo przeskanowane
    
    
    Rezultat :
    4 urządzenia (N), 3 skrzyżowania(N-1)
    


    Jeżeli ostatni bit w wektorze stanów, po przejrzeniu całej sekwencji 64 bitów, wynosi 2(s:1,z:1), oznacza to, że obie gałęzie "0" i "1" zostały przeskanowane i ten bit można zamienić na stan:0 i zajętość:0. Tę część realizuje :

    
    while(buffer[pozycja-1]==2) {
    buffer[pozycja]=0;
    pozycja--;
    }
    


    Sprawdza też, czy położony proksymalnie (bliżej początku) bit nie jest równy 1. Jeśli tak, oznacza to, że ta część drzewa również została już przeskanowana.

    UFFF. Późno, więc pewnie są błędy w opisie.

    EDIT : Ciąg dalszy optymalizacji : W tej chwili 64 bitowy kod jest przechowywany w 64 bajtach!. Należy zmodyfikować funkcję używając przesunięć bitowych tak, żeby zapisywała bez 8-krotnego nadmiaru danych. Dziś postaram się dorzucić funkcję zoptymalizowaną pod kątem zajmowanego RAM procesora na sposób opisany w poście poniżej.
  • #12 8519736
    Konto nie istnieje
    Konto nie istnieje  
  • #13 8520156
    gdL
    Poziom 27  
    10 urządzeń -> 80 bajtów do zapamiętania, to dość sporo, zwłaszcza dla niektórych uC (ATTINY). Można sukcesywnie zapisywać do EEPROMu, jednak jeśli go nie ma, to funkcja jak powyższa, jedynie lekko zmodyfikowana powinna umożliwić obsługę dużych sieci 1-Wire przy pomocy mikrokontrolerów o niewielkiej ilości pamięci RAM. Wystarczyłoby przekazać do funkcji liczbę z zakresu (0 do N-1) przy której ma się zatrzymać. Ta liczba reprezentowałaby urządzenie o adresie, który w danej chwili był skanowany. Wszystkie inne byłyby bezczynne. Wtedy możnaby nawiązać z aktywnym urządzeniem kontakt, a nawet tymczasowo zapamiętać jego 64bit ROM w celu ponownego wywołania.

    Nie wiem czy Search ROM bywa często tak używana, wiem, że w dokumentacji jest ta możliwość wspomniana.
  • #14 8520224
    Konto nie istnieje
    Konto nie istnieje  
  • #15 8520266
    gdL
    Poziom 27  
    Chętnie bym zobaczył kod/pseudokod takiej funkcji. Najlepiej, żeby to był jednak kod i do tego sprawdzony. 1Wire jest popularny i na pewno byłoby to pomocne wielu osobom.
    Moja funkcja może być łatwo zmieniona tak, że nie będzie wymagać dodatkowych danych poza tablicą tymczasową maksymalnie N-bajtów, a po optymalizacji 2*N bitów do nawigacji po drzewie. Niestety wtedy adresowanie będzie za każdym razem wymagało przeszukania i bezbłędne trafianie do danego urządzenia będzie tylko wtedy działać, jeśli pomiędzy przeszukaniami sieć nie będzie się zmieniać.
  • Pomocny post
    #16 8520304
    Konto nie istnieje
    Konto nie istnieje  
  • #17 8547077
    gdL
    Poziom 27  
    Zmodyfikowałem wyżej opisaną funkcję tak, że nie wymaga tworzenia dużej tablicy w RAM, przy okazji zmniejszeniu uległ kod wynikowy. Minusem jest CIUT dłuższa komunikacja w duzych sieciach 1-Wire.

    
    ///////////////////////////////////////////////////////
    //Szuka urzadzen 1Wire i uaktywnia N-te urzadzenie/////
    unsigned char useDevice(unsigned char useIt) {
    unsigned char bit,bit_complementary,pozycja,buffer[useIt+1];
    
    for(unsigned char i=0;i<useIt+1;i++) {
    buffer[i]=0;
    }
    	for(unsigned char i=0;i<useIt;i++) {
    	pozycja=0;
    	if(~reset1Wire()&1) return 0;
    	sendByte1Wire(SEARCH_ROM);
    		for(unsigned char bitNo=0;bitNo<64;bitNo++) {
    		bit=readBit();
    		bit_complementary=readBit();
    			if ((~(bit|bit_complementary))&1) { 
    				if(buffer[pozycja+1]==0) {
    				buffer[pozycja]++;
    				}
    			writeBit((buffer[pozycja]-1));
    			pozycja++;
    			} else {
    			writeBit(bit);
    			} 
    		}
    		while(buffer[pozycja-1]==2) {
    		buffer[pozycja]=0;
    		pozycja--;
    		}
    	}
    	return 1;
    }
    //////////////////////////////////////////////////////
    


    Możliwa dalsza optymalizacja jest opisana w poście wyżej. Działające biblioteki , wraz z przykładem zastosowania funkcji do pobrania temperatury podaję w załączniku.

    Uwaga do załącznika : Jeśli ktoś chce używać tych funkcji, to niech najpierw sobie ustawi w pliku 1WireLib.h porty wejścia/wyjścia.
  • Pomocny post
    #18 8547397
    Konto nie istnieje
    Konto nie istnieje  
REKLAMA