/* MOD2DENSE.C - Procedures for handling dense mod2 matrices. *//* Copyright (c) 1996, 2000, 2001 by Radford M. Neal  * * Permission is granted for anyone to copy, use, or modify this program  * for purposes of research or education, provided this copyright notice  * is retained, and note is made of any changes that have been made.  * * This program is distributed without any warranty, express or implied. * As this program was written for research purposes only, it has not been * tested to the degree that would be advisable in any important application. * All use of this program is entirely at the user's own risk. *//* NOTE:  See mod2dense.html for documentation on these procedures. */#include <stdlib.h>#include <stdio.h>#include <math.h>#include "alloc.h"#include "intio.h"#include "mod2dense.h"/* ALLOCATE SPACE FOR A DENSE MOD2 MATRIX. */mod2dense *mod2dense_allocate ( int n_rows, 		/* Number of rows in matrix */  int n_cols		/* Number of columns in matrix */){  mod2dense *m;  int j;  if (n_rows<=0 || n_cols<=0)  { fprintf(stderr,"mod2dense_allocate: Invalid number of rows or columns\n");    exit(1);  }  m = chk_alloc (1, sizeof *m);  m->n_rows = n_rows;  m->n_cols = n_cols;  m->n_words = (n_rows+mod2_wordsize-1) >> mod2_wordsize_shift;  m->col = chk_alloc (m->n_cols, sizeof *m->col);  m->bits = chk_alloc(m->n_words*m->n_cols, sizeof *m->bits);  for (j = 0; j<m->n_cols; j++)  { m->col[j] = m->bits + j*m->n_words;  }  return m;}/* FREE SPACE OCCUPIED BY A DENSE MOD2 MATRIX. */void mod2dense_free( mod2dense *m		/* Matrix to free */){ free(m->bits);  free(m->col);  free(m);}/* CLEAR A DENSE MOD2 MATRIX. */void mod2dense_clear( mod2dense *r){  int k, j;  for (j = 0; j<mod2dense_cols(r); j++)  { for (k = 0; k<r->n_words; k++)    { r->col[j][k] = 0;    }  }}/* COPY A DENSE MOD2 MATRIX. */void mod2dense_copy( mod2dense *m,		/* Matrix to copy */  mod2dense *r		/* Place to store copy of matrix */){   int k, j;  if (mod2dense_rows(m)>mod2dense_rows(r)    || mod2dense_cols(m)>mod2dense_cols(r))  { fprintf(stderr,"mod2dense_copy: Destination matrix is too small\n");    exit(1);  }  for (j = 0; j<mod2dense_cols(m); j++)  { for (k = 0; k<m->n_words; k++)    { r->col[j][k] = m->col[j][k];    }    for ( ; k<r->n_words; k++)    { r->col[j][k] = 0;    }  }  for ( ; j<mod2dense_cols(r); j++)  { for (k = 0; k<r->n_words; k++)    { r->col[j][k] = 0;    }  }}/* COPY ROWS OF A DENSE MOD2 MATRIX. */void mod2dense_copyrows( mod2dense *m,		/* Matrix to copy */  mod2dense *r,		/* Place to store copy of matrix */  int *rows		/* Indexes of rows to copy, from 0 */){   int i, j;  if (mod2dense_cols(m)>mod2dense_cols(r))  { fprintf(stderr,      "mod2dense_copyrows: Destination matrix has fewer columns than source\n");    exit(1);  }  mod2dense_clear(r);  for (i = 0; i<mod2dense_rows(r); i++)  { if (rows[i]<0 || rows[i]>=mod2dense_rows(m))    { fprintf(stderr,"mod2dense_copyrows: Row index out of range\n");      exit(1);    }    for (j = 0; j<mod2dense_cols(m); j++)    { mod2dense_set(r,i,j,mod2dense_get(m,rows[i],j));    }  }}/* COPY COLUMNS OF A DENSE MOD2 MATRIX. */void mod2dense_copycols( mod2dense *m,		/* Matrix to copy */  mod2dense *r,		/* Place to store copy of matrix */  int *cols		/* Indexes of columns to copy, from 0 */){   int k, j;  if (mod2dense_rows(m)>mod2dense_rows(r))  { fprintf(stderr,      "mod2dense_copycols: Destination matrix has fewer rows than source\n");    exit(1);  }  for (j = 0; j<mod2dense_cols(r); j++)  { if (cols[j]<0 || cols[j]>=mod2dense_cols(m))    { fprintf(stderr,"mod2dense_copycols: Column index out of range\n");      exit(1);    }    for (k = 0; k<m->n_words; k++)    { r->col[j][k] = m->col[cols[j]][k];    }    for ( ; k<r->n_words; k++)    { r->col[j][k] = 0;    }  }}/* PRINT A DENSE MOD2 MATRIX IN HUMAN-READABLE FORM. */void mod2dense_print     ( FILE *f,  mod2dense *m){   int i, j;  for (i = 0; i<mod2dense_rows(m); i++)  { for (j = 0; j<mod2dense_cols(m); j++)    { fprintf(f," %d",mod2dense_get(m,i,j));    }    fprintf(f,"\n");  }}/* WRITE A DENSE MOD2 MATRIX TO A FILE IN MACHINE-READABLE FORM.   Data is written using intio_write, so that it will be readable on a machine   with a different byte-ordering.  At present, this assumes that the words    used to pack bits into are no longer than 32 bits. */int mod2dense_write     ( FILE *f,   mod2dense *m){   int j, k;  intio_write(f,m->n_rows);  if (ferror(f)) return 0;  intio_write(f,m->n_cols);  if (ferror(f)) return 0;  for (j = 0; j<mod2dense_cols(m); j++)  {    for (k = 0; k<m->n_words; k++)    { intio_write(f,m->col[j][k]);      if (ferror(f)) return 0;    }  }  return 1;}/* READ A DENSE MOD2 MATRIX STORED IN MACHINE-READABLE FORM FROM A FILE. */mod2dense *mod2dense_read  ( FILE *f){   int n_rows, n_cols;  mod2dense *m;  int j, k;    n_rows = intio_read(f);  if (feof(f) || ferror(f) || n_rows<=0) return 0;  n_cols = intio_read(f);  if (feof(f) || ferror(f) || n_cols<=0) return 0;  m = mod2dense_allocate(n_rows,n_cols);  for (j = 0; j<mod2dense_cols(m); j++)  {    for (k = 0; k<m->n_words; k++)    { m->col[j][k] = intio_read(f);      if (feof(f) || ferror(f))       { mod2dense_free(m);        return 0;      }    }  }  return m;}/* GET AN ELEMENT FROM A DENSE MOD2 MATRIX. */int mod2dense_get  ( mod2dense *m, 	/* Matrix to get element from */  int row,		/* Row of element (starting with zero) */  int col		/* Column of element (starting with zero) */){  if (row<0 || row>=mod2dense_rows(m) || col<0 || col>=mod2dense_cols(m))  { fprintf(stderr,"mod2dense_get: row or column index out of bounds\n");    exit(1);  }  return mod2_getbit (m->col[col][row>>mod2_wordsize_shift],                       row&mod2_wordsize_mask);}/* SET AN ELEMENT IN A DENSE MOD2 MATRIX. */void mod2dense_set ( mod2dense *m, 	/* Matrix to modify element of */  int row,		/* Row of element (starting with zero) */  int col,		/* Column of element (starting with zero) */  int value		/* New value of element (0 or 1) */){   mod2word *w;  if (row<0 || row>=mod2dense_rows(m) || col<0 || col>=mod2dense_cols(m))  { fprintf(stderr,"mod2dense_set: row or column index out of bounds\n");    exit(1);  }  w = &m->col[col][row>>mod2_wordsize_shift];  *w = value ? mod2_setbit1(*w,row&mod2_wordsize_mask)              : mod2_setbit0(*w,row&mod2_wordsize_mask);}/* FLIP AN ELEMENT OF A DENSE MOD2 MATRIX. */int mod2dense_flip  ( mod2dense *m, 	/* Matrix to flip element in */  int row,		/* Row of element (starting with zero) */  int col		/* Column of element (starting with zero) */){  mod2word *w;  int b;  if (row<0 || row>=mod2dense_rows(m) || col<0 || col>=mod2dense_cols(m))  { fprintf(stderr,"mod2dense_flip: row or column index out of bounds\n");    exit(1);  }  b = 1 ^ mod2_getbit (m->col[col][row>>mod2_wordsize_shift],                        row&mod2_wordsize_mask);  w = &m->col[col][row>>mod2_wordsize_shift];  *w = b ? mod2_setbit1(*w,row&mod2_wordsize_mask)          : mod2_setbit0(*w,row&mod2_wordsize_mask);  return b;}/* COMPUTE THE TRANSPOSE OF A DENSE MOD2 MATRIX. */void mod2dense_transpose( mod2dense *m,		/* Matrix to compute transpose of (left unchanged) */  mod2dense *r		/* Result of transpose operation */){  mod2word w, v, *p;  int k1, j1, i2, j2;  if (mod2dense_rows(m)!=mod2dense_cols(r)    || mod2dense_cols(m)!=mod2dense_rows(r))  { fprintf(stderr,     "mod2dense_transpose: Matrices have incompatible dimensions\n");    exit(1);  }  if (r==m)  { fprintf(stderr,      "mod2dense_transpose: Result matrix is the same as the operand\n");    exit(1);  }  mod2dense_clear(r);  for (j1 = 0; j1<mod2dense_cols(m); j1++)  {     i2 = j1 >> mod2_wordsize_shift;    v = 1 << (j1 & mod2_wordsize_mask);    p = m->col[j1];    k1 = 0;    for (j2 = 0; j2<mod2dense_cols(r); j2++)    { if (k1==0)      { w = *p++;        k1 = mod2_wordsize;      }      if (w&1)      { r->col[j2][i2] |= v;      }      w >>= 1;           k1 -= 1;