+
+#if GCC_VERSION < 3400
+/* Table of number of set bits in a character, indexed by value of char. */
+static unsigned char popcount_table[] =
+{
+ 0,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,4,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,4,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,5,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,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,5,5,6,4,5,5,6,5,6,6,7,
+ 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,
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
+};
+
+/* Count the bits in an SBITMAP element A. */
+
+static unsigned long
+sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
+{
+ unsigned long ret = 0;
+ unsigned i;
+
+ if (a == 0)
+ return 0;
+
+ /* Just do this the table way for now */
+ for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
+ ret += popcount_table[(a >> i) & 0xff];
+ return ret;
+}
+#endif
+
+/* Count the number of bits in SBITMAP a, up to bit MAXBIT. */
+
+unsigned long
+sbitmap_popcount (sbitmap a, unsigned long maxbit)
+{
+ unsigned long count = 0;
+ unsigned ix;
+ unsigned int lastword;
+
+ if (maxbit == 0)
+ return 0;
+
+ if (maxbit >= a->n_bits)
+ maxbit = a->n_bits;
+
+ /* Count the bits in the full word. */
+ lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
+ for (ix = 0; ix < lastword; ix++)
+ {
+ if (a->popcount)
+ {
+ count += a->popcount[ix];
+#ifdef BITMAP_DEBUGGING
+ gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
+#endif
+ }
+ else
+ count += do_popcount (a->elms[ix]);
+ }
+
+ /* Count the remaining bits. */
+ if (lastword < a->size)
+ {
+ unsigned int bitindex;
+ SBITMAP_ELT_TYPE theword = a->elms[lastword];
+
+ bitindex = maxbit % SBITMAP_ELT_BITS;
+ if (bitindex != 0)
+ {
+ theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
+ count += do_popcount (theword);
+ }
+ }
+ return count;
+}
+