blob: dfb08252b04580a2346530dff019247d44c52c90 [file] [log] [blame]
#include "util.h"
#include "coretype.h"
/*****************************************************************************/
/* MODULE NAME: BitVector.c MODULE TYPE: (adt) */
/*****************************************************************************/
/* MODULE IMPORTS: */
/*****************************************************************************/
#include <ctype.h> /* MODULE TYPE: (sys) */
#include <limits.h> /* MODULE TYPE: (sys) */
#include <string.h> /* MODULE TYPE: (sys) */
/*****************************************************************************/
/* MODULE INTERFACE: */
/*****************************************************************************/
#include "bitvect.h"
/* ToolBox.h */
#define and && /* logical (boolean) operators: lower case */
#define or ||
#define not !
#define AND & /* binary (bitwise) operators: UPPER CASE */
#define OR |
#define XOR ^
#define NOT ~
#define SHL <<
#define SHR >>
#ifdef ENABLE_MODULO
#define mod % /* arithmetic operators */
#endif
#define blockdef(name,size) unsigned char name[size]
#define blocktypedef(name,size) typedef unsigned char name[size]
/*****************************************************************************/
/* MODULE RESOURCES: */
/*****************************************************************************/
#define bits_(BitVector) *(BitVector-3)
#define size_(BitVector) *(BitVector-2)
#define mask_(BitVector) *(BitVector-1)
#define ERRCODE_TYPE "sizeof(word) > sizeof(size_t)"
#define ERRCODE_BITS "bits(word) != sizeof(word)*8"
#define ERRCODE_WORD "bits(word) < 16"
#define ERRCODE_LONG "bits(word) > bits(long)"
#define ERRCODE_POWR "bits(word) != 2^x"
#define ERRCODE_LOGA "bits(word) != 2^ld(bits(word))"
#define ERRCODE_NULL "unable to allocate memory"
#define ERRCODE_INDX "index out of range"
#define ERRCODE_ORDR "minimum > maximum index"
#define ERRCODE_SIZE "bit vector size mismatch"
#define ERRCODE_PARS "input string syntax error"
#define ERRCODE_OVFL "numeric overflow error"
#define ERRCODE_SAME "result vector(s) must be distinct"
#define ERRCODE_EXPO "exponent must be positive"
#define ERRCODE_ZERO "division by zero error"
#define ERRCODE_OOPS "unexpected internal error - please contact author"
const N_int BitVector_BYTENORM[256] =
{
0x00, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02, 0x03,
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, /* 0x00 */
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x10 */
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x20 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x30 */
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x40 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x50 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x60 */
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0x70 */
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x80 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x90 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xA0 */
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xB0 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xC0 */
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xD0 */
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xE0 */
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
0x05, 0x06, 0x06, 0x07, 0x06, 0x07, 0x07, 0x08 /* 0xF0 */
};
/*****************************************************************************/
/* MODULE IMPLEMENTATION: */
/*****************************************************************************/
/**********************************************/
/* global implementation-intrinsic constants: */
/**********************************************/
#define BIT_VECTOR_HIDDEN_WORDS 3
/*****************************************************************/
/* global machine-dependent constants (set by "BitVector_Boot"): */
/*****************************************************************/
static N_word BITS; /* = # of bits in machine word (must be power of 2) */
static N_word MODMASK; /* = BITS - 1 (mask for calculating modulo BITS) */
static N_word LOGBITS; /* = ld(BITS) (logarithmus dualis) */
static N_word FACTOR; /* = ld(BITS / 8) (ld of # of bytes) */
static N_word LSB = 1; /* = mask for least significant bit */
static N_word MSB; /* = mask for most significant bit */
static N_word LONGBITS; /* = # of bits in unsigned long */
static N_word LOG10; /* = logarithm to base 10 of BITS - 1 */
static N_word EXP10; /* = largest possible power of 10 in signed int */
/********************************************************************/
/* global bit mask table for fast access (set by "BitVector_Boot"): */
/********************************************************************/
static wordptr BITMASKTAB;
/*****************************/
/* global macro definitions: */
/*****************************/
#define BIT_VECTOR_ZERO_WORDS(target,count) \
while (count-- > 0) *target++ = 0;
#define BIT_VECTOR_FILL_WORDS(target,fill,count) \
while (count-- > 0) *target++ = fill;
#define BIT_VECTOR_FLIP_WORDS(target,flip,count) \
while (count-- > 0) *target++ ^= flip;
#define BIT_VECTOR_COPY_WORDS(target,source,count) \
while (count-- > 0) *target++ = *source++;
#define BIT_VECTOR_BACK_WORDS(target,source,count) \
{ target += count; source += count; while (count-- > 0) *--target = *--source; }
#define BIT_VECTOR_CLR_BIT(address,index) \
*(address+(index>>LOGBITS)) &= NOT BITMASKTAB[index AND MODMASK];
#define BIT_VECTOR_SET_BIT(address,index) \
*(address+(index>>LOGBITS)) |= BITMASKTAB[index AND MODMASK];
#define BIT_VECTOR_TST_BIT(address,index) \
((*(address+(index>>LOGBITS)) AND BITMASKTAB[index AND MODMASK]) != 0)
#define BIT_VECTOR_FLP_BIT(address,index,mask) \
(mask = BITMASKTAB[index AND MODMASK]), \
(((*(addr+(index>>LOGBITS)) ^= mask) AND mask) != 0)
#define BIT_VECTOR_DIGITIZE(type,value,digit) \
value = (type) ((digit = value) / 10); \
digit -= value * 10; \
digit += (type) '0';
/*********************************************************/
/* private low-level functions (potentially dangerous!): */
/*********************************************************/
static N_word power10(N_word x)
{
N_word y = 1;
while (x-- > 0) y *= 10;
return(y);
}
static void BIT_VECTOR_zro_words(wordptr addr, N_word count)
{
BIT_VECTOR_ZERO_WORDS(addr,count)
}
static void BIT_VECTOR_cpy_words(wordptr target, wordptr source, N_word count)
{
BIT_VECTOR_COPY_WORDS(target,source,count)
}
static void BIT_VECTOR_mov_words(wordptr target, wordptr source, N_word count)
{
if (target != source)
{
if (target < source) BIT_VECTOR_COPY_WORDS(target,source,count)
else BIT_VECTOR_BACK_WORDS(target,source,count)
}
}
static void BIT_VECTOR_ins_words(wordptr addr, N_word total, N_word count,
boolean clear)
{
N_word length;
if ((total > 0) and (count > 0))
{
if (count > total) count = total;
length = total - count;
if (length > 0) BIT_VECTOR_mov_words(addr+count,addr,length);
if (clear) BIT_VECTOR_zro_words(addr,count);
}
}
static void BIT_VECTOR_del_words(wordptr addr, N_word total, N_word count,
boolean clear)
{
N_word length;
if ((total > 0) and (count > 0))
{
if (count > total) count = total;
length = total - count;
if (length > 0) BIT_VECTOR_mov_words(addr,addr+count,length);
if (clear) BIT_VECTOR_zro_words(addr+length,count);
}
}
static void BIT_VECTOR_reverse(charptr string, N_word length)
{
charptr last;
N_char temp;
if (length > 1)
{
last = string + length - 1;
while (string < last)
{
temp = *string;
*string = *last;
*last = temp;
string++;
last--;
}
}
}
static N_word BIT_VECTOR_int2str(charptr string, N_word value)
{
N_word length;
N_word digit;
charptr work;
work = string;
if (value > 0)
{
length = 0;
while (value > 0)
{
BIT_VECTOR_DIGITIZE(N_word,value,digit)
*work++ = (N_char) digit;
length++;
}
BIT_VECTOR_reverse(string,length);
}
else
{
length = 1;
*work++ = (N_char) '0';
}
return(length);
}
static N_word BIT_VECTOR_str2int(charptr string, N_word *value)
{
N_word length;
N_word digit;
*value = 0;
length = 0;
digit = (N_word) *string++;
/* separate because isdigit() is likely a macro! */
while (isdigit((int)digit) != 0)
{
length++;
digit -= (N_word) '0';
if (*value) *value *= 10;
*value += digit;
digit = (N_word) *string++;
}
return(length);
}
/********************************************/
/* routine to convert error code to string: */
/********************************************/
const char * BitVector_Error(ErrCode error)
{
switch (error)
{
case ErrCode_Ok: return( NULL ); break;
case ErrCode_Type: return( ERRCODE_TYPE ); break;
case ErrCode_Bits: return( ERRCODE_BITS ); break;
case ErrCode_Word: return( ERRCODE_WORD ); break;
case ErrCode_Long: return( ERRCODE_LONG ); break;
case ErrCode_Powr: return( ERRCODE_POWR ); break;
case ErrCode_Loga: return( ERRCODE_LOGA ); break;
case ErrCode_Null: return( ERRCODE_NULL ); break;
case ErrCode_Indx: return( ERRCODE_INDX ); break;
case ErrCode_Ordr: return( ERRCODE_ORDR ); break;
case ErrCode_Size: return( ERRCODE_SIZE ); break;
case ErrCode_Pars: return( ERRCODE_PARS ); break;
case ErrCode_Ovfl: return( ERRCODE_OVFL ); break;
case ErrCode_Same: return( ERRCODE_SAME ); break;
case ErrCode_Expo: return( ERRCODE_EXPO ); break;
case ErrCode_Zero: return( ERRCODE_ZERO ); break;
default: return( ERRCODE_OOPS ); break;
}
}
/*****************************************/
/* automatic self-configuration routine: */
/*****************************************/
/*******************************************************/
/* */
/* MUST be called once prior to any other function */
/* to initialize the machine dependent constants */
/* of this package! (But call only ONCE, or you */
/* will suffer memory leaks!) */
/* */
/*******************************************************/
ErrCode BitVector_Boot(void)
{
N_long longsample = 1L;
N_word sample = LSB;
N_word lsb;
if (sizeof(N_word) > sizeof(size_t)) return(ErrCode_Type);
BITS = 1;
while (sample <<= 1) BITS++; /* determine # of bits in a machine word */
if (BITS != (sizeof(N_word) << 3)) return(ErrCode_Bits);
if (BITS < 16) return(ErrCode_Word);
LONGBITS = 1;
while (longsample <<= 1) LONGBITS++; /* = # of bits in an unsigned long */
if (BITS > LONGBITS) return(ErrCode_Long);
LOGBITS = 0;
sample = BITS;
lsb = (sample AND LSB);
while ((sample >>= 1) and (not lsb))
{
LOGBITS++;
lsb = (sample AND LSB);
}
if (sample) return(ErrCode_Powr); /* # of bits is not a power of 2! */
if (BITS != (LSB << LOGBITS)) return(ErrCode_Loga);
MODMASK = BITS - 1;
FACTOR = LOGBITS - 3; /* ld(BITS / 8) = ld(BITS) - ld(8) = ld(BITS) - 3 */
MSB = (LSB << MODMASK);
BITMASKTAB = (wordptr) yasm_xmalloc((size_t) (BITS << FACTOR));
if (BITMASKTAB == NULL) return(ErrCode_Null);
for ( sample = 0; sample < BITS; sample++ )
{
BITMASKTAB[sample] = (LSB << sample);
}
LOG10 = (N_word) (MODMASK * 0.30103); /* = (BITS - 1) * ( ln 2 / ln 10 ) */
EXP10 = power10(LOG10);
return(ErrCode_Ok);
}
void BitVector_Shutdown(void)
{
if (BITMASKTAB) yasm_xfree(BITMASKTAB);
}
N_word BitVector_Size(N_int bits) /* bit vector size (# of words) */
{
N_word size;
size = bits >> LOGBITS;
if (bits AND MODMASK) size++;
return(size);
}
N_word BitVector_Mask(N_int bits) /* bit vector mask (unused bits) */
{
N_word mask;
mask = bits AND MODMASK;
if (mask) mask = (N_word) ~(~0L << mask); else mask = (N_word) ~0L;
return(mask);
}
const char * BitVector_Version(void)
{
return("6.4");
}
N_int BitVector_Word_Bits(void)
{
return(BITS);
}
N_int BitVector_Long_Bits(void)
{
return(LONGBITS);
}
/********************************************************************/
/* */
/* WARNING: Do not "free()" constant character strings, i.e., */
/* don't call "BitVector_Dispose()" for strings returned */
/* by "BitVector_Error()" or "BitVector_Version()"! */
/* */
/* ONLY call this function for strings allocated with "malloc()", */
/* i.e., the strings returned by the functions "BitVector_to_*()" */
/* and "BitVector_Block_Read()"! */
/* */
/********************************************************************/
void BitVector_Dispose(charptr string) /* free string */
{
if (string != NULL) yasm_xfree((voidptr) string);
}
void BitVector_Destroy(wordptr addr) /* free bitvec */
{
if (addr != NULL)
{
addr -= BIT_VECTOR_HIDDEN_WORDS;
yasm_xfree((voidptr) addr);
}
}
void BitVector_Destroy_List(listptr list, N_int count) /* free list */
{
listptr slot;
if (list != NULL)
{
slot = list;
while (count-- > 0)
{
BitVector_Destroy(*slot++);
}
free((voidptr) list);
}
}
wordptr BitVector_Create(N_int bits, boolean clear) /* malloc */
{
N_word size;
N_word mask;
N_word bytes;
wordptr addr;
wordptr zero;
size = BitVector_Size(bits);
mask = BitVector_Mask(bits);
bytes = (size + BIT_VECTOR_HIDDEN_WORDS) << FACTOR;
addr = (wordptr) yasm_xmalloc((size_t) bytes);
if (addr != NULL)
{
*addr++ = bits;
*addr++ = size;
*addr++ = mask;
if (clear)
{
zero = addr;
BIT_VECTOR_ZERO_WORDS(zero,size)
}
}
return(addr);
}
listptr BitVector_Create_List(N_int bits, boolean clear, N_int count)
{
listptr list = NULL;
listptr slot;
wordptr addr;
N_int i;
if (count > 0)
{
list = (listptr) malloc(sizeof(wordptr) * count);
if (list != NULL)
{
slot = list;
for ( i = 0; i < count; i++ )
{
addr = BitVector_Create(bits,clear);
if (addr == NULL)
{
BitVector_Destroy_List(list,i);
return(NULL);
}
*slot++ = addr;
}
}
}
return(list);
}
wordptr BitVector_Resize(wordptr oldaddr, N_int bits) /* realloc */
{
N_word bytes;
N_word oldsize;
N_word oldmask;
N_word newsize;
N_word newmask;
wordptr newaddr;
wordptr source;
wordptr target;
oldsize = size_(oldaddr);
oldmask = mask_(oldaddr);
newsize = BitVector_Size(bits);
newmask = BitVector_Mask(bits);
if (oldsize > 0) *(oldaddr+oldsize-1) &= oldmask;
if (newsize <= oldsize)
{
newaddr = oldaddr;
bits_(newaddr) = bits;
size_(newaddr) = newsize;
mask_(newaddr) = newmask;
if (newsize > 0) *(newaddr+newsize-1) &= newmask;
}
else
{
bytes = (newsize + BIT_VECTOR_HIDDEN_WORDS) << FACTOR;
newaddr = (wordptr) yasm_xmalloc((size_t) bytes);
if (newaddr != NULL)
{
*newaddr++ = bits;
*newaddr++ = newsize;
*newaddr++ = newmask;
target = newaddr;
source = oldaddr;
newsize -= oldsize;
BIT_VECTOR_COPY_WORDS(target,source,oldsize)
BIT_VECTOR_ZERO_WORDS(target,newsize)
}
BitVector_Destroy(oldaddr);
}
return(newaddr);
}
wordptr BitVector_Shadow(wordptr addr) /* makes new, same size but empty */
{
return( BitVector_Create(bits_(addr),true) );
}
wordptr BitVector_Clone(wordptr addr) /* makes exact duplicate */
{
N_word bits;
wordptr twin;
bits = bits_(addr);
twin = BitVector_Create(bits,false);
if ((twin != NULL) and (bits > 0))
BIT_VECTOR_cpy_words(twin,addr,size_(addr));
return(twin);
}
wordptr BitVector_Concat(wordptr X, wordptr Y) /* returns concatenation */
{
/* BEWARE that X = most significant part, Y = least significant part! */
N_word bitsX;
N_word bitsY;
N_word bitsZ;
wordptr Z;
bitsX = bits_(X);
bitsY = bits_(Y);
bitsZ = bitsX + bitsY;
Z = BitVector_Create(bitsZ,false);
if ((Z != NULL) and (bitsZ > 0))
{
BIT_VECTOR_cpy_words(Z,Y,size_(Y));
BitVector_Interval_Copy(Z,X,bitsY,0,bitsX);
*(Z+size_(Z)-1) &= mask_(Z);
}
return(Z);
}
void BitVector_Copy(wordptr X, wordptr Y) /* X = Y */
{
N_word sizeX = size_(X);
N_word sizeY = size_(Y);
N_word maskX = mask_(X);
N_word maskY = mask_(Y);
N_word fill = 0;
wordptr lastX;
wordptr lastY;
if ((X != Y) and (sizeX > 0))
{
lastX = X + sizeX - 1;
if (sizeY > 0)
{
lastY = Y + sizeY - 1;
if ( (*lastY AND (maskY AND NOT (maskY >> 1))) == 0 ) *lastY &= maskY;
else
{
fill = (N_word) ~0L;
*lastY |= NOT maskY;
}
while ((sizeX > 0) and (sizeY > 0))
{
*X++ = *Y++;
sizeX--;
sizeY--;
}
*lastY &= maskY;
}
while (sizeX-- > 0) *X++ = fill;
*lastX &= maskX;
}
}
void BitVector_Empty(wordptr addr) /* X = {} clr all */
{
N_word size = size_(addr);
BIT_VECTOR_ZERO_WORDS(addr,size)
}
void BitVector_Fill(wordptr addr) /* X = ~{} set all */
{
N_word size = size_(addr);
N_word mask = mask_(addr);
N_word fill = (N_word) ~0L;
if (size > 0)
{
BIT_VECTOR_FILL_WORDS(addr,fill,size)
*(--addr) &= mask;
}
}
void BitVector_Flip(wordptr addr) /* X = ~X flip all */
{
N_word size = size_(addr);
N_word mask = mask_(addr);
N_word flip = (N_word) ~0L;
if (size > 0)
{
BIT_VECTOR_FLIP_WORDS(addr,flip,size)
*(--addr) &= mask;
}
}
void BitVector_Primes(wordptr addr)
{
N_word bits = bits_(addr);
N_word size = size_(addr);
wordptr work;
N_word temp;
N_word i,j;
if (size > 0)
{
temp = 0xAAAA;
i = BITS >> 4;
while (--i > 0)
{
temp <<= 16;
temp |= 0xAAAA;
}
i = size;
work = addr;
*work++ = temp XOR 0x0006;
while (--i > 0) *work++ = temp;
for ( i = 3; (j = i * i) < bits; i += 2 )
{
for ( ; j < bits; j += i ) BIT_VECTOR_CLR_BIT(addr,j)
}
*(addr+size-1) &= mask_(addr);
}
}
void BitVector_Reverse(wordptr X, wordptr Y)
{
N_word bits = bits_(X);
N_word mask;
N_word bit;
N_word value;
if (bits > 0)
{
if (X == Y) BitVector_Interval_Reverse(X,0,bits-1);
else if (bits == bits_(Y))
{
/* mask = mask_(Y); */
/* mask &= NOT (mask >> 1); */
mask = BITMASKTAB[(bits-1) AND MODMASK];
Y += size_(Y) - 1;
value = 0;
bit = LSB;
while (bits-- > 0)
{
if ((*Y AND mask) != 0)
{
value |= bit;
}
if (not (mask >>= 1))
{
Y--;
mask = MSB;
}
if (not (bit <<= 1))
{
*X++ = value;
value = 0;
bit = LSB;
}
}
if (bit > LSB) *X = value;
}
}
}
void BitVector_Interval_Empty(wordptr addr, N_int lower, N_int upper)
{ /* X = X \ [lower..upper] */
N_word bits = bits_(addr);
N_word size = size_(addr);
wordptr loaddr;
wordptr hiaddr;
N_word lobase;
N_word hibase;
N_word lomask;
N_word himask;
N_word diff;
if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
{
lobase = lower >> LOGBITS;
hibase = upper >> LOGBITS;
diff = hibase - lobase;
loaddr = addr + lobase;
hiaddr = addr + hibase;
lomask = (N_word) (~0L << (lower AND MODMASK));
himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
if (diff == 0)
{
*loaddr &= NOT (lomask AND himask);
}
else
{
*loaddr++ &= NOT lomask;
while (--diff > 0)
{
*loaddr++ = 0;
}
*hiaddr &= NOT himask;
}
}
}
void BitVector_Interval_Fill(wordptr addr, N_int lower, N_int upper)
{ /* X = X + [lower..upper] */
N_word bits = bits_(addr);
N_word size = size_(addr);
N_word fill = (N_word) ~0L;
wordptr loaddr;
wordptr hiaddr;
N_word lobase;
N_word hibase;
N_word lomask;
N_word himask;
N_word diff;
if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
{
lobase = lower >> LOGBITS;
hibase = upper >> LOGBITS;
diff = hibase - lobase;
loaddr = addr + lobase;
hiaddr = addr + hibase;
lomask = (N_word) (~0L << (lower AND MODMASK));
himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
if (diff == 0)
{
*loaddr |= (lomask AND himask);
}
else
{
*loaddr++ |= lomask;
while (--diff > 0)
{
*loaddr++ = fill;
}
*hiaddr |= himask;
}
*(addr+size-1) &= mask_(addr);
}
}
void BitVector_Interval_Flip(wordptr addr, N_int lower, N_int upper)
{ /* X = X ^ [lower..upper] */
N_word bits = bits_(addr);
N_word size = size_(addr);
N_word flip = (N_word) ~0L;
wordptr loaddr;
wordptr hiaddr;
N_word lobase;
N_word hibase;
N_word lomask;
N_word himask;
N_word diff;
if ((size > 0) and (lower < bits) and (upper < bits) and (lower <= upper))
{
lobase = lower >> LOGBITS;
hibase = upper >> LOGBITS;
diff = hibase - lobase;
loaddr = addr + lobase;
hiaddr = addr + hibase;
lomask = (N_word) (~0L << (lower AND MODMASK));
himask = (N_word) ~((~0L << (upper AND MODMASK)) << 1);
if (diff == 0)
{
*loaddr ^= (lomask AND himask);
}
else
{
*loaddr++ ^= lomask;
while (--diff > 0)
{
*loaddr++ ^= flip;
}
*hiaddr ^= himask;
}
*(addr+size-1) &= mask_(addr);
}
}
void BitVector_Interval_Reverse(wordptr addr, N_int lower, N_int upper)
{
N_word bits = bits_(addr);
wordptr loaddr;
wordptr hiaddr;
N_word lomask;
N_word himask;
if ((bits > 0) and (lower < bits) and (upper < bits) and (lower < upper))
{
loaddr = addr + (lower >> LOGBITS);
hiaddr = addr + (upper >> LOGBITS);
lomask = BITMASKTAB[lower AND MODMASK];
himask = BITMASKTAB[upper AND MODMASK];
for ( bits = upper - lower + 1; bits > 1; bits -= 2 )
{
if (((*loaddr AND lomask) != 0) XOR ((*hiaddr AND himask) != 0))
{
*loaddr ^= lomask; /* swap bits only if they differ! */
*hiaddr ^= himask;
}
if (not (lomask <<= 1))
{
lomask = LSB;
loaddr++;
}
if (not (himask >>= 1))
{
himask = MSB;
hiaddr--;
}
}
}
}
boolean BitVector_interval_scan_inc(wordptr addr, N_int start,
N_intptr min, N_intptr max)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
N_word offset;
N_word bitmask;
N_word value;
boolean empty;
if ((size == 0) or (start >= bits_(addr))) return(FALSE);
*min = start;
*max = start;
offset = start >> LOGBITS;
*(addr+size-1) &= mask;
addr += offset;
size -= offset;
bitmask = BITMASKTAB[start AND MODMASK];
mask = NOT (bitmask OR (bitmask - 1));
value = *addr++;
if ((value AND bitmask) == 0)
{
value &= mask;
if (value == 0)
{
offset++;
empty = TRUE;
while (empty and (--size > 0))
{
if ((value = *addr++)) empty = false; else offset++;
}
if (empty) return(FALSE);
}
start = offset << LOGBITS;
bitmask = LSB;
mask = value;
while (not (mask AND LSB))
{
bitmask <<= 1;
mask >>= 1;
start++;
}
mask = NOT (bitmask OR (bitmask - 1));
*min = start;
*max = start;
}
value = NOT value;
value &= mask;
if (value == 0)
{
offset++;
empty = TRUE;
while (empty and (--size > 0))
{
if ((value = NOT *addr++)) empty = false; else offset++;
}
if (empty) value = LSB;
}
start = offset << LOGBITS;
while (not (value AND LSB))
{
value >>= 1;
start++;
}
*max = --start;
return(TRUE);
}
boolean BitVector_interval_scan_dec(wordptr addr, N_int start,
N_intptr min, N_intptr max)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
N_word offset;
N_word bitmask;
N_word value;
boolean empty;
if ((size == 0) or (start >= bits_(addr))) return(FALSE);
*min = start;
*max = start;
offset = start >> LOGBITS;
if (offset >= size) return(FALSE);
*(addr+size-1) &= mask;
addr += offset;
size = ++offset;
bitmask = BITMASKTAB[start AND MODMASK];
mask = (bitmask - 1);
value = *addr--;
if ((value AND bitmask) == 0)
{
value &= mask;
if (value == 0)
{
offset--;
empty = TRUE;
while (empty and (--size > 0))
{
if ((value = *addr--)) empty = false; else offset--;
}
if (empty) return(FALSE);
}
start = offset << LOGBITS;
bitmask = MSB;
mask = value;
while (not (mask AND MSB))
{
bitmask >>= 1;
mask <<= 1;
start--;
}
mask = (bitmask - 1);
*max = --start;
*min = start;
}
value = NOT value;
value &= mask;
if (value == 0)
{
offset--;
empty = TRUE;
while (empty and (--size > 0))
{
if ((value = NOT *addr--)) empty = false; else offset--;
}
if (empty) value = MSB;
}
start = offset << LOGBITS;
while (not (value AND MSB))
{
value <<= 1;
start--;
}
*min = start;
return(TRUE);
}
void BitVector_Interval_Copy(wordptr X, wordptr Y, N_int Xoffset,
N_int Yoffset, N_int length)
{
N_word bitsX = bits_(X);
N_word bitsY = bits_(Y);
N_word source = 0; /* silence compiler warning */
N_word target = 0; /* silence compiler warning */
N_word s_lo_base;
N_word s_hi_base;
N_word s_lo_bit;
N_word s_hi_bit;
N_word s_base;
N_word s_lower = 0; /* silence compiler warning */
N_word s_upper = 0; /* silence compiler warning */
N_word s_bits;
N_word s_min;
N_word s_max;
N_word t_lo_base;
N_word t_hi_base;
N_word t_lo_bit;
N_word t_hi_bit;
N_word t_base;
N_word t_lower = 0; /* silence compiler warning */
N_word t_upper = 0; /* silence compiler warning */
N_word t_bits;
N_word t_min;
N_word mask;
N_word bits;
N_word sel;
boolean ascending;
boolean notfirst;
wordptr Z = X;
if ((length > 0) and (Xoffset < bitsX) and (Yoffset < bitsY))
{
if ((Xoffset + length) > bitsX) length = bitsX - Xoffset;
if ((Yoffset + length) > bitsY) length = bitsY - Yoffset;
ascending = (Xoffset <= Yoffset);
s_lo_base = Yoffset >> LOGBITS;
s_lo_bit = Yoffset AND MODMASK;
Yoffset += --length;
s_hi_base = Yoffset >> LOGBITS;
s_hi_bit = Yoffset AND MODMASK;
t_lo_base = Xoffset >> LOGBITS;
t_lo_bit = Xoffset AND MODMASK;
Xoffset += length;
t_hi_base = Xoffset >> LOGBITS;
t_hi_bit = Xoffset AND MODMASK;
if (ascending)
{
s_base = s_lo_base;
t_base = t_lo_base;
}
else
{
s_base = s_hi_base;
t_base = t_hi_base;
}
s_bits = 0;
t_bits = 0;
Y += s_base;
X += t_base;
notfirst = FALSE;
while (TRUE)
{
if (t_bits == 0)
{
if (notfirst)
{
*X = target;
if (ascending)
{
if (t_base == t_hi_base) break;
t_base++;
X++;
}
else
{
if (t_base == t_lo_base) break;
t_base--;
X--;
}
}
sel = ((t_base == t_hi_base) << 1) OR (t_base == t_lo_base);
switch (sel)
{
case 0:
t_lower = 0;
t_upper = BITS - 1;
t_bits = BITS;
target = 0;
break;
case 1:
t_lower = t_lo_bit;
t_upper = BITS - 1;
t_bits = BITS - t_lo_bit;
mask = (N_word) (~0L << t_lower);
target = *X AND NOT mask;
break;
case 2:
t_lower = 0;
t_upper = t_hi_bit;
t_bits = t_hi_bit + 1;
mask = (N_word) ((~0L << t_upper) << 1);
target = *X AND mask;
break;
case 3:
t_lower = t_lo_bit;
t_upper = t_hi_bit;
t_bits = t_hi_bit - t_lo_bit + 1;
mask = (N_word) (~0L << t_lower);
mask &= (N_word) ~((~0L << t_upper) << 1);
target = *X AND NOT mask;
break;
}
}
if (s_bits == 0)
{
if (notfirst)
{
if (ascending)
{
if (s_base == s_hi_base) break;
s_base++;
Y++;
}
else
{
if (s_base == s_lo_base) break;
s_base--;
Y--;
}
}
source = *Y;
sel = ((s_base == s_hi_base) << 1) OR (s_base == s_lo_base);
switch (sel)
{
case 0:
s_lower = 0;
s_upper = BITS - 1;
s_bits = BITS;
break;
case 1:
s_lower = s_lo_bit;
s_upper = BITS - 1;
s_bits = BITS - s_lo_bit;
break;
case 2:
s_lower = 0;
s_upper = s_hi_bit;
s_bits = s_hi_bit + 1;
break;
case 3:
s_lower = s_lo_bit;
s_upper = s_hi_bit;
s_bits = s_hi_bit - s_lo_bit + 1;
break;
}
}
notfirst = TRUE;
if (s_bits > t_bits)
{
bits = t_bits - 1;
if (ascending)
{
s_min = s_lower;
s_max = s_lower + bits;
}
else
{
s_max = s_upper;
s_min = s_upper - bits;
}
t_min = t_lower;
}
else
{
bits = s_bits - 1;
if (ascending) t_min = t_lower;
else t_min = t_upper - bits;
s_min = s_lower;
s_max = s_upper;
}
bits++;
mask = (N_word) (~0L << s_min);
mask &= (N_word) ~((~0L << s_max) << 1);
if (s_min == t_min) target |= (source AND mask);
else
{
if (s_min < t_min) target |= (source AND mask) << (t_min-s_min);
else target |= (source AND mask) >> (s_min-t_min);
}
if (ascending)
{
s_lower += bits;
t_lower += bits;
}
else
{
s_upper -= bits;
t_upper -= bits;
}
s_bits -= bits;
t_bits -= bits;
}
*(Z+size_(Z)-1) &= mask_(Z);
}
}
wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y,
N_int Xoffset, N_int Xlength,
N_int Yoffset, N_int Ylength)
{
N_word Xbits = bits_(X);
N_word Ybits = bits_(Y);
N_word limit;
N_word diff;
if ((Xoffset <= Xbits) and (Yoffset <= Ybits))
{
limit = Xoffset + Xlength;
if (limit > Xbits)
{
limit = Xbits;
Xlength = Xbits - Xoffset;
}
if ((Yoffset + Ylength) > Ybits)
{
Ylength = Ybits - Yoffset;
}
if (Xlength == Ylength)
{
if ((Ylength > 0) and ((X != Y) or (Xoffset != Yoffset)))
{
BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
}
}
else /* Xlength != Ylength */
{
if (Xlength > Ylength)
{
diff = Xlength - Ylength;
if (Ylength > 0) BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
if (limit < Xbits) BitVector_Delete(X,Xoffset+Ylength,diff,FALSE);
if ((X = BitVector_Resize(X,Xbits-diff)) == NULL) return(NULL);
}
else /* Ylength > Xlength ==> Ylength > 0 */
{
diff = Ylength - Xlength;
if (X != Y)
{
if ((X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL);
if (limit < Xbits) BitVector_Insert(X,limit,diff,FALSE);
BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
}
else /* in-place */
{
if ((Y = X = BitVector_Resize(X,Xbits+diff)) == NULL) return(NULL);
if (limit >= Xbits)
{
BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
}
else /* limit < Xbits */
{
BitVector_Insert(X,limit,diff,FALSE);
if ((Yoffset+Ylength) <= limit)
{
BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
}
else /* overlaps or lies above critical area */
{
if (limit <= Yoffset)
{
Yoffset += diff;
BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
}
else /* Yoffset < limit */
{
Xlength = limit - Yoffset;
BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Xlength);
Yoffset = Xoffset + Ylength; /* = limit + diff */
Xoffset += Xlength;
Ylength -= Xlength;
BitVector_Interval_Copy(X,Y,Xoffset,Yoffset,Ylength);
}
}
}
}
}
}
}
return(X);
}
boolean BitVector_is_empty(wordptr addr) /* X == {} ? */
{
N_word size = size_(addr);
boolean r = TRUE;
if (size > 0)
{
*(addr+size-1) &= mask_(addr);
while (r and (size-- > 0)) r = ( *addr++ == 0 );
}
return(r);
}
boolean BitVector_is_full(wordptr addr) /* X == ~{} ? */
{
N_word size = size_(addr);
N_word mask = mask_(addr);
boolean r = FALSE;
wordptr last;
if (size > 0)
{
r = TRUE;
last = addr + size - 1;
*last |= NOT mask;
while (r and (size-- > 0)) r = ( NOT *addr++ == 0 );
*last &= mask;
}
return(r);
}
boolean BitVector_equal(wordptr X, wordptr Y) /* X == Y ? */
{
N_word size = size_(X);
N_word mask = mask_(X);
boolean r = FALSE;
if (bits_(X) == bits_(Y))
{
r = TRUE;
if (size > 0)
{
*(X+size-1) &= mask;
*(Y+size-1) &= mask;
while (r and (size-- > 0)) r = (*X++ == *Y++);
}
}
return(r);
}
Z_int BitVector_Lexicompare(wordptr X, wordptr Y) /* X <,=,> Y ? */
{ /* unsigned */
N_word bitsX = bits_(X);
N_word bitsY = bits_(Y);
N_word size = size_(X);
boolean r = TRUE;
if (bitsX == bitsY)
{
if (size > 0)
{
X += size;
Y += size;
while (r and (size-- > 0)) r = (*(--X) == *(--Y));
}
if (r) return((Z_int) 0);
else
{
if (*X < *Y) return((Z_int) -1); else return((Z_int) 1);
}
}
else
{
if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1);
}
}
Z_int BitVector_Compare(wordptr X, wordptr Y) /* X <,=,> Y ? */
{ /* signed */
N_word bitsX = bits_(X);
N_word bitsY = bits_(Y);
N_word size = size_(X);
N_word mask = mask_(X);
N_word sign;
boolean r = TRUE;
if (bitsX == bitsY)
{
if (size > 0)
{
X += size;
Y += size;
mask &= NOT (mask >> 1);
if ((sign = (*(X-1) AND mask)) != (*(Y-1) AND mask))
{
if (sign) return((Z_int) -1); else return((Z_int) 1);
}
while (r and (size-- > 0)) r = (*(--X) == *(--Y));
}
if (r) return((Z_int) 0);
else
{
if (*X < *Y) return((Z_int) -1); else return((Z_int) 1);
}
}
else
{
if (bitsX < bitsY) return((Z_int) -1); else return((Z_int) 1);
}
}
charptr BitVector_to_Hex(wordptr addr)
{
N_word bits = bits_(addr);
N_word size = size_(addr);
N_word value;
N_word count;
N_word digit;
N_word length;
charptr string;
length = bits >> 2;
if (bits AND 0x0003) length++;
string = (charptr) yasm_xmalloc((size_t) (length+1));
if (string == NULL) return(NULL);
string += length;
*string = (N_char) '\0';
if (size > 0)
{
*(addr+size-1) &= mask_(addr);
while ((size-- > 0) and (length > 0))
{
value = *addr++;
count = BITS >> 2;
while ((count-- > 0) and (length > 0))
{
digit = value AND 0x000F;
if (digit > 9) digit += (N_word) 'A' - 10;
else digit += (N_word) '0';
*(--string) = (N_char) digit; length--;
if ((count > 0) and (length > 0)) value >>= 4;
}
}
}
return(string);
}
ErrCode BitVector_from_Hex(wordptr addr, charptr string)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
boolean ok = TRUE;
size_t length;
N_word value;
N_word count;
int digit;
if (size > 0)
{
length = strlen((char *) string);
string += length;
while (size-- > 0)
{
value = 0;
for ( count = 0; (ok and (length > 0) and (count < BITS)); count += 4 )
{
digit = (int) *(--string); length--;
/* separate because toupper() is likely a macro! */
digit = toupper(digit);
if (digit == '_')
count -= 4;
else if ((ok = (isxdigit(digit) != 0)))
{
if (digit >= (int) 'A') digit -= (int) 'A' - 10;
else digit -= (int) '0';
value |= (((N_word) digit) << count);
}
}
*addr++ = value;
}
*(--addr) &= mask;
}
if (ok) return(ErrCode_Ok);
else return(ErrCode_Pars);
}
ErrCode BitVector_from_Oct(wordptr addr, charptr string)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
boolean ok = TRUE;
size_t length;
N_word value;
N_word value_fill = 0;
N_word count;
Z_word count_fill = 0;
int digit = 0;
if (size > 0)
{
length = strlen((char *) string);
string += length;
while (size-- > 0)
{
value = value_fill;
for ( count = count_fill; (ok and (length > 0) and (count < BITS)); count += 3 )
{
digit = (int) *(--string); length--;
if (digit == '_')
count -= 3;
else if ((ok = (isdigit(digit) && digit != '8' && digit != '9')) != 0)
{
digit -= (int) '0';
value |= (((N_word) digit) << count);
}
}
count_fill = (Z_word)count-(Z_word)BITS;
if (count_fill > 0)
value_fill = (((N_word) digit) >> (3-count_fill));
else
value_fill = 0;
*addr++ = value;
}
*(--addr) &= mask;
}
if (ok) return(ErrCode_Ok);
else return(ErrCode_Pars);
}
charptr BitVector_to_Bin(wordptr addr)
{
N_word size = size_(addr);
N_word value;
N_word count;
N_word digit;
N_word length;
charptr string;
length = bits_(addr);
string = (charptr) yasm_xmalloc((size_t) (length+1));
if (string == NULL) return(NULL);
string += length;
*string = (N_char) '\0';
if (size > 0)
{
*(addr+size-1) &= mask_(addr);
while (size-- > 0)
{
value = *addr++;
count = BITS;
if (count > length) count = length;
while (count-- > 0)
{
digit = value AND 0x0001;
digit += (N_word) '0';
*(--string) = (N_char) digit; length--;
if (count > 0) value >>= 1;
}
}
}
return(string);
}
ErrCode BitVector_from_Bin(wordptr addr, charptr string)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
boolean ok = TRUE;
size_t length;
N_word value;
N_word count;
int digit;
if (size > 0)
{
length = strlen((char *) string);
string += length;
while (size-- > 0)
{
value = 0;
for ( count = 0; (ok and (length > 0) and (count < BITS)); count++ )
{
digit = (int) *(--string); length--;
switch (digit)
{
case (int) '0':
break;
case (int) '1':
value |= BITMASKTAB[count];
break;
case (int) '_':
count--;
break;
default:
ok = FALSE;
break;
}
}
*addr++ = value;
}
*(--addr) &= mask;
}
if (ok) return(ErrCode_Ok);
else return(ErrCode_Pars);
}
charptr BitVector_to_Dec(wordptr addr)
{
N_word bits = bits_(addr);
N_word length;
N_word digits;
N_word count;
N_word q;
N_word r;
boolean loop;
charptr result;
charptr string;
wordptr quot;
wordptr rest;
wordptr temp;
wordptr base;
Z_int sign;
length = (N_word) (bits / 3.3); /* digits = bits * ln(2) / ln(10) */
length += 2; /* compensate for truncating & provide space for minus sign */
result = (charptr) yasm_xmalloc((size_t) (length+1)); /* remember the '\0'! */
if (result == NULL) return(NULL);
string = result;
sign = BitVector_Sign(addr);
if ((bits < 4) or (sign == 0))
{
if (bits > 0) digits = *addr; else digits = (N_word) 0;
if (sign < 0) digits = ((N_word)(-((Z_word)digits))) AND mask_(addr);
*string++ = (N_char) digits + (N_char) '0';
digits = 1;
}
else
{
quot = BitVector_Create(bits,FALSE);
if (quot == NULL)
{
BitVector_Dispose(result);
return(NULL);
}
rest = BitVector_Create(bits,FALSE);
if (rest == NULL)
{
BitVector_Dispose(result);
BitVector_Destroy(quot);
return(NULL);
}
temp = BitVector_Create(bits,FALSE);
if (temp == NULL)
{
BitVector_Dispose(result);
BitVector_Destroy(quot);
BitVector_Destroy(rest);
return(NULL);
}
base = BitVector_Create(bits,TRUE);
if (base == NULL)
{
BitVector_Dispose(result);
BitVector_Destroy(quot);
BitVector_Destroy(rest);
BitVector_Destroy(temp);
return(NULL);
}
if (sign < 0) BitVector_Negate(quot,addr);
else BitVector_Copy(quot,addr);
digits = 0;
*base = EXP10;
loop = (bits >= BITS);
do
{
if (loop)
{
BitVector_Copy(temp,quot);
if (BitVector_Div_Pos(quot,temp,base,rest))
{
BitVector_Dispose(result); /* emergency exit */
BitVector_Destroy(quot);
BitVector_Destroy(rest); /* should never occur */
BitVector_Destroy(temp); /* under normal operation */
BitVector_Destroy(base);
return(NULL);
}
loop = not BitVector_is_empty(quot);
q = *rest;
}
else q = *quot;
count = LOG10;
while (((loop and (count-- > 0)) or ((not loop) and (q != 0))) and
(digits < length))
{
if (q != 0)
{
BIT_VECTOR_DIGITIZE(N_word,q,r)
}
else r = (N_word) '0';
*string++ = (N_char) r;
digits++;
}
}
while (loop and (digits < length));
BitVector_Destroy(quot);
BitVector_Destroy(rest);
BitVector_Destroy(temp);
BitVector_Destroy(base);
}
if ((sign < 0) and (digits < length))
{
*string++ = (N_char) '-';
digits++;
}
*string = (N_char) '\0';
BIT_VECTOR_reverse(result,digits);
return(result);
}
struct BitVector_from_Dec_static_data {
wordptr term;
wordptr base;
wordptr prod;
wordptr rank;
wordptr temp;
};
BitVector_from_Dec_static_data *BitVector_from_Dec_static_Boot(N_word bits)
{
BitVector_from_Dec_static_data *data;
data = yasm_xmalloc(sizeof(BitVector_from_Dec_static_data));
if (bits > 0)
{
data->term = BitVector_Create(BITS,FALSE);
data->base = BitVector_Create(BITS,FALSE);
data->prod = BitVector_Create(bits,FALSE);
data->rank = BitVector_Create(bits,FALSE);
data->temp = BitVector_Create(bits,FALSE);
} else {
data->term = NULL;
data->base = NULL;
data->prod = NULL;
data->rank = NULL;
data->temp = NULL;
}
return data;
}
void BitVector_from_Dec_static_Shutdown(BitVector_from_Dec_static_data *data)
{
if (data) {
BitVector_Destroy(data->term);
BitVector_Destroy(data->base);
BitVector_Destroy(data->prod);
BitVector_Destroy(data->rank);
BitVector_Destroy(data->temp);
}
yasm_xfree(data);
}
ErrCode BitVector_from_Dec_static(BitVector_from_Dec_static_data *data,
wordptr addr, charptr string)
{
ErrCode error = ErrCode_Ok;
N_word bits = bits_(addr);
N_word mask = mask_(addr);
boolean init = (bits > BITS);
boolean minus;
boolean shift;
boolean carry;
wordptr term;
wordptr base;
wordptr prod;
wordptr rank;
wordptr temp;
N_word accu;
N_word powr;
N_word count;
size_t length;
int digit;
if (bits > 0)
{
term = data->term;
base = data->base;
prod = data->prod;
rank = data->rank;
temp = data->temp;
length = strlen((char *) string);
if (length == 0) return(ErrCode_Pars);
digit = (int) *string;
if ((minus = (digit == (int) '-')) or
(digit == (int) '+'))
{
string++;
if (--length == 0) return(ErrCode_Pars);
}
string += length;
if (init)
{
BitVector_Empty(prod);
BitVector_Empty(rank);
}
BitVector_Empty(addr);
*base = EXP10;
shift = FALSE;
while ((not error) and (length > 0))
{
accu = 0;
powr = 1;
count = LOG10;
while ((not error) and (length > 0) and (count-- > 0))
{
digit = (int) *(--string); length--;
/* separate because isdigit() is likely a macro! */
if (isdigit(digit) != 0)
{
accu += ((N_word) digit - (N_word) '0') * powr;
powr *= 10;
}
else error = ErrCode_Pars;
}
if (not error)
{
if (shift)
{
*term = accu;
BitVector_Copy(temp,rank);
error = BitVector_Mul_Pos(prod,temp,term,FALSE);
}
else
{
*prod = accu;
if ((not init) and ((accu AND NOT mask) != 0)) error = ErrCode_Ovfl;
}
if (not error)
{
carry = FALSE;
BitVector_compute(addr,addr,prod,FALSE,&carry);
/* ignores sign change (= overflow) but not */
/* numbers too large (= carry) for resulting bit vector */
if (carry) error = ErrCode_Ovfl;
else
{
if (length > 0)
{
if (shift)
{
BitVector_Copy(temp,rank);
error = BitVector_Mul_Pos(rank,temp,base,FALSE);
}
else
{
*rank = *base;
shift = TRUE;
}
}
}
}
}
}
if (not error and minus)
{
BitVector_Negate(addr,addr);
if ((*(addr + size_(addr) - 1) AND mask AND NOT (mask >> 1)) == 0)
error = ErrCode_Ovfl;
}
}
return(error);
}
ErrCode BitVector_from_Dec(wordptr addr, charptr string)
{
ErrCode error = ErrCode_Ok;
N_word bits = bits_(addr);
N_word mask = mask_(addr);
boolean init = (bits > BITS);
boolean minus;
boolean shift;
boolean carry;
wordptr term;
wordptr base;
wordptr prod;
wordptr rank;
wordptr temp;
N_word accu;
N_word powr;
N_word count;
size_t length;
int digit;
if (bits > 0)
{
length = strlen((char *) string);
if (length == 0) return(ErrCode_Pars);
digit = (int) *string;
if ((minus = (digit == (int) '-')) or
(digit == (int) '+'))
{
string++;
if (--length == 0) return(ErrCode_Pars);
}
string += length;
term = BitVector_Create(BITS,FALSE);
if (term == NULL)
{
return(ErrCode_Null);
}
base = BitVector_Create(BITS,FALSE);
if (base == NULL)
{
BitVector_Destroy(term);
return(ErrCode_Null);
}
prod = BitVector_Create(bits,init);
if (prod == NULL)
{
BitVector_Destroy(term);
BitVector_Destroy(base);
return(ErrCode_Null);
}
rank = BitVector_Create(bits,init);
if (rank == NULL)
{
BitVector_Destroy(term);
BitVector_Destroy(base);
BitVector_Destroy(prod);
return(ErrCode_Null);
}
temp = BitVector_Create(bits,FALSE);
if (temp == NULL)
{
BitVector_Destroy(term);
BitVector_Destroy(base);
BitVector_Destroy(prod);
BitVector_Destroy(rank);
return(ErrCode_Null);
}
BitVector_Empty(addr);
*base = EXP10;
shift = FALSE;
while ((not error) and (length > 0))
{
accu = 0;
powr = 1;
count = LOG10;
while ((not error) and (length > 0) and (count-- > 0))
{
digit = (int) *(--string); length--;
/* separate because isdigit() is likely a macro! */
if (isdigit(digit) != 0)
{
accu += ((N_word) digit - (N_word) '0') * powr;
powr *= 10;
}
else error = ErrCode_Pars;
}
if (not error)
{
if (shift)
{
*term = accu;
BitVector_Copy(temp,rank);
error = BitVector_Mul_Pos(prod,temp,term,FALSE);
}
else
{
*prod = accu;
if ((not init) and ((accu AND NOT mask) != 0)) error = ErrCode_Ovfl;
}
if (not error)
{
carry = FALSE;
BitVector_compute(addr,addr,prod,FALSE,&carry);
/* ignores sign change (= overflow) but not */
/* numbers too large (= carry) for resulting bit vector */
if (carry) error = ErrCode_Ovfl;
else
{
if (length > 0)
{
if (shift)
{
BitVector_Copy(temp,rank);
error = BitVector_Mul_Pos(rank,temp,base,FALSE);
}
else
{
*rank = *base;
shift = TRUE;
}
}
}
}
}
}
BitVector_Destroy(term);
BitVector_Destroy(base);
BitVector_Destroy(prod);
BitVector_Destroy(rank);
BitVector_Destroy(temp);
if (not error and minus)
{
BitVector_Negate(addr,addr);
if ((*(addr + size_(addr) - 1) AND mask AND NOT (mask >> 1)) == 0)
error = ErrCode_Ovfl;
}
}
return(error);
}
charptr BitVector_to_Enum(wordptr addr)
{
N_word bits = bits_(addr);
N_word sample;
N_word length;
N_word digits;
N_word factor;
N_word power;
N_word start;
N_word min;
N_word max;
charptr string;
charptr target;
boolean comma;
if (bits > 0)
{
sample = bits - 1; /* greatest possible index */
length = 2; /* account for index 0 and terminating '\0' */
digits = 1; /* account for intervening dashes and commas */
factor = 1;
power = 10;
while (sample >= (power-1))
{
length += ++digits * factor * 6; /* 9,90,900,9000,... (9*2/3 = 6) */
factor = power;
power *= 10;
}
if (sample > --factor)
{
sample -= factor;
factor = (N_word) ( sample / 3 );
factor = (factor << 1) + (sample - (factor * 3));
length += ++digits * factor;
}
}
else length = 1;
string = (charptr) yasm_xmalloc((size_t) length);
if (string == NULL) return(NULL);
start = 0;
comma = FALSE;
target = string;
while ((start < bits) and BitVector_interval_scan_inc(addr,start,&min,&max))
{
start = max + 2;
if (comma) *target++ = (N_char) ',';
if (min == max)
{
target += BIT_VECTOR_int2str(target,min);
}
else
{
if (min+1 == max)
{
target += BIT_VECTOR_int2str(target,min);
*target++ = (N_char) ',';
target += BIT_VECTOR_int2str(target,max);
}
else
{
target += BIT_VECTOR_int2str(target,min);
*target++ = (N_char) '-';
target += BIT_VECTOR_int2str(target,max);
}
}
comma = TRUE;
}
*target = (N_char) '\0';
return(string);
}
ErrCode BitVector_from_Enum(wordptr addr, charptr string)
{
ErrCode error = ErrCode_Ok;
N_word bits = bits_(addr);
N_word state = 1;
N_word token;
N_word indx = 0; /* silence compiler warning */
N_word start = 0; /* silence compiler warning */
if (bits > 0)
{
BitVector_Empty(addr);
while ((not error) and (state != 0))
{
token = (N_word) *string;
/* separate because isdigit() is likely a macro! */
if (isdigit((int)token) != 0)
{
string += BIT_VECTOR_str2int(string,&indx);
if (indx < bits) token = (N_word) '0';
else error = ErrCode_Indx;
}
else string++;
if (not error)
switch (state)
{
case 1:
switch (token)
{
case (N_word) '0':
state = 2;
break;
case (N_word) '\0':
state = 0;
break;
default:
error = ErrCode_Pars;
break;
}
break;
case 2:
switch (token)
{
case (N_word) '-':
start = indx;
state = 3;
break;
case (N_word) ',':
BIT_VECTOR_SET_BIT(addr,indx)
state = 5;
break;
case (N_word) '\0':
BIT_VECTOR_SET_BIT(addr,indx)
state = 0;
break;
default:
error = ErrCode_Pars;
break;
}
break;
case 3:
switch (token)
{
case (N_word) '0':
if (start < indx)
BitVector_Interval_Fill(addr,start,indx);
else if (start == indx)
BIT_VECTOR_SET_BIT(addr,indx)
else error = ErrCode_Ordr;
state = 4;
break;
default:
error = ErrCode_Pars;
break;
}
break;
case 4:
switch (token)
{
case (N_word) ',':
state = 5;
break;
case (N_word) '\0':
state = 0;
break;
default:
error = ErrCode_Pars;
break;
}
break;
case 5:
switch (token)
{
case (N_word) '0':
state = 2;
break;
default:
error = ErrCode_Pars;
break;
}
break;
}
}
}
return(error);
}
void BitVector_Bit_Off(wordptr addr, N_int indx) /* X = X \ {x} */
{
if (indx < bits_(addr)) BIT_VECTOR_CLR_BIT(addr,indx)
}
void BitVector_Bit_On(wordptr addr, N_int indx) /* X = X + {x} */
{
if (indx < bits_(addr)) BIT_VECTOR_SET_BIT(addr,indx)
}
boolean BitVector_bit_flip(wordptr addr, N_int indx) /* X=(X+{x})\(X*{x}) */
{
N_word mask;
if (indx < bits_(addr)) return( BIT_VECTOR_FLP_BIT(addr,indx,mask) );
else return( FALSE );
}
boolean BitVector_bit_test(wordptr addr, N_int indx) /* {x} in X ? */
{
if (indx < bits_(addr)) return( BIT_VECTOR_TST_BIT(addr,indx) );
else return( FALSE );
}
void BitVector_Bit_Copy(wordptr addr, N_int indx, boolean bit)
{
if (indx < bits_(addr))
{
if (bit) BIT_VECTOR_SET_BIT(addr,indx)
else BIT_VECTOR_CLR_BIT(addr,indx)
}
}
void BitVector_LSB(wordptr addr, boolean bit)
{
if (bits_(addr) > 0)
{
if (bit) *addr |= LSB;
else *addr &= NOT LSB;
}
}
void BitVector_MSB(wordptr addr, boolean bit)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
if (size-- > 0)
{
if (bit) *(addr+size) |= mask AND NOT (mask >> 1);
else *(addr+size) &= NOT mask OR (mask >> 1);
}
}
boolean BitVector_lsb_(wordptr addr)
{
if (size_(addr) > 0) return( (*addr AND LSB) != 0 );
else return( FALSE );
}
boolean BitVector_msb_(wordptr addr)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
if (size-- > 0)
return( (*(addr+size) AND (mask AND NOT (mask >> 1))) != 0 );
else
return( FALSE );
}
boolean BitVector_rotate_left(wordptr addr)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
N_word msb;
boolean carry_in;
boolean carry_out = FALSE;
if (size > 0)
{
msb = mask AND NOT (mask >> 1);
carry_in = ((*(addr+size-1) AND msb) != 0);
while (size-- > 1)
{
carry_out = ((*addr AND MSB) != 0);
*addr <<= 1;
if (carry_in) *addr |= LSB;
carry_in = carry_out;
addr++;
}
carry_out = ((*addr AND msb) != 0);
*addr <<= 1;
if (carry_in) *addr |= LSB;
*addr &= mask;
}
return(carry_out);
}
boolean BitVector_rotate_right(wordptr addr)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
N_word msb;
boolean carry_in;
boolean carry_out = FALSE;
if (size > 0)
{
msb = mask AND NOT (mask >> 1);
carry_in = ((*addr AND LSB) != 0);
addr += size-1;
*addr &= mask;
carry_out = ((*addr AND LSB) != 0);
*addr >>= 1;
if (carry_in) *addr |= msb;
carry_in = carry_out;
addr--;
size--;
while (size-- > 0)
{
carry_out = ((*addr AND LSB) != 0);
*addr >>= 1;
if (carry_in) *addr |= MSB;
carry_in = carry_out;
addr--;
}
}
return(carry_out);
}
boolean BitVector_shift_left(wordptr addr, boolean carry_in)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
N_word msb;
boolean carry_out = carry_in;
if (size > 0)
{
msb = mask AND NOT (mask >> 1);
while (size-- > 1)
{
carry_out = ((*addr AND MSB) != 0);
*addr <<= 1;
if (carry_in) *addr |= LSB;
carry_in = carry_out;
addr++;
}
carry_out = ((*addr AND msb) != 0);
*addr <<= 1;
if (carry_in) *addr |= LSB;
*addr &= mask;
}
return(carry_out);
}
boolean BitVector_shift_right(wordptr addr, boolean carry_in)
{
N_word size = size_(addr);
N_word mask = mask_(addr);
N_word msb;
boolean carry_out = carry_in;
if (size > 0)
{
msb = mask AND NOT (mask >> 1);
addr += size-1;
*addr &= mask;
carry_out = ((*addr AND LSB) != 0);
*addr >>= 1;
if (carry_in) *addr |= msb;
carry_in = carry_out;
addr--;
size--;
while (size-- > 0)
{
carry_out = ((*addr AND LSB) != 0);
*addr >>= 1;
if (carry_in) *addr |= MSB;
carry_in = carry_out;
addr--;
}
}
return(carry_out);
}
void BitVector_Move_Left(wordptr addr, N_int bits)
{
N_word count;
N_word words;
if (bits > 0)
{
count = bits AND MODMASK;
words = bits >> LOGBITS;
if (bits >= bits_(addr)) BitVector_Empty(addr);
else
{
while (count-- > 0) BitVector_shift_left(addr,0);
BitVector_Word_Insert(addr,0,words,TRUE);
}
}
}
void BitVector_Move_Right(wordptr addr, N_int bits)
{
N_word count;
N_word words;
if (bits > 0)
{
count = bits AND MODMASK;
words = bits >> LOGBITS;
if (bits >= bits_(addr)) BitVector_Empty(addr);
else
{
while (count-- > 0) BitVector_shift_right(addr,0);
BitVector_Word_Delete(addr,0,words,TRUE);
}
}
}
void BitVector_Insert(wordptr addr, N_int offset, N_int count, boolean clear)
{
N_word bits = bits_(addr);
N_word last;
if ((count > 0) and (offset < bits))
{
last = offset + count;
if (last < bits)
{
BitVector_Interval_Copy(addr,addr,last,offset,(bits-last));
}
else last = bits;
if (clear) BitVector_Interval_Empty(addr,offset,(last-1));
}
}
void BitVector_Delete(wordptr addr, N_int offset, N_int count, boolean clear)
{
N_word bits = bits_(addr);
N_word last;
if ((count > 0) and (offset < bits))
{
last = offset + count;
if (last < bits)
{
BitVector_Interval_Copy(addr,addr,offset,last,(bits-last));
}
else count = bits - offset;
if (clear) BitVector_Interval_Empty(addr,(bits-count),(bits-1));
}
}
boolean BitVector_increment(wordptr addr) /* X++ */
{
N_word size = size_(addr);
N_word mask = mask_(addr);
wordptr last = addr + size - 1;
boolean carry = TRUE;
if (size > 0)
{
*last |= NOT mask;
while (carry and (size-- > 0))
{
carry = (++(*addr++) == 0);
}
*last &= mask;
}
return(carry);
}
boolean BitVector_decrement(wordptr addr) /* X-- */
{
N_word size = size_(addr);
N_word mask = mask_(addr);
wordptr last = addr + size - 1;
boolean carry = TRUE;
if (size > 0)
{
*last &= mask;
while (carry and (size-- > 0))
{
carry = (*addr == 0);
--(*addr++);
}
*last &= mask;
}
return(carry);
}
boolean BitVector_compute(wordptr X, wordptr Y, wordptr Z, boolean minus, boolean *carry)
{
N_word size = size_(X);
N_word mask = mask_(X);
N_word vv = 0;
N_word cc;
N_word mm;
N_word yy;
N_word zz;
N_word lo;
N_word hi;
if (size > 0)
{
if (minus) cc = (*carry == 0);
else cc = (*carry != 0);
/* deal with (size-1) least significant full words first: */
while (--size > 0)
{
yy = *Y++;
if (minus) zz = (N_word) NOT ( Z ? *Z++ : 0 );
else zz = (N_word) ( Z ? *Z++ : 0 );
lo = (yy AND LSB) + (zz AND LSB) + cc;
hi = (yy >> 1) + (zz >> 1) + (lo >> 1);
cc = ((hi AND MSB) != 0);
*X++ = (hi << 1) OR (lo AND LSB);
}
/* deal with most significant word (may be used only partially): */
yy = *Y AND mask;
if (minus) zz = (N_word) NOT ( Z ? *Z : 0 );
else zz = (N_word) ( Z ? *Z : 0 );
zz &= mask;
if (mask == LSB) /* special case, only one bit used */
{
vv = cc;
lo = yy + zz + cc;
cc = (lo >> 1);
vv ^= cc;
*X = lo AND LSB;
}
else
{
if (NOT mask) /* not all bits are used, but more than one */
{
mm = (mask >> 1);
vv = (yy AND mm) + (zz AND mm) + cc;
mm = mask AND NOT mm;
lo = yy + zz + cc;
cc = (lo >> 1);
vv ^= cc;
vv &= mm;
cc &= mm;
*X = lo AND mask;
}
else /* other special case, all bits are used */
{
mm = NOT MSB;
lo = (yy AND mm) + (zz AND mm) + cc;
vv = lo AND MSB;
hi = ((yy AND MSB) >> 1) + ((zz AND MSB) >> 1) + (vv >> 1);
cc = hi AND MSB;
vv ^= cc;
*X = (hi << 1) OR (lo AND mm);
}
}
if (minus) *carry = (cc == 0);
else *carry = (cc != 0);
}
return(vv != 0);
}
boolean BitVector_add(wordptr X, wordptr Y, wordptr Z, boolean *carry)
{
return(BitVector_compute(X,Y,Z,FALSE,carry));
}
boolean BitVector_sub(wordptr X, wordptr Y, wordptr Z, boolean *carry)
{
return(BitVector_compute(X,Y,Z,TRUE,carry));
}
boolean BitVector_inc(wordptr X, wordptr Y)
{
boolean carry = TRUE;
return(BitVector_compute(X,Y,NULL,FALSE,&carry));
}
boolean BitVector_dec(wordptr X, wordptr Y)
{
boolean carry = TRUE;
return(BitVector_compute(X,Y,NULL,TRUE,&carry));
}
void BitVector_Negate(wordptr X, wordptr Y)
{
N_word size = size_(X);
N_word mask = mask_(X);
boolean carry = TRUE;
if (size > 0)
{
while (size-- > 0)
{
*X = NOT *Y++;
if (carry)
{
carry = (++(*X) == 0);
}
X++;
}