Doing something useful

You probably are tired of writing programs for computing the factorial. So I wrote one for you that uses functions. Your job will be to write a program that computes the greatest common divisor (gcd).

Calling conventions for Quiz06

This is what caller and callee have to know about each other in this Quiz:

The symbols RET, CALLEE0, ..., CALLEE3 are defined and are used for functions calls as follows:

  • The caller uses %RET for the return address (so a callee can return with jmp %RET, %0).

  • Functions can receive at most four arguments. The callee expects to receive them as follows:

    • First argument in %CALLEE0

    • ...

    • Forth argument %CALLEE3

    If a function returns a value the callee will store it in %CALLEE0 before returning.

    The callee is only allowed to use the register %CALLEE0, ..., %CALLEE3. These registers are consecutive (which is important to know for using instructions like divq that operate on register pairs and register triplets).

Quiz06: Computing the greatest common divisor

Write a program gcd.s that computes for two 64-bit unsigned integers the greatest common divisor (gcd). Provide the user a nice experience, i.e. using the program looks like this:

1
2
3
4
5
6
7
8
theon$ ulm gcd
a = 18
b = 12
gcd(18, 12) = 6
theon$ ulm gcd
a = 350982
b = 822647
gcd(350982, 822647) = 527

Use the following algorithm for your implementation:

Submit your program with

1
submit hpc quiz06 gcd.s

Conditional jumps for equalities and inequalities

So far we only have covered the conditional jumps `jz and jnz`. These can be used for realizing conditions like $x = y$ or $x \neq y$:

  • Jump if \(y = x\) is realized by the pattern: compute \(y-x\) and check if the zero flag is set: 

    1
2
    subq  %X,     %Y,     %0
jz    some_label

  • Jump if \(y \neq x\) is realized by the pattern: compute \(y-x\) and check if the zero flag is not set: 

    1
2
    subq  %X,     %Y,     %0
jnz   some_label

For inequalities we proceed accordingly. But we have to distinguish whether the bit pattern are used for signed or unsigned integers:

  • For unsigned integers instructions ja (jump above), jae (jump above equal), jb (jump below), jbe (jump below equal) can be used. In all these cases first compute \(y-x\) and then choose what condition should cause a jump:

    • ja jumps if \(y-x > 0\).

    • jae jumps if \(y-x \geq 0\).

    • jb jumps if \(y-x < 0\).

    • jbe jumps if \(y-x \leq 0\).

  • For signed integers instructions jg (jump greater), jge (jump greater equal), jl (jump less), jle (jump less equal) can be used. In all these cases first compute \(y-x\) and then choose what condition should cause a jump:

    • jg jumps if \(y-x > 0\).

    • jge jumps if \(y-x \geq 0\).

    • jl jumps if \(y-x < 0\).

    • jle jumps if \(y-x \leq 0\).

Example for computing the factorial

This is actually the program for computing the factorial that I showed in a video before. If you use it interactively it looks and feels like that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
theon$ ulm factorial
n = 20
20! = 2432902008176640000
theon$ ulm factorial
n = 0
0! = 1
theon$ ulm factorial
n = 3
3! = 6
theon$ ulm factorial
n = 10
10! = 3628800

Here the output when it is used non-interactive (by piping an echo output):

theon$ ulmas -o factorial factorial.s
theon$ echo 20 | ulm factorial
n = 20! = 2432902008176640000
theon$ echo 0 | ulm factorial
n = 0! = 1
theon$ echo 1 | ulm factorial
n = 1! = 1
theon$ echo 10 | ulm factorial
n = 10! = 3628800
theon$ 

For \(n>20\) we get \(n! \bmod 2^{64}\) as result (of course the ULM would provide instructions for computing that with 128 bits or more):

theon$ ulmas -o factorial factorial.s
theon$ echo 21 | ulm factorial
n = 21! = 14197454024290336768
theon$ 

Have a good look at it! Not just because it is nice but also because you can use ideas for the assignment ;-)

session09/func/factorial.s 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
        # Example for realizing leaf functions (recursive calls will fail!)


        # registers that a callee can use
        .equ    CALLEE0,        1
        .equ    CALLEE1,        CALLEE0 + 1
        .equ    CALLEE2,        CALLEE1 + 1
        .equ    CALLEE3,        CALLEE2 + 1

        # all other registers belong to the caller
        .equ    CALL,           CALLEE3 + 1     
        .equ    RET,            CALL + 1
        .equ    N,              RET + 1
        .equ    RES,            N + 1

        .data
str0    .string "n = "
str1    .string "! = "
str2    .string "\n"

        .text
/*
        Entry point of the program
*/

        # puts(str0);
        ldzwq   puts,           %CALL
        ldzwq   str0,           %CALLEE0
        jmp     %CALL,          %RET

        # readuint();
        ldzwq   readuint,       %CALL
        jmp     %CALL,          %RET
        addq    %CALLEE0,       %0,             %N

        # %RES = factorial(%N);
        ldzwq   factorial,      %CALL
        addq    %N,             %0,             %CALLEE0
        jmp     %CALL,          %RET
        addq    %CALLEE0,       %0,             %RES

        # printuint(%N);
        ldzwq   printuint,      %CALL
        addq    %N,             %0,             %CALLEE0
        jmp     %CALL,          %RET

        # puts(str1);
        ldzwq   puts,           %CALL
        ldzwq   str1,           %CALLEE0
        jmp     %CALL,          %RET


        # printuint(%RES);
        ldzwq   printuint,      %CALL
        addq    %RES,           %0,             %CALLEE0
        jmp     %CALL,          %RET

        # puts(str2);
        ldzwq   puts,           %CALL
        ldzwq   str2,           %CALLEE0
        jmp     %CALL,          %RET
/*
        Exit point
*/
        halt    0

//------------------------------------------------------------------------------

/*
        void
        puts(const char *);
*/

puts:
.L0     movzbq  (%CALLEE0),     %CALLEE1
        subq    0,              %CALLEE1,       %0
        jz      .L1
        putc    %CALLEE1
        addq    1,              %CALLEE0,       %CALLEE0
        jmp     .L0
.L1     jmp     %RET,           %0

/*
        uint64_t
        readuint();
*/
readuint:
        ldzwq   0,              %CALLEE0
.L2     getc    %CALLEE1
        subq    '\n',           %CALLEE1,       %0
        jz      .L3
        subq    '0',            %CALLEE1,       %CALLEE1
        imulq   10,             %CALLEE0,       %CALLEE0
        addq    %CALLEE1,       %CALLEE0,       %CALLEE0
        jmp     .L2
.L3     jmp     %RET,           %0


/*
        void
        printuint(uint64_t);
*/
        .bss
.L4     .space  21

        .text
printuint:
        ldzwq   .L4,            %CALLEE3

        ldzwq   0,              %CALLEE1

.L5     divq    10,             %CALLEE0,       %CALLEE0
        addq    '0',            %CALLEE2,       %CALLEE2
        addq    1,              %CALLEE3,       %CALLEE3
        movb    %CALLEE2,       (%CALLEE3)
        subq    0,              %CALLEE0,       %0
        jnz     .L5

.L6     movzbq  (%CALLEE3),     %CALLEE2
        subq    0,              %CALLEE2,       %0
        jz      .L7
        putc    %CALLEE2
        subq    1,              %CALLEE3,       %CALLEE3
        jmp     .L6
.L7     jmp     %RET,           %0

/*
        uint64_t
        factorial(uint64_t);
*/
factorial:
        ldzwq   1,              %CALLEE1
loop    subq    0,              %CALLEE0,       %0
        jz      done
        imulq   %CALLEE0,       %CALLEE1,       %CALLEE1
        subq    1,              %CALLEE0,       %CALLEE0
        jmp     loop
done    addq    %CALLEE1,       %0,             %CALLEE0
        jmp     %RET,           %0

Skeleton for quiz06

theon$ ulmas -o gcd gcd_skeleton.s
theon$ (echo 350982; echo  822647) | ulm gcd
a = b = gcd(350982, 822647) = 350982
theon$ 
session09/func/gcd_skeleton.s 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
        # Example for realizing leaf functions (recursive calls will fail!)


        # registers that a callee can use
        .equ    CALLEE0,        1
        .equ    CALLEE1,        CALLEE0 + 1
        .equ    CALLEE2,        CALLEE1 + 1
        .equ    CALLEE3,        CALLEE2 + 1

        # all other registers belong to the caller
        .equ    CALL,           CALLEE3 + 1     
        .equ    RET,            CALL + 1
        .equ    A,              RET + 1
        .equ    B,              A + 1
        .equ    RES,            B + 1

        .data
str0    .string "a = "
str1    .string "b = "
str2    .string "gcd("
str3    .string ", "
str4    .string ") = "
str5    .string "\n"

        .text
/*
        Entry point of the program
*/

        # puts(str0);
        ldzwq   puts,           %CALL
        ldzwq   str0,           %CALLEE0
        jmp     %CALL,          %RET

        # readuint();
        ldzwq   readuint,       %CALL
        jmp     %CALL,          %RET
        addq    %CALLEE0,       %0,             %A

        # puts(str1);
        ldzwq   puts,           %CALL
        ldzwq   str1,           %CALLEE0
        jmp     %CALL,          %RET

        # readuint();
        ldzwq   readuint,       %CALL
        jmp     %CALL,          %RET
        addq    %CALLEE0,       %0,             %B

        # %RES = gcd(%A, %B);
        ldzwq   gcd,            %CALL
        addq    %A,             %0,             %CALLEE0
        addq    %B,             %0,             %CALLEE1
        jmp     %CALL,          %RET
        addq    %CALLEE0,       %0,             %RES

        # puts(str2);
        ldzwq   puts,           %CALL
        ldzwq   str2,           %CALLEE0
        jmp     %CALL,          %RET


        # printuint(%A);
        ldzwq   printuint,      %CALL
        addq    %A,             %0,             %CALLEE0
        jmp     %CALL,          %RET

        # puts(str3);
        ldzwq   puts,           %CALL
        ldzwq   str3,           %CALLEE0
        jmp     %CALL,          %RET

        # printuint(%B);
        ldzwq   printuint,      %CALL
        addq    %B,             %0,             %CALLEE0
        jmp     %CALL,          %RET

        # puts(str4);
        ldzwq   puts,           %CALL
        ldzwq   str4,           %CALLEE0
        jmp     %CALL,          %RET

        # printuint(%RES);
        ldzwq   printuint,      %CALL
        addq    %RES,           %0,             %CALLEE0
        jmp     %CALL,          %RET

        # puts(str5);
        ldzwq   puts,           %CALL
        ldzwq   str5,           %CALLEE0
        jmp     %CALL,          %RET
/*
        Exit point
*/
        halt    0

//------------------------------------------------------------------------------

/*
        void
        puts(const char *)
*/

puts:
.L0     movzbq  (%CALLEE0),     %CALLEE1
        subq    0,              %CALLEE1,       %0
        jz      .L1
        putc    %CALLEE1
        addq    1,              %CALLEE0,       %CALLEE0
        jmp     .L0
.L1     jmp     %RET,           %0

/*
        uint64_t
        readuint();
*/
readuint:
        ldzwq   0,              %CALLEE0
.L2     getc    %CALLEE1
        subq    '\n',           %CALLEE1,       %0
        jz      .L3
        subq    '0',            %CALLEE1,       %CALLEE1
        imulq   10,             %CALLEE0,       %CALLEE0
        addq    %CALLEE1,       %CALLEE0,       %CALLEE0
        jmp     .L2
.L3     jmp     %RET,           %0


/*
        void
        printuint(uint64_t);
*/
        .bss
.L4     .space  21

        .text
printuint:
        ldzwq   .L4,            %CALLEE3

        ldzwq   0,              %CALLEE1

.L5     divq    10,             %CALLEE0,       %CALLEE0
        addq    '0',            %CALLEE2,       %CALLEE2
        addq    1,              %CALLEE3,       %CALLEE3
        movb    %CALLEE2,       (%CALLEE3)
        subq    0,              %CALLEE0,       %0
        jnz     .L5

.L6     movzbq  (%CALLEE3),     %CALLEE2
        subq    0,              %CALLEE2,       %0
        jz      .L7
        putc    %CALLEE2
        subq    1,              %CALLEE3,       %CALLEE3
        jmp     .L6
.L7     jmp     %RET,           %0

/*
        uint64_t
        gcd(uint64_t a, uint64_t b);

        a:      %CALLEE0
        b:      %CALLEE1
*/
gcd:

        #
        #       Your code here
        #

done    jmp     %RET,           %0