内存操作

简介

在高级语言中，我们可以使用多维数组对内存进行多维操作，但实际上，一般这些多维数组在内存中也只是按照一维的形式连续存储的。比如二维数组 arr[2][2]，他在内存中会占用 4 个单位的连续空间，分别保存 arr[0][0],arr[0][1],arr[1][0],arr[1][1]。

作为低级语言，汇编语言对内存只能进行一维操作。而为了实现多维操作，我们就需要使用一些技巧了，下面会进行举例分析。

样例分析

使用高级语言的话只需要两个 for 循环嵌套，如下：

1
2
3
4
5
6
7
int value = 0;
int arr[16][16];
for (int i = 0; i < 16; i++) {
    for (int j = 0; j < 16; j++) {
        arr[i][j] = value++;
    }
}

使用汇编语言的话，就需要分为三步：

  • 初始化数据
1
2
3
4
5
6
7
8
9
.data
    data: .word 0 : 256       # storage for 16x16 matrix of words

.text
    li $t0, 16         # $t0 = number of rows
    li $t1, 16         # $t1 = number of columns
    move $s0, $zero    # $s0 = row counter
    move $s1, $zero    # $s1 = column counter
    move $t2, $zero    # $t2 = the value to be stored

$t0 和 $t1 是总的行列数，$s0 和 $s1 是当前赋值的行列数，$t2 就是要赋的值。

  • 为一行矩阵赋值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#________ tag1 _______
loop:
    mult $s0, $t1      # $s2 = row * #cols (two-instruction sequence)
    mflo $s2           # move multiply result from lo register to $s2
    add $s2, $s2, $s1  # $s2 += column counter
    sll $s2, $s2, 2    # $s2 *= 4 (shift left 2 bits) for byte offset
    sw $t2, data($s2)  # store the value in matrix element
#---------------------  

#________ tag2 _______
    addi $t2, $t2, 1   # increment value to be stored
#---------------------  

# Loop control: If we increment past last column, reset colume counter and increment row counter
#               If we increment past last row,we're finished.

#________ tag3 _______
    addi $s1, $s1, 1   # increment coumn counter
#---------------------  

    bne $s1, $t1, loop # not at end of row so loop back

tag1 代码段为当前矩阵元素对应的内存赋值，tag2 和 tag3 代码段更新数据，最后一行判断这一行矩阵是否已完全赋值。

  • 准备为下一行矩阵赋值
1
2
3
4
5
6
    move $s1, $zero    # reset column counter
    addi $s0, $s0, 1   # increment row counter
    bne $s0, $t0, loop # not at end of matrix so loop back
# We're finished traversing the matrix
    li $v0, 10         # system service 10 is exit
    syscall            # we are outta here

当一行矩阵已赋完值后，更新数据，然后重新跳回到 loop 处为下一行矩阵赋值，直到整个矩阵都赋完值。

利用Macros简化二维数组的计算

算数组中元素的地址是一个重复且固定的算法，因此，计划创建一个 macro 来代替这些语句，从而减少代码行数，增加可读性，以便出错后更好的调试代码。

下面的代码实现了将对应的便宜量存储到%dst中

1
2
3
4
5
6
7
8
9
10
.macro calc_addr(%dst, %row, %column, %rank)
    # dts: the register to save the calculated address
    # row: the row that element is in
    # column: the column that element is in
    # rank: the number of lines(rows) in the matrix
    multu %row, %rank
    mflo %dst
    addu %dst, %dst, %column
    sll %dst, %dst, 2
.end_macro

这是一个矩阵乘法的汇编代码的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
#include <iostream>

int main()
{
    int n;
    int num1[10][10]={{0}};
    int num2[10][10]={{0}};
    int num3[10][10]={{0}};
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&num1[i][j]);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&num2[i][j]);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
                num3[i][j]+= num1[i][k] * num2[k][j];

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            printf("%d ", num3[i][j]);
        printf("\n");
    }

    return 0;
}

根据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
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
.data
num1: .space 300
num2: .space 300
num3: .space 300
str_space: .asciiz " "
str_enter: .asciiz "\n"

.macro getIndex(%dst,%row,%i,%j)
	mult %row,%i
	mflo %dst
	addu %dst,%dst,%j
	sll %dst,%dst,2
.end_macro

.macro readInt(%dst)
	li $v0,5
	syscall 
	move %dst,$v0
.end_macro 

.macro printStr(%dst)
	li $v0,4
	la $a0,%dst
	syscall
.end_macro 

.text
readInt($s0)	#read n

#read num1[][]
li $t7,0	#i
read1_for_i:
	beq $t7,$s0,read1_for_i_end	#i<n
	
	li $t8,0	#j
	read1_for_j:
		beq $t8,$s0,read1_for_j_end	#j<n
		
		readInt($t0)	#read num1[i][j] to $t0
		getIndex($t1,$s0,$t7,$t8)
		sw $t0,num1($t1)
		
		addi $t8,$t8,1
		j read1_for_j
	read1_for_j_end:

	addi $t7,$t7,1
	j read1_for_i
read1_for_i_end:

#read num2[][]
li $t7,0	#i=0
read2_for_i:
	beq $t7,$s0,read2_for_i_end	#i<n
	
	li $t8,0	#j=0
	read2_for_j:
		beq $t8,$s0,read2_for_j_end	#j<n
		
		readInt($t0)	#read num2[i][j] to $t0
		getIndex($t1,$s0,$t7,$t8)
		sw $t0,num2($t1)
		
		addi $t8,$t8,1
		j read2_for_j
	read2_for_j_end:

	addi $t7,$t7,1
	j read2_for_i
read2_for_i_end:

#initial num3[n][n]
li $t7,0	#i=0
ini_for_i:
	beq $t7,$s0,ini_for_i_end	#i<n
	
	li $t8,0	#j=0
	ini_for_j:
		beq $t8,$s0,ini_for_j_end	#j<n
		
		getIndex($t1,$s0,$t7,$t8)
		sw $0,num3($t1)
		
		addi $t8,$t8,1
		j ini_for_j
	ini_for_j_end:

	addi $t7,$t7,1
	j ini_for_i
ini_for_i_end:

#cumpute
#num3[i][j]=sum(num1[i][k]*num2[k][j])
li $t7,0	#i=0
com_for_i:
	beq $t7,$s0,com_for_i_end
	
	li $t8,0	#j=0
	com_for_j:
		beq $t8,$s0,com_for_j_end
		
		li $t9,0	#k=0
		com_for_k:
			beq $t9,$s0,com_for_k_end
			
			getIndex($t0,$s0,$t7,$t9)	#num1[i][k]
			getIndex($t1,$s0,$t9,$t8)	#num2[k][j]
			lw $s1,num1($t0)
			lw $s2,num2($t1)
			
			mult $s1,$s2	#num1[i][k]*num2[k][j]
			mflo $s1		#store to $s1
			
			getIndex($t0,$s0,$t7,$t8)	#num2[i][j]
			lw $s2,num3($t0)
			addu $s1,$s1,$s2	#num3[i][j]+=s1
			sw $s1,num3($t0)
			
			addi $t9,$t9,1	#k++
			j com_for_k
		com_for_k_end:
		
		addi $t8,$t8,1
		j com_for_j
	com_for_j_end:
	
	addi $t7,$t7,1
	j com_for_i
com_for_i_end:

#print num3[n][n]
li $t7,0	#i=0
prt_for_i:
	beq $t7,$s0,prt_for_i_end	#i<n
	
	li $t8,0	#j=0
	prt_for_j:
		beq $t8,$s0,prt_for_j_end	#j<n
		
		getIndex($t1,$s0,$t7,$t8)
		lw $t2,num3($t1)
		li $v0,1
		move $a0,$t2
		syscall
		printStr(str_space)
		
		addi $t8,$t8,1
		j prt_for_j
	prt_for_j_end:

	printStr(str_enter)
	addi $t7,$t7,1
	j prt_for_i
prt_for_i_end:

常用macro

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
.data
num: .space 600
str_enter: .asciiz "\n"
str_space: .asciiz " "

.macro getIndex(%dst,%n,%i,%y)
	mult %n,%i
	mflo %dst
	add %dst,%dst,%y
	sll %dst,%dst,2
.end_macro

.macro readInt(%dst)
	li $v0,5
	syscall
	move %dst,$v0
.end_macro

.macro printInt(%dst)
	move $a0,%dst
	li $v0,1
	syscall
.end_macro

.macro printStr(%dst)
	la $a0,%dst
	li $v0,4
	syscall
.end_macro

.macro inStack(%dst)
	sw %dst,0($sp)
	subi $sp,$sp,4
.end_macro

.macro outStack(%dst)
	addi $sp,$sp,4
	lw %dst,0($sp)
.end_macro	

.text
#balabal...