[linux-2.6-block.git] / fs / udf / crc.c

/*
 * crc.c
 *
 * PURPOSE
 *	Routines to generate, calculate, and test a 16-bit CRC.
 *
 * DESCRIPTION
 *	The CRC code was devised by Don P. Mitchell of AT&T Bell Laboratories
 *	and Ned W. Rhodes of Software Systems Group. It has been published in
 *	"Design and Validation of Computer Protocols", Prentice Hall,
 *	Englewood Cliffs, NJ, 1991, Chapter 3, ISBN 0-13-539925-4.
 *
 *	Copyright is held by AT&T.
 *
 *	AT&T gives permission for the free use of the CRC source code.
 *
 * COPYRIGHT
 *	This file is distributed under the terms of the GNU General Public
 *	License (GPL). Copies of the GPL can be obtained from:
 *		ftp://prep.ai.mit.edu/pub/gnu/GPL
 *	Each contributing author retains all rights to their own work.
 */

#include "udfdecl.h"

static const uint16_t crc_table[256] = {
	0x0000U, 0x1021U, 0x2042U, 0x3063U, 0x4084U, 0x50a5U, 0x60c6U, 0x70e7U,
	0x8108U, 0x9129U, 0xa14aU, 0xb16bU, 0xc18cU, 0xd1adU, 0xe1ceU, 0xf1efU,
	0x1231U, 0x0210U, 0x3273U, 0x2252U, 0x52b5U, 0x4294U, 0x72f7U, 0x62d6U,
	0x9339U, 0x8318U, 0xb37bU, 0xa35aU, 0xd3bdU, 0xc39cU, 0xf3ffU, 0xe3deU,
	0x2462U, 0x3443U, 0x0420U, 0x1401U, 0x64e6U, 0x74c7U, 0x44a4U, 0x5485U,
	0xa56aU, 0xb54bU, 0x8528U, 0x9509U, 0xe5eeU, 0xf5cfU, 0xc5acU, 0xd58dU,
	0x3653U, 0x2672U, 0x1611U, 0x0630U, 0x76d7U, 0x66f6U, 0x5695U, 0x46b4U,
	0xb75bU, 0xa77aU, 0x9719U, 0x8738U, 0xf7dfU, 0xe7feU, 0xd79dU, 0xc7bcU,
	0x48c4U, 0x58e5U, 0x6886U, 0x78a7U, 0x0840U, 0x1861U, 0x2802U, 0x3823U,
	0xc9ccU, 0xd9edU, 0xe98eU, 0xf9afU, 0x8948U, 0x9969U, 0xa90aU, 0xb92bU,
	0x5af5U, 0x4ad4U, 0x7ab7U, 0x6a96U, 0x1a71U, 0x0a50U, 0x3a33U, 0x2a12U,
	0xdbfdU, 0xcbdcU, 0xfbbfU, 0xeb9eU, 0x9b79U, 0x8b58U, 0xbb3bU, 0xab1aU,
	0x6ca6U, 0x7c87U, 0x4ce4U, 0x5cc5U, 0x2c22U, 0x3c03U, 0x0c60U, 0x1c41U,
	0xedaeU, 0xfd8fU, 0xcdecU, 0xddcdU, 0xad2aU, 0xbd0bU, 0x8d68U, 0x9d49U,
	0x7e97U, 0x6eb6U, 0x5ed5U, 0x4ef4U, 0x3e13U, 0x2e32U, 0x1e51U, 0x0e70U,
	0xff9fU, 0xefbeU, 0xdfddU, 0xcffcU, 0xbf1bU, 0xaf3aU, 0x9f59U, 0x8f78U,
	0x9188U, 0x81a9U, 0xb1caU, 0xa1ebU, 0xd10cU, 0xc12dU, 0xf14eU, 0xe16fU,
	0x1080U, 0x00a1U, 0x30c2U, 0x20e3U, 0x5004U, 0x4025U, 0x7046U, 0x6067U,
	0x83b9U, 0x9398U, 0xa3fbU, 0xb3daU, 0xc33dU, 0xd31cU, 0xe37fU, 0xf35eU,
	0x02b1U, 0x1290U, 0x22f3U, 0x32d2U, 0x4235U, 0x5214U, 0x6277U, 0x7256U,
	0xb5eaU, 0xa5cbU, 0x95a8U, 0x8589U, 0xf56eU, 0xe54fU, 0xd52cU, 0xc50dU,
	0x34e2U, 0x24c3U, 0x14a0U, 0x0481U, 0x7466U, 0x6447U, 0x5424U, 0x4405U,
	0xa7dbU, 0xb7faU, 0x8799U, 0x97b8U, 0xe75fU, 0xf77eU, 0xc71dU, 0xd73cU,
	0x26d3U, 0x36f2U, 0x0691U, 0x16b0U, 0x6657U, 0x7676U, 0x4615U, 0x5634U,
	0xd94cU, 0xc96dU, 0xf90eU, 0xe92fU, 0x99c8U, 0x89e9U, 0xb98aU, 0xa9abU,
	0x5844U, 0x4865U, 0x7806U, 0x6827U, 0x18c0U, 0x08e1U, 0x3882U, 0x28a3U,
	0xcb7dU, 0xdb5cU, 0xeb3fU, 0xfb1eU, 0x8bf9U, 0x9bd8U, 0xabbbU, 0xbb9aU,
	0x4a75U, 0x5a54U, 0x6a37U, 0x7a16U, 0x0af1U, 0x1ad0U, 0x2ab3U, 0x3a92U,
	0xfd2eU, 0xed0fU, 0xdd6cU, 0xcd4dU, 0xbdaaU, 0xad8bU, 0x9de8U, 0x8dc9U,
	0x7c26U, 0x6c07U, 0x5c64U, 0x4c45U, 0x3ca2U, 0x2c83U, 0x1ce0U, 0x0cc1U,
	0xef1fU, 0xff3eU, 0xcf5dU, 0xdf7cU, 0xaf9bU, 0xbfbaU, 0x8fd9U, 0x9ff8U,
	0x6e17U, 0x7e36U, 0x4e55U, 0x5e74U, 0x2e93U, 0x3eb2U, 0x0ed1U, 0x1ef0U
};

/*
 * udf_crc
 *
 * PURPOSE
 *	Calculate a 16-bit CRC checksum using ITU-T V.41 polynomial.
 *
 * DESCRIPTION
 *	The OSTA-UDF(tm) 1.50 standard states that using CRCs is mandatory.
 *	The polynomial used is:	x^16 + x^12 + x^15 + 1
 *
 * PRE-CONDITIONS
 *	data		Pointer to the data block.
 *	size		Size of the data block.
 *
 * POST-CONDITIONS
 *	<return>	CRC of the data block.
 *
 * HISTORY
 *	July 21, 1997 - Andrew E. Mileski
 *	Adapted from OSTA-UDF(tm) 1.50 standard.
 */
uint16_t udf_crc(const uint8_t *data, uint32_t size, uint16_t crc)
{
	while (size--)
		crc = crc_table[(crc >> 8 ^ *(data++)) & 0xffU] ^ (crc << 8);

	return crc;
}

/****************************************************************************/
#if defined(TEST)

/*
 * PURPOSE
 *	Test udf_crc()
 *
 * HISTORY
 *	July 21, 1997 - Andrew E. Mileski
 *	Adapted from OSTA-UDF(tm) 1.50 standard.
 */

unsigned char bytes[] = { 0x70U, 0x6AU, 0x77U };

int main(void)
{
	unsigned short x;

	x = udf_crc(bytes, sizeof bytes);
	printf("udf_crc: calculated = %4.4x, correct = %4.4x\n", x, 0x3299U);

	return 0;
}

#endif /* defined(TEST) */

/****************************************************************************/
#if defined(GENERATE)

/*
 * PURPOSE
 *	Generate a table for fast 16-bit CRC calculations (any polynomial).
 *
 * DESCRIPTION
 *	The ITU-T V.41 polynomial is 010041.
 *
 * HISTORY
 *	July 21, 1997 - Andrew E. Mileski
 *	Adapted from OSTA-UDF(tm) 1.50 standard.
 */

#include <stdio.h>

int main(int argc, char **argv)
{
	unsigned long crc, poly;
	int n, i;

	/* Get the polynomial */
	sscanf(argv[1], "%lo", &poly);
	if (poly & 0xffff0000U) {
		fprintf(stderr, "polynomial is too large\en");
		exit(1);
	}

	printf("/* CRC 0%o */\n", poly);

	/* Create a table */
	printf("static unsigned short crc_table[256] = {\n");
	for (n = 0; n < 256; n++) {
		if (n % 8 == 0)
			printf("\t");
		crc = n << 8;
		for (i = 0; i < 8; i++) {
			if (crc & 0x8000U)
				crc = (crc << 1) ^ poly;
			else
				crc <<= 1;
			crc &= 0xFFFFU;
		}
		if (n == 255)
			printf("0x%04xU ", crc);
		else
			printf("0x%04xU, ", crc);
		if (n % 8 == 7)
			printf("\n");
	}
	printf("};\n");

	return 0;
}

#endif /* defined(GENERATE) */
Commit	Line	Data
1da177e4 LT	1	/*
	2	* crc.c
	3	*
	4	* PURPOSE
	5	* Routines to generate, calculate, and test a 16-bit CRC.
	6	*
	7	* DESCRIPTION
	8	* The CRC code was devised by Don P. Mitchell of AT&T Bell Laboratories
	9	* and Ned W. Rhodes of Software Systems Group. It has been published in
	10	* "Design and Validation of Computer Protocols", Prentice Hall,
	11	* Englewood Cliffs, NJ, 1991, Chapter 3, ISBN 0-13-539925-4.
	12	*
	13	* Copyright is held by AT&T.
	14	*
	15	* AT&T gives permission for the free use of the CRC source code.
	16	*
1da177e4 LT	17	* COPYRIGHT
	18	* This file is distributed under the terms of the GNU General Public
	19	* License (GPL). Copies of the GPL can be obtained from:
	20	* ftp://prep.ai.mit.edu/pub/gnu/GPL
	21	* Each contributing author retains all rights to their own work.
	22	*/
	23
	24	#include "udfdecl.h"
	25
c8ed837d	26	static const uint16_t crc_table[256] = {
1da177e4 LT	27	0x0000U, 0x1021U, 0x2042U, 0x3063U, 0x4084U, 0x50a5U, 0x60c6U, 0x70e7U,
	28	0x8108U, 0x9129U, 0xa14aU, 0xb16bU, 0xc18cU, 0xd1adU, 0xe1ceU, 0xf1efU,
	29	0x1231U, 0x0210U, 0x3273U, 0x2252U, 0x52b5U, 0x4294U, 0x72f7U, 0x62d6U,
	30	0x9339U, 0x8318U, 0xb37bU, 0xa35aU, 0xd3bdU, 0xc39cU, 0xf3ffU, 0xe3deU,
	31	0x2462U, 0x3443U, 0x0420U, 0x1401U, 0x64e6U, 0x74c7U, 0x44a4U, 0x5485U,
	32	0xa56aU, 0xb54bU, 0x8528U, 0x9509U, 0xe5eeU, 0xf5cfU, 0xc5acU, 0xd58dU,
	33	0x3653U, 0x2672U, 0x1611U, 0x0630U, 0x76d7U, 0x66f6U, 0x5695U, 0x46b4U,
	34	0xb75bU, 0xa77aU, 0x9719U, 0x8738U, 0xf7dfU, 0xe7feU, 0xd79dU, 0xc7bcU,
	35	0x48c4U, 0x58e5U, 0x6886U, 0x78a7U, 0x0840U, 0x1861U, 0x2802U, 0x3823U,
	36	0xc9ccU, 0xd9edU, 0xe98eU, 0xf9afU, 0x8948U, 0x9969U, 0xa90aU, 0xb92bU,
	37	0x5af5U, 0x4ad4U, 0x7ab7U, 0x6a96U, 0x1a71U, 0x0a50U, 0x3a33U, 0x2a12U,
	38	0xdbfdU, 0xcbdcU, 0xfbbfU, 0xeb9eU, 0x9b79U, 0x8b58U, 0xbb3bU, 0xab1aU,
	39	0x6ca6U, 0x7c87U, 0x4ce4U, 0x5cc5U, 0x2c22U, 0x3c03U, 0x0c60U, 0x1c41U,
	40	0xedaeU, 0xfd8fU, 0xcdecU, 0xddcdU, 0xad2aU, 0xbd0bU, 0x8d68U, 0x9d49U,
	41	0x7e97U, 0x6eb6U, 0x5ed5U, 0x4ef4U, 0x3e13U, 0x2e32U, 0x1e51U, 0x0e70U,
	42	0xff9fU, 0xefbeU, 0xdfddU, 0xcffcU, 0xbf1bU, 0xaf3aU, 0x9f59U, 0x8f78U,
	43	0x9188U, 0x81a9U, 0xb1caU, 0xa1ebU, 0xd10cU, 0xc12dU, 0xf14eU, 0xe16fU,
	44	0x1080U, 0x00a1U, 0x30c2U, 0x20e3U, 0x5004U, 0x4025U, 0x7046U, 0x6067U,
	45	0x83b9U, 0x9398U, 0xa3fbU, 0xb3daU, 0xc33dU, 0xd31cU, 0xe37fU, 0xf35eU,
	46	0x02b1U, 0x1290U, 0x22f3U, 0x32d2U, 0x4235U, 0x5214U, 0x6277U, 0x7256U,
	47	0xb5eaU, 0xa5cbU, 0x95a8U, 0x8589U, 0xf56eU, 0xe54fU, 0xd52cU, 0xc50dU,
	48	0x34e2U, 0x24c3U, 0x14a0U, 0x0481U, 0x7466U, 0x6447U, 0x5424U, 0x4405U,
	49	0xa7dbU, 0xb7faU, 0x8799U, 0x97b8U, 0xe75fU, 0xf77eU, 0xc71dU, 0xd73cU,
	50	0x26d3U, 0x36f2U, 0x0691U, 0x16b0U, 0x6657U, 0x7676U, 0x4615U, 0x5634U,
	51	0xd94cU, 0xc96dU, 0xf90eU, 0xe92fU, 0x99c8U, 0x89e9U, 0xb98aU, 0xa9abU,
	52	0x5844U, 0x4865U, 0x7806U, 0x6827U, 0x18c0U, 0x08e1U, 0x3882U, 0x28a3U,
	53	0xcb7dU, 0xdb5cU, 0xeb3fU, 0xfb1eU, 0x8bf9U, 0x9bd8U, 0xabbbU, 0xbb9aU,
	54	0x4a75U, 0x5a54U, 0x6a37U, 0x7a16U, 0x0af1U, 0x1ad0U, 0x2ab3U, 0x3a92U,
	55	0xfd2eU, 0xed0fU, 0xdd6cU, 0xcd4dU, 0xbdaaU, 0xad8bU, 0x9de8U, 0x8dc9U,
	56	0x7c26U, 0x6c07U, 0x5c64U, 0x4c45U, 0x3ca2U, 0x2c83U, 0x1ce0U, 0x0cc1U,
	57	0xef1fU, 0xff3eU, 0xcf5dU, 0xdf7cU, 0xaf9bU, 0xbfbaU, 0x8fd9U, 0x9ff8U,
	58	0x6e17U, 0x7e36U, 0x4e55U, 0x5e74U, 0x2e93U, 0x3eb2U, 0x0ed1U, 0x1ef0U
	59	};
	60
	61	/*
	62	* udf_crc
	63	*
	64	* PURPOSE
	65	* Calculate a 16-bit CRC checksum using ITU-T V.41 polynomial.
	66	*
	67	* DESCRIPTION
	68	* The OSTA-UDF(tm) 1.50 standard states that using CRCs is mandatory.
	69	* The polynomial used is: x^16 + x^12 + x^15 + 1
	70	*
	71	* PRE-CONDITIONS
	72	* data Pointer to the data block.
	73	* size Size of the data block.
	74	*
	75	* POST-CONDITIONS
	76	* <return> CRC of the data block.
	77	*
	78	* HISTORY
	79	* July 21, 1997 - Andrew E. Mileski
	80	* Adapted from OSTA-UDF(tm) 1.50 standard.
	81	*/
c8ed837d	82	uint16_t udf_crc(const uint8_t *data, uint32_t size, uint16_t crc)
1da177e4 LT	83	{
	84	while (size--)
	85	crc = crc_table[(crc >> 8 ^ *(data++)) & 0xffU] ^ (crc << 8);
	86
	87	return crc;
	88	}
	89
	90	/****************************************************************************/
	91	#if defined(TEST)
	92
	93	/*
	94	* PURPOSE
	95	* Test udf_crc()
	96	*
	97	* HISTORY
	98	* July 21, 1997 - Andrew E. Mileski
	99	* Adapted from OSTA-UDF(tm) 1.50 standard.
	100	*/
	101
	102	unsigned char bytes[] = { 0x70U, 0x6AU, 0x77U };
	103
	104	int main(void)
	105	{
	106	unsigned short x;
	107
d375b970 CG	108	x = udf_crc(bytes, sizeof bytes);
d375b970 CG	109	printf("udf_crc: calculated = %4.4x, correct = %4.4x\n", x, 0x3299U);
1da177e4 LT	110
	111	return 0;
	112	}
	113
28de7948	114	#endif /* defined(TEST) */
1da177e4 LT	115
	116	/****************************************************************************/
	117	#if defined(GENERATE)
	118
	119	/*
	120	* PURPOSE
	121	* Generate a table for fast 16-bit CRC calculations (any polynomial).
	122	*
	123	* DESCRIPTION
	124	* The ITU-T V.41 polynomial is 010041.
	125	*
	126	* HISTORY
	127	* July 21, 1997 - Andrew E. Mileski
	128	* Adapted from OSTA-UDF(tm) 1.50 standard.
	129	*/
	130
	131	#include <stdio.h>
	132
	133	int main(int argc, char **argv)
	134	{
	135	unsigned long crc, poly;
	136	int n, i;
	137
	138	/* Get the polynomial */
	139	sscanf(argv[1], "%lo", &poly);
cb00ea35	140	if (poly & 0xffff0000U) {
1da177e4 LT	141	fprintf(stderr, "polynomial is too large\en");
	142	exit(1);
	143	}
	144
	145	printf("/* CRC 0%o */\n", poly);
	146
	147	/* Create a table */
	148	printf("static unsigned short crc_table[256] = {\n");
cb00ea35	149	for (n = 0; n < 256; n++) {
1da177e4 LT	150	if (n % 8 == 0)
	151	printf("\t");
	152	crc = n << 8;
cb00ea35 CG	153	for (i = 0; i < 8; i++) {
cb00ea35 CG	154	if (crc & 0x8000U)
1da177e4 LT	155	crc = (crc << 1) ^ poly;
	156	else
	157	crc <<= 1;
cb00ea35	158	crc &= 0xFFFFU;
1da177e4 LT	159	}
	160	if (n == 255)
	161	printf("0x%04xU ", crc);
	162	else
	163	printf("0x%04xU, ", crc);
cb00ea35	164	if (n % 8 == 7)
1da177e4 LT	165	printf("\n");
	166	}
	167	printf("};\n");
	168
	169	return 0;
	170	}
	171
28de7948	172	#endif /* defined(GENERATE) */