diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/dktools/dk3bf.c |
Initial commit
Diffstat (limited to 'support/dktools/dk3bf.c')
-rw-r--r-- | support/dktools/dk3bf.c | 760 |
1 files changed, 760 insertions, 0 deletions
diff --git a/support/dktools/dk3bf.c b/support/dktools/dk3bf.c new file mode 100644 index 0000000000..409200533e --- /dev/null +++ b/support/dktools/dk3bf.c @@ -0,0 +1,760 @@ +/* + 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 : */ + |