From owner-freebsd-bugs Wed Mar 12 5:30:24 2003 Delivered-To: freebsd-bugs@hub.freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 3561B37B404 for ; Wed, 12 Mar 2003 05:30:13 -0800 (PST) Received: from freefall.freebsd.org (freefall.freebsd.org [216.136.204.21]) by mx1.FreeBSD.org (Postfix) with ESMTP id D7B3243FAF for ; Wed, 12 Mar 2003 05:30:10 -0800 (PST) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (gnats@localhost [127.0.0.1]) by freefall.freebsd.org (8.12.6/8.12.6) with ESMTP id h2CDUANS069029 for ; Wed, 12 Mar 2003 05:30:10 -0800 (PST) (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.12.6/8.12.6/Submit) id h2CDUA85069028; Wed, 12 Mar 2003 05:30:10 -0800 (PST) Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 61B6A37B401 for ; Wed, 12 Mar 2003 05:20:50 -0800 (PST) Received: from castle.jp.FreeBSD.org (castle.jp.FreeBSD.org [210.226.20.15]) by mx1.FreeBSD.org (Postfix) with ESMTP id A2AAB43FA3 for ; Wed, 12 Mar 2003 05:20:48 -0800 (PST) (envelope-from kogane@jp.FreeBSD.org) Received: (from kogane@localhost) by castle.jp.FreeBSD.org (8.11.6+3.4W/8.11.3) id h2CDKlL31889; Wed, 12 Mar 2003 22:20:47 +0900 (JST) (envelope-from kogane) Message-Id: <200303080155.h281tGD09709.chi@bd.mbn.or.jp> Date: Mon, 10 Mar 2003 07:43:19 +0900 From: Chiharu Shibata Reply-To: Chiharu Shibata To: FreeBSD-gnats-submit@FreeBSD.org X-Send-Pr-Version: 3.113 Subject: kern/49957: CRC32 generator should be the common routine Sender: owner-freebsd-bugs@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org >Number: 49957 >Category: kern >Synopsis: CRC32 generator should be the common routine >Confidential: no >Severity: non-critical >Priority: medium >Responsible: freebsd-bugs >State: open >Quarter: >Keywords: >Date-Required: >Class: change-request >Submitter-Id: current-users >Arrival-Date: Wed Mar 12 05:30:10 PST 2003 >Closed-Date: >Last-Modified: >Originator: Chiharu Shibata >Release: any >Organization: Japan FreeBSD Users Group >Environment: Using NIC for ethernet >Description: Many NIC needs CRC32 generator to receive multicast packets, and each NIC driver has it locally. We should make the common routine of CRC32 generator. (NetBSD already did so.) >How-To-Repeat: none >Fix: Here is the patch of the common CRC32 generator routines. The table-driven version of big-endian is contributed by Seishi Hiragushi. --- sys/net/if_ethersubr.c 2003/02/02 11:29:47 1.2 +++ if_ethersubr.c 2003/03/07 07:36:36 @@ -49,6 +49,7 @@ #include #include #include +#include #include #include @@ -914,3 +915,95 @@ } } +#if 0 +#define CRC32_POLY_BE 0x04c11db7UL +#define CRC32_POLY_LE 0xedb88320UL + +/* + * These are for reference. We have a table-driven version + * of the crc32 generator, which is faster than the double-loop. + */ +u_int32_t +ether_crc32_be(const u_int8_t *buf, size_t len) +{ + u_int32_t crc = ~0; + u_int8_t b; + int carry, i, j; + + for (i = 0; i < len; ++i) { + b = *buf++; + for (j = 8; --j >= 0;) { + carry = ((crc & 0x80000000) ? 1 : 0) ^ (b & 0x01); + crc <<= 1; + b >>= 1; + if (carry) + crc ^= CRC32_POLY_BE; + } + } + return crc; +} + +u_int32_t +ether_crc32_le(const u_int8_t *buf, size_t len) +{ + u_int32_t crc = ~0; + u_int8_t b; + int carry, i, j; + + for (i = 0; i < len; ++i) { + b = *buf++; + for (j = 8; --j >= 0;) { + carry = ((crc & 0x01) ? 1 : 0) ^ (b & 0x01); + crc >>= 1; + b >>= 1; + if (carry) + crc ^= CRC32_POLY_LE; + } + } + return crc; +} +#else +u_int32_t +ether_crc32_be(const u_int8_t *buf, size_t len) +{ + u_int32_t crc = ~0; + int i; + + static u_int8_t cnv[] = { + 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, + }; + + static const u_int32_t crctab[] = { + 0x00000000UL, 0x04c11db7UL, 0x09823b6eUL, 0x0d4326d9UL, + 0x130476dcUL, 0x17c56b6bUL, 0x1a864db2UL, 0x1e475005UL, + 0x2608edb8UL, 0x22c9f00fUL, 0x2f8ad6d6UL, 0x2b4bcb61UL, + 0x350c9b64UL, 0x31cd86d3UL, 0x3c8ea00aUL, 0x384fbdbdUL, + }; + + for (i = 0; i < len; ++i) { + crc = (crc << 4) ^ crctab[(crc >> 28) ^ cnv[*buf & 0xf]]; + crc = (crc << 4) ^ crctab[(crc >> 28) ^ cnv[*buf++ >>4]]; + } + return crc; +} + +u_int32_t +ether_crc32_le(const u_int8_t *buf, size_t len) +{ + u_int32_t crc = ~0; + int i; + static const u_int32_t crctab[] = { + 0x00000000UL, 0x1db71064UL, 0x3b6e20c8UL, 0x26d930acUL, + 0x76dc4190UL, 0x6b6b51f4UL, 0x4db26158UL, 0x5005713cUL, + 0xedb88320UL, 0xf00f9344UL, 0xd6d6a3e8UL, 0xcb61b38cUL, + 0x9b64c2b0UL, 0x86d3d2d4UL, 0xa00ae278UL, 0xbdbdf21cUL, + }; + + for (i = 0; i < len; ++i) { + crc ^= *buf++; + crc = (crc >> 4) ^ crctab[crc & 0xf]; + crc = (crc >> 4) ^ crctab[crc & 0xf]; + } + return crc; +} +#endif --- sys/net/if_var.h 2003/02/02 11:44:23 1.1 +++ if_var.h 2003/02/02 11:49:22 @@ -74,6 +74,9 @@ #endif #include /* get TAILQ macros */ +#ifdef _KERNEL +#include /* u_int* */ +#endif TAILQ_HEAD(ifnethead, ifnet); /* we use TAILQs so that the order of */ TAILQ_HEAD(ifaddrhead, ifaddr); /* instantiation is preserved in the list */ @@ -332,6 +335,8 @@ struct mbuf *, struct sockaddr *, struct rtentry *)); int ether_output_frame __P((struct ifnet *, struct mbuf *)); int ether_ioctl __P((struct ifnet *, int, caddr_t)); +u_int32_t ether_crc32_be __P((const u_int8_t *, size_t)); +u_int32_t ether_crc32_le __P((const u_int8_t *, size_t)); int if_addmulti __P((struct ifnet *, struct sockaddr *, struct ifmultiaddr **)); %%%%%%%%%%%%%%%% In addition, the follows are sample patches for NIC driver. Many NIC drivers need to modify like this. --- sys/pci/if_dc.c 2003/02/02 12:26:40 1.1 +++ if_dc.c 2003/02/02 12:52:19 @@ -229,7 +229,6 @@ static void dc_setcfg __P((struct dc_softc *, int)); static u_int32_t dc_crc_le __P((struct dc_softc *, caddr_t)); -static u_int32_t dc_crc_be __P((caddr_t)); static void dc_setfilt_21143 __P((struct dc_softc *)); static void dc_setfilt_asix __P((struct dc_softc *)); static void dc_setfilt_admtek __P((struct dc_softc *)); @@ -901,7 +900,6 @@ return; } -#define DC_POLY 0xEDB88320 #define DC_BITS_512 9 #define DC_BITS_128 7 #define DC_BITS_64 6 @@ -910,15 +908,10 @@ struct dc_softc *sc; caddr_t addr; { - u_int32_t idx, bit, data, crc; + u_int32_t crc; /* Compute CRC for the address value. */ - crc = 0xFFFFFFFF; /* initial value */ - - for (idx = 0; idx < 6; idx++) { - for (data = *addr++, bit = 0; bit < 8; bit++, data >>= 1) - crc = (crc >> 1) ^ (((crc ^ data) & 1) ? DC_POLY : 0); - } + crc = ether_crc32_le(addr, ETHER_ADDR_LEN); /* * The hash table on the PNIC II and the MX98715AEC-C/D/E @@ -937,30 +930,7 @@ /* * Calculate CRC of a multicast group address, return the lower 6 bits. */ -static u_int32_t dc_crc_be(addr) - caddr_t addr; -{ - u_int32_t crc, carry; - int i, j; - u_int8_t c; - - /* Compute CRC for the address value. */ - crc = 0xFFFFFFFF; /* initial value */ - - for (i = 0; i < 6; i++) { - c = *(addr + i); - for (j = 0; j < 8; j++) { - carry = ((crc & 0x80000000) ? 1 : 0) ^ (c & 0x01); - crc <<= 1; - c >>= 1; - if (carry) - crc = (crc ^ 0x04c11db6) | carry; - } - } - - /* return the filter bit position */ - return((crc >> 26) & 0x0000003F); -} +#define dc_crc_be(addr) ((ether_crc32_be((addr), ETHER_ADDR_LEN) >> 26) & 0x3F) /* * 21143-style RX filter setup routine. Filter programming is done by --- sys/i386/isa/if_lnc.c 2003/02/02 12:54:23 1.1 +++ if_lnc.c 2003/02/02 12:50:57 @@ -218,27 +218,11 @@ return (inw(sc->bdp)); } -static __inline u_long -ether_crc(const u_char *ether_addr) -{ -#define POLYNOMIAL 0xEDB88320UL - u_char i, j, addr; - u_int crc = 0xFFFFFFFFUL; - - for (i = 0; i < ETHER_ADDR_LEN; i++) { - addr = *ether_addr++; - for (j = 0; j < MULTICAST_FILTER_LEN; j++) { - crc = (crc >> 1) ^ (((crc ^ addr) & 1) ? POLYNOMIAL : 0); - addr >>= 1; - } - } - return crc; -#undef POLYNOMIAL -} - /* * Set up the logical address filter for multicast packets */ +#define ether_crc(ep) (ether_crc32_le((ep), ETHER_ADDR_LEN) >> 26) + static __inline void lnc_setladrf(struct lnc_softc *sc) { @@ -266,8 +250,7 @@ if (ifma->ifma_addr->sa_family != AF_LINK) continue; - index = ether_crc(LLADDR((struct sockaddr_dl *)ifma->ifma_addr)) - >> 26; + index = ether_crc(LLADDR((struct sockaddr_dl *)ifma->ifma_addr)); sc->init_block->ladrf[index >> 3] |= 1 << (index & 7); } } --- sys/dev/ed/if_ed.c 2003/02/02 11:12:50 1.1 +++ if_ed.c 2003/02/02 11:12:53 @@ -102,7 +102,6 @@ static void ed_setrcr __P((struct ed_softc *)); -static u_int32_t ds_crc __P((u_char *ep)); /* * Interrupt conversion table for WD/SMC ASIC/83C584 @@ -3398,35 +3397,11 @@ } /* - * Compute crc for ethernet address - */ -static u_int32_t -ds_crc(ep) - u_char *ep; -{ -#define POLYNOMIAL 0x04c11db6 - register u_int32_t crc = 0xffffffff; - register int carry, i, j; - register u_char b; - - for (i = 6; --i >= 0;) { - b = *ep++; - for (j = 8; --j >= 0;) { - carry = ((crc & 0x80000000) ? 1 : 0) ^ (b & 0x01); - crc <<= 1; - b >>= 1; - if (carry) - crc = (crc ^ POLYNOMIAL) | carry; - } - } - return crc; -#undef POLYNOMIAL -} - -/* * Compute the multicast address filter from the * list of multicast addresses we need to listen to. */ +#define ds_crc(ep) (ether_crc32_be((ep), ETHER_ADDR_LEN) >> 26) + static void ds_getmcaf(sc, mcaf) struct ed_softc *sc; @@ -3443,8 +3418,7 @@ ifma = ifma->ifma_link.le_next) { if (ifma->ifma_addr->sa_family != AF_LINK) continue; - index = ds_crc(LLADDR((struct sockaddr_dl *)ifma->ifma_addr)) - >> 26; + index = ds_crc(LLADDR((struct sockaddr_dl *)ifma->ifma_addr)); af[index >> 3] |= 1 << (index & 7); } } --- sys/dev/fe/if_fe.c 2003/02/02 12:48:36 1.1 +++ if_fe.c 2003/02/02 12:51:52 @@ -2085,34 +2085,11 @@ } /* - * Compute hash value for an Ethernet address - */ -static int -fe_hash ( u_char * ep ) -{ -#define FE_HASH_MAGIC_NUMBER 0xEDB88320L - - u_long hash = 0xFFFFFFFFL; - int i, j; - u_char b; - u_long m; - - for ( i = ETHER_ADDR_LEN; --i >= 0; ) { - b = *ep++; - for ( j = 8; --j >= 0; ) { - m = hash; - hash >>= 1; - if ( ( m ^ b ) & 1 ) hash ^= FE_HASH_MAGIC_NUMBER; - b >>= 1; - } - } - return ( ( int )( hash >> 26 ) ); -} - -/* * Compute the multicast address filter from the * list of multicast addresses we need to listen to. */ +#define fe_hash(ep) (ether_crc32_le((ep), ETHER_ADDR_LEN) >> 26) + static struct fe_filter fe_mcaf ( struct fe_softc *sc ) { --- sys/dev/usb/if_cue.c 2003/02/02 02:18:59 1.1 +++ if_cue.c 2003/02/02 02:22:48 @@ -117,7 +117,6 @@ Static void cue_shutdown __P((device_t)); Static void cue_setmulti __P((struct cue_softc *)); -Static u_int32_t cue_crc __P((caddr_t)); Static void cue_reset __P((struct cue_softc *)); Static int csr_read_1 __P((struct cue_softc *, int)); @@ -348,24 +347,10 @@ return(0); } -#define CUE_POLY 0xEDB88320 #define CUE_BITS 9 -Static u_int32_t cue_crc(addr) - caddr_t addr; -{ - u_int32_t idx, bit, data, crc; - - /* Compute CRC for the address value. */ - crc = 0xFFFFFFFF; /* initial value */ - - for (idx = 0; idx < 6; idx++) { - for (data = *addr++, bit = 0; bit < 8; bit++, data >>= 1) - crc = (crc >> 1) ^ (((crc ^ data) & 1) ? CUE_POLY : 0); - } - - return (crc & ((1 << CUE_BITS) - 1)); -} +#define cue_crc(addr) (ether_crc32_le((addr), ETHER_ADDR_LEN) \ + & ((1 << CUE_BITS) - 1)) Static void cue_setmulti(sc) struct cue_softc *sc; >Release-Note: >Audit-Trail: >Unformatted: To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-bugs" in the body of the message