Шаг 21 - Кодировка UTF-8 для русского алфавита, верхний toupper и нижний tolower регистр

Участвуя в разработке практически любого современного проекта для русскоязычной аудитории Вы так или иначе столкнетесь с тем, что весь мир старается перейти на универсальную кодировку символов UTF-8. Русскоязычные кодировки такие как koi8-r, cp-1251, cp-866 и iso-8859-5, которые раньше широко применялись в операционных системах Unix, Windows, DOS практически выходят из обихода.

Если Вы разрабатываете в PHP, JavaScript, MySQL, Python и других современных языках Вы наверняка не будете испытывать проблем с кодировками при работе со строками и их сравнении и сортировке. В библиотеке glibc с этим помоему есть некоторые проблемы. Мне не хотелось разбираться с возможностями locale, библиотеками преобразования кодировок типа iconv (http) и ICU (http) и прочими вещами, так как на данный момент мне требовалось просто получить текст в верхнем или нижнем регистре для операций с ним, например вычислении хеша или поиске слова в строке.

Ничего готового я не смог найти, поэтому решил написать несколько функций сам.

Для начала, кодировка UTF-8 кодирует огромное количество сиволов, которые можно найти в мире, для этого применяется от 1 до 4 байтов на один символ. Часть символов до 127, полностью совпадает с кодировкой ASCII, поэтому кодировка английского текста в UTF-8 не испытывает никаких проблем в различных функциях работающих со строками и символами.

Для начала работы я не знал кодировку русских символов и мне надо было получить эти коды в программе. Самым простым способом было написать следующую программу в любом редакторе, поддерживающем сохранение в кодировке utf-8:

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

struct letter_utf8 {
	unsigned char *upper;
	unsigned char *lower;
} ru_letters[] = {
{"А","а"},{"Б","б"},{"В","в"},{"Г","г"},{"Д","д"},
{"Е","е"},{"Ё","ё"},{"Ж","ж"},{"З","з"},{"И","и"},
{"Й","й"},{"К","к"},{"Л","л"},{"М","м"},{"Н","н"},
{"О","о"},{"П","п"},{"Р","р"},{"С","с"},{"Т","т"},
{"У","у"},{"Ф","ф"},{"Х","х"},{"Ц","ц"},{"Ч","ч"},
{"Ш","ш"},{"Щ","щ"},{"Ъ","ъ"},{"Ы","ы"},{"Ь","ь"},
{"Э","э"},{"Ю","ю"},{"Я","я"},{NULL,NULL}
};

int main() {
	int i, k;
	size_t l, c;

	i = 0;
	while (ru_letters[i].upper != NULL) {
		l = strlen(ru_letters[i].upper);
		printf("%02d = %s(%ld)", i+1, ru_letters[i].upper, l);
		// hex
		printf(" hex[");
		for (k = 0; k < l; k++) printf("%s0x%" PRIx8, k>0? " ":"", ru_letters[i].upper[k]);
		printf("]");

		// dec
		printf(" dec[");
		for (k = 0; k < l; k++) printf("%s%" PRIu8,  k>0? " ":"", ru_letters[i].upper[k]);
		printf("]");

		printf(" - ");
		l = strlen(ru_letters[i].lower);
		printf("%s(%ld)",ru_letters[i].lower, l);

		// hex
		printf(" hex[");
		for (k = 0; k < l; k++) printf("%s0x%" PRIx8, k>0? " ":"", ru_letters[i].lower[k]);
		printf("]");

		// dec
		printf(" dec[");
		for (k = 0; k < l; k++) printf("%s%" PRIu8, k>0? " ":"", ru_letters[i].lower[k]);
		printf("]");

		printf("\n");
		i++;
	}
}

После запуска программы получаем следующий вывод:

01 = А(2) hex[0xd0 0x90] dec[208 144] - а(2) hex[0xd0 0xb0] dec[208 176]
02 = Б(2) hex[0xd0 0x91] dec[208 145] - б(2) hex[0xd0 0xb1] dec[208 177]
03 = В(2) hex[0xd0 0x92] dec[208 146] - в(2) hex[0xd0 0xb2] dec[208 178]
04 = Г(2) hex[0xd0 0x93] dec[208 147] - г(2) hex[0xd0 0xb3] dec[208 179]
05 = Д(2) hex[0xd0 0x94] dec[208 148] - д(2) hex[0xd0 0xb4] dec[208 180]
06 = Е(2) hex[0xd0 0x95] dec[208 149] - е(2) hex[0xd0 0xb5] dec[208 181]
07 = Ё(2) hex[0xd0 0x81] dec[208 129] - ё(2) hex[0xd1 0x91] dec[209 145]
08 = Ж(2) hex[0xd0 0x96] dec[208 150] - ж(2) hex[0xd0 0xb6] dec[208 182]
09 = З(2) hex[0xd0 0x97] dec[208 151] - з(2) hex[0xd0 0xb7] dec[208 183]
10 = И(2) hex[0xd0 0x98] dec[208 152] - и(2) hex[0xd0 0xb8] dec[208 184]
11 = Й(2) hex[0xd0 0x99] dec[208 153] - й(2) hex[0xd0 0xb9] dec[208 185]
12 = К(2) hex[0xd0 0x9a] dec[208 154] - к(2) hex[0xd0 0xba] dec[208 186]
13 = Л(2) hex[0xd0 0x9b] dec[208 155] - л(2) hex[0xd0 0xbb] dec[208 187]
14 = М(2) hex[0xd0 0x9c] dec[208 156] - м(2) hex[0xd0 0xbc] dec[208 188]
15 = Н(2) hex[0xd0 0x9d] dec[208 157] - н(2) hex[0xd0 0xbd] dec[208 189]
16 = О(2) hex[0xd0 0x9e] dec[208 158] - о(2) hex[0xd0 0xbe] dec[208 190]
17 = П(2) hex[0xd0 0x9f] dec[208 159] - п(2) hex[0xd0 0xbf] dec[208 191]
18 = Р(2) hex[0xd0 0xa0] dec[208 160] - р(2) hex[0xd1 0x80] dec[209 128]
19 = С(2) hex[0xd0 0xa1] dec[208 161] - с(2) hex[0xd1 0x81] dec[209 129]
20 = Т(2) hex[0xd0 0xa2] dec[208 162] - т(2) hex[0xd1 0x82] dec[209 130]
21 = У(2) hex[0xd0 0xa3] dec[208 163] - у(2) hex[0xd1 0x83] dec[209 131]
22 = Ф(2) hex[0xd0 0xa4] dec[208 164] - ф(2) hex[0xd1 0x84] dec[209 132]
23 = Х(2) hex[0xd0 0xa5] dec[208 165] - х(2) hex[0xd1 0x85] dec[209 133]
24 = Ц(2) hex[0xd0 0xa6] dec[208 166] - ц(2) hex[0xd1 0x86] dec[209 134]
25 = Ч(2) hex[0xd0 0xa7] dec[208 167] - ч(2) hex[0xd1 0x87] dec[209 135]
26 = Ш(2) hex[0xd0 0xa8] dec[208 168] - ш(2) hex[0xd1 0x88] dec[209 136]
27 = Щ(2) hex[0xd0 0xa9] dec[208 169] - щ(2) hex[0xd1 0x89] dec[209 137]
28 = Ъ(2) hex[0xd0 0xaa] dec[208 170] - ъ(2) hex[0xd1 0x8a] dec[209 138]
29 = Ы(2) hex[0xd0 0xab] dec[208 171] - ы(2) hex[0xd1 0x8b] dec[209 139]
30 = Ь(2) hex[0xd0 0xac] dec[208 172] - ь(2) hex[0xd1 0x8c] dec[209 140]
31 = Э(2) hex[0xd0 0xad] dec[208 173] - э(2) hex[0xd1 0x8d] dec[209 141]
32 = Ю(2) hex[0xd0 0xae] dec[208 174] - ю(2) hex[0xd1 0x8e] dec[209 142]
33 = Я(2) hex[0xd0 0xaf] dec[208 175] - я(2) hex[0xd1 0x8f] dec[209 143]

И тут можно заметить интересные закономерности. Так как русский алфавит состоит из 33 букв, то для удобства приведения к ближайщей степени двойки 32 одну лишнюю букву убрали в сторону, конечно же по частоте использования это оказалась буква Ё. Вы можете увидеть, что ее код выбивается из последовательности. Тут можно заметить, что коды русских букв все двухбайтовые, первым из которых является 0xd0 или 0xd1. Затем второй байт выбирает большой или малый регистр символов, последовательность верхнего регистра символов идет от 0xd0 0x90 до 0xd0 0xaf, а малый регистр занимает два участка по 16 символов как видно 0xd0 0xb0 до 0xd0 0xbf и 0xd1 0x80 до 0xd1 0x80. Буква Ё занимает два кода отдельно от этих последовательностей, большая 0xd0 0x81 и малая 0xd1 0x91.

Теперь основываясь на этих кодах напишем функции преобразования строки в верхний и нижний регистр. Общая идея в том, что надо получить первый байт и если он из подходящих нам, то анализировать второй следующий за ним.

void ru_utf8_tolower(char *str) {
	if (!str) return;
	unsigned char *a,*b;
	a = (unsigned char *) str;
	while (*a != 0) {
		if ((*a >= 0x41) && (*a <= 0x5a)) { // ENG
			*a = 0x61 + (*a - 0x41);
		} else if (*a == 0xd0) { // RUS
			b = a++;
			if (*a == 0) break;
			if ((*a >= 0x90) && (*a <= 0x9f)) {
				*a = 0xb0 + (*a - 0x90);
			} else if ((*a >= 0xa0) && (*a <= 0xaf)) {
				*a = 0x80 + (*a - 0xa0);
				*b = 0xd1;
			} else if (*a == 0x81) { // letter e:
				*a = 0x91;
				*b = 0xd1;
			} else a--;
		}
		a++;
	}
} // ru_utf8_tolower

void ru_utf8_toupper(char *str) {
	if (!str) return;
	unsigned char *a,*b;
	a = (unsigned char *) str;
	while (*a != 0) {
		if ((*a >= 0x61) && (*a <= 0x7a)) { // ENG
			*a = 0x41 + (*a - 0x61);
		} else if (*a == 0xd0) { // RUS
			b = a++;
			if (*a == 0) break;
			if ((*a >= 0xb0) && (*a <= 0xbf)) {
				*a = 0x90 + (*a - 0xb0);
			} else a--;
		} else if (*a == 0xd1) {
			b = a++;
			if (*a == 0) break;
			if ((*a >= 0x80) && (*a <= 0x8f)) {
				*a = 0xa0 + (*a - 0x80);
				*b = 0xd0;
			} else if (*a == 0x91) { // letter e:
				*a = 0x81;
				*b = 0xd0;
			} else a--;
		}
		a++;
	} // while
} // ru_utf8_toupper

После написания данных функций я решил измерить скорость их работы и возможно найти какие-то оптимизации. Для этого подключил файл sys/time.h и написал несколько макросов для измерения времени работы, добавьте этот код в начало программы:

#include <sys/time.h>

struct timeval start_time, end_time;
char double_number[100];
double start_double, end_double;

#define TIMER_START() gettimeofday(&start_time, NULL);
#define TIMER_END()   gettimeofday(&end_time, NULL);
#define TIMER_OUT(a) \
	sprintf(double_number, "%ld.%ld",start_time.tv_sec, start_time.tv_usec);\
	sscanf(double_number,"%lf", &start_double);\
	sprintf(double_number, "%ld.%ld",end_time.tv_sec, end_time.tv_usec);\
	sscanf(double_number,"%lf", &end_double);\
	printf("%s %ld.%ld - %ld.%ld = %f\n", a, end_time.tv_sec, end_time.tv_usec,\
		start_time.tv_sec, start_time.tv_usec, end_double - start_double);

После этого определим несколько буферов и выполним несколько тестов производительности. В следующем коде будем копировать строку в буфер и преобразовывать регистр. Тут важно не забывать, что размер буфера должен быть как минимум в два раза больше, например строка с алфавитом на экране занимает 33 символа, в то время как в памяти она занимает 66 байт + 1 на конец строки.

	c = 50000000; // number of operation

	const char upper_str1[] = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ";
	const char lower_str1[] = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя";
	char buffer_str[100];

	buffer_str[0]=0;
	printf("upper_str1 [%s]\n", upper_str1);
	printf("lower_str1 [%s]\n", lower_str1);
	printf("buffer_str [%s]\n", buffer_str);


	printf("\nctrcpy test:\n");
	TIMER_START();
	for (l = 0; l < c; l++) {
		strcpy(buffer_str, upper_str1);
	}
	TIMER_END();
	TIMER_OUT("strcpy");

	printf("\ntolower test:\n");
	TIMER_START();
	for (l = 0; l < c; l++) {
		strcpy(buffer_str, upper_str1);
		ru_utf8_tolower(buffer_str);
	}
	TIMER_END();
	TIMER_OUT("tolower");

	printf("\ntoupper test:\n");
	TIMER_START();
	for (l = 0; l < c; l++) {
		strcpy(buffer_str, lower_str1);
		ru_utf8_toupper(buffer_str);
	}
	TIMER_END();
	TIMER_OUT("toupper");

Вот вам для примера несколько выводов этой программ:

upper_str1 [АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ]
lower_str1 [абвгдеёжзийклмнопрстуфхцчшщъыьэюя]
buffer_str []

ctrcpy test:
strcpy 1604489797.563336 - 1604489796.901257 = 0.662079

tolower test:
tolower 1604489807.606725 - 1604489797.563353 = 10.043372

toupper test:
toupper 1604489820.951395 - 1604489807.606737 = 13.344658

И еще один:

ctrcpy test:
strcpy 1604489925.376859 - 1604489924.714747 = 0.662112

tolower test:
tolower 1604489935.106099 - 1604489925.376875 = 9.729224

toupper test:
toupper 1604489948.592920 - 1604489935.106109 = 13.486811

Можно сделать вывод, что преобразование в верхний регистр занимает больше времени, но это и видно по коду, так как символы в нижнем регистре имеют различный первый байт, то сравнений требуется делать больше.

Задумываясь над оптимизациями кода можно вспомнить, что операции работы с памятью происходят более длительное время, из этого родилась первая оптимизация - введение переменной для операций сравнения и вычисления:

void ru_utf8_tolower_o1(char *str) {
	if (!str) return;
	unsigned char *a,*b;
	unsigned char c;
	a = (unsigned char *) str;
	c = *a;
	while (c != 0) {
		if ((c >= 0x41) && (c <= 0x5a)) { // ENG
				*a = 0x61 + (c - 0x41);
		} else if (c == 0xd0) { // RUS
			b = a++; c = *a;
			if (c == 0) break;
			if ((c >= 0x90) && (c <= 0x9f)) {
				*a = 0xb0 + (c - 0x90);
			} else if ((c >= 0xa0) && (c <= 0xaf)) {
				*a = 0x80 + (c - 0xa0);
				*b = 0xd1;
			} else if (c == 0x81) { // letter e:
				*a = 0x91;
				*b = 0xd1;
			} else a--;
		}
		a++;
		c = *a;
	}
} // ru_utf8_tolower_o1

Вот примеры времени выполнения в цикле. Хорошо видно, что незначительное ускорее есть:

tolower = 19.496820 sec
tolower_o1 = 18.428909 sec
tolower = 19.213790 sec
tolower_o1 = 18.149849 sec
tolower = 19.572263 sec
tolower_o1 = 18.146423 sec
tolower = 19.508638 sec
tolower_o1 = 18.723864 sec
tolower = 18.931112 sec
tolower_o1 = 18.148161 sec

Я попробовал двинуться дальше и поочередно заставил компилятор использовать для переменных регистры процессора, с помощью ключевого слова register. Сначала переменную register unsigned char c, а затем и register unsigned char *a, *b. И это стало фееричным ускорением:

tolower = 22.263686 sec
tolower_o1 = 18.418550 sec
tolower_o2 = 13.898395 sec
tolower_o3 = 10.055407 sec
tolower = 22.405867 sec
tolower_o1 = 17.924197 sec
tolower_o2 = 14.376714 sec
tolower_o3 = 10.051730 sec
tolower = 22.384672 sec
tolower_o1 = 17.909208 sec
tolower_o2 = 14.379175 sec
tolower_o3 = 10.054474 sec
tolower = 22.416999 sec
tolower_o1 = 17.955479 sec
tolower_o2 = 14.378212 sec
tolower_o3 = 10.053261 sec
tolower = 22.376226 sec
tolower_o1 = 18.528445 sec
tolower_o2 = 13.765601 sec
tolower_o3 = 10.056075 sec

Удивительно как можно ускорить работу алгоритма, указав компилятору на то, чтобы он держал наиболее часто используемые данные в регистрах. Итого имеем результирующий код, работающий быстрее первоначального в два раза:

void ru_utf8_tolower_o3(char *str) {
	if (!str) return;
	register unsigned char *a,*b;
	register unsigned char c;
	a = (unsigned char *) str;
	c = *a;
	while (c != 0) {
		if ((c >= 0x41) && (c <= 0x5a)) { // ENG
			*a = 0x61 + (c - 0x41);
		} else if (c == 0xd0) { // RUS
			b = a++; c = *a;
			if (c == 0) break;
			if ((c >= 0x90) && (c <= 0x9f)) {
				*a = 0xb0 + (c - 0x90);
			} else if ((c >= 0xa0) && (c <= 0xaf)) {
				*a = 0x80 + (c - 0xa0);
				*b = 0xd1;
			} else if (c == 0x81) { // letter e:
				*a = 0x91;
				*b = 0xd1;
			} else a--;
		}
		a++;
		c = *a;
	}
} // ru_utf8_tolower_o3

Применим такие же оптимизации для преобразования в верхний регистр. И получаем следующие значения ускорения:

strcpy = 1.318308 sec
toupper = 21.633709 sec
toupper_o3 = 10.762970 sec
toupper = 21.108497 sec
toupper_o3 = 10.108307 sec
toupper = 21.570133 sec
toupper_o3 = 10.107059 sec
toupper = 21.946732 sec
toupper_o3 = 10.108061 sec
toupper = 21.723422 sec
toupper_o3 = 10.109840 sec

Как и следовало ожидать в два раза, вот код этой функции:

void ru_utf8_toupper_o3(char *str) {
	if (!str) return;
	register unsigned char *a,*b;
	register unsigned char c;
	a = (unsigned char *) str;
	c = *a;
	while (c != 0) {
		if ((c >= 0x61) && (c <= 0x7a)) { // ENG
			*a = 0x41 + (c - 0x61);
		} else if (c == 0xd0) { // RUS
			b = a++; c = *a;
			if (c == 0) break;
			if ((c >= 0xb0) && (c <= 0xbf)) {
				*a = 0x90 + (c - 0xb0);
			} else a--;
		} else if (c == 0xd1) {
			b = a++; c = *a;
			if (c == 0) break;
			if ((c >= 0x80) && (c <= 0x8f)) {
				*a = 0xa0 + (c - 0x80);
				*b = 0xd0;
			} else if (c == 0x91) { // letter e:
				*a = 0x81;
				*b = 0xd0;
			} else a--;
		}
		a++;
		c = *a;
	} // while
} // ru_utf8_toupper_o3

При обработке очень больших объемов данных в несколько терабайт, когда обработка может занимать сутки, любое даже небольшое ускорение работы кода может привести к большой экономии времени, железа и электричества. Для больших высоконагруженных проектов такие ускорения всегда выливаются в большую экономию средств.

Данные фукнции портят исходные данные, возможно это не всем подходит в работе, но основываясь на коде данных фукнций Вы самостоятельно сможете реализовать преобразование строки с копированием в новый буфер.

Конечно же это не все требуемые фукнции для полноценной работы с кодировкой utf8, в будущем попробуем разобраться со сравнением срок strcmp, strcasecmp и копированием частей строк типа strncpy, поиском символа strchr и другие функции, для которых функции из стандартной библиотеки могут дать неверные результаты при работе с символами различного размера в байтах.


Предыдущий Шаг | Оглавление
Автор Кузин Андрей.