/* BITOPS.C - Various bit-manipulation procedures.
 *
 *	Audit Trail
 *
 *	09/11/87 - v001 - GSK - Original
 */

#include "ctype.h"

#define FULLBYT 0xff
#define TBUFSIZ 100
#define SUCCESS	0
#define FAILURE	-1
#define NULL (char *)0

typedef unsigned BOOL;

/* *************************** GENERAL NOTES *****************************
 *
 *	Most of these routines deal with "bit fields" of arbitrary
 *	length. In general, you pass them a (char) pointer to a block of memory,
 * 	which will be interpreted and manipulated as a stream of bits, regardless
 *	of byte or word boundaries after the original pointer. Several of these 
 *	routines take a bit offset argument, which is an ABSOLUTE number of bits
 *	(zero-relative) from the base pointer; in other words, a bit offset of
 *	75 points to the 76th bit in the block, starting from the base pointer.
 *
 ****************************************************************************/


/* GETBIT - Get the value of the bit (0, 1) at passed ptr, offset by bitoffs
 *			bits. The offset may be any positive number; if >8, the byte 
 *			pointer will be incremented accordingly.
 */

short getbit(ptr, bitoffs)

char *ptr;		/* Base pointer */
short bitoffs;	/* Offset from ptr in number of bits */

{

	if (ptr == NULL || bitoffs < 0)
	    return (FAILURE);

	ptr += (bitoffs / 8);	/* Knock up ptr to byte requested */
	bitoffs %= 8;		/* Get bit relative to its own byte */

	return (short)((*ptr >> (7 - bitoffs)) & 1);
}


/* SETBIT - Set a specified bit number in a char string to 1 or 0. The bit
 *			number may be any positive value; if > 8, the byte pointer will
 *			be incremented accordingly.
 */

short setbit(ptr, bitnum, val)

char *ptr;		/* Base of string */
short bitnum;	/* Bit number, 0 relative */
short val;		/* Value to set, 1 or 0 */

{
	short byteoffs;		/* Byte offset in string */
	char mask;		/* Masking value */


	if (ptr == NULL || bitnum < 0 || (val != 0 && val != 1))
	    return (FAILURE);

	ptr += (byteoffs = bitnum / 8);	/* Calc offset, reset ptr */

	if (byteoffs)
	    bitnum %= (byteoffs * 8);	/* Find bit within byte */

/* Mask = bit string of zeroes with one in bitnum position */

 	mask = 1 << (7 - bitnum);

	if (val)			/* If turn-on bit, OR with mask */
	    *ptr |= mask;
	else				/* Else, AND with inverse (ones-complement) of mask */
	    *ptr &= ~mask;

	return (SUCCESS);
}


/* COUNTBIT - Count the bits of specified value (0 or 1) in a bit field. The
 *				field may be any number of bytes in length. If val==0, then
 *				"off" bits will be counted; otherwise, "on" bits.
 */

short countbit(basep, nbytes, val)

char *basep;	/* Starting byte to begin count */
short nbytes;	/* Number of bytes to count thru */
short val;		/* Bit value to count, 0 or 1 */

{
	short count;	/* Number of bits counted */
	short bit;	/* Bit loop counter */
	char *ptr;	/* Loop pointer */


	if (basep == NULL || nbytes <= 0 || (val != 0 && val != 1))
	    return (FAILURE);

	count = 0;

	for (ptr = basep; ptr < basep + nbytes; ptr++)
		{
	    for (bit = 0; bit < 8; bit++)
		count += (getbit(ptr, bit) == val);
		}

	return (count);
}


/* BITPATRN -  Generate an array of chars or ints corresponding to the bit
 *				pattern of the passed char. If patyp == 'C', an array of
 *				character '0's and '1's will be generated; if 'I', an array
 *				numeric 0/1's.
 *
 *			NOTE that you pass a single CHAR, not a char *. Thus if you
 *				need a pattern array more than 8 elements long, call
 *				bitpatrn() in a loop and concatenate the results.
 */

short bitpatrn(chr, patp, patyp)

char chr;	/* Char to generate pattern from */
char *patp;	/* Ptr to array of chars or ints, depending on patyp */
char patyp;	/* Pattern type: Char or Int (NOT case sensitive) */

{
	short ptrinc;	/* Pointer increment per bit */
	short bit;		/* Bit counter */
	short bitval;	/* Bit value, 1 or 0 */


	patyp = toupper(patyp);

	if (patp == NULL || (patyp != 'C' && patyp != 'I'))
	    return (FAILURE);

	ptrinc = 1 + (patyp == 'I');

	for (bit = 0; bit < 8; bit++, patp += ptrinc)
		{
	    bitval = getbit(&chr, bit);

	    if (patyp == 'I')	/* Int array: Set low bytes of each pair */
			{
			*patp = bitval;
			*(patp + 1) = 0;
	    	}
	    else
			*patp = '0' + bitval;
		}
	return (SUCCESS);
}


/* BYTE2BIT -  Translate the byte passed to a bit pattern, placed at char
 *				*ptr, offset by bitoffs bits from left. Do not write onto next
 *				byte from ptr if lastbyt set. This allows a bit pattern to be
 *				copied to another place in memory regardless of byte
 *				boundaries. For example, if bitoffs == 3, then the left 5 bits
 *				of the passed byte will be copied to the right 5 bits of the
 *				destination ptr, and the right 3 bits of the byte onto the
 *				left 3 bits of the following location (unless lastbyt == YES),
 *				in which case only the FIRST dest char will be written on).
 *				Issuing a call with a ZERO bit offset, like:
 *
 *					byte2bit('A', dest, 0, anything);
 *
 *				is equivalent to: *dest = 'A';
 */

short byte2bit(byte, ptr, bitoffs, lastbyt)

char byte;		/* Character to translate */
char *ptr;		/* DESTINATION Ptr: Points to starting byte to write to */
short bitoffs;	/* Offset of starting bit from DESTINATION ptr, 0-7 */
BOOL lastbyt;	/* Flag: Do not write bits to next char if set */

{
	short bit;	/* Bit counter */


	if (ptr == NULL || bitoffs < 0 || bitoffs > 7)
	    return (FAILURE);

/* Write left side of passed byte to right side of 1st destination char, 
   leaving left side of dest char unchanged */

	for (bit = bitoffs; bit <= 7; bit++)
	    setbit(ptr, bit, getbit(&byte, bit - bitoffs));

/* Write right side of byte to left side of next destination char, 
   leaving right side unchanged */

	if (bitoffs && !lastbyt)
	    for (bit = 0; bit < bitoffs; bit++)
			setbit(ptr + 1, bit, getbit(&byte, bit + 8 - bitoffs));

	return (SUCCESS);
}


/* BIT2BYTE.C - Take next 8 bits from starting char *, offset by specified
 *				number of bits (bitoffs), translate to a byte and return
 *				value as a char. Starting point need not conform to a byte
 *				boundary. For example, if bitoffs = 3, then translation will
 *				begin with the 4th bit (offsets are 0-relative) of the passed
 *				ptr; if lastbyt == YES, then only the remaining 5 bits will
 *				be translated (offsets 3 thru 7); otherwise, a full 8 bits
 *				will be translated, the remaining 3 coming from the left 3
 *				bits of the byte following ptr. Issuing a call with a ZERO
 *				bit offset like:
 *
 *					mychar = bit2byte(there, 0, anything);
 *
 *				is equivalent to: mychar = *there;
 */

char bit2byte(ptr, bitoffs, lastbyt)

char *ptr;		/* Ptr to starting byte to take from */
short bitoffs;	/* Offset of starting bit from ptr, 0-7 */
BOOL lastbyt;	/* Flag: Do not take bits from next char if set */

{
	char byte;


	if (ptr == NULL || bitoffs < 0 || bitoffs > 7)
	    return (0);

	byte = *ptr << bitoffs;		/* Set left side of byte */

	if (bitoffs && !lastbyt)	/* Set right side from next byte */

	    byte |= (*(++ptr) >> (8 - bitoffs));

	return (byte);
}


/* INSBITS - Insert specified number of bits to bit field beginning at basep,
 *				starting insertion bitoffs bits from the base. Inserted bits
 *				will be all of the same	value (0 or 1). Bits above the
 *				insertion point will be pushed up in memory, up the limit of
 *				total field size fldsize (arbitrary size limit defined by
 *				TBUFSIZ).
 *
 *			NOTE: If you need a routine to insert a specific bit pattern
 *				(not just all 0's or 1's), use this as a template. You only
 *				need to change the "fill middle bytes" section.
 */

short insbits(basep, bitoffs, nbits, val, fldsize)

char *basep;	/* Ptr to base of bit field */
short bitoffs;	/* Number of bits offset from left to begin insert */
short nbits;	/* Number of bits to insert */
short val;		/* Value to insert, 1 or 0 */
short fldsize;	/* Total size of bit field in bytes */

{
	char buffer[TBUFSIZ];		/* Temporary copy buffer */
	char *firstbyt, *lastbyt;	/* Bytes where insert begins/ends */
	short firstoffs, lastoffs;	/* Bit offsets in first, last bytes */
	short n;					/* Field index counter */
	short lastbit;				/* Offset of last bit in field */
	char *ptr;					/* Temporary ptr */


	if (basep == NULL || nbits <= 0 || fldsize <= 0 || fldsize > TBUFSIZ)
	    return (FAILURE);

	firstbyt = basep + bitoffs / 8;
	lastbit = bitoffs + nbits - 1;
	lastbyt = basep + lastbit / 8;
	firstoffs = bitoffs % 8;
	lastoffs = lastbit % 8;

	if (firstbyt >= basep + fldsize)
	    return (FAILURE);

	setmem(buffer, sizeof(buffer), 0);	/* Init copy buffer */

/* Copy from firstbyt thru end of field to buffer */

	for (ptr = firstbyt, n = 0; ptr < basep + fldsize; ptr++, n++)
	    buffer[n] = bit2byte(ptr, firstoffs, ptr == basep + fldsize - 1);

/* Set the starting byte, leaving left part as is */

	if (val)
	    *firstbyt |= FULLBYT >> firstoffs;
	else
	    *firstbyt &= FULLBYT << (8 - firstoffs);

/* Fill middle bytes; do not overwrite end of field */

	for (ptr = firstbyt + 1; ptr < lastbyt; ptr++)
		{
	    if (ptr >= basep + fldsize)
			break;

		*ptr = (val) ? FULLBYT : 0;
		}

/* Set ending byte, leaving right part as is */

	if (lastbyt < basep + fldsize && lastbyt != firstbyt)
		{
	    if (val)
	    	*lastbyt |= FULLBYT << (7 - lastoffs);
	    else
	    	*lastbyt &= FULLBYT >> (lastoffs + 1);
		}

/* Write buffer from last byte to end of field */

	for (ptr = lastbyt, n = 0; ptr < basep + fldsize; ptr++, n++)
	    byte2bit(buffer[n], ptr, lastoffs + 1, ptr == basep + fldsize - 1);

	return (SUCCESS);
}


/* DELBITS.C - Delete specified number of bits from bit field beginning at
 *				basep offset by bitoffs bits. The bit field may be any number
 *				of bytes in length, and the deleted section may be any number
 *				of bits in length and need not conform to byte boundaries. The
 *				bits above the deleted section are moved down to fill the
 *				gap, and the top of the field filled with the specified value.
 *
 *		NOTE: Bit field size fldsize is arbitrarily limited to TBUFSIZ as
 *				defined below.
 */

short delbits(basep, bitoffs, nbits, val, fldsize)

char *basep;	/* Ptr to base of bit field */
short bitoffs;	/* Number of bits offset from left to begin delete */
short nbits;	/* Number of bits to delete */
short val;		/* Value to fill vacated right side of field, 1 or 0 */
short fldsize;	/* Total size of bit field in BYTES */

{
	char buffer[TBUFSIZ];		/* Temporary copy buffer */
	char *firstbyt, *lastbyt;	/* Bytes where delete begins/ends */
	short firstoffs, lastoffs;	/* Bit offsets in first, last bytes */
	short n;					/* Field index counter */
	short lastbit;				/* Offset of last bit in field */
	char *ptr;					/* Temporary ptr */


	if (basep == NULL || nbits <= 0 || fldsize <= 0 || fldsize > TBUFSIZ)
	    return (FAILURE);

	firstbyt = basep + bitoffs / 8;
	lastbit = bitoffs + nbits - 1;
	lastbyt = basep + lastbit / 8;
	firstoffs = bitoffs % 8;
	lastoffs = lastbit % 8;

	if (firstbyt >= basep + fldsize)
	    return (FAILURE);

	if (val)
	    setmem(buffer, sizeof(buffer), FULLBYT);	/* Init copy buffer */
	else
	    setmem(buffer, sizeof(buffer), 0);

/* Copy to buffer: From bit after end of deleted section to end of field */

	if (++lastoffs > 7)
		{
	    lastbyt++;
	    lastoffs = 0;
		}

	for (ptr = lastbyt, n = 0; ptr < basep + fldsize; ptr++, n++)
	    buffer[n] = bit2byte(ptr, lastoffs, ptr == basep + fldsize - 1);

/* Write buffer to deleted part thru end of field; end is filled with val */

	for (ptr = firstbyt, n = 0; ptr < basep + fldsize; ptr++, n++)
	    byte2bit(buffer[n], ptr, firstoffs, ptr == basep + fldsize - 1);

	return (SUCCESS);
}


/* BITZVALU - Evaluate the next nbits bits from the starting char * and bit
 *				offset and return the value. Uses a simple counting algorithm,
 *				starting with the rightmost bit in the designated field and
 *				moving left, adding a successive power of 2 for each "on" bit.
 *
 *			EXAMPLES: Given a pointer to the array of hex values: 1E A4 7C
 *
 *						bitzvalu(ptr, 8, 8)		returns 164 (00A4)
 *						bitzvalu(ptr, 3, 4)		returns  15 (000F)
 *						bitzvalu(ptr, 10, 10)	returns 583 (0247)
 *
 *		NOTE: Returns an unsigned value. The number of bits evaluated may not
 *			  be more than 16. If bad parameters are passed, returns 0.
 */

unsigned bitzvalu(ptr, bitoffs, nbits)

char *ptr;		/* Ptr to starting byte to take from */
short bitoffs;	/* Offset of starting bit from ptr */
short nbits;	/* Number of bits to evaluate */
{
	unsigned num = 0;	/* Initialize all bits to 0 */
	int bit;
	unsigned mult = 1;

	if (ptr == NULL || nbits < 1 || nbits > 16)
		return (0);

	for (bit = nbits - 1; bit >= 0; bit--, mult *= 2)
		num += (getbit(ptr, bitoffs + bit) * mult);

	return (num);
}


/* CONTRIBUTED BY: Gordon Kramer, Liberty Tree Software, Belchertown, MA */