Статья: "Два слова из трёх букв"

Статья

Два слова из трёх букв

Как вы уже поняли, в этой статье речь пойдёт про RND (случайное число) и CRC (контрольная сумма).

Почему всё в кучу, спросите вы? Потому что это всё взято из одного и того же проекта, хотя и не в этом дело, а в том, что разбивать на маленькие статейки нет особого смысла.

Статья ориентирована на начинающих, каким и я являюсь. Я буду писать с точки зрения новичка, который столкнулся с этими проблемами и нашёл решения и нужную документацию не сразу. Надеюсь, кому-то всё это поможет. Кроме того, я постараюсь не отсылать в RTFM, а рассказать своими словами.

Если кто-то заметит в статье явную грубую или не очень грубую, но не менее явную ошибку - исправляйте на форуме, я буду только благодарен.

Все примеры писались и компилировались в Windows98, среда - VC6++ с использованием библиотеки MFC.

1 Случайное число (RND)

RND - это псевдослучайное число (от "Random" - случайный). В языке Бейсик и многих других языках более высокого уровня, чем C++, есть функция RND(n), которая генерит псевдослучайное число в диапазоне 0<X<1. В C++ я такой функции не заметил, но, возможно, это и к лучшему. Вас не смущает приставка "псевдо"? Да, "ненастоящее" случайное число! Так когда-то и было - по крайней мере в программируемых калькуляторах и том же Бейсике. Делалось это так - составлялась таблица из истинно случайных чисел и навсегда зашивалась в ПЗУ (в МК) или файл (в ПК). Далее - далеко не случайно - из этой таблицы брались числа, обычно просто по очереди, сдвигая некий указатель на единицу после каждого запроса RND программой. Или составлялась мутная формула с участием 3 и 5 цифры дробной части числа, сильно зависящего от констант (!) - экспоненты или числа пи.

Сомневаюсь, что в современных языках, имеющих встроенную функцию RND(), борода приклеена по-другому. А в результате: после запуска программы эти числа появляются в определённом порядке со всеми вытекающими. Казалось бы, что может быть проще, чем получить случайное число? Кинул кубик - выпало число. В природе ПСЕВДО случайные цифры и параметры практически не встречаются, а почти что ИСТИННО случайных - полно, сама эволюция-матушка. А вот в электронной цифровой системе после запуска все цифровые процессы (если так можно выразиться) начинаются одинаково. Приходим к двум выводам:

срочно нужно избавляться от приставки псевдо-
для этого необходимо внести в программу природную случайность!

Можно сделать вовсе извращенными методами: например, улавливанием из воздуха электрических помех с помощью специально разработанного устройства, подключемого к USB порту и распространяемого вместе с программой, батарейки и "гарантия 1 месяц прилагается, пломбы не срывать". Но можно проще.

Добавим в объект View нашей программы две переменные:

Код:

//файл LT6View.h
class CLT6View : public CFormView
{
private:
	DWORD m_dwRNDx;//RND-число от координаты X
	DWORD m_dwRNDy;//RND-число от координаты Y
	...
	...
}

Затем добавим в обработчик сообщения WM_MOUSEMOVE объекта View две строки

Код:

//	файл LT6View.h
void CLT6View::OnMouseMove(UINT nFlags, CPoint point)
{
//перемешиваем случайное число
	m_dwRNDx+=(DWORD)((ULONG)point.x)+((DWORD)((ULONG)point.y)<<20);
	m_dwRNDy+=(DWORD)((ULONG)point.y)+(DWORD)((ULONG)point.x)<<14);
//вызываем обработчик родительского класса
	CFormView::OnMouseMove(nFlags, point);
}

То есть, при движении курсора мыши по окну View обработчик вызывается каждый раз, когда меняются координаты курсора, при этом к переменной m_dwRNDx прибавляется значение координаты X и значение координаты Y, сдвинутое на 20 бит влево. Также к переменной m_dwRNDy прибавляется значение координаты Y и значение координаты X, сдвинутое на 14 бит влево. Сдвиги нужны для того, чтобы значение четырёхбайтной переменной росло не только с младших разрядов, но и где-то со старших. В результате всего получается целых 8, я не побоюсь этого слова, СЛУЧАЙНЫХ байт! Ведь не у каждого человека настолько твёрдая рука, чтобы повторить траекторию курсора в точности. Количество сдвигов подобрано эмпирически таким образом, чтобы перемешивание числа радовало глаз. Это удобно проследить таким способом. Добавим в форму объекта View элемент CStatic и присвоим ему идентификатор IDC_STATIC1. В обработчик сообщения добавим ещё 3 строчки кода:

Код:

void CLT6View::OnMouseMove(UINT nFlags, CPoint point)
{
//перемешиваем случайное число
	m_dwRNDx+=(DWORD)((ULONG)point.x)+((DWORD)((ULONG)point.y)<<20);
	m_dwRNDy+=(DWORD)((ULONG)point.y)+(DWORD)((ULONG)point.x)<<14);
//m_dwRNDx - старшие 4 байта
//m_dwRNDy - младшие 4 байта
	CString txt;
	txt.Format("%8x%8x",m_dwRNDx,m_dwRNDy);
	((CStatic*)GetDlgItem(IDC_STATIC1))->SetWindowText(txt);
//вызываем обработчик родительского класса
	CFormView::OnMouseMove(nFlags, point);
}

Запускаем программу и совершаем движения vsim.. Наше число будет выводиться как 16-разрядное шестнадцатеричное число.

2 Контрольная сумма (CRC)

Контрольная сумма используется для проверки правильности и целостности файла, сообщения, переданного с другого компьютера, и вообще любого массива, состоящего из байтов (или, как вариант, из двоичных чисел с другой разрядностью, например, 16 бит).

В статье использована информация из документа AN730 фирмы Microchip, автор - Thomas Schmidt. Смысл вычисления CRC заключается в следующем. Выбирается какой-нибудь полином (для простоты - шестнадцатибитное число, константа) P16. Это будет полиномом контрольной суммы - с помощью него будет считаться и проверяться контрольная сумма. Пусть выберем его равным 0x8102. Всё сообщение (массив байтов) представляется как одно N-разрядное двоичное число. Затем производится операция, похожая на деление, но не совсем деление. Представьте себе деление двоичных чисел столбиком (да, с непривычки глаза округляются, но это ещё ягодки, косточки потом выпадут). Но вместо привычного вычитания знаменателя из длинного числителя, будем производить операцию "поразрядное исключающее или". Так же точно в промежуточных "остатках" от "деления" знаменателя станут появляться незначащие нули, и числитель станет двигаться под знаменателем вправо, пока не пройдёт до самых младших разрядов. Но на этом нельзя останавливаться - к сообщению СПРАВА нужно дописать количество нулей, равное РАЗРЯДНОСТИ полинома P16. То есть, в нашем случае - 16 нулей. Операция деления продолжается, пока "знаменатель" не доедет до конца этого удлинённого сообщения. Естественно, никакого частного и в помине нет - оно и не нужно; в результате останется только "остаток", по разрядности равный полиному. Это и есть CRC.

Теоретически, полученная таким образом CRC однозначно характеризует последовательность битов в исходном сообщении, и поменяйся хоть один бит - его CRC с тем же полиномом поменяется. Но это теоретически, а доказано или нет - не знаю. Хотя вполне вероятно.

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

Но программно это решается проще. Оставим теорию.

Представьте 16-битную переменную CRCHL (тип WORD или unsigned long, ULONG) и 8-битную переменную CRCBUF (тип BYTE или unsigned char, UCHAR). В CRCHL будет накапливаться текущее значение CRC, а CRCBUF - это буфер-приёмник каждого нового байта сообщения. Те два нулевых байта в конце сообщения тоже припишем, но потом. Инициализация такова: в старший байт CRCHL помещаются первый байт сообщения (то есть, с индексом 0 - не забывайте, что нумерация начинается с нуля, а количество - с единицы), а в младший байт CRCHL - второй байт сообщения (индекс - 1). В буфер CRCBUF помещается третий байт сообщения. Представили этот ещё не запущенный конвеер? Теперь погнали.

1.1) Полученное трёхбайтное число сдвигается влево на 1 бит. Старший бит этого числа выдвигается в переменную С (аналог флага переноса) типа bool. Справа вдвигается бит, равный нулю:
C <- (CRCHL)( CRCBUF) <-0
1.2) Eсли флаг C установлен, то производим операцию xor (исключающее или) между переменной CRCHL и полиномом P16:
CRCHL = CRCHL xor P16
1.3) Пункты 1.1 и 1.2 повторяются ещё 7 раз - то есть, пока весь буфер не будет вдвинут в CRCHL.

2) В освободившийся теперь буфер помещается следующий байт сообщения - и переходим к 1). Если сообщение закончилось, переходим к 3).

3) Теперь нужно приписать ещё два нулевых байта к сообщению (мысленно).

4.1) Двухбайтное число CRCHL сдвигается влево на 1 бит. Старший бит этого числа выдвигается в переменную С. Справа вдвигается бит, равный нулю:
C <- (CRCHL) <-0
4.2) если флаг C установлен, то производим операцию xor (исключающее или) между переменной CRCHL и полиномом P16:
CRCHL = CRCHL xor P16
4.3) пункты 4.1 и 4.2 повторяются ещё 15 раз - так как мы приписали всего 16 нулевых битов.

5) В переменной CRCHL - и есть наше CRC.

Теперь реализация (здесь переменная C - типа WORD, для исключения проблем с преобразованием типов):

Код:

//генерация CRC. buf - указатель на массив типа BYTE с сообщением.
//Num (>=3) - количество байт в сообщении.
WORD CLT6View::MakeCRC16(BYTE *buf, WORD Num)
{
	WORD Polynom16=0x8102;//полином 0b1000 0001 0000 0010
	WORD CRCHL;//хранит текущую CRC
	BYTE CRCBUF;//буфер для очередного байта сообщения
	BYTE i;
	WORD n,c;
	
//первые два байта сообщения
	CRCHL=((WORD)buf[0])<<8 | buf[1];
	//по очереди достаём все байты сообщения
	for(n=2;n<Num;n++)
	{
//кладём в буфер очередной байт сообщения
		CRCBUF=buf[n];
//и побитно вдвигаем его в CRCHL
		for(i=0;i<8;i++)
		{
//бит, выдвинутый слева из CRCHL (bool!!)
			c=CRCHL & 0x8000;
//сдвиг CRCHL и вдвигание старшего бита из CRCBUF
			CRCHL=CRCHL<<1 | CRCBUF>>7;
//сдвиг CRCBUF
			CRCBUF=CRCBUF<<1;
//если из CRCHL вначале был выдвинут ненулевой бит, то xor
			if(c)CRCHL^=Polynom16;
		}
	}

//"добавляем в конец сообщения ещё 2 нулевых байта"
	for(i=0;i<16;i++)
	{
//бит, выдвинутый слева из CRCHL (bool!!)
		c=CRCHL & 0x8000;
//сдвиг CRCHL и вдвигание нуля из CRCBUF
		CRCHL=CRCHL<<1;
//если из CRCHL вначале был выдвинут ненулевой бит,то xor
		if(c)CRCHL^=Polynom16;
	}
	return CRCHL;
}

К примеру подсунем процедуре буфер, заполненный так:
	
	BYTE bufer[]={0,1,2,3,4,5,6,7,8};
	WORD crc=MakeCRC16(bufer,9);
//значение crc==0x46a0

У меня всё.

Версия для печати

Обсудить на форуме