Newsgroup: it.comp.lang.c
Titolo: Algoritmo per copiare bit

Ragazzi datemi una mano con questo algoritmo.
In memoria ho un array di unsigned char bidimensionale che mi
rappresenta un frame di un display a 2 colori. Il primo indice
rappresenta la coordinata verticale (indice 0, riga superiore). Il
secondo indice rappresenta un gruppo di 8 pixel in orizzontale (indice
0, i primi 8 pixel a sinistra). Il bit più significativo è il pixel
più a sinistra.
  unsigned char f[32][24];   /* frame di 192x32 pixel */
Ho poi un array lineare di unsigned char che mi rappresenta una
immagine (sempre a 2 colori e sempre organizzata nello stesso modo a
gruppi di 8 pixel).
  unsigned char btm[] = { ... };
L'immagine può avere larghezza, in pixel, qualsiasi (non
necessariamente multipla di 8). In questo caso, solo i bit più
significativi dell'ultimo byte di ogni linea dell'immagine sono usati.
Per esempio, un rettangolo di 11 pixel di larghezza e 4 di altezza è
così definito:
  unsigned char btm[] = { 0xFF, 0xE0, 0xFF, 0xE0, 0xFF, 0xE0, 0xFF,
0xE0 };
Sicuramente i bit non usati di una bitmap sono a zero.
Bene, devo implementare un algoritmo che mi copia questa bitmap in una
posizione qualsiasi del frame, senza cancellare i pixel adiacenti. Io
ho scritto questo:
------
void gui_bitblt (const unsigned char *btm, unsigned int xl, unsigned
int yl, unsigned int x0, unsigned int y0)
{
  unsigned char av = 8 - (x0 & 0x07);
  unsigned char bv = x0 & 0x07;
  unsigned char bbv = (xl - av) & 0x07;
  unsigned char aav = av >= xl ? xl : 0;
  unsigned char expr1 = 0xff << av;
  unsigned char expr2 = (0xff << av) | (0xff >> (bv + aav));
  unsigned char expr3 = 0xff << (8 - bv - aav);
  unsigned char expr4 = 0xff >> bbv;
  unsigned char expr5 = 0xff << (8 - bbv);
  unsigned char expr6 = (xl - av) >> 3;
  x0 >>= 3;
  while (yl--) {
    int i;
    unsigned char *f = &fb[y0++][x0];
    if (aav) {
      *f &= expr2;
      *f++ |= (*btm++ >> bv) & expr3;
      continue;
    } else {
      *f &= expr1;
      *f++ |= (*btm++ >> bv);
    }
    for (i = 0; i < expr6; ++i) {
      *f++ = (*(btm - 1) << av) | (*btm >> bv);
      btm++;
    }
    if (bbv) {
      *f &= expr4;
      if (av == 8)
        *f |= *btm++ & expr5;
      else {
        *f |= ((*(btm - 1) << av) | (*btm >> bv)) & expr5;
        btm++;
      }
    }
}
------
Siccome devo ottimizzare al massimo il tempo di esecuzione della
routine, ho precalcolato alcune quantità che vengono usate all'interno
del ciclo principale.
Dovrebbe funzionare... dico dovrebbe perchè alcuni test che ho fatto
sembrano positivi, però non so se ho provato tutto. Inoltre la
funzione è diventata ormai complicata e non riesco neanche a leggerla
molto.
Voi potete fare di meglio? Considerate che dovrebbe funzionare sempre,
anche con larghezza della bitmap molto piccola (tipo 1 pixel).
C'è un modo semplice per poter fare una copia della bitmap in modalità
reverse o in modalità XOR con il contenuto attuale del frame?


Non molto tempo fa (qualche mese, mi sembra) proprio su questo gruppo
c'era stata un domanda identica, e se non ricordo male c'era anche
molto codice. Purtroppo non sono riuscito a ritrovare il thread, ma se
cerchi un po' vedrai che lo trovi.


Ok, google mi ha aiutato:
http://groups.google.it/group/it.hobby.elettronica.digitale/browse_thread/thread/5fccba82ff522df2/ac240c68f0d3fa09
Non so però se è quello che cercavi.

 Non so però se è quello che cercavi.
Sì, se vedi bene quel thread l'ho iniziato io.
Ho cercato di seguire i suggerimenti dati durante quella discussione
ed è venuto fuori il mostro di
algoritmo che vi ho postato ora. Volevo solo capire se si poteva fare
di meglio, visto che è diventato
illeggibile e probabilmente non funziona sempre.


Fossi in te come prima cosa darei un nome significativo (o anche una
sigla basterebbe) alle variabili expr[1-6]. Poi non capisco da dove
derivano i 3 e i 0x07. Ultima cosa non riesco a leggere il codice
senza studiarmelo, ma mi sembra che ci sono troppi "if" dentro un
ciclo, cosa che mi suona concettualmente strana per il problema che
affronti.
Magari una piccola descrizione dell'algoritmo? :-)

 Magari una piccola descrizione dell'algoritmo? :-)
La strategia è quella di dividere la copia della bitmap nella copia
delle
righe: da qui il ciclo principale while() su tutte le linee.
Per ogni linea, la copia si riduce in 3 fasi:
  1- modifica parziale del primo byte del framebuffer (primo if)
  2- modifica totale dei byte centrali (ciclo for)
  3- modifica parziale dell'ultimo byte (ultimo if)
E' ovvio che in casi particolari la seconda e/o terza fase potrebbero
non
essere necessarie.
Ecco il codice commentato:
---
void
gui_bitblt (const unsigned char *btm,
    unsigned int xl, unsigned int yl,
    unsigned int x0, unsigned int y0)
{
    /* Ogni byte della bitmap può essere diviso in due parti:
     * - av pixel a sinistra che devono essere shiftati a destra
     * - bv pixel a destra che devono essere shiftati a sinistra
     * Ovviamente av+bv=8. Notare che lo shift a destra è di bv bit;
lo shift a
     * sinistra è di av bit.
     *
     * Esempio: x0 = 3.
     * Il primo byte della bitmap è diviso in 5 (av) pixel da shiftare
a destra
     * di 3 (bv) bit e 3 (bv) pixel da shiftare a sinistra di 5 (av).
     *
     * L'algoritmo si basa quindi su un ciclo for che effettua queste
due
     * operazioni su ogni byte del framebuffer. Solo il primo e
l'ultimo byte
     * del framebuffer (a parte casi particolari) devono essere
modificati in
     * parte. Gli altri byte intermedi vengono modificati
completamente (vedi
     * ciclo for).
     *
     * C'è un caso molto particolare in cui la bitmap ha pochi pixel
in
     * larghezza e non vanno usati tutti gli av pixel (vedi variabile
aav).
     */
    unsigned char bv = x0 & 0x07;          /* Num. pixel da shiftare a
dx */
    unsigned char av = 8 - bv;             /* Num. pixel da shiftare a
sx */
    unsigned char bbv = (xl - av) & 0x07;  /* Num. pixel nell'ultimo
byte */
    unsigned char aav = av >= xl ? xl : 0; /* Num. pixel caso bitmap
strette */
    /* Mi calcolo un po' di espressioni che verrano usate più volte
nel ciclo
     * successivo (si risparmia un po' di tempo). */
    unsigned char expr1 = 0xff << av;
    unsigned char expr2 = expr1 | (0xff >> (bv + aav));
    unsigned char expr3 = 0xff << (8 - bv - aav);
    unsigned char expr4 = 0xff >> bbv;
    unsigned char expr5 = 0xff << (8 - bbv);
    unsigned char expr6 = (xl - av) >> 3;
    x0 >>= 3;
    while (yl--) {
        int i;
        unsigned char *f = &fb[y0++][x0];
        /* Primo byte da modificare parzialmente (quindi è necessario
fare
         * un'operazione di mascheramento e non di assegnazione, come
nel ciclo
         * for). In un caso particolare (av=8), questa procedura
coincide con
         * l'assegnamento.
         * Bisogna stare attenti al caso di pochi pixel (aav > 0). */
        if (aav) {
            *f &= expr2;
            *f++ |= (*btm++ >> bv) & expr3;
            continue;
        } else {
            *f &= expr1;
            *f++ |= (*btm++ >> bv);
        }
        /* Loop principale in cui i byte del framebuffer vanno
modificati
         * completamente, quindi si può fare direttamente un
assegnamento
         * (senza mascherare). */
        for (i = 0; i < expr6; ++i) {
            *f++ = (*(btm - 1) << av) | (*btm >> bv);
            btm++;
        }
        /* Ultimo byte da modificare parzialmente (anche qui,
operazione di
         * mascheramento). f punta all'ultimo byte del framebuffer da
         * modificare. btm punta all'ultimo byte della bitmap (o, nel
caso
         * particale bbv <= bv, già al successivo). */
        if (bbv) {
            *f &= expr4;
            *f |= ((*(btm - 1) << av) | (*btm >> bv)) & expr5;
            if (bbv > bv) btm++;
        }
    }
}
---
Penso che il tempo di esecuzione sia elevato per i numerose shift che
bisogna
fare. Per ottimizzare ulteriormente il tempo di esecuzione, mi viene
in mente
soltanto di sostituire le operazioni di shift nelle expr[1-6] con
apposite tabelle.
Altri suggerimenti?

 apposite tabelle.
contando che le expr[1-6] le calcoli solo una volta per esecuzione
della funzione, non credo guadagneresti piu' di tanto.
I miei consigli sono:
- usa nomi di variabili decenti: av,bv,... non si capisce cosa servano
=> si perde in leggibilita'
- unsigned char *f = &fb[y0++][x0]; => cos'e' fb? Perche' non lo passi
anche lui nei parametri? mettere y0++ li non serve a niente (a livello
di velocita' di esecuzione). Anzi, in certi processori (roba piccola,
a 8bit) allunga il codice assembly.
- controlla il codice assembly generato per vedere se il compilatore
e' efficiente nel tradurre il tuo codice.
Ciao Jack

 wrote:

Togli gli shift e metti divisioni / moduli. E' lavoro del compilatore,
non tuo. Come fai a sapere che shiftare di tre sia più veloce che
dividere per otto sul target finale? Stessa cosa vale per le
espressioni: sicuramente il compilatore riesce a mettere in qualche
registro le "costanti".
Altra cosa: scrivere btm[1] o *(btm+1) è uguale.
Ultima: le espressioni "*f++ |= (qualcosa)". Non è assolutamente
facile riuscire a capire cosa viene incrementato quando.
Per il resto l'algoritmo è ok :-) Quello che farei io per aumentare la
leggibilità (e di quasi niente le performances) sarebbe fare due
funzioni di copia, una per il caso "allineato" e una no (più
ovviamente una terza funzione che con un if chiama l'una o l'altra).
Avrai tre funzioni più corte e più leggibili, senza if dentro i
cicli. :D

 e' efficiente nel tradurre il tuo codice.
Sembra di sì, non penso si riesca a fare molto di più da quella parte.
Magari è l'algoritmo in sè che si può cambiare, chissà.
In pratica quella funzione la utilizzerò molte volte per disegnare i
caratteri
di un font grafico non proporzionale. Per disegnare una stringa,
disegno i
singoli caratteri che sono memorizzati in array. E' un compito
abbastanza
semplice, ma l'organizzazione del display a 8 pixel rende il tutto
molto
complicato.

 cicli. :D
Il caso allineato sarebbe banale, il caso non allineato sarebbe
comunque
uguale alla funzione che ho già ora. I due if all'interno del ciclo
non
sono relativi all'allineamento o meno, ma ad altri casi particolari.
Il primo if è per bitmap molto corte dove il primo byte deve essere
modificato
solo centralmente, lasciando inalterati i bit a sinistra e a destra.
Il secondo if è per l'ultimo byte del framebuffer che può essere
modificato
solo parzialmente.
Quello che cercavo di fare, senza successo, è eliminare i due if
cercando di
far funzionare l'algoritmo anche nei casi "degeneri".

 dalla tabella.
questo perche' il tuo micro ha pochi registri, probabilmente un
accumulatore e un paio di registri di appoggio, difficile che ci
possano stare delle costanti.
Una cosa che potresti fare (ma significa rivedere tutto l'algoritmo)
e' di gestire 2 byte per volta invece che uno visto che usi un micro a
16 bit.
Cioe' invece di mettere 16 pixel in 2 variabili da 1 byte li metti in
una variabile di 2 byte (tipicamente int invece che char).
Questo perche' spesso i micro piccoli lavorano meglio quando le
variabili sono della stessa lunghezza della "parola" del micro (e' una
questione di indirizzamento)
Ciao Jack


eheh :-)
A questo punto un po' più di sforzo e conviene usare interi con sizeof
() messi dove serve.
P.S. Comunque non vedo il problema di prestazioni per cose del genere.
Il display alla fine ha anche i suoi tempi di refresh che non sono
proprio proprio immediati.

 questione di indirizzamento)
In effetti si può provare. Penso però che il guadagno non dipenda da
un
più veloce accesso alla memoria, piuttosto dalle minori operazioni che
si fanno (se la linea della bitmap è di 16 pixel, faccio una
operazione
piuttosto che due).
Considerando però che i glifi dei caratteri del mio font hanno
larghezza
massima di 8 pixel, penso che non ci sia un grande vantaggio.

 proprio proprio immediati.
Questo sì, però il micro non deve fare solo quello...