[mirror_ubuntu-bionic-kernel.git] / lib / libcrc32c.c

/* 
 * CRC32C
 *@Article{castagnoli-crc,
 * author =       { Guy Castagnoli and Stefan Braeuer and Martin Herrman},
 * title =        {{Optimization of Cyclic Redundancy-Check Codes with 24
 *                 and 32 Parity Bits}},
 * journal =      IEEE Transactions on Communication,
 * year =         {1993},
 * volume =       {41},
 * number =       {6},
 * pages =        {},
 * month =        {June},
 *}
 * Used by the iSCSI driver, possibly others, and derived from the
 * the iscsi-crc.c module of the linux-iscsi driver at
 * http://linux-iscsi.sourceforge.net.
 *
 * Following the example of lib/crc32, this function is intended to be
 * flexible and useful for all users.  Modules that currently have their
 * own crc32c, but hopefully may be able to use this one are:
 *  net/sctp (please add all your doco to here if you change to
 *            use this one!)
 *  <endoflist>
 *
 * Copyright (c) 2004 Cisco Systems, Inc.
 * 
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option) 
 * any later version.
 *
 */
#include <linux/crc32c.h>
#include <linux/compiler.h>
#include <linux/module.h>

MODULE_AUTHOR("Clay Haapala <chaapala@cisco.com>");
MODULE_DESCRIPTION("CRC32c (Castagnoli) calculations");
MODULE_LICENSE("GPL");

#define CRC32C_POLY_BE 0x1EDC6F41
#define CRC32C_POLY_LE 0x82F63B78

#ifndef CRC_LE_BITS 
# define CRC_LE_BITS 8
#endif


/*
 * Haven't generated a big-endian table yet, but the bit-wise version
 * should at least work.
 */
#if defined CRC_BE_BITS && CRC_BE_BITS != 1
#undef CRC_BE_BITS
#endif
#ifndef CRC_BE_BITS
# define CRC_BE_BITS 1
#endif

EXPORT_SYMBOL(crc32c_le);

#if CRC_LE_BITS == 1
/*
 * Compute things bit-wise, as done in crc32.c.  We could share the tight 
 * loop below with crc32 and vary the POLY if we don't find value in terms
 * of space and maintainability in keeping the two modules separate.
 */
u32 __pure
crc32c_le(u32 crc, unsigned char const *p, size_t len)
{
	int i;
	while (len--) {
		crc ^= *p++;
		for (i = 0; i < 8; i++)
			crc = (crc >> 1) ^ ((crc & 1) ? CRC32C_POLY_LE : 0);
	}
	return crc;
}
#else

/*
 * This is the CRC-32C table
 * Generated with:
 * width = 32 bits
 * poly = 0x1EDC6F41
 * reflect input bytes = true
 * reflect output bytes = true
 */

static const u32 crc32c_table[256] = {
	0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
	0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
	0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
	0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
	0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
	0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
	0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
	0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
	0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
	0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
	0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
	0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
	0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
	0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
	0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
	0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
	0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
	0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
	0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
	0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
	0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
	0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
	0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
	0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
	0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
	0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
	0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
	0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
	0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
	0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
	0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
	0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
	0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
	0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
	0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
	0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
	0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
	0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
	0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
	0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
	0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
	0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
	0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
	0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
	0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
	0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
	0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
	0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
	0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
	0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
	0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
	0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
	0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
	0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
	0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
	0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
	0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
	0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
	0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
	0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
	0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
	0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
	0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
	0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
};

/*
 * Steps through buffer one byte at at time, calculates reflected 
 * crc using table.
 */

u32 __pure
crc32c_le(u32 crc, unsigned char const *data, size_t length)
{
	while (length--)
		crc =
		    crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);

	return crc;
}

#endif	/* CRC_LE_BITS == 8 */

EXPORT_SYMBOL(crc32c_be);

#if CRC_BE_BITS == 1
u32 __pure
crc32c_be(u32 crc, unsigned char const *p, size_t len)
{
	int i;
	while (len--) {
		crc ^= *p++ << 24;
		for (i = 0; i < 8; i++)
			crc =
			    (crc << 1) ^ ((crc & 0x80000000) ? CRC32C_POLY_BE :
					  0);
	}
	return crc;
}
#endif

/*
 * Unit test
 *
 * A small unit test suite is implemented as part of the crypto suite.
 * Select CRYPTO_CRC32C and use the tcrypt module to run the tests.
 */
Commit	Line	Data
1da177e4 LT	1	/*
	2	* CRC32C
	3	*@Article{castagnoli-crc,
	4	* author = { Guy Castagnoli and Stefan Braeuer and Martin Herrman},
	5	* title = {{Optimization of Cyclic Redundancy-Check Codes with 24
	6	* and 32 Parity Bits}},
	7	* journal = IEEE Transactions on Communication,
	8	* year = {1993},
	9	* volume = {41},
	10	* number = {6},
	11	* pages = {},
	12	* month = {June},
	13	*}
	14	* Used by the iSCSI driver, possibly others, and derived from the
	15	* the iscsi-crc.c module of the linux-iscsi driver at
	16	* http://linux-iscsi.sourceforge.net.
	17	*
	18	* Following the example of lib/crc32, this function is intended to be
	19	* flexible and useful for all users. Modules that currently have their
	20	* own crc32c, but hopefully may be able to use this one are:
	21	* net/sctp (please add all your doco to here if you change to
	22	* use this one!)
	23	* <endoflist>
	24	*
	25	* Copyright (c) 2004 Cisco Systems, Inc.
	26	*
	27	* This program is free software; you can redistribute it and/or modify it
	28	* under the terms of the GNU General Public License as published by the Free
	29	* Software Foundation; either version 2 of the License, or (at your option)
	30	* any later version.
	31	*
	32	*/
	33	#include <linux/crc32c.h>
	34	#include <linux/compiler.h>
	35	#include <linux/module.h>
1da177e4 LT	36
	37	MODULE_AUTHOR("Clay Haapala <chaapala@cisco.com>");
	38	MODULE_DESCRIPTION("CRC32c (Castagnoli) calculations");
	39	MODULE_LICENSE("GPL");
	40
	41	#define CRC32C_POLY_BE 0x1EDC6F41
	42	#define CRC32C_POLY_LE 0x82F63B78
	43
	44	#ifndef CRC_LE_BITS
	45	# define CRC_LE_BITS 8
	46	#endif
	47
	48
	49	/*
	50	* Haven't generated a big-endian table yet, but the bit-wise version
	51	* should at least work.
	52	*/
	53	#if defined CRC_BE_BITS && CRC_BE_BITS != 1
	54	#undef CRC_BE_BITS
	55	#endif
	56	#ifndef CRC_BE_BITS
	57	# define CRC_BE_BITS 1
	58	#endif
	59
	60	EXPORT_SYMBOL(crc32c_le);
	61
	62	#if CRC_LE_BITS == 1
	63	/*
	64	* Compute things bit-wise, as done in crc32.c. We could share the tight
	65	* loop below with crc32 and vary the POLY if we don't find value in terms
	66	* of space and maintainability in keeping the two modules separate.
	67	*/
e8c44319	68	u32 __pure
1da177e4 LT	69	crc32c_le(u32 crc, unsigned char const *p, size_t len)
	70	{
	71	int i;
	72	while (len--) {
	73	crc ^= *p++;
	74	for (i = 0; i < 8; i++)
	75	crc = (crc >> 1) ^ ((crc & 1) ? CRC32C_POLY_LE : 0);
	76	}
	77	return crc;
	78	}
	79	#else
	80
	81	/*
	82	* This is the CRC-32C table
	83	* Generated with:
	84	* width = 32 bits
	85	* poly = 0x1EDC6F41
	86	* reflect input bytes = true
	87	* reflect output bytes = true
	88	*/
	89
5f507d9e	90	static const u32 crc32c_table[256] = {
1da177e4 LT	91	0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
	92	0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
	93	0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
	94	0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
	95	0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
	96	0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
	97	0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
	98	0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
	99	0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
	100	0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
	101	0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
	102	0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
	103	0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
	104	0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
	105	0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
	106	0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
	107	0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
	108	0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
	109	0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
	110	0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
	111	0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
	112	0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
	113	0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
	114	0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
	115	0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
	116	0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
	117	0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
	118	0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
	119	0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
	120	0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
	121	0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
	122	0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
	123	0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
	124	0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
	125	0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
	126	0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
	127	0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
	128	0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
	129	0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
	130	0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
	131	0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
	132	0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
	133	0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
	134	0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
	135	0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
	136	0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
	137	0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
	138	0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
	139	0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
	140	0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
	141	0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
	142	0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
	143	0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
	144	0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
	145	0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
	146	0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
	147	0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
	148	0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
	149	0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
	150	0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
	151	0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
	152	0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
	153	0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
	154	0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
155	};
156
157	/*
158	* Steps through buffer one byte at at time, calculates reflected
159	* crc using table.
160	*/
161
e8c44319	162	u32 __pure
ef19454b	163	crc32c_le(u32 crc, unsigned char const *data, size_t length)
1da177e4	164	{
1da177e4 LT	165	while (length--)
	166	crc =
	167	crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
	168
ef19454b	169	return crc;
1da177e4 LT	170	}
	171
	172	#endif /* CRC_LE_BITS == 8 */
	173
	174	EXPORT_SYMBOL(crc32c_be);
	175
	176	#if CRC_BE_BITS == 1
e8c44319	177	u32 __pure
1da177e4 LT	178	crc32c_be(u32 crc, unsigned char const *p, size_t len)
	179	{
	180	int i;
	181	while (len--) {
	182	crc ^= *p++ << 24;
	183	for (i = 0; i < 8; i++)
	184	crc =
	185	(crc << 1) ^ ((crc & 0x80000000) ? CRC32C_POLY_BE :
	186	0);
	187	}
	188	return crc;
	189	}
	190	#endif
	191
	192	/*
	193	* Unit test
	194	*
	195	* A small unit test suite is implemented as part of the crypto suite.
	196	* Select CRYPTO_CRC32C and use the tcrypt module to run the tests.
	197	*/