Забытые секреты кодинга

Как же приятно иногда бывает открывать
старые папки! Нет, не каталоги на жестком
диске, а картонные такие папки с
тесемочками, в которых хранятся у меня
старые компьютерные журналы. Читаешь, и
начинаешь вспоминать, что слово «хакер»
изначально означало не подростка-взломщика,
образ которого так очернила современная
пресса, а вполне серьезного взрослого
дядьку, правда, слегка помешанного на
нестандартных трюках и методах оптимизации.
Не могу удержаться от того, чтобы привести
один непрограммистский трюк. На первом
рисунке ты видишь по два ярлыка на разные
версии Microsoft Word и Microsoft Excel. Но ведь два файла
с одинаковыми именами не могут находиться в
одной папке! На другом рисунке — папки с
документацией, ясное дело, отсортированы по
алфавиту, но «Linux» почему-то стоит раньше «DOS»
и «Windows».

В чем здесь секрет? А в том, что в именах
файлов некоторые английские буквы заменены
русскими (например, латинское a на русское а
в словах «Platform - DOS» и «Platform - Windows»). В
результате изменяется порядок сортировки и
появляется возможность добавить еще один
файл, имя которого на первый взгляд ни чем
не отличается от первого.

Когда еще не было ни Norton Commander, ни
юниксовских шеллов, завершающих имя файла
по нажатию Tab, с помощью этого трюка можно
было скрыть файл от любопытных глаз и
шаловливых ручек. Команда ls или dir в DOS
показывала имя файла, но определить, какие
буквы в нем русские, было невозможно.
Поэтому нельзя было запустить другую
команду (просмотра, копирования или
удаления) с этим файлом.

Иногда я жалею, что не родился лет этак на
двадцать раньше, и пропустил романтические
времена программируемых
микрокалькуляторов и ЭВМ, занимавших
полкомнаты. Процессоры тогда были
медленными, а память — крошечной, и
ассемблерная программа не умещалась в нее
без длительной борьбы за оптимальность
кода. Сейчас программисты отупели до сборки
тяжеловесных, неуклюжих программ из
готовых компонентов, а хакеры занялись
взломом этих программных монстров. И то, и
другое, имхо, до невозможности глупо, ибо
железо и средства разработки меняются
настолько быстро, что создать сейчас
серьезную систему, которая потребует 5–7
лет работы, практически нереально. Поэтому
большинство кодеров занято довольно
бестолковой текущей работой, которая к тому
же не приносит никакой радости . Никаких
красивых миниатюрных решений — только
паттерны, применение давно изученных
подходов и алгоритмов.

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

Строки как числа

Вот простейший кусок кода — мы получаем
путь к файлу из текстового поля и должны
приписать к нему имя файла hak:

char s[MAX_PATH];
GetDlgItemText(hDlg, ID_PATH, s, sizeof(s));
strcat(s, "hak"); // Копируем
имя файла в конец строки

Казалось бы, чего уж проще? Но если ты
залезешь в дизассемблер, то увидишь весьма
и весьма сложный код функции strcat(). Сначала
ищется конец обеих строк инструкциями repne
scasb, затем выполняется копирование
инструкцией rep movsb. И это для четырех-то байт!
Ведь можно написать просто:

mov dword ptr [EDI], 'kah' ; EDI показывает на конец
строки

Буквы записаны в обратном порядке из-за
того, что процессоры x86 переворачивают
байты в слове (так называемый формат little-endian).
Если бы мы работали под Macintosh, нужно бы было
написать просто 'hak'. Но на PC байты придется
перевернуть, что на языке С будет выглядеть
так:

char s[MAX_PATH], *p;
p = s + GetDlgItemText(hDlg, ID_PATH, s, sizeof(s));
// Теперь в p лежит
указатель на конец строки
*(long*)p = 'h' | 'a' << 8 | 'k' << 16;

Буква k сдвигается в старший байт, a — в
средний, а h остается во младшем байте. В
самом старшем байте будет стоять ноль, то
есть признак конца строки в C.

При копирования в память процессор
переставит байты местами, и в строке они
будут следовать друг за другом в обычном
порядке ("hak", а не "kah"). Чтобы не
писать каждый раз этот код, сделаем два
простых макроса, для четырехбайтного типа
long и для двухбайтного short:

// Преобразовать
4 символа в long
#define toShort(a,b) ((unsigned char)a | (unsigned char)b << 8)
// Преобразовать 2
символа в short
#define toLong(a,b,c,d) ((unsigned char)a | (unsigned char)b << 8 | \
(unsigned char)c << 16 | (unsigned char)d << 24)

// Пример:
*(long*)p = toLong('h', 'a', 'k', '\0');

Вместо '\0' можно написать обычный ноль.
Преобразования в беззнаковый тип
понадобились потому, что без них русские
буквы (с кодами во второй половине ASCII-таблицы)
будут сдвигаться со знаковым расширением, и
в результате получится совсем не то, чего мы
хотели. Еще нужно понять, что все сдвиги и
логические ИЛИ выполняются на этапе
компиляции, посему в ассемблерный код
попадет только одна команда:

mov dword ptr [какой-то-регистр], 'kah'

Если у нас более длинное имя файла,
например, «hacker.txt», нужно будет вызывать
макросы несколько раз:

*(long*)p = toLong('h', 'a', 'c', 'k');
*(long*)(p+4) = toLong('e', 'r', '.', 't');
*(long*)(p+8) = toShort('x', 't');
*(p+10) = '\0';

Но этот код все равно быстрее и короче, чем
strcat(p, "hacker.txt"). Непонятно только, почему
ни один компилятор (по крайней мере, из
известных мне) не может выполнять эту, в
общем-то, рутинную оптимизацию
автоматически. Оптимизируют какие-то редко
используемые двойные условия, какие-то
очень специфические операции с плавающей
запятой, а до такой простой вещи додуматься
не могут!

Точно таким же способом можно ускорить
сравнение строк. Пусть нужно написать
интерпретатор какого-то скриптового языка (скажем,
для автоматизации подбора паролей или атак
на сервер). В языке есть две команды «CRACK» и «FUCK»,
которые начинаются с новой строки, лишние
пробелы и отступы игнорируются. У каждой
команды есть аргументы, какие — нам для
этого примера неважно. Обычно подобные вещи
пишут с помощью функции strcmp():

FILE f; char s[200], arg[200];
if (f = fopen("C:\\script.bas", "r")) { // Если
удалось открыть файл
while( fscanf( f, " %[^ \t] ", s) == 1 ) { // Читаем
команду
if( fscanf(f, "%[^\r\n]", arg) != 1 ) // Читаем
аргумент 
break;
if( strcmp(s, "CRACK") == 0 )
printf("CRACK with %s\n", arg); // Выполняем
команду CRACK
else if( strcmp(s, "FUCK") == 0 )
printf("FUCK with %s\n", arg); // Выполняем
команду FUCK
else
printf("Unrecognized command: %s", s);
}
fclose(f); // Закрываем файл
}

Эта программа не лишена ряда недостатков (в
частности, функция fscanf вызовет
переполнение стека, если длина команды или
аргумента больше 200 байт), но речь сейчас не
об этом. Главное, что можно переписать этот
фрагмент кода, используя макросы toLong, toShort, и
он будет работать гораздо быстрее:

if( toLong('C','R','A','C') == *(long*)s
&&
toShort('K','\0') == *(short*)(s+4))
puts("Нашли команду CRACK");
else if( toLong('F','U','C','K') == *(long*)s && '\0' == *(s+4))
puts("Нашли команду FUCK");

Для дальнейшего ускорения программы
нужно отказаться от fopen/fscanf. Если будем
читать файл функциями Win32 API, то заодно
избавимся от stack-bug. Но тогда придется
ручками писать цикл, пропускающий пробелы и
табуляцию в начале строки — такова плата за
производительность. Ну и конечно, реальный
интерпретатор будет выполнять какие-то
полезные действия, а не просто выводить
строки на экран.

Однотипные интерфейсные элементы

Имеется ряд однотипных элементов, которые
выполняют одно и то же действие, например,
кнопки вставки специальных символов или
меню выбора цвета в html-редакторе. Как
написать программу так, чтобы не пришлось
повторять один и тот же код для всех кнопок?
В Delphi VCL вопрос решается элементарно: один и
тот же обработчик события для всех кнопок, а
в свойстве Tag указываем символ или код цвета.
Но как сделать то же в Win32? Идея такова:
запишем код символа в идентификатор
элемента (control ID). Обычно MSVC++ раздает
идентификаторы произвольно, а мы возьмем да
переделаем их так, как нам удобнее:

// файл
resource.h
#define ID_APPLY 100 // Идентификаторы,
назначенные VC++
#define ID_FILEOPEN 101
// Наши идентификаторы:
#define ID_LAQUO 0x10AB // Открывающая
кавычка
#define ID_RAQUO 0x10BB // Закрывающая
кавычка
#define ID_DEG 0x10B0 // Градус

«Фишка» в том, что AB, BB, B0 — это ASCII-коды
кавычек и градуса в кодировке Windows. А 0x1000
служит признаком того, что перед нами одна
из кнопок, вводящих спецсимвол.

// В
оконной процедуре
case WM_COMMAND:
if( wParam & 0x1000 ) {
int x = toShort(wParam & 0xFF, '\0');
SendMessage(hWndText, EM_REPLACESEL, FALSE, (LPARAM)&x);
}
else if (ID_APPLY == wParam)
// Применяем изменения
break;

Вот и все! В переменную x записывается
строка-число, состоящая из нужного
спецсимвола (его код выделяем по маске 0xFF),
после которой следует признак конца строки.
Сообщение EM_REPLACESEL вставляет спецсимвол в
текущую позицию курсора. Кроме кнопок со
спецсимволами у нас есть кнопка ID_APPLY.
Именно для того, чтобы отличить остальные
кнопки от нее, мы добавляем к их
идентификаторам 0x1000.

Операции с фиксированной точкой

Есть такие интересные уравнения:

x = r cos A?t,
y = r sin B?t, где r = sin t?C

Интересны они не сами по себе (синусы
вообще довольно скучная вещь), а из-за тех
графиков, которые они описывают. При разных
значениях коэффициентов A, B, C получаются
вот такие симпатичные фигуры.

Если у тебя еще что-то сохранилось в
голове от школьных уроков математики, ты
наверняка вспомнил про полярные координаты.
Можно сказать, что это графики функции sin t?C
в искаженных полярных координатах. Сам по
себе график sin(C*t) - это «цветок», у которого t
лепестков. Например, sin(t*9) в полярных
координатах — это цветок с девятью
лепестками.

Но у нас есть еще коэффициенты A и B,
которые искажают, скручивают этот цветочек.
В результате получается то, что нарисовано
выше. Например, фигура (A = 40, B = 49, C = 18),
которую я обычно называю «обручальные
кольца», это хорошенько перекрученный
цветок с 18 лепестками. Коэффициенты A, B, C
находятся подбором. Эксперименты
показывают, что лучше брать взаимно простые
числа (те, которые не делятся друг на друга).
Чем больше коэффициенты, тем больше линий
будет на графике.

Программу, которая рисует эти милые
картинки, ты найдешь здесь.
Если пропустить все подготовительные
операции (инициализацию таймера, выбор
кисти нужного цвета, заливку фона и прочее),
то останется такой код:

double t, a; int r, x, y;
...
t = 0;
do {
r = sin(a + t * C);
x = int(rect.bottom/2 * (r * cos(t * A) + 1));
y = int(rect.bottom/2 * (r * sin(t * B) + 1));
t += 1e-3;
LineTo(hdc2, x, y);
} while(t < pi*2);
a += 1e-2;

Рисовать будем не статическую картинку (это
не интересно), а анимацию. Переменная t
изменяется в цикле от 0 до 2? с каким-то
небольшим шагом, например, 10–3. На каждом
проходе цикла мы вычисляем координаты (x, y)
следующей точки и проводим до нее линию.
Весь цикл рисует один график, одну
неподвижную картинку. Для анимации вводим
параметр a, который при каждом вызове
таймера изменяется на какой-то небольшой
шаг, например, 10–2. Переменную a можно
вставить куда угодно. Если вставим в
выражение для r, график будет извиваться и
перекручиваться. Если попробуем изменять x
или y, фигура на экране будет «переливаться»,
но форма ее останется той же.

rect.bottom — это размер картинки. Функции sin и
cos дают значения от -1 до 1, а мы домножаем их
на rect.bottom, чтобы растянуть рисунок до
нужного размера. Единицу добавляем, чтобы
сместить изображение в центр окна.

Этот код работает неплохо, но довольно
медленно. На очень старых компах он просто
тормозит, а новые довольно сильно загружает.
Duron-800 загрузился на целых 10%. Даже mp3-плеер с
очень прожорливым кодеком mpg123
эксплуатирует всего 5–7% времени моего
процессора. Непорядок. Попробуем
оптимизировать?

Больше всего времени отнимают операции с
плавающей точкой, повторяющиеся вычисления
синусов и косинусов. Между тем нам не нужно
знать точное значение синусов, достаточно
2–3 знаков после запятой, ведь экранные
координаты x, y — это целые числа, а не
дробные. В таких случаях очень помогают
числа с фиксированной запятой.

Чтобы избавиться от дробей, умножим все
числа на какой-то коэффициент, например, на
100. Тогда вместо того, чтобы вычислять,
скажем, 3.14 + 1.3 – 9, компьютер будет считать 314
+ 130 – 900. Для нас разницы никакой, но
процессор работает с целыми числами
намного быстрее. Такой способ и называется
«число с фиксированной точкой» или
фиксированной запятой. В качестве
масштабного коэффициента возьмем 256, потому
что делить на степени двойки гораздо
быстрее, чем на 100 или на 1000. Точность
составит 1 / 256, то есть числа, которые
различаются меньше чем на 1 / 256, будут в
таком представлении одинаковыми. Для
нашего примера этого достаточно.

Если мы хотим перемножить два числа с
фиксированной точкой, нужно перемножить их,
а затем разделить на 256 или на другой
коэффициент. Чтобы умножить число с
фиксированной точкой на обычное целое
число, нужно просто перемножить их. Это
похоже на умножение десятичных дробей в
пятом классе — когда умножаем 1.23 на 3.14,
нужно умножить 123 на 314, а затем перенести
запятую на 4 цифры влево. А если умножаем 1.23
на целое число 9, запятая будет стоять перед
двумя цифрами, как и было в исходном числе
1.23. Осталось придумать, как находить синусы
и косинусы. А мы не будем их считать —
просто возьмем таблицу с синусами углов sin(0),
sin(1/256), sin(2/256), sin(3/256) и так далее до sin (? / 2).
Остальные синусы можно находить по
формулам приведения, вычитая из аргумента
? или ? / 2. Таблицу нам напечатает такая
программа:

for(int i = 0; i <= pi/2; ++i)
{ // Переводим из
фиксированной точки в плавающую, считаем
синус:
double a = sin(double(i) / 256);
// Переводим из
плавающей точки в фиксированную, выводим
результат:
printf("%d, ", int(a * 256));
}

В результате получим длинный массив
возрастающих чисел. Можно сжать его и / или
воспользоваться тем, что до определенного
числа x верно выражение sin(x) = x, хотя большого
смысла в этих извращениях нет. Программа и
так не слишком большая.

int inline sin(int x)
{ x %= 2 * pi;
if(x < pi)
{ if(x - pi/2 > 0) // от pi/2 до pi
return c[x - pi/2]; // по ф-ле
приведения
return s[x]; // от 0 до pi/2 -
просто берем из массива
}
if(x - 3*pi/2 > 0) // от 3/2*pi до
2*pi
return -c[x - 3*pi/2]; // по ф-ле
приведения
return -s[x - pi]; // от pi до 3/2*pi
- по ф-ле приведения
}

Функция sin() всего лишь берет значение
синуса или косинуса из массива (s или c).
Точно также работает функция cos(). Константа
pi объявлена как представление числа ? с
фиксированной точкой. Значения углов
больше 2? уменьшаем, находя остаток от
деления по модулю 2?. Кстати, функция не
работает с отрицательными углами. Для
нашего примера это неважно и ненужно, но,
вообще говоря, нужно вставить еще одно
сравнение:

x %= 2 * pi;
if(x < 0)
x += 2 * pi;
if(x < pi) // и далее по
тексту

И, наконец, основной код:

int r, x, y, t, a; // Все
переменные целые
t = 0;
do {
r = sin(a + t * C);
x = (rect.bottom/2 * ((r * cos(t * A) >> 8) + 0x100)) >> 8;
y = (rect.bottom/2 * ((r * sin(t * B) >> 8) + 0x100)) >> 8;
t++; // Увеличиваем на 1/256
LineTo(hdc2, x, y);
} while(t < pi*2);
a++; // Увеличиваем на 1/256

Находим r с фиксированной точкой, умножаем
на синус или на косинус (про правила
умножения я уже говорил). Прибавляем 0x100, то
есть единицу с фиксированной точкой. Затем
умножаем на обычное целое число rect.bottom/2 и
сдвигаем на 8 разрядов (делим на 256), чтобы
получить целое число для функции LineTo.

Перед тобой далеко не самый совершенный
код. Можно было бы избавиться от сравнений в
функциях sin/cos, разбив цикл на несколько
частей. Можно избежать умножений t * A, t * B,
создав еще парочку массивов со значениями
функций v(t) = cos(t * A) >> 8 и u(t) = sin(t * B) >> 8.
Но главное, что работает эта программа
гораздо быстрее предыдущей. У меня она
загружала процессор всего на 1 процент! Ты
можешь прогнать оба примера на своем
компьютере. Вариант с фиксированной точкой
приведен в файле xakep1.cpp, с плавающей точкой
— xakep1a.cpp.

На сегодня всё. Если понравилось или
наоборот, не понравилось, — пиши, адрес в
начале статьи. Продолжение следует при
условии (if), что (будут отклики). Тогда я
опубликую еще несколько трюков.