lib/bitvector/BitVector.h

   1 #ifndef MODULE_BIT_VECTOR
   2 #define MODULE_BIT_VECTOR
   3 #ifdef __cplusplus
   4 extern "C"
   5 {
   6 #endif
   7 /*****************************************************************************/
   8 /*  MODULE NAME:  BitVector.h                           MODULE TYPE:  (adt)  */
   9 /*****************************************************************************/
  10 /*  MODULE IMPORTS:                                                          */
  11 /*****************************************************************************/
  12 #include <stdlib.h>                                 /*  MODULE TYPE:  (sys)  */
  13 #include <limits.h>                                 /*  MODULE TYPE:  (sys)  */
  14 #include <string.h>                                 /*  MODULE TYPE:  (sys)  */
  15 #include <ctype.h>                                  /*  MODULE TYPE:  (sys)  */
  16 #include "ToolBox.h"                                /*  MODULE TYPE:  (dat)  */
  17 /*****************************************************************************/
  18 /*  MODULE INTERFACE:                                                        */
  19 /*****************************************************************************/
  20
  21 typedef enum
  22     {
  23         ErrCode_Ok = 0,    /* everything went allright                       */
  24
  25         ErrCode_Type,      /* types word and size_t have incompatible sizes  */
  26         ErrCode_Bits,      /* bits of word and sizeof(word) are inconsistent */
  27         ErrCode_Word,      /* size of word is less than 16 bits              */
  28         ErrCode_Long,      /* size of word is greater than size of long      */
  29         ErrCode_Powr,      /* number of bits of word is not a power of two   */
  30         ErrCode_Loga,      /* error in calculation of logarithm              */
  31
  32         ErrCode_Null,      /* unable to allocate memory                      */
  33
  34         ErrCode_Indx,      /* index out of range                             */
  35         ErrCode_Ordr,      /* minimum > maximum index                        */
  36         ErrCode_Size,      /* bit vector size mismatch                       */
  37         ErrCode_Pars,      /* input string syntax error                      */
  38         ErrCode_Ovfl,      /* numeric overflow error                         */
  39         ErrCode_Same,      /* operands must be distinct                      */
  40         ErrCode_Expo,      /* exponent must be positive                      */
  41         ErrCode_Zero       /* division by zero error                         */
  42     } ErrCode;
  43
  44 typedef wordptr *listptr;
  45
  46 /* ===> MISCELLANEOUS BASIC FUNCTIONS: <=== */
  47
  48 charptr BitVector_Error      (ErrCode error);  /* return string for err code */
  49
  50 ErrCode BitVector_Boot       (void);                 /* 0 = ok, 1..7 = error */
  51
  52 N_word  BitVector_Size       (N_int bits);  /* bit vector size (# of words)  */
  53 N_word  BitVector_Mask       (N_int bits);  /* bit vector mask (unused bits) */
  54
  55 /* ===> CLASS METHODS: <=== */
  56
  57 charptr BitVector_Version    (void);                /* return version string */
  58
  59 N_int   BitVector_Word_Bits  (void);     /* return # of bits in machine word */
  60 N_int   BitVector_Long_Bits  (void);    /* return # of bits in unsigned long */
  61
  62 /* ===> CONSTRUCTOR METHODS: <=== */
  63
  64 wordptr BitVector_Create     (N_int bits, boolean clear);          /* malloc */
  65 listptr BitVector_Create_List(N_int bits, boolean clear, N_int count);
  66
  67 wordptr BitVector_Resize     (wordptr oldaddr, N_int bits);       /* realloc */
  68
  69 wordptr BitVector_Shadow     (wordptr addr); /* make new same size but empty */
  70 wordptr BitVector_Clone      (wordptr addr);         /* make exact duplicate */
  71
  72 wordptr BitVector_Concat     (wordptr X, wordptr Y); /* return concatenation */
  73
  74 /* ===> DESTRUCTOR METHODS: <=== */
  75
  76 void    BitVector_Dispose            (charptr string);             /* string */
  77 void    BitVector_Destroy            (wordptr addr);               /* bitvec */
  78 void    BitVector_Destroy_List       (listptr list, N_int count);  /* list   */
  79
  80 /* ===> OBJECT METHODS: <=== */
  81
  82 /* ===> bit vector copy function: */
  83
  84 void    BitVector_Copy       (wordptr X, wordptr Y);              /* X = Y   */
  85
  86 /* ===> bit vector initialization: */
  87
  88 void    BitVector_Empty      (wordptr addr);                      /* X = {}  */
  89 void    BitVector_Fill       (wordptr addr);                      /* X = ~{} */
  90 void    BitVector_Flip       (wordptr addr);                      /* X = ~X  */
  91
  92 void    BitVector_Primes     (wordptr addr);
  93
  94 /* ===> miscellaneous functions: */
  95
  96 void    BitVector_Reverse    (wordptr X, wordptr Y);
  97
  98 /* ===> bit vector interval operations and functions: */
  99
 100 void    BitVector_Interval_Empty     (wordptr addr, N_int lower, N_int upper);
 101 void    BitVector_Interval_Fill      (wordptr addr, N_int lower, N_int upper);
 102 void    BitVector_Interval_Flip      (wordptr addr, N_int lower, N_int upper);
 103 void    BitVector_Interval_Reverse   (wordptr addr, N_int lower, N_int upper);
 104
 105 boolean BitVector_interval_scan_inc  (wordptr addr, N_int start,
 106                                       N_intptr min, N_intptr max);
 107 boolean BitVector_interval_scan_dec  (wordptr addr, N_int start,
 108                                       N_intptr min, N_intptr max);
 109
 110 void    BitVector_Interval_Copy      (wordptr X, wordptr Y, N_int Xoffset,
 111                                       N_int Yoffset, N_int length);
 112
 113 wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y,
 114                                       N_int Xoffset, N_int Xlength,
 115                                       N_int Yoffset, N_int Ylength);
 116
 117 /* ===> bit vector test functions: */
 118
 119 boolean BitVector_is_empty   (wordptr addr);                  /* X == {} ?   */
 120 boolean BitVector_is_full    (wordptr addr);                  /* X == ~{} ?  */
 121
 122 boolean BitVector_equal      (wordptr X, wordptr Y);          /* X == Y ?    */
 123 Z_int   BitVector_Lexicompare(wordptr X, wordptr Y);          /* X <,=,> Y ? */
 124 Z_int   BitVector_Compare    (wordptr X, wordptr Y);          /* X <,=,> Y ? */
 125
 126 /* ===> bit vector string conversion functions: */
 127
 128 charptr BitVector_to_Hex     (wordptr addr);
 129 ErrCode BitVector_from_Hex   (wordptr addr, charptr string);
 130
 131 charptr BitVector_to_Bin     (wordptr addr);
 132 ErrCode BitVector_from_Bin   (wordptr addr, charptr string);
 133
 134 charptr BitVector_to_Dec     (wordptr addr);
 135 ErrCode BitVector_from_Dec   (wordptr addr, charptr string);
 136
 137 charptr BitVector_to_Enum    (wordptr addr);
 138 ErrCode BitVector_from_Enum  (wordptr addr, charptr string);
 139
 140 /* ===> bit vector bit operations, functions & tests: */
 141
 142 void    BitVector_Bit_Off    (wordptr addr, N_int index); /*  X = X \ {x}    */
 143 void    BitVector_Bit_On     (wordptr addr, N_int index); /*  X = X + {x}    */
 144 boolean BitVector_bit_flip   (wordptr addr, N_int index); /* (X+{x})\(X*{x}) */
 145
 146 boolean BitVector_bit_test   (wordptr addr, N_int index); /*  {x} in X ?     */
 147
 148 void    BitVector_Bit_Copy   (wordptr addr, N_int index, boolean bit);
 149
 150 /* ===> bit vector bit shift & rotate functions: */
 151
 152 void    BitVector_LSB                (wordptr addr, boolean bit);
 153 void    BitVector_MSB                (wordptr addr, boolean bit);
 154 boolean BitVector_lsb_               (wordptr addr);
 155 boolean BitVector_msb_               (wordptr addr);
 156 boolean BitVector_rotate_left        (wordptr addr);
 157 boolean BitVector_rotate_right       (wordptr addr);
 158 boolean BitVector_shift_left         (wordptr addr, boolean carry_in);
 159 boolean BitVector_shift_right        (wordptr addr, boolean carry_in);
 160 void    BitVector_Move_Left          (wordptr addr, N_int bits);
 161 void    BitVector_Move_Right         (wordptr addr, N_int bits);
 162
 163 /* ===> bit vector insert/delete bits: */
 164
 165 void    BitVector_Insert     (wordptr addr, N_int offset, N_int count,
 166                               boolean clear);
 167 void    BitVector_Delete     (wordptr addr, N_int offset, N_int count,
 168                               boolean clear);
 169
 170 /* ===> bit vector arithmetic: */
 171
 172 boolean BitVector_increment  (wordptr addr);                        /*  X++  */
 173 boolean BitVector_decrement  (wordptr addr);                        /*  X--  */
 174
 175 boolean BitVector_compute    (wordptr X, wordptr Y, wordptr Z, boolean minus,
 176                                                                boolean *carry);
 177 boolean BitVector_add        (wordptr X, wordptr Y, wordptr Z, boolean *carry);
 178 boolean BitVector_sub        (wordptr X, wordptr Y, wordptr Z, boolean *carry);
 179 boolean BitVector_inc        (wordptr X, wordptr Y);
 180 boolean BitVector_dec        (wordptr X, wordptr Y);
 181
 182 void    BitVector_Negate     (wordptr X, wordptr Y);
 183 void    BitVector_Absolute   (wordptr X, wordptr Y);
 184 Z_int   BitVector_Sign       (wordptr addr);
 185 ErrCode BitVector_Mul_Pos    (wordptr X, wordptr Y, wordptr Z, boolean strict);
 186 ErrCode BitVector_Multiply   (wordptr X, wordptr Y, wordptr Z);
 187 ErrCode BitVector_Div_Pos    (wordptr Q, wordptr X, wordptr Y, wordptr R);
 188 ErrCode BitVector_Divide     (wordptr Q, wordptr X, wordptr Y, wordptr R);
 189 ErrCode BitVector_GCD        (wordptr X, wordptr Y, wordptr Z);
 190 ErrCode BitVector_GCD2       (wordptr U, wordptr V, wordptr W,      /*   O   */
 191                                          wordptr X, wordptr Y);     /*   I   */
 192 ErrCode BitVector_Power      (wordptr X, wordptr Y, wordptr Z);
 193
 194 /* ===> direct memory access functions: */
 195
 196 void    BitVector_Block_Store(wordptr addr, charptr buffer, N_int length);
 197 charptr BitVector_Block_Read (wordptr addr, N_intptr length);
 198
 199 /* ===> word array functions: */
 200
 201 void    BitVector_Word_Store (wordptr addr, N_int offset, N_int value);
 202 N_int   BitVector_Word_Read  (wordptr addr, N_int offset);
 203
 204 void    BitVector_Word_Insert(wordptr addr, N_int offset, N_int count,
 205                               boolean clear);
 206 void    BitVector_Word_Delete(wordptr addr, N_int offset, N_int count,
 207                               boolean clear);
 208
 209 /* ===> arbitrary size chunk functions: */
 210
 211 void    BitVector_Chunk_Store(wordptr addr, N_int chunksize,
 212                               N_int offset, N_long value);
 213 N_long  BitVector_Chunk_Read (wordptr addr, N_int chunksize,
 214                               N_int offset);
 215
 216 /* ===> set operations: */
 217
 218 void    Set_Union            (wordptr X, wordptr Y, wordptr Z); /* X = Y + Z */
 219 void    Set_Intersection     (wordptr X, wordptr Y, wordptr Z); /* X = Y * Z */
 220 void    Set_Difference       (wordptr X, wordptr Y, wordptr Z); /* X = Y \ Z */
 221 void    Set_ExclusiveOr      (wordptr X, wordptr Y, wordptr Z); /*(Y+Z)\(Y*Z)*/
 222 void    Set_Complement       (wordptr X, wordptr Y);            /* X = ~Y    */
 223
 224 /* ===> set functions: */
 225
 226 boolean Set_subset           (wordptr X, wordptr Y);            /* X in Y ?  */
 227
 228 N_int   Set_Norm             (wordptr addr);                    /* = | X |   */
 229 N_int   Set_Norm2            (wordptr addr);                    /* = | X |   */
 230 N_int   Set_Norm3            (wordptr addr);                    /* = | X |   */
 231 Z_long  Set_Min              (wordptr addr);                    /* = min(X)  */
 232 Z_long  Set_Max              (wordptr addr);                    /* = max(X)  */
 233
 234 /* ===> matrix-of-booleans operations: */
 235
 236 void    Matrix_Multiplication(wordptr X, N_int rowsX, N_int colsX,
 237                               wordptr Y, N_int rowsY, N_int colsY,
 238                               wordptr Z, N_int rowsZ, N_int colsZ);
 239
 240 void    Matrix_Product       (wordptr X, N_int rowsX, N_int colsX,
 241                               wordptr Y, N_int rowsY, N_int colsY,
 242                               wordptr Z, N_int rowsZ, N_int colsZ);
 243
 244 void    Matrix_Closure       (wordptr addr, N_int rows, N_int cols);
 245
 246 void    Matrix_Transpose     (wordptr X, N_int rowsX, N_int colsX,
 247                               wordptr Y, N_int rowsY, N_int colsY);
 248
 249 /*****************************************************************************/
 250 /*  MODULE RESOURCES:                                                        */
 251 /*****************************************************************************/
 252
 253 #define bits_(BitVector) *(BitVector-3)
 254 #define size_(BitVector) *(BitVector-2)
 255 #define mask_(BitVector) *(BitVector-1)
 256
 257 #define  ERRCODE_TYPE  "sizeof(word) > sizeof(size_t)"
 258 #define  ERRCODE_BITS  "bits(word) != sizeof(word)*8"
 259 #define  ERRCODE_WORD  "bits(word) < 16"
 260 #define  ERRCODE_LONG  "bits(word) > bits(long)"
 261 #define  ERRCODE_POWR  "bits(word) != 2^x"
 262 #define  ERRCODE_LOGA  "bits(word) != 2^ld(bits(word))"
 263 #define  ERRCODE_NULL  "unable to allocate memory"
 264 #define  ERRCODE_INDX  "index out of range"
 265 #define  ERRCODE_ORDR  "minimum > maximum index"
 266 #define  ERRCODE_SIZE  "bit vector size mismatch"
 267 #define  ERRCODE_PARS  "input string syntax error"
 268 #define  ERRCODE_OVFL  "numeric overflow error"
 269 #define  ERRCODE_SAME  "result vector(s) must be distinct"
 270 #define  ERRCODE_EXPO  "exponent must be positive"
 271 #define  ERRCODE_ZERO  "division by zero error"
 272 #define  ERRCODE_OOPS  "unexpected internal error - please contact author"
 273
 274 extern const N_int BitVector_BYTENORM[256];
 275 /*
 276 {
 277     0x00, 0x01, 0x01, 0x02,  0x01, 0x02, 0x02, 0x03,
 278     0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
 279     0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
 280     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 281     0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
 282     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 283     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 284     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 285     0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
 286     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 287     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 288     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 289     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 290     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 291     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 292     0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
 293     0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
 294     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 295     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 296     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 297     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 298     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 299     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 300     0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
 301     0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
 302     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 303     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 304     0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
 305     0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
 306     0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
 307     0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
 308     0x05, 0x06, 0x06, 0x07,  0x06, 0x07, 0x07, 0x08
 309 };
 310 */
 311
 312 /*****************************************************************************/
 313 /*  MODULE IMPLEMENTATION:                                                   */
 314 /*****************************************************************************/
 315
 316 /*****************************************************************************/
 317 /*  VERSION:  6.4                                                            */
 318 /*****************************************************************************/
 319 /*  VERSION HISTORY:                                                         */
 320 /*****************************************************************************/
 321 /*                                                                           */
 322 /*    Version 6.4  03.10.04  Added C++ comp. directives. Improved "Norm()".  */
 323 /*    Version 6.3  28.09.02  Added "Create_List()" and "GCD2()".             */
 324 /*    Version 6.2  15.09.02  Overhauled error handling. Fixed "GCD()".       */
 325 /*    Version 6.1  08.10.01  Make VMS linker happy: _lsb,_msb => _lsb_,_msb_ */
 326 /*    Version 6.0  08.10.00  Corrected overflow handling.                    */
 327 /*    Version 5.8  14.07.00  Added "Power()". Changed "Copy()".              */
 328 /*    Version 5.7  19.05.99  Quickened "Div_Pos()". Added "Product()".       */
 329 /*    Version 5.6  02.11.98  Leading zeros eliminated in "to_Hex()".         */
 330 /*    Version 5.5  21.09.98  Fixed bug of uninitialized "error" in Multiply. */
 331 /*    Version 5.4  07.09.98  Fixed bug of uninitialized "error" in Divide.   */
 332 /*    Version 5.3  12.05.98  Improved Norm. Completed history.               */
 333 /*    Version 5.2  31.03.98  Improved Norm.                                  */
 334 /*    Version 5.1  09.03.98  No changes.                                     */
 335 /*    Version 5.0  01.03.98  Major additions and rewrite.                    */
 336 /*    Version 4.2  16.07.97  Added is_empty, is_full.                        */
 337 /*    Version 4.1  30.06.97  Added word-ins/del, move-left/right, inc/dec.   */
 338 /*    Version 4.0  23.04.97  Rewrite. Added bit shift and bool. matrix ops.  */
 339 /*    Version 3.2  04.02.97  Added interval methods.                         */
 340 /*    Version 3.1  21.01.97  Fixed bug on 64 bit machines.                   */
 341 /*    Version 3.0  12.01.97  Added flip.                                     */
 342 /*    Version 2.0  14.12.96  Efficiency and consistency improvements.        */
 343 /*    Version 1.1  08.01.96  Added Resize and ExclusiveOr.                   */
 344 /*    Version 1.0  14.12.95  First version under UNIX (with Perl module).    */
 345 /*    Version 0.9  01.11.93  First version of C library under MS-DOS.        */
 346 /*    Version 0.1  ??.??.89  First version in Turbo Pascal under CP/M.       */
 347 /*                                                                           */
 348 /*****************************************************************************/
 349 /*  AUTHOR:                                                                  */
 350 /*****************************************************************************/
 351 /*                                                                           */
 352 /*    Steffen Beyer                                                          */
 353 /*    mailto:sb@engelschall.com                                              */
 354 /*    http://www.engelschall.com/u/sb/download/                              */
 355 /*                                                                           */
 356 /*****************************************************************************/
 357 /*  COPYRIGHT:                                                               */
 358 /*****************************************************************************/
 359 /*                                                                           */
 360 /*    Copyright (c) 1995 - 2004 by Steffen Beyer.                            */
 361 /*    All rights reserved.                                                   */
 362 /*                                                                           */
 363 /*****************************************************************************/
 364 /*  LICENSE:                                                                 */
 365 /*****************************************************************************/
 366 /*                                                                           */
 367 /*    This library is free software; you can redistribute it and/or          */
 368 /*    modify it under the terms of the GNU Library General Public            */
 369 /*    License as published by the Free Software Foundation; either           */
 370 /*    version 2 of the License, or (at your option) any later version.       */
 371 /*                                                                           */
 372 /*    This library is distributed in the hope that it will be useful,        */
 373 /*    but WITHOUT ANY WARRANTY; without even the implied warranty of         */
 374 /*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU       */
 375 /*    Library General Public License for more details.                       */
 376 /*                                                                           */
 377 /*    You should have received a copy of the GNU Library General Public      */
 378 /*    License along with this library; if not, write to the                  */
 379 /*    Free Software Foundation, Inc.,                                        */
 380 /*    59 Temple Place, Suite 330, Boston, MA 02111-1307 USA                  */
 381 /*                                                                           */
 382 /*    or download a copy from ftp://ftp.gnu.org/pub/gnu/COPYING.LIB-2.0      */
 383 /*                                                                           */
 384 /*****************************************************************************/
 385 #ifdef __cplusplus
 386 }
 387 #endif
 388 #endif