хеширование

[mishutka]

Всем спасибо. топик закрыт

[Advertiser]

[psb]

вот вариант без таблиц, думаю, не составит труда разобраться (наверное).

unsigned long crc_octets(const unsigned char *octets, int len)
{
  unsigned long crc = 0xFFFFFFFF;
  unsigned long temp;
  int j;

  while (len--) 
  {
    temp = (unsigned long)((crc & 0xFF) ^ *octets++);
    for (j = 0; j < 8; j++) 
    {
      if (temp & 0x1)
        temp = (temp >> 1) ^ 0xEDB88320;
      else
        temp >>= 1;
    }
    crc = (crc >> 8) ^ temp;
  }
  return crc ^ 0xFFFFFFFF;
}

[Barmaley_m]

Для остальных присутствующих хочу заметить важный момент о CRC. Существует много вариантов вычисления CRC даже при одинаковой ее длине (32 бита): во-первых может быть разным направление сдвига (в "стандартной" CRC32 он идет слева направо), во-вторых, может быть разным значение полинома (в "стандартной" CRC32 полином равен 0xEDB88320). Под "Стандартной" CRC-32 имеется в виду та, которая используется в Ethernet и вообще наиболее распространена на PC: так, например, архиваторы ZIP и RAR используют именно этот алгоритм для вычисления CRC для контроля целостности файлов в архивах.

В последнем сообщении от psb приведена программа для расчета именно этой "стандартной" CRC. Этим она ценна, а также своей краткостью и простотой. Хотя нетабличный расчет CRC выполняется намного дольше табличного: данные обрабатываются побитно, и внутренний цикл выполняется для каждого бита входных данных. При табличном же расчете внутренний цикл выполняется для каждого байта, а не бита. Прирост в скорости более чем в 8 раз.

Примеры, которые приведены в Википедии, используют другой полином и поэтому могут доставить неприятности программисту, пытающемуся повторить стандартный алгоритм и получить совместимые с ним результаты.