/* Copyright (C) 2019-2020, Dirk Krause SPDX-License-Identifier: BSD-3-Clause */ /* WARNING: This file was generated by the dkct program (see http://dktools.sourceforge.net/ for details). 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: dk4bm.ctr */ /** @file dk4bm.c The dk4bm module. */ #line 202 "dk4bm.ctr" #include "dk4mem.h" #include "dk4memrs.h" #include "dk4bm.h" #line 208 "dk4bm.ctr" /** One byte. */ typedef unsigned char dk4bm_uc_t; /** Pointer to unsigned chars. */ typedef unsigned char *dk4bm_puc_t; /** Bits within a byte. */ static unsigned char bib[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; /** Constant value 0 for comparisons. */ #define SZ0 ((size_t)0U) /** Constant value 8 for comparisons. */ #define SZ8 ((size_t)8U) dk4_bit_matrix_t * dk4bm_open( size_t rows, size_t columns, dk4_er_t *erp ) { dk4_bit_matrix_t *back = NULL; /* Function result */ dk4bm_puc_t *ppuc; /* Pointer: traverse back->data */ size_t bpr; /* Bytes per row */ size_t i; /* Index: traverse back->data */ int ok; /* Flag: All allocations ok */ #line 250 "dk4bm.ctr" if ((SZ0 < rows) && (SZ0 < columns)) { bpr = columns / SZ8; if (SZ0 != (columns % SZ8)) bpr++; #line 254 "dk4bm.ctr" back = dk4mem_new(dk4_bit_matrix_t,1,erp); if (NULL != back) { back->rows = rows; back->columns = columns; back->bytes_per_row = bpr; back->data = dk4mem_new(dk4bm_puc_t,rows,erp); if (NULL != back->data) { /* Initialize all row pointers to NULL */ ppuc = back->data; for (i = 0; i < rows; i++) { *(ppuc++) = NULL; } /* Allocate the rows */ ppuc = back->data; ok = 1; for (i = 0; i < rows; i++) { *ppuc = dk4mem_new(dk4bm_uc_t,bpr,erp); if (NULL != *ppuc) { DK4_MEMRES(*ppuc,bpr); } else { #line 279 "dk4bm.ctr" ok = 0; } ppuc++; } /* Check allocations, delete object on error */ if (0 == ok) { dk4bm_close(back, 0); back = NULL; } } else { #line 292 "dk4bm.ctr" dk4bm_close(back, 0); back = NULL; } } #if TRACE_DEBUG else { #line 298 "dk4bm.ctr" } #endif } else { #line 302 "dk4bm.ctr" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } #line 304 "dk4bm.ctr" return back; } #define USE_MEMCPY_FOR_ROWS 1 dk4_bit_matrix_t * dk4bm_open_copy( dk4_bit_matrix_t const *psrc, dk4_er_t *erp ) { dk4_bit_matrix_t *back = NULL; #if USE_MEMCPY_FOR_ROWS dk4bm_puc_t const *ps; /* Source data */ dk4bm_puc_t *pd; /* Destination data */ #endif size_t i; /* Current row number to copy */ #if (!(USE_MEMCPY_FOR_ROWS)) size_t j; int v; #endif #line 327 "dk4bm.ctr" if (NULL != psrc) { back = dk4bm_open(psrc->rows, psrc->columns, erp); if (NULL != back) { #if USE_MEMCPY_FOR_ROWS ps = psrc->data; pd = back->data; for (i = SZ0; i < psrc->rows; i++) { DK4_MEMCPY(*pd,*ps,psrc->bytes_per_row); ps++; pd++; } #endif #if (!(USE_MEMCPY_FOR_ROWS)) for (i = SZ0; i < back->rows; i++) { for (j = SZ0; j < back->columns; j++) { v = 0; if (0 != dk4bm_get(&v, psrc, i, j, NULL)) { if (0 != v) { dk4bm_set(back, i, j, 1, NULL); } } } } #endif } } else { dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } #line 356 "dk4bm.ctr" return back; } int dk4bm_set( dk4_bit_matrix_t *pmb, size_t row, size_t column, int value, dk4_er_t *erp ) { size_t byteno; /* Byte number within row */ size_t bitno; /* Bit number within byte */ int back = 0; /* Function result */ #line 374 "dk4bm.ctr" #line 375 "dk4bm.ctr" if ((NULL != pmb) && (NULL != pmb->data)) { if ((row < pmb->rows) && (column < pmb->columns)) { byteno = column / SZ8; bitno = column % SZ8; if (0 != value) { ((pmb->data)[row])[byteno] |= bib[bitno]; } else { ((pmb->data)[row])[byteno] &= (~(bib[bitno])); } back = 1; } else { #line 388 "dk4bm.ctr" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } } else { #line 392 "dk4bm.ctr" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } #line 394 "dk4bm.ctr" return back; } int dk4bm_get( int *pdest, dk4_bit_matrix_t const *pmb, size_t row, size_t column, dk4_er_t *erp ) { size_t byteno; /* Byte number within row */ size_t bitno; /* Bit number within byte */ int back = 0; /* Function result */ #line 412 "dk4bm.ctr" if ((NULL != pdest) && (NULL != pmb) && (NULL != pmb->data)) { if ((row < pmb->rows) && (column < pmb->columns)) { byteno = column / SZ8; bitno = column % SZ8; if (0x00 != ((((pmb->data)[row])[byteno]) & bib[bitno])) { *pdest = 1; } else { *pdest = 0; } back = 1; } else { #line 425 "dk4bm.ctr" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } } else { #line 429 "dk4bm.ctr" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } #line 431 "dk4bm.ctr" return back; } /* 2019-10-06 ---------- Cache-friendly programming. ---------- To see whether there is an indirect path from node i to node j -- if not yet present -- we check a list of all nodes k whether there is a known path from i to k and a known path from k to j. A cache-friendly algorithm is used here. Instead of ijk-algorithm (also called "naive algorithm") the order of loops is changed here to ikj. Variable i is used as row index for both i->j and i->k, an array pointer is calculated from the row index i. Variable k is used as row index k->j but also as column index i->k. Variable j is only used as column index in both i->j and k->j, the column index results in an index within an array. So i is the variable for the outermost loop, k is the variable for the middle loop and j is the variable for the inner loop. */ int dk4bm_expand( dk4_bit_matrix_t *pmb, dk4_er_t *erp ) { dk4bm_uc_t *ptri; /* Pointer: Row i bytes */ dk4bm_uc_t *ptrk; /* Pointer: Row k bytes */ size_t i; /* Destination row index */ size_t j; /* Destination column index */ size_t k; /* Intermediate point index */ size_t i_byte; /* Byte number of i within row */ size_t i_bit; /* Bit number of i within byte */ size_t j_byte; /* Byte number of j within row */ size_t j_bit; /* Bit number of j within byte */ size_t k_byte; /* Byte number of k within row */ size_t k_bit; /* Bit number of k within byte */ #if TRACE_DEBUG unsigned long passno = 0UL; /* Current pass number */ #endif int changed; /* Flag: Change occured in current pass */ int back = 0; /* Function result */ #line 478 "dk4bm.ctr" if ((NULL != pmb) && (NULL != pmb->data) && (pmb->rows == pmb->columns)) { if (0 < pmb->rows) { back = 1; changed = 1; while(0 != changed) { #line 483 "dk4bm.ctr" changed = 0; i_byte = 0; i_bit = 0; for (i = 0; i < pmb->rows; i++) { #line 488 "dk4bm.ctr" ptri = (pmb->data)[i]; k_byte = 0; k_bit = 0; for (k = 0; k < pmb->rows; k++) { #line 493 "dk4bm.ctr" ptrk = (pmb->data)[k]; if (0x00 != (ptri[k_byte] & bib[k_bit])) { j_byte = 0; j_bit = 0; for (j = 0; j < pmb->rows; j++) { #line 499 "dk4bm.ctr" if (0x00 == (ptri[j_byte] & bib[j_bit])) { #line 501 "dk4bm.ctr" if (0x00 != (ptrk[j_byte] & bib[j_bit])) { #line 503 "dk4bm.ctr" ptri[j_byte] |= bib[j_bit]; changed = 1; } } j_bit++; if (8 <= j_bit) { j_bit = 0; j_byte++; } } } k_bit++; if (8 <= k_bit) { k_bit = 0; k_byte++; } } i_bit++; if (8 <= i_bit) { i_bit = 0; i_byte++; } } #line 523 "dk4bm.ctr" } } else { #line 526 "dk4bm.ctr" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } } else { #line 530 "dk4bm.ctr" dk4error_set_simple_error_code(erp, DK4_E_INVALID_ARGUMENTS); } #line 532 "dk4bm.ctr" return back; } void dk4bm_close( dk4_bit_matrix_t *pbm, int san ) { dk4bm_puc_t *ppuc; /* Pointer: Traverse pbm->data */ size_t i; /* Index: Traverse pbm->data */ #line 546 "dk4bm.ctr" if (NULL != pbm) { if (NULL != pbm->data) { ppuc = pbm->data; for (i = 0; i < pbm->rows; i++) { if (NULL != *ppuc) { if (0 != san) { dk4mem_reset_secure(*ppuc,pbm->bytes_per_row,NULL); } dk4mem_free(*ppuc); } ppuc++; } dk4mem_free(pbm->data); } if (0 != san) { dk4mem_reset_secure(pbm,sizeof(dk4_bit_matrix_t),NULL); } dk4mem_free(pbm); } #line 565 "dk4bm.ctr" } /* vim: set ai sw=4 ts=4 : */