From d91f8b64e31e912378ec2396908ee4801514a9fa Mon Sep 17 00:00:00 2001 From: "Brian S. O'Neill" Date: Mon, 3 Nov 2008 02:42:40 +0000 Subject: Add back support for BigDecimal now that key encoding works correctly. --- .../java/com/amazon/carbonado/raw/DataDecoder.java | 3 +- .../java/com/amazon/carbonado/raw/DataEncoder.java | 5 +- .../amazon/carbonado/raw/EncodingConstants.java | 5 + .../carbonado/raw/GenericEncodingStrategy.java | 4 +- .../java/com/amazon/carbonado/raw/KeyDecoder.java | 170 ++++++----- .../java/com/amazon/carbonado/raw/KeyEncoder.java | 326 ++++++++++++--------- 6 files changed, 286 insertions(+), 227 deletions(-) (limited to 'src/main/java') diff --git a/src/main/java/com/amazon/carbonado/raw/DataDecoder.java b/src/main/java/com/amazon/carbonado/raw/DataDecoder.java index ce5b7c9..407df0c 100644 --- a/src/main/java/com/amazon/carbonado/raw/DataDecoder.java +++ b/src/main/java/com/amazon/carbonado/raw/DataDecoder.java @@ -400,7 +400,7 @@ public class DataDecoder { * @return amount of bytes read from source * @throws CorruptEncodingException if source data is corrupt * @since 1.2 - * / + */ public static int decode(byte[] src, int srcOffset, BigDecimal[] valueRef) throws CorruptEncodingException { @@ -446,7 +446,6 @@ public class DataDecoder { throw new CorruptEncodingException(null, e); } } - */ /** * Decodes the given byte array. diff --git a/src/main/java/com/amazon/carbonado/raw/DataEncoder.java b/src/main/java/com/amazon/carbonado/raw/DataEncoder.java index 990b7e7..4b6cab4 100644 --- a/src/main/java/com/amazon/carbonado/raw/DataEncoder.java +++ b/src/main/java/com/amazon/carbonado/raw/DataEncoder.java @@ -362,7 +362,7 @@ public class DataEncoder { * @param dstOffset offset into destination array * @return amount of bytes written * @since 1.2 - * / + */ public static int encode(BigDecimal value, byte[] dst, int dstOffset) { if (value == null) { dst[dstOffset] = NULL_BYTE_HIGH; @@ -378,14 +378,13 @@ public class DataEncoder { * @param value BigDecimal value to encode, may be null * @return amount of bytes needed to encode * @since 1.2 - * / + */ public static int calculateEncodedLength(BigDecimal value) { if (value == null) { return 1; } return signedVarIntLength(value.scale()) + calculateEncodedLength(value.unscaledValue()); } - */ /** * Encodes the given optional byte array into a variable amount of diff --git a/src/main/java/com/amazon/carbonado/raw/EncodingConstants.java b/src/main/java/com/amazon/carbonado/raw/EncodingConstants.java index 997e491..5defdc2 100644 --- a/src/main/java/com/amazon/carbonado/raw/EncodingConstants.java +++ b/src/main/java/com/amazon/carbonado/raw/EncodingConstants.java @@ -18,6 +18,8 @@ package com.amazon.carbonado.raw; +import java.math.BigInteger; + /** * * @@ -40,4 +42,7 @@ class EncodingConstants { /** Byte to terminate variable data encoded for ascending order */ static final byte TERMINATOR = (byte)1; + + static final BigInteger ONE_HUNDRED = BigInteger.valueOf(100); + static final BigInteger ONE_THOUSAND = BigInteger.valueOf(1000); } diff --git a/src/main/java/com/amazon/carbonado/raw/GenericEncodingStrategy.java b/src/main/java/com/amazon/carbonado/raw/GenericEncodingStrategy.java index c68f06b..c5417c4 100644 --- a/src/main/java/com/amazon/carbonado/raw/GenericEncodingStrategy.java +++ b/src/main/java/com/amazon/carbonado/raw/GenericEncodingStrategy.java @@ -383,8 +383,8 @@ public class GenericEncodingStrategy { Class clazz = propertyType.toClass(); if (clazz != null) { return Lob.class.isAssignableFrom(clazz) || - BigInteger.class.isAssignableFrom(clazz);/* || - BigDecimal.class.isAssignableFrom(clazz);*/ + BigInteger.class.isAssignableFrom(clazz) || + BigDecimal.class.isAssignableFrom(clazz); } return false; } diff --git a/src/main/java/com/amazon/carbonado/raw/KeyDecoder.java b/src/main/java/com/amazon/carbonado/raw/KeyDecoder.java index eb44c53..a14a1a3 100644 --- a/src/main/java/com/amazon/carbonado/raw/KeyDecoder.java +++ b/src/main/java/com/amazon/carbonado/raw/KeyDecoder.java @@ -443,60 +443,11 @@ public class KeyDecoder { * @return amount of bytes read from source * @throws CorruptEncodingException if source data is corrupt * @since 1.2 - * / + */ public static int decode(byte[] src, int srcOffset, BigDecimal[] valueRef) throws CorruptEncodingException { - final int originalOffset; - BigInteger unscaledValue; - int scale; - - try { - int header = src[srcOffset] & 0xff; - - int headerSize; - switch (header) { - case (NULL_BYTE_HIGH & 0xff): case (NULL_BYTE_LOW & 0xff): - valueRef[0] = null; - return 1; - - case 0x7f: case 0x80: - valueRef[0] = BigDecimal.ZERO; - return 1; - - case 1: case 0x7e: case 0x81: case 0xfe: - headerSize = 5; - break; - - default: - headerSize = 1; - break; - } - - originalOffset = srcOffset; - srcOffset += headerSize; - - BigInteger[] unscaledRef = new BigInteger[1]; - srcOffset += decode(src, srcOffset, unscaledRef); - - header = src[srcOffset++] & 0xff; - if (header > 0 && header < 0xff) { - scale = header - 0x80; - } else { - scale = DataDecoder.decodeInt(src, srcOffset); - srcOffset += 4; - } - - unscaledValue = unscaledRef[0]; - if (unscaledValue.signum() < 0) { - scale = ~scale; - } - } catch (IndexOutOfBoundsException e) { - throw new CorruptEncodingException(null, e); - } - - valueRef[0] = new BigDecimal(unscaledValue, scale); - return srcOffset - originalOffset; + return decode(src, srcOffset, valueRef, 0); } /** @@ -508,18 +459,29 @@ public class KeyDecoder { * @return amount of bytes read from source * @throws CorruptEncodingException if source data is corrupt * @since 1.2 - * / + */ public static int decodeDesc(byte[] src, int srcOffset, BigDecimal[] valueRef) throws CorruptEncodingException { - final int originalOffset; + return decode(src, srcOffset, valueRef, -1); + } + + /** + * @param xorMask 0 for normal decoding, -1 for descending decoding + */ + private static int decode(byte[] src, int srcOffset, BigDecimal[] valueRef, int xorMask) + throws CorruptEncodingException + { + final int originalOffset = srcOffset; BigInteger unscaledValue; int scale; try { - int header = src[srcOffset] & 0xff; + int header = (src[srcOffset] ^ xorMask) & 0xff; + + int digitAdjust; + int exponent; - int headerSize; switch (header) { case (NULL_BYTE_HIGH & 0xff): case (NULL_BYTE_LOW & 0xff): valueRef[0] = null; @@ -529,33 +491,92 @@ public class KeyDecoder { valueRef[0] = BigDecimal.ZERO; return 1; - case 1: case 0x7e: case 0x81: case 0xfe: - headerSize = 5; + case 1: case 0x7e: + digitAdjust = 999 + 12; + exponent = (~DataDecoder.decodeInt(src, srcOffset + 1)) ^ xorMask; + srcOffset += 5; + break; + + case 0x81: case 0xfe: + digitAdjust = 12; + exponent = DataDecoder.decodeInt(src, srcOffset + 1) ^ xorMask; + srcOffset += 5; break; default: - headerSize = 1; + exponent = (src[srcOffset++] ^ xorMask) & 0xff; + if (exponent >= 0x82) { + digitAdjust = 12; + exponent -= 0xc0; + } else { + digitAdjust = 999 + 12; + exponent = 0x3f - exponent; + } break; } - originalOffset = srcOffset; - srcOffset += headerSize; - - BigInteger[] unscaledRef = new BigInteger[1]; - srcOffset += decodeDesc(src, srcOffset, unscaledRef); - - header = src[srcOffset++] & 0xff; - if (header > 0 && header < 0xff) { - scale = 0x7f - header; - } else { - scale = ~DataDecoder.decodeInt(src, srcOffset); - srcOffset += 4; + // Significand is base 1000 encoded, 10 bits per digit. + + unscaledValue = null; + int precision = 0; + + int accum = 0; + int bits = 0; + BigInteger lastDigit = null; + + loop: while (true) { + accum = (accum << 8) | ((src[srcOffset++] ^ xorMask) & 0xff); + bits += 8; + if (bits >= 10) { + int digit = (accum >> (bits - 10)) & 0x3ff; + + switch (digit) { + case 0: + case 1023: + lastDigit = lastDigit.divide(ONE_HUNDRED); + if (unscaledValue == null) { + unscaledValue = lastDigit; + } else { + unscaledValue = unscaledValue.multiply(BigInteger.TEN).add(lastDigit); + } + precision += 1; + break loop; + case 1: + case 1022: + lastDigit = lastDigit.divide(BigInteger.TEN); + if (unscaledValue == null) { + unscaledValue = lastDigit; + } else { + unscaledValue = unscaledValue.multiply(ONE_HUNDRED).add(lastDigit); + } + precision += 2; + break loop; + case 2: + case 1021: + if (unscaledValue == null) { + unscaledValue = lastDigit; + } else { + unscaledValue = unscaledValue.multiply(ONE_THOUSAND).add(lastDigit); + } + precision += 3; + break loop; + + default: + if (unscaledValue == null) { + if ((unscaledValue = lastDigit) != null) { + precision += 3; + } + } else { + unscaledValue = unscaledValue.multiply(ONE_THOUSAND).add(lastDigit); + precision += 3; + } + bits -= 10; + lastDigit = BigInteger.valueOf(digit - digitAdjust); + } + } } - unscaledValue = unscaledRef[0]; - if (unscaledValue.signum() < 0) { - scale = ~scale; - } + scale = precision - exponent; } catch (IndexOutOfBoundsException e) { throw new CorruptEncodingException(null, e); } @@ -563,7 +584,6 @@ public class KeyDecoder { valueRef[0] = new BigDecimal(unscaledValue, scale); return srcOffset - originalOffset; } - */ /** * Decodes the given byte array as originally encoded for ascending order. diff --git a/src/main/java/com/amazon/carbonado/raw/KeyEncoder.java b/src/main/java/com/amazon/carbonado/raw/KeyEncoder.java index 0c90499..bea676b 100644 --- a/src/main/java/com/amazon/carbonado/raw/KeyEncoder.java +++ b/src/main/java/com/amazon/carbonado/raw/KeyEncoder.java @@ -434,90 +434,19 @@ public class KeyEncoder { * @param dstOffset offset into destination array * @return amount of bytes written * @since 1.2 - * / + */ public static int encode(BigDecimal value, byte[] dst, int dstOffset) { - /* Encoding of first byte: - - 0x00: null low (unused) - 0x01: negative signum; four bytes follow for positive exponent - 0x02..0x3f: negative signum; positive exponent; 3e range, 61..0 - 0x40..0x7d: negative signum; negative exponent; 3e range, -1..-62 - 0x7e: negative signum; four bytes follow for negative exponent - 0x7f: negative zero (unused) - 0x80: zero - 0x81: positive signum; four bytes follow for negative exponent - 0x82..0xbf: positive signum; negative exponent; 3e range, -62..-1 - 0xc0..0xfd: positive signum; positive exponent; 3e range, 0..61 - 0xfe: positive signum; four bytes follow for positive exponent - 0xff: null high - * / - if (value == null) { dst[dstOffset] = NULL_BYTE_HIGH; return 1; } - int signum = value.signum(); - if (signum == 0) { + if (value.signum() == 0) { dst[dstOffset] = (byte) 0x80; return 1; } - final int originalOffset = dstOffset; - - int scale = value.scale(); - int exponent = value.precision() - scale; - System.out.println("exponent: " + exponent); - System.out.println("unscaled: " + value.unscaledValue()); - - if (signum < 0) { - if (exponent >= -0x3e && exponent < 0x3e) { - dst[dstOffset++] = (byte) (0x3f - exponent); - } else { - if (exponent < 0) { - dst[dstOffset++] = (byte) 0x7e; - } else { - dst[dstOffset++] = (byte) 1; - } - DataEncoder.encode(~exponent, dst, dstOffset); - dstOffset += 4; - } - } else { - if (exponent >= -0x3e && exponent < 0x3e) { - dst[dstOffset++] = (byte) (exponent + 0xc0); - } else { - if (exponent < 0) { - dst[dstOffset++] = (byte) 0x81; - } else { - dst[dstOffset++] = (byte) 0xfe; - } - DataEncoder.encode(exponent, dst, dstOffset); - dstOffset += 4; - } - } - - dstOffset += encode(value.unscaledValue(), dst, dstOffset); - - /* Encoding of scale: - - 0x00: negative scale; four bytes follow for scale - 0x01..0x7f: negative scale; 7f range, -127..-1 - 0x80..0xfe: positive scale; 7f range, 0..126 - 0xff: positive scale; four bytes follow for scale - * / - - if (signum < 0) { - scale = ~scale; - } - if (scale >= -0x7f && scale < 0x7f) { - dst[dstOffset++] = (byte) (scale + 0x80); - } else { - dst[dstOffset++] = scale < 0 ? ((byte) 0) : ((byte) 0xff); - DataEncoder.encode(scale, dst, dstOffset); - dstOffset += 4; - } - - return dstOffset - originalOffset; + return encode(value).copyTo(dst, dstOffset); } /** @@ -534,114 +463,221 @@ public class KeyEncoder { * @param dstOffset offset into destination array * @return amount of bytes written * @since 1.2 - * / + */ public static int encodeDesc(BigDecimal value, byte[] dst, int dstOffset) { - /* Encoding of first byte: - - 0x00: null high (unused) - 0x01: positive signum; four bytes follow for positive exponent - 0x02..0x3f: positive signum; positive exponent; 3e range, 0..61 - 0x40..0x7d: positive signum; negative exponent; 3e range, -62..-1 - 0x7e: positive signum; four bytes follow for negative exponent - 0x7f: zero - 0x80: negative zero (unused) - 0x81: negative signum; four bytes follow for negative exponent - 0x82..0xbf: negative signum; negative exponent; 3e range, -1..-62 - 0xc0..0xfd: negative signum; positive exponent; 3e range, 61..0 - 0xfe: negative signum; four bytes follow for positive exponent - 0xff: null low - * / - if (value == null) { dst[dstOffset] = NULL_BYTE_LOW; return 1; } - int signum = value.signum(); - if (signum == 0) { + if (value.signum() == 0) { dst[dstOffset] = (byte) 0x7f; return 1; } - final int originalOffset = dstOffset; + return encode(value).copyDescTo(dst, dstOffset); + } + + /** + * Returns the amount of bytes required to encode a BigDecimal. + * + *

Note: It is recommended that value be normalized by stripping + * trailing zeros. This makes searching by value much simpler. + * + * @param value BigDecimal value to encode, may be null + * @return amount of bytes needed to encode + * @since 1.2 + */ + public static int calculateEncodedLength(BigDecimal value) { + if (value == null || value.signum() == 0) { + return 1; + } + + return encode(value).mLength; + } + + private static class CachedBigDecimal { + static final ThreadLocal cLocal = + new ThreadLocal(); + + final BigDecimal mValue; + final byte[] mEncoded; + final int mLength; + + CachedBigDecimal(BigDecimal value, byte[] encoded, int length) { + mValue = value; + mEncoded = encoded; + mLength = length; + } + + int copyTo(byte[] dst, int dstOffset) { + int length = mLength; + System.arraycopy(mEncoded, 0, dst, dstOffset, length); + return length; + } + + int copyDescTo(byte[] dst, int dstOffset) { + byte[] encoded = mEncoded; + int length = mLength; + for (int i=0; i> 3); + + byte[] encoded = new byte[length]; + length = encodeUncached(value, encoded); + + cached = new CachedBigDecimal(value, encoded, length); + CachedBigDecimal.cLocal.set(cached); + + return cached; + } + + /** + * @param value cannot be null or zero + */ + private static int encodeUncached(BigDecimal value, byte[] dst) { + /* Encoding of header: + + 0x00: null low (unused) + 0x01: negative signum; four bytes follow for positive exponent + 0x02..0x3f: negative signum; positive exponent; 3e range, 61..0 + 0x40..0x7d: negative signum; negative exponent; 3e range, -1..-62 + 0x7e: negative signum; four bytes follow for negative exponent + 0x7f: negative zero (unused) + 0x80: zero + 0x81: positive signum; four bytes follow for negative exponent + 0x82..0xbf: positive signum; negative exponent; 3e range, -62..-1 + 0xc0..0xfd: positive signum; positive exponent; 3e range, 0..61 + 0xfe: positive signum; four bytes follow for positive exponent + 0xff: null high + */ - int scale = value.scale(); - int exponent = value.precision() - scale; + int dstOffset = 0; + int precision = value.precision(); + int exponent = precision - value.scale(); - if (signum < 0) { + if (value.signum() < 0) { if (exponent >= -0x3e && exponent < 0x3e) { - dst[dstOffset++] = (byte) (exponent + 0xc0); + dst[dstOffset++] = (byte) (0x3f - exponent); } else { if (exponent < 0) { - dst[dstOffset++] = (byte) 0x81; + dst[dstOffset] = (byte) 0x7e; } else { - dst[dstOffset++] = (byte) 0xfe; + dst[dstOffset] = (byte) 1; } - DataEncoder.encode(exponent, dst, dstOffset); - dstOffset += 4; + DataEncoder.encode(~exponent, dst, dstOffset + 1); + dstOffset += 5; } } else { if (exponent >= -0x3e && exponent < 0x3e) { - dst[dstOffset++] = (byte) (0x3f - exponent); + dst[dstOffset++] = (byte) (exponent + 0xc0); } else { if (exponent < 0) { - dst[dstOffset++] = (byte) 0x7e; + dst[dstOffset] = (byte) 0x81; } else { - dst[dstOffset++] = (byte) 1; + dst[dstOffset] = (byte) 0xfe; } - DataEncoder.encode(~exponent, dst, dstOffset); - dstOffset += 4; + DataEncoder.encode(exponent, dst, dstOffset + 1); + dstOffset += 5; } } - dstOffset += encodeDesc(value.unscaledValue(), dst, dstOffset); - - /* Encoding of scale: + // Significand must be decimal encoded to maintain proper sort order. + // Base 1000 is more efficient than base 10 and still maintains proper + // sort order. A minimum of two bytes must be generated, however. + + BigInteger unscaledValue = value.unscaledValue(); + + // Ensure a non-fractional amount of base 1000 digits. + int terminator; + switch (precision % 3) { + case 0: default: + terminator = 2; + break; + case 1: + terminator = 0; + unscaledValue = unscaledValue.multiply(ONE_HUNDRED); + break; + case 2: + terminator = 1; + unscaledValue = unscaledValue.multiply(BigInteger.TEN); + break; + } - 0x00: positive scale; four bytes follow for scale - 0x01..0x7f: positive scale; 7f range, 0..126 - 0x80..0xfe: negative scale; 7f range, -127..-1 - 0xff: negative scale; four bytes follow for scale - * / + // 10 bits per digit and 1 extra terminator digit. Digit values 0..999 + // are encoded as 12..1011. Digit values 0..11 and 1012..1023 are used + // for terminators. - if (signum < 0) { - scale = ~scale; - } - if (scale >= -0x7f && scale < 0x7f) { - dst[dstOffset++] = (byte) (0x7f - scale); + int digitAdjust; + if (unscaledValue.signum() >= 0) { + digitAdjust = 12; } else { - dst[dstOffset++] = scale < 0 ? ((byte) 0xff) : ((byte) 0); - DataEncoder.encode(~scale, dst, dstOffset); - dstOffset += 4; + digitAdjust = 999 + 12; + terminator = 1023 - terminator; } - return dstOffset - originalOffset; - } + int pos = ((unscaledValue.bitLength() + 9) / 10) + 1; + int[] digits = new int[pos]; + digits[--pos] = terminator; - /** - * Returns the amount of bytes required to encode a BigDecimal. - * - *

Note: It is recommended that value be normalized by stripping - * trailing zeros. This makes searching by value much simpler. - * - * @param value BigDecimal value to encode, may be null - * @return amount of bytes needed to encode - * @since 1.2 - * / - public static int calculateEncodedLength(BigDecimal value) { - if (value == null || value.signum() == 0) { - return 1; + while (unscaledValue.signum() != 0) { + BigInteger[] divrem = unscaledValue.divideAndRemainder(ONE_THOUSAND); + + if (--pos < 0) { + // Handle rare case when an extra digit is required. + int[] newDigits = new int[digits.length + 1]; + System.arraycopy(digits, 0, newDigits, 1, digits.length); + digits = newDigits; + pos = 0; + } + + digits[pos] = divrem[1].intValue() + digitAdjust; + + unscaledValue = divrem[0]; + } + + // Now encode digits in proper order, 10 bits per digit. 1024 possible + // values per 10 bits, and so base 1000 is quite efficient. + + int accum = 0; + int bits = 0; + for (int i=0; i> (bits -= 8)); + } while (bits >= 8); } - int scale = value.scale(); - int exponent = value.precision() - value.scale(); + if (bits != 0) { + dst[dstOffset++] = (byte) (accum << (8 - bits)); + } - int headerSize = (exponent >= -0x3e && exponent < 0x3e) ? 1 : 5; - int scaleSize = (scale >= -0x7f && scale < 0x7f) ? 1 : 5; - - return headerSize + calculateEncodedLength(value.unscaledValue()) + scaleSize; + return dstOffset; } - */ /** * Encodes the given optional unsigned byte array into a variable amount of -- cgit v1.2.3