Форум программистов CodeGuru
20 Октябрь 2018, 08:17:00 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.

Войти
Новости:
 
   Начало   Помощь Войти Регистрация  
Страниц: [1]   Вниз
  Печать  
Автор Тема: CRC общая формула  (Прочитано 28090 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Vektor
Новичок
*
Офлайн Офлайн

Сообщений: 8


Просмотр профиля
« : 22 Июнь 2010, 20:00:48 »

Нужно написать общую фломулу для любого CRC (CRC16, CRC32, СКС64). Нужна универсальная формула или алгоритм, модно исходник на Delphi
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #1 : 23 Июнь 2010, 07:08:23 »

Так формула, алгоритм или исходник ? Голливудская улыбка

Вообще, гугль знает кучу ссылок на информацию о CRC (как теорию, алгоритмы, так и готовые исходники).
Гуглить надо по запросу CRC, CRC32 или "Циклический избыточный код".

В википедии точно есть статья на эту тему. К тому же, помнится, там были примеры исходников.
Записан

Vektor
Новичок
*
Офлайн Офлайн

Сообщений: 8


Просмотр профиля
« Ответ #2 : 23 Июнь 2010, 17:54:01 »

Спасибо за ответ, но меня интересует вопрос о существовании универсальной формулы , а не конкретно crc16, crc32, crc64...
Кто знает, прошу дать ссылку.. или  исходники
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #3 : 23 Июнь 2010, 18:28:04 »

Имхо, нет там этой самой "универсальной формулы".
Полиномы в разных CRC разные.

Вот, посылал же в педивикию: CRC aka циклический избыточный код.
Записан

Vektor
Новичок
*
Офлайн Офлайн

Сообщений: 8


Просмотр профиля
« Ответ #4 : 23 Июнь 2010, 20:16:48 »

Хорошо, формулы нет. Значит наверное есть алгоритм, который работает со всеми 30 полиномами?
Записан
holdmann
Пользователь
***
Офлайн Офлайн

Сообщений: 262



Просмотр профиля
« Ответ #5 : 24 Июнь 2010, 13:22:40 »

стало быть есть такой. Почитать тематический материал не пробовали?
Записан

Елси вы хотите купить, продать, отремонтировать автомобиль в Ижевске: Вам сюда =)
(c)holdmann
Vektor
Новичок
*
Офлайн Офлайн

Сообщений: 8


Просмотр профиля
« Ответ #6 : 24 Июнь 2010, 14:36:45 »

Прошу ссылку по общему алгоритму, если не трудно...
Записан
Vektor
Новичок
*
Офлайн Офлайн

Сообщений: 8


Просмотр профиля
« Ответ #7 : 24 Июнь 2010, 17:23:48 »

Люди, горю. На следующей неделе зачет, а нигде не смог найти алгоритм который не использует таблицы. Для CRC8 ,CRC16, CRC32   куча, а общего универсального алгоритма, приспособленного под любой полином так и не нашел. Вообще-то мне нужен лучше код на Delphi. Прошу помощи клуба.
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #8 : 24 Июнь 2010, 18:57:43 »

Люди, горю. На следующей неделе зачет
...
Вообще-то мне нужен лучше код на Delphi.

Вот с этого и стоило начинать  Тащусь !

Тыкнулся в гугль.
По первой ссылке нашел и нагло скопипастил:

Цитировать
О библиотеке:

1. Содержит универсальный алгоритм вычисления CRC-сумм (любой размер от 1 до SizeOf(Cardinal), любой полином).
2. Алгоритм представлен в 2-х реализациях: табличном и нетабличном.
2.1. Табличный алгоритм быстр, но требует доп. память для хранения предварительно сформированной таблицы CRC.
Предназначен для применения в ПЭВМ (а также в аппаратных комплексах с достаточным объемом памяти)
2.2. Нетабличный алгоритм в несколько раз медленнее, но компактен в памяти. Предназначен для реализации в аппаратных комплексах с малым объемом памяти.
3. В представленном молуле переключение между табличной и нетабличной реализациями алгоритма осуществляется установкой/сбросом символа TABLE_ALGORITHM.
4. По умолчанию включен табличный алгоритм. Нетабличный представлен просто для сведения.
5. Также в библиотеку добавлены функции вычисления стандартных CRC16/CRC32, реализованные как вызов универсальной CRC-функции.

CRC.pas

Код:
{
  Universal CRC Library
  Version 2.11 for Delphi 4.0-8.0 & C++Builder 4.0-6.0
}

unit CRC;

{$INCLUDE CRC.Compiler.inc}

{$DEFINE TABLE_ALGORITHM}

interface

type
  TCRCSize = 1..SizeOf(Cardinal);

  TCRCTable = array[Byte] of Cardinal;

procedure InitCRCTable(
  const CRCSize   : TCRCSize;
        Polynomial: Cardinal;
  out   Value     : TCRCTable
);

function UniCRC(
  const Buffer      : Pointer;
  const BufferSize  : Integer;
  const CRCSize     : TCRCSize;
  const CRCTable    : TCRCTable;
  const InvertResult: Boolean
                                  ): Cardinal; overload; {$INCLUDE CRC.Unsafe.inc}

function UniCRC(
  const Buffer      : Pointer;
  const BufferSize  : Integer;
  const CRCSize     : TCRCSize;
        Polynomial  : Cardinal;
  const InvertResult: Boolean
                                 ): Cardinal; overload; {$INCLUDE CRC.Unsafe.inc}

function CRC16(
  const Buffer    : Pointer;
  const BufferSize: Integer
                              ): Word; {$INCLUDE CRC.Unsafe.inc}

function CRC32(
  const Buffer    : Pointer;
  const BufferSize: Integer
                              ): Longword; {$INCLUDE CRC.Unsafe.inc}

implementation

const
  CRC16Size       = SizeOf(Word);
  CRC32Size       = SizeOf(Longword);

  CRC16Polynomial = Word($A001);
  CRC32Polynomial = Longword($EDB88320);

type
  PByte = ^Byte;

function CRCMask(const CRCSize: TCRCSize): Cardinal;
var
  HiBitMask: Cardinal;
begin
  HiBitMask := 1 shl (CRCSize shl 3 - 1);
  Result := HiBitMask or (HiBitMask - 1);
end;

procedure InitCRCTable(
  const CRCSize   : TCRCSize;
        Polynomial: Cardinal;
  out   Value     : TCRCTable
);
var
  Ofs: Byte;
  Shifts: Integer;
  T: Cardinal;
begin
  Polynomial := Polynomial and CRCMask(CRCSize);
  for Ofs := Low(Value) to High(Value) do
  begin
    T := Ofs;
    for Shifts := 0 to 7 do
      if T and 1 <> 0 then
        T := (T shr 1) xor Polynomial
      else
        T :=  T shr 1;
    Value[Ofs] := T;
  end;
end;

function UniCRC(
  const Buffer      : Pointer;
  const BufferSize  : Integer;
  const CRCSize     : TCRCSize;
  const CRCTable    : TCRCTable;
  const InvertResult: Boolean
                                  ): Cardinal;
var
  Mask: Cardinal;
  pB: PByte;
  Ofs: Integer;
begin
  Mask := CRCMask(CRCSize);
  Result := Mask;
  pB := Buffer;
  for Ofs := 0 to BufferSize - 1 do
  begin
    Result := (Result shr 8) xor CRCTable[pB^ xor Byte(Result)];
    Inc(pB);
  end;
  if InvertResult then
    Result := Result xor Mask;
end;

function UniCRC(
  const Buffer      : Pointer;
  const BufferSize  : Integer;
  const CRCSize     : TCRCSize;
        Polynomial  : Cardinal;
  const InvertResult: Boolean
                                 ): Cardinal;
var
  Mask: Cardinal;
  pB: PByte;
  Ofs, Shifts: Integer;
begin
  Mask := CRCMask(CRCSize);
  Polynomial := Polynomial and Mask;
  Result := Mask;
  pB := Buffer;
  for Ofs := 0 to BufferSize - 1 do
  begin
    Result := Result xor pB^;
    for Shifts := 0 to 7 do
      if Result and 1 <> 0 then
        Result := (Result shr 1) xor Polynomial
      else
        Result :=  Result shr 1;
    Inc(pB);
  end;
  if InvertResult then
    Result := Result xor Mask;
end;

{$IFDEF TABLE_ALGORITHM}
var
  FCRC16Table: TCRCTable;
  FCRC32Table: TCRCTable;
{$ENDIF}

function CRC16(
  const Buffer    : Pointer;
  const BufferSize: Integer
                              ): Word;
begin
  Result := UniCRC(
              Buffer,
              BufferSize,
              CRC16Size,
              {$IFDEF TABLE_ALGORITHM} FCRC16Table {$ELSE} CRC16Polynomial {$ENDIF},
              False
            );
end;

function CRC32(
  const Buffer    : Pointer;
  const BufferSize: Integer
                              ): Longword;
begin
  Result := UniCRC(
              Buffer,
              BufferSize,
              CRC32Size,
              {$IFDEF TABLE_ALGORITHM} FCRC32Table {$ELSE} CRC32Polynomial {$ENDIF},
              True
            );
end;

{$IFDEF TABLE_ALGORITHM}
initialization
  InitCRCTable(CRC16Size, CRC16Polynomial, FCRC16Table);
  InitCRCTable(CRC32Size, CRC32Polynomial, FCRC32Table);
{$ENDIF}
 
end.

CRC.Compiler.inc

Код:
{$IFDEF VER150}
  {$DEFINE DELPHI7}
  {$DEFINE DELPHI7_OR_HIGHER}
{$ENDIF}

{$IFDEF VER160}
  {$DEFINE DELPHI7_OR_HIGHER}
  {$DEFINE DELPHI8}
  {$DEFINE DELPHI8_OR_HIGHER}
{$ENDIF}

{$IFDEF DELPHI8_OR_HIGHER}
  {$UNSAFECODE ON}
{$ENDIF}

{$IFDEF DELPHI7}
  {$WARN UNSAFE_TYPE OFF}
{$ENDIF}

{$IFDEF DELPHI7_OR_HIGHER}
  {$WARN UNSAFE_CODE OFF}
{$ENDIF}


CRC.Unsafe.inc

Код:
{$IFDEF DELPHI8_OR_HIGHER} unsafe; {$ENDIF}


И еще в тему:


 ГЫ !
Записан

Vektor
Новичок
*
Офлайн Офлайн

Сообщений: 8


Просмотр профиля
« Ответ #9 : 25 Июнь 2010, 10:56:17 »

СПАСИБО!!! Начинаю разбираться.
Записан
Vektor
Новичок
*
Офлайн Офлайн

Сообщений: 8


Просмотр профиля
« Ответ #10 : 25 Июнь 2010, 15:12:56 »

Вот теперь запутался с обращением к функции CRC32 . Я имею: некоторый файл, с его полным путем к нему. Как мне получить две переменные

1. const Buffer: Pointer;
2. const BufferSize: Integer 

???

Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #11 : 26 Июнь 2010, 08:12:39 »

Имхо, это указатель на буфер (в памяти) и размер буфера.
Т.е. если надо посчитать crc всего файла, то:
1. получаете размер файла (будет потом передаваться в качестве BufferSize).
2. выделяете любым образом буфер полученного размера (получаете указатель на буфер - Buffer).
3. читаете в него файл (заполнение буфера данными).
4. ???
5. PROFIT!!!
Записан

Vektor
Новичок
*
Офлайн Офлайн

Сообщений: 8


Просмотр профиля
« Ответ #12 : 26 Июнь 2010, 20:53:29 »

Спасибо. С этим я разобрался, но возник другой вопрос:
вот в функциях CRC32 и CRC16 первые два параметра (pBuffer, iBufferSize) - Strim.Memory и Strim.Size данного файла.
CRC32Size - тоже понятен или 4 или 2 (для 32 и для 16 соответственно). FCRC32Table  - это таблица, CRC32Polynomial - полином, а что делает последний параметр - логический. Почему в CRC32 он равет true а в  CRC16 - false?
Записан
3V
Администратор
Ветеран
*****
Офлайн Офлайн

Сообщений: 1347



Просмотр профиля WWW
« Ответ #13 : 30 Июнь 2010, 19:08:53 »

InvertResult ? Там в коде же.
Если InvertResult true, то к результат xor-ится с Mask.
xor - поразрядное исключающее "или".
Записан

ATAMAN200
Интересующийся
**
Офлайн Офлайн

Сообщений: 29


Просмотр профиля
« Ответ #14 : 25 Октябрь 2010, 19:44:25 »

Ну если тебе для любого CRC то вот код он расчитывает CRC следующим образом:
Для примера рассчитаем контрольную сумму нескольких 16-битных слов: 0x398a, 0xf802, 0x14b2, 0xc281. Находим их сумму с поразрядным дополнением:
0x398a + 0xf802 = 0x1318c → 0x318d ;
0x318d + 0x14b2 = 0x0463f → 0x463f ;
0x463f + 0xc281 = 0x108c0 → 0x08c1 .
Теперь находим поразрядное дополнение до единицы полученного результата:
0x08c1 = 0000 1000 1100 0001 → 1111 0111 0011 1110 = 0xf73e или, проще — 0xffff − 0x08c1 = 0xf73e. Это и есть искомая контрольная сумма.

Код:
#include "stdafx.h"
#include <iostream>
#include "conio.h"
using namespace std;
unsigned __int16 in_cksum ( unsigned __int16 *ptr, int nbytes )
{
register unsigned __int32 sum;
unsigned __int16 oddbyte;
register unsigned __int16 answer;
sum = 0;
while ( nbytes > 1 )
{
sum += *ptr ++;
nbytes -= 2;
}
if ( nbytes == 1 )
{
oddbyte = 0;
* (( unsigned char *) &oddbyte ) = * (unsigned char *) ptr;
sum += oddbyte;
}
sum = ( sum >> 16 ) + ( sum & 0xFFFF);
sum += (sum >> 16 );
answer=~sum;
return (answer);
}
unsigned __int16 aaa[4] = {0x398a, 0xf802, 0x14b2, 0xc281};
unsigned __int16 bbb;
int main()
{
bbb = in_cksum (aaa, sizeof(aaa));
cout << hex << bbb << endl;
getch();
}

Среда разработки Microsoft Visual Studio 2008, модуль C++.
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!