BEGIN {
    entry = 0
    total_length = 0
    while ((getline < ARGV[1]) > 0) {
        if (match($0, /^[[:space:]]*OID_[[:alpha:]][[:alnum:]_]+,/) > 0) {
            name = substr($0, RSTART, RLENGTH - 1)
            sub(/^[[:space:]]*OID_/, "", name)
            if (match($0, /^[[:space:]]*OID_[[:alpha:]][[:alnum:]_]+,[[:space:]]+\/\*[[:space:]]+[012][[:digit:]\.]*[[:space:]]+\*\//) > 0) {
                entry++

                oid = substr($0, RSTART, RLENGTH)
                sub(/[[:space:]]*\*\/$/, "", oid)
                sub(/[[:space:]]*OID_[[:alpha:]][[:alnum:]_]+,[[:space:]]+\/\*[[:space:]]+/, "", oid)

                mutable_oid = oid
                component_count = 0
                while (1) {
                    if (match(mutable_oid, /^[^.]+/) > 0) {
                        components[++component_count] = substr(mutable_oid, RSTART, RLENGTH)
                        sub(/^[^.]+(\.)?/, "", mutable_oid)
                    } else break
                }
                bytes[entry, 1] = components[1] * 40 + components[2]
                bytes_length[entry] = 1
                for (i = 3; i <= component_count; i++) {
                    component = components[i]
                    start = bytes_length[entry] + 1
                    while (component > 0) {
                        insert2D(bytes, entry, bytes_length[entry], start, or(and(component, 0x7f), 0x80))
                        bytes_length[entry]++
                        component = rshift(component, 7)
                    }
                    bytes[entry, bytes_length[entry]] = and(bytes[entry, bytes_length[entry]], 0x7f)
                }
                hash = bytes_length[entry] - 1
                for (i2 = 1; i2 <= bytes_length[entry]; i2++) {
                    hash = hash + bytes[entry, i2] * 33
                }

                names[entry] = name
                oids[entry] = oid
                indexes[entry] = total_length
                hashes[entry] = and(0xff, xor(hash, rshift(hash, 8), rshift(hash, 16), rshift(hash, 24)))
                total_length += bytes_length[entry]
            }
        }
    }

    print "/*" > ARGV[2]
    print " * Automatically generated by ./lib/build_OID_registry. Do not edit" >> ARGV[2]
    print " */" >> ARGV[2]

    if (total_length <= 255) int_type = "char"
    else int_type = "short"
    printf("\nstatic const unsigned %s oid_index[OID__NR + 1] = {\n", int_type) >> ARGV[2]
    for (i3 = 1; i3 <= entry; i3++) {
        printf("\t[OID_%s] = %d,\n", names[i3], indexes[i3]) >> ARGV[2]
    }
    printf("\t[OID__NR] = %d\n", total_length) >> ARGV[2]
    print "};" >> ARGV[2]

    printf("\nstatic const unsigned char oid_data[%d] = {\n", total_length) >> ARGV[2]
    for (i4 = 1; i4 <= entry; i4++) {
        printf("\t%s, \t// %s\n", concat2D(bytes, i4, bytes_length[i4], ", "), names[i4]) >> ARGV[2]
    }
    print "};" >> ARGV[2]

    sort(entry, names, oids, indexes, hashes, bytes, bytes_length)

    if (entry <= 255) numbits = 8
    else numbits = 16
    print "" >> ARGV[2]
    print "static const struct {" >> ARGV[2]
    print "\tunsigned char hash;" >> ARGV[2]
    printf("\tenum OID oid : %d;\n", numbits) >> ARGV[2]
    print "} oid_search_table[OID__NR] = {" >> ARGV[2]
    for (i5 = 1; i5 <= entry; i5++) {
        hex_length = 0
        for (i6 = 1; i6 <= bytes_length[i5]; i6++) {
            hex[i6] = sprintf("%02x", bytes[i5, i6])
            hex_length++
        }
        printf("\t[%3d] = { %3d, OID_%-35s }, // %s\n", i5 - 1, hashes[i5], names[i5], concat(hex, hex_length)) >> ARGV[2]
    }
    print "};" >> ARGV[2]
}

function insert2D(A, entry, last, start, value,    stop, s) {
    for (stop = last; stop >= start; stop--) {
        A[entry, stop + 1] = A[entry, stop]
    }
    A[entry, start] = value
}

function concat(A, count,    s, i) {
    s = ""
    for (i = 1; i <= count; i++) s = s A[i]
    return s
}

function concat2D(A, d1, count, delimiter,    s, i) {
    s = ""
    for (i = 1; i <= count; i++) {
        if (i == count) s = s A[d1, i]
        else s = s A[d1, i] delimiter
    }
    return s
}

function swap(A, e1, e2,    tmp) {
    tmp = A[e1]
    A[e1] = A[e2]
    A[e2] = tmp
}

function sorter(e1, e2, hashes, bytes, bytes_length,    i) {
    if (hashes[e1] != hashes[e2]) return hashes[e1] < hashes[e2]
    else if (bytes_length[e1] != bytes_length[e2]) {
        return bytes_length[e1] < bytes_length[e2]
    }
    for (i = bytes_length[e1]; i >= 1; i--) {
        if (bytes[e1, i] != bytes[e2, i]) return bytes[e1, i] < bytes[e2 , i]
    }
}

function sort(entry, names, oids, indexes, hashes, bytes, bytes_length,    ran_sort, e1, e2, skip_sort) {
    while (1) {
        ran_sort = 0
        for (e1 = 1; e1 < entry; e1++) {
            e2 = (e1 + 1) >= entry ? entry : e1 + 1
            if (sorter(e1, e2, hashes, bytes, bytes_length) == 0) {
                ran_sort = 1
                swap(names, e1, e2)
                swap(oids, e1, e2)
                swap(indexes, e1, e2)
                swap(hashes, e1, e2)
                for (i = 1; i <= bytes_length[e1]; i++) bytes_tmp[i] = bytes[e1, i]
                for (i = 1; i <= bytes_length[e2]; i++) bytes[e1, i] = bytes[e2, i]
                for (i = 1; i <= bytes_length[e1]; i++) bytes[e2, i] = bytes_tmp[i]
                swap(bytes_length, e1, e2)
            }
        }
        if (ran_sort == 0) break
    }
}