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 # Error class for all exceptions to do with BitMap.
  28 class BitMapError < StandardError; end
  29
  30 CHAR_BIT = 8
  31
  32 # Bitmap - 13 columns, 3 rows:
  33 # 1000000000000
  34 # 0000001000000
  35 # 0000000000001
  36 #
  37 # Bytestring:
  38 #   byte 0   byte 1   byte 2   byte 3   byte 4   byte 5
  39 # +--------+--------+--------+--------+--------+--------+
  40 # |10000000|00000000|00000010|00000000|00000000|00000001|
  41 # +--------+--------+--------+--------+--------+--------+
  42 #
  43 # Padding:
  44 #        row 0             row 1             row 2
  45 #  10000000 00000xxx 00000010 00000xxx 00000000 00001xxx
  46 class BitMap
  47   attr_accessor :cols, :rows, :byte_array
  48
  49   # Method to initialize a BitMap.
  50   def initialize(cols, rows)
  51     @cols       = cols
  52     @rows       = rows
  53     @pads       = padding
  54     size        = ((rows * (cols + @pads)) / CHAR_BIT)
  55     @byte_array = "\0" * size
  56   end
  57
  58   # Method that set bits to 1 at specified columns, and rows.
  59   # Usage: set(1, 4)
  60   #        set(true, 4)
  61   #        set([0, 4, 5], true)
  62   #        set([0 .. 4], true)
  63   # TODO:  set(-1, true)
  64   # TODO:  set([1 .. -2], true)
  65   def set(cols, rows)
  66     cols = cols_expand(cols)
  67     rows = rows_expand(rows)
  68
  69     set_c(cols, rows)
  70   end
  71
  72   # Method that set bits to 0 at specified columns, and rows.
  73   # Usage: unset(1, 4)
  74   #        unset(true, 4)
  75   #        unset([0, 4, 5], true)
  76   #        unset([0 .. 4], true)
  77   # TODO:  unset(-1, true)
  78   # TODO:  unset([1 .. -2], true)
  79   def unset(cols, rows)
  80     cols = cols_expand(cols)
  81     rows = rows_expand(rows)
  82
  83     unset_c(cols, 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(bm.byte_array, 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       bitwise_and_c(bit_map.byte_array)
 114     elsif @rows == bit_map.rows
 115       bitwise_and_col_c(bit_map.byte_array)
 116     elsif @cols == bit_map.cols
 117       bitwise_and_row_c(self.byte_array, bm.byte_array, bit_map.byte_array, @cols, @rows)
 118     else
 119       raise BitMapError, "can't & uneven bit maps: #{@rows} x #{@cols} & #{bit_map.rows} x #{bit_map.cols}"
 120     end
 121
 122     bm
 123   end
 124
 125   # Method to convert a bit array to a string.
 126   def to_s
 127     max_rows = 20
 128     max_cols = 60
 129     rows     = []
 130
 131     (0 ... @rows).each do |r|
 132       row = ""
 133       (0 ... @cols).each do |c|
 134         pos = r * (@cols + @pads) + c
 135
 136         if self.set? pos
 137           row << "1"
 138         else
 139           row << "0"
 140         end
 141       end
 142
 143       if @cols > max_cols
 144         row = row[0 ... max_cols] + " ... (#{@cols})"
 145       end
 146
 147       if rows.size > max_rows
 148         rows << "..."
 149         rows << "(#{@rows})"
 150         break
 151       end
 152
 153       rows << row
 154     end
 155
 156     rows.join($/)
 157   end
 158
 159   private
 160
 161   def padding
 162     (((@cols % CHAR_BIT) != 0) ? (CHAR_BIT - (@cols % CHAR_BIT)) : 0)
 163   end
 164
 165   def rows_expand(rows)
 166     if rows.is_a? Fixnum
 167       rows = [rows]
 168     elsif rows == true
 169       rows = (0 ... @rows).to_a
 170     elsif rows.is_a? Array and rows.first.is_a? Range
 171       rows = rows.first.to_a
 172       rows = [0] if rows.empty? # FIXME
 173     end
 174
 175     raise BitMapError, "row outside bitmap: #{rows.first}" if rows.first < 0
 176     raise BitMapError, "row outside bitmap: #{rows.last}"  if rows.last  >= @rows
 177
 178     rows
 179   end
 180
 181   def cols_expand(cols)
 182     if cols.is_a? Fixnum
 183       cols = [cols]
 184     elsif cols == true
 185       cols = (0 ... @cols).to_a
 186     elsif cols.is_a? Array and cols.first.is_a? Range
 187       cols = cols.first.to_a
 188     end
 189
 190     raise BitMapError, "column outside bitmap: #{cols.first}" if cols.first < 0
 191     raise BitMapError, "column outside bitmap: #{cols.last}"  if cols.last  >= @cols
 192
 193     cols
 194   end
 195
 196   inline do |builder|
 197     builder.add_static "rows",       'rb_intern("@rows")',       "ID"
 198     builder.add_static "cols",       'rb_intern("@cols")',       "ID"
 199     builder.add_static "byte_array", 'rb_intern("@byte_array")', "ID"
 200
 201     builder.prefix %s{
 202       unsigned char bit_count[256] = {
 203         0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 204         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 205         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 206         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 207         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 208         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 209         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 210         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 211         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 212         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 213         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 214         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 215         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 216         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 217         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 218         4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
 219       };
 220     }
 221
 222     builder.prefix %{
 223       #define COUNT_BITS(c) (bit_count[c])
 224     }
 225
 226     builder.prefix %{
 227       #define PADDING(cols) (((cols % CHAR_BIT) != 0) ? (CHAR_BIT - (cols % CHAR_BIT)) : 0)
 228     }
 229
 230     builder.prefix %{
 231       #define BYTE_SIZE(rows, cols) (rows * (cols + PADDING(cols)) / CHAR_BIT)
 232     }
 233
 234     builder.prefix %{
 235       #define BYTE_POS(pos) (pos / CHAR_BIT)
 236     }
 237
 238     builder.prefix %{
 239       #define BIT_POS(pos) (1 << (CHAR_BIT - 1 - (pos % CHAR_BIT)))
 240     }
 241
 242     builder.c %{
 243       VALUE fill_c()
 244       {
 245         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 246         VALUE          _rows       = rb_ivar_get(self, rows);
 247         VALUE          _cols       = rb_ivar_get(self, cols);
 248         unsigned char* byte_array  = StringValuePtr(_byte_array);
 249         int            rows        = NUM2INT(_rows);
 250         int            cols        = NUM2INT(_cols);
 251         int            size        = BYTE_SIZE(rows, cols);
 252         int            i           = 0;
 253
 254         for (i = 0; i < size; i++) byte_array[i] = ~0;
 255
 256         return self;
 257       }
 258     }
 259
 260     builder.c %{
 261       VALUE empty_c()
 262       {
 263         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 264         VALUE          _rows       = rb_ivar_get(self, rows);
 265         VALUE          _cols       = rb_ivar_get(self, cols);
 266         unsigned char* byte_array  = StringValuePtr(_byte_array);
 267         int            rows        = NUM2INT(_rows);
 268         int            cols        = NUM2INT(_cols);
 269         int            size        = BYTE_SIZE(rows, cols);
 270         int            i           = 0;
 271
 272         for (i = 0; i < size; i++) byte_array[i] = 0;
 273
 274         return self;
 275       }
 276     }
 277
 278     builder.c %{
 279       VALUE bit_test_c(VALUE _pos)
 280       {
 281         int            pos         = NUM2INT(_pos);
 282         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 283         unsigned char* byte_array  = StringValuePtr(_byte_array);
 284
 285         return ((byte_array[BYTE_POS(pos)] & BIT_POS(pos)) != 0);
 286       }
 287     }
 288
 289     builder.c %{
 290       void set_c(VALUE _cols_array, VALUE _rows_array)
 291       {
 292         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 293         VALUE          _cols       = rb_ivar_get(self, cols);
 294         unsigned char* byte_array  = StringValuePtr(_byte_array);
 295         int            cols        = NUM2INT(_cols);
 296
 297         VALUE          *cols_array = RARRAY_PTR(_cols_array);
 298         VALUE          *rows_array = RARRAY_PTR(_rows_array);
 299         int            col_size    = (int) RARRAY_LEN(_cols_array);
 300         int            row_size    = (int) RARRAY_LEN(_rows_array);
 301         int            c           = 0;
 302         int            r           = 0;
 303         int            pad         = PADDING(cols);
 304         int            pos         = 0;
 305
 306         for (r = 0; r < row_size; r++)
 307         {
 308           for (c = 0; c < col_size; c++)
 309           {
 310             pos = NUM2INT(rows_array[r]) * (cols + pad) + NUM2INT(cols_array[c]);
 311
 312             byte_array[BYTE_POS(pos)] |= BIT_POS(pos);
 313           }
 314         }
 315       }
 316     }
 317
 318     builder.c %{
 319       void unset_c(VALUE _cols_array, VALUE _rows_array)
 320       {
 321         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 322         VALUE          _cols       = rb_ivar_get(self, cols);
 323         unsigned char* byte_array  = StringValuePtr(_byte_array);
 324         int            cols        = NUM2INT(_cols);
 325
 326         VALUE          *cols_array = RARRAY_PTR(_cols_array);
 327         VALUE          *rows_array = RARRAY_PTR(_rows_array);
 328         int            col_size    = (int) RARRAY_LEN(_cols_array);
 329         int            row_size    = (int) RARRAY_LEN(_rows_array);
 330         int            c           = 0;
 331         int            r           = 0;
 332         int            pad         = PADDING(cols);
 333         int            pos         = 0;
 334         unsigned char  mask        = 0;
 335
 336         for (r = 0; r < row_size; r++)
 337         {
 338           for (c = 0; c < col_size; c++)
 339           {
 340             pos = NUM2INT(rows_array[r]) * (cols + pad) + NUM2INT(cols_array[c]);
 341
 342             mask = BIT_POS(pos);
 343             mask = ~mask;
 344
 345             byte_array[BYTE_POS(pos)] &= mask;
 346           }
 347         }
 348       }
 349     }
 350
 351     builder.c %{
 352       void slice_c(VALUE _new_array, VALUE _new_cols, VALUE _new_rows)
 353       {
 354         VALUE          _old_array  = rb_ivar_get(self, byte_array);
 355         VALUE          _old_cols   = rb_ivar_get(self, cols);
 356         VALUE          _old_rows   = rb_ivar_get(self, rows);
 357         unsigned char* old_array   = StringValuePtr(_old_array);
 358         int            old_cols    = NUM2INT(_old_cols);
 359         int            old_rows    = NUM2INT(_old_rows);
 360
 361         unsigned char* new_array   = StringValuePtr(_new_array);
 362         VALUE          *cols_array = RARRAY_PTR(_new_cols);
 363         VALUE          *rows_array = RARRAY_PTR(_new_rows);
 364         int            col_count   = (int) RARRAY_LEN(_new_cols);
 365         int            row_count   = (int) RARRAY_LEN(_new_rows);
 366         int            c           = 0;
 367         int            r           = 0;
 368         int            old_pos     = 0;
 369         int            new_pos     = 0;
 370         int            old_pad     = PADDING(old_cols);
 371         int            new_pad     = PADDING(col_count);
 372
 373         for (r = 0; r < row_count; r++)
 374         {
 375           for (c = 0; c < col_count; c++)
 376           {
 377             old_pos = NUM2INT(rows_array[r]) * (old_cols + old_pad) + NUM2INT(cols_array[c]);
 378             new_pos = r * (col_count + new_pad) + c;
 379
 380             if ((old_array[BYTE_POS(old_pos)] & BIT_POS(old_pos)) != 0)
 381               new_array[BYTE_POS(new_pos)] |= BIT_POS(new_pos);
 382           }
 383         }
 384       }
 385     }
 386
 387     builder.c %{
 388       void bitwise_and_row_c(VALUE _old_array, VALUE _new_array, VALUE _row_array, VALUE _cols, VALUE _rows)
 389       {
 390         unsigned char* old_array = StringValuePtr(_old_array);
 391         unsigned char* new_array = StringValuePtr(_new_array);
 392         unsigned char* row_array = StringValuePtr(_row_array);
 393         int            cols      = NUM2INT(_cols);
 394         int            rows      = NUM2INT(_rows);
 395         int            col_bytes = (cols / CHAR_BIT) + ((cols % CHAR_BIT) ? 1: 0);
 396         int            c         = 0;
 397         int            r         = 0;
 398
 399         for (r = 0; r < rows; r++)
 400         {
 401           for (c = 0; c < col_bytes; c++) {
 402             new_array[r * col_bytes + c] = old_array[r * col_bytes + c] & row_array[c];
 403           }
 404         }
 405       }
 406     }
 407
 408     builder.c %{
 409       VALUE sum_c()
 410       {
 411         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 412         VALUE          _rows       = rb_ivar_get(self, rows);
 413         VALUE          _cols       = rb_ivar_get(self, cols);
 414         unsigned char* byte_array  = StringValuePtr(_byte_array);
 415         int            rows        = NUM2INT(_rows);
 416         int            cols        = NUM2INT(_cols);
 417         int            size        = BYTE_SIZE(rows, cols);
 418         int            i           = 0;
 419         int            sum         = 0;
 420
 421         for (i = 0; i < size; i++)
 422           sum += COUNT_BITS(byte_array[i]);
 423
 424         return INT2NUM(sum);
 425       }
 426     }
 427
 428     builder.c %{
 429       VALUE sum_rows_c()
 430       {
 431         VALUE          _byte_array = rb_ivar_get(self, byte_array);
 432         VALUE          _rows       = rb_ivar_get(self, rows);
 433         VALUE          _cols       = rb_ivar_get(self, cols);
 434         unsigned char* byte_array  = StringValuePtr(_byte_array);
 435         int            rows        = NUM2INT(_rows);
 436         int            cols        = NUM2INT(_cols);
 437         int            col_bytes   = (cols / CHAR_BIT) + ((cols % CHAR_BIT) ? 1: 0);
 438         int            r           = 0;
 439         int            c           = 0;
 440         int            sums[rows];
 441         VALUE          rb_sums     = rb_ary_new();
 442
 443         int pos = 0;
 444
 445         for (r = 0; r < rows; r++) sums[r] = 0;
 446
 447         for (r = 0; r < rows; r++)
 448         {
 449           for (c = 0; c < col_bytes; c++) {
 450             sums[r] += COUNT_BITS(byte_array[r * col_bytes + c]);
 451           }
 452         }
 453
 454         for (r = 0; r < rows; r++) rb_ary_push(rb_sums, INT2FIX(sums[r]));
 455
 456         return rb_sums;
 457       }
 458     }
 459   end
 460
 461   alias :sum      :sum_c
 462   alias :sum_rows :sum_rows_c
 463   alias :set?     :bit_test_c
 464   alias :fill!    :fill_c
 465   alias :empty!   :empty_c
 466 end