CR-6059 OPENDJ-1712 Change integer matching rule normalized representation ...

Matthew Swift

13.36.2015 9f6a6a85a8a3b37fab4c1af44c94a6d151619608

CR-6059 OPENDJ-1712 Change integer matching rule normalized representation to work with default comparator

 opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/IntegerEqualityMatchingRuleImpl.java

@@ -22,13 +22,11 @@
 *
 *
 *      Copyright 2009 Sun Microsystems, Inc.
 *      Portions copyright 2013-2014 ForgeRock AS
 *      Portions copyright 2013-2015 ForgeRock AS
 */
package org.forgerock.opendj.ldap.schema;

import static org.forgerock.opendj.ldap.schema.IntegerOrderingMatchingRuleImpl.*;

import java.util.Comparator;
import static org.forgerock.opendj.ldap.schema.IntegerOrderingMatchingRuleImpl.normalizeValueAndEncode;

import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteString;
@@ -41,12 +39,6 @@
 * potentially share the same index.
 */
final class IntegerEqualityMatchingRuleImpl extends AbstractEqualityMatchingRuleImpl {

    @Override
    public Comparator<ByteSequence> comparator(final Schema schema) {
        return COMPARATOR;
    }

    @Override
    public ByteString normalizeAttributeValue(final Schema schema, final ByteSequence value)
            throws DecodeException {

 opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/IntegerOrderingMatchingRuleImpl.java

@@ -22,121 +22,118 @@
 *
 *
 *      Copyright 2009 Sun Microsystems, Inc.
 *      Portions copyright 2014 ForgeRock AS.
 *      Portions copyright 2014-2015 ForgeRock AS.
 */
package org.forgerock.opendj.ldap.schema;

import static com.forgerock.opendj.ldap.CoreMessages.WARN_ATTR_SYNTAX_ILLEGAL_INTEGER;

import java.math.BigInteger;
import java.util.Comparator;

import org.forgerock.opendj.ldap.Assertion;
import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ConditionResult;
import org.forgerock.opendj.ldap.ByteStringBuilder;
import org.forgerock.opendj.ldap.DecodeException;
import org.forgerock.opendj.ldap.spi.IndexQueryFactory;

/**
 * This class defines the integerOrderingMatch matching rule defined in X.520
 * and referenced in RFC 4519. The implementation of this matching rule is
 * intentionally aligned with the ordering matching rule so that they could
 * intentionally aligned with the equality matching rule so that they could
 * potentially share the same index.
 */
final class IntegerOrderingMatchingRuleImpl extends AbstractOrderingMatchingRuleImpl {
    static final Comparator<ByteSequence> COMPARATOR = new Comparator<ByteSequence>() {
        @Override
        public int compare(final ByteSequence o1, final ByteSequence o2) {
            final BigInteger i1 = decodeNormalizedValue(o1);
            final BigInteger i2 = decodeNormalizedValue(o2);
            return i1.compareTo(i2);
        }
    };
    /** Sign mask to be used when encoding zero or positive integers. */
    static final byte SIGN_MASK_POSITIVE = (byte) 0x00;

    /** Sign mask to be used when encoding negative integers. */
    static final byte SIGN_MASK_NEGATIVE = (byte) 0xff;

    /**
     * Encodes an integer using a format which is suitable for comparisons using
     * {@link ByteSequence#compareTo(ByteSequence)}. The integer is encoded as
     * follows:
     * <ul>
     * <li>bit 0: sign bit, 0 = negative, 1 = positive
     * <li>bits 1-3: length of the encoded length in bytes (0 when length is <
     *     2^4, 4 when length is < 2^32)
     * <li>bits 4-7: encoded length when length is < 2^4
     * <li>bits 4-15: encoded length when length is < 2^12
     * <li>bits 4-23: encoded length when length is < 2^20
     * <li>bits 4-31: encoded length when length is < 2^28
     * <li>bits 4-35: encoded length when length is < 2^31 (bits 35-39 are
     *     always zero, because an int is 32 bits)
     * <li>remaining: byte encoding of the absolute value of the integer.
     * </ul>
     * When the value is negative all bits from bit 1 onwards are inverted.
     */
    static ByteString normalizeValueAndEncode(final ByteSequence value) throws DecodeException {
        return encodeNormalizedValue(normalizeValue(value));
    }

    private static BigInteger normalizeValue(final ByteSequence value) throws DecodeException {
        final BigInteger bi;
        try {
            return new BigInteger(value.toString());
            bi = new BigInteger(value.toString());
        } catch (final Exception e) {
            throw DecodeException.error(WARN_ATTR_SYNTAX_ILLEGAL_INTEGER.get(value));
        }

        /*
         * BigInteger.toByteArray() always includes a sign bit, which means that
         * we gain an extra zero byte for numbers that require a multiple of 8
         * bits, e.g. 128-255, 32768-65535, because the sign bit overflows into
         * an additional byte. We'll strip it out in that case because we encode
         * the sign bit in the header.
         */
        final byte[] absBytes = bi.abs().toByteArray();
        final int length = absBytes.length;
        final boolean removeLeadingByte = length > 1 && absBytes[0] == 0;
        final int trimmedLength = removeLeadingByte ? length - 1 : length;
        final int startIndex = removeLeadingByte ? 1 : 0;
        final byte signMask = bi.signum() < 0 ? SIGN_MASK_NEGATIVE : SIGN_MASK_POSITIVE;

        // Encode the sign, length of the length, and the length.
        final ByteStringBuilder builder = new ByteStringBuilder(trimmedLength + 5);
        encodeHeader(builder, trimmedLength, signMask);

        // Encode the absolute value of the integer..
        for (int i = startIndex; i < length; i++) {
            builder.append((byte) (absBytes[i] ^ signMask));
        }

        return builder.toByteString();
    }

    private static BigInteger decodeNormalizedValue(final ByteSequence normalizedValue) {
        return new BigInteger(normalizedValue.toByteArray());
    }

    private static ByteString encodeNormalizedValue(final BigInteger normalizedValue) {
        return ByteString.wrap(normalizedValue.toByteArray());
    }

    @Override
    public Comparator<ByteSequence> comparator(final Schema schema) {
        return COMPARATOR;
    }

    @Override
    public Assertion getAssertion(final Schema schema, final ByteSequence value)
            throws DecodeException {
        final BigInteger normAssertion = normalizeValue(value);
        return new Assertion() {
            @Override
            public <T> T createIndexQuery(final IndexQueryFactory<T> factory)
                    throws DecodeException {
                return factory.createRangeMatchQuery(getIndexId(), ByteString.empty(),
                        encodeNormalizedValue(normAssertion), false, false);
            }

            @Override
            public ConditionResult matches(final ByteSequence normValue) {
                return ConditionResult.valueOf(decodeNormalizedValue(normValue).compareTo(
                        normAssertion) < 0);
            }
        };
    }

    @Override
    public Assertion getGreaterOrEqualAssertion(final Schema schema, final ByteSequence value)
            throws DecodeException {
        final BigInteger normAssertion = normalizeValue(value);
        return new Assertion() {
            @Override
            public <T> T createIndexQuery(final IndexQueryFactory<T> factory)
                    throws DecodeException {
                return factory.createRangeMatchQuery(getIndexId(), encodeNormalizedValue(normAssertion), ByteString
                        .empty(), true, false);
            }

            @Override
            public ConditionResult matches(final ByteSequence normValue) {
                return ConditionResult.valueOf(decodeNormalizedValue(normValue).compareTo(
                        normAssertion) >= 0);
            }
        };
    }

    @Override
    public Assertion getLessOrEqualAssertion(final Schema schema, final ByteSequence value)
            throws DecodeException {
        final BigInteger normAssertion = normalizeValue(value);
        return new Assertion() {
            @Override
            public <T> T createIndexQuery(final IndexQueryFactory<T> factory)
                    throws DecodeException {
                return factory.createRangeMatchQuery(getIndexId(), ByteString.empty(),
                        encodeNormalizedValue(normAssertion), false, true);
            }

            @Override
            public ConditionResult matches(final ByteSequence normValue) {
                return ConditionResult.valueOf(decodeNormalizedValue(normValue).compareTo(
                        normAssertion) <= 0);
            }
        };
    // Package private for unit testing.
    static void encodeHeader(final ByteStringBuilder builder, final int length,
            final byte signMask) {
        if ((length & 0x0000000F) == length) {
            // 0000xxxx
            final byte b0 = (byte) (0x80 | length & 0x0F);
            builder.append((byte) (b0 ^ signMask));
        } else if ((length & 0x00000FFF) == length) {
            // 0001xxxx xxxxxxxx
            final byte b0 = (byte) (0x90 | length >> 8 & 0x0F);
            builder.append((byte) (b0 ^ signMask));
            builder.append((byte) (length & 0xFF ^ signMask));
        } else if ((length & 0x000FFFFF) == length) {
            // 0010xxxx xxxxxxxx xxxxxxxx
            final byte b0 = (byte) (0xA0 | length >> 16 & 0x0F);
            builder.append((byte) (b0 ^ signMask));
            builder.append((byte) (length >> 8 & 0xFF ^ signMask));
            builder.append((byte) (length & 0xFF ^ signMask));
        } else if ((length & 0x0FFFFFFF) == length) {
            // 0011xxxx xxxxxxxx xxxxxxxx xxxxxxxx
            final byte b0 = (byte) (0xB0 | length >> 24 & 0x0F);
            builder.append((byte) (b0 ^ signMask));
            builder.append((byte) (length >> 16 & 0xFF ^ signMask));
            builder.append((byte) (length >> 8 & 0xFF ^ signMask));
            builder.append((byte) (length & 0xFF ^ signMask));
        } else {
            // 0100xxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx0000
            final byte b0 = (byte) (0xC0 | length >> 28 & 0x0F);
            builder.append((byte) (b0 ^ signMask));
            builder.append((byte) (length >> 20 & 0xFF ^ signMask));
            builder.append((byte) (length >> 12 & 0xFF ^ signMask));
            builder.append((byte) (length >> 4 & 0xFF ^ signMask));
            builder.append((byte) (length << 4 & 0xFF ^ signMask));
        }
    }

    @Override

 opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java

@@ -22,7 +22,7 @@
 *
 *
 *      Copyright 2010 Sun Microsystems, Inc.
 *      Portions copyright 2011-2014 ForgeRock AS.
 *      Portions copyright 2011-2015 ForgeRock AS.
 */
package org.forgerock.opendj.ldap;

@@ -1122,7 +1122,7 @@
            { "dc=example\\+other,dc=com", "dc=com,dc=example%2Bother" },
            { "dc=example\\2Bother,dc=com", "dc=com,dc=example%2Bother" },
            // integer
            { "governingStructureRule=256,dc=com", "dc=com,governingstructurerule=%01%00" },
            { "governingStructureRule=256,dc=com", "dc=com,governingstructurerule=%82%01%00" },
            // uuid
            { "entryUUID=597ae2f6-16a6-1027-98f4-d28b5365dc14,dc=com",
              "dc=com,entryuuid=597ae2f6-16a6-1027-98f4-d28b5365dc14" },

 opendj-core/src/test/java/org/forgerock/opendj/ldap/schema/IntegerOrderingMatchingRuleTest.java

@@ -22,17 +22,25 @@
 *
 *
 *      Copyright 2009 Sun Microsystems, Inc.
 *      Portions copyright 2014 ForgeRock AS.
 *      Portions copyright 2014-2015 ForgeRock AS.
 */
package org.forgerock.opendj.ldap.schema;

import static org.fest.assertions.Assertions.assertThat;
import static org.forgerock.opendj.ldap.schema.IntegerOrderingMatchingRuleImpl.SIGN_MASK_NEGATIVE;
import static org.forgerock.opendj.ldap.schema.IntegerOrderingMatchingRuleImpl.SIGN_MASK_POSITIVE;
import static org.forgerock.opendj.ldap.schema.IntegerOrderingMatchingRuleImpl.encodeHeader;
import static org.forgerock.opendj.ldap.schema.SchemaConstants.OMR_INTEGER_OID;

import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.ByteStringBuilder;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

/**
 * Test the IntegerOrderingMatchingRule.
 */
@SuppressWarnings("javadoc")
public class IntegerOrderingMatchingRuleTest extends OrderingMatchingRuleTest {

    /** {@inheritDoc} */
@@ -76,6 +84,15 @@
            { "-987654321987654321987654321", "-987654321987654321987654322", 1 },
            {"987654321987654321987654321", "987654321987654321987654322", -1},
            { "987654321987654321987654321", "987654321987654321987654321", 0 },
            // Values which have very different encoded lengths.
            { "-987654321987654321987654321", "-1", -1 },
            { "-987654321987654321987654321", "1", -1 },
            { "987654321987654321987654321", "-1", 1 },
            { "987654321987654321987654321", "1", 1 },
            { "-1", "-987654321987654321987654321", 1 },
            { "1", "-987654321987654321987654321", 1 },
            {"-1", "987654321987654321987654322", -1},
            {"1", "987654321987654321987654322", -1},
        };
    }

@@ -84,4 +101,61 @@
    protected MatchingRule getRule() {
        return Schema.getCoreSchema().getMatchingRule(OMR_INTEGER_OID);
    }

    private enum Sign {
        POSITIVE(SIGN_MASK_POSITIVE), NEGATIVE(SIGN_MASK_NEGATIVE);
        private final byte mask;
        private Sign(byte mask) {
            this.mask = mask;
        }
    };

    private int length(int i) {
        return i;
    }

    private String expected(int... bytes) {
        ByteStringBuilder builder = new ByteStringBuilder();
        for (int b : bytes) {
            builder.append((byte) b);
        }
        return builder.toByteString().toHexString();
    }

    @DataProvider
    private Object[][] headerEncoding() {
        return new Object[][] {
            // @formatter:off
            { length(1 << 0),      Sign.POSITIVE, expected(0x81) },
            { length(1 << 4) - 1,  Sign.POSITIVE, expected(0x8f) },
            { length(1 << 4),      Sign.POSITIVE, expected(0x90, 0x10) },
            { length(1 << 12) - 1, Sign.POSITIVE, expected(0x9f, 0xff) },
            { length(1 << 12),     Sign.POSITIVE, expected(0xa0, 0x10, 0x00) },
            { length(1 << 20) - 1, Sign.POSITIVE, expected(0xaf, 0xff, 0xff) },
            { length(1 << 20),     Sign.POSITIVE, expected(0xb0, 0x10, 0x00, 0x00) },
            { length(1 << 28) - 1, Sign.POSITIVE, expected(0xbf, 0xff, 0xff, 0xff) },
            { length(1 << 28),     Sign.POSITIVE, expected(0xc1, 0x00, 0x00, 0x00, 0x00) },
            { length(1 << 31) - 1, Sign.POSITIVE, expected(0xc7, 0xff, 0xff, 0xff, 0xf0) },

            { length(1 << 0),      Sign.NEGATIVE, expected(0x7e) },
            { length(1 << 4) - 1,  Sign.NEGATIVE, expected(0x70) },
            { length(1 << 4),      Sign.NEGATIVE, expected(0x6f, 0xef) },
            { length(1 << 12) - 1, Sign.NEGATIVE, expected(0x60, 0x00) },
            { length(1 << 12),     Sign.NEGATIVE, expected(0x5f, 0xef, 0xff) },
            { length(1 << 20) - 1, Sign.NEGATIVE, expected(0x50, 0x00, 0x00) },
            { length(1 << 20),     Sign.NEGATIVE, expected(0x4f, 0xef, 0xff, 0xff) },
            { length(1 << 28) - 1, Sign.NEGATIVE, expected(0x40, 0x00, 0x00, 0x00) },
            { length(1 << 28),     Sign.NEGATIVE, expected(0x3e, 0xff, 0xff, 0xff, 0xff) },
            { length(1 << 31) - 1, Sign.NEGATIVE, expected(0x38, 0x00, 0x00, 0x00, 0x0f) },
            // @formatter:on
        };
    }

    @Test(dataProvider = "headerEncoding")
    public void testHeaderEncoding(int length, Sign sign, String expectedHexString) {
        ByteStringBuilder builder = new ByteStringBuilder();
        encodeHeader(builder, length, sign.mask);
        ByteString actual = builder.toByteString();
        assertThat(actual.toHexString()).isEqualTo(expectedHexString);
    }
}