[rohc] Sorted?!

["West, Mark (ITN)" <[e-mail]>]

Hi all,

First of all, this is *not* about default algorithms.  Honest ;-)

However, from the recent discussion about 'deflate' there were questions 
regarding the use of dynamic Huffman trees rather than static ones.

If you look at how RFC 1951 defines the storage of the dynamic Huffman 
tree information (a compressed list of the code length for each value), 
this is at odds with the definition of the HUFFMAN instruction (which 
requires the code-lengths to be in increasing order).

To solve this, it is necessary to construct a mapping from one 
representation to the other.  This can be easily done by sorting the 
list.  Clearly a sort could be written in UDVM byte-code, although I 
suspect this to be a rather painful process, with a non-trivial overhead.

The alternative (and it has been suggested that this might make sense 
from the perspective of other compression algorithms) is to introduce a 
'SORT' instruction.

At its simplest, this would sort an 'r' row by 'c' column table of 
2-byte entries (where the start address, 'r' and 'c' are the parameters).

Of course, the biggest concern with such an instruction (I would think) 
is with the DoS security implication.
Following on from Carsten's security e-mail, if we set the 'cost' of 
SORT to be 'O(n.log(n))' we are constraining the implementation.
If we set it to 'O(n^2)' you would need to make many cycles available to 
be able to perform any kind of sort (which generally opens up a DoS 
vulnerability).
(Of course, these issues are essentially the same regardless of whether 
the sort is implemented as a single instruction or in byte-code)

So, if we feel that sorting is a useful operation (and I contend that it 
just might be, if you want to support to the full range of 'deflate' 
compressed formats), should we have a SORT instruction?

Cheers,

Mark.

-- 
Mark A. West, Consultant Engineer
Roke Manor Research Ltd., Romsey, Hants.  SO51 0ZN
Phone [phone]   Fax  [phone]

(Yes, I do know that my disclaimer is in an attachment.  And, no, I 
didn't ask for it to be that way)