ndr-nkc.de ndr-nbc.de
  
Startseite
News
 
NDR-NKC
Geräte Z80
Geräte 68000
Geräte 8088
 
NKC Emulator
 
Z80 Section
Baugruppen
ROM's
Software
68000 Section
Baugruppen
ROM's
PASCAL/S
Software
CP/M 68K
8088 Section
Baugruppen
Downloads
 
Bussysteme
Stromversorgung
Input / Output
Grafikkarten
Speicherkarten
Massenspeicher
Weitere Baugruppen
 
Projekte
 
Dokumentation
Datenblätter
Glossar
Portraits
Links

Impressum

 

64-Bit Integer-Arithmetik

Ein etwas umfangreicherer Beitrag, der das Rechnen mit großen Zahlen auf dem NKC möglich macht. Das Projekt besteht aus einer Assembler-Bibliothek, in der die Rechenoperationen umgesetzt sind und aus einer Header-Datei, in der die Datenstruktur und Funktionen zur Ein- und Ausgabe umgesetzt sind.

Da es in C keinen nativen Datentyp für 64-Bit Zahlen gibt, werden alle Parameter mittels Pointern auf die Datenstruktur an die Funktionen übergeben.

Zurück zum Inhaltsverzeichnis der Beiträge

Die Datenstruktur

Die 64 Bit umfassenden Werte werden in zwei Teile zu je 32 Bit aufgeteilt. Dazu wird ein eigener Datentyp U64 definiert. 

typedef struct {
  long hi;    // Bits 63 bis 32
  long lo;    // Bits 31 bis 0
} U64;

Enthaltene Funktionen

In der Assembler-Bibliothek sind neben der 4 Grundrechenarten Addition, Subtraktion, Multiplikation, Division mit Rest noch Funktionen zum bitweisen Verschieben sowie Hilfsfunktionen umgesetzt Alles Weitere kann aus den Kommentaren oder den anschließenden Beispielen entnommen werden. 




MAKE64


Erstellt ein U64 aus einer link-Variablen oder Konstanten.

.globl _make64
_make64:
  link a6,#0
  move.l 12(a6),a1   ; pointer auf &a 
  move.l #0,(a1)     ; a.hi = 0
  move.l 8(a6),4(a1) ; a.lo = long 
  unlk a6
  rts




DUP64


Erstellt eine Kopie einer U64-Variablen.

.globl _dup64
_dup64: 
  link a6,#0
  move.l  8(a6),a0   ; pointer auf &a
  move.l 12(a6),a1   ; pointer auf &r
  move.l (a0),(a1)   ; a.hi -> r.hi
  move.l 4(a0),4(a1) ; a.lo -> r.lo
  unlk a6
  rts




ADD64


Addiert zwei U64-Variablen. Das Ergebnis wird in einer dritten U64-Variable abgelegt.

.globl _add64
_add64:
  link a6,#0
  move.l  8(a6),a0   ; pointer auf &a
  move.l 12(a6),a1   ; pointer auf &b
  move.l 16(a6),a2   ; pointer auf &r
  move.l 4(a0),d0    ; D0 = a.lo    
  move.l (a0),d1     ; D1 = a.hi    
  add.l  4(a1),d0    ; D0 = a.lo + b.lo  
  move.l (a1),d2     ; D2 = b.hi 
  addx.l d2,d1       ; D1 = a.hi + b.hi + extend
  move.l d0,4(a2)    ; r.lo = D0 
  move.l d1,(a2)     ; r.hi = D1 
  unlk a6
  rts




SUB64


Subtrahiert die zweite U64 von der ersten U64-Variablen. Das Ergebnis wird in einer dritten U64-Variable abgelegt.

.globl _sub64
_sub64:
  link a6,#0
  move.l  8(a6),a0   ; pointer auf &a
  move.l 12(a6),a1   ; pointer auf &b
  move.l 16(a6),a2   ; pointer auf &r
  move.l 4(a0),d0    ; D0 = a.lo 
  move.l (a0),d1     ; D1 = a.hi 
  sub.l  4(a1),d0    ; D0 = a.lo - b.lo  
  move.l (a1),d2     ; D2 = b.hi 
  subx.l d2,d1       ; D1 = a.hi - b.hi - borrow
  move.l d0,4(a2)    ; r.lo = D0 
  move.l d1,(a2)     ; r.hi = D1 
  unlk a6
  rts




MUL64


Multipliziert zwei U64-Variablen. Das Ergebnis wird in einer dritten U64-Variable abgelegt.

.globl _mul64
_mul64:
  link a6,#0
  move.l  8(a6),a0   ; A0 = &a 
  move.l 12(a6),a1   ; A1 = &b
  move.l 16(a6),a2   ; A2 = &r
  move.l 4(a0),d0    ; D0 = a.lo 
  move.l (a0),d1     ; D1 = a.hi 
  move.l 4(a1),d2    ; D2 = b.lo 
  move.l (a1),d3     ; D3 = b.hi 
  clr.l d4           ; r.lo = 0    
  clr.l d5           ; r.hi = 0  
  moveq #63,d6       ; Schleifenzaehler
m64_loop:  
  btst #0,d2         ; Bit 0 von b gesetzt? 
  beq.s m64_noadd    ; nein, nicht addieren
  add.l d0,d4        ; r.lo = r.lo + a.lo
  addx.l d1,d5       ; r.hi = r.hi + a.hi + extend
m64_noadd:  
  lsl.l #1,d0        ; a <<= 1
  roxl.l #1,d1
  lsr.l #1,d3        ; b >>= 1
  roxr.l #1,d2
  dbra d6,m64_loop   ; 64 Bits bearbeiten
  move.l d4,4(a2)    ; r.lo ablegen 
  move.l d5,(a2)     ; r.hi ablegen 
  unlk a6
  rts




DIV64


Dividiert zwei U64-Variablen. Als Ergebnis stehen der Quotient und der Rest gleichzeitig in zwei getrennten U64-Variablen zur Verfügung.

.globl _div64
_div64:
  link a6,#-24       ; Platz fuer N,R,Q
  move.l  8(a6),a0   ; &a (Divisor)             
  move.l 12(a6),a1   ; &b (Divident)             
  move.l 16(a6),a2   ; &q (Quotient)            
  move.l 20(a6),a3   ; &r (Reminder)            
* Division durch 0 abfangen  
  move.l (a1),d0     ; D0 = b.lo
  move.l 4(a1),d1    ; D1 = b.hi
  or.l d1,d0
  bne.s div_nz       ; != 0, normale Division
* b == 0 : q=0, r=a               
  clr.l d0
  clr.l d1
  move.l d0,(a2)     ; q.lo = 0
  move.l d1,4(a2)    ; q.hi = 0
  move.l (a0),(a3)   ; r.lo = a.lo
  move.l 4(a0),4(a3) ; r.hi = a.hi
  unlk a6
  rts
div_nz:
* N = a
  move.l 4(a0),d0
  move.l (a0),d1 
  move.l d0,-24(a6)    ; N = a  
  move.l d1,-20(a6)   
  clr.l -16(a6)        ; R = 0
  clr.l -12(a6)
  clr.l  -8(a6)        ; Q = 0
  clr.l  -4(a6)
* Schleife ueber 64 Bit
  moveq #63,d7
div_loop:
* R <<= 1
  move.l -16(a6),d0
  move.l -12(a6),d1
  lsl.l #1,d0
  roxl.l #1,d1
  move.l d0,-16(a6)
  move.l d1,-12(a6)
* Bit 63 von N nach Bit 0 von R uebertragen
  move.l -20(a6),d0
  btst #31,d0
  beq.s no_msb
  move.l -16(a6),d1
  bset #0,d1
  move.l d1,-16(a6)
no_msb:
* N <<= 1 
  move.l -24(a6),d0    ; N.lo
  move.l -20(a6),d1    ; N.hi
  lsl.l #1,d0
  roxl.l #1,d1
  move.l d0,-24(a6)
  move.l d1,-20(a6)
* Vergleich: R >= b ?
  move.l -12(a6),d0    ; D0 = R.hi
  move.l (a1),d1       ; D1 = b.hi 
  cmp.l d1,d0
  blt.s no_sub         ; R < b 
  bgt.s do_sub         ; R > b
  move.l -16(a6),d0    ; D0 = R.lo
  move.l 4(a1),d1      ; D1 = b.lo 
  cmp.l d1,d0
  blt.s no_sub         ; R < b
do_sub:
* R = R - b
  move.l -16(a6),d0    ; D0 = R.lo
  move.l -12(a6),d1    ; D1 = R.hi
  move.l 4(a1),d2      ; D2 = b.lo 
  move.l (a1),d3       ; D3 = b.hi 
  sub.l d2,d0
  subx.l d3,d1
  move.l d0,-16(a6)
  move.l d1,-12(a6)
* Q = (Q << 1) | 1
  move.l -8(a6),d0     ; D0 = Q.lo
  move.l -4(a6),d1     ; D1 = Q.hi
  lsl.l #1,d0
  roxl.l #1,d1
  bset #0,d0           ; + 1
  move.l d0,-8(a6)
  move.l d1,-4(a6)
  bra.s after_q
no_sub:
* Q <<= 1
  move.l -8(a6),d0     ; D0 = Q.lo
  move.l -4(a6),d1     ; D1 = Q.hi
  lsl.l #1,d0
  roxl.l #1,d1
  move.l d0,-8(a6)
  move.l d1,-4(a6)
after_q:
  dbra d7,div_loop
* Ergebnis speichern
  move.l -8(a6),d0     ; Q.lo
  move.l -4(a6),d1     ; Q.hi
  move.l d1,(a2)       ; q.hi = Q.hi      
  move.l d0,4(a2)      ; q.lo = Q.lo       
  move.l -16(a6),d0    ; R.lo
  move.l -12(a6),d1    ; R.hi
  move.l d1,(a3)       ; r.hi = R.hi        
  move.l d0,4(a3)      ; r.lo = R.li        
  unlk a6
  rts




SHL64


Schiebt alle Bits einer U64-Variablen um eine Position nach links (Multiplikation mit 2).

.globl _shl64
_shl64:
  link a6,#0
  move.l  8(a6),a0   ; pointer auf &a 
  move.l (a0),d0     ; D0 = a.lo
  move.l 4(a0),d1    ; D1 = a.hi
  lsl.l #1,d0        ; D0 = a.lo << 1, extend
  roxl.l #1,d1       ; D1 = a.hi << 1, bit 0 = extend
  move.l d0,(a0)     ; a.lo = D0
  move.l d1,4(a0)    ; a.hi = D1
  unlk a6
  rts




SHL64


Schiebt alle Bits einer U64-Variablen um eine Position nach rechts (Division durch 2).

.globl _shr64
_shr64:
  link a6,#0
  move.l  8(a6),a0   ; pointer auf &a 
  move.l (a0),d0     ; D0 = a.lo
  move.l 4(a0),d1    ; D1 = a.hi
  lsr.l #1,d1        ; D1 = a.hi >> 1, extend
  roxr.l #1,d0       ; D0 = a.lo >> 1, bit 31 = extend
  move.l d0,(a0)     ; a.lo = D0
  move.l d1,4(a0)    ; a.hi = D1
  unlk a6
  rts



Die obigen Routinen sind in der Datei U64.S abgelegt und werden mit AS68 U64.S in die Objekt-Datei U64.O übersetzt. Um die Funktionen in C nutzen zu können, muss die Objekt-Datei zusätzlich beim Kompilieren angegeben werden. 


Die Header-Datei


In der Header-Datei U64.H ist die Datenstruktur definiert. Zusätzlich C-Funktionen zum Ausgeben einer U64-Variable als Dezimalzahl und zum Umwandeln eines Strings in eine U64-Variable.

/* u64.h  64-Bit-Arithmetik fuer CP/M-68K, C-Interface */

#ifndef U64_H
#define U64_H

/* Struktur 2 mal 32 Bit */
typedef struct {
    long hi;
    long lo;
} U64;


/* Wandelt U64 -> dezimalen String in dst */
char *dec64(a, dst)
U64  *a;
char *dst;
{
    char digits[32];     // Zwischenspeicher fuer Ziffern
    int  nd;             // Anzahl gesammelter Ziffern
    int  i;
    U64  tmp, ten, q, r;
    // Kopie von a anlegen
    tmp.hi = a->hi;
    tmp.lo = a->lo;
    // Spezialfall: 0
    if (tmp.hi == 0L && tmp.lo == 0L) {
        dst[0] = '0';
        dst[1] = (char)0;
        return dst;
    }
    make64(10L, &ten);
    nd = 0;
    // Ziffern von hinten sammeln
    while (!(tmp.hi == 0L && tmp.lo == 0L) && nd < (int)sizeof(digits)) {
        // tmp / 10: Quotient -> q, Rest -> r */
        div64(&tmp, &ten, &q, &r);
        // Rest (r) ist 0..9 -> Ziffer
        digits[nd++] = (char)('0' + (int)r.lo);
        // weiter mit Quotient
        tmp.hi = q.hi;
        tmp.lo = q.lo;
    }
    // Ziffern nach dst kopieren
    i = 0;
    while (nd > 0) {
        dst[i++] = digits[--nd];
    }
    dst[i] = (char)0;
    return dst;
}

/* Wandelt String nach U64 */
decto64(s, a)
char *s;
U64 *a;
{
    U64 res;       // aktuelles Ergebnis
    U64 ten;       // Konstante 10
    U64 tmp;       // Zwischenwert fuer res * 10
    U64 digit64;   // 64-Bit-Version einer einzelnen Ziffer
    int ch;

    // res = 0
    res.hi = 0L;
    res.lo = 0L;
    // ten = 10
    make64(10L, &ten);
    // fuehrende Leerzeichen ueberspringen
    while (*s == ' ' || *s == 't') {
        s++;
    }
    // optionales '+' ignorieren
    if (*s == '+') {
        s++;
    }
    // Ziffern verarbeiten
    while ((ch = *s) >= '0' && ch <= '9') {
        // res = res * 10
        mul64(&res, &ten, &tmp);
        // digit64 = (long)(ch - '0')
        make64((long)(ch - '0'), &digit64);
        // res = tmp + digit64
        add64(&tmp, &digit64, &res);
        s++;
    }
    // Ergebnis in *a zurueckschreiben
    a->hi = res.hi;
    a->lo = res.lo;
}

#endif /* U64_H */




Ein Testprogramm

Das Programm demonstriert die Anwendung aller oben gezeigten Funktionen.


#include "stdio.h"
#include "u64.h"

main()
{
  U64 a, b, q, r;
  char buf[32];

  printf("=========================================================n");
  printf("          Demonstration der 64-Bit Arithmetikn");
  printf("=========================================================n");
  a.hi = 0x01234567L;
  a.lo = 0x89ABCDEFL;
  decto64("20",&b);
  printf("A      = %08lX%08lX  (%20s dezimal)",(a).hi,(a).lo,dec64(&a,buf));
  printf("B      = %08lX%08lX  (%20s dezimal)",(b).hi,(b).lo,dec64(&b,buf));
  add64(&a,&b,&r);
  printf("A + B  = %08lX%08lX  (%20s dezimal)",(r).hi,(r).lo,dec64(&r,buf));
  sub64(&a,&b,&r);
  printf("A - B  = %08lX%08lX  (%20s dezimal)",(r).hi,(r).lo,dec64(&r,buf));
  mul64(&a,&b,&r);
  printf("A * B  = %08lX%08lX  (%20s dezimal)",(r).hi,(r).lo,dec64(&r,buf));
  div64(&a,&b,&q,&r);
  printf("A / B  = %08lX%08lX  (%20s dezimal)",(q).hi,(q).lo,dec64(&q,buf));
  printf("A  B  = %08lX%08lX  (%20s dezimal)",(r).hi,(r).lo,dec64(&r,buf));
  printf("=========================================================n");
  a.hi = 0L;
  a.lo = 0xFFFFFFFFL;
  printf("32 BIT = %08lX%08lX  (%20s dezimal)",(a).hi,(a).lo,dec64(&a,buf));
  a.hi = 0xFFFFFFFFL;
  printf("64 BIT = %08lX%08lX  (%20s dezimal)",(a).hi,(a).lo,dec64(&a,buf));
  b.hi = 0;
  b.lo = 0x00001000L;
  printf("B      = %08lX%08lX  (%20s dezimal)",(b).hi,(b).lo,dec64(&b,buf));
  shl64(&b);
  printf("SHL(B) = %08lX%08lX  (%20s dezimal)",(b).hi,(b).lo,dec64(&b,buf));
  shr64(&b);
  printf("SHR(B) = %08lX%08lX  (%20s dezimal)",(b).hi,(b).lo,dec64(&b,buf));
  printf("=========================================================n");
}




Screenshot


Nach dem Aufruf des generierten Programms T64.68K zeigt der NKC folgendes Bild. 








Zurück zum Inhaltsverzeichnis der Beiträge










Texte und Bilder © 2006 - 2025 by Andreas Rohmann
Layout and hosted by LOGO Datensysteme GmbH, Bremerhaven