[Varie] Bitwise operations

[sottovento]

Allora non sono l'unico!!!

//TCP Header structure as per RFC 793
struct tcphdr {
 u_short th_sport;  /* source port */
 u_short th_dport;  /* destination port */
 tcp_seq th_seq;   /* sequence number */
 tcp_seq th_ack;   /* acknowledgement number */
#if BYTE_ORDER == LITTLE_ENDIAN
 u_int th_x2:4,  /* (unused) */
  th_off:4;  /* data offset */
#endif
#if BYTE_ORDER == BIG_ENDIAN
 u_int th_off:4,  /* data offset */
  th_x2:4;  /* (unused) */
#endif
 u_char th_flags;
#define TH_FIN 0x01
#define TH_SYN 0x02
#define TH_RST 0x04
#define TH_PUSH 0x08
#define TH_ACK 0x10
#define TH_URG 0x20
#define TH_ECE 0x40
#define TH_CWR 0x80
#define TH_FLAGS (TH_FIN|TH_SYN|TH_RST|TH_ACK|TH_URG|TH_ECE|TH_CWR)
 
 u_short th_win;   /* window */
 u_short th_sum;   /* checksum */
 u_short th_urp;   /* urgent pointer */
};

Sembra che, chi usa i bitfield, consideri che si parta sempre da lsb.
Nel codice copiato, si fa la distinzione fra big endian/little endian ma non e' che faccia senso, visto che definiscono 8 bit.

Tornando a bomba sui linguaggi ad alto livello pascal/python/modula 2/...: come diceva cdimauro, i set hanno una implementazione piu' "matematica", corrispondente agli insiemi.
I bitfield e le operazioni di masking del C, no! Questo perche' sono fatte in primis per l'accesso all'hardware, cosa che certamente i linguaggi citati non prevedono

[The_ouroboros]

Originariamente inviato da sottovento

Nel codice copiato, si fa la distinzione fra big endian/little endian ma non e' che faccia senso, visto che definiscono 8 bit.

Ha senso dai 16bit in su in effetti

[The_ouroboros]

Originariamente inviato da sottovento

Tornando a bomba sui linguaggi ad alto livello pascal/python/modula 2/...: come diceva cdimauro, i set hanno una implementazione piu' "matematica", corrispondente agli insiemi.
I bitfield e le operazioni di masking del C, no! Questo perche' sono fatte in primis per l'accesso all'hardware, cosa che certamente i linguaggi citati non prevedono

Sono a + alto livello del C, quindi + astratti...
Il C è quasi un asm astratto a mio parere

[cdimauro]

Originariamente inviato da The_ouroboros

io le uso entrambe per non limitarmi ma devo dire che a forza di vederla la AT&T non mi spiace più come prima.
I vari l,b,w sono comodi.
Forse il posizionamento degli offset è scomodo a prima vista

Intel Syntax

instr   foo,segreg:[base+index*scale+disp]

mov     eax,[ebx+20h]

add     eax,[ebx+ecx*2h

lea     eax,[ebx+ecx]

sub     eax,[ebx+ecx*4h-20h]


AT&T Syntax

instr   %segreg:disp(base,index,scale),foo

movl    0x20(%ebx),%eax

addl    (%ebx,%ecx,0x2),%eax

leal    (%ebx,%ecx),%eax

subl    -0x20(%ebx,%ecx,0x4),%eax

Sarà questione di abitudine, ma trovo orribile e poco leggibile la sintassi AT&T.

Visto che hai tirato in ballo i suffissi, beh, sono inutili! Se specifichi che il registro di destinazione è eax, è già evidente che sto usando un long. Avrebbe senso per la memoria, ma se la sorgente è eax, la destinazione sarà a 32 bit... Con gli immediati il discorso cambierebbe, ma nel codice più frequente il suffisso nella sintassi AT&T è superfluo.

Originariamente inviato da sottovento

Allora non sono l'unico!!!

//TCP Header structure as per RFC 793
struct tcphdr {
 u_short th_sport;  /* source port */
 u_short th_dport;  /* destination port */
 tcp_seq th_seq;   /* sequence number */
 tcp_seq th_ack;   /* acknowledgement number */
#if BYTE_ORDER == LITTLE_ENDIAN
 u_int th_x2:4,  /* (unused) */
  th_off:4;  /* data offset */
#endif
#if BYTE_ORDER == BIG_ENDIAN
 u_int th_off:4,  /* data offset */
  th_x2:4;  /* (unused) */
#endif
 u_char th_flags;
#define TH_FIN 0x01
#define TH_SYN 0x02
#define TH_RST 0x04
#define TH_PUSH 0x08
#define TH_ACK 0x10
#define TH_URG 0x20
#define TH_ECE 0x40
#define TH_CWR 0x80
#define TH_FLAGS (TH_FIN|TH_SYN|TH_RST|TH_ACK|TH_URG|TH_ECE|TH_CWR)
 
 u_short th_win;   /* window */
 u_short th_sum;   /* checksum */
 u_short th_urp;   /* urgent pointer */
};

Sembra che, chi usa i bitfield, consideri che si parta sempre da lsb.
Nel codice copiato, si fa la distinzione fra big endian/little endian ma non e' che faccia senso, visto che definiscono 8 bit.

Avrebbe senso soltanto se il compilatore partisse dall' MSB anziché dall'LSB.

Per il resto, con 8 bit l'endianess c'entra poco.

Tornando a bomba sui linguaggi ad alto livello pascal/python/modula 2/...: come diceva cdimauro, i set hanno una implementazione piu' "matematica", corrispondente agli insiemi.

Per questo si apprezzano di più: sono più comodi e intuitivi.

I bitfield e le operazioni di masking del C, no! Questo perche' sono fatte in primis per l'accesso all'hardware, cosa che certamente i linguaggi citati non prevedono

Già: è di più di basso livello.

Originariamente inviato da The_ouroboros

Sono a + alto livello del C, quindi + astratti...
Il C è quasi un asm astratto a mio parere

Per questo viene considerato come linguaggio di medio-basso livello.

[The_ouroboros]

Originariamente inviato da cdimauro

Sarà questione di abitudine, ma trovo orribile e poco leggibile la sintassi AT&T.

Visto che hai tirato in ballo i suffissi, beh, sono inutili! Se specifichi che il registro di destinazione è eax, è già evidente che sto usando un long. Avrebbe senso per la memoria, ma se la sorgente è eax, la destinazione sarà a 32 bit... Con gli immediati il discorso cambierebbe, ma nel codice più frequente il suffisso nella sintassi AT&T è superfluo.

Dato che si trovano entrambi... e nel mondo *nix AT&T è lo standard

[cdimauro]

Capisco, ma c'è da spararsi a lavorare con quella sintassi. Lavorare in assembly è già un martirio: figuriamoci in quelle condizioni.

Io, ad esempio, non ho apprezzato nemmeno la sintassi "classica", e almeno per 65C02 e PIC Microchip ho realizzato delle mie versioni di assembly ad alto livello, che mi consentono di scrivere codice di basso livello, ma in maniera più pratica e comoda.

[sottovento]

Originariamente inviato da cdimauro

Avrebbe senso soltanto se il compilatore partisse dall' MSB anziché dall'LSB.

Non proprio: partisse dall'msb occorrerebbe specificare anche quale e' il bit piu' significativo nell'intervallo! In pratica, si avrebbe una pericolosissima inversione del peso dei bit. Questo spiega perche', nonostante lo standard non dica nulla sulla allocazione dei bit, partono tutti da lsb.

Originariamente inviato da cdimauro

Per il resto, con 8 bit l'endianess c'entra poco.

Giustissimo

Originariamente inviato da cdimauro

Per questo si apprezzano di più: sono più comodi e intuitivi.

Giusto, pero' se quel bit serve ad accendere la lavatrice, con linguaggi a piu' alto livello resti con la biancheria sporca

Originariamente inviato da cdimauro

Già: è di più di basso livello.

Per questo viene considerato come linguaggio di medio-basso livello.

Di pure basso livello senza paura, ed andrebbe trattato come tale, anche se spesso non succede.

Allora, guardando in giro posso dire: cdimauro ha ragione su tutta la linea, non esiste assolutamente uno standard. Tuttavia a causa di evidenti limitazioni nella soluzione opposta, l'allocazione partendo da lsb e' uno standard de-facto. Sempre che, con il linguaggio C, si possa parlare di standard

[The_ouroboros]

Originariamente inviato da cdimauro

Capisco, ma c'è da spararsi a lavorare con quella sintassi. Lavorare in assembly è già un martirio: figuriamoci in quelle condizioni.

Dato che al momento è più un "lavoro" di debugging e lavoro principalmente su piattaforma *nix mi sono adattato.

C'è solo vantaggio a leggerle entrambe.

Cmq, uscendo un po dal seminato, sto dando un occhio ad ARM... non male come ABI, pi+ semplice di x86/x64 ma, per alcune operazioni, molto veloce.

[The_ouroboros]

Originariamente inviato da sottovento

Allora, guardando in giro posso dire: cdimauro ha ragione su tutta la linea, non esiste assolutamente uno standard. Tuttavia a causa di evidenti limitazioni nella soluzione opposta, l'allocazione partendo da lsb e' uno standard de-facto. Sempre che, con il linguaggio C, si possa parlare di standard

consuetudine diffusa?

[The_ouroboros]

Originariamente inviato da cdimauro

Io, ad esempio, non ho apprezzato nemmeno la sintassi "classica", e almeno per 65C02 e PIC Microchip ho realizzato delle mie versioni di assembly ad alto livello, che mi consentono di scrivere codice di basso livello, ma in maniera più pratica e comoda.

Ma che bruta roba

[marco.r]

Originariamente inviato da The_ouroboros

Sono a casa in malattia e la mente divaga...
Il pensiero mi è ricaduto a qualche giorno fa quando debuggavo un programma e mi è sorta una domanda..
Chi usa ancora, con le moderne pipeline dei processori, le Bitwise operations?

Nel senso, a parte gli ambiente embedded, ovvio

Invero mi sa che, sempre con i moderni processori, anche usare lo xorg per swappare registri senza appoggio non sia tanto conveniente..

Proprio perche' operano bit a bit, le operazioni bitwise permettono due cose interessanti: applicare la stessa operazione su piu' bit (ovviamente) e operare su una sola parte del numero.

Il primo fatto vuol dire che se io ho una qualsiasi informazioni che riesco a rappresentare con un numero limitato di bit posso fare la stessa operazione contemporaneamente su piu' valori.
Quello degli insiemi di interi di cui si parlava prima e' un esempio. Posso rappresentare un insieme di piccoli numeri (<64 su una macchina a 64bit) con un singolo intero. Operazioni come intersezione o unione si fanno con una unica operazione bitwise. Una rappresentazione con una lista di numeri richiede molte piu' operazioni. A seconda del contesto questo potrebbe fare la differenza. La cosa si puo' estendere semplicemente ad insiemi piu' grandi.

Il secondo fatto vuol dire che io posso rappresentare piu' informazioni su un unico intero. Questo diventa molto comodo quando voglio trasferire dell'informazione e mi interessa minimizzare lo spazio utilizzato. Un esempio pratico sono i flag su un header di un pacchetto TCP (o anche IP), visto che posso usare un singolo bit per rappresentare il valore attivo o meno del flag. Le operazioni bitwise mi serviranno per estrarre il valore del singolo flag.

Un'altra applicazione e' quella di aggiungere delle informazioni ai puntatori in linguaggio di programmazione. In questo caso lo scopo e' quello di evitare una doppia reindirezione piuttosto che limitare l'uso della memoria.
Pensa ad un linguaggio di programmazione dinamico, come puo' essere ruby. Come faccio a rappresentare un numero intero e a distinguerlo da un oggetto vero e proprio quando lo passo a funzioni e metodi ? Una possibilita' e' di farne il cosidetto boxing e usare un oggetto per tenerne il contenuto vero e proprio, col problema che pero' nella migliore delle ipotesi raddoppio la memoria utilizzata. Con un linguaggio statico posso sapere a priori che e' un numero e quindi passare come argomento direttamente il valore.

Oppure posso sfruttare il fatto che solitamente la memoria che alloco allineato alla parola, per cui su macchine a 32 bit avro' i due bit piu' bassi sempre a 0. Perche' non sfruttarli per tenere delle informazioni aggiuntive ? Ad esempio potrei decidere che se metto 01 invece che 00 so che si tratta di un numero, usando un po' di shifting prima/dopo le operazioni sui numeri.

Storicamente, nei GC mark-and-sweep e compagnia, si usava un bit per la marcatura del puntatore durante la fase di mark.

Insomma esempi di uso se ne trovano a bizzeffe.

[The_ouroboros]

bellissimo intervento che offre ottimi spunti, grazie

[cdimauro]

Originariamente inviato da sottovento

Non proprio: partisse dall'msb occorrerebbe specificare anche quale e' il bit piu' significativo nell'intervallo! In pratica, si avrebbe una pericolosissima inversione del peso dei bit. Questo spiega perche', nonostante lo standard non dica nulla sulla allocazione dei bit, partono tutti da lsb.

Esatto: nulla è specificato nello standard, ma viene utilizzata una soluzione perché, all'atto pratico, una decisione la si deve pur prendere.

Giusto, pero' se quel bit serve ad accendere la lavatrice, con linguaggi a piu' alto livello resti con la biancheria sporca

Questo dipende tutto dall'implementazione. Come dicevo, col Turbo Pascal era ben specificato com'era implementato il tipo "set of", per cui non c'erano sorprese e si poteva usare tranquillamente per mappare qualunque cosa, anche i registri hardware.
Lo stesso vale per il Modula-2 e il suo bitset.

La differenza, rispetto al C, è che questi linguaggi offrono un meccanismo più comodo e di alto livello per fare sostanzialmente le stesse cose.

Di pure basso livello senza paura, ed andrebbe trattato come tale, anche se spesso non succede.

Allora, guardando in giro posso dire: cdimauro ha ragione su tutta la linea, non esiste assolutamente uno standard. Tuttavia a causa di evidenti limitazioni nella soluzione opposta, l'allocazione partendo da lsb e' uno standard de-facto. Sempre che, con il linguaggio C, si possa parlare di standard

Beh, uno standard c'è, e ti dirò: trovo pure giusto che certi dettagli vengano lasciati all'implementazione del linguaggio.

Originariamente inviato da The_ouroboros

Dato che al momento è più un "lavoro" di debugging e lavoro principalmente su piattaforma *nix mi sono adattato.

C'è solo vantaggio a leggerle entrambe.

Indubbiamente.

Cmq, uscendo un po dal seminato, sto dando un occhio ad ARM... non male come ABI, pi+ semplice di x86/x64 ma, per alcune operazioni, molto veloce.

x64 è molto simile ad ARM come ABI.

Quest'ultima ha un vantaggio nelle chiamate al kernel, soprattutto grazie al fatto che viene effettuato il banking dei registri, per cui ci si trova con dei registri immediatamente utilizzabili (senza doverli salvare prima nello stack, ad esempio).

Originariamente inviato da The_ouroboros

Ma che bruta roba

Beh, brutta proprio no, se consideri che parliamo di un processore estremamente vecchio e a 8 bit. C'ho speso parecchio tempo, e mi sono pure divertito all'epoca.

Originariamente inviato da marco.r

Proprio perche' operano bit a bit, le operazioni bitwise permettono due cose interessanti: applicare la stessa operazione su piu' bit (ovviamente) e operare su una sola parte del numero.

Il primo fatto vuol dire che se io ho una qualsiasi informazioni che riesco a rappresentare con un numero limitato di bit posso fare la stessa operazione contemporaneamente su piu' valori.
Quello degli insiemi di interi di cui si parlava prima e' un esempio. Posso rappresentare un insieme di piccoli numeri (<64 su una macchina a 64bit) con un singolo intero. Operazioni come intersezione o unione si fanno con una unica operazione bitwise. Una rappresentazione con una lista di numeri richiede molte piu' operazioni. A seconda del contesto questo potrebbe fare la differenza. La cosa si puo' estendere semplicemente ad insiemi piu' grandi.

Il secondo fatto vuol dire che io posso rappresentare piu' informazioni su un unico intero. Questo diventa molto comodo quando voglio trasferire dell'informazione e mi interessa minimizzare lo spazio utilizzato. Un esempio pratico sono i flag su un header di un pacchetto TCP (o anche IP), visto che posso usare un singolo bit per rappresentare il valore attivo o meno del flag. Le operazioni bitwise mi serviranno per estrarre il valore del singolo flag.

Un'altra applicazione e' quella di aggiungere delle informazioni ai puntatori in linguaggio di programmazione. In questo caso lo scopo e' quello di evitare una doppia reindirezione piuttosto che limitare l'uso della memoria.
Pensa ad un linguaggio di programmazione dinamico, come puo' essere ruby. Come faccio a rappresentare un numero intero e a distinguerlo da un oggetto vero e proprio quando lo passo a funzioni e metodi ? Una possibilita' e' di farne il cosidetto boxing e usare un oggetto per tenerne il contenuto vero e proprio, col problema che pero' nella migliore delle ipotesi raddoppio la memoria utilizzata. Con un linguaggio statico posso sapere a priori che e' un numero e quindi passare come argomento direttamente il valore.

Oppure posso sfruttare il fatto che solitamente la memoria che alloco allineato alla parola, per cui su macchine a 32 bit avro' i due bit piu' bassi sempre a 0. Perche' non sfruttarli per tenere delle informazioni aggiuntive ? Ad esempio potrei decidere che se metto 01 invece che 00 so che si tratta di un numero, usando un po' di shifting prima/dopo le operazioni sui numeri.

Storicamente, nei GC mark-and-sweep e compagnia, si usava un bit per la marcatura del puntatore durante la fase di mark.

Insomma esempi di uso se ne trovano a bizzeffe.

Sì, infatti, sono estremamente utili, specialmente smanettando a basso livello.

Quella di utilizzare i bit bassi di un puntatore per indicare il tipo dell'oggetto oppure la presenza di un intero o altro, la cullo da tempo per la virtual machine di Python. Ne abbiamo parlato con un altro paio di core dev che lavorano sulla virtual machine, all'ultima EuroPython, ma il problema più grosso è che si tratta di una modifica enorme, che impatterebbe praticamente tutto.

L'idea è concreta, visto che i puntatori sono tutti allineati almeno a 8 byte (e a 16 per le architetture a 64 bit; adesso non ricordo bene, però), per cui i primi 3 bit (bassi) sono sempre a zero e potrebbero essere utilmente impiegati per specificare immediatamente il tipo.

C'è, però, da pagare il prezzo del masking per ogni operazione: per ripulire i 3 bit bassi quando si è in presenza di un puntatore vero e proprio, e per eliminarli del tutto se abbiamo un intero. Questa cosa si deve fare ogni volta che si deve manipolare il puntatore o l'intero, ed è questo il deterrente principale nell'utilizzo di questa tecnica.

In ARM64 è stata fatta una cosa molto utile, a cui ho pensato da molto tempo che si potesse applicare a x64: l'uso degli 8 bit alti dei puntatore come tag. In pratica il processore taglia via in automatico gli 8 bit alti ogni volta che usa un puntatore per referenziare la memoria, realizzando in hardware quello che, invece, dovremmo implementare in software. Il fatto che siano ben 8 bit sarebbe molto comodo perché consentirebbe di specificare diversi tipi di dati.

Spero che AMD o Intel facciano la stessa con le future implementazioni di x64: sono anni che lo auspico. Tanto il futuro è rappresentato da macchine a 64 bit, e questa sarebbe un'utilissima funzionalità.

[The_ouroboros]

Originariamente inviato da cdimauro

In ARM64 è stata fatta una cosa molto utile, a cui ho pensato da molto tempo che si potesse applicare a x64: l'uso degli 8 bit alti dei puntatore come tag. In pratica il processore taglia via in automatico gli 8 bit alti ogni volta che usa un puntatore per referenziare la memoria, realizzando in hardware quello che, invece, dovremmo implementare in software. Il fatto che siano ben 8 bit sarebbe molto comodo perché consentirebbe di specificare diversi tipi di dati.

Spero che AMD o Intel facciano la stessa con le future implementazioni di x64: sono anni che lo auspico. Tanto il futuro è rappresentato da macchine a 64 bit, e questa sarebbe un'utilissima funzionalità.

In effetti ARM diventa sempre più interessante come architettura

[cdimauro]

Se riscrivi completamente l'architettura, beh, puoi fare quello che vuoi (e anche di meglio, te l'assicuro ).

ARM64 della vecchia ARM ha mantenuto soltanto il nome. Poi, ok, è in grado di eseguire il vecchio codice, ma ARM ha introdotto una nuova modalità d'esecuzione a 64 bit, e con un'ISA anch'essa completamente diversa.

Per rendere l'idea, è simile a quanto ha fatto AMD con x64. Anche se AMD è stata molto meno drastica (perché ha mantenuto la vecchia opcode table, cambiando un po' di cose).

[The_ouroboros]

a volte la rottura totale e la scelta migliore.
Non si può supportare a vita con retrocompatibilità.

P.S: ARM64 clean and elegant and ARM goes 64bit (più specifico)

[cdimauro]

ARM64 la conosco abbastanza. I link me li leggo appena posso.

Comunque è "clean" perché riprogettata da zero. Ma hanno dovuto fare delle scelte di compromesso (infatti hanno buttato via alcuni pilastri della vecchia architettura ARM).

Però è anche "fat": opcode soltanto a 32 bit. Mentre ARM aveva tirato fuori quelli a 16-32 bit con Thumb/2, e che aiutavano molto ad aumentare la densità di codice.

[The_ouroboros]

Originariamente inviato da cdimauro

ARM64 la conosco abbastanza. I link me li leggo appena posso.

Comunque è "clean" perché riprogettata da zero. Ma hanno dovuto fare delle scelte di compromesso (infatti hanno buttato via alcuni pilastri della vecchia architettura ARM).

Però è anche "fat": opcode soltanto a 32 bit. Mentre ARM aveva tirato fuori quelli a 16-32 bit con Thumb/2, e che aiutavano molto ad aumentare la densità di codice.

I link erano per me in primis e per gli altri interessati...anzi se na hai altri scrivi pure
Ma non credo ci troverai nulla di nuovo

Thumb/2 mi aveva sempre incuriosito ai tempi di quando mi sono interessato agli smartphone android/ios

P.S: Modalità Thumb: ad ARM si sono ristretti… gli opcode! e Thumb/2 (Con Thumb-2 ARM tradisce i RISC e ritorna… ai CISC! )

[cdimauro]

Thumb/2 è molto usata proprio per ridurre la dimensione del codice, ed è molto importante proprio in dispositivi come smarthphone e tablet (ma anche sistemi embedded e microcontrollori). Ecco perché ha avuto un notevole successo.

Purtroppo di altri link sull'ARM64 non saprei cosa darti.

[marco.r]

Originariamente inviato da cdimauro

C'è, però, da pagare il prezzo del masking per ogni operazione: per ripulire i 3 bit bassi quando si è in presenza di un puntatore vero e proprio, e per eliminarli del tutto se abbiamo un intero. Questa cosa si deve fare ogni volta che si deve manipolare il puntatore o l'intero, ed è questo il deterrente principale nell'utilizzo di questa tecnica.

In teoria con una oculata scelta dei tag si dovrebbe un po' ridurre il prezzo da pagare.
Supponendo di utilizzare 4 bit per i tag, uso il pattern 0000 e 1000 per (rispettivamente) interi pari e dispari: la somma rimane invariata, per la moltiplicazione mi basta un preshift di uno dei due operandi di 3 bit etc.
Mi rimane da ripulire il puntatore nel caso sia un puntatore vero e proprio, ma alla fine nessuna alternativa e' piu' economica... se non devo ripulire dovro' aggiungere un offset (per la parola successiva) etc.