From 3a7456dd96820eea36e9f9656c7f5e29714f78d4 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Wed, 5 Dec 2001 09:40:16 +0000 Subject: [PATCH] * src/warshall.c (TC, RTC): De-obsfucate (source reduced to 22% of what it was!). * src/warshall.h: Remove accidental duplication of the content. --- ChangeLog | 7 ++++ src/warshall.c | 103 ++++++++++++------------------------------------- src/warshall.h | 27 +------------ 3 files changed, 33 insertions(+), 104 deletions(-) diff --git a/ChangeLog b/ChangeLog index 1b041ea6..10cfebb7 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2001-12-05 Akim Demaille + + * src/warshall.c (TC, RTC): De-obsfucate (source reduced to 22% of + what it was!). + * src/warshall.h: Remove accidental duplication of the content. + + 2001-12-05 Akim Demaille * src/closure.c (set_fderives): De-obfuscate. diff --git a/src/warshall.c b/src/warshall.c index 0d7af6ad..a9d579e6 100644 --- a/src/warshall.c +++ b/src/warshall.c @@ -1,5 +1,5 @@ /* Generate transitive closure of a matrix, - Copyright 1984, 1989, 2000 Free Software Foundation, Inc. + Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -22,93 +22,40 @@ #include "system.h" #include "warshall.h" -/* Given n by n matrix of bits R, modify its contents to be the - transive closure of what was given. */ +/*-------------------------------------------------------------. +| Given n by n matrix of bits R, modify its contents to be the | +| transive closure of what was given. | +`-------------------------------------------------------------*/ + +#define R(Num) (unsigned *) ((char *) R + ((Num) * rowsize)) static void TC (unsigned *R, int n) { - int rowsize; - unsigned mask; - unsigned *rowj; - unsigned *rp; - unsigned *rend; - unsigned *ccol; - - unsigned *relend; - unsigned *cword; - unsigned *rowi; - - rowsize = WORDSIZE(n) * sizeof(unsigned); - relend = (unsigned *) ((char *) R + (n * rowsize)); - - cword = R; - mask = 1; - rowi = R; - while (rowi < relend) - { - ccol = cword; - rowj = R; - - while (rowj < relend) - { - if (*ccol & mask) - { - rp = rowi; - rend = (unsigned *) ((char *) rowj + rowsize); - - while (rowj < rend) - *rowj++ |= *rp++; - } - else - { - rowj = (unsigned *) ((char *) rowj + rowsize); - } - - ccol = (unsigned *) ((char *) ccol + rowsize); - } - - mask <<= 1; - if (mask == 0) - { - mask = 1; - cword++; - } - - rowi = (unsigned *) ((char *) rowi + rowsize); - } + int rowsize = WORDSIZE (n) * sizeof (unsigned); + int i, j, k; + + for (i = 0; i < n; ++i) + for (j = 0; j < n; ++j) + if (BITISSET (R (i), j)) + for (k = 0; k < rowsize; ++k) + if (BITISSET (R (i), k)) + SETBIT (R (j), k); } -/* Reflexive Transitive Closure. Same as TC - and then set all the bits on the diagonal of R. */ +/*---------------------------------------------------------------. +| Reflexive Transitive Closure. Same as TC and then set all the | +| bits on the diagonal of R. | +`---------------------------------------------------------------*/ void RTC (unsigned *R, int n) { - int rowsize; - unsigned mask; - unsigned *rp; - unsigned *relend; - - TC(R, n); - - rowsize = WORDSIZE(n) * sizeof(unsigned); - relend = (unsigned *) ((char *) R + n*rowsize); - - mask = 1; - rp = R; - while (rp < relend) - { - *rp |= mask; - - mask <<= 1; - if (mask == 0) - { - mask = 1; - rp++; - } + int rowsize = WORDSIZE (n) * sizeof (unsigned); + int i; - rp = (unsigned *) ((char *) rp + rowsize); - } + TC (R, n); + for (i = 0; i < n; ++i) + SETBIT (R (i), i); } diff --git a/src/warshall.h b/src/warshall.h index 80d56dde..ed3aeaf6 100644 --- a/src/warshall.h +++ b/src/warshall.h @@ -1,30 +1,5 @@ /* Generate transitive closure of a matrix, - Copyright 1984, 1989, 2000 Free Software Foundation, Inc. - - This file is part of Bison, the GNU Compiler Compiler. - - Bison is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. - - Bison is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with Bison; see the file COPYING. If not, write to - the Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. */ - -#ifndef WARSHALL_H_ -# define WARSHALL_H_ - -void RTC PARAMS ((unsigned *, int)); -#endif /* !WARSHALL_H_ */ -/* Generate transitive closure of a matrix, - Copyright 1984, 1989, 2000 Free Software Foundation, Inc. + Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. -- 2.47.2