Эмуляция 1801ВП1-128 в ПЛИС

**Patron** · 13.12.2013, 23:20

Сообщение от Vslav

Вот текст программки которая соответствует извлеченному алгоритму

Для прикола - ещё один вариант того же алгоритма, использующий только сдвиги:

Код:

unsigned short int crc16( unsigned short crc, unsigned char data )
{
	printf("\r\n %02X ( %04X,", data, crc);

	crc = ~crc;
	crc =  unsigned char (crc >> 8) | (crc << 8);
	crc ^= data;
	crc ^= unsigned char (crc) >> 4;
	crc ^= crc << 12;
	crc ^= unsigned char (crc) << 5;
	crc = ~crc;
	
	printf(" %04X )", crc );
	return crc;
}

Результат запуска:

Код:

 A1 ( 0000, BBC4 )
 A1 ( BBC4, 6974 )
 30 ( 6974, A1D3 )
 31 ( A1D3, 4EB6 )
 32 ( 4EB6, 1714 )
 33 ( 1714, 6EE9 )
CRC: 9116
 A1 ( 0000, BBC4 )
 A1 ( BBC4, 6974 )
 30 ( 6974, A1D3 )
 31 ( A1D3, 4EB6 )
 32 ( 4EB6, 1714 )
 33 ( 1714, 6EE9 )
 91 ( 6EE9, E9FF )
 16 ( E9FF, FFFF )
TMP: FFFF CRC OK

---------- Post added at 22:20 ---------- Previous post was at 22:04 ----------

В оригинале - это алгоритм CRC-16:

Код:

CRC-16
width=16 poly=0x1021 init=0xFFFF refin=false refout=false
xorout=0x0000 check=0x29B1

Код:

unsigned short int crc16( unsigned short crc, unsigned char data )
{
	printf("\n %02X ( %04X,", data, crc);

	crc =  unsigned char (crc >> 8) | (crc << 8);
	crc ^= data;
	crc ^= unsigned char (crc) >> 4;
	crc ^= crc << 12;
	crc ^= unsigned char (crc) << 5;
	
	printf(" %04X )", crc );
	return crc;
}

int main(int argc, char *argv[])
{
	unsigned short crc, tmp;

	crc = 0xFFFF;
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0x30);
	crc = crc16(crc, 0x31);
	crc = crc16(crc, 0x32);
	crc = crc16(crc, 0x33);
	tmp = crc;
	printf("\nCRC: %04X", tmp);
}

**Advertiser** · 13.12.2013, 23:20

**Alex_K** · 13.12.2013, 23:55

Уж для того, чтобы разобраться какой алгоритм используется для подсчета CRC, в архиве "сырые данные" с нулевой дорожки нижней стороны отформатированной на УКНЦ дискеты. Там все - и межсекторные промежутки, и маркеры, и заголовки, и данные, ну и соответственно CRC.

**Patron** · 14.12.2013, 00:53

Сообщение от Alex_K

Там все - и межсекторные промежутки, и маркеры, и заголовки, и данные, ну и соответственно CRC.

Чтобы далеко не ходить - возьмём заголовок первого сектора:

Код:

A1 A1 A1 FE 00 00 01 02 CA 6F

Запустим эти байты в стандартный алгоритм CRC-16:

Код:

	printf("Write:");
	crc = 0xFFFF;
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xFE);
	crc = crc16(crc, 0x00);
	crc = crc16(crc, 0x00);
	crc = crc16(crc, 0x01);
	crc = crc16(crc, 0x02);
	tmp = crc;
	printf("\nCRC: %04X", tmp);

	printf("\n\nRead:");
	crc = 0xFFFF;
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xFE);
	crc = crc16(crc, 0x00);
	crc = crc16(crc, 0x00);
	crc = crc16(crc, 0x01);
	crc = crc16(crc, 0x02);
	crc = crc16(crc, 0xCA);
	crc = crc16(crc, 0x6F);
	printf("\nTMP: %04X", crc);
	if ( crc == 0x0000 ) printf(" CRC OK");

Результат запуска:

Код:

Write:
 A1 ( FFFF, 443B )
 A1 ( 443B, 968B )
 A1 ( 968B, CDB4 )
 FE ( CDB4, B230 )
 00 ( B230, B799 )
 00 ( B799, 4E3C )
 01 ( 4E3C, 852B )
 02 ( 852B, CA6F )
CRC: CA6F

Read:
 A1 ( FFFF, 443B )
 A1 ( 443B, 968B )
 A1 ( 968B, CDB4 )
 FE ( CDB4, B230 )
 00 ( B230, B799 )
 00 ( B799, 4E3C )
 01 ( 4E3C, 852B )
 02 ( 852B, CA6F )
 CA ( CA6F, 6F00 )
 6F ( 6F00, 0000 )
TMP: 0000 CRC OK

ВП1-128 "внутри себя" использует инверсный вариант CRC-16, но перед записью на диск инвертирует CRC, поэтому на диск пишется в точности то же, что генерит стандартный алгоритм CRC-16:

Код:

CRC-16
width=16 poly=0x1021 init=0xFFFF refin=false refout=false
xorout=0x0000 check=0x29B1

**Vslav** · 14.12.2013, 01:22

В оригинале - это алгоритм CRC-16:

Код:

CRC-16
width=16 poly=0x1021 init=0xFFFF refin=false refout=false
xorout=0x0000 check=0x29B1

У меня вопрос есть. Описание алгоритма по Вильямсу это хорошо. Но у нас очевидно используется не банальное деление на полином 0x1021 и получение остатка. Алгоритм модифицирован так что на выходе получается некоторое магическое число, которое будучи пропущено вместе с блоком данных дает в итоге конкретное фиксированное значение. Я когда-то с этим разбирался, там небольшая математическая хитрость, но сейчас в упор не могу найти эту информацию. Не внесет ли кто ясность?

Update: кажется тут деление не самого сообщения (блока данных), а деление сообщения умноженого на разрядность образующего полинома (в данном случае на x^16). То есть находим остаток не от деления блока данных, а от деления блока данных умноженного на x^16. Потом когда мы из него вычитаем (в полиномиальной арифметике эквивалентно добавлению) остаток от деления, то результат делится на полином нацело, и остаток для проверки нулевой (или 0xFFFF в инверсном варианте). Но пока свести программу к делению на 1021 у меня не получается с нужным результатом.

---------- Post added at 23:22 ---------- Previous post was at 23:18 ----------

Сообщение от Patron

Чтобы далеко не ходить - возьмём заголовок первого сектора:

Код:

A1 A1 A1 FE 00 00 01 02 CA 6F

Любопытно, какой глубокий смысл в трех маркерах, если они все включаются в контрольную сумму. Если первый не раcпознан - сумма некорректная. Ну разве что проигнорировать сумму и пытаться вытащить из сектора хоть что-то.

**Patron** · 14.12.2013, 11:32

Сообщение от Vslav

у нас очевидно используется не банальное деление на полином 0x1021 и получение остатка

Ну, это как посмотреть. Вот внутренний алгоритм ВП1-128 в каноническом виде:

Код:

unsigned short int crc16( unsigned short crc, unsigned char data )
{
	printf("\n %02X ( %04X,", data, crc);

	crc = ~crc;
	crc ^= unsigned short (data) << 8;

	for( int i = 0 ; i < 8 ; i++ )
	{
		if( crc & 0x8000 ) { crc = (crc << 1) ^ 0x1021; }
		else               { crc = (crc << 1);          }
	}
	crc = ~crc;
	
	printf(" %04X )", crc );
	return crc;
}

int main(int argc, char *argv[])
{
	unsigned short crc, tmp;

	crc = 0x0000;
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0x30);
	crc = crc16(crc, 0x31);
	crc = crc16(crc, 0x32);
	crc = crc16(crc, 0x33);
	tmp = ~crc;
	printf("\nCRC: %04X", tmp);
}

А вот - стандартный алгоритм CRC-16 в каноническом виде:

Код:

unsigned short int crc16( unsigned short crc, unsigned char data )
{
	printf("\n %02X ( %04X,", data, crc);

	crc ^= unsigned short (data) << 8;

	for( int i = 0 ; i < 8 ; i++ )
	{
		if( crc & 0x8000 ) { crc = (crc << 1) ^ 0x1021; }
		else               { crc = (crc << 1);          }
	}
	
	printf(" %04X )", crc );
	return crc;
}

int main(int argc, char *argv[])
{
	unsigned short crc, tmp;

	crc = 0xFFFF;
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0x30);
	crc = crc16(crc, 0x31);
	crc = crc16(crc, 0x32);
	crc = crc16(crc, 0x33);
	tmp = crc;
	printf("\nCRC: %04X", tmp);
}

Оба алгоритма пишут на диск одно и то же, но алгоритм ВП1-128 использует начальное значение 0 и дважды инвертирует CRC, а стандартный алгоритм CRC-16 - использует начальное значение -1 и ни разу не инвертирует CRC.

...

**Vslav** · 14.12.2013, 12:10

Алгоритм-то мы вытащили, уже у нас есть достоверные и софтовые и аппаратные реализации, но я хочу докопаться до математической сути.

Если упрощенно и в терминах обычной арифметики, то у нас есть некоторое число m - сообщение (передаваемый блок полезных данных). Есть некоторая константа делитель p. Мы берем вычисляем остаток от деления: r = m mod p. Понятно что остаток от деления: (m - r) mod p будет нулевым и на этом можно выполнять простую проверку.

CRC - это остаток полиномиального деления на полином. У нас в данном случае используется методика проверки CRC "one-pass" - это когда сама CRC принимается и загоняется в тот же поток вместе с данными, а результирующая CRC сравнивается с константой. Чтобы такая методика работала надо делить не само сообщение, а конкатенацию: i | m | c, где i представляет собой начальное значение, а c - некоторая дополняющая константа (магическое число, разрядностью такой же как и у остатка, которое получится на приемном конце после вычисления CRC для блока + принятая сумма), часто c нулевое (как и в нашем случае). Принимающая сторона уже выполняет деление i | m | (c - r) и в итоге получает в остатке константу c.

Классическое полиномиальное деление "в столбик" (методы сдвигов и табличный - суть оптимизация, нам сейчас надо понять первичный алгоритм):

Код:

unsigned short int crc16_m2(unsigned short crc, unsigned char data)
{
  int i;
  for(i=0; i<8; i++)
  {
    if (crc & 0x8000)
    {
      crc <<= 1;
      crc |= (data >> 7) & 1;
      crc ^= 0x1021;
    }
    else
    {
      crc <<= 1;
      crc |= (data >> 7) & 1;
    }
    data <<= 1;
  }
  return crc;
}

Вот я и хочу привести процедуру к использованию этой канонической функции. В Вашем коде делится сообщение уже сдвинутое на 16 разрядов влево, то есть имеет место добавление той самой константы c состоящей из 16 нулевых битов. В-общем, тут загвоздка похоже просто чтоi достаточно хитрое и не является простым префиксом из 0xFFFF, поэтому у меня не получается аналогичный результат. А так - да, ясно что вдвигание данных по факту в 17-бит - это и есть учет последних нулевых бит, которые отдельно в конце у нас не вдвигаются.

**Patron** · 14.12.2013, 13:39

Сообщение от Vslav

В Вашем коде делится сообщение уже сдвинутое на 16 разрядов влево, то есть имеет место добавление той самой константы c состоящей из 16 нулевых битов.

Вот классический "безразмерный" вариант, вычисляющий CRC-16 для произвольной последовательности битов.

Внутренний вариант ВП1-128:

Код:

unsigned short int crc16_bitstep( unsigned short crc, int bit )
{
	int crc_high_bit = ( crc & 0x8000 ? 1 : 0 );
	int DoInvert     = bit ^ crc_high_bit;

	if( DoInvert ) { crc = (crc << 1) ^ 0x1021; }
	else           { crc = (crc << 1);          }

	return crc;
}

unsigned short int crc16( unsigned short crc, unsigned char data )
{
	printf("\n %02X ( %04X,", data, crc);

	crc = ~crc;
	for( unsigned char mask = 0x80 ; mask ; mask >>= 1 )
	{
		int bit = ( data & mask ? 1 : 0 );
		crc = crc16_bitstep( crc, bit );
	}
	crc = ~crc;
	
	printf(" %04X )", crc );
	return crc;
}

int main(int argc, char *argv[])
{
	unsigned short crc, tmp;

	crc = 0x0000;
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0x30);
	crc = crc16(crc, 0x31);
	crc = crc16(crc, 0x32);
	crc = crc16(crc, 0x33);
	tmp = ~crc;
	printf("\nCRC: %04X", tmp);
}

Стандартный алгоритм CRC-16:

Код:

unsigned short int crc16_bitstep( unsigned short crc, int bit )
{
	int crc_high_bit = ( crc & 0x8000 ? 1 : 0 );
	int DoInvert     = bit ^ crc_high_bit;

	if( DoInvert ) { crc = (crc << 1) ^ 0x1021; }
	else           { crc = (crc << 1);          }

	return crc;
}

unsigned short int crc16( unsigned short crc, unsigned char data )
{
	printf("\n %02X ( %04X,", data, crc);

	for( unsigned char mask = 0x80 ; mask ; mask >>= 1 )
	{
		int bit = ( data & mask ? 1 : 0 );
		crc = crc16_bitstep( crc, bit );
	}
	
	printf(" %04X )", crc );
	return crc;
}

int main(int argc, char *argv[])
{
	unsigned short crc, tmp;

	crc = 0xFFFF;
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0xA1);
	crc = crc16(crc, 0x30);
	crc = crc16(crc, 0x31);
	crc = crc16(crc, 0x32);
	crc = crc16(crc, 0x33);
	tmp = crc;
	printf("\nCRC: %04X", tmp);
}

**Vslav** · 14.12.2013, 14:13

Сообщение от Patron

Вот классический "безразмерный" вариант, вычисляющий CRC-16 для произвольной последовательности битов.

Внутренний вариант ВП1-128:

Код:

unsigned short int crc16_bitstep( unsigned short crc, int bit )
{
	int crc_high_bit = ( crc & 0x8000 ? 1 : 0 );
	int DoInvert     = bit ^ crc_high_bit;

	if( DoInvert ) { crc = (crc << 1) ^ 0x1021; }
	else           { crc = (crc << 1);          }

	return crc;
}

Да, спасибо, в хороший вид привели (кстати, делятся инвертированные данные, иначе было бы - if(!DoInvert ))

Я вижу отличие в том что каждый новый бит данных добавляется в СТАРШИЙ разряд сдвигового регистра. А когда мы "по-школьному" делим "в столбик" новый разряд (цифру) мы всегда добавляем справа - то есть в МЛАДШИЙ разряд. На самом деле понятно почему так - мы же после блока данных не вдвигаем еще дополнительных два нулевых байта, вместо этого мы умножаем каждый бит данных на 0x10000 сразу при вдвигании, поэтому дополнительные байты не нужны. То есть математика тут у нас та же - полиномиальное деление конкатенации сообщения и шестнадцати дополнительных замыкающих нулей. Просто хотелось бы привести к обычному делению "в столбик" (с вкидыванием нового разряда вправо), но видимо такая модификация алгоритма к нему не приводится.

Впрочем, по Вашему последнему коду сейчас видно, что если на вход подать 16-битное значение совпадающее с тем что в регистре на данный момент, то ни один xor не будет выполнен и получим 0. Об алгоритме как там сумма вычислялась вообще можно в таком случае не думать.

**Patron** · 14.12.2013, 14:52

Сообщение от Vslav

Я вижу отличие в том что каждый новый бит данных добавляется в СТАРШИЙ разряд сдвигового регистра.

Биты вообще не добавляются.

Аппаратный алгоритм такой:

1. 16-разрядный регистр CRC сдвигается влево, старший разряд при этом выходит в триггер.
2. Выход триггера бывшего старшего разряда CRC и старший бит сдвигового регистра ( т.е. текущий бит данных ) логически складываются и их исключающее ИЛИ управляет инверсией 0-го, 5-го и 12-го битов регистра CRC.

Вот и весь алгоритм CRC-16.

---------- Post added at 13:52 ---------- Previous post was at 13:32 ----------

Перед делением полиномов - делимое ( у нас - один бит ) сдвигается влево на кол-во разрядов, равное степени делителя ( у нас - на 16 разрядов ).

**Vslav** · 14.12.2013, 15:51

Сообщение от Patron

Биты вообще не добавляются.

Добавляются, добавляются. В этом суть деления "в столбик".

Сообщение от Patron

1. 16-разрядный регистр CRC сдвигается влево, старший разряд при этом выходит в триггер.

На самом деле регистр делителя 17-битный. Но старший 16-й бит (нумерация битов здесь и далее с 0 - 0..16) при делении всегда нулевой, потому что регистр всегда содержит только остаток. А перед сдвигом достаточно проверить 15-й бит, поэтому старший 16-й бит регистра обычно не реализовывают ни в софте, ни в железе. В наших примерах можно объявить переменную crc 32-битным и проверять 0x10000 ПОСЛЕ сдвига - это сути деления более соответствует, чем проверять 0x8000 ДО сдвига.

Итерация деления такая (нас только остаток интересует) - cначала в регистре некоторое имеем 17-битное значение - 0xxxx. Поскольку старший бит нулевой то ПОЛНЫЙ 17-битный полином 0x11021 мы вычесть не можем. Поэтому сдвигаем 17-битное значение влево, а в младший разряд добавляем новый бит данных. Ну как в школе - берем из делимого очередную цифру и приписываем к остатку справа. Ессно, в школе цифры десятичные, а тут двоичные. Если в 17-ом разряде оказывается единица - то мы вычитаем ПОЛНЫЙ полином 0x11021. Операция вычитания/сложения в полиномиальной арифметике это XOR. Поэтому 17-бит всегда в начале и конце итерации нулевой.

Так вот, в реализации ВП1-128 (ну и вообще, видимо, в алгоритмах CRC заточенных под one-pass checking) происходит сдвиг, при этом добавление новой цифры (из входящего битового потока) происходит не справа в младший разряд, а самый старший - в нереализуемый 17-бит. Что соответствует умножению бита данных на 0x10000 (как в обычной так и в полиномиальной арифметике).

Сообщение от Patron

2. Выход триггера бывшего старшего разряда CRC и старший бит сдвигового регистра ( т.е. текущий бит данных ) логически складываются

Старший разряд 16-битного регистра CRC - это будет как раз 16-й виртуальный бит после сдвига. А очередной бит данных добавляемый к 16-му разряду - это и есть результат неявного умножения битов сообщения на 0x10000. XOR - это и есть сумма. Это есть по сути внесение новой цифры - приписывание цифры справа в школе означает умножение текущего остатка на 10 и добавление цифры. Так и тут - умножили остаток на 2 и добавили новую цифру, только не просто так, а умноженную на 0x10000 - попадает на 16-й разряд . Потом смотрим на получившийся 16-бит - результат - 1? значит можно вычитать (операция XOR для полиномов) полный полином 0x11021. 0? - ничего не делаем - вычесть нельзя. Ну как в школе - приписали цифру, вычесть не можем? значит цифра частного - 0, а остаток не меняем.

Сообщение от Patron

Перед делением полиномов - делимое ( у нас - один бит ) сдвигается влево на кол-во разрядов, равное степени делителя ( у нас - на 16 разрядов ).

Не-а, это не перед делением полиномов. Это именно частность алгоритма CRC - дополнительное неявное умножение (сдвиг влево) на разрядность остатка, чтобы потом прошло one-pass checking (получение 0 в результате вычисления суммы на приемном конце).

Вот так выглядит Ваша функция в ПОЛНОМ виде:

Код:

unsigned short int crc16_bitstep( unsigned short crc, int bit )
{
	unsigned long reg;
	//
	// Перенесли в более длинный регистр (нам надо 17 бит)
	//
	reg = crc;
	//
	// Умножили текущий остаток на x (на 2)
	//
	reg = reg << 1;
	//
	// Добавили к остатку новые данные умноженные на x^16 (0x10000)
	//
	reg = reg ^ ((unsigned long)bit << 16);

	if (reg & 0x10000)
	{
		//
		// Можем вычесть полином x^16 + x^12 + x^5 + x^0
		//
		reg ^= 0x11021;
	}
	crc = (unsigned short)reg;
	return crc;
}

Если же обычное деление полиномов - то без умножения на 0x10000, пишется просто: reg = reg ^ (unsigned long)bit;
Насчет что добавляются инвертированные данные был неправ, похоже делится все в прямом виде.

ZXPRESS •	ZXART •
ZXTUNES •	ZX Spectrum Old Demos •
Virtual TR-DOS •	World of Spectrum •

User Tag List

Тема: Эмуляция 1801ВП1-128 в ПЛИС

Опции темы

Отображение

Информация о теме

Пользователи, просматривающие эту тему

Похожие темы

ЮТ-88: Реализация на ПЛИС (DE1)

Вопрос по ПЛИС

Аксель на ПЛИС

Список версий 1801ВП1 и 1801РЕ2

1801вп1-128

Ваши права