Set constants
Per Bothner
bothner@cygnus.com
Wed Mar 31 23:46:00 GMT 1999
It has been a while since I looked at this, but here is some notes.
> when storing constants of type "set" in Pascal or Chill, the GNU
> compiler uses a string of bytes. In Pascal, however, we currently
> handle sets as strings of ints. This causes problems on big-endian
> machines (for obvious reasons).
Actually, I thought it might make sense to store bitstrings in
machine order. I.e. on a little-endian machine, bit 0 would be
the low-order bit of the first byte/word, while on a big-endian
machine bit 0 would be the high-order bit of byte/word. In that
case it wouldn't matter if you used byte or word accesses, as
long as the access unit divies the length in bytes. (The disadvantage
is that the run-time library needs to know the bit order, which
can be a problem.)
But, yes, I agree the "unit" should be a "word" of an int or
a long. If you look in libchill/powerset.h, you will see that
a SET_WORD can be either an unsigned char or an unsigned int.
The original code used char, but I started generalizing it.
The goal was to re-write it so that SET_WORD could be a larger
unit, but I never got around to doing that. So to:
> Is there any special reason why the GNU
> compiler stores sets as bytes?
there is no fundamental reason, only that the initial
implementation used that. (Also, they wanted to be layout-compatible
with an older implementation.)
> If not, I would suggest to change get_set_constructor_bytes() in tree.c
> and related functions to generate ints instead of bytes.
Do so, with my blessing - but note that there is also a Chill runtime
that needs to be changed. You also have to watch out for debugging.
I actually started writing a more generic low-level bitstring library.
The intent was this would be used for libg++, for Chill, possibly Pascal
and other languages/libraries. This was included in libg++, but
I never finished it, or tried seriously to use it for Chill.
It has been in libg++ since 1994:
Sun May 22 17:13:24 1994 Per Bothner (bothner@kalessin.cygnus.com)
* bitand.c, bitany.c, bitblt.c, bitclear.c, bitcopy.c, bitcount.c,
bitdo1.h, bitdo2.h, bitinvert.c, bitlcomp.c, bitprims.h, bitset1.c,
bitxor.c: Preliminary version of language-independent (sub-)library
for general low-level manipulation of bistrings.
* BitString.h, BitString.cc, Makefile.in: Partially re-written
BitString class using the new library.
I put some effort into, for example handle general 2-operand bit-operations,
handling overlapping strings as well as non-aligned strings.
It would be great if someone could take this over.
Here is the header file bitprims.h:
#ifndef _BS_PRIMS
#define _BS_PRIMS
/* A bitstring is an array of _BS_word. */
typedef unsigned long _BS_word;
#define _BS_CHAR_BIT 8
#define _BS_BITS_PER_WORD (_BS_CHAR_BIT*sizeof(_BS_word))
#define _BS_WORDS_NEEDED(NBITS) ((NBITS+_BS_BITS_PER_WORD-1)/_BS_BITS_PER_WORD)
/* For now, we number the bits in a _BS_word in little-endian order.
Later, might use machine order. */
#ifdef CHILL_LIB
#ifndef BITS_BIG_ENDIAN
#include "config.h"
#endif
#define _BS_BIGENDIAN BITS_BIG_ENDIAN
#else
#define _BS_BIGENDIAN 0
#endif
/* By "left" we mean where bit number 0 is.
Hence, so left shift is << if we're numbering the bits in big-endian oder,
and >> if we're numbering the bits in little-endian order.
Currently, we always use little-endian order.
Later, we might use machine-endian order. */
#if _BS_BIGENDIAN
#define _BS_LEFT <<
#define _BS_RIGHT >>
#else
#define _BS_LEFT >>
#define _BS_RIGHT <<
#endif
#if _BS_BIGENDIAN
#define _BS_BITMASK(BITNO) ((_BS_word)1 << (_BS_BITS_PER_WORD - 1 - (BITNO)))
#else
#define _BS_BITMASK(BITNO) ((_BS_word)1 << (BITNO))
#endif
/* Given a PTR which may not be aligned on a _BS_word boundary,
set NEW_PTR to point to (the beginning of) the corresponding _BS_word.
Adjust the bit-offset OFFSET to compensate for the difference. */
#define _BS_ADJUST_ALIGNED(NEW_PTR, PTR, OFFSET) \
( (NEW_PTR) = (_BS_word*)(((char*)(PTR)-(char*)0) & ~(sizeof(_BS_word)-1)), \
(OFFSET) += (char*)(PTR) - (char*)(NEW_PTR) )
/* Given a bit pointer (PTR, OFFSET) normalize it so that
OFFSET < _BS_BITS_PER_WORD. */
#define _BS_NORMALIZE(PTR, OFFSET) \
{ _BS_size_t __tmp_ind = _BS_INDEX (OFFSET); \
(PTR) += __tmp_ind; \
(OFFSET) -= __tmp_ind * _BS_BITS_PER_WORD; }
#define _BS_INDEX(I) ((unsigned)(I) / _BS_BITS_PER_WORD)
#define _BS_POS(I) ((I) & (_BS_BITS_PER_WORD -1 ))
#ifndef _BS_size_t
#if __GNUC__ > 1
#define _BS_size_t __SIZE_TYPE__
#else
#define _BS_size_t unsigned long
#endif
#endif
#ifndef __P
#ifdef __STDC__
#define __P(protos) protos
#else
#define __P(protos) ()
#endif
#endif /*!__P*/
#if !defined(__STDC__) && !defined(const)
#define const
#endif
#if !defined(__STDC__) && !defined(void)
#define void int
#endif
/* The 16 2-operand raster-ops:
These match the correspodning GX codes in X11. */
enum _BS_alu {
_BS_alu_clear = 0 /* 0 */,
_BS_alu_and = 1 /* src & dst */,
_BS_alu_andReverse = 2 /* src & ~dst */,
_BS_alu_copy = 3 /* src */,
_BS_alu_andInverted = 4 /* ~src & dst */,
_BS_alu_noop = 5 /* dst */,
_BS_alu_xor = 6 /* src ^ dst */,
_BS_alu_or = 7 /* src | dst */,
_BS_alu_nor = 8 /* ~src & ~dst */,
_BS_alu_equiv = 9 /* ~(src ^ dst) */,
_BS_alu_invert = 10 /* ~dst */,
_BS_alu_orReverse = 11 /* src | ~dst */,
_BS_alu_copyInverted = 12 /* ~src */,
_BS_alu_orInverted = 13 /* ~src | dst */,
_BS_alu_nand = 14 /* ~src | d~st */,
_BS_alu_set = 15 /* ~src | dst */
};
#define _BS
#define _BS
#ifdef __cplusplus
extern "C" {
#endif
extern void _BS_and __P((_BS_word*,int, const _BS_word*, int, _BS_size_t));
extern void _BS_blt __P((enum _BS_alu,
_BS_word*,int, const _BS_word*,int, _BS_size_t));
extern void _BS_copy __P((_BS_word*,int, const _BS_word*,int, _BS_size_t));
#define _BS_copy_0(DS, SS, LENGTH) _BS_copy(DS, 0, SS, 0, LENGTH)
extern int _BS_count __P((const _BS_word*, int, _BS_size_t));
extern int _BS_any __P((const _BS_word*, int, _BS_size_t));
extern void _BS_clear __P((_BS_word*, int, _BS_size_t));
extern void _BS_set __P((_BS_word*, int, _BS_size_t));
extern void _BS_invert __P((_BS_word*, int, _BS_size_t));
int _BS_lcompare_0 __P((const _BS_word*, _BS_size_t,
const _BS_word*, _BS_size_t));
extern void _BS_xor __P((_BS_word*,int, const _BS_word*,int, _BS_size_t));
#ifdef __cplusplus
}
#endif
#endif /* !_BS_PRIMS */
Here is bitdo2.h, which is a complete 1-dimensional "bitblt",
handling overlapping and non-aligned bitstrings:
#ifndef ONES
#define ONES ((_BS_word)(~0L))
#endif
#ifndef DOIT_SOLID
#ifdef DOIT
#define DOIT_SOLID(dst, src) DOIT(dst, src, (_BS_word)(~0))
#else
#define DOIT_SOLID(dst, src) (dst) = (COMBINE(dst, src))
#endif
#endif
#ifndef DOIT
#define DOIT(dst, src, mask) \
(dst) = ((COMBINE(dst, src)) & (mask)) | ((dst) & ~(mask))
#endif
_BS_word word0, mask;
int shift0, shift1;
if (length == 0)
goto done;
shift0 = srcbit - dstbit;
/* First handle the case that only one destination word is touched. */
if (length + dstbit <= _BS_BITS_PER_WORD)
{
_BS_word mask
= (ONES _BS_LEFT (_BS_BITS_PER_WORD - length)) _BS_RIGHT dstbit;
_BS_word word0 = *psrc++;
if (shift0 <= 0) /* dstbit >= srcbit */
{
word0 = word0 _BS_RIGHT (-shift0);
}
else
{
word0 = word0 _BS_LEFT shift0;
if (length + srcbit > _BS_BITS_PER_WORD)
word0 = word0 | (*psrc _BS_RIGHT (_BS_BITS_PER_WORD - shift0));
}
DOIT(*pdst, word0, mask);
goto done;
}
/* Next optimize the case that the source and destination are aligned. */
if (shift0 == 0)
{
_BS_word mask;
if (psrc > pdst)
{
if (srcbit)
{
mask = ONES _BS_RIGHT srcbit;
DOIT(*pdst, *psrc, mask);
pdst++; psrc++;
length -= _BS_BITS_PER_WORD - srcbit;
}
for (; length >= _BS_BITS_PER_WORD; length -= _BS_BITS_PER_WORD)
{
DOIT_SOLID(*pdst, *psrc);
pdst++; psrc++;
}
if (length)
{
mask = ONES _BS_LEFT (_BS_BITS_PER_WORD - length);
DOIT(*pdst, *psrc, mask);
}
}
else if (psrc < pdst)
{
_BS_size_t span = srcbit + length;
pdst += span / (_BS_size_t)_BS_BITS_PER_WORD;
psrc += span / (_BS_size_t)_BS_BITS_PER_WORD;
span %= (_BS_size_t)_BS_BITS_PER_WORD;
if (span)
{
mask = ONES _BS_LEFT (_BS_BITS_PER_WORD - span);
DOIT(*pdst, *psrc, mask);
length -= span;
}
pdst--; psrc--;
for (; length >= _BS_BITS_PER_WORD; length -= _BS_BITS_PER_WORD)
{
DOIT_SOLID(*pdst, *psrc);
pdst--; psrc--;
}
if (srcbit)
{
mask = ONES _BS_RIGHT srcbit;
DOIT(*pdst, *psrc, mask);
}
}
/* else if (psrc == pdst) --nothing to do--; */
goto done;
}
/* Now we assume shift!=0, and more than on destination word is changed. */
if (psrc >= pdst) /* Do the updates in forward direction. */
{
_BS_word word0 = *psrc++;
_BS_word mask = ONES _BS_RIGHT dstbit;
if (shift0 > 0)
{
_BS_word word1 = *psrc++;
shift1 = _BS_BITS_PER_WORD - shift0;
DOIT(*pdst, (word0 _BS_LEFT shift0) | (word1 _BS_RIGHT shift1), mask);
word0 = word1;
}
else /* dstbit > srcbit */
{
shift1 = -shift0;
shift0 += _BS_BITS_PER_WORD;
DOIT(*pdst, word0 _BS_RIGHT shift1, mask);
}
pdst++;
length -= _BS_BITS_PER_WORD - dstbit;
for ( ; length >= _BS_BITS_PER_WORD; length -= _BS_BITS_PER_WORD)
{
register _BS_word word1 = *psrc++;
DOIT_SOLID(*pdst,
(word0 _BS_LEFT shift0) | (word1 _BS_RIGHT shift1));
pdst++;
word0 = word1;
}
if (length > 0)
{
_BS_size_t mask = ONES _BS_LEFT (_BS_BITS_PER_WORD - length);
word0 = word0 _BS_LEFT shift0;
if (length > shift1)
word0 = word0 | (*psrc _BS_RIGHT shift1) ;
DOIT (*pdst, word0, mask);
}
}
else /* Do the updates in backward direction. */
{
_BS_word word0;
/* Make (psrc, srcbit) and (pdst, dstbit) point to *last* bit. */
psrc += (srcbit + length - 1) / _BS_BITS_PER_WORD;
srcbit = (srcbit + length - 1) % _BS_BITS_PER_WORD;
pdst += (dstbit + length - 1) / _BS_BITS_PER_WORD;
dstbit = (dstbit + length - 1) % _BS_BITS_PER_WORD;
shift0 = srcbit - dstbit;
word0 = *psrc--;
mask = ONES _BS_LEFT (_BS_BITS_PER_WORD - 1 - dstbit);
if (shift0 < 0)
{
_BS_word word1 = *psrc--;
shift1 = -shift0;
shift0 += _BS_BITS_PER_WORD;
DOIT (*pdst, (word0 _BS_RIGHT shift1) | (word1 _BS_LEFT shift0),
mask);
word0 = word1;
}
else
{
shift1 = _BS_BITS_PER_WORD - shift0;
DOIT(*pdst, word0 _BS_LEFT shift0, mask);
}
pdst--;
length -= dstbit + 1;
for ( ; length >= _BS_BITS_PER_WORD; length -= _BS_BITS_PER_WORD)
{
register _BS_word word1 = *psrc--;
DOIT_SOLID(*pdst,
(word0 _BS_RIGHT shift1) | (word1 _BS_LEFT shift0));
pdst--;
word0 = word1;
}
if (length > 0)
{
_BS_size_t mask = ONES _BS_RIGHT (_BS_BITS_PER_WORD - length);
word0 = word0 _BS_RIGHT shift1;
if (length > shift0)
word0 = word0 | (*psrc _BS_LEFT shift0) ;
DOIT (*pdst, word0, mask);
}
}
done: ;
Here is bitand.c, which implements the set intersection operator:
/* Copyright (C) 1994 Free Software Foundation
This file is part of the GNU BitString Library. This library is free
software; you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option)
any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this library; see the file COPYING. If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
As a special exception, if you link this library with files
compiled with a GNU compiler to produce an executable, this does not cause
the resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why
the executable file might be covered by the GNU General Public License. */
/* Written by Per Bothner (bothner@cygnus.com). */
#include "bitprims.h"
/* Copy LENGTH bits from (starting at SRCBIT) into pdst starting at DSTBIT.
This will work even if psrc & pdst overlap. */
void
_BS_and (pdst, dstbit, psrc, srcbit, length)
register _BS_word* pdst;
int dstbit;
register const _BS_word* psrc;
int srcbit;
_BS_size_t length;
{
#define COMBINE(dst, src) (dst) & (src)
#include "bitdo2.h"
}
Here is bitblt.c, the generic one operand "bitblt" function,
which implements all 16 2-operand operations:
/* Copyright (C) 1994 Free Software Foundation
This file is part of the GNU BitString Library. This library is free
software; you can redistribute it and/or modify it under the
terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option)
any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this library; see the file COPYING. If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
As a special exception, if you link this library with files
compiled with a GNU compiler to produce an executable, this does not cause
the resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why
the executable file might be covered by the GNU General Public License. */
/* Written by Per Bothner (bothner@cygnus.com).
Based on ideas in the X11 MFB server. */
#include "bitprims.h"
#define ONES ((_BS_word)(~0))
/* Copy LENGTH bits from (starting at SRCBIT) into pdst starting at DSTBIT.
This will work even if psrc & pdst overlap. */
void
_BS_blt (op, pdst, dstbit, psrc, srcbit, length)
enum _BS_alu op;
register _BS_word* pdst;
int dstbit;
register const _BS_word* psrc;
int srcbit;
_BS_size_t length;
{
_BS_word ca1, cx1, ca2, cx2;
switch (op)
{
case _BS_alu_clear:
_BS_clear (pdst, dstbit, length);
return;
case _BS_alu_and:
_BS_and (pdst, dstbit, psrc, srcbit, length);
return;
case _BS_alu_andReverse:
ca1 = ONES; cx1 = 0; ca2 = ONES; cx2 = 0;
break;
case _BS_alu_copy:
_BS_copy (pdst, dstbit, psrc, srcbit, length);
return;
case _BS_alu_andInverted:
ca1 = ONES; cx1 = ONES; ca2 = 0; cx2 = 0;
break;
case _BS_alu_noop:
return;
case _BS_alu_xor:
_BS_xor (pdst, dstbit, psrc, srcbit, length);
return;
case _BS_alu_or:
ca1 = ONES; cx1 = ONES; ca2 = ONES; cx2 = 0;
break;
case _BS_alu_nor:
ca1 = ONES; cx1 = ONES; ca2 = ONES; cx2 = ONES;
break;
case_BS_alu_equiv:
ca1 = 0; cx1 = ONES; ca2 = ONES; cx2 = ONES;
break;
case _BS_alu_invert:
_BS_invert (pdst, dstbit, length);
return;
case _BS_alu_orReverse:
ca1 = ONES; cx1 = ONES; ca2 = 0; cx2 = ONES;
break;
case _BS_alu_copyInverted:
ca1 = 0; cx1 = 0; ca2 = ONES; cx2 = ONES;
break;
case _BS_alu_orInverted:
ca1 = ONES; cx1 = 0; ca2 = ONES; cx2 = ONES;
break;
case _BS_alu_nand:
ca1 = ONES; cx1 = 0; ca2 = 0; cx2 = ONES;
break;
case _BS_alu_set:
_BS_set (pdst, dstbit, length);
return;
}
{
#define COMBINE(dst, src) ((dst) & ((src) & ca1 ^ cx1) ^ ((src) & ca2 ^ cx2))
#include "bitdo2.h"
}
}
--Per Bothner
Cygnus Solutions bothner@cygnus.com http://www.cygnus.com/~bothner
More information about the Gcc
mailing list