#	This is a shell archive.
#	Remove everything above and including the cut line.
#	Then run the rest of the file through sh.
#----cut here-----cut here-----cut here-----cut here----#
#!/bin/sh
# shar:	Shell Archiver
#	Run the following text with /bin/sh to create:
#	Makefile
#	README
#	bytecnt.c
#	l_bitcnt.c
#	nibcnt.c
#	s_bitcnt.c
# This archive created: Thu Jul 13 14:14:12 1989
sed 's/^X//' << \SHAR_EOF > Makefile
X# Makefile for VxWorks bitcnt submission - R. Neitzel 13 July 1989
X
XCC = cc
X
X# Change this for your compiler
XCFLAGS = -c -O4
X
Xall: byte_cnt nib_cnt l_bitcnt s_bitcnt
X	echo "Done"
X
Xbyte_cnt: bytecnt.c
X	$(CC) $(CFLAGS) bytecnt.c
X
Xnib_cnt: nibcnt.c
X	$(CC) $(CFLAGS) nibcnt.c
X
Xl_bitcnt: l_bitcnt.c
X	$(CC) $(CFLAGS) l_bitcnt.c
X
Xs_bitcnt: s_bitcnt.c
X	$(CC) $(CFLAGS) s_bitcnt.c
X
SHAR_EOF
sed 's/^X//' << \SHAR_EOF > README
XThis is a set of three bit counting routines. They all perform the
Xsame function - counting the number of set bits in an integer
X(assuming 32 bit integers). Two of them are closely related: byte_cnt
Xuses the value of each byte of the integer as an index into a 256 byte
Xlookup table, while nib_cnt does the same for nibbles and an 8 byte
Xlut. l_bitcnt uses a form of "parallel" addition, adding bit pairs
Xuntil it gets the result. Why three selections - well nib_cnt is
Xreally just for fun, since it definitely slower. l_bitcnt runs about
Xthe same speed as byte_cnt, but uses less space.
X
XAll 3 were timed on a MVME-133 at 25MHz. They were compiled with the
XSun cc compiler using -O4. Two tests where run - a straight timexN and
Xa 'real' test that looped from 0 to 10000. The results are:
X
X		timexN		Loop		Code size
X		------		----		---------
X
Xbyte_cnt  	11 us		116 ms		354 bytes
Xnib_cnt		21 us		166 ms		188 bytes
Xl_bitcnt	13 us		116 ms		114 bytes
X
XNote that code size includes the LUTs. Also note that in real use
Xbyte_cnt and l_bitcnt are in a dead heat.
X
XI have also include s_bitcnt, which does the same as l_bitcnt for
Xshorts.
X
XTo build any of these type 'make NAME', where NAME is one of byte_cnt,
Xnib_cnt, l_bitcnt, s_bitcnt or all (to get all of course :-))
X  SHAR_EOF
sed 's/^X//' << \SHAR_EOF > bytecnt.c
X/*
X  Module: bytecnt.c
X  Author: Richard E. K. Neitzel
X
Xrevision history
X----------------
X1.0,9jan89,rekn            written
X
X
X  Explanation:
X      This routine takes an integer and returns the number of bits it contains
X      which are set. It does this via a byte sized (haha) lookup table.
X      WARNING! This assumes that integers are 32 bits! 
X
X*/
X
Xstatic unsigned char bit_tbl[] = {
X0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,
X4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,
X4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,
X5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,
X4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,
X4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,
X5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
X};
X
X
Xint byte_cnt(item)
Xunsigned int item;
X{
X    register unsigned char *ptr; /* Byte pointer */
X    register int sum = 0;	/* Return value */
X
X    if (item == sum)		/* Why do it */
X      return(sum);
X
X    ptr = &item;		/* Ready! */
X
X/* Now look at each byte, using it's value as index into lut. */
X    sum += bit_tbl[*ptr++];
X    sum += bit_tbl[*ptr++];
X    sum += bit_tbl[*ptr++];
X    sum += bit_tbl[*ptr];
X
X    return(sum);
X}
SHAR_EOF
sed 's/^X//' << \SHAR_EOF > l_bitcnt.c
X/*
X  Module: l_bitcnt.c
X  Author: Richard E. K. Neitzel
X
Xrevision history
X----------------
X1.0,9jan89,rekn            written
X
X
X  Explanation:
X      This routine takes an integer and returns the number of bits it contains
X      which are set. It does this via 'parallel' addition, turning the integer
X      into sets of bit pairs of increasing size. WARNING! This assumes that
X      integers are 32 bits! 
X*/
X
Xint l_bitcnt(word)
Xint word;
X{
X    register int j, k;		/* Our work area */
X
X    if (!word)			/* Why bother? */
X      return(0);
X
X    j = word;
X
X    k = j & 0x55555555;		/* Clear every other bit */
X    j >>= 1;			/* Do again for cleared bits */
X    j &= 0x55555555;
X    j += k;			/* 1st pairs done */
X
X    k = j & 0x33333333;		/* Clear every two bits */
X    j >>= 2;
X    j &= 0x33333333;
X    j += k;			/* 2nd pairs done */
X
X    k = j & 0xffff;		/* Only need last 4 sets */
X    j &= 0xffff0000;		/* and top 4 here */
X    j = j >> 16;		/* ready - */
X    j += k;			/* add 3rd pairs */
X
X    k = j & 0xf0f;		/* Clear bits */
X    j >>= 4;			/* Repeat */
X    j &= 0xf0f;
X    j += k;			/* add 4th pairs */
X
X    k = j & 0xff;		/* Now add the 8 bit pairs */
X    j >>= 8;
X    j += k;
X
X    return(j);			/* bye */
X}
SHAR_EOF
sed 's/^X//' << \SHAR_EOF > nibcnt.c
X/*
X  Module: nibcnt.c
X  Author: Richard E. K. Neitzel
X
Xrevision history
X----------------
X1.0,9jan89,rekn            written
X
X
X  Explanation:
X      This routine takes an integer and returns the number of bits it contains
X      which are set. It does this via a nibble sized lookup table.
X      WARNING! This assumes that integers are 32 bits! 
X
X*/
X
Xstatic unsigned char bit_tbl[] = {
X0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4
X};
X
Xint nib_cnt(item)
Xunsigned int item;
X{
X    register int sum = 0;	/* Bit count */
X    register char *ptr;		/* Byte pointer */
X
X    if (item == sum)		/* Why? */
X      return(sum);
X
X    ptr = &item;		/* Ready! */
X
X/* Now look at each nibble in turn, using it as an index into lut */
X    sum += bit_tbl[(*ptr >> 4)];
X    sum += bit_tbl[(*ptr++ & 0xf)];
X    sum += bit_tbl[(*ptr >> 4)];
X    sum += bit_tbl[(*ptr++ & 0xf)];
X    sum += bit_tbl[(*ptr >> 4)];
X    sum += bit_tbl[(*ptr++ & 0xf)];
X    sum += bit_tbl[(*ptr >> 4)];
X    sum += bit_tbl[(*ptr++ & 0xf)];
X
X    return(sum);
X}
SHAR_EOF
sed 's/^X//' << \SHAR_EOF > s_bitcnt.c
X/*
X  Module: s_bitcnt.c
X  Author: Richard E. K. Neitzel
X
Xrevision history
X----------------
X1.0,9jan89,rekn            written
X
X
X  Explanation:
X      This routine takes an integer and returns the number of bits it contains
X      which are set. It does this via 'parallel' addition, turning the integer
X      into sets of bit pairs of increasing size. WARNING! This assumes that
X      shorts are 16 bits!
X*/
X
Xint s_bitcnt(word)
Xshort word;
X{
X    register short i, j, k;	/* our work area */
X
X    if (!word)			/* Why bother? */
X      return(0);
X
X    j = word;
X
X    k = j & 0x5555;		/* Clear every other bit */
X    j >>= 1;			/* Repeat for other bits */
X    j &= 0x5555;		
X    j += k;			/* 1st pairs */
X
X    k = j & 0x3333;		/* Clear every two bits */
X    j >>= 2;			/* shift and repeat */
X    j &= 0x3333;
X    j += k;			/* 2nd pairs */
X
X    k = j & 0xff;		/* Get lower pairs */
X    j &= 0xff00;		/* Get upper pairs */
X    j >>= 8;
X    j += k;			/* 3rd pairs */
X
X    k = j & 0xf;		/* Get last pairs */
X    j >>= 4;
X    j += k;
X
X    return(j);			/* bye */
X}
X
SHAR_EOF
#	End of shell archive
exit 0