summaryrefslogtreecommitdiff
path: root/support/dktools/dk3bf.c
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/dktools/dk3bf.c
Initial commit
Diffstat (limited to 'support/dktools/dk3bf.c')
-rw-r--r--support/dktools/dk3bf.c760
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 : */
+