Divisione tra un 64 bit ed un 32 da convertire in C

Tra un po' mi servira' avere il codice arduino per effettuare la divisione tra una grandezza intera a 64 bit ed un divisore da 32 bit. Sostazialmente il piu' e' fatto solo che per comodita' ho costruito tutto in Delphi, che conosco bene e che mi permetteva di effettuare subito il confronto con la divisione effettuata col suo compilatore. In sostanza si tratta di tradurre il codice da Pascal a c arduino, se c'e' qualcuno interessato che mi da una mano l'accetto volentieri. In particolare non so come inserire del codice assembler all'interno del C, grazie Giorgio

Ecco il codice in pascal con un po’ di assembler 8086, grazie dell’aiuto giorgio

// Divisione a 64bit
// N.B. Per valori del dividendo vicini ai 32 bit e’ necessaria la sottrazione a 64 bit
n:=64;
Count:=64;
Q1:=0; Q2:=0;
R1:=0; R2:=0;
// Dividendo a 64 bit
Dv1:=(Dv Shl 32) Shr 32;
Dv2:= Dv Shr 32;
for i:=1 to n do
begin
Count:=Count-1;
if Count>=32 then // DWord + significativa
begin
// X2:=DWord(1) Shl (Count-32);
X2:=DWord(1) Shl (Count-32);
// X2:=Dv2 And X2
X2:=Dv2 And X2;
//
X2:=X2 Shr (Count-32);
// R:=(R Shl 1)
K1:=$80000000 And R1;
R1:=R1 Shl 1;
R2:=R2 Shl 1;
if K1<>0 then
R2:=R2+1;
// R:=R Or X;
R1:=R1 Or X2;
end
else // Count<=31 DWord meno significativa
begin
X1:=DWord(1) Shl Count;
// X2:=DWord(1) Shl (Count-32);
// X2:=Dv2 And X2
X1:=Dv1 And X1;
//
X1:=X1 Shr Count;
// R:=(R Shl 1)
K1:=$80000000 And R1;
R1:=R1 Shl 1;
R2:=R2 Shl 1;
if K1<>0 then
R2:=R2+1;
// R:=R Or X;
R1:=R1 Or X1;
end;
// Sottrae il De dal Resto finche’ questo e’ < De
While True do
begin
// R>=De?
X1:=0;
if R2>0 then // Se supera i 32 bit: De e’ da 32
X1:=1
else
if R1>=De then
X1:=1;
if X1=0 then // allora R<De → Esci
break;
// Q:=Q+1;
Asm
ADD Q1, 1
ADC Q2, 0
end;
//R:=R-De;
Asm
MOV EAX, De
SUB R1, EAX
SBB R2, 0
end;
end;
// Fine While
if i<n then
begin
// Q:=Q Shl 1;
X1:=$80000000 And Q1;
Q1:=Q1 Shl 1;
Q2:=Q2 Shl 1;
if X1<>0 then
Q2:=Q2+1;
end;
end; // Fine For i

Dimenticavo le variabili: var Q1, Q2, Dv1, Dv2, n, i, De, R1, R2, X1, X2, K1 sono tutte unsigned integer da 32 bit

E' ultratestato, cmq per la verifica del codice basta anche usare la calcolatrice scientifica di windows, ciao

Questo aggiunge uno al quoziente Q composto da (Q2,Q1) la ADC somma l'eventuale riporto proveniente da Q1+1 Asm ADD Q1, 1 ADC Q2, 0 end;

Asm MOV EAX, De SUB R1, EAX SBB R2, 0 end;

Pardon mi e’ partito un post.
In sostanza la prima fa Q1=Q1+1 e la successiva Q2=Q2+Riporto (se c’e’)

In questa sotto EAX e’ un registro a 32 bit e equivale a: R1=R1-De + R2=R2-(eventuale prestito)

Asm
MOV EAX, De
SUB R1, EAX
SBB R2, 0
end;

Ora nel tradurle in C come facciamo ad ottenere le inform. sul prestito e sul riporto? per questo anche in Pascal ho preferito
usare l’assembler in questo caso. Pensiamo ad una alternativa.
Se in Delphi sommo due integer ed il risultato va oltre l’interger per il riporto si ha un’eccezione che uno puo’ gestire come vuole.
Il che pero mi sembra un po’ macchinoso…
Chissa che la notte porti consiglio, Giorgio

@padoang:
mi viene in mente una soluzione un po’ stupidotta ma forse funzionale

fai un check prima della somma e controlli se il risultato è minore di Q1. Ciò significa che la variabile è andata in overflow: in questo caso incrementi Q2.

unsigned long Q1=4294967294 //il max è 4294967295
unsigned long Q2=...;

if ((Q1+2)<Q1) {
  Q2++;
}

poi non sono chiari i parametri // Dividendo a 64 bit Dv1 = (Dv Shl 32) Shr 32; Dv2 = Dv Shr 32;

a questo sopra non ci badare, in delphi usavo variabili equivalenti a 64 bit (int64), cosi in una form avevo contemporaneamente il risultato della divisione eseguita dall'algoritmo e quello calcolato in delphi, per questo sulla correttezza sono convinto, ho fatto molte verifiche. Arduino mi arrivera' a gg., per cui non so se avro' problemi di prestazioni... spero di no. perche' me lo chiedi? Oggi che ho + tempo ci lavoro anch'io nelle conversione a C,

giorgio

padoang: a questo sopra non ci badare, in delphi usavo variabili equivalenti a 64 bit (int64),

Giusto per la cronaca, avrgcc supporta il tipo dato "long long int" (u_int64_t) che è un 64 bit, però non è possibile utilizzarlo su i micro a 8 bit, sebbene viene correttamente compilato come dichiarazione non appena si cerca di assegnare alla variabile un valore maggiore di 2^32 viene fornito un errore di assegnazione oppure crash in runtime se l'overflow avviene durante un calcolo.

Avr libc reference

Ti stavo per postare l’algoritmo che hai gia’ trovato, che lavora con 64 bit e che mi sembra certamente piu’ comprensibile.
Come puoi riscontrare quello finale copia il 64bit introducendo pero la necessita’ di usare variabili unsigned da 32 bit, nient’altro.

Incollo una mi traduzione di bozza e se sei cosi’ gentile da dirmi come fai in C a sommare/sottrare due variabili ognuna composta da 2 cifre a 32 bit, eliminerei la parte assembler. Poi da’ un errore in While(True) che non capisco.

#define lon unsigned long
.
.
.

void function(lon &dv1, lon &dv2, lon &de, lon &q1, lon &q2, lon &r1, lon &r2)
{
lon n, i, x1, x2, k1, count;
n=64;
count=64;
q1=0;
q2=0;
r1=0;
r2=0;
for(i=1;i<=n;i++)
{
count–;
if (count>=32)
{
x2=lon(1) << (count-32);
x2=dv2 & x2;
x2=x2 >> (count-32);
k1=0x80000000 & r1;
r1=r1 << 1;
r2=r2 << 1;
if (k1!=0)
r2++;
r1=r1 | x2;
}
else
{
x1=lon(1) << count;
x1=dv1 & x1;
x1=x1 >> count;
k1=0x80000000 & r1;
r1=r1 << 1;
r2=r2 << 1;
if (k1!=0)
r2++;
r1=r1 | x1;
}
//
While(True)
{
x1=0;
if (r2>0)
x1=1;
else
if (r1>=de)
x1=1;
if (x1=0)
break;
// q=q+1 (col riporto)
Asm
Add q1, 1
Adc q1, 0

// r=r-de (col prestito)
Mov EAX, de
SUB r1, EAX
SBB r2, 0
end;
}
// End While
if (i<n)
{
x1=0x80000000 & q1;
q1=q1 << 1;
q2=q2 << 1;
if (x1!=0)
q2++;
}
} // Fine ciclo For

Si il codice e' un po' buttato li in fretta ma funziona, come capirari ognuno preferisce usare i pezzi da lui creati, grazie cmq per i tuoi codici. Per il riporto sommando ad esempio gli addendi meno significativi A1 e B1 a 32 bit posso di re che ho il riporto se

B1>=~A1+1

vi torna?

Allora mi spiego. Il codice proviene da questo in Delphi che pero’ usa var. a 64 bit. L’ho fatto prima per questo tipo di variabili in modo da concentrarmi + sull’algoritmo della divisione che sui passaggi a 32 bit.
n:=64;
Count:=64;
Q:=0;
R:=0;
Q1:=0;
Q2:=0;
for i:=1 to n do
begin
Count:=Count-1;
K:=int64(1) Shl Count;
K:=Dv And K; // Cifra al posto Count
K:=K Shr Count;
R:=(R Shl 1) Or K;
While R>=De do
begin
Q:=Q+1;
R:=R-De;
end;
if i<n then
Q:=Q Shl 1;
end;

Poi dopo quando e’ stato maturo l’ho modificato per adattarlo alle var. a 32 bit unsigned long, ma se si guardano i commenti segue passo passo questo sopra salvo lavorare con le unsigned long.
Quell’int64 che trovi anche sopra e’ il nome delle variabili intere da 64 bit in Delphi ed e’ usato sopra come cast,
altrimenti, per una scelta del compilatore, lo shift non andava oltre i 32 passi.
Per quanto riguarda il “casino” nel mio codice che ho postato ieri devi considerare che volutamente,
per questioni di velocita’, non ho strutturato il codice in modo da utilizzare il meno possibile lo stack
Mi spiace si chiuda la collaborazione sostanzialmente senza motivo, giorgio

legacy:

padoang: come capirari ognuno preferisce usare i pezzi da lui creati

No, non lo capisco, non siamo qui a risolvere i tuoi problemi, quindi saro' breve: il tuo codice e' pessimo, non insegna nulla a nessuno e non porta alcun valore aggiunto, specialmente se ti si fanno domande se ti si danno suggerimenti e tu bellamente te ne freghi tergiversando la qualsiasi.

legacy datti una calmata. Se non hai voglia di aiutare non rispondere e basta. Ognuno ha il diritto di chiedere.

Ciao Uwe Federer

@ legacy

"non siamo qui a risolvere i tuoi problemi," é una Tua opinione non condivisa da tanti. Perché Ti permetti di parlare in loro nome? "il tuo codice e' pessimo," é un offesa "non insegna nulla a nessuno" é un'atra offesa "e non porta alcun valore aggiunto," é una Tua opinione, solo Tua. "specialmente se ti si fanno domande se ti si danno suggerimenti e tu bellamente te ne freghi tergiversando la qualsiasi." Un po di tolleranza ci vuole. Non tutte le risposte sono buone e ognuno ha il diritto di non seguirle e fare i propri errori.

Non permetto delle offese e non permetto che uno scrive la sua opinione facendola sembrare l' opinione di tutti.

Ciao Uwe