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
Последние статьи :
  Rust 07.11   
  Go 25.12   
  EXT4 10.11   
  FS benchmark 15.09   
  Сетунь 23.07   
  Trees 25.06   
  Apache 03.02   
  SQL 30.07   
  JFS 10.06   
  B-trees 01.06   
 
TOP 20
 Go Web ...589 
 2.0-> Linux IP Networking...337 
 Secure Programming for Li...276 
 2.6-> Kernel 2.6.17...222 
 Kamran Husain...213 
 William Gropp...211 
 Robbins 4...203 
 Rodriguez 9...194 
 Rodriguez 6...187 
 UML 3...187 
 Advanced Bash Scripting G...187 
 Kamran Husain...181 
 Steve Pate 1...181 
 Ethreal 1...179 
 Стивенс 8...179 
 Daniel Bovet 2...177 
 Rodriguez 8...176 
 Kernel Notes...172 
 Steve Pate 3...172 
 Advanced Bash Scripting G...167 
 
  01.03.2019 : 2682145 посещений 

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

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

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