path: root/third_party/heimdal/lib/asn1/README.md

# Heimdal's ASN.1 Compiler

This is a new README, and it's not very rich in contents yet.  Be sure to check
out the [README on the template backend](/lib/asn1/README-template.md) and the [README
on automatic open type decoding via X.681/X.682/X.683
annotations](/lib/asn1/README-X681.md).

## Table of Contents

 1. [Introduction](#Introduction)
 2. [ASN.1 Support in Heimdal](#asn1-support-in-heimdal)
 3. [News](#News)
 4. [Features](#Features)
 5. [Limitations](#Limitations)
 6. [Compiler Usage](#Compiler-usage)
 7. [APIs Generated by the Compiler](#APIs-generated-by-the-compiler)
 8. [`asn1_print` Usage](#asn1_print-usage)
 9. [Implementation](#implementation)
 10. [Moving From C](#moving-from-c)

## Introduction

ASN.1 is a... some would say baroque, perhaps obsolete, archaic even, "syntax"
for expressing data type schemas, and also a set of "encoding rules" (ERs) that
specify many ways to encode values of those types for interchange.

Some ERs are binary, others are textual.  Some binary ERs are tag-length-value
(TLV), others have no need for tagging.  Some of the ERs are roundly and
rightly disliked, but then there are XER (XML Encoding Rules) and JER (JSON
Encoding Rules) that really illustrate how the syntax and the encoding rules
really are separate and distinct things.

ASN.1 is a wheel that everyone loves to reinvent, and often badly.  It's worth
knowing a bit about it before reinventing this wheel badly yet again.

It's also worth pondering that there appears to be ways to map most data
exchange metaschemas and schemas onto others, and therefore too, transliterate
most encodings onto others.

First, an example of the syntax:

```ASN.1
-- This is what a certificate looks like (as in TLS server certificates, or
-- "SSL certs):
Certificate  ::=  SEQUENCE  {
     tbsCertificate       TBSCertificate,
     signatureAlgorithm   AlgorithmIdentifier,
     signatureValue       BIT STRING
}

-- The main body of a certificate is here though:
TBSCertificate  ::=  SEQUENCE  {
     version         [0]  Version DEFAULT 1,
     serialNumber         CertificateSerialNumber,
     signature            AlgorithmIdentifier,
     issuer               Name,
     validity             Validity,
     subject              Name,
     subjectPublicKeyInfo SubjectPublicKeyInfo,
     issuerUniqueID  [1]  IMPLICIT BIT STRING OPTIONAL,
     subjectUniqueID [2]  IMPLICIT BIT STRING OPTIONAL,
     extensions      [3]  EXPLICIT Extensions OPTIONAL
}
```

Here we see something akin to a "structure" or "record" with various named
fields of various types.  Some of these are optional, which means they can have
no value given in encodings.  One is defaulted, which means that if no values
is given in encodings then the default value is intended.

Those `[0]` things are called tags and are decidedly obsolete, along with all
"tag-length-value" (TLV) or "self-describing" encoding rules.  Tags appear as
lexical tokens in ASN.1 only because a) in the early 80s TLV encodings were
thought fantastic, and b) automatic tagging wasn't invented and implemented
until it was too late.  New ASN.1 modules should never need to have those tags
appear in the syntax.

ASN.1 has a lot of competition, and may even be obsolete.  Obsolete
technologies take decades to die out because of the need to interoperate with
the installed base.  So even if ASN.1 is obsolete, we find ourselves needing to
implement a large subset of it in order to implement certain important network
protocols.

Encoding rules?  There are many:

 - JSON Encoding Rules (JER) ([X.697](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.697))

   Use JSON instead of some binary scheme like DER (see below).

 - XML Encoding Rules (XER) ([X.693](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.693))

 - Generic String Encoding Rules (GSER) ([RFC3641](https://tools.ietf.org/html/rfc3641))

 - Basic, Distinguished, and Canonical Encoding Rules (BER, DER, CER) ([X.690](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.690)

   These are the dreaded tag-length-value encoding rules.  They are redundant,
   wasteful, and inefficient in spite of being non-textual (i.e., binary)!

   The descriptor "tag-length-value" is due to all values being encoded as some
   bytes for a "tag", then some bytes for the length of the encoded value, then
   the encoded value itself.  The body of a structured type (e.g.,
   `Certificate`) is itself a concatenation of the TLV encodings of the fields
   of that structured type, in order.

   DER and CER are alternative canonical forms of BER.

 - Packed Encoding Rules (PER) ([X.691](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.691)) and Octet Encoding Rules (OER) ([X.696](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.696))

   These are a lot like eXternal Data Representation
   ([XDR](https://tools.ietf.org/html/rfc4506.html)), but with 1-octet
   alignment instead of 4-octet alignment.

There is also a meta encoding rule system, the Encoding Control Notation (ECN)
([X.692](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.692))
intended to be able to express all sorts of kinds of encodings.

Heimdal currently only supports DER for encoding, and DER and BER for decoding,
but soon may support JER as well, and can print values as JSON, though not
compliant with JER.

The syntax itself is specified by
[X.680](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.680),
with extensions via
[X.681](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.681),
[X.682](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.682),
and
[X.683](https://www.itu.int/rec/T-REC-X/recommendation.asp?lang=en&parent=T-REC-X.683),.

## ASN.1 Support in Heimdal

Heimdal contains an implementation of:

 - ASN.1
 - PKIX
 - Kerberos
 - misc. Heimdal-specific protocols related to PKIX and Kerberos, such as:

    - Online certification authority protocols
    - Kerberos KDC replication protocols
    - Kerberos administration protocols

PKIX and Kerberos both require ASN.1 and DER support.

For historical reasons many ASN.1-using projects have used hand-rolled codecs
that have proven difficult to implement, maintain, and extend, and, of course,
buggy.  Heimdal has its own ASN.1 module compiler and library in order to avoid
the pitfalls of hand-rolled codecs, and to satisfy Heimdal's internal needs.

There are other ASN.1 compilers and libraries out there, of course, but it
would prove difficult to switch compilers as generally ASN.1 compilers lack
sufficient control over generated types and APIs for programming languages.

Heimdal's ASN.1 compiler supports a large subset of X.680, X.681, X.682, and
X.683, as well as a large subset of X.690, with an architecture that should
make it easy to add support for encoding rules other than X.690.

## News

In recent times the following features have been added:

 - Feature parity for the "template" backend, even superiority, as the codegen
   backend does not yet support automatic open type decoding/encoding.

 - IMPLICIT tagging support is finally complete.

 - Automatic open type traversal, using a subset of X.681/X.682/X.683 for
   expressing the requisite metadata.

 - Decoration of ASN.1 types with "hidden" fields (ones that don't get encoded
   or decoded) of ASN.1 or C types.

## Futures

 - JER support?

 - XDR/NDR/OER support?

 - Generate comparators?  (lib/hx509 has a half-baked Certificate comparator)

## Features

 - Most of X.680 is supported.

 - Most of X.690 is supported for decoding, with only DER supported for
   encoding.

 - For cryptographic applications there is a `--preserve-binary=TYPE` compiler
   option that causes the `TYPE`'s C `struct` to gain a `_save` field where the
   original encoding of the `TYPE` is preserved by the decoder.  This allows
   cryptographic applications to validate signatures, MACs, authenticated
   decryption tags, checksums, etc., without having to re-encode the `TYPE`
   (which wouldn't even work if the encoding received were BER and BER were
   permitted for that `TYPE`).

 - Unconstrained integer types have a large integer representation in C that is
   not terribly useful in common cases.  Range and member constraints on
   integer types cause the compiler to use `int`, `int64_t`, `unsigned int`,
   and/or `uint64_t` as appropriate.

 - The Heimdal ASN.1 compiler currently handles a large subset of X.680, and
   (in a branch) a small subset of X.681, X.682, and X.683, which manifests as
   automatic handling of all open types contained in `SET`/`SEQUENCE` types
   that are parameterized with information object sets.  This allows all open
   types in PKIX certificates, for example, to get decoded automatically no
   matter how deeply nested.  We use a TCG EK certificate that has eight
   certificate extensions, including subject alternative names and subject
   directory attributes where the attribute values are not string types, and
   all of these things get decoded automatically.

 - The template backend dedups templates to save space.  This is an O(N^2) kind
   of feature that we need to make optional, but it works.  (When we implement
   JER this will have the side-effect of printing the wrong type names in some
   cases because two or more types have the same templates and get deduped.)

 - There is an _experimental_ ASN.1 module -> JSON feature in the compiler.  It
   currently dumps type and value definitions, but not class, or object set
   definitions.  Even for types, it is not complete, and the JSON schema used
   is subject to change *WITHOUT NOTICE*.

   Perhaps eventually we can re-write the compiler as a C-coded ASN.1 -> JSON
   stage followed by a jq-coded code and template generator state, which would
   make it much easier to extend the compiler.

 - We have an `asn1_print` program that can decode DER from any exported types
   from any ASN.1 modules committed in Heimdal:

   ```bash
   $ ./asn1_print ek.crt Certificate |
     jq '.tbsCertificate.extensions[3]._extnValue[]._values'
   ```

   ```JSON
   [
     {
       "_type": "TPMSpecification",
       "family": "2.0",
       "level": 0,
       "revision": 138
     }
   ]
   [
     {
       "_type": "TPMSecurityAssertions",
       "version": 0,
       "fieldUpgradable": true,
       "ekGenerationType": "ekgt-injected",
       "ekGenerationLocation": "tpmManufacturer",
       "ekCertificateGenerationLocation": "tpmManufacturer",
       "ccInfo": {
         "_type": "CommonCriteriaMeasures",
         "version": "3.1",
         "assurancelevel": "ealevel4",
         "evaluationStatus": "evaluationCompleted",
         "plus": true,
         "strengthOfFunction": null,
         "profileOid": null,
         "profileUri": null,
         "targetOid": null,
         "targetUri": null
       },
       "fipsLevel": {
         "_type": "FIPSLevel",
         "version": "140-2",
         "level": "sllevel2",
         "plus": false
       },
       "iso9000Certified": false,
       "iso9000Uri": null
     }
   ]
   ```

   A complete dump of such a certificate:

   ```bash
   $ ./asn1_print ek.crt Certificate | jq .
   ```

   ```JSON
   {
     "_type": "Certificate",
     "tbsCertificate": {
       "_type": "TBSCertificate",
       "_save": "30820376A00302010202146A0597BA71D7E6D3AC0EDC9EDC95A15B998DE40A300D06092A864886F70D01010B05003055310B3009060355040613024348311E301C060355040A131553544D6963726F656C656374726F6E696373204E56312630240603550403131D53544D2054504D20454B20496E7465726D656469617465204341203035301E170D3138313231343030303030305A170D3238313231343030303030305A300030820122300D06092A864886F70D01010105000382010F003082010A0282010100CC14EB27A78CEB0EA486FA2DF7835F5FA8E905B097012B5BDE50380C355B1A2A721BBC3D08DD21796CDB239FA95310651B1B56FD2CFE53C87352EBD996E33256160404CE9302A08066801E786A2F86E181F949966F492A85B58EAA4A6A8CB3697551BB236E87CC7BF8EC1347871C91E15437E8F266BF1EA5EB271FDCF374D8B47DF8BCE89E1FAD61C2A088CB4036B359CB72A294973FEDCCF0C340AFFD14B64F041165581ACA34147C1C75617047058F7ED7D603E032508094FA73E8B9153DA3BF255D2CBBC5DF301BA8F74D198BEBCE86040FC1D2927C7657414490D802F482F3EBF2DE35EE149A1A6DE8D16891FBFBA02A18AFE59F9D6F149744E5F0D559B10203010001A38201A9308201A5301F0603551D230418301680141ADB994AB58BE57A0CC9B900E7851E1A43C0866030420603551D20043B303930370604551D2000302F302D06082B060105050702011621687474703A2F2F7777772E73742E636F6D2F54504D2F7265706F7369746F72792F30590603551D110101FF044F304DA44B304931163014060567810502010C0B69643A353335343444323031173015060567810502020C0C53543333485450484148433031163014060567810502030C0B69643A303034393030303830670603551D090460305E301706056781050210310E300C0C03322E300201000202008A304306056781050212313A30380201000101FFA0030A0101A1030A0100A2030A0100A310300E1603332E310A01040A01020101FFA40F300D16053134302D320A0102010100300E0603551D0F0101FF040403020520300C0603551D130101FF0402300030100603551D250409300706056781050801304A06082B06010505070101043E303C303A06082B06010505073002862E687474703A2F2F7365637572652E676C6F62616C7369676E2E636F6D2F73746D74706D656B696E7430352E637274",
       "version": "rfc3280_version_3",
       "serialNumber": "6A0597BA71D7E6D3AC0EDC9EDC95A15B998DE40A",
       "signature": {
         "_type": "AlgorithmIdentifier",
         "algorithm": {
           "_type": "OBJECT IDENTIFIER",
           "oid": "1.2.840.113549.1.1.11",
           "components": [
             1,
             2,
             840,
             113549,
             1,
             1,
             11
           ],
           "name": "id-pkcs1-sha256WithRSAEncryption"
         },
         "parameters": "0500"
       },
       "issuer": {
         "_choice": "rdnSequence",
         "value": [
           [
             {
               "_type": "AttributeTypeAndValue",
               "type": {
                 "_type": "OBJECT IDENTIFIER",
                 "oid": "2.5.4.6",
                 "components": [
                   2,
                   5,
                   4,
                   6
                 ],
                 "name": "id-at-countryName"
               },
               "value": {
                 "_choice": "printableString",
                 "value": "CH"
               }
             }
           ],
           [
             {
               "_type": "AttributeTypeAndValue",
               "type": {
                 "_type": "OBJECT IDENTIFIER",
                 "oid": "2.5.4.10",
                 "components": [
                   2,
                   5,
                   4,
                   10
                 ],
                 "name": "id-at-organizationName"
               },
               "value": {
                 "_choice": "printableString",
                 "value": "STMicroelectronics NV"
               }
             }
           ],
           [
             {
               "_type": "AttributeTypeAndValue",
               "type": {
                 "_type": "OBJECT IDENTIFIER",
                 "oid": "2.5.4.3",
                 "components": [
                   2,
                   5,
                   4,
                   3
                 ],
                 "name": "id-at-commonName"
               },
               "value": {
                 "_choice": "printableString",
                 "value": "STM TPM EK Intermediate CA 05"
               }
             }
           ]
         ]
       },
       "validity": {
         "_type": "Validity",
         "notBefore": {
           "_choice": "utcTime",
           "value": "2018-12-14T00:00:00Z"
         },
         "notAfter": {
           "_choice": "utcTime",
           "value": "2028-12-14T00:00:00Z"
         }
       },
       "subject": {
         "_choice": "rdnSequence",
         "value": []
       },
       "subjectPublicKeyInfo": {
         "_type": "SubjectPublicKeyInfo",
         "algorithm": {
           "_type": "AlgorithmIdentifier",
           "algorithm": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "1.2.840.113549.1.1.1",
             "components": [
               1,
               2,
               840,
               113549,
               1,
               1,
               1
             ],
             "name": "id-pkcs1-rsaEncryption"
           },
           "parameters": "0500"
         },
         "subjectPublicKey": "2160:3082010A0282010100CC14EB27A78CEB0EA486FA2DF7835F5FA8E905B097012B5BDE50380C355B1A2A721BBC3D08DD21796CDB239FA95310651B1B56FD2CFE53C87352EBD996E33256160404CE9302A08066801E786A2F86E181F949966F492A85B58EAA4A6A8CB3697551BB236E87CC7BF8EC1347871C91E15437E8F266BF1EA5EB271FDCF374D8B47DF8BCE89E1FAD61C2A088CB4036B359CB72A294973FEDCCF0C340AFFD14B64F041165581ACA34147C1C75617047058F7ED7D603E032508094FA73E8B9153DA3BF255D2CBBC5DF301BA8F74D198BEBCE86040FC1D2927C7657414490D802F482F3EBF2DE35EE149A1A6DE8D16891FBFBA02A18AFE59F9D6F149744E5F0D559B10203010001"
       },
       "issuerUniqueID": null,
       "subjectUniqueID": null,
       "extensions": [
         {
           "_type": "Extension",
           "extnID": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "2.5.29.35",
             "components": [
               2,
               5,
               29,
               35
             ],
             "name": "id-x509-ce-authorityKeyIdentifier"
           },
           "critical": false,
           "extnValue": "301680141ADB994AB58BE57A0CC9B900E7851E1A43C08660",
           "_extnValue_choice": "ext-AuthorityKeyIdentifier",
           "_extnValue": {
             "_type": "AuthorityKeyIdentifier",
             "keyIdentifier": "1ADB994AB58BE57A0CC9B900E7851E1A43C08660",
             "authorityCertIssuer": null,
             "authorityCertSerialNumber": null
           }
         },
         {
           "_type": "Extension",
           "extnID": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "2.5.29.32",
             "components": [
               2,
               5,
               29,
               32
             ],
             "name": "id-x509-ce-certificatePolicies"
           },
           "critical": false,
           "extnValue": "303930370604551D2000302F302D06082B060105050702011621687474703A2F2F7777772E73742E636F6D2F54504D2F7265706F7369746F72792F",
           "_extnValue_choice": "ext-CertificatePolicies",
           "_extnValue": [
             {
               "_type": "PolicyInformation",
               "policyIdentifier": {
                 "_type": "OBJECT IDENTIFIER",
                 "oid": "2.5.29.32.0",
                 "components": [
                   2,
                   5,
                   29,
                   32,
                   0
                 ],
                 "name": "id-x509-ce-certificatePolicies-anyPolicy"
               },
               "policyQualifiers": [
                 {
                   "_type": "PolicyQualifierInfo",
                   "policyQualifierId": {
                     "_type": "OBJECT IDENTIFIER",
                     "oid": "1.3.6.1.5.5.7.2.1",
                     "components": [
                       1,
                       3,
                       6,
                       1,
                       5,
                       5,
                       7,
                       2,
                       1
                     ],
                     "name": "id-pkix-qt-cps"
                   },
                   "qualifier": "1621687474703A2F2F7777772E73742E636F6D2F54504D2F7265706F7369746F72792F"
                 }
               ]
             }
           ]
         },
         {
           "_type": "Extension",
           "extnID": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "2.5.29.17",
             "components": [
               2,
               5,
               29,
               17
             ],
             "name": "id-x509-ce-subjectAltName"
           },
           "critical": true,
           "extnValue": "304DA44B304931163014060567810502010C0B69643A353335343444323031173015060567810502020C0C53543333485450484148433031163014060567810502030C0B69643A3030343930303038",
           "_extnValue_choice": "ext-SubjectAltName",
           "_extnValue": [
             {
               "_choice": "directoryName",
               "value": {
                 "_choice": "rdnSequence",
                 "value": [
                   [
                     {
                       "_type": "AttributeTypeAndValue",
                       "type": {
                         "_type": "OBJECT IDENTIFIER",
                         "oid": "2.23.133.2.1",
                         "components": [
                           2,
                           23,
                           133,
                           2,
                           1
                         ],
                         "name": "tcg-at-tpmManufacturer"
                       },
                       "value": {
                         "_choice": "utf8String",
                         "value": "id:53544D20"
                       }
                     }
                   ],
                   [
                     {
                       "_type": "AttributeTypeAndValue",
                       "type": {
                         "_type": "OBJECT IDENTIFIER",
                         "oid": "2.23.133.2.2",
                         "components": [
                           2,
                           23,
                           133,
                           2,
                           2
                         ],
                         "name": "tcg-at-tpmModel"
                       },
                       "value": {
                         "_choice": "utf8String",
                         "value": "ST33HTPHAHC0"
                       }
                     }
                   ],
                   [
                     {
                       "_type": "AttributeTypeAndValue",
                       "type": {
                         "_type": "OBJECT IDENTIFIER",
                         "oid": "2.23.133.2.3",
                         "components": [
                           2,
                           23,
                           133,
                           2,
                           3
                         ],
                         "name": "tcg-at-tpmVersion"
                       },
                       "value": {
                         "_choice": "utf8String",
                         "value": "id:00490008"
                       }
                     }
                   ]
                 ]
               }
             }
           ]
         },
         {
           "_type": "Extension",
           "extnID": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "2.5.29.9",
             "components": [
               2,
               5,
               29,
               9
             ],
             "name": "id-x509-ce-subjectDirectoryAttributes"
           },
           "critical": false,
           "extnValue": "305E301706056781050210310E300C0C03322E300201000202008A304306056781050212313A30380201000101FFA0030A0101A1030A0100A2030A0100A310300E1603332E310A01040A01020101FFA40F300D16053134302D320A0102010100",
           "_extnValue_choice": "ext-SubjectDirectoryAttributes",
           "_extnValue": [
             {
               "_type": "AttributeSet",
               "type": {
                 "_type": "OBJECT IDENTIFIER",
                 "oid": "2.23.133.2.16",
                 "components": [
                   2,
                   23,
                   133,
                   2,
                   16
                 ],
                 "name": "tcg-at-tpmSpecification"
               },
               "values": [
                 "300C0C03322E300201000202008A"
               ],
               "_values_choice": "at-TPMSpecification",
               "_values": [
                 {
                   "_type": "TPMSpecification",
                   "family": "2.0",
                   "level": 0,
                   "revision": 138
                 }
               ]
             },
             {
               "_type": "AttributeSet",
               "type": {
                 "_type": "OBJECT IDENTIFIER",
                 "oid": "2.23.133.2.18",
                 "components": [
                   2,
                   23,
                   133,
                   2,
                   18
                 ],
                 "name": "tcg-at-tpmSecurityAssertions"
               },
               "values": [
                 "30380201000101FFA0030A0101A1030A0100A2030A0100A310300E1603332E310A01040A01020101FFA40F300D16053134302D320A0102010100"
               ],
               "_values_choice": "at-TPMSecurityAssertions",
               "_values": [
                 {
                   "_type": "TPMSecurityAssertions",
                   "version": 0,
                   "fieldUpgradable": true,
                   "ekGenerationType": "ekgt-injected",
                   "ekGenerationLocation": "tpmManufacturer",
                   "ekCertificateGenerationLocation": "tpmManufacturer",
                   "ccInfo": {
                     "_type": "CommonCriteriaMeasures",
                     "version": "3.1",
                     "assurancelevel": "ealevel4",
                     "evaluationStatus": "evaluationCompleted",
                     "plus": true,
                     "strengthOfFunction": null,
                     "profileOid": null,
                     "profileUri": null,
                     "targetOid": null,
                     "targetUri": null
                   },
                   "fipsLevel": {
                     "_type": "FIPSLevel",
                     "version": "140-2",
                     "level": "sllevel2",
                     "plus": false
                   },
                   "iso9000Certified": false,
                   "iso9000Uri": null
                 }
               ]
             }
           ]
         },
         {
           "_type": "Extension",
           "extnID": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "2.5.29.15",
             "components": [
               2,
               5,
               29,
               15
             ],
             "name": "id-x509-ce-keyUsage"
           },
           "critical": true,
           "extnValue": "03020520",
           "_extnValue_choice": "ext-KeyUsage",
           "_extnValue": [
             "keyEncipherment"
           ]
         },
         {
           "_type": "Extension",
           "extnID": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "2.5.29.19",
             "components": [
               2,
               5,
               29,
               19
             ],
             "name": "id-x509-ce-basicConstraints"
           },
           "critical": true,
           "extnValue": "3000",
           "_extnValue_choice": "ext-BasicConstraints",
           "_extnValue": {
             "_type": "BasicConstraints",
             "cA": false,
             "pathLenConstraint": null
           }
         },
         {
           "_type": "Extension",
           "extnID": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "2.5.29.37",
             "components": [
               2,
               5,
               29,
               37
             ],
             "name": "id-x509-ce-extKeyUsage"
           },
           "critical": false,
           "extnValue": "300706056781050801",
           "_extnValue_choice": "ext-ExtKeyUsage",
           "_extnValue": [
             {
               "_type": "OBJECT IDENTIFIER",
               "oid": "2.23.133.8.1",
               "components": [
                 2,
                 23,
                 133,
                 8,
                 1
               ],
               "name": "tcg-kp-EKCertificate"
             }
           ]
         },
         {
           "_type": "Extension",
           "extnID": {
             "_type": "OBJECT IDENTIFIER",
             "oid": "1.3.6.1.5.5.7.1.1",
             "components": [
               1,
               3,
               6,
               1,
               5,
               5,
               7,
               1,
               1
             ],
             "name": "id-pkix-pe-authorityInfoAccess"
           },
           "critical": false,
           "extnValue": "303C303A06082B06010505073002862E687474703A2F2F7365637572652E676C6F62616C7369676E2E636F6D2F73746D74706D656B696E7430352E637274",
           "_extnValue_choice": "ext-AuthorityInfoAccess",
           "_extnValue": [
             {
               "_type": "AccessDescription",
               "accessMethod": {
                 "_type": "OBJECT IDENTIFIER",
                 "oid": "1.3.6.1.5.5.7.48.2",
                 "components": [
                   1,
                   3,
                   6,
                   1,
                   5,
                   5,
                   7,
                   48,
                   2
                 ],
                 "name": "id-pkix-ad-caIssuers"
               },
               "accessLocation": {
                 "_choice": "uniformResourceIdentifier",
                 "value": "http://secure.globalsign.com/stmtpmekint05.crt"
               }
             }
           ]
         }
       ]
     },
     "signatureAlgorithm": {
       "_type": "AlgorithmIdentifier",
       "algorithm": {
         "_type": "OBJECT IDENTIFIER",
         "oid": "1.2.840.113549.1.1.11",
         "components": [
           1,
           2,
           840,
           113549,
           1,
           1,
           11
         ],
         "name": "id-pkcs1-sha256WithRSAEncryption"
       },
       "parameters": "0500"
     },
     "signatureValue": "2048:3D4C381E5B4F1BCBE09C63D52F1F04570CAEA142FD9CD942043B11F8E3BDCF50007AE16CF8869013041E92CDD3280BA4B51FBBD40582ED750219E261A695095674855AACEB520ADAFF9E7E908480A39CDCF900462D9171960FFE55D3AC49E8C981341BBD2EFBCC252A4C18A4F3B7C84CCE42CE70A208C84D2630A7ABFBE72D6271E75B9FF1C971D20EB3DBD763F1E04D834EAA692D2E4001BBF4730A3E3FDA9711AE386524D91C63BE0E516D00D5C6141FCCF6C539F3518E180049865BE16B69CAE1F8CB7FDC474B38F7EE56CBE7D8A89D9BA99B65D5265AEF32AA62426B10E6D75BB8677EC44F755BBC2806FD2B4E04BDF5D44259DBEAA42B6F563DF7AA7506"
   }
   ```

   (Notice that OID names look a bit weird.  For reasons that may have been
   lost to time and may no longer be relevant, these OIDs are defined with
   slightly different names in the ASN.1 modules in Heimdal's source tree.
   We'll fix this eventually.)

...

## Limitations

 - `libasn1`'s and, therefore, `asn1_print`'s JSON support is not X.697 (JER)
   compatible.

 - Control over C types generated is very limited, mainly only for integer
   types.

 - When using the template backend, `SET { .. }` types are currently not sorted
   by tag as they should be, but if the module author sorts them by hand then
   DER will be produced.

 - `REAL` is not supported.

 - `EmbeddedPDV` is not supported.

 - `BMPString` is not supported.

 - IA5String is not properly supported -- it's essentially treated as a
   `UTF8String` with a different tag.  This is true of all the string types.

 - Only types can be imported at this time.  Without some rototilling we likely
   will not be able to import anything other than types, values, and object
   sets.

 - Only simple value syntax is supported.  Constructed value syntax (i.e.,
   values of `SET`, `SEQUENCE`, `SET OF`, and `SEQUENCE OF`), is not supported.
   Values of `CHOICE` types are also not supported.

 - There is no way to substitute object sets at run-time.  This means that
   automatic decoding through open types will spend more CPU cycles than the
   application might want, by decoding more types than the application might
   care about.  The ability to substitute object sets at run-time would require
   a change to the APIs generated.

 - ...

## Compiler Usage

The various options for the Heimdal ASN.1 compiler are described in its manual
page, which is included below.

The `--option-file=FILE` option is particularly useful, as it allows additional
compiler options to be read from a file.

The `--preserve-binary=TYPE-NAME` option is critical for signature validation
as it causes the decoder to save the encoding of the given type so that
signature validation code can easily find the original encoding and thus avoid
having to re-encode or resort to other hacks.  E.g., we use this for preserving
the original encoding of the `tbsCertificate` field of `Certificate`.

The `--sequence=TYPE-NAME` causes the compiler to generate additional utility
functions for adding or removing items from the named type when it is a
`SEQUENCE OF` or `SET OF` type.

See the manual page `asn1_compile.1`:

```text
ASN1_COMPILE(1)		  BSD General Commands Manual	       ASN1_COMPILE(1)

NAME
     asn1_compile — compile ASN.1 modules

SYNOPSIS
     asn1_compile [--template] [--prefix-enum] [--enum-prefix=PREFIX]
		  [--encode-rfc1510-bit-string] [--decode-dce-ber]
		  [--support-ber] [--preserve-binary=TYPE] [--sequence=TYPE]
		  [--decorate=DECORATION] [--one-code-file] [--gen-name=NAME]
		  [--option-file=FILE] [--original-order] [--no-parse-units]
		  [--type-file=C-HEADER-FILE] [--version] [--help]
		  [FILE.asn1 [NAME]]

DESCRIPTION
     asn1_compile compiles an ASN.1 module into C source code and header
     files.

     A fairly large subset of ASN.1 as specified in X.680, and the ASN.1 In‐
     formation Object System as specified in X.681, X.682, and X.683 is sup‐
     ported, with support for the Distinguished Encoding Rules (DER), partial
     Basic Encoding Rules (BER) support, and experimental JSON support (encod‐
     ing only at this time).

     See the compiler's README files for details about the C code and inter‐
     faces it generates.

     The Information Object System support includes automatic codec support
     for encoding and decoding through “open types” which are also known as
     “typed holes”.  See RFC 5912 for examples of how to use the ASN.1 Infor‐
     mation Object System via X.681/X.682/X.683 annotations.  See the com‐
     piler's README files for more information on ASN.1 Information Object
     System support.

     Extensions specific to Heimdal are generally not syntactic in nature but
     rather command-line options to this program.  For example, one can use
     command-line options to:
	   •	   enable decoding of BER-encoded values;
	   •	   enable RFC1510-style handling of ‘BIT STRING’ types;
	   •	   enable saving of as-received encodings of specific types
		   for the purpose of signature validation;
	   •	   generate add/remove utility functions for array types;
	   •	   decorate generated ‘struct’ types with fields that are nei‐
		   ther encoded nor decoded;
     etc.

     ASN.1 x.680 features supported:
	   •	   most primitive types (except BMPString and REAL);
	   •	   all constructed types, including SET and SET OF;
	   •	   explicit and implicit tagging.

     Size and range constraints on the ‘INTEGER’ type cause the compiler to
     generate appropriate C types such as ‘int’, ‘unsigned int’, ‘int64_t’,
     ‘uint64_t’.  Unconstrained ‘INTEGER’ is treated as ‘heim_integer’, which
     represents an integer of arbitrary size.

     Caveats and ASN.1 x.680 features not supported:
	   •	   JSON encoding support is not quite X.697 (JER) compatible.
		   Its JSON schema is subject to change without notice.
	   •	   Control over C types generated is very limited, mainly only
		   for integer types.
	   •	   When using the template backend, `SET { .. }` types are
		   currently not sorted by tag as they should be, but if the
		   module author sorts them by hand then correct DER will be
		   produced.
	   •	   ‘AUTOMATIC TAGS’ is not supported.
	   •	   The REAL type is not supported.
	   •	   The EmbeddedPDV type is not supported.
	   •	   The BMPString type is not supported.
	   •	   The IA5String is not properly supported, as it's essen‐
		   tially treated as a UTF8String with a different tag.
	   •	   All supported non-octet strings are treated as like the
		   UTF8String type.
	   •	   Only types can be imported into ASN.1 modules at this time.
	   •	   Only simple value syntax is supported.  Constructed value
		   syntax (i.e., values of SET, SEQUENCE, SET OF, and SEQUENCE
		   OF types), is not supported.	 Values of `CHOICE` types are
		   also not supported.

     Options supported:

     --template
	     Use the “template” backend instead of the “codegen” backend
	     (which is the default backend).

	     The template backend generates “templates” which are akin to
	     bytecode, and which are interpreted at run-time.

	     The codegen backend generates C code for all functions directly,
	     with no template interpretation.

	     The template backend scales better than the codegen backend be‐
	     cause as we add support for more encoding rules and more opera‐
	     tions (we may add value comparators) the templates stay mostly
	     the same, thus scaling linearly with size of module.  Whereas the
	     codegen backend scales linear with the product of module size and
	     number of encoding rules supported.

     --prefix-enum
	     This option should be removed because ENUMERATED types should al‐
	     ways have their labels prefixed.

     --enum-prefix=PREFIX
	     This option should be removed because ENUMERATED types should al‐
	     ways have their labels prefixed.

     --encode-rfc1510-bit-string
	     Use RFC1510, non-standard handling of “BIT STRING” types.

     --decode-dce-ber

     --support-ber

     --preserve-binary=TYPE
	     Generate a field named ‘_save’ in the C struct generated for the
	     named TYPE.  This field is used to preserve the original encoding
	     of the value of the TYPE.

	     This is useful for cryptographic applications so that they can
	     check signatures of encoded values as-received without having to
	     re-encode those values.

	     For example, the TBSCertificate type should have values preserved
	     so that Certificate validation can check the signatureValue over
	     the tbsCertificate's value as-received.

	     The alternative of encoding a value to check a signature of it is
	     brittle.  For types where non-canonical encodings (such as BER)
	     are allowed, this alternative is bound to fail.  Thus the point
	     of this option.

     --sequence=TYPE
	     Generate add/remove functions for the named ASN.1 TYPE which must
	     be a ‘SET OF’ or ‘SEQUENCE OF’ type.

     --decorate=ASN1-TYPE:FIELD-ASN1-TYPE:fname[?]
	     Add to the C struct generated for the given ASN.1 SET, SEQUENCE,
	     or CHOICE type named ASN1-TYPE a “hidden” field named fname of
	     the given ASN.1 type FIELD-ASN1-TYPE, but do not encode or decode
	     it.  If the fname ends in a question mark, then treat the field
	     as OPTIONAL.

	     This is useful for adding fields to existing types that can be
	     used for internal bookkeeping but which do not affect interoper‐
	     ability because they are neither encoded nor decoded.  For exam‐
	     ple, one might decorate a request type with state needed during
	     processing of the request.

     --decorate=ASN1-TYPE:void*:fname
	     Add to the C struct generated for the given ASN.1 SET, SEQUENCE,
	     or CHOICE type named ASN1-TYPE a “hidden” field named fname of
	     type ‘void *’ (but do not encode or decode it.

	     The destructor and copy constructor functions generated by this
	     compiler for ASN1-TYPE will set this field to the ‘NULL’ pointer.

     --decorate=ASN1-TYPE:FIELD-C-TYPE:fname[?]:[copyfn]:[freefn]:header
	     Add to the C struct generated for the given ASN.1 SET, SEQUENCE,
	     or CHOICE type named ASN1-TYPE a “hidden” field named fname of
	     the given external C type FIELD-C-TYPE, declared in the given
	     header but do not encode or decode this field.  If the fname ends
	     in a question mark, then treat the field as OPTIONAL.

	     The header must include double quotes or angle brackets.  The
	     copyfn must be the name of a copy constructor function that takes
	     a pointer to a source value of the type, and a pointer to a des‐
	     tination value of the type, in that order, and which returns zero
	     on success or else a system error code on failure.	 The freefn
	     must be the name of a destructor function that takes a pointer to
	     a value of the type and which releases resources referenced by
	     that value, but does not free the value itself (the run-time al‐
	     locates this value as needed from the C heap).  The freefn should
	     also reset the value to a pristine state (such as all zeros).

	     If the copyfn and freefn are empty strings, then the decoration
	     field will neither be copied nor freed by the functions generated
	     for the TYPE.

     --one-code-file
	     Generate a single source code file.  Otherwise a separate code
	     file will be generated for every type.

     --gen-name=NAME
	     Use NAME to form the names of the files generated.

     --option-file=FILE
	     Take additional command-line options from FILE.

     --original-order
	     Attempt to preserve the original order of type definition in the
	     ASN.1 module.  By default the compiler generates types in a topo‐
	     logical sort order.

     --no-parse-units
	     Do not generate to-int / from-int functions for enumeration
	     types.

     --type-file=C-HEADER-FILE
	     Generate an include of the named header file that might be needed
	     for common type defintions.

     --version

     --help

NOTES
     Currently only the template backend supports automatic encoding and de‐
     coding of open types via the ASN.1 Information Object System and
     X.681/X.682/X.683 annotations.

HEIMDAL			       February 22, 2021		       HEIMDAL
```

## APIs Generated by the Compiler

Every named type in an ASN.1 module gets a corresponding type in C.
Em-dashes in symbols become underscores.

Every named type in an ASN.1 module also gets several functions generated
associated with it:

 - `int decode_TypeName(const unsigned char *, size_t, TypeName *, size_t *);`

   Decodes a value of `TypeName` in the given byte array of the given size,
   into the given `TypeName` object, and outputs the number of bytes parsed.

   Returns 0 on success, or an error that can be formatted as a string using
   the `com_err` library.

 - `int encode_TypeName(unsigned char *, size_t, const TypeName *, size_t *);`

   Encodes the given object of `TypeName` type into the given byte array of the
   given size, outputting the number of bytes used.

   NOTE WELL: the `unsigned char *` pointer must point to the _last_ byte of
   the buffer!

   Returns 0 on success, or an error that can be formatted as a string using
   the `com_err` library, including system errors such as `ENOMEM`.

 - `int length_TypeName(const TypeName *);`

   Returns the number of bytes needed to encode the given object.

 - `void free_TypeName(TypeName *);`

   Releases the memory associated with the content of the given object, but
   note that the object itself is _not_ released.

 - `int copy_TypeName(const TypeName *, TypeName *);`

   Copies the content of the given `const` object to the destination,
   non-`const` object.

   Returns 0 on success, or an error that can be formatted as a string using
   the `com_err` library, including system errors such as `ENOMEM`.

 - `char *print_TypeName(const TypeName *, int);`

   Returns a string (JSON) representation of the given object.  The `int`
   argument is a bitset of flags:

    - `ASN1_PRINT_INDENT`

      Indent the JSON.  If not given the the JSON will have no interstitial
      whitespace, including newlines.

You will want to review the data structures generated.  They look like:

```C
    typedef struct TBSCertificate TBSCertificate;
    typedef struct AlgorithmIdentifier AlgorithmIdentifier;
    typedef struct ... ...;

    /*
    Certificate ::= SEQUENCE {
      tbsCertificate       TBSCertificate,
      signatureAlgorithm   AlgorithmIdentifier,
      signatureValue         BIT STRING {
      },
    }
    */

    typedef struct Certificate {
      TBSCertificate tbsCertificate;
      AlgorithmIdentifier signatureAlgorithm;
      heim_bit_string signatureValue;
    } Certificate;

    /*
    TBSCertificate ::= SEQUENCE {
      version                [0] Version OPTIONAL,
      serialNumber           CertificateSerialNumber,
      signature              AlgorithmIdentifier,
      issuer                 Name,
      validity               Validity,
      subject                Name,
      subjectPublicKeyInfo   SubjectPublicKeyInfo,
      issuerUniqueID         [1] IMPLICIT   BIT STRING {
      } OPTIONAL,
      subjectUniqueID        [2] IMPLICIT   BIT STRING {
      } OPTIONAL,
      extensions             [3] Extensions OPTIONAL,
    }
    */

    typedef struct TBSCertificate {
      heim_octet_string _save;
      Version *version;
      CertificateSerialNumber serialNumber;
      AlgorithmIdentifier signature;
      Name issuer;
      Validity validity;
      Name subject;
      SubjectPublicKeyInfo subjectPublicKeyInfo;
      heim_bit_string *issuerUniqueID;
      heim_bit_string *subjectUniqueID;
      Extensions *extensions;
    } TBSCertificate;
```

Note how trivial the mapping onto C is.

`OPTIONAL` fields become pointer fields, with `NULL` indicating
absence and non-NULL indicating presence.

And so on.

## `asn1_print` Usage

```text
ASN1_PRINT(1)		  BSD General Commands Manual		 ASN1_PRINT(1)

NAME
     asn1_print — dump ASN.1 DER encoded values

SYNOPSIS
     asn1_print [-i | --no-indent] [-I | --inner] [-l | --list-types]
		[-A | --try-all-types] [-S | --raw-sequence] [-n | --no-print]
		[-q | --quiet] [--test-encode] [--test-copy]
		[-l -v | --version] [-l -h | --help] [FILE [TypeName...]]

DESCRIPTION
     asn1_print Dumps ASN.1 DER-encoded values.  If one or more TypeName argu-
     ments are given, then asn1_print will print the value in a JSON-like for-
     mat using its knowledge of the ASN.1 modules defining those types, stop-
     ping at the first type for which it can successfully decode the value.
     If TypeNames are given, they must be the names of ASN.1 types exported by
     an ASN.1 modules that are compiled into asn1_print.  Use the
     --try-all-types option to attempt decoding as all ASN.1 types known to
     asn1_print.  If neither any TypeName nor --try-all-types are given, then
     the value will be parsed and displayed using just the self-describing
     nature of DER.

     Options supported:

     -i, --no-indent
	     Do not indent dump.

     -I, --inner
	     Try to parse inner structures of OCTET STRING and constructed
	     values.

     -l, --list-types
	     List all types known to asn1_print.

     -A, --try-all-types
	     Attempt to decode the value as any of all types known to
	     asn1_print.

     -S, --raw-sequence
	     If a value parses as a given TypeName but any bytes are left
	     over, try to parse those separately as well until all bytes are
	     consumed or an error occurs.

     -n, --no-print
	     For the case where -A or --try-all-types or where a TypeName is
	     given, do not output a JSON representation of the value, just
	     attempt to decode it.  This is useful for fuzzing.

     -q, --quiet
	     Similar to -n, --no-print but JSON output will be formatted, just
	     not output.  As with -n, --no-print, this option requires -A -/
	     --try-all-types or that a TypeName be given.  This is useful for
	     fuzzing.

     --test-encode
	     Check that encoding produces the same value as decoding.  Useful
	     for fuzzing.

     --test-copy
	     Test copy functions.  Useful for fuzzing.

     -v, --version

     -h, --help

HEIMDAL 		       February 22, 2021		       HEIMDAL
```

## Implementation

See:

 - `lib/asn1/main.c` for the `main()` function of the compiler
 - `lib/asn1/asn1parse.y` for the grammar and most of the parsing into an AST
 - `lib/asn1/symbol.h` for the types making up the AST
 - `lib/asn1/{hash,symbol}.c` for compiler AST supporting functionality
 - `lib/asn1/gen.c` for the C header file generator
 - `lib/asn1/gen_template.c` for the template generator
 - `lib/asn1/gen_{decode,encode,length,copy,free}.c` for the C code generator
 - `lib/asn1/gen_{glue,seq}.c` for misc code generator
 - `lib/asn1/template.c` for the template interpreter
 - `lib/asn1/der*.c` for primitive type primitives
 - `lib/asn1/extra.c` for primitives related to `ANY`

...

## Futures

 - Add JER support so we can convert between JER and DER?

 - Add XDR support?  There are no ASN.1 Encoding Rules based on XDR, but it is
   trivial to construct such for at least that subset of ASN.1 for which the
   XDR syntax has equivalent semantics.

 - Add OER support?

 - Add NDR support?  There are no ASN.1 Encoding Rules based on NDR, but it is
   trivial to construct such for at least that subset of ASN.1 for which the
   IDL syntax has equivalent semantics.

 - Perhaps third parties will contribute more control over generated types?
   This may require separate publication of the Heimdal ASN.1 compiler from the
   rest of Heimdal.

## Moving From C

 - Generate and output a JSON representation of the compiled ASN.1 module.

 - Code codegen/templategen backends in jq or Haskell or whatever.

 - Code template interpreters in some host language.

 - Eventually rewrite the compiler itself in Rust or whatever.