diff mbox series

[U-Boot,v1,07/11] lib: add oid registry utility

Message ID 20191011074200.30269-8-takahiro.akashi@linaro.org
State Superseded
Delegated to: Tom Rini
Headers show
Series import x509/pkcs7 parsers from linux | expand

Commit Message

AKASHI Takahiro Oct. 11, 2019, 7:41 a.m. UTC
Imported from linux kernel v5.3.

Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
---
 include/linux/oid_registry.h | 117 ++++++++++++++++++++
 lib/Kconfig                  |   5 +
 lib/Makefile                 |  16 +++
 lib/build_OID_registry       | 203 +++++++++++++++++++++++++++++++++++
 lib/oid_registry.c           | 179 ++++++++++++++++++++++++++++++
 5 files changed, 520 insertions(+)
 create mode 100644 include/linux/oid_registry.h
 create mode 100755 lib/build_OID_registry
 create mode 100644 lib/oid_registry.c

Comments

Heinrich Schuchardt Oct. 12, 2019, 12:58 p.m. UTC | #1
On 10/11/19 9:41 AM, AKASHI Takahiro wrote:
> Imported from linux kernel v5.3.

Please, indicate in the commit message which files are verbatim copies
and which files had to be adjusted. E.g. in lib/oid_registry.c you
adjusted the includes.

>
> Signed-off-by: AKASHI Takahiro <takahiro.akashi@linaro.org>
> ---
>   include/linux/oid_registry.h | 117 ++++++++++++++++++++
>   lib/Kconfig                  |   5 +
>   lib/Makefile                 |  16 +++
>   lib/build_OID_registry       | 203 +++++++++++++++++++++++++++++++++++

Shouldn't this file go into /scripts or /tools?

Best regards

Heinrich

>   lib/oid_registry.c           | 179 ++++++++++++++++++++++++++++++
>   5 files changed, 520 insertions(+)
>   create mode 100644 include/linux/oid_registry.h
>   create mode 100755 lib/build_OID_registry
>   create mode 100644 lib/oid_registry.c
>
> diff --git a/include/linux/oid_registry.h b/include/linux/oid_registry.h
> new file mode 100644
> index 000000000000..657d6bf2c064
> --- /dev/null
> +++ b/include/linux/oid_registry.h
> @@ -0,0 +1,117 @@
> +/* SPDX-License-Identifier: GPL-2.0-or-later */
> +/* ASN.1 Object identifier (OID) registry
> + *
> + * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
> + * Written by David Howells (dhowells@redhat.com)
> + */
> +
> +#ifndef _LINUX_OID_REGISTRY_H
> +#define _LINUX_OID_REGISTRY_H
> +
> +#include <linux/types.h>
> +
> +/*
> + * OIDs are turned into these values if possible, or OID__NR if not held here.
> + *
> + * NOTE!  Do not mess with the format of each line as this is read by
> + *	  build_OID_registry.pl to generate the data for look_up_OID().
> + */
> +enum OID {
> +	OID_id_dsa_with_sha1,		/* 1.2.840.10030.4.3 */
> +	OID_id_dsa,			/* 1.2.840.10040.4.1 */
> +	OID_id_ecdsa_with_sha1,		/* 1.2.840.10045.4.1 */
> +	OID_id_ecPublicKey,		/* 1.2.840.10045.2.1 */
> +
> +	/* PKCS#1 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1)} */
> +	OID_rsaEncryption,		/* 1.2.840.113549.1.1.1 */
> +	OID_md2WithRSAEncryption,	/* 1.2.840.113549.1.1.2 */
> +	OID_md3WithRSAEncryption,	/* 1.2.840.113549.1.1.3 */
> +	OID_md4WithRSAEncryption,	/* 1.2.840.113549.1.1.4 */
> +	OID_sha1WithRSAEncryption,	/* 1.2.840.113549.1.1.5 */
> +	OID_sha256WithRSAEncryption,	/* 1.2.840.113549.1.1.11 */
> +	OID_sha384WithRSAEncryption,	/* 1.2.840.113549.1.1.12 */
> +	OID_sha512WithRSAEncryption,	/* 1.2.840.113549.1.1.13 */
> +	OID_sha224WithRSAEncryption,	/* 1.2.840.113549.1.1.14 */
> +	/* PKCS#7 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-7(7)} */
> +	OID_data,			/* 1.2.840.113549.1.7.1 */
> +	OID_signed_data,		/* 1.2.840.113549.1.7.2 */
> +	/* PKCS#9 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-9(9)} */
> +	OID_email_address,		/* 1.2.840.113549.1.9.1 */
> +	OID_contentType,		/* 1.2.840.113549.1.9.3 */
> +	OID_messageDigest,		/* 1.2.840.113549.1.9.4 */
> +	OID_signingTime,		/* 1.2.840.113549.1.9.5 */
> +	OID_smimeCapabilites,		/* 1.2.840.113549.1.9.15 */
> +	OID_smimeAuthenticatedAttrs,	/* 1.2.840.113549.1.9.16.2.11 */
> +
> +	/* {iso(1) member-body(2) us(840) rsadsi(113549) digestAlgorithm(2)} */
> +	OID_md2,			/* 1.2.840.113549.2.2 */
> +	OID_md4,			/* 1.2.840.113549.2.4 */
> +	OID_md5,			/* 1.2.840.113549.2.5 */
> +
> +	/* Microsoft Authenticode & Software Publishing */
> +	OID_msIndirectData,		/* 1.3.6.1.4.1.311.2.1.4 */
> +	OID_msStatementType,		/* 1.3.6.1.4.1.311.2.1.11 */
> +	OID_msSpOpusInfo,		/* 1.3.6.1.4.1.311.2.1.12 */
> +	OID_msPeImageDataObjId,		/* 1.3.6.1.4.1.311.2.1.15 */
> +	OID_msIndividualSPKeyPurpose,	/* 1.3.6.1.4.1.311.2.1.21 */
> +	OID_msOutlookExpress,		/* 1.3.6.1.4.1.311.16.4 */
> +
> +	OID_certAuthInfoAccess,		/* 1.3.6.1.5.5.7.1.1 */
> +	OID_sha1,			/* 1.3.14.3.2.26 */
> +	OID_sha256,			/* 2.16.840.1.101.3.4.2.1 */
> +	OID_sha384,			/* 2.16.840.1.101.3.4.2.2 */
> +	OID_sha512,			/* 2.16.840.1.101.3.4.2.3 */
> +	OID_sha224,			/* 2.16.840.1.101.3.4.2.4 */
> +
> +	/* Distinguished Name attribute IDs [RFC 2256] */
> +	OID_commonName,			/* 2.5.4.3 */
> +	OID_surname,			/* 2.5.4.4 */
> +	OID_countryName,		/* 2.5.4.6 */
> +	OID_locality,			/* 2.5.4.7 */
> +	OID_stateOrProvinceName,	/* 2.5.4.8 */
> +	OID_organizationName,		/* 2.5.4.10 */
> +	OID_organizationUnitName,	/* 2.5.4.11 */
> +	OID_title,			/* 2.5.4.12 */
> +	OID_description,		/* 2.5.4.13 */
> +	OID_name,			/* 2.5.4.41 */
> +	OID_givenName,			/* 2.5.4.42 */
> +	OID_initials,			/* 2.5.4.43 */
> +	OID_generationalQualifier,	/* 2.5.4.44 */
> +
> +	/* Certificate extension IDs */
> +	OID_subjectKeyIdentifier,	/* 2.5.29.14 */
> +	OID_keyUsage,			/* 2.5.29.15 */
> +	OID_subjectAltName,		/* 2.5.29.17 */
> +	OID_issuerAltName,		/* 2.5.29.18 */
> +	OID_basicConstraints,		/* 2.5.29.19 */
> +	OID_crlDistributionPoints,	/* 2.5.29.31 */
> +	OID_certPolicies,		/* 2.5.29.32 */
> +	OID_authorityKeyIdentifier,	/* 2.5.29.35 */
> +	OID_extKeyUsage,		/* 2.5.29.37 */
> +
> +	/* EC-RDSA */
> +	OID_gostCPSignA,		/* 1.2.643.2.2.35.1 */
> +	OID_gostCPSignB,		/* 1.2.643.2.2.35.2 */
> +	OID_gostCPSignC,		/* 1.2.643.2.2.35.3 */
> +	OID_gost2012PKey256,		/* 1.2.643.7.1.1.1.1 */
> +	OID_gost2012PKey512,		/* 1.2.643.7.1.1.1.2 */
> +	OID_gost2012Digest256,		/* 1.2.643.7.1.1.2.2 */
> +	OID_gost2012Digest512,		/* 1.2.643.7.1.1.2.3 */
> +	OID_gost2012Signature256,	/* 1.2.643.7.1.1.3.2 */
> +	OID_gost2012Signature512,	/* 1.2.643.7.1.1.3.3 */
> +	OID_gostTC26Sign256A,		/* 1.2.643.7.1.2.1.1.1 */
> +	OID_gostTC26Sign256B,		/* 1.2.643.7.1.2.1.1.2 */
> +	OID_gostTC26Sign256C,		/* 1.2.643.7.1.2.1.1.3 */
> +	OID_gostTC26Sign256D,		/* 1.2.643.7.1.2.1.1.4 */
> +	OID_gostTC26Sign512A,		/* 1.2.643.7.1.2.1.2.1 */
> +	OID_gostTC26Sign512B,		/* 1.2.643.7.1.2.1.2.2 */
> +	OID_gostTC26Sign512C,		/* 1.2.643.7.1.2.1.2.3 */
> +
> +	OID__NR
> +};
> +
> +extern enum OID look_up_OID(const void *data, size_t datasize);
> +extern int sprint_oid(const void *, size_t, char *, size_t);
> +extern int sprint_OID(enum OID, char *, size_t);
> +
> +#endif /* _LINUX_OID_REGISTRY_H */
> diff --git a/lib/Kconfig b/lib/Kconfig
> index 26c94f49ecd2..d2955c8feb0e 100644
> --- a/lib/Kconfig
> +++ b/lib/Kconfig
> @@ -527,6 +527,11 @@ config ASN1
>   	help
>   	  Enable asn1 decoder library.
>
> +config OID_REGISTRY
> +	bool
> +	help
> +	  Enable fast lookup object identifier registry.
> +
>   source lib/efi/Kconfig
>   source lib/efi_loader/Kconfig
>   source lib/optee/Kconfig
> diff --git a/lib/Makefile b/lib/Makefile
> index eb3a675fb8c2..677ec33a1ce1 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -118,4 +118,20 @@ else
>   obj-y += vsprintf.o strto.o strmhz.o
>   endif
>
> +#
> +# Build a fast OID lookip registry from include/linux/oid_registry.h
> +#
> +obj-$(CONFIG_OID_REGISTRY) += oid_registry.o
> +
> +$(obj)/oid_registry.o: $(obj)/oid_registry_data.c
> +
> +$(obj)/oid_registry_data.c: $(srctree)/include/linux/oid_registry.h \
> +			    $(src)/build_OID_registry
> +	$(call cmd,build_OID_registry)
> +
> +quiet_cmd_build_OID_registry = GEN     $@
> +      cmd_build_OID_registry = perl $(srctree)/$(src)/build_OID_registry $< $@
> +
> +clean-files     += oid_registry_data.c
> +
>   subdir-ccflags-$(CONFIG_CC_OPTIMIZE_LIBS_FOR_SPEED) += -O2
> diff --git a/lib/build_OID_registry b/lib/build_OID_registry
> new file mode 100755
> index 000000000000..d7fc32ea8ac2
> --- /dev/null
> +++ b/lib/build_OID_registry
> @@ -0,0 +1,203 @@
> +#!/usr/bin/perl -w
> +# SPDX-License-Identifier: GPL-2.0-or-later
> +#
> +# Build a static ASN.1 Object Identified (OID) registry
> +#
> +# Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
> +# Written by David Howells (dhowells@redhat.com)
> +#
> +
> +use strict;
> +
> +my @names = ();
> +my @oids = ();
> +
> +if ($#ARGV != 1) {
> +    print STDERR "Format: ", $0, " <in-h-file> <out-c-file>\n";
> +    exit(2);
> +}
> +
> +#
> +# Open the file to read from
> +#
> +open IN_FILE, "<$ARGV[0]" || die;
> +while (<IN_FILE>) {
> +    chomp;
> +    if (m!\s+OID_([a-zA-z][a-zA-Z0-9_]+),\s+/[*]\s+([012][.0-9]*)\s+[*]/!) {
> +	push @names, $1;
> +	push @oids, $2;
> +    }
> +}
> +close IN_FILE || die;
> +
> +#
> +# Open the files to write into
> +#
> +open C_FILE, ">$ARGV[1]" or die;
> +print C_FILE "/*\n";
> +print C_FILE " * Automatically generated by ", $0, ".  Do not edit\n";
> +print C_FILE " */\n";
> +
> +#
> +# Split the data up into separate lists and also determine the lengths of the
> +# encoded data arrays.
> +#
> +my @indices = ();
> +my @lengths = ();
> +my $total_length = 0;
> +
> +for (my $i = 0; $i <= $#names; $i++) {
> +    my $name = $names[$i];
> +    my $oid = $oids[$i];
> +
> +    my @components = split(/[.]/, $oid);
> +
> +    # Determine the encoded length of this OID
> +    my $size = $#components;
> +    for (my $loop = 2; $loop <= $#components; $loop++) {
> +	my $c = $components[$loop];
> +
> +	# We will base128 encode the number
> +	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
> +	$tmp = int($tmp / 7);
> +	$size += $tmp;
> +    }
> +    push @lengths, $size;
> +    push @indices, $total_length;
> +    $total_length += $size;
> +}
> +
> +#
> +# Emit the look-up-by-OID index table
> +#
> +print C_FILE "\n";
> +if ($total_length <= 255) {
> +    print C_FILE "static const unsigned char oid_index[OID__NR + 1] = {\n";
> +} else {
> +    print C_FILE "static const unsigned short oid_index[OID__NR + 1] = {\n";
> +}
> +for (my $i = 0; $i <= $#names; $i++) {
> +    print C_FILE "\t[OID_", $names[$i], "] = ", $indices[$i], ",\n"
> +}
> +print C_FILE "\t[OID__NR] = ", $total_length, "\n";
> +print C_FILE "};\n";
> +
> +#
> +# Encode the OIDs
> +#
> +my @encoded_oids = ();
> +
> +for (my $i = 0; $i <= $#names; $i++) {
> +    my @octets = ();
> +
> +    my @components = split(/[.]/, $oids[$i]);
> +
> +    push @octets, $components[0] * 40 + $components[1];
> +
> +    for (my $loop = 2; $loop <= $#components; $loop++) {
> +	my $c = $components[$loop];
> +
> +	# Base128 encode the number
> +	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
> +	$tmp = int($tmp / 7);
> +
> +	for (; $tmp > 0; $tmp--) {
> +	    push @octets, (($c >> $tmp * 7) & 0x7f) | 0x80;
> +	}
> +	push @octets, $c & 0x7f;
> +    }
> +
> +    push @encoded_oids, \@octets;
> +}
> +
> +#
> +# Create a hash value for each OID
> +#
> +my @hash_values = ();
> +for (my $i = 0; $i <= $#names; $i++) {
> +    my @octets = @{$encoded_oids[$i]};
> +
> +    my $hash = $#octets;
> +    foreach (@octets) {
> +	$hash += $_ * 33;
> +    }
> +
> +    $hash = ($hash >> 24) ^ ($hash >> 16) ^ ($hash >> 8) ^ ($hash);
> +
> +    push @hash_values, $hash & 0xff;
> +}
> +
> +#
> +# Emit the OID data
> +#
> +print C_FILE "\n";
> +print C_FILE "static const unsigned char oid_data[", $total_length, "] = {\n";
> +for (my $i = 0; $i <= $#names; $i++) {
> +    my @octets = @{$encoded_oids[$i]};
> +    print C_FILE "\t";
> +    print C_FILE $_, ", " foreach (@octets);
> +    print C_FILE "\t// ", $names[$i];
> +    print C_FILE "\n";
> +}
> +print C_FILE "};\n";
> +
> +#
> +# Build the search index table (ordered by length then hash then content)
> +#
> +my @index_table = ( 0 .. $#names );
> +
> +@index_table = sort {
> +    my @octets_a = @{$encoded_oids[$a]};
> +    my @octets_b = @{$encoded_oids[$b]};
> +
> +    return $hash_values[$a] <=> $hash_values[$b]
> +	if ($hash_values[$a] != $hash_values[$b]);
> +    return $#octets_a <=> $#octets_b
> +	if ($#octets_a != $#octets_b);
> +    for (my $i = $#octets_a; $i >= 0; $i--) {
> +	return $octets_a[$i] <=> $octets_b[$i]
> +	    if ($octets_a[$i] != $octets_b[$i]);
> +    }
> +    return 0;
> +
> +} @index_table;
> +
> +#
> +# Emit the search index and hash value table
> +#
> +print C_FILE "\n";
> +print C_FILE "static const struct {\n";
> +print C_FILE "\tunsigned char hash;\n";
> +if ($#names <= 255) {
> +    print C_FILE "\tenum OID oid : 8;\n";
> +} else {
> +    print C_FILE "\tenum OID oid : 16;\n";
> +}
> +print C_FILE "} oid_search_table[OID__NR] = {\n";
> +for (my $i = 0; $i <= $#names; $i++) {
> +    my @octets = @{$encoded_oids[$index_table[$i]]};
> +    printf(C_FILE "\t[%3u] = { %3u, OID_%-35s }, // ",
> +	   $i,
> +	   $hash_values[$index_table[$i]],
> +	   $names[$index_table[$i]]);
> +    printf C_FILE "%02x", $_ foreach (@octets);
> +    print C_FILE "\n";
> +}
> +print C_FILE "};\n";
> +
> +#
> +# Emit the OID debugging name table
> +#
> +#print C_FILE "\n";
> +#print C_FILE "const char *const oid_name_table[OID__NR + 1] = {\n";
> +#
> +#for (my $i = 0; $i <= $#names; $i++) {
> +#    print C_FILE "\t\"", $names[$i], "\",\n"
> +#}
> +#print C_FILE "\t\"Unknown-OID\"\n";
> +#print C_FILE "};\n";
> +
> +#
> +# Polish off
> +#
> +close C_FILE or die;
> diff --git a/lib/oid_registry.c b/lib/oid_registry.c
> new file mode 100644
> index 000000000000..209edc73b99f
> --- /dev/null
> +++ b/lib/oid_registry.c
> @@ -0,0 +1,179 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +/* ASN.1 Object identifier (OID) registry
> + *
> + * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
> + * Written by David Howells (dhowells@redhat.com)
> + */
> +
> +#ifdef __UBOOT__
> +#include <linux/compat.h>
> +#else
> +#include <linux/module.h>
> +#include <linux/export.h>
> +#endif
> +#include <linux/oid_registry.h>
> +#include <linux/kernel.h>
> +#include <linux/errno.h>
> +#include <linux/bug.h>
> +#include "oid_registry_data.c"
> +
> +MODULE_DESCRIPTION("OID Registry");
> +MODULE_AUTHOR("Red Hat, Inc.");
> +MODULE_LICENSE("GPL");
> +
> +/**
> + * 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);
> +
> +/*
> + * sprint_OID - Print an Object Identifier into a buffer
> + * @data: The encoded OID to print
> + * @datasize: The size of the encoded OID
> + * @buffer: The buffer to render into
> + * @bufsize: The size of the buffer
> + *
> + * The OID is rendered into the buffer in "a.b.c.d" format and the number of
> + * bytes is returned.  -EBADMSG is returned if the data could not be intepreted
> + * and -ENOBUFS if the buffer was too small.
> + */
> +int sprint_oid(const void *data, size_t datasize, char *buffer, size_t bufsize)
> +{
> +	const unsigned char *v = data, *end = v + datasize;
> +	unsigned long num;
> +	unsigned char n;
> +	size_t ret;
> +	int count;
> +
> +	if (v >= end)
> +		goto bad;
> +
> +	n = *v++;
> +	ret = count = snprintf(buffer, bufsize, "%u.%u", n / 40, n % 40);
> +	if (count >= bufsize)
> +		return -ENOBUFS;
> +	buffer += count;
> +	bufsize -= count;
> +
> +	while (v < end) {
> +		num = 0;
> +		n = *v++;
> +		if (!(n & 0x80)) {
> +			num = n;
> +		} else {
> +			num = n & 0x7f;
> +			do {
> +				if (v >= end)
> +					goto bad;
> +				n = *v++;
> +				num <<= 7;
> +				num |= n & 0x7f;
> +			} while (n & 0x80);
> +		}
> +		ret += count = snprintf(buffer, bufsize, ".%lu", num);
> +		if (count >= bufsize)
> +			return -ENOBUFS;
> +		buffer += count;
> +		bufsize -= count;
> +	}
> +
> +	return ret;
> +
> +bad:
> +	snprintf(buffer, bufsize, "(bad)");
> +	return -EBADMSG;
> +}
> +EXPORT_SYMBOL_GPL(sprint_oid);
> +
> +/**
> + * sprint_OID - Print an Object Identifier into a buffer
> + * @oid: The OID to print
> + * @buffer: The buffer to render into
> + * @bufsize: The size of the buffer
> + *
> + * The OID is rendered into the buffer in "a.b.c.d" format and the number of
> + * bytes is returned.
> + */
> +int sprint_OID(enum OID oid, char *buffer, size_t bufsize)
> +{
> +	int ret;
> +
> +	BUG_ON(oid >= OID__NR);
> +
> +	ret = sprint_oid(oid_data + oid_index[oid],
> +			 oid_index[oid + 1] - oid_index[oid],
> +			 buffer, bufsize);
> +	BUG_ON(ret == -EBADMSG);
> +	return ret;
> +}
> +EXPORT_SYMBOL_GPL(sprint_OID);
>
diff mbox series

Patch

diff --git a/include/linux/oid_registry.h b/include/linux/oid_registry.h
new file mode 100644
index 000000000000..657d6bf2c064
--- /dev/null
+++ b/include/linux/oid_registry.h
@@ -0,0 +1,117 @@ 
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* ASN.1 Object identifier (OID) registry
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ */
+
+#ifndef _LINUX_OID_REGISTRY_H
+#define _LINUX_OID_REGISTRY_H
+
+#include <linux/types.h>
+
+/*
+ * OIDs are turned into these values if possible, or OID__NR if not held here.
+ *
+ * NOTE!  Do not mess with the format of each line as this is read by
+ *	  build_OID_registry.pl to generate the data for look_up_OID().
+ */
+enum OID {
+	OID_id_dsa_with_sha1,		/* 1.2.840.10030.4.3 */
+	OID_id_dsa,			/* 1.2.840.10040.4.1 */
+	OID_id_ecdsa_with_sha1,		/* 1.2.840.10045.4.1 */
+	OID_id_ecPublicKey,		/* 1.2.840.10045.2.1 */
+
+	/* PKCS#1 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1)} */
+	OID_rsaEncryption,		/* 1.2.840.113549.1.1.1 */
+	OID_md2WithRSAEncryption,	/* 1.2.840.113549.1.1.2 */
+	OID_md3WithRSAEncryption,	/* 1.2.840.113549.1.1.3 */
+	OID_md4WithRSAEncryption,	/* 1.2.840.113549.1.1.4 */
+	OID_sha1WithRSAEncryption,	/* 1.2.840.113549.1.1.5 */
+	OID_sha256WithRSAEncryption,	/* 1.2.840.113549.1.1.11 */
+	OID_sha384WithRSAEncryption,	/* 1.2.840.113549.1.1.12 */
+	OID_sha512WithRSAEncryption,	/* 1.2.840.113549.1.1.13 */
+	OID_sha224WithRSAEncryption,	/* 1.2.840.113549.1.1.14 */
+	/* PKCS#7 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-7(7)} */
+	OID_data,			/* 1.2.840.113549.1.7.1 */
+	OID_signed_data,		/* 1.2.840.113549.1.7.2 */
+	/* PKCS#9 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-9(9)} */
+	OID_email_address,		/* 1.2.840.113549.1.9.1 */
+	OID_contentType,		/* 1.2.840.113549.1.9.3 */
+	OID_messageDigest,		/* 1.2.840.113549.1.9.4 */
+	OID_signingTime,		/* 1.2.840.113549.1.9.5 */
+	OID_smimeCapabilites,		/* 1.2.840.113549.1.9.15 */
+	OID_smimeAuthenticatedAttrs,	/* 1.2.840.113549.1.9.16.2.11 */
+
+	/* {iso(1) member-body(2) us(840) rsadsi(113549) digestAlgorithm(2)} */
+	OID_md2,			/* 1.2.840.113549.2.2 */
+	OID_md4,			/* 1.2.840.113549.2.4 */
+	OID_md5,			/* 1.2.840.113549.2.5 */
+
+	/* Microsoft Authenticode & Software Publishing */
+	OID_msIndirectData,		/* 1.3.6.1.4.1.311.2.1.4 */
+	OID_msStatementType,		/* 1.3.6.1.4.1.311.2.1.11 */
+	OID_msSpOpusInfo,		/* 1.3.6.1.4.1.311.2.1.12 */
+	OID_msPeImageDataObjId,		/* 1.3.6.1.4.1.311.2.1.15 */
+	OID_msIndividualSPKeyPurpose,	/* 1.3.6.1.4.1.311.2.1.21 */
+	OID_msOutlookExpress,		/* 1.3.6.1.4.1.311.16.4 */
+
+	OID_certAuthInfoAccess,		/* 1.3.6.1.5.5.7.1.1 */
+	OID_sha1,			/* 1.3.14.3.2.26 */
+	OID_sha256,			/* 2.16.840.1.101.3.4.2.1 */
+	OID_sha384,			/* 2.16.840.1.101.3.4.2.2 */
+	OID_sha512,			/* 2.16.840.1.101.3.4.2.3 */
+	OID_sha224,			/* 2.16.840.1.101.3.4.2.4 */
+
+	/* Distinguished Name attribute IDs [RFC 2256] */
+	OID_commonName,			/* 2.5.4.3 */
+	OID_surname,			/* 2.5.4.4 */
+	OID_countryName,		/* 2.5.4.6 */
+	OID_locality,			/* 2.5.4.7 */
+	OID_stateOrProvinceName,	/* 2.5.4.8 */
+	OID_organizationName,		/* 2.5.4.10 */
+	OID_organizationUnitName,	/* 2.5.4.11 */
+	OID_title,			/* 2.5.4.12 */
+	OID_description,		/* 2.5.4.13 */
+	OID_name,			/* 2.5.4.41 */
+	OID_givenName,			/* 2.5.4.42 */
+	OID_initials,			/* 2.5.4.43 */
+	OID_generationalQualifier,	/* 2.5.4.44 */
+
+	/* Certificate extension IDs */
+	OID_subjectKeyIdentifier,	/* 2.5.29.14 */
+	OID_keyUsage,			/* 2.5.29.15 */
+	OID_subjectAltName,		/* 2.5.29.17 */
+	OID_issuerAltName,		/* 2.5.29.18 */
+	OID_basicConstraints,		/* 2.5.29.19 */
+	OID_crlDistributionPoints,	/* 2.5.29.31 */
+	OID_certPolicies,		/* 2.5.29.32 */
+	OID_authorityKeyIdentifier,	/* 2.5.29.35 */
+	OID_extKeyUsage,		/* 2.5.29.37 */
+
+	/* EC-RDSA */
+	OID_gostCPSignA,		/* 1.2.643.2.2.35.1 */
+	OID_gostCPSignB,		/* 1.2.643.2.2.35.2 */
+	OID_gostCPSignC,		/* 1.2.643.2.2.35.3 */
+	OID_gost2012PKey256,		/* 1.2.643.7.1.1.1.1 */
+	OID_gost2012PKey512,		/* 1.2.643.7.1.1.1.2 */
+	OID_gost2012Digest256,		/* 1.2.643.7.1.1.2.2 */
+	OID_gost2012Digest512,		/* 1.2.643.7.1.1.2.3 */
+	OID_gost2012Signature256,	/* 1.2.643.7.1.1.3.2 */
+	OID_gost2012Signature512,	/* 1.2.643.7.1.1.3.3 */
+	OID_gostTC26Sign256A,		/* 1.2.643.7.1.2.1.1.1 */
+	OID_gostTC26Sign256B,		/* 1.2.643.7.1.2.1.1.2 */
+	OID_gostTC26Sign256C,		/* 1.2.643.7.1.2.1.1.3 */
+	OID_gostTC26Sign256D,		/* 1.2.643.7.1.2.1.1.4 */
+	OID_gostTC26Sign512A,		/* 1.2.643.7.1.2.1.2.1 */
+	OID_gostTC26Sign512B,		/* 1.2.643.7.1.2.1.2.2 */
+	OID_gostTC26Sign512C,		/* 1.2.643.7.1.2.1.2.3 */
+
+	OID__NR
+};
+
+extern enum OID look_up_OID(const void *data, size_t datasize);
+extern int sprint_oid(const void *, size_t, char *, size_t);
+extern int sprint_OID(enum OID, char *, size_t);
+
+#endif /* _LINUX_OID_REGISTRY_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 26c94f49ecd2..d2955c8feb0e 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -527,6 +527,11 @@  config ASN1
 	help
 	  Enable asn1 decoder library.
 
+config OID_REGISTRY
+	bool
+	help
+	  Enable fast lookup object identifier registry.
+
 source lib/efi/Kconfig
 source lib/efi_loader/Kconfig
 source lib/optee/Kconfig
diff --git a/lib/Makefile b/lib/Makefile
index eb3a675fb8c2..677ec33a1ce1 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -118,4 +118,20 @@  else
 obj-y += vsprintf.o strto.o strmhz.o
 endif
 
+#
+# Build a fast OID lookip registry from include/linux/oid_registry.h
+#
+obj-$(CONFIG_OID_REGISTRY) += oid_registry.o
+
+$(obj)/oid_registry.o: $(obj)/oid_registry_data.c
+
+$(obj)/oid_registry_data.c: $(srctree)/include/linux/oid_registry.h \
+			    $(src)/build_OID_registry
+	$(call cmd,build_OID_registry)
+
+quiet_cmd_build_OID_registry = GEN     $@
+      cmd_build_OID_registry = perl $(srctree)/$(src)/build_OID_registry $< $@
+
+clean-files     += oid_registry_data.c
+
 subdir-ccflags-$(CONFIG_CC_OPTIMIZE_LIBS_FOR_SPEED) += -O2
diff --git a/lib/build_OID_registry b/lib/build_OID_registry
new file mode 100755
index 000000000000..d7fc32ea8ac2
--- /dev/null
+++ b/lib/build_OID_registry
@@ -0,0 +1,203 @@ 
+#!/usr/bin/perl -w
+# SPDX-License-Identifier: GPL-2.0-or-later
+#
+# Build a static ASN.1 Object Identified (OID) registry
+#
+# Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+# Written by David Howells (dhowells@redhat.com)
+#
+
+use strict;
+
+my @names = ();
+my @oids = ();
+
+if ($#ARGV != 1) {
+    print STDERR "Format: ", $0, " <in-h-file> <out-c-file>\n";
+    exit(2);
+}
+
+#
+# Open the file to read from
+#
+open IN_FILE, "<$ARGV[0]" || die;
+while (<IN_FILE>) {
+    chomp;
+    if (m!\s+OID_([a-zA-z][a-zA-Z0-9_]+),\s+/[*]\s+([012][.0-9]*)\s+[*]/!) {
+	push @names, $1;
+	push @oids, $2;
+    }
+}
+close IN_FILE || die;
+
+#
+# Open the files to write into
+#
+open C_FILE, ">$ARGV[1]" or die;
+print C_FILE "/*\n";
+print C_FILE " * Automatically generated by ", $0, ".  Do not edit\n";
+print C_FILE " */\n";
+
+#
+# Split the data up into separate lists and also determine the lengths of the
+# encoded data arrays.
+#
+my @indices = ();
+my @lengths = ();
+my $total_length = 0;
+
+for (my $i = 0; $i <= $#names; $i++) {
+    my $name = $names[$i];
+    my $oid = $oids[$i];
+
+    my @components = split(/[.]/, $oid);
+
+    # Determine the encoded length of this OID
+    my $size = $#components;
+    for (my $loop = 2; $loop <= $#components; $loop++) {
+	my $c = $components[$loop];
+
+	# We will base128 encode the number
+	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
+	$tmp = int($tmp / 7);
+	$size += $tmp;
+    }
+    push @lengths, $size;
+    push @indices, $total_length;
+    $total_length += $size;
+}
+
+#
+# Emit the look-up-by-OID index table
+#
+print C_FILE "\n";
+if ($total_length <= 255) {
+    print C_FILE "static const unsigned char oid_index[OID__NR + 1] = {\n";
+} else {
+    print C_FILE "static const unsigned short oid_index[OID__NR + 1] = {\n";
+}
+for (my $i = 0; $i <= $#names; $i++) {
+    print C_FILE "\t[OID_", $names[$i], "] = ", $indices[$i], ",\n"
+}
+print C_FILE "\t[OID__NR] = ", $total_length, "\n";
+print C_FILE "};\n";
+
+#
+# Encode the OIDs
+#
+my @encoded_oids = ();
+
+for (my $i = 0; $i <= $#names; $i++) {
+    my @octets = ();
+
+    my @components = split(/[.]/, $oids[$i]);
+
+    push @octets, $components[0] * 40 + $components[1];
+
+    for (my $loop = 2; $loop <= $#components; $loop++) {
+	my $c = $components[$loop];
+
+	# Base128 encode the number
+	my $tmp = ($c == 0) ? 0 : int(log($c)/log(2));
+	$tmp = int($tmp / 7);
+
+	for (; $tmp > 0; $tmp--) {
+	    push @octets, (($c >> $tmp * 7) & 0x7f) | 0x80;
+	}
+	push @octets, $c & 0x7f;
+    }
+
+    push @encoded_oids, \@octets;
+}
+
+#
+# Create a hash value for each OID
+#
+my @hash_values = ();
+for (my $i = 0; $i <= $#names; $i++) {
+    my @octets = @{$encoded_oids[$i]};
+
+    my $hash = $#octets;
+    foreach (@octets) {
+	$hash += $_ * 33;
+    }
+
+    $hash = ($hash >> 24) ^ ($hash >> 16) ^ ($hash >> 8) ^ ($hash);
+
+    push @hash_values, $hash & 0xff;
+}
+
+#
+# Emit the OID data
+#
+print C_FILE "\n";
+print C_FILE "static const unsigned char oid_data[", $total_length, "] = {\n";
+for (my $i = 0; $i <= $#names; $i++) {
+    my @octets = @{$encoded_oids[$i]};
+    print C_FILE "\t";
+    print C_FILE $_, ", " foreach (@octets);
+    print C_FILE "\t// ", $names[$i];
+    print C_FILE "\n";
+}
+print C_FILE "};\n";
+
+#
+# Build the search index table (ordered by length then hash then content)
+#
+my @index_table = ( 0 .. $#names );
+
+@index_table = sort {
+    my @octets_a = @{$encoded_oids[$a]};
+    my @octets_b = @{$encoded_oids[$b]};
+
+    return $hash_values[$a] <=> $hash_values[$b]
+	if ($hash_values[$a] != $hash_values[$b]);
+    return $#octets_a <=> $#octets_b
+	if ($#octets_a != $#octets_b);
+    for (my $i = $#octets_a; $i >= 0; $i--) {
+	return $octets_a[$i] <=> $octets_b[$i]
+	    if ($octets_a[$i] != $octets_b[$i]);
+    }
+    return 0;
+
+} @index_table;
+
+#
+# Emit the search index and hash value table
+#
+print C_FILE "\n";
+print C_FILE "static const struct {\n";
+print C_FILE "\tunsigned char hash;\n";
+if ($#names <= 255) {
+    print C_FILE "\tenum OID oid : 8;\n";
+} else {
+    print C_FILE "\tenum OID oid : 16;\n";
+}
+print C_FILE "} oid_search_table[OID__NR] = {\n";
+for (my $i = 0; $i <= $#names; $i++) {
+    my @octets = @{$encoded_oids[$index_table[$i]]};
+    printf(C_FILE "\t[%3u] = { %3u, OID_%-35s }, // ",
+	   $i,
+	   $hash_values[$index_table[$i]],
+	   $names[$index_table[$i]]);
+    printf C_FILE "%02x", $_ foreach (@octets);
+    print C_FILE "\n";
+}
+print C_FILE "};\n";
+
+#
+# Emit the OID debugging name table
+#
+#print C_FILE "\n";
+#print C_FILE "const char *const oid_name_table[OID__NR + 1] = {\n";
+#
+#for (my $i = 0; $i <= $#names; $i++) {
+#    print C_FILE "\t\"", $names[$i], "\",\n"
+#}
+#print C_FILE "\t\"Unknown-OID\"\n";
+#print C_FILE "};\n";
+
+#
+# Polish off
+#
+close C_FILE or die;
diff --git a/lib/oid_registry.c b/lib/oid_registry.c
new file mode 100644
index 000000000000..209edc73b99f
--- /dev/null
+++ b/lib/oid_registry.c
@@ -0,0 +1,179 @@ 
+// SPDX-License-Identifier: GPL-2.0-or-later
+/* ASN.1 Object identifier (OID) registry
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ */
+
+#ifdef __UBOOT__
+#include <linux/compat.h>
+#else
+#include <linux/module.h>
+#include <linux/export.h>
+#endif
+#include <linux/oid_registry.h>
+#include <linux/kernel.h>
+#include <linux/errno.h>
+#include <linux/bug.h>
+#include "oid_registry_data.c"
+
+MODULE_DESCRIPTION("OID Registry");
+MODULE_AUTHOR("Red Hat, Inc.");
+MODULE_LICENSE("GPL");
+
+/**
+ * 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);
+
+/*
+ * sprint_OID - Print an Object Identifier into a buffer
+ * @data: The encoded OID to print
+ * @datasize: The size of the encoded OID
+ * @buffer: The buffer to render into
+ * @bufsize: The size of the buffer
+ *
+ * The OID is rendered into the buffer in "a.b.c.d" format and the number of
+ * bytes is returned.  -EBADMSG is returned if the data could not be intepreted
+ * and -ENOBUFS if the buffer was too small.
+ */
+int sprint_oid(const void *data, size_t datasize, char *buffer, size_t bufsize)
+{
+	const unsigned char *v = data, *end = v + datasize;
+	unsigned long num;
+	unsigned char n;
+	size_t ret;
+	int count;
+
+	if (v >= end)
+		goto bad;
+
+	n = *v++;
+	ret = count = snprintf(buffer, bufsize, "%u.%u", n / 40, n % 40);
+	if (count >= bufsize)
+		return -ENOBUFS;
+	buffer += count;
+	bufsize -= count;
+
+	while (v < end) {
+		num = 0;
+		n = *v++;
+		if (!(n & 0x80)) {
+			num = n;
+		} else {
+			num = n & 0x7f;
+			do {
+				if (v >= end)
+					goto bad;
+				n = *v++;
+				num <<= 7;
+				num |= n & 0x7f;
+			} while (n & 0x80);
+		}
+		ret += count = snprintf(buffer, bufsize, ".%lu", num);
+		if (count >= bufsize)
+			return -ENOBUFS;
+		buffer += count;
+		bufsize -= count;
+	}
+
+	return ret;
+
+bad:
+	snprintf(buffer, bufsize, "(bad)");
+	return -EBADMSG;
+}
+EXPORT_SYMBOL_GPL(sprint_oid);
+
+/**
+ * sprint_OID - Print an Object Identifier into a buffer
+ * @oid: The OID to print
+ * @buffer: The buffer to render into
+ * @bufsize: The size of the buffer
+ *
+ * The OID is rendered into the buffer in "a.b.c.d" format and the number of
+ * bytes is returned.
+ */
+int sprint_OID(enum OID oid, char *buffer, size_t bufsize)
+{
+	int ret;
+
+	BUG_ON(oid >= OID__NR);
+
+	ret = sprint_oid(oid_data + oid_index[oid],
+			 oid_index[oid + 1] - oid_index[oid],
+			 buffer, bufsize);
+	BUG_ON(ret == -EBADMSG);
+	return ret;
+}
+EXPORT_SYMBOL_GPL(sprint_OID);