Merge branch 'release-2.140.101'
[feisty_meow.git] / 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.