Odejmowanie dowolnie długich liczb assembler IA-32 problem pomocy

[freeman]

Witam
Powiedzcie gdzie może tutaj być błąd bo ja już nie mam siły.Wywułuje tą funkcję  w C pod takimi parametrami

extern void sub (unsigned int n,unsigned int *op,unsigned int *oper);
unsigned int op1[]={0x0,0x0,0x0,0x0,0x3,0x0};
unsigned int op2[]={0x0,0x0,0x0,0x0,0x0,0x3};
unsigned int op3[]={0,0,0,0,0,0};
unsigned int jeden[] = {0,0,0,0,0,1};
unsigned int wynik[] = {0,0,0,0,0,0};
_sub(n,op1,op2);

kompilalator ASM to NASM, kompilacja pod linuxem i linkowanie gcc

Program wysyje się dla takich danych                   
unsigned int op1[]={0x0,0x0,0x0,0x0,0x3,0x0};
unsigned int op2[]={0x0,0x0,0x0,0x0,0x0,0x3};

tzn zwracany wynik to 0 0 0 0 3 -3 czyli tak jakby nie uwzględniał pożyczki przy odejmowaniu a wg mnie powinien uwzględniać przynajmniej tak wynika ze specyfikacji funkcji SBB

Kod

; void sub (int n, int *op, int *oper)
                         
_sub:
	mov eax, [esp+8] ;*op
	mov edx, [esp+12] ;*oper
	mov ecx, [esp+4] ;licznik
	clc
	pushfd
odj:
	;popfd ;ladujemy flage cf
 
	push ecx ;licznik na stos
 
	mov ecx, [edx] ;odejmowanie parti bitow
	sbb [eax], ecx ;
 
	pop ecx ;licznik do ecx 
 
	;pushfd ;zapamietujemy cf
 
	add eax, 4 ;przesuwamy wskaznik na nastepna porcje danych
	add edx, 4 ;
 
 
	sub ecx, 1 ;zmniejszamy licznik
	jnz odj ;skaczemy jesli licznik != 0 do dodawania
 
	popfd ;przygotowujemy stos do wyjscia
	ret
 

[Złośliwiec]

A co to ma wspólnego z programowaniem gier? Bo jakoś czuję, że niewiele (bardziej mi to pachnie jakimś projektem na studia ), a w takim przypadku wątek kwalifikuje się do zamknięcia.

[Xion]

Oczywiście że nie uwzględnia pożyczki. Używasz instrukcji ADD, którą ją właśnie olewa. Dodawanie z uwzględnieniem carry flag jest przeprowadzane przy pomocy ADC.

[Liosan]

sbb: This instruction subtracts the operators and subtracts one to the result if CF is activated. The source operator is always subtracted from the destiny.

Z tej specyfikacji wynika, ze odejmie 1 tylko jeśli CF jest ustawione. Z tego co widze, przed petlą czyścisz CF (instrukcja clc), a potem żadna instrukcja już raczej jej nie ustawi.

Spodziewales sie dostać -4? Inaczej: jak to miało działac? Assembler o 3 nad ranem to baaaardzo zly pomysl...

Liosan

[mikael]

Khem... Ja tu błędu nie widzę A przynajmniej nie tam, gdzie go szukacie...

Jeżeli procedurka jest wywoływana dla argumentów op1, op2 (w tej właśnie kolejności), to w EAX ląduje *op1, a w EDX *op2. W efekcie op2 jest odejmowane od op1...

A teraz pytanie: co otrzymamy, jeśli odejmiemy 300000 (op2) od 030000 (op1)?

Podpowiedź:
0-0 = 0
0-0 = 0
0-0 = 0
0-0 = 0
3-0 = 3
0-3 = -3

Wszystko się zgadza (przynajmniej - zgodnie z tym algorytmem - sam kod jest OK).

Fakt - rzeczywisty wynik powinien być równy -270000, ale do tego to akurat trzeba by nieco inaczej ten algorytm skonstruować... Oj - zapomniało się już, jak się odejmuje w słupku?

[Krzysiek K.]

Wszystko jest fajnie i spoko, jezeli chodzi o sam "rdzeń" kodu, tylko przeoczyłeś jedna małą rzecz - instrukcje add i sub, których użyłeś do zmiany eax, edx i ecx nadpisuja Ci flagę CF. Proponuję wywalić, uzywając przy tym innego trybu adresowania typu [esi+ecx*4] (mnożenie przez cztery procesor wykonuje jako przesunięcie. Sekwencję sub/jnz można zastapic pojedynczym rozkazem loop, który własnie do tego służy. Przy okazji, użycie ecx w adresowaniu zapewni, że liczba odejmowana jest od najstarszej części, czyli zgodnie z notacja używaną na PC.

[freeman]

@Krzysiek K.
napisałem nową funkcję (prawie zgodną z twoją specyfikacją) ale ta za to nic nie robi, tzn dla dowolnych danych zwraca te same dowolne dane. Funkcja poprostu mimo że teoretycznie powinna działać to nie działa ;/

Oto jej ciało

Kod:

_sub2:                          ; void sub (int n, int *op, int *oper)
  MOV EAX, [ESP + 4]            ;  n
  MOV ECX, [ESP + 8]            ;  op
  MOV EDX, 0                    ;  i = 0
  PUSH EBX                      ;
  MOV EBX, [ESP + 16]          ;  oper
  PUSH EDI                      ;  tmp
  CLC                          ;  CF = 0
subloop:                        ;  do
  MOV EDI, [EDX * 4 + EBX]      ;   tmp = oper[i]
  SBB [EDX * 4 + ECX], EDI      ;   op[i] -= tmp + CF
  INC EDX                      ;   i++
  DEC EAX                      ;   n--
  JNZ endsubloop                ;   while (n)
endsubloop:                   
  POP EDI
  POP EBX
  RET

Nie mam pomysłów jak zmienić ten algorytm żeby działał dobrze, asm jest dość dziwnym językiem ;/

[mikael]

@Krzysiek: przyznam Ci rację co do tego, że dobrym zwyczajem (zwłaszcza dla początkujących) jest używanie takich instrukcji do obsługi pętli, które w ogóle nie modyfikują flag (np. LEA, lub proponowane przez Ciebie wykorzystanie możliwości kalkulacji adresu). Nie przyznam Ci natomiast racji w tej sytuacji. Inkrementacja wskaźnika nie powinna tu stanowić problemu. CF ustawiona zostałaby tylko wtedy, gdyby aktualna zawartość wskaźnika + 4 przekroczyła 32 bity (czyli 0xFFFFFFFF + 4, 0xFFFFFFFE + 4, 0xFFFFFFFD + 4 i 0xFFFFFFFC + 4). W przypadku adresowania jest to raczej wysoce wątpliwy przypadek... Podobnie sprawa ma się z licznikiem.

Głównym problemem w tym przypadku będzie reprezentacja liczb ujemnych. Ponieważ mówimy o "dowolnie długich liczbach", należy zastanowić się, jak reprezentowana ma być liczba ujemna? Ponieważ ma to być dowolnie długa liczba, musimy przyjąć, że znak liczby będzie ustalony przy najstarszej cyfrze różnej od zera (a więc -1234 należałoby zapisać jako -1, 2 ,3 ,4 - czy raczej 4, 3, 2, -1).

Do całej operacji proponowałbym zastosować metodę uzupełniania do 9 (nine's complement - poszukaj w necie freeman).

[Krzysiek K.]

napisałem nową funkcję (prawie zgodną z twoją specyfikacją) ale ta za to nic nie robi

Prawie robi różnicę. Chwila... tutaj przecież właśnie nie robi poprawnie tej róznicy.

Zastanów się, co robi poniższa instrukcja "skoku":

Kod:

JNZ endsubloop                ;   while (n)
endsubloop:

@Krzysiek: przyznam Ci rację co do tego, że dobrym zwyczajem (zwłaszcza dla początkujących) jest używanie takich instrukcji do obsługi pętli, które w ogóle nie modyfikują flag (np. LEA, lub proponowane przez Ciebie wykorzystanie możliwości kalkulacji adresu). Nie przyznam Ci natomiast racji w tej sytuacji. Inkrementacja wskaźnika nie powinna tu stanowić problemu. CF ustawiona zostałaby tylko wtedy, gdyby aktualna zawartość wskaźnika + 4 przekroczyła 32 bity (czyli 0xFFFFFFFF + 4, 0xFFFFFFFE + 4, 0xFFFFFFFD + 4 i 0xFFFFFFFC + 4). W przypadku adresowania jest to raczej wysoce wątpliwy przypadek... Podobnie sprawa ma się z licznikiem.

Ale chyba przyznasz mi rację, że te wszystkie add/sub wyzerują flagę CF, w której powinna byc przechowywana pożyczka do nastepnego obiegu pętli.

Głównym problemem w tym przypadku będzie reprezentacja liczb ujemnych. Ponieważ mówimy o "dowolnie długich liczbach", należy zastanowić się, jak reprezentowana ma być liczba ujemna? Ponieważ ma to być dowolnie długa liczba, musimy przyjąć, że znak liczby będzie ustalony przy najstarszej cyfrze różnej od zera (a więc -1234 należałoby zapisać jako -1, 2 ,3 ,4 - czy raczej 4, 3, 2, -1).

Do całej operacji proponowałbym zastosować metodę uzupełniania do 9 (nine's complement - poszukaj w necie freeman).

Tutaj jest ona reprezentowana normalnie w postaci binarnej i kodzie U2, tyle że liczba może być 32-, 64-, 96- i ogólnie (n*32)-bitowa.

[mikael]

@Krzysiek: cholera - tak przyznam Ci rację, że wyzeruje... Masz rację

A co do samego algorytmu:

W naszym przypadku mamy o tyle prościej, że obie liczby są N-pozycyjne (jest jeden licznik, więc obie liczby są równie długie - co najwyżej dopełnione zerami). Metoda uzupełnienia dziewiątek polega na zastąpieniu substraktu (liczby odejmowanej) jego dopełnieniem do N-pozycyjnej dziewiątki, a następnienie dodaniu obu liczb i wykorzystaniu wiodącej jedynki rezultatu. Na przykładzie:

Kod:

(321 - 123 = 198)

Uwzględniamy dopełnienie zerami (załóżmy, że do 4 pozycji):

  0 3 2 1
- 0 1 2 3
=========

Przekształcamy na 0321 + (9999 - 0123), czyli dla każdej pozycji wykonujemy tak naprawdę X+9-Y:

  0 3 2 1
+ 9 9 9 9
- 0 1 2 3
=========

Pozycja[0]: 1 + 9 = 10 - 3 = 7
Pozycja[1]: 2 + 9 = 11 - 2 = 9
Pozycja[2]: 3 + 9 = 12 - 1 = 11 (pozostawiamy 1, dziesiątkę przenosimy wyżej!!!)
Pozycja[3]: 1 + 9 + 0 = 10 - 0 = 10 (pozostawiamy 0, dziesiątkę przenosimy wyżej!!!)
Pozycja[4]: = 1 (tej pozycji nie zapisujemy, jest to przeniesienie poza zakres!!!)

Otrzymujemy więc: (1) 0 1 9 7
A teraz do naszego wyniku dodajemy (1) z przeniesienia... Co otrzymujemy? 198 :)

A teraz trudniejsza sztuka - wynik będzie ujemny...

(123 - 321 = - 198)

Przekształcamy:
  0 1 2 3
+ 9 9 9 9
- 0 3 2 1

Pozycja[0]: 3 + 9 = 12 - 1 = 11 (pozostawiamy 1, dziesiątkę przenosimy)
Pozycja[1]: 2 + 9 + 1 (z przeniesienia) = 12 - 2 = 10 (zostawiamy 0, dziesiątkę przenosimy)
Pozycja[2]: 1 + 9 + 1 (z przeniesienia) = 11 - 3 = 8
Pozycja[3]: 0 + 9 = 9 - 0 = 9
Pozycja[4]: 0 (nie było przeniesienia z pozycji [3])

Otrzymaliśmy (0) 9 8 0 1. Do naszego wyniku dodajemy 0 (pozycja[4]).

9801... Trochę dziwny wynik? Nie... Jak łatwo zauważyć, jest to to samo, co liczba ujemna w N-pozycyjnym binarnym...

9999 - 9801 = 0198...

Pozycja[4], której nigdzie nie zapisujemy, spełnia rolę flagi wskazującej, czy wynik jest ujemny, czy też dodatni. Jeżeli Pozycja[4] = 1, to wynik jest dodatni i nie musimy z nim nic robić. Jeśli jest równa 0, wynik jest ujemny i należy go skomplementować do dziewiątek ("zanegować", ale w systemie dziesiętnym, a więc przez dziewiątki) i ewentualnie ustawić znak najstarszej cyfry wyniku różnej od zera na liczbę ujemną...