FW: [jcifs] ASN.1

[Richard Caper]

It's basically a time-space tradeoff.  By using:

    public byte[] encode(); // returns encoded object

a large constructed object would look something like:

    public byte[] encode() {
        byte[] child1Data = child1.encode();
        byte[] child2Data = child2.encode();
        int length = child1Data.length + child2Data.length;
        byte[] myData = new byte[length + headerInfoLength];
        // stick my tag + length into front of myData, then
        // System.arraycopy children in
        return myData;
    }

This is fairly simple, but requires a bit more memory overhead (plus
lots of array allocation and copying).  Also, once the toplevel byte[]
is built it itself needs to be copied to buffer (or written to
stream).

Mike's approach, if I understand correctly, would basically be:

    public int size(); // returns required size
    public void encode(byte[] dest, int offset, int length);

which would look like:

    public int size() {
        int child1Size = child1.size();
        int child2Size = child2.size();
        return headerSize + child1Size + child2Size;
        // also cache my size for future calls
    }

    public void encode(byte[] dest, int offset, int length) {
        int idx = offset;
        // write tag to dest
        // write size() to dest
        idx += headerSize;
        child1.encode(dest, idx, child1.size());
        idx += child1.size();
        child2.encode(dest, idx, child2.size());
    }

So while you have to run 2 passes, you can encode directly to the
toplevel buffer.  Since the size is cached for each object in the
first pass, it doesn't have to be calculated again.

Not sure which would end up being a faster/better approach.


On 4/22/05, Tapperson Kevin <Kevin.Tapperson at hcahealthcare.com> wrote:
> Mike,
> 
> May I suggest separating the encoding into two phases.  The first phase is
> the actual encoding work; converting the objects into byte[]'s.  The second
> phase is the construction of the ASN.1 data buffer.  Don't touch your
> ASN1Buffer "dst" in the first phase.  Here's a pseudo code example (this may
> not be entirely correct; it's pretty early), but the concept still works.  I
> used this methodology when I wrote an LDAP proxy a couple years ago.  I have
> attached some code from my LDAP proxy project as an example.  You can find
> the LDAP RFC with all of its ASN.1 definitions at
> http://www.faqs.org/rfcs/rfc2251.html.  If nothing else, the BERUtils class
> that I wrote may help.  Rename example.zip.txt to example.zip.
> 
>     void encode( ASN1Buffer dst ) {
>         //phase 1
>         byte[] nameBytes = new byte[0];
>         if (name != null) {
>             //the encode method would return a byte[] consisting of { 0xA0,
> length(name), name bytes... }
>             nameBytes = name.encode();
>         }
>         byte[] oldBytes = new byte[0];
>         if (old != null) {
>             oldBytes = old.encode();
>         }
> 
>         //phase 2
>         dst.enc_intn( 0x60, 1 );
>         dst.enc_length( nameBytes.length + oldBytes.length );
>         if (name != null) {
>             dst.write(nameBytes);
>         }
>         if (oid != null) {
>             dst.write(oldBytes);
>         }
>     }
> 
> -----Original Message-----
> From: jcifs-bounces+kevin.tapperson=hcahealthcare.com at lists.samba.org
> [mailto:jcifs-bounces+kevin.tapperson=hcahealthcare.com at lists.samba.org]
> On Behalf Of Michael B Allen
> Sent: Friday, April 22, 2005 2:25 AM
> To: jcifs at samba.org
> Subject: [jcifs] ASN.1
> 
> I'm sort of just emailing this to myself for later but if anyone out
> there's an ASN.1 expert let me share my pain... I need some limited ASN.1
> / DER code for SPNEGO. Decoding this stuff is pretty easy but I've been
> thinking all night about how to *encode* it.
> 
> The problem is (assuming a little knowledge of DER encoding here) that you
> can't encode an object until you know the size of it's payload and you
> don't know the size of the payload until you encode it. Well obviously
> that's not entirely true or it quite simply wouldn't be possible to do
> this at all.  Rather what you must do is first traverse the entire tree
> of objects from the leaves up just to add up the sizes. Then you can
> recur again to encode everything.
> 
> What an inelegant pain in the ass. It's ironic that the standard is
> so miserly about saving every little byte in encoding lengths because
> doing so incurs this inefficent encoding requirement. And what's even
> more inefficient are all the Java implementations out there that create
> an Object for every tag. Arg. OOP is just a tool, and it's not the right
> tool for decoding/encoding ASN.1!
> 
> Anyway, here's my pseudocode for how I think I'm going to handle this. I
> think I have it figure'd out but any input or anecdotes about ASN.1,
> SPNEGO, extended security, etc is welcome.
> 
> Mike
> 
> Record ::= SEQUENCE {
>    name [0] Name OPTIONAL,
>    oid  [1] OBJECT IDENTIFER
> }
> 
> The above shoddy ASN.1 might be encoded/decoded in DER w/ something like:
> 
> class Record extends ASN1Object {
> 
>     private int size = -1;
> 
>         /* The idea here is that Name and OID are also ASN1Objects
>          * that have similar encode and decode methods. So we
>          * demonstrate recursion with one node.
>      */
>     Name name;
>     OID oid;
> 
>     int size() {
>         if (size > 0) return size;
>         int n = 0;
>         if (name != null) {
>             int m = name.size();
>             n += 1 + lenlen( m ) + m;
>                                 /* lenlen computes the number of bytes
> required
>                                  * to encode the length of the object
>                                  */
>         }
>         if (oid != null)
>             n += oid.size();
>         return 1 + lenlen(n) + n;
>     }
> 
>     void encode( ASN1Buffer dst ) {
>         dst.enc_intn( 0x60, 1 );
>         dst.enc_length( size() );
>         if (name != null) {
>             int n = name.size();
>             dst.enc_intn( 0xA0, 1 );
>             dst.enc_length( n );
>             name.encode( dst );
>         }
>         if (oid != null) {
>             int n = oid.size();
>             dst.enc_intn( 0xA1, 1 );
>             dst.enc_length( n );
>             oid.encode( dst );
>         }
>     }
>     void decode( ASN1Buffer src ) {  /* decoding is easy */
>         src.dec_intn( 1 );
>         src.dec_length();
>         for ( ;; ) {
>             int tag = src.dec_intn( 1 ) & 0xF;
>             src.dec_length();
>             switch (tag) {
>                 case 0:
>                     name = new Name();
>                     name.decode( src );
>                     break;
>                 case 1:
>                     ...
>             }
>         }
>     }
> }
> 
> call() {
>     Record r = new Record();
>     r.name = new Name();
>     r.name....set name members
>     r.oid = SPNEGO.MECHANISM_KERBEROS;
>     r.encode( dst );
> 
>     OR to decode
> 
>     Record r = new Record();
>     r.decode( src );
> }
> 
> --
> IRC - where men are men, women are men, and the boys are FBI agents.
> 
> 
>