[Vari] Context 1: Bitmap

[gugoXX]

Volevo aprire una serie di topic con alcuni esercizi che possono essere interessanti.
L'idea sarebbe quella di proporre una soluzione efficiente, indipendentemente dal linguaggio. Ovvero concentrandosi sugli algoritmi piuttosto che sulla implementazione nel linguaggio X.
Ovvio che poi soluzioni eleganti in ciascun linguaggio sono apprezzate.

Sia data una bitmap 1000x1000x8bit di profondita', immaginatela a toni di grigio, e codificatela come meglio vi aggrada o come il linguaggio propone.
Una matrice bidimensionale di byte e' considerata sufficiente, anche se non e' proprio una bitmap.
Si vorrebbe invertire l'ordine dei bit di ciascun byte di colore, effettuando in pratica uno specchio di ciascun byte, nel modo piu' efficiente.
Esempio 10001101 diventa 10110001, 00111101 diventa 10111100 e cosi' via.

Non e' richiesta la lettura di file o tantomeno la lettura di file tipizzati (gif, jpg, etc.), introducente l'input come meglio aggrada (certo che se si leggesse da file sarebbe meglio).

[^TiGeRShArK^]

mmm...
ma per invertire ogni byte di colore non si dovrebbe fare 255 - il valore del byte?
perchè nel post di sopra rivolti il byte anzichè fare 255 - byte?

[gugoXX]

Originariamente inviato da ^TiGeRShArK^

mmm...
ma per invertire ogni byte di colore non si dovrebbe fare 255 - il valore del byte?
perchè nel post di sopra rivolti il byte anzichè fare 255 - byte?

Si', hai ragione, non e' il negativo. E' un inverso che non ha forse molto senso colorimetrico.

Se c'e' 10010000 diventa 00001001

Alcuni che sono gia' di natura simmetrici restano cosi' come sono:
00011000 -> 00011000

[^TiGeRShArK^]

la soluzione + veloce in assoluto mi sa che è specificare l'endianess dei byte della matrice, ma non so se è possibile nei vari linguaggi...
altirmenti la prima che viene in mente è semplicemente prendere i bit ad uno ad uno e copiarli in un'altro byte in ordine inverso.

[banryu79]

Originariamente inviato da ^TiGeRShArK^

altirmenti la prima che viene in mente è semplicemente prendere i bit ad uno ad uno e copiarli in un'altro byte in ordine inverso.

Durante l'iterazione della matrice inserirei i risultati in una Hash Map dove la chiave è il byte originale e il valore il byte invertito: se il prossimo elemento da processare è già presente nell'hash map non occorre ricalcolarlo.

Probabilmente non è il massimo dell'efficienza ma potrebbe avere un senso all'aumentare delle dimensioni della matrice (della bitmap) ?

[^TiGeRShArK^]

Originariamente inviato da banryu79

Durante l'iterazione della matrice inserirei i risultati in una Hash Map dove la chiave è il byte originale e il valore il byte invertito: se il prossimo elemento da processare è già presente nell'hash map non occorre ricalcolarlo.

Probabilmente non è il massimo dell'efficienza ma potrebbe avere un senso all'aumentare delle dimensioni della matrice (della bitmap) ?

mmm..vero, tanto hai solo 256 valori possibili e quindi aumenteresti l'efficenza di molto
Chissà come fanno a i vari linguaggi a gestire l'endianess ora che ci penso

[banryu79]

Originariamente inviato da ^TiGeRShArK^

Chissà come fanno a i vari linguaggi a gestire l'endianess ora che ci penso

Non ne so nulla

[marco.r]

Originariamente inviato da banryu79

Durante l'iterazione della matrice inserirei i risultati in una Hash Map dove la chiave è il byte originale e il valore il byte invertito: se il prossimo elemento da processare è già presente nell'hash map non occorre ricalcolarlo.

Probabilmente non è il massimo dell'efficienza ma potrebbe avere un senso all'aumentare delle dimensioni della matrice (della bitmap) ?

Perchè una Hash Map ?
Ti basta un array come cache

[banryu79]

Originariamente inviato da marco.r

Perchè una Hash Map ?
Ti basta un array come cache

Perchè non ci ho pensato a fondo, sono in ufficio, ho letto il post e ho scritto la prima cosa che mi è saltata in mente dopo aver letto la risposta di TigerShark.
Inoltre non ho esperienze solide con queste cose.

Inoltre stavo pensando in Java: le HashMap sono comode.

Come faresti con un unico array?

[^TiGeRShArK^]

Originariamente inviato da banryu79

Perchè non ci ho pensato a fondo, sono in ufficio, ho letto il post e ho scritto la prima cosa che mi è saltata in mente dopo aver letto la risposta di TigerShark.
Inoltre non ho esperienze solide con queste cose.

Inoltre stavo pensando in Java: le HashMap sono comode.

Come faresti con un unico array?

con l'array basterebbe creare un array di byte con 256 celle e mettere il byte rivoltato nella cella corrispondente al suo reciproco..

tipo se hai il byte 000000001 scriverai nell'indice 1 dell'array il byte 10000000

[marco.r]

Visto che hai solo 8 bit di valori, usi un array con 256 elementi

Qualcosa come il seguente (in C++)

typedef unsigned char uchar8; // o quel che è

uchar8 b0 = 1,
    b1=2,
    b2=4,
    b3=8,
    b4=16,
    b5=32,
    b6=64,
    b7=128;

uchar8 invert( uchar8 x )
{
  return ((x&b0)<<7) + ((x&b1) << 5) + ((x&b2) << 3) + ((x&b3) << 1)
    +((x&b4)>>1) + ((x&b5) >> 3) + ((x&b6) >> 5) + ((x&b7) >> 7);
}

void invertMatrix( uchar8** matrix, int rows, int cols )
{
  uchar8 inverted[256];
  for ( int i=0 ; i< 256 ; ++i )
  {
    inverted[i] = invert(i);
  }
  for ( int i=0 ; i<rows ; ++i )
  {
    for ( int j=0 ; j<cols ; ++j )
    {
      matrix[i][j] = inverted[ matrix[i][j] ];
    }
  }
}

[banryu79]

Geniale, stavo provando a rifletterci e appunto a capire come mappare l'indice dell'array con il byte originale.
Molto meglio della soluzione con l'hashmap, grazie per la spiegazione

OT:
se la Bitmap fosse a profondità maggiore, diciamo 16 bit, come faresti?

Non capisco bene questo:

uchar8 invert( uchar8 x )
{
return ((x&b0)<<7) + ((x&b1) << 5) + ((x&b2) << 3) + ((x&b3) << 1)
+((x&b4)>>1) + ((x&b5) >> 3) + ((x&b6) >> 5) + ((x&b7) >> 7);
}

Conosco il significato degli opertori bitwise ma non avendoli mai usati ne scritto algoritmi con essi stento a interpretare tutta l'operazione.
Se hai tempo e puoi spiegarlo mi faresti un favore, sennò me lo guardo con calma stasera.

[^TiGeRShArK^]

Originariamente inviato da banryu79

Geniale, stavo provando a rifletterci e appunto a capire come mappare l'indice dell'array con il byte originale.
Molto meglio della soluzione con l'hashmap, grazie per la spiegazione

OT:
se la Bitmap fosse a profondità maggiore, diciamo 16 bit, come faresti?

Non capisco bene questo:

Conosco il significato degli opertori bitwise ma non avendoli mai usati ne scritto algoritmi con essi stento a interpretare tutta l'operazione.
Se hai tempo e puoi spiegarlo mi faresti un favore, sennò me lo guardo con calma stasera.

ricava il bit 0 facendo un and con 1 e lo shifta di 7 a sinistra in modo da mandarlo al posto del bit + significativo, prende il bit 1 e fa la stessa cosa, ma poichè è + vicino di uno al centro e poichè lo deve spostare nella posizione del bit + significativo - 1 allora è sufficiente spostarlo di 5.
Lo stesso fa con gli altri bit e infine somma il risultato

[Big Bamboo]

Forse per invertire è meglio fare a gruppi di bit invece che singoli

inverto prima i 4 bit destra - sinistra
byte = (byte & 0x0F) << 4 | (byte & 0xF0) >> 4;

poi con 2 maschere sposti 2 bit per ogni lato
byte = (byte & 0x33) << 2 | (byte & 0xCC) >> 2;

ed infine i singoli bit
byte = (byte & 0x55) << 1 | (byte & 0xAA) >> 1;

Con il codice assembler si potrebbe effettivamente valutare la soluzione migliore

[gugoXX]

Dai vabbene.
Questo era il riscaldamento e ovviamente abbiamo trovato la soluzione ottima (ovviamente O(N) dove N e' il numero di pixel), e anche l'algoritmo corretto, ovvero usare un array.

Direi che si puo' riassumere con
Quando vangono utilizzati molti se non tutti i valori possibili di un range di dominio, allora e' bene usare un array, altrimenti una hastable.

Ottimo anche l'algoritmo per trovare lo speculare di un byte, che con una manciata di istruzioni senza cicli e senza salti ottiene subito il risultato.

Passiamo oltre.

[^TiGeRShArK^]

Originariamente inviato da gugoXX

Dai vabbene.
Questo era il riscaldamento e ovviamente abbiamo trovato la soluzione ottima (ovviamente O(N) dove N e' il numero di pixel), e anche l'algoritmo corretto, ovvero usare un array.

Direi che si puo' riassumere con
Quando vangono utilizzati molti se non tutti i valori possibili di un range di dominio, allora e' bene usare un array, altrimenti una hastable.

Ottimo anche l'algoritmo per trovare lo speculare di un byte, che con una manciata di istruzioni senza cicli e senza salti ottiene subito il risultato.

Passiamo oltre.

Bene, avanti così!

[Oceans11]

Originariamente inviato da ^TiGeRShArK^

mmm...
ma per invertire ogni byte di colore non si dovrebbe fare 255 - il valore del byte?
perchè nel post di sopra rivolti il byte anzichè fare 255 - byte?

ehm...scusate raga....ma dove fate 255-byte????
scrivere il byte da destra verso sinistra mica funziona!?!

Non ci vuole: byte XOR 0xFF???

Premetto che la soluzione con gli shift mi ha ingrippato parecchio....

[marco.r]

Originariamente inviato da banryu79

Geniale, stavo provando a rifletterci e appunto a capire come mappare l'indice dell'array con il byte originale.
Molto meglio della soluzione con l'hashmap, grazie per la spiegazione

OT:
se la Bitmap fosse a profondità maggiore, diciamo 16 bit, come faresti?

Con 16 bit ancora ti conviene usare la stessa tecnica 2^16 = 65k byte di memoria per l'array, praticamente niente. Ovviamente se l'array e' piu' grande, altrimenti non serve a niente .
Se i valori sono maggiori penso abbia senso utilizzare comunque una tabella piu' piccola e "cachare" a pezzi.
Ad esempio usando qualcosa tipo

makeUint32( uchar8 x3, uchar8 x2, uchar8 x1, uchar8 x0 )
{
    return (x3<<24) + (x2<<16) + (x1<<8) + x0;
}

uchar8 byte(int n,uint32 x)
{
  return (x & (0xff << (n*8))) >> (n*8);
}

/* ... prepara la tabella inverted come sopra ... */

uint32 invert32( uint32 x)
{
  return makeUint32( inverted[byte(3,x)], inverted[byte(2,x)], inverted[byte(1,x)], inverted[byte(0,x)]);
}

O qualcosa del genere (disclaimer: non ho provato il codice ).
Magari si puo' scrivere lo smistamento dei vari bit in modo piu' veloce (non e' una cosa di cui mi occupo abitualmente), ma l'idea e' comunque quella.

[^TiGeRShArK^]

Originariamente inviato da Oceans11

ehm...scusate raga....ma dove fate 255-byte????
scrivere il byte da destra verso sinistra mica funziona!?!

Non ci vuole: byte XOR 0xFF???

Premetto che la soluzione con gli shift mi ha ingrippato parecchio....

infatti non lo facciamo in nessun posto
gugoxx intendeva che bisognava invertire il byte NON in senso colorimetrico (che si ottiene con 255 - byte), ma bisognava fare un mirror del byte attorno all'asse centrale...
ad esempio 10000000 diventa 00000001, 01000000 diventa 00000010 e così via

[Vincenzo1968]

È ancora valido questo contest? Posso postare la mia soluzione?

Ciao