计算机系统-从应用程序到底层实现 课件 第12讲-程序机器级表示：复杂数据

《计算机系统》数据《计算机系统》课程教学组2025年春季学期0304结构0201小结联合数组内容提要数组的内存分配基本原则T

A[L]：typeT，lengthL，在内存中连续分配

L*sizeof(T)

个字节charstring[12];xx+12intval[5];xx+4x+8x+12x+16x+20doublea[3];x+24xx+8x+16char*p[3];xx+8x+16x+24xx+4x+8x+12IA32x86-64char怎么是4个字节？！数组的元素访问基本原则T

A[L]：typeT，lengthL，标识符A可用于表示数组的首地址，也可以通过TypeT*转换成数组首地址intval[5];15213xx+4x+8x+12x+16x+20Reference

Type

Valueval[4] int 3val int* xval+1 int* x+4&val[2] int* x+8val[5] int ??数组举例#defineZLEN5typedefintzip_dig[ZLEN];zip_dighnu={1,5,2,1,3};zip_digmit={0,2,1,3,9};zip_digucb={9,4,7,2,0};zip_dighnu;15213162024283236zip_digmit;02139364044485256zip_digucb;94720566064687276声明“zip_digcmu”等价于“intcmu[5]”连续声明的数组内存地址一般也是连续分配数组访问zip_dighnu;15213162024283236intget_digit(zip_digz,intdig){returnz[dig];}#%edx=z#%eax=digmovl(%edx,%eax,4),%eax#z[dig]寄存器

%edx

中存储数组的起始地址寄存器

%eax中保存了数组元素下标值需要访问的数据地址为

4*%eax+%edx内存寻址方式：(%edx,%eax,4)数组的循环访问#edx=z movl $0,%eax #%eax=i.L4: #loop: addl $1,(%edx,%eax,4) #z[i]++ addl $1,%eax #i++ cmpl $5,%eax #i:5 jne .L4 #if!=,gotoloop(.L4)voidzincr(zip_digz){inti;for(i=0;i<ZLEN;i++)z[i]++;}二维数组A[0][0]A[0][C-1]A[R-1][0]•

•

••

•

•A[R-1][C-1]•••••••

•

•A[0][0]A[0][C-1]•

•

•A[1][0]A[1][C-1]•

•

•A[R-1][0]A[R-1][C-1]•

•

•4*R*CBytes声明T

A[R][C];数据类型

T；R

行,C

列假设类型T的元素需要

K

字节数组大小R*C*Kbytes排列方式以行为主序intA[R][C];二维数组举例#definePCOUNT4zip_digpgh[PCOUNT]={{1,5,2,0,6},{1,5,2,1,3},{1,5,2,1,7},{1,5,2,2,1}};zip_digpgh[4];769611613615615206152131521715221“zip_digpgh[4]”等价于“intpgh[4][5]”变量

pgh:含有四个元素的数组，每个元素都是一个包含五个整数的数组——值得注意的是，这些元素在内存中是连续分配的数组的访问数组大酒店家庭成员43210找到楼层(3楼）找到家长3楼2号家庭先上车家长21001234567891011内存中数据是连续存放的，而二维数组又是以“行优先”的原则存放。二维数组访问•

•

••

•

•A[i][0]A[i][C-1]A[i]•

•

•A[R-1][0]A[R-1][C-1]A[R-1]•

•

•A•

•

•A[0][0]A[0][C-1]A[0]A+i*C*4A+(R-1)*C*4intA[R][C];A+C*4行向量方式

A[i]

是一个包含

C

个元素的数组每个元素都是T类型，需要K个字节从地址

A+

i*(C*K)开始二维数组访问•

•

••

•

•A[i][0]A[i][C-1]A[i]•

•

•A[R-1][0]A[R-1][C-1]A[R-1]•

•

•A•

•

•A[0][0]A[0][C-1]A[0]A+i*C*KA+(R-1)*C*KintA[R][C];A+C*K数据元素

A[i][j]是一个类型为T的元素，需要K个字节存储地址为：A+i*(C*K)+j*K=A+(i*C+j)*K嵌套数组zip_dighnu={1,5,2,1,3};zip_digmit={0,2,1,3,9};zip_digucb={9,4,7,2,0};#defineUCOUNT3int*univ[UCOUNT]={mit,hnu,ucb};变量

univ

定义了一个含有三个元素的数组；每个元素都是一个整数数组指针。361601656164168univhnumitucb152131620242832360213936404448525694720566064687276嵌套数组访问intget_univ_digit(intindex,intdig){returnuniv[index][dig];}取数据过程(IA32)Mem[Mem[univ+4*index]+4*dig]需要访问两次内存：第一次得到整数数组的头指针；然后再访问得到数据数组访问对比intget_pgh_digit(intindex,intdig){returnpgh[index][dig];}intget_univ_digit(intindex,intdig){returnuniv[index][dig];}二维数组嵌套在C代码中访问代码非常相似，但取数据方式很不相同！Mem[pgh+20*index+4*dig]Mem[Mem[univ+4*index]+4*dig]定长数组优化#defineN16typedefintfix_matrix[N][N];/*Getelementa[i][j]*/intfix_ele(fix_matrixa,inti,intj){returna[i][j];}#defineIDX(n,i,j)=((i)*(n)+(j))/*Getelementa[i][j]*/intvec_ele(intn,int*a,inti,intj){returna[IDX(n,i,j)];}/*Getelementa[i][j]*/intvar_ele(intn,inta[n][n],inti,intj){returna[i][j];}定长数组数组长度在编译前就已经确定编译器根据情况进行优化（P161）定长数组优化/*Getelementa[i][j]*/intfix_ele(fix_matrixa,inti,intj){returna[i][j];} movl 12(%ebp),%edx #i sall $6,%edx #i*64 movl 16(%ebp),%eax #j sall $2,%eax #j*4 addl 8(%ebp),%eax #a+j*4 movl (%eax,%edx),%eax #*(a+j*4+i*64)优化的数组元素访问

地址：

A+i*(C*K)

+j*KC=16,K=4定长数组优化无优化的数组元素访问

地址：A+i*(C*K)

+j*KC=n,K=4，需要执行整数乘法操作/*Getelementa[i][j]*/intvar_ele(intn,inta[n][n],inti,intj){returna[i][j];} movl 8(%ebp),%eax #n sall $2,%eax #n*4 movl %eax,%edx #n*4 imull 16(%ebp),%edx #i*n*4 movl 20(%ebp),%eax #j sall $2,%eax #j*4 addl 12(%ebp),%eax #a+j*4 movl (%eax,%edx),%eax #*(a+j*4+i*n*4)课堂习题有一整型数组intA[5][3]，&A=0xF4150C18,求其下列元素地址：（1）A[2][1];（2）A[3][2];（3）A[4][1]0xF4150C40，0xF4150C50，0xF4150C580xF4150C34，0xF4150C44，0xF4150C4C0xF4150C36，0xF4150C42，0xF4150C4A0xF4150C34，0xF4150C44，0xF4150C4D0304结构0201小结联合数组内容提要结构的内存分配structrec{inta[3];inti;structrec*n;};内存分配ian0121620C语言中的结构内存连续分配通过结构的名称与成员名称来访问数据结构中可能包括不同数据类型的成员结构数据的访问structrec{inta[3];inti;structrec*n;};ian0121620r+12rr+16结构中的元素可通过：rec->a，rec->i，rec->n或者rec.a，rec.i，rec.n进行访问访问结构成员变量结构名表明了首地址通过编移量访问IA32汇编代码 #%edx=val #%eax=r

movl%edx,12(%eax)

#Mem[r+12]=valvoidset_i(structrec*r,intval){r->i=val;}结构数据的访问r+idx*4rian0121620structrec{inta[3];inti;structrec*n;};参数Mem[%ebp+8]:rMem[%ebp+12]:idx movl 12(%ebp),%eax #Getidx sall $2,%eax #idx*4 addl 8(%ebp),%eax #r+idx*4int*get_ap(structrec*r,intidx){return&r->a[idx];}结构数据的访问structrec{inta[3];inti;structrec*n;};voidset_val(structrec*r,intval){inti=r->i;r->a[i]=val;

r=r->n;

}ian0121620Element

iRegisterValue%edxr%ecxval movl 12(%edx),%eax #r->i movl %ecx,(%edx,%eax,4) #r->a[i]=val movl 16(%edx),%edx #r=r->n未对齐数据数据对齐要求数据地址必须是

K的整数倍（K为数据类型的字节数）结构与对齐ci[0]i[1]vpp+1p+5p+9p+17structS1{charc;inti[2];doublev;}*p;ci[0]i[1]v3bytes4bytesp+0p+4p+8p+16p+24Multipleof4Multipleof8Multipleof8Multipleof8对齐的一些规则1byte:char,…没有限制2bytes:short,…地址位的最低位必须是024bytes:int,float,char*,…地址位的最低两位必须是0028bytes:double,…Windows(以及绝大多数操作系统):地址位的最低三位必须是0002Linux:地址位的最低两位必须是00212bytes:longdoubleWindows,Linux:地址位的最低两位必须是002结构的对齐方式在结构内部:

必须满足每一种数据类型的对齐方式整体上首地址必须是

K的整数倍（K为最大元素字节数）例如(Windows或x86-64):structS1中，K=8（因为最大元素为double）structS1{charc;inti[2];doublev;}*p;ci[0]i[1]v3bytes4bytesp+0p+4p+8p+16p+24Multipleof4Multipleof8Multipleof8Multipleof8结构内存分配的差异x86-64,

WindowsK=8（最大元素为double，8对齐）IA32LinuxK=4（最大元素为double，4对齐）structS1{charc;inti[2];doublev;}*p;c3bytesi[0]i[1]4bytesvp+0p+4p+8p+16p+24c3bytesi[0]i[1]vp+0p+4p+8p+12p+20空字节填充（Windows&X86-64）structS2{doublev;inti[2];charc;}*p;vi[0]i[1]c7bytesp+0p+8p+16p+24Multipleofk=8空字节填充（IA32Linux）structS2{doublev;inti[2];charc;}*p;vi[0]i[1]c3bytesp+0p+8p+16P+20Multipleofk=4结构数组（Windows&X86-64）因为在内存中，数组元素是连接分配，因此需要考虑每一个结构的起始地址对齐。K＝8structS2{doublev;inti[2];charc;}a[10];a[0]a[1]a[2]•••a+0a+24a+48a+72vi[0]i[1]c7bytesA+24A+32A+40A+48A[1]:结构数组（IA32Linux）因为在内存中，数组元素是连接分配，因此需要考虑每一个结构的起始地址对齐。K＝4structS2{doublev;inti[2];charc;}a[10];a[0]a[1]a[2]•••a+0a+20a+40a+60vi[0]i[1]c3bytesA+20A+28A+36A+40A[1]:结构对齐三大原则结构的首地址必须是最大元素字节数的整数倍；结构中每个数据的地址必须是自身字节数的整数倍；结构的总体长度必须是最大元素字节数的整数倍。结构数组元素访问从声明来看，a[idx]元素j的偏移量应该6但实际上却是8structS3{shorti;floatv;shortj;}a[10];

a[0]•••

a[idx]•••a+0a+12a+12*idxi2bytesvj2bytesa+12*idxa+12*idx+8shortget_j(intidx){returna[idx].j;} #%eax=idx leal(%eax,%eax,2),%eax#3*idx movswla+8(,%eax,4),%eax节省内存空间大尺寸数据放前面！效果如下(K=4)structS4{charc;inti;chard;}*p;structS5{inti;charc;chard;}*p;ci3bytesd3bytescid2bytes课堂习题Windonws环境下定义：structtest{ inti; charc; intj; doubleb;}该结构在内存中占用28字节；该结构在内存中占用16字节；该结构在内存中占用24字节；该结构在内存中占用32字节；0304结构0201小结联合数组内容提要联合的内存分配根据最大的元素来分配内存空间unionU1{charc;inti[2];doublev;}*up;structS1{charc;inti[2];doublev;}*sp;ci[0]i[1]vup+0up+4up+8c3bytesi[0]i[1]4bytesvsp+0sp+4sp+8sp+16sp+24联合中的类型typedefunion{floatf;unsignedu;}bit_float_t;fu04floatbit2float(unsignedu){bit_float_targ;arg.u=u;returnarg.f;}unsignedfloat2bit(floatf){bit_float_targ;arg.f=f;returnarg.u;}Sameas(float)u?Sameas(unsigned)f?联合的字节顺序union{unsignedcharc[8];unsignedshorts[4];unsignedinti[2];unsignedlongl[1];}dw;c[0]c[1]c[2]c[3]c[4]c[5]c[6]c[7]s[0]s[1]s[2]s[3]i[0]i[1]l[0]32-bitc[0]c[1]c[2]c[3]c[4]c[5]c[6]c[7]s[0]s[1]s[2]s[3]i[0]i[1]l[0]64-bit联合的字节顺序intj;for(j=0;j<8;j++)dw.c[j]=0xf0+j;printf("Characters0-7==[0x%x,0x%x,0x%x,0x%x,0x%x,0x%x,0x%x,0x%x]\n",dw.c[0],dw.c[1],dw.c[2],dw.c[3],dw.c[4],dw.c[5],dw.c[6],dw.c[7]);printf("Shorts0-3==[0x%x,0x%x,0x%x,0x%x]\n",dw.s[0],dw.s[1],dw.s[2],dw.s[3]);printf("Ints0-1==[0x%x,0x%x]\n",dw.i[0],dw.i[1]);printf("Long0==[0x%lx]\n",dw.l[0]);union{unsignedcharc[8];unsignedshorts[4];unsignedinti[2];unsignedlongl[1];}dw;联合的字节顺序IA32小端法f0f1f2f3f4f5f6f7c[0]c[1]c[2]c[3]c[4]c[5]c[6]c[7]s[0]s[1]s[2]s[3]i[0]i[1]l[0]LSBMSBLSBMSBPrintPrintCharacters0-7==[0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7]Shorts0-3==[0xf1f0,0xf3f2,0xf5f4,0xf7f6]Ints0-1==[0xf3f2f1f0,0xf7f6f5f4]Long0=