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

Constructors

Constructor and Description
SetSortEncodingCountTest()

Method Summary

Modifier and Type	Method and Description
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

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, countTestCases, createResult, fail, fail, failNotEquals, failNotSame, failSame, format, getName, run, run, runBare, runTest, setName, setUp, tearDown, toString

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