Вычисление CRC32 от строки

Иногда для самых разных целей требуется вычислить контрольную сумму строки. Одним из алгоритмов её вычисления является Cyclic redundancy check (CRC) или Циклический избыточный код. CRC является практическим приложением помехоустойчивого кодирования, основанном на определённых математических свойствах циклического кода.

Мы не будем останавливаться на математических подробностях, а просто напишем на D алгоритм CRC32. Цифра 32 определяет количество битов, используемых для вычисления значения CRC. Конечно, есть алгоритмы и с другим количеством битов, но CRC32 является наиболее распространённым в наши дни.

Вот таким образом можно вычислить CRC32:

import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

auto calculateCRC32(string s)
{
	// полином CRC32
	enum int POLYNOMIAL = 0xedb88320;
	
	// вычисление CRC таблицы
	uint[256] createCRCTable()
	{
		typeof(return) crc32Table;
		uint crc32;

		for (int i = 0; i < 256; i++) { crc32 = cast(uint) i; for (int j = 8; j > 0; j--)
			{
				if ((crc32 & 1) == 1)
				{
					crc32 = (crc32 >> 1) ^ POLYNOMIAL;
				}
				else
				{
					crc32 >>= 1;
				}
			}

			crc32Table[i] = crc32;
		}

		return crc32Table;
	}

    // вычисление таблицы на этапе компиляции
	static crc32Table = createCRCTable;

	// строка в байтовом представлении
	auto bytesOfString = s.representation;
	// результат
	uint result = 0xffffffff;

	foreach (block; bytesOfString)
	{
		result = (result >> 8) ^ crc32Table[block ^
				((result) & 0x000000ff)
		];
	}


	return ~result;
}

Теперь испытаем:

void main()
{
	// выводим шестнадцатеричное число
	writefln("%x", calculateCRC32("Как Однажды Головой Жак-звонарь Разбил Фонарь"));
}

На выводе:

3bc19632

P.S.:

ba7ba095

  ;)

И да, не забывайте вступать в нашу группу Вконтакте и подписываться на наш Twitter по желанию. Там можно пообщаться с авторами и редакторами блога.