-
Notifications
You must be signed in to change notification settings - Fork 0
/
stack.s
158 lines (134 loc) · 3.36 KB
/
stack.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
.text
.globl _s_create
.globl _s_push
.globl _s_pop
.globl _s_top
.globl _s_destroy
.globl _s_start_iterator
.globl _s_next
.equ DEFAULT_STACK_CAP, 8 ; 8 quads
.equ STACK_SIZE, 4 + 4 + 8 + 4
.p2align 2
; stack requires 20 bytes.
; word top +0
; word capacity +4
; quad data +8
; word iterator +16
; return stack in x0
_s_create:
stp fp, lr, [sp, -32]!
str x19, [sp, 16]
; initialize memory to zero for
mov x0, STACK_SIZE
bl _malloc
mov x19, x0 ; store for later in x19
mov w1, -1 ; top to -1 to start
str w1, [x0] ; set count to zero
mov w1, DEFAULT_STACK_CAP
str w1, [x0, 4] ; set capacity
str wzr, [x0, 16] ; set iterator 0
; allocate data
mov w0, w1
mov w1, 8 ; quads
bl _calloc
str x0, [x19, 8] ; assign pointer to stack structure
mov x0, x19 ; return stack pointer from this procedure
ldr x19, [sp, 16]
ldp fp, lr, [sp], 32
ret
; accept stack in x0
; quad value in x1
_s_push: ; cannot clobber x12
stp fp, lr, [sp, -32]!
stp x19, x20, [sp, 16]
mov x19, x0 ; use x19 for stack
mov x20, x1 ; use x20 for value
; load stack count and check if need to resize
ldr w8, [x19] ; load count
ldr w9, [x19, 4] ; load cap
cmp w9, w8, lsl 1 ; compare cap to top times two
bgt 0f ; if it's greater, do nothing, otherwise resize
; resize here
lsl w9, w9, 1 ; double cap
str w9, [x19, 4] ; store new cap
; call realloc
ldr x0, [x19, 8] ; load current data address
sxtw x1, w9 ; sign extend new size to x1 for argument
; use quad alignment for new size
lsl x1, x1, 3
bl _realloc
str x0, [x19, 8] ; store new pointer
0:
; insert here
; load pointer to data
ldr x8, [x19, 8]
ldr w9, [x19] ; load count
sxtw x9, w9 ; sign extend w1 to x1
add x9, x9, 1 ; increment
str w9, [x19] ; write new count
str x20, [x8, x9, lsl 3] ; store value in data at count offset with quad alignment
; guarantee next element is zero
add x9, x9, 1
str xzr, [x8, x9, lsl 3]
ldp x19, x20, [sp, 16]
ldp fp, lr, [sp], 32
ret
; accept stack in x0
; return value in x0
_s_pop: ; cannot clobber x12
; load current count
ldr w8, [x0]
; guard to make sure stack isn't empty
cmp w8, -1
bgt 0f
mov x0, xzr ; return zero
ret
0:
sxtw x10, w8
ldr x9, [x0, 8] ; data
ldr x11, [x9, x10, lsl 3] ; access value at top of stack, x0 for return
str xzr, [x9, x10, lsl 3] ; overwrite value with zero
subs w8, w8, 1 ; decrement top
str w8, [x0] ; write new top
mov x0, x11 ; return value
ret
; stack in x0
; value in x0
_s_top: ; cannot clobber x12
ldr w8, [x0]
cmp w8, -1
bgt 0f
mov x0, xzr ; return zero
ret
0:
; load current top
ldr x9, [x0, 8]
ldr x0, [x9, x8, lsl 3]
ret
; stack in x0
; simply deallocates stack and its data
_s_destroy:
stp fp, lr, [sp, -32]!
str x19, [sp, 16]
mov x19, x0 ; save
ldr x0, [x0, 8]
bl _free
mov x0, x19
bl _free
ldr x19, [sp, 16]
ldp fp, lr, [sp], 32
ret
; stack in x0
_s_start_iterator:
str wzr, [x0, 16] ; set iterator to bottom of stack
ret
; stack in x0
_s_next:
ldr w8, [x0, 16] ; load iterator
sxtw x8, w8
ldr x1, [x0, 8] ; data
ldr x1, [x1, x8, lsl 3] ; load return value
add w8, w8, 1
str w8, [x0, 16] ; update iterator
mov x0, x1
ret