Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
 iakovlev.org 
 Languages
 С
 GNU С Library 
 Qt 
 STL 
 Threads 
 C++ 
 Samples 
 stanford.edu 
 ANSI C
 Libs
 LD
 Socket
 Pusher
 Pipes
 Encryption
 Plugin
 Inter-Process
 Errors
 Deep C Secrets
 C + UNIX
 Linked Lists / Trees
 Asm
 Perl
 Python
 Shell
 Erlang
 Go
 Rust
 Алгоритмы
NEWS
Последние статьи :
  Тренажёр 16.01   
  Эльбрус 05.12   
  Алгоритмы 12.04   
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
 
TOP 20
 MINIX...3057 
 Solaris...2933 
 LD...2904 
 Linux Kernel 2.6...2470 
 William Gropp...2180 
 Rodriguez 6...2011 
 C++ Templates 3...1945 
 Trees...1936 
 Kamran Husain...1865 
 Secure Programming for Li...1791 
 Максвелл 5...1710 
 DevFS...1693 
 Part 3...1682 
 Stein-MacEachern-> Час...1632 
 Go Web ...1624 
 Ethreal 4...1618 
 Arrays...1606 
 Стивенс 9...1603 
 Максвелл 1...1592 
 FAQ...1538 
 
  01.01.2024 : 3621733 посещений 

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

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

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