lib/oid_registry.c

   1 /* ASN.1 Object identifier (OID) registry
   2  *
   3  * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
   4  * Written by David Howells (dhowells@redhat.com)
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public Licence
   8  * as published by the Free Software Foundation; either version
   9  * 2 of the Licence, or (at your option) any later version.
  10  */
  11
  12 #include <linux/export.h>
  13 #include <linux/oid_registry.h>
  14 #include "oid_registry_data.c"
  15
  16 /**
  17  * look_up_OID - Find an OID registration for the specified data
  18  * @data: Binary representation of the OID
  19  * @datasize: Size of the binary representation
  20  */
  21 enum OID look_up_OID(const void *data, size_t datasize)
  22 {
  23         const unsigned char *octets = data;
  24         enum OID oid;
  25         unsigned char xhash;
  26         unsigned i, j, k, hash;
  27         size_t len;
  28
  29         /* Hash the OID data */
  30         hash = datasize - 1;
  31
  32         for (i = 0; i < datasize; i++)
  33                 hash += octets[i] * 33;
  34         hash = (hash >> 24) ^ (hash >> 16) ^ (hash >> 8) ^ hash;
  35         hash &= 0xff;
  36
  37         /* Binary search the OID registry.  OIDs are stored in ascending order
  38          * of hash value then ascending order of size and then in ascending
  39          * order of reverse value.
  40          */
  41         i = 0;
  42         k = OID__NR;
  43         while (i < k) {
  44                 j = (i + k) / 2;
  45
  46                 xhash = oid_search_table[j].hash;
  47                 if (xhash > hash) {
  48                         k = j;
  49                         continue;
  50                 }
  51                 if (xhash < hash) {
  52                         i = j + 1;
  53                         continue;
  54                 }
  55
  56                 oid = oid_search_table[j].oid;
  57                 len = oid_index[oid + 1] - oid_index[oid];
  58                 if (len > datasize) {
  59                         k = j;
  60                         continue;
  61                 }
  62                 if (len < datasize) {
  63                         i = j + 1;
  64                         continue;
  65                 }
  66
  67                 /* Variation is most likely to be at the tail end of the
  68                  * OID, so do the comparison in reverse.
  69                  */
  70                 while (len > 0) {
  71                         unsigned char a = oid_data[oid_index[oid] + --len];
  72                         unsigned char b = octets[len];
  73                         if (a > b) {
  74                                 k = j;
  75                                 goto next;
  76                         }
  77                         if (a < b) {
  78                                 i = j + 1;
  79                                 goto next;
  80                         }
  81                 }
  82                 return oid;
  83         next:
  84                 ;
  85         }
  86
  87         return OID__NR;
  88 }
  89 EXPORT_SYMBOL_GPL(look_up_OID);