Hello, t...@!
The pci/usb (and others) known_{products,vendors} generated from
{pci,usb}devs are really big and scanning them is not so efficient.
I took the reyk@'s bsearch() implementation found in ieee80211 code
and moved it to libkern.
To sort tables I've rewritten the devlist2h from awk to perl, since
it can sort :). Imho, this implementation is a bit cleaner and
does not have that big license header.
Since usb/pci is only supported so far, I hope if you like it I can
continue replacing the rest of autoconf matching goo to bsearch
What do you think?
Index: conf/files
===================================================================
RCS file: /cvs/src/sys/conf/files,v
retrieving revision 1.504
diff -u -p -r1.504 files
--- conf/files 6 Oct 2010 22:19:20 -0000 1.504
+++ conf/files 16 Dec 2010 00:12:53 -0000
@@ -1085,6 +1085,7 @@ file lib/libkern/mcount.c gprof
file lib/libkern/getsn.c
file lib/libkern/random.c
file lib/libkern/timingsafe_bcmp.c
+file lib/libkern/bsearch.c
file lib/libkern/arch/${MACHINE_ARCH}/strchr.S | lib/libkern/strchr.c
file lib/libkern/arch/${MACHINE_ARCH}/strrchr.S | lib/libkern/strrchr.c
file lib/libkern/arch/${MACHINE_ARCH}/__main.S | lib/libkern/__main.c
Index: dev/pci/Makefile
===================================================================
RCS file: /cvs/src/sys/dev/pci/Makefile,v
retrieving revision 1.4
diff -u -p -r1.4 Makefile
--- dev/pci/Makefile 14 Oct 1996 09:01:34 -0000 1.4
+++ dev/pci/Makefile 16 Dec 2010 00:12:53 -0000
@@ -1,8 +1,6 @@
# $OpenBSD: Makefile,v 1.4 1996/10/14 09:01:34 deraadt Exp $
-# $NetBSD: Makefile,v 1.1 1995/06/18 01:07:04 cgd Exp $
-AWK= awk
+PERL?= perl
-pcidevs.h pcidevs_data.h: pcidevs devlist2h.awk
- /bin/rm -f pcidevs.h pcidevs_data.h
- ${AWK} -f devlist2h.awk pcidevs
+pcidevs.h pcidevs_data.h: pcidevs devlist2h.pl
+ ${PERL} devlist2h.pl < pcidevs
Index: dev/pci/devlist2h.pl
===================================================================
RCS file: dev/pci/devlist2h.pl
diff -N dev/pci/devlist2h.pl
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ dev/pci/devlist2h.pl 16 Dec 2010 00:12:53 -0000
@@ -0,0 +1,167 @@
+#!/usr/bin/perl -w
+use strict;
+
+my $hfile = "pcidevs.h";
+my $dfile = "pcidevs_data.h";
+
+open HFILE, ">$hfile";
+open DFILE, ">$dfile";
+sub header {
+ my ($file, $version) = @_;
+ chomp $version;
+
+ print {$file} <<__END;
+/*
+ * THIS FILE AUTOMATICALLY GENERATED. DO NOT EDIT.
+ *
+ * generated from:
+ * $version
+ */
+__END
+}
+
+my $version = readline;
+header \*HFILE, $version;
+header \*DFILE, $version;
+
+my %vendorhash;
+my @vendors;
+my @products;
+
+my $commentmode = 0;
+my @commentbuf;
+my $leadblank = 0;
+
+while (<>) {
+ chomp;
+ if ($commentmode) {
+ push @commentbuf, $_;
+ if (/\*\/\s*$/) {
+ $commentmode = 0;
+ }
+ next;
+ }
+
+ if (/^vendor/) {
+ my @data = split /[ \t]+/;
+ my ($k, $vendor, $id) = splice @data, 0, 3;
+ my $descr = join ' ', @data;
+
+ my @copy = @commentbuf;
+ my %new = (
+ vendor => $vendor,
+ id => $id,
+ descr => $descr,
+
+ lblank => $leadblank,
+ comment => \...@copy,
+ );
+ push @vendors, \%new;
+ $vendorhash{$vendor} = \%new;
+
+ $leadblank = 0;
+ @commentbuf = ();
+ } elsif (/^product/) {
+ my @data = split /[ \t]+/;
+ my ($k, $vendor, $product, $id) = splice @data, 0, 4;
+ my $descr = join ' ', @data;
+
+ my @copy = @commentbuf;
+ my %new = (
+ vendor => $vendor,
+ product => $product,
+ id => $id,
+ descr => $descr,
+
+ lblank => $leadblank,
+ comment => \...@copy,
+ );
+ push @products, \%new;
+
+ $leadblank = 0;
+ @commentbuf = ();
+ } elsif (/^$/) {
+ $leadblank = 1;
+ } elsif (/^\s*\/\*.*\*\/$/) { # oneline comment
+ push @commentbuf, $_;
+ } elsif (/^\s*\/\*/) {
+ $commentmode = 1;
+ push @commentbuf, $_;
+ }
+}
+die "invalid syntax\n" if $commentmode;
+
+sub prologue {
+ my $h = shift;
+ print HFILE "\n" if $h->{lblank};
+ if (@{$h->{comment}}) {
+ print HFILE join("\n", @{$h->{comment}});
+ print HFILE "\n";
+ }
+}
+
+foreach my $v (@vendors) {
+ prologue $v;
+ print HFILE <<__END;
+#define PCI_VENDOR_$v->{vendor} $v->{id} /* $v->{descr} */
+__END
+}
+
+foreach my $p (@products) {
+ prologue $p;
+ print HFILE <<__END;
+#define PCI_PRODUCT_$p->{vendor}_$p->{product} $p->{id}
+__END
+}
+
+print DFILE <<__END;
+/* Descriptions of known vendors and devices. */
+struct pci_known_vendor {
+ pci_vendor_id_t vendor;
+ const char *vendorname;
+};
+
+struct pci_known_product {
+ pci_vendor_id_t vendor;
+ pci_product_id_t product;
+ const char *productname;
+};
+
+static const struct pci_known_vendor pci_known_vendors[] = {
+__END
+
+foreach my $v (sort { hex($a->{id}) <=> hex($b->{id}) } @vendors) {
+ print DFILE <<__END;
+ { PCI_VENDOR_$v->{vendor}, "$v->{descr}" },
+__END
+}
+
+sub productcmp {
+ my $ah = $vendorhash{$a->{vendor}};
+ my $bh = $vendorhash{$b->{vendor}};
+ my $res = hex($ah->{id}) <=> hex($bh->{id});
+ if ($res == 0) {
+ $res = hex($a->{id}) <=> hex($b->{id});
+ }
+ return $res;
+}
+
+print DFILE <<__END;
+ { 0, NULL }
+};
+
+static const struct pci_known_product pci_known_products[] = {
+__END
+
+foreach my $p (sort productcmp @products) {
+ print DFILE <<__END;
+ {
+ PCI_VENDOR_$p->{vendor}, PCI_PRODUCT_$p->{vendor}_$p->{product},
+ "$p->{descr}"
+ },
+__END
+}
+print DFILE <<__END;
+ { 0, 0, NULL }
+};
+__END
Index: dev/pci/pci_subr.c
===================================================================
RCS file: /cvs/src/sys/dev/pci/pci_subr.c,v
retrieving revision 1.21
diff -u -p -r1.21 pci_subr.c
--- dev/pci/pci_subr.c 21 Feb 2007 13:08:22 -0000 1.21
+++ dev/pci/pci_subr.c 16 Dec 2010 00:12:53 -0000
@@ -44,6 +44,9 @@
#ifdef PCIVERBOSE
#include <dev/pci/pcidevs.h>
#include <dev/pci/pcidevs_data.h>
+
+static int pci_known_vendor_cmp(const void *, const void *);
+static int pci_known_product_cmp(const void *, const void *);
#endif
/*
@@ -276,43 +279,64 @@ const struct pci_class pci_class[] = {
{ 0 },
};
+#ifdef PCIVERBOSE
+#define _intcmp(a, b) (a != b ? (a > b ? 1 : -1) : 0)
+static int
+pci_known_vendor_cmp(const void *a, const void *b)
+{
+ const struct pci_known_vendor *v1 = a;
+ const struct pci_known_vendor *v2 = b;
+
+ return (_intcmp(v1->vendor, v2->vendor));
+}
+
+static int
+pci_known_product_cmp(const void *a, const void *b)
+{
+ const struct pci_known_product *p1 = a;
+ const struct pci_known_product *p2 = b;
+ int cmp;
+
+ cmp = _intcmp(p1->vendor, p2->vendor);
+ if (cmp == 0)
+ cmp = _intcmp(p1->product, p2->product);
+ return (cmp);
+}
+#undef _intcmp
+#endif /* PCIVERBOSE */
+
const char *
pci_findvendor(pcireg_t id_reg)
{
#ifdef PCIVERBOSE
- pci_vendor_id_t vendor = PCI_VENDOR(id_reg);
- const struct pci_known_vendor *kdp;
-
- kdp = pci_known_vendors;
- while (kdp->vendorname != NULL) { /* all have vendor name */
- if (kdp->vendor == vendor)
- break;
- kdp++;
- }
- return (kdp->vendorname);
-#else
- return (NULL);
+ struct pci_known_vendor key = {
+ PCI_VENDOR(id_reg)
+ };
+ const struct pci_known_vendor *kdp;
+
+ kdp = bsearch(&key, pci_known_vendors, nitems(pci_known_vendors),
+ sizeof(struct pci_known_vendor), pci_known_vendor_cmp);
+ if (kdp)
+ return (kdp->vendorname);
#endif
+ return (NULL);
}
const char *
pci_findproduct(pcireg_t id_reg)
{
#ifdef PCIVERBOSE
- pci_vendor_id_t vendor = PCI_VENDOR(id_reg);
- pci_product_id_t product = PCI_PRODUCT(id_reg);
- const struct pci_known_product *pkp;
-
- pkp = pci_known_products;
- while (pkp->productname != NULL) { /* all have product name */
- if (pkp->vendor == vendor && pkp->product == product)
- break;
- pkp++;
- }
- return (pkp->productname);
-#else
- return NULL;
+ const struct pci_known_product *pkp;
+ struct pci_known_product key = {
+ PCI_VENDOR(id_reg), PCI_PRODUCT(id_reg)
+ };
+
+ pkp = bsearch(&key, pci_known_products, nitems(pci_known_products),
+ sizeof(struct pci_known_product), pci_known_product_cmp);
+ if (pkp)
+ return (pkp->productname);
#endif
+ return (NULL);
}
void
Index: lib/libkern/bsearch.c
===================================================================
RCS file: lib/libkern/bsearch.c
diff -N lib/libkern/bsearch.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ lib/libkern/bsearch.c 16 Dec 2010 00:12:55 -0000
@@ -0,0 +1,41 @@
+/* $OpenBSD$ */
+
+/*
+ * Copyright (c) 2004, 2005 Reyk Floeter <[email protected]>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/param.h>
+#include <lib/libkern/libkern.h>
+
+const void *
+bsearch(const void *key, const void *base0, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *))
+{
+ const char *base = base0;
+ int lim, cmp;
+ const void *p;
+
+ for (lim = nmemb; lim != 0; lim >>= 1) {
+ p = base + (lim >> 1) * size;
+ cmp = (*compar)(key, p);
+ if (cmp == 0)
+ return ((const void *)p);
+ if (cmp > 0) { /* key > p: move right */
+ base = (const char *)p + size;
+ lim--;
+ } /* else move left */
+ }
+ return (NULL);
+}
Index: lib/libkern/libkern.h
===================================================================
RCS file: /cvs/src/sys/lib/libkern/libkern.h,v
retrieving revision 1.27
diff -u -p -r1.27 libkern.h
--- lib/libkern/libkern.h 20 Jul 2010 15:28:44 -0000 1.27
+++ lib/libkern/libkern.h 16 Dec 2010 00:12:55 -0000
@@ -142,6 +142,8 @@ abs(int j)
void __assert(const char *, const char *, int, const char *)
__attribute__ ((__noreturn__));
int bcmp(const void *, const void *, size_t);
+const void *bsearch(const void *, const void *, size_t, size_t,
+ int (*)(const void *, const void *));
void bzero(void *, size_t);
int ffs(int);
void *memchr(const void *, int, size_t);
Index: net80211/ieee80211_regdomain.c
===================================================================
RCS file: /cvs/src/sys/net80211/ieee80211_regdomain.c,v
retrieving revision 1.7
diff -u -p -r1.7 ieee80211_regdomain.c
--- net80211/ieee80211_regdomain.c 26 Nov 2006 19:46:28 -0000 1.7
+++ net80211/ieee80211_regdomain.c 16 Dec 2010 00:12:55 -0000
@@ -55,32 +55,6 @@ ieee80211_r_map[] = IEEE80211_REGDOMAIN_
static const struct ieee80211_countryname
ieee80211_r_ctry[] = IEEE80211_REGDOMAIN_COUNTRY_NAMES;
-#ifndef bsearch
-const void *bsearch(const void *, const void *, size_t, size_t,
- int (*)(const void *, const void *));
-
-const void *
-bsearch(const void *key, const void *base0, size_t nmemb, size_t size,
- int (*compar)(const void *, const void *))
-{
- const char *base = base0;
- int lim, cmp;
- const void *p;
-
- for (lim = nmemb; lim != 0; lim >>= 1) {
- p = base + (lim >> 1) * size;
- cmp = (*compar)(key, p);
- if (cmp == 0)
- return ((const void *)p);
- if (cmp > 0) { /* key > p: move right */
- base = (const char *)p + size;
- lim--;
- } /* else move left */
- }
- return (NULL);
-}
-#endif
-
int
ieee80211_regdomain_compare_cn(const void *a, const void *b)
{
Index: dev/usb/usb_subr.c
===================================================================
RCS file: /cvs/src/sys/dev/usb/usb_subr.c,v
retrieving revision 1.75
diff -u -p -r1.75 usb_subr.c
--- usb_subr.c 6 Dec 2010 04:30:57 -0000 1.75
+++ usb_subr.c 16 Dec 2010 00:22:02 -0000
@@ -77,6 +77,9 @@ u_int32_t usb_cookie_no = 0;
#ifdef USBVERBOSE
#include <dev/usb/usbdevs_data.h>
+
+static int usb_known_product_cmp(const void *, const void *);
+static int usb_known_vendor_cmp(const void *, const void *);
#endif /* USBVERBOSE */
const char * const usbd_error_strs[] = {
@@ -213,15 +216,43 @@ usbd_trim_spaces(char *p)
*e = 0; /* kill trailing spaces */
}
+#ifdef USBVERBOSE
+#define _intcmp(a, b) (a != b ? (a > b ? 1 : -1) : 0)
+static int
+usb_known_vendor_cmp(const void *a, const void *b)
+{
+ const struct usb_known_vendor *v1 = a;
+ const struct usb_known_vendor *v2 = b;
+
+ return (_intcmp(v1->vendor, v2->vendor));
+}
+
+static int
+usb_known_product_cmp(const void *a, const void *b)
+{
+ const struct usb_known_product *p1 = a;
+ const struct usb_known_product *p2 = b;
+ int cmp;
+
+ cmp = _intcmp(p1->vendor, p2->vendor);
+ if (cmp == 0)
+ cmp = _intcmp(p1->product, p2->product);
+ return (cmp);
+}
+#undef _intcmp
+#endif /* USBVERBOSE */
+
void
usbd_devinfo_vp(usbd_device_handle dev, char *v, size_t vl,
char *p, size_t pl, int usedev)
{
- usb_device_descriptor_t *udd = &dev->ddesc;
- char *vendor = NULL, *product = NULL;
+ usb_device_descriptor_t *udd = &dev->ddesc;
+ char *vendor = NULL, *product = NULL;
#ifdef USBVERBOSE
- const struct usb_known_vendor *ukv;
- const struct usb_known_product *ukp;
+ const struct usb_known_vendor *ukv;
+ const struct usb_known_product *ukp;
+ struct usb_known_vendor vkey;
+ struct usb_known_product pkey;
#endif
if (dev == NULL) {
@@ -237,24 +268,20 @@ usbd_devinfo_vp(usbd_device_handle dev,
}
#ifdef USBVERBOSE
if (vendor == NULL || product == NULL) {
- for (ukv = usb_known_vendors;
- ukv->vendorname != NULL;
- ukv++) {
- if (ukv->vendor == UGETW(udd->idVendor)) {
- vendor = ukv->vendorname;
- break;
- }
- }
- if (vendor != NULL) {
- for (ukp = usb_known_products;
- ukp->productname != NULL;
- ukp++) {
- if (ukp->vendor == UGETW(udd->idVendor) &&
- (ukp->product == UGETW(udd->idProduct))) {
- product = ukp->productname;
- break;
- }
- }
+ vkey.vendor = pkey.vendor = UGETW(udd->idVendor);
+ pkey.product = UGETW(udd->idProduct);
+
+ ukv = bsearch(&vkey, usb_known_vendors,
+ nitems(usb_known_vendors),
+ sizeof(usb_known_vendors), usb_known_vendor_cmp);
+ if (ukv) {
+ vendor = ukv->vendorname;
+
+ ukp = bsearch(&pkey, usb_known_products,
+ nitems(usb_known_products),
+ sizeof(usb_known_products), usb_known_product_cmp);
+ if (ukp)
+ product = ukp->productname;
}
}
#endif
Index: dev/usb/devlist2h.pl
===================================================================
RCS file: dev/usb/devlist2h.pl
diff -N dev/usb/devlist2h.pl
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ dev/usb/devlist2h.pl 16 Dec 2010 00:31:23 -0000
@@ -0,0 +1,170 @@
+#!/usr/bin/perl -w
+use strict;
+
+my $hfile = "usbdevs.h";
+my $dfile = "usbdevs_data.h";
+
+open HFILE, ">$hfile";
+open DFILE, ">$dfile";
+sub header {
+ my ($file, $version) = @_;
+ chomp $version;
+
+ print {$file} <<__END;
+/*
+ * THIS FILE AUTOMATICALLY GENERATED. DO NOT EDIT.
+ *
+ * generated from:
+ * $version
+ */
+__END
+}
+
+my $version = readline;
+header \*HFILE, $version;
+header \*DFILE, $version;
+
+my %vendorhash;
+my @vendors;
+my @products;
+
+my $commentmode = 0;
+my @commentbuf;
+my $leadblank = 0;
+
+while (<>) {
+ chomp;
+ if ($commentmode) {
+ push @commentbuf, $_;
+ if (/\*\/\s*$/) {
+ $commentmode = 0;
+ }
+ next;
+ }
+
+ if (/^vendor/) {
+ my @data = split /[ \t]+/;
+ my ($k, $vendor, $id) = splice @data, 0, 3;
+ my $descr = join ' ', @data;
+
+ my @copy = @commentbuf;
+ my %new = (
+ vendor => $vendor,
+ id => $id,
+ descr => $descr,
+
+ lblank => $leadblank,
+ comment => \...@copy,
+ );
+ push @vendors, \%new;
+ $vendorhash{$vendor} = \%new;
+
+ $leadblank = 0;
+ @commentbuf = ();
+ } elsif (/^product/) {
+ my @data = split /[ \t]+/;
+ my ($k, $vendor, $product, $id) = splice @data, 0, 4;
+ my $descr = join ' ', @data;
+
+ my @copy = @commentbuf;
+ my %new = (
+ vendor => $vendor,
+ product => $product,
+ id => $id,
+ descr => $descr,
+
+ lblank => $leadblank,
+ comment => \...@copy,
+ );
+ push @products, \%new;
+
+ $leadblank = 0;
+ @commentbuf = ();
+ } elsif (/^$/) {
+ $leadblank = 1;
+ } elsif (/^\s*\/\*.*\*\/$/) { # oneline comment
+ push @commentbuf, $_;
+ } elsif (/^\s*\/\*/) {
+ $commentmode = 1;
+ push @commentbuf, $_;
+ }
+}
+die "invalid syntax\n" if $commentmode;
+
+sub prologue {
+ my $h = shift;
+ print HFILE "\n" if $h->{lblank};
+ if (@{$h->{comment}}) {
+ print HFILE join("\n", @{$h->{comment}});
+ print HFILE "\n";
+ }
+}
+
+foreach my $v (@vendors) {
+ prologue $v;
+ print HFILE <<__END;
+#define USB_VENDOR_$v->{vendor} $v->{id} /* $v->{descr} */
+__END
+}
+
+foreach my $p (@products) {
+ prologue $p;
+ print HFILE <<__END;
+#define USB_PRODUCT_$p->{vendor}_$p->{product} $p->{id}
+__END
+}
+
+print DFILE <<__END;
+/*
+ * Descriptions of known vendors and devices ("products").
+ */
+struct usb_known_vendor {
+ u_int16_t vendor;
+ char *vendorname;
+};
+
+struct usb_known_product {
+ u_int16_t vendor;
+ u_int16_t product;
+ char *productname;
+};
+
+
+const struct usb_known_vendor usb_known_vendors[] = {
+__END
+
+foreach my $v (sort { hex($a->{id}) <=> hex($b->{id}) } @vendors) {
+ print DFILE <<__END;
+ { USB_VENDOR_$v->{vendor}, "$v->{descr}" },
+__END
+}
+
+sub productcmp {
+ my $ah = $vendorhash{$a->{vendor}};
+ my $bh = $vendorhash{$b->{vendor}};
+ my $res = hex($ah->{id}) <=> hex($bh->{id});
+ if ($res == 0) {
+ $res = hex($a->{id}) <=> hex($b->{id});
+ }
+ return $res;
+}
+
+print DFILE <<__END;
+ { 0, NULL }
+};
+
+const struct usb_known_product usb_known_products[] = {
+__END
+
+foreach my $p (sort productcmp @products) {
+ print DFILE <<__END;
+ {
+ USB_VENDOR_$p->{vendor}, USB_PRODUCT_$p->{vendor}_$p->{product},
+ "$p->{descr}"
+ },
+__END
+}
+print DFILE <<__END;
+ { 0, 0, NULL }
+};
+__END
Index: dev/usb/Makefile
===================================================================
RCS file: /cvs/src/sys/dev/usb/Makefile,v
retrieving revision 1.3
diff -u -p -r1.3 Makefile
--- dev/usb/Makefile 4 Jun 2007 10:34:04 -0000 1.3
+++ dev/usb/Makefile 16 Dec 2010 00:31:23 -0000
@@ -1,7 +1,6 @@
# $OpenBSD: Makefile,v 1.3 2007/06/04 10:34:04 mbalmer Exp $
-# $NetBSD: Makefile.usbdevs,v 1.2 1999/01/07 22:18:23 augustss Exp $
-AWK= awk
+PERL?= perl
UNAME= uname
PROG= makemap.awk
@@ -9,9 +8,8 @@ MAP= ../pckbc/wskbdmap_mfii.c
all: usbdevs.h ukbdmap.c
-usbdevs.h usbdevs_data.h: usbdevs devlist2h.awk
- /bin/rm -f usbdevs.h usbdevs_data.h
- ${AWK} -f devlist2h.awk usbdevs
+usbdevs.h usbdevs_data.h: usbdevs devlist2h.pl
+ ${PERL} devlist2h.pl < usbdevs
ukbdmap.c: ${MAP} ${PROG}
/bin/rm -f $@
