Binary GCD in Assembler

virtuell Realisticer

Nabend allerseits,

vorweg, hierbei handelt es sich nicht um x86-Assembler, sondern um einen
Assembler fuer eine CPU die selbst gebaut worden ist.

Wir muessen mit Hilfe dieses Assemblers ein Programm schreiben, welches
2 Brueche addieren/subtrahieren + kuerzen kann. Und genau hier kommt der
binary gcd zum Einsatz.

Das Problem:

Irgendwie laeuft es nicht richtig und ich brauch Hilfe von euch, den Fehler
zu finden :).

Hier der Quellcode:

bgcd:
  st r0, #bgcd_u           //get bgcd_u's address
  ld r0, (r0)              //load bgcd_u (first value)

  st r1, #bgcd_v           //get bgcd_v's address
  ld r1, (r1)              //load bgcd_v (second value)

  //** now lets check whether one of them is zero
  //** if(r0 == 0 || r1 == 0) return v | u;
  jz #bgcd_zero, r0
  jz #bgcd_zero, r1

  //** let shift := lg K, where K is the greatest power of 2
  //** deviding both u and v
  //** for (shift = 0; ((u | v) & 1) == 0; ++shift) {
  //**   u >>= 1;
  //**   v >>= 1;
  //** }
  st r2, #0                //shift counter
  st r3, #1
bgcd_for:
  or r4, r0, r1            //r4 = (u | v)
  and r4, r4, r3           //r4 & 1 (odd number)?
  jz #bgcd_for_end, r4
  sar r0, r0               //r4 != 0 => r0 >>= 1; r1 >>= 1;
  sar r1, r1
  add r2, r2, r3           //increase shift counter
  jmp #bgcd_for

//** while ((u & 1) == 0)
//**   u >>= 1;
bgcd_for_end:
bgcd_while_u:
    and r4, r0, r3
    jnz #bgcd_while_u_end, r4
    sar r0, r0
    jmp #bgcd_while_u

bgcd_while_u_end:
  st r6, #0x8000
  //** from here on, u is always odd
//** do {
bgcd_do:
//** while ((v & 1) == 0)  /* Loop X */
//**    v >>= 1;
bgcd_while_v:
      and r4, r1, r3
      jnz #bgcd_while_v_end, r4
      sar r1, r1
      jmp #bgcd_while_v

bgcd_while_v_end:
    //** now u and v are both odd, so diff(u, v) is even
    //** let u = min(u, v), v = diff(u, v)/2
//** if (u < v) {
//**    v -= u;
//** }
bgcd_if:                //if(bgcd_u < bgcd_v)
        sub r4, r0, r1
        jz #bgcd_else, r4     //zero means bgcd_u == bgcd_v
        and r4, r4, r6        
        jz #bgcd_else, r4     //zero means bgcd_u > bgcd_v
        sub r1, r1, r0        //bgcd_v -= bgcd_u
        jmp #bgcd_end_if
//** else {
//**   int diff = u - v;
//**   u = v;
//**   v = diff;
//** }
bgcd_else:
        sub r4, r0, r1        //r4 = bgcd_u - bgcd_v
        st r0, r1             //bgcd_u = bgcd_v
        st r1, r4             //bgcd_v = r4
bgcd_end_if:
//** v >>= 1;
        sar r1, r1
//** } while (v != 0);
bgcd_do_while:
    jnz #bgcd_do, r1          //v != 0 => repeat loop
    st r5, r2

//** return u << shift;
bgcd_while_shift:
  jz #bgcd_end, r2            //shift counter is zero
  sal r0, r0                  //left shift bgcd_u
  sub r2, r2, r3              //decrease shift counter
  jmp #bgcd_while_shift       //and repeat loop

bgcd_end:
  st r6, #bgcd_result         //get bgcd_result's address
  st (r6), r0                 //save result
  //jmp r7                      //and return
  halt

bgcd_zero:
  st r2, #0
  or r2, r0, r1            //if r0 == 0 result is r1 and vice versa
  st r3, #bgcd_result      //get bgcd_result's address
  st (r3), r2              //save result
  //jmp r7                   //and return
  halt

//********************end bgcd******************************************

.org 0x00ff

//bgcd vars
.dw bgcd_u 30
.dw bgcd_v 10
.dw bgcd_result 0

Irgendwo muss der Wurm drinne sein. Ich bekomme folgende Werte (hex):

u    |     v      |    result
--------------------------------
  30         10            5     (hier fehlt 1 linksshift zum korrekten Erg.)
   5          5            2     (hmmm...hier passt gar nichts)
  10         10            5     (hier fehlt 1 linksshift)
 100        100           19     (hier fehlen 2 linksshifts)

Wo liegt mein Fehler?

gruss
v R

[edit]
Quelle fuer den Source: http://en.wikipedia.org/wiki/Binary_GCD_algorithm
[/edit]

[edit2]
Auf dem Forentreffen haben Jester, Shade und ich einen Interpreter fuer den
Assemblierten Code geschrieben. Bei Interesse, kann ich euch den Assembler +
den Interpreter (fuer diesen auch den Source) zukommen lassen. Hab leider
keinen Webspace, deswegen kann ich das nur auf Anfrage zuschicken
[/edit2]

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Rund um die Programmierung in das Forum Assembler verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

virtuell Realisticer

Danke an schnitzl. Im Label bgcd_for: darf es nicht jz sondern muss jnz heissen.

gruss
v R