-
Notifications
You must be signed in to change notification settings - Fork 92
/
mod2dense.h
113 lines (78 loc) · 4.35 KB
/
mod2dense.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/* MOD2DENSE.H - Interface to module for handling dense mod2 matrices. */
/* Copyright (c) 1995-2012 by Radford M. Neal.
*
* Permission is granted for anyone to copy, use, modify, and distribute
* these programs and accompanying documents for any purpose, provided
* this copyright notice is retained and prominently displayed, and note
* is made of any changes made to these programs. These programs and
* documents are distributed without any warranty, express or implied.
* As the programs were written for research purposes only, they have not
* been tested to the degree that would be advisable in any important
* application. All use of these programs is entirely at the user's own
* risk.
*/
/* This module implements operations on matrices of mod2 elements (bits,
with addition and multiplication being done modulo 2). The matrices
are stored with consecutive bits of a column packed into words, and
the procedures are implemented where possible using bit operations
on these words. This is an appropriate representation when the matrices
are dense (ie, 0s and 1s are about equally frequent).
All procedures in this module display an error message on standard
error and terminate the program if passed an invalid argument (indicative
of a programming error), or if memory cannot be allocated. Errors from
invalid contents of a file result in an error code being returned to the
caller, with no message being printed by this module.
*/
#include <stdint.h> /* Has the definition of uint32_t used below */
/* PACKING OF BITS INTO WORDS. Bits are packed into 32-bit words, with
the low-order bit coming first. */
typedef uint32_t mod2word; /* Data type that holds packed bits. If uint32_t
doesn't exist, change it to unsigned long */
#define mod2_wordsize 32 /* Number of bits that fit in a mod2word. Can't
be increased without changing intio module */
#define mod2_wordsize_shift 5 /* Amount to shift by to divide by wordsize */
#define mod2_wordsize_mask 0x1f /* What to AND with to produce mod wordsize */
/* Extract the i'th bit of a mod2word. */
#define mod2_getbit(w,i) (((w)>>(i))&1)
/* Make a word like w, but with the i'th bit set to 1 (if it wasn't already). */
#define mod2_setbit1(w,i) ((w)|(1<<(i)))
/* Make a word like w, but with the i'th bit set to 0 (if it wasn't already). */
#define mod2_setbit0(w,i) ((w)&(~(1<<(i))))
/* STRUCTURE REPRESENTING A DENSE MATRIX. These structures are dynamically
allocated using mod2dense_allocate (or by other procedures that call
mod2dense_allocate). They should be freed with mod2dense_free when no
longer required.
Direct access to this structure should be avoided except in low-level
routines. Use the macros and procedures defined below instead. */
typedef struct
{
int n_rows; /* Number of rows in the matrix */
int n_cols; /* Number of columns in the matrix */
int n_words; /* Number of words used to store a column of bits */
mod2word **col; /* Pointer to array of pointers to columns */
mod2word *bits; /* Pointer to storage block for bits in this matrix
(pieces of this block are pointed to from col) */
} mod2dense;
/* MACROS. */
#define mod2dense_rows(m) ((m)->n_rows) /* Get the number of rows or columns */
#define mod2dense_cols(m) ((m)->n_cols) /* in a matrix */
/* PROCEDURES. */
mod2dense *mod2dense_allocate (int, int);
void mod2dense_free (mod2dense *);
void mod2dense_clear (mod2dense *);
void mod2dense_copy (mod2dense *, mod2dense *);
void mod2dense_copyrows (mod2dense*, mod2dense *, int *);
void mod2dense_copycols (mod2dense*, mod2dense *, int *);
void mod2dense_print (FILE *, mod2dense *);
int mod2dense_write (FILE *, mod2dense *);
mod2dense *mod2dense_read (FILE *);
int mod2dense_get (mod2dense *, int, int);
void mod2dense_set (mod2dense *, int, int, int);
int mod2dense_flip(mod2dense *, int, int);
void mod2dense_transpose (mod2dense *, mod2dense *);
void mod2dense_add (mod2dense *, mod2dense *, mod2dense *);
void mod2dense_multiply (mod2dense *, mod2dense *, mod2dense *);
int mod2dense_equal (mod2dense *, mod2dense *);
int mod2dense_invert (mod2dense *, mod2dense *);
int mod2dense_forcibly_invert (mod2dense *, mod2dense *, int *, int *);
int mod2dense_invert_selected (mod2dense *, mod2dense *, int *, int *);