lezione 3.1 1602005
# ho per il momento deciso di saltare la lezione 2-esercizi, perchè devo migliorarla, e siccome ci vuole tempo (che non ho), ho deciso di mettere questa che era quasi pronta.
.
LEZIONE 3.1
DA UN PROBLEMA ALLA SOLUZIONE:
INTRODUZIONE ALLA PROGRAMMAZIONE
Siccome questo è un argomento troppo importante per essere saltato, vi tocca. Senza di esso potreste avere varie difficoltà in seguito, perciò ho deciso di affrontarlo una volta per tutte. Inoltre è un requisito nel caso in cui voleste imparare un linguaggio di programmazione ad oggetti (come il Ruby, usato in rpg).
___
Ogni giorno ci troviamo a dover risolvere dei problemi. Ad esempio scegliere cosa fare da mangiare o montare un mobile sono alcuni dei problemi quotidiani. La maggior parte di essi sono risolti istintivamente da noi; non necessariamente nel senso che usiamo l'istinto, ma che non ci riflettiamo più di tanto perché viene automatico. mentre se il problema è più difficile (montare il mobile) dobbiamo seguire le istruzioni che ci vengono fornite. anche i computer vengono utilizzati per risolvere problemi. Una volta erano prevalentemente di tipo matematico (i primi computer erano solo enormi calcolatori), mentre oggi si utilizzano per qualsiasi scopo: esempio previsioni del tempo, controllo di una centrale atomica, realizzazione di grafica. I computer però non ragionano da soli, serve qualcuno che li "istruisca" per fare tutte queste cose utili, ovvero il programmatore. Ebbene, c'è una similitudine tra il computer e noi che montiamo un mobile: seguiamo delle istruzioni scritte da altri. Questo insieme di istruzioni viene chiamato algoritmo. Si potrebbe scendere nei dettagli sulle proprietà degli algoritmi, ma dovrei andare a riprendere gli appunti di tanti anni fa(magari posso farlo per le prossime lezioni). Perciò per il momento ci concentriamo sul capire bene come funzionano questi algoritmi. Ne incontriamo a bizzeffe ogni giorno, il mondo ne è pieno. Sostanzialmente, ad ogni problema risolvibile è possibile associare un algoritmo risolutivo. Un algoritmo è una sequenza di passi (istruzioni) da eseguire per risolvere un problema.
Ad esempio per preparare la pasta ci sono dei passi (accendi il Gas, metti l'acqua, ecc) che il cuoco esegue. Anche se può sembrare naturale, in realtà una qualsiasi azione è il frutto di ben precise "istruzioni", eseguite in sequenza dal nostro cervello.
Un altro esempio di algoritmo lo avevamo visto le volte scorse, quando vi avevo detto come ricavare un puntatore o indicizzare una tabella.
la programmazione è l'"arte" di istruire i computer. per farlo serve elaborare un algoritmo che risolve il problema. in questo corso non risolveremo problemi di tipo strano, come la costruzione di un mobile o la preparazione di una pietanza, ma agli inizi saranno prevalentemente di tipo matematico per prendere confidenza, e poi sposteremo il campo verso la piattaforma GBA.
Un esempio di problema potrebbe essere: determinare il massimo tra una serie di numeri.
adesso compirò quella "brutta cosa" che è copiare wikipedia (perchè non voglio scavare nei quaderni lol) per informarvi sulle proprietà degli algoritmi per aiutarvi a capire il tipo di procedimento necessario;
- i passi costituenti devono essere "elementari", ovvero non ulteriormente scomponibili (atomicità)
- i passi costituenti devono essere interpretabili in modo diretto e univoco dall'esecutore, sia esso umano o artificiale (non ambiguità)
- l'algoritmo deve essere composto da un numero finito di passi e richiedere una quantità finita di dati in ingresso (finitezza)
- l'esecuzione deve avere termine dopo un tempo finito (terminazione)
- l'esecuzione deve portare a un risultato univoco (effettività).
In generale non esiste una sola soluzione ad un dato problema; le soluzioni potrebbero essere numerose. La programmazione consiste proprio nel trovare la strada più efficiente che conduce alla soluzione del problema in oggetto. Ecco perchè programmatori diversi possono dare diverse soluzioni (magari corrispondenti a diverse visioni del problema), anche se entrambe corrette.
"Ho capito, ma come faccio a risolvere un problema?" bisogna precisare che non esiste una "ricetta" universalmente valida, ma ci sono dei paletti che definiscono in generale un percorso da seguire per semplificare l'approccio.
Per risolvere un problema innanzitutto bisogna "prenderlo" e analizzarlo. La prima cosa da fare è stabilire cosa richiede la soluzione (output) e cosa dobbiamo conoscere in principio per poter risolverlo (input). Prendo l'esempio del massimo: cosa devo fornire al programma e cosa deve "buttar fuori"? Devo inserire alcuni numeri, e devo ricevere ancora un numero (non è detto che si utilizzino sempre solo i numeri per operare, si può anche operare sul testo, sulle immagini, ecc, così come il programma potrebbe dare quelle cose come soluzione)
Poi esistono due diversi approcci, entrambi validi, per analizzare il problema e iniziare a determinare una soluzione. il secondo è sconsigliato ai Principianti.
Top-down e Bottom-up; Come suggerisce il nome, i due sono opposti.
Nel modello top-down si formula inizialmente una visione generale del sistema, ovvero se ne descrive la finalità principale senza scendere nel dettaglio delle sue parti. Ogni parte del sistema è successivamente rifinita aggiungendo maggiori dettagli della progettazione. Ogni nuova parte così ottenuta può quindi essere nuovamente rifinita, specificando ulteriori dettagli, finché la specifica completa è sufficientemente dettagliata da validare il modello. Il modello top-down è spesso progettato con l'ausilio di "scatole nere" che semplificano il riempimento ma non consentono di capirne il meccanismo elementare.
In contrasto con il modello top-down c'è la progettazione bottom-up, nella quale parti individuali del sistema sono specificate in dettaglio, e poi connesse tra loro in modo da formare componenti più grandi, a loro volta interconnesse fino a realizzare un sistema completo. Le strategie basate sul flusso informativo bottom-up sembrano potenzialmente necessarie e sufficienti, poiché basate sulla conoscenza di tutte le variabili in grado di condizionare gli elementi del sistema.
Ricapitolando le differenze ma senza scendere troppo nei dettagli tecnici, abbiamo che
La programmazione top-down è uno stile di programmazione in cui la progettazione inizia specificando parti complesse e suddividendole successivamente in parti più piccole (divide et impera). Eventualmente, i componenti sono specificati quanto basta per la codifica ed il programma viene anche scritto.
Il bottom up prende corpo dal punto di partenza (bottom) ovvero dalla situazione iniziale; considera l'obiettivo finale, induce a costruire un percorso sequenziale organizzato in passaggi successivi in cui l'ancoraggio tra traguardi intermedi e obiettivo finale è generalmente ricercato in modo intuitivo (euristico).
come compito potreste descrivermi nel linguaggio a voi più naturale (es: italiano scritto) la risoluzione di un paio di problemi. (non copiatevi)
nella lezione successiva vedremo di
formalizzare le vostre soluzioni con opportuni metodi e iniziare la programmazione.
facile: dati 3 numeri, determinare il maggiore (SUGGERIMENTO: chiamate i numeri in qualche modo, come ad esempio A,B,C. vi aiuterà nello stabilire le
condizioni delle "sentenze")
facile: calcola l'area di un n-agono (figura geometrica regolare con n lati) (n a scelta dell'utente) (SUGGERIMENTO: vai a rivedere le formule)
facile/medio (dipende dal livello di formalismo del linguaggio usato): fornire i primi 40 multipli di 13 (SUGGERIMENTO: dovrete contare le volte...)
medio: calcolare le soluzioni reali dell'equazione ax^2+bx+c=k (SUGGERIMENTO: torna comodo un linguaggio matematico)
(in caso non abbiate ancora affrontato l'argomento a scuola, potete saltarlo)
ciao
lezione 3.2 160215
# AS: blake finisci i compiti rimanenti
.
LEZIONE 3.2
(sarà unita alla precedente)
DIAGRAMMI DI FLUSSO
Per gli amici (impropriamente) "schemi a blocchi", i diagrammi di flusso servono per rappresentare graficamente un algoritmo (sequenza di passi elementari, con alcune proprietà già viste, da seguire per risolvere un problema).
Di norma vengono introdotti parallelamente agli algoritmi, ad essi profondamente legati, in quanto sono la loro rappresentazione in un linguaggio
formale
Esistono 2 grandi tipologie di diagrammi di flusso: non strutturati e strutturati. Noi non tratteremo i primi, in quanto non di interesse per fare programmazione. Tuttavia tra i due non ci sono grosse differenze tali da implicare grossi cambiamenti nello studio e negli esercizi, ma riveste grande importanza quando bisogna applicare il risultato su un calcolatore: semplicemente, quelli non strutturati non sono riproducibili su un computer. Inoltre abituano male alla programmazione, facendo uso di tecniche errate; Perciò vi farò un favore per la vostra crescita personale, e non ve li spiegherò nemmeno.
Cominciamo
ogni schema a blocchi è composto da blocchi connessi mediante frecce. l'esecutore segue il percorso indicato dalla freccia ed esegue le istruzioni riportate all'interno dei blocchi.
ogni schema inizia e si conclude con due blocchi speciali, chiamati I (inizio) e F (fine). di norma sono rotondi (la
notazione utilizzata è ininfluente, c'è chi li fa trapezoidali, molto brutti da vedere, ma bisogna mettersi d'accordo a priori).
Questo che segue è un esempio di utilizzo dei due blocchi in uno schema stupido, inutile, che non fa niente. Ma una proprietà ce l'ha: essenzialmente è la base di ogni programma: deve avere esattamente un inizio e una o più fini. (ci sono dispute teoriche altolocate che non ci interessano sulle varie proprietà algoritmiche)
http://www.pokemonhacking.it/attachment.php?aid=382
introduciamo un altro blocco: il blocco operativo. questo blocco è di forma rettangolare, e viene usato per impartire istruzioni all'esecutore. Un esempio di istruzioni può essere "accendi il gas", "metti il bullone X nel foro Y del pianale", ecc. Devono perciò essere
interpretabili ed
eseguibili dal lettore. Noi purtroppo però ci occuperemo soltanto di problemi matematici, che sono quelli che rappresentabili meglio con gli schemi a blocchi. Un concetto importantissimo per questo blocco sono le
variabili: per farla semplice, si tratta di una sorta di "contenitori" nella memoria del computer, che possiamo usare come vogliamo per conservare le informazioni (temporanee) che ci servono.
Ad esempio, se mi chiedono di contare fino a 100, inizio dicendo "1", "2", "3" .... ovvero sto usando un po' della mia memoria a breve termine per conservare l'informazione del numero cui sono arrivato a contare.
Ma ciancio alle bande, ecco un piccolo esempio di blocco di istruzioni quadrato.
http://www.pokemonhacking.it/attachment.php?aid=383
come potete intuire, questi blocchi in serie sono le istruzioni per calcolare l'area di un trapezio! Abbiamo assegnato a 3 variabili B, b e h i valori base maggiore, base minore e altezza, che poi abbiamo usato nel calcolo dell'area. notare che ho omesso il verso delle frecce, in quanto ovvio (verso il basso).
tutti quei quadrati in serie si dice che formano una
struttura di
sequenza.
La sequenza è un insieme di blocchi contigui di tipo operativo.
http://www.pokemonhacking.it/attachment.php?aid=384
qui vedete come un insieme di rettangoli possa essere schematizzato in un solo grande rettangolo, in quanto la loro natura è la medesima. ma attenzione, non significa che spariscano, semplicemente facciamo uno "zoom-out" di un livello di generalizzazione, e i dettagli implementativi si perdono. potremmo sostituire i puntini con un generico "Area_Trapezio", nome che racchiude in sè tutti e soli i comandi scritti a sinistra.
Gli schemi a blocchi strutturati si compongono soltanto di strutture. ogni struttura è una generalizzazione di blocchi dello stesso tipo. ad esempio, poco sopra, abbiamo visto la sequenza. ne rimangono 2.
Un altro tipo di blocco è il parallelogramma: dentro di esso si mettono gli input/output, ovvero le cose che l'utente scrive (immette nel calcolatore) o il computer gli dice (verso opposto).
è talmente banale che unirò l'esempio con quelli successivi.
Il nuovo tipo di blocco per questo paragrafo è il rombo: esso permette di fare delle scelte. se durante la nostra soluzione del problema dobbiamo fare cose diverse in base alle circostanze, useremo il blocco rombo. al suo interno si mette una
condizione[i] che dovrà essere [i]valutata. se è vera, si prenderà la strada del Vero, se è falsa si prenderà la strada del Falso.
esempietto:
http://www.pokemonhacking.it/attachment.php?aid=387
Analizziamo questo nuovo schema, che ci propone molto spunti di riflessione.
Innanzitutto diciamo quale sia il suo scopo generale. Serve per dimostrare l'uso dei blocchi di input /output: chiede una frase (la password), la riceve, la confronta e a seconda che sia Uguale o meno a quella desiderata fa cose diverse.
Vi invito a notare le " che circondano la frase. I computer sono esseri molto precisi, non amano le cose pressappoco. Perciò dovete specificare esattamente ciò che deve essere scritto, e la maggior parte dei
linguaggi usa proprio ". Poi vediamo questo "accesso", ma cos'è? È anche lui una variabile, ma il suo cassetto (nella distesa di armadi che rappresenta la RAM) è piccolo, perciò non è adatto a contenere
interi o
reali (i tipi che abbiamo utilizzato nel trapezio), ma ha posto solo per un particolare
tipo di valore, che può assumere soltanto due stati: vero o falso (come un interruttore, una bandierina del guardalinee, una flag nello scripting - actually è la flag che deriva da qui). Questo tipo di valore si chiama
booleano, da George Boole, un matematico che ha fatto... Cose Che non ci interessano per il momento. Inoltre è possibile avere variabili che conservano i singoli
caratteri (comunemente rappresentanti da un byte); o anche frasi intere, come quella del disegno: il tipo di queste variabili si chiama
Stringa. Una stringa è un insieme contiguo di caratteri terminata da un byte con valore particolare. Generalmente in informatica le stringhe sono null-terminated, ovvero finiscono per 0x00, mentre quei geniacci della game freak, come saprete, hanno sovvertito l'ordine naturale delle cose, perciò le loro stringhe sono FF-terminated.
Successivamente c'è la parte più importante dell'esempio, ovvero la scelta. Ciò che sta dentro il rombo deve necessariamente poter essere valutato come vero o falso. E poi l'esecuzione continuerà nel ramo corrispondente. Non è necessario avere sempre entrambi i rami, il tutto dipende dalla necessità. Notare nuovamente le ", in quanto una stringa (frase) deve essere precisamente delimitata, altrimenti come possiamo confrontare una cosa non ben definita? (negazione di una proprietà degli algoritmi)
Altra cosa molto importante è il simbolo "==", non fatevi spaventare, non è niente di oscuro. Semplicemente significa "Uguale". E allora perché non usiamo il classico "="? Perché quest'ultimo in realtà non significa "Uguale", anche se con l'abitudine si dice ormai così; in realtà significa "assegno alla variabile a sinistra il valore a destra". E siccome non possono esserci due
operatori identici (come si distinguerebbero?), è stato inventato quello. In realtà si potrebbe anche utilizzare "=", ma solo se prima ci si è messi d'accordo che soltanto dentro il rombo "=" significa "uguaglianza" (operatore logico) e non "assegnamento" (istruzione).
Finite le operazioni da eseguire durante la
selezione (questo il nome formale della struttura di scelta), si ritorna allo stesso punto di prima, solo un passo dopo. Notate come le frecce convergano nello stesso punto, in linea con l'apertura del rombo, e da cui le frecce diventano una sola che Prosegue nel programma.
Eseguiamo ancora una volta l'operazione di zoom out, e vediamo gli elementi principali che costituiscono il programma.
http://www.pokemonhacking.it/attachment.php?aid=388
Abbiamo una struttura sequenza seguita da una selezione, che ovviamente porta ad altre sotto sequenze.
Abbiamo visto due strutture che hanno il loro blocco caratteristico (sequenza e selezione), e un blocco che non ha una sua struttura personale (parallelogramma, anche se è possibile farlo rientrare nella sequenza). Quale combinazione manca? La terza struttura fondamentale che non ha il suo blocco!
L'ultima struttura infatti non introduce un nuovo blocco, ma fa uso di tutti i tipi di blocchi visti finora, ed è forse la più potente per quanto riguarda la risoluzione dei problemi. Prima di gettarsi nelle definizioni, considerate questo esempio.
Devo sommare Tra loro i numeri dispari da 1 a 10. Posso benissimo fare tanti cubetti in cui assegno una variabile e la sommo. Oppure posso usare una Strada più comoda. Infatti, se i numeri da sommare fossero stati 100 o anche 1000, non avremmo più finito di scrivere a mano tutti i numeri. Dunque ci serve un modo per ripetere le stesse operazioni più e più volte. Dobbiamo trovare un modo di evitare le ripetizioni. Ebbene questo esiste e si chiama ciclo, realizzato tramite la struttura dell'
iterazione. Non ha niente di difficile, basta stare attenti a come è fatta.
si compone di:
- la condizione di permanenza nel ciclo
- il corpo delle istruzioni
- il rimando ad un altro punto del diagramma
sembra strano? In realtà noi la applichiamo tutti i giorni, inconsapevolmente!
Perdonatemi questo esempio. Quando preparate la pasta seguite varie istruzioni: mettete l'acqua, mettete il sale, ecc, una normale sequenza. Poi però dovrete aspettare che la pasta sia cotta. Allora dopo un po' assaggiate. se è pronta, proseguite, altrimenti tornate indietro e rifate i passaggi.
identifichiamo le componenti:
- condizione di permanenza: la pasta è cotta?
- corpo delle istruzioni: aspetta; assaggia.
- rimando: se non è cotta, rifai le azioni
ed ecco finalmente come si presenta una risoluzione con ciclo (due possibilità diverse ma equivalenti):
http://www.pokemonhacking.it/attachment.php?aid=389
(il "i è dispari" lo guarderemo più avanti)
sono possibili 2 metodi risolutivi, a seconda di quando viene valutata la condizione di permanenza, se all'inizio o alla fine del ciclo. La differenza è che nel primo le istruzioni vengono eseguite almeno una volta, mentre nell'altro questo comportamento non è garantito a priori. Sta al programmatore scegliere di volta in volta la struttura più adatta.
abbiamo quasi finito, mancano un paio di precisazioni. Abbiamo usato le frecce per indicare le direzioni da seguire. ciò non significa che possiamo andare dove vogliamo: ogni struttura ha le sue regole di funzionamento, e soprattutto, cosa più importante, non si può uscire dalla struttura in cui si è. Ecco perchè vi ho stufato tanto prima (e lo farò ancora un'ultima volta) indicandovi le zone di competenza di ciascuna. Ad esempio quella che è più comune sbagliare è l'iterazione. La freccia può, nel primo caso (controllo alla fine), entrare soltanto nella sequenza precedente (se non esiste una sequenza se ne fa una fittizia "nulla", ovvero di dimensione 0), non inserirsi in altre strutture! mentre per il secondo tipo di iterazione (controllo all'inizio), la freccia può solo tornare al rombo della condizione di permanenza.
è anche possibile, qualora si renda necessario, utilizzare più strutture dentro altre: questo processo si chiama
annidamento; e in effetti l'ho usato nell'ultimo disegno: ho messo un rombo dentro un altro rombo. questa cosa si può fare anche all'infinito, finchè non viola le proprietà degli algoritmi.
ed ecco infine la tabella riassuntiva
http://www.pokemonhacking.it/attachment.php?aid=390
per concludere veramente, vi dico che il teorema di jacopini-bohm dice che ogni problema può essere risolto soltanto con l'uso di sequenza, selezione e iterazione, perciò mettetevi tranquilli e pensate ad un modo per risolvere il problema, che ci sarà sicuramente, e non fate dipanare frecce ovunque intorno all'universo.
Per il momento metabolizzate bene questo, che non è poca roba, la prossima volta vedremo qualche esercizio! (potete però cominciare già a pensare a qualche algoritmo per allenarvi, nel buio della vostra cameretta)
ci vediamo
esercizi 3.1 160217
ESERCIZI 3.1
facciamo qualche esercizio!^^
teoria necessaria per svolgere al meglio gli esercizi:
- Funzioni
è un particolare costrutto sintattico, in qualche linguaggio di programmazione, che permette di raggruppare, all'interno di programma, una sequenza di istruzioni in un unico blocco di istruzioni espletando così una determinata e in generale più complessa operazione, azione o elaborazione sui dati del programma stesso in modo tale che a partire da determinati input restituisca determinati output.
(grazie wikipedia, scusate ma non sarei riuscito ad esprimerlo così bene con parole mie)
in alcuni linguaggi le funzioni assumono nomi diversi
(se siete interessati...)
in pascal le funzioni senza valore di ritorno si chiamano procedure
in assembly si chiamano routine
nei linguaggi ad oggetti si chiamano metodi
"i è dispari" (o pari non ricordo) dell'altra volta era una funzione che ritornava o VERO o FALSO. le funzioni si usano anche per scrivere di meno, in quanto raggruppano molte istruzioni in una sola.
- Valore di ritorno
quando una funzione termina, restituisce un valore al blocco invocante. Questo può essere di qualunque tipo di dato, ovvero intero, reale, booleano, intero corto, intero lungo, carattere, e anche quelli definiti da voi. tuttavia questo comportamento non è obbligatorio, se il contesto non lo richiede. dopotutto, se avete fatto matematica a livelli non bassi (diciamo che una seconda superiore va bene), avrete visto le funzioni, come relazioni che associano agli elementi di un insieme, al più un elemento di un altro insieme. Lo stesso in informatica.
ciò che nella lezione precedente abbiamo racchiuso in un unico blocco più grosso potrebbe benissimo essere racchiuso in una funzione; riconducendoci agli esempi, "area_trapezio" e "is_odd_number" sono anch'esse funzioni; la prima non ritorna nulla (si dice che è di tipo void) la seconda ritorna un booleano
- Vettori (array in inglese)
la definizione è molto semplice, ma sono uno strumento importantissimo: un vettore è una sequenza di dati dello stesso tipo in memoria.
(con sequenza intendo elementi contigui, tenetelo bene a mente)
ad esempio una stringa di testo è un vettore di tipo carattere:
"Ciao mondo" è rappresentato in memoria:
[...] [C] [i,] [a] [o] [ ] [m] [o] [n] [d] [o] [...]
(la i è brutta perchè ho dovuto ingannare il formattatore, altrimenti me la considerava italic)
i puntini all'inizio e alla fine sono quella notazione in grammatica per dire "c'è dell'altro".
questa è la rappresentazione generica di un vettore:
![[Immagine: Array+in+Java+Comparision.gif]](http://2.bp.blogspot.com/-v-dkON4gwhQ/U4cw77VA-2I/AAAAAAAABkI/RL1x8PGgt-U/s1600/Array+in+Java+Comparision.gif)
un elemento di un vettore può contenere a sua volta un vettore. in Questo caso prende il nome di matrice. un esempio di matrice è una mappa di tiles, in cui le "colonne" sono elementi delle "righe" (o viceversa a seconda dell'implementazione)
realizzazione:
![[Immagine: array-2d.png]](http://ycpcs.github.io/cs201-summer2014/notes/figures/array-2d.png)
e considerando una matrice 3x3, ogni elemento è:
![[Immagine: Image377.gif]](http://www.math.it/formulario/images/determinanti/Image377.gif)
abbiamo finito per ora! ~
in questi esercizi simulerò i passaggi risolutivi che uno dovrebbe seguire.
sono 5 esercizi sugli algoritmi (schemi a blocchi) perchè non posso allegare più immagini di così.
Per i disegni così belli ho usato un programma chiamato Algobuild
1) dato un numero, stampa (o ritorna) il fattoriale
il fattoriale di un mumero è il prodotto dei numeri da 1 al numero stesso.
ad esempio, se il numero è 5, il fattoriale è 5*4*3*2*1=120
input: un numero
output: un numero
strategia risolutiva: dobbiamo avere un valore temporaneo che sarà il risultato
dobbiamo anche moltiplicare il risultato delle moltiplicazioni precedenti per qualcosa di nuovo; ci fermeremo quando il fattore raggiunge 1.
http://www.pokemonhacking.it/attachment.php?aid=393
2) dati n numeri (uno alla volta), calcolare la media
input:
- un numero che indicala quantità di numeri da processare
- tanti numeri (da processare uno alla volta)
output
la media di tutti
strategia risolutiva: ogni volta che l'utente inserisce un numero,dovremo aggiornare la somma. calcoleremo la media alla fine dell'inserimento (totale/numero di elementi)
http://www.pokemonhacking.it/attachment.php?aid=395
3) soluzione equazione di secondo grado
un'equazione del tipo ax^2+bx+c=0 ha soluzione
x1= -b+sqrt(b^2-4*a*c))/2*a
x2= -b+sqrt(b^2-4*a*c))/2*a
chiederemo i coefficienti a, b, c e verificheremo che il discriminante non sia negativo (non si può fare la radice quadrata di un numero negativo!

), poi applicheremo la formula
http://www.pokemonhacking.it/attachment.php?aid=396
4) data una stringa, invertirla
input: un vettore
output: un vettore
strategia risolutiva: inizio a riempire il nuovo vettore partendo dall'ultima posizione
dell'altro
http://www.pokemonhacking.it/attachment.php?aid=397
5) dato un vettore, calcolare la moda (il valore più ricorrente)
input: un vettore
output: un numero
strategia risolutiva:
creo una tabella (detta matrice, ovvero un vettore di vettori) in cui memorizzo ogni valore e le sue occorrenze. scorro il vettore dato e "popolo" la tabella. ogni volta che trovo un valore lo aggiungo al contatore. alla fine scorro l'intera tabella per trovare il valore con più occorrenze.
la tabella è grande esattamente quanto il vettore (x2 ovviamente), e non è il massimo dell'ottimizzazione.
si potrebbe fare in varie altre maniere, di cui sicuramente una meno esosa di risorse, ma al momento non ho tempo per pensarci troppo
http://www.pokemonhacking.it/attachment.php?aid=398
(scusate se ci sono un paio di piccoli errori nel disegno, ma sinceramente non ho voglia di rifare tutto)
ora, compiti (per il momento chiedo di mandarli via MP per evitare che i furbi copino)! ~
avete max 10/12 giorni di tempo
- dato un numero, stabilire se è pari o dispari
suggerimento: un numero è pari quando è divisibile per 2. cosa vuol dire essere divisibile per due?
per fare questo ci sono almeno 3 possibili strade (proprietà degli algoritmi)
- dati 2 vettori, produrne un terzo con la loro somma (somma "termine a termine" delle componenti)
- dati 2 vettori, concatenarli ("attaccarli")
suggerimento: creare un nuovo vettore, ovviamente più grande, in cui si mettono gli altri
- dati n numeri inseriti dall'utente n anche scelto dall'utente), stabilire il maggiore
- dati i 3 lati di un triangolo, classificarlo (scaleno, isoscele, equilatero)
suggerimento: bisogna sapere come sono i lati tra di loro (in lunghezza)
e per oggi è utto!
la prossima volta, finalmente ASM!
lezione 4 160223
.
LEZIONE 4
ASM
#integrare con jpan
Eccoci alla parte che forse vi interessa maggiormente! Se avete capito bene l'ultima lezione non dovreste avere grossi problemi.
Spesso abbreviato in ASM, è quanto di più vicino al linguaggio macchina l'uomo possa comprendere senza diventare pazzo. Infatti il linguaggio macchina è fatto dai cosiddetti codici operativi, ovvero dei byte che vengono letti dal processore, ed ognuno ha un preciso significato come istruzione. La sua particolarità rispetto agli altri linguaggi di programmazione è che c'è una corrispondenza 1:1 tra istruzioni scritte e istruzioni reali della macchina. Significa che per ogni istruzione scritta/letta da noi esiste un singolo codice operativo, e questa cosa si esprime dicendo che "esiste una sostituzione mnemonica tra istruzione della macchina e parola chiave del linguaggio" L'assembli infatti è stato inventato per risparmiare la fatica di programmare i calcolatori inserendo nella loro memoria direttamente il codice macchina, costituito da zeri e uni (potete vederli nelle guide linkate all'inizio).
#spiegare meglio, aggiustare la frase, introdurre i primi calcolatori elettronici
L'assembly, come avrete intuito, è un linguaggio a basso livello, per cui non è dotato di tutti i meccanismi di sicurezza che di solito abbiamo con la programmazione. Siamo solo noi e l'hardware. In altre parole, siamo i padroni totali, ma dobbiamo anche prenderne le responsabilità (come dicevano in un film).
Prima però bisogna capire come funziona il processore.
Esso è responsabile dell'esecuzione fisica del gioco, svolge i calcoli necessari e controlla le periferiche (tutta roba trovabile su wikipedia).
La CPU è composta da varie parti; a grandi linee troviamo l'ALU, unità che esegue le operazioni via hardware (i circuiti elettronici elaborano i byte), la CU, unità di controllo, e i BUS (collegamenti elettrici) che trasferiscono i dati. Esiste poi un minuscolo settore di memoria che è sufficiente a contenere giusto i dati che servono per la corrente operazione. Tale spazio prende il nome di registri (da non confondere con i registri I/O tipici del GBA). I registri possono essere paragonati a delle variabili, ovvero dei contenitori di informazioni. Pensate ad una tazza piena di riso: noi possiamo mettere dentro tutti i chicchi di riso che vogliamo, ovviamente finchè non tracima, oppure possiamo svuotarne il contenuto, o anche solo contare quanti chicchi contiene in un certo momento (perdonatemi il brutto esempio, copiato da qualcuno su internet). I registri del GBA sono lunghi 32 bit, ovvero possono contenere dati fino a FFFFFFFFh, da cui si suol dire che il GBA è una macchina a 32 bit (come i computer fino a qualche anno fa).
Il processore funziona secondo uno schema fisso sempre uguale:
- reperimento delle istruzioni (fetch)
- decodifica delle istruzioni (decode)
- esecuzione delle istruzioni (execute)
Questo processo si chiama
pipeline, termine con cui si identificano le condutture petrolifere, proprio perchè il processo (scusate la ripetizione) è costante come il flusso di liquido. Le fasi vengono tutte svolte tramite dei circuiti dedicati ad ogni singolo compito, residenti un po' ovunque nella console (per la prima fase intervengono i bus sulla scheda madre e sulla cartuccia di gioco, le alte due invece vengono eseguite all'interno del processore). Questa pipeline a 3 stadi è tra le più semplici, e ad ogni istante ci sono 3 differenti istruzioni che stanno subendo un passo diverso tra quelli possibili (ovviamente in ordine). La più semplice ovviamente è quella che fa le operazioni una alla volta. Giusto per curiosità, i processori desktop hanno pipeline con addirittura decine di passi! (il pentium 4 una quarantina, perchè doveva essere il più veloce processore single core)
Prima di tuffarci a capofitto nelle istruzioni, bisogna spendere ancora qualche parola sullo specifico processore con cui lavoreremo: l'ARM7TDMI.
Il processore del GBA adotta l'architettura RISC, dunque è piuttosto semplice. RISC vuol dire Reduced Instruction Set Computer, ovvero elaboratore con set di istruzioni ridotto; modello che si contrappone ai CISC (Complex Instruction Set Computer), di uso tipico nei computer. L'e due architetture sono opposte; la seconda presenta molte istruzioni elementari utilizzabili, mentre la prima, per ridurre la complessità in ambienti critici, come una console portatile, offre soltanto lo stretto indispensabile in termini di operazioni effettuabili a livello di codice macchina. Ma proprio questo gli conferisce consumi energetici ridotti (io a volte arrivavo a 10 ore col GBA!!! [emoji15]); è anche stato usato in diversi vecchi dispositivi come l'ipod touch 1G.
Semplice fino a un certo punto; ci sono comunque un sacco di aspetti da tenere conto, anche tralasciando la realizzazione fisica (per quello c'è il noiosissimo libro facoltativo linkato all'inizio, ne sconsiglio vivamente la lettura se non siete bravi in elettronica (io tre quarti delle cose manco le so leggere asd)).
REGISTRI:
- R0-R12: registri general purpose, possono essere usati per contenere qualunque dato
- R13: Stack Pointer. usato per tenere traccia dell'ultima posozione dello stack
- R14: Link Register, contiene l'indirizzo di ritorno della funzione
- R15: Program counter, indica la prossima istruzione da fetchare.
- CPSR: Current Program Status Register è il nome del PSW, un registro interno che raccoglie informazioni come lo stato dell'ultima operazione.
#spiegare bene cosa sono SP e LR nella prossima revisione
parte tradotta direttamente dalla documentazione:
L'ARM7TDMI ha due "modalità operative", ovvero può lavorare con due diversi
set di istruzioni
- ARM, set di istruzioni a 32 bit
- Thumb, set di istruzioni a 16 bit
Il set thumb è un sotto-set dell'ARM, ogni sua istruzione ha una corrispondenza nel set esteso, che svolge lo stesso compito. La cosa forte è che entrambe le modalità condividono gli stessi registri, permettendo una forte collaborazione tra le due, consentendo di ottimizzare sia lo spazio occupato sia le prestazioni.
Infatti durante l'esecuzione, ogni istruzione a 16 bit viene "decompressa" nel suo equivalente a 32 bit, permettendo di sfruttare appieno le capacità della macchina.
Thumb ha tutti i vantaggi di un "cuore" a 32 bit:
- indirizzamento a 32 bit (significa che potrete trattare memoria fino a 4 GB, ma siccome come sapete il GBA si ferma a 0E-000000, avrete comunque tutto il range disponibile)
- registri a 32 bit
- operazioni a 32 bit
- trasferimento di memoria a 32 bit
il codice thumb occupa tipicamente il 65% del corrispettivo ARM, e fornisce il 160% delle prestazioni,
se letto da una memoria a 16 bit. La ROM guarda caso ha un sistema di trasferimento a 16 bit, ecco spiegato il motivo per cui i giochi sono principalmente compilati in questa modalità. Tuttavia, se eseguito in uno spazio a 32 bit (ad esempio dalla RAM), la superiorità del codice thumb scema. Infatti sono fatte in ARM e residenti in RAM le routine di gestione degli interrupt, che noi non vedremo.
Il core del processore usa il primo bit del program counter per determinare cosa mettere in un altro registro interno, che serve per stabilire il set di istruzioni da usare (ecco spiegato l'arcano mistero del +1 nel callasm

).
Il processore supporta sia la modalità di storage dei dati big endian che little endian.
ma siccome devono complicarci le cose (-.-") il default è little endian, in quanto di più veloce processamento (ha a che fare con la realizazione fisica dei circuiti dediti ai calcoli).
I precedenti termini si riferiscono a come le informazioni vengono scritte nella memoria. Big endian memorizza le informazioni a partire dal MSB (most significant bit), mentre little endian dal LSB (least significant bit).
Durante la modalità thumb, i registri alti (8-15) non sono immediatamente accessibili con le operazioni elementari. Se non possiamo farne a meno come deposito temporaneo di informazioni, possiamo usare alcune istruzioni per copiarvi il contenuto dei registri bassi (0-7), o anche copiare il loro contenuto nei registri bassi, ovvero nell'altro senso.
ogni istruzione può essere eseguita condizionalmente in modalità ARM, mentre l'unica istruzione condizionale in modalità thumb è il salto.
fine parte tradotta
Dopo questa estenuante introduzione penso che siamo pronti per vedere i veri comandi! ~
NOTA: non vi insegnerò la sintassi, a parte un caso che vedremo, perchè è noiosa e fine a se stessa, e potete trovarla nella documentazione. Reputo molto più istruttivo prima comprendere bene effettivamente cosa fanno i vari comandi.
ISTRUZIONI ARITMETICHE
- ADD/MUL/SUB
operazioni matematiche come somma, moltiplicazione, sottrazione.
di solito si scrive il comando seguito da 3 registri: registro destinazione del risultato, registro operando 1, registro operando 2. oppure si usa un immediato (un piccolo valore scritto direttamente nel codice, senza dover sprecare un registro)
ISTRUZIONI LOGICHE
- AND fa l'and bit a bit di due registri #spiegare
- EOR fa l'Esclusive Or (XOR) dei bit di due registri #spiegare
- LSL/LSR serve per shiftare i bytes a destra o a sinistra. approfondimento sullo shift:
questa operazione è utile quando si vuole moltiplicare per potenze di 2. infatti si può moltiplicare di 2^n un numero spostando verso sinistra n volte i bytes. Per dividere shiftiamo verso destra.
esempio:
5d
0101b
shiftiamo di 1
1010b
10d
esempio
50d
110010b
shiftiamo di 1
011001b
25d
# revisione ^
- NEG nega il contenuto di un registro, bit per bit, ma attenzione, farà "0-valore", dunque il risultato sarà avanti di 1 rispetto a quello che ci aspetteremmo!
- ORR fa l'or dei registri, bit a bit. #spiegare
ISTRUZIONI PER IL CONTROLLO DEL FLUSSO
- B/BL/BX servono per eseguire dei salti nel codice. I salti permettono di alterare il normale flusso di esecuzione del programma, ma per routine semplici non sono necessari. Di solito si usano quando si testa una condizione e si vuole un comportamento diverso a seconda dei casi. Se avete capito bene i goto negli script, non avrete problemi. La differenza tra i tre è che B salta e basta, BL salta e copia il PC nel LR per un facile ritorno, BX salta e cambia modo operativo, a seconda dell'ultimo bit del valore.
E' possibile aggiungere delle condizioni all'istruzione B.
B + qualcosa significa salta se:
- EQ equal
- NE not equal
- CS Carry Set
- CC Carry clear
- HS unsigned higer or same
- LO Unsigned Lower
- MI Minus/negative
- PL Plus/Positive or Zero
- VS Overflow
- VC No Overflow
- HI unsigned higher
- LS Unsigned Lower or Same
- GE Signed Greater Than or Equal
- LT Less than
- GT Signed Greater than
- LE Signed less than or equal
- GE Greater than or equal
- AL Always
- NE Never
#spiegare alcuni, tradure, c2
notiamo che gli ultimi 2 sono praticamente inutili.
I salti condizionali sono molto usati con l'istruzione CMP.
le varianti condizionali si basano sul CPSR, perciò sono utili solamente se seguono un'istruzione CMP. potreste comunque usarle quando volete (come ogni istruzione del resto), ma non avrebbe molto senso.
BKPT breakpoint, serve per interrompere l'esecuzione del programma a scopi di debugging.
CMP paragona. può paragonare un registro ad un byte, o 2 registri tra loro e mette il risultato nel PSW (CPSR), subito dopo sarebbe utile eseguire un salto. altrimenti è un'operazione sprecata. Questo è l'unico modo di eseguire istruzioni condizionali in modalità thumb
ISTRUZIONI PER OPERAZIONI SULLA MEMORIA
(#cancellare: prima era miste)
- LDR/LDRB/LDRH/MOV Serve per caricare un registro con dei dati. Esistono varie opzioni, come un valore immediato; un valore letto dall'indirizzamento indiretto; un valore ottenuto mediante operazioni, ecc. La differenza sostanziale tra i tre sta in cosa caricano: LDR 32 bit, LDRH 16 bit (H sta per Half) , LDRB 8 bit (B sta per Byte). MOV invece inizializza un registro con un byte presente nelostesso codice operativo.
- STR/STRB/STRH Questi invece fanno l'operazione inversa del LDR, ovvero "stoccano" (da store) il dato da qualche parte. Anche qui Vi sono molte opzioni, ma è meglio visionarle sulla guida, in quanto in questa sede appesantirebbe la lettura.
- POP/PUSH servono all'inizio e alla fine della nostra funzione ASM (non in tutti i casi, solo nelle sotto-funzioni - dunque praticamente sempre) per accatastare sulla pila i contenuti dei registri che ci serviranno per compiere le operazioni. E' buona cosa ricordarsi di andare a riprendere le informazioni e rimetterle alloro posto una volta terminata la routine.
E' importante ricordare che per iniziare una sotto-funzione (quelle trattate in questa guida) su usa PUSH LR (più eventuali registri usati) e per terminarla si deve fare POP PC. Questo perchè quando eseguiamo un salto il Link Register assume il valore dell'offset dell'istruzione successiva a quella del salto. ovvero, per chi usa un IDE, "step over". ovvero, per i comuni umani, considera la funzione chiamata dal salto come una singola istruzione, e dunque l'istruzione seguente non è la prima che si incontra dopo aver seguito il salto, ma quella effettivamente successiva nel file (rimane allo stesso livello di profondità delle sotto-funzioni). Una volta accantonato il LR e compiuta la routine, dobbiamo tornare indietro. Come? Facile. Poppando (ok, doppiosenso, scusate) il LR otteniamo il punto dove continua la nostra ROM, ma per andarci dobbiamo metterlo nel Program Counter!
#da qualche parte metttere endianess
vi è andata bene che non vi do compiti, prossima volta esercizi, vediamo qualcosa in azione!
#revisionare tutto
esercizi 4 160226
spero di non avervi disturbato e che non vi dispiaccia se ho deciso di fondere le aule, è per una gestione meno incasinata! (avere altro disordine è l'ultima cosa che voglio)
questa lexione va in onda in edizione ridottaa causa della grande richiesta che ne ha accorciato i tempi di sviluppo! perciò avrete un paio di esempi in meno (posso passarveli comunque quando saranno pronti), ma alla fine per quelli bravi come voi non è che facessero una grande differenza.
ESERCIZI 4
ASM BASE
in questa sede trasporremo in ASM gli algoritmi visti nelle precedenti lezioni, con lo scopo di abituarci alla sintassi ^^
ho preso alcuni degli esercizi della volta scorsa, in modo da poter riflettere sulle differenze, più alcuni presi da internet sul C, o inventati da me ^^
innanzitutto se avete dei dubbi sulla sintassi consultate pure il PDF che vi ho fato scaricare all'inizio.
esso ha 3 aree: una zona in cui viene presentato il comando in modo molto sintetico, una che illustra la sintassi di ogni variante di ogni comando, e una che mostra come sono fisicamente realizzati gli opcodes. Ora vi esporrò brevemente i punti salienti della sintassi.
(NB: per alleggerire la grafica della pagina non ho quasi mai usato i tag quote o code, ma ho lasciato una riga vuota prima e dopo ogni blocco che ne avrebbe fatto uso)
- [RX] indica di indirizzare l'operazione all'offset di memoria contenuto nel registro.
dunque, l'istruzione
LDR RX, [RY]
caricherà in RX i 4 byte presenti all'indirizzo di memoria contenuto in RY.
[RX, RY]
oppure
[RX, #valore]
significa indirizzare l'operazione all'indirizzo contenuto da RX + RY (o valore)
.
- le etichette servono per distinguere parti di programma, come le funzioni, e servono come destinazione dei salti. per dichiarare un'etichetta basta metterne il nome seguito da due punti, così:
main:
.
- quando iniziate una routine ricordatevi SEMPRE di allinearla. per farlo si usa:
.align X, 0xY, 0xZ
questa è una direttiva al compilatore, ovvero delle istruzioni che noi gli diamo per informarlo di qualcosa prima di procedere a compilare. le direttive iniziano con il punto. in particolare align indica di allineare il compilato a partire da 2^X byte, riempiendo lo spazio intermedio con il byte Y, fino ad un massimo di Z byte, altrimenti il processo verrà saltato. gli ultimi due parametri sono opzionali.
#mostrare esempio sulfile vero, anche ascii
L'align è anche usato sui dati, in quanto se non fossero allineati (specialmente le strutture), sarebbe un casino assicurato nella gestione della memoria. Inoltre alcuni opcodes, se avete letto la documentazione, hanno un offset di reperimento delle informazioni che va a blocchi di 4 byte.
Dunque la pratica, abbastanza diffusa qua da noi, di usare
LDR RX, .pointer
[...]
.align 2
.pointer:
.word 0xqualcosa
nasce dal fatto che l'istruzione LDR ha nei suoi campi (a livello fisico) un valore che indica "quante word in là" andare a prendere il dato. (ricordando che una word è lunga 4 bytes, e 2^2 fa 4)
tuttavia questa pratica ha uno o due elementi non completamente corretti.
innanzitutto si sta usando le direttive come semplici etichette, e questo potrebbe dare problemi in compilazione.
dunque potreste sostituire con
LDR RX, valore
[...]
.align 2
valore: .word 0xqualcosa
se proprio non voleste niente sotto, un'altra soluzione è
LDR RX, =0xqualcosa
in questo modo caricherete subito il valore.
oppure potreste anche fare di meglio. quest'ultimo metodo è parecchio scomodo, in quanto incline agli errori e non centralizzato (se usate un valore molte volte e ad un tratto lo volete sostituire, dovrete cercarlo per tutto il sorgente).
leggendo la guida dell'assemblatoreho scoperto questa nuova direttiva chiamata "equ". svolge un compito simile al #define del C, ovvero sostituisce tutte le occorrenze di un valore nel testo, gestendo automaticamente la questione degli allineamenti. in questo modo scriverete una sola volta il valore, ma potrete usarlo sempre, unendo così i vantaggi dei due metodi (centralizzazione del valore e praticità). ecco un esempio:
.equ alias, 0xqualcosa
LDR RX, =alias
dove alias è una qualunque parola inventata da noi. la direttiva può essere inserita ovunque nel sorgente, perciò prestate attenzione, anche se vi potrebbe sembrare un vantaggio, in realtà contribuisce a rendere meno leggibile il codice. Sarà bene adottare un proprio stile, ovvero decidere se mettere tutte le dichiarazioni di costanti all'inizio o alla fine del file (personalmente ritengo che dichiarare una costante al momento dell'uso renda poco leggibile il codice).
un'altra direttiva è .include, che unisce un file in quello corrente, a compile-time:
supponete di aver creato un file con delle funzioni che usate spesso. potrete "includere" il file nel vostro nuovo sorgente (di solito i file di sorgente assembly si chiamano *.ASM o *.S ) in modo da poterle usare senza doverle riscrivere. è una tecnica molto comoda, in quanto consente di risparmiare tempo. la sintassi è questa:
.include "path"
dove path è il percorso al vostro file. le virgolette vanno messe.
.
- per inserire un immediato, si usa #
un immediato è un valore da usare nell'operazione, inserito nell'istruzione stessa, al posto di usare un registro. in genere se avete valori, conosciuti prima dell'esecuzione, inferiori o uguali a 255 si possono tranquillamente mettere come immediati.
esempio:
MOV R1, #0
.
- potete inserire un commento con la chiocciola, e quel'intera riga, a partire dal carattere chiocciola, non verrà considerata durante la compilazione. esempio:
LDR R0, 0x083E6E50 @carico l'offset
consiglio di inserire sempre qualche commento, anche se all'inizio possa sembrare inutile, perchè potrebbe capitarvi di non riuscire a capire il vostro stesso codice! questo perchè è complicato, e se non lo guardate per un po' vi dimenticherete. Poi se lo dovrete far leggere ad altri è ancora più "moralmente obbligatorio": è un vero atto di cortesia!
ed ecco alcuni swi che potrebbero tornarvi utili (#se leggete "dsi" o "nds" per favore ignoratelo):
Codice:
SWI 06h - Div
Signed Division, r0/r1.
r0 signed 32bit Number
r1 signed 32bit Denom
Return:
r0 Number DIV Denom ;signed
r1 Number MOD Denom ;signed
r3 ABS (Number DIV Denom) ;unsigned
For example, incoming -1234, 10 should return -123, -4, +123.
The function usually gets caught in an endless loop upon division by zero.
SWI 08h - Sqrt
Calculate square root.
r0 unsigned 32bit number
Return:
r0 unsigned 16bit number
The result is an integer value, so Sqrt(2) would return 1, to avoid this inaccuracy, shift left incoming number by 2*N as much as possible (the result is then shifted left by 1*N). Ie. Sqrt(2 shl 30) would return 1.41421 shl 15.
SWI 09h - ArcTan
Calculates the arc tangent.
r0 Tan, 16bit (1bit sign, 1bit integral part, 14bit decimal part)
Return:
r0 "-PI/2<THETA/<PI/2" in a range of C000h-4000h.
Note: there is a problem in accuracy with "THETA<-PI/4, PI/4<THETA".
LZ77UnCompReadNormalWrite8bit (Wram) - SWI 11h
LZ77UnCompReadNormalWrite16bit (Vram) - SWI 12h
Expands LZ77-compressed data. The Wram function is faster, and writes in units of 8bits. For the Vram function the destination must be halfword aligned, data is written in units of 16bits.
CAUTION: Writing 16bit units to [dest-1] instead of 8bit units to [dest] means the reading from [dest-1] won't work, ie. the "Vram" function works only with disp=001h..FFFh, but not with disp=000h.
If the size of the compressed data is not a multiple of 4, please adjust it as much as possible by padding with 0. Align the source address to a 4-Byte boundary.
r0 Source address, pointing to data as such:
Data header (32bit)
Bit 0-3 Reserved
Bit 4-7 Compressed type (must be 1 for LZ77)
Bit 8-31 Size of decompressed data
Repeat below. Each Flag Byte followed by eight Blocks.
Flag data (8bit)
Bit 0-7 Type Flags for next 8 Blocks, MSB first
Block Type 0 - Uncompressed - Copy 1 Byte from Source to Dest
Bit 0-7 One data byte to be copied to dest
Block Type 1 - Compressed - Copy N+3 Bytes from Dest-Disp-1 to Dest
Bit 0-3 Disp MSBs
Bit 4-7 Number of bytes to copy (minus 3)
Bit 8-15 Disp LSBs
r1 Destination address
r2 Callback parameter ;\for NDS/DSi "ReadByCallback" variants only
r3 Callback structure ;/(see Callback notes below)
Return: No return value.
SWI 0Ch - CpuFastSet
Memory copy/fill in units of 32 bytes. Memcopy is implemented as repeated LDMIA/STMIA [Rb]!,r2-r9 instructions. Memfill as single LDR followed by repeated STMIA [Rb]!,r2-r9.
After processing all 32-byte-blocks, the NDS/DSi additonally processes the remaining words as 4-byte blocks. BUG: The NDS/DSi uses the fast 32-byte-block processing only for the first N bytes (not for the first N words), so only the first quarter of the memory block is FAST, the remaining three quarters are SLOWLY copied word-by-word.
The length is specifed as wordcount, ie. the number of bytes divided by 4.
On the GBA, the length should be a multiple of 8 words (32 bytes) (otherwise the GBA is forcefully rounding-up the length). On NDS/DSi, the length may be any number of words (4 bytes).
r0 Source address (must be aligned by 4)
r1 Destination address (must be aligned by 4)
r2 Length/Mode
Bit 0-20 Wordcount (GBA: rounded-up to multiple of 8 words)
Bit 24 Fixed Source Address (0=Copy, 1=Fill by WORD[r0])
Return: No return value, Data written to destination address.
SWI 0Bh - CpuSet
Memory copy/fill in units of 4 bytes or 2 bytes. Memcopy is implemented as repeated LDMIA/STMIA [Rb]!,r3 or LDRH/STRH r3,[r0,r5] instructions. Memfill as single LDMIA or LDRH followed by repeated STMIA [Rb]!,r3 or STRH r3,[r0,r5].
The length must be a multiple of 4 bytes (32bit mode) or 2 bytes (16bit mode). The (half)wordcount in r2 must be length/4 (32bit mode) or length/2 (16bit mode), ie. length in word/halfword units rather than byte units.
r0 Source address (must be aligned by 4 for 32bit, by 2 for 16bit)
r1 Destination address (must be aligned by 4 for 32bit, by 2 for 16bit)
r2 Length/Mode
Bit 0-20 Wordcount (for 32bit), or Halfwordcount (for 16bit)
Bit 24 Fixed Source Address (0=Copy, 1=Fill by {HALF}WORD[r0])
Bit 26 Datasize (0=16bit, 1=32bit)
Return: No return value, Data written to destination address.
Note: On GBA, NDS7 and DSi7, these two functions will silently reject to do anything if the source start or end addresses are reaching into the BIOS area. The NDS9 and DSi9 don't have such read-proctections.
SWI 05h - VBlankIntrWait ;DSi7/DSi9=bugged?
Continues to wait in Halt status until a new V-Blank interrupt occurs.
The function sets r0=1 and r1=1 (plus r2=0 on DSi7) and does then execute IntrWait (SWI 04h), see IntrWait for details.
No parameters, no return value.
noi (io) negli esercizi useremo l'indirizzo 02000000 come scambio di informazioni tra script e routine; potrete facilmente cambiarlo.
ESERCIZIO: dato un numero, stampa (o ritorna) il fattoriale
Codice:
.THUMB
.ALIGN 2, 0x0
@; RO: OFFSET MEM
@; R1: VALORE
@; R2: DECREMENTO
PUSH {R0-R4,LR}
MOV R0, #1 @;INIZIALIZZO REGISTRO: 2000000
LSL R0, #0X19
LDRH R1, [R0] @; LEGGO VALORE INPUT
MOV R2, R1
fattoriale_ciclo_calcolo:
SUB R2, R2, #1 @; ALGORITMO ITERATIVO DEL FATTORIALE
MUL R1, R2
CMP R2, #1
BHI fattoriale_ciclo_calcolo
STR R1, [R0] @;FORNISCO IL RISULTATO
POP {R0-R4,PC}
tutto quello che abbiamo fatto è stato inizializzare i valori ed eseguire un semplice ciclo in cui moltiplichiamo il numero per sè stesso.
ESERCIZIO: dati n numeri, calcolare la media
avvertenza: ho usato il byte a 200000 per indicare il numero di elementi, che ho messo in un vettore (per complicare un pochino le cose, se no non c'è gusto XD - no scherzo in realtà perchè così avete già in mente come trattare gli altri problemi complicati sui vettori) che compare subito dopo (a pensarci bene in Pascal le stringhe di testo sono vettori di 255 elementi in cui lo 0-esimo indica la lunghezza totale... ma questa è un'altra storia, mi è venuta la coincidenza per caso! )
ecco, ogni tanto provate a fare un riassunto del contenuto dei registri, come ho fato io due volte qua sotto (le righe lunghe), così da non confondervi!
(consiglio di usare programmers notepad per avere la sintassi colorata)
Codice:
.thumb
.align 2, 0x0
.equ scambio, 0x2000000
push {r0-r4, lr}
@; r0: accesso vettore, r1: numero elementi r2: somma temporanea r3: elemento letto corrente r4: indice del vettore
inizializzazione:
mov r2, #0
mov r4, #0
ldr r1, =scambio
mov r0, r1 @; copio
ldrb r1, [r1] @; leggo il numero di elementi
add r0, r0, #1 @; mi posiziono sul vettore
ciclo:
ldrb r3, [r0, r4] @; accesso tramite indicizzazione
add r2, r2, r3
add r4, r4, #1
cmp r1, r4
bhi ciclo
@; r0: somma temporanea r1: numero elementi r2: / r3: / r4: memorizzazione
mov r4, r0 @; preparo la divisione
sub r4, r4, #1
mov r0, r2
mov r2, #0
mov r3, #0
swi 0x6
strb r3, [r4] @; comunicazione del risultato
fine:
pop {r0-r4, pc}
notate che per entrambi gli esempi ho scelto di memorizzare il risultato nella memoria RAM per semplicità. Se però le funzioni fossero state inserite in un contesto più ampio, sarebbe stato preferibile usare un valore di ritorno. come si fa? bisogna semplicemente non pushare un (o più) registro, che useremo per contenere il risultato. un esempio di questa tecnica è lo SWI, come abbiamo visto nella divisione, che ritorna qualcosa nei registri. ma noi come possiamo?
generalizzando,
Codice:
PUSH {RY-RZ, LR}
@ fai qualcosa
MOV RX, XXX @ memorizza in qualche modo il risultato
POP {RY-RZ,PC}
con, generalmente, X < Y < Z (numeri sempre a vostra scelta, ma meglio se sensata)
in questo modo RX sarà in comune sia alla funzione corrente che a quella
chiamante. poi quello che la chiamante farà non è affar della corrente.
nella seconda tipologia di esercizi userò il valore di ritorno, dunque attenti!
#sposare su programmazione
una funzione si dice
ricorsiva se durante l'esecuzione chiama sè stessa o chiama una funzione che chiama sè stessa. equivalentemente, in matematica, una funzione è ricorsiva se è definita in termini di sè stessa.
è importante che esista una condizione di base che permette di non chiamare la funzione, altrimenti si genererebbe un ciclo infinito.
pensiamo al fattoriale di n, ovvero la produttoria di numeri che vanno da 1 a n.
è possibile usare l'algoritmo iterativo (anzi c'è un teorema che dice che qualunque problema è risolvibile tramite le strutture fonfamentali), oppure quello ricorsivo.
in questo caso, il fattoriale di n (scritto n!) possiamo vederlo come n*(n-1)!.
[attachment=441]
è proprio la condizione di base che ci permette di uscire dal calcolo.
Che succede se finite i registri come variabili?
abbiamo essenzialmente tre alternative: usare la memoria, lo stack o i registri alti.
per usare la memoria non ci vuole molto, basta scrivere sulla 02 qualche valore da andare a prendere dopo. ovviamente però non dovrete dimenticare dove avete messo i dati! per questo è meglio organizzare la cosa come un vettore di int (il tipo di grandezza massima) allineato, e il cui indirizzo è mantenuto in un rgistro. ora, con semplici immediati (ricordate equ), potrete accedere a qualsiasi cosa vogliate (dubito che abbiate più di 255 variabili), tramite l'indirizzamento scostato (quello con il [RX, #numero]).
la seconda alternativa invece è più integrata nel sistema, ma più delicata.
infatti potrete pushare (accatastare) sullo stack un qualsiasi valore, caricare il nuovo dato in un registro, fare l'operazione e poi poppare (togliere) il valore. RICORDATE CHE ALL'INIZIO E ALLA FINE DEL PROGRAMMA ASM LO STACK DEVE ESSERE NELLO STESSO STATO! ovvero, POPPATE SEMPRE CIO' CHE PUSHATE!
questo perchè altrimenti il programma esterno (la ROM) si ritroverà dati non coerenti e anrà in crash (nel migliore dei casi sarà tutto glitchato)
Poi voi in mezzo alla vostra pila personale potrete fare tutte le vostre porcherie (so che le farete, anche se dovrebbe essere vietato da un'autorità universale), come ad esempio prendere un valore dal mezzo (se lo fate con una pila di piatti vedete che vi succede... XD)... l'importante però è che alla fine della vostra funzione lo stack sia come l'avete trovato.
la terza soluzione, che è un po' scontata, prevede di utilizzare i registri da 8 a 12. il problema è che pochissimi opcodes li trattano, perciò sono scomodi. e comunque dovrete depositarne il contenuto con uno dei metodi di prima ^^".
ora c'è una nuova tipologia di esercizio: io vi darò una funzione, e dovrete rispondere cosa fanno. le prime sono di esempio.
1)
avete due files, quello del programma e quello di utility.
Codice:
.thumb
.equ input, 0x2000000
.ascii "inizio programma" @; scrive sul file binario
.align 4, 0x0
PUSH {R0-R4, LR}
main:
LDR R2, =input
LDR R4, [R2]
MOV R0, R4
MOV R1, #4
BL utility_main
CMP R0, #0
BNE no
MOV R0, R4 @; riprendo il dato parcheggiato
MOV R1, #100
BL utility_main
CMP R0, #0
BNE si
MOV R0, R4
MOV R1, #25
LSL R1, #4
BL utility_main
CMP R0, #0
BNE no
si:
MOV R0, #1
LDR R2, =input
STRB R0, [R2]
b return
no:
MOV R0, #0
LDR R2, =input
STRB R0, [R2]
return:
POP {R0-R4, PC}
.include "lib/utility.s" @; entro in una cartella per prendere l'utility
@; l'ho messo in fondo perchè il compilatore non ha capacità di riconoscere il programma prinicipale, compila solo
@; nell'ordine in cui trova il codice, perciò così abbiamo subito il nostro programma all'inizio del file binario
@; (utile per fare eventualmente un callasm); mentre le librerie non ci interessano e rimarranno confinate in fondo.
Codice:
.THUMB
.ALIGN 4, 0xFF
utility_main:
PUSH {R2-R6,LR}
MOV R2, #0
MOV R3, #0
MOV R5, R0
MOV R4, R1
SWI #0X6
CMP R1, R4
BHI utility_correggi
B utility_fine
utility_correggi:
NEG R1, R1
SUB R1, R1, #1
utility_fine:
MOV R0, R1
POP {R2-R6,PC}
innanzitutto scopriamo cosa fa l'utiliti. R0 e R1 sono parametri, in quanto usati senza essere pushati. notiamo inoltre che usa lo swi del div, dunque sarà qualcosa attinente alla divisione. noi sappiamo l'output del div, e vediamo che la routine è interessata al R1, ovvero il modulo. anzi, la funzione ritorna proprio quello in R0. ma cos'è quel pezzo prima della fine? se il modulo è maggiore del denominatore (#per una questione che mi son dimenticato di spiegare, si chiama "complemento a due", se volete cercarla su internet o se no mandatemi un messaggio), significa che il numero è necessariamente negativo, dunque lo nega e sottrae 1, ovvero ottiene lo stesso numero positivo.
dunque la routine restituisce il valore assoluto del modulo tra R0 e R1.
cosa fa il file principale?
-controlla se un numero è divisibile per 4
--se non è divisibile restituisce 0
--altrimenti
---controlla se è divisibile per 100
----se no, restituisce 1
----altrimenti
-----controlla se è divisibile per 400 (25*2^4)
-----restituisce la stessa verità del'ultimo controllo.
questo è palesemente l'algoritmo di controllo della bisestilità di un anno.
(la comunicazione con l'esterno avviene tramite RAM e non tramite ritorno perchè è stata pensata per essere usata in uno script)
consiglio: usate le librerie, aiuteranno a scrivere molto meno!
in particolare, potreste fare dei "wrapper" per le funzioni swi, come la precedente, dato che fanno spesso e volentieri macello con i registri, potreste trovarvi in difficoltà. dunque con una routine come questa annullerete l'effetto caos e anzi ritornerete in modo elegante ciò che vi serve.
#calcolatrice
compito
vi consiglio di trovare prima una soluzione con gli schemi a blocchi. e dato che non sono necessarie molte variabili, vi consiglio anzi di tradurre 1:1 le singole strutture in blocchi di codice assemly (ad esempio tutte le sequenze in una sequenza asm), e poi di etichettarli. così potrete facilmente creare il controllo del flusso di esecuzione.
- verificare se un vettore è ordinato
- verificare se un vettore contiene elementi tutti uguali
- bonus: compattare un vettore (eliminare i valori duplicati e quelli pari a 0)
consigli:
- inutile dire che i cicli saranno d'importanza fondamentale.
- non avete limitazioni oltre alle richieste. (a buon intenditor... vabbè ve la spiego: non vi ho detto di che tipo è il vettore, dunque sceglietene uno comodo... vabbè ve lo dico ancora: di sicuro non sarà il tipo booleano o short, ma un tipo che sfrutta appieno la tecnologia del processore...)
- per l'ultimo, prima create una funzione per individuare gli zeri e scorrere a "sinistra" (nella memoria) tutte le celle successive. poi create una funzione che itera su tutto l'array in cerca di valori duplicati, che verranno "marcati" con degli 0. poi fate ripassare la funzione di eliminazione degli zeri.
è vero, questo algoritmo non è il massimo dell'efficienza (anzi è il male in persona), ma sicuramente è molto intuitivo, dunque di facile realizzazione.
è possibile utilizzare sia l'algoritmo iterativo che ricorsivo, dunque buona fortuna! ^^
#intersezione di 2 vett IN C
cosa fanno queste routine?
1)
Codice:
.thumb
.align 2, 0xFF
.equ input, 0x2000000
main:
Push {r0-r4, lr}
ldr r1, =input
ldr r0, [r1]
bl func
str r0, [r1]
pop {r0-r4, pc}
func:
push {r1-r4, lr}
cmp r0, #1
beq return
cmp r0, #0
beq return
mov r1, r0
sub r0, #1
bl func
mul r0, r1
return:
pop {r1-r4, pc}
#fare: palindromo/-
anche per stavolta mandatemi i compiti via MP, più avanti studierò un sistema per evitare che gli "esterni" "riciclino" i vostri compiti (perchè do per scontato che non vi copiate tra voi

).
#nel caso non vi basti, c'è pure il documento di jpan su pc ~
crediti: gbatek, tonc