X.509: Implement simple static OID registry

Implement a simple static OID registry that allows the mapping of an encoded
OID to an enum value for ease of use.

The OID registry index enum appears in the:

	linux/oid_registry.h

header file.  A script generates the registry from lines in the header file
that look like:

	<sp*>OID_foo,<sp*>/*<sp*>1.2.3.4<sp*>*/

The actual OID is taken to be represented by the numbers with interpolated
dots in the comment.

All other lines in the header are ignored.

The registry is queries by calling:

	OID look_up_oid(const void *data, size_t datasize);

This returns a number from the registry enum representing the OID if found or
OID__NR if not.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

1 files changed, 89 insertions, 0 deletions

diff --git a/lib/oid_registry.c b/lib/oid_registry.c
new file mode 100644
index 0000000..33cfd17
--- /dev/null
+++ b/lib/oid_registry.c
@@ -0,0 +1,89 @@
+/* ASN.1 Object identifier (OID) registry
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <linux/export.h>
+#include <linux/oid_registry.h>
+#include "oid_registry_data.c"
+
+/**
+ * look_up_OID - Find an OID registration for the specified data
+ * @data: Binary representation of the OID
+ * @datasize: Size of the binary representation
+ */
+enum OID look_up_OID(const void *data, size_t datasize)
+{
+	const unsigned char *octets = data;
+	enum OID oid;
+	unsigned char xhash;
+	unsigned i, j, k, hash;
+	size_t len;
+
+	/* Hash the OID data */
+	hash = datasize - 1;
+
+	for (i = 0; i < datasize; i++)
+		hash += octets[i] * 33;
+	hash = (hash >> 24) ^ (hash >> 16) ^ (hash >> 8) ^ hash;
+	hash &= 0xff;
+
+	/* Binary search the OID registry.  OIDs are stored in ascending order
+	 * of hash value then ascending order of size and then in ascending
+	 * order of reverse value.
+	 */
+	i = 0;
+	k = OID__NR;
+	while (i < k) {
+		j = (i + k) / 2;
+
+		xhash = oid_search_table[j].hash;
+		if (xhash > hash) {
+			k = j;
+			continue;
+		}
+		if (xhash < hash) {
+			i = j + 1;
+			continue;
+		}
+
+		oid = oid_search_table[j].oid;
+		len = oid_index[oid + 1] - oid_index[oid];
+		if (len > datasize) {
+			k = j;
+			continue;
+		}
+		if (len < datasize) {
+			i = j + 1;
+			continue;
+		}
+
+		/* Variation is most likely to be at the tail end of the
+		 * OID, so do the comparison in reverse.
+		 */
+		while (len > 0) {
+			unsigned char a = oid_data[oid_index[oid] + --len];
+			unsigned char b = octets[len];
+			if (a > b) {
+				k = j;
+				goto next;
+			}
+			if (a < b) {
+				i = j + 1;
+				goto next;
+			}
+		}
+		return oid;
+	next:
+		;
+	}
+
+	return OID__NR;
+}
+EXPORT_SYMBOL_GPL(look_up_OID);