Moltiplicazione con istruzione nativa su micro AVR

[ipervale]

Ciao ragazzi,
nei file d'esempio per i micro avr 8 bit ho trovato questo codice che è possibile usare sui core dotati dell'istruzione 'mul'

Codice: Seleziona tutto

;******************************************************************************
;*
;* FUNCTION
;*   mul16x16_32
;* DECRIPTION
;*   Unsigned multiply of two 16bits numbers with 32bits result.
;* USAGE
;*   r19:r18:r17:r16 = r23:r22 * r21:r20
;* STATISTICS
;*   Cycles :   17 + ret
;*   Words :      13 + ret
;*   Register usage: r0 to r2 and r16 to r23 (11 registers)
;* NOTE
;*   Full orthogonality i.e. any register pair can be used as long as
;*   the 32bit result and the two operands does not share register pairs.
;*   The routine is non-destructive to the operands.
;*
;******************************************************************************

mul16x16_32:
   clr   r2
   mul   r23, r21      ; ah * bh
   movw   r19:r18, r1:r0
   mul   r22, r20      ; al * bl
   movw   r17:r16, r1:r0
   mul   r23, r20      ; ah * bl
   add   r17, r0
   adc   r18, r1
   adc   r19, r2
   mul   r21, r22      ; bh * al
   add   r17, r0
   adc   r18, r1
   adc   r19, r2
   ret


Siccome sono molto ignorante in matematica mi piacerebbe sapere qual è il principio che c'è dietro questa implementazione e se è possibile ampliarla anche per moltiplicazioni diverse (tipo un intero 16 bits x un intero 32/24 bits).
Sono sempre rimasto affascinato dai giochini che si riescono a fare in binario...

Grazie,
Valentino

[djnz]

Principio spiegato con i numeri decimali:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

[GuidoB]

Praticamente fai 4 moltiplicazioni a 8 bit per moltiplicare due numeri a 16 bit, ottenendo un risultato a 32 bit, giusto? Si può certamente estendere a fattori a 24 o più bit. Non ricordo l'algoritmo nei dettagli, ma l'ha spiegato chi mi ha preceduto. Non è difficile.

Per moltiplicare in binario è necessario conoscere solo le tabelline dello 0 e dell'1.
Per cui, seguendo lo stesso algoritmo della moltiplicazione manuale che si impara alle elementari, si moltiplica il moltiplicando per ogni cifra del moltiplicatore, e si sommano tutti i risultati, opportunamente fatti slittare a sinistra di tanti posti quanta è la posizione della cifra utilizzata del moltiplicatore.

Se la cifra per cui si moltiplica è 0, moltiplicando x 0 = 0.
Se la cifra per cui si moltiplica è 1, moltiplicando x 1 = moltiplicando.

Utilizzando solo l'addizione e lo shift a sinistra, si può fare con una routine software (senza un moltiplicatore parallelo).

Se il moltiplicando ha n cifre e il moltiplicatore m cifre, per implementare un moltiplicatore parallelo c'è bisogno di m sommatori a n cifre, in ciascuno dei quali entrano il moltiplicando moltiplicato per la cifra corrispondente del moltiplicatore (quindi, o 0 o il moltiplicando stesso, cioè basta copiarlo), e la somma del sommatore opportunamente slittato, corrispondente alla cifra del moltiplicatore occupante la posizione immediatamente meno significativa rispetto alla attuale.

Alla fine si fa tutto con un po' di full adder, qualche half adder e un po' di porte AND che effettuano la moltiplicazione per 0 o per 1.
Con un moltiplicatore parallelo si può effettuare la moltiplicazione in un solo colpo di clock, quindi tanto velocemente quanto l'addizione.

Se le cifre sono molte, la propagazione dei riporti attraverso i full adder richiede più tempo. In tal caso, per incrementare la velocità, si adottano reti logiche di anticipazione del riporto.

Charles Babbage, nella prima metà dell'800, in piena età vittoriana, progettò un calcolatore meccanico programmabile (la macchina analitica), che aveva la RAM, la CPU con relativo microcodice e tante altre caratteristiche dei calcolatori elettronici moderni. Rimasi sbalordito al leggere che l'ALU aveva anche l'anticipazione del riporto, un livello di ottimizzazione che, non esistendo ancora calcolatori, poteva essere immaginato solo da un vero genio.
Si trattava di una macchina che calcolava in base 10, che non arrivò ad essere realizzata per la complessità, la mancanza di finanziamenti sufficienti, e il caratteraccio di Babbage che litigò con l'artigiano che lo aiutava a realizzarla.
Chi progettò l'ENIAC (il primo calcolatore elettronico, a valvole termoioniche) disse che nel progetto di Babbage c'era già tutto.

[xyz]

Gli AVR hanno la moltiplicazione con solo due registri a 8 bit e il risultato a 16 bit è messo nei registri R0 e R1. Per Moltiplicare due numeri a 16 bit devi scomporli in più moltiplicazioni a 8 bit, Hx e Lx sono registri a 8 con il byte alto e basso del numero a 16 bit Vx

Codice: Seleziona tutto

V1 = 256*H2 + L1
V2 = 256*H4 + L3

V1 * V2 = (256*H2 + L1) * (256*H4 + L3)
        = 65536*H2*H4 + 256*(H2*L3+H4*L1) + L1*L3

Servono 4 moltiplicazioni con le varie somme con riporto allineate in modo da ottenere il risultato a 32 bit su 4 registi a 8 bit

[ipervale]

Grazie a tutti per le risposte.
Non avevo minimamente pensato che l'algoritmo ricalcasse il sistema del calcolo manuale (anche perché mi sono dimenticato come si fa! )
Adesso posso divertirmi ad implementare anche moltiplicazioni con interi di dimensioni diverse.
E ho pure scoperto che dietro un semplice 'mul' c'è un mondo incredibile...

Di nuovo grazie a tutti
Valentino