From 88194f7f16e705c21ea890febb8f1f2f3e2420b7 Mon Sep 17 00:00:00 2001
From: "Brian S. O'Neill" <bronee@gmail.com>
Date: Fri, 18 Jul 2008 04:39:37 +0000
Subject: Added utilities for encoding and decoding BigIntegers.
---
.../java/com/amazon/carbonado/raw/DataDecoder.java | 21 ++++
.../java/com/amazon/carbonado/raw/DataEncoder.java | 57 +++++++++++
.../java/com/amazon/carbonado/raw/KeyDecoder.java | 89 +++++++++++++++++
.../java/com/amazon/carbonado/raw/KeyEncoder.java | 107 +++++++++++++++++++++
4 files changed, 274 insertions(+)
(limited to 'src/main/java/com/amazon/carbonado')
diff --git a/src/main/java/com/amazon/carbonado/raw/DataDecoder.java b/src/main/java/com/amazon/carbonado/raw/DataDecoder.java
index 635b52e..5ea5c1d 100644
--- a/src/main/java/com/amazon/carbonado/raw/DataDecoder.java
+++ b/src/main/java/com/amazon/carbonado/raw/DataDecoder.java
@@ -18,6 +18,8 @@
package com.amazon.carbonado.raw;
+import java.math.BigInteger;
+
import java.io.EOFException;
import java.io.InputStream;
import java.io.IOException;
@@ -369,6 +371,25 @@ public class DataDecoder {
}
}
+ /**
+ * Decodes a BigInteger.
+ *
+ * @param src source of encoded data
+ * @param srcOffset offset into encoded data
+ * @param valueRef decoded BigInteger is stored in element 0, which may be null
+ * @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, BigInteger[] valueRef)
+ throws CorruptEncodingException
+ {
+ byte[][] bytesRef = new byte[1][];
+ int amt = decode(src, srcOffset, bytesRef);
+ valueRef[0] = (bytesRef[0] == null) ? null : new BigInteger(bytesRef[0]);
+ return amt;
+ }
+
/**
* 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 e8383b9..7f4f5d3 100644
--- a/src/main/java/com/amazon/carbonado/raw/DataEncoder.java
+++ b/src/main/java/com/amazon/carbonado/raw/DataEncoder.java
@@ -18,6 +18,8 @@
package com.amazon.carbonado.raw;
+import java.math.BigInteger;
+
import java.io.IOException;
import java.io.OutputStream;
@@ -306,6 +308,61 @@ public class DataEncoder {
}
}
+ /**
+ * Encodes the given optional BigInteger into a variable amount of
+ * bytes. If the BigInteger is null, exactly 1 byte is written. Otherwise,
+ * the amount written can be determined by calling calculateEncodedLength.
+ *
+ * @param value BigInteger value to encode, may be null
+ * @param dst destination for encoded bytes
+ * @param dstOffset offset into destination array
+ * @return amount of bytes written
+ * @since 1.2
+ */
+ public static int encode(BigInteger value, byte[] dst, int dstOffset) {
+ if (value == null) {
+ dst[dstOffset] = NULL_BYTE_HIGH;
+ return 1;
+ }
+
+ byte[] bytes = value.toByteArray();
+
+ // Write the byte array length first, in a variable amount of bytes.
+ int amt = encodeLength(bytes.length, dst, dstOffset);
+
+ // Now write the byte array.
+ System.arraycopy(bytes, 0, dst, dstOffset + amt, bytes.length);
+
+ return amt + bytes.length;
+ }
+
+ /**
+ * Returns the amount of bytes required to encode the given BigInteger.
+ *
+ * @param value BigInteger value to encode, may be null
+ * @return amount of bytes needed to encode
+ * @since 1.2
+ */
+ public static int calculateEncodedLength(BigInteger value) {
+ if (value == null) {
+ return 1;
+ }
+
+ int byteCount = (value.bitLength() >> 3) + 1;
+
+ if (byteCount < 128) {
+ return 1 + byteCount;
+ } else if (byteCount < 16384) {
+ return 2 + byteCount;
+ } else if (byteCount < 2097152) {
+ return 3 + byteCount;
+ } else if (byteCount < 268435456) {
+ return 4 + byteCount;
+ } else {
+ return 5 + byteCount;
+ }
+ }
+
/**
* Encodes the given optional byte array into a variable amount of
* bytes. If the byte array is null, exactly 1 byte is written. Otherwise,
diff --git a/src/main/java/com/amazon/carbonado/raw/KeyDecoder.java b/src/main/java/com/amazon/carbonado/raw/KeyDecoder.java
index 4f78738..8c4bf02 100644
--- a/src/main/java/com/amazon/carbonado/raw/KeyDecoder.java
+++ b/src/main/java/com/amazon/carbonado/raw/KeyDecoder.java
@@ -18,6 +18,8 @@
package com.amazon.carbonado.raw;
+import java.math.BigInteger;
+
import com.amazon.carbonado.CorruptEncodingException;
import static com.amazon.carbonado.raw.EncodingConstants.*;
@@ -331,6 +333,93 @@ public class KeyDecoder {
return bits == 0x7fffffffffffffffL ? null : Double.longBitsToDouble(bits);
}
+ /**
+ * Decodes the given BigInteger as originally encoded for ascending order.
+ *
+ * @param src source of encoded data
+ * @param srcOffset offset into encoded data
+ * @param valueRef decoded BigInteger is stored in element 0, which may be null
+ * @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, BigInteger[] valueRef)
+ throws CorruptEncodingException
+ {
+ int header = src[srcOffset];
+ if (header == NULL_BYTE_HIGH || header == NULL_BYTE_LOW) {
+ valueRef[0] = null;
+ return 1;
+ }
+
+ header &= 0xff;
+
+ int headerSize;
+ int bytesLength;
+ if (header > 1 && header < 0xfe) {
+ if (header < 0x80) {
+ bytesLength = 0x80 - header;
+ } else {
+ bytesLength = header - 0x7f;
+ }
+ headerSize = 1;
+ } else {
+ bytesLength = Math.abs(DataDecoder.decodeInt(src, srcOffset + 1));
+ headerSize = 5;
+ }
+
+ byte[] bytes = new byte[bytesLength];
+ System.arraycopy(src, srcOffset + headerSize, bytes, 0, bytesLength);
+ valueRef[0] = new BigInteger(bytes);
+ return headerSize + bytesLength;
+ }
+
+ /**
+ * Decodes the given BigInteger as originally encoded for descending order.
+ *
+ * @param src source of encoded data
+ * @param srcOffset offset into encoded data
+ * @param valueRef decoded BigInteger is stored in element 0, which may be null
+ * @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, BigInteger[] valueRef)
+ throws CorruptEncodingException
+ {
+ int header = src[srcOffset];
+ if (header == NULL_BYTE_HIGH || header == NULL_BYTE_LOW) {
+ valueRef[0] = null;
+ return 1;
+ }
+
+ header &= 0xff;
+
+ int headerSize;
+ int bytesLength;
+ if (header > 1 && header < 0xfe) {
+ if (header < 0x80) {
+ bytesLength = 0x80 - header;
+ } else {
+ bytesLength = header - 0x7f;
+ }
+ headerSize = 1;
+ } else {
+ bytesLength = Math.abs(DataDecoder.decodeInt(src, srcOffset + 1));
+ headerSize = 5;
+ }
+
+ byte[] bytes = new byte[bytesLength];
+
+ srcOffset += headerSize;
+ for (int i=0; i<bytesLength; i++) {
+ bytes[i] = (byte) ~src[srcOffset + i];
+ }
+
+ valueRef[0] = new BigInteger(bytes);
+ return headerSize + bytesLength;
+ }
+
/**
* Decodes the given byte array as originally encoded for ascending order.
* The decoding stops when any kind of terminator or illegal byte has been
diff --git a/src/main/java/com/amazon/carbonado/raw/KeyEncoder.java b/src/main/java/com/amazon/carbonado/raw/KeyEncoder.java
index 8d374a1..2d2dd71 100644
--- a/src/main/java/com/amazon/carbonado/raw/KeyEncoder.java
+++ b/src/main/java/com/amazon/carbonado/raw/KeyEncoder.java
@@ -18,6 +18,8 @@
package com.amazon.carbonado.raw;
+import java.math.BigInteger;
+
import static com.amazon.carbonado.raw.EncodingConstants.*;
/**
@@ -297,6 +299,111 @@ public class KeyEncoder {
}
}
+ /**
+ * Encodes the given optional BigInteger into a variable amount of
+ * bytes. If the BigInteger is null, exactly 1 byte is written. Otherwise,
+ * the amount written can be determined by calling calculateEncodedLength.
+ *
+ * @param value byte array value to encode, may be null
+ * @param dst destination for encoded bytes
+ * @param dstOffset offset into destination array
+ * @return amount of bytes written
+ * @since 1.2
+ */
+ public static int encode(BigInteger value, byte[] dst, int dstOffset) {
+ if (value == null) {
+ dst[dstOffset] = NULL_BYTE_HIGH;
+ return 1;
+ }
+
+ byte[] bytes = value.toByteArray();
+ // Always at least one.
+ int bytesLength = bytes.length;
+
+ int headerSize;
+ if (bytesLength < 0x7f) {
+ // First byte is 0x02..0x7f for negative values and 0x80..0xfd for
+ // positive values.
+ if (value.signum() < 0) {
+ dst[dstOffset] = (byte) (0x80 - bytesLength);
+ } else {
+ dst[dstOffset] = (byte) (bytesLength + 0x7f);
+ }
+ headerSize = 1;
+ } else {
+ dst[dstOffset] = (byte) (value.signum() < 0 ? 1 : 0xfe);
+ int encodedLen = value.signum() < 0 ? -bytesLength : bytesLength;
+ DataEncoder.encode(encodedLen, dst, dstOffset + 1);
+ headerSize = 5;
+ }
+
+ System.arraycopy(bytes, 0, dst, headerSize + dstOffset, bytesLength);
+
+ return headerSize + bytesLength;
+ }
+
+ /**
+ * Encodes the given optional BigInteger into a variable amount of bytes
+ * for descending order. If the BigInteger is null, exactly 1 byte is
+ * written. Otherwise, the amount written can be determined by calling
+ * calculateEncodedLength.
+ *
+ * @param value byte array value to encode, may be null
+ * @param dst destination for encoded bytes
+ * @param dstOffset offset into destination array
+ * @return amount of bytes written
+ * @since 1.2
+ */
+ public static int encodeDesc(BigInteger value, byte[] dst, int dstOffset) {
+ if (value == null) {
+ dst[dstOffset] = NULL_BYTE_LOW;
+ return 1;
+ }
+
+ byte[] bytes = value.toByteArray();
+ // Always at least one.
+ int bytesLength = bytes.length;
+
+ int headerSize;
+ if (bytesLength < 0x7f) {
+ // First byte is 0x02..0x7f for negative values and 0x80..0xfd for
+ // positive values.
+ if (value.signum() < 0) {
+ dst[dstOffset] = (byte) (bytesLength + 0x7f);
+ } else {
+ dst[dstOffset] = (byte) (0x80 - bytesLength);
+ }
+ headerSize = 1;
+ } else {
+ dst[dstOffset] = (byte) (value.signum() < 0 ? 0xfe : 1);
+ int encodedLen = value.signum() < 0 ? bytesLength : -bytesLength;
+ DataEncoder.encode(encodedLen, dst, dstOffset + 1);
+ headerSize = 5;
+ }
+
+ dstOffset += headerSize;
+ for (int i=0; i<bytesLength; i++) {
+ dst[dstOffset + i] = (byte) ~bytes[i];
+ }
+
+ return headerSize + bytesLength;
+ }
+
+ /**
+ * Returns the amount of bytes required to encode a BigInteger.
+ *
+ * @param value BigInteger value to encode, may be null
+ * @return amount of bytes needed to encode
+ * @since 1.2
+ */
+ public static int calculateEncodedLength(BigInteger value) {
+ if (value == null) {
+ return 1;
+ }
+ int bytesLength = (value.bitLength() >> 3) + 1;
+ return bytesLength < 0x7f ? (1 + bytesLength) : (5 + bytesLength);
+ }
+
/**
* Encodes the given optional unsigned byte array into a variable amount of
* bytes. If the byte array is null, exactly 1 byte is written. Otherwise,
--
cgit v1.2.3