M4RI 20250128
mzd.h
Go to the documentation of this file.
1
10#ifndef M4RI_MZD
11#define M4RI_MZD
12
13/*******************************************************************
14 *
15 * M4RI: Linear Algebra over GF(2)
16 *
17 * Copyright (C) 2007, 2008 Gregory Bard <bard@fordham.edu>
18 * Copyright (C) 2008-2013 Martin Albrecht <M.R.Albrecht@rhul.ac.uk>
19 * Copyright (C) 2011 Carlo Wood <carlo@alinoe.com>
20 *
21 * Distributed under the terms of the GNU General Public License (GPL)
22 * version 2 or higher.
23 *
24 * This code is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 * General Public License for more details.
28 *
29 * The full text of the GPL is available at:
30 *
31 * http://www.gnu.org/licenses/
32 *
33 ********************************************************************/
34
35#ifdef HAVE_CONFIG_H
36#include "config.h"
37#endif
38
39#include <m4ri/m4ri_config.h>
40
41#include <assert.h>
42#include <math.h>
43#include <stdio.h>
44
45#if __M4RI_HAVE_SSE2
46#include <emmintrin.h>
47#endif
48
49#include <m4ri/debug_dump.h>
50
59#define __M4RI_MUL_BLOCKSIZE MIN(((int)sqrt((double)(4 * __M4RI_CPU_L3_CACHE))) / 2, 2048)
60
61
68typedef struct mzd_t {
69
79
92 uint8_t flags;
93
94 /* ensures sizeof(mzd_t) == 64 */
95 uint8_t padding[63 - 2 * sizeof(rci_t) - 2 * sizeof(wi_t) - sizeof(word) - sizeof(void *)];
96
98 word *data;
100
101/* clang-format off */
102/*
103 The rows are stacked consecutively in memory. The first word of the first row
104 is given by M->data.
105
106 Each row start M->rowstride words after the previous row (see the mzd_row function).
107
108 Windows are "views" into an underlying matrix, with potentially a smaller number
109 of rows and columns. The window has the same rowstride as the underlying matrix,
110 but they have a different data pointer. Because a window may start anywhere,
111 M->data cannot be expected to be aligned, at least not in windows.
112
113 There may or may not be extra (full) words between rows (always when the matrix
114 is a window, not necessarily when the matrix is not a window, depending on what
115 we do about alignment).
116
117 If (M->ncols % m4ri_radix != 0), then there are "excess bits" at the end of the row.
118 M->high_bitmask tells which bits are meaningful. M4RI policy is the following:
119 * if the matrix is not a window, the excess bits MUST be zero. In this case, they
120 MAY be overwritten (with fresh zeroes).
121 * if the matrix is a window with non-zero excess, then the excess bits MUST be
122 preserved (because they may be significant in the underlying matrix).
123
124
125 <------------------------ M->rowstride (in words) -------------------->
126
127 .-----------------------------------------------------------------------.
128 M->data ----> | [excess 0 bits]|
129 | [excess 0 bits]|
130 | .-------------------------------------. [excess 0 bits]|
131 W->data ------+----> |window [excess bits]| [excess 0 bits]|
132 | | [excess bits]| [excess 0 bits]|
133 | | [excess bits]| [excess 0 bits]|
134 | | [excess bits]| [excess 0 bits]|
135 | .-------------------------------------' [excess 0 bits]|
136 | [excess 0 bits]|
137 `-----------------------------------------------------------------------'
138*/
139/* clang-format on */
140
144static uint8_t const mzd_flag_nonzero_excess = 0x2;
145
150static uint8_t const mzd_flag_windowed = 0x4;
151
159static inline int mzd_is_windowed(mzd_t const *M) {
160 return M->flags & mzd_flag_windowed;
161}
162
170static inline int mzd_is_dangerous_window(mzd_t const *M) {
171 uint8_t const danger = mzd_flag_windowed | mzd_flag_nonzero_excess;
172 return (M->flags & danger) == danger;
173}
174
175
185static inline word *mzd_row(mzd_t *M, rci_t row) {
186 return M->data + M->rowstride * row;
187}
188
189static inline word const * mzd_row_const(mzd_t const *M, rci_t row) {
190 return mzd_row((mzd_t *)M, row);
191}
192
203mzd_t *mzd_init(rci_t const r, rci_t const c);
204
211void mzd_free(mzd_t *A);
212
234mzd_t *mzd_init_window(mzd_t *M, rci_t const lowr, rci_t const lowc, rci_t const highr,
235 rci_t const highc);
236
243static inline mzd_t const *mzd_init_window_const(mzd_t const *M, rci_t const lowr, rci_t const lowc,
244 rci_t const highr, rci_t const highc) {
245 return mzd_init_window((mzd_t *)M, lowr, lowc, highr, highc);
246}
247
254#define mzd_free_window mzd_free
255
265static inline void _mzd_row_swap(mzd_t *M, rci_t const rowa, rci_t const rowb,
266 wi_t const startblock) {
267 if ((rowa == rowb) || (startblock >= M->width)) { return; }
268
269 wi_t width = M->width - startblock - 1;
270 word *a = mzd_row(M, rowa) + startblock;
271 word *b = mzd_row(M, rowb) + startblock;
272 word tmp;
273 word const mask_end = M->high_bitmask;
274
275 for (wi_t i = 0; i < width; ++i) {
276 tmp = a[i];
277 a[i] = b[i];
278 b[i] = tmp;
279 }
280 tmp = (a[width] ^ b[width]) & mask_end;
281 a[width] ^= tmp;
282 b[width] ^= tmp;
283
284 __M4RI_DD_ROW(M, rowa);
285 __M4RI_DD_ROW(M, rowb);
286}
287
296static inline void mzd_row_swap(mzd_t *M, rci_t const rowa, rci_t const rowb) {
297 _mzd_row_swap(M, rowa, rowb, 0);
298}
299
312void mzd_copy_row(mzd_t *B, rci_t i, mzd_t const *A, rci_t j);
313
314
325static inline void mzd_col_swap_in_rows(mzd_t *M, rci_t const cola, rci_t const colb,
326 rci_t const start_row, rci_t const stop_row) {
327 if (cola == colb) { return; }
328
329 rci_t const _cola = cola;
330 rci_t const _colb = colb;
331
332 wi_t const a_word = _cola / m4ri_radix;
333 wi_t const b_word = _colb / m4ri_radix;
334
335 int const a_bit = _cola % m4ri_radix;
336 int const b_bit = _colb % m4ri_radix;
337
338 word *RESTRICT ptr = mzd_row(M, start_row);
339 int max_bit = MAX(a_bit, b_bit);
340 int count_remaining = stop_row - start_row;
341 int min_bit = a_bit + b_bit - max_bit;
342 int offset = max_bit - min_bit;
343 word mask = m4ri_one << min_bit;
344 int count = count_remaining;
345
346 // Apparently we're calling with start_row == stop_row sometimes (seems a bug to me).
347 if (count <= 0) { return; }
348
349 if (a_word == b_word) {
350 while (1) {
351 count_remaining -= count;
352 assert(count_remaining == 0);
353 ptr += a_word;
354 int fast_count = count / 4;
355 int rest_count = count - 4 * fast_count;
356 word xor_v[4];
357 wi_t const rowstride = M->rowstride;
358 while (fast_count--) {
359 xor_v[0] = ptr[0];
360 xor_v[1] = ptr[rowstride];
361 xor_v[2] = ptr[2 * rowstride];
362 xor_v[3] = ptr[3 * rowstride];
363 xor_v[0] ^= xor_v[0] >> offset;
364 xor_v[1] ^= xor_v[1] >> offset;
365 xor_v[2] ^= xor_v[2] >> offset;
366 xor_v[3] ^= xor_v[3] >> offset;
367 xor_v[0] &= mask;
368 xor_v[1] &= mask;
369 xor_v[2] &= mask;
370 xor_v[3] &= mask;
371 xor_v[0] |= xor_v[0] << offset;
372 xor_v[1] |= xor_v[1] << offset;
373 xor_v[2] |= xor_v[2] << offset;
374 xor_v[3] |= xor_v[3] << offset;
375 ptr[0] ^= xor_v[0];
376 ptr[rowstride] ^= xor_v[1];
377 ptr[2 * rowstride] ^= xor_v[2];
378 ptr[3 * rowstride] ^= xor_v[3];
379 ptr += 4 * rowstride;
380 }
381 while (rest_count--) {
382 word xor_v = *ptr;
383 xor_v ^= xor_v >> offset;
384 xor_v &= mask;
385 *ptr ^= xor_v | (xor_v << offset);
386 ptr += rowstride;
387 }
388 break;
389 }
390 } else {
391 word *RESTRICT min_ptr;
392 wi_t max_offset;
393 if (min_bit == a_bit) {
394 min_ptr = ptr + a_word;
395 max_offset = b_word - a_word;
396 } else {
397 min_ptr = ptr + b_word;
398 max_offset = a_word - b_word;
399 }
400 while (1) {
401 count_remaining -= count;
402 assert(count_remaining == 0);
403 wi_t const rowstride = M->rowstride;
404 while (count--) {
405 word xor_v = (min_ptr[0] ^ (min_ptr[max_offset] >> offset)) & mask;
406 min_ptr[0] ^= xor_v;
407 min_ptr[max_offset] ^= xor_v << offset;
408 min_ptr += rowstride;
409 }
410 break;
411 }
412 }
413
414 __M4RI_DD_MZD(M);
415}
416
424static inline void mzd_col_swap(mzd_t *M, rci_t const cola, rci_t const colb) {
425 mzd_col_swap_in_rows(M, cola, colb, 0, M->nrows);
426}
427
428
440static inline BIT mzd_read_bit(mzd_t const *M, rci_t const row, rci_t const col) {
441 word const * truerow = mzd_row_const(M, row);
442 return __M4RI_GET_BIT(truerow[col / m4ri_radix], col % m4ri_radix);
443}
444
457static inline void mzd_write_bit(mzd_t *M, rci_t const row, rci_t const col, BIT const value) {
458 word * truerow = mzd_row(M, row);
459 __M4RI_WRITE_BIT(truerow[col / m4ri_radix], col % m4ri_radix, value);
460}
461
472static inline void mzd_xor_bits(mzd_t *M, rci_t const x, rci_t const y, int const n,
473 word values) {
474 int const spot = y % m4ri_radix;
475 wi_t const block = y / m4ri_radix;
476 word *row = mzd_row(M, x);
477 row[block] ^= values << spot;
478 int const space = m4ri_radix - spot;
479 if (n > space) { row[block + 1] ^= values >> space; }
480}
481
492static inline void mzd_and_bits(mzd_t *M, rci_t const x, rci_t const y, int const n,
493 word values) {
494 /* This is the best way, since this will drop out once we inverse the bits in values: */
495 values >>= (m4ri_radix - n); /* Move the bits to the lowest columns */
496
497 int const spot = y % m4ri_radix;
498 wi_t const block = y / m4ri_radix;
499 word *row = mzd_row(M, x);
500 row[block] &= values << spot;
501 int const space = m4ri_radix - spot;
502 if (n > space) { row[block + 1] &= values >> space; }
503}
504
514static inline void mzd_clear_bits(mzd_t *M, rci_t const x, rci_t const y, int const n) {
515 assert(n > 0 && n <= m4ri_radix);
516 word values = m4ri_ffff >> (m4ri_radix - n);
517 int const spot = y % m4ri_radix;
518 wi_t const block = y / m4ri_radix;
519 word *row = mzd_row(M, x);
520 row[block] &= ~(values << spot);
521 int const space = m4ri_radix - spot;
522 if (n > space) { row[block + 1] &= ~(values >> space); }
523}
524
537static inline void mzd_row_add_offset(mzd_t *M, rci_t dstrow, rci_t srcrow, rci_t coloffset) {
538 assert(dstrow < M->nrows && srcrow < M->nrows && coloffset < M->ncols);
539 wi_t const startblock = coloffset / m4ri_radix;
540 wi_t wide = M->width - startblock;
541 word *src = mzd_row(M, srcrow) + startblock;
542 word *dst = mzd_row(M, dstrow) + startblock;
543 word const mask_begin = __M4RI_RIGHT_BITMASK(m4ri_radix - coloffset % m4ri_radix);
544 word const mask_end = M->high_bitmask;
545
546 *dst++ ^= *src++ & mask_begin;
547 --wide;
548
549#if __M4RI_HAVE_SSE2
550 int not_aligned = __M4RI_ALIGNMENT(src, 16) != 0; /* 0: Aligned, 1: Not aligned */
551 if (wide > not_aligned + 1) /* Speed up for small matrices */
552 {
553 if (not_aligned) {
554 *dst++ ^= *src++;
555 --wide;
556 }
557 /* Now wide > 1 */
558 __m128i *__src = (__m128i *)src;
559 __m128i *__dst = (__m128i *)dst;
560 __m128i *const eof = (__m128i *)((unsigned long)(src + wide) & ~0xFUL);
561 do {
562 __m128i xmm1 = _mm_xor_si128(*__dst, *__src);
563 *__dst++ = xmm1;
564 } while (++__src < eof);
565 src = (word *)__src;
566 dst = (word *)__dst;
567 wide = ((sizeof(word) * wide) % 16) / sizeof(word);
568 }
569#endif
570 wi_t i = -1;
571 while (++i < wide) { dst[i] ^= src[i]; }
572 /*
573 * Revert possibly non-zero excess bits.
574 * Note that i == wide here, and wide can be 0.
575 * But really, src[wide - 1] is M->rows[srcrow][M->width - 1] ;)
576 * We use i - 1 here to let the compiler know these are the same addresses
577 * that we last accessed, in the previous loop.
578 */
579 dst[i - 1] ^= src[i - 1] & ~mask_end;
580
581 __M4RI_DD_ROW(M, dstrow);
582}
583
595void mzd_row_add(mzd_t *M, rci_t const sourcerow, rci_t const destrow);
596
611mzd_t *mzd_transpose(mzd_t *DST, mzd_t const *A);
612
627mzd_t *mzd_mul_naive(mzd_t *C, mzd_t const *A, mzd_t const *B);
628
643mzd_t *mzd_addmul_naive(mzd_t *C, mzd_t const *A, mzd_t const *B);
644
656mzd_t *_mzd_mul_naive(mzd_t *C, mzd_t const *A, mzd_t const *B, int const clear);
657
667mzd_t *_mzd_mul_va(mzd_t *C, mzd_t const *v, mzd_t const *A, int const clear);
668
675void mzd_randomize(mzd_t *M);
676
685typedef word (*m4ri_random_callback)(void *data);
686
694void mzd_randomize_custom(mzd_t *M, m4ri_random_callback rc, void *data);
695
710void mzd_set_ui(mzd_t *M, unsigned int const value);
711
725rci_t mzd_gauss_delayed(mzd_t *M, rci_t const startcol, int const full);
726
740rci_t mzd_echelonize_naive(mzd_t *M, int const full);
741
749int mzd_equal(mzd_t const *A, mzd_t const *B);
750
762int mzd_cmp(mzd_t const *A, mzd_t const *B);
763
771mzd_t *mzd_copy(mzd_t *DST, mzd_t const *A);
772
791mzd_t *mzd_concat(mzd_t *C, mzd_t const *A, mzd_t const *B);
792
810mzd_t *mzd_stack(mzd_t *C, mzd_t const *A, mzd_t const *B);
811
824mzd_t *mzd_submatrix(mzd_t *S, mzd_t const *M, rci_t const lowr, rci_t const lowc,
825 rci_t const highr, rci_t const highc);
826
838mzd_t *mzd_invert_naive(mzd_t *INV, mzd_t const *A, mzd_t const *I);
839
851mzd_t *mzd_add(mzd_t *C, mzd_t const *A, mzd_t const *B);
852
861mzd_t *_mzd_add(mzd_t *C, mzd_t const *A, mzd_t const *B);
862
871#define mzd_sub mzd_add
872
881#define _mzd_sub _mzd_add
882
892static inline word mzd_read_bits(mzd_t const *M, rci_t const x, rci_t const y, int const n) {
893 int const spot = y % m4ri_radix;
894 wi_t const block = y / m4ri_radix;
895 int const spill = spot + n - m4ri_radix;
896 word const *row = mzd_row_const(M, x);
897 word temp = (spill <= 0)
898 ? row[block] << -spill
899 : (row[block + 1] << (m4ri_radix - spill)) | (row[block] >> spill);
900 return temp >> (m4ri_radix - n);
901}
902
919static inline void mzd_combine_even_in_place(mzd_t *A, rci_t const a_row, wi_t const a_startblock,
920 mzd_t const *B, rci_t const b_row,
921 wi_t const b_startblock) {
922
923 wi_t wide = A->width - a_startblock - 1;
924
925 word *a = mzd_row(A, a_row) + a_startblock;
926 word const *b = mzd_row_const(B, b_row) + b_startblock;
927
928#if __M4RI_HAVE_SSE2
929 if (wide > 2) {
931 if (__M4RI_ALIGNMENT(a, 16)) {
932 *a++ ^= *b++;
933 wide--;
934 }
935
936 if (__M4RI_ALIGNMENT(a, 16) == 0 && __M4RI_ALIGNMENT(b, 16) == 0) {
937 __m128i *a128 = (__m128i *)a;
938 __m128i *b128 = (__m128i *)b;
939 const __m128i *eof = (__m128i *)((unsigned long)(a + wide) & ~0xFUL);
940
941 do {
942 *a128 = _mm_xor_si128(*a128, *b128);
943 ++b128;
944 ++a128;
945 } while (a128 < eof);
946
947 a = (word *)a128;
948 b = (word *)b128;
949 wide = ((sizeof(word) * wide) % 16) / sizeof(word);
950 }
951 }
952#endif // __M4RI_HAVE_SSE2
953
954 if (wide > 0) {
955 wi_t n = (wide + 7) / 8;
956 switch (wide % 8) {
957 case 0: do { *(a++) ^= *(b++);
958 case 7: *(a++) ^= *(b++);
959 case 6: *(a++) ^= *(b++);
960 case 5: *(a++) ^= *(b++);
961 case 4: *(a++) ^= *(b++);
962 case 3: *(a++) ^= *(b++);
963 case 2: *(a++) ^= *(b++);
964 case 1: *(a++) ^= *(b++);
965 } while (--n > 0);
966 }
967 }
968
969 *a ^= *b & A->high_bitmask;
970
971 __M4RI_DD_MZD(A);
972}
973
993static inline void mzd_combine_even(mzd_t *C, rci_t const c_row, wi_t const c_startblock,
994 mzd_t const *A, rci_t const a_row, wi_t const a_startblock,
995 mzd_t const *B, rci_t const b_row, wi_t const b_startblock) {
996
997 wi_t wide = A->width - a_startblock - 1;
998 word const *a = mzd_row_const(A, a_row) + a_startblock;
999 word const *b = mzd_row_const(B, b_row) + b_startblock;
1000 word *c = mzd_row(C, c_row) + c_startblock;
1001
1002#if __M4RI_HAVE_SSE2
1003 if (wide > 2) {
1005 if (__M4RI_ALIGNMENT(a, 16)) {
1006 *c++ = *b++ ^ *a++;
1007 wide--;
1008 }
1009
1010 if ((__M4RI_ALIGNMENT(b, 16) | __M4RI_ALIGNMENT(c, 16)) == 0) {
1011 __m128i *a128 = (__m128i *)a;
1012 __m128i *b128 = (__m128i *)b;
1013 __m128i *c128 = (__m128i *)c;
1014 const __m128i *eof = (__m128i *)((unsigned long)(a + wide) & ~0xFUL);
1015
1016 do {
1017 *c128 = _mm_xor_si128(*a128, *b128);
1018 ++c128;
1019 ++b128;
1020 ++a128;
1021 } while (a128 < eof);
1022
1023 a = (word *)a128;
1024 b = (word *)b128;
1025 c = (word *)c128;
1026 wide = ((sizeof(word) * wide) % 16) / sizeof(word);
1027 }
1028 }
1029#endif // __M4RI_HAVE_SSE2
1030
1031 if (wide > 0) {
1032 wi_t n = (wide + 7) / 8;
1033 switch (wide % 8) {
1034 case 0: do { *(c++) = *(a++) ^ *(b++);
1035 case 7: *(c++) = *(a++) ^ *(b++);
1036 case 6: *(c++) = *(a++) ^ *(b++);
1037 case 5: *(c++) = *(a++) ^ *(b++);
1038 case 4: *(c++) = *(a++) ^ *(b++);
1039 case 3: *(c++) = *(a++) ^ *(b++);
1040 case 2: *(c++) = *(a++) ^ *(b++);
1041 case 1: *(c++) = *(a++) ^ *(b++);
1042 } while (--n > 0);
1043 }
1044 }
1045 *c ^= ((*a ^ *b ^ *c) & C->high_bitmask);
1046
1047 __M4RI_DD_MZD(C);
1048}
1049
1068static inline void mzd_combine(mzd_t *C, rci_t const c_row, wi_t const c_startblock, mzd_t const *A,
1069 rci_t const a_row, wi_t const a_startblock, mzd_t const *B,
1070 rci_t const b_row, wi_t const b_startblock) {
1071
1072 if ((C == A) & (a_row == c_row) & (a_startblock == c_startblock)) {
1073 mzd_combine_even_in_place(C, c_row, c_startblock, B, b_row, b_startblock);
1074 } else {
1075 mzd_combine_even(C, c_row, c_startblock, A, a_row, a_startblock, B, b_row, b_startblock);
1076 }
1077 return;
1078}
1079
1088static inline int mzd_read_bits_int(mzd_t const *M, rci_t const x, rci_t const y, int const n) {
1089 return __M4RI_CONVERT_TO_INT(mzd_read_bits(M, x, y, n));
1090}
1091
1098int mzd_is_zero(mzd_t const *A);
1099
1108void mzd_row_clear_offset(mzd_t *M, rci_t const row, rci_t const coloffset);
1109
1126int mzd_find_pivot(mzd_t const *M, rci_t start_row, rci_t start_col, rci_t *r, rci_t *c);
1127
1140double mzd_density(mzd_t const *A, wi_t res);
1141
1156double _mzd_density(mzd_t const *A, wi_t res, rci_t r, rci_t c);
1157
1167
1174static inline word mzd_hash(mzd_t const *A) {
1175 word hash = 0;
1176 for (rci_t r = 0; r < A->nrows; ++r) {
1177 hash ^= rotate_word(calculate_hash(mzd_row_const(A, r), A->width), r % m4ri_radix);
1178 }
1179 return hash;
1180}
1181
1191mzd_t *mzd_extract_u(mzd_t *U, mzd_t const *A);
1192
1202mzd_t *mzd_extract_l(mzd_t *L, mzd_t const *A);
1203
1204#endif // M4RI_MZD
int rci_t
Type of row and column indexes.
Definition misc.h:72
#define __M4RI_ALIGNMENT(addr, n)
Return alignment of addr w.r.t. n. For example the address 17 would be 1 aligned w....
Definition misc.h:421
int64_t wi_t
Type of word indexes.
Definition misc.h:81
#define __M4RI_CONVERT_TO_INT(w)
Explicit conversion macro.
Definition misc.h:99
#define __M4RI_GET_BIT(w, spot)
Get the bit spot (counting from the left) in the word w.
Definition misc.h:226
#define __M4RI_WRITE_BIT(w, spot, value)
Write the value to the bit spot in the word w.
Definition misc.h:236
uint64_t word
A word is the typical packed data structure to represent packed bits.
Definition misc.h:87
int BIT
Pretty for a boolean int.
Definition misc.h:64
static word const m4ri_ffff
A word with all bits set.
Definition misc.h:153
static int const m4ri_radix
The number of bits in a word.
Definition misc.h:141
#define MAX(x, y)
Return the maximal element of x and y.
Definition misc.h:163
#define __M4RI_RIGHT_BITMASK(n)
create a bit mask to zero out all but the n rightmost bits.
Definition misc.h:297
static word const m4ri_one
The number one as a word.
Definition misc.h:147
mzd_t * mzd_transpose(mzd_t *DST, mzd_t const *A)
Transpose a matrix.
Definition mzd.c:1119
static int mzd_is_windowed(mzd_t const *M)
Test if a matrix is windowed.
Definition mzd.h:159
static uint8_t const mzd_flag_nonzero_excess
flag when ncols%64 != 0
Definition mzd.h:144
mzd_t * mzd_submatrix(mzd_t *S, mzd_t const *M, rci_t const lowr, rci_t const lowc, rci_t const highr, rci_t const highc)
Copy a submatrix.
Definition mzd.c:1586
rci_t mzd_echelonize_naive(mzd_t *M, int const full)
Gaussian elimination.
Definition mzd.c:234
word(* m4ri_random_callback)(void *data)
Random callback that produces uniformly distributed random words on every call.
Definition mzd.h:685
static void mzd_col_swap_in_rows(mzd_t *M, rci_t const cola, rci_t const colb, rci_t const start_row, rci_t const stop_row)
Swap the two columns cola and colb but only between start_row and stop_row.
Definition mzd.h:325
void mzd_randomize(mzd_t *M)
Fill matrix M with uniformly distributed bits.
Definition mzd.c:1271
void mzd_row_clear_offset(mzd_t *M, rci_t const row, rci_t const coloffset)
Clear the given row, but only begins at the column coloffset.
Definition mzd.c:192
void mzd_randomize_custom(mzd_t *M, m4ri_random_callback rc, void *data)
Fill matrix M with uniformly distributed bits.
Definition mzd.c:1283
mzd_t * mzd_stack(mzd_t *C, mzd_t const *A, mzd_t const *B)
Stack A on top of B and write the result to C.
Definition mzd.c:1411
void mzd_row_add(mzd_t *M, rci_t const sourcerow, rci_t const destrow)
Add the rows sourcerow and destrow and stores the total in the row destrow.
Definition mzd.c:188
void mzd_free(mzd_t *A)
Free a matrix created with mzd_init.
Definition mzd.c:180
rci_t mzd_first_zero_row(mzd_t const *A)
Return the first row with all zero entries.
Definition mzd.c:1827
static void mzd_row_swap(mzd_t *M, rci_t const rowa, rci_t const rowb)
Swap the two rows rowa and rowb.
Definition mzd.h:296
static uint8_t const mzd_flag_windowed
flag for windowed matrix
Definition mzd.h:150
mzd_t * mzd_init(rci_t const r, rci_t const c)
Create a new matrix of dimension r x c.
Definition mzd.c:142
int mzd_cmp(mzd_t const *A, mzd_t const *B)
Return -1,0,1 if if A < B, A == B or A > B respectively.
Definition mzd.c:1334
static void mzd_row_add_offset(mzd_t *M, rci_t dstrow, rci_t srcrow, rci_t coloffset)
Add the rows sourcerow and destrow and stores the total in the row destrow, but only begins at the co...
Definition mzd.h:537
void mzd_copy_row(mzd_t *B, rci_t i, mzd_t const *A, rci_t j)
copy row j from A to row i from B.
Definition mzd.c:1642
mzd_t * mzd_invert_naive(mzd_t *INV, mzd_t const *A, mzd_t const *I)
Invert the matrix target using Gaussian elimination.
Definition mzd.c:1438
mzd_t * _mzd_mul_va(mzd_t *C, mzd_t const *v, mzd_t const *A, int const clear)
Matrix multiplication optimized for v*A where v is a vector.
Definition mzd.c:1257
static void mzd_and_bits(mzd_t *M, rci_t const x, rci_t const y, int const n, word values)
AND n bits from values to M starting a position (x,y).
Definition mzd.h:492
mzd_t * mzd_addmul_naive(mzd_t *C, mzd_t const *A, mzd_t const *B)
Naive cubic matrix multiplication and addition.
Definition mzd.c:1160
int mzd_is_zero(mzd_t const *A)
Zero test for matrix.
Definition mzd.c:1630
double mzd_density(mzd_t const *A, wi_t res)
Return the number of nonzero entries divided by nrows * ncols.
Definition mzd.c:1825
static void mzd_combine_even(mzd_t *C, rci_t const c_row, wi_t const c_startblock, mzd_t const *A, rci_t const a_row, wi_t const a_startblock, mzd_t const *B, rci_t const b_row, wi_t const b_startblock)
c_row[c_startblock:] = a_row[a_startblock:] + b_row[b_startblock:] for offset 0
Definition mzd.h:993
static void mzd_clear_bits(mzd_t *M, rci_t const x, rci_t const y, int const n)
Clear n bits in M starting a position (x,y).
Definition mzd.h:514
static void _mzd_row_swap(mzd_t *M, rci_t const rowa, rci_t const rowb, wi_t const startblock)
Swap the two rows rowa and rowb starting at startblock.
Definition mzd.h:265
static word * mzd_row(mzd_t *M, rci_t row)
Get pointer to first word of row.
Definition mzd.h:185
static void mzd_combine_even_in_place(mzd_t *A, rci_t const a_row, wi_t const a_startblock, mzd_t const *B, rci_t const b_row, wi_t const b_startblock)
a_row[a_startblock:] += b_row[b_startblock:] for offset 0
Definition mzd.h:919
static word mzd_hash(mzd_t const *A)
Return hash value for matrix.
Definition mzd.h:1174
mzd_t * mzd_concat(mzd_t *C, mzd_t const *A, mzd_t const *B)
Concatenate B to A and write the result to C.
Definition mzd.c:1386
struct mzd_t mzd_t
Dense matrices over GF(2).
static int mzd_read_bits_int(mzd_t const *M, rci_t const x, rci_t const y, int const n)
Get n bits starting a position (x,y) from the matrix M.
Definition mzd.h:1088
rci_t mzd_gauss_delayed(mzd_t *M, rci_t const startcol, int const full)
Gaussian elimination.
Definition mzd.c:209
static void mzd_combine(mzd_t *C, rci_t const c_row, wi_t const c_startblock, mzd_t const *A, rci_t const a_row, wi_t const a_startblock, mzd_t const *B, rci_t const b_row, wi_t const b_startblock)
row3[col3:] = row1[col1:] + row2[col2:]
Definition mzd.h:1068
double _mzd_density(mzd_t const *A, wi_t res, rci_t r, rci_t c)
Return the number of nonzero entries divided by nrows * ncols considering only the submatrix starting...
Definition mzd.c:1793
static word mzd_read_bits(mzd_t const *M, rci_t const x, rci_t const y, int const n)
Definition mzd.h:892
static void mzd_write_bit(mzd_t *M, rci_t const row, rci_t const col, BIT const value)
Write the bit value to position M[row,col].
Definition mzd.h:457
static void mzd_col_swap(mzd_t *M, rci_t const cola, rci_t const colb)
Swap the two columns cola and colb.
Definition mzd.h:424
static void mzd_xor_bits(mzd_t *M, rci_t const x, rci_t const y, int const n, word values)
XOR n bits from values to M starting a position (x,y).
Definition mzd.h:472
static int mzd_is_dangerous_window(mzd_t const *M)
Test if a matrix is windowed with non-zero excess.
Definition mzd.h:170
mzd_t * mzd_extract_u(mzd_t *U, mzd_t const *A)
Definition mzd.c:1844
mzd_t * _mzd_mul_naive(mzd_t *C, mzd_t const *A, mzd_t const *B, int const clear)
Naive cubic matrix multiplication with the pre-transposed B.
Definition mzd.c:1175
mzd_t * mzd_init_window(mzd_t *M, rci_t const lowr, rci_t const lowc, rci_t const highr, rci_t const highc)
Create a window/view into the matrix M.
Definition mzd.c:160
int mzd_equal(mzd_t const *A, mzd_t const *B)
Return TRUE if A == B.
Definition mzd.c:1315
static BIT mzd_read_bit(mzd_t const *M, rci_t const row, rci_t const col)
Read the bit at position M[row,col].
Definition mzd.h:440
mzd_t * mzd_copy(mzd_t *DST, mzd_t const *A)
Copy matrix A to DST.
Definition mzd.c:1364
mzd_t * mzd_extract_l(mzd_t *L, mzd_t const *A)
Definition mzd.c:1856
mzd_t * mzd_add(mzd_t *C, mzd_t const *A, mzd_t const *B)
Set C = A+B.
Definition mzd.c:1458
int mzd_find_pivot(mzd_t const *M, rci_t start_row, rci_t start_col, rci_t *r, rci_t *c)
Find the next nonzero entry in M starting at start_row and start_col.
Definition mzd.c:1662
static mzd_t const * mzd_init_window_const(mzd_t const *M, rci_t const lowr, rci_t const lowc, rci_t const highr, rci_t const highc)
Create a const window/view into a const matrix M.
Definition mzd.h:243
mzd_t * _mzd_add(mzd_t *C, mzd_t const *A, mzd_t const *B)
Same as mzd_add but without any checks on the input.
Definition mzd.c:1472
void mzd_set_ui(mzd_t *M, unsigned int const value)
Set the matrix M to the value equivalent to the integer value provided.
Definition mzd.c:1295
mzd_t * mzd_mul_naive(mzd_t *C, mzd_t const *A, mzd_t const *B)
Naive cubic matrix multiplication.
Definition mzd.c:1142
Dense matrices over GF(2).
Definition mzd.h:68
wi_t rowstride
Definition mzd.h:78
wi_t width
Definition mzd.h:72
rci_t nrows
Definition mzd.h:70
uint8_t flags
Definition mzd.h:92
word high_bitmask
Definition mzd.h:97
rci_t ncols
Definition mzd.h:71