Single Linked Lists and Quiz 15

Implement the following C program in assembly:

session15/list/list.c 
 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
#include <stdio.h>

struct ListNode
{
    struct ListNode *next;
    char            id;
};

struct ListNode c, a, b;

int printList(const struct ListNode *listNode);

int
main(void)
{
    a.id = 'a';
    a.next = &b;

    b.id = 'b';
    b.next = &c;

    c.id = 'c';
    c.next = 0;

    printList(&a);

    putchar('\n');
}

int
printList(const struct ListNode *listNode)
{
    for (; listNode; listNode = listNode->next) {
        putchar(listNode->id);
    }

    return 1;   // because we need to return something
}

Of course the function call putchar() can be realized with a putc instruction.

You program should generate the same output as the assmbler program created by gcc:

theon$ gcc list.c
theon$ ./a.out
abc
theon$ 

Or ucc:

theon$ ucc list.c
theon$ ./a.out
abc
theon$ 

Submit your assembly program _list.s- with:

1
submit hpc quiz15 isa.txt list.s

There are no automatic tests (no message/email means your submit succeeded).

Provided Material: Skeleton

You can use the instruction set from Session 14 and this skeleton:

session15/list/list_quiz15.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
    # calling conventions
    .equ    FP,         1
    .equ    SP,         2
    .equ    RET_ADDR,   3

    .equ    ret,        0
    .equ    fp,         ret + 8
    .equ    rval,       fp + 8
    .equ    fparam0,    rval + 8
    .equ    fparam1,    fparam0 + 8

    .equ    local0,     -8
    .equ    local1,     local0 - 8

    # for the demo
    .equ    FUNC_ADDR,  4


    /*
     * function: _start
     */
_start:
    ldzwq   0,              %SP

    # call: int main(void)
    subq    8 * (3 + 0),    %SP,        %SP
    ldzwq   main,           %FUNC_ADDR
    call    %FUNC_ADDR,     %RET_ADDR
    movq    rval(%SP),      %4                  # return value in %4
    addq    8 * (3 + 0),    %SP,        %SP


    halt    %4                                  # halt with return value

    /*
       struct ListNode c, a, b;
    */
    .bss
    .align 8
a:
    .space 9

    .align 8
b:
    .space 9

    .align 8
c:
    .space 9



    /*
     * function: int main(void)
     */
    .text
#
#   pool for main
#
    .align  8
.main.pool
.main.pool.a
    .quad   a
.main.pool.b
    .quad   b
.main.pool.c
    .quad   c
.main.pool.printList
    .quad   printList

#
#   offsets for pool members
#
    .equ    p.a,            (.main.pool.a - .main.pool) / 8
    .equ    p.b,            (.main.pool.b - .main.pool) / 8
    .equ    p.c,            (.main.pool.c - .main.pool) / 8
    .equ    p.printList,    (.main.pool.printList - .main.pool) / 8

    .text
main:
    // prologue
    movq    %RET_ADDR,      ret(%SP)
    movq    %FP,            fp(%SP)
    movq    %SP,            %FP
    subq    8 * 1,          %SP,            %SP

    .equ    n,              local0

    // body

#   a.id = 'a';
    ldzwq   'a',            %4
    ldpa    .main.pool,     %5
    ldfp    p.a(%5),        %5
    movb    %4,             8(%5)

#   a.next = &b;

#   b.id = 'b';

#   b.next = &c;

#   c.id = 'c';

#   c.next = 0;

#   printList(&a);

#   putchar('\n');

#   return 0;

.main.ret
    // epilogue
    movq    %FP,            %SP
    movq    fp(%SP),        %FP
    movq    ret(%SP),       %RET_ADDR
    ret     %RET_ADDR

    /*
     * function: int printList(const struct ListNode *listNode)
     */
    .text
printList:
    // prologue
    movq    %RET_ADDR,      ret(%SP)
    movq    %FP,            fp(%SP)
    movq    %SP,            %FP
    subq    8 * 0,          %SP,        %SP

    .equ    listNode,       fparam0

    // body

#   for (; listNode; listNode = listNode->next) {

#   putchar(listNode->id);


#   }

#   return 1;

    // epilogue
    movq    %FP,            %SP
    movq    fp(%SP),        %FP
    movq    ret(%SP),       %RET_ADDR
    ret     %RET_ADDR

In listquiz15.s_ the definition

1
struct ListNode c, a, b;

of the uninitialized global variables a, b and c in the BSS segment is already realized. Also the statement

1
a.id = 'a';

is already implemented.