Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
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