Работа с битовыми масками.

← →
Riply © (2008-01-22 16:06) [0]

Здравствуйте !
Допустим, у нас есть две битовые маски.
Нам надо их сравнить и, если они различны, то выкинуть из каждой
те биты, которые есть в другой. Т.е. оставить только "отличающиеся".
У меня вот что получилось:
function DeleteEqualBits(const pBitMap1, pBitMap2: PRTL_BITMAP): DWord; var i: integer; DWordCount, Tmp: DWord; pdw1, pdw2: PULONG; begin Result := 0; DWordCount := min(pBitMap1.SizeOfBitMap, pBitMap2.SizeOfBitMap) div 8; if DWordCount > 0 then begin pdw1 := pBitMap1.Buffer; pdw2 := pBitMap2.Buffer; for i := 0 to Pred(DWordCount) do if pdw1^ <> pdw2^ then begin Tmp := pdw1^ xor pdw2^; pdw1^ := pdw1^ and Tmp; pdw2^ := pdw2^ and Tmp; inc(Result); end; end; end;
Помогите, пожалуйста оптимизировать это безобразие,
если, конечно, оно того заслуживает :)

← →
DVM © (2008-01-22 16:09) [1]

> Riply ©

PRTL_BITMAP у меня нет такого типа - это откуда?

← →
Rouse_ © (2008-01-22 16:12) [2]

Тезка, а тебе не кажется что ты ксоришь только первые 4 байта масок в цикле? :)

← →
homm © (2008-01-22 16:12) [3]

> [0] Riply © (22.01.08 16:06)
> Нам надо их сравнить и, если они различны, то выкинуть из
> каждой те биты, которые есть в другой.

Не понятно, что значит выкинуть? Бит может быть установлен и сброшен.

← →
Семеныч (2008-01-22 16:15) [4]

1. Делаем третью маску: Mask3 := Mask1 xor Mask2
2. Mask1 := Mask1 and Mask3; Mask2 = Mask2 and Mask3

===========

Под xor и and понимаются режимы работы BitBlt.

← →
Riply © (2008-01-22 16:19) [5]

> [1] DVM © (22.01.08 16:09)

> PRTL_BITMAP у меня нет такого типа - это откуда?

RTL_BITMAP = packed record SizeOfBitMap: ULONG; //0 Number of bits in bit map Buffer: PULONG; //4 Pointer to the bit map itself end; PRTL_BITMAP = ^RTL_BITMAP;

> [2] Rouse_ © (22.01.08 16:12)
> Тезка, а тебе не кажется что ты ксоришь только первые 4 байта масок в цикле? :)

:)
Вот к чему приводит спешка. Спасибо. :)
Но вопрос не отпал.

← →
Rouse_ © (2008-01-22 16:33) [6]

> Но вопрос не отпал.

Я даже не вижу что тут можно еще оптимизировать :) Все вроде логично выстроенно...

← →
Sapersky (2008-01-22 17:04) [7]

DWordCount := min(pBitMap1.SizeOfBitMap, pBitMap2.SizeOfBitMap) div 8;

SizeOfBitMap - размер в битах или байтах?
И в том, и другом варианте в DWordCount будет явно не кол-во DWord"ов.
Ещё, если размер в байтах не обязательно кратен DWord, нужно отдельно обработать байты в конце.

← →
Riply © (2008-01-22 17:05) [8]

> [6] Rouse_ © (22.01.08 16:33)
> Я даже не вижу что тут можно еще оптимизировать :) Все вроде логично выстроенно...

Тогда так и оставлю, записав ее в разряд готовых.
Правда, после исправления проверки одного и того же блока,
она стала выглядеть совсем "не эстетично" :)

← →
Riply © (2008-01-22 17:13) [9]

> [7] Sapersky (22.01.08 17:04)
> SizeOfBitMap - размер в битах или байтах?

В битах.

> И в том, и другом варианте в DWordCount будет явно не кол-во DWord"ов.
Точно. Спасибо.

> Ещё, если размер в байтах не обязательно кратен DWord, нужно отдельно обработать байты в конце.
Будет кратен исходя из условий инициализации (они описаны для ф-ии RtlInitializeBitMap)

← →
Riply © (2008-01-22 17:19) [10]

Выложу ка я последний вариант, а то ошибки растут как грибы :)
Может кто еще найдет.
function DeleteEqualBits(const pBitMap1, pBitMap2: PRTL_BITMAP): DWord; var i: integer; DWordCount, Tmp: DWord; pdw1, pdw2: PULONG; begin Result := 0; DWordCount := min(pBitMap1.SizeOfBitMap, pBitMap2.SizeOfBitMap) div (8 * SizeOf(DWord)); if DWordCount > 0 then begin pdw1 := pBitMap1.Buffer; pdw2 := pBitMap2.Buffer; for i := 0 to Pred(DWordCount) do begin if pdw1^ <> pdw2^ then begin Tmp := pdw1^ xor pdw2^; pdw1^ := pdw1^ and Tmp; pdw2^ := pdw2^ and Tmp; inc(Result); end else begin pdw1^ := 0; pdw2^ := 0; end; inc(pdw1); inc(pdw2); end; end; end;

← →
oldman © (2008-01-22 18:23) [11]

> Допустим, у нас есть две битовые маски.
> Нам надо их сравнить и, если они различны, то выкинуть из
> каждой
> те биты, которые есть в другой. Т.е. оставить только "отличающиеся".

И что на выходе???

← →
Sapersky (2008-01-22 19:44) [12]

Riply © (22.01.08 17:19) [10]

Если уж придираться к эстетике - то const в списке параметров лишний, либо const TRTL_BITMAP, либо просто PRTL_BITMAP.
Тип DWordCount лучше сделать Integer, так же как и счётчика (i), тогда можно будет выкинуть начальную проверку на 0.

← →
guav © (2008-01-22 23:14) [13]

А что тут делает ветвление ?
> if pdw1^ <> pdw2^ then

> else
> begin
> pdw1^ := 0;
> pdw2^ := 0;
> end;

разве то что до else не справится с равными значениями ?

> если, конечно, оно того заслуживает :)

Что за задача ?
Я вот тоже не так давно не с того конца подошел к оптимизации, в результате выяснилось, что на самом деле проблема решается применением правильной структуры (http://delphimaster.net/view/4-1198141284/ ).

← →
Riply © (2008-01-23 04:57) [14]

> [12] Sapersky (22.01.08 19:44)
> Если уж придираться к эстетике - то...
"придираться к эстетике" нужно !
Спасибо. :)

> [11] oldman © (22.01.08 18:23)
> И что на выходе???
> [13] guav © (22.01.08 23:14)
> Что за задача ?

Для некого файлового объекта, двумя различными способами,
делается SnapShort дерева его "детей".
Надо сравнить результаты. (Т.е. объект такой-то есть в первом
SnapShort-е и отсутствует во втором. И наоборот.)
Если они одинаковы, то все хорошо, иначе создаем структуру,
содержащую их объеденение.
Предполагается поиск вхождений элементов одной структуры в
другую (любым способом), заменить работой с битовыми масками.
(Их можно создать на этапе сканирования, взяв за основу номер записи в MFT)
После сравнения двух масок, в них остаются только биты соответствующие
номерам записей "лишних" объектов.
Используя их легко создается наше "объеденение" SnapShort-ов.
Первые эксперименты по использованию масок впечатляют.
Они дают выигрыш по времени не в разы, а на порядки.
Плюс к этому они могут и помочь сэкономить память,
которая требуется для привеления SnapShort-ов в вид, "пригодный для сравнения" :)

← →
Zeqfreed © (2008-01-23 07:30) [15]

Позволю себе тоже попридираться к эстетике, если позволите :)

Во-первых, в слове «снапшот» нет буквы р.
А во-вторых, DeleteEqualBits вообще никак не отображает сути функции, потому что «удалить» биты нельзя. На мой взгляд можно обозвать функцию как-нибудь наподобие SnapshotsDifference или DifferentiateSnapshots.

← →
Riply © (2008-01-23 08:10) [16]

> [15] Zeqfreed © (23.01.08 07:30)
> Позволю себе тоже попридираться к эстетике, если позволите :)

Спасибо.

P.S.
Мне кажется, что в результате получится, пусть даже "не рабочая",
но зато очень эстетичная функция :)

← →
guav © (2008-01-23 11:43) [17]

> Надо сравнить результаты. (Т.е. объект такой-то есть в первом
> SnapShort-е и отсутствует во втором. И наоборот.)
> Если они одинаковы, то все хорошо, иначе создаем структуру,
> содержащую их объеденение.

Т.е. надо просто добавлять сразу все объекты в одну сруктуру :) (разумеется, структура д.б. такова, чтобы дупликаты не добавлялись).

> [17] guav © (23.01.08 11:43)
> Т.е. надо просто добавлять сразу все объекты в одну сруктуру :)

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

В первозданном виде первая "струтура" это смесь
FILE_ID_BOTH_DIR_INFORMATION и FILE_STREAM_INFORMATION,
которые заполнялись Nt - функциями с запросом на возвращение
"не единственного" вхождения и записывались в память
последовательно, по мере их поступления.
Добавлять в эту кашу (без преобразования ее в удобоворимый вид)
что-то другое не представляется возможным (или не очень просто).
Совсем другое дело - выдернуть из нее по маске
только нужные нам элементы.
Так мы избавляемся от любых ее преобразований и
поиска в ней элеменов на вхождение (что тоже не просто учитывая ее "несортированность").
Даже эта операция может понадобиться только в том случае,
если в ней окажутся элементы, не найденные вторым способом,
а это нам станет известно из сравнения масок.

> [18] Riply © (23.01.08 13:03)

Я в подобных случаях использовал бы ассоциативные контейнеры. Дело в том, что единиц в bitmape я так понял предполагается не очень много, поэтому памяти потребуется меньше.
Даже если не хочешь смешивать массивы, сами номера я бы помещал не в bitmap а в ассоциативный контейнер.
Если нужна сортировка, то set, иначе вообще hash set.

THashSet отсюда http://sourceforge.net/projects/dclx прикрутить попробуй

> [19] guav © (23.01.08 14:11)
> Я в подобных случаях использовал бы ассоциативные контейнеры.

А кто это такие ?

> Дело в том, что единиц в bitmape я так понял предполагается не очень много,
> поэтому памяти потребуется меньше.

Максимальное количество битов в bitmape заранее
известно: MftValidDataLength div BytesPerFileRecordSegment
(если правильно помню названия полей)

> [21] Riply © (23.01.08 14:24)

> А кто это такие ?

Контейнеры, которые упорядочены не произвольно, а таким образом, чтобы элементы можно было находить по ключу.
У set"ов ключ и есть элемент, у map"ов элемент содержит ключ и значение. У сортированных с помощью дерева элемент ищется за логарифмическое время, и все эелементы идут в порядке, определяемом стравнением ключей. У hash контейнеров - за константное время, но элементы идут не в порядке, определяемом стравнением ключей.

> Максимальное количество битов в bitmape заранее
> известно: MftValidDataLength div BytesPerFileRecordSegment

Я понимаю. Я просто предлагаю как вариант попробовать, мож скорость не потеряешь, а память выиграешь.
Кстати, теоретически, памяти в любом случае может не хватить. для номера в MFT зарезервировано 6 байт. 2^48 div 8 больше размера 32разрядного адресного пространства 2^32.

> [22] guav © (23.01.08 14:34)
> Я понимаю. Я просто предлагаю как вариант попробовать,
> мож скорость не потеряешь, а память выиграешь.

Уже скачала. Буду смотреть.

> Кстати, теоретически, памяти в любом случае может не хватить.
> для номера в MFT зарезервировано 6 байт. 2^48 div 8 больше
> размера 32разрядного адресного пространства 2^32.

Очень хочется увидеть диск, сожержащий более MAXDWORD "файловых" объектов.
Простое любопытство :)
А уж поработать на нем ! Например поискать файлы содежащие определенное слово :)

Я тоже посмотрел свою ссылку, предлагаю вот что:
Раз ты всё равно исходишь из предположения, что файлов меньше MAXDWORD, использовать обычный THashSet оттуда, и приводить FILE_REFERENCE к TObject.

Работа с битовыми масками. Найти похожие ветки