写点什么

程序的机器级表示 - 数组的分配和访问

用户头像
引花眠
关注
发布于: 2020 年 09 月 06 日

基本原则

数组:将一组标量数据聚集成更大数据类型的方式。 在C语言中,可以产生指向数组中元素的指针,并对指针进行运算。 对于数据类型T和整数常数N,声明语句如下:



T A[N];



如果起始位置标示为x,则这段代码有两个作用



  1. 在内存中分配一个L*N字节的连续区域,其中L是数据类型T的大小(单位为字节)

  2. 标识符A,可以用A来作为指向数组开头的指针,这个指针的值就是x



可以用0~N-1的整数索引来访问该数组的元素,数组i被保存在x+L*i的位置。 对于以下数组声明:



char A[12];
char *B[15];
int C[6];
double *D[5];



数组元素与位置的关系如下



数组 元素大小 总的大小 起始地址 元素i
A 1 12 Xa Xa+i
B 8 120 Xb Xb+i*8
C 4 24 Xc Xc+i*4
D 8 40 Xd Xd+i*8



之前有关于如何访问内存中的数据,可以发现内存访问指令可以来简化数组访问 假设E是一个int数组,而我们想计算E[i],如果E的起始地址在%rdx,i存放在%rcx,则 (%rdx,%rcx,4)会执行 %rdx+4*%rcx



mov (%rdx,%rcx,4),%eax #读取可以将Xe+4*i内存位置的值,放在%eax



指针运算

C语言允许对指针进行运算,而计算出来的值会根据该指针引用的数据类型的大小进行伸缩。



也就是说,如果 P 是一个执行类型 T 的数据的指针,P 的值为 Xp,那么表达式P+i 的值为 Xp+L*i,这里 L 是数据类型T的大小。



假设整型数组 E 的起始地址和整数索引 i 分别存放在寄存器 %edx 和 %ecx 中,下面是每个表达式的汇编代码实现,结果存放在 %eax 中。



表达式 类型 值 汇编代码
E int* Xe movq %rdx, %rax
E[0] int M[Xe] movl (%rdx), %rax
E[i] int M[Xe+4i] movl (%rdx, %rcx, 4), %eax
&E[2] int* Xe+8 leaq 8(%rdx), %rax
E+i-1 int* Xe+4i-4 leaq -4(%rdx, %rcx, 4), %rax
*(E+i-3) int M[Xe+4i-12] movl -12(%rdx, %rcx, 4), %eax
&E[i]-E long i movq %rcx, rax




ps: leaq 指令用来计算地址

定长数组

要理解定长和变长数组,我们必须搞清楚一个概念,就是说这个“定”和“变”是针对什么来说的。在这里我们说,这两个字是针对编译器来说的,也就是说,如果在编译时数组的长度确定,我们就称为定长数组,反之则称为变长数组。



#define N 16
typedef int fix_matrix[N][N];
// 计算A的i行与B的k列的内积
int fix_prod_ele(fix_matrix A, fix_matrix B, long i, long k){
long j;
int result;
for(j = 0 ;j < N; j++){
result += A[i][j] * B[j][k];
}
return result;
}



反编译之后的代码



// 计算A的i行与B的k列的内积
int fix_prod_ele(fix_matrix A, fix_matrix B, long i, long k){
int *Aptr = &A[i][0];
int *Bptr = &B[0][k];
int *Bend = &B[N][k];
int result = 0;
do{
result += *Aptr * *Bptr;
*Aptr++;
*Bptr += N;
}while(Bptr!=Bend)
return result;
}



去掉了索引j,把所有数组引用都转换为指针引用, 指针Aptr指向A的i行, 指针Bptr指向B的k列,Bptr+N就可以指向下一列 指针Bend指向B的k列的最后一个元素,用于终止条件判断。



变长数组

与定长数组不同,变长数组中元素的个数可以是一个表达式,表达式可以在数组分配时才计算。



int var_ele(int n,int A[n][n],int i,int j)
{
return A[i][j];
}



与定长数组计算i的地址不同,动态的版本必须用乘法指令对i伸缩n倍。



参考资料

  1. 豆瓣-深入理解计算机系统(原书第3版)

发布于: 2020 年 09 月 06 日阅读数: 43
用户头像

引花眠

关注

还未添加个人签名 2018.06.11 加入

还未添加个人简介

评论

发布
暂无评论
程序的机器级表示-数组的分配和访问