Table of Contents

Semestrální práce

Termín odevzdání Nejlépe před 27.05.2020 23:59 CEST
Nejpozději 31.05.2020 23:59 CEST
Základní implementace 12b
Extra funkcionality až 8 bodů
Minimální počet bodů na zápočet 10
Počet uploadů 1 finální verze + případné opravy dle uvážení cvičícího (hodnotitele)
Výchozí implementace bab36prga-sem.zip
Podpora Video tutoriál (180 min), Hints
Při včasném odevzdání (první termín) lze řešit případné nedodělky do termínu finálního odevzdání. Detaily dohodněte se svým cvičícím.

Semestrální práce navazuje na implementaci HW 08, kterou rozšiřuje o výpočet fraktálu, který mapuje dynamický systém v části komplexní roviny do 2D obrázku. Konkrétně se jedná o výpočet Juliovy množiny, který je dán rekurzivní rovnicí: $$z_{i+1}= z_i^2 + c,$$ pro kterou vyšetřujeme, zdali pro nějaké zvolené komplexní číslo $c$ posloupnost čísel $z_i$ diverguje či nikoliv. Pro příslušný bod $z_0\in\mathbb{C}$ tak dostáváme posloupnosti hodnot $z_1, z_2, \ldots,z_n$ a říkáme, že bod $z_0$ patří do Juliovy množiny, pokud je posloupnost hodnot $z_1, z_2, \ldots,z_n$ omezená, tj. nediverguje. Test divergence posloupnosti můžeme imperativně otestovat pro zvolený počet prvků posloupnosti $n$ tak, že ověříme, že platí $|z_i|< 2$ pro $0 < i \le n$. Tedy v případě, že absolutní hodnota libovolného komplexního čísla $z_i$ z posloupnosti $z_i\in{z_1, z_n,\ldots, n}$ je větší nebo rovna 2 posloupnost diverguje a bod $z_0$ leží vně Juliovy množiny. Přesnost určení zdali $z_0\in\mathbb{C}$ patří nebo nepatří do Juliovy množiny záleží na počtu testovaných prvků posloupnosti ${z_1, z_2, \ldots, z_n}$. Pro větší hodnoty $n$ může být výpočet náročnější, hodnota ale bude přesnější. Dále můžeme využít hodnotu prvního konkrétního kroku $z_k$, $0<k\le n$, pro který není splněna podmína $|z_k|<2$ využít k obarvení odpovídajícího bodu komplexní roviny a vytvořit tak barevný obrázek Juliovy množiny např.

Uvedený obrázek odpovídá zobrazení části komplexní roviny definované intervaly mezi body $-1.6-1.1j$ a $1.6+1.1j$ na obrázek o rozměru 640$\times$480 pro $c=-0.4 +0.6j$ a $n=60$. Body patřící do Juliovy množiny jsou zobrazeny černě a body, které do množiny nepatří, jsou označeny barvou podle příslušné hodnoty $k$, při kterém bylo poprvé detekováno, že bod $z_0$ do množiny nepatří, tj. $|z_k|>2$ pro konkrétní $z_0$. Barva je vypočtena po složkách RGB podle

kde $t$ je podíl $k/n$, tj. číslo od 0 do 1.

Nejzajímavější části Juliovy množiny jsou tak její okraje a zmenšením části komplexní roviny, ze které vybíráme komplexní čísla $z_0$ můžeme přibližit okraj např.

Například pro obdélníkový výřez komplexní roviny definovaný body $a,b\in\mathbb{C}$ mapovaný do obrázku s rozlišením $320\times 240$ získáme:

$a=-0.5-0.5j$, $b=0.5+0.5j$ $a=0.01+0.2j$, $b=0.05+0.25j$

Komunikační protokol

Modul aplikace, která simuluje Nucleo řídící desku, počítá konkrétní část fraktálu podle zadaných parametrů, které jsou z ovládací aplikace zasílány po rouře (pipe). Vlastní výpočet probíhá tak, že řídicí aplikace zašle zprávu MSG_COMPUTE, která specifikuje část výpočtu tzv. chunk ID (cid). Výchozím bodem obdélníkového výřezu pro výpočet je dán komplexním číslem $re + im j$ a počtem hodnot (sloupců) na reálné ose (z leva do prava) a počtem hodnot (řádku) na imaginární ose (zhora dolů). Krok sloupce a řádku, spolu s hodnotou komplexního čísla $c$ a počtem kroků je součástí zprávy MSG_SET_COMPUTE. Definice jednotlivých zpráv odpovídá definici složeného typu struct message v souboru message.h 

// Definition of the communication messages
typedef enum {
   MSG_OK,               // ack of the received message
   MSG_ERROR,            // report error on the previously received command
   MSG_ABORT,            // abort - from user button or from serial port
   MSG_DONE,             // report the requested work has been done
   MSG_GET_VERSION,      // request version of the firmware
   MSG_VERSION,          // send version of the firmware as major,minor, patch level, e.g., 1.0p1
   MSG_STARTUP,          // init message (id, up to 9 bytes long string, cksum)
   MSG_SET_COMPUTE,      // set computation parameters
   MSG_COMPUTE,          // request computation of a batch of tasks (chunk_id, nbr_tasks)
   MSG_COMPUTE_DATA,     // computed result (chunk_id, result)
   MSG_NBR
} message_type;
 
#define STARTUP_MSG_LEN 9
 
typedef struct {
   uint8_t major;
   uint8_t minor;
   uint8_t patch;
} msg_version;
 
typedef struct {
   uint8_t message[STARTUP_MSG_LEN];
} msg_startup;
 
typedef struct {
   double c_re;  // re (x) part of the c constant in recursive equation
   double c_im;  // im (y) part of the c constant in recursive equation
   double d_re;  // increment in the x-coords
   double d_im;  // increment in the y-coords
   uint8_t n;    // number of iterations per each pixel
} msg_set_compute;
 
typedef struct {
    uint8_t cid; // chunk id
    double re;    // start of the x-coords (real)
    double im;    // start of the y-coords (imaginary)
    uint8_t n_re; // number of cells in x-coords
    uint8_t n_im; // number of cells in y-coords
} msg_compute;
 
typedef struct {
   uint8_t cid;  // chunk id
   uint8_t i_re; // x-coords 
   uint8_t i_im; // y-coords
   uint8_t iter; // number of iterations
} msg_compute_data;
 
typedef struct {
   uint8_t type;   // message type
   union {
      msg_version version;
      msg_startup startup;
      msg_set_compute set_compute;
      msg_compute compute;
      msg_compute_data compute_data;
   } data;
   uint8_t cksum; // message command
} message;

Inicializační zpráva MSG_STARTUP může být například definována jako 

message msg = { .data.startup.message =  { 'P', 'R', 'G', 'A', '-', 'S', 'E', 'M', '1' } };
vhodnější je však například zakódovat do zprávy identifikaci autora, např. ČVUT username.

Výměna zpráv a průběh komunikace

Komunikace probíhá pomocí zápisové a čtecí roury.

V případě zaslání zprávy MSG_SET_COMPUTE nebo i MSG_COMPUTE jsou nastaveny nové hodnoty a výpočet pokračuje podle posledně zadaných hodnot. Kdykoliv (i v případě běžícího výpočtu) je možné si vyžádat verzi aplikace Modul zasláním zprávy MSG_GET_VERSION, na kterou Modul promptně odpovídá MSG_VERSION.

Typický průběh komunikace mezi PC a Modulovou aplikací může vypadat například následovně:

Je doporučené uvažovat omezený rozsah n_re a n_im zprávy MSG_SET_COMPUTE, který spolu s bajtovou reprezentací c_id udává, jak je možné organizovat výpočet a jak velké obrázky (rozlišení) je možné aplikací počítat. Dále je doporučené omezení hodnoty $n$, aby nebyla vyšší než 200.

Aplikace Modul

Modul aplikace počítá části fraktálu, které jsou odesílány zprávami MSG_COMPUTE_DATA. Aplikace reaguje na stisk kláves:

Ovládací aplikace

Implementaci ovládací aplikace lze také založit na řešení HW 08, která vyčítá hodnoty stiknutých kláves a příslušně reaguje. Výpis stavu aplikace lze jednoduše realizovat textovým výpisem (pro základní implementací semestrální práce). Způsob ovládání není striktně předepsán a záleží na invenci řešení. Může například reagovat na stisk následujících kláves:

V průběhu běhu aplikce může program vypisovat dílčí stavy a události na standardní (chybový) výstup s nějakým jednoduchým rozlišením kategorie typu výpisu např. INFO, DEBUG, WARN, ERROR: 

"ERROR: Cannot open serial port %s\n", serial
"INFO: Create thread '%s' %s\n", threads_names[i], ( r == 0 ? "OK" : "FAIL") 
"INFO: Get version requested\n"
"INFO: Set new computation resolution %dx%d no. of chunks: %d\n", ...
"WARN: New computation parameters requested but it is discarded due to on ongoing computation\n"
"INFO: Set new computation resolution %dx%d no. of chunks: %d\n", ..
"INFO: New computation chunk id: %d for part %d x %d\n", msg.data.compute.cid, msg.data.compute.n_re, msg.data.compute.n_im
"WARN: New computation requested but it is discarded due on ongoing computation\n"
"INFO: Chunk reset request\n"
"WARN: Chunk reset request discarded, it is currently computing\n"
"WARN: Abort requested but it is not computing\n"
"WARN: received grid results is out of range of the current grid"
"ERROR: send_message() does not send all bytes of the message!\n"
"INFO: Module restarted - '%s'\n", str
"INFO: Receive ok from Module\n"
"WARN: Receive error from Module\n"
"INFO: Abort from Module\n"
"DEBUG: received results %d\n", computation.grid[idx]
"WARN: received grid results is out of range of the current grid"
"WARN: received compute data has cid %d which is different from cid %d - cannot align data to the grid properly\x0a", msg->data.compute_data.cid, computation.cid
"WARN: Module sends new data without computing \n"
"INFO: Module reports the computation is done computing: %d\n", computation.computing
"INFO: Prepare new chunk of data cid: %d\n", msg_send.data.compute.cid
"ERROR: send_message() does not send all bytes of the message!\n"
"INFO: Call join to the thread %s\n", threads_names[i]
"INFO: Joining the thread %s has been %s\n", threads_names[i], (r == 0 ? "OK" : "FAIL")
"INFO: Exit input thead %p\n", pthread_self()
"ERROR: Unknown message type has been received 0x%x\n - '%c'", c, c
"ERROR: Cannot parse message type %d\n", msg_buf[0]
"WARN: the packet has not been received discard what has been read\n"
"ERROR: Cannot receive data from the serial port\n"
"INFO: Exit serial_rx_thread %p\n", pthread_self()
"DEBUG: Write message: "

Vizualizace

Vlastní zobrazení fraktálu lze realizovat s využitím knihovny SDL a pro jednoduchost například s využitím modulu xwin_sdl.zip, který obsahuje pouze tři funkce:

S ohledem na rychlost komunikace je doporučeno v základní implementaci počítat pouze malý obrázek, např. $320\times 240$, pro který může vedle terminálového vstupu okno aplikace vypadat například

Knihovna SDL

Knihovnu SDL je doporučeno použít ve verzi 2, tj. např. sdl2-2.0.5 a potřebné adresáře s hlavičkovými soubory a knihovnami pro linkování přidat prostřednictvím nástroje sdl2-config např. přidat do Makefile: 

CFLAGS+=$(shell sdl2-config --cflags)
LDFLAGS+=$(shell sdl2-config --libs)

Hodnocení

Hodnocení implementace semestrální práce je složeno ze dvou kategorií funkcionalit: základních a dodatečných (extra). Všechny zdrojové kódy je nutné nahrát do odevzdávacího systému BRUTE a to nejpozději k termínu odevzdání. Funkčnost aplikace bude hodnocena na základě uploadovaných souborů. Kromě vlastních funkcionalit je součástí hodnocení také prokázání orientace v kódu. Hodnocení bude provedeno dle časových dispozic hodnotitele a autora/ky semestrální práce, což by ideálně mělo proběhnout v průběhu semestru, nejpozději v posledním týdnu semestru. Dle časových a prostorových dispozic může dojít k vlastnímu hodnocení až v průběhu zkouškového, proto je pro termín odevzdání rozhodující datum uploadu všech souborů do odevzdávacího systému.

Základní implementace

Zvláště hodnocené (extra) funkcionality

Zvláště hodnocené funkcionality podstatným způsobem rozšiřují možnosti aplikace a uživatelského komfortu. Níže uvedený výčet je indikativní spolu s možným bodovým ziskem a představuje vodítko jakým směrem lze aplikaci rozšířit s využitím funkcí a knihoven, které jsou nutné pro realizaci základní verze aplikace.

Maximální počet bodů za extra funkcionality je 8 bodů, tj. implementace 4 funkcionalit.