Line data Source code
1 : /* Copyright 2017 noseglasses <shinynoseglasses@gmail.com>
2 : *
3 : * This program is free software: you can redistribute it and/or modify
4 : * it under the terms of the GNU Lesser General Public License as published by
5 : * the Free Software Foundation, either version 3 of the License, or
6 : * (at your option) any later version.
7 : *
8 : * This program is distributed in the hope that it will be useful,
9 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 : * GNU Lesser General Public License for more details.
12 : *
13 : * You should have received a copy of the GNU Lesser General Public License
14 : * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 : */
16 :
17 : #include "detail/ppg_compression_detail.h"
18 : #include "detail/ppg_context_detail.h"
19 : #include "detail/ppg_token_vtable_detail.h"
20 : #include "detail/ppg_malloc_detail.h"
21 : #include "ppg_debug.h"
22 :
23 : #include <stdio.h>
24 : #include "assert.h"
25 :
26 66 : static void ppg_compression_context_symbol_buffer_resize(
27 : PPG_Compression_Symbol_Buffer *symbols,
28 : PPG_Count new_size)
29 : {
30 66 : if(new_size == 0) {
31 18 : new_size = 4;
32 : }
33 :
34 66 : PPG_Compression_Symbol *new_buffer
35 66 : = (PPG_Compression_Symbol *)PPG_MALLOC(
36 : new_size*sizeof(PPG_Compression_Symbol));
37 :
38 66 : if(!symbols->buffer) {
39 18 : symbols->buffer = new_buffer;
40 18 : return;
41 : }
42 :
43 48 : PPG_ASSERT(new_size > symbols->n_allocated);
44 :
45 216 : for(PPG_Count i = 0; i < symbols->n_stored; ++i) {
46 :
47 168 : new_buffer[i] = symbols->buffer[i];
48 : }
49 :
50 48 : free(symbols->buffer);
51 :
52 48 : symbols->buffer = new_buffer;
53 :
54 48 : symbols->n_allocated = new_size;
55 : }
56 :
57 18 : PPG_Compression_Context ppg_compression_init(void)
58 : {
59 18 : PPG_Compression_Context__ *ccontext
60 : = (PPG_Compression_Context__ *)PPG_MALLOC(sizeof(PPG_Compression_Context__));
61 :
62 18 : ccontext->symbols_lookup.buffer = NULL;
63 18 : ccontext->symbols_lookup.n_allocated = 0;
64 18 : ccontext->symbols_lookup.n_stored = 0;
65 :
66 18 : ppg_compression_context_symbol_buffer_resize(&ccontext->symbols_lookup, 4);
67 :
68 18 : ccontext->target_storage = NULL;
69 18 : ccontext->symbols = NULL;
70 : // ccontext->vptrs = NULL;
71 18 : ccontext->storage_size = 0;
72 :
73 18 : return (PPG_Compression_Context)ccontext;
74 : }
75 :
76 18 : void ppg_compression_finalize(PPG_Compression_Context ccontext)
77 : {
78 18 : if(!ccontext) { return; }
79 :
80 18 : PPG_Compression_Context__ *ccontext__
81 : = (PPG_Compression_Context__ *)ccontext;
82 :
83 18 : if(ccontext__->symbols_lookup.buffer) {
84 18 : free(ccontext__->symbols_lookup.buffer);
85 18 : ccontext__->symbols_lookup.buffer = NULL;
86 : }
87 :
88 18 : if(ccontext__->target_storage) {
89 18 : free(ccontext__->target_storage);
90 : }
91 :
92 18 : free(ccontext__);
93 : }
94 :
95 184 : void ppg_compression_register_symbol(
96 : PPG_Compression_Context ccontext,
97 : void *symbol,
98 : char *symbol_name)
99 : {
100 184 : if(!symbol) { return; }
101 :
102 184 : if(!symbol_name) {
103 0 : PPG_ERROR("Trying to register a symbol with NULL symbol name\n");
104 : }
105 :
106 : // printf("Registering symbol %s = %p\n", symbol_name, symbol);
107 :
108 184 : PPG_Compression_Context__ *ccontext__
109 : = (PPG_Compression_Context__ *)ccontext;
110 :
111 184 : PPG_ASSERT(ccontext__);
112 184 : PPG_ASSERT(ccontext__->symbols_lookup.buffer);
113 :
114 184 : if(ccontext__->symbols_lookup.n_stored == ccontext__->symbols_lookup.n_allocated) {
115 :
116 : // Double the size with each allocation
117 : //
118 48 : ppg_compression_context_symbol_buffer_resize(
119 : &ccontext__->symbols_lookup,
120 48 : 2*ccontext__->symbols_lookup.n_allocated);
121 : }
122 :
123 184 : ccontext__->symbols_lookup.buffer[ccontext__->symbols_lookup.n_stored] =
124 : (PPG_Compression_Symbol) {
125 : .address = symbol,
126 : .name = symbol_name
127 : };
128 :
129 184 : ++ccontext__->symbols_lookup.n_stored;
130 : }
131 :
132 : typedef struct {
133 : size_t memory;
134 : size_t n_tokens;
135 : } PPG_Compression_Size_Data;
136 :
137 868 : static void ppg_compression_collect_token_size_requirement(
138 : PPG_Token__ *token, void *user_data)
139 : {
140 868 : PPG_Compression_Size_Data *size_data = (PPG_Compression_Size_Data *)user_data;
141 :
142 868 : size_data->memory += PPG_CALL_VIRT_METHOD(token, dynamic_size);
143 :
144 868 : ++size_data->n_tokens;
145 868 : }
146 :
147 18 : static size_t ppg_compression_allocate_target_buffer(PPG_Compression_Context__ *ccontext)
148 : {
149 18 : PPG_Compression_Size_Data size_data =
150 : (PPG_Compression_Size_Data){
151 : .memory = 0,
152 : .n_tokens = 0
153 : };
154 :
155 18 : size_data.memory += ppg_context_get_size_requirements (ppg_context);
156 :
157 : // Collect the size requirements of all tokens in the tree
158 : //
159 18 : ppg_token_traverse_tree(ppg_context->pattern_root,
160 : (PPG_Token_Tree_Visitor)ppg_compression_collect_token_size_requirement,
161 : NULL,
162 : (void *)&size_data);
163 :
164 18 : PPG_ASSERT(!ccontext->target_storage);
165 :
166 : // printf("Allocating target_storage size %lu\n", size_data.memory);
167 :
168 18 : ccontext->target_storage = (char*)PPG_MALLOC(size_data.memory);
169 :
170 : // printf("Allocating target_storage %p\n", ccontext->target_storage);
171 :
172 18 : ccontext->storage_size = size_data.memory;
173 :
174 18 : return size_data.n_tokens;
175 : }
176 :
177 868 : static void ppg_compression_copy_token(
178 : PPG_Token__ *token, void *user_data)
179 : {
180 : // printf("Original:\n");
181 : // PPG_CALL_VIRT_METHOD(token, print_self, 0, false);
182 :
183 868 : char **target = (char **)user_data;
184 :
185 868 : PPG_Token__ *new_token = (PPG_Token__ *)*target;
186 :
187 868 : *target = PPG_CALL_VIRT_METHOD(token, placement_clone, *target);
188 :
189 : // printf("Clone raw:\n");
190 : // PPG_CALL_VIRT_METHOD(new_token, print_self, 0, false);
191 :
192 : // Abuse the old tree's temporarily to
193 : // store child ptr. Node parent pointers are thereby
194 : // used to store node copies.
195 : // This assumes that the
196 : // parent ptrs are restored afterwards through
197 : // a tree traversal.
198 : //
199 868 : if(token->parent) {
200 :
201 850 : if(token->parent->parent) {
202 :
203 : // Note: Here token->parent->parent is actually the clone of token->parent
204 : //
205 850 : new_token->parent = token->parent->parent;
206 : }
207 :
208 : // Get the storage index of the current node
209 : //
210 850 : PPG_Count child_id = 0;
211 1986 : for(; child_id < token->parent->n_children; ++child_id) {
212 :
213 1986 : if(token->parent->children[child_id] == token) {
214 850 : break;
215 : }
216 : }
217 :
218 : // printf("Resetting child %d\n", child_id);
219 850 : new_token->parent->children[child_id] = new_token;
220 : }
221 :
222 868 : token->parent = new_token;
223 :
224 : // printf("Original after:\n");
225 : // PPG_CALL_VIRT_METHOD(token, print_self, 0, false);
226 : //
227 : // printf("\nClone:\n");
228 : // PPG_CALL_VIRT_METHOD(new_token, print_self, 0, false);
229 868 : }
230 :
231 868 : static void ppg_compression_generate_relative_addresses(
232 : PPG_Token__ *token, void *begin_of_buffer)
233 : {
234 868 : PPG_CALL_VIRT_METHOD(token, addresses_to_relative, begin_of_buffer);
235 :
236 868 : token->vtable = (PPG_Token_Vtable*)ppg_token_vtable_id_from_ptr(token->vtable);
237 868 : }
238 :
239 434 : static void ppg_compression_generate_absolute_addresses(
240 : PPG_Token__ *token, void *begin_of_buffer)
241 : {
242 :
243 434 : token->vtable = (PPG_Token_Vtable*)ppg_token_vtable_ptr_from_id((uintptr_t)token->vtable);
244 434 : PPG_CALL_VIRT_METHOD(token, addresses_to_absolute, begin_of_buffer);
245 434 : }
246 :
247 2882 : static void ppg_compression_restore_tree_relations(PPG_Token__ *token)
248 : {
249 5312 : for(PPG_Count i = 0; i < token->n_children; ++i) {
250 2430 : token->children[i]->parent = token;
251 :
252 2430 : ppg_compression_restore_tree_relations(token->children[i]);
253 : }
254 2882 : }
255 :
256 18 : static void ppg_compression_copy_context(PPG_Compression_Context__ *ccontext)
257 : {
258 18 : void *target = ppg_context_copy(ppg_context,
259 18 : ccontext->target_storage);
260 :
261 18 : PPG_Context *target_context = (PPG_Context*)ccontext->target_storage;
262 :
263 18 : target_context->pattern_root = (PPG_Token__ *)target;
264 :
265 18 : ppg_token_traverse_tree(ppg_context->pattern_root,
266 : (PPG_Token_Tree_Visitor)ppg_compression_copy_token,
267 : NULL,
268 : (void *)&target);
269 :
270 : // We destroyed parent-child relation during the previous tree traverse.
271 : // Now we restore it.
272 : //
273 18 : ppg_context->pattern_root->parent = NULL;
274 18 : ppg_compression_restore_tree_relations(ppg_context->pattern_root);
275 :
276 : // printf("properties: %d\n", *((int*)&target_context->properties));
277 :
278 : // As this is not a dynamically allocated context, we
279 : // have to prevent auto destruction
280 : //
281 18 : target_context->properties.destruction_enabled = false;
282 18 : }
283 :
284 18 : static void ppg_compression_convert_all_addresses_to_relative(PPG_Compression_Context__ *ccontext)
285 : {
286 18 : char *target = ccontext->target_storage;
287 :
288 18 : PPG_Context *target_context = (PPG_Context*)target;
289 :
290 : // Convert pointers to relative addresses
291 : //
292 18 : ppg_token_traverse_tree(target_context->pattern_root,
293 : NULL,
294 : (PPG_Token_Tree_Visitor)ppg_compression_generate_relative_addresses,
295 : (void *)target);
296 :
297 36 : target_context->pattern_root = (PPG_Token__ *)((char*)target_context->pattern_root
298 18 : - target);
299 18 : }
300 :
301 868 : static void ppg_compression_register_pointers(
302 : PPG_Token__ *token, void *user_data)
303 : {
304 868 : PPG_Compression_Context__ *ccontext
305 : = (PPG_Compression_Context__ *)user_data;
306 :
307 868 : PPG_CALL_VIRT_METHOD(token, register_ptrs_for_compression, ccontext);
308 868 : }
309 :
310 18 : void ppg_compression_generate_dynamic_assignment_information(
311 : PPG_Compression_Context__ *ccontext)
312 : {
313 : // The context resides at the front of the target storage
314 : //
315 18 : PPG_Context *context = (PPG_Context *)ccontext->target_storage;
316 :
317 : // Register dynamic symbols of the context
318 :
319 18 : if(context->event_processor) {
320 18 : ppg_compression_context_register_symbol((void**)&context->event_processor, ccontext);
321 : }
322 :
323 18 : if(context->signal_callback.func) {
324 18 : ppg_compression_context_register_symbol((void**)&context->signal_callback.func, ccontext);
325 : }
326 :
327 18 : if(context->signal_callback.user_data) {
328 0 : ppg_compression_context_register_symbol((void**)&context->signal_callback.user_data, ccontext);
329 : }
330 :
331 18 : if(context->time_manager.time) {
332 18 : ppg_compression_context_register_symbol((void**)&context->time_manager.time, ccontext);
333 : }
334 :
335 18 : if(context->time_manager.time_difference) {
336 18 : ppg_compression_context_register_symbol((void**)&context->time_manager.time_difference, ccontext);
337 : }
338 :
339 18 : if(context->time_manager.compare_times) {
340 18 : ppg_compression_context_register_symbol((void**)&context->time_manager.compare_times, ccontext);
341 : }
342 :
343 : // Traverse the search tree and collect any dynamic symbols of tokens
344 : //
345 18 : ppg_token_traverse_tree(context->pattern_root,
346 : (PPG_Token_Tree_Visitor)ppg_compression_register_pointers,
347 : NULL,
348 : (void *)ccontext);
349 18 : }
350 :
351 18 : void ppg_compression_write_c_char_array(char *array_name,
352 : char *array,
353 : size_t size)
354 : {
355 :
356 : // printf("array size: %lu\n", size);
357 : // printf("array: %p\n", array);
358 :
359 : #define ROW_LENGTH 16
360 :
361 18 : size_t n_rows = size / ROW_LENGTH;
362 18 : size_t n_remaining = size % ROW_LENGTH;
363 :
364 : // printf("/*\n");
365 : //
366 : // for(size_t row = 0; row < n_rows; ++row) {
367 : //
368 : // for(size_t col = 0; col < ROW_LENGTH; ++col) {
369 : // printf("%lu: 0x%02x\n", row*ROW_LENGTH + col, (int)(array[row*ROW_LENGTH + col] & 0xff));
370 : // }
371 : // }
372 : //
373 : // if(n_remaining) {
374 : // for(size_t col = 0; col < ROW_LENGTH; ++col) {
375 : // printf("%lu: 0x%02x\n", n_rows*ROW_LENGTH + col, (int)(array[n_rows*ROW_LENGTH + col] & 0xff));
376 : // }
377 : // }
378 : // printf("*/\n\n");
379 :
380 18 : printf("char %s[] = {\n", array_name);
381 :
382 : // printf("n_rows: %lu\n", n_rows);
383 : // printf("n_remaining: %lu\n", n_remaining);
384 :
385 4126 : for(size_t row = 0; row < n_rows; ++row) {
386 :
387 4108 : printf(" ");
388 :
389 69836 : for(size_t col = 0; col < ROW_LENGTH; ++col) {
390 65728 : printf("0x%02x, ", (int)(array[row*ROW_LENGTH + col] & 0xff));
391 : }
392 :
393 4108 : printf("\n");
394 : }
395 :
396 18 : if(n_remaining) {
397 :
398 102 : for(size_t col = 0; col < n_remaining; ++col) {
399 92 : printf("0x%02x, ", (int)(array[n_rows*ROW_LENGTH + col] & 0xff));
400 : }
401 :
402 10 : printf("\n");
403 : }
404 :
405 18 : printf("};\n\n");
406 18 : }
407 :
408 9 : void ppg_compression_setup_context(void *context)
409 : {
410 : // uprintf("c setup ctxt\n");
411 9 : char *context_c = (char*)context;
412 :
413 9 : PPG_Context *the_context = (PPG_Context *)context;
414 :
415 9 : PPG_ASSERT(the_context->properties.papageno_enabled);
416 :
417 9 : ppg_restore_context(the_context);
418 :
419 : // Convert relative addresses to absolute addresses
420 : //
421 9 : the_context->pattern_root = (PPG_Token__*)((char*)context_c
422 9 : + (uintptr_t)the_context->pattern_root);
423 :
424 9 : ppg_token_traverse_tree(the_context->pattern_root,
425 : (PPG_Token_Tree_Visitor)ppg_compression_generate_absolute_addresses,
426 : NULL,
427 : (void *)context);
428 :
429 : // Reset the parent pointers
430 : //
431 9 : ppg_token_traverse_tree(the_context->pattern_root,
432 : (PPG_Token_Tree_Visitor)ppg_compression_restore_tree_relations,
433 : NULL,
434 : (void *)context);
435 :
436 : // printf("properties: %u\n", *((unsigned char*)&the_context->properties));
437 :
438 9 : PPG_ASSERT(the_context->properties.papageno_enabled);
439 9 : }
440 :
441 18 : void ppg_compression_write_c_output(PPG_Compression_Context__ *ccontext,
442 : char *name_tag)
443 : {
444 18 : printf("\n/*__PPG_START_OF_GENERATED_CODE__*/\n\n");
445 : // Start with writing the raw data
446 : //
447 : char context_name[100]/*, aux_name[100]*/;
448 :
449 18 : sprintf(context_name, "%s_context", name_tag);
450 : // sprintf(aux_name, "%s_context_aux", name_tag);
451 :
452 :
453 : // printf("properties before write: %d\n", *((int*)&((PPG_Context*)(ccontext->target_storage))->properties));
454 :
455 : // printf("Written at %lu\n", (size_t)((char*)&((PPG_Context*)(ccontext->target_storage))->properties - (char*)ccontext->target_storage));
456 :
457 18 : printf("/*\nSize of context %lu bytes\n\n", (unsigned long)ccontext->storage_size);
458 :
459 18 : printf("tree_depth: %d\n", (int)ppg_context->tree_depth);
460 18 : printf("layer: %d\n", (int)ppg_context->layer);
461 18 : printf("abort_input: %d\n", (int)ppg_context->abort_input);
462 18 : printf("time_last_event: %d\n", (int)ppg_context->time_last_event);
463 18 : printf("event_timeout: %d\n", (int)ppg_context->event_timeout);
464 :
465 18 : printf("*/\n\n");
466 :
467 18 : ppg_compression_write_c_char_array(context_name,
468 : ccontext->target_storage,
469 : ccontext->storage_size);
470 :
471 18 : printf("#define PPG_INITIALIZE_CONTEXT_%s \\\n", name_tag);
472 18 : printf(" \\\n");
473 :
474 : // printf(" ccontext->target_storage = %p\n", ccontext->target_storage);
475 :
476 746 : for(size_t i = 0; i < ccontext->n_symbols; ++i) {
477 :
478 : // printf(" ccontext->symbols[i] = %p\n", ccontext->symbols[i]);
479 :
480 728 : size_t offset = (char*)ccontext->symbols[i] - ccontext->target_storage;
481 :
482 : // Lookup the symbol name.
483 : //
484 : // TODO: Turn this inefficient linear search into something more
485 : // efficient by, e.g. sorting the buffer first
486 : // and then perform a binary search.
487 : //
488 728 : int s = ppg_compression_check_symbol_registered(ccontext, *ccontext->symbols[i]);
489 :
490 728 : if(s < 0) {
491 0 : PPG_ERROR("Unable to find symbol %p\n", *ccontext->symbols[i]);
492 : }
493 :
494 728 : PPG_ASSERT(s >= 0);
495 :
496 728 : printf(" *((uintptr_t*)&%s[%lu]) = (uintptr_t)&%s; \\\n", context_name, (long unsigned int)offset,
497 728 : ccontext->symbols_lookup.buffer[s].name
498 : );
499 : }
500 :
501 18 : printf(" \\\n");
502 18 : printf(" ppg_compression_setup_context(%s); \\\n",
503 : context_name/*, aux_name, aux_name*/);
504 :
505 18 : printf(" \\\n");
506 :
507 18 : printf(" ppg_global_set_current_context((void*)%s);\n", context_name);
508 18 : printf("\n/*__PPG_END_OF_GENERATED_CODE__*/\n");
509 18 : }
510 :
511 18 : void ppg_compression_run(PPG_Compression_Context ccontext,
512 : char *name_tag)
513 18 : {
514 18 : PPG_Compression_Context__ *ccontext__
515 : = (PPG_Compression_Context__ *)ccontext;
516 :
517 18 : size_t n_tokens = ppg_compression_allocate_target_buffer(ccontext__);
518 :
519 18 : ppg_compression_copy_context(ccontext__);
520 :
521 : // Use stack memory to hold symbol and vptr data
522 : ///
523 18 : void **symbols[4*n_tokens];
524 :
525 18 : ccontext__->symbols = symbols;
526 18 : ccontext__->n_symbols = 0;
527 18 : ccontext__->n_symbols_space = sizeof(symbols);
528 :
529 18 : ppg_compression_generate_dynamic_assignment_information(ccontext__);
530 :
531 : // Important: This must be done last, as it invalidates any pointers
532 : // of the token tree. Thus no tree traversal is possible afterwards.
533 : //
534 18 : ppg_compression_convert_all_addresses_to_relative(ccontext__);
535 :
536 : // Now the compression context is complete
537 :
538 18 : ppg_compression_write_c_output(ccontext__, name_tag);
539 18 : }
|