The attached patch adds a new method to the Integer class:
unsigned int MinEncodedBits(Signedness=UNSIGNED) const;
It works just like the existing MinEncodedSize() function except that it
gives a more precise answer by counting bits instead of bytes.
It's also useful for porting Java BigInteger code to C++ because without it
there's no easy way to emulate Java's BigInteger.bitLength() function.
I hope this patch makes it into Crypto++ and would appreciate any feedback.
Thanks.
- Russ
Index: integer.cpp
===================================================================
RCS file: /cvsroot/cryptopp/c5/integer.cpp,v
retrieving revision 1.21
diff -u -r1.21 integer.cpp
--- integer.cpp 31 Oct 2003 02:40:42 -0000 1.21
+++ integer.cpp 15 Nov 2003 03:23:08 -0000
@@ -3052,6 +3052,38 @@
}
}
+unsigned int Integer::MinEncodedBits(Signedness s) const
+{
+ unsigned wordCount = WordCount();
+ unsigned bitCount = 0;
+
+ if (wordCount)
+ {
+ --wordCount;
+ bitCount = BitPrecision(reg[wordCount]);
+ }
+
+ // if signed and *this is not a negative power of 2, ++bitCount
+ if (s == SIGNED)
+ {
+ if (NotNegative() || reg[wordCount] != 1 << (bitCount-1))
+ ++bitCount;
+ else
+ {
+ for (unsigned i = 0; i < wordCount; ++i)
+ {
+ if (reg[i] != 0)
+ {
+ ++bitCount;
+ break;
+ }
+ }
+ }
+ }
+
+ return wordCount * WORD_BITS + bitCount;
+}
+
unsigned int Integer::MinEncodedSize(Signedness signedness) const
{
unsigned int outputLen = STDMAX(1U, ByteCount());
Index: integer.h
===================================================================
RCS file: /cvsroot/cryptopp/c5/integer.h,v
retrieving revision 1.6
diff -u -r1.6 integer.h
--- integer.h 31 Jul 2003 01:54:53 -0000 1.6
+++ integer.h 15 Nov 2003 03:23:09 -0000
@@ -160,11 +160,32 @@
//! \name ENCODE/DECODE
//@{
+ //! minimum number of bits needed to encode this integer
+ /*! For an unsigned encoding, this returns the number of bits needed
+ to represent the absolute value of the number, that is:
+
+ floor(log2(abs(*this))) + 1
+
+ For a signed encoding, this returns number of bits needed to
+ represent the number in 2's complement form, including a sign
bit:
+
+ floor(log2(*this<0 ? -(*this+1) : *this)) + 2
+
+ Signed encodings are particularly useful for interoperating
with
+ code that uses Java's BigInteger class, which exposes a 2's
+ complement representation. The following relation holds between
+ Cryto++'s signed MinEncodedBits() method and Java's bitLength()
+ method:
+
+ Integer::MinEncodedBits(SIGNED) ==
BigInteger.bitLength() + 1
+ */
+ unsigned int MinEncodedBits(Signedness=UNSIGNED) const;
+
//! minimum number of bytes to encode this integer
- /*! MinEncodedSize of 0 is 1 */
+ /*! this returns max(1, ceiling(MinEncodedBits(signedness)/8)) */
unsigned int MinEncodedSize(Signedness=UNSIGNED) const;
//! encode in big-endian format
- /*! unsigned means encode absolute value, signed means encode two's
complement if negative.
+ /*! unsigned means encode absolute value, signed means encode two's
complement
if outputLen < MinEncodedSize, the most significant bytes will
be dropped
if outputLen > MinEncodedSize, the most significant bytes will
be padded
*/
