|
|
1
|
+/* Merge HPC prototype run-length-encoded .tix files (NOT part of GHC).
|
|
|
2
|
+ *
|
|
|
3
|
+ * Build: cc -O3 -std=c11 -Wall -Wextra -o tix-rle-merge tix-rle-merge.c
|
|
|
4
|
+ * Usage: ./tix-rle-merge RLE_DIRECTORY OUTPUT.tix
|
|
|
5
|
+ *
|
|
|
6
|
+ * Input and output format (HPCTIX\2):
|
|
|
7
|
+ * 7 bytes "HPCTIX\2", ULEB128 module count;
|
|
|
8
|
+ * for each module:
|
|
|
9
|
+ * ULEB128 name length, name bytes, little-endian uint32 hash,
|
|
|
10
|
+ * ULEB128 box count;
|
|
|
11
|
+ * repeated (ULEB128 zero-run length, ULEB128 nonzero-run length,
|
|
|
12
|
+ * that many positive ULEB128 Word64 counts)
|
|
|
13
|
+ * until exactly 'box count' counters are described.
|
|
|
14
|
+ *
|
|
|
15
|
+ * No terminator follows an RLE module. A trailing zero run is represented
|
|
|
16
|
+ * by (zero-run length, 0). Modules with zero boxes contain no run records.
|
|
|
17
|
+ *
|
|
|
18
|
+ * The accumulator is a dense uint64_t array per distinct module, as in
|
|
|
19
|
+ * tix-sparse-prototype.c. Checks counter overflow and malformed inputs.
|
|
|
20
|
+ */
|
|
|
21
|
+#define _POSIX_C_SOURCE 200809L
|
|
|
22
|
+#include <dirent.h>
|
|
|
23
|
+#include <errno.h>
|
|
|
24
|
+#include <inttypes.h>
|
|
|
25
|
+#include <stdint.h>
|
|
|
26
|
+#include <stdio.h>
|
|
|
27
|
+#include <stdlib.h>
|
|
|
28
|
+#include <string.h>
|
|
|
29
|
+#include <sys/stat.h>
|
|
|
30
|
+
|
|
|
31
|
+#define MAGIC "HPCTIX\0"
|
|
|
32
|
+#define BUCKETS 8192
|
|
|
33
|
+
|
|
|
34
|
+typedef struct { unsigned char *data; size_t len, cap; } Buffer;
|
|
|
35
|
+typedef struct { const unsigned char *p, *end; } Reader;
|
|
|
36
|
+typedef struct Module {
|
|
|
37
|
+ char *name;
|
|
|
38
|
+ uint32_t hash;
|
|
|
39
|
+ size_t n;
|
|
|
40
|
+ uint64_t *ticks;
|
|
|
41
|
+ uint64_t seen_epoch;
|
|
|
42
|
+ struct Module *next;
|
|
|
43
|
+} Module;
|
|
|
44
|
+typedef struct {
|
|
|
45
|
+ Module *buckets[BUCKETS];
|
|
|
46
|
+ Module **mods;
|
|
|
47
|
+ size_t len, cap;
|
|
|
48
|
+ uint64_t epoch, filecount, input_entries;
|
|
|
49
|
+} Acc;
|
|
|
50
|
+
|
|
|
51
|
+static const char *context;
|
|
|
52
|
+static void die(const char *msg) {
|
|
|
53
|
+ fprintf(stderr, "%s: %s\n", context ? context : "tix-rle-merge", msg);
|
|
|
54
|
+ exit(1);
|
|
|
55
|
+}
|
|
|
56
|
+static void *xmalloc(size_t n) {
|
|
|
57
|
+ void *p = malloc(n ? n : 1);
|
|
|
58
|
+ if (!p) die("out of memory");
|
|
|
59
|
+ return p;
|
|
|
60
|
+}
|
|
|
61
|
+static void *xrealloc(void *p, size_t n) {
|
|
|
62
|
+ void *q = realloc(p, n ? n : 1);
|
|
|
63
|
+ if (!q) die("out of memory");
|
|
|
64
|
+ return q;
|
|
|
65
|
+}
|
|
|
66
|
+static void reserve(Buffer *b, size_t add) {
|
|
|
67
|
+ if (add > SIZE_MAX - b->len) die("buffer too large");
|
|
|
68
|
+ size_t need = b->len + add;
|
|
|
69
|
+ if (need <= b->cap) return;
|
|
|
70
|
+ size_t cap = b->cap ? b->cap : 256;
|
|
|
71
|
+ while (cap < need) {
|
|
|
72
|
+ if (cap > SIZE_MAX / 2) { cap = need; break; }
|
|
|
73
|
+ cap *= 2;
|
|
|
74
|
+ }
|
|
|
75
|
+ b->data = xrealloc(b->data, cap);
|
|
|
76
|
+ b->cap = cap;
|
|
|
77
|
+}
|
|
|
78
|
+static void bytes(Buffer *b, const void *src, size_t n) {
|
|
|
79
|
+ reserve(b, n);
|
|
|
80
|
+ memcpy(b->data + b->len, src, n);
|
|
|
81
|
+ b->len += n;
|
|
|
82
|
+}
|
|
|
83
|
+static void byte(Buffer *b, unsigned char c) {
|
|
|
84
|
+ reserve(b, 1);
|
|
|
85
|
+ b->data[b->len++] = c;
|
|
|
86
|
+}
|
|
|
87
|
+static void putvar(Buffer *b, uint64_t x) {
|
|
|
88
|
+ while (x >= 128) {
|
|
|
89
|
+ byte(b, (unsigned char)((x & 127) | 128));
|
|
|
90
|
+ x >>= 7;
|
|
|
91
|
+ }
|
|
|
92
|
+ byte(b, (unsigned char)x);
|
|
|
93
|
+}
|
|
|
94
|
+static void put32(Buffer *b, uint32_t x) {
|
|
|
95
|
+ for (unsigned k = 0; k < 4; k++) byte(b, (unsigned char)(x >> (8*k)));
|
|
|
96
|
+}
|
|
|
97
|
+static uint64_t getvar(Reader *r) {
|
|
|
98
|
+ uint64_t x = 0;
|
|
|
99
|
+ for (unsigned k = 0; k < 10; k++) {
|
|
|
100
|
+ if (r->p == r->end) die("truncated variable-length integer");
|
|
|
101
|
+ unsigned c = *r->p++;
|
|
|
102
|
+ if (k == 9 && (c & 0xfe)) die("variable-length integer overflow");
|
|
|
103
|
+ x |= (uint64_t)(c & 127) << (7*k);
|
|
|
104
|
+ if (!(c & 128)) {
|
|
|
105
|
+ if (k && c == 0) die("noncanonical variable-length integer");
|
|
|
106
|
+ return x;
|
|
|
107
|
+ }
|
|
|
108
|
+ }
|
|
|
109
|
+ die("unterminated variable-length integer");
|
|
|
110
|
+ return 0;
|
|
|
111
|
+}
|
|
|
112
|
+static uint32_t get32(Reader *r) {
|
|
|
113
|
+ if ((size_t)(r->end - r->p) < 4) die("truncated hash");
|
|
|
114
|
+ uint32_t x = 0;
|
|
|
115
|
+ for (unsigned k = 0; k < 4; k++) x |= (uint32_t)(*r->p++) << (8*k);
|
|
|
116
|
+ return x;
|
|
|
117
|
+}
|
|
|
118
|
+static unsigned char *readfile(const char *path, size_t *size) {
|
|
|
119
|
+ FILE *f = fopen(path, "rb");
|
|
|
120
|
+ if (!f) { perror(path); exit(1); }
|
|
|
121
|
+ if (fseek(f, 0, SEEK_END)) die("seek failed");
|
|
|
122
|
+ long n = ftell(f);
|
|
|
123
|
+ if (n < 0 || fseek(f, 0, SEEK_SET)) die("size failed");
|
|
|
124
|
+ if ((uintmax_t)n > SIZE_MAX) die("file too large");
|
|
|
125
|
+ unsigned char *data = xmalloc((size_t)n);
|
|
|
126
|
+ if (fread(data, 1, (size_t)n, f) != (size_t)n) die("read failed");
|
|
|
127
|
+ if (fclose(f)) die("close failed");
|
|
|
128
|
+ *size = (size_t)n;
|
|
|
129
|
+ return data;
|
|
|
130
|
+}
|
|
|
131
|
+static void writefile(const char *path, const void *data, size_t n) {
|
|
|
132
|
+ FILE *f = fopen(path, "wb");
|
|
|
133
|
+ if (!f) { perror(path); exit(1); }
|
|
|
134
|
+ if (fwrite(data, 1, n, f) != n) die("write failed");
|
|
|
135
|
+ if (fclose(f)) die("close failed");
|
|
|
136
|
+}
|
|
|
137
|
+static uint64_t namehash(const char *s) {
|
|
|
138
|
+ uint64_t h = UINT64_C(14695981039346656037);
|
|
|
139
|
+ for (; *s; s++) { h ^= (unsigned char)*s; h *= UINT64_C(1099511628211); }
|
|
|
140
|
+ return h;
|
|
|
141
|
+}
|
|
|
142
|
+static Module *module(Acc *a, const char *name, uint32_t hash, size_t n) {
|
|
|
143
|
+ size_t bucket = namehash(name) % BUCKETS;
|
|
|
144
|
+ for (Module *m = a->buckets[bucket]; m; m = m->next) {
|
|
|
145
|
+ if (strcmp(m->name, name)) continue;
|
|
|
146
|
+ if (m->hash != hash || m->n != n) die("incompatible module hash/number of boxes");
|
|
|
147
|
+ return m;
|
|
|
148
|
+ }
|
|
|
149
|
+ if (n > SIZE_MAX / sizeof(uint64_t)) die("module too large");
|
|
|
150
|
+ Module *m = xmalloc(sizeof(*m));
|
|
|
151
|
+ m->name = strdup(name);
|
|
|
152
|
+ if (!m->name) die("out of memory");
|
|
|
153
|
+ m->hash = hash;
|
|
|
154
|
+ m->n = n;
|
|
|
155
|
+ m->ticks = calloc(n ? n : 1, sizeof(uint64_t));
|
|
|
156
|
+ if (!m->ticks) die("out of memory");
|
|
|
157
|
+ m->seen_epoch = 0;
|
|
|
158
|
+ m->next = a->buckets[bucket];
|
|
|
159
|
+ a->buckets[bucket] = m;
|
|
|
160
|
+ if (a->len == a->cap) {
|
|
|
161
|
+ if (a->cap > SIZE_MAX / (2 * sizeof(*a->mods))) die("too many modules");
|
|
|
162
|
+ a->cap = a->cap ? 2 * a->cap : 256;
|
|
|
163
|
+ a->mods = xrealloc(a->mods, a->cap * sizeof(*a->mods));
|
|
|
164
|
+ }
|
|
|
165
|
+ a->mods[a->len++] = m;
|
|
|
166
|
+ return m;
|
|
|
167
|
+}
|
|
|
168
|
+static void mergeone(Acc *a, const char *path) {
|
|
|
169
|
+ context = path;
|
|
|
170
|
+ size_t size;
|
|
|
171
|
+ unsigned char *data = readfile(path, &size);
|
|
|
172
|
+ Reader r = {data, data + size};
|
|
|
173
|
+ if (size < 7 || memcmp(r.p, MAGIC, 7)) die("wrong magic/version (expected HPCTIX\\2)");
|
|
|
174
|
+ r.p += 7;
|
|
|
175
|
+ uint64_t nmods = getvar(&r);
|
|
|
176
|
+ if (nmods > (uint64_t)(r.end - r.p)) die("invalid module count");
|
|
|
177
|
+ if (++a->epoch == 0) die("epoch overflow");
|
|
|
178
|
+
|
|
|
179
|
+ for (uint64_t j = 0; j < nmods; j++) {
|
|
|
180
|
+ uint64_t name_len = getvar(&r);
|
|
|
181
|
+ if (name_len > SIZE_MAX - 1 || name_len > (uint64_t)(r.end - r.p))
|
|
|
182
|
+ die("invalid name length");
|
|
|
183
|
+ char *name = xmalloc((size_t)name_len + 1);
|
|
|
184
|
+ memcpy(name, r.p, (size_t)name_len);
|
|
|
185
|
+ name[name_len] = 0;
|
|
|
186
|
+ if (memchr(name, 0, (size_t)name_len)) die("embedded NUL in module name");
|
|
|
187
|
+ r.p += (size_t)name_len;
|
|
|
188
|
+ uint32_t hash = get32(&r);
|
|
|
189
|
+ uint64_t boxes = getvar(&r);
|
|
|
190
|
+ if (boxes > SIZE_MAX / sizeof(uint64_t)) die("too many counters");
|
|
|
191
|
+ Module *m = module(a, name, hash, (size_t)boxes);
|
|
|
192
|
+ free(name);
|
|
|
193
|
+ if (m->seen_epoch == a->epoch) die("duplicate module");
|
|
|
194
|
+ m->seen_epoch = a->epoch;
|
|
|
195
|
+
|
|
|
196
|
+ /* RLE records account for exactly 'boxes' positions. */
|
|
|
197
|
+ size_t pos = 0;
|
|
|
198
|
+ while (pos < m->n) {
|
|
|
199
|
+ uint64_t zeros = getvar(&r);
|
|
|
200
|
+ if (zeros > m->n - pos) die("zero run exceeds module box count");
|
|
|
201
|
+ pos += (size_t)zeros;
|
|
|
202
|
+ uint64_t nonzeros = getvar(&r);
|
|
|
203
|
+ if (nonzeros > m->n - pos) die("nonzero run exceeds module box count");
|
|
|
204
|
+ if (!zeros && !nonzeros) die("empty RLE record");
|
|
|
205
|
+
|
|
|
206
|
+ size_t stop = pos + (size_t)nonzeros;
|
|
|
207
|
+ for (; pos < stop; pos++) {
|
|
|
208
|
+ uint64_t value = getvar(&r);
|
|
|
209
|
+ if (!value) die("zero value in nonzero run");
|
|
|
210
|
+ if (UINT64_MAX - m->ticks[pos] < value) die("counter overflow");
|
|
|
211
|
+ m->ticks[pos] += value;
|
|
|
212
|
+ }
|
|
|
213
|
+ if (UINT64_MAX - a->input_entries < nonzeros) die("entry count overflow");
|
|
|
214
|
+ a->input_entries += nonzeros;
|
|
|
215
|
+ }
|
|
|
216
|
+ }
|
|
|
217
|
+ if (r.p != r.end) die("unexpected trailing bytes");
|
|
|
218
|
+ free(data);
|
|
|
219
|
+ a->filecount++;
|
|
|
220
|
+}
|
|
|
221
|
+static int cmpmod(const void *a, const void *b) {
|
|
|
222
|
+ const Module *const *x = a, *const *y = b;
|
|
|
223
|
+ return strcmp((*x)->name, (*y)->name);
|
|
|
224
|
+}
|
|
|
225
|
+static Buffer serialise(const Acc *a) {
|
|
|
226
|
+ Buffer b = {0};
|
|
|
227
|
+ bytes(&b, MAGIC, 7);
|
|
|
228
|
+ putvar(&b, a->len);
|
|
|
229
|
+ for (size_t j = 0; j < a->len; j++) {
|
|
|
230
|
+ Module *m = a->mods[j];
|
|
|
231
|
+ size_t name_len = strlen(m->name);
|
|
|
232
|
+ putvar(&b, name_len);
|
|
|
233
|
+ bytes(&b, m->name, name_len);
|
|
|
234
|
+ put32(&b, m->hash);
|
|
|
235
|
+ putvar(&b, m->n);
|
|
|
236
|
+
|
|
|
237
|
+ size_t i = 0;
|
|
|
238
|
+ while (i < m->n) {
|
|
|
239
|
+ size_t start = i;
|
|
|
240
|
+ while (i < m->n && m->ticks[i] == 0) i++;
|
|
|
241
|
+ putvar(&b, i - start);
|
|
|
242
|
+ start = i;
|
|
|
243
|
+ while (i < m->n && m->ticks[i] != 0) i++;
|
|
|
244
|
+ putvar(&b, i - start);
|
|
|
245
|
+ for (size_t k = start; k < i; k++) putvar(&b, m->ticks[k]);
|
|
|
246
|
+ }
|
|
|
247
|
+ }
|
|
|
248
|
+ return b;
|
|
|
249
|
+}
|
|
|
250
|
+static int is_tix(const char *s) {
|
|
|
251
|
+ size_t n = strlen(s);
|
|
|
252
|
+ return n >= 4 && strcmp(s + n - 4, ".tix") == 0;
|
|
|
253
|
+}
|
|
|
254
|
+static int cmpstr(const void *a, const void *b) {
|
|
|
255
|
+ return strcmp(*(char *const *)a, *(char *const *)b);
|
|
|
256
|
+}
|
|
|
257
|
+static void merge_dir(const char *dir, const char *output) {
|
|
|
258
|
+ DIR *d = opendir(dir);
|
|
|
259
|
+ if (!d) { perror(dir); exit(1); }
|
|
|
260
|
+ char **paths = NULL;
|
|
|
261
|
+ size_t n = 0, cap = 0;
|
|
|
262
|
+ struct dirent *e;
|
|
|
263
|
+ struct stat outstat;
|
|
|
264
|
+ int output_exists = stat(output, &outstat) == 0;
|
|
|
265
|
+ while ((e = readdir(d))) {
|
|
|
266
|
+ if (!is_tix(e->d_name)) continue;
|
|
|
267
|
+ size_t dlen = strlen(dir), flen = strlen(e->d_name);
|
|
|
268
|
+ if (dlen > SIZE_MAX - flen - 2) die("path too long");
|
|
|
269
|
+ char *path = xmalloc(dlen + flen + 2);
|
|
|
270
|
+ snprintf(path, dlen + flen + 2, "%s/%s", dir, e->d_name);
|
|
|
271
|
+ struct stat st;
|
|
|
272
|
+ if (stat(path, &st) || !S_ISREG(st.st_mode)) { free(path); continue; }
|
|
|
273
|
+ if (!strcmp(path, output) ||
|
|
|
274
|
+ (output_exists && st.st_dev == outstat.st_dev && st.st_ino == outstat.st_ino))
|
|
|
275
|
+ die("output file is among input files");
|
|
|
276
|
+ if (n == cap) {
|
|
|
277
|
+ if (cap > SIZE_MAX / (2 * sizeof(*paths))) die("too many input files");
|
|
|
278
|
+ cap = cap ? 2 * cap : 256;
|
|
|
279
|
+ paths = xrealloc(paths, cap * sizeof(*paths));
|
|
|
280
|
+ }
|
|
|
281
|
+ paths[n++] = path;
|
|
|
282
|
+ }
|
|
|
283
|
+ closedir(d);
|
|
|
284
|
+ if (!n) die("no input .tix files");
|
|
|
285
|
+ qsort(paths, n, sizeof(*paths), cmpstr);
|
|
|
286
|
+ Acc a = {0};
|
|
|
287
|
+ for (size_t i = 0; i < n; i++) {
|
|
|
288
|
+ mergeone(&a, paths[i]);
|
|
|
289
|
+ free(paths[i]);
|
|
|
290
|
+ if (a.filecount % 1000 == 0)
|
|
|
291
|
+ fprintf(stderr, "Merged %" PRIu64 " files\n", a.filecount);
|
|
|
292
|
+ }
|
|
|
293
|
+ free(paths);
|
|
|
294
|
+ qsort(a.mods, a.len, sizeof(*a.mods), cmpmod);
|
|
|
295
|
+ Buffer out = serialise(&a);
|
|
|
296
|
+ context = output;
|
|
|
297
|
+ writefile(output, out.data, out.len);
|
|
|
298
|
+ fprintf(stderr, "Merged %" PRIu64 " files, %zu modules, %" PRIu64
|
|
|
299
|
+ " nonzero input counters; result %zu bytes\n",
|
|
|
300
|
+ a.filecount, a.len, a.input_entries, out.len);
|
|
|
301
|
+ free(out.data);
|
|
|
302
|
+ for (size_t i = 0; i < a.len; i++) {
|
|
|
303
|
+ free(a.mods[i]->ticks);
|
|
|
304
|
+ free(a.mods[i]->name);
|
|
|
305
|
+ free(a.mods[i]);
|
|
|
306
|
+ }
|
|
|
307
|
+ free(a.mods);
|
|
|
308
|
+}
|
|
|
309
|
+int main(int argc, char **argv) {
|
|
|
310
|
+ if (argc != 3) {
|
|
|
311
|
+ fprintf(stderr, "Usage: %s RLE_DIRECTORY OUTPUT.tix\n", argv[0]);
|
|
|
312
|
+ return 2;
|
|
|
313
|
+ }
|
|
|
314
|
+ merge_dir(argv[1], argv[2]);
|
|
|
315
|
+ return 0;
|
|
|
316
|
+} |