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...3058 
 Solaris...2934 
 LD...2908 
 Linux Kernel 2.6...2488 
 William Gropp...2187 
 Rodriguez 6...2018 
 C++ Templates 3...1948 
 Trees...1941 
 Kamran Husain...1868 
 Secure Programming for Li...1795 
 Максвелл 5...1712 
 DevFS...1696 
 Part 3...1686 
 Stein-MacEachern-> Час...1635 
 Go Web ...1630 
 Ethreal 4...1620 
 Стивенс 9...1609 
 Arrays...1609 
 Максвелл 1...1598 
 FAQ...1540 
 
  01.01.2024 : 3621733 посещений 

iakovlev.org

String

В этой статье рассматриваются функции ядра 2.6.16 , связанные с обработкой строк. В частности , речь пойдет о файлах:
include/asm-i386/string.h
lib/string.c.

В хидере представлена низкоуровневая реализация этих функций с использованием inline-asm. Во втором - библиотечном - файле представлена высоко-уровневая c-реализация.

Рассмотрим обе реализации для следующих функций:


 char * strcpy - копирование строки
 char * strcat - конкатенация строки
 int strcmp    - сравнение 2-х строк
 char * strchr - поиск символа в строке
 size_t strlen - длина строки
 void * memcpy - копирует области памяти
 

char * strcpy

Функция имеет 2 параметра - адрес приемника и адрес источника. Функция strcpy() копирует строку, указанную как src (включая завершающий символ `\0'), в массив, указанный как dest. Строки не могут перекрываться, и в целевой строке dest должно быть достаточно места для получения копии. Функция strcpy() возвращает указатель на целевую строку dest. Если целевая строка strcpy недостаточно велика , то может случиться переполнение строк фиксированной длины.

Давайте сравним оба варианта.
Си-вариант:


 char *strcpy(char *dest, const char *src)
 {
 	char *tmp = dest;
 
 	while ((*dest++ = *src++) != '\0')
 		/* nothing */;
 	return tmp;
 }
 

Инлайн-вариант:


 static inline char * strcpy(char * dest,const char *src)
 {
 int d0, d1, d2;
 __asm__ __volatile__(
 	"1:\tlodsb\n\t"
 	"stosb\n\t"
 	"testb %%al,%%al\n\t"
 	"jne 1b"
 	: "=&S" (d0), "=&D" (d1), "=&a" (d2)
 	:"0" (src),"1" (dest) : "memory");
 return dest;
 }
 

Рассмотрим пример :


 char dest [ 128 ] ;
 char *source = "claudio" ;
 int main ( void )
 {
 strcpy ( &dest[0],source ) ;
 puts ( dest) ;
 return 0;
 }
 
Сишный вариант функции дизассемблируется в следующий код (gcc 4.1.0) - с флагом -O2 :

 	movzbl	(%ecx), %eax
 	addl	$1, %ecx
 	movb	%al, (%edx)
 	addl	$1, %edx
 	testb	%al, %al
 	jne	.L2
 
В стеке находятся приемник и источник. Здесь в ecx лежит указатель на источник , в edx - указатель на приемник . Выполняем цикл , пока не доходим в источнике до 0.

 

Теперь рассмотрим инлайн-вариант функции.
Адрес источника хранится в esi, приемника - в edi, процесс копирования идет до тех пор , пока мы не достигнем 0. Констрэйнты "S", "D", "a" указывают на то , что регистры esi, edi , eax - это clobber registers. Инлайн-вариант функции и дизассемблировать не надо - и так понятно , что получится следующий код :


 	1:	lodsb
 	stosb
 	testb %al,%al
 	jne 1b
 
Это цикл , внутри которого :
1 lodsb - в регистр al грузим 1-й байт из источника - регистра SI
2 stosb - копируем байт из al в приемник - DI
3 testb %al,%al - проверяем , не дошли ли до нулевого байта.
4 jne 1b - повторяем цикл

Разница в том , что в первом случае для операции копирования в цикле мы используем регистры общего назначения и источник с приемником помещаем в стек , во втором же случае в цикле мы работаем с регистрами si и di , а в стек помещаем указатели на память - регистры si и di, которые указывают на память с источником с приемником.

char * strcat

strcat добавляет копию строки, указанной src, (включая завершающий знак NULL) к концу строки, указанной dst. Пеpвый знак src замещает знак NULL в конце стpоки dst. Эта функция возвращает пеpвоначальное значение dst.
Си-вариант:

 char *strcat(char *dest, const char *src)
 {
 	char *tmp = dest;
 
 	while (*dest)
 		dest++;
 	while ((*dest++ = *src++) != '\0')
 		;
 	return tmp;
 }
 

Инлайн-вариант:


 static inline char * strcat(char * dest,const char * src)
 {
 int d0, d1, d2, d3;
 __asm__ __volatile__(
 	"repne\n\t"
 	"scasb\n\t"
 	"decl %1\n"
 	"1:\tlodsb\n\t"
 	"stosb\n\t"
 	"testb %%al,%%al\n\t"
 	"jne 1b"
 	: "=&S" (d0), "=&D" (d1), "=&a" (d2), "=&c" (d3)
 	: "0" (src), "1" (dest), "2" (0), "3" (0xffffffffu):"memory");
 return dest;
 }
 
Дизасемблированный си-вариант :

 .L5:
 	addl	$1, %edx
 	cmpb	$0, (%edx)
 	jne	.L5
 	.p2align 4,,7
 .L8:
 	movzbl	(%ecx), %eax
 	addl	$1, %ecx
 	movb	%al, (%edx)
 	addl	$1, %edx
 	testb	%al, %al
 	jne	.L8
 
Первый цикл L5 необходим для того,чтобы ноль на конце приемника заменить на первый символ источника. Второй цикл L8 уже клеит строку.
Здесь указатель на источник лежит в ecx , приемник - в edx.

Инлайн-вариант :


 	repne
 	scasb
 	decl %edi
 1:	lodsb
 	stosb
 	testb %al,%al
 	jne 1b
 
1 repne - цикл со счетчиком в cx
2 scasb - сравнивает байт , лежащий в ax , с байтом памяти , адрес которого лежит в di
3 decl %edi - двигаем указатель , пока не дойдем до ноля
4 ну и дальше второй цикл - клеим строку : уже знакомая картина - то , что мы видели в strcpy

int strcmp

int strcmp(const char *a, const char *b);

strcmp сравнивает две строки
Если *a в лексикографическом порядке идет после *b, то strcmp возвращает число, большее нуля. Если две строки совпадают, то strcmp возвращает ноль. Если *a в лексикографическом порядке идет пеpед *b, то strcmp возвращает число, меньшее нуля.

Си-вариант:


 int strcmp(const char *cs, const char *ct)
 {
 	signed char __res;
 
 	while (1) {
 		if ((__res = *cs - *ct++) != 0 || !*cs++)
 			break;
 	}
 	return __res;
 }
 
Инлайн-вариант:

 static inline int strcmp(const char * cs,const char * ct)
 {
 int d0, d1;
 register int __res;
 __asm__ __volatile__(
 	"1:\tlodsb\n\t"
 	"scasb\n\t"
 	"jne 2f\n\t"
 	"testb %%al,%%al\n\t"
 	"jne 1b\n\t"
 	"xorl %%eax,%%eax\n\t"
 	"jmp 3f\n"
 	"2:\tsbbl %%eax,%%eax\n\t"
 	"orb $1,%%al\n"
 	"3:"
 	:"=a" (__res), "=&S" (d0), "=&D" (d1)
 	:"1" (cs),"2" (ct)
 	:"memory");
 return __res;
 

char * strchr

char * strchr(const char *string, int c);

Функция ищет знак в строке

Эта функция находит первое появление c (преобразованного в char) в строке, указанной string (включая завершающий знак NULL). Возвращается yказатель на обнаруженный знак, или NULL-yказатель, если c не встречается в строке.

Си-вариант :


 char *strchr(const char *s, int c)
 {
 	for (; *s != (char)c; ++s)
 		if (*s == '\0')
 			return NULL;
 	return (char *)s;
 }
 
Инлайн-вариант:

 static inline char * strchr(const char * s, int c)
 {
 int d0;
 register char * __res;
 __asm__ __volatile__(
 	"movb %%al,%%ah\n"
 	"1:\tlodsb\n\t"
 	"cmpb %%ah,%%al\n\t"
 	"je 2f\n\t"
 	"testb %%al,%%al\n\t"
 	"jne 1b\n\t"
 	"movl $1,%1\n"
 	"2:\tmovl %1,%0\n\t"
 	"decl %0"
 	:"=a" (__res), "=&S" (d0)
 	:"1" (s),"0" (c)
 	:"memory");
 return __res;
 }
 

size_t strlen

size_t strlen(const char *str);

Функция strlen считает длину строки знаков, начинающейся в *str, подсчитывая знаки вплоть до достижения знака NULL. strlen возвращает число знаков.

Си-вариант:


 size_t strlen(const char *s)
 {
 	const char *sc;
 
 	for (sc = s; *sc != '\0'; ++sc)
 		/* nothing */;
 	return sc - s;
 }
 
Инлайн-вариант:

 static inline size_t strlen(const char * s)
 {
 int d0;
 register int __res;
 __asm__ __volatile__(
 	"repne\n\t"
 	"scasb\n\t"
 	"notl %0\n\t"
 	"decl %0"
 	:"=c" (__res), "=&D" (d0)
 	:"1" (s),"a" (0), "0" (0xffffffffu)
 	:"memory");
 return __res;
 }
 

void * memcpy

void* memcpy(void *out, const void *in, size_t n);

Эта функция копирует n байт из области памяти, начинающейся с in, в область памяти, начинающейся с out. Если эти области перекрываются, то результат не определен. memcpy возвращает указатель на первый байт области, начинающейся с out.

Си-вариант:


 void *memcpy(void *dest, const void *src, size_t count)
 {
 	char *tmp = dest;
 	char *s = src;
 
 	while (count--)
 		*tmp++ = *s++;
 	return dest;
 }
 
Инлайн-вариант:

 static __always_inline void * __memcpy(void * to, const void * from, size_t n)
 {
 int d0, d1, d2;
 __asm__ __volatile__(
 	"rep ; movsl\n\t"
 	"movl %4,%%ecx\n\t"
 	"andl $3,%%ecx\n\t"
 #if 1	/* want to pay 2 byte penalty for a chance to skip microcoded rep? */
 	"jz 1f\n\t"
 #endif
 	"rep ; movsb\n\t"
 	"1:"
 	: "=&c" (d0), "=&D" (d1), "=&S" (d2)
 	: "0" (n/4), "g" (n), "1" ((long) to), "2" ((long) from)
 	: "memory");
 return (to);
 }
 
Оставьте свой комментарий !

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

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

2007-10-02 10:08:59