File: djb.h

package info (click to toggle)
libm4ri 20200125-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 2,560 kB
  • sloc: ansic: 12,633; sh: 4,304; makefile: 137
file content (146 lines) | stat: -rw-r--r-- 3,660 bytes parent folder | download
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/**
 * \file djb.h
 *
 * \brief Dan Bernstein's "Optimizing linear maps mod 2"
 *
 * This code is a port of sort1.cpp available at http://binary.cr.yp.to/linearmod2.html
 *
 * Given a matrix A djb_compile(A) will compute a djb_t data structure which realises A with
 * (heuristically) (m * n)/(log m - loglog m) XORs.
 * 
 * It makes use of a binary heap written by Martin Kunev which is available at
 * https://gist.github.com/martinkunev/1365481
 *
 * \author Martin Albrecht <martinralbrecht@googlemail.com>
 */

#ifndef M4RI_DJB_H
#define M4RI_DJB_H

#include <m4ri/mzd.h>

/**
 * \brief Specify source type of addition
 */

typedef enum {
  source_target, //< add from target matrix
  source_source //< add from source matrix
} srctyp_t;

/**
 * \brief DJB's optimized linear maps mod 2
 */
 
typedef struct {
  rci_t nrows; /*!< Number of rows of map */
  rci_t ncols; /*!< Number of columns of map */
  rci_t *target; /*!< target row at index i */
  rci_t *source; /*!< source row at index i */
  srctyp_t *srctyp; /*!< source type at index i */
  rci_t length; /*!< length of target, source and srctype */
  wi_t allocated; /*!< how much did we allocate already */
} djb_t;

/**
 * Standard allocation chunk
 */

#define M4RI_DJB_BASE_SIZE 64

/**
 * Allocate a new DJB linear map
 *
 * \param nrows Number of rows
 * \param ncols Number of columns 
 */

static inline djb_t *djb_init(rci_t nrows, rci_t ncols) {
  /* we want to use realloc, so we call unaligned malloc */
  djb_t *m = (djb_t*)malloc(sizeof(djb_t));
  if (m == NULL)
    m4ri_die("malloc failed.\n");

  m->nrows = nrows;
  m->ncols = ncols;
  m->target = (rci_t*)malloc(sizeof(rci_t)    * M4RI_DJB_BASE_SIZE);
  m->source = (rci_t*)malloc(sizeof(rci_t)    * M4RI_DJB_BASE_SIZE);
  m->srctyp = (srctyp_t*)malloc(sizeof(srctyp_t) * M4RI_DJB_BASE_SIZE);
  m->length = 0;
  m->allocated = M4RI_DJB_BASE_SIZE;

  if (m->target == NULL || m->source == NULL || m->srctyp == NULL)
    m4ri_die("malloc failed.\n");
  return m;
}

/**
 * Free a DJB linear maps
 *
 * \param m Map
 */

static inline void djb_free(djb_t *m) {
  free(m->target);
  free(m->source);
  free(m->srctyp);
  free(m);
}

/**
 * Add a new operation out[target] ^= srctype[source] to queue.
 *
 * \param z DJB linear map.
 * \param target Output index
 * \param source Input index
 * \param srctyp Type of input (source_source or source_target)
 */

static inline void djb_push_back(djb_t *z, rci_t target, rci_t source, srctyp_t srctyp) {
  assert((target < z->nrows) && 
         ((source < z->ncols) | (srctyp != source_source)) &&
         ((source < z->nrows) | (srctyp != source_target)));
  if (z->length >= z->allocated) {
    z->allocated += M4RI_DJB_BASE_SIZE;
    z->target = (rci_t*)realloc(z->target, z->allocated*sizeof(rci_t));
    z->source = (rci_t*)realloc(z->source, z->allocated*sizeof(rci_t));
    z->srctyp = (srctyp_t*)realloc(z->srctyp, z->allocated*sizeof(srctyp_t));
  }
  z->target[z->length] = target;
  z->source[z->length] = source;
  z->srctyp[z->length] = srctyp;
  z->length++;
}

/**
 * Compile a new DJB linear map from A.
 *
 * \param A
 */

djb_t *djb_compile(mzd_t *A);

/**
 * \brief W = m*V
 *
 * Apply the linear map m to V and write the result in W.
 *
 * \param z  DJB linear map.
 * \param W  Output matrix
 * \param V  Input matrix
 */

void djb_apply_mzd(djb_t *z, mzd_t *W, const mzd_t *V);


/**
 * Print infomrmation on linear map mA
 */

static inline void djb_info(const djb_t *z) {
  double save = (double)z->length / (double)(z->nrows * z->ncols);
  printf("%d x %d linear map in %d xors (cost: %.5f)\n", z->nrows, z->ncols, z->length, save);
}


#endif //M4RI_DJB_H