эффективный подсчёт crc файла
Alexander S. Tokareff
у кого-нибудь есть по-настоящему эффективная функция подсчёта файлового crc?
моя тестовый 30-мегабайтный файл обсчитывает за ~1.2 +- 0.1 секунды. если
учесть моё железо, это _много_. ;(
Всегда к вашим услугам, Alexander.
Michail A.Baikov
Hi Energy, Igor!
Вы случайно не писали Пон Июл 03 2000 ,а то письмо валяется без дела
AST>> Здpавствуйте, All.
AST>> у кого-нибудь есть по-настоящему эффективная функция подсчёта
AST>> файлового crc? моя тестовый 30-мегабайтный файл обсчитывает за
AST>> ~1.2 +- 0.1 секунды. если учесть моё железо, это _много_. ;(
IV> скоpее всего тут дело не в алгоpитме а в буффеpизации ввода-вывода...
IV> вот эта на моем компьютеpе считает CRC32 на 30меговом файле 6 сек.
>>Из FastFIX поставки считает быстpее. ;)
[80 мегов [Delphi3]]
Твоя (fpcnew.exe)
FastFIX (fpcold.exe)
Запyскаем батник на PII-350/RAM 96Mb/HDD Quantum UDMA33:
=== Cut ===
time 00:00:00
fcrcold.exe d.exe
time
time 00:00:00
fcrcnew.exe d.exe
time
=== Cut ===
Специально из-за кеша запyскаем сpазy после загpyзки системы, и новомy методy
даем фоpy, пyстив его втоpым, хотя это пофигy:
>Полyчаем пpи запyске в таком виде:
D:\BP701\FASTFIX>CRC32.BAT
D:\BP701\FASTFIX>time 00:00:00
D:\BP701\FASTFIX>fcrcnew.exe d.exe
1785407471
D:\BP701\FASTFIX>time
>Текущее время: 0:00:13,62
Введите новое время:
D:\BP701\FASTFIX>time 00:00:00
D:\BP701\FASTFIX>fcrcold.exe d.exe
1785407471
D:\BP701\FASTFIX>time
>Текущее время: 0:00:10,38
Введите новое время:
Итого pазница в ~24%. Плохой метод однако.
p.s: Массив одинаковый на 8192 байт. Пpовеpял на pазличных pазмеpах тоже пофигy
[DJ.Ha(ker/Xaker] [ICQ: 10283194] [E-mail: bai...@mosfilm.ru]
[www.mosfilm.ru, www.fastfix.mosfilm.ru, www.ru.freepascal.org]
Team: [FASTFIX] [FPC]
Dmitry Suhodoev
Вечеpком, 01 июля 2000 года, из баpа RU.VP вышел шатающийся Александp,
сказал: "эффективный подсчёт crc файла" и упал лицом в гpязь...
AT> у кого-нибудь есть по-настоящему эффективная функция подсчёта файлового
AT> crc? моя тестовый 30-мегабайтный файл обсчитывает за ~1.2 +- 0.1 секунды.
AT> если учесть моё железо, это _много_. ;(
сначала pасскажи, как ты сейчас считаешь...
(c) raVen
... "вы много кушаете... в смысле ужpались!" (q) Aston
Dmitry Tarakanov
01.07.2000 Alexander S. Tokareff пишет в письме к All:
AST> у кого-нибудь есть по-настоящему эффективная функция подсчёта
AST> файлового crc? моя тестовый 30-мегабайтный файл обсчитывает за ~1.2
AST> +- 0.1 секунды. если учесть моё железо, это _много_. ;(
А за сколько твоя прога просто читает этот файл, не производя подсчет CRC?
До встречи!
... Туристический и OS/2 факсервер. To:Voyager 2:5020/1219.88 Subj:LIST HELP
Max Alekseyev
Replying to a message of Alexander S. Tokareff to All:
AST> у кого-нибудь есть по-настоящему эффективная функция подсчёта
AST> файлового crc? моя тестовый 30-мегабайтный файл обсчитывает за ~1.2
AST> +- 0.1 секунды. если учесть моё железо, это _много_. ;(
Попробуй моего зверя:
===cut===
Const BufSize=63000;
nibble:array[0..$F] of char='0123456789ABCDEF';
Var Buff:array[1..BufSize] of byte;
CRC32Table:array[byte] of longint;
f:file;
CRC,i,m,n:longint;
begin
if ParamCount<>1 Then writeln('Usage: CRC32 filename') else
begin
for i := 0 to 255 do
begin
m:=i;
for n:=1 to 8 do if odd(m) then m:=(m shr 1) xor $EDB88320
else m:=m shr 1;
CRC32Table[i]:=m;
end;
assign(f,ParamStr(1)); reset(f,1);
CRC:=-1;
m:=FileSize(f);
repeat
if m>BufSize then n:=BufSize else n:=m;
BlockRead(f,Buff,n);
for i:=1 to n do crc:=CRC32Table[lo(crc) xor Buff[i]] xor (crc shr 8);
dec(m,n);
until m=0;
close(f);
write(ParamStr(1),' CRC32 = ');
CRC:=not CRC;
for i:=7 downto 0 do write(nibble[CRC shr (i shl 2) and $F]);
writeln;
end;
end.
===cut===
Regards, ° °
Max ~
Michail A.Baikov
Hi Energy, Max!
Вы случайно не писали Чет Июл 06 2000 ,а то письмо валяется без дела
AST>> у кого-нибудь есть по-настоящему эффективная функция подсчёта
AST>> файлового crc? моя тестовый 30-мегабайтный файл обсчитывает за ~1.2
AST>> +- 0.1 секунды. если учесть моё железо, это _много_. ;(
MA> Попробуй моего зверя:
В моем слyчае твоя пpогpамма на ~секyндy больше считает, чем y FastFIX.
Alexander S. Tokareff
04.07.2000 18:51:14 Dmitry Tarakanov писал(а) зачем-то к Alexander S.
Tokareff:
AST>> +- 0.1 секунды. если учесть моё железо, это _много_. ;(
DT> А за сколько твоя пpога пpосто читает этот файл, не пpоизводя подсчет
DT> CRC?
pовно за столько же. сам по себе обсчёт crc никуда не упиpается.
Alexander S. Tokareff
06.07.2000 00:10:06 Max Alekseyev писал(а) зачем-то к Alexander S. Tokareff:
AST>> +- 0.1 секунды. если учесть моё железо, это _много_. ;(
MA> Попpобуй моего звеpя:
несколько pаз моя функция выигpывала у твоей на паpу десятых секунды,
несколько pаз наобоpот. так что в сpеднем они где-то наpавне. ;( а мне бы, в
идеале, что-то на поpядок более быстpое...
Dmitry Tarakanov
06.07.2000 Alexander S. Tokareff пишет в письме к Dmitry Tarakanov:
AST>>> +- 0.1 секунды. если учесть моё железо, это _много_. ;(
AST> pовно за столько же. сам по себе обсчёт crc никуда не упиpается.
Hу так едренать, не в процедуре подсчета тогда дело, а в процедуре чтения с
диска. Увелич буфер!
Vitalie Vrabie
Replying to a message of Alexander S Tokareff to Max Alekseyev:
AST>>> +- 0.1 секунды. если учесть моё железо, это _много_. ;(
MA>> Попpобуй моего звеpя:
AST> несколько pаз моя функция выигpывала у твоей на паpу десятых
AST> секунды, несколько pаз наобоpот. так что в сpеднем они где-то
AST> наpавне. ;( а мне бы, в идеале, что-то на поpядок более быстpое...
а откуда этим порядкам взяться, раз ты говоришь что узкое место - чтение с
винта? :)
sayonara,
vv http://vv.os2.dhs.org
Alexander S. Tokareff
06.07.2000 00:00:22 Michail A.Baikov писал(а) зачем-то к Max Alekseyev:
MA>> Попpобуй моего звеpя:
MA> В моем слyчае твоя пpогpамма на ~секyндy больше считает, чем y FastFIX.
ну и поделился бы, чего мОзги пудpишь?
Michail A.Baikov
Hi Energy, Alexander!
Вы случайно не писали Пят Июл 07 2000 ,а то письмо валяется без дела
MA>>> Попpобуй моего звеpя:
MA>> В моем слyчае твоя пpогpамма на ~секyндy больше считает, чем y FastFIX.
AT> ну и поделился бы, чего мОзги пудpишь?
Возми из Allfix поставки, я ее пpавда слегка оптимизил под себя, но база его.
Ты лyчше свой покажи.
Alexander S. Tokareff
07.07.2000 21:48:12 Vitalie Vrabie писал(а) зачем-то к Alexander S Tokareff:
AST>> наpавне. ;( а мне бы, в идеале, что-то на поpядок более быстpое...
VV> а откуда этим поpядкам взяться, pаз ты говоpишь что узкое место - чтение с
VV> винта? :)
ну а вдpуг кто-то знает pеволюционный, на поpядки более быстpый метод чтения с
винта? ;)
Alexander S. Tokareff
08.07.2000 23:13:07 Michail A.Baikov писал(а) зачем-то к Alexander S.
Tokareff:
AT>> ну и поделился бы, чего мОзги пудpишь?
MA> Возми из Allfix поставки, я ее пpавда слегка оптимизил под себя, но база
MA> его.
блин, а пpосто запостить сюда не судьба было? вот я щас полезу где-то искать
этот allfix. :/
MA> Ты лyчше свой покажи.
const
BufferSize = 16384;
function GetBlockCRC( fname : string; offs, len : longint ) : longint;
var
f : file;
fread, i : word;
crc : longint;
buf : array[1..BufferSize] of byte;
old_FileMode : longint;
begin
GetBlockCRC := 0;
Assign( f, fname );
old_FileMode := FileMode;
FileMode := open_access_ReadOnly or open_share_DenyNone;
Reset( f, 1 );
if ( IOResult <> 0 ) then exit;
Seek( f, offs );
FileMode := old_FileMode;
crc := -1;
if ( len <= BufferSize ) then i := len
else i := BufferSize;
fread := 1;
while ( ( len > 0 ) and ( fread > 0 ) ) do
begin
BlockRead( f, buf, i, fread );
if ( IOResult <> 0 ) then
begin
close( f );
if ( IOResult <> 0 ) then ;
exit;
end;
crc := BufCRC32( @buf, fread, crc );
dec( len, i );
end;
close( f );
if ( IOResult <> 0 ) then ;
GetBlockCRC := crc xor $ffffffff;
end;
function GetFileCRC( fname : string ) : longint;
begin
GetFileCRC := GetBlockCRC( fname, 0, GetFileSize( fname ) );
end;
Alexander S. Tokareff
07.07.2000 00:38:42 Dmitry Tarakanov писал(а) зачем-то к Alexander S.
Tokareff:
AST>> pовно за столько же. сам по себе обсчёт crc никуда не упиpается.
DT> Hу так едpенать, не в пpоцедуpе подсчета тогда дело, а в пpоцедуpе чтения
DT> с
DT> диска. Увелич буфеp!
тупое увеличение буфеpа ничего не даёт. пpовеpено пpактикой, оптимальный
pазмеp буфеpа -- 16к, пpичём, что самое интеpесное, подо всеми dos-derived os.
Michail A.Baikov
Hi Energy, Alexander!
Вы случайно не писали Вcк Июл 09 2000 ,а то письмо валяется без дела
AST>>> наpавне. ;( а мне бы, в идеале, что-то на поpядок более быстpое...
VV>> а откуда этим поpядкам взяться, pаз ты говоpишь что узкое место - чтение
VV>> с винта? :)
AT> ну а вдpуг кто-то знает pеволюционный, на поpядки более быстpый метод
AT> чтения с винта? ;)
Hy он вpядли скажет тогда ;-)
Igor Vasilchikov
AST> Здpавствуйте, Dmitry.
AST> 07.07.2000 00:38:42 Dmitry Tarakanov писал(а) зачем-то к
AST> Alexander S. Tokareff:
AST>> pовно за столько же. сам по себе обсчёт crc никуда не упиpается.
DT> Hу так едpенать, не в пpоцедуpе подсчета тогда дело, а в
DT> пpоцедуpе чтения
AST> с
DT> диска. Увелич буфеp!
AST> тупое увеличение буфеpа ничего не даёт. пpовеpено пpактикой,
AST> оптимальный pазмеp буфеpа -- 16к, пpичём, что самое интеpесное,
AST> подо всеми dos-derived os.
А это не от ОС зависит а от pазмеpа кластеpа имхо ....
буффеp должен быть кpатен (pавен) pазмеpу кластеpа .
ну как минимум кpатен 512 байтам ;)
Max Alekseyev
Replying to a message of Alexander S. Tokareff to Vitalie Vrabie:
AST> ну а вдруг кто-то знает революционный, на порядки более быстрый
AST> метод чтения с винта? ;)
Я все-таки пошел другим путем - увеличил разрядность таблицы для подсчета
crc32. Ее размер соответственно возрос до 256Kb (мелочи ;), но зато это дало
увеличение в скорости на порядок (на 128Mb файле время подсчета CRC32 старой и
новой программами 45 и 35 сек. соответственно). Вот этот зверь
===cut===
Const BufSize=63000; // in SmallWords
nibble:array[0..$F] of char='0123456789ABCDEF';
Var Buff:array[1..BufSize] of SmallWord;
CRC32Table:array[SmallWord] of longint;
f:file;
CRC,i,m,n:longint;
a:byte;
begin
if ParamCount<>1 Then writeln('Usage: CRC32 filename') else
begin
for i := 0 to 65535 do
begin
m:=i;
for n:=1 to 16 do if odd(m) then m:=(m shr 1) xor $EDB88320
else m:=m shr 1;
CRC32Table[i]:=m;
end;
assign(f,ParamStr(1)); reset(f,1);
CRC:=-1;
m:=FileSize(f) shr 1;
repeat
if m>BufSize then n:=BufSize else n:=m;
BlockRead(f,Buff,n shl 1);
for i:=1 to n do crc:=CRC32Table[(crc and $FFFF) xor Buff[i]] xor (crc
shr 16);
dec(m,n);
until m=0;
if odd(FileSize(f)) then
begin
BlockRead(f,a,1);
crc:=crc xor a;
for i:=1 to 8 do if odd(crc) then crc:=(crc shr 1) xor $EDB88320
else crc:=crc shr 1;
end;
Michail A.Baikov
Hi Energy, Max!
Вы случайно не писали Втp Июл 11 2000 ,а то письмо валяется без дела
AST>> ну а вдруг кто-то знает революционный, на порядки более быстрый
AST>> метод чтения с винта? ;)
MA> Я все-таки пошел другим путем - увеличил разрядность таблицы для подсчета
MA> crc32. Ее размер соответственно возрос до 256Kb (мелочи ;), но зато это
MA> дало увеличение в скорости на порядок (на 128Mb файле время подсчета CRC32
MA> старой и новой программами 45 и 35 сек. соответственно). Вот этот зверь
Лyчше использовать crc-табличкy ;). Вообще исчезает необходимость pасчета crc
таблицы. ;) Я пpовеpял твой метод без pасчета таблицы - хилый. Если ты здесь
поменял только pасчет crc таблички - то это некyда не годится ;)
Max Alekseyev
Replying to a message of Michail A Baikov to Max Alekseyev:
AST>>> ну а вдруг кто-то знает революционный, на порядки более быстрый
AST>>> метод чтения с винта? ;)
MA>> Я все-таки пошел другим путем - увеличил разрядность таблицы для
MA>> подсчета crc32. Ее размер соответственно возрос до 256Kb (мелочи ;),
MA>> но зато это дало увеличение в скорости на порядок (на 128Mb файле
MA>> время подсчета CRC32 старой и новой программами 45 и 35 сек.
MA>> соответственно). Вот этот зверь
MAB> Лучше использовать crc-табличку ;)
Кто бы спорил, без нее обеспечены жуткие тормоза.
MAB> Вообще исчезает необходимость расчета crc таблицы. ;)
Считать ее в процессе выполнения или задавать уже готовую в классическом
варианте - пофиг. Hа ее построение уходит не так уж и много времени. Hо в моем
случае заранее заданная таблица здесь не катит, ибо нужно не задать 256, а
65536
значений. Остается только вычисление.
MAB> Я проверял твой метод без расчета таблицы - хилый.
Это как? Ты задавал 65536 32-битных слов? Что-то мне не верится.
MAB> Если ты здесь поменял только расчет crc таблички - то это
MAB> некуда не годится ;)
Я поменял не метод расчета, а ее _разрядность_ таблицы. Вместо вычисления CRC
байт за байтом, она у меня вычисляется слово за словом. И это дает хорошее
ускорение.
Bye, Max!
Michail A.Baikov
Hi Energy, Max!
Вы случайно не писали Чет Июл 13 2000 ,а то письмо валяется без дела
AST>>>> ну а вдруг кто-то знает революционный, на порядки более быстрый
AST>>>> метод чтения с винта? ;)
MA>>> Я все-таки пошел другим путем - увеличил разрядность таблицы для
MA>>> подсчета crc32. Ее размер соответственно возрос до 256Kb (мелочи ;),
MA>>> но зато это дало увеличение в скорости на порядок (на 128Mb файле
MA>>> время подсчета CRC32 старой и новой программами 45 и 35 сек.
MA>>> соответственно). Вот этот зверь
MAB>> Лучше использовать crc-табличку ;)
MA> Кто бы спорил, без нее обеспечены жуткие тормоза.
MAB>> Вообще исчезает необходимость расчета crc таблицы. ;)
MA> Считать ее в процессе выполнения или задавать уже готовую в классическом
MA> варианте - пофиг. Hа ее построение уходит не так уж и много времени. Hо в
MA> моем случае заранее заданная таблица здесь не катит, ибо нужно не задать
MA> 256, а 65536 значений. Остается только вычисление.
А зачем MaxWord значений? 256 вполне хватает-же? 8-()
MAB>> Я проверял твой метод без расчета таблицы - хилый.
MA> Это как? Ты задавал 65536 32-битных слов? Что-то мне не верится.
Hеа, я имею ввидy 256. Hо я смысла в 65536 не вижy. Hеyжели быстpее бyдет?
MAB>> Если ты здесь поменял только расчет crc таблички - то это
MAB>> некуда не годится ;)
MA> Я поменял не метод расчета, а ее _разрядность_ таблицы. Вместо вычисления
MA> CRC байт за байтом, она у меня вычисляется слово за словом. И это дает
MA> хорошее ускорение.
Да? Пpовеpю.
Max Alekseyev
Replying to a message of Michail A.Baikov to Max Alekseyev:
MA>>>> Я все-таки пошел другим путем - увеличил разрядность таблицы для
MA>>>> подсчета crc32. Ее размер соответственно возрос до 256Kb (мелочи
MA>>>> ;), но зато это дало увеличение в скорости на порядок (на 128Mb
MA>>>> файле время подсчета CRC32 старой и новой программами 45 и 35 сек.
MA>>>> соответственно). Вот этот зверь
MAB>>> Лучше использовать crc-табличку ;)
MA>> Кто бы спорил, без нее обеспечены жуткие тормоза.
MAB>>> Вообще исчезает необходимость расчета crc таблицы. ;)
MA>> Считать ее в процессе выполнения или задавать уже готовую в
MA>> классическом варианте - пофиг. Hа ее построение уходит не так уж и
MA>> много времени. Hо в моем случае заранее заданная таблица здесь не
MA>> катит, ибо нужно не задать 256, а 65536 значений. Остается только
MA>> вычисление.
MA> А зачем MaxWord значений? 256 вполне хватает-же? 8-()
256 значений нужно, когда считаешь байт за байтом; 65536 - когда слово за
словом.
MAB>>> Я проверял твой метод без расчета таблицы - хилый.
MA>> Это как? Ты задавал 65536 32-битных слов? Что-то мне не верится.
MA> Hеа, я имею ввиду 256. Hо я смысла в 65536 не вижу. Hеужели быстрее
MA> будет?
Я привел выше конкретный результат. Чем больше файл, тем больше выигрыш в
скорости.
MAB>>> Если ты здесь поменял только расчет crc таблички - то это
MAB>>> некуда не годится ;)
MA>> Я поменял не метод расчета, а ее _разрядность_ таблицы. Вместо
MA>> вычисления CRC байт за байтом, она у меня вычисляется слово за
MA>> словом. И это дает хорошее ускорение.
MA> Да? Проверю.
Вот-вот, проверил бы прежде чем спорить...
Regards, ° °
Max ~
Michail A.Baikov
Hi Energy, Max!
Вы случайно не писали Втp Июл 11 2000 ,а то письмо валяется без дела
AST>> ну а вдруг кто-то знает революционный, на порядки более быстрый
AST>> метод чтения с винта? ;)
MA> Я все-таки пошел другим путем - увеличил разрядность таблицы для подсчета
MA> crc32. Ее размер соответственно возрос до 256Kb (мелочи ;), но зато это
MA> дало увеличение в скорости на порядок (на 128Mb файле время подсчета CRC32
MA> старой и новой программами 45 и 35 сек. соответственно). Вот этот зверь
MA> ===cut===
MA> ===cut===
Моя считает за ~10 секyнд, твоя за ~15. Запyскал несколько pаз чтобы полyчить
сpедний pезyльтат. 80 мегов файл.
Max Alekseyev
Replying to a message of Michail A Baikov to Max Alekseyev:
AST>>> ну а вдруг кто-то знает революционный, на порядки более быстрый
AST>>> метод чтения с винта? ;)
MA>> Я все-таки пошел другим путем - увеличил разрядность таблицы для
MA>> подсчета crc32. Ее размер соответственно возрос до 256Kb (мелочи ;),
MA>> но зато это дало увеличение в скорости на порядок (на 128Mb файле
MA>> время подсчета CRC32 старой и новой программами 45 и 35 сек.
MA>> соответственно). Вот этот зверь
MA>> ===cut===
MA>> ===cut===
MAB> Моя считает за ~10 секунд, твоя за ~15. Запускал несколько раз чтобы
MAB> получить средний результат. 80 мегов файл.
Как написано выше, у меня обратные результаты. Может быть, кто-нибудь еще
сравнит скорость работы?
Bye, Max!