code_ruby/lib/maasha/bitmap.rb

   1 # Copyright (C) 2012 Martin A. Hansen.
   2
   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.
   7
   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.
  12
  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.
  16
  17 # http://www.gnu.org/copyleft/gpl.html
  18
  19 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  20
  21 # This software is part of the Biopieces framework (www.biopieces.org).
  22
  23 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  24
  25 require 'inline'
  26
  27 CHAR_BIT      = 8    # This is not guaranteed! FIXME
  28 BITS_PER_WORD = 64   # This is not portable!   FIXME
  29
  30 # Error class for all exceptions to do with BitMap.
  31 class BitMapError < StandardError; end
  32
  33 # Bitmap - 13 columns, 3 rows:
  34 # 1000000000000
  35 # 0000001000000
  36 # 0000000000001
  37 class BitMap
  38   attr_reader :cols, :rows, :map, :width
  39
  40   # Method to initialize a BitMap.
  41   def initialize(cols, rows)
  42     @cols  = cols
  43     @rows  = rows
  44     @pads  = pad_init
  45     @width = @cols + @pads
  46     @map   = map_init
  47   end
  48
  49   # Method that set bits to 1 at specified columns, and rows.
  50   # Usage: set(1, 4)
  51   #        set(true, 4)
  52   #        set([0, 4, 5], true)
  53   #        set([0 .. 4], true)
  54   # TODO:  set(-1, true)
  55   # TODO:  set([1 .. -2], true)
  56   def set(cols, rows)
  57     cols = cols_expand(cols)
  58     rows = rows_expand(rows)
  59
  60     set_c(@map, @width, cols, rows)
  61   end
  62
  63   # Method that set bits to 0 at specified columns, and rows.
  64   # Usage: unset(1, 4)
  65   #        unset(true, 4)
  66   #        unset([0, 4, 5], true)
  67   #        unset([0 .. 4], true)
  68   # TODO:  unset(-1, true)
  69   # TODO:  unset([1 .. -2], true)
  70   def unset(cols, rows)
  71     cols = cols_expand(cols)
  72     rows = rows_expand(rows)
  73
  74     unset_c(@map, @width, cols, rows)
  75   end
  76
  77   def sum
  78     size = @rows * @width / BITS_PER_WORD
  79     sum_c(@map, size)
  80   end
  81
  82   def sum_rows
  83     sum_rows_c(@map, @width, rows)
  84   end
  85
  86   # Method to get a slice from a bitmap from specified rows and columns,
  87   # and return this slice as a new BitMap object.
  88   # Usage: slice(1, 4)
  89   #        slice(true, 4)
  90   #        slice([0, 4, 5], true)
  91   #        slice([0 .. 4], true)
  92   # TODO:  slice(-1, true)
  93   # TODO:  slice([1 .. -2], true)
  94   def slice(cols, rows)
  95     cols = cols_expand(cols)
  96     rows = rows_expand(rows)
  97     bm   = BitMap.new(cols.size, rows.size)
  98
  99     slice_c(@map, @width, bm.map, bm.width, cols, rows)
 100
 101     bm
 102   end
 103
 104   # Method that performs bit wise and operation between:
 105   #   1: an entire bit map.
 106   #   2: a bit map row.
 107   #   3: a bit map column.
 108   # The result is saved in self.
 109   def &(bit_map)
 110     bm = BitMap.new(@cols, @rows)
 111
 112     if @rows == bit_map.rows and @cols == bit_map.cols
 113       raise # TODO
 114       bitwise_and_c()
 115     elsif @rows == bit_map.rows
 116       raise # TODO
 117       bitwise_and_col_c()
 118     elsif @cols == bit_map.cols
 119       bitwise_and_row_c(@map, bm.map, bit_map.map, @width, @rows)
 120     else
 121       raise BitMapError, "can't & uneven bit maps: #{@rows} x #{@cols} & #{bit_map.rows} x #{bit_map.cols}"
 122     end
 123
 124     bm
 125   end
 126
 127   def set?(c, r)
 128     btest_c(@map, @width, c, r)
 129   end
 130
 131   # Method to convert a bit array to a string.
 132   def to_s
 133     max_rows = 20
 134     max_cols = 60
 135     rows     = []
 136
 137     (0 ... @rows).each do |r|
 138       row = ""
 139       (0 ... @cols).each do |c|
 140         if set?(c, r)
 141           row << "1"
 142         else
 143           row << "0"
 144         end
 145       end
 146
 147       if @cols > max_cols
 148         row = row[0 ... max_cols] + " ... (#{@cols})"
 149       end
 150
 151       if rows.size > max_rows
 152         rows << "..."
 153         rows << "(#{@rows})"
 154         break
 155       end
 156
 157       rows << row
 158     end
 159
 160     rows.join($/)
 161   end
 162
 163   private
 164
 165   def pad_init
 166     if (@cols % BITS_PER_WORD) != 0
 167       pads = BITS_PER_WORD - (@cols % BITS_PER_WORD)
 168     else
 169       pads = 0
 170     end
 171
 172     pads
 173   end
 174
 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.
 179   def map_init
 180     size = @rows * @width / CHAR_BIT
 181
 182     "\0" * size
 183   end
 184
 185   def rows_expand(rows)
 186     if rows.is_a? Fixnum
 187       rows = [rows]
 188     elsif rows == true
 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
 193     end
 194
 195     raise BitMapError, "row outside bitmap: #{rows.first}" if rows.first < 0
 196     raise BitMapError, "row outside bitmap: #{rows.last}"  if rows.last  >= @rows
 197
 198     rows
 199   end
 200
 201   def cols_expand(cols)
 202     if cols.is_a? Fixnum
 203       cols = [cols]
 204     elsif cols == true
 205       cols = (0 ... @cols).to_a
 206     elsif cols.is_a? Array and cols.first.is_a? Range
 207       cols = cols.first.to_a
 208     end
 209
 210     raise BitMapError, "column outside bitmap: #{cols.first}" if cols.first < 0
 211     raise BitMapError, "column outside bitmap: #{cols.last}"  if cols.last  >= @cols
 212
 213     cols
 214   end
 215
 216   inline do |builder|
 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"
 220
 221     # New
 222     builder.prefix %s{
 223       typedef uint64_t word_t;
 224     }
 225
 226     # New
 227     builder.prefix %s{
 228       enum { BITS_PER_WORD = sizeof(word_t) * CHAR_BIT };
 229     }
 230
 231     # New
 232     builder.prefix %s{
 233       #define WORD_OFFSET(b) ((b) / BITS_PER_WORD)
 234     }
 235
 236     # New
 237     builder.prefix %s{
 238       #define BIT_OFFSET(b)  ((b) % BITS_PER_WORD)
 239     }
 240
 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
 243     # bits set.
 244     builder.prefix %{
 245       int count_bits_c(word_t x) {
 246         int count;
 247
 248         for (count = 0; x; count++)
 249           x &= x - 1;
 250
 251         return count;
 252       }
 253     }
 254
 255     # New
 256     builder.prefix %{
 257       void bit_set_c(word_t *map, int pos) {
 258         map[WORD_OFFSET(pos)] |= (1 << BIT_OFFSET(pos));
 259       }
 260     }
 261
 262     # New
 263     builder.prefix %{
 264       void bit_unset_c(word_t *map, int pos) {
 265         map[WORD_OFFSET(pos)] &= ~(1 << BIT_OFFSET(pos));
 266       }
 267     }
 268
 269     builder.c %{
 270       void set_c(VALUE _map, VALUE _width, VALUE _cols_ary, VALUE _rows_ary)
 271       {
 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);
 278         int     c            = 0;
 279         int     r            = 0;
 280         int     pos          = 0;
 281
 282         for (r = 0; r < row_ary_size; r++)
 283         {
 284           for (c = 0; c < col_ary_size; c++)
 285           {
 286             pos = NUM2INT(rows_ary[r]) * width + NUM2INT(cols_ary[c]);
 287
 288             bit_set_c(map, pos);
 289           }
 290         }
 291       }
 292     }
 293
 294     builder.c %{
 295       void unset_c(VALUE _map, VALUE _width, VALUE _cols_ary, VALUE _rows_ary)
 296       {
 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);
 303         int     c             = 0;
 304         int     r             = 0;
 305         int     pos           = 0;
 306
 307         for (r = 0; r < rows_ary_size; r++)
 308         {
 309           for (c = 0; c < cols_ary_size; c++)
 310           {
 311             pos = NUM2INT(rows_ary[r]) * width + NUM2INT(cols_ary[c]);
 312
 313             bit_unset_c(map, pos);
 314           }
 315         }
 316       }
 317     }
 318
 319     # New
 320     builder.prefix %{
 321       int bit_test_c(word_t* map, int pos)
 322       {
 323         word_t bit = map[WORD_OFFSET(pos)] & (1 << BIT_OFFSET(pos));
 324
 325         return bit != 0;
 326       }
 327     }
 328
 329     # New
 330     builder.c %{
 331       VALUE btest_c(VALUE _map, VALUE _width, VALUE _col, VALUE _row)
 332       {
 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;
 338
 339         return bit_test_c(map, pos);
 340       }
 341     }
 342
 343     builder.c %{
 344       void slice_c(VALUE _old_map, VALUE _old_width, VALUE _new_map, VALUE _new_width, VALUE _cols_ary, VALUE _rows_ary)
 345       {
 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);
 354         int     old_pos       = 0;
 355         int     new_pos       = 0;
 356         int     c             = 0;
 357         int     r             = 0;
 358
 359         for (r = 0; r < rows_ary_size; r++)
 360         {
 361           for (c = 0; c < cols_ary_size; c++)
 362           {
 363             old_pos = NUM2INT(rows_ary[r]) * old_width + NUM2INT(cols_ary[c]);
 364
 365             if (bit_test_c(old_map, old_pos))
 366             {
 367               new_pos = r * new_width + c;
 368               bit_set_c(new_map, new_pos);
 369             }
 370           }
 371         }
 372       }
 373     }
 374
 375     builder.c %{
 376       void bitwise_and_row_c(VALUE _old_map, VALUE _new_map, VALUE _row_map, VALUE _width, VALUE _rows)
 377       {
 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;
 384         int     c       = 0;
 385         int     r       = 0;
 386
 387         for (r = 0; r < rows; r++)
 388         {
 389           for (c = 0; c < size; c++) {
 390             new_map[r * size + c] = old_map[r * size + c] & row_map[c];
 391           }
 392         }
 393       }
 394     }
 395
 396     builder.c %{
 397       VALUE sum_c(VALUE _map, VALUE _size)
 398       {
 399         word_t *map  = (word_t*) StringValuePtr(_map);
 400         int     size = NUM2INT(_size);
 401         int     i    = 0;
 402         int     sum  = 0;
 403
 404         for (i = 0; i < size; i++)
 405           sum += count_bits_c(map[i]);
 406
 407         return INT2NUM(sum);
 408       }
 409     }
 410
 411     builder.c %{
 412       VALUE sum_rows_c(VALUE _map, VALUE _width, VALUE _rows)
 413       {
 414         word_t *map   = (word_t*) StringValuePtr(_map);
 415         int     width = NUM2INT(_width);
 416         int     rows  = NUM2INT(_rows);
 417         int     r     = 0;
 418         int     c     = 0;
 419         int     sums[rows];
 420         VALUE   sums_ary = rb_ary_new();
 421         int     size  = width / BITS_PER_WORD;
 422         int     pos   = 0;
 423
 424         for (r = 0; r < rows; r++) sums[r] = 0;
 425
 426         for (r = 0; r < rows; r++)
 427         {
 428           for (c = 0; c < size; c++) {
 429             pos = r * size + c;
 430
 431             sums[r] += count_bits_c(map[pos]);
 432           }
 433         }
 434
 435         for (r = 0; r < rows; r++) rb_ary_push(sums_ary, INT2FIX(sums[r]));
 436
 437         return sums_ary;
 438       }
 439     }
 440   end
 441 end