[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: propagation control

Actually, when we were designing the PGP 3.0 data formats, we came up
with an encoding that is linear on both encode and decode, modulo some
fixed-size buffer (default is 4KByte blocks).  The encoding adds an
overhead of approximately 1 byte/block.  The encoder needs to be able
to buffer up to the block size; the decoder doesn't need to buffer at
all.

More details available upon request.

-derek

dpkemp@missi.ncsc.mil (David P. Kemp) writes:

> 
> > From: "Phillip M. Hallam-Baker" <hallam@ai.mit.edu>
> > 
> > This is of course very ASN.1, I don't mind ASN.1 except for the DER
> > rules which are completely braindamaged. If it had been made an
> > absolute requirement that every structure should be capable of
> > being encoded and decoded using a simple linear descent the problem
> > would not occur.
> 
> 
> I noticed you were very careful to specify DER, as opposed to BER.
> The Basic Encoding Rules (BER), of course, allow you to specify length of
> an object explicitly at the beginning, or implicitly by sending an
> end token when the object is finished.
> 
> There are two canonical encoding subsets of BER: the Canonical Encoding
> Rules (CER) and Distinguished Encoding Rules (DER).  CER has the properties
> you want - the length of an object does not need to be known before
> spitting out the encoded data.
> 
> Whether you prefer DER or CER is largely a matter of whether you do
> encoding or decoding more frequently.  In the case of certificates which
> are typically created once on a potentially "large" machine but verified
> many times on "resource-challenged" platforms, a coding format which
> specifies the length of the item at the beginning (allowing memory to
> be allocated before decoding the item) is preferable.  DER is such a
> format.
> 
> In summary, CER is linear-encode and recursive decode, whereas DER is
> recursive-encode and linear-decode.  BER allows it to be done either way.
> 
> These properties are not specific to ASN.1 and BER; they are applicable
> to any transfer format - either the length must be known or filled in at
> the beginning, or it isn't known until the end.  I don't know how you
> could have a format that allows both encoding and decoding of arbitrary-
> length nested objects to be done linearly.
> 
> I also think that in the case of certificates, it hardly matters.  Doing
> random access or recursive descent over an object that is 1/2 KB or 2KB
> or 5KB long is no problem.  It's only when you start dealing with objects
> that don't fit into RAM (such as streaming media) that the difference
> becomes important.

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/      PP-ASEL      N1NWH
       warlord@MIT.EDU                        PGP key available