1 files changed, 251 insertions, 0 deletions
diff --git a/src/bitstring.h b/src/bitstring.h
new file mode 100644
index 0000000..8052691
--- /dev/null
+++ b/src/bitstring.h
@@ -0,0 +1,251 @@
+#ifndef BU_BITSTRING_H
+#define BU_BITSTRING_H
+namespace Bu
+{
+        /**
+         * Manages an arbitrarily sized string of bits, and allows basic interaction
+         * with them.  This includes basic non-mathematical bitwise operations such
+         * as setting and testing bits, shifting the string, inversion and a few
+         * extras like randomization.  On linux systems this takes advantage of long
+         * longs giving you a maximum size of about 2tb per string.
+         *
+         * For more general and mathematical type interaction see BitStringInt.
+         * 
+         *@author Mike Buland
+         */
+        class BitString
+        {
+        public:
+                /**
+                 * Constructs a blank and basic BitString.  This is actually useful since
+                 * you can resize BitStrings at will, and even retain the data that was
+                 * in them.
+                 */
+                BitString();
+                /**
+                 * Constructs a BitString object as a copy of another BitString.  This is
+                 * a standard copy constructor and produces an exact duplicate of the
+                 * original BitString object.
+                 *@param xSrc Source BitString to copy data from.
+                 */
+                BitString( const BitString &xSrc );
+                /**
+                 * Constructs a BitString with length nBits and optionally fills it with
+                 * random data.  The default setting, to not fill randomly, will produce
+                 * a blank (all zeros) string of the specified size.
+                 *@param nBits The length of the new BitString in bits.
+                 *@param bFillRandomly Wether or not to randomize this BitString.
+                 */
+                BitString( long nBits, bool bFillRandomly=false );
+                /**
+                 * Virtual deconstructor for the BitString.  Takes care of cleanup for you.
+                 * What more do you really want to know?
+                 */
+                virtual ~BitString();
+                // basic interaction
+                /**
+                 * Sets a bit in the BitString.  In it's normal mode it will always turn
+                 * the given bit on, to clear a bit set bBitState to false instead of
+                 * true.  This operation runs in O(1).
+                 *@param nBit The zero-based index of the bit to modify.
+                 *@param bBitState Set to true to set the bit to 1, set to false to set
+                 * the bit to 0.
+                 */
+                void setBit( long nBit, bool bBitState=true );
+                /**
+                 * Reverses the state of the given bit.  This will set the given bit to a
+                 * 1 if it was 0, and to 0 if it was 1.  This operation runs in O(1), and
+                 * it should be noted that using this is marginally faster than doing the
+                 * test and flip yourself with getBit and setBit since it uses a bitwise
+                 * not operation and doesn't actually test the bit itself.
+                 *@param nBit The index of the bit to flip.
+                 */
+                void flipBit( long nBit );
+                /**
+                 * Gets the state of the given bit.  This follows the standard convention
+                 * used so far, a returned value of true means the bit in question is 1,
+                 * and a value of flase means the bit is 0.  All bits out of range of the
+                 * BitString are treated as off, but are "accessable" in that this does not
+                 * produce any kind of error message.  This is intentional.  This operation
+                 * runs in O(1).
+                 *@param nBit The index of the bit to test.
+                 *@returns True for a 1, false for a 0.
+                 */
+                bool getBit( long nBit );
+                /**
+                 * Inverts the entire BitString, in effect this calls flipBit on every bit
+                 * in the string but is faster since it can operate on whole bytes at a
+                 * time instead of individual bits.  This operation runs in O(N).
+                 */
+                void invert();
+                /**
+                 * Returns the number of bits allocated in this BitString.  This operation
+                 * runs in O(N) time since this value is cached and not computed.
+                 *@returns The number of bits allocated in this BitString.
+                 */
+                long getBitLength();
+                /**
+                 * Sets the entire BitString to zeros, but it does it very quickly.  This
+                 * operation runs in O(N).
+                 */
+                void clearString();
+                /**
+                 * Gets another BitString that is autonomous of the current one (contains
+                 * a copy of the memory, not a pointer) and contains a subset of the data
+                 * in the current BitString.  This is an inclusive operation, so grabbing
+                 * bits 0-5 will give you 6 bits.  This is based on a very tricky
+                 * bit-shifting algorithm and runs very quickly, in O(N) time.
+                 * Passing in a value of zero for nUpper, or any value for nUpper that is
+                 * less than nLower will set nUpper equal to the number of bits in the
+                 * BitString.
+                 *@param nLower The first bit in the current string, will be the first bit
+                 * (0 index) in the new sub string.
+                 *@param nUpper The last bit in the current string, will be the last bit in
+                 * the new sub string.  nUpper is included in the sub string.
+                 *@returns A new BitString object ready to be used.  Please note that
+                 * managing this new object is up to whomever calls this function.
+                 */
+                class BitString getSubString( long nLower, long nUpper );
+                /**
+                 * Sets the number of bits in the BitString, allocating more memory if
+                 * necesarry, or freeing extra if able.  The default operation of this
+                 * function clears all data in the BitString while resizing it.  If you
+                 * would like to keep as much of the data that you had in your BitString
+                 * as possible, then set bClear to false, and any data that will fit into
+                 * the new BitString length will be retained.  If increasing the number of
+                 * bits, the new bits will come into existance cleared (set to 0).
+                 *@param nLength The number of bits to set the BitString to.
+                 *@param bClear When true, all data is eradicated and zeroed, when set to
+                 * false an effort is made to retain the existing data.
+                 *@returns true on success, false on failure.
+                 */
+                bool setBitLength( long nLength, bool bClear=true );
+                /**
+                 * Randomize the entire BitString, one bit at a time.  This is actually
+                 * the function called by the constructor when the user selects initial
+                 * randomization.  This function uses the system random() function, so
+                 * srandom may be used to effect this process at will.
+                 */
+                void randomize();
+                /**
+                 * Operates exactly like <<.  All data in the BitString is shifted to
+                 * the left by some number of bits, any data pushed off the edge of the
+                 * BitString is lost, and all new data coming in will be zeroed.
+                 * Using a negative value in the shiftLeft function will turn it into the
+                 * shiftRight function.
+                 *@param nAmt The number of bit positions to shift all data.
+                 */
+                void shiftLeft( long nAmt ); // just like <<
+                /**
+                 * Operates exactly like >>.  All data in the BitString is shifted to
+                 * the right by some number of bits, any data pushed off the edge of the
+                 * BitString is lost, and all new data coming in will be zeroed.
+                 * Using a negative value in the shiftRight function will turn it into the
+                 * shiftLeft function.
+                 *@param nAmt The number of bit positions to shift all data.
+                 */
+                void shiftRight( long nAmt ); // just like >>
+                /**
+                 * Searches through the BitString and returns the index of the highest
+                 * order bit position (the highest index) with an on bit (a bit set to 1).
+                 * This is a handy helper function and rather faster than calling getBit()
+                 * over and over again.
+                 *@returns The index of the highest indexed on bit.
+                 */
+                long getHighestOrderBitPos();
+                // Conversion
+                /**
+                 * Convert a block of data (no more than 32 bits) to a primitive long type.
+                 * This is done in a little bit interesting way, so it may not always be
+                 * the fastest way to access the data that you want, although it will
+                 * always ensure that the long that is written makes numerical sense, as
+                 * we write numbers, regaurdless of platform.
+                 *@param nStart The first bit in the BitString to include in the long
+                 *@param nSize THe number of bits to include, if this value is set over
+                 * 32 it will be automatically truncated to, or however many bits there
+                 * are in a long in your system.
+                 *@returns A long converted from your raw BitString data.
+                 */
+                long toLong( long nStart = 0, long nSize = 32 );
+                /**
+                 * Converts the data into a human-readable SString object.  SString is
+                 * used to make transport of the string and management very simple.  Since
+                 * BitStrings will generally be longer than your average strip of ints a
+                 * faculty is included and turned on by default that will insert spacers
+                 * into the output text every 8 places.  For debugging work, this is
+                 * definately reccomended.
+                 *@param bAddSpacers Leave set to true in order to have the output broken
+                 * into logical groupings of 8 bits per block.  Set to off to have a harder
+                 * to read solid block of bits.
+                 *@returns A SString object containing the produced string.
+                 */
+                //std::string toString( bool bAddSpacers = true );
+                // Utility
+                /**
+                 * Converts the given number of bits into the smallest allocatable unit,
+                 * which is bytes in C and on most systems nowadays.  This is the minimum
+                 * number of bytes needed to contain the given number of bits, so there is
+                 * generally some slop if they are not evenly divisible.
+                 *@param nBits The number of bits you wish to use.
+                 *@returns The number of bytes you will need to contain the given number
+                 * of bits.
+                 */
+                //static long bitsToBytes( long nBits );
+                /**
+                 * Writes all data in the BitString, including a small header block
+                 * describing the number of bits in the BitString to the file described
+                 * by the given file descriptor.  The data writen is purely sequential and
+                 * probably not too easy to read by other mechanisms, although the
+                 * readFromFile function should always be able to do it.  This function
+                 * does not open nor close the file pointed to by fh.
+                 *@param fh The file descriptor of the file to write the data to.
+                 *@returns true if the operation completed without error, false otherwise.
+                 */
+                //bool writeToFile( FILE *fh );
+                /**
+                 * Reads data formatted by writeToFile and clears out any data that may
+                 * have been in the BitString.  This function preserves nothing in the
+                 * original BitString that it may be replacing.  This function does not
+                 * open nor close the file pointed to by fh.
+                 *@param fh The file descriptor to try to read the data from.
+                 *@returns true if the operation completed without error, false otherwise.
+                 */
+                //bool readFromFile( FILE *fh );
+                //operators
+                BitString &operator=( const BitString &xSrc );
+                BitString operator~();
+                BitString operator<<( const long nAmt );
+                BitString operator>>( const long nAmt );
+        private:
+                void fixup();
+                unsigned char *caData;
+                long nBits;
+                long nBytes;
+                unsigned char cTopByteMask;
+        };
+};
+#endif

diff --git a/src/bitstring.h b/src/bitstring.h new file mode 100644 index 0000000..8052691 --- /dev/null +++ b/src/bitstring.h
@@ -0,0 +1,251 @@
	1	#ifndef BU_BITSTRING_H
	2	#define BU_BITSTRING_H
	3
	4	namespace Bu
	5	{
	6	/**
	7	* Manages an arbitrarily sized string of bits, and allows basic interaction
	8	* with them. This includes basic non-mathematical bitwise operations such
	9	* as setting and testing bits, shifting the string, inversion and a few
	10	* extras like randomization. On linux systems this takes advantage of long
	11	* longs giving you a maximum size of about 2tb per string.
	12	*
	13	* For more general and mathematical type interaction see BitStringInt.
	14	*
	15	*@author Mike Buland
	16	*/
	17	class BitString
	18	{
	19	public:
	20	/**
	21	* Constructs a blank and basic BitString. This is actually useful since
	22	* you can resize BitStrings at will, and even retain the data that was
	23	* in them.
	24	*/
	25	BitString();
	26
	27	/**
	28	* Constructs a BitString object as a copy of another BitString. This is
	29	* a standard copy constructor and produces an exact duplicate of the
	30	* original BitString object.
	31	*@param xSrc Source BitString to copy data from.
	32	*/
	33	BitString( const BitString &xSrc );
	34
	35	/**
	36	* Constructs a BitString with length nBits and optionally fills it with
	37	* random data. The default setting, to not fill randomly, will produce
	38	* a blank (all zeros) string of the specified size.
	39	*@param nBits The length of the new BitString in bits.
	40	*@param bFillRandomly Wether or not to randomize this BitString.
	41	*/
	42	BitString( long nBits, bool bFillRandomly=false );
	43
	44	/**
	45	* Virtual deconstructor for the BitString. Takes care of cleanup for you.
	46	* What more do you really want to know?
	47	*/
	48	virtual ~BitString();
	49
	50	// basic interaction
	51	/**
	52	* Sets a bit in the BitString. In it's normal mode it will always turn
	53	* the given bit on, to clear a bit set bBitState to false instead of
	54	* true. This operation runs in O(1).
	55	*@param nBit The zero-based index of the bit to modify.
	56	*@param bBitState Set to true to set the bit to 1, set to false to set
	57	* the bit to 0.
	58	*/
	59	void setBit( long nBit, bool bBitState=true );
	60
	61	/**
	62	* Reverses the state of the given bit. This will set the given bit to a
	63	* 1 if it was 0, and to 0 if it was 1. This operation runs in O(1), and
	64	* it should be noted that using this is marginally faster than doing the
	65	* test and flip yourself with getBit and setBit since it uses a bitwise
	66	* not operation and doesn't actually test the bit itself.
	67	*@param nBit The index of the bit to flip.
	68	*/
	69	void flipBit( long nBit );
	70
	71	/**
	72	* Gets the state of the given bit. This follows the standard convention
	73	* used so far, a returned value of true means the bit in question is 1,
	74	* and a value of flase means the bit is 0. All bits out of range of the
	75	* BitString are treated as off, but are "accessable" in that this does not
	76	* produce any kind of error message. This is intentional. This operation
	77	* runs in O(1).
	78	*@param nBit The index of the bit to test.
	79	*@returns True for a 1, false for a 0.
	80	*/
	81	bool getBit( long nBit );
	82
	83	/**
	84	* Inverts the entire BitString, in effect this calls flipBit on every bit
	85	* in the string but is faster since it can operate on whole bytes at a
	86	* time instead of individual bits. This operation runs in O(N).
	87	*/
	88	void invert();
	89
	90	/**
	91	* Returns the number of bits allocated in this BitString. This operation
	92	* runs in O(N) time since this value is cached and not computed.
	93	*@returns The number of bits allocated in this BitString.
	94	*/
	95	long getBitLength();
	96
	97	/**
	98	* Sets the entire BitString to zeros, but it does it very quickly. This
	99	* operation runs in O(N).
	100	*/
	101	void clearString();
	102
	103	/**
	104	* Gets another BitString that is autonomous of the current one (contains
	105	* a copy of the memory, not a pointer) and contains a subset of the data
	106	* in the current BitString. This is an inclusive operation, so grabbing
	107	* bits 0-5 will give you 6 bits. This is based on a very tricky
	108	* bit-shifting algorithm and runs very quickly, in O(N) time.
	109	* Passing in a value of zero for nUpper, or any value for nUpper that is
	110	* less than nLower will set nUpper equal to the number of bits in the
	111	* BitString.
	112	*@param nLower The first bit in the current string, will be the first bit
	113	* (0 index) in the new sub string.
	114	*@param nUpper The last bit in the current string, will be the last bit in
	115	* the new sub string. nUpper is included in the sub string.
	116	*@returns A new BitString object ready to be used. Please note that
	117	* managing this new object is up to whomever calls this function.
	118	*/
	119	class BitString getSubString( long nLower, long nUpper );
	120
	121	/**
	122	* Sets the number of bits in the BitString, allocating more memory if
	123	* necesarry, or freeing extra if able. The default operation of this
	124	* function clears all data in the BitString while resizing it. If you
	125	* would like to keep as much of the data that you had in your BitString
	126	* as possible, then set bClear to false, and any data that will fit into
	127	* the new BitString length will be retained. If increasing the number of
	128	* bits, the new bits will come into existance cleared (set to 0).
	129	*@param nLength The number of bits to set the BitString to.
	130	*@param bClear When true, all data is eradicated and zeroed, when set to
	131	* false an effort is made to retain the existing data.
	132	*@returns true on success, false on failure.
	133	*/
	134	bool setBitLength( long nLength, bool bClear=true );
	135
	136	/**
	137	* Randomize the entire BitString, one bit at a time. This is actually
	138	* the function called by the constructor when the user selects initial
	139	* randomization. This function uses the system random() function, so
	140	* srandom may be used to effect this process at will.
	141	*/
	142	void randomize();
	143
	144	/**
	145	* Operates exactly like <<. All data in the BitString is shifted to
	146	* the left by some number of bits, any data pushed off the edge of the
	147	* BitString is lost, and all new data coming in will be zeroed.
	148	* Using a negative value in the shiftLeft function will turn it into the
	149	* shiftRight function.
	150	*@param nAmt The number of bit positions to shift all data.
	151	*/
	152	void shiftLeft( long nAmt ); // just like <<
	153
	154	/**
	155	* Operates exactly like >>. All data in the BitString is shifted to
	156	* the right by some number of bits, any data pushed off the edge of the
	157	* BitString is lost, and all new data coming in will be zeroed.
	158	* Using a negative value in the shiftRight function will turn it into the
	159	* shiftLeft function.
	160	*@param nAmt The number of bit positions to shift all data.
	161	*/
	162	void shiftRight( long nAmt ); // just like >>
	163
	164	/**
	165	* Searches through the BitString and returns the index of the highest
	166	* order bit position (the highest index) with an on bit (a bit set to 1).
	167	* This is a handy helper function and rather faster than calling getBit()
	168	* over and over again.
	169	*@returns The index of the highest indexed on bit.
	170	*/
	171	long getHighestOrderBitPos();
	172
	173	// Conversion
	174	/**
	175	* Convert a block of data (no more than 32 bits) to a primitive long type.
	176	* This is done in a little bit interesting way, so it may not always be
	177	* the fastest way to access the data that you want, although it will
	178	* always ensure that the long that is written makes numerical sense, as
	179	* we write numbers, regaurdless of platform.
	180	*@param nStart The first bit in the BitString to include in the long
	181	*@param nSize THe number of bits to include, if this value is set over
	182	* 32 it will be automatically truncated to, or however many bits there
	183	* are in a long in your system.
	184	*@returns A long converted from your raw BitString data.
	185	*/
	186	long toLong( long nStart = 0, long nSize = 32 );
	187
	188	/**
	189	* Converts the data into a human-readable SString object. SString is
	190	* used to make transport of the string and management very simple. Since
	191	* BitStrings will generally be longer than your average strip of ints a
	192	* faculty is included and turned on by default that will insert spacers
	193	* into the output text every 8 places. For debugging work, this is
	194	* definately reccomended.
	195	*@param bAddSpacers Leave set to true in order to have the output broken
	196	* into logical groupings of 8 bits per block. Set to off to have a harder
	197	* to read solid block of bits.
	198	*@returns A SString object containing the produced string.
	199	*/
	200	//std::string toString( bool bAddSpacers = true );
	201
	202	// Utility
	203	/**
	204	* Converts the given number of bits into the smallest allocatable unit,
	205	* which is bytes in C and on most systems nowadays. This is the minimum
	206	* number of bytes needed to contain the given number of bits, so there is
	207	* generally some slop if they are not evenly divisible.
	208	*@param nBits The number of bits you wish to use.
	209	*@returns The number of bytes you will need to contain the given number
	210	* of bits.
	211	*/
	212	//static long bitsToBytes( long nBits );
	213
	214	/**
	215	* Writes all data in the BitString, including a small header block
	216	* describing the number of bits in the BitString to the file described
	217	* by the given file descriptor. The data writen is purely sequential and
	218	* probably not too easy to read by other mechanisms, although the
	219	* readFromFile function should always be able to do it. This function
	220	* does not open nor close the file pointed to by fh.
	221	*@param fh The file descriptor of the file to write the data to.
	222	*@returns true if the operation completed without error, false otherwise.
	223	*/
	224	//bool writeToFile( FILE *fh );
	225
	226	/**
	227	* Reads data formatted by writeToFile and clears out any data that may
	228	* have been in the BitString. This function preserves nothing in the
	229	* original BitString that it may be replacing. This function does not
	230	* open nor close the file pointed to by fh.
	231	*@param fh The file descriptor to try to read the data from.
	232	*@returns true if the operation completed without error, false otherwise.
	233	*/
	234	//bool readFromFile( FILE *fh );
	235
	236	//operators
	237	BitString &operator=( const BitString &xSrc );
	238	BitString operator~();
	239	BitString operator<<( const long nAmt );
	240	BitString operator>>( const long nAmt );
	241
	242	private:
	243	void fixup();
	244	unsigned char *caData;
	245	long nBits;
	246	long nBytes;
	247	unsigned char cTopByteMask;
	248	};
	249	};
	250
	251	#endif