libchill/cardps.c

   1 /* Implement POWERSET runtime actions for CHILL.
   2    Copyright (C) 1992,1993 Free Software Foundation, Inc.
   3    Author: Wilfried Moser, et al
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21 #define __CHILL_LIB__
  22
  23 #include <stdio.h>
  24 #include "powerset.h"
  25
  26
  27 /*
  28  * function __cardpowerset
  29  *
  30  * parameters:
  31  *      ps              powerset
  32  *      bitlength       length of powerset
  33  *
  34  * returns:
  35  *      long            number of set bits
  36  *
  37  * exceptions:
  38  *  none
  39  *
  40  * abstract:
  41  *  returns the number of set bit's in a powerset
  42  *
  43  */
  44
  45 /* bit_count[I] is number of '1' bits in I. */
  46 static
  47 const unsigned char __four_bit_count[16] = {
  48     0, 1, 1, 2,
  49     1, 2, 2, 3,
  50     1, 2, 2, 3,
  51     2, 3, 3, 4 };
  52
  53 long
  54 __cardpowerset (ps, bitlength)
  55      SET_WORD      *ps;
  56      unsigned long  bitlength;
  57 {
  58   unsigned long count = 0;
  59   if (bitlength <= SET_CHAR_SIZE)
  60     {
  61       register SET_CHAR c = *((SET_CHAR *)ps);
  62       /* count 4 bits at a time. */
  63       while (c > 0)
  64         {
  65           count += __four_bit_count[c & 15];
  66           c >>= 4;
  67         }
  68       return count;
  69     }
  70   else if (bitlength <= SET_SHORT_SIZE)
  71     {
  72       register SET_SHORT c = *((SET_SHORT *)ps);
  73       /* count 4 bits at a time. */
  74       while (c > 0)
  75         {
  76           count += __four_bit_count[c & 15];
  77           c >>= 4;
  78         }
  79       return count;
  80     }
  81   else
  82     {
  83       register SET_WORD *p = ps;
  84       SET_WORD *endp = p + BITS_TO_WORDS(bitlength);
  85
  86       while (p < endp)
  87         {
  88           register SET_WORD c = *p++;
  89           /* count 4 bits at a time. */
  90           while (c > 0)
  91             {
  92               count += __four_bit_count[c & 15];
  93               c >>= 4;
  94             }
  95         }
  96       return (count);
  97     }
  98 }