Quali operazioni integer del complemento 2 possono essere utilizzate senza azzerare i bit alti negli ingressi, se si desidera solo la parte bassa del risultato?

Nella programmazione di assiemi, è piuttosto comune voler calcolare qualcosa dai bit bassi di un registro che non garantisce l’azzeramento degli altri bit. Nei linguaggi di livello superiore come C, devi semplicemente trasmettere i tuoi input alle dimensioni ridotte e lasciare che il compilatore decida se deve azzerare i bit superiori di ciascun input separatamente o se può troncare i bit superiori del risultato dopo il fatto.

Questo è particolarmente comune per x86-64 (aka AMD64), per vari motivi 1 , alcuni dei quali sono presenti in altri ISA.

Userò 64bit x86 per gli esempi, ma l’intento è di chiedere / discutere il complemento a 2 e l’aritmetica binaria senza segno in generale, dato che tutte le moderne CPU lo usano . (Si noti che C e C ++ non garantiscono il complemento 4 di due e che l’overflow con segno è un comportamento non definito).

Ad esempio, si consideri una semplice funzione che può essere compilata con un’istruzione LEA 2 . ( rax SysV (Linux) ABI 3 , i primi due argomenti di funzione sono in rdi e rsi , con il ritorno in rax . rax è un tipo a 32 bit.)

 ; int intfunc(int a, int b) { return a + b*4 + 3; } intfunc: lea eax, [edi + esi*4 + 3] ; the obvious choice, but gcc can do better ret 

gcc sa che l’aggiunta, anche degli interi con segno negativo, trasporta solo da destra a sinistra, quindi i bit superiori degli input non possono influenzare ciò che accade in eax . Così, salva un byte di istruzioni e usa lea eax, [rdi + rsi*4 + 3]

Quali altre operazioni hanno questa proprietà dei bit bassi del risultato non in base ai bit alti degli input?

E perché funziona?



Le note

1 Perché questo emerge frequentemente per x86-64 : x86-64 ha istruzioni di lunghezza variabile, dove un byte di prefisso extra cambia la dimensione dell’operando (da 32 a 64 o 16), quindi è ansible salvare un byte in istruzioni altrimenti eseguito alla stessa velocità. Ha anche false dipendenze (AMD / P4 / Silvermont) quando scrive il basso 8b o 16b di un registro (o uno stallo quando in seguito legge il registro completo (Intel pre-IvB)): Per ragioni storiche, scrive solo in 32b sub -registri zero il resto del registro 64b . Quasi tutte le operazioni aritmetiche e logiche possono essere utilizzate sugli 8, 16 o 32 bit bassi, nonché sui 64 bit completi dei registri di uso generale. Anche le istruzioni vettoriali intere sono piuttosto non ortogonali, con alcune operazioni non disponibili per alcune dimensioni degli elementi.

Inoltre, a differenza di x86-32, l’ABI passa args di funzione nei registri e non è necessario che i bit superiori siano zero per i tipi stretti.

2 LEA: come altre istruzioni, la dimensione dell’operando di default di LEA è 32 bit, ma la dimensione dell’indirizzo predefinito è 64 bit. Un byte prefisso dimensione operando ( 0x66 o REX.W ) può rendere l’operando di output dimensione 16 o 64 bit. Un byte prefisso dimensione indirizzo ( 0x67 ) può ridurre la dimensione dell’indirizzo a 32 bit (in modalità 64 bit) o ​​16 bit (in modalità 32 bit). Quindi, in modalità 64 bit, lea eax, [edx+esi] richiede un byte in più di lea eax, [rdx+rsi] .

È ansible fare lea rax, [edx+esi] , ma l’indirizzo è ancora calcolato solo con 32 bit (un carry non imposta il bit 32 di rax ). Ottieni risultati identici con lea eax, [rdx+rsi] , che è due byte più corti. Quindi, il prefisso dimensione indirizzo non è mai utile con LEA , come avvertono i commenti in uscita di sassembly dall’eccellente disassemblatore objconv di Agner Fog.

3 ABI x86 : il chiamante non deve azzerare (o firmare estendere) la parte superiore dei registri a 64 bit utilizzati per trasmettere o restituire i tipi più piccoli in base al valore. Un chiamante che voleva usare il valore di ritorno come indice di array avrebbe dovuto firmarlo – estenderlo (con movzx rax, eax , o l’istruzione speciale-per-eax cdqe . (Da non confondere con cdq , quale estende idiv in idiv : idiv ad esempio per impostare per idiv .))

Ciò significa che una funzione che restituisce unsigned int può calcolare il suo valore di ritorno in un temporaneo a 64 bit in rax , e non richiedere un rax mov eax, eax per azzerare i bit superiori di rax . Questa decisione di progettazione funziona bene nella maggior parte dei casi: spesso il chiamante non ha bisogno di istruzioni aggiuntive per ignorare i bit non definiti nella metà superiore di rax .


4 C e C ++

C e C ++ specificatamente non richiedono due interi con segno binario complementare (eccetto per std::atomic tipi std::atomic C ++ ). Anche il complemento e il segno / la magnitudine sono consentiti , quindi per C completamente portatili, questi trucchi sono utili solo con i tipi unsigned . Ovviamente per le operazioni con segno, un bit di segno impostato nella rappresentazione di segno / magnitudine significa che gli altri bit vengono sottratti, piuttosto che aggiunti, per esempio. Non ho lavorato attraverso la logica per il complemento

Tuttavia, i bit-hack che funzionano solo con il complemento a due sono molto diffusi , perché in pratica nessuno si interessa di nient’altro. Molte cose che funzionano con il complemento a due dovrebbero anche funzionare con il proprio complemento, dal momento che il bit del segno continua a non cambiare l’interpretazione degli altri bit: ha solo un valore di – (2 N -1) (invece di 2 N ). La rappresentazione di segno / magnitudine non ha questa proprietà: il valore di posizione di ogni bit è positivo o negativo a seconda del bit di segno.

Si noti inoltre che i compilatori C possono supporre che l’overflow con segno non avvenga mai , perché è un comportamento non definito. Quindi, per esempio, i compilatori possono e devono assumere (x+1) < x è sempre falso . In questo modo, il rilevamento dell’overflow con segno è piuttosto problematico in C. Si noti che la differenza tra wrapping non firmato (carry) e overflow firmato .

Ampie operazioni che possono essere utilizzate con la spazzatura nei bit superiori:

  • logiche bit a bit
  • spostamento a sinistra (compresa la *scale in [reg1 + reg2*scale + disp] )
  • addizione / sottrazione (e quindi istruzioni LEA : il prefisso dimensione indirizzo non è mai necessario. Basta usare la dimensione dell’operando desiderata per troncare se necessario).
  • La metà bassa di un multiplo. ad es. 16b x 16b -> 16b può essere fatto con un 32b x 32b -> 32b. È ansible evitare le bancarelle LCP (e problemi di registro parziale) da imul r16, r/m16, imm16 utilizzando un 32 bit imul r32, r/m32, imm32 e quindi leggendo solo i 16 bassi del risultato. (Prestare attenzione con i riferimenti di memoria più ampia se si utilizza la versione m32 , però.)

    Come sottolineato dal manuale Intel insn ref, le forms operand 2 e 3 di imul sono sicure per l’uso su interi senza segno. I bit di segno degli ingressi non influenzano i bit N del risultato in un multiplo N x N -> N bit.)

  • 2 x (cioè shift by x ): Funziona almeno su x86, dove il numero di turni è mascherato, piuttosto che saturo, fino alla larghezza dell’operazione, quindi high garbage in ecx , o anche i bit alti di cl , don ‘ t influenza il numero di turni. Si applica anche agli spostamenti senza bandiera di BMI2 ( shlx ecc.), Ma non ai turni vettoriali ( pslld xmm, xmm/m128 ecc., Che saturano il conteggio). I compilatori intelligenti ottimizzano il mascheramento in allontanamento del numero di turni, consentendo un linguaggio sicuro per le virate in C (nessun comportamento non definito) .

Ovviamente i flag come carry / overflow / sign / zero saranno tutti influenzati dalla spazzatura in bit alti di un’operazione più ampia. Gli spostamenti di x86 mettono l’ultimo bit spostato nella bandiera di carry, quindi questo influenza anche i turni.

Operazioni che non possono essere usate con spazzatura nei bit superiori:

  • giusto turno
  • piena moltiplicazione: ad es. per 16b x 16b -> 32b, assicurarsi che i 16 superiori degli ingressi siano a zero o imul prima di eseguire 32ul x 32b -> 32b imul . Oppure usa un imul -operando a 16 bit o imul per mettere male il risultato in dx:ax . (La scelta dell’istruzione firmata e non firmata avrà effetto sul 16b superiore allo stesso modo dell’estensione dello zero o del segno prima di un imul 32b.)

  • indirizzamento della memoria ( [rsi + rax] ): firmare o zero estendere secondo necessità. Non esiste una modalità di indirizzamento [rsi + eax] .

  • divisione e resto

  • log2 (cioè posizione del bit impostato più alto)
  • conteggio dello zero finale (a meno che non si sappia che c’è un bit impostato nella parte che si desidera, o semplicemente controllare un risultato più grande di N come controllo non trovato).

Il complemento a due, come la base non firmata 2, è un sistema di valore del posto. L’MSB per base2 senza segno ha un valore di posizione 2 N-1 in un numero N bit (ad es. 2 31 ). Nel complemento a 2, l’MSB ha un valore di -2 N-1 (e quindi funziona come un bit di segno). L’articolo di wikipedia spiega molti altri modi di comprendere il complemento a 2 e di negare un numero base2 non firmato.

Il punto chiave è che avere il bit di segno impostato non modifica l’interpretazione degli altri bit . Addizione e sottrazione funzionano esattamente come per base2 senza segno, ed è solo l’interpretazione del risultato che differisce tra firmato e non firmato. (ad es. overflow con segno si verifica quando è presente un carry in ma non fuori dal bit del segno .)

Inoltre, trasportare si propaga solo da LSB a MSB (da destra a sinistra). La sottrazione è la stessa: indipendentemente dal fatto che ci sia qualcosa nei bit più alti da prendere in prestito, i bit bassi lo prendono in prestito. Se ciò provoca un overflow o carry, saranno interessati solo i bit alti. per esempio:

  0x801F -0x9123 ------- 0xeefc 

Gli 8 bit bassi, 0xFC , non dipendono da ciò da cui hanno preso in prestito. Si “avvolgono” e trasmettono il prestito agli 8 superiori.

Quindi, addizione e sottrazione hanno la proprietà che i bit bassi del risultato non dipendono da alcun bit superiore degli operandi.

Poiché LEA utilizza solo addizione (e spostamento a sinistra), l’utilizzo della dimensione dell’indirizzo predefinita è sempre corretto. Ritardare il troncamento fino a quando la dimensione dell’operando entra in gioco per il risultato va sempre bene.

(Eccezione: il codice a 16 bit può utilizzare un prefisso dimensione indirizzo per eseguire calcoli a 32 bit. Nel codice 32 o 64b, il prefisso dimensione indirizzo riduce la larghezza anziché aumentare.)


La moltiplicazione può essere pensata come aggiunta ripetuta, o come spostamento e aggiunta. La metà bassa non è influenzata da alcun bit superiore. In questo esempio a 4 bit, ho scritto tutti i prodotti bit che sono sumti nei 2 bit di risultato bassi. Sono coinvolti solo i 2 bit bassi di entrambe le sorgenti. È chiaro che questo funziona in generale: i prodotti parziali sono spostati prima dell’aggiunta, quindi i bit alti nella sorgente non influenzano mai i bit più bassi nel risultato in generale.

Vedi Wikipedia per una versione più ampia di questo con una spiegazione molto più dettagliata . Ci sono molti buoni risultati di google per la moltiplicazione con codice binario , incluso un po ‘di materiale didattico.

  *Warning*: This diagram is probably slightly bogus. ABCD A has a place value of -2^3 = -8 * abcd a has a place value of -2^3 = -8 ------ RRRRrrrr AAAAABCD * d sign-extended partial products + AAAABCD * c + AAABCD * b - AABCD * a (a * A = +2^6, since the negatives cancel) ---------- D*d ^ C*d+D*c 

Effettuare una moltiplicazione con segno invece che con un multiplo senza segno produce ancora lo stesso risultato nella metà bassa (i 4 bit bassi in questo esempio). L’estensione del segno dei prodotti parziali avviene solo nella metà superiore del risultato.

Questa spiegazione non è molto accurata (e forse ha anche degli errori), ma c’è una buona prova che è vero e sicuro da usare nel codice di produzione:

  • gcc usa imul per calcolare il prodotto unsigned long di due input unsigned long . Guarda un esempio di questo di gcc approfittando di LEA per altre funzioni sul explorer del compilatore Godbolt .

  • Il manuale di Intel insn ref dice:

Le forms a due e tre operandi possono anche essere utilizzate con operandi senza segno perché la metà inferiore del prodotto è la stessa, indipendentemente dal fatto che gli operandi siano firmati o non firmati. I flag CF e OF, tuttavia, non possono essere utilizzati per determinare se la metà superiore del risultato è diversa da zero.

  • La decisione progettuale di Intel di introdurre solo 2 e 3 forms di operando di imul , non mul .

Ovviamente le operazioni logiche binarie bit a bit (e / o / xor / not) trattano ogni bit in modo indipendente: il risultato per una posizione di bit dipende solo dal valore degli ingressi in quella posizione di bit. Anche i cambi di bit sono piuttosto ovvi.