Date: Mon, 10 Mar 2003 07:43:19 +0900 From: Chiharu Shibata <chi@bd.mbn.or.jp> To: FreeBSD-gnats-submit@FreeBSD.org Subject: kern/49957: CRC32 generator should be the common routine Message-ID: <200303080155.h281tGD09709.chi@bd.mbn.or.jp>
next in thread | raw e-mail | index | archive | help
>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 <sys/socket.h>
#include <sys/sockio.h>
#include <sys/sysctl.h>
+#include <sys/types.h>
#include <net/if.h>
#include <net/netisr.h>
@@ -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 <sys/queue.h> /* get TAILQ macros */
+#ifdef _KERNEL
+#include <sys/types.h> /* 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200303080155.h281tGD09709.chi>