Секонд-хендс (Хакерское abandonware)

[Хакер]

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

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

Принцип, который заложен в алогоритм, оптимален, т.е. быстрее уже некуда. Сам же код — не очень, т.е. есть куда оптимизировать (если кого-то нынящняя скорость не устроит, могу поправить исходники и кинуть исправленную библу).

А, ну ещё библиотека умеет делать CopyMemory при помощи MMX (копируя 8 байтов за итерацию).

Кого заинтересовало, кому надо — отдам даром.

[tyomitch]

А можно огласить принцип, который заложен в алогоритм?

[Хакер]

Долго и не интересно

[tyomitch]

Было б неинтересно, я бы не спрашивал

[Хакер]

Ну тебе интересно найти какой-нибудь ещё принцип, который уделает мой по скорости, и таким образом поставить под сомнение высказывание:

Принцип, который заложен в алогоритм, оптимален, т.е. быстрее уже некуда.

Я ведь угадал?

[tyomitch]

Верно.
Но не ради осмеяния использованного алгоритма, а ради плодотворной дискуссии.

[Хакер]

Ладно.


О терминах:

Active-Range — диапазон допустимых символов в слове.
LFT — Length-Filtering Table (частный случай JAT).
JAT — Jump Adresses Table.

При финализации библиотеки (все опции выставили, вызвали функцию Finalize) в памяти создаётся базовая, самая главная и первичная таблица — LFT.

Функция [GetWordID] делает элементарное:
Берёт длину слова. Умножает её на 4. Прибавляет результат к указателю LFT. И делает jmp по полученному адресу.

Изначально, когда не добавлено ещё ни одного слова, все ячейки LFT содержат указатели на одно и то же — на терминаторы.

Терминатором называется некий кусочек кода, примерно такого содержания:

xor eax, eax
retn ???

Поэтому, если, не добавив предварительно никаких слов, вызвать [GetWordID] с каким-нибудь словом, будет сделан jump прямо на терминатор, т.е. будет возвращён 0, что означает, что слово не распознано.

При добавлении "в систему" нового слова для его обработки строится дерево. Я называю его деревом маршрутизации. Посколько в данном механизме слово является не более чем маршрутом, по которому пройдётся процессор, выполняя код роутеров.

Роутер (в рамках данной библиотеки), это код, который берёт текущий символ слова, умножает его код на 4, прибавляет к адресу ассоциированной с роутером JAT и делает по полученному адресу jmp.

Частично дерево уже может быть построено, поэтому происходит маршрутизация (только в данном случае обход дерева осуществляет не сам процессор, выполняя код роутеров и производя джампы, а код библиотеки, изучая JAT-ы), определяется то место слова, на котором дерево обрывается и оставшаяся часть дерева достраивается. Листками дерева (узлами без потомков) являются финализаторы — кусочки кода, отличающиеся от терминаторов только тем, что не обнуляют eax, а записывают в него идентификатор слова.

Для примера представим, что алфавит у нас 5-буквенный, а слова могут быть длиной от 1 до 4 букв.

Слова следующие:

Код: Выделить всё

A — 1
B — 2
E — 3
BAA — 4
BAB — 5
BAE — 6
CEC — 7
CED — 8
ABAD — 10
ABAE — 11
ABBA — 12

После добавления всех этих слов дерево будет выглядеть так:



Получается, что для того, чтобы распознать слово длиной L символов должно выполниться 4+6L инструкций процессора (в предлагаемой библе несколько больше). Что очень мало для такой задачи, а значит код будет выполняться очень быстро. Кроме того, ты данные из памяти читают блоками (ты сам говорил) и кешируются.

В предлагаемой библе всё монолитно. А так, я отсоединил механизм создания самого графа маршрутизации (теперь он может быть сколько угодно зацикленным, содержать JAT-ы любого размера, несколько ребер-переходов может вести к одному роутеру, а в качестве роутера может быть произвольный код) и оформил его в виде отдельной библы. Задача распознования слова построена над этой библой. Кроме того, на этой библе я уже сделал несколько парсеров, а также упомянутый ранее дизассемблер.

[Antonariy]

Схема похожа на проснувшегося Ктулху.

[SLIM]

Мне было бы интересно. Не думаю что сразу с лету разберусь во всем этом. Но обучения ради...

[pronto]

А сколько памяти займут все таблицы, ну, например, для 10^6 слов, если алфавит из 33-х букв?

[Хакер]

Зависит от слов.

В моей задаче слов было 150-200 и скорость была превыше всего.

[pronto]

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

[MIT]

Я мало что понял из вышеследующего развернутого описания (может поздно просто - устал), но в качастве учебного пособия/материала думаю следует ознакомится. Тем более, поставленная задача весьма распространена, и если изложенный сособ действительно является самым быстрым (а поводов к сомнению лично у меня нет), то думаю что данная работа может пригодится и практически.
Хакер, и мне, и мне тоже скинь! Буду категорически благодарен!

[Хакер]

Держите.

KRM-Test.rar

(33.01 Кб) Скачиваний: 208

Что в архиве:
В архиве проект, и его откомпилированная (снабженная манифестом) версия.
Программа предназначена для тестирования библы и нахождения в ней багов. Просматривая код проекта, можно понять, как работать с библой.

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

Для работы же с самой библиотекой — эти функции объявлять не надо. Всё что нужно — уже объявлено в TLB, которая подключена к проекту.

Хинт-1: Распознователь нечувствителен к регистру. Word, wOrd и WoRD — одно и то же для него. Кому надо case-sensative-ность, пишите, расскажу как сделать.

Хинт-2: Active-Range меняется прокруткой колёсика, с фокусом, установленном на нужном текст-боксе.

Хинт-3: Размер LFT необязательно устанавливать таким, чтобы он был гарантировано больше длины максимально длинного слова. Если слово будет иметь длину больше, чем размер LFT, то последняя будет расширена до нужных размеров.

Просто надо учитывать, что расширение LFT — процесс небыстрый, поэтому если изначально выставить маленький размер LFT, а потом добавлять длинные слова, то она будет вынуждена постоянно расширяться.

З.Ы. Если появятся баги, пинайте keks-n'а — он проводил тестирование, и заверил меня, что багов нет.

[pronto]

Еще не смотрел, но уже премного благодарен!

Add: Студия ругается на отсутствие frmJATViewer.frm!

[MIT]

Хакер, категорически благодарен!