Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
iakovlev.org

Массивы

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)"
 
 
Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье