1 # Copyright (C) 2012 Martin A. Hansen.
3 # This program is free software; you can redistribute it and/or
4 # modify it under the terms of the GNU General Public License
5 # as published by the Free Software Foundation; either version 2
6 # of the License, or (at your option) any later version.
8 # This program is distributed in the hope that it will be useful,
9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 # GNU General Public License for more details.
13 # You should have received a copy of the GNU General Public License
14 # along with this program; if not, write to the Free Software
15 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 # http://www.gnu.org/copyleft/gpl.html
19 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
21 # This software is part of the Biopieces framework (www.biopieces.org).
23 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
27 CHAR_BIT = 8 # This is not guaranteed! FIXME
28 BITS_PER_WORD = 64 # This is not portable! FIXME
30 # Error class for all exceptions to do with BitMap.
31 class BitMapError < StandardError; end
33 # Bitmap - 13 columns, 3 rows:
38 attr_reader :cols, :rows, :map, :width
40 # Method to initialize a BitMap.
41 def initialize(cols, rows)
45 @width = @cols + @pads
49 # Method that set bits to 1 at specified columns, and rows.
52 # set([0, 4, 5], true)
55 # TODO: set([1 .. -2], true)
57 cols = cols_expand(cols)
58 rows = rows_expand(rows)
60 set_c(@map, @width, cols, rows)
63 # Method that set bits to 0 at specified columns, and rows.
66 # unset([0, 4, 5], true)
67 # unset([0 .. 4], true)
68 # TODO: unset(-1, true)
69 # TODO: unset([1 .. -2], true)
71 cols = cols_expand(cols)
72 rows = rows_expand(rows)
74 unset_c(@map, @width, cols, rows)
78 size = @rows * @width / BITS_PER_WORD
83 sum_rows_c(@map, @width, rows)
86 # Method to get a slice from a bitmap from specified rows and columns,
87 # and return this slice as a new BitMap object.
90 # slice([0, 4, 5], true)
91 # slice([0 .. 4], true)
92 # TODO: slice(-1, true)
93 # TODO: slice([1 .. -2], true)
95 cols = cols_expand(cols)
96 rows = rows_expand(rows)
97 bm = BitMap.new(cols.size, rows.size)
99 slice_c(@map, @width, bm.map, bm.width, cols, rows)
104 # Method that performs bit wise and operation between:
105 # 1: an entire bit map.
107 # 3: a bit map column.
108 # The result is saved in self.
110 bm = BitMap.new(@cols, @rows)
112 if @rows == bit_map.rows and @cols == bit_map.cols
115 elsif @rows == bit_map.rows
118 elsif @cols == bit_map.cols
119 bitwise_and_row_c(@map, bm.map, bit_map.map, @width, @rows)
121 raise BitMapError, "can't & uneven bit maps: #{@rows} x #{@cols} & #{bit_map.rows} x #{bit_map.cols}"
128 btest_c(@map, @width, c, r)
131 # Method to convert a bit array to a string.
137 (0 ... @rows).each do |r|
139 (0 ... @cols).each do |c|
148 row = row[0 ... max_cols] + " ... (#{@cols})"
151 if rows.size > max_rows
166 if (@cols % BITS_PER_WORD) != 0
167 pads = BITS_PER_WORD - (@cols % BITS_PER_WORD)
175 # Method to initialize a block of memory holding a bitmap.
176 # The block will be initialized as a zeroed Ruby string, but
177 # will be padded with 0's so that each row is a multiplum of
178 # BITS_PER_WORD - which is 64 or 32 bits.
180 size = @rows * @width / CHAR_BIT
185 def rows_expand(rows)
189 rows = (0 ... @rows).to_a
190 elsif rows.is_a? Array and rows.first.is_a? Range
191 rows = rows.first.to_a
192 rows = [0] if rows.empty? # FIXME
195 raise BitMapError, "row outside bitmap: #{rows.first}" if rows.first < 0
196 raise BitMapError, "row outside bitmap: #{rows.last}" if rows.last >= @rows
201 def cols_expand(cols)
205 cols = (0 ... @cols).to_a
206 elsif cols.is_a? Array and cols.first.is_a? Range
207 cols = cols.first.to_a
210 raise BitMapError, "column outside bitmap: #{cols.first}" if cols.first < 0
211 raise BitMapError, "column outside bitmap: #{cols.last}" if cols.last >= @cols
217 builder.add_static "rows", 'rb_intern("@rows")', "ID"
218 builder.add_static "cols", 'rb_intern("@cols")', "ID"
219 builder.add_static "byte_array", 'rb_intern("@byte_array")', "ID"
223 typedef uint64_t word_t;
228 enum { BITS_PER_WORD = sizeof(word_t) * CHAR_BIT };
233 #define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
238 #define BIT_OFFSET(b) ((b) % BITS_PER_WORD)
241 # Method to count all set bits in an unsigned long int (64 bits)
242 # based on a variant of pop_count optimal for bits with most 0
245 int count_bits_c(word_t x) {
248 for (count = 0; x; count++)
257 void bit_set_c(word_t *map, int pos) {
258 map[WORD_OFFSET(pos)] |= (1 << BIT_OFFSET(pos));
264 void bit_unset_c(word_t *map, int pos) {
265 map[WORD_OFFSET(pos)] &= ~(1 << BIT_OFFSET(pos));
270 void set_c(VALUE _map, VALUE _width, VALUE _cols_ary, VALUE _rows_ary)
272 word_t *map = (word_t *) StringValuePtr(_map);
273 int width = NUM2INT(_width);
274 VALUE *cols_ary = RARRAY_PTR(_cols_ary);
275 VALUE *rows_ary = RARRAY_PTR(_rows_ary);
276 int col_ary_size = (int) RARRAY_LEN(_cols_ary);
277 int row_ary_size = (int) RARRAY_LEN(_rows_ary);
282 for (r = 0; r < row_ary_size; r++)
284 for (c = 0; c < col_ary_size; c++)
286 pos = NUM2INT(rows_ary[r]) * width + NUM2INT(cols_ary[c]);
295 void unset_c(VALUE _map, VALUE _width, VALUE _cols_ary, VALUE _rows_ary)
297 word_t *map = (word_t *) StringValuePtr(_map);
298 int width = NUM2INT(_width);
299 VALUE *cols_ary = RARRAY_PTR(_cols_ary);
300 VALUE *rows_ary = RARRAY_PTR(_rows_ary);
301 int cols_ary_size = (int) RARRAY_LEN(_cols_ary);
302 int rows_ary_size = (int) RARRAY_LEN(_rows_ary);
307 for (r = 0; r < rows_ary_size; r++)
309 for (c = 0; c < cols_ary_size; c++)
311 pos = NUM2INT(rows_ary[r]) * width + NUM2INT(cols_ary[c]);
313 bit_unset_c(map, pos);
321 int bit_test_c(word_t* map, int pos)
323 word_t bit = map[WORD_OFFSET(pos)] & (1 << BIT_OFFSET(pos));
331 VALUE btest_c(VALUE _map, VALUE _width, VALUE _col, VALUE _row)
333 word_t *map = (word_t*) StringValuePtr(_map);
334 int width = NUM2INT(_width);
335 int col = NUM2INT(_col);
336 int row = NUM2INT(_row);
337 int pos = row * width + col;
339 return bit_test_c(map, pos);
344 void slice_c(VALUE _old_map, VALUE _old_width, VALUE _new_map, VALUE _new_width, VALUE _cols_ary, VALUE _rows_ary)
346 word_t *old_map = (word_t*) StringValuePtr(_old_map);
347 int old_width = NUM2INT(_old_width);
348 word_t *new_map = (word_t*) StringValuePtr(_new_map);
349 int new_width = NUM2INT(_new_width);
350 VALUE *cols_ary = RARRAY_PTR(_cols_ary);
351 VALUE *rows_ary = RARRAY_PTR(_rows_ary);
352 int cols_ary_size = (int) RARRAY_LEN(_cols_ary);
353 int rows_ary_size = (int) RARRAY_LEN(_rows_ary);
359 for (r = 0; r < rows_ary_size; r++)
361 for (c = 0; c < cols_ary_size; c++)
363 old_pos = NUM2INT(rows_ary[r]) * old_width + NUM2INT(cols_ary[c]);
365 if (bit_test_c(old_map, old_pos))
367 new_pos = r * new_width + c;
368 bit_set_c(new_map, new_pos);
376 void bitwise_and_row_c(VALUE _old_map, VALUE _new_map, VALUE _row_map, VALUE _width, VALUE _rows)
378 word_t *old_map = (word_t*) StringValuePtr(_old_map);
379 word_t *new_map = (word_t*) StringValuePtr(_new_map);
380 word_t *row_map = (word_t*) StringValuePtr(_row_map);
381 int width = NUM2INT(_width);
382 int rows = NUM2INT(_rows);
383 int size = width / BITS_PER_WORD;
387 for (r = 0; r < rows; r++)
389 for (c = 0; c < size; c++) {
390 new_map[r * size + c] = old_map[r * size + c] & row_map[c];
397 VALUE sum_c(VALUE _map, VALUE _size)
399 word_t *map = (word_t*) StringValuePtr(_map);
400 int size = NUM2INT(_size);
404 for (i = 0; i < size; i++)
405 sum += count_bits_c(map[i]);
412 VALUE sum_rows_c(VALUE _map, VALUE _width, VALUE _rows)
414 word_t *map = (word_t*) StringValuePtr(_map);
415 int width = NUM2INT(_width);
416 int rows = NUM2INT(_rows);
420 VALUE sums_ary = rb_ary_new();
421 int size = width / BITS_PER_WORD;
424 for (r = 0; r < rows; r++) sums[r] = 0;
426 for (r = 0; r < rows; r++)
428 for (c = 0; c < size; c++) {
431 sums[r] += count_bits_c(map[pos]);
435 for (r = 0; r < rows; r++) rb_ary_push(sums_ary, INT2FIX(sums[r]));