8 #include "shrinkstar.h"
16 void printLinkedList(struct Node *node);
17 void append(struct Node** head_ref, int new_data);
18 void freeList(struct Node** head_ref);
20 /****************************************************************************
21 * Attempts to shrinks the dimension of the affine space by one dimension.
22 * The affine space is specified by
23 * the first 'k' columns of the 'n'x'n' matrix 'G', translated by 'h',
24 * that have an inner product with 'xi' of 'alpha'. 'GBar' is 'G^(-1)^T',
25 * and ('Q', 'D', 'J') specify the quadratic form on this affine space.
27 * If result is an EMPTY affine space then return value is 'E'.
28 * If result is the SAME affine space then return value is 'A'.
29 * If result is a SUCCESSfully shrunk affine space then return value is 'U'.
31 * Note that D, and J are assumed to be nx1 and nxn even though they are
32 * actually kx1 and kxk (extra elements are ignored).
33 ****************************************************************************/
35 char shrinkstar(int n, int *k, int *h, int **G, int **GBar, int *xi, int alpha) {
36 // Note that D and J must be dynamically allocated arrays as they can change size in this function. This is also the reason that we need their base pointer and are greater in pointer depth by one.
41 struct Node* setS = NULL;
42 struct Node* setWalker = NULL;
45 if(dotProductMod(xi, G[a], n, 2) == 1)
49 beta = (alpha + dotProductMod(xi, h, n, 2))%2;
62 // we define tmpVec, tmpMatrix, R and RT now for later use since we are sure that *k!=0 (since otherwise setS==NULL) and so they will be finite-sized
63 int* tmpVec; // temporary vector used in swapping G and GBar rows and in Eq. 49 for updating D
64 /*int** tmpMatrix; // temporary matrix used to store intermediate value of J = R times J times R^T
65 tmpMatrix = calloc(*k, sizeof(int*));
67 tmpMatrix[a] = calloc(*k, sizeof(int));*/
69 int** R; // basis change matrix R and R^T
71 R = calloc(*k, sizeof(int*));
72 RT = calloc(*k, sizeof(int*));
73 // initially set it to the k-dimensional identity matrix
75 R[a] = calloc(*k, sizeof(int));
77 RT[a] = calloc(*k, sizeof(int));
81 int i = setS->data; // pick first element in setS to be added to the new space's shift vector
83 if(setS->next != NULL) {
84 setWalker = setS->next;
85 setS->data = setS->next->data;
86 setS->next = setS->next->next;
93 while(setWalker != NULL) {
96 G[setWalker->data][a] = (G[setWalker->data][a] + G[i][a])%2;
99 /*R[setWalker->data][i] = 1;
100 RT[i][setWalker->data] = 1;
102 tmpVec = calloc(*k, sizeof(int));
106 /* for(a=0;a<*k;a++) */
107 /* tmpVec[c] = tmpVec[c] + R[c][a]*((*D)[a]); */
108 /* for(a=0;a<*k;a++) */
109 /* for(b=a+1;b<*k;b++) */
110 /* tmpVec[c] = tmpVec[c] + (*J)[a][b]*R[c][a]*R[c][b]; */
111 /* tmpVec[c] = tmpVec[c]%8; */
113 tmp += R[c][c]*((*D)[c]);
114 tmp += R[c][i]*((*D)[i]);
116 tmp += ((*J)[c][i])*R[c][c]*R[c][i];
118 tmp += ((*J)[i][c])*R[c][i]*R[c][c];
121 memcpy(*D, tmpVec, sizeof(int)*(*k));
124 // Eq. 50 update of J
130 tmp += R[c][c]*((*J)[c][d])*R[d][d];
131 tmp += R[c][c]*((*J)[c][i])*R[d][i];
132 tmp += R[c][i]*((*J)[i][d])*R[d][d];
134 tmp += R[c][c]*((*J)[c][i])*R[d][i];
138 tmp += R[c][i]*((*J)[i][d])*R[d][d];
141 tmp += R[c][i]*((*J)[i][i])*R[d][i];
143 tmpMatrix[c][d] = tmp;
147 memcpy(((*J)[c]), tmpMatrix[c], sizeof(int)*(*k));*/
148 /* multMatrixMod(*J,RT,tmpMatrix,*k,*k,*k,*k,8); */
149 /* multMatrixMod(R,tmpMatrix,*J,*k,*k,*k,*k,8); */
151 if(setWalker->data != i) {
152 R[setWalker->data][i] = 0; // reset R
153 RT[i][setWalker->data] = 0;
156 // update GBar rows, gbar
158 GBar[i][a] = (GBar[i][a] + GBar[setWalker->data][a])%2;
160 setWalker = setWalker->next;
164 R[*k-1][*k-1] = 0; R[i][i] = 0;
165 R[i][*k-1] = 1; R[*k-1][i] = 1;
166 RT[*k-1][*k-1] = 0; RT[i][i] = 0;
167 RT[i][*k-1] = 1; RT[*k-1][i] = 1;
173 GBar[i] = GBar[*k-1];
177 //(Note: can't quite directly use previous faster algorithm since R[c][c]!=1 forall c. However, this can still be brought down by a factor of N by the same algorithm appropriately tweaked.)
179 tmpVec = calloc(*k, sizeof(int));
183 /* for(a=0;a<*k;a++) */
184 /* tmpVec[c] = tmpVec[c] + R[c][a]*((*D)[a]); */
185 /* for(a=0;a<*k;a++) { */
186 /* for(b=a+1;b<*k;b++) */
187 /* tmpVec[c] = tmpVec[c] + (*J)[a][b]*R[c][a]*R[c][b]; */
189 /* tmpVec[c] = tmpVec[c]%8; */
190 /* tmp += R[c][c]*((*D)[c]); // iff c!=i and c!=(*k-1) this can be non-zero
191 tmp += R[c][*k-1]*((*D)[*k-1]); // iff c=i this can be non-zero
192 tmp += R[c][i]*((*D)[i]); // iff c=*k-1 this can be non-zero
195 /* tmp += ((*J)[c][i])*R[c][c]*R[c][i]; */
197 /* tmp += ((*J)[i][c])*R[c][i]*R[c][c]; */
199 /* tmp += ((*J)[c][*k-1])*R[c][c]*R[c][*k-1]; */
200 /* else if((*k-1)<c) // pretty sure this can't happen */
201 /* tmp += ((*J)[*k-1][c])*R[c][*k-1]*R[c][c]; */
203 /* tmp += ((*J)[i][*k-1])*R[c][i]*R[c][*k-1]; */
204 /* else if((*k-1)<i) */
205 /* tmp += ((*J)[*k-1][i])*R[c][*k-1]*R[c][i]; */
206 /* tmpVec[c] = tmp%8;
208 memcpy(*D, tmpVec, sizeof(int)*(*k));
211 // Eq. 50 update of J
215 if(c!=(*k-1) && c!=i) {
216 if(d!=(*k-1) && d!=i) {
217 tmp += R[c][c]*((*J)[c][d])*R[d][d];
219 tmp += R[c][c]*((*J)[c][i])*R[d][i];
220 tmp += R[c][c]*((*J)[c][*k-1])*R[d][*k-1];
223 if(d!=(*k-1) && d !=i) {
224 tmp += R[c][i]*((*J)[i][d])*R[d][d];
225 tmp += R[c][*k-1]*((*J)[*k-1][d])*R[d][d];
227 tmp += R[c][i]*((*J)[i][*k-1])*R[d][*k-1];
228 tmp += R[c][*k-1]*((*J)[*k-1][i])*R[d][i];
229 tmp += R[c][i]*((*J)[i][i])*R[d][i];
230 tmp += R[c][*k-1]*((*J)[*k-1][*k-1])*R[d][*k-1];
233 tmpMatrix[c][d] = tmp%8;
237 memcpy(((*J)[c]), tmpMatrix[c], sizeof(int)*(*k));*/
238 /* multMatrixMod(*J,RT,tmpMatrix,*k,*k,*k,*k,8); */
239 /* multMatrixMod(R,tmpMatrix,*J,*k,*k,*k,*k,8); */
242 R[*k-1][*k-1] = 1; R[i][i] = 1;
243 R[i][*k-1] = 0; R[*k-1][i] = 0;
244 RT[*k-1][*k-1] = 1; RT[i][i] = 1;
245 RT[i][*k-1] = 0; RT[*k-1][i] = 0;
248 h[a] = (h[a] + beta*G[*k-1][a])%2;
250 // update Q & D using Eqs. 52 & 53 with y = beta*G[*k-1][:]
251 // since h is expressed in F_2^n, in F_2^n, y_i = beta*delta_{i,*k-1}
252 // (and so the second sum of Eq. 52 is always over zero terms)
253 /**Q = (*Q + ((*D)[*k-1])*beta)%8;
255 for(a=0; a<*k; a++) {
256 (*D)[a] = ((*D)[a] + (*J)[a][*k-1]*beta)%8;
259 // remove the kth row & column from J
260 // remove the ith element from D
262 // we only need tmpMatrix to be (k-1)x(k-1) and it is kxk
263 /*for(a=0; a<(*k-1); a++) {
264 //tmpMatrix[a] = calloc(*k-1, sizeof(int)); // no need!
265 for(b=0; b<(*k-1); b++)
266 tmpMatrix[a][b] = (*J)[a][b];
268 deallocate_mem(J, *k);
269 *J = calloc(*k-1, sizeof(int*));
270 for(a=0; a<(*k-1); a++) {
271 (*J)[a] = calloc(*k-1, sizeof(int));
272 for(b=0; b<(*k-1); b++)
273 (*J)[a][b] = tmpMatrix[a][b];
275 deallocate_mem(&tmpMatrix, *k);*/
277 /*tmpVec = calloc(*k-1, sizeof(int));
278 for(a=0; a<(*k-1); a++)
281 *D = calloc(*k-1, sizeof(int));
282 memcpy(*D, tmpVec, sizeof(int)*(*k-1));
285 deallocate_mem(&R, *k);
286 deallocate_mem(&RT, *k);
293 return 'U'; // SUCCESS
298 void append(struct Node** head_ref, int new_data)
300 struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
301 struct Node *last = *head_ref;
303 new_node->data = new_data;
304 new_node->next = NULL;
306 // if the linked list is empty, then make the new node as head
307 if (*head_ref == NULL) {
308 *head_ref = new_node;
312 // else traverse till the last node
313 while (last->next != NULL) {
316 last->next = new_node;
321 /*void freeList(struct Node** head_ref)
324 struct Node *second_last_walker = *head_ref;
325 struct Node *walker = *head_ref;
327 // else traverse till the last node
329 while(walker->next != NULL) {
330 while(walker->next != NULL) {
331 //printf("!%d\n", walker->data);
332 second_last_walker = walker;
333 walker = walker->next;
334 //printf("%d\n", walker->data);
335 //printf("!%d\n", second_last_walker->data);
338 second_last_walker->next = NULL;
340 //printf("!!%d\n", second_last_walker->data);
348 void freeList(struct Node** head_ref)
351 struct Node *walker = *head_ref;
352 struct Node *walker2;
354 // else traverse till the last node
356 walker2 = walker->next;
357 while(walker2 != NULL) {
360 walker2 = walker->next;
368 void printLinkedList(struct Node *node)
375 printf(" %d ", node->data);