From mboxrd@z Thu Jan 1 00:00:00 1970 From: Matt_Domsch@Dell.com Date: Thu, 30 Nov 2000 21:40:08 +0000 Subject: [Linux-ia64] [PATCH] EFI GPT CRC32 function fix - take 2 Message-Id: List-Id: References: In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: linux-ia64@vger.kernel.org My previous submission had an ugly comment inserted when the crc code was put into OpenSSH, which said "All rights reserved". Rather than trust that no one would get upset over a one-line copyrighted function prototype, here's a pass that should guarantee license compliance. This applies against the last 2.4.0-test10-ia64 patch. Thanks, Matt diff -burN kernel24-2.4.0-test10/linux/fs/partitions/Makefile kernel24-2.4.0-test10-crcfix/linux/fs/partitions/Makefile --- kernel24-2.4.0-test10/linux/fs/partitions/Makefile Thu Nov 30 15:47:31 2000 +++ kernel24-2.4.0-test10-crcfix/linux/fs/partitions/Makefile Thu Nov 30 15:44:05 2000 @@ -8,7 +8,7 @@ # Note 2! The CFLAGS definitions are now in the main makefile... O_TARGET := partitions.o -OX_OBJS := check.o +OX_OBJS := check.o efi_crc32.o obj-$(CONFIG_ACORN_PARTITION) += acorn.o obj-$(CONFIG_AMIGA_PARTITION) += amiga.o diff -burN kernel24-2.4.0-test10/linux/fs/partitions/efi.c kernel24-2.4.0-test10-crcfix/linux/fs/partitions/efi.c --- kernel24-2.4.0-test10/linux/fs/partitions/efi.c Thu Nov 30 15:47:31 2000 +++ kernel24-2.4.0-test10-crcfix/linux/fs/partitions/efi.c Thu Nov 30 15:49:54 2000 @@ -4,8 +4,14 @@ * http://developer.intel.com/technology/efi/efi.htm * efi.[ch] by Matt Domsch * Copyright 2000 Dell Computer Corporation - * CRC routines taken from the EFI Sample Implementation, - * 1999.12.31, lib/crc.c + * + * Note, the EFI Specification, v0.99, has a reference to + * Dr. Dobbs Journal, May 1994 (actually it's in May 1992) + * but that isn't the CRC function being used by EFI. Intel's + * EFI Sample Implementation shows that they use the same function + * as was COPYRIGHT (C) 1986 Gary S. Brown. See the files efi_crc32.[ch] + * for further information. + * * * 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 @@ -25,6 +31,10 @@ * TODO: * * Changelog: + * Thu Nov 30 2000 Matt Domsch + * - Replaced Intel's CRC32 function with an equivalent + * non-license-restricted version. + * * Wed Oct 25 2000 Matt Domsch * - Fixed the LastLBA() call to return the proper last block * @@ -46,6 +56,7 @@ #include #include "check.h" +#include "efi_crc32.h" #include "efi.h" #if CONFIG_BLK_DEV_MD && CONFIG_AUTODETECT_RAID @@ -61,76 +72,7 @@ #define debug_printk(...) #endif -/* CRC routines taken from the EFI Sample Implementation, - * 1999.12.31, lib/crc.c - * - * Note, the EFI Specification, v0.99, has a reference to - * Dr. Dobbs Journal, May 1994 (actually it's in May 1992) - * but that isn't the CRC function being used by EFI. - */ - -static u32 CRCTable[256] = { - 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, - 0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, - 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, - 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, - 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, - 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, - 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C, - 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, - 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, - 0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, - 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106, - 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, - 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, - 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, - 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950, - 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, - 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, - 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, - 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA, - 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F, - 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, - 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, - 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84, - 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, - 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, - 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, - 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E, - 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, - 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, - 0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, - 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28, - 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, - 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, - 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, - 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242, - 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, - 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, - 0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, - 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, - 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, - 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, - 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, - 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D -}; - -static u32 -CalculateCrc (void *_pt, u32 Size) -{ - u8 *pt = (u8 *)_pt; - register u32 Crc; - /* compute crc */ - Crc = 0xffffffff; - while (Size) { - Crc = (Crc >> 8) ^ CRCTable[(__u8) Crc ^ *pt]; - pt += 1; - Size -= 1; - } - Crc = Crc ^ 0xffffffff; - return Crc; -} @@ -387,7 +329,7 @@ /* Check the GUID Partition Table CRC */ origcrc = (*gpt)->HeaderCRC32; (*gpt)->HeaderCRC32 = 0; - crc = CalculateCrc(*gpt, (*gpt)->HeaderSize); + crc = efi_crc32((const unsigned char *)(*gpt), (*gpt)->HeaderSize); if (crc != origcrc) { @@ -415,7 +357,8 @@ } /* Check the GUID Partition Entry Array CRC */ - crc = CalculateCrc(*ptes, (*gpt)->NumberOfPartitionEntries * + crc = efi_crc32((const unsigned char *)(*ptes), + (*gpt)->NumberOfPartitionEntries * (*gpt)->SizeOfPartitionEntry); if (crc != (*gpt)->PartitionEntryArrayCRC32) { diff -burN kernel24-2.4.0-test10/linux/fs/partitions/efi_crc32.c kernel24-2.4.0-test10-crcfix/linux/fs/partitions/efi_crc32.c --- kernel24-2.4.0-test10/linux/fs/partitions/efi_crc32.c Wed Dec 31 18:00:00 1969 +++ kernel24-2.4.0-test10-crcfix/linux/fs/partitions/efi_crc32.c Thu Nov 30 15:43:38 2000 @@ -0,0 +1,127 @@ +/* + * Nov 30, 2000 Matt Domsch + * - Copied crc32.c from the linux/drivers/net/cipe directory, + * now named efi_crc32.[ch] + * - Modified it by seeding the crc with ~0 instead of 0, and + * xor'ing the final value with ~0, per Intel EFI algorithm. + * - changed unsigned long to u32, added #include + * - changed len to be an unsigned long + * - changed crc32val to be a register + * - named the function efi_crc32() to be clear that it's different + * - License remains unchanged! It's still GPL-compatable! + */ + + /* =============================== */ + /* COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or */ + /* code or tables extracted from it, as desired without restriction. */ + /* */ + /* First, the polynomial itself and its table of feedback terms. The */ + /* polynomial is */ + /* X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0 */ + /* */ + /* Note that we take it "backwards" and put the highest-order term in */ + /* the lowest-order bit. The X^32 term is "implied"; the LSB is the */ + /* X^31 term, etc. The X^0 term (usually shown as "+1") results in */ + /* the MSB being 1. */ + /* */ + /* Note that the usual hardware shift register implementation, which */ + /* is what we're using (we're merely optimizing it by doing eight-bit */ + /* chunks at a time) shifts bits into the lowest-order term. In our */ + /* implementation, that means shifting towards the right. Why do we */ + /* do it this way? Because the calculated CRC must be transmitted in */ + /* order from highest-order term to lowest-order term. UARTs transmit */ + /* characters in order from LSB to MSB. By storing the CRC this way, */ + /* we hand it to the UART in the order low-byte to high-byte; the UART */ + /* sends each low-bit to hight-bit; and the result is transmission bit */ + /* by bit from highest- to lowest-order term without requiring any bit */ + /* shuffling on our part. Reception works similarly. */ + /* */ + /* The feedback terms table consists of 256, 32-bit entries. Notes: */ + /* */ + /* The table can be generated at runtime if desired; code to do so */ + /* is shown later. It might not be obvious, but the feedback */ + /* terms simply represent the results of eight shift/xor opera- */ + /* tions for all combinations of data and CRC register values. */ + /* */ + /* The values must be right-shifted by eight bits by the "updcrc" */ + /* logic; the shift must be unsigned (bring in zeroes). On some */ + /* hardware you could probably optimize the shift in assembler by */ + /* using byte-swap instructions. */ + /* polynomial $edb88320 */ + /* */ + /* -------------------------------------------------------------------- */ + +#include "efi_crc32.h" + +static u32 efi_crc32_tab[] = { + 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, + 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, + 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, + 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL, + 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L, + 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L, + 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L, + 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL, + 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L, + 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL, + 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L, + 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L, + 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L, + 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL, + 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL, + 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L, + 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL, + 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L, + 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L, + 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L, + 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL, + 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L, + 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L, + 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL, + 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L, + 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L, + 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L, + 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L, + 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L, + 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL, + 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL, + 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L, + 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L, + 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL, + 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL, + 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L, + 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL, + 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L, + 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL, + 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L, + 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL, + 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L, + 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L, + 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL, + 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L, + 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L, + 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, + 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L, + 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L, + 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L, + 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL, + 0x2d02ef8dL + }; + +/* Return a 32-bit CRC of the contents of the buffer. */ + +u32 efi_crc32(const unsigned char *s, unsigned long len) +{ + unsigned long i; + register u32 crc32val; + + crc32val = ~0; + for (i = 0; i < len; i ++) + { + crc32val + efi_crc32_tab[(crc32val ^ s[i]) & 0xff] ^ + (crc32val >> 8); + } + crc32val ^= ~0; + return crc32val; +} diff -burN kernel24-2.4.0-test10/linux/fs/partitions/efi_crc32.h kernel24-2.4.0-test10-crcfix/linux/fs/partitions/efi_crc32.h --- kernel24-2.4.0-test10/linux/fs/partitions/efi_crc32.h Wed Dec 31 18:00:00 1969 +++ kernel24-2.4.0-test10-crcfix/linux/fs/partitions/efi_crc32.h Thu Nov 30 15:42:16 2000 @@ -0,0 +1,17 @@ +/* + * efi_crc32.h + * See efi_crc32.c for license and changes + */ +#ifndef EFI_CRC32_H +#define EFI_CRC32_H + +#include + +/* + * This computes a 32 bit CRC of the data in the buffer, and returns the CRC. + * The polynomial used is 0xedb88320. + */ + +u32 efi_crc32(const unsigned char *buf, unsigned long len); + +#endif /* EFI_CRC32_H */