Участвуя в разработке практически любого современного проекта для русскоязычной аудитории Вы так или иначе столкнетесь с тем, что весь мир старается перейти на универсальную кодировку символов 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 и другие функции, для которых функции из стандартной библиотеки могут дать неверные результаты при работе с символами различного размера в байтах.