1 /*
2 * \author Martin Kunev <martinkunev@gmail.com> original implementation of C99 heap
3 * \author Martin Albrecht <martinralbrecht@googlemail.com> adapted to M4RI + DJB map
4 */
5
6 #ifdef HAVE_CONFIG_H
7 #include "config.h"
8 #endif
9
10 #include <m4ri/mzd.h>
11 #include <m4ri/io.h>
12 #include <m4ri/misc.h>
13 #include <m4ri/djb.h>
14 #include <m4ri/xor.h>
15
16 #ifndef _MSC_VER
17 #include <unistd.h>
18 #endif
19 #include <stdlib.h>
20
mzd_compare_rows_revlex(const mzd_t * A,rci_t a,rci_t b)21 static inline int mzd_compare_rows_revlex(const mzd_t *A, rci_t a, rci_t b) {
22 for(wi_t j=A->width-1; j>=0; j--) {
23 if (A->rows[a][j] < A->rows[b][j])
24 return 0;
25 if (A->rows[a][j] > A->rows[b][j])
26 return 1;
27 }
28 return 1;
29 }
30
31 /**
32 * \brief A Heap
33 */
34
35 typedef struct heap {
36 unsigned int size; /*!< Size of the allocated memory (in number of items) */
37 unsigned int count; /*!< Count of the elements in the heap */
38 rci_t *data; /*!< Array with the elements */
39 } heap_t;
40
41 // Returns the biggest element in the heap
42 #define heap_front(h) (*(h)->data)
43
heap_free(heap_t * h)44 void heap_free(heap_t *h) {
45 free(h->data);
46 free(h);
47 }
48
49 static const unsigned int heap_base_size = 4;
50
51 // Prepares the heap for use
heap_init()52 heap_t *heap_init() {
53 heap_t * h = (heap_t*)malloc(sizeof(heap_t));
54 if (h == NULL) m4ri_die("malloc failed.\n");
55 *h = (heap_t){
56 .size = heap_base_size,
57 .count = 0,
58 .data = malloc(sizeof(rci_t) * heap_base_size)
59 };
60 if (h->data == NULL) m4ri_die("malloc failed.\n");
61 return h;
62 }
63
64 // Inserts element to the heap
heap_push(struct heap * restrict h,rci_t value,const mzd_t * A)65 void heap_push(struct heap *restrict h, rci_t value, const mzd_t *A) {
66 unsigned int index, parent;
67
68 // Resize the heap if it is too small to hold all the data
69 if (h->count == h->size) {
70 h->size <<= 1;
71 h->data = realloc(h->data, sizeof(rci_t) * h->size);
72 if (h->data == NULL) m4ri_die("realloc failed.\n");
73 }
74
75 // Find out where to put the element and put it
76 for(index = h->count++; index; index = parent) {
77 parent = (index - 1) >> 1;
78 if (mzd_compare_rows_revlex(A, h->data[parent], value))
79 break;
80 h->data[index] = h->data[parent];
81 }
82 h->data[index] = value;
83 }
84
85 // Removes the biggest element from the heap
heap_pop(struct heap * restrict h,const mzd_t * A)86 void heap_pop(struct heap *restrict h, const mzd_t *A) {
87 unsigned int index, swap, other;
88
89 // Remove the biggest element
90 rci_t temp = h->data[--h->count];
91
92 // Resize the heap if it's consuming too much memory
93 if ((h->count <= (h->size >> 2)) && (h->size > heap_base_size)) {
94 h->size >>= 1;
95 h->data = realloc(h->data, sizeof(rci_t) * h->size);
96 if (h->data == NULL) m4ri_die("realloc failed.\n");
97 }
98
99 // Reorder the elements
100 for(index = 0; 1; index = swap) {
101 // Find the child to swap with
102 swap = (index << 1) + 1;
103 if (swap >= h->count) break; // If there are no children, the heap is reordered
104 other = swap + 1;
105 if ((other < h->count) && mzd_compare_rows_revlex(A, h->data[other], h->data[swap])) swap = other;
106 if (mzd_compare_rows_revlex(A, temp, h->data[swap]))
107 break; // If the bigger child is less than or equal to its parent, the heap is reordered
108
109 h->data[index] = h->data[swap];
110 }
111 h->data[index] = temp;
112 }
113
djb_compile(mzd_t * A)114 djb_t *djb_compile(mzd_t *A) {
115 heap_t *h = heap_init();
116 rci_t m = A->nrows;
117 rci_t n = A->ncols;
118
119 djb_t *z = djb_init(m, n);
120
121 for (rci_t i=0; i < m; i++)
122 heap_push(h, i, A); // sort by mzd_compare_rows_revlex
123
124 while (n > 0) {
125 if (mzd_read_bit(A, heap_front(h), n - 1) == 0) {
126 --n;
127 continue;
128 }
129
130 rci_t temp = heap_front(h);
131 heap_pop(h, A);
132
133 if (m >= 2 && mzd_read_bit(A, heap_front(h), n - 1)) {
134 mzd_row_add(A, heap_front(h), temp);
135 djb_push_back(z, temp, heap_front(h), source_target);
136 } else {
137 mzd_write_bit(A, temp, n-1, 0);
138 djb_push_back(z, temp, n-1, source_source);
139 }
140 heap_push(h, temp, A);
141 }
142 heap_free(h);
143
144 return z;
145 }
146
djb_apply_mzd(djb_t * m,mzd_t * W,const mzd_t * V)147 void djb_apply_mzd(djb_t *m, mzd_t *W, const mzd_t *V) {
148 assert(W->width == V->width);
149 rci_t i = m->length;
150 while (i > 0) {
151 --i;
152 if (m->srctyp[i] == source_source) {
153 _mzd_combine(mzd_row(W, m->target[i]), mzd_row(V, m->source[i]), W->width);
154 } else {
155 _mzd_combine(mzd_row(W, m->target[i]), mzd_row(W, m->source[i]), W->width);
156 }
157 }
158 }
159
djb_print(djb_t * m)160 void djb_print(djb_t *m) {
161 int *iszero = m4ri_mm_malloc(sizeof(int)*m->nrows);
162 for(int i = 0; i < m->nrows; ++i)
163 iszero[i] = 1;
164
165 rci_t i = m->length;
166 while (i > 0) {
167 --i;
168 if (iszero[m->target[i]]) {
169 if (m->srctyp[i] == source_source) {
170 printf("cpy src[%d] to dst[%d]\n", m->source[i], m->target[i]);
171 } else {
172 printf("cpy dst[%d] to dst[%d]\n", m->source[i], m->target[i]);
173 }
174 iszero[m->target[i]] = 0;
175 } else {
176 if (m->srctyp[i] == source_source) {
177 printf("add src[%d] to dst[%d]\n", m->source[i], m->target[i]);
178 } else {
179 printf("add dst[%d] to dst[%d]\n", m->source[i], m->target[i]);
180 }
181 }
182 }
183 m4ri_mm_free(iszero);
184 }
185