nucleus/library/structures/bit_vector.cpp

   1 /*****************************************************************************\
   2 *                                                                             *
   3 *  Name   : bit_vector                                                        *
   4 *  Author : Chris Koeritz                                                     *
   5 *                                                                             *
   6 *******************************************************************************
   7 * Copyright (c) 1990-$now By Author.  This program is free software; you can  *
   8 * redistribute it and/or modify it under the terms of the GNU General Public  *
   9 * License as published by the Free Software Foundation; either version 2 of   *
  10 * the License or (at your option) any later version.  This is online at:      *
  11 *     http://www.fsf.org/copyleft/gpl.html                                    *
  12 * Please send any updates to: fred@gruntose.com                               *
  13 \*****************************************************************************/
  14
  15 #include "bit_vector.h"
  16
  17 #include <basis/byte_array.h>
  18 #include <basis/definitions.h>
  19 #include <basis/functions.h>
  20 #include <basis/guards.h>
  21
  22 //#define DEBUG_BIT_VECTOR
  23   // uncomment this to get debugging noise.
  24
  25 #undef LOG
  26 #ifdef DEBUG_BIT_VECTOR
  27   #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), s)
  28 #else
  29   #define LOG(s) {}
  30 #endif
  31
  32 using namespace basis;
  33
  34 namespace structures {
  35
  36 bit_vector::bit_vector()
  37 : _implementation(new byte_array(0, NULL_POINTER)), _number_of_bits(0)
  38 {}
  39
  40 bit_vector::bit_vector(int number_of_bits, const abyte *initial)
  41 : _implementation(new byte_array(0, NULL_POINTER)), _number_of_bits(0)
  42 {
  43   reset(number_of_bits);
  44   if (!initial) return;
  45   _implementation->reset(number_of_packets(number_of_bits,
  46       int(BITS_PER_BYTE)), initial);
  47 }
  48
  49 bit_vector::bit_vector(const bit_vector &to_copy)
  50 : _implementation(new byte_array(*to_copy._implementation)),
  51   _number_of_bits(to_copy._number_of_bits)
  52 {}
  53
  54 bit_vector::~bit_vector() { WHACK(_implementation); }
  55
  56 bit_vector &bit_vector::operator = (const bit_vector &to_copy)
  57 {
  58   if (this == &to_copy) return *this;
  59   *_implementation = *to_copy._implementation;
  60   _number_of_bits = to_copy._number_of_bits;
  61   return *this;
  62 }
  63
  64 bit_vector::operator const byte_array & () const { return *_implementation; }
  65
  66 int bit_vector::bits() const { return _number_of_bits; }
  67
  68 bool bit_vector::whole() const { return negative(find_first(0)); }
  69
  70 bool bit_vector::empty() const { return negative(find_first(1)); }
  71
  72 bool bit_vector::operator == (const bit_vector &that) const
  73 { return compare(that, 0, _number_of_bits); }
  74
  75 bool bit_vector::on(int position) const
  76 { return get_bit(into_two_dim(position)); }
  77
  78 bool bit_vector::off(int position) const { return !on(position); }
  79
  80 void bit_vector::resize(int number_of_bits)
  81 {
  82 //printf("resize invoked, old size %d, new size %d...\n", bits(), number_of_bits);
  83   if (negative(number_of_bits)) return;
  84   if (bits() == number_of_bits) return;
  85   int old_size = bits();
  86   _number_of_bits = number_of_bits;
  87   int number_of_bytes = number_of_packets(number_of_bits, int(BITS_PER_BYTE));
  88   _implementation->resize(number_of_bytes);
  89   // clear new space if the vector got larger.
  90   if (old_size < number_of_bits) {
  91     // lazy reset doesn't compute byte boundary, just does 8 bits.
  92     for (int i = old_size; i < old_size + 8; i++) {
  93       clear(i);
  94 //printf("clearing bit %d.\n", i);
  95     }
  96     // clear the bytes remaining.
  97     int old_bytes = number_of_packets(old_size + 8, int(BITS_PER_BYTE));
  98     for (int j = old_bytes; j < number_of_bytes; j++) {
  99 //printf("clearing bit %d through %d.\n", j * 8, j * 8 + 7);
 100       _implementation->use(j) = 0;
 101     }
 102   }
 103 }
 104
 105 void bit_vector::reset(int number_of_bits)
 106 {
 107   resize(number_of_bits);
 108   memset(_implementation->access(), 0, _implementation->length());
 109 }
 110
 111 bit_vector::two_dim_location bit_vector::into_two_dim(int position) const
 112 {
 113   two_dim_location to_return;
 114   to_return.c_byte = position / BITS_PER_BYTE;
 115   to_return.c_offset = position % BITS_PER_BYTE;
 116   return to_return;
 117 }
 118
 119 bool bit_vector::get_bit(const two_dim_location &pos_in2) const
 120 {
 121   bounds_return(pos_in2.c_byte * BITS_PER_BYTE + pos_in2.c_offset, 0,
 122     _number_of_bits - 1, false);
 123   abyte test_mask = abyte(1 << pos_in2.c_offset);
 124   return TEST(abyte(_implementation->get(pos_in2.c_byte)), test_mask);
 125 }
 126
 127 void bit_vector::set_bit(int position, bool value)
 128 {
 129   bounds_return(position, 0, bits() - 1, );
 130   set_bit(into_two_dim(position), value);
 131 }
 132
 133 void bit_vector::set_bit(const two_dim_location &pos_in2, bool set_it)
 134 {
 135   abyte test_mask = abyte(1 << pos_in2.c_offset);
 136   if (set_it) SET(_implementation->use(pos_in2.c_byte), test_mask);
 137   else CLEAR((abyte &)_implementation->get(pos_in2.c_byte), test_mask);
 138 }
 139
 140 bool bit_vector::operator [](int position) const
 141 {
 142   bounds_return(position, 0, _number_of_bits - 1, false);
 143   return get_bit(into_two_dim(position));
 144 }
 145
 146 void bit_vector::light(int position)
 147 {
 148   bounds_return(position, 0, _number_of_bits - 1, );
 149   set_bit(into_two_dim(position), true);
 150 }
 151
 152 void bit_vector::clear(int position)
 153 {
 154   bounds_return(position, 0, _number_of_bits - 1, );
 155   set_bit(into_two_dim(position), false);
 156 }
 157
 158 int bit_vector::find_first(bool to_find) const
 159 {
 160   const abyte whole_set = abyte(0xFF);
 161   // search through the whole bytes first.
 162   for (int full_byte = 0; full_byte < _implementation->length(); full_byte++) {
 163     if ( (to_find && _implementation->get(full_byte))
 164          || (!to_find && (_implementation->get(full_byte) != whole_set)) ) {
 165       // the first appropriate byte is searched for the first appropriate bit.
 166       for (int i = full_byte * BITS_PER_BYTE; i < minimum
 167           (int(_number_of_bits), (full_byte+1)*BITS_PER_BYTE); i++) {
 168         if (on(i) == to_find) return i;
 169       }
 170       return common::NOT_FOUND;
 171     }
 172   }
 173   return common::NOT_FOUND;
 174 }
 175
 176 bool bit_vector::compare(const bit_vector &that, int start, int stop) const
 177 {
 178   for (int i = start; i <= stop; i++) {
 179     if (on(i) != that.on(i)) return false;
 180   }
 181   return true;
 182 }
 183
 184 astring bit_vector::text_form() const
 185 {
 186   astring to_return;
 187   int bits_on_line = 0;
 188   const int estimated_elements_on_line = 64;
 189   for (int i = 0; i < _number_of_bits; i++) {
 190     // below prints out the bit number heading.
 191     if (bits_on_line == 0) {
 192       if (i != 0) to_return += "\n";
 193       if (i < 10000) to_return += " ";
 194       if (i < 1000) to_return += " ";
 195       if (i < 100) to_return += " ";
 196       if (i < 10) to_return += " ";
 197       to_return += a_sprintf("%d", i);
 198       to_return += " | ";
 199     }
 200     if (on(i)) to_return += "1";
 201     else to_return += "0";
 202     bits_on_line++;
 203     if (bits_on_line >= estimated_elements_on_line) bits_on_line = 0;
 204     else if ( !(bits_on_line % BITS_PER_BYTE) ) to_return += " ";
 205   }
 206   to_return += "\n";
 207   return to_return;
 208 }
 209
 210 bit_vector bit_vector::subvector(int start, int end) const
 211 {
 212   bounds_return(start, 0, bits() - 1, bit_vector());
 213   bounds_return(end, 0, bits() - 1, bit_vector());
 214   int size = end - start + 1;
 215   bit_vector to_return(size);
 216   for (int i = start; i <= end; i++) to_return.set_bit(i - start, on(i));
 217   return to_return;
 218 }
 219
 220 bool bit_vector::overwrite(int start, const bit_vector &to_write)
 221 {
 222   bounds_return(start, 0, bits() - 1, false);
 223   int end = start + to_write.bits() - 1;
 224   bounds_return(end, 0, bits() - 1, false);
 225   for (int i = start; i <= end; i++) set_bit(i, to_write[i - start]);
 226   return true;
 227 }
 228
 229 enum endian { LEFT_ENDIAN, RIGHT_ENDIAN };
 230 endian host_byte_order = LEFT_ENDIAN;  // bytes within words.
 231 endian host_bit_order = LEFT_ENDIAN;  // bits within bytes.
 232
 233 // probably the treatment for right endian in either case
 234 // of bytes or bits is wrong.
 235
 236 bool bit_vector::set(int start, int size, basis::un_int source)
 237 {
 238   bounds_return(start, 0, bits() - 1, false);
 239   int end = start + size - 1;
 240   bounds_return(end, 0, bits() - 1, false);
 241   bounds_return(size, 1, 32, false);
 242   bit_vector from_int(32, (abyte *)&source);
 243
 244 // is this algorithm even remotely near the truth?
 245   if (host_bit_order == RIGHT_ENDIAN)
 246     from_int._implementation->resize(size, byte_array::NEW_AT_BEGINNING);
 247   else from_int.resize(size);  // left endian machine.
 248   overwrite(start, from_int);
 249   return true;
 250 }
 251
 252 basis::un_int bit_vector::get(int start, int size) const
 253 {
 254   int end = start + size - 1;
 255   bit_vector segment = subvector(start, end);
 256   // padding to bytes.
 257   int new_length = segment.bits();
 258   if (new_length % 8) {
 259     new_length = ( (new_length+8) / 8) * 8;
 260     LOG(a_sprintf("new size is %d.", new_length));
 261   }
 262   segment.resize(new_length);
 263
 264   if (host_bit_order == RIGHT_ENDIAN) {
 265     bit_vector new_segment(segment.bits());
 266     for (int i = 0; i < segment.bits(); i += 8)
 267       for (int j = i; j < i + BITS_PER_BYTE; j++)
 268         if (j < segment.bits())
 269           new_segment.set_bit(i + (7 - (j - i)), segment[j]);
 270     segment = new_segment;  // copy the new form.
 271   }
 272
 273   LOG("new seg after bit copy:");
 274   LOG(segment);
 275
 276   basis::un_int to_return = 0;
 277
 278   int bytes_used = number_of_packets(segment.bits(), int(BITS_PER_BYTE));
 279   // 4 = # of bytes in a int.
 280   for (int i = minimum(4, bytes_used) - 1; i >= 0; i--) {
 281 #ifdef DEBUG_BIT_VECTOR
 282     bit_vector tmp(8, &segment._implementation->get(i));
 283     LOG(a_sprintf("%d: src bits %s", i, tmp.text_form().s()));
 284 #endif
 285
 286 #ifdef DEBUG_BIT_VECTOR
 287     bit_vector tmp4(32, (abyte *)&to_return);
 288     LOG(a_sprintf("%d: pre shift dest %s", i, tmp4.text_form().s()));
 289 #endif
 290     if (host_byte_order == LEFT_ENDIAN) to_return <<= 8;
 291     else to_return >>= 8;
 292 #ifdef DEBUG_BIT_VECTOR
 293     bit_vector tmp5(32, (abyte *)&to_return);
 294     LOG(a_sprintf("%d: post shift dest %s", i, tmp5.text_form().s()));
 295 #endif
 296
 297     basis::un_int mask = segment._implementation->get(i);
 298     if (host_byte_order == RIGHT_ENDIAN) mask <<= 23;
 299 #ifdef DEBUG_BIT_VECTOR
 300     bit_vector tmp3(32, (abyte *)&to_return);
 301     LOG(a_sprintf("%d: pre dest bits %s", i, tmp3.text_form().s()));
 302 #endif
 303     SET(to_return, mask);
 304 #ifdef DEBUG_BIT_VECTOR
 305     bit_vector tmp2(32, (abyte *)&to_return);
 306     LOG(a_sprintf("%d: post dest bits %s", i, tmp2.text_form().s()));
 307 #endif
 308   }
 309
 310 #ifdef DEBUG_BIT_VECTOR
 311   bit_vector tmp(32, (abyte *)&to_return);
 312   LOG(a_sprintf("final bits %s", tmp.text_form().s()));
 313 #endif
 314   return to_return;
 315 }
 316
 317 } //namespace.