Массивы
Randal E. Bryant
Массивы в си представляют из себя набор данных , обьединенных одним типом .
Одна из особенностей си-шных массивов заключается в том , что всегда можно сгенерировать
указатель , с помощью которого можно получить доступ к элементам массива .
В ассемблере это реализовано с помощью адресных манипуляций . Продвинутые оптимизированные
компиляторы генерируют достаточно качественный машинный код в этом плане .
Рассмотрим массив типа T и размерности N :
T A[N ];
В данном случае под массив выделяется L * N байт , где L - размер типа T .
Рассмотрим декларации :
char A[12];
char *B[8];
double C[6];
gouble *D[5]
Будут сгенерированы массивы со следующими параметрами :
Массив |
Размер типа |
Размер массива |
A |
1 |
12 |
B |
4 |
32 |
C |
8 |
48 |
D |
4 |
20 |
Рассмотрим пример : пусть у нас имеется int-вый массив Е и мы хотим вычислить
i-й элемент массива . Пусть адрес массива хранится в %edx и индекс i
хранится в %ecx . Следующая команда :
movl (%edx,%ecx,4),%eax
прочитает это элемент и сохранит его в регистре %eax .
Си-шная арифметика позволяет оперировать над указателями независимо от того , на какой
тип он указывает . Допустим , у нас имеется указатель *p , указывающий на массив типа T .
Выражение (p+i) имеет смысл , поскольку он будет указывать на реальный соответствующий
элемент массива Т .
Вернемся к нашему примеру с int-вым массивом E и произведем над ним следующую операцию :
int decimal5(int *x)
{
int i;
int val = 0;
for (i = 0; i < 5; i++)
val = 10*val + x[i];
return val;
}
int decimal5_opt(int *x)
{
int val = 0;
int *xend = x+4;
do {
val = 10*val + *x;
x++;
}
while (x <= xend);
return val;
}
Даны 2 си-шных варианта - исходный и оптимизированный .
Ассеммблерный эквивалент , сгенерированный компилятором , больше подходит для
2-й варианта .
xorl %eax,%eax # val = 0
leal 16(%ecx),%ebx # xend = x+4
leal (%eax,%eax,4),%edx # loop:
movl (%ecx),%eax # Compute 5*val
addl $4,%ecx # x++
leal (%eax,%edx,2),%eax # val = *x + 2*(5*val)
cmpl %ebx,%ecx # Compare x:xend
movl %edx,%eax # if , Go to loop
В этом примере команда leal используется для генерации адреса .
Команда movl используется для ссылки на память .
Яковлев С: Я написал вариант этой программы :
int xx[5]={1,2,3,4,5};
void main()
{
int *x=&xx[0];
printf("%d\n",*x);
int t = decimal5(x) ;
printf("%d",t);
}
int decimal5(int *x)
{
int i;
int val = 1;
for (i = 0; i < 5; i++)
val = val + x[i];
return val;
}
У меня компиляция с ключами -O2 -S породила следующий код :
.file "dec.c"
.globl xx
.data
.align 4
.type xx, @object
.size xx, 20
xx:
.long 1
.long 2
.long 3
.long 4
.long 5
.text
.p2align 2,,3
.globl decimal5
.type decimal5, @function
decimal5:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %ecx # в %ecx лежит адрес массива
movl $1, %eax
xorl %edx, %edx # в %edx лежит порядковый номер
.p2align 2,,3
.L5:
addl (%ecx,%edx,4), %eax # "магическое" извлечение по индексу
incl %edx
cmpl $4, %edx
jle .L5
leave
ret
.size decimal5, .-decimal5
.p2align 2,,3
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
andl $-16, %esp
subl $16, %esp
pushl $xx
call decimal5
leave
ret
.size main, .-main
.section .note.GNU-stack,"",@progbits
.ident "GCC: (GNU) 3.4.2 20041017 (Red Hat 3.4.2-6.fc3)"
Давайте рассмотрим 2-мерный массив :
int A[4][3];
В принципе , то же самое можно продекларировать и по-другому :
typedef int row3[3];
row3 A[4];
Мы определили новый тип row3 . Массив A состоит из 4-х таких типов , размер типа - 12 байт.
Итого суммарный размер : 4 * 12 = 48 байт
В памяти эти элементы расположены в следующем порядке :
A [0] [0] |
A [0] [1] |
A [0] [2] |
A [1] [0] |
A [1] [1] |
A [1] [2] |
A [2] [0] |
A [2] [1] |
A [2] [2] |
Рассмотрим пример : имеются 2 матрицы размера 3 х 3 . Нужно найти
произведение строки 1-й матрицы на столбец второй :
#define N 3
typedef int fix_matrix[N][N] ;
int fix_prod_ele (fix_matrix A, fix_matrix B, int i, int k)
{
int j;
int result = 0;
for (j = 0; j < N; j++)
result += A[i][j] * B[j][k];
return result;
}
void main()
{
fix_matrix A;
fix_matrix B;
int i ,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
A[i][j]=i+j;
B[i][j]=i*j;
}
}
int fp = fix_prod_ele (A,B,1,1) ;
}
Компиляция с опцией -O2 -S сгенерит следующий код :
.file "dec.c"
.text
.p2align 2,,3
.globl fix_prod_ele
.type fix_prod_ele, @function
fix_prod_ele:
pushl %ebp
movl %esp, %ebp
movl 16(%ebp), %edx # параметр i -> %edx
movl 20(%ebp), %eax # параметр k -> %eax
leal (%edx,%edx,2), %edx # адрес строки -> %edx
pushl %esi
leal 0(,%eax,4), %ecx # адрес столбца -> %ecx
sall $2, %edx
pushl %ebx
xorl %esi, %esi
addl 12(%ebp), %ecx # указатель - на первый элемент столбца
addl 8(%ebp), %edx # указатель - на первый элемент строки
movl $2, %ebx
.p2align 2,,3
.L5:
movl (%ecx), %eax
imull (%edx), %eax # перемножение
addl %eax, %esi # суммирование результата
addl $4, %edx # указатель переходит на следующий элемент строки
addl $12, %ecx # указатель переходит на следующий элемент столбца
decl %ebx # счетчик
jns .L5 # если > 0
popl %ebx
movl %esi, %eax
popl %esi
leave
ret
.size fix_prod_ele, .-fix_prod_ele
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "%d"
.text
.p2align 2,,3
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
pushl %edi
pushl %esi
pushl %ebx
subl $108, %esp
andl $-16, %esp
subl $16, %esp
xorl %esi, %esi
xorl %edi, %edi
.L17:
xorl %ecx, %ecx
xorl %ebx, %ebx
.p2align 2,,3
.L16:
leal (%edi,%ecx), %edx
leal (%esi,%ecx), %eax
incl %ecx
movl %ebx, -120(%ebp,%edx,4)
addl %esi, %ebx
cmpl $2, %ecx
movl %eax, -72(%ebp,%edx,4)
jle .L16
incl %esi
addl $3, %edi
cmpl $2, %esi
jle .L17
pushl $1
pushl $1
leal -120(%ebp), %eax
pushl %eax
leal -72(%ebp), %eax
pushl %eax
call fix_prod_ele
popl %edx
popl %ecx
pushl %eax
pushl $.LC0
call printf
leal -12(%ebp), %esp
popl %ebx
popl %esi
popl %edi
leave
ret
.size main, .-main
.section .note.GNU-stack,"",@progbits
.ident "GCC: (GNU) 3.4.2 20041017 (Red Hat 3.4.2-6.fc3)"
|