/* WARNING: This file was generated by dkct. Changes you make here will be lost if dkct is run again! You should modify the original source and run dkct on it. Original source: dk3bf.ctr */ /* Copyright (C) 2011-2017, Dirk Krause Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above opyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. * Neither the name of the author nor the names of contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /** @file dk3bf.c The dk3bf module. */ #line 102 "dk3bf.ctr" #include "dk3all.h" #include "dk3cores.h" #line 108 "dk3bf.ctr" /** Bit mask to set/retrieve single bits in a byte. */ static unsigned char const dk3bf_bits_in_byte[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; /** Bit masks to reset a single bit in a byte */ static unsigned char const dk3bf_not_in_byte[] = { 0x7F, 0xBF, 0xDF, 0xEF, 0xF7, 0xFB, 0xFD, 0xFE }; /** Keywords used by the module, not localized. */ static dkChar const * const dk3bf_kw[] = { /* 0 */ dkT("/bitmatrix/expand/cache-friendly"), /* 1 */ dkT("/proc/cache/available"), /* 2 */ dkT("/proc/cache/percent"), NULL #line 143 "dk3bf.ctr" }; void dk3bf_close(dk3_bf_t *b) { if(b) { dk3_release(b->data); b->nbits = 0; b->app = NULL; dk3_delete(b); } } dk3_bf_t * dk3bf_open_app(size_t nbits, dk3_app_t *app) { dk3_bf_t *back = NULL; size_t sz = 0; /* Number of bytes needed. */ if(nbits) { sz = nbits / 8; if(nbits % 8) { sz++; } back = dk3_new_app(dk3_bf_t,1,app); if(back) { back->nbits = nbits; back->data = NULL; back->app = app; back->data = dk3_new_app(unsigned char,sz,app); if(back->data) { dk3mem_res((void *)(back->data), sz); } else { dk3bf_close(back); back = NULL; } } } return back; } void dk3bf_set(dk3_bf_t *b, size_t n, int v) { size_t byteno = 0; /* Byte index in data. */ size_t inbyte = 0; /* Number of bit within the byte. */ if(b) { if(n < b->nbits) { byteno = n / 8; inbyte = n % 8; if(v) { (b->data)[byteno] |= dk3bf_bits_in_byte[inbyte]; } else { (b->data)[byteno] &= (~(dk3bf_bits_in_byte[inbyte])); } } else { if(b->app) { /* ERROR: Index out of range. */ dk3app_log_i1(b->app, DK3_LL_ERROR, 200); } } } } int dk3bf_get(dk3_bf_t const *b, size_t n) { int back = 0; size_t byteno = 0; /* Byte index in data. */ size_t inbyte = 0; /* Number of bit within the byte. */ if(b) { if(n < b->nbits) { byteno = n / 8; inbyte = n % 8; if(((b->data)[byteno]) & (dk3bf_bits_in_byte[inbyte])) { back = 1; } } else { if(b->app) { /* ERROR: Index out of range. */ dk3app_log_i1(b->app, DK3_LL_ERROR, 200); } } } return back; } #if VERSION_BEFORE_20140605 void dk3bm_close(dk3_bm_t *b) { size_t i = 0; /* Index of current row to delete. */ if(b) { if(b->data) { for(i = 0; i < b->rows; i++) { dk3_release((b->data)[i]); } dk3_delete(b->data); } b->data = NULL; b->app = NULL; b->columns = 0; b->rows = 0; dk3_delete(b); } } dk3_bm_t * dk3bm_open(size_t x, size_t y, dk3_app_t *app) { size_t bytes_per_row = 0; /* Number of bytes per row. */ size_t i = 0; /* Current row to initialize. */ int ok = 0; /* Flag: Success. */ dk3_bm_t *back = NULL; if((x) && (y)) { back = dk3_new_app(dk3_bm_t,1,app); if(back) { back->columns = x; back->rows = y; back->app = app; back->data = NULL; bytes_per_row = x / 8; if(x % 8) { bytes_per_row++; } back->data = dk3_new_app(DK3_PUCHAR,y,app); if(back->data) { ok = 1; for(i = 0; i < y; i++) { (back->data)[i] = NULL; } for(i = 0; i < y; i++) { (back->data)[i] = dk3_new_app(unsigned char,bytes_per_row,app); if((back->data)[i]) { dk3mem_res((void *)((back->data)[i]), bytes_per_row); } else { ok = 0; } } if(ok == 0) { dk3bm_close(back); back = NULL; } } else { dk3_delete(back); back = NULL; } } } return back; } void dk3bm_set(dk3_bm_t *b, size_t x, size_t y, int v) { unsigned char *pu = NULL; /* Row pointer. */ size_t byteno = 0; /* Index of byte in row. */ size_t bitno = 0; /* Index of bit within the byte. */ if(b) { if((x < b->columns) && (y < b->rows)) { pu = (b->data)[y]; byteno = x / 8; bitno = x % 8; if(v) { pu[byteno] |= dk3bf_bits_in_byte[bitno]; } else { pu[byteno] &= (~(dk3bf_bits_in_byte[bitno])); } } } } int dk3bm_get(dk3_bm_t const *b, size_t x, size_t y) { int back = 0; unsigned char *pu = NULL; /* Row pointer. */ size_t byteno = 0; /* Index of byte within the row. */ size_t bitno = 0; /* Index of bit within the byte. */ if(b) { if((x < b->columns) && (y < b->rows)) { pu = (b->data)[y]; byteno = x / 8; bitno = x % 8; if((pu[byteno]) & (dk3bf_bits_in_byte[bitno])) { back = 1; } } } return back; } void dk3bm_expand(dk3_bm_t *b) { int f_change_found = 0; /* Flag: Change found in this pass. */ size_t i = 0; /* Source node number. */ size_t j = 0; /* Destination node number. */ size_t k = 0; /* Intermediate node number. */ size_t p = 0; /* Number of current pass. */ if(b) { if(b->columns == b->rows) { p = 0; do { f_change_found = 0; for(i = 0; i < b->columns; i++) { for(j = 0; j < b->rows; j++) { if(!dk3bm_get(b, i, j)) { for(k = 0; k < b->columns; k++) { if(dk3bm_get(b, i, k)) { if(dk3bm_get(b, k, j)) { dk3bm_set(b, i, j, 1); f_change_found = 1; } } } } } } p++; } while((f_change_found) && (p < b->columns)); } else { if(b->app) { /* ERROR: Matrix must be a square! */ dk3app_log_i1(b->app, DK3_LL_ERROR, 201); } } } } #else void dk3bm_close(dk3_bm_t *b) { size_t i; if (b) { if (b->data) { if (b->columns < b->rows) { for (i = 0; i < b->columns; i++) { dk3_release((b->data)[i]); } } else { for (i = 0; i < b->rows; i++) { dk3_release((b->data)[i]); } } dk3_delete(b->data); } b->data = NULL; b->app = NULL; b->columns = 0; b->rows = 0; b->cachesize = 0; dk3_delete(b); } } #if VERSION_BEFORE_20140809 /** Find cache size available to this bit matrix expansion. @param app Application structure. @return Cache size if preferences found, 0 otherwise. */ static size_t dk3bf_get_cache_size(dk3_app_t *app) { dkChar buf[128]; unsigned long ul = 0UL; size_t back = 0; int found = 0; int ec = 0; #line 417 "dk3bf.ctr" if (dk3app_get_pref(app, dk3bf_kw[0], buf, DK3_SIZEOF(buf,dkChar))) { #if VERSION_BEFORE_20140716 if (1 == dk3sf_sscanf3(buf, dkT("%lu"), &ul)) #else if (0 != dk3ma_ul_from_string(&ul, buf, NULL)) #endif { back = (size_t)ul; found = 1; if ((unsigned long)back != ul) { back = 0; found = 0; } } } if (!(found)) { if (dk3app_get_pref(app, dk3bf_kw[1], buf, DK3_SIZEOF(buf,dkChar))) { #if VERSION_BEFORE_20140716 if (1 == dk3sf_sscanf3(buf, dkT("%lu"), &ul)) #else if (0 != dk3ma_ul_from_string(&ul, buf, NULL)) #endif { back = (size_t)ul; found = 1; if ((unsigned long)back != ul) { back = 0; found = 0; } if (found) { found = 0; if (dk3app_get_pref(app, dk3bf_kw[2], buf, DK3_SIZEOF(buf,dkChar))) { #if VERSION_BEFORE_20140716 if (1 == dk3sf_sscanf3(buf, dkT("%lu"), &ul)) #else if (0 != dk3ma_ul_from_string(&ul, buf, NULL)) #endif { back = dk3mem_mul_size_t(back, (size_t)ul, &ec) / 100; if (ec) { back = 0; } else { found = 1; } } } if ((back) && (!(found))) { back = back / 4; if (0 < back) { back = 1; } } } } } } #line 471 "dk3bf.ctr" return back; } #else /** Find cache size available to this bit matrix expansion. @param app Application structure. @return Cache size if preferences found, 0 otherwise. */ static size_t dk3bf_get_cache_size(dk3_app_t *app) { dkChar buf[128]; /* Preference value text */ dk3_um_t um1; /* From preferences */ dk3_um_t um2; /* From preferences */ size_t back = 0; int ec = 0; /* Error code */ #line 491 "dk3bf.ctr" if (dk3app_get_pref(app, dk3bf_kw[0], buf, DK3_SIZEOF(buf,dkChar))) { #if VERSION_BEFORE_20140716 if (dk3ma_string_to_um(&um1, buf)) #else if (0 != dk3ma_um_from_string(&um1, buf, NULL)) #endif { #if VERSION_BEFORE_20140716 back = dk3ma_um_to_sz(um1, NULL); #else #if DK3_SIZEOF_SIZE_T >= DK3_SIZEOF_UM back = (size_t)um1; #else if ((dk3_um_t)DK3_SIZE_T_MAX >= um1) { back = (size_t)um1; } #endif #endif } } if (0 == back) { if (dk3app_get_pref(app, dk3bf_kw[1], buf, DK3_SIZEOF(buf,dkChar))) { #if VERSION_BEFORE_20140716 if (dk3ma_string_to_um(&um1, buf)) #else if (0 != dk3ma_um_from_string(&um1, buf, NULL)) #endif { if (dk3app_get_pref(app, dk3bf_kw[2], buf, DK3_SIZEOF(buf,dkChar))) { #if VERSION_BEFORE_20140716 if (dk3ma_string_to_um(&um2, buf)) #else if (0 != dk3ma_um_from_string(&um2, buf, NULL)) #endif { if (DK3_UM_0 < um2) { if ((dk3_um_t)100U >= um2) { back = dk3ma_um_to_sz( (dk3ma_um_mul_ok(um1, um2, &ec) / ((dk3_um_t)100U)), &ec ); if (0 != ec) { back = 0; } } } } } if (0 == back) { ec = 0; back = dk3ma_um_to_sz((um1 / ((dk3_um_t)4U)), &ec); if (0 != ec) { back = 0; } } } } } #line 546 "dk3bf.ctr" return back; } #endif dk3_bm_t * dk3bm_open(size_t x, size_t y, dk3_app_t *app) { dk3_bm_t *back = NULL; size_t bpstr = 0; /* Bytes per strip */ size_t i = 0; /* Current strip index */ int ok = 0; /* Flag: Successfully */ #line 561 "dk3bf.ctr" if ((x) && (y)) { back = dk3_new_app(dk3_bm_t,1,app); if (back) { back->columns = x; back->rows = y; back->app = app; back->cachesize = 0; back->data = NULL; if (x < y) { #line 570 "dk3bf.ctr" bpstr = y / 8; if (y % 8) { bpstr++; } back->data = dk3_new_app(DK3_PUCHAR,x,app); if (back->data) { #line 574 "dk3bf.ctr" ok = 1; for (i = 0; i < x; i++) { (back->data)[i] = NULL; } for (i = 0; i < x; i++) { (back->data)[i] = dk3_new_app(unsigned char,bpstr,app); if ((back->data)[i]) { dk3mem_res((void *)((back->data)[i]), bpstr); } else { ok = 0; } } if (!(ok)) { #line 585 "dk3bf.ctr" dk3bm_close(back); back = NULL; } } else { #line 588 "dk3bf.ctr" dk3_release(back); } } else { #line 591 "dk3bf.ctr" bpstr = x / 8; if (x % 8) { bpstr++; } back->data = dk3_new_app(DK3_PUCHAR,y,app); if (back->data) { #line 595 "dk3bf.ctr" ok = 1; for (i = 0; i < y; i++) { (back->data)[i] = NULL; } for (i = 0; i < y; i++) { (back->data)[i] = dk3_new_app(unsigned char,bpstr,app); if ((back->data)[i]) { dk3mem_res((void *)((back->data)[i]), bpstr); } else { ok = 0; } } if (!(ok)) { #line 606 "dk3bf.ctr" dk3bm_close(back); back = NULL; } } else { #line 609 "dk3bf.ctr" dk3_release(back); } } if (back) { if (app) { back->cachesize = dk3bf_get_cache_size(app); } } } else { #line 618 "dk3bf.ctr" } } else { #line 620 "dk3bf.ctr" } #line 622 "dk3bf.ctr" return back; } void dk3bm_set_cache_size(dk3_bm_t *b, size_t cs) { if (b) { b->cachesize = cs; } } void dk3bm_set(dk3_bm_t *b, size_t x, size_t y, int v) { unsigned char *pu = NULL; /* Stripe pointer */ size_t byteno = 0; /* Index of byte in stripe */ size_t bitno = 0; /* Index of bit within the byte */ #line 642 "dk3bf.ctr" if (b) { if ((x < b->columns) && (y < b->rows)) { if (b->columns < b->rows) { pu = (b->data)[x]; byteno = y / 8; bitno = y % 8; } else { pu = (b->data)[y]; byteno = x / 8; bitno = x % 8; } if (v) { pu[byteno] |= dk3bf_bits_in_byte[bitno]; } else { pu[byteno] &= dk3bf_not_in_byte[bitno]; } } } #line 661 "dk3bf.ctr" } int dk3bm_get(dk3_bm_t const *b, size_t x, size_t y) { unsigned char *pu = NULL; /* Stripe pointer */ size_t byteno = 0; /* Index of byte within stripe */ size_t bitno = 0; /* Index of bit within byte */ int back = 0; #line 674 "dk3bf.ctr" if (b) { if ((x < b->columns) && (y < b->rows)) { if (b->columns < b->rows) { pu = (b->data)[x]; byteno = y / 8; bitno = y % 8; } else { pu = (b->data)[y]; byteno = x / 8; bitno = x % 8; } if((pu[byteno]) & (dk3bf_bits_in_byte[bitno])) { back = 1; } } } #line 691 "dk3bf.ctr" return back; } void dk3bm_expand(dk3_bm_t *b) { int f_cache_fr = 1; /* Flag: Cache friendly */ int f_change_found = 0; /* Flag: Change found */ size_t i = 0; /* Source node number */ size_t j = 0; /* Destination node number */ size_t k = 0; /* Intermediate node */ size_t mxs = 0; /* Matrix size */ int ec = 0; /* Math error code */ #line 707 "dk3bf.ctr" if (b) { #line 708 "dk3bf.ctr" if (b->columns == b->rows) { #line 709 "dk3bf.ctr" if (b->cachesize) { mxs = dk3mem_mul_size_t(b->rows, b->columns, &ec); if (mxs % 8) { mxs = mxs / 8 + 1; } else { mxs = mxs / 8; } if (0 == ec) { if (mxs <= b->cachesize) { f_cache_fr = 0; } } } else { f_cache_fr = 0; } if (f_cache_fr) { #line 717 "dk3bf.ctr" do { f_change_found = 0; for (j = 0; j < b->rows; j++) { for (k = 0; k < b->columns; k++) { for (i = 0; i < b->columns; i++) { if (!(dk3bm_get(b, i, j))) { if (dk3bm_get(b, k, j)) { if (dk3bm_get(b, i, k)) { dk3bm_set(b, i, j, 1); f_change_found = 1; } } } } } } } while(f_change_found); } else { #line 735 "dk3bf.ctr" do { f_change_found = 0; for (i = 0; i < b->columns; i++) { for (j = 0; j < b->rows; j++) { if (!(dk3bm_get(b, i, j))) { for (k = 0; k < b->columns; k++) { if (dk3bm_get(b, i, k)) { if (dk3bm_get(b, k, j)) { dk3bm_set(b, i, j, 1); f_change_found = 1; } } } } } } } while(f_change_found); } } else { #line 754 "dk3bf.ctr" if (b->app) { /* ERROR: Matrix must be a square! */ dk3app_log_i1(b->app, DK3_LL_ERROR, 201); } } } #line 760 "dk3bf.ctr" } #endif /* vim: set ai sw=2 : */