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 <linux/kernel.h>
  15 #include <linux/errno.h>
  16 #include <linux/bug.h>
  17 #include "oid_registry_data.c"
  18
  19 /**
  20  * look_up_OID - Find an OID registration for the specified data
  21  * @data: Binary representation of the OID
  22  * @datasize: Size of the binary representation
  23  */
  24 enum OID look_up_OID(const void *data, size_t datasize)
  25 {
  26         const unsigned char *octets = data;
  27         enum OID oid;
  28         unsigned char xhash;
  29         unsigned i, j, k, hash;
  30         size_t len;
  31
  32         /* Hash the OID data */
  33         hash = datasize - 1;
  34
  35         for (i = 0; i < datasize; i++)
  36                 hash += octets[i] * 33;
  37         hash = (hash >> 24) ^ (hash >> 16) ^ (hash >> 8) ^ hash;
  38         hash &= 0xff;
  39
  40         /* Binary search the OID registry.  OIDs are stored in ascending order
  41          * of hash value then ascending order of size and then in ascending
  42          * order of reverse value.
  43          */
  44         i = 0;
  45         k = OID__NR;
  46         while (i < k) {
  47                 j = (i + k) / 2;
  48
  49                 xhash = oid_search_table[j].hash;
  50                 if (xhash > hash) {
  51                         k = j;
  52                         continue;
  53                 }
  54                 if (xhash < hash) {
  55                         i = j + 1;
  56                         continue;
  57                 }
  58
  59                 oid = oid_search_table[j].oid;
  60                 len = oid_index[oid + 1] - oid_index[oid];
  61                 if (len > datasize) {
  62                         k = j;
  63                         continue;
  64                 }
  65                 if (len < datasize) {
  66                         i = j + 1;
  67                         continue;
  68                 }
  69
  70                 /* Variation is most likely to be at the tail end of the
  71                  * OID, so do the comparison in reverse.
  72                  */
  73                 while (len > 0) {
  74                         unsigned char a = oid_data[oid_index[oid] + --len];
  75                         unsigned char b = octets[len];
  76                         if (a > b) {
  77                                 k = j;
  78                                 goto next;
  79                         }
  80                         if (a < b) {
  81                                 i = j + 1;
  82                                 goto next;
  83                         }
  84                 }
  85                 return oid;
  86         next:
  87                 ;
  88         }
  89
  90         return OID__NR;
  91 }
  92 EXPORT_SYMBOL_GPL(look_up_OID);
  93
  94 /*
  95  * sprint_OID - Print an Object Identifier into a buffer
  96  * @data: The encoded OID to print
  97  * @datasize: The size of the encoded OID
  98  * @buffer: The buffer to render into
  99  * @bufsize: The size of the buffer
 100  *
 101  * The OID is rendered into the buffer in "a.b.c.d" format and the number of
 102  * bytes is returned.  -EBADMSG is returned if the data could not be intepreted
 103  * and -ENOBUFS if the buffer was too small.
 104  */
 105 int sprint_oid(const void *data, size_t datasize, char *buffer, size_t bufsize)
 106 {
 107         const unsigned char *v = data, *end = v + datasize;
 108         unsigned long num;
 109         unsigned char n;
 110         size_t ret;
 111         int count;
 112
 113         if (v >= end)
 114                 return -EBADMSG;
 115
 116         n = *v++;
 117         ret = count = snprintf(buffer, bufsize, "%u.%u", n / 40, n % 40);
 118         buffer += count;
 119         bufsize -= count;
 120         if (bufsize == 0)
 121                 return -ENOBUFS;
 122
 123         while (v < end) {
 124                 num = 0;
 125                 n = *v++;
 126                 if (!(n & 0x80)) {
 127                         num = n;
 128                 } else {
 129                         num = n & 0x7f;
 130                         do {
 131                                 if (v >= end)
 132                                         return -EBADMSG;
 133                                 n = *v++;
 134                                 num <<= 7;
 135                                 num |= n & 0x7f;
 136                         } while (n & 0x80);
 137                 }
 138                 ret += count = snprintf(buffer, bufsize, ".%lu", num);
 139                 buffer += count;
 140                 bufsize -= count;
 141                 if (bufsize == 0)
 142                         return -ENOBUFS;
 143         }
 144
 145         return ret;
 146 }
 147 EXPORT_SYMBOL_GPL(sprint_oid);
 148
 149 /**
 150  * sprint_OID - Print an Object Identifier into a buffer
 151  * @oid: The OID to print
 152  * @buffer: The buffer to render into
 153  * @bufsize: The size of the buffer
 154  *
 155  * The OID is rendered into the buffer in "a.b.c.d" format and the number of
 156  * bytes is returned.
 157  */
 158 int sprint_OID(enum OID oid, char *buffer, size_t bufsize)
 159 {
 160         int ret;
 161
 162         BUG_ON(oid >= OID__NR);
 163
 164         ret = sprint_oid(oid_data + oid_index[oid],
 165                          oid_index[oid + 1] - oid_index[oid],
 166                          buffer, bufsize);
 167         BUG_ON(ret == -EBADMSG);
 168         return ret;
 169 }
 170 EXPORT_SYMBOL_GPL(sprint_OID);