mod2sparse.c

用C语言编写的LDPC译码程序

/* MOD2SPARSE.C - Procedures for handling sparse mod2 matrices. */

/* Copyright (c) 2000 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.
 */


#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include "alloc.h"
#include "intio.h"
#include "mod2sparse.h"


/* ALLOCATE AN ENTRY WITHIN A MATRIX. */

static mod2entry *alloc_entry
( mod2sparse *m
)
{ 
  mod2block *b;
  mod2entry *e;
  int k;

  if (m->next_free==0)
  { 
    b = chk_alloc (1, sizeof *b);

    b->next = m->blocks;
    m->blocks = b;

    for (k = 0; k<Mod2sparse_block; k++)
    { b->entry[k].left = m->next_free;
      m->next_free = &b->entry[k];
    }
  }

  e = m->next_free;
  m->next_free = e->left;

  e->pr = 0;
  e->lr = 0;

  return e;
}


/* ALLOCATE SPACE FOR A SPARSE MOD2 MATRIX.  Prints a message and exits if 
   there is not enough memory available for the matrix.  The matrix will
   be set to all zeros (ie, have no entries). */

mod2sparse *mod2sparse_allocate
( int n_rows, 		/* Number of rows in matrix */
  int n_cols		/* Number of columns in matrix */
)
{
  mod2sparse *m;
  mod2entry *e;
  int i, j;

  if (n_rows<=0 || n_cols<=0)
  { fprintf(stderr,"mod2sparse_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->rows = chk_alloc (n_rows, sizeof *m->rows);
  m->cols = chk_alloc (n_cols, sizeof *m->cols);

  m->blocks = 0;
  m->next_free = 0;

  for (i = 0; i<n_rows; i++)
  { e = &m->rows[i];
    e->left = e->right = e->up = e->down = e;
    e->row = e->col = -1;
  }

  for (j = 0; j<n_cols; j++)
  { e = &m->cols[j];
    e->left = e->right = e->up = e->down = e;
    e->row = e->col = -1;
  }

  return m;
}


/* FREE SPACE OCCUPIED BY A SPARSE MOD2 MATRIX.  The pointer passed and all
   pointers to entries within this matrix should no longer be used after 
   mod2sparse_free returns. */

void mod2sparse_free
( mod2sparse *m		/* Matrix to free */
)
{ 
  mod2block *b;

  free(m->rows);
  free(m->cols);

  while (m->blocks!=0)
  { b = m->blocks;
    m->blocks = b->next;
    free(b);
  }
}


/* CLEAR A SPARSE MATRIX TO ALL ZEROS.  The space occupied by entries in
   the matrix is freed for general use. */

void mod2sparse_clear
( mod2sparse *r
)
{
  mod2block *b;
  mod2entry *e;
  int i, j;

  for (i = 0; i<mod2sparse_rows(r); i++)
  { e = &r->rows[i];
    e->left = e->right = e->up = e->down = e;
  }

  for (j = 0; j<mod2sparse_cols(r); j++)
  { e = &r->cols[j];
    e->left = e->right = e->up = e->down = e;
  }

  while (r->blocks!=0)
  { b = r->blocks;
    r->blocks = b->next;
    free(b);
  }
}


/* COPY A SPARSE MATRIX.  The first matrix is copied to the second, which
   must already have been allocated, and must have dimensions at least as
   big as the first.  The space occupied by entries in the second matrix is
   freed for general use (which may include being reused immediately for 
   the copies of the entries in the first matrix). */

void mod2sparse_copy
( mod2sparse *m,	/* Matrix to copy */
  mod2sparse *r		/* Place to store copy of matrix */
)
{
  mod2entry *e;
  int i;

  if (mod2sparse_rows(m)>mod2sparse_rows(r) 
   || mod2sparse_cols(m)>mod2sparse_cols(r))
  { fprintf(stderr,"mod2sparse_copy: Destination matrix is too small\n");
    exit(1);
  }

  mod2sparse_clear(r);

  for (i = 0; i<mod2sparse_rows(m); i++)
  {
    e = mod2sparse_first_in_row(m,i); 

    while (!mod2sparse_at_end(e))
    { mod2sparse_insert(r,e->row,e->col);
      e = mod2sparse_next_in_row(e);
    }
  }
}


/* COPY COLUMNS OF A SPARSE MOD2 MATRIX.  Copies selected columns of the 
   first matrix to the second matrix (which must already exist, and have 
   at least as many rows as the first matrix).  The columns to copy
   are given in order as an array of length the same as the number of 
   columns in the second matrix; duplicates are allowed. */

void mod2sparse_copycols
( mod2sparse *m,	/* Matrix to copy */
  mod2sparse *r,	/* Place to store copy of matrix */
  int *cols		/* Index of columns to copy, from 0 */
)
{ 
  mod2entry *e;
  int j;

  if (mod2sparse_rows(m)>mod2sparse_rows(r))
  { fprintf(stderr,
      "mod2sparse_copycols: Destination matrix has fewer rows than source\n");
    exit(1);
  }

  mod2sparse_clear(r);

  for (j = 0; j<mod2sparse_cols(r); j++)
  { if (cols[j]<0 || cols[j]>=mod2sparse_cols(m))
    { fprintf(stderr,"mod2sparse_copycols: Column index out of range\n");
      exit(1);
    }
    e = mod2sparse_first_in_col(m,cols[j]);
    while (!mod2sparse_at_end(e))
    { mod2sparse_insert(r,e->row,e->col);
      e = mod2sparse_next_in_col(e);
    }
  }
}


/* PRINT A SPARSE MOD2 MATRIX IN HUMAN-READABLE FORM.  The output consists of
   one line per row, of the form 

      row: col col col ...

   where 'row' is the index of the row, and the 'col' entries are the indexes
   of columns that are non-zero in that row.  Indexes start at zero.  The
   number of columns is not indicated in the output. */

void mod2sparse_print
( FILE *f,
  mod2sparse *m
)
{ 
  int rdigits, cdigits;
  mod2entry *e;
  int i;

  rdigits = mod2sparse_rows(m)<=10 ? 1 
          : mod2sparse_rows(m)<=100 ? 2
          : mod2sparse_rows(m)<=1000 ? 3
          : mod2sparse_rows(m)<=10000 ? 4
          : mod2sparse_rows(m)<=100000 ? 5
          : 6;

  cdigits = mod2sparse_cols(m)<=10 ? 1 
          : mod2sparse_cols(m)<=100 ? 2
          : mod2sparse_cols(m)<=1000 ? 3
          : mod2sparse_cols(m)<=10000 ? 4
          : mod2sparse_cols(m)<=100000 ? 5
          : 6;

  for (i = 0; i<mod2sparse_rows(m); i++)
  { 
    fprintf(f,"%*d:",rdigits,i);

    e = mod2sparse_first_in_row(m,i);
    while (!mod2sparse_at_end(e))
    { fprintf(f," %*d",cdigits,mod2sparse_col(e));
      e = mod2sparse_next_in_row(e);
    }

    fprintf(f,"\n");
  }
}


/* WRITE A SPARSE MOD2 MATRIX TO A FILE IN MACHINE-READABLE FORM.  Returns
   one if successful, zero if an error of some sort occurred. 

   The data written to the file is machine but not human readable.  It 
   consists of negative integers giving row indexes (starting at 1), which
   apply until the next row index, and positive integers giving column 
   indexes (starting at 1) for a non-zero entry in the matrix.  A zero index
   is written at the end.

   Data is written one byte at a time using intio_write so that it will 
   be readable on a machine with a different byte ordering. */

int mod2sparse_write
( FILE *f,
  mod2sparse *m
)
{
  mod2entry *e;
  int i;

  intio_write(f,m->n_rows);
  if (ferror(f)) return 0;

  intio_write(f,m->n_cols);
  if (ferror(f)) return 0;

  for (i = 0; i<mod2sparse_rows(m); i++)
  { 
    e = mod2sparse_first_in_row(m,i);

    if (!mod2sparse_at_end(e))
    {
      intio_write (f, -(i+1));
      if (ferror(f)) return 0;

      while (!mod2sparse_at_end(e))
      { 
        intio_write (f, mod2sparse_col(e)+1);
        if (ferror(f)) return 0;

        e = mod2sparse_next_in_row(e);
      }
    }
  }

  intio_write(f,0);
  if (ferror(f)) return 0;

  return 1;
}


/* READ A SPARSE MOD2 MATRIX STORED IN MACHINE-READABLE FORM FROM A FILE.  
   The data is expected to be in the format written by mod2sparse_write.  
   The value returned is zero if some sort of error occurred (either an
   error reading the file, or data not in the right format).

   The file is left positioned after the last of the data read.  Other data
   (such as another matrix) may follow. */

mod2sparse *mod2sparse_read
( FILE *f
)
{
  int n_rows, n_cols;
  mod2sparse *m;
  int v, row, col;

  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 = mod2sparse_allocate(n_rows,n_cols);

  row = -1;

  for (;;)
  {
    v = intio_read(f);
    if (feof(f) || ferror(f)) break;

    if (v==0)
    { return m;
    }
    else if (v<0) 
    { row = -v-1;
      if (row>=n_rows) break;
    }
    else 
    { col = v-1;
      if (col>=n_cols) break;
      if (row==-1) break;
      mod2sparse_insert(m,row,col);
    }
  }

  /* Error if we get here. */

  mod2sparse_free(m);
  return 0;   
}


/* LOOK FOR AN ENTRY WITH GIVEN ROW AND COLUMN.  If the given element is
   non-zero, a pointer to its entry is returned.  If the element is zero
   (and hence has no entry), a zero pointer is returned. 

   This procedure first looks to see if the entry is the last in its row or 
   in its column (or would be if it existed).  If it isn't, it searches in 
   parallel from the beginning of the row and the beginning of the column, 
   so that the operation will be fast if either the row or the column is 
   sparse. */

mod2entry *mod2sparse_find
( mod2sparse *m,
  int row,
  int col
)
{ 
  mod2entry *re, *ce;

  if (row<0 || row>=mod2sparse_rows(m) || col<0 || col>=mod2sparse_cols(m))
  { fprintf(stderr,"mod2sparse_find: row or column index out of bounds\n");
    exit(1);
  }

  /* Check last entries in row and column. */

  re = mod2sparse_last_in_row(m,row);
  if (mod2sparse_at_end(re) || mod2sparse_col(re)<col) 
  { return 0;
  }
  if (mod2sparse_col(re)==col) 
  { return re;
  }

  ce = mod2sparse_last_in_col(m,col);
  if (mod2sparse_at_end(ce) || mod2sparse_row(ce)<row)
  { return 0;
  }
  if (mod2sparse_row(ce)==row)
  { return ce;
  }

  /* Search row and column in parallel, from the front. */

  re = mod2sparse_first_in_row(m,row);
  ce = mod2sparse_first_in_col(m,col);

  for (;;)
  { 
    if (mod2sparse_at_end(re) || mod2sparse_col(re)>col)
    { return 0;
    } 
    if (mod2sparse_col(re)==col) 
    { return re;
    }

    if (mod2sparse_at_end(ce) || mod2sparse_row(ce)>row)
    { return 0;
    } 
    if (mod2sparse_row(ce)==row)
    { return ce;
    }

    re = mod2sparse_next_in_row(re);
    ce = mod2sparse_next_in_col(ce);
  }
}


/* INSERT AN ENTRY WITH GIVEN ROW AND COLUMN.  Adds a new entry at the given
   row and column.  If such an entry already exists, nothing is done (this 
   is not considered to be an error). 

   This procedure first looks to see if the entry belongs at the end of the
   the row and/or column.  If it doesn't, it searches for its place in the 
   row or column starting from the beginning. 

   Inserting an entry may require allocating space from the general memory
   pool, which may fail, in which case a message is printed and the program
   terminated. */

mod2entry *mod2sparse_insert
( mod2sparse *m,
  int row,
  int col
)
{
  mod2entry *re, *ce, *ne;

  if (row<0 || row>=mod2sparse_rows(m) || col<0 || col>=mod2sparse_cols(m))
  { fprintf(stderr,"mod2sparse_insert: row or column index out of bounds\n");
    exit(1);
  }

  /* Find old entry and return it, or allocate new entry and insert into row. */

  re = mod2sparse_last_in_row(m,row);

  if (!mod2sparse_at_end(re) && mod2sparse_col(re)==col) 
  { return re;
  }

  if (mod2sparse_at_end(re) || mod2sparse_col(re)<col) 
  { re = re->right;
  }
  else
  {
    re = mod2sparse_first_in_row(m,row);

    for (;;)
    {