Помогите распознать контрольную сумму

Помогите, пожалуйста, узнать что за алгоритм выдаёт контрольную сумму. Копаю словарь т9 в нокии, словарь открывается только при правельной контрольной сумме иначе удаляется.
Алгоритм вроде бы 32битный и поидее что то до боли простое, потому как должен быстро работать на смарте..

размер файла 8112байт (буквы в словоре в юникоде)
первые 8 байт не изменяются и имеют следущее значение - 15 86 1F 10 0F 00 00 00
по адресу (offset) 8h, 9h, Ah и Bh - вероятно контрольная сумма
по адресу (offset) Eh, fh - тоже какаято контрольная сумаа.. вроде как зависит от какова хитрого алгоритма подсчета кодов букв в словоре(может какой то щетчик)
по адресу (offset) Ch, Dh, 12h и 13h - не известно что, но они не меняются
по адресу (offset) 14h и 15h - лежит количество слов в словаре
по адресу (offset) 16h и 17h - тут вроде как количество байт использованых для словоря
словарь начинается с offset 1Eh и вероятно контрольная сумма тоже считается с этого байта
A0 обозначает начало новой записи дальше идет 00 потом идет байт в котором записано количество букв в слове за ним 00(очевидно второй байт на количество букв?).

Вот примеры:
15 86 1F 10 0F 00 00 00 2E A2 D3 50 A4 1F F4 28 - контрольная сумма тут - 2E A2 D3 50
00 00 0F 00 01 00 08 00 00 00 36 00 00 00 A0 00
02 00 30 04 30 04 00 00 00 00 00 00 00 00 00 00 - 02 количество букв, 30 04 30 04 - буквы "аа"
..дальше нули

15 86 1F 10 0F 00 00 00 7A D1 D9 45 A4 1F F5 28 - контрольная сумма тут - 7A D1 D9 45
00 00 0F 00 01 00 08 00 00 00 36 00 00 00 A0 00
02 00 30 04 31 04 00 00 00 00 00 00 00 00 00 00
..дальше нули

15 86 1F 10 0F 00 00 00 86 44 C7 7A A4 1F F6 28 - контрольная сумма тут - 86 44 C7 7A
00 00 0F 00 01 00 08 00 00 00 36 00 00 00 A0 00
02 00 30 04 32 04 00 00 00 00 00 00 00 00 00 00
..дальше нули.


В приложении примеры файлов..

 

Приведенные данные вписываются в алгоритм CRC32 с полиномом 0x562735В7, где порядок бит в байте little endian, а порядок байтов big endian. Константу вычислите сами.

 

Спасибо за помощь!!!.. Но к сожалению я обсолютно ничего не понял...

 

http://ru.wikipedia.org/wiki/CRC32
http://www.zorc.breitbandkatze.de/crc.html
http://www.easics.be/webtools/crctool

 

Видимо я слишком глупый((..

порядок каких битов и байтов?.
Если не затруднит - разжуйте пожалуйста откуда и что считать...

 

Little endian - это значит, что число растет от младших разрядов к старшим. Как мы и привыкли в математике. Например, если байт = 00100100(bin), то чему он будет равен вычисляется так:
100100(bin) = 2^2 + 2^5 = 4 + 32 = 36
Если запись десятичного числа выглядит как = 10367, то эта запись = 7 + 6*10 + 3*100 + 0*1000 + 1*10000 = числу 10367.

Big endian - это от старших разрядов к младших. Применительно к байтам это означает что старшина битов растет с конца числа. Н-р, вот десятичная запись числа:
10367 = 1 + 0*10 + 3*100 + 6*1000 + 7*1000 = числу 76301
Теперь про big endian касательно байтов. У процессоров есть 2 типа данных:
word - состоит из 2-х байт
dword - состоит из 2-х word
Порядок следования байтов в word и word'ов в dword'е определяется точно также. Пример (h означает что число записано в 16-ричной системе счисления):
word = 10 3Ah = 10h + 3Ah*100h = числу 3A10h
dword = 10 3A 7B 21h = 3A10h + 217Bh*10000h = числу 217B3A10h

 

Благодарю за разьяснение.
На примере:
15 86 1F 10 0F 00 00 00 2E A2 D3 50 A4 1F F4 28
00 00 0F 00 01 00 08 00 00 00 36 00 00 00 A0 00 - как я понял CRC надо считать с A0
02 00 30 04 30 04 00 00 00 00 00 00 00 00 00 00
..дальше нули
тоесть переворачивать это - A0 00 02 00 30 04 30 04 - надо так - 04 30 04 30 00 02 00 A0
04 30 04 30 00 02 00 A0 ( и плюс нули до конца файла.. ) - это число надо читать?
И про какую константу говорил RElf ?

 

насчет байтов я неправильно сказал - на самом деле здесь все little endian
а полином такой: 0xD7352756
или в нормальном виде:
x^32 + x^30 + x^29 + x^27 + x^25 + x^23 + x^22 + x^21 + x^18 + x^15 + x^13 + x^11 + x^10 + x^7 + x^6 + x^5 + x^3 + x + 1

константа имелась в виду, которая используется в CRC (по-английски - bit pattern):
http://en.wikipedia.org/wiki/Cyclic_redundancy_check#Specification_of_CRC
она вообще говоря будет зависеть от того, с какого места считать CRC и от какой длины данных.

можно тупо взять сорцы классического crc-32 с полиномом 0xEDB88320, заменить полином на указанный выше и подогнать константу (в классическом crc-32 она равна 0xFFFFFFFF) под данные. ну и погонять на большем числе наборов, чтобы окончательно убедиться, что это действительно crc

 

Тоесть константа определяется тупо перебором?

15 86 1F 10 0F 00 00 00 2E A2 D3 50 A4 1F F4 28
00 00 0F 00 01 00 08 00 00 00 36 00 00 00 A0 00
02 00 30 04 30 04 00 00 00 00 00 00 00 00 00 00
считать надо именно в таком виде - ничего не преворачивая?

 

Нет, перебор не нужен. Считаете CRC с нулевой константой, ксорите результат с тем, что должно быть - это и есть искомая константа (которая накладывается в конце вычислений).
Считать нужно как и в классическом crc-32, только заголовок предварительно нужно отрезать от собственно данных.

 

Хм.. что то не получается.

Полином как вы и сказали - 0xD7352756
Константу использовал и 0x00000000 и 0xFFFFFFFF

Допустим получил crc используя полином - 0xD7352756 и константу - 0xFFFFFFFF, crc в этом случае будет - 65CCBF81, далее 65CCBF81 XOR 2EA2D350(этот оригинальный crc этого файла, я правельно понял что на него надо ксорить?) получается - 4B6E6CD1 этим числом заменяю константу в алгаритме, выполняю программу и получаю - 7CD3BB8B

Что неправельно делаю?


вот нашел код на паскале(delphi, и на нем то с трудом получается програмировать.. сильно не пинайте ) его и использовал:

Код (Text):

1.  unit Unit1;
2.  
3. interface
4.  
5. uses
6.   Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
7.   Dialogs, IcsPlus, StdCtrls;
8.  
9. type
10.   TForm1 = class(TForm)
11.     Button1: TButton;
12.     Edit1: TEdit;
13.     procedure Button1Click(Sender: TObject);
14.   private
15.     { Private declarations }
16.   public
17.     { Public declarations }
18.   end;
19.  
20. var
21.   Form1: TForm1;
22.   CRC32Table: array [Byte] of Cardinal;
23.  
24. Const
25.   Crc32Init = $ffffffff;
26.   Crc32Polynomial = $D7352756;
27.  
28. implementation
29.  
30. {$R *.dfm}
31.  
32.  
33. function  Crc32Next   (Crc32Current: LongWord; const Data; Count: LongWord):
34. LongWord; register;
35. Asm //file://EAX - CRC32Current; EDX - Data; ECX - Count
36.   test  ecx, ecx
37.   jz    @@EXIT
38.   PUSH  ESI
39.   MOV   ESI, EDX  //file://Data
40.  
41. @@Loop:
42.     MOV EDX, EAX                       // copy CRC into EDX
43.     LODSB                              // load next byte into AL
44.     XOR EDX, EAX                       // put array index into DL
45.     SHR EAX, 8                         // shift CRC one byte right
46.     SHL EDX, 2                         // correct EDX (*4 - index in array)
47.     XOR EAX, DWORD PTR CRC32Table[EDX] // calculate next CRC value
48.   dec   ECX
49.   JNZ   @@Loop                         // LOOP @@Loop
50.   POP   ESI
51. @@EXIT:
52. End;//Crc32Next
53.  
54. function  Crc32Done   (Crc32: LongWord): LongWord; register;
55. Asm
56.   NOT   EAX
57. End;//Crc32Done
58.  
59. function  Crc32Initialization: Pointer;
60. Asm
61.   push    EDI
62.   STD
63.   mov     edi, OFFSET CRC32Table+ ($400-4)  // Last DWORD of the array
64.   mov     edx, $FF  // array size
65.  
66. @im0:
67.   mov     eax, edx  // array index
68.   mov     ecx, 8
69. @im1:
70.   shr     eax, 1
71.   jnc     @Bit0
72.   xor     eax, Crc32Polynomial  // <ìàãè÷åñêîå> ÷èñëî - òîæå ÷òî ó
73. //ZIP,ARJ,RAR,:
74. @Bit0:
75.   dec     ECX
76.   jnz     @im1
77.  
78.   stosd
79.   dec     edx
80.   jns     @im0
81.  
82.   CLD
83.   pop     EDI
84.   mov     eax, OFFSET CRC32Table
85. End;//Crc32Initialization
86.  
87. function  Crc32Stream (Source: TStream; Count: Longint): LongWord;
88. var
89.   BufSize, N: Integer;
90.   Buffer: PChar;
91. Begin
92.   Result:=Crc32Init;
93.   if Count = 0 then begin
94.     Source.Position:= 0;
95.     Count:= Source.Size;
96.   end;
97.  
98.   if Count > IcsPlusIoPageSize then BufSize:= IcsPlusIoPageSize else
99. BufSize:= Count;
100.   GetMem(Buffer, BufSize);
101.   try
102.     while Count <> 0 do begin
103.       if Count > BufSize then N := BufSize else N := Count;
104.       Source.ReadBuffer(Buffer^, N);
105.       Result:=Crc32Next(Result,Buffer^,N);
106.       Dec(Count, N);
107.     end;
108.   finally
109.     Result:=Crc32Done(Result);
110.     FreeMem(Buffer);
111.   end;
112. End;//Crc32Stream
113.  
114.  
115.  
116. procedure TForm1.Button1Click(Sender: TObject);
117. var
118.   FS: TFileStream;
119.   Crc: LongWord;
120. begin
121.   Crc32Initialization;
122.   FS:= TFileStream.Create('K:\noname',fmOpenRead);
123.   try
124.     Crc:=Crc32Stream(FS,0);
125.     edit2.Text := IntToHex(Crc,8);
126.   finally
127.     FS.FREE;
128.   end;
129. end;
130.  
131. end.

 

Во-первых, не забывайте отрезать заголовок перед подсчетом crc. Во-вторых, ксорить в вашем примере надо с 0x50D3A22E, а не с 0x2EA2D350 (не забывайте про little endian).

 

Спасибо за помощь, но ничего не вышло. Склоняюсь что я просто не создан для подбного либо одно из двух.

 

Весь мозг изломал.. но так и не понял как это сделать((..
RElf у вас получилось вычислить crc нужную? подскажите как именно её считать, у меня обсолютно не получается. Пользуюсь кодом что выше описан, может в нем что то не правельно?
Может я неправельно зоголовок нахожу.. хотя кромсал файл побайтово - ниче не вышло.

 

RElf
Откуда вы взяли полином 0x50D3A22E?
demonogr
http://www.sendspace.com/file/na8klh -неплохое описание CRC

 

To um0v
1. 0x50D3A22E это не полином это crc исходного файла, представленное в little endian, оригинальное, взятое из файла, 0x2EA2D350.

2. Спасибо за чтиво.

 

Ошибся. Полином 0xD7352756. Так как он был вычислен?

 

Если вкратце, то представил данные и значения контрольных сумм как полиномы над полем GF(2), рассмотрел три разности (чтобы избавиться от зависимости от неизвестной константы) f_i(x) и разности соответствующих контрольных сумм g_i(x), далее составил две различные линейные комбинации (с полиномиальными коэффициентами) из f_1(x), f_2(x) и f_3(x) равные нулю. Соответствующие линейные комбинации из g_1(x), g_2(x), g_3(x) тогда обязаны делиться на CRC-полином (если контрольные суммы действительно представляют собой CRC). При этом оказалось, что НОД этих комбинаций равен неприводимому полиному 32-й степени, что с большой вероятностью говорит о том, что был использован именно CRC алгоритм с этим самым полиномом.
Полином приведен выше.

 

Но можно обойтись и без математики - сделать цикл по всем 2^32 возможным полиномам. И для каждого полинома на одном наборе данных вычислить константу (вычислить crc с нулевой константой и поксорить результат с ожидаемым), а на другом наборе проверить дает ли текущий полином и вычисленная константа нужное значение crc.
Таким образом, за не более чем 2^33 вычислений crc искомый полином отыщется (если это действительно crc).

 

[---]