org.bouncycastle.asn1.test
Class SetSortEncodingCountTest

java.lang.Object
  junit.framework.Assert
      junit.framework.TestCase
          org.bouncycastle.asn1.test.SetSortEncodingCountTest

All Implemented Interfaces:

junit.framework.Test

public class SetSortEncodingCountTest

extends junit.framework.TestCase

DER requires the elements of a SET to be sorted by their encodings, and ASN1Set sorts with an insertion sort. It used to re-derive an element's encoding every time the insertion loop shifted it, so ordering N elements cost O(N^2) encodings rather than O(N) encodings compared O(N^2) times. On input already in descending order every insertion shifts the whole placed prefix, so a SET arriving off the wire cost seconds to minutes of CPU to re-encode - and the sort is reached from toDERObject() / getEncoded(DER) and equals(), which for CMS runs over the signed attributes before the signature is checked.

The encodings are now derived once and carried alongside the elements. This is asserted by counting, not by timing: the elements below record how often they are asked for their encoding, so the bound is exact and does not depend on how loaded the machine is. Note the sort is still O(N^2) in comparisons - that is the insertion sort itself, unchanged here.

Constructor Summary

SetSortEncodingCountTest()

Method Summary

void	testSortEncodesEachElementOnce()
void	testSortOrderUnchanged() The compatibility assertion: memoising the encodings must not change the order they end up in.

Methods inherited from class junit.framework.TestCase

countTestCases, createResult, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

Methods inherited from class junit.framework.Assert

assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertEquals, assertFalse, assertFalse, assertNotNull, assertNotNull, assertNotSame, assertNotSame, assertNull, assertNull, assertSame, assertSame, assertTrue, assertTrue, fail, fail

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SetSortEncodingCountTest

public SetSortEncodingCountTest()

Method Detail

testSortEncodesEachElementOnce

public void testSortEncodesEachElementOnce()
                                    throws java.io.IOException

Throws:

java.io.IOException

testSortOrderUnchanged

public void testSortOrderUnchanged()
                            throws java.io.IOException

The compatibility assertion: memoising the encodings must not change the order they end up in. Sorting descending input has to give exactly the ascending encodings.

Throws:

java.io.IOException